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

Xuan Li

cs.LGSep 12, 2026

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

Authors: Xuan Li

Organizations: University of New South Wales, Sydney, Australia

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

Figures & tables

Unknown among $\{m,\beta\}$	noiseless price (Section 4 )	price under fixed $\varepsilon\in(0,\tfrac{1}{2}]$
none / only $m$ / only $\beta$	$\Theta(1)$	$\Theta(1)$ (Thms. 5.1 , 5.7 )
both $m$ and $\beta$	$\Theta(1)$ (Thms. 4.4 , 4.10 )	$\Theta_{\varepsilon}(\Phi(k))$ (Thms. 5.5 , 5.6 )

Table 1: The uniform price of adaptation

\phi_{\varepsilon}(k)

of Section 2 , i.e.

\inf

over algorithms (or anytime policies) of the worst case over

T\geq 16k

, over

\beta

, over instances of

\mathcal{I}_{\beta}

and over admissible noise tables, of

\hat{R}\,q_{\beta}/\mathbb{E}[\widehat{\mathrm{ALG}}_{T}]

. The algorithm is chosen before

\beta

and the instance. The noisy lower bound is established at the hard horizons

T=16k^{\prime}

32k^{\prime}

of Theorem 5.6 and is asymptotic in

k

; it is not claimed at every fixed

T\geq 16k

. Whether

T

\varepsilon

may be read does not change the order in any cell: the upper bounds do not read them, the lower bound allows them. Each cell is a separate infimum:

\phi_{\varepsilon}

is defined relative to a class

\mathfrak{A}

fixed by what the algorithms may read, so the entries of different rows are values of the same functional taken over different

\mathfrak{A}

. In the known-scale cells the scale advice refers to the same designated optimal arm as the envelope hypothesis and the noisy benchmark; the arm’s index itself is not supplied to the algorithm. If instead the advice is allowed to come from an arbitrary cumulatively optimal arm, with terminal value

m_{0}\leq 2m^{\circ}

by Lemma 3.1 (5), running

\mathrm{RET}(T,m_{0}/2)

for known

T

and phases with advice

m_{0}/8

for unknown

T

gives the constants

4096

and

65536

respectively, so the

\Theta(1)

entries are unchanged.

Multi-Armed Bandits

Multi-Armed Bandits study how to choose among uncertain actions over time while balancing immediate rewards with learning.

See all 348 papers

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

Oct 16, 2026

Budgeted Bayesian Bandits for Future Utilization

The multi-armed bandit problem models the trade-off between exploration and exploitation. In this paper, we study the variant where exploration has a hard budget and precedes exploitation. Prior guarantees include a 1/3 approximation by Guha and Munagala using Lagrangian duality, and a 4/27 approximation by Ma against a primal linear programming relaxation for a more general model. We show that the analyses of both algorithms are tight, even when their relaxations are asymptotically exact. We provide a different efficient algorithm that achieves a 0.43 approximation. We then provide an efficient algorithm whose guarantee approaches 1-e^{-1} approx 0.63 for bounded exchangeable reward observations in a non-vanishing regime, which is asymptotically tight against natural linear programming relaxations. The technique also gives certificates for stopping sequential model evaluation.

Sudipto Guha

Markovian Bandits Multi-Armed Bandits Approximation Algorithms

Ask PDF

Sep 14, 2026

Bandits with Probing: Optimal Coverage and the Role of Feedback

In bandits with probing, a learner selects at most

k

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.

Yongjie Guan

Zhejiang University of Technology

Multi-Armed Bandits Minimax Regret Adversarial Bandits

Ask PDF

Abstract

Multi-Armed Bandits

Explore similar work

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

Budgeted Bayesian Bandits for Future Utilization

Bandits with Probing: Optimal Coverage and the Role of Feedback