Expected Sample Complexity in Multi-Armed Bandits

Nadav Sukenik; Nadav Merlis

cs.LGOct 7, 2026

Expected Sample Complexity in Multi-Armed Bandits

Authors: Nadav Sukenik, Nadav Merlis

Organizations: Technion – Institute of Technology

Abstract

Sample complexity is a widely used metric in sequential decision-making problems, defined as the number of suboptimal decisions during the interaction between the agent and an environment. We study the sample complexity of stochastic multi-armed bandit problems and introduce the expected sample complexity performance measure, analyzing it in a novel framework called approximately correct in expectation (ACE). We show that ACE guarantees imply almost sure convergence to the optimal expected reward, in contrast to high-probability guarantees found in other frameworks, and also show how to convert ACE guarantees into explicit expected regret bounds. We further show that, in contrast to existing measures, deterministic algorithms cannot obtain favorable ACE bounds, and analyze stochastic algorithms in two settings: when the allowed suboptimality level $ε$ is known to the algorithm and when it is unknown. In the former, we devise an explore-then- $ε$ -greedy algorithm, and in the latter, we analyze the expected sample complexity of Thompson sampling. Finally, we establish nearly matching lower bounds for both settings, showing that the algorithms are tight in $ε$ and proving a performance separation between the two regimes.

Figures & tables

Appendix figures & tables2 assets

Supplementary material from the paper’s appendix.

Appendix

Figure 1: Flow of randomness in round $t$ of the interaction. The policy $\pi_{t}$ is determined from the past history $\mathcal{F}_{t-1}$ . The internal randomization $U_{t}$ is then revealed, making the realized action $A_{t}$ and any other internal choice mechanism predictable before the reward $X_{t}$ is observed.

Figure 2: The X-axis is number of rounds, the Y-axis is the estimated expected sample complexity with $\epsilon=0.018$ up to round $t$ , using $100,000$ simulations of the interaction of $\pi^{TS(\mathcal{N})}$ with the environment. The 99% CI for the expected sample complexity at round $100$ is $[55.076538,55.452762]$ for $\mathbb{E}_{\nu}\left[N_{\epsilon}\left(\pi^{TS(\mathcal{N})},100\right)\right]$ , and $[64.676313,65.170247]$ for $\mathbb{E}_{\nu^{\prime}}\left[N_{\epsilon}\left(\pi^{TS(\mathcal{N})},100\right)\right]$

Explore similar work

May 1, 2026cs.LG

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

Stochastic Multi-Armed Bandits Regret Trade-Off

Ask PDF

Sep 29, 2026stat.ML

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

Stochastic Multi-Armed Bandits Bandits Optimal

Ask PDF

Jul 14, 2026stat.ML

Thompson Sampling Is 2-Competitive for Mistakes

We consider Bayesian bandit models and prove that Thompson sampling makes at most twice the expected number of mistakes (selections of a suboptimal arm) as any other policy. Our analysis applies as long as the latent arm processes are independent and each arm evolves only when played. For stochastic bandits with best arm defined via mean reward, this confirms a conjecture of Guha and Munagala from 2014, where the factor

2

is already best possible. The result holds under any nonincreasing sequence of round weights, including fixed horizon and geometric discounting.

Mark Sellke, Gregory Valiant

Thompson Sampling Optimal Policies

Ask PDF