Source-linked AI summary
Online Bandit Learning against an Adaptive Adversary: from Regret to Policy Regret
Raman Arora, Ofer Dekel, Ambuj Tewari
TL;DR
Standard regret becomes inadequate when adversaries adapt to the learner’s actions, so the paper defines policy regret as a more meaningful comparator. It proves impossibility with unbounded adversary memory and uses mini-batching to obtain sublinear policy regret for bounded-memory adversaries.
Problem
Standard regret can compare the player with a competitor under an infeasible adversary response, making its meaning unclear against adaptive adversaries.
Method
The paper defines policy regret and wraps any bandit algorithm in a mini-batching procedure that repeats actions and supplies averaged batch losses.
Results
No bandit algorithm guarantees sublinear policy regret against unbounded-memory adaptive adversaries, whereas bounded memory enables sublinear bounds, including O(T^2/3) for mini-batched EXP3.
Takeaways & Limitations
Policy regret provides a comparator aligned with action-dependent adversary responses, and mini-batching transfers sublinear regret guarantees to bounded-memory adaptive settings.
Takeaways & Limitations
The paper leaves policy-regret lower bounds and the necessity of mini-batching as open questions.
Abstract
from arXiv · showhide
Online learning algorithms are designed to learn even when their input is generated by an adversary. The widely-accepted formal definition of an online algorithm's ability to learn is the game-theoretic notion of regret. We argue that the standard definition of regret becomes inadequate if the adversary is allowed to adapt to the online algorithm's actions. We define the alternative notion of policy regret, which attempts to provide a more meaningful way to measure an online algorithm's performance against adaptive adversaries. Focusing on the online bandit setting, we show that no bandit algorithm can guarantee a sublinear policy regret against an adaptive adversary with unbounded memory. On the other hand, if the adversary's memory is bounded, we present a general technique that converts any bandit algorithm with a sublinear regret bound into an algorithm with a sublinear policy regret bound. We extend this result to other variants of regret, such as switching regret, internal regret, and swap regret.
1. Introduction
The paper argues that standard regret loses its intuitive meaning against adaptive adversaries because its comparator assumes the adversary reacts to the player’s sequence even when a competitor is secretly played. It introduces policy regret and develops bandit methods for bounded-memory adversaries.
- Online bandit setting: Bandit learning models repeated action choices against loss functions, with the player observing only the loss of the selected action.The player updates its strategy from observed loss values while seeking to minimize cumulative loss.
- Standard regret: Standard external pseudo-regret compares cumulative player loss with the best deterministic action sequence in a competitor class.For an oblivious adversary, this difference has the intuitive interpretation of regretting the chosen action sequence.
- Standard regret: Adaptive adversaries make standard regret problematic because its comparator evaluates a competitor under losses generated in response to the player’s original sequence.The resulting baseline describes an infeasible situation in which the adversary reacts to one sequence while the competitor secretly plays another.
- Policy regret: Policy regret compares the player’s loss with the loss that would have occurred had the player actually played the best competitor sequence.This definition captures that an adaptive adversary may respond differently to different action sequences.
- Main results: The paper shows that no bandit algorithm guarantees sublinear policy regret against an adaptive adversary with unbounded memory.With bounded adversary memory, mini-batching converts any bandit algorithm with regret O(T^q) into policy regret O(T^(1/(2−q))).
- Main results: The general technique extends beyond constant-action bandit competitors to switching regret, internal regret, and swap regret.The paper positions this as a general transformation rather than a result for only one concrete algorithm.
2. Policy regret
Policy regret exposes failures of standard regret against adaptive adversaries, while bounded adversary memory enables mini-batching reductions from sublinear regret to sublinear policy regret.
- For oblivious adversaries, the resulting policy-regret bound coincides with the standard regret bound.
- Ω(T) policy regret is unavoidable for some adaptive adversary when competing against the best constant action sequence.The construction yields expected policy regret at least pT while standard regret remains zero.
- An adaptive adversary can make standard regret misleading by reacting to the player’s first action while favoring a different constant sequence.This separates low standard regret from actually learning good actions.
- An m-memory-bounded adversary depends only on the m + 1 most recent actions, with oblivious and fully adaptive adversaries corresponding to memory bounds 0 and ∞.Switching friction costs provide a natural 1-memory-bounded example.
- Mini-batching transforms any algorithm with sublinear standard regret against adaptive adversaries into an algorithm with sublinear policy regret against m-memory-bounded adversaries.The transformed algorithm repeats one sampled action for each batch and need not know m, although m appears in the analysis.
- The reduction uses batch size τ greater than m and yields an overall policy-regret bound of τR(T/τ)+Tm/τ+τ.For R(J)=CJ^q+o(J^q), the bound specializes to the paper’s stated asymptotic form.
3. Applying the Result
The general conversion technique yields sublinear policy-regret guarantees for mini-batched bandit algorithms against memory-bounded adaptive adversaries. It applies across k-armed bandits, bandit convex optimization, bandit linear optimization, and bandit submodular minimization.
- k-armed bandit: O(T^2/3) policy regret is obtained for mini-batched EXP3 against an m-memory-bounded adaptive adversary.The batch size is τ = (7k log k)^-1/3T^1/3, and the bound is (m + 1)(7k log k)^1/3T^2/3 + o(T^2/3).
- Bandit convex optimization: The conversion technique is applied to bandit convex optimization using the regret guarantee of Flaxman, Kalai, and McMahan’s algorithm.The supplied passages specify the mini-batch construction and parameters but do not include the resulting policy-regret expression.
- Bandit linear optimization: O(T^3/4) policy regret is obtained for mini-batched McMahan and Blum’s algorithm in bandit linear optimization.With τ = (15d)^-3/4T^1/4, the bound is (m + 1)(15dT)^3/4 + o(T^3/4).
- Bandit submodular minimization: O(T^3/4) policy regret is obtained for mini-batched Hazan and Kale’s algorithm in bandit submodular minimization.With τ = (12k)^-3/4T^1/4, the bound is (m + 1)(12kT)^3/4 + o(T^3/4).
4. Extensions
The paper extends the mini-batching conversion beyond constant competitors to known-memory settings, switching competitors, and Φ-regret. These extensions preserve policy-regret guarantees under appropriate regret assumptions.
- General extensions: Theorem 2 can require only a regret bound against 1-memory-bounded adversaries rather than arbitrary adaptive adversaries.The proof uses the condition τ > m and the induced mini-batch loss sequence.
- When m is Known: When m is known, omitting the first m rounds of each mini-batch makes the induced sequence 0-memory-bounded.This means the original algorithm’s regret guarantee need only hold against oblivious adversaries, while choosing τ using m can reduce its dependence in policy-regret bounds.
- When m is Known: For bandit linear optimization with known m, the paper gives a policy-regret bound for a mini-batched algorithm whose original regret guarantee holds against oblivious adversaries.The construction uses the Abernethy, Hazan, and Rakhlin algorithm, ignores the first m loss values in each mini-batch, and applies for T > 8ϑ log T.
- Switching Competitors: The conversion extends from constant-action competitors to piece-wise constant sequences with at most s switches.At most s batches are affected by competitor switches, contributing an additional sτ term because losses are bounded.
- Switching Competitors: O(T^2/3) policy regret is obtained for mini-batched EXP3.S against sequences with at most s switches and an m-memory-bounded adaptive adversary.The stated bound is 7ks log(kT) 1/3T^2/3 + O(T^1/3).
- Switching Competitors: The same approach can provide switching guarantees in bandit convex optimization when regret guarantees under action switches are available.The paper notes that related extensions were discussed but not explicitly derived by Flaxman et al.
- Internal Regret, Swap Regret, Φ-Regret: Theorem 6 bounds policy Φ-regret by τR(T/τ) + Tm/τ + τ for any transformation set Φ under an m-memory-bounded adaptive adversary.This follows by repeating the conversion technique when the base algorithm’s Φ-regret is bounded by R(J).
- Internal Regret, Swap Regret, Φ-Regret: An external-regret-to-internal-regret conversion can be combined with the paper’s technique to obtain internal policy-regret bounds.The paper states that this applies to the online learning algorithms discussed in the paper.
5. Discussion
The paper argues that policy regret better captures regret against adaptive adversaries and establishes non-trivial upper bounds for several bandit algorithms. However, the tightness of these bounds remains unknown, and the necessity of mini-batching is unresolved.
- The paper defines policy regret to capture the adversary’s potentially different responses to different action sequences.
- Non-trivial upper bounds are proved for various bandit algorithms.
- Lower bounds are absent in both bandit and full-information settings, so the tightness of the upper bounds is unknown.
- It remains possible that algorithms designed specifically for policy regret could achieve superior bounds, but this has not been shown.
- The necessity of mini-batching is unresolved because a non-trivial policy-regret bound for unmodified EXP3 may still be possible.