{"id":"4a52a4eb-55b8-4356-8047-f48da8d4a867","arxiv_id":"1908.04970","paper_version":2,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":7.0,"correctness_risk":"low","formal_verification":"none","parameter_count":2,"one_line_summary":"A constant alpha-divergence bound between the true and approximate posterior does not guarantee sub-linear regret in Thompson sampling; adding forced exploration restores sub-linear regret for alpha<=0.","lead":"This paper analyzes Thompson sampling when the posterior is only known approximately, measured by alpha-divergence. It shows that small constant approximation error can cause linear regret, but for alpha<=0 adding forced exploration restores sub-linear regret.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 2's proof assumes finite-volume regions; without a corrected proof, Theorem 3 does not rigorously transfer small parameter-divergence to small arm-divergence for Gaussian priors.","rationale":"The reader's verdict of CONDITIONAL rests on two minor technical issues; I agree with that overall assessment. The more consequential of the two is the proof of Lemma 2, because it is the bridge that lets Theorem 3 (whose algorithm and proof are phrased with arm-marginal distributions) be applied to approximate inference methods whose stated error guarantee is about the full posterior distribution. Without a valid transfer, the positive claim that forced exploration restores sub-linear regret for α≤0 is not rigorously available for the Gaussian-prior case in Assumption 2. The negative Theorems 1 and 2 are self-contained and do not depend on Lemma 2; their constructions are explicit and the divergence bounds are uniform in t, so I see no significant objection to the central negative claim. The independence assumption in Theorem 2 is restrictive but is stated explicitly and suffices for an existential negative result, so I do not treat it as a flaw. The concrete check—re-proving Lemma 2 via the f-divergence data-processing inequality—is likely to succeed, in which case the proof gap is a presentation issue rather than a mathematical error. For that reason I recommend keeping the reader's CONDITIONAL verdict (no change), while flagging this lemma as the piece that should be fixed before publication.","tokens_in":18437,"tokens_out":38712,"duration_ms":365568,"concrete_test":"Replace the proof of Lemma 2 by invoking the data-processing inequality for f-divergences: for the measurable map φ(m)=argmax_i m_i, Dα(P,Q) ≥ Dα(P∘φ^{-1}, Q∘φ^{-1}). Verify that the α-divergence in Eq. (3) is an f-divergence with convex f(t)=(1−t^α)/(α(1−α)) for all relevant α, then the inequality holds without any finite-volume condition. If the corrected proof goes through, the gap is closed. As an independent numerical check, sample random Gaussian posteriors on R^2 (means and covariances) and compute both divergences for α∈{−1,0,0.5}; a single violation would show the lemma is false, whereas agreement supports the DPI-based fix.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Appendix C proves Lemma 2, which states that the α-divergence between the arm-marginal distributions is at most the α-divergence between the full posterior and approximation, by applying Lemma 9 with a uniform density 1/|S| on each best-arm region S=Ω_i. Lemma 9 requires the volume |S| to be finite. Under Assumption 2 (the uncorrelated multivariate Gaussian prior), the parameter space is R^k and the regions Ω_i={m:mi=max_j m_j} have infinite volume, so the Jensen argument in the proof is not defined. This matters because Theorem 3 is stated for the arm-marginal divergence Dα(Π_t,Q_t)<ε, while the inference-error measure in the paper's problem statement and in the Ensemble sampling/mean-field applications is the full parameter divergence Dα(Π_t,Q_t)<ε. The transfer from one to the other is precisely Lemma 2. If the lemma is not established for unbounded supports, the positive result for α≤0 is not rigorously connected to the parameter-space error guarantees for Gaussian priors. The inequality is the data-processing inequality for f-divergences and is very likely true; the issue is that the proof as written does not show it, so the theorem's applicability to Assumption 2 is not yet supported.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies Thompson sampling with approximate inference in k-armed bandits, measuring inference error by alpha-divergence. It shows that if the approximate posterior is only required to have small constant alpha-divergence from the true posterior at every round, then Thompson sampling can suffer linear frequentist and Bayesian regret: for alpha>0 through an over-exploring construction (Theorem 1, Corollary 1), and for alpha<1 through an under-exploring construction under an independence condition on the prior (Theorem 2, Corollary 2). Conversely, for alpha<=0, the paper proposes adding forced exploration with probability p_t=o(1) and sum p_t=infinity, and proves sublinear regret (Theorem 3). The negative constructions are explicit and checkable; the positive result depends on an external posterior-concentration lemma from Russo (2016) and on Lemma 2, which transfers a divergence bound from parameter space to the distribution over the best arm.","tokens_in":18691,"tokens_out":17310,"duration_ms":143463,"significance":"If the results stand, the paper delivers a clean message: an alpha-divergence error bound alone is not a sufficient statistic for the exploration behavior of Thompson sampling, and forced exploration can repair the problem for alpha<=0. The constructive lower bounds are built from explicit posterior reweightings rather than fitted parameters, which makes Theorems 1 and 2 robust and easy to verify. The paper also connects the discussion to Ensemble sampling and mean-field variational inference, and its simulations support the main intuition. The main open point for the positive result is the rigor of Lemma 2 for unbounded Gaussian parameter spaces, which is true but requires a corrected proof.","major_comments":[{"comment":"The proof of Lemma 2 applies Lemma 9 with the uniform density 1/|S| on each best-arm region S=Omega_i, which requires |Omega_i| to be finite. Under Assumption 2 (uncorrelated multivariate Gaussian prior) the parameter space is R^k and the regions Omega_i={m:m_i=max_j m_j} have infinite volume, so the Jensen argument as written is undefined. This matters because Theorem 3 is stated for Assumption 2 and its proof needs the arm-level bound D_alpha(Pi_t,Q_t)<epsilon to follow from the parameter-level bound, making Lemma 2 load-bearing. The inequality itself is the data-processing inequality for f-divergences under the deterministic map m -> argmax_i m_i and is true; please replace the proof with an explicit data-processing argument or a limiting argument over finite-volume truncations of Omega_i.","section":"Lemma 2 (main text, proof in Appendix C)"},{"comment":"The paper overloads the symbols Pi_t and Q_t: immediately before Theorem 3 they are defined as distributions on the best arm, while in the problem statement and in Lemma 2 they are distributions on the parameter vector. Theorem 3 states D_alpha(Pi_t,Q_t)<epsilon without specifying which pair, and the paragraph after Lemma 2 says 'whenever the condition D_alpha(Pi_t,Q_t)<epsilon is satisfied, the condition D_alpha(Pi_t,Q_t)<epsilon will be satisfied' with identical notation for both. This ambiguity makes the logical chain from the parameter-space guarantee to Lemma 10 hard to verify. Please introduce distinct symbols for the arm-level and parameter-level distributions and rewrite the affected statements.","section":"Section 5.1, Theorem 3, and Lemma 2"}],"minor_comments":[{"comment":"In the alpha=1 entry, the factor 1-1/e^epsilon is correct but can be read as a misprint; writing e^{-epsilon} would be clearer.","section":"Appendix A, Lemma 5"},{"comment":"The captions read 'epsilon as a function z' and should be 'epsilon as a function of z'.","section":"Section B.4, Figure 5 captions"},{"comment":"The claim that Lemma 10 applies when the KL bound holds only on a subset of times T0 is informal; Lemma 10 as stated requires the bound at all times. The intended subsequence argument should be made explicit if this application is meant to be more than heuristic.","section":"Section E"},{"comment":"When alpha=0 or alpha=1, D_alpha is defined by its limiting value; stating this explicitly next to Eq. (3) would help the reader.","section":"Section 2.3, Eq. (3)"}],"recommendation":"major_revision","confidential_remarks":"The central negative results are constructive and sound; the main defect is the proof of Lemma 2 for unbounded supports, which is a genuine gap affecting Theorem 3's applicability to Gaussian priors but is easily fixed by a data-processing-inequality proof. The paper is a worthwhile contribution; with the lemma repaired and the notation cleaned up, I would support acceptance."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: this is a solid theory paper. It shows that a constant α-divergence bound between posterior and approximation is not enough to guarantee sublinear regret for Thompson sampling, and that for α≤0 a small forced-exploration rate restores sublinearity. The counterexamples in Theorems 1 and 2 are constructed, not fitted, and the proofs are mostly checkable. That is the real contribution; I haven't seen this characterization elsewhere.\n\nThe positive result (Theorem 3) is also new and practically useful: add p_t=o(1) exploration with divergent sum, and under the Russo/Qin assumptions you get o(T) regret even with a large constant error. The application to Ensemble sampling with Θ(log T) models in Appendix E is a nice touch.\n\nSoft spots, in order:\n1. Lemma 2, which transfers a parameter-space divergence bound to the arm-marginal divergence, is proved via a Jensen step over regions Ω_i with a uniform density 1/|Ω_i|. Under the Gaussian prior (Assumption 2) those regions have infinite volume, so the proof as written doesn't apply. The inequality itself is just the data-processing inequality for f-divergences, so the math is almost certainly true, but the proof needs a limiting argument or a direct DPI citation. Since Theorem 3's applicability to Gaussian priors relies on this transfer, the paper should fix it before publication.\n2. Theorem 2's independence assumption (M2 ⊥ M1−M2) is doing a lot of work. The authors state it plainly, but it means the under-exploration lower bound only applies to a restricted class of priors. Fine as a lower bound, just don't over-generalize.\n3. No code for the simulations. Not a correctness problem, and the simulations are illustrative, but reproducibility would be better with code.\n\nThe citation pattern looks honest; Lu & Van Roy is the right comparison, and the authors are clear about what is new and what depends on external lemmas. The 'deterministic mapping f' existence results are carefully worded so as not to overclaim.\n\nBottom line: this deserves a serious refereeing. The main theorems are likely correct, the Lemma 2 proof gap is real but patchable, and the paper gives a clear takeaway: with α>0 constant inference error can be fatal; with α≤0 forced exploration rescues you. I'd send it to review.","headline":"A clean existence result showing constant α-divergence error can break Thompson sampling; the forced-exploration fix for α≤0 is new, but Lemma 2's proof needs a patch for unbounded parameter spaces.","tokens_in":19214,"tokens_out":3536,"would_cite":true,"duration_ms":33254,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper shows that even a small constant error in the approximate posterior, measured by alpha-divergence, can make Thompson sampling incur linear regret, and that for alpha <= 0 a small amount of forced exploration restores sublinear…","keywords":["Thompson sampling","approximate inference","alpha-divergence","multi-armed bandits","regret bounds","forced exploration","posterior concentration","exploration-exploitation"],"falsifier":"Run a two-armed Gaussian bandit with a prior where M2 and M1-M2 are dependent, and use the paper's under-exploring approximation that always puts mass on the suboptimal arm. If the alpha-divergence to the true posterior grows with time and the regret becomes sublinear, the independence condition is essential to the construction; if the regret stays linear, the phenomenon is broader than the stated assumptions.","tokens_in":18223,"feed_emoji":"🎰","tokens_out":8851,"duration_ms":78356,"temperature":0.7,"pith_summary":"The paper studies Thompson sampling when the posterior distribution is only approximated, with the error measured by alpha-divergence. It establishes that for any positive error threshold, there are approximate posteriors within that threshold that cause linear regret: over-exploration when alpha > 0 and under-exploration when alpha < 1. For alpha <= 0, it proves that adding a forced-exploration step—choosing an arm uniformly at random with probability p_t that decays to zero but sums to infinity—restores sublinear regret even when the approximation error is a large constant. These results matter because exact posterior inference is rarely available in practice, so knowing which approximation errors are harmless and which are fatal guides the design of practical Thompson sampling variants.","feed_headline":"Tiny inference errors can push Thompson sampling to linear regret","feed_subtitle":"Some epsilon-close posteriors under- or over-explore; when alpha is nonpositive, forced exploration restores sublinear regret.","key_machinery":"The key object is the $\\alpha$-divergence D_alpha(P,Q) = (1 - integral p^$\\alpha$ q^(1-$\\alpha$) dx) / ($\\alpha$(1-$\\alpha$)), a family that includes reverse KL ($\\alpha$ to 0), forward KL ($\\alpha$ to 1), Hellinger ($\\alpha$ = 1/2), and chi-squared ($\\alpha$ = 2). The sign of $\\alpha$ determines which region of the posterior the approximation preserves: small $\\alpha$ fits the dominant mode, while large $\\alpha$ covers the whole support. The paper constructs explicit approximate distributions that shift probability mass from the region where the best arm is identified to the suboptimal-arm region; for $\\alpha$ > 0 this creates over-exploration, while for $\\alpha$ < 1 the posterior fails to concentrate because pulling the suboptimal arm reveals nothing about the ranking (under the independence assumption). For $\\alpha$ <= 0, the proof leverages a posterior-concentration lemma: if every arm is chosen infinitely often, the posterior probability of the true best arm tends to 1, and the divergence bound then forces the approximation to concentrate as well.","core_discovery":"The core discovery is that a constant bound on the alpha-divergence between the true posterior and the approximate posterior is, by itself, insufficient to guarantee good regret: for any epsilon > 0 and any alpha, there exist approximate posteriors satisfying D_alpha(Pi_t, Q_t) < epsilon at every step that make Thompson sampling choose the wrong arm a constant fraction of the time (for alpha > 0) or always (for alpha < 1 under an independence condition), yielding linear frequentist and Bayesian regret. Conversely, for alpha <= 0, the same divergence constraint is benign once the algorithm is augmented with a uniform-random action with probability p_t = o(1) and sum_t p_t = infinity; then the posterior concentrates and the regret becomes o(T).","pith_inferences":["A reader might infer that the alpha-divergence value alone is not the right diagnostic for approximate Thompson sampling; what matters for regret is whether the approximation preserves the probability mass assigned to the optimal-arm region, so benchmarking algorithms solely by divergence error is insufficient.","The independence condition in the under-exploration theorem is probably not sharp: with dependent means, alternative approximation constructions might still block posterior concentration, but the paper's explicit construction would need modification.","The same divergence-parameterized analysis could extend to other Bayesian sequential decision problems, such as Bayesian optimization or active learning, where the analogue of forced exploration is an informative query rather than a uniform one."],"forward_implications":["Any practical approximate inference scheme for Thompson sampling must either keep the alpha-divergence error below a shrinking threshold for all but o(T) steps, or pair the algorithm with forced exploration when alpha <= 0.","The negative result for alpha > 0 cannot be repaired by forced exploration; methods whose approximation errors fall in that regime (for example, those minimizing forward KL or chi-squared divergence) need a different safeguard.","For alpha <= 0, a simple uniform-random action with decaying probability converts a linearly-regretting approximate sampler into one with o(T) regret, provided the underlying posterior-concentration lemma applies.","The paper shows that methods such as ensemble sampling and mean-field variational inference, which are known to under-explore, can be improved by this forced-exploration step in theory and in simulations."],"supporting_citations":[{"why":"Supplies Lemma 1: if every arm is chosen infinitely often, the posterior probability of the true best arm converges to 1; also provides Assumption 1 for correlated priors.","marker":"Russo (2016)"},{"why":"Supplies Assumption 2, an alternative Gaussian-prior setting under which the same posterior-concentration lemma holds.","marker":"Qin et al. (2017)"},{"why":"Proves the sublinear Bayesian regret of exact Thompson sampling that the paper's corollaries show can turn linear under approximation.","marker":"Russo & Roy (2016)"},{"why":"Proves sublinear frequentist regret for exact Thompson sampling under standard priors; serves as the baseline that the negative results contrast with.","marker":"Agrawal & Goyal (2013)"},{"why":"Introduces ensemble sampling and its linear regret in the k-armed case with a constant number of models; the paper shows forced exploration can improve it.","marker":"Lu & Van Roy (2017)"},{"why":"Explains the mode-covering versus support-covering behaviour of alpha-divergence used to interpret over- and under-exploration.","marker":"Minka (2005)"}],"fun_headline_variants":["Small inference error can break Thompson sampling","Approximate posteriors can cause linear regret in TS","For alpha<=0, forced exploration fixes Thompson sampling","Constant alpha-divergence error is not enough for TS","Add exploration to survive approximate inference in TS"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The under-exploration negative result assumes that, under the prior, the suboptimal arm's mean is independent of the difference between the two means, so pulling the wrong arm teaches the algorithm nothing about which arm is better.","fun_headline_variants_meta":{"raw":{"variants":["Small inference error can break Thompson sampling","Approximate posteriors can cause linear regret in TS","For alpha<=0, forced exploration fixes Thompson sampling","Constant alpha-divergence error is not enough for TS","Add exploration to survive approximate inference in TS"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000201,"raw_usage":{"total_tokens":1309,"prompt_tokens":808,"completion_tokens":501,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":424,"completion_tokens_details":{"reasoning_tokens":429}},"tokens_in":424,"tokens_out":501,"duration_ms":5857,"temperature":1.0,"reasoning_tokens":429,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T13:28:07.362125+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run a two-armed Gaussian bandit with a prior where M2 and M1-M2 are dependent, and use the paper's under-exploring approximation that always puts mass on the suboptimal arm. If the alpha-divergence to the true posterior grows with time and the regret becomes sublinear, the independence condition is essential to the construction; if the regret stays linear, the phenomenon is broader than the stated assumptions.","supporting_citations":[{"cited_title":"Improving the expected improvement algorithm","cited_arxiv_id":null,"evidence_quote":"Supplies Assumption 2, an alternative Gaussian-prior setting under which the same posterior-concentration lemma holds."},{"cited_title":"and Goyal, N","cited_arxiv_id":null,"evidence_quote":"Proves sublinear frequentist regret for exact Thompson sampling under standard priors; serves as the baseline that the negative results contrast with."},{"cited_title":"Divergence measures and message passing","cited_arxiv_id":null,"evidence_quote":"Explains the mode-covering versus support-covering behaviour of alpha-divergence used to interpret over- and under-exploration."}],"review_version":1}