{"id":"31f08cf7-8389-47e7-bbf3-e7d6335f9b5b","arxiv_id":"2505.23927","paper_version":1,"verdict":"REJECT","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"high","formal_verification":"none","parameter_count":0,"one_line_summary":"A model-free posterior sampling algorithm for online RLHF is shown to achieve O(sqrt(T)) regret when the completed function class has low Bellman eluder dimension.","lead":"The paper designs a Thompson sampling algorithm for reinforcement learning from human feedback, where the model learns from pairwise comparisons of trajectories, and proves a regret bound that grows with the square root of the number of rounds. It is a theoretical contribution aimed at understanding when preference-based learning is statistically efficient.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The paper never proves that the posterior sample f^t used in Algorithm 1 belongs to the confidence set V_1^F on which Lemma B.6's Bellman-error concentration is stated; the §B.2 remark that f 'plays the role of MLE maximizer' is unsupported and is load-bearing for Step III.","rationale":"The reader's weakest assumption identifies exactly the load-bearing gap in the proof. The central claim is the theorem's high-probability regret bound, and the proof's Step III is the only place where the Bellman eluder dimension controls cumulative Bellman error. To invoke Lemma B.6 on the selected function, the paper needs the realized posterior draw f^t to be in the confidence set V_1^F. The MLE generalization bound in Lemma B.4 controls the expected squared distance between two posterior draws, which is a statement about the posterior distribution, not about any single realized draw. A random draw from the posterior can be far from the MLE, especially early in the run, and the paper provides no concentration argument turning the posterior-averaged bound into containment of the realized f^t. The sentence in Section B.2 is the only attempted bridge, and it is incorrect: greedy selection in the algorithm selects a policy from a posterior sample, not the MLE. This is a correctness-level flaw, not a missing detail. The ill-posed definition of V_1^F in Eq. (4) (the membership condition does not depend on the candidate f) reinforces that the proof structure needs repair. The paper's own admission that function-class completion can destroy low Bellman eluder dimension is a secondary concern because the theorem is conditional on the completed class having low BE dimension; the posterior-containment gap is more fundamental. The novelty of combining MLE-based concentration with model-free Thompson sampling is real, but the proof as written does not support the claimed guarantee. The simulation uses variational inference rather than exact posterior sampling and cannot substitute for the missing proof step. Therefore the reader's reject verdict is justified, and no adjustment is needed.","tokens_in":21198,"tokens_out":7972,"duration_ms":76511,"concrete_test":"Independently re-derive the Step III application to the realized posterior draw: starting only from Lemma B.4, prove that the f^t drawn in Algorithm 1 satisfies sum_{i=1}^{t-1} E_{x~pi^i_0}[(f^t_h(x) - T_h f^t_{h+1}(x))^2] <= O(beta^F_h(t) + beta^F_{h+1}(t)) with probability at least 1 - delta. A concrete counterexample worth trying: take a finite class F = {f_1, f_2} with uniform prior, and let the MLE after the first round be f_1 while the posterior assigns f_2 probability 1/4; compute the probability that a posterior draw at round 2 is f_2 and that f_2's squared deviation from the MLE exceeds the V_1^F threshold. If this probability exceeds delta, the Step III invocation fails for that instance.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Algorithm 1 (line 3) samples f^t from the posterior p(f | D_{t-1}), a random draw. Step III of the proof of Theorem 4.1 applies Lemma B.6 and Lemma D.3 to the realized sequence phi_t = f^t_h - T_h f^t_{h+1}. Lemma B.6, however, controls the cumulative squared Bellman error only for functions f in the MLE-based confidence set V_1^F defined in Eq. (4). No lemma shows that a posterior draw lies in V_1^F. The only bridge, Section B.2, states that 'f obtained by greedy selection in the algorithm plays the role of MLE maximizer bf', which conflates sampling from the posterior with maximizing the likelihood. A posterior draw is not the argmax of the posterior, and the MLE generalization bound (Lemma B.4) bounds posterior-averaged squared deviations, not the deviation of each realized draw. Without containment of f^t in V_1^F, the bound on the cumulative squared Bellman error of the realized f^t is not established, so the eluder-dimension argument in Step III collapses. Additionally, the definition of V_1^F in (4) as written includes an inner expectation over f_h sampled from the posterior, making the membership condition independent of the candidate f; this ill-posed definition must be repaired before the argument can be assessed.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies online RLHF with general function approximation and proposes Algorithm 1, a model-free Thompson sampling algorithm that samples an action-value function from the posterior and plays greedy policies. The main result (Theorem 4.1) claims a high-probability regret bound O(H sqrt(d t beta_G)) for all t, where d is the Bellman eluder dimension of a completed function class G_F and beta_G is a log-bracketing complexity term. The analysis introduces a confidence set V_1^F based on an MLE generalization bound and derives a squared Bellman error concentration inequality (Lemma B.6) to feed into the Bellman eluder dimension argument.","tokens_in":21411,"tokens_out":5690,"duration_ms":51777,"significance":"If the main theorem were proved, the paper would provide the first eluder-type regret bound for model-free Thompson sampling in RLHF, a useful complement to the confidence-set method of Chen et al. [7] and the model-based randomized algorithm of Wu and Sun [48]. The MLE-based concentration inequality (Lemma B.4/B.6) is a potentially interesting technical contribution, and the paper openly discusses limitations of the function-class completion. However, the central proof step—linking the posterior sample drawn in Algorithm 1 to the MLE-based confidence set—is missing, and the definition of V_1^F is ill-posed. These issues undermine Theorem 4.1 as stated.","major_comments":[{"comment":"The confidence set V_1^F is ill-defined. The membership condition contains an inner expectation E_{f_h}[ (f_h(x_t) - hat f_h(x_t))^2 | H_{t-1} ], where f_h is sampled from the posterior; this expression does not depend on the candidate function (f_1,...,f_H) being tested. Consequently V_1^F is either empty or equal to all of F, making the 'for any f in V_1^F' statements in Lemma B.6 vacuous or trivial. The definition must be repaired before the argument can be assessed.","section":"Appendix B.2, Eq. (4)"},{"comment":"The proof never establishes that the posterior sample f^t used in Algorithm 1 lies in V_1^F. Algorithm 1 draws f^t from p(f|D_{t-1}), but Lemma B.6 controls the cumulative squared Bellman error only for functions in V_1^F, and Step III invokes Lemma B.2(1) with phi_t = f^t_h - T_h f^t_{h+1} for the realized f^t. The single bridging sentence, 'f obtained by greedy selection in the algorithm plays the role of MLE maximizer hat f', conflates sampling from the posterior with maximizing the likelihood; a posterior draw is not the MLE. Since Lemma B.4 bounds posterior-averaged squared deviations rather than the deviation of a realized draw, the needed containment f^t in V_1^F is unproven and the eluder argument collapses.","section":"Appendix B.2 and Step III of Appendix C"},{"comment":"The paper defines regret as a frequentist quantity in Section 2, but the proof in Step I of Section 4.4 and Appendix C replaces it with Bayesian regret by writing Regret(T) = E_{f*} [ V^{pi^t_0}_{1;f^t} - V^{pi^t_0}_{1;f^*} ] (s_1) and using posterior exchangeability of f^t and f*. That identity holds only for the Bayesian regret, not for the high-probability regret bound stated in Theorem 4.1. The connection between the Bayesian argument and the claimed 'with probability at least 1-delta' statement is not made explicit, so the theorem's statement is not supported by the proof as written.","section":"Section 4.4 and Theorem 4.1"},{"comment":"The completed function class G_F is an assumption object, not a construction, and the paper itself notes that for finite F the completion may have log-covering number Theta(T), potentially yielding linear regret. The bound in Theorem 4.1 depends on d = dim_BE(G_F), but the paper does not show that d is small for nontrivial classes beyond the linear case. This makes the practical scope of the claimed O(sqrt(T)) regret unclear, though it is an assumption rather than an internal inconsistency.","section":"Section 3.1"}],"minor_comments":[{"comment":"'crucial rules' should be 'crucial roles' in both occurrences.","section":"Abstract and Section 5"},{"comment":"'Thomson sampling' should be 'Thompson sampling'.","section":"Appendix E"},{"comment":"'exiting sample-efficient RL algorithms' should be 'existing sample-efficient RL algorithms'.","section":"Related Works"},{"comment":"Equation (2) sums over t=1 to T, while Step II in Appendix C sums over t=0 to T; the indexing should be unified.","section":"Section 4.3, Eq. (2)"},{"comment":"The notation 'p(·|S_{t-1})' is confusing; it should be 'p(·|D_{t-1})' or 'p(·|H_{t-1})'.","section":"Algorithm 1, line 3"},{"comment":"The display 'r(τ^i) = P H h=1 = r(...)' contains an extra equality sign and should be corrected.","section":"Section 2.1"},{"comment":"The statement quantifies 'for all f in V_1^F' but the left-hand side uses f^t and the right-hand side uses beta terms; the connection between the quantified f and the sequence f^t is not defined, which makes the lemma hard to parse.","section":"Lemma B.6"}],"recommendation":"reject","confidential_remarks":"The paper addresses a timely and important problem, and the authors are clearly aware of the relevant literature. However, the central technical gap—showing that posterior draws used by the algorithm satisfy the Bellman error concentration inequality required by the eluder argument—is substantial and not a local fix. The ill-posed definition of V_1^F compounds the problem. The novelty relative to [21] and [48] is incremental, and the main advertised contribution is not established by the submitted proofs. I would not encourage a quick resubmission without a genuinely new concentration argument for posterior sampling."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The headline is that the paper's core claim is not supported as written, and the stress-test note correctly finds the weak point: Algorithm 1 draws f^t from the posterior, but the only Bellman-error concentration (Lemma B.6) is proven for functions in the MLE-based set V_1^F, and no step shows a posterior draw belongs to that set. The remark in Section B.2 that the greedy-selected f 'plays the role of MLE maximizer' is not an argument, because a posterior draw is not the argmax of the likelihood and the MLE generalization bound (Lemma B.4) controls posterior-averaged squared deviations, not each realized draw. On top of that, the definition of V_1^F in (4) as written puts an inner expectation over f_h drawn from the posterior inside the defining inequality, which makes membership independent of the candidate tuple (f_1,...,f_H). That definition has to be repaired before the lemmas can even be evaluated. What the paper does well: it identifies a genuinely new object - model-free posterior sampling for online RLHF with general function approximation - and the idea of deriving a Bellman-error concentration from the MLE generalization bound is the right kind of bridge between Thompson sampling and eluder-type analysis. The writing is clear and the authors are honest about the soft spots: they explicitly flag that the completed function class can destroy the low Bellman-eluder dimension (they say finite classes can end up with linear regret) and that the empirical section uses variational inference rather than exact posterior sampling. The other weaknesses are secondary but real: the theorem is stated as a high-probability bound while the analysis is Bayesian (the step showing f^t and f^* are identically distributed is an in-expectation argument), and the simulation is qualitative with no code. The known-transition assumption is also restrictive, though acceptable for a first cut. Who this is for: people working on Thompson sampling in RLHF theory, or on eluder-type analyses of randomized algorithms. If the containment issue is repairable - say by directly proving that the realized posterior draw has low expected Bellman error via a different lemma - the paper would be a solid contribution. As it stands, the main theorem is not established. I'd still send it to a serious referee, because the question matters and the gap looks repairable rather than a dead end.","headline":"The core theorem is unsupported because the posterior draw is never shown to lie in the confidence set used by the Bellman-error concentration, but the new combination is worth a serious referee's time.","tokens_in":772,"tokens_out":895,"would_cite":false,"duration_ms":47779,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"Model-free Thompson sampling for online RLHF is claimed to achieve O(sqrt(T)) regret when the completed value-function class has low Bellman eluder dimension, with the proof resting on a new MLE-based squared Bellman error concentration…","keywords":["online RLHF","Thompson sampling","Bellman eluder dimension","general function approximation","posterior sampling","regret bound","preference-based reinforcement learning","maximum likelihood estimator"],"falsifier":"Take a finite function class F whose completion G_F has log-covering number growing like T log 2, as the paper notes for finite classes, and run Algorithm 1; if the cumulative squared Bellman error of the posterior draws exceeds the claimed O(beta_F) bound on a positive fraction of runs, the concentration step in the proof fails. More directly, inspect the posterior draws f^t: any round t where f^t falls outside the set V_1^F defined in Eq. (4) with non-negligible probability refutes the assertion that greedy selection plays the role of the MLE maximizer.","tokens_in":20884,"feed_emoji":"🤖","tokens_out":4350,"duration_ms":39630,"temperature":0.7,"pith_summary":"The paper proposes a model-free Thompson sampling algorithm for online reinforcement learning from human feedback (RLHF) with general function approximation, and it claims an O(sqrt(T)) regret bound. This matters because most theoretical RLHF algorithms rely on confidence-set or model-based methods, while posterior sampling is more computationally tractable in practice. The paper's key move is to derive a concentration inequality for squared Bellman error from a maximum likelihood estimator generalization bound, then feed that inequality into a Bellman eluder dimension argument. If correct, the result shows that posterior sampling can match the statistical efficiency of confidence-set methods in preference-based RL.","feed_headline":"Model-free Thompson sampling gets O(sqrt(T)) regret in online RLHF","feed_subtitle":"Posterior sampling matches confidence-set bounds when the Bellman eluder dimension of the completed class stays small.","key_machinery":"The load-bearing objects are the completed function class G_F (the closure of F under all possible posterior distributions, introduced so that realizability and completeness hold under posterior sampling), the Bellman eluder dimension of the residual class F_h - T_h F_{h+1}, and the confidence set V_1^F built from the MLE generalization bound. The MLE generalization bound converts preference log-likelihood into a bound on the squared distance between posterior draws and the MLE; applied to Bellman residuals, it yields the concentration inequality that makes the eluder dimension argument go through. The algorithm itself draws f^t from the posterior in each round, plays the greedy policy of f^t against the greedy policy of the previous round, and updates the dataset with the resulting trajectory comparison.","core_discovery":"On the paper's own terms, the central discovery is that model-free posterior sampling can achieve the same eluder-type regret guarantee as confidence-set RLHF. With probability at least 1-delta, Algorithm 1 satisfies Regret(t) <= O(H $\\sqrt$(d t beta_G)) for all t, where d is the Bellman eluder dimension of the completed function class G_F and beta_G is a log-bracketing complexity term. The proof works in three steps: it simplifies the Bayesian regret using the fact that the posterior draw f^t and the true model f* are identically distributed given history, it bounds the regret by cumulative Bellman error through a standard policy loss decomposition, and it controls that error using a new squared-Bellman-error concentration inequality obtained from the MLE generalization bound. The paper presents this as the first eluder-type regret bound for Thompson sampling in online RLHF.","pith_inferences":["If the gap between posterior sampling and the confidence set is repaired, the same MLE-based concentration argument would likely transfer to Thompson sampling for standard RL, as the paper itself hints.","The paper's own finite-class calculation suggests a stress test: for a finite function class, completion can inflate the log-covering number to order T log 2, so the sqrt(T) bound may degrade; checking whether natural parameterized classes such as linear or low-rank classes preserve low Bellman eluder dimension under completion would determine the practical scope of the result.","A testable extension is to replace the sigmoid link with other monotone link functions in the preference model and see whether the regret bound's dependence on kappa tracks the inverse derivative lower bound as the paper predicts."],"forward_implications":["Posterior sampling with a planning oracle can match the statistical efficiency of confidence-set methods in online RLHF, achieving O(sqrt(T)) regret when the Bellman eluder dimension and log-bracketing constants are fixed.","The comparator policy can simply be the previous round's greedy policy, so no separate exploration policy or reward-model training loop is required by the algorithm.","The squared Bellman error concentration inequality holds uniformly for every function in the confidence set, not only for the function executed in a given round, which strengthens the standard eluder argument.","An epsilon-optimal policy with O(H^2 d beta_G / epsilon^2)-style sample complexity follows directly from the regret bound."],"supporting_citations":[{"why":"Supplies the Bellman eluder dimension definition and the eluder-type regret machinery that the paper adapts to posterior sampling.","marker":"[21]"},{"why":"Provides the MLE generalization bound used to construct the confidence set and is the model-based Thompson sampling predecessor that the paper contrasts with its model-free method.","marker":"[48]"},{"why":"Supplies the preference model definition and the MLE-based confidence-set result that the paper relies on in Lemma B.5.","marker":"[57]"},{"why":"Establishes the first confidence-set based algorithm for online RLHF with general function approximation, serving as the statistical baseline the paper matches.","marker":"[7]"}],"fun_headline_variants":["Thompson sampling proves O(sqrt(T)) regret in online RLHF","Posterior sampling matches confidence-set regret in RLHF","First eluder-type regret bound for RLHF Thompson sampling","Model-free RLHF: Thompson sampling achieves O(sqrt(T)) regret","O(sqrt(T)) regret: Thompson sampling for online RLHF"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The posterior sample f^t in round t lies in the MLE-based confidence set V_1^F, so the squared Bellman error bound applies to the functions actually played; the paper supports this only by asserting that greedy selection plays the role of the MLE maximizer, which is not proven.","fun_headline_variants_meta":{"raw":{"variants":["Thompson sampling proves O(sqrt(T)) regret in online RLHF","Posterior sampling matches confidence-set regret in RLHF","First eluder-type regret bound for RLHF Thompson sampling","Model-free RLHF: Thompson sampling achieves O(sqrt(T)) regret","O(sqrt(T)) regret: Thompson sampling for online RLHF"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001016,"raw_usage":{"total_tokens":4270,"prompt_tokens":904,"completion_tokens":3366,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":520,"completion_tokens_details":{"reasoning_tokens":3279}},"tokens_in":520,"tokens_out":3366,"duration_ms":25125,"temperature":1.0,"reasoning_tokens":3279,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T12:38:50.134203+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a finite function class F whose completion G_F has log-covering number growing like T log 2, as the paper notes for finite classes, and run Algorithm 1; if the cumulative squared Bellman error of the posterior draws exceeds the claimed O(beta_F) bound on a positive fraction of runs, the concentration step in the proof fails. More directly, inspect the posterior draws f^t: any round t where f^t falls outside the set V_1^F defined in Eq. (4) with non-negligible probability refutes the assertion that greedy selection plays the role of the MLE maximizer.","supporting_citations":[{"cited_title":"Bellman eluder dimension: new rich classes of rl problems, and sample-efficient algorithms","cited_arxiv_id":null,"evidence_quote":"Supplies the Bellman eluder dimension definition and the eluder-type regret machinery that the paper adapts to posterior sampling."},{"cited_title":"Lee, and Wen Sun","cited_arxiv_id":null,"evidence_quote":"Supplies the preference model definition and the MLE-based confidence-set result that the paper relies on in Lemma B.5."}],"review_version":1}