On Instability of Minimax Optimal Optimism-Based Bandit Algorithms

• URL: http://arxiv.org/abs/2511.18750v1
• Date: Mon, 24 Nov 2025 04:23:26 GMT
• Title: On Instability of Minimax Optimal Optimism-Based Bandit Algorithms
• Abstract summary: Multi-armed bandit (MAB) algorithms are challenging due to their adaptive, non-i.i.d. nature.<n>We analyze the stability properties of a broad class of bandit algorithms based on the optimism principle.<n>We show that widely used minimax-optimal UCB-style algorithms, including MOSS, Anytime-MOSS, Vanilla-MOSS, ADA-UCB, OC-UCB, KL-MOSS, KL-UCB-SWITCH, and Anytime KL-UCB-SWITCH, are unstable.
• Score: 2.5782420501870296
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Statistical inference from data generated by multi-armed bandit (MAB) algorithms is challenging due to their adaptive, non-i.i.d. nature. A classical manifestation is that sample averages of arm rewards under bandit sampling may fail to satisfy a central limit theorem. Lai and Wei's stability condition provides a sufficient, and essentially necessary criterion, for asymptotic normality in bandit problems. While the celebrated Upper Confidence Bound (UCB) algorithm satisfies this stability condition, it is not minimax optimal, raising the question of whether minimax optimality and statistical stability can be achieved simultaneously. In this paper, we analyze the stability properties of a broad class of bandit algorithms that are based on the optimism principle. We establish general structural conditions under which such algorithms violate the Lai-Wei stability criterion. As a consequence, we show that widely used minimax-optimal UCB-style algorithms, including MOSS, Anytime-MOSS, Vanilla-MOSS, ADA-UCB, OC-UCB, KL-MOSS, KL-UCB++, KL-UCB-SWITCH, and Anytime KL-UCB-SWITCH, are unstable. We further complement our theoretical results with numerical simulations demonstrating that, in all these cases, the sample means fail to exhibit asymptotic normality. Overall, our findings suggest a fundamental tension between stability and minimax optimal regret, raising the question of whether it is possible to design bandit algorithms that achieve both. Understanding whether such simultaneously stable and minimax optimal strategies exist remains an important open direction.

Related papers

• Stability beyond Bounded Differences: Sharp Generalization Bounds under Finite $L_p$ Moments [3.5932002706017556]
  We develop a stability-based framework that requires only a finite $L_p$ moment condition.<n>We derive sharp high-probability generalization bounds across a range of learning paradigms.
  arXiv  Detail & Related papers  (2026-06-05T02:59:49Z)
• Stability and Robustness via Regularization: Bandit Inference via Regularized Stochastic Mirror Descent [2.0999222360659613]
  Recent work has identified stability as a sufficient condition for valid inference under adaptivity.<n>This paper develops a systematic theory of stability for bandit algorithms based on mirror descent.<n>A modified variant of regularized-EXP3 maintains normality of empirical arm means even in the presence of adversarial corruptions.
  arXiv  Detail & Related papers  (2026-03-10T19:27:47Z)
• Avoiding the Price of Adaptivity: Inference in Linear Contextual Bandits via Stability [2.5782420501870296]
  We argue that stability and statistical efficiency can coexist within a single contextual bandit method.<n>We show that our algorithm achieves regret guarantees that are minimax optimal up to logarithmic factors.
  arXiv  Detail & Related papers  (2025-12-23T13:53:53Z)
• EVaR-Optimal Arm Identification in Bandits [7.340828059560291]
  We study the fixed-confidence best arm identification problem within the multiarmed bandit (MAB) framework under the Entropic Value-at-Risk criterion.
  arXiv  Detail & Related papers  (2025-10-06T11:49:56Z)
• Asymptotically Optimal Linear Best Feasible Arm Identification with Fixed Budget [55.938644481736446]
  We introduce a novel algorithm for best feasible arm identification that guarantees an exponential decay in the error probability.<n>We validate our algorithm through comprehensive empirical evaluations across various problem instances with different levels of complexity.
  arXiv  Detail & Related papers  (2025-06-03T02:56:26Z)
• Achieving adaptivity and optimality for multi-armed bandits using Exponential-Kullback Leibler Maillard Sampling [24.487235945761913]
  We study the problem of $K$-armed bandits with reward distributions belonging to a one- parameter exponential distribution family.<n>We propose an algorithm that can achieve multiple optimality criteria simultaneously, including Asymptotic Optimality, Minimax Optimality with a $sqrtln (K)$ factor, Sub-UCB, and variance-adaptive worst-case regret bound.
  arXiv  Detail & Related papers  (2025-02-20T09:12:16Z)
• Towards a Sharp Analysis of Offline Policy Learning for $f$-Divergence-Regularized Contextual Bandits [49.96531901205305]
  We analyze $f$-divergence-regularized offline policy learning.<n>For reverse Kullback-Leibler (KL) divergence, we give the first $tildeO(epsilon-1)$ sample complexity under single-policy concentrability.<n>We extend our analysis to dueling bandits, and we believe these results take a significant step toward a comprehensive understanding of $f$-divergence-regularized policy learning.
  arXiv  Detail & Related papers  (2025-02-09T22:14:45Z)
• UCB algorithms for multi-armed bandits: Precise regret and adaptive inference [6.349503549199403]
  Upper Confidence Bound (UCB) algorithms are a widely-used class of sequential algorithms for the $K$-armed bandit problem.<n>We show that the Lai-Robbins regret formula is exact if and only if the sub-optimality gaps exceed the order $sigmasqrtKlog T/T$.<n>We also show that its maximal regret deviates from the minimax regret by a logarithmic factor, and therefore settling its strict minimax optimality in the negative.
  arXiv  Detail & Related papers  (2024-12-09T01:14:02Z)
• Unified theory of upper confidence bound policies for bandit problems targeting total reward, maximal reward, and more [0.8287206589886879]
  The upper confidence bound (UCB) policy is recognized as an order-optimal solution for the classical total-reward bandit problem. We show that the UCB policy achieves the order optimality in both total-reward and max bandit problems. We propose PIUCB algorithms, which aim to pull the arm with the highest probability of improvement.
  arXiv  Detail & Related papers  (2024-11-01T03:39:33Z)
• Best Arm Identification with Fixed Budget: A Large Deviation Perspective [54.305323903582845]
  We present sred, a truly adaptive algorithm that can reject arms in it any round based on the observed empirical gaps between the rewards of various arms. In particular, we present sred, a truly adaptive algorithm that can reject arms in it any round based on the observed empirical gaps between the rewards of various arms.
  arXiv  Detail & Related papers  (2023-12-19T13:17:43Z)
• PAPAL: A Provable PArticle-based Primal-Dual ALgorithm for Mixed Nash Equilibrium [58.26573117273626]
  We consider the non-AL equilibrium nonconptotic objective function in two-player zero-sum continuous games. Our novel insights into the particle-based algorithms for continuous distribution strategies are presented.
  arXiv  Detail & Related papers  (2023-03-02T05:08:15Z)
• Stability and Generalization for Markov Chain Stochastic Gradient Methods [49.981789906200035]
  We provide a comprehensive generalization analysis of MC-SGMs for both minimization and minimax problems. We establish the optimal excess population risk bounds for both smooth and non-smooth cases. We develop the first nearly optimal convergence rates for convex-concave problems both in expectation and with high probability.
  arXiv  Detail & Related papers  (2022-09-16T15:42:51Z)
• Amortized Conditional Normalized Maximum Likelihood: Reliable Out of Distribution Uncertainty Estimation [99.92568326314667]
  We propose the amortized conditional normalized maximum likelihood (ACNML) method as a scalable general-purpose approach for uncertainty estimation. Our algorithm builds on the conditional normalized maximum likelihood (CNML) coding scheme, which has minimax optimal properties according to the minimum description length principle. We demonstrate that ACNML compares favorably to a number of prior techniques for uncertainty estimation in terms of calibration on out-of-distribution inputs.
  arXiv  Detail & Related papers  (2020-11-05T08:04:34Z)
• Stability of Stochastic Gradient Descent on Nonsmooth Convex Losses [52.039438701530905]
  We provide sharp upper and lower bounds for several forms of gradient descent (SGD) on arbitrary Lipschitz nonsmooth convex losses. Our bounds allow us to derive a new algorithm for differentially private nonsmooth convex optimization with optimal excess population risk.
  arXiv  Detail & Related papers  (2020-06-12T02:45:21Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.