CS Paper Radar

Bayesian Fixed-Confidence Best-Arm Identification with Abstention

Yuqi Huang, Yunlong Hou, Vincent Y. F. Tan

cs.LG cs.IT ·submitted 2026-10-21 19:45 UTC · v1
theory

Abstract

We study the Bayesian fixed-confidence best-arm identification problem in which a learner can abstain from making a terminal recommendation. Subject to a target error probability $δ$ and an abstention budget $α$, we propose Screen-and-Confirm (S&C) and analyze its expected stopping time. We further derive the minimum expected stopping time for any algorithm that satisfies these constraints. For Gaussian priors and rewards, as $(δ,α)\downarrow(0,0)$, we establish matching upper and lower bounds up to multiplicative constants, with rate $κ_ν^2[1+\log((α+δ)/δ)]/(α+δ)$, where $κ_ν$ is the prior density of the top-two gap at zero, highlighting that nearly tied instances govern the sampling cost. When abstention is disallowed ($α=0$), S&C yields the optimal $Θ(1/δ)$ dependence for fixed model parameters, removing the additional $\log(1/δ)$ factor in the upper bound of Jang et al. (2024) under our Gaussian assumptions. We further characterize the exact multiplicative constant of the minimum expected stopping time for practical regimes including (i) fixed $α\in (0,1)$ and (ii) $α/δ\to\infty$, which are also achieved by S&C.

Closest papers

Nearest neighbours by meaning across the whole index.

Nearly Optimal Fixed-Confidence Best-Arm Identification with 1-Bit Feedback

cs.LG cs.AIstat.ML ·2026-10-02 ·Khang Luong, Dinh Thai Son, Hoang Ta, Hung The Tran, Tuan Quang Dam
top venuetheory similarity 0.72
Abstract · To appear in Advances in Neural Information Processing Systems 39 (NeurIPS 2026, Spotlight)

We study fixed-confidence best-arm identification under strict 1-bit feedback constraints. At each round, the learner selects an arm and a query set, and receives only a single bit indicating whether the sampled reward belongs to that set. We consider a distribution-free finite-variance setting with arm-wise localization, where direct empirical mean estimation is no longer available and clipping becomes unavoidable. We first formulate a time-uniform 1-bit mean-estimation primitive based on randomized threshold queries and a clipped tail-integral identity. We then embed this primitive into candidate-challenger best-arm identification algorithms. A fixed-clipping algorithm gives a simple anytime $(ε,δ)$-PAC guarantee, while a phased adaptive-clipping algorithm matches the clipping level to the current resolution and yields a gap-adaptive sample complexity. We also prove a $K$-arm worst-case information-theoretic lower bound showing that the logarithmic penalty caused by finite-variance 1-bit feedback is intrinsic. This bound matches the leading dependence of the phased algorithm up to lower-order $\log\log$ factors.

0.40

Halve-Then-Greedy: Adaptive Sampling for Posterior Success with Near-Optimal Instance Dependence

cs.LG stat.ML ·2026-10-14 ·Yinan Li, Kwang-Sung Jun, Kapilan Balagopalan, Tuan Nguyen, Yao Zhao +2 more
theory similarity 0.71
Abstract

We study fixed-budget adaptive experimentation aimed at maximizing the probability of obtaining sufficient posterior evidence that a recommended design's mean performance exceeds a target. Unlike best-arm identification, this objective does not require finding the best design. For Gaussian bandits with a Gaussian prior, we propose \emph{Halve-Then-Greedy} (HTG), which combines a large initial balanced allocation, successive halving, and posterior-greedy sampling. We prove instance-dependent, finite-budget exponential bounds on posterior-failure probability that capture both separation from unfavorable arms and the presence of multiple favorable arms. On one-positive-arm families, we establish an asymptotic sample-complexity lower bound that HTG matches up to a logarithmic factor. We further analyze uniform sampling and sequential halving, revealing regimes where they require more samples than HTG by linear and logarithmic factors, respectively. Simulations illustrate HTG's sample-efficiency advantages and their dependence on instance structure.

0.18

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.69
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

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.68
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

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

cs.LG stat.ML ·2026-10-01 ·Nam Nguyen, Tuan Quang Dam
similarity 0.67
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.

0.13

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.66
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

Cost-Aware Best-LLM Identification using Dueling Feedback

cs.LG cs.AIstat.ML ·2026-09-24 ·Sarvesh Gharat, Nikhil Karamchandani, Jayakrishnan Nair
top venuetheory similarity 0.66
Abstract · We propose a cost-aware dueling bandit algorithm for best arm identification, prove its asymptotic optimality, and demonstrate its effective…

Inspired by the problem of identifying the best model from a collection of large language models (LLMs) with heterogeneous querying costs, we formulate and analyse a variant of the multi-armed bandit (MAB) with (i) dueling feedback, where pairwise comparisons between model responses provide robust preference signals, and (ii) heterogeneous sampling costs, reflecting the differing costs of querying different LLMs. Assuming the existence of a Condorcet winner, a condition we empirically validate across multiple real-world datasets, we propose a Track-and-Stop style algorithm for best-arm identification with prescribed confidence. We prove that the algorithm almost surely achieves the asymptotically optimal cost as the error tends to zero. Finally, we extensively evaluate our approach on both synthetic and real-world instances, demonstrating consistent improvements over classical cost-unaware algorithms and their cost-aware extensions.

0.41

Future Information-Directed Sampling for Bayesian Nonstationary Bandits

cs.LG ·2026-09-27 ·Yichen Song, Alessio Russo, Aldo Pacchiano
published similarity 0.66
Abstract · 18 pages. An earlier version appeared at the ICML 2026 DEMO Workshop

Exploration--exploitation is a central trade-off in bandit learning. While classical algorithms such as upper confidence bound methods and Thompson Sampling effectively balance this trade-off in stationary environments, their exploration strategies mainly reduce uncertainty about the current optimal arm, which can be insufficient in nonstationary settings where future optimal arms may differ substantially from current ones. In this paper, we propose Future Information-Directed Sampling (FIDS), a new algorithm for Bayesian nonstationary bandits that explicitly explores to gather information about future optimal arms. We show that FIDS achieves regret comparable to Thompson Sampling up to a small constant factor, while being able to exploit predictive information structures that conventional exploration objectives fail to capture. To address the practical difficulty of posterior inference, we further propose a supervised-learning-based approximation framework that learns the FIDS policy from offline data, and demonstrate its effectiveness on synthetic benchmarks.

0.33