PaperlayerView exact revision on arXiv

Source-linked AI summary

Fighting Bandits with a New Kind of Smoothness

Jacob Abernethy, Chansoo Lee, Ambuj Tewari

arXiv:1512.04152v1cs.LGcs.GTstat.ML

TL;DR

Adversarial multi-armed bandits require learning from feedback about only the chosen action, motivating methods with worst-case regret guarantees. The paper unifies regularization and perturbation algorithms through convex smoothing and differential consistency. Tsallis regularization matches the minimax regret rate with a tighter constant, while bounded-tail-hazard perturbations achieve near-optimal regret matching EXP3.

  • Problem

    In adversarial multi-armed bandits, the learner sees only the selected action’s loss, making worst-case regret guarantees challenging.

    Source: §2 · p. 2

  • Method

    The paper unifies regularization and perturbation algorithms using a convex-smoothing analysis framework based on differential consistency.

    Source: §1 · p. 2, §2.2 · p. 4

  • Results

    Tsallis-entropy regularization matches the minimax regret rate of Audibert and Bubeck (2009) with a tighter constant, while bounded-tail-hazard perturbations achieve near-optimal regret matching EXP3.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The analysis connects perturbation-based bandit performance to the hazard rate of the smoothing distribution.

    Source: §4.2 · p. 7

    The authors conjecture that a monotonically increasing hazard rate that does not converge can permit a loss sequence with at least linear regret.

    Source: §4.2 · p. 7

Abstract

from arXiv · show

We define a novel family of algorithms for the adversarial multi-armed bandit problem, and provide a simple analysis technique based on convex smoothing. We prove two main results. First, we show that regularization via the \emph{Tsallis entropy}, which includes EXP3 as a special case, achieves the $\Theta(\sqrt{TN})$ minimax regret. Second, we show that a wide class of perturbation methods achieve a near-optimal regret as low as $O(\sqrt{TN \log N})$ if the perturbation distribution has a bounded hazard rate. For example, the Gumbel, Weibull, Frechet, Pareto, and Gamma distributions all satisfy this key property.

1 Introduction

Adversarial bandit research seeks worst-case regret guarantees despite feedback that reveals only the chosen action’s loss. This paper unifies regularization and perturbation methods through a new analysis framework, yielding results for Tsallis entropy and bounded-hazard perturbations.

1 Introduction

  • Earlier worst-case bandit work established nearly optimal regret for EXP3, while later online-linear-optimization guarantees extended to related settings.Earlier bandit results had relied on stochastic assumptions such as IID losses.Source: §1 · p. 1
  • FTRL uses a regularizer to stabilize its objective, whereas FTPL adds sampled noise to a linear optimization problem.FTPL is computationally simpler because its objective is linear, but its randomness has made analysis more complex.Source: §1 · pp. 1–2
  • The paper proposes differential consistency as a smoothing-based framework that unifies regularization and perturbation algorithms for adversarial bandits.It is presented as a route to a broad class of optimal and near-optimal algorithms.Source: §1 · p. 2
  • Tsallis-entropy regularization matches the minimax regret rate of Audibert and Bubeck (2009) with a tighter constant, and the resulting algorithm fully generalizes EXP3.The paper also identifies EXP3 with entropy regularization when the decision set is the probability simplex.Source: §1 · pp. 1–2
  • Perturbation methods achieve near-optimal regret matching EXP3 when their noise distribution has a bounded hazard rate in the tail.The authors conjecture this condition is both necessary and sufficient.Source: §1 · p. 2

2 Gradient-Based Prediction Algorithms for the Multi-Armed Bandit

In adversarial bandits, the learner observes only the selected action’s loss, and the paper studies a gradient-based template for this limited-feedback setting. Its central analysis idea is differential consistency, a stronger smoothness condition suited to the large loss-estimate increments that bandit feedback can produce.

2 Gradient-Based Prediction Algorithms for the Multi-Armed Bandit

  • The learner selects from N actions but observes only the loss of the sampled action, unlike in the full-information setting.The objective is to minimize regret against the best fixed action in hindsight.Source: §2 · p. 2

2.1 The Gradient-Based Algorithmic Template

  • GBPA maintains an unbiased cumulative-loss estimate and uses the gradient of a differentiable convex function as its sampling distribution.The template encompasses FTRL and FTPL, and inverse-probability scaling is inherent to unbiased estimation from partial observations.Source: §2.1 · p. 3

2.2 A New Kind of Smoothness

  • Differential consistency bounds smoothness in relation to the gradient because bandit loss estimates can grow as large as the inverse of the smallest action probability.A uniform Hessian bound is insufficient for the divergence terms in the regret analysis; the paper uses the stronger condition to derive a generic bound.Source: §2.2 · p. 4

3 A Minimax Bandit Algorithm via Tsallis Smoothing

The section reformulates a subfamily of INF using Tsallis entropy, placing EXP3 and power-potential methods in one framework. Its analysis gives a regret bound that recovers the 2√TN rate at a particular parameter choice, while α→1 recovers the EXP3 bound.

3 A Minimax Bandit Algorithm via Tsallis Smoothing

  • This reformulation covers a subfamily of INF that includes both EXP3’s exponential potential and a power potential with q > 1.It gives a natural interpolation between the two potential functions using an analysis based on differential consistency.Source: §3 · pp. 4–5
  • Tsallis entropy includes Shannon entropy as an asymptotic special case, and the section uses it in place of Shannon entropy for the GBPA potential.EXP3 is the GBPA instance whose potential is the Fenchel conjugate of Shannon entropy.Source: §3 · p. 5

4 Near-Optimal Bandit Algorithms via Stochastic Smoothing

The section develops stochastic smoothing as a way to analyze perturbation-based bandit algorithms. It connects the regret bound to the perturbation distribution’s hazard rate and gives a near-optimal regret guarantee for specified distributions.

4 Near-Optimal Bandit Algorithms via Stochastic Smoothing

  • Stochastic smoothing makes the expected maximum of perturbed coordinates convex, allowing differentiation to be exchanged with expectation under the stated conditions.The resulting gradient lies in the probability simplex, and unbounded support ensures each partial derivative is nonzero.Source: §4 · p. 6

4.1 Connection to Follow the Perturbed Leader

  • Sampling from the smoothed function is equivalent to bandit FTPL, while Geometric Resampling iteratively estimates its gradient when no closed-form expression is available.The sampling step is efficient, but estimating the gradient is generally difficult.Source: §4.1 · p. 6

4.2 Hazard Rate analysis

  • The analysis links GBPA performance to the smoothing distribution’s hazard rate, with divergence penalty at most N(sup hD) each round.The authors describe this connection as new to adversarial bandit algorithm design; convexity makes the underestimation penalty non-positive, while the overestimation penalty is bounded by the expected maximum perturbation.Source: §4.2 · p. 7
  • Theorem 4.2’s bound separates overestimation, underestimation, and divergence penalties, and scaling perturbations changes the hazard rate inversely with the scale.The proof uses convexity for the underestimation term and bounds the overestimation term by the expected maximum perturbation.Source: §4.2 · p. 7
  • O(√TN log N) expected regret is achieved by FTPL with distributions listed in Table 1 and Geometric Resampling with M set as specified in Corollary 4.4.The table’s scope is distributions that give this regret bound; its individual entries are not available in the supplied passage.Source: §4.2 · p. 7, Table 1 · p. 8
  • Conjecture 4.5 states that a monotonically increasing hazard rate that does not converge, as for Gaussian noise, permits a loss sequence causing at least linear regret.This is presented as a conjecture, not a proved result.Source: §4.2 · p. 7

A Proof of the GBPA Regret Bound (Lemma 2.1)

Lemma A.1 expresses Algorithm 2’s expected regret using overestimation and underestimation penalty terms.

A Proof of the GBPA Regret Bound (Lemma 2.1)

B Relaxing Assumptions on the Distribution

The appendix gives two ways to adapt perturbation distributions to the assumptions used in the analysis: mirror their support or condition away from small values.

B.1 Mirroring trick for extending the support

  • Mirroring a nonnegative random variable’s density around zero extends its support while preserving the distribution of its absolute value.The mirrored variable has density g(y) = 1/2 f(|y|).Source: §B.1 · pp. 10–11
  • The mirrored distribution’s hazard rate on the negative half-line is bounded by the original distribution’s hazard rate at the corresponding positive value.The lemma compares the hazard rates of X and its mirrored version Y.Source: §B.1 · pp. 10–11

B.2 Conditioning trick for unbounded hazard rate near zero

  • Conditioning on X > 1 removes a hazard-rate blow-up confined to small values when the hazard rate is bounded above 1.The conditioned variable’s hazard rate at y equals the original hazard rate at 1 + y; another positive conditioning threshold can be used.Source: §B.2 · p. 11

C Detailed derivation of extreme value behavior

The appendix characterizes maxima of iid Gumbel, Frechet, Weibull, and Gamma variables. These results describe how the maximum’s distribution or tail behaves as the number of variables grows.

C.1 Maximum of iid Gumbel

  • The maximum of N iid Gumbel variables is Gumbel with its mean increased by log N.A single Gumbel variable has mean γ0, the Euler–Mascheroni constant.Source: §C.1 · p. 11

C.2 Maximum of iid Frechet

  • For Frechet variables with α > 1, the maximum remains Frechet and its mean scales by N^(1/α).The mean is infinite when α is not greater than 1.Source: §C.2 · p. 11

C.3 Maximum of iid Weibull

  • For modified Weibull variables, the maximum’s tail is bounded by N exp(−(t + 1)^k + 1).The bound follows from P(max Xi > t) ≤ N P(X1 > t).Source: §C.3 · p. 11

C.4 Maximum of iid Gamma

  • The normalized maximum of N iid Gamma(α, β) variables follows a Gumbel distribution with specified centering and scale parameters.The passage identifies cN = β^−1 and dN = β^−1(log N + (α − 1) log log N − log Γ(α)).Source: §C.4 · p. 12

C.5 Maximum of iid Pareto

For modified Pareto variables, a union bound controls the tail of their maximum, yielding an upper bound on its expectation.

C.5 Maximum of iid Pareto

  • E[max_i X_i] ≤ (α/(α − 1))N^(1/α) for the modified Pareto variables.The tail bound is P(max_i X_i > t) ≤ N/(1 + t)^α.Source: §C.5 · p. 12

D.1 Pareto distribution

For α > 1, the modified Pareto distribution has a bounded hazard rate and an expected maximum that grows as N^(1/α).

D.1 Pareto distribution

  • The modified Pareto hazard is bounded by α, and the expected maximum of N iid variables is at most αN^(1/α)/(α − 1).The bound applies for α > 1; otherwise the mean is infinite.Source: §D.1 · p. 13

D.2 Frechet distribution

For α > 1, the Frechet distribution’s hazard rate is bounded, supporting an O(√(TN log N)) regret bound. The appendix bounds the hazard by treating x ≥ 1 and x < 1 separately.

D.2.1 Elementary calculations for bounding Frechet distribution’s hazard rate

  • For α > 1, the Frechet hazard rate is bounded above by 2α, established by separate bounds for x ≥ 1 and x < 1.For x < 1, the argument reduces to bounding y^(α+1) exp(−y^α) by 1.Source: §D.2 · p. 13, §D.2.1 · p. 13

D.2 Frechet distribution

  • O(√(TN log N)) regret follows for the Frechet perturbation, with the choice of α larger than 1 whenever N > 2.The maximum of N iid Frechet variables is Frechet with its mean scaled by N^(1/α).Source: §D.2 · p. 13

D.3 Weibull distribution

Modified Weibull distributions have bounded hazard rates and yield regret bounds determined by their parameter; the best bound occurs at the exponential case.

D.3 Weibull distribution

  • For k = 1/m, the modified Weibull hazard is bounded by k and the expected maximum scales as O(m!(log N)^m).For k < 1, its tails are heavier than exponential but lighter than Pareto or Frechet.Source: §D.3 · p. 14
  • The entire modified Weibull family yields O(√(TN)) regret bounds, with the best bound at m = 1, the exponential case.The unmodified Weibull hazard is unbounded for k > 1 at large x and for k < 1 at small x.Source: §D.3 · p. 14

Related papers

Loading 1512.04152v1…