PaperlayerView exact revision on arXiv

Source-linked AI summary

Tsallis-INF: An Optimal Algorithm for Stochastic and Adversarial Bandits

Julian Zimmert, Yevgeny Seldin

arXiv:1807.07623v6cs.LGstat.ML

TL;DR

The paper addresses whether one bandit algorithm can achieve optimal stochastic and adversarial pseudo-regret without knowing the regime. It proposes Tsallis-INF and shows simultaneous optimality, while extending the analysis to self-bounding adversaries and related settings.

  • Problem

    Whether optimal stochastic and adversarial pseudo-regret can be achieved simultaneously without prior knowledge of the regime has remained open.

  • Method

    The paper uses online mirror descent with Tsallis entropy regularization, focusing on α=1/2, and introduces a self-bounding adversarial regime.

  • Results

    Tsallis-INF achieves optimal logarithmic stochastic pseudo-regret and optimal square-root adversarial regret simultaneously without prior regime knowledge.

  • Takeaways & Limitations

    The analysis closes logarithmic gaps to lower bounds and covers stochastically constrained adversaries and adversarially corrupted stochastic bandits as special cases.

  • Takeaways & Limitations

    The analysis assumes a unique best arm, although experiments suggest this technical assumption may be an artifact of the proof.

Abstract

from arXiv · show

We derive an algorithm that achieves the optimal (within constants) pseudo-regret in both adversarial and stochastic multi-armed bandits without prior knowledge of the regime and time horizon. The algorithm is based on online mirror descent (OMD) with Tsallis entropy regularization with power $α=1/2$ and reduced-variance loss estimators. More generally, we define an adversarial regime with a self-bounding constraint, which includes stochastic regime, stochastically constrained adversarial regime (Wei and Luo), and stochastic regime with adversarial corruptions (Lykouris et al.) as special cases, and show that the algorithm achieves logarithmic regret guarantee in this regime and all of its special cases simultaneously with the adversarial regret guarantee.} The algorithm also achieves adversarial and stochastic optimality in the utility-based dueling bandit setting. We provide empirical evaluation of the algorithm demonstrating that it significantly outperforms UCB1 and EXP3 in stochastic environments. We also provide examples of adversarial environments, where UCB1 and Thompson Sampling exhibit almost linear regret, whereas our algorithm suffers only logarithmic regret. To the best of our knowledge, this is the first example demonstrating vulnerability of Thompson Sampling in adversarial environments. Last, but not least, we present a general stochastic analysis and a general adversarial analysis of OMD algorithms with Tsallis entropy regularization for $α\in[0,1]$ and explain the reason why $α=1/2$ works best.

1. Introduction

The paper addresses whether one bandit algorithm can achieve optimal stochastic and adversarial pseudo-regret without knowing the regime. Tsallis-INF answers yes while extending logarithmic guarantees to a self-bounded adversarial regime and related settings.

  • Method: Tsallis-INF uses online mirror descent with Tsallis entropy regularization, with α = 1/2 as its key specialization.The algorithm is anytime and requires neither the time horizon nor doubling schemes.
  • Motivation and contribution: The paper resolves an open question by achieving optimal logarithmic stochastic pseudo-regret and optimal square-root adversarial regret simultaneously without prior regime knowledge.This guarantee concerns pseudo-regret, which is weaker than expected regret.
  • Guarantees: With reduced-variance estimators, the stochastic leading constant is within a factor of 2 of the Lai–Robbins lower bound, while the adversarial constant is within a factor below 15 of the minimax lower bound.These factors are reported for the corresponding regret bounds.
  • Intermediate regimes: A self-bounding adversarial regime includes stochastic, stochastically constrained adversarial, and adversarially corrupted stochastic regimes; Tsallis-INF achieves logarithmic regret there.The paper also reports an improved regret bound for adversarially corrupted stochastic regimes.
  • Extensions: Tsallis-INF also achieves stochastic and adversarial optimality for utility-based dueling bandits.This extension uses a Sparring framework.
  • Empirical evaluation: Empirically, Tsallis-INF outperforms standard baselines in several stochastic and stochastically constrained adversarial environments, while Thompson Sampling can suffer almost linear regret adversarially.In stochastic environments it is only slightly worse than Thompson Sampling and significantly better than the other listed competitors.

2. Problem Setting

The paper formalizes stochastic, adaptive adversarial, and intermediate bandit environments through losses and pseudo-regret. A self-bounding constraint unifies several regimes, including stochastic and corrupted stochastic settings.

  • Bandit model: At each round, the agent selects one of K arms, receives its loss, and observes only that played-arm loss.The environment supplies a loss vector in [0,1]^K.
  • Performance measure: Pseudo-regret compares the algorithm with a best arm in expectation, with expectation over the algorithm’s and environment’s internal randomization.The best arm is defined in hindsight in expectation.
  • Adversarial regime: In the adaptive adversarial setting, losses may be selected arbitrarily based on prior actions and the adversary’s internal randomization.For deterministic oblivious adversaries, pseudo-regret coincides with expected regret.
  • Self-bounding constraint: A self-bounding constraint requires the adversary’s cumulative losses to satisfy a regret-related condition at time T, without requiring it at every earlier time.The constraint is parameterized by Δ, C, and T.
  • Stochastic regime: The stochastic regime has time-independent loss means and satisfies the self-bounding condition with suboptimality gaps Δ_i and C = 0.The same best arm applies across rounds, allowing one arm to be selected as i* when ties occur.
  • Intermediate regimes: Stochastically constrained adversarial losses have fixed expected pairwise gaps, although distributional means and other parameters may change with time and depend on past actions.Stochastic bandits with adversarial corruptions are also treated as a special case of the self-bounding regime.

3. Online Mirror Descent

Tsallis-INF applies online mirror descent with time-varying Tsallis-entropy regularization to bandit loss estimates. Importance weighting supplies unbiased estimates, while reduced-variance estimators and simplex-constrained updates define the practical framework.

  • Online mirror descent: Online mirror descent updates arm weights from cumulative estimated losses using the gradient of a regularizer’s convex conjugate.The framework supports time-varying regularizers and weighted cumulative losses.
  • Loss estimation: Because bandit feedback reveals only the played loss, the algorithm uses unbiased importance-weighted estimates to update cumulative losses.These estimates replace the unobserved complete loss vector.
  • Reduced-variance estimators: Reduced-variance importance-weighted estimators remain unbiased for any baseline B_t(i) in [0,1] and minimize worst-case estimator variance when the baseline is chosen appropriately.They can nevertheless take negative values.
  • Implementation: The algorithm’s weights solve a constrained optimization problem on the probability simplex, with normalization determined implicitly and approximated efficiently by Newton’s method.Algorithm 1 initializes cumulative estimated losses at the zero vector; Algorithm 2 computes the normalization factor.
  • Tsallis regularization: Tsallis-INF regularizes with the negative α-Tsallis entropy family, whose limiting cases connect to log-barrier and negative Shannon entropy regularization.The paper studies α in [0,1].
  • Regularization choices: Symmetric regularization uses ξ_i = 1, whereas stochastic analysis for α ≠ 1/2 uses asymmetric weights ξ_i = Δ_i^(1−2α).The asymmetric choice depends on unknown gaps and is therefore mainly theoretical.

4. Main Results

Tsallis-INF with α = 1/2 achieves optimal pseudo-regret scaling in adversarial and stochastic bandits without prior regime knowledge, using a self-bounding analysis that also covers intermediate environments.

  • Tsallis-INF with α = 1/2 achieves optimal regret bounds in both adversarial and stochastic bandits.The stochastic guarantee follows as a special case of the self-bounding analysis.
  • The algorithm combines online mirror descent with Tsallis entropy regularization and importance-weighted or reduced-variance loss estimators.The reduced-variance estimator improves constants without changing regret rates.
  • The adversarial guarantee has T regret scaling, while self-bounded environments receive logarithmic regret scaling.Stochastic and stochastically constrained adversarial regimes are included as special cases.
  • The reduced-variance stochastic bound is within a multiplicative factor of 2 of the asymptotic Lai–Robbins lower bound.The paper describes this as optimal within that multiplicative factor.
  • The reduced-variance adversarial bound is within a multiplicative factor of less than 15 of the minimax lower bound.The paper identifies its leading constant as the tightest adversarial guarantee known at the time.
  • The proofs assume a unique best arm, although experiments suggest this assumption may be an artifact of the analysis.The paper conjectures that the uniqueness requirement can be removed.
  • For α ≠ 1/2, the analyzed Tsallis-INF versions do not achieve simultaneous stochastic and adversarial optimality.The general analysis explains why α = 1/2 works best, while the two analyses use different regularizations.

5. Additional Intermediate Regimes Between Stochastic and Adversarial

The self-bounding framework covers adversarial corruptions of stochastically constrained environments, yielding logarithmic regret for logarithmic corruption, while related regimes remain unresolved.

  • 5.1 Stochastic Bandits with Adversarial Corruptions: Tsallis-INF achieves logarithmic regret in the corrupted self-bounding regime.The resulting corollary improves upon bounds by Lykouris et al. and Gupta et al., though those works differ in assumptions and guarantee type.
  • 5.1 Stochastic Bandits with Adversarial Corruptions: Stochastically constrained adversaries with adaptive corruption are a special case of self-bounding environments with parameters (∆, 2C, T).The underlying adversary has gaps ∆ and corruption amount bounded by C.
  • 5.1 Stochastic Bandits with Adversarial Corruptions: After adaptive corruption, the best-arm identity may change and multiple best arms may appear.Uniqueness is required only for the stochastically constrained adversary before corruption.
  • 5.2 Open Problem: The Performance in Seldin and Slivkins’ Environments: Tsallis-INF has not been shown to achieve logarithmic regret in Seldin and Slivkins’ intermediate regimes.The paper notes that an earlier analysis was incorrect and identifies cumulative-gap definitions as a challenge.

6. Dueling Bandits

Sparring with two Tsallis-INF instances extends the algorithm’s stochastic and adversarial guarantees to utility-based dueling bandits.

  • Utility-based dueling bandits select two arms and observe the winner of their duel.Utilities are fixed in the stochastic setting and can be time dependent in the adversarial setting.
  • Sparring runs two black-box MAB algorithms, with each receiving loss based on whether its selected arm wins.Its regret is the sum of the individual MAB regret values.
  • In stochastic Sparring, each black-box MAB faces a stochastically constrained adversarial environment because the baseline shifts with the partner’s arm choice.Earlier Sparring analyses lacked a stochastic guarantee because no algorithm was known to achieve logarithmic regret in that setting.
  • Applying Tsallis-INF in Sparring achieves stochastic and adversarial optimality in utility-based dueling bandits.The result is stated for two independent Tsallis-INF versions.

7. Proofs

The proofs use standard OMD potential decomposition, refined stability and penalty bounds, and the self-bounding constraint to obtain stochastic guarantees while retaining adversarial analysis.

  • Proof framework: OMD decomposes regret into stability and penalty terms through a potential function.The potential is Φ_t(−L)=max_{w∈∆K−1}{⟨w,−L⟩−Ψ_t(w)}.
  • Proof framework: For α-Tsallis regularizers, f(x) and g(x) scale as x^(1−α) and x^α; at α=1/2, both scale as √x.The analysis chooses a corresponding decreasing learning-rate schedule.
  • Stochastic analysis: The stochastic analysis constrains the maximization using the self-bounding property, excluding the worst-case √T regret scenario.For C=0, the constraint gives a lower bound on regret in terms of expected suboptimal-arm play, enabling logarithmic control.
  • Assumption: The analysis assumes a unique best arm because the current refinement can eliminate only one arm from the regret bound.Multiple zero-gap arms would lack negative contributions that control their expected play.
  • Key lemmas: Separate stability and penalty lemmas support analyses with importance-weighted and reduced-variance estimators across α∈[0,1].The refined stability inequalities are used for adversarial, self-bounding, and estimator-specific results.
  • Key lemmas: The refined bounds exploit negative contributions from the best-arm regularizer term and exclude the best arm from a summation.This refinement produces an added linear term controlled by ˜f(x)=f(x)+c′x≤(1+c′)f(x).

8. Experiments

Experiments compare Tsallis-INF with standard stochastic and adversarial bandit algorithms in stochastic, stochastically constrained adversarial, and multiple-optimal-arm settings. Tsallis-INF with reduced-variance estimators performs strongly across these environments, while UCB1 and Thompson Sampling can incur almost linear regret under shifting means.

  • Experimental protocol: The experiments estimate pseudo-regret over 100 repetitions and display two standard deviations using shaded areas.Plots show the first 10000 time steps linearly and later steps from 10^4 to 10^7 on log-log axes.
  • Standard stochastic MAB: In the standard stochastic MAB, Tsallis-INF with reduced-variance estimators closely follows Thompson Sampling and outperforms the other competitors by a large margin.The experiment varies the number of arms K and gap ∆, with one optimal arm having mean reward (1 + ∆)/2 and suboptimal arms (1 − ∆)/2.
  • Stochastically constrained adversaries: In stochastically constrained adversarial environments, UCB1 and Thompson Sampling suffer almost linear regret, whereas the other algorithms are almost unaffected by shifting means.The environment alternates between two stochastic settings whose phase lengths increase exponentially.
  • Regret behavior: Tsallis-INF with importance-weighted estimators achieves logarithmic regret in both stochastic and stochastically constrained adversarial environments.Reduced-variance estimators significantly improve the constants in both experiments.
  • Multiple optimal arms: With multiple optimal arms, the empirical regret does not increase when the number of optimal-arm copies grows and decreases as the number of suboptimal arms grows.This experiment uses one suboptimal arm with mean loss 9/16 and optimal arms with mean loss 7/16.

9. Discussion

The discussion presents Tsallis-INF as simultaneously optimal across adversarial and stochastic settings, while extending the analysis to broader regimes and dueling bandits. It also identifies assumptions and open questions for future work.

  • Main conclusions: The α = 1/2 Tsallis-INF algorithm achieves optimality in both adversarial and stochastic regimes without knowing the environment.The analysis closes logarithmic gaps to existing best-of-both-worlds lower bounds.
  • Generalized regime: A self-bounding adversarial regime includes stochastic, stochastically constrained adversarial, and adversarially corrupted stochastic bandits as special cases.The algorithm provides logarithmic pseudo-regret in this regime together with adversarial regret guarantees.
  • Extensions: Tsallis-INF is applicable to utility-based dueling bandits, where it achieves stochastic and adversarial optimality.
  • Limitations: The analysis assumes a unique zero entry among adversarial suboptimality gaps, corresponding to a unique best arm in stochastic settings.The authors suggest this assumption is likely an artifact of the analysis and plan to address it in future work.
  • Future directions: Open questions include closing the remaining factor-2 gap, establishing logarithmic regret in intermediate regimes, and applying Tsallis-INF to other problems.The authors note that importance-weighted losses make the method suitable for partial monitoring games.

Appendix A. Asymptotic Lower Bound

The appendix derives an asymptotic lower bound for consistent stochastic-bandit algorithms by bounding the relevant KL term and related summations.

  • KL bound: For suboptimality gaps Δ_i ∈ [0, 0.5], the appendix upper-bounds the KL term using a Taylor expansion around Δ_i = 0.
  • Lower bound: The resulting lower bound applies to any consistent algorithm in the stated stochastic setting.
  • Technical bounds: The appendix bounds auxiliary sums and terms involving square-root time dependencies using explicit estimates and the Riemann zeta function.It also states lemmas covering monotonicity, limits, and finite-horizon inequalities.
  • General inequalities: The technical lemmas establish inequalities for functions parameterized by α ∈ [0, 1], including limit conventions at α = 1 and z = 1.

Appendix C. Support Lemmas for Section 7

The support lemmas develop analytic properties of the Tsallis-entropy OMD potential and its optimization map, with particular refinements for α = 1/2.

  • Notation and potential: The appendix introduces vector, diagonal-matrix, and canonical-norm notation used in the OMD analysis.
  • Optimization map: The potential is treated through its Legendre properties, so its gradient is invertible and supports the algorithm’s probability computation.
  • Optimization map: The Bregman divergence associated with a Legendre function is used as part of the potential-based analysis.
  • Stability: The appendix separately controls the stability term and derives a tighter bound for reduced-variance estimators when α = 1/2.
  • Stability: The analysis includes monotonicity properties in α and conditions ensuring the estimator-dependent quantities remain in the required range.

Proof

The proof section assembles convexity, unbiasedness, conjugate-potential identities, and stability and penalty bounds to establish the OMD analysis.

  • Proof assembly: The proof combines intermediate inequalities and stability bounds to complete the main stability lemma.
  • Stability analysis: The proof controls stability through bounds on the convex conjugate and the Hessian of the Tsallis potential.
  • Probability characterization: The proof uses a Lagrange multiplier to characterize the probabilities selected by the constrained potential optimization.
  • Stability analysis: Several stability cases use convexity, Jensen’s inequality, non-negativity of importance-weighted estimators, and bounded losses.
  • Penalty analysis: The penalty analysis applies a standard lemma to bound potential differences and then uses estimator unbiasedness to relate estimated and actual cumulative losses.

Appendix D. Proof of Theorem 4

The proof of Theorem 4 bounds stability, concave, linear, and penalty terms using lemmas, Taylor approximations, and a threshold T0. It then combines these bounds and rearranges the resulting inequalities to complete the proof.

  • The proof uses learning rate η_t = 16α and treats the limit cases α ∈ {0, 1} with a more technical argument.
  • Bounding the stability term: The stability term is bounded separately before and after a threshold T0 chosen so that η_T0ξ_i ≤ 1.
  • Bounding the concave part: The concave terms are upper bounded using first-order Taylor approximations for w^(1−α) and w^α.
  • Finishing the proof: After combining the intermediate inequalities, the proof rearranges the terms and multiplies by 4 to obtain the theorem’s conclusion.
  • Bounding the penalty term: The proof bounds the penalty term with Lemma 12 and uses Lemma 14 to control remaining factors and logarithmic terms.
Loading 1807.07623v6…