Abstract
We study the problem of reliably identifying the best (lowest loss) arm in a stochastic multi-armed bandit when the expected loss of each arm is monotone decreasing as a function of its pull count. This models, for instance, scenarios where each arm itself represents an optimization algorithm for finding the minimizer of a common function, and there is a limited time available to test the algorithms before committing to one of them. We assume that the decreasing expected loss of each arm depends on the number of its pulls as a (inverse) polynomial with unknown coefficients. We propose two fixed-budget best arm identification algorithms – one for the case of sparse polynomial decay models and the other for general polynomial models – along with bounds on the identification error probability. We also derive algorithm-independent lower bounds on the error probability. These bounds are seen to be factored into the product of the usual problem complexity and the model complexity that only depends on the parameters of the model. This indicates that our methods can identify the best arm even when the budget is smaller. We conduct empirical studies of our algorithms to complement our theoretical findings.
Introduction
In traditional multi-armed bandit problems, the expected reward of an arm is typically assumed to be stationary. However, in many real-world applications—such as hyperparameter optimization or algorithm selection—the performance of an "arm" improves as it is allocated more resources. This paper investigates the "decreasing bandit" setting, where the expected loss of each arm is a monotone decreasing function of its pull count. This framework allows researchers to identify the best-performing algorithm even when the total evaluation budget is tight.
Modeling the Learning Curve
The core innovation of this work is the assumption that the expected loss follows a structured polynomial decay model:
$$E[y_{i,\tau}] = \sum_{m=1}^d \frac{\theta_m(i)}{\tau^{\rho_m}}$$
where $\tau$ is the number of pulls, $\theta$ represents unknown coefficients, and $\rho$ are known powers. This structural assumption allows the learner to extrapolate the future performance of an arm based on limited initial observations, effectively "predicting" which arm will eventually be the best.
Proposed Algorithms: LS-SH and LASSO-SH
To identify the best arm within a fixed budget $T$, the authors adapt the Sequential Halving (SH) framework. In each round, the algorithm plays all remaining arms, fits the observed data to the model, and eliminates the bottom half of the arms based on their estimated performance. Two variants are proposed:
- LS-SH (Least Squares): Employs an online least-squares estimator to fit the polynomial model. This is effective when the number of terms $d$ is small.
- LASSO-SH: Utilizes L1-regularization (LASSO) to handle high-dimensional scenarios where many potential decay terms exist, but only a few are significant for a given arm.
Theoretical and Empirical Results
The authors derive upper and lower bounds on the error probability, revealing that the complexity of the problem is factored into two components: the standard "gap" between arms and a novel "model complexity" term ($\gamma$). This theoretical framework explains why model-based approaches can succeed even when the budget is too small for model-free methods to reliably distinguish between arms.
Empirical evaluations on synthetic data and real-world trajectories (such as the TuRBO optimization algorithm) show that LS-SH and LASSO-SH achieve near-perfect accuracy with budgets as small as 200 pulls. In contrast, model-free baselines like Rising Successive Rejects (RSR) and RUCBE hovered between 20% and 60% accuracy under the same constraints.
Conclusion and Future Work
By leveraging the structural properties of learning curves, this research provides a robust framework for best arm identification in non-stationary environments. While the current theory assumes the decay powers $\rho$ are known, the authors suggest that future work could extend these guarantees to cases where these powers must be estimated online, or explore "infinite-armed" scenarios where the learner chooses from a continuous space of algorithms.
Summary updated