PaperlayerView exact revision on arXiv

Source-linked AI summary

Does 1/2-Tsallis-INF Also Work Well for Best-Arm Identification?

Jingxin Zhan, Yuze Han, Zhihua Zhang

arXiv:2608.15365v1cs.LG

TL;DR

Can 1/2-Tsallis-INF identify the best arm reliably without additional exploration, despite being designed for regret minimization? Using toy diffusion models and a Lyapunov-function analysis, the paper proves polynomial failure decay with an essentially tight exponent of 2.

  • Problem

    Whether 1/2-Tsallis-INF can reliably identify the best arm without additional exploration remains unclear beyond its regret guarantees.

  • Method

    The paper analyzes the estimated-loss gap using diffusion toy models and constructs a Lyapunov function to control importance-weighted fluctuations.

  • Results

    The failure probability decays as t^-2+α^2μ_i*/4+ρ, approaches t^-2 as α→0, and a lower bound shows that exponent 2 is essentially tight.

  • Takeaways & Limitations

    The paper provides a first BAI guarantee for an FTRL method using the original algorithm without explicit exploration.

  • Takeaways & Limitations

    The analysis assumes i.i.d. stochastic losses with a unique optimal arm, and importance-weighted variance can become uncontrolled when the estimated gap is substantially negative.

Abstract

from arXiv · show

Regret minimization (RM) and best-arm identification (BAI) are two fundamental objectives in multi-armed bandits. Among regret-minimizing algorithms, $1/2$-Tsallis-INF is a canonical best-of-both-worlds FTRL algorithm: it achieves logarithmic pseudo-regret in stochastic bandits while retaining minimax-optimal regret in adversarial bandits, without knowing the environment in advance. This raises a natural question: can the same algorithm, without additional exploration, also identify the best arm reliably? We study this question in stochastic bandits by analyzing the failure probability $\operatorname{Err}_t$, defined as the probability that the empirical best arm determined by the cumulative importance-weighted loss estimates of 1/2-Tsallis-INF differs from the true optimal arm. The main difficulty is that, at the logarithmic-regret scale, suboptimal arms are sampled with probability heuristically of order $1/t$. Consequently, importance weighting causes the cumulative estimator to fluctuate on the same linear scale as its mean separation. To overcome this obstacle, guided by a diffusion toy model, we construct a Lyapunov function for the gap process between the estimated cumulative loss of the optimal arm and that of the best competing arm. This leads to polynomial upper bounds on $\operatorname{Err}_t$: for learning rate $η_t=α/\sqrt t$, $\operatorname{Err}_t$ decays at rate $t^{-2+α^2μ_{i_*}/4+ρ}$ for any $ρ>0$, where $μ_{i_*}$ denotes the mean loss of the true optimal arm. We also establish a lower bound $Ω(t^{-2-\varepsilon})$ for any $\varepsilon>0$, showing that the exponent $2$ is essentially tight.

1 Introduction

The paper asks whether unmodified 1/2-Tsallis-INF can identify the best arm in stochastic bandits while retaining its best-of-both-worlds design. It proves polynomial failure-probability bounds despite importance-weighted fluctuations, with exponent 2 essentially tight.

  • Motivation: 1/2-Tsallis-INF is studied as a best-of-both-worlds FTRL algorithm for best-arm identification without additional exploration.The analysis targets stochastic bandits while using the algorithm’s original importance-weighted cumulative loss estimates.
  • Problem formulation: The failure probability Err_t is the probability that the empirical minimizer of estimated cumulative losses differs from the unique optimal arm.This criterion differs from standard regret analysis, which evaluates cumulative loss incurred by the sampling distribution.
  • Technical obstacle: Importance weighting creates high variance because suboptimal arms are heuristically sampled with probability 1/t, causing estimator fluctuations comparable to their mean separation.This prevents direct reliance on concentration arguments for empirical means.
  • Main result: t^-2+α^2μ_i*/4+ρ bounds Err_t for learning rate η_t=α/√t and any ρ>0, without modifying the algorithm or adding exploration.The rate approaches t^-2 as α tends to zero.
  • Main result: t^-2 is essentially tight, established through a Lyapunov analysis of the estimated loss-gap process guided by diffusion and discrete toy models.The toy models expose the drift–variance balance and the origin of exponent 2.

2 Preliminaries

The paper formulates stochastic multi-armed bandits with unknown i.i.d. losses and analyzes 1/2-Tsallis-INF within the FTRL framework. Failure analysis uses importance-weighted cumulative loss estimates and reduces identification errors to the sign of an optimal-versus-best-suboptimal gap.

  • Problem formulation: The stochastic bandit has d arms, i.i.d. loss vectors in [0, 1]^d, unknown means μ_i, and a unique optimal arm i_* minimizing expected loss.Each suboptimality gap is Δ_i = μ_i − μ_i_*.
  • Problem formulation: The learner observes and suffers only the selected arm’s loss, so cumulative losses are updated using an unbiased importance-weighted estimator.The estimated cumulative losses are denoted by ˆL_t.
  • Failure characterization: The failure probability Err_t is the probability that the empirical best arm from cumulative estimated losses differs from the true optimal arm.The empirical best arm is defined through the minimum estimated cumulative loss.
  • Failure characterization: The gap D_t compares the optimal arm’s estimated cumulative loss with the smallest estimated cumulative loss among suboptimal arms, and Err_t analysis reduces to whether D_t is positive.This gap is defined using N_t, the minimum cumulative estimated loss over suboptimal arms.
  • FTRL policy: FTRL selects arms using a probability vector determined by the learning rate η_t and a convex regularizer Ψ.The paper focuses on 1/2-Tsallis-INF, which uses Ψ(p) = −4∑_i√p_i and satisfies the BOBW guarantee.

3 Main Results

The main results establish polynomial upper and lower bounds for the failure probability Err_t of 1/2-Tsallis-INF’s unmodified importance-weighted estimator. The upper rate depends on the learning-rate coefficient, while the lower bound shows that exponent 2 is essentially tight.

  • Upper bound: Err_t decays at least as t^-q for any q < 2 − α^2μ_i*/4 under a unique optimal arm and α ∈ (0, 1).The bound holds for every t ≥ 1, with constants depending on α, q, and an arbitrarily small ρ > 0.
  • Upper bound: t^-2+α^2μ_i*/4+ρ is the stated failure-probability decay rate when η_t = α/√t, with ρ > 0 arbitrarily small.This quantifies how the learning-rate coefficient affects the polynomial exponent.
  • Proof strategy: The analysis overcomes importance-weighted estimator variance of order t by constructing a Lyapunov function for the estimated loss-gap process.A diffusion approximation and Itô’s formula guide the construction of the Lyapunov function used in the proof.
  • Lower bound: t^-2 is the fastest possible polynomial decay rate up to t^ε factors: for every ε > 0, Err_t has a lower bound Ω(t^-2-ε).This lower bound is nearly tight with the upper bound as α approaches 0.
  • Scope: The proof techniques suggest that analogous upper and lower bounds may extend to the general θ-Tsallis-INF algorithm.The paper does not establish this extension directly.

4 Construction of the Lyapunov Function

The section constructs the Lyapunov function by simplifying the estimated-loss gap through two toy models and seeking a nonnegative function that grows polynomially while remaining uniformly integrable. A diffusion-based analysis motivates its form, while discrete-model moment behavior forces the exponent choice m = 2.

  • Lyapunov-function requirements: The construction targets a nonnegative gt satisfying polynomial growth on y ≥ 0 and a uniformly bounded expectation of gt(Dt).These are Properties (P1) and (P2), with Dt the gap between the optimal arm’s estimator and the best competing arm’s estimator.
  • Toy-model simplification: The analysis first replaces the non-optimal arm’s estimated cumulative loss by its mean, then develops discrete- and continuous-time toy models for the resulting gap process.The continuous model replaces a discrete martingale increment with a Gaussian fluctuation having matching drift and variance order, enabling Itô-based analysis.
  • Diffusion-based ansatz: The diffusion analysis seeks gt(Yt) as a supermartingale, using a coordinate shift and separated time-space solutions to derive compatible positive- and negative-half-line branches.The positive branch is motivated by power-law spatial solutions, while the negative branch is matched at the interface to preserve smoothness.
  • Choice of exponent: For m > 2, the discrete increment’s higher moments can make E_t[gt+1(Yt+1)]/gt(Yt) arbitrarily large, so gt(Yt) cannot be a supermartingale.This obstruction is absent from the Gaussian toy model because it retains only the first two moments of the increment.
  • Choice of exponent: m = 2 maximizes the admissible growth exponent q among choices m ≤ 2 and also yields a particularly simple Lyapunov function for subsequent analysis.The rate is governed by q ≤ m − θ ≤ m − α^2m(m−1)/8, whose relevant upper bound increases through m = 2.

5 Proof Sketch of the Upper Bound

The upper-bound proof sketch addresses why the toy-model supermartingale argument fails in the full bandit setting and introduces growth and case-splitting arguments to control the gap process. A key lemma ensures growth of the best competing estimate when the gap is not too negative, while the complementary regime is handled because the Lyapunov function is already small.

  • Proof obstacles: The toy-model supermartingale argument becomes difficult in the actual bandit model because the best competing estimate need not increase every round and importance-weighted estimates can have excessive variance.With more than two arms, tied minimum estimates cannot all increase when only one arm is selected; when the gap is strongly negative, suboptimal-arm sampling probabilities become very small.
  • Controlling competitor growth: Lemma 5.1 guarantees that, when the gap is not too negative, the best competing estimate grows by a constant amount after sufficiently many rounds.The lemma applies for sufficiently large L and under the stated condition involving d and L.
  • Controlling competitor growth: L is chosen of order d log(d)/∆^2 to handle the difficulty that the best competing estimate may fail to grow steadily.The proof of this growth result is deferred to Appendix E, which also contains additional results describing the growth of the competing estimate.
  • Case analysis: The analysis splits according to whether the gap exceeds the threshold −√t/α: above it, the Lyapunov argument applies, while below it, the Lyapunov function is already small.For sufficiently large L, sufficiently small λ, and sufficiently large t, the two cases combine to bound the expected Lyapunov function and yield the theorem.

6 Proof Sketch of the Lower Bound

The lower-bound proof constructs iterated stopping times whose positive-probability occurrence keeps the gap process positive over expanding intervals. This yields a lower bound on the failure probability with asymptotic exponent −2.

  • 6 Proof Sketch of the Lower Bound: The proof of Theorem 3.3 is based on Lemma 6.1, which constructs stopping times satisfying growth, positivity, and finite-probability properties.The lemma assumes 0 < α < 1 and μ_i∗ > 0, with B chosen above a universal threshold.
  • 6 Proof Sketch of the Lower Bound: Iterating Lemma 6.1 gives stopping times τ_k whose occurrence probabilities decrease geometrically with k.The construction starts from a time satisfying the required interval condition and defines τ_k recursively.
  • 6 Proof Sketch of the Lower Bound: Choosing k logarithmically in t converts the stopping-time probability bound into the asymptotic exponent log(a_B) → −2.A rigorous version of this stopping-time argument is deferred to Appendix B.
  • 6 Proof Sketch of the Lower Bound: On the event {τ_k < +∞}, the stopping-time growth and gap positivity imply D_t > 0 throughout an interval extending to approximately a_B^kτ_0.This persistent positivity is the event used to lower-bound the probability of empirical-best-arm failure.

7 Concluding Remarks · Appendix

The paper analyzes best-arm identification for 1/2-Tsallis-INF without explicit exploration. It proves polynomial error decay and a nearly tight exponent-2 lower bound using toy models and a Lyapunov-function approach.

  • 7 Concluding Remarks: The study analyzes best-arm identification for the classical best-of-both-worlds algorithm 1/2-Tsallis-INF.It considers whether this FTRL method can identify the true optimal arm without explicit exploration.
  • 7 Concluding Remarks: For η_t = α/√t, the empirical-best-arm error probability decays as t^-2+α^2μ_i*/4+ρ for any ρ > 0.The error event is that the empirical best arm differs from the true optimal arm.
  • 7 Concluding Remarks: This provides, to the authors’ knowledge, the first best-arm-identification guarantee for an FTRL method without explicit exploration.The guarantee concerns the decay of the probability that the empirical best arm differs from the true optimal arm.
  • 7 Concluding Remarks: The corresponding lower bound indicates that the rate t^-2 is essentially tight.Thus, the upper-bound exponent is matched up to arbitrarily small slack in the stated sense.
  • 7 Concluding Remarks: The analysis addresses high variance through two new toy models and a Lyapunov-function-based approach.These tools are introduced to overcome the technical difficulty caused by importance-weighted estimation variance.
  • 7 Concluding Remarks: The paper suggests that the introduced technical tools may be useful beyond this analysis.The passage specifically identifies the toy models and Lyapunov-function approach as potentially useful methods.

A Proof of Theorem 3.2

The section proves Theorem 3.2 by analyzing the gap process separately on positive and negative half-lines. A grid-based supermartingale and stopping-time argument controls the process uniformly for all t ≥ N, completing the theorem.

  • Proof of Lemma A.1: The proof analyzes the gap process D_t in two cases, according to whether D_t ≥ 0 or lies on the negative half-line.The auxiliary increment U_t balances the means by comparing Δ(t + L) + D_{t+L} with Δt + D_t.
  • Conclusion: The final substitutions and absorptions yield the claimed bound, which proves Theorem 3.2.The theorem concerns t ≥ N; earlier times are handled directly using Err_t ≤ 1 in the surrounding argument.
  • Gridwise control: E[H_{j+1} | G_j] ≤ H_j, so the gridwise process H_j is a nonnegative supermartingale under the conditions of Lemma A.1.The grid spacing L enables application of Lemma A.1 after fixing a residue class.
  • Uniform bound: For every t ≥ N, the argument represents t uniquely on one of the L residue-class grids and combines the resulting estimates with an initial-time bound.The proof separately bounds E[g_{N+r}(D_{N+r})] for 0 ≤ r < L before substituting λ, L, and N.
  • Stopping-time argument: A stopping-time decomposition controls the difficult term involving H_j 1{X_j ∈ M_j} by partitioning grid indices according to whether the target region is reached.The resulting bounds are converted from a grid union bound into a series over stopping times.

B Proof of Theorem 3.3

This section completes the proof of Theorem 3.3 by establishing a suitable start time and then formalizing the stopping-time argument. The proof shows that the required stopping-time sequence is valid and begins with positive probability, enabling the theorem’s conclusion.

  • Establishing the start time: The event F has positive probability, proving that the required start-time condition holds for some T ≥ Cd^2.F combines selecting the optimal arm through round T′ − 1 with not selecting it through rounds T′ to T′′.
  • Formal stopping-time construction: The recursively defined sequence (τ_k) is inductively shown to consist of stopping times satisfying τ_k ≥ T + k − 1.The induction uses measurability together with Lemma 6.1 to establish both the stopping-time property and the lower bound on each τ_k.
  • Formal stopping-time construction: At each stopping time, the normalized gap remains within [v_B, V_B], and P(τ_0 < +∞) > 0.The interval property follows from the definition of τ_0 and Lemma 6.1, while positivity follows from Lemma B.1.
  • Completing Theorem 3.3: For every t ≥ T, the stopping-time construction selects an index k ensuring t ≤ (T − 1)a_k, after which the proof lower-bounds the desired quantity using Eq. (50).The argument first establishes D_t > 0 over the relevant intervals and then chooses k = ⌈log_{a_B}(t/(T − 1))⌉.

C Proof of Lemma 6.1

The section proves Lemma 6.1 by defining a stopping time τ(t) and establishing its measurability, the stated properties, and the probability bound through conditional decomposition and tower-property arguments.

  • Stopping-time definition: τ(t) is a stopping time with respect to (F_s)_{s≥1}.The proof checks that each event defining {τ(t)=t′} is measurable in F_{t′}.
  • Proof of item (2): D_{t′} remains positive, with D_{t′} ≥ B t′ > 0.This follows from D_{t′} ≥ D_t − 4d(t′−t) and the lower bound implied by τ(t).
  • Proof of item (3): Item (3) is proved by decomposing the probability according to σ(t) and controlling each term using the tower property.The proof introduces A_k = {σ(t) ≥ k} and recursively lower-bounds conditional probabilities of avoiding the optimal arm.
  • Proof completion: The proof concludes after summing the bounds over k from m−(t)+1 through m+(t), with parameter constraints deferred to Appendix H.2.The final summation uses Eq. (65), while the admissibility of t and B is verified separately.

D Important Facts … H Verification of the parameter constraints

The appendices establish structural facts about the estimated-loss process, derive growth and moment bounds needed for the main proofs, and verify the parameter constraints used in Theorem 3.2 and Lemma 6.1.

  • D Important Facts: For Algorithm 1 with 0 < α < 1, Lemma D.6 provides a constant Cα > 0 depending only on α for all t ≥1.This is one of the section’s principal auxiliary results.
  • D Important Facts: P(F) > 0 for the event F defined in Eq. (46), as established by Lemma D.7.The proof constructs positive-probability events through two inductions.
  • E Growth of Nt: The growth analysis lower-bounds Nt+L − Nt by restricting attention to near-minimal suboptimal arms and controlling their centered importance-weighted fluctuations.The relevant arms have larger selection probabilities and lower estimator variance, while Freedman-type bounds control negative deviations.
  • F.1 The positive half-line: The positive-half-line argument yields a forward bound for st by iterating its recurrence and absorbing lower-order terms when t is sufficiently large.Lemma F.2 takes Cα = 1 + α2/4, and Lemma F.3 propagates the bound over L steps.
  • G Auxiliary Lemmas: The auxiliary lemmas compare the two branches of gt, construct stopped supermartingales, and bound sums involving f(x) = xq e−λ√x.These tools support the stopping-time and Lyapunov arguments.
  • No independence is required. Define: The probabilistic toolkit requires no independence for the conditional moment bounds, uses exponential-moment control for bounded centered variables, and includes a one-sided Freedman inequality.The auxiliary results also establish divergence properties for a recursive sequence and positivity criteria for nonnegative random variables.
  • H Verification of the parameter constraints: The final section verifies the parameter constraints appearing in the proofs of Theorem 3.2 and Lemma 6.1.No additional quantitative condition is visible in the supplied passage.

H.1 Verification for Theorem 3.2

The section verifies that the parameter choices and sufficiently large constants satisfy all conditions required by Theorem 3.2. It also checks the lower bounds on N and concludes the theorem’s verification.

  • H.1 Verification for Theorem 3.2: The prescribed parameter choices, with C sufficiently small and Cα,q,ρ sufficiently large, verify the stated constraints and equations.These choices establish Eq. (31), the λ-constraint and remaining condition in Eq. (33), and Eq. (19).
  • H.1 Verification for Theorem 3.2: The remaining verification concerns the lower bounds on N.The argument uses d ≥ 2 and 0 < ∆ ≤ 1 before enlarging C′ if necessary.
  • H.1 Verification for Theorem 3.2: After increasing C′α,q,ρ if necessary, the constraints in Eqs. (17), (21), and (23), along with Eqs. (27) and (34), all hold.The same choice also verifies N ≥ L and ∆2N ≥ d.
  • H.1 Verification for Theorem 3.2: These checks complete the verification of Theorem 3.2.The conclusion follows after establishing every listed parameter and lower-bound condition.

H.2 Verification for Lemma 6.1

The verification of Lemma 6.1 proceeds by choosing the universal constant C sufficiently large so that the required parameter inequalities hold. These choices establish the cited equations and complete the lemma’s verification.

  • Parameter choices: Choosing C sufficiently large ensures B ≥ 8d, Cd^2 ≥ 144d^2, V_B ≥ 8d, and aB > 1.These inequalities imply Eqs. (58), (57), and (56).
  • Completion: For sufficiently large B, the remaining bounds establish Eqs. (63), (69), (68), and (64), completing the verification of Lemma 6.1.The argument also uses B ≥ α^-1 and B ≥ 16 to derive Eq. (69).
  • Intermediate bounds: The same parameter choices, together with D_t/B > 42, establish Eqs. (54) and (71).The verification explicitly derives Eq. (54) and then confirms Eq. (71).
Loading 2608.15365v1…