Bandits with Probing: Optimal Regret and the Limits of Winner Feedback
cs.LG · cs.DS · stat.ML
Quick verdict
Resolves open probing-bandit problems with two tight minimax regret laws; coherent novel construction, though full proofs exceed what this text can verify.
Summary
This theory paper determines the minimax regret for bandits where a learner probes at most k of n arms per round and observes only the maximum reward (winner feedback, BestProbe) or all probed values (AllProbe), competing against the best fixed arm. Two laws are established with universal constants and anytime algorithms. First, under independent stochastic rewards with winner feedback, or over arbitrary fixed sequences given signed block contrasts, regret scales as Φ = min{(n−k)T/n, (n−k)/k}, proving two probes already give bounded regret and resolving open questions of Bhaskara et al. (2023), whose best prior bounds were O(n² log T). Second, allowing arbitrary within-round dependence under BestProbe yields R = (n−k)/n·min{T, (n+T)/k, √(nT/k)}, adding an irreducible learning cost. The upper bounds combine Tsallis mirror-descent contrasts whose stability cost is paid by the probing surplus itself, exact anchor-sample recovery from winner feedback via rejection resampling, gain banks that fund sample advancement, and gain-funded activation near full coverage. Lower bounds use hidden-arm coverage arguments plus a correlated threshold construction that renders winner labels uninformative. Extensions cover partial numerical revelation, pair-feasibility thresholds, and heterogeneous quotas. Limitations: purely theoretical with large explicit constants (e.g., regret < 236m−360 for the two-probe policy), no empirical validation, and proofs spanning appendices that cannot be fully verified from the extracted text.
Review complete
Assessment at a glance
4
risk flags identified
● high 0
● medium 2
● low 2
5 strengths · 5 weaknesses · 5 author questions
AI text signal = Binoculars zero-shot detector score over 20 sampled passages (Fast-DetectGPT co-reported) — absence does not prove human authorship, and a flag does not imply misconduct.
Levels reflect verification complexity — not a quality score. Evolve never rates your paper.
Key claims under review
- For independent stochastic rewards under winner feedback (and fixed arrays under Contrast or AllProbe), the minimax regret is Θ(min{(n−k)T/n, (n−k)/k}) with universal constants and anytime policies (Theorem 1).
- Under BestProbe with arbitrary joint i.i.d. rewards or fixed arrays, the minimax regret is Θ((n−k)/n · min{T, (n+T)/k, √(nT/k)}); the learning term is irreducible, proved by a correlated threshold family (Theorem 2, App. G.3).
- Two probes suffice for bounded, horizon-independent regret of order n under the weaker BestProbe interface, resolving the open questions of Bhaskara et al. (2023).
- Winner labels alone match the BestProbe law up to T ≍ nk, after which numerical maxima improve the rate by a factor Θ(√(T/(nk))) (Corollary 11 and (6.3)).
- For downward-closed action families containing all singletons, horizon-independent regret holds iff every pair of arms is a feasible action (Proposition 15).
Strengths
Complete minimax characterizations
Theorems 1 and 2 give matching order upper and lower bounds with explicit universal constants (e.g., ½Φ ≤ V ≤ 1400Φ in Thm 1; (1/1024)R ≤ V ≤ 64R in Thm 2) and anytime policies, including the exact T=1 value (n−k)/n (App. A).
Resolves explicit open problems
Table 1 shows Bhaskara et al. (2023) had O(n² log T) for k=2 BestProbe, O(n²) for k=3 AllProbe, and e^O(n^{8/3}T^{1/3}) for k=4; this paper proves Θ(Φ) with k=2 under the weaker BestProbe interface, answering both of their stated questions.
Novel technical machinery
Ablation-style necessity examples
Honest scope and useful extensions
Weaknesses
Unwieldy explicit constants
No empirical validation
Proof load rests on unverifiable appendix chains
Thin quantitative related-work positioning
AI-assisted proof exploration
Full Review Report
$1.99 · one-timeUnlock the complete preliminary analysis Evolve produced for this paper.
Report preview
Preliminary Review: Bandits with Probing (arXiv 2609.15248)
The remaining sections cover Methodology Assessment, Statistical Evidence, Results & Reproducibility, Limitations & Risks, and Verdict & Recommendations.
- 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 a bandit with probing?
A bandit variant where, each round, the learner may probe up to k of n arms and receives the maximum of the probed rewards in [0,1] — under winner feedback also the identity of the winning arm — while regret is measured against the single best fixed arm.
What is the paper's main result?
Two matching minimax regret laws: with independent rewards (or fixed sequences with signed contrast feedback), regret Θ(min{(n−k)T/n, (n−k)/k}), which is bounded for any k≥2; allowing arbitrary within-round reward dependence under winner-only feedback adds an irreducible learning term, giving Θ((n−k)/n · min{T, (n+T)/k, √(nT/k)}).
Does probing two arms already give bounded regret?
Yes. The paper proves Θ(n) horizon-independent regret with k=2 under the weaker BestProbe interface, answering an open question of Bhaskara et al. (2023), whose earlier bound for this case was O(n² log T).
Does the paper include code or experiments?
No. It is purely theoretical: the algorithms (e.g., Algorithm 1 with gain banks, the contrast policy, and the gate procedures) are fully specified, but no code repository or empirical evaluation is reported.
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.
- Mathematical notation is mangled by text extraction (subscripts, min/√ symbols); quoted constants follow the printed text as extracted.
- Appendix proofs are present in the extraction but were not independently re-derived; the review assesses claim structure and stated lemmas, not line-by-line proof correctness.
- No figures exist beyond tables; Table 1 and Table 2 were extracted as text only.
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.