Skip to content

A Near-optimal, Scalable and Parallelizable Framework for Stochastic Bandits Robust to Adversarial Corruptions and Beyond

🕒 Published (v1): 2025-01-01 · Source: NeurIPS · Venue: NeurIPS 2025 · link

Ask a follow-up

Open an assistant pre-loaded with this paper's context.

💬 Ask ChatGPT✦ Ask Claude

TL;DR

BARBAT (Bad Arms get Recourse, Best Arm gets Trust) is an elimination-based bandit framework that resolves an open problem by achieving near-optimal O(C + Σ log(T)/Δk) regret against adversarial corruptions, eliminating the O(KC) factor of prior work BARBAR. The framework extends cleanly to multi-agent, batched, graph, and semi-bandit settings, with advantages in computational efficiency and parallelizability over FTRL-based alternatives.

Problem

The prior state-of-the-art elimination-based algorithm BARBAR achieves regret O(KC + Σ 1/Δk) under adversarial corruptions of level C, which is suboptimal by a factor of K relative to the Ω(C) lower bound. FTRL-based methods achieve optimal regret but require solving a constrained convex optimization each round (expensive in semi-bandit settings), assume a unique optimal arm, and resist parallelization — making them unsuitable for multi-agent and batched settings.

Method

BARBAT uses static, data-independent epoch lengths Nm = O(K·2^{2(m-1)}), preventing the adversary from exploiting dynamic epoch lengths to inflate pulls of suboptimal arms (the mechanism by which BARBAR incurs the K factor). Within epoch m, per-arm pull counts nm_k = O(1/Δ^{m-1}_k)^2 are maintained, and all remaining pulls in the epoch are assigned to the current estimated best arm k_m. Epoch-varying failure probabilities δm ≈ O(1/(mK·2^{2m})) — rather than a global δ — tighten the confidence bounds and eliminate dependence on the horizon T. Extensions adapt the epoch structure and arm-selection logic to: (1) MA-BARBAT — agents share epoch-end reward sums with O(V log(VT)) total communication; (2) BB-BARBAT — epoch lengths scaled to match L batches, each epoch serving as one batch; (3) SOG-BARBAT — computes an out-domination set of the feedback graph to satisfy per-arm observation requirements; (4) DS-BARBAT — tracks the top-d arms as the estimated optimal action.

Key Contributions

  • BARBAT framework: resolves the open problem of optimal elimination-based bandits under adversarial corruption; achieves O(C + Σ_{Δk>0} log(T)/Δk + K log²(1/Δ)/Δ) regret without prior knowledge of T.
  • MA-BARBAT: cooperative multi-agent extension; individual regret reduced by factor V with communication cost O(V log(VT)).
  • BB-BARBAT: first robust algorithm for batched bandits with adversarial corruptions; includes a matching lower bound Ω(T^{1/L}·K + C^{1-1/L}).
  • SOG-BARBAT: strongly-observable directed graph bandits; improves corruption term from O(αC) to O(C) vs. prior work; does not require prior knowledge of independence number α.
  • DS-BARBAT: d-set semi-bandits; computationally faster than FTRL methods (no convex solve per round); near-optimal regret O(dC + Σ log(T)/Δk).
  • All methods drop the unique-optimal-arm assumption required by FTRL counterparts.

Results

  • Multi-agent (V=10): MA-BARBAT outperforms DRAA, IND-BARBAR, IND-FTRL on K∈{12,16}, C∈{2000,5000}; smallest regret increase when C is raised (robustness advantage).
  • Graph bandits: SOG-BARBAT significantly outperforms Shannon-FTRL and Tsallis-FTRL on directed graphs with K∈{12,16}, C∈{2000,5000}.
  • Semi-bandits (d=3 for K=12, d=4 for K=16): DS-BARBAT significantly outperforms HYBRID, LBINF, LBINF_LS, LBINF_GD; also faster per Table 3 (Appendix).
  • All 50-trial averages with standard deviations; no batched bandit empirical comparison presented (algorithm is novel for this setting).

Limitations

  • Regret bound contains an extra T-independent term K log²(1/Δ)/Δ not present in FTRL bounds; gap from O(log²T) to O(log T) remains open.
  • BB-BARBAT has a gap between its upper bound O(CT^{1/(L+3)} + T^{4/(L+3)} · ...) and lower bound Ω(T^{1/L}·K + C^{1-1/L}).
  • No extension to linear bandits or contextual bandits is provided.
  • MA-BARBAT achieves o(log T) communication only under the unique-best-arm assumption, which the authors drop — their O(log(VT)) cost per agent may be suboptimal.
  • All experiments are synthetic; no real-world or corrupted-reward scenario from practice is validated.

Relevance to Agentic AI / LLM Agents

This work is relevant to multi-agent decision-making under adversarial interference — a foundational concern in deployments where agents operate in partially adversarial environments (e.g., tool-call reward signals that may be poisoned, feedback from untrusted oracles, or manipulated human ratings in RLHF). The MA-BARBAT extension directly addresses how cooperative agents should pool information to maintain robust, near-optimal exploration when a shared adversary corrupts observed rewards, a model applicable to multi-agent LLM systems coordinating on sequentially chosen actions. The batched bandit extension maps onto settings where agents receive feedback only after completing a task batch (e.g., batch RL fine-tuning or offline feedback loops). The computational efficiency advantage over FTRL — no per-round convex solve — is practical for resource-constrained agent deployments.