CS Paper Radar

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

Kaixuan Ji, Qiwei Di, Qingyue Zhao, Heyang Zhao, Quanquan Gu

cs.AI stat.MLcs.LGmath.STstat.ME ·submitted 2026-09-29 23:33 UTC · v2
theory

Abstract

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

Closest papers

Nearest neighbours by meaning across the whole index.

Nearly Minimax-Optimal Regret for Linear Contextual Bandits with Arbitrary Adaptive Action Sets

cs.LG cs.GT ·2026-09-14 ·Tianyuan Jin
theory similarity 0.80
Abstract

We study stochastic linear contextual bandits with arbitrary action menus that may depend on the fixed parameter and the interaction history. We establish matching upper and lower bounds, up to logarithmic factors. Let $d$ be the dimension, $K$ be the menu size, and $T$ the time horizon. For $2\le K\le d$, we prove an upper bound $\widetilde O(K^{1/4}\sqrt{dT})$. When $T\ge d^2$, we further prove a lower bound $Ω(K^{1/4}\sqrt{dT})$. Thus, for $T\ge d^2$ and $2\le K\le d$, the upper and lower bounds match up to logarithmic factors, and the polynomial dependence on $K$ is optimal. Compared with the previous $\widetilde O(\sqrt{dKT})$ bound, our upper bound improves the dependence on $K$ by a factor of $K^{1/4}$. For $K\ge d$, we prove an upper bound $\widetilde O_{d,T}\left(\sqrt{dT}\min\{\sqrt d,(d\log K)^{1/4}\}\right)$ and a lower bound $Ω\left(\sqrt{dT}\min\left\{\sqrt d,\left(\frac{d\log K}{\log(2d)}\right)^{1/4}\right\}\right)$. Here, $\widetilde O_{d,T}$ omits logarithmic factors only in $d$ and $T$. In particular, for polynomially large $K\ge d$, the upper and lower bounds both scale as $d^{3/4}\sqrt T$ up to logarithmic factors, improving the standard $\widetilde O(d\sqrt T)$ rate by a factor of $d^{1/4}$. As $K$ grows further, the regret smoothly recovers the $d\sqrt T$ scale once $\log K$ reaches order $d$.

0.41

Toward Optimal Switching Regret for Multi-Armed Bandits with Oblivious Adversary

cs.LG stat.ML ·2026-09-11 ·Mengxiao Zhang
similarity 0.78
Abstract

We study switching regret in adversarial multi-armed bandits, where the learner competes with an arm sequence that changes at most $S$ times. When $S$ is known, an optimal expected regret of $\widetilde{\mathcal{O}}(\sqrt{(S+1)KT})$ is obtainable [Auer et al., 2002]. However, when $S$ is unknown, Marinov and Zimmert [2021] show that this guarantee is impossible under an adaptive adversary. In this paper, we show that a single algorithm achieves $\widetilde{\mathcal{O}}(\sqrt{(S+1)KT})$ expected regret for every $S$ against an oblivious adversary, resolving an open problem of Auer et al. [2019b]. Our algorithm combines a fixed-share learner initialized with a small learning rate and dyadic-interval subroutines that search for local improvements using randomized learning rates and implicit exploration. Importantly, a non-uniform prior favors following the main learner, keeping the cost of maintaining many subroutines small. When the subroutines accumulate sufficient improvement over the main learner, its learning rate doubles, allowing adaptation to the unknown number of comparator switches $S$.

0.17

Prior-Free Competitive Ratios for Improving Bandits: Scale, Curvature and Horizon Are Free, but Not Jointly Under Noise

cs.LG ·2026-09-12 ·Xuan Li
theory similarity 0.77
Abstract

In the improving multi-armed bandits problem, each of $k$ arms has an unknown nondecreasing, discretely concave reward curve $f_i$, and pulling arm $i$ for the $t$-th time yields $f_i(t)$. For sufficiently long horizons, Blum and Ravichandran (ALT 2025) proved that randomized algorithms achieve an $O(\sqrt k)$ approximation to the best single arm when the scale $m=f^*(T)$ of the optimal arm is known ($T\ge2k$), and $O(\sqrt k\log k)$ when it is not ($T>4k$), against an $Ω(\sqrt k)$ lower bound. The logarithmic factor is unnecessary: a one-page \emph{probe-and-commit} algorithm achieves competitive ratio $4\sqrt3\,\sqrt k$ for $T\ge2\lfloor\sqrt k\rfloor$, without any knowledge of the scale, and we determine the optimal ratio for every horizon, $Θ(\sqrt k+k/T)$, also for unknown horizons. Without noise, \emph{no prior is needed at all}: a random-marginal probing algorithm reading neither the scale $m$, nor the concavity-envelope exponent $β$ of Blum, Garicano, Ravichandran and Sharma (UAI 2026), nor the horizon $T$, achieves the optimal $Θ(k^{β/(1+β)}+k/T)$ simultaneously for every $β$ and every horizon. Under the multiplicative noise model of Blum and Ravichandran, probe-and-commit keeps the same all-horizon order $Θ(\sqrt k+k/T)$ without knowing the noise level (and $Θ(\sqrt k)$ on the same range), but the price of priors jumps: for any fixed noise level $\varepsilon\in(0,1/2]$, the uniform price of adaptation $φ_\varepsilon(k)$ --- the worst case over horizons $T\ge16k$ of the loss relative to $k^{β/(1+β)}$ for algorithms knowing neither $m$ nor $β$ --- is $Θ_\varepsilon(\sqrt{\log k/\log\log k})$, the lower bound asymptotic in $k$ at fixed positive $\varepsilon$ and matched by a nested random-permutation probing algorithm, whereas knowing either $m$ or $β$ alone restores a constant price.

0.22

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

Achieving Minimax-Optimal First-Order and Best-of-Both-Worlds Regret Simultaneously in Multi-Armed Bandits

cs.LG ·2026-10-29 ·Mengxiao Zhang
similarity 0.76
Abstract

We study first-order and best-of-both-worlds regret guarantees in multi-armed bandits. Pogodin and Lattimore (2019) proposed an algorithm that combines minimax-optimal worst-case regret with a first-order guarantee whose loss-dependent term is $\mathcal{O}(\sqrt{K L^\star}\log T)$, where $T$ denotes the horizon, $L^\star$ denotes the smallest expected cumulative loss among fixed arms, and $K$ denotes the number of arms. However, a logarithmic gap remains between this loss-dependent term and the optimal first-order scale. In this paper, we remove this logarithmic factor by proposing an efficient and parameter-free algorithm that achieves the minimax optimal first-order regret guarantee $\mathcal{O}(\sqrt{K L^\star})$. Technically, our algorithm is built upon FTRL with a Tsallis entropy regularizer (Zimmert and Seldin,2021), with a learning rate adapted to the learner's cumulative loss and a sampling distribution determined by a scalar fixed point. This construction controls the combined estimation and stability cost in terms of the learner's loss. Moreover, we show that the same algorithm achieves a best-of-both-worlds guarantee, with $\mathcal{O}(\sum_{i\ne i^\star}\frac{\log T}{Δ_i})$ regret for i.i.d. losses with a unique best arm $i^\star$, where $Δ_i$ denotes the suboptimality gap of arm $i$.

0.10

Bandits with Probing: Optimal Coverage and the Role of Feedback

cs.LG cs.DSstat.ML ·2026-09-14 ·Yongjie Guan
similarity 0.75
Abstract · 40 pages, 1 table

In bandits with probing, a learner selects at most $k$ of $n$ arms per round, earns the largest of their rewards, and competes with the best fixed single arm. For independent arms with i.i.d. rewards in $[0,1]$ and $2\le k<n$, the minimax regret is $Θ\bigl(\frac{n-k}{n}\min\{T,n/k\}\bigr)$, the cost of locating an unknown good arm, and observing only the maximum suffices to attain it. In particular, two probes give $Θ(\min\{T,n\})$ regret, which resolves two open questions of Bhaskara et al. (2023) with weaker feedback. Our policy turns the probing surplus, the excess of the maximum over each probed arm, into exploration capital, and a permanent random core yields the sharp dependence on $k$. On arbitrary fixed reward arrays, same-round contrasts between blocks of arms attain the same rate, because the surplus pays for the stability of mirror descent. Winner feedback, the maximum together with its winning label, instead incurs an additional learning cost under joint i.i.d. rewards and on fixed arrays. We characterize this cost even when values are revealed only intermittently, using policies that know neither the horizon nor the revelation rate. For three independent arms and two probes, exact maxima, Bernoulli-rounded maxima with winning labels, and winning labels alone have minimax regret $Θ(1)$, $Θ(\sqrt T)$, and $Θ(T)$: rounding preserves conditional means but not the rate.

0.25

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

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