Multi-Armed Bernoulli Bandits via Minimax Single-Arm Stopping

Huikang Liu; Zhengchao Wang; Daniel Kuhn; Wolfram Wiesemann

cs.LGSep 19, 2026

Multi-Armed Bernoulli Bandits via Minimax Single-Arm Stopping

Authors: Huikang Liu, Zhengchao Wang, Daniel Kuhn, Wolfram Wiesemann

Organizations: Shanghai Jiao Tong University · The University of Sydney · École Polytechnique Fédérale de Lausanne · Imperial College Business School

Abstract

We develop an index policy for finite-horizon Bernoulli multi-armed bandits from minimax solutions to single-arm bandit (SAB) problems. Each SAB problem involves choosing between an unknown Bernoulli arm and a known reward. We show that minimizing worst-case regret of SAB problems over all non-anticipative policies admits an exact semi-infinite linear programming formulation. The resulting stopping policies offer a natural way to compare arms: the higher the known reward against which a policy continues sampling, the more promising the unknown arm. We turn this intuition into indices based on cumulative continuation probabilities, with a monotone adjustment and a reward-shortfall cap. By relating index errors to the regret of single-arm stopping policies, we establish a distribution-free regret bound of $4.45\sqrt{KT}+10.75K$ for $K$ arms and horizon $T$ . This bound matches the minimax-optimal regret order established in the literature. The guarantee extends to rewards supported on $[0,1]$ through Bernoulli randomization. We also provide a finite-grid implementation with quantified approximation loss. In numerical experiments, the SAB-based index policy achieves lower worst-case regret than every tested benchmark policy across all evaluated numbers of arms and horizons, while closely matching the grid-based MAB minimax policy in the two-arm setting.

Figures & tables

Panel of Figure 1 — Figure 1: Single-arm performance and continuation decisions. In the right panel, filled black circles denote pulling the unknown arm, hollow circles denote stopping, and the half-filled circle denotes the randomized state of the SAB policy.

Figure 2: Known-arm reward boundary for pulling with probability greater than

1/2

, at

T=200

and

s=n/2

. The horizontal line is the empirical mean

s/n=0.5

Figure 3: Estimated worst-case regret for

K=2

. SAB-LP-MAB is compared with the benchmark policies and the grid-based MAB minimax policy computed on the

0.005

-spaced Bernoulli grid.

Panel of Figure 4 — Figure 4: Estimated worst-case regret over the evaluation grid for $K=4$ and $K=8$ . SAB-LP-MAB uses the same untuned construction $H=\lceil T/K\rceil$ , $G=2H$ , and $b=\sqrt{G}/4$ in both panels.

Appendix figures & tables1 asset

Supplementary material from the paper’s appendix.

Appendix

Panel of Figure 5 — Figure 5: Estimated worst-case regret over the evaluation grid for $K=4$ and $K=8$ . SAB-LP-MAB uses the same untuned construction $H=\lceil T/K\rceil$ , $G=2H$ , and $b=\sqrt{G}/4$ in both panels.

Explore similar work

Sep 29, 2026

Bandits with Multiple Optimal Arms: Minimax Regret and Non-Adaptivity

We study multi-armed bandits (MAB) with multiple optimal arms, motivated by the fact that many practical decision making problems admit multiple correct answers. For

K

-armed bandits with

A

optimal arms, we first provide a sharper analysis of previous sub-sampling algorithms (De Heide et al., 2021; Zhu and Nowak, 2020), establishing a

\tilde{O}\Big(\frac{K-A}{\sqrt{KA}}\sqrt{T} \Big)

minimax regret, where

T

is the total number of interactions and

\tilde O(\cdot)

drops all constant and logarithmic factors, improving the previous

\tilde{O}(\sqrt{KT/A})

regret. We then provide a matching lower bound up to logarithmic factors, indicating that our established rate is nearly minimax-optimal. We further show that the knowledge of

A

up to

\tilde{O}(1)

factors is necessary to achieve near-optimal regret, as near-optimal algorithms for one number of optimal arms must incur substantially larger regret than optimal regret for a smaller number. Overall, our results provide a comprehensive minimax characterization of

K

-armed bandits with

A

over the entire range of

1 \leq A \leq K-1

Kaixuan Ji, Qiwei Di, Qingyue Zhao +2

Department of Computer Science, University of California, Los Angeles, CA 90095, USA

Multi-Armed Bandits Minimax Regret Regret Minimization

Ask PDF

May 10, 2026

Optimal Regret for Single Index Bandits

We study the

\textit{single-index bandit}

problem, where rewards depend on an unknown one-dimensional projection of high-dimensional contexts through an unknown reward function. This model extends linear and generalized linear bandits to a nonparametric setting, and is particularly relevant when the reward function is not known in advance. While optimal regret guarantees are known for monotone reward functions, the general non-monotone case remains poorly understood, with the best known bound being

\tilde{\mathcal{O}}(T^{3/4})

(under standard boundedness and Lipschitz assumptions on the reward function [Kang et al., 2025]). We close this gap by establishing the optimal regret for general single-index bandits. We propose a simple two-phase algorithm, namely, Zoomed Single Index Bandit with Upper Confidence Bound (

\texttt{ZoomSIB-UCB}

), that first estimates the projection direction via a normalized Stein estimator, and then reduces the problem to a one-dimensional bandit using discretization and finally use UCB. This approach achieves a regret of

\tilde{\mathcal{O}}(T^{2/3})

, and improves significantly upon prior work without any additional assumptions. We also prove a matching minimax lower bound of

\tildeΩ(T^{2/3})

, showing that the upper bound is essentially tight. Our upper and lower bounds together provide a sharp characterization of the regret in single-index bandits. Moreover, the empirical results further demonstrate the effectiveness and robustness of our approach.

Devdan Dey, Sujoy Bhore, Avishek Ghosh

Department of Computer Science and Engineering, Indian Institute of Technology Bombay.

Multi-Armed Bandits Single-Index Models Minimax Regret Regret Minimization Contextual Bandits

Ask PDF

May 1, 2026

Trading off rewards and errors in multi-armed bandits

In multi-armed bandits, the most-explored arms are the most informative, while reward maximization typically pulls only the best arm. We study the tradeoff between identifying arm means accurately and accumulating reward, and present an algorithm with regret guarantees that interpolates between the two objectives. We provide both upper and lower bounds and validate empirically.

Akram Erraqabi, Alessandro Lazaric, Michal Valko +2

Inria SequeL · CMU · EnLearn

Multi-Armed Bandits Exploration-Exploitation Tradeoff Best-Arm Identification Regret Minimization

Ask PDF