Research map / Bandits and online learning / Multi-armed bandits

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

NeurIPS 2026 · Bandits and online learning › Multi-armed bandits · approach: Fixed-confidence versus fixed-budget identification · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Shows that the unmodified 1/2-Tsallis-INF FTRL bandit algorithm, whose importance-weighted cumulative loss estimates identify the empirical best arm, has best-arm identification failure probability decaying polynomially at rate about t^{-2+alpha^2 mu/4+rho}, with a matching-order lower bound of t^{-2-eps}.

Problem

Whether the best-of-both-worlds 1/2-Tsallis-INF algorithm, without extra exploration, identifies the best arm reliably from its importance-weighted cumulative loss estimates in stochastic bandits; i.e., the decay rate of the failure probability Err_t.

Approach

Guided by diffusion and discrete toy models of the estimated loss gap, construct a Lyapunov function g_t (quadratic on the positive side, exponential on the negative side) whose expectation is bounded and is a supermartingale-like quantity, yielding polynomial failure bounds for the unmodified IW estimator.

Key results

• Upper bound: for eta_t=alpha/sqrt(t), Err_t <= C t^{-q} for any q < 2 - alpha^2 mu_{i*}/4, i.e., rate t^{-2+alpha^2 mu_{i*}/4+rho}.
• Lower bound: Err_t >= C' t^{-2-eps} for any eps>0 under 0<alpha<1 and mu_{i*}>0, so exponent 2 is essentially tight (approached as alpha->0).

Surprising findings

• The upper-bound exponent depends on alpha so that smaller learning-rate constants give faster decay approaching t^{-2}, the opposite of intuition about learning rates.

Limitations

• Lower bound does not capture dependence on alpha, so the upper bound is not fully matched.
• Analysis restricted to stochastic bandits with a unique optimal arm and 1/2-Tsallis regularizer; extension to general theta-Tsallis is only conjectured.
• Toy-model derivation is heuristic; constants depend heavily on d and Delta (d^{3q} log^{2q} d / Delta^{4q}).

Experimental setup

Metrics: failure probability Err_t decay exponent

Builds on: Tsallis-INF best-of-both-worlds FTRL UCB

Closest papers by meaning

• Balancing Performance and Costs in Best Arm Identification (NeurIPS 2025 · similarity 0.92)
• Optimal Multi-Fidelity Best-Arm Identification (NeurIPS 2024 · similarity 0.90)
• Best Arm Identification in Generalized Linear Bandits via Hybrid Feedback (NeurIPS 2026 · similarity 0.90)
• Almost Minimax Optimal Best Arm Identification in Piecewise Stationary Linear Bandits (NeurIPS 2024 · similarity 0.90)
• Sharp Non-Asymptotic Analysis of the Penalized Challenger in $\beta$-EB-TCI for Bernoulli Bandits (NeurIPS 2026 · similarity 0.89)
• Fixed Confidence Best Arm Identification in the Bayesian Setting (NeurIPS 2024 · similarity 0.89)