When Greedy Sampling Explores: KL-Regularized Contextual Bandits without Eluder-Dimension Dependence
Zichen Wang, Haoyang Hong, Huazheng Wang
cs.LG
Quick verdict
First eluder-free polylog regret for KL-regularized bandits via greedy sampling; analysis looks sound but carries e^{2η} factors and experiments are toy.
Summary
This theory paper studies KL-regularized contextual bandits under reward feedback (RF) and preference feedback (PF), showing that plain greedy sampling — drawing actions from the Gibbs policy induced by the current least-squares/MLE estimate — achieves polylogarithmic regret without explicit eluder-dimension dependence. For RF, Theorem 1 gives O(ηe^{2η} log T · log(N_R T/δ)) under a finite reward class, improving on the dimension-dependent guarantee of K-UCB (Zhao et al., 2025b). Theorems 2–3 extend the guarantee via Wu et al.'s (2025a) ORLHF-GS to the general preference and Bradley–Terry models, and sharpen their dimension-dependent GP bound from ηe^{3η}+η³e^{9η} to ηe^{η}. The authors also analyze UCB-style counterparts (GP-UCB, BT-UCB) and characterize a trade-off: greedy wins when e^{2η} log T ≲ eluder dimension (strong regularization), UCB wins as η grows, and K-UCB saturates at a √T rate. The analysis rests on regret-to-prediction-error decompositions (Lemmas 4, 5, 7), Freedman-type uniform convergence, and likelihood-ratio boundedness of Gibbs policies. Main limitations: bounds degrade exponentially in η; results cover only finite function classes (the infinite-class extension is asserted, not proven); and the sole experiment is a small synthetic RF-only comparison (3 contexts, 3 actions, 5 functions, T=5000, 10 seeds) against K-UCB, with no PF experiments.
Review complete
Assessment at a glance
4
risk flags identified
● high 0
● medium 3
● low 1
4 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
- Greedy sampling from the Gibbs policy of the least-squares estimate achieves eluder-dimension-independent regret O(ηe^{2η} log T·log(N_R T/δ)) for KL-regularized contextual bandits with reward feedback (Theorem 1).
- The same greedy algorithm achieves eluder-free bounds under preference feedback: O(ηe^{3η} log T·log(N_P T/δ)) for the general preference model and O(ηe^{2η} log T·log(N_R T/δ)) for Bradley–Terry (Theorems 2–3).
- The dimension-dependent GP analysis improves Wu et al. (2025a)'s ηe^{3η}+η³e^{9η} dependence to ηe^{η} (Theorem 2).
- Greedy sampling's bound is sharper than UCB-style bounds when e^{2η} log T ≲ d_RF, while optimism wins as regularization weakens and K-UCB saturates at a √T rate (Section 4, Corollary 4).
- A synthetic experiment (Section 6, Fig. 1) qualitatively confirms the predicted greedy-vs-UCB transition across η ∈ {0.5, …, 2000}.
Strengths
First eluder-dimension-free polylogarithmic rates for KL-regularized bandits under both RF and PF
Theorem 1 gives O(ηe^{2η} log T·log(N_R T/δ)) for RF-GS; Theorems 2–3 extend to GP (O(ηe^{3η} log T·log(N_P T/δ))) and BT via ORLHF-GS, removing the d_GP/d_BT terms present in Wu et al. (2025a).
Genuine sharpening of existing dimension-dependent bounds
The GP bound improves Wu et al.'s (2025a, App. D.1) ηe^{3η}+η³e^{9η} to ηe^{η} (Theorem 2), driven by the exact KL identity and Bregman-divergence argument in Lemma 5 rather than black-box tools.
Complete, self-contained proofs with explicit constants
Clear regime characterization of greedy vs. optimism
Weaknesses
Exponential η factors undercut the headline claim
Finite-class-only theory
Minimal empirical support
Incremental novelty over Wu et al. (2025a)
Trade-off compares upper bounds, and 'UCB' naming is loose
Full Review Report
$1.99 · one-timeUnlock the complete preliminary analysis Evolve produced for this paper.
Report preview
Scope & Claims
The paper (arXiv:2609.13564v2, cs.LG) studies KL-regularized contextual bandits with full-support reference policies, finite reward/preference classes under realizability (Assumptions 1–2), and three feedback models: reward (RF), general preference (GP), and Bradley–Terry (BT). The headline claim is the first eluder-dimension-independent polylogarithmic regret for greedy sampling in this family. Theorem 1 bounds RF-GS (Algorithm 1), which each round runs least squares and samples from the Gibbs policy of the estimate (Eq. 4), by O(ηe^{2η} log T · log(N_R T/δ)). Theorems 2–3 transfer this to preference feedback via Wu et al.'s (2025a) ORLHF-GS (Algorithm 2, imported unchanged): O(ηe^{3η} log T log(N_P T/δ)) for GP and O(ηe^{2η} log T log(N_R T/δ)) for BT. Companion dimension-dependent results sharpen Wu et al.'s GP bound from ηe^{3η}+η³e^{9η} to ηe^{η}, and UCB-style counterparts (K-UCB in Corollary 4; GP-UCB/BT-UCB in Corollaries 2–3) achieve eO(min{ηd, √(dT)}). Section 4 formalizes the trade-off: greedy wins when e^{2η} log T ≲ d_RF; UCB wins as η grows; K-UCB saturates at a √T rate.
The remaining sections cover Methodology Assessment, Statistical Evidence, Results & Reproducibility, Limitations & Risks, and Verdict & Recommendations.
- All 4 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 eluder dimension and why does removing it matter?
The eluder dimension measures how long a function class can keep 'fooling' sequentially chosen queries; regret bounds for optimistic (UCB) bandit algorithms typically grow with it, and it can be large for rich function classes. This paper proves that, under sufficiently strong KL regularization toward a reference policy, plain greedy sampling attains polylogarithmic regret whose complexity is only logarithmic in the horizon and in the size of a finite function class — with no eluder term — under both reward- and preference-based feedback.
What are the main regret bounds proven in the paper?
Theorem 1: greedy sampling from the least-squares Gibbs policy gives O(ηe^{2η} log T·log(N_R T/δ)) regret for KL-regularized contextual bandits with reward feedback. Theorem 2: O(ηe^{3η} log T·log(N_P T/δ)) under the general preference model, plus a sharpened dimension-dependent bound with ηe^{η} dependence. Theorem 3: O(ηe^{2η} log T·log(N_R T/δ)) under the Bradley–Terry model. UCB-style counterparts achieve eO(min{ηd, √(dT)}) with the relevant eluder dimension.
When does greedy sampling beat UCB in KL-regularized bandits?
According to the paper's comparison of upper bounds, the greedy bound O(ηe^{2η} log T·log(N_R T/δ)) is sharper when e^{2η} log T is below the eluder dimension — i.e., under strong KL regularization (small η). As η grows, the exponential factor dominates and UCB-style bounds (η·d or √(T·d)) become sharper; for very large η, K-UCB saturates at the standard √T-type contextual-bandit rate. A small synthetic experiment reproduces this transition qualitatively.
Is code or data available for the experiments?
The provided text contains no code or data availability statement. The experiment described is small and synthetic (3 contexts, 3 actions, 5 reward functions, T=5000 rounds, 10 seeds), but the five functions in the class R are not specified, so exact replication would require author clarification.
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.
- Figures are not part of the extracted text: Section 6's experimental claims rest on Fig. 1, whose curves could not be inspected (only the caption and surrounding prose are present). All lemmas, proofs, and references appear complete through the end of Appendix E.
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.