Prior-Free Competitive Ratios for Improving Bandits: Scale, Curvature and Horizon Are Free, but Not Jointly Under Noise
cs.LG
Quick verdict
Proves scale, curvature and horizon priors cost only Θ(1) noiselessly in improving bandits but Θ(√(log k/log log k)) jointly under noise; rigorous, constants large.
Summary
This theory paper revisits improving multi-armed bandits (k arms with unknown nondecreasing, discretely concave curves; the t-th pull of arm i yields f_i(t)) and asks which prior knowledge — optimal-arm scale m, concavity-envelope exponent β, horizon T — is necessary for near-optimal competitive ratios. Against Blum–Ravichandran (ALT 2025), whose unknown-scale algorithm paid an extra log k for T>4k, a one-page probe-and-commit algorithm achieves 4√3·√k for T ≥ 2⌊√k⌋ with no scale knowledge, and the optimal all-horizon ratio Θ(√k + k/T) is established with matching lower bounds plus an anytime variant reading only k (Theorems 3.4, 3.8, 3.12). Noiselessly, random-marginal probing with random-priority keys attains the optimal Θ(k^{β/(1+β)} + k/T) simultaneously for every β without reading m, β, or T (Theorems 4.4, 4.10, 4.11) — all priors are free, answering a per-instance adaptation question raised by Blum et al. (UAI 2026). Under multiplicative noise, probe-and-commit stays robust without knowing ε (Theorem 5.1), but the price of not knowing both m and β jumps to Θ_ε(√(log k/log log k)) asymptotically in k, matched by nested permutation probing (Theorems 5.5, 5.6); either prior alone restores a constant price. Limitations: constants reach 8192, the noisy lower bound requires k ≥ k₀(ε) ≥ 2^256 and holds only at hard horizons, and there are no experiments.
Review complete
Assessment at a glance
4
risk flags identified
● high 0
● medium 1
● low 3
5 strengths · 5 weaknesses · 5 author questions
Levels reflect verification complexity — not a quality score. Evolve never rates your paper.
Key claims under review
- Unknown scale is free: a probe-and-commit algorithm achieves competitive ratio 4√3√k for T≥2⌊√k⌋ without knowing m, and the minimax ratio of scale-oblivious algorithms is Θ(√k+k/T) at every horizon, including unknown horizons (Theorems 3.4, 3.8, 3.12).
- Without noise, one single algorithm (RMP/SRMP) simultaneously attains the optimal Θ(k^{β/(1+β)}+k/T) for every envelope exponent β without reading m, β, or T, so the noiseless price of priors is Θ(1) (Theorems 4.4, 4.10, 4.11).
- Under oblivious multiplicative noise, probe-and-commit keeps Θ(√k+k/T) without knowing ε, but every algorithm knowing neither m nor β loses a factor Θ_ε(√(log k/log log k)) at some horizon (asymptotic in k, at hard horizons), matched by nested permutation probing; knowing either prior alone restores a constant price (Theorems 5.1, 5.5, 5.6, 5.7).
- Deterministic algorithms have minimax ratio Θ(k) for T≥2k, exactly k(k+1)/2 at T=k, and unbounded ratio for T<k; under additive stochastic noise with fixed variance no uniform prior-free guarantee better than order k can hold (Section 6, Open Problem 4).
Strengths
Clean removal of the log k factor and a complete horizon characterization
PC samples s=⌊√k⌋ arms, probes each ⌊T/(2s)⌋ times, commits to the largest probe value; Lemma 3.3's two-branch analysis (fooling arms vs. sampling the optimum) gives E[ALG]≥R/(16√k), sharpened to 4√3·√k (Theorem 3.4). Theorem 3.8 brackets the scale-oblivious minimax ratio between ¼(√k+k/T) and 24(√k+k/T) for all k,T≥1; Theorem 3.12 gives an anytime variant (constant 1536), and Example 3.11 shows the naive doubling schedule is genuinely deficient, not just harder to analyze.
Genuine simultaneous adaptation without any prior in the noiseless model
RMP weights observed increments by fixed random priorities Z_i; Lemma 4.2 charges decoy work to their total value, avoiding the multi-scale union bound that produced log k. SRMP (Theorem 4.10) attains R/8192·min{k^{−β/(1+β)}, T/k} at every horizon with one and the same algorithm for all β. Section 2 explicitly distinguishes class-wise ∀β∃A_β from simultaneous ∃A∀β, and the result addresses the per-instance worst-case gap that Blum et al. (UAI 2026, App. D) left open.
Matching upper and lower bounds for the noisy price of priors, with explicit quantifiers
Unusually careful scholarly hygiene toward prior work
Complete self-contained proofs, including delicate bookkeeping
Weaknesses
Constants are far from operational
The headline noise separation is purely asymptotic
No empirical component despite simple, implementable algorithms
Model sensitivity limits the scope of the title's claims
Negative-result narrative is narrower than the section framing suggests
Full Review Report
$1.99 · one-timeUnlock the complete preliminary analysis Evolve produced for this paper.
- All 5 strengths & 5 weaknesses, analyzed in detail
- 4 risk flags with severity, section & reviewer questions
- Methods & statistical evidence assessment
- 5 questions a peer reviewer would ask
- Full six-dimension evaluation report & recommendations
One-time purchase · this paper only
One-time purchase, this paper only. AI-generated preliminary analysis — not peer review.
Frequently asked questions
What is the improving multi-armed bandits problem?
It is a bandit model where each arm's reward grows with repeated investment: pulling arm i for the t-th time yields f_i(t), where f_i is nondecreasing and discretely concave (diminishing returns). Since total reward is maximized by committing to the single best arm from the start, performance is measured by the competitive ratio between the best single arm's total reward and the algorithm's expected total reward over the horizon.
What does 'price of priors' mean in this paper?
It quantifies how much an algorithm loses when it is not told certain parameters: the reward scale m (the optimal arm's terminal value), the concavity-envelope exponent β, the horizon T, or the noise level ε. The paper proves all of these priors cost at most a constant factor in the noiseless model, but under fixed multiplicative noise, not knowing both m and β simultaneously costs an extra Θ(√(log k/log log k)) factor (asymptotically in the number of arms k), while knowing either one alone still costs only a constant.
How does this paper improve on Blum and Ravichandran's ALT 2025 result?
Blum and Ravichandran achieved an O(√k) competitive ratio only when the scale m was known in advance, and O(√k log k) when it was unknown (requiring T>4k). This paper's simple probe-and-commit algorithm removes the log k factor entirely, works for all T≥2⌊√k⌋, characterizes the optimal ratio at every horizon as Θ(√k+k/T), handles unknown horizons with an anytime version, and stays robust to multiplicative noise without knowing the noise level ε.
Does the paper include experiments or code?
No. It is a purely theoretical work: six algorithms are given in pseudocode (Algorithms 1–6) with complete proofs, but there are no simulations, no empirical evaluation, and no released code. The algorithms are simple enough to implement, but the proved constants (e.g., 8192) mean the guarantees are structural rather than practically calibrated.
About this review
This is an AI-generated preliminary review by Evolve.Pub, produced from the openly available text of the paper. It is not peer review and does not represent the authors' views. The canonical record of the paper is at the publisher link above.
- The abstract in the supplied metadata is truncated mid-sentence; the embedded full text (running through the references and both appendices, ~29 pages) was used for this review and appears essentially complete.
- Mathematical proofs were assessed structurally, not re-verified line by line; formula rendering in the extraction is degraded in places (flattened fractions, subscript/superscript loss), so a few numeric claims were reconstructed from surrounding context (e.g., the Theorem 5.6 bound 8192/(εΦ(k))).
- The only table (Table 1, the price-of-priors comparison) and all displayed equations were extracted as inline text; no figures exist in the extraction to assess.
- Review covers arXiv v1 (12 Sep 2026); peer-review status and any later-version changes cannot be assessed from the text.
Go deeper on this paper
Wrote a paper? Stress-test it before reviewers do.
Upload your manuscript for the same structured scrutiny — reasoning, statistics, evidence, figures, and reproducibility.