CS Paper Radar

Sharp Non-Asymptotic Analysis of the Penalized Challenger in $β$-EB-TCI for Bernoulli Bandits

Nam Nguyen, Tuan Quang Dam

cs.LG stat.ML ·submitted 2026-10-01 16:11 UTC · v2

Abstract

Top-two algorithms are simple and effective for fixed-confidence best-arm identification, but their sharp non-asymptotic behavior is still not well understood. We study this question for Bernoulli bandits through $β$-EB-TCI, the empirical-best top-two rule of Jourdan et al., whose challenger minimizes a Bernoulli transportation cost plus a logarithmic penalty in its pull count. We first analyze the stabilized regime, in which the empirical leader has become the true best arm and its sampling fraction stays close to $β$. In this regime, every suboptimal arm is sampled linearly often, and, with high probability, the stopping time is at most $T_β^{\star}(μ)\log(1/δ)$ plus stabilization and lower-order concentration terms, with the exact fixed-$β$ leading coefficient. The main remaining difficulty is therefore to control when the regime is reached. For the original rule, we obtain a non-asymptotic high-probability stopping bound on every Bernoulli instance with a unique best arm. Under a finite-mean sufficient-exploration condition, the bound yields the sharp expected sample complexity; combined with the exploration result of Jourdan et al., this covers pairwise-distinct means under their tie-breaking convention. A mild forced-exploration guard, which uses only $O(\sqrt{Kt})$ pulls up to time $t$, gives a self-contained sharp expected bound for any number of arms with a unique best arm. We also identify a limitation of proof strategies that try to handle equal suboptimal means through a single index-comparison argument.

Closest papers

Nearest neighbours by meaning across the whole index.

Multi-Armed Bernoulli Bandits via Minimax Single-Arm Stopping

cs.LG math.OCstat.ML ·2026-09-19 ·Huikang Liu, Zhengchao Wang, Daniel Kuhn, Wolfram Wiesemann
benchmark similarity 0.75
Abstract · This work is a preprint and has not been submitted to any conference or journal yet

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.

0.21

Transfer Learning in Bandits from Unknown Adaptive Policies: Problem-Dependent Lower and Upper Bounds

cs.LG ·2026-10-15 ·Adrien Prevost, Timothee Mathieu, Waris Radji, Odalric-Ambrym Maillard
theory similarity 0.73
Abstract · 50 pages, 4 figures

Transfer learning in stochastic multi-armed bandits is typically studied assuming that prior data forms a fixed offline dataset or is generated by a known source. In practice, historical observations come from a previous adaptive decision process whose policy is unknown. We study this setting for bounded rewards in $[0,1]$. Before the online game starts, the learner receives, for each arm $k$, $N'_k$ observations drawn i.i.d.\ from an unknown distribution $ν'_k$, collected by an arbitrary and possibly data-dependent strategy, so the sample sizes $N'_k$ may be random. Source and target means satisfy $|μ_k-μ'_k|<L_k$ for known constants $(L_k)_k$. We derive an asymptotic problem-dependent lower bound and propose KL-UCB-Transfer, which combines online and historical data and achieves logarithmic regret with an improved leading constant whenever $μ'_a<μ_1-L_a$, and recovers the classical KL-UCB guarantee otherwise. Since bounding the source-target discrepancy is often unrealistic, we relax the assumption to the one-sided condition $μ_k-μ'_k<L_k$ and show that logarithmic regret can survive under misspecification, characterizing three regimes ranging from improvement to a degraded logarithmic bound to a loss of guarantee. Simulations illustrate the practical benefits of exploiting process-generated historical data.

0.16

Toward the Optimal Regret-Instability Trade-off in Multi-Armed Bandits

cs.LG stat.MLmath.OCmath.ST ·2026-08-18 ·Kaifei Wang, Yinyu Ye, Han Zhong
theory similarity 0.71
Abstract

Multi-armed bandit algorithms are evaluated by regret, yet comparable regret can coexist with different allocations across independent runs. We study the trade-off between worst-case regret $\mathcal{R}_{K,T}$ and instability $\mathcal S_{K,T}$, defined as the largest standard deviation of a terminal pull count, for $K$ arms and $T$ rounds. We prove the finite-time lower bound $\mathcal R_{K,T}\mathcal S_{K,T}\ge C T^{3/2}$, where $C$ is independent of $K$ and $T$, under a finite-time regret condition and without the regularity assumptions imposed in the prior asymptotic analysis. We also introduce Stabilized Lower-Envelope UCB (\textup{\textsc{SLE-UCB}}), a new tunable algorithm combining a running lower-envelope index with a decreasing pull-count stabilizer. \textup{\textsc{SLE-UCB}} satisfies $\mathcal R_{K,T}\mathcal S_{K,T}=O(T^{3/2}\log K)$, with an implicit constant independent of $K$ and $T$, matching the lower bound exactly in $T$ and within a logarithmic factor in $K$. To prove the instability bound, we develop a new offline top-prefix representation that removes path dependence from online decisions. Together with single-reward perturbations and the Efron--Stein inequality, this representation controls pull-count variance. Thus, regret and instability depend reciprocally on $K$, while their product has no polynomial dependence on $K$. These results resolve the open question raised in the literature concerning the sharp arm-dependent regret--instability frontier.

0.06

The Price of Current-Effect Inference in Nonstationary Multi-Armed Bandits

cs.LG stat.ML ·2026-10-21 ·Sharan Sahu, Martin T. Wells
similarity 0.71
Abstract · 49 pages, 8 figures, 5 tables

Adaptive experiments use bandit algorithms to favor interventions with higher expected rewards. However, decision-makers also require reliable inference on current treatment effects: differences between intervention and reference-arm mean rewards at the present time, rather than historical averages. These objectives conflict: reward maximization favors better interventions, whereas current-effect inference requires continued exploration of potentially suboptimal interventions as outcomes change over time. We characterize this tradeoff for $K$-arm bandits with Hölder-smooth mean rewards of exponent $β\in(0,1]$ and constant $L$. Requiring high-probability simultaneous coverage of all current effects by confidence intervals of width at most $w$, we establish matching minimax bounds, up to logarithmic factors, on expected dynamic regret. Over horizon $T$, our algorithm TRACE (Tracking Rewards and Current Effects) achieves regret of order $\widetilde{O}_β\left(\sqrt{KT}+K^{β/(2β+1)}L^{1/(2β+1)}T^{(β+1)/(2β+1)}+Kw^{-2}(1+L^{1/β}w^{-1/β})\right)$, where the notation hides logarithms and constants depending only on $β$. This regret--precision tradeoff separates reward-learning regret from the cost of refreshing current-effect estimates, which remains unavoidable even when one arm is uniformly optimal. An empirical-Bernstein e-process extension adapts exploration to realized prediction errors while preserving worst-case guarantees. When within-block drift is negligible relative to sampling error, all observations, including reward-learning observations, can be reused for asymptotically normal pointwise inference and stronger local stationarity yields local asymptotic efficiency. Finally, we show that regret constraints can prevent honest adaptation to unknown smoothness and support our theory with extensive numerical experiments.

0.08

Does 1/2-Tsallis-INF Also Work Well for Best-Arm Identification?

cs.LG ·2026-08-15 ·Jingxin Zhan, Yuze Han, Zhihua Zhang
theory similarity 0.70
Abstract

Regret minimization (RM) and best-arm identification (BAI) are two fundamental objectives in multi-armed bandits. Among regret-minimizing algorithms, $1/2$-Tsallis-INF is a canonical best-of-both-worlds FTRL algorithm: it achieves logarithmic pseudo-regret in stochastic bandits while retaining minimax-optimal regret in adversarial bandits, without knowing the environment in advance. This raises a natural question: can the same algorithm, without additional exploration, also identify the best arm reliably? We study this question in stochastic bandits by analyzing the failure probability $\operatorname{Err}_t$, defined as the probability that the empirical best arm determined by the cumulative importance-weighted loss estimates of 1/2-Tsallis-INF differs from the true optimal arm. The main difficulty is that, at the logarithmic-regret scale, suboptimal arms are sampled with probability heuristically of order $1/t$. Consequently, importance weighting causes the cumulative estimator to fluctuate on the same linear scale as its mean separation. To overcome this obstacle, guided by a diffusion toy model, we construct a Lyapunov function for the gap process between the estimated cumulative loss of the optimal arm and that of the best competing arm. This leads to polynomial upper bounds on $\operatorname{Err}_t$: for learning rate $η_t=α/\sqrt t$, $\operatorname{Err}_t$ decays at rate $t^{-2+α^2μ_{i_*}/4+ρ}$ for any $ρ>0$, where $μ_{i_*}$ denotes the mean loss of the true optimal arm. We also establish a lower bound $Ω(t^{-2-\varepsilon})$ for any $\varepsilon>0$, showing that the exponent $2$ is essentially tight.

0.04

Best Arm Identification for Bandits with Shifting Means

cs.LG stat.ML ·2026-10-07 ·Lukas Zierahn, Wouter M. Koolen, Shubhada Agrawal, Christina Katsimerou, Dirk van der Hoeven
top venuetheoryhot direction similarity 0.70
Abstract · Accepted at NeurIPS 2026

We study the best arm identification problem in a stochastic environment with a novel form of adversarial perturbations, which we coin Shifting Means. While classically the mean rewards of the $K$ arms are stable in time, in Shifting Means only the gaps $\boldsymbolΔ$ between mean rewards are stable, while their common shift may be determined adversarially in each round. The objective of the learner is to identify the best arm with high probability while minimizing sample complexity (the fixed confidence setting). Handling shifts requires new tools: we show that algorithms employing a Generalized Likelihood Ratio Test (GLRT) stopping rule, including the popular Track-and-Stop, fail under time-varying shifts. Instead, we propose Importance Weights for Shifting Means ($\mathsf{ISM}$). Assuming means bounded by $U$ and $σ^2$-sub-Gaussian rewards, we show $\mathsf{ISM}$ to be $δ$-correct and to enjoy a sample complexity bound of order $K (σ^2 + U^2) Δ_{\min}^{-2} \ln \frac{1}δ$. We also present a matching (up to constant factors) worst-case lower bound and evaluate our results empirically.

0.45

Accelerating Linear Bandits with Persistent Candidate Sets

cs.LG ·2026-10-09 ·Bingkui Tong, Daria Korovaitceva, Marina Sheshukova, Sergey Samsonov, Junpei Komiyama
theory similarity 0.69
Abstract

Exhaustive optimistic scoring can make action selection costly in linear bandits with a large fixed set of $K$ actions, requiring $\mathcal{O}(K)$ score evaluations per round. We introduce Persistent Candidate LinUCB (\textsc{PC-LinUCB}), which maintains $k$ active actions and samples $q$ challengers uniformly from the remaining $K-k$ actions at each round. By scoring only these $k+q$ candidates, \textsc{PC-LinUCB} reduces the number of score evaluations per round to $\mathcal{O}(k+q)$. We establish problem-independent and problem-dependent high-probability regret bounds consisting of a standard linear-bandit learning term and an additive discovery cost of order $\mathcal{O}\left((K-k)\log(K-k)/q\right)$ at fixed confidence. Notably, this additional cost does not grow with the horizon. For fixed gaps and sufficiently long horizons, we establish an $Ω\left((K-k)/q\right)$ regret lower bound under uniform challenger sampling, showing that partial candidate access itself imposes an unavoidable regret cost. Experiments show that \textsc{PC-LinUCB} substantially accelerates LinUCB while maintaining comparable regret, and that the persistent candidate mechanism can extend beyond LinUCB.

0.20

High-Probability Regret Bounds for Feel-Good Thompson Sampling

cs.IT stat.MLcs.LG ·2026-10-14 ·Xuheng Li, Qingyue Zhao, Quanquan Gu
similarity 0.69
Abstract · 22 pages

Feel-good Thompson sampling (FGTS) augments the posterior of vanilla Thompson sampling with an exploration term that favors reward functions with high predicted optimal values. This modification achieves minimax-optimal regret up to logarithmic factors in linear contextual bandits, but existing analyses of its two standard variants establish regret guarantees in expectation. In this paper, we derive the first high-probability regret bounds for both cumulative and current-step FGTS in contextual bandits with general realizable function approximation. Our bounds depend on the corresponding decoupling coefficients and the prior mass near the true reward function. In the $d$-dimensional linear setting, both variants satisfy $\mathrm{Regret}(T)=O\big(d\sqrt T\log(2T)+\sqrt T\log(1/δ)\big)$ with probability at least $1-δ$, where $T$ is the time horizon. This bound matches the dimension and horizon dependence of algorithms based on the upper confidence bounds, up to logarithmic factors. Relative to the expected-regret guarantees, the cost of controlling the regret with high probability is confined to additive terms with at most linear dependence on $\log(1/δ)$. The proof ideas are partially developed by GPT-6 Astra under the authors' guidance.

0.19