{"id":"bd005147-8b6f-4986-9ca5-64318aee5a76","arxiv_id":"2412.10616","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"A hybrid online-plus-offline preference optimization algorithm, HPO, provably needs fewer samples than pure online or offline RLHF in linear MDP settings.","lead":"This paper proposes combining offline preference data with online exploration to align language models more sample-efficiently. It gives theoretical guarantees showing that starting from an offline dataset can reduce the number of online human preference queries needed, compared to purely online or offline methods.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lower-bound reduction in Appendix B is asserted, not constructed; without explicit hard MDP instances for beta>0, the 'beats lower bounds' claim is unsupported.","rationale":"The reader's weakest assumption correctly identifies the missing lower-bound reduction as the load-bearing point for the central claim. My independent reading confirms that Appendix B contains a reduction from linear bandits to linear dueling bandits, but not an embedding of the RLHF problem into the dueling-bandit model for the regularized objective J_beta. Without explicit hard instances and feature maps, Theorems 2 and 3 do not lower-bound the RLHF problems that HPO is claimed to beat. The main upper-bound proof in Appendix A is a plausible extension of XPO, and I found no fatal internal contradiction there, so I do not recommend rejection. However, the advertised 'provably optimal' and 'beats lower bounds' statements are conditional on a rigorous reduction that is not present. I also note that the definition of d_hyb in Theorem 4 is not coherent as written, which is an additional reason to keep the verdict conditional; fixing that definition and re-deriving the SEC bound would be part of the required revision. Overall, the reader's CONDITIONAL verdict remains appropriate.","tokens_in":18458,"tokens_out":14003,"duration_ms":134639,"concrete_test":"Construct an explicit token-level DCMDP family and policy class Pi satisfying Assumptions 1 and 2 such that, for a specified beta>0, the preference oracle induced by the Bradley-Terry model is exactly a linear dueling bandit on a d-dimensional action set matching the hard instances of Li et al. (2022) and Wagenmaker et al. (2022). Then verify the claimed minimax lower bounds for J_beta. If no such construction exists, or if the KL penalty changes the comparison probabilities so that the cited lower bounds do not transfer, the 'beats lower bounds' conclusion is invalid.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The advertised improvement over pure offline/online methods rests on Theorems 2 and 3, whose proofs (Appendix B) reduce RLHF to a linear dueling bandit with score s(a)= and then cite existing linear-bandit lower bounds. This reduction is not actually carried out: no MDP, transition law, trajectory feature map, policy class, or BTL hard instance is constructed, and no argument shows that an RLHF learner's query set (policies/trajectories in a token-level MDP) can realize the unrestricted action sets used in the cited linB lower bounds. Moreover, the proof explicitly sets beta=0 ('s(.) essentially corresponds to J(.) of eq. (2) for beta=0'), whereas Theorems 2 and 3 are stated for the KL-regularized objective J_beta with a 'choice of beta'. A hard instance for beta=0 does not lower-bound J_beta suboptimality for beta>0, because the KL penalty changes the objective and can make the J_beta gap smaller than the unregularized reward gap. Thus even if Theorem 1 is correct, the paper has not shown that pure offline/online algorithms are subject to the lower bounds that HPO is compared with.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes Hybrid Preference Optimization (HPO), an RLHF algorithm that trains a DPO-style policy on the union of an online preference buffer and minibatches drawn from a static offline preference dataset, together with an optimism regularizer. The main theoretical result is Theorem 1, which bounds the KL-regularized suboptimality gap in terms of a newly defined hybrid sequential extrapolation coefficient SEC_Hyb. Theorem 4 specializes this to linear MDPs as O~(Rmax e^{2Rmax} sqrt(d d_hyb / T)), and Theorems 2 and 3 claim lower bounds for pure offline and pure online RLHF. The paper concludes that HPO is provably more sample-efficient than either pure regime. Section 6 reports experiments on a linear contextual bandit comparing HPO with online and offline baselines.","tokens_in":18751,"tokens_out":12419,"duration_ms":109212,"significance":"If the main results were correct, this would be a notable advance: it would give the first analysis showing that hybrid preference data can strictly reduce the sample complexity of online RLHF without concentrability assumptions, and it would identify a linear-MDP regime in which the hybrid rate is better than the pure offline and pure online minimax rates. The paper does contain genuine technical pieces: the concentration argument is patterned on Xie et al. (2024), and the determinant calculation in the proof of Theorem 4 is a meaningful step. However, the advertised conclusions are not supported as written. The definition of SEC_Hyb in Section 4.3 does not match the quantity used in the regret decomposition in Appendix A.2, so the key inequality in the proof of Theorem 1 has the wrong direction under the stated definitions. The quantity d_hyb in Section 5.2 is not defined as a count, although the proof of Theorem 4 treats it as one. Finally, the lower-bound reduction in Appendix B is asserted rather than constructed and is explicitly carried out for beta=0, while Theorems 2 and 3 are stated for the KL-regularized objective J_beta.","major_comments":[{"comment":"The inequality sum_t I(t) <= SEC_Hyb used in the proof of Theorem 1 has the wrong direction under the definitions as written. In Definition 4.2 the t-th denominator is Vmax^2 ∨ ((t-1) E_{mu(t)}[(eg_off)^2]) = Vmax^2 ∨ (Σ_{i1, each SEC term is no larger than the corresponding I(t), so the claimed bound Σ_t I(t) ≤ SEC_Hyb does not follow; if anything the reverse inequality holds. Because this step converts the concentration inequality into the SEC-dependent rate, Theorem 1 is not established as written.","section":"Section 4.3 / Appendix A.2"},{"comment":"The definition of d_hyb is malformed and the proof uses a different object. The displayed definition d_hyb = max_i { ||tilde_Lambda_off^{-1/2} v_i||^2 ≲ Ω(1/√T) } is a maximum over boolean conditions, not a count; it can only take values 0 or 1, and the predicate mixes asymptotic notation in a non-well-formed way. In the proof of Theorem 4, d_hyb is instead described as 'the number of indices in [d] such that λ_off^{(i)} ≤ Ω(1/T)'. The correct definition should be d_hyb = |{ i : λ_off^{(i)} ≤ C/T }| for an explicit constant C, or an equivalent sum of indicators. Since the claimed rate O~(sqrt(d d_hyb / T)) and the subsequent comparison with the pure offline and online lower bounds depend on d_hyb scaling as the number of poorly covered directions, this must be fixed.","section":"Section 5.2"},{"comment":"The reduction from RLHF to linear dueling bandits is asserted, not constructed. Appendix B states that 'the reward/score function s(·) essentially corresponds to the J(·) function of eq. (2) (for beta=0)' and then cites existing linear-bandit lower bounds, but it never constructs the MDP instances, transition laws, trajectory feature maps, policy classes, or hard BTL preference distributions needed to instantiate the cited lower bounds in the RLHF setting. The proof explicitly works with beta=0, whereas Theorems 2 and 3 are stated for the KL-regularized objective J_beta; a hard instance for the unregularized reward does not imply a lower bound on J_beta suboptimality because the KL penalty changes the objective and can shrink the gap. Moreover, the cited lower bounds concern decision sets in R^d, and no argument shows that the trajectories or policies queried by an RLHF learner can realize those action sets. Without this construction, the claim in Section 5.2 that HPO beats the pure offline and pure online lower bounds is unsupported.","section":"Appendix B / Theorems 2 and 3"},{"comment":"The abstract and contribution list claim 'matching lower bounds' and a 'provably optimal theoretical bound' for hybrid RLHF. Theorems 2 and 3, however, are lower bounds for pure offline and pure online RLHF, not for the hybrid problem; no hybrid lower bound is provided. Even if Theorems 2 and 3 were correct, they would show that HPO improves over the pure regimes, not that its rate is optimal among hybrid algorithms. The wording should be adjusted to state precisely what is and is not proved.","section":"Abstract / Section 1.1"}],"minor_comments":[{"comment":"Assumption 2 uses Vmax before Vmax is defined; the definition of Vmax should appear before the assumption and be restated with its units.","section":"Section 4.2"},{"comment":"The statement says 'for any beta > 0 and T ∈ [N]' without defining N earlier in the paper; clarify whether N denotes the offline dataset size or some other budget.","section":"Theorem 1"},{"comment":"The expression '≲ Ω(1/√T)' is not a well-formed threshold predicate. Replace it with an explicit eigen-threshold condition of the form λ_off^{(i)} ≤ C/T with an absolute constant C.","section":"Section 5.2"},{"comment":"The remark that SEC_Hyb < SEC_RLHF is immediate from C_off ≥ 0 and is therefore definitional. The substantive claim is that the concentration argument in Lemma 1 actually pays for the extra offline denominator term; the paper should say so explicitly to avoid giving the impression that the improvement is only a definitional artifact.","section":"Definition 4.2, Remark"},{"comment":"The text says 'whereas the hybrid algorithm has seen Noff offline samples and T - Noff offline samples'; the second occurrence should presumably read 'online samples'. Also, 'VPO' is never defined, and no error bars or number of seeds are reported for the experimental curves.","section":"Section 6"}],"recommendation":"major_revision","confidential_remarks":"The upper-bound framework is plausibly salvageable: the SEC mismatch can likely be repaired by redefining SEC_Hyb to match the actual regret-decomposition denominator, and the d_hyb definition is a fixable formal error. The lower-bound part is a larger gap: establishing Theorems 2 and 3 for the KL-regularized RLHF objective requires an explicit construction of hard MDP instances, not just a citation of dueling-bandit lower bounds. Given that the paper's headline claim is that HPO provably beats both pure offline and pure online lower bounds, I would ask the authors to supply that construction or remove the 'beats lower bounds' claim. I do not see the current issues as irreparable, but they are load-bearing and require a substantive revision."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Here's the short version: the upper-bound half of this paper is a solid, incremental extension of XPO to hybrid offline+online RLHF, and the concentration argument appears to hold up. The advertised 'beats both lower bounds' conclusion, however, rests on a lower-bound reduction that is sketched, not carried out, and on a malformed definition of d_hyb. I'd send it to review with the expectation of major revision on Section 5 and Appendix B.\n\nWhat's actually new: Theorem 1 gives a sample complexity bound for HPO (XPO plus gamma offline minibatches per round) with SEC_HybRLHF. The concentration lemma in Appendix A is a genuine derivation; the linear-MDP determinant bound in Theorem 4 is also new and plausible. The SEC definition does make the hybrid coefficient no larger than the online SEC because of the nonnegative C_off term, so part of the improvement is definitional—but the proof of the bound given that definition is real work. The paper is honest about building on Xie et al. 2024, and the citation pattern is appropriate.\n\nWhere it goes soft. First, Section 5.2's d_hyb is defined as a maximum over vectors and then used as a count of eigenvalues. That's a clear typo-level error, but it sits at the base of Theorem 4 and needs fixing. Second, and more serious, the lower bounds in Theorems 2 and 3 are not actually proven for the RLHF problem. Appendix B reduces RLHF to a linear dueling bandit with score s(a)=, cites Saha 2021 Lemma 8 and Wagenmaker/Li lower bounds, and explicitly says s(.) corresponds to J(.) 'for beta=0.' No MDP, transition law, trajectory feature map, or BTL hard instance is constructed, and the beta>0 case is never addressed. The KL penalty changes the objective, so a hard instance for beta=0 does not imply a lower bound on the J_beta gap for beta>0. That means the claim that HPO beats pure offline and online minimax lower bounds is unsupported, even if Theorem 1 is correct.\n\nThe experiment is a single linear contextual bandit with no error bars or code, which is acceptable for a theory paper but shouldn't be used as strong evidence.\n\nBottom line: the upper-bound contribution is worth refereeing, and the authors are clearly capable. Send it out, but ask for a rigorous lower-bound reduction or a softened claim, and a clean definition of d_hyb. I wouldn't cite it in its current form.","headline":"Solid upper-bound extension of XPO to hybrid RLHF, but the lower-bound reduction is sketched rather than proven, so the headline 'beats both lower bounds' claim is currently unsupported.","tokens_in":19251,"tokens_out":3062,"would_cite":false,"duration_ms":24853,"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":"Mixing a fixed offline preference dataset with online exploration makes RLHF provably more sample-efficient than either pure offline or pure online training.","keywords":["hybrid preference optimization","RLHF","online exploration","offline preference data","sample complexity","linear MDP","sequential extrapolation coefficient","direct preference optimization"],"falsifier":"Run HPO on a linear MDP with known $d_{\\mathrm{hyb}}$ and record the gap; if it decays more slowly than $\\sqrt{d\\,d_{\\mathrm{hyb}}/T}$ up to log factors, Theorem 4 is false. Separately, for a two-step token-level MDP with $\\beta>0$, compute the log preference odds between two trajectories under the Bradley-Terry model: if it is not an affine function of a fixed trajectory feature, the lower-bound reduction in Appendix B does not hold and the claimed separation from pure methods collapses.","tokens_in":18275,"feed_emoji":"🎯","tokens_out":11158,"duration_ms":98114,"temperature":0.7,"pith_summary":"This paper tries to establish that the most sample-efficient way to align a policy from human preferences is to use both kinds of data: keep the cheap offline preference pairs and add a small number of freshly queried online comparisons. It introduces HPO, a DPO-style algorithm that, at each of $T$ online rounds, mixes $\\gamma$ labeled pairs drawn uniformly from the offline dataset into the online preference buffer and then solves an optimistic version of the DPO objective. The paper proves that the suboptimality gap of the returned policy is controlled by a hybrid exploration coefficient that only counts what the offline data has not already covered. In linear MDPs this gives a gap of $\\widetilde{O}(R_{\\max} e^{2 R_{\\max}} \\sqrt{d\\, d_{\\mathrm{hyb}}/T})$, which recovers the pure online rate when the offline data covers nothing and is strictly better whenever it covers any feature direction. The stated lower bounds for pure offline and pure online RLHF are what make the improvement a provable separation rather than an empirical observation.","feed_headline":"Hybrid RLHF provably beats pure offline and online alignment","feed_subtitle":"Offline preference data shrinks the search space; HPO's sample complexity scales with only the directions still unexplored.","key_machinery":"The central object is the hybrid sequential extrapolation coefficient $\\operatorname{SEC}_{\\mathrm{HybRLHF}}$ (Definition 4.2), a preference-feedback analogue of the sequential extrapolation coefficient. It measures, over $T$ rounds, how far the current policy's implicit preference signal $g^{(\\pi)}(\\tau, \\tilde\\tau)$ can depart from the KL-regularized objective relative to a variance term built from the online sampling distribution and the offline dataset's empirical coverage $C^{(\\pi)}_{\\mathrm{off}}$. The second mechanism is the parameter $\\gamma$: at each step HPO draws $\\gamma$ labeled pairs uniformly from $D_{\\mathrm{off}}$ into the hybrid set, and the proof uses $\\gamma$ to convert the offline data into extra denominator mass in the concentration bound, equivalently a larger effective sample size $t-1+\\gamma$ at round $t$. In linear MDPs, applying the elliptical potential lemma to the covariance $\\Lambda_{\\mathrm{off}} + (V_{\\max}^2/\\gamma)I$ turns $\\operatorname{SEC}_{\\mathrm{HybRLHF}}$ into $O(d_{\\mathrm{hyb}} \\log(1 + 4T/V_{\\max}^2))$, where $d_{\\mathrm{hyb}}$ counts the feature directions not yet covered by the offline data. This is what carries the claim that hybrid training only needs to explore the residual feature directions.","core_discovery":"On its own terms, the central discovery is that the difficulty of preference-based alignment is set not by the whole policy class but by the part of the policy class not already covered by the offline dataset. HPO makes this concrete: at each online round it adds $\\gamma$ labeled pairs drawn uniformly from the offline set into the online buffer, then minimizes the optimistic DPO objective of equation (5). The proof shows that the suboptimality gap of the returned policy satisfies\n$$J_\\$\\beta$(\\pi^*_\\$\\beta$)-J_\\$\\beta$(\\hat\\pi) \\lesssim (V_{\\max}+R_{\\max})$e^{{2R_{\\max}}$}\\sqrt{\\frac{(1+\\gamma/T)\\operatorname{SEC}_{\\mathrm{HybRLHF}}\\log(|\\Pi|T/\\delta)\\log T}{T}},$$\nwith $\\operatorname{SEC}_{\\mathrm{HybRLHF}}$ the hybrid sequential extrapolation coefficient of Definition 4.2. Because the offline term $\\gamma\\, C^{(\\pi)}_{\\mathrm{off}}$ appears inside the variance term of the coefficient, $\\operatorname{SEC}_{\\mathrm{HybRLHF}} < \\operatorname{SEC}_{\\mathrm{RLHF}}$ for any nonempty offline dataset, and in linear MDPs the coefficient reduces to $\\widetilde{O}(d_{\\mathrm{hyb}})$, the number of feature directions whose offline empirical covariance is below $O(1/T)$. The resulting rate $\\widetilde{O}(R_{\\max} e^{2R_{\\max}}\\sqrt{d\\,d_{\\mathrm{hyb}}/T})$ is claimed to beat the pure offline lower bound $\\Omega(\\sqrt{d^2/N_{\\mathrm{off}}})$ and the pure online lower bound $\\Omega(\\sqrt{d^2/T})$ whenever $d_{\\mathrm{hyb}}