PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Xuan Li

arXiv:2609.17595v1cs.LG

TL;DR

Improving bandits asks how to allocate pulls among arms with nondecreasing, discretely concave rewards when their curves are unknown. This paper develops prior-free probing algorithms and determines how noise changes adaptation guarantees. Without noise, optimal guarantees require no priors; under fixed positive noise, adaptation without either scale or envelope exponent has a growing price.

  • Problem

    Earlier scale-based thresholds require m, and removing that information incurred a logarithmic overhead; envelope-dependent guarantees also require parameter selection or offline instances.

    Source: §1 · p. 3

  • Method

    The paper uses scale-free probe-and-commit, random-marginal probing without noise, and nested random-permutation probing for the noisy adaptation result.

    Source: §1 · pp. 2–3

  • Results

    Without noise, random-marginal probing achieves the optimal Θ(k^(β/(1+β)) + k/T) order simultaneously for every admissible β and horizon; under fixed positive noise, the adaptation price is bounded below by Ω_ε(Φ(k)) and matched by nested random-permutation probing.

    Source: §1 · pp. 2–3

  • Takeaways & Limitations

    Without noise the price of not knowing m, β, or T is Θ(1), while under fixed positive noise knowing either m or β alone restores a constant price.

    Source: §1 · pp. 2–3

    The random-marginal counterexamples do not rule out every repair; the nonconstant uniform-price result instead comes from Theorem 5.6 under fixed positive noise, asymptotically in k.

    Source: §5.2 · p. 17

Abstract

from arXiv · show

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 $\Omega(\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, $\Theta(\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 $\beta$ of Blum, Garicano, Ravichandran and Sharma (UAI 2026), nor the horizon $T$, achieves the optimal $\Theta(k^{\beta/(1+\beta)}+k/T)$ simultaneously for every $\beta$ and every horizon. Under the multiplicative noise model of Blum and Ravichandran, probe-and-commit keeps the same all-horizon order $\Theta(\sqrt k+k/T)$ without knowing the noise level (and $\Theta(\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 $\phi_\varepsilon(k)$ --- the worst case over horizons $T\ge16k$ of the loss relative to $k^{\beta/(1+\beta)}$ for algorithms knowing neither $m$ nor $\beta$ --- is $\Theta_\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 $\beta$ alone restores a constant price.

1 Introduction

The introduction presents prior-free algorithms for improving bandits and distinguishes their guarantees without noise from the higher adaptation cost under multiplicative noise. It also positions these results against earlier scale-dependent guarantees.

1 Introduction

  • Earlier work gives an O(√k) approximation with known scale and O(√k log k) without it for sufficiently long horizons; the new scale-oblivious result removes that logarithmic overhead.The introduction attributes the earlier guarantees to Blum and Ravind्रachandran [1].Source: §1 · p. 2
  • Probe-and-commit achieves a scale-oblivious competitive ratio of 4√3√k for sufficiently long horizons, and the optimal ratio is Θ(√k + k/T) at every horizon.An anytime version reads only k; the naive doubling schedule does not attain this order at every horizon.Source: §1 · p. 2
  • Without noise, random-marginal probing adapts simultaneously to every admissible β without knowing m or β, achieving the optimal Θ(k^(β/(1+β)) + k/T) ratio at every horizon.An anytime version reads neither T nor those priors.Source: §1 · p. 2
  • Under multiplicative noise, probe-and-commit retains an all-horizon Θ(√k + k/T) order without knowing the noise level, up to the stated factor a²/b.The introduction contrasts this guarantee with the noiseless random-marginal algorithm, which fails under noise.Source: §1 · p. 2
  • With fixed positive noise, the uniform adaptation price for algorithms knowing neither m nor β is at least Ω_ε(Φ(k)) and is matched by nested random-permutation probing; knowing either prior alone restores a constant price.The lower bound is asymptotic in k and holds even when the algorithm reads T and ε.Source: §1 · p. 3
  • Earlier scale-based thresholds compare rewards with an absolute threshold involving m, while probe-and-commit selects the best probe by relative comparison.The introduction identifies the unknown scale and the prior logarithmic cost of guessing it as motivation for scale-oblivious methods.Source: §1 · p. 3

2 Model and conventions

This section fixes the reward model, benchmark, parameter conventions, and knowledge classes used to state the paper’s guarantees. It also specifies the multiplicative-noise setting and how adaptation is evaluated.

2 Model and conventions

  • Each arm has an unknown, nondecreasing reward function with diminishing returns, and its reward on a pull depends on that arm’s pull count rather than calendar time.The functions are fixed before the algorithm runs; the algorithm observes only collected rewards.Source: §2 · p. 3
  • The benchmark is cumulative reward from the best single arm, and a competitive ratio compares that benchmark with the algorithm’s expected reward.A comparator attaining the maximum is denoted ∗; prior-free envelope results use a cumulatively optimal comparator satisfying the envelope condition.Source: §2 · pp. 3–4
  • The envelope condition LE(β) requires the optimal arm’s reward at time t to be at least its terminal reward times (t/T)^β; every admissible concave nondecreasing curve satisfies LE(1).The paper’s positive results require the condition only for the optimal arm.Source: §2 · p. 4
  • Scale-oblivious, β-oblivious, and anytime algorithms respectively do not read m, β, or T, though they may estimate quantities from observations already collected.For unknown horizons, an anytime policy is evaluated at every T.Source: §2 · p. 4
  • Simultaneous adaptation means one algorithm works across every β, unlike class-wise minimax bounds that may use a different algorithm for each β.The uniform price of adaptation fixes the algorithm before the exponent, instance, and noise are chosen; scale advice tied to a horizon does not imply one guarantee at every stopping time.Source: §2 · pp. 4–5
  • The noisy model uses adversarially fixed rewards within multiplicative ε of the true rewards, while the benchmark remains the policy playing the best uncorrupted arm.The observed noisy values may be non-monotone and non-concave; a = 1 − ε and b = 1 + ε bound the noisy benchmark relative to the true one.Source: §2 · p. 5

3 Unknown scale is free

This section studies scale-oblivious probing under discrete concavity, giving a no-scale guarantee for maximizing the largest single reward within its stated horizon scope, alongside known- and unknown-horizon guarantees and lower bounds across the full horizon range. It also states the benchmark when the envelope exponent β is known.

3.1 Consequences of discrete concavity

  • Discrete concavity makes f(t)/t nonincreasing and yields P(u)/P(T) ≥ (u/T)^2 for 1 ≤ u ≤ T.These prefix-sum facts support the probe-and-commit analysis.Source: §3.1 · p. 6

3.2 Probe-and-commit

  • For k = 1, the ratio is 1; the algorithm uses no information about m.Source: §3.2 · p. 7

3.3 Lower bounds and the full horizon dependence

  • The delayed-reveal construction gives lower bounds by hiding a uniformly random good arm among arms truncated at depth d.Before the good arm is pulled d + 1 times, its run matches a virtual instance in which every arm is truncated.Source: §3.3 · p. 8
  • The scale-oblivious minimax ratio is Θ(√k + k/T) for every horizon T ≥ 1.The upper bound uses probe-and-commit with truncated parameters; the lower bound includes both a √k term and a k/T term.Source: §3.3 · p. 8

3.4 Unknown horizon

  • APC reads only k and achieves the all-horizon order Θ(√k + k/T) without knowing T.It uses fresh probe-and-commit samples in phases and does not reset pull counts; the phase schedule starts at length 1.Source: §3.4 · pp. 9–10

3.5 Known envelope exponent

  • For known β, scale-oblivious probe-and-commit has class-wise ratio Θ(k^γ + k/T), where γ = β/(1 + β).The stated upper guarantee is for arms satisfying LE(β), and the lower-bound construction stays within that class.Source: §3.5 · pp. 10–11
  • For known β and unknown T, independent probe-and-commit phases achieve O(k^γ) for every T ≥ 2⌈Kβ⌉.The phases use fresh samples without resetting pull counts.Source: §3.5 · pp. 10–11
  • For maximizing the largest single reward, PC’s last pull is its maximum observed reward, with E[max] ≥ E[ALG_T]/T ≥ M/(32k) by the transfer argument of [1, App. B].The bound uses Lemma 3.1(5).Source: §3.5 · p. 11
  • Theorem 3.4 directly gives a no-scale-knowledge, no-logarithm guarantee for T ≥ 2⌊√k⌋, not identical to a statement in [1].Source: §3.5 · p. 11

4 Without noise, every prior is free

Without noise, the paper removes the need to know the optimal arm’s envelope exponent β, scale m, or horizon T. Random-marginal probing adapts across β, and sparse inclusion extends its optimal competitive ratio to every horizon.

4.1 Random-marginal probing

  • RMP draws independent random priorities, probes greedily by last observed increment divided by priority, then commits to an arm.Its guarantee applies to an optimal arm satisfying LE(β), while the algorithm itself reads neither m nor β.Source: §4.1 · p. 12
  • The random-marginal analysis bounds expected greedy work by total truncated increment v, rather than by the number of scales times v, removing the logarithm.The probe phase is a merge of the arms’ nonincreasing increment-priority sequences.Source: §4.1 · p. 12
  • For k ≥2, β∈(0, 1], and T ≥16k, when the optimal arm satisfies LE(β), RMP(T) reads neither m nor β and guarantees E[ALGT] ≥ 3/256 R k^-β/(1+β).Source: §4.1 · p. 13

4.2 All horizons: independent sparse inclusion

  • Independent sparse inclusion fixes the short-horizon initialization problem and accounts for the good-decoy branch without multiplying by the optimal arm’s inclusion probability.SRMP samples arms independently, probes the included set, and commits; it falls back to a uniform arm when the set is empty or too large.Source: §4.2 · p. 14
  • For every horizon, SRMP achieves the optimal Θ(k^β/(1+β) + k/T) competitive ratio without knowing m or β, giving a Θ(1) price for not knowing m, β, or T.The same SRMP attains the bounds simultaneously across the admissible β classes.Source: §4.1 · p. 13, §4.2 · p. 15
  • An anytime SRMP phased algorithm reads only k and guarantees E[ALGT] ≥ 2^-19 R Qβ(k,T) for every T ≥1 and every instance whose optimal arm satisfies LE(β).The phases have lengths 1, 2, 4, … and use fresh randomness.Source: §4.2 · p. 15

5 Multiplicative noise: the price of priors jumps

The section examines how multiplicative noise and available advice affect competitive guarantees, including constant-factor RET guarantees with scale advice, the fixed-arm vanishing-noise regime, and a no-input mixture with blocking. It also treats the growing joint cost of not knowing scale and curvature under fixed positive noise and describes a known-prior approach to restoring a constant price.

5.1 Probe-and-commit is robust and needs no ε

  • Noisy probe-and-commit reads neither m nor ε, while its phase-wise guarantee holds conditionally on history and its minimax order remains scale-oblivious.The phase-wise estimate yields guarantees up to a factor a²/b; the lower bounds from Section 3 persist because zero noise is admissible.Source: §5.1 · p. 16

5.2 Random-marginal probing breaks

  • A fake-growth example defeats random-marginal probing and two increment-based repairs, but the section does not claim that every repair fails.A zero key at the wrong moment causes the decoy to be committed; Theorem 5.6, not this example, establishes the adaptation lower bound.Source: §5.2 · p. 17

5.3 A matching pair: nested permutation probing and a hidden-growth lower bound

  • Nested permutation probing uses a random arm order, nonincreasing probe depths, and commits to the arm with the largest running maximum.The algorithm is specified for H ≥16k and reads neither m, β, nor ε; its depth schedule is budget-feasible.Source: §5.3 · pp. 18–19
  • For fixed ε>0, the uniform price of not knowing m and β is Θ_ε(√(log k/log log k)), matched by nested permutation probing and a hidden-growth lower bound.The lower bound is asymptotic in k and established at specified hard horizons; the price takes a worst case over T ≥16k.Source: §5.3 · p. 19

5.4 Knowing either prior alone restores a constant price

  • With scale μ known, random-exponent elimination is presented as a route to a constant price without knowing β or ε.The algorithm reads k, H, and μ; its guarantee is framed for a comparator satisfying g*(t) ≥ μ(t/H)^β.Source: §5.4 · pp. 20–21
  • With known scale m=f*(T), RET gives a constant-factor qβ guarantee for every qualifying β without reading β or ε; phased advice m/4 extends this to unknown T≥16k.The stated guarantees use H=T and μ=m for known T, or phases H_j=16k·2^j for unknown T.Source: §5.4 · p. 21
  • For fixed k, a vanishing noise level restores a constant price uniformly over T; this differs from the fixed-ε, k→∞ regime.The passage states that these two limits do not interact.Source: §5.4 · p. 21
  • Blocking lets the Proposition 5.8 proof replace 1+cεT with 1+O(εk) to obtain a bound uniform in T, but the paper does not claim blocking is necessary.The counterexample does not refute keys based on the running-maximum level or the reading that keeps the largest dyadic window.Source: §5.4 · p. 21
  • The no-input mixture selects APC, phased NPA, or anytime SRMP uniformly at random; in the noiseless model it guarantees E[ALG_T] ≥ R Qβ(k,T)/(3·2^19) for every T≥1.Under noise, the anytime SRMP branch contributes only through nonnegative rewards.Source: §5.4 · pp. 21–22

6 Deterministic algorithms, positioning, and open problems

The section gives deterministic bounds with explicit horizon qualifications, then relates the paper’s relative probing choices to prior work and identifies a limitation under additive noise. It also distinguishes what remains achievable from what is ruled out in that noise setting.

Deterministic algorithms

  • For T ≥ 2k, probing each arm ⌊T/(2k)⌋ times and committing earns at least R/(8k), while a deterministic lower-bound construction forces ratio at least k/2.The upper bound is proved independently for a known horizon; the lower-bound construction follows [3].Source: §6 · p. 22
  • At T = 2k − 1, probing every arm once and committing gives ratio at most 2k − 1, so the deterministic order remains Θ(k) at that horizon.The paper explicitly makes no claim that 2k is the sharp boundary.Source: §6 · p. 22
  • At T = k, the deterministic minimax ratio is exactly k(k + 1)/2, while for T < k an unvisited arm can make the ratio unbounded.At T = 2k − 1, the order is still Θ(k); the paper does not claim the exact horizon where the order changes.Source: §6 · pp. 22–23

Positioning

  • Relative comparisons replace scale-dependent absolute thresholds: probe-and-commit selects the largest probe value, while random-marginal variants weight observed increments by random priorities.The discussion describes this technical difference without claiming why earlier approaches chose their route.Source: §6 · p. 23
  • Theorems 4.4, 4.10, and 5.7 give per-instance guarantees adapting to β without reading it in the noiseless model and in the noisy model with known scale.In the noisy model with both scale and exponent unknown, Theorem 5.6 establishes that per-instance adaptation has a growing price.Source: §6 · p. 23

Open problems

  • With fixed-variance additive Gaussian noise and a uniformly random location for the sole positive-mean arm, some location forces ratio at least k − o(1) as δ ↓ 0.This rules out a uniform o(k) guarantee of the present form, but not a guarantee of order k; the passage leaves signal and horizon conditions as an open question.Source: §6 · p. 24

A Proof of Theorem 5.7 (known scale, unknown β and ε)

The proof orders noisy arm tests by random weights and uses a threshold to ensure that either a competing arm or the comparator is committed. Under the envelope condition, this yields a reward guarantee with known scale and horizon, and a phase construction extends it to an unknown horizon.

Comparator test

  • If the comparator’s weight is at most q, its elimination test never fires, and it reaches observed value v within n1 ≤ H/8 pulls.The argument uses the envelope condition and the noise lower bound a ≥ 1/2.Source: A Proof of Theorem 5.7 (known scale,… · pp. 25–26

Bounding probe work

Reward guarantee

  • The proof splits into disjoint events: a non-comparator reaches v, or the comparator’s weight lies in [p, q] and it reaches v; either way the committed arm earns reward.The event {p ≤ U* ≤ q} is independent of the decoy-work events, enabling the combined guarantee.Source: A Proof of Theorem 5.7 (known scale,… · p. 26

Known scale, known horizon

  • With known scale and horizon, the proof obtains expected reward at least aRq^β/(2048b) under the envelope condition.Here a and b are the multiplicative noise bounds, and the comparator satisfies the stated β-envelope assumption.Source: A Proof of Theorem 5.7 (known scale,… · pp. 24, 26

Known scale, unknown horizon

  • For an unknown horizon, geometrically increasing phases yield a guarantee proportional to Rq^β, with the completed phase horizon exceeding T/4.The phase construction uses known scale and contributes nonnegative rewards in other phases.Source: A Proof of Theorem 5.7 (known scale,… · p. 27

B A blocked confidence-key algorithm for small noise

The appendix adapts random-marginal probing to small multiplicative noise by operating on macro-steps and ranking arms with confidence keys. Its key lemmas control those keys and probe work, while the resulting bound approaches its noiseless dependence as the noise bound decreases.

Algorithm

  • The algorithm groups pulls into macro-steps, attaches each step’s last observation, and commits to the arm with the largest cumulative value.Any remaining pulls after H macro-steps go to the committed arm.Source: B A blocked confidence-key algorithm… · p. 27

Confidence key

  • Macro-curves remain nonnegative, nondecreasing, and discretely concave, while the confidence key is nonnegative, nonincreasing, and lower-bounds the true increment.Below a threshold v, the key is also bounded above by the truncated increment plus a noise-dependent term.Source: B A blocked confidence-key algorithm… · p. 27

Blocked hitting lemma

  • The blocked hitting lemma combines a comparator-inclusion event, a bound on probe work, and reward from the committed arm to obtain a lower bound involving the comparator’s reward.Its stated bound is one half the minimum of the competing-arm reward term and the comparator-inclusion term.Source: B A blocked confidence-key algorithm… · p. 28

All-horizon guarantee

  • The all-horizon bound uses a factor D depending on the noise bound, and for fixed k, D tends to 1 as the bound tends to zero.The accompanying factor a²/b also tends to 1, uniformly in the horizon and instance.Source: B A blocked confidence-key algorithm… · pp. 28–29
Loading 2609.17595v1…