Stability and Robustness via Regularization: Bandit Inference via Regularized Stochastic Mirror Descent

• URL: http://arxiv.org/abs/2603.10184v1
• Date: Tue, 10 Mar 2026 19:27:47 GMT
• Title: Stability and Robustness via Regularization: Bandit Inference via Regularized Stochastic Mirror Descent
• Abstract summary: 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.
• Score: 2.0999222360659613
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Statistical inference with bandit data presents fundamental challenges due to adaptive sampling, which violates the independence assumptions underlying classical asymptotic theory. Recent work has identified stability as a sufficient condition for valid inference under adaptivity. This paper develops a systematic theory of stability for bandit algorithms based on stochastic mirror descent, a broad algorithmic framework that includes the widely-used EXP3 algorithm as a special case. Our contributions are threefold. First, we establish a general stability criterion: if the average iterates of a stochastic mirror descent algorithm converge in ratio to a non-random probability vector, then the induced bandit algorithm is stable. This result provides a unified lens for analyzing stability across diverse algorithmic instantiations. Second, we introduce a family of regularized-EXP3 algorithms employing a log-barrier regularizer with appropriately tuned parameters. We prove that these algorithms satisfy our stability criterion and, as an immediate corollary, that Wald-type confidence intervals for linear functionals of the mean parameter achieve nominal coverage. Notably, we show that the same algorithms attain minimax-optimal regret guarantees up to logarithmic factors, demonstrating that inference-enabling stability and learning efficiency are compatible objectives within the mirror descent framework. Third, we establish robustness to corruption: a modified variant of regularized-EXP3 maintains asymptotic normality of empirical arm means even in the presence of $o(T^{1/2})$ adversarial corruptions. This stands in sharp contrast to other stable algorithms such as UCB, which suffer linear regret even under logarithmic levels of corruption.

Related papers

• Efficient Inference after Directionally Stable Adaptive Experiments [47.32051320630248]
  We study inference on pathwise differentiable targets after adaptive data collection, such as a bandit.<n>We introduce a novel target-specific condition, directional stability, which is strictly weaker than previously imposed target-aparametric stability conditions.
  arXiv  Detail & Related papers  (2026-02-25T01:09:18Z)
• 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)
• Statistical Inference under Adaptive Sampling with LinUCB [15.167069362020426]
  We show that the linear upper confidence bound (LinUCB) algorithm for linear bandits satisfies a property called stability.<n>We establish a central limit theorem for the LinUCB algorithm, establishing normality for the limiting distribution of the estimation error.
  arXiv  Detail & Related papers  (2025-11-28T21:48:18Z)
• On Instability of Minimax Optimal Optimism-Based Bandit Algorithms [2.5782420501870296]
  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.
  arXiv  Detail & Related papers  (2025-11-24T04:23:26Z)
• The Relative Instability of Model Comparison with Cross-validation [65.90853456199493]
  Cross-validation can be used to provide a confidence interval for the test error of a stable machine learning algorithm.<n>Relative stability cannot easily be derived from existing stability results, even for simple algorithms.<n>We empirically confirm the invalidity of CV confidence intervals for the test error difference when either soft-thresholding or the Lasso is used.
  arXiv  Detail & Related papers  (2025-08-06T12:54: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)
• Stability and Generalization for Stochastic Recursive Momentum-based Algorithms for (Strongly-)Convex One to $K$-Level Stochastic Optimizations [20.809499420384256]
  STORM-based algorithms have been widely developed to solve one to $K$-level ($K geq 3$) optimization problems. This paper provides a comprehensive analysis of three representative STORM-based algorithms.
  arXiv  Detail & Related papers  (2024-07-07T07:07:04Z)
• Exploring the Algorithm-Dependent Generalization of AUPRC Optimization with List Stability [107.65337427333064]
  optimization of the Area Under the Precision-Recall Curve (AUPRC) is a crucial problem for machine learning. In this work, we present the first trial in the single-dependent generalization of AUPRC optimization. Experiments on three image retrieval datasets on speak to the effectiveness and soundness of our framework.
  arXiv  Detail & Related papers  (2022-09-27T09:06:37Z)
• Private Robust Estimation by Stabilizing Convex Relaxations [22.513117502159922]
  $(epsilon, delta)$-differentially private (DP) $(epsilon, delta)$-differentially private (DP) $(epsilon, delta)$-differentially private (DP)
  arXiv  Detail & Related papers  (2021-12-07T07:47:37Z)
• 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)
• Distributionally Robust Bayesian Optimization [121.71766171427433]
  We present a novel distributionally robust Bayesian optimization algorithm (DRBO) for zeroth-order, noisy optimization. Our algorithm provably obtains sub-linear robust regret in various settings. We demonstrate the robust performance of our method on both synthetic and real-world benchmarks.
  arXiv  Detail & Related papers  (2020-02-20T22:04:30Z)

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.