PaperlayerView exact revision on arXiv

Source-linked AI summary

More Adaptive Algorithms for Adversarial Bandits

Chen-Yu Wei, Haipeng Luo

arXiv:1801.03265v3cs.LGstat.ML

TL;DR

The paper addresses adaptive regret in adversarial bandits with partial feedback. It proposes a generic optimistic mirror-descent framework with a log-barrier regularizer and derives data-dependent bounds involving best-arm variance, path-lengths, negative terms, and stochastic gaps.

  • Problem

    Adversarial multi-armed bandits require minimizing regret when the learner observes only the selected arm's loss.

  • Method

    The paper develops a generic semi-bandit algorithm using optimistic mirror descent, a log-barrier regularizer, correction terms, and increasing learning rates.

  • Results

    The framework yields new adaptive expected-regret bounds based on the variance or path-length of the best arm, all-arm path-lengths with a negative term, and fixed stochastic gaps.

  • Takeaways & Limitations

    The resulting algorithms improve previous work, with parameter-free variants for some bounds and faster convergence rates in certain partial-feedback games.

  • Takeaways & Limitations

    The best-arm variance and best-arm path-length results require tuning a learning-rate parameter using unknown quantities; parameter-free versions remain open for those results.

Abstract

from arXiv · show

We develop a novel and generic algorithm for the adversarial multi-armed bandit problem (or more generally the combinatorial semi-bandit problem). When instantiated differently, our algorithm achieves various new data-dependent regret bounds improving previous work. Examples include: 1) a regret bound depending on the variance of only the best arm; 2) a regret bound depending on the first-order path-length of only the best arm; 3) a regret bound depending on the sum of first-order path-lengths of all arms as well as an important negative term, which together lead to faster convergence rates for some normal form games with partial feedback; 4) a regret bound that simultaneously implies small regret when the best arm has small loss and logarithmic regret when there exists an arm whose expected loss is always smaller than those of others by a fixed gap (e.g. the classic i.i.d. setting). In some cases, such as the last two results, our algorithm is completely parameter-free. The main idea of our algorithm is to apply the optimism and adaptivity techniques to the well-known Online Mirror Descent framework with a special log-barrier regularizer. The challenges are to come up with appropriate optimistic predictions and correction terms in this framework. Some of our results also crucially rely on using a sophisticated increasing learning rate schedule.

1. Introduction

The paper introduces a generic adversarial bandit algorithm whose instantiations yield adaptive, data-dependent regret bounds in the semi-bandit setting. These bounds cover best-arm variance and path-length measures, faster game convergence, and simultaneous small-loss and logarithmic-regret guarantees.

  • Contribution: The authors propose a generic bandit algorithm for the combinatorial semi-bandit setting, with multiple instantiations producing new data-dependent expected regret bounds.The framework specializes to MAB losses ℓt,i ∈ [−1, 1].
  • Adaptive bounds: The regret can depend on the unnormalized variance of only the best arm, rather than the average variance across all arms.The best-arm variance can be O(1) even when the average variance is Θ(T).
  • Adaptive bounds: The regret can depend on K times the first-order path-length of the best arm.This result requires tuning a learning-rate parameter to an unknown best-arm quantity.
  • Stochastic-style guarantees: Another bound simultaneously gives small regret when the best arm has small loss and logarithmic regret when an arm has a fixed expected-loss gap.The logarithmic guarantee applies beyond the simple i.i.d. setting and uses a parameter-free algorithm variant.
  • Method: The method combines Online Mirror Descent with a log-barrier regularizer, optimism, adaptivity, correction terms, and, for one result, an increasing learning-rate schedule.Using the log-barrier in the semi-bandit setting is described as new, and the combined analysis is non-trivial.

2. Problem Setup and Algorithm Overview

The paper formulates combinatorial semi-bandits with semi-bandit feedback and presents BROAD-OMD, a log-barrier OMD framework combining optimism, adaptivity, corrections, and time-varying regularization.

  • Problem Setup: In each round, the learner selects a subset of arms, incurs its summed loss, and observes losses only for selected arms.The action is a binary vector from a predefined action set, and the adversary is assumed oblivious.
  • Problem Setup: Regret measures the learner’s accumulated loss against the best fixed action in the action set.The classic MAB is the special case where each action selects exactly one arm.
  • Algorithm Overview: BROAD-OMD extends optimistic OMD with a log-barrier regularizer, auxiliary updates, and correction terms based on estimated losses.The learner samples from w_t, an optimistic update using m_t, while an auxiliary point uses the loss estimator and correction a_t.
  • Algorithm Overview: Table 1 summarizes BROAD-OMD configurations and MAB regret bounds, while the last two rows require a doubling trick for parameter-free algorithms.The table links specific framework choices to the resulting regret guarantees.
  • Algorithm Overview: The framework uses time-varying regularizers and learning rates, with sophisticated corrections for best-arm-dependent bounds and a_t = 0 for other results.The generic algorithm is instantiated through choices of m_t, loss estimators, corrections, and learning rates.
  • Algorithm Overview: Sampling and optimization are computationally tractable under polynomial constraint descriptions, with simpler solutions for MAB.For MAB, w_t directly gives arm probabilities and the optimization problems can be solved by binary search.

3. BROAD-OMD with Option I

BROAD-OMD combines Online Mirror Descent with a log-barrier regularizer, optimistic predictions, correction terms, and adaptive learning rates to obtain data-dependent regret bounds. Its instantiations yield bounds based on comparator-specific estimation error, best-arm variance, and best-arm path-length, while addressing bandit-feedback constraints.

  • General framework: The framework’s key comparator-dependent term is ⟨u, a_t⟩, enabling regret bounds that depend only on the comparator u.The algorithm must configure predictions and correction terms so the required condition holds while keeping this term controlled.
  • General framework: Inverse-propensity estimators can make squared estimation errors scale as 1/w_t,i^2, so BROAD-OMD uses a correction term 6η_t,i w_t,i(ℓ̂_t,i−m_t,i)^2.The factor w_t,i cancels the large inverse-propensity contribution in expectation, though it makes the required condition more stringent than with entropy regularization.
  • General framework: Corollary 3 shows expected regret depends only on squared estimation error for actions selected by the comparator, with dependence on K0 stated as optimal.Different estimator and prediction choices instantiate the general theorem into concrete adaptive bounds, including the MAB and semi-bandit settings.
  • 3.1. Variance Bound: The first application replaces dependence on T with the variance of only the best arm, unlike prior bounds using the average variance across all arms.The paper notes these quantities are incomparable and that best-arm variance can be O(1) while average variance is Θ(T).
  • 3.1. Variance Bound: With reservoir sampling, optimistic predictions use an unbiased estimate of the running mean, allowing the variance-bound construction despite unknown means and bandit feedback.Uniform exploration produces an estimator with E[μ̃_t]=μ_t and a stated variance control before setting m_t=μ̃_t−1.
  • 3.2. Path-length Bound: The path-length application obtains a slightly weaker first-order path-length bound because the desired second-order path-length target is difficult under bandit feedback.It uses the most recent observed loss as the optimistic prediction and an increasing individual learning-rate schedule, with thresholds and uniform exploration controlling small sampling probabilities.

4. BROAD-OMD with Option II

Option II sets a_t=0 in BROAD-OMD and derives regret bounds using log-barrier analysis, with path-length terms over all arms and a negative term. A doubling trick makes the resulting algorithm parameter-free and supports guarantees spanning adversarial and stochastic settings.

  • BROAD-OMD with Option II: Option II sets a_t=0 and analyzes BROAD-OMD with a log-barrier regularizer.The framework uses optimistic mirror descent updates with adaptive estimators and learning rates.
  • Parameter-free adaptation: A doubling trick restarts the algorithm when an observable quantity crosses a threshold, avoiding optimal prior tuning and making the algorithm parameter-free.This procedure is formalized as Algorithm 3 and underlies the parameter-free result.
  • Another Path-length Bound: The resulting path-length bound depends on the sum of first-order path-lengths of all arms rather than only the best arm.This bound does not require negative regret for the path-length calculation, but it can be worse or better depending on the instance.
  • Fast Convergence in Bandit Games: The regret bound also contains an additional negative term that can yield faster convergence rates in bandit-feedback games.The paper connects this term and path-length bounds to convergence rates for equilibrium computation.
  • Adapting to Stochastic Bandits: Under a fixed expected-loss gap, the stochastic model includes classic i.i.d. MAB as a special case, while the expected regret is measured against the empirically best arm.The stochastic assumption does not require independence or identical distributions.
  • Adapting to Stochastic Bandits: The same bound yields small-loss regret in adversarial settings and logarithmic regret in the stochastic setting when losses are non-negative.The paper emphasizes that the doubling trick is essential for the parameter-free guarantee.

5. Conclusions and Discussions

The paper develops and analyzes a general bandit framework based on optimism, adaptivity, log-barrier regularization, and increasing learning rates. Its instantiations produce adaptive regret bounds, while several extensions remain open.

  • Conclusions and Discussions: The framework combines optimistic mirror descent, a log-barrier regularizer, and increasing learning rates to obtain adaptive bandit algorithms.The paper presents these techniques as the basis of its general algorithm.
  • Conclusions and Discussions: The authors identify improving K-dependence for path-length bounds, obtaining second-order path-length bounds, and extending the method to linear bandits as future directions.These are stated as open directions rather than achieved results.

Appendix A. Proof of Lemma 1

The appendix develops technical lemmas for the two BROAD-OMD update rules under a log-barrier regularizer. These lemmas establish local optimality and stability properties used in later theorem proofs.

  • Appendix A. Proof of Lemma 1: The proof begins with a generic Online Mirror Descent optimality property for Bregman-proximal updates.Applying first-order optimality yields inequalities for both update rules.
  • Appendix A. Proof of Lemma 1: The appendix bounds instantaneous regret by combining the two update inequalities with the algorithm’s optimistic and correction terms.This produces the core one-step relation used in the main analysis.
  • Appendix A. Proof of Lemma 1: Under the log-barrier geometry, the auxiliary update remains in a local neighborhood of the current iterate.The stated stability relation compares local norms around the two iterates.
  • Appendix A. Proof of Lemma 1: Taylor expansion and boundary arguments establish membership of the next auxiliary iterate in the relevant local set.The proof checks the boundary and uses the assumed conditions to obtain the inclusion.
  • Appendix A. Proof of Lemma 1: The remaining lemmas apply these local stability results to BROAD-OMD in general convex domains and in the MAB setting.The appendix identifies the main theorem conditions needed for these applications.

Appendix C. Proof of Theorem 2 and Corollary 3

The proof of Theorem 2 verifies the required estimator and learning-rate conditions, then applies the master inequality to derive Corollary 3. The analysis controls correction-term expectations and discards non-positive contributions.

  • Appendix C. Proof of Theorem 2 and Corollary 3: The proof first establishes Equation (3) using the auxiliary lemmas for the log-barrier updates.This verifies the central condition required by Theorem 2.
  • Appendix C. Proof of Theorem 2 and Corollary 3: Applying Theorem 2 and ignoring non-positive −A_t terms yields the stated regret inequality.The proof then substitutes the selected learning rates and optimistic predictions.
  • Appendix C. Proof of Theorem 2 and Corollary 3: For Corollary 3, the proof checks the theorem conditions under the chosen η_t,i and ℓ̂_t,i before applying the theorem.The resulting bound is completed by selecting an appropriate comparator u.
  • Appendix C. Proof of Theorem 2 and Corollary 3: The analysis bounds the expected correction term and loss estimator using E[at,i]=O(η) and E[ℓ̂t,i]=O(1).These estimates control the per-round contributions in expectation.

Appendix D. Proof of Theorem 4

The proof separates uniformly sampled rounds from the remaining rounds and applies existing bounds to control the resulting terms. With M = Θ(ln T), the principal terms are bounded by O(QT,i∗ + 1), yielding an O(η(QT,i∗ + 1)) contribution.

  • Uniform-sampling rounds form a separate set S, and w′ is not updated on those rounds.
  • Corollary 3 is applied on rounds outside S to initiate the proof bound.
  • The second term of (19) is bounded by a constant using Lemma 18, so the second term of (18) is O(η(QT,i∗ + 1)).
  • M = Θ(ln T) makes the first and third terms of (19) each order O(QT,i∗ + 1).

Appendix E. Proof of Theorem 5

The proof of Theorem 5 relies on a logarithmically bounded number of learning-rate changes and separately bounds the terms arising in the regret decomposition. Lemma 19 provides the learning-rate control needed for these bounds.

  • Lemma 19 states that each arm’s learning rate changes at most log2 T times and remains at most 5η1,i.
  • The proof tracks the rounds at which each arm’s learning rate is multiplied by κ to establish the update-count bound.
  • Theorem 5 introduces τj as the last update round for arm j and assumes an update occurred, since otherwise the bound is trivial.
  • The proof converts an intermediate bound into the desired regret by controlling the remaining summation and taking expectations.

Appendix F. Proofs of Lemma 6 and Theorem 7

These proofs derive regret bounds through lemmas controlling the optimistic-gradient terms and the log-barrier potential, then extend the algorithm with a doubling-trick schedule. The resulting analysis verifies the conditions needed for the stated corollary.

  • Lemma 6 is used to expand instantaneous regret into analyzable terms for Theorem 7.
  • Theorem 7 bounds the second term using Lemmas 15 and 14 and lower-bounds the log-barrier quantity through h(y) = y−1−ln y.
  • The algorithm’s doubling-trick version restarts epochs by halving η when its break condition is met.
  • The epoch analysis bounds the cumulative optimistic loss, including the no-restart case and the case where a previous epoch finishes.
  • Corollary 9 is obtained by verifying Theorem 7’s conditions and substituting the stated upper and lower bounds while using E[B] = O(1).

Appendix I. Omitted Details in Section 4.1.1

The section applies BROAD-OMD to two-player zero-sum games with scalar bandit feedback. Using path-length terms that cancel between the players, the analysis establishes convergence faster than the standard 1/√T rate in the stated setting.

  • The discussion restricts attention to two-player zero-sum games, although generalization to multi-player games is described as straightforward.
  • Players repeatedly choose rows and columns from mixed strategies in an unknown matrix game, receiving scalar feedback for their realized actions.
  • Using Exp3 for both players yields expected average-strategy convergence to Nash equilibrium at rate 1/√T.
  • BROAD-OMD gives one player a path-length term closely related to the other player’s negative regret term, enabling cancellation and faster convergence.
  • Theorem 20 states that both players can run BROAD-OMD with ηt,i = η = (M + N)−1 to obtain the stated Nash-equilibrium convergence rate.
  • The resulting convergence remains slower than the 1/T full-information rate because the analysis uses first-order rather than second-order path-length bounds.

Appendix J. Proof of Theorem 10

The proof of Theorem 10 verifies the conditions required by Theorem 8, then derives stochastic and adversarial regret bounds from intermediate inequalities.

  • The proof verifies conditions (ii) and (iii) of Theorem 8 for the chosen predictions and estimates.It sets ˆℓt,i = ℓt,i and uses wt,i and mt,i in checking the conditions.
  • Theorem 8 is then applied to obtain the principal intermediate inequality for the proof.
  • Stochastic setting: The stochastic analysis takes expectations over ℓ1, . . . , ℓT and bounds the resulting terms using inequalities (27), (28), and (30).
  • Stochastic setting: The expected regret is subsequently upper bounded by the derived stochastic expression.
  • Adversarial setting: The adversarial analysis continues from an intermediate step of inequality (29), followed by algebraic rearrangement involving KLT,i∗ln T + K ln T.
Loading 1801.03265v3…