Exact Bayes Regret and Asymptotic Optimality in High-Dimensional Gaussian Bandits
Prakhar Singhvi, Yi Zou, Abhishek Bhattacharjee
stat.ML · cs.LG · math.ST
Quick verdict
This paper derives closed-form proportional-regime Bayes regret curves for Gaussian bandits, proving greedy is asymptotically optimal and beats Thompson sampling; proofs look coherent but lack numerical validation.
Summary
This paper analyzes Bayesian linear bandits in the proportional regime where horizon T and dimension d grow with T/d → s. Its core result is that the posterior covariance trace converges, uniformly over all causal policies, to an explicit deterministic function v(s), so the amount of learning is policy-independent while decision quality is not. The authors derive closed-form cumulative regret curves for Thompson sampling, posterior-mean greedy selection, and a family of policies scaling the posterior sampling covariance, with L1 convergence of realized regret. A lower bound over the full causal policy class shows greedy attains first-order asymptotic Bayes optimality, while Thompson sampling incurs strictly larger regret; its instantaneous ratio to greedy lies in (1,2), approaching 2 at long proportional horizons but 3/2 in the vanishing-noise limit, with limit order stated explicitly. Instantaneous regret itself converges to a nondegenerate Gaussian decision-loss distribution. All claims are proved in five appendices, including a policy-uniform adaptive spectral comparison via entropy and Talagrand transport that avoids any state-evolution recursion. The main limitation is the strict scope: fixed candidate-arm count with isotropic Gaussian prior and candidates; correlated or growing pools are excluded, and no simulations or code verify the exact formulas.
Review complete
Assessment at a glance
4
risk flags identified
● high 0
● medium 3
● low 1
4 strengths · 4 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
- The normalized posterior covariance trace converges to an explicit deterministic limit v(s) uniformly over all causal policies, making the amount of information learned policy-independent in this model (Theorem 5.1).
- Posterior-mean greedy selection attains the infimum of first-order asymptotic Bayes regret over the entire causal policy class (Theorem 5.4).
- Thompson sampling incurs strictly larger leading regret than greedy; the instantaneous regret ratio is exactly 1+q(s) ∈ (1,2) and approaches 2 at long proportional horizons, but 3/2 in the sequential vanishing-noise limit (Theorems 5.5, 6.2, 6.3).
- The scaled instantaneous regret converges to a nondegenerate Gaussian decision-loss distribution rather than to a constant, so the expected regret curve is not a probability limit of individual-round regret (Theorem 5.6).
Strengths
Policy-uniform posterior state enables genuine optimization over policies
Theorem 5.1 proves a single scalar law v(s) for posterior trace, mean norm, and overlaps uniformly over ALL admissible policies (which may depend on d and T), with no state-evolution recursion assumed. Lemma A.1's entropy-plus-Talagrand coupling (E||X-Z||_F^2 ≤ 2N log K/d) is a clean mechanism that handles even nonlinear selection rules.
Sharper-in-constants conclusions rather than rate bounds
The paper delivers exact objects: regret curves ρ0, ρ1 (5.10), closed-form cumulative integrals (6.1)-(6.2), the exact instantaneous ratio 1+q(s) of Theorem 5.5, and explicit iterated limits in Theorem 6.3 (3/2 vs 2 depending on limit order). This quantifies differences that O(√(dT)) bounds cannot distinguish.
Correctly separates expectation limits from distributional limits
Honest scope discussion and explicit caveat placement
Weaknesses
Narrow model scope despite general-sounding title
No simulations or code whatsoever
'Exact' framing overstates first-order asymptotics
Reference list hygiene
Full Review Report
$1.99 · one-timeUnlock the complete preliminary analysis Evolve produced for this paper.
Report preview
Scope & Claims
The paper studies a K-armed Gaussian linear bandit (Definition 4.1) with θ* ~ N(0, τ²I_d), fresh candidates x_{t,a} ~ N(0, I_d/d), N(0, σ²) noise, and horizon T = ⌊Γd⌋. Its central claim is a two-layer separation: the *amount* of learning is policy-independent, while the *conversion* of learned information into reward is policy-dependent. Theorem 5.1 proves d^{−1}tr C_⌊sd⌋ → v(s) uniformly over all admissible causal policies, with v(s) the explicit MP-resolvent root of (A.2). From this, Theorem 5.3 derives deterministic regret curves ρ_η(s) and L1 convergence of realized cumulative regret; Theorem 5.4 proves posterior-mean greedy attains the asymptotic infimum over the *full* causal class; Theorem 5.5 gives the exact price of posterior randomization (instantaneous TS/greedy ratio = 1 + q(s)); Theorem 5.6 shows single-round regret scaled by d converges to a nondegenerate Gaussian loss; Section 6 works out closed forms and horizon–noise asymptotics, including the 3/2-vs-2 iterated-limit contrast of Theorem 6.3.
The remaining sections cover Methodology Assessment, Statistical Evidence, Results & Reproducibility, Limitations & Risks, and Verdict & Recommendations.
- All 4 strengths & 4 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 does this paper claim about Thompson sampling vs greedy in high-dimensional bandits?
In its proportional Gaussian model (horizon proportional to dimension, Gaussian prior and candidate arms), the paper proves that posterior-mean greedy selection achieves the lowest possible first-order Bayes regret over all causal policies, while Thompson sampling incurs strictly larger regret. The instantaneous regret ratio of Thompson sampling to greedy lies between 1 and 2, approaching 2 at long proportional horizons, and 3/2 in a vanishing-noise limit.
Why is Thompson sampling worse than greedy if they learn the same amount?
The paper's key separation is that no policy changes the leading (first-order) posterior uncertainty in this model — exploration cannot improve first-order learning. The extra posterior draw in Thompson sampling only perturbs the direction used to pick an arm, and that perturbation strictly lowers the immediate expected reward, so randomization pays a first-order decision price without any first-order information benefit.
What are the model assumptions and when do the conclusions apply?
The theory requires exactly: a fixed number K≥2 of candidate arms per round, an isotropic Gaussian prior on the parameter, independent isotropic Gaussian candidate vectors, Gaussian noise, and a horizon proportional to the dimension. Correlated arm pools, non-isotropic priors, growing pools, or other horizon scalings fall outside the proven scope and can change the conclusions.
Is the paper's regret formula exact, or an approximation?
It is exact only in the asymptotic sense: after normalizing by dimension and letting d→∞ with T/d → s, the normalized regret converges (in L1, uniformly on compact s-intervals) to closed-form deterministic curves. At finite dimension there are unquantified correction terms, so the word 'exact' should not be read as a finite-dimensional identity.
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.
- Extraction appears complete (main text plus all five appendices), but the review reflects this single extracted text; no external verification of references was performed.
- Proofs are compact; correctness judgments are at consistency-check level (e.g., resolvent fixed point, ratio identities, limit orders), not a full line-by-line refereeing.
- Figures are absent from the source; the paper appears to contain none, so no visual claims were assessed.
- The arXiv identifier (2609.28718) and several future-dated citations are as-extracted from the source text and could not be verified.
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.