Source-linked AI summary
Better Algorithms for Stochastic Bandits with Adversarial Corruptions
Anupam Gupta, Tomer Koren, Kunal Talwar
TL;DR
The paper asks whether stochastic bandit guarantees can remain strong under adversarially corrupted feedback. It proposes BARBAR, an algorithm that adapts without knowing the corruption level, and reports substantially improved regret guarantees with little degradation under significant corruption; the analysis still leaves a gap between Ω(C) and O(KC).
Problem
The problem is to obtain stochastic-bandit guarantees that degrade smoothly as adversarial corruption increases.
Method
BARBAR is an agnostic algorithm for stochastic multi-armed bandits with adversarial corruptions.
Results
BARBAR removes the multiplicative dependence on C in existing bounds, replacing it with an additive dependence while tolerating corruption up to C = O(T/K).
Takeaways & Limitations
The layered design bounds corruption impact by retaining recourse for arms and using only immediately preceding-epoch information.
Takeaways & Limitations
The remaining gap is between the lower bound Ω(C) and the upper bound O(KC).
Abstract
from arXiv · showhide
We study the stochastic multi-armed bandits problem in the presence of adversarial corruption. We present a new algorithm for this problem whose regret is nearly optimal, substantially improving upon previous work. Our algorithm is agnostic to the level of adversarial contamination and can tolerate a significant amount of corruption with virtually no degradation in performance.
1 Introduction
The paper studies stochastic multi-armed bandits whose feedback can be adversarially corrupted, seeking guarantees that retain stochastic performance while tolerating contamination. It introduces BARBAR, an agnostic algorithm whose corruption dependence is additive rather than multiplicative and that remains effective at substantial corruption levels.
- Motivation: Adversarial bandit algorithms are robust but typically sacrifice the logarithmic-in-T regret available in stochastic bandits.This motivates guarantees that degrade smoothly between stochastic and adversarial settings.
- Motivation: Adversarial corruption can cause standard stochastic algorithms such as UCB and AAE to eliminate the true best arm.The resulting failure can produce severe regret even with a small amount of corruption.
- Our results: BARBAR adapts through multiple layers: faster layers are more corruption-sensitive, while slower layers are more robust.This layered design automatically adapts to the amount of adversarial contamination without knowing C in advance.
- Our results: BARBAR removes the multiplicative dependence on C in prior bounds and replaces it with an additive dependence.The algorithm is entirely agnostic to the corruption level and is described as extremely simple.
- Our results: In the uncorrupted case, the new result recovers classical stochastic regret bounds up to a logarithmic factor.The paper also states robustness up to C = O(T/K), with essentially the same regret as in the uncorrupted case.
2 Setup: Stochastic MAB with Adversarial Corruptions
The setup combines stochastic arm rewards with adversarially corrupted feedback over T rounds. The player is evaluated by pseudo-regret while remaining agnostic to the corruption level C.
- Model: The problem has K arms with unknown reward distributions, means µ_i, a unique best arm i⋆, and gaps ∆_i = µ⋆ − µ_i.Rewards are supported in [0,1].
- Interaction: On each round, stochastic rewards are generated, the adversary produces corrupted rewards, and the player selects an arm and observes its corrupted feedback.The adversary observes the reward vector before generating corrupted rewards.
- Objective: The player’s performance is measured using the standard pseudo-regret metric for stochastic multi-armed bandits.The paper notes that its results extend to several other regret notions.
- Adversary: The corruption level C measures the adversary’s total corruption, but the main setting assumes C is unknown to the player.The adversary may be adaptive based on past choices and observed stochastic rewards, but not the player’s choice on the same round.
3 The BARBAR Algorithm
BARBAR adapts the stochastic-bandit elimination strategy to adversarial corruption by using exponentially growing epochs, conservative gap estimates, and continued sampling of apparently inferior arms. Its analysis establishes a high-probability regret bound for the resulting algorithm.
- Algorithm design: BARBAR modifies Active Arm Elimination to remain robust to adversarial corruptions.The algorithm is named Bandit Algorithm with Robustness: Bad Arms get Recourse.
- Epoch structure: Epoch lengths grow roughly as 2^2m, and each epoch estimates arm gaps using information from the immediately preceding epoch.The algorithm biases sampling toward seemingly better arms.
- Guarantee: With probability at least 1 − δ, Theorem 1 bounds the regret of Algorithm 1.The proof decomposes regret across epochs, arms, and the three cases determined by estimated gaps and corruption.
- Guarantee: The algorithm’s analysis is essentially tight because an Appendix B instance yields Ω(KC) regret.The corresponding expected-regret conversion sets δ = 1/T and contributes only O(1) from the failure event.
- Analysis: The analysis controls reward estimates and arm-pull counts using Chernoff-Hoeffding and Freedman-type concentration inequalities.The proof conditions on an event E that holds simultaneously across arms and epochs with high probability.
4 Better Bounds for Special Cases
Additional assumptions improve BARBAR’s main corruption-dependent term from O(KC) to approximately O~(C). These cases include known corruption, known optimal mean, and other restricted corruption settings, while the general improvement remains open.
- Special-case bounds: Under several additional assumptions, the first regret term improves from O(KC) to O~(C).The authors present these cases as evidence that a better general bound may be achievable.
- Random corruption: If corruption occurs independently and uniformly with probability η each round, the setting is equivalent to adversarial perturbations of the arm means by ±η.The value of η may be unknown to the player.
- Known corruption: When C is known, Active Arm Elimination can use epochs of length at least Ω(C + 2^m log(K/δ)) to maintain accurate empirical estimates.The cited argument states that an arm with gap ∆_i ≥ 2^-m can then be eliminated.
- Early corruption: When the corruption is confined to the first C steps, restarting AAE on exponentially scheduled intervals gives an improved regret bound for unknown C.The supplied passage states this construction but truncates the displayed bound.
- Known gap: If the minimal gap ∆ is known, a variant plays the previous epoch’s winner extensively while sampling every other arm according to the gap estimate.The supplied passages state that this variant yields a similarly improved bound.
- Known optimal mean: If the optimal mean µ⋆ is known, the total regret is bounded by O(C) plus an additional logarithmic-order term.The supplied result explicitly attributes the O(C) contribution to corruption across epochs.
5 Discussion
The discussion establishes an Ω(C) lower bound for pseudo-regret and explains how alternative regret notions behave under corruption. It also identifies a gap between the algorithm’s Ω(C) lower bound and O(KC) upper bound.
- 5.1 A Lower bound: Ω(C) pseudo-regret is unavoidable for all C up to T/2, even when C is known.The lower-bound construction uses two deterministic arms and corruption that makes them indistinguishable.
- 5.2 Alternative notions of regret: The paper’s pseudo-regret upper bounds transfer to realized regret with respect to actual corrupted rewards, up to a logarithmic factor.The discussion states that high-probability pseudo-regret bounds imply corresponding high-probability realized-regret bounds.
- 5.2 Alternative notions of regret: For regret restricted to uncorrupted steps, the upper bounds and Ω(C) lower bound extend directly, ruling out o(C) regret for any C.This notion matches motivating settings where corrupted rewards are not of interest.
- 5.2 Alternative notions of regret: For realized regret on corrupted rewards, adversarial algorithms can achieve O(√(KT))-type bounds, while stochastic guarantees face corruption-dependent lower bounds.On the lower-bound instance, adversarial algorithms balance linear inlier regret against linear negative outlier regret.
- 5.3 Open questions: The work leaves open closing the gap between its Ω(C) lower bound and O(KC) upper bound, improving log^2 T dependence, and extending results beyond multi-armed bandits.The stated extensions include linear and contextual bandits.
A Concentration Inequalities
The analysis uses multiplicative concentration inequalities to obtain sharper rates for random variables with small expectations, including variants of Chernoff–Hoeffding and Freedman bounds.
- Multiplicative concentration inequalities provide sharper rates for random variables with small expectations.
- The section states a multiplicative Chernoff–Hoeffding bound for independent [0,1]-valued random variables.
- It also records a Freedman martingale concentration inequality for martingale difference sequences.
- The Freedman variant assumes bounded increments, with |X_t| ≤ b, and defines a cumulative variance quantity V.
B Tightness of Our Analysis
A constructed instance shows that the analysis’s first regret term is tight: corrupting the optimal arm in one epoch causes a subsequent epoch to incur regret approximately (K−1)C.
- The example uses one optimal arm with mean reward 1 and all other arms with mean reward 0.
- 15 ∈ [14/15, 15/16], so an uncorrupted epoch has length N_m = λ(2^{2(m−1)} + O(K)).
- Setting C = N_c and corrupting the optimal arm throughout epoch c removes the information gathered in earlier epochs.
- (K − 1)C regret arises in the next epoch, demonstrating that the analysis requires a factor of K multiplying the C term.
C From Pseudo-regret to Regret
The analysis converts a high-probability pseudo-regret bound into a high-probability realized-regret bound using concentration inequalities and auxiliary quantities. The resulting guarantee holds with probability at least 1 − 2δ, with an additional O(B) bound when the relevant quantity is constant.
- The result applies to regret defined using uncorrupted rewards; the corrupted-reward version differs by at most an additive O(C) in the worst case.
- Pseudo regret sums each suboptimal arm’s pull count T_i weighted by its gap Δ_i, while realized regret measures reward differences directly.
- Starting from Pr(R ≤ B) ≥ 1 − δ, the argument assumes B ≥ max_{i≠i⋆} 1/Δ_i and introduces an auxiliary quantity.
- Azuma’s inequality separately controls R⋆ − R, while Hölder’s inequality is applied to the other difference, R′ − R⋆.
- The pseudo-regret bound implies R = Σ_{i≠i⋆} T_iΔ_i ≤ B with probability at least 1 − δ.
- The conversion yields a probability of at least 1 − 2δ, and when the relevant bound is constant, the resulting quantity is at most O(B).