🤖 machine learning

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

This paper demonstrates that the regret-minimizing algorithm 1/2-Tsallis-INF can also reliably identify the best arm in stochastic bandits without additional exploration, achieving a polynomial decay rate in failure probability that is shown to be essentially tight.

Original authors: Jingxin Zhan, Yuze Han, Zhihua Zhang

Published 2026-08-18

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Jingxin Zhan, Yuze Han, Zhihua Zhang

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

In the world of decision-making under uncertainty, there is a constant tension between two goals. Imagine a gambler at a row of slot machines, or a doctor choosing between several treatments for a patient. The first goal is to do as well as possible right now, learning which option is best while minimizing the cost of trying the wrong ones. This is known as regret minimization: the learner wants to avoid pulling a suboptimal lever too often. The second goal is different. Here, the learner is given a fixed amount of time to explore, and at the very end, must point to the single best option with high confidence. This is called best-arm identification. For decades, researchers have treated these as separate challenges, often requiring different strategies. One approach favors caution and exploitation to save resources, while the other demands aggressive exploration to gather enough data to be sure.

A recent breakthrough in this field involves an algorithm called 1/2-Tsallis-INF. This method is special because it is a "best-of-both-worlds" solution. Without needing to know in advance whether the environment is random and predictable or chaotic and hostile, it automatically adapts to perform optimally in both scenarios. It is a rare tool that can minimize regret effectively while remaining robust against malicious interference. However, a lingering question remained: does this same algorithm, left to its own devices without any extra forced exploration, also succeed at the second goal? Can it reliably identify the single best option at the end of the process, or does its strategy for minimizing regret accidentally sabotage its ability to find the true winner?

Researchers Jingxin Zhan, Yuze Han, and Zhihua Zhang set out to answer this question. They focused on a specific type of environment where the outcomes are random but follow a consistent pattern. In this setting, the algorithm makes choices based on a running tally of estimated losses, which it updates using a technique called importance weighting. This technique is necessary because the algorithm only sees the result of the option it picked, not the results of the options it ignored. To guess what the unchosen options would have done, it scales up the observed loss by the inverse of the probability that it was chosen. While this creates an unbiased estimate, it also introduces a massive problem: the estimates fluctuate wildly. When the algorithm is doing its job well and rarely picking a bad option, the probability of picking that bad option becomes tiny. Consequently, the importance-weighted estimate for that bad option becomes enormous and unstable. This high variance makes it incredibly difficult to prove that the algorithm's running tally has correctly separated the best option from the rest.

The team discovered that the algorithm does indeed work for identifying the best arm, but the path to certainty is slower and more fragile than one might hope. They proved that the probability of the algorithm making a mistake—the chance that it points to the wrong arm at the end—does decrease over time. Specifically, this failure probability shrinks at a rate proportional to the inverse of the square of the time elapsed. In simpler terms, if you double the time spent exploring, the chance of error drops by a factor of four. This is a polynomial decay, which is a solid guarantee, but it is not as fast as the logarithmic speed often seen in other contexts. The researchers showed that this rate is essentially the best possible for this specific algorithm without adding extra mechanisms to force exploration. If the algorithm were to try to identify the best arm faster, it would likely sacrifice its ability to minimize regret or handle adversarial environments.

To reach this conclusion, the researchers had to overcome a significant mathematical hurdle. Standard tools for analyzing such systems rely on the idea that averages settle down quickly, but the wild fluctuations caused by importance weighting prevent this from happening. The team developed a new way to track the algorithm's progress by constructing a special mathematical function, known as a Lyapunov function, which acts like a stability meter. They built this function by studying simplified models of the algorithm's behavior, including a continuous model that mimics the random drift of a particle. By analyzing how this function changes over time, they were able to show that despite the noise, the gap between the estimated performance of the best arm and its competitors eventually widens enough to ensure a correct identification. They also established a lower bound, proving that the algorithm cannot possibly do much better than this rate; the square-root relationship between time and error probability is a fundamental limit for this approach.

The findings confirm that the 1/2-Tsallis-INF algorithm is a complete solution for both minimizing regret and identifying the best arm, provided one accepts a specific rate of convergence. It does not need to be modified or supplemented with extra exploration steps to achieve this dual success. The work provides the first rigorous guarantee that a Follow-the-Regularized-Leader algorithm, which relies on importance-weighted estimates, can reliably find the best option in a random environment. While the speed of identification is limited by the very mechanism that makes the algorithm so robust against uncertainty, the result demonstrates that a single, unified strategy can indeed handle the complex trade-off between learning quickly and learning correctly. The researchers' work closes a gap in our understanding of these adaptive systems, showing that even in the face of high variance, the truth can be found with enough patience and the right mathematical tools.

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

Problem Setting
This paper investigates the Best-Arm Identification (BAI) capabilities of the 1/2-Tsallis-INF algorithm within the stochastic multi-armed bandit (MAB) framework. While 1/2-Tsallis-INF is a canonical "best-of-both-worlds" (BOBW) algorithm known for achieving logarithmic pseudo-regret in stochastic environments and minimax-optimal regret in adversarial environments without prior knowledge of the regime, its performance in BAI tasks remains unexplored.

The specific objective is to analyze the failure probability, denoted as $Err_t = P(i^*_t \neq i^*)$ , where $i^*_t$ is the empirical best arm determined by the cumulative importance-weighted loss estimates of the algorithm, and $i^*$ is the true optimal arm. The study focuses on whether the algorithm can reliably identify the optimal arm using its standard importance-weighted estimates without adding explicit forced exploration mechanisms, which would otherwise compromise its BOBW properties.

Methodological Challenges
The primary technical obstacle is the high variance inherent in importance-weighted (IW) estimators used by Follow-The-Regularized-Leader (FTRL) algorithms.

In standard UCB-type algorithms, BAI analysis relies on concentration inequalities for empirical means.
In 1/2-Tsallis-INF, suboptimal arms are sampled with probability roughly $O(1/t)$ to achieve logarithmic regret. Consequently, the variance of the IW estimator for a suboptimal arm at a single round is $O(t)$ .
This causes the cumulative estimator to fluctuate on the same linear scale as its mean separation from the optimal arm. Standard concentration arguments fail because the noise magnitude is comparable to the signal gap.
Prior approaches to bypass this variance issue involved adding explicit exploration, but this destroys the BOBW guarantee. This paper addresses the problem using the unmodified algorithm.

Methodology: Lyapunov Function Analysis
To overcome the variance issue, the authors construct a Lyapunov function to analyze the stochastic dynamics of the gap process $D_t = \hat{L}_{t, i^*} - N_t$ , where $N_t$ is the minimum cumulative estimated loss among suboptimal arms.

Toy Models: The derivation is guided by two simplified toy models:
- A discrete-time process approximating the gap dynamics.
- A continuous-time diffusion process derived via Itô's formula.
Function Construction: These models reveal a specific drift-variance balance, leading to the construction of a piecewise Lyapunov function $g_t(y)$ $g_{t} (y)$ :
- For $y < 0$ (gap is negative): $g_t(y) = \Delta^2 t^q e^{\lambda y}$ .
- For $y \geq 0$ (gap is positive): $g_t(y) = t^{-\theta}(y + \Delta t)^2$ .
- Here, $\Delta$ is the suboptimality gap, and parameters $q, \theta, \lambda$ are tuned to ensure $g_t(D_t)$ behaves as a supermartingale.
Key Insight: The analysis determines that the exponent $m=2$ in the polynomial term is critical. Values $m > 2$ fail to maintain the supermartingale property due to the heavy tails of the IW estimator, while $m=2$ maximizes the convergence rate parameter $q$ under the constraint $m \leq 2$ .

Key Contributions and Results
The paper provides the first quantitative BAI-type guarantee for an FTRL algorithm without additional exploration.

Upper Bound (Theorem 3.1): For a learning rate $\eta_t = \alpha/\sqrt{t}$ , the failure probability decays polynomially:
$Err_t \leq C \cdot t^{-q}$
where $q < 2 - \frac{\alpha^2 \mu_{i^*}}{4}$ (specifically, $q \in (0, 2 - \frac{\alpha^2 \mu_{i^*}}{4})$ ). As the learning rate coefficient $\alpha \to 0$ , the decay rate approaches $t^{-2}$ .
Lower Bound (Theorem 3.3): The authors establish a matching lower bound, showing that for any $\epsilon > 0$ , $Err_t \geq C' t^{-2-\epsilon}$ . This proves that the exponent $2$ is essentially tight for this algorithm.
Technical Novelty: The work demonstrates that despite the high variance of importance-weighted estimators, the specific structure of the 1/2-Tsallis-INF regularizer allows for reliable BAI. The Lyapunov function approach is highlighted as a potential tool for analyzing other BOBW settings and Tsallis-entropy FTRL algorithms.

Significance
The paper claims that this is the first result to directly analyze the probabilistic behavior of the unmodified importance-weighted estimator in the context of BAI. It resolves the tension between regret minimization and best-arm identification for BOBW algorithms, showing that 1/2-Tsallis-INF can identify the optimal arm with polynomially decaying failure probability without sacrificing its robustness to adversarial environments. The results suggest that the trade-off between regret and identification accuracy is governed by the learning rate coefficient $\alpha$ , where smaller $\alpha$ yields faster identification but potentially higher regret constants, consistent with known lower bounds relating cumulative regret and simple regret.

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

More like this