Pith. sign in

REVIEW 3 major objections 4 minor 4 cited by

This paper proves that the dual gap of a greedy Nash policy is bounded by the square of the parameter-estimation error, giving polylogarithmic regularized regret under any strongly convex regularizer and a sqrt(η r T) rate for explore-then-

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

T0 review · deepseek-v4-flash

2026-08-02 20:28 UTC pith:HM2I5O7C

load-bearing objection Theorem 3.1 is a real contribution; the fast-rate theorems don't follow from Assumption 1 as stated—the coverage lemma is applied to same-context pairs that need a joint/conditional diversity condition. the 3 major comments →

arxiv 2602.23116 v3 pith:HM2I5O7C submitted 2026-02-26 cs.LG cs.GTstat.ML

Provably Efficient Regularized Online RLHF with Generalized Bilinear Preferences

Junghyun Lee , Minju Hong , Kwang-Sung Jun , Chulhee Yun , Se-Young Yun This is my paper
classification cs.LG cs.GTstat.ML MSC 68Q3291A05
keywords generalized bilinear preference modelregularized RLHFNash equilibriumdual gapgreedy samplingexplore-then-commitstrong convexityskew-symmetric matrix
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper studies online RLHF with potentially intransitive preferences, modeled by the Generalized Bilinear Preference Model (GBPM): the probability that action a1 beats a2 in context x is μ(φ1ᵀΘ⋆φ2), where Θ⋆ is a low-rank skew-symmetric matrix and μ is a symmetric link. Its goal is to show that fast (polylogarithmic) regret guarantees, previously proven only for reverse-KL regularization, are generic. It proves that the dual gap of any greedy Nash policy is bounded by the square of the estimation error, using only strong convexity of the regularizer and skew-symmetry of the preference matrix. From that quadratic bound, Greedy Sampling achieves Õ(η d⁴ C_min⁻¹ (log T)²) regularized regret, and Explore-Then-Commit achieves Õ(√(η r T)) regret free of polynomial dimension factors. If correct, these results show strong convexity, not KL-specific geometry, is the mechanism behind fast rates.

Core claim

The central claim is Theorem 3.1: for any estimator bΘ and any β⁻¹-strongly convex regularizer, the dual gap of the policy that plays the Nash equilibrium of the estimated game is bounded by both (L_μ²ηβ+L_μ)E[||(Θ⋆−bΘ)φ||²] and (L_μ/2)E[||Eφ||+||Eφ||²]. The proof expands the regularized objective, uses the integral-probability-metric representation of ℓ1-distance and the fact that the expectation of ˙μ(φᵀΘφ')φᵀEφ' vanishes when both actions are drawn from the same policy, then applies strong convexity to control the ℓ1 distance by the square root of the dual gap, producing a self-bounding quadratic inequality. The paper then feeds this inequality into two algorithms: Greedy Sampling with a

What carries the argument

The Generalized Bilinear Preference Model (GBPM) — P*(a1≻a2|x)=μ(φ1ᵀΘ⋆φ2) with Θ⋆ low-rank, skew-symmetric — is the setting. The load-bearing proof device is the self-bounding quadratic inequality (Eq. 9): X ≤ √(L_μ²ηβ/2) E[||Eφ||]√X + (L_μ/2)E[||Eφ||²], obtained from Theorem 3.1; solving it makes regret proportional to squared estimation error rather than its first power. Two supporting mechanisms are the Coverage Lemma (B.2), which converts sums over basis vectors into expected elliptical potentials under the feature-diversity assumption, and a Freedman-type concentration argument that turns expected elliptical potentials into a linear self-bounding inequality for the Greedy Sampling analy

Load-bearing premise

The load-bearing premise is that the exploration policy's feature covariance covers the greedy policy's features at the same context; the paper's Assumption 1 only guarantees this coverage after averaging over contexts, and the proof's 'Applying the above lemma' step in Section B.1 uses the paired/conditional version without proving it.

What would settle it

Take d=2, contexts x1,x2 with d0 uniform, exploration policy ρ returning e1 at x1 and e2 at x2 (so E[φφᵀ]=0.5 I, satisfying Assumption 1). Let the greedy policy at x2 produce feature e1, and set M=(e1⊗e1)(e1⊗e1)ᵀ. Then the Coverage Lemma's left side equals 1, while E_{a'∼ρ(·|x2)}[(e1⊗φ(x2,a'))ᵀM(e1⊗φ(x2,a'))]=0 because exploration at x2 only produces e2. The claimed inequality 1 ≤ C_min⁻¹·0 fails for the paired context used in Section B.1, so the polylogarithmic regret bound does not follow from Assumption 1 alone.

Watch this falsifier — get emailed when new claim-graph text bears on it.

If this is right

  • Any β⁻¹-strongly convex regularizer — KL, chi-squared, Tsallis entropy, f-divergences — yields the same polylogarithmic regret mechanism; KL-specific bounds are not necessary.
  • Greedy Sampling's regularized regret is Õ(η d⁴ C_min⁻¹ (log T)²), removing exponential dependence on η that earlier analyses suffered.
  • In the high-dimensional regime, Explore-Then-Commit attains Õ(√(η r T)) and Õ(r^{1/3}T^{2/3}) with no explicit poly(d) factor, the first such guarantee for online RLHF under GBPM.
  • For KL, chi-squared, and mixed chi-squared regularizers, the feature-diversity assumption can be bypassed at the cost of an η-dependent factor (eη, η, or 1+η respectively).
  • An online-to-batch conversion turns these regret bounds into sample-complexity guarantees for finding an approximate Nash equilibrium.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Because Theorem 3.1 is stated for any estimator and any strongly convex regularizer, the same quadratic dual-gap argument should transfer to other symmetric zero-sum games with skew-symmetric bilinear payoff, e.g., dueling bandits or matrix games, where short exploration phases could then enjoy √T-type rates.
  • The conditional-coverage gap identified in the proof suggests a concrete fix: modify the exploration policy to guarantee coverage conditional on the context that the greedy policy actually faces; if that can be done, C_min⁻¹ dependence would disappear.
  • The trade-off between GS's d⁴ (log T)² and ETC's √(η r T) means the right algorithm depends on dimension, rank, and horizon — a practical rule-of-thumb: use ETC when d is large and r ≪ d, and GS when η is small and C_min ≈ 1.
  • The authors' h(η) analysis for KL/chi-squared hints that other f-divergences with invertible f' might also bypass feature diversity; deriving coverage ratios for general f is a natural extension.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

3 major / 4 minor

Summary. The paper studies regularized online RLHF under the Generalized Bilinear Preference Model (GBPM), where the preference probability is mu(phi_1^T Theta_* phi_2) with skew-symmetric low-rank Theta_*. Its central theoretical contribution is Theorem 3.1, a bound on the dual gap of a greedy Nash policy by the square of the current estimation error, derived from strong convexity of the regularizer and skew-symmetry of Theta_*. Under a feature-diversity assumption (Assumption 1), the paper claims Greedy Sampling attains O~(eta d^4 C_min^{-1} log^2 T) and O~(d^2 sqrt T) regret, and Explore-Then-Commit attains poly(d)-free O~(sqrt(eta r T)) and O~(T^{2/3}) regret. The paper also discusses relations to KL-specific analyses, eluder dimension, and extensions in appendices.

Significance. The central self-bounding dual-gap inequality is elegant and, if correct, is a genuine step toward showing that fast regularized RLHF rates are not specific to reverse KL regularization but follow from strong convexity. The paper is clearly written and the proofs are detailed, with a useful comparison to prior work. The main caveat is that both algorithmic results rely on coverage arguments that currently require a stronger per-context or joint coverage condition than what Assumption 1 states. The conceptual contribution of Theorem 3.1 appears sound, but the regret guarantees of Theorems 4.2 and 5.2 are not established by the proofs as written. No code or machine-checked proofs are provided, but the mathematical exposition is generally self-contained.

major comments (3)
  1. [Section B.1, Eq. (18); Lemma B.2] The transition from the sum of expected potentials E_{phi_t~hat_pi_t} ||phi_t tensor e_j||^2 to C_min^{-1} E_{phi_t~hat_pi_t, tilde_phi_t~rho}[vec(phi_t tilde_phi_t^top)^T ...] does not follow from Assumption 1. Lemma B.2 is valid pointwise for a fixed phi using the marginal law of tilde_phi~rho, but in Algorithm 1 the two features are drawn from the same revealed context x_t. The proof needs a conditional or joint coverage condition such as E_{a~rho(·|x)}[phi(x,a)phi(x,a)^top] >= C_min I for d0-a.e. x. Assumption 1 only gives E_x E_{a~rho(·|x)}[phi phi^T] >= C_min I. A concrete failure: X={x1,x2}, d0 uniform, phi(x1,a)=e1, phi(x2,a)=e2, and M=(e1 tensor e2)(e1 tensor e2)^T. Assumption 1 holds with C_min=1/2, but at x1 the conditional covariance is e1e1^T and the claimed inequality fails. Both bounds of Theorem 4.2 pass through this step.
  2. [Section C.2, Lemma C.4] The proof of restricted strong convexity claims lambda_min(E_x[A_x tensor A_x]) = lambda_min(E_x A_x)^2 >= C_min^2. This identity is false for random PSD matrices: with A_x equal to e1e1^T or e2e2^T with probability 1/2, E_x A_x = (1/2)I but E_x[A_x tensor A_x] has a zero eigenvalue. The required lower bound in Lemma C.4 is not implied by Assumption 1, and the same same-context coupling issue appears because the two exploration features are drawn from rho at the same x_t. This undermines Lemma C.4 and therefore both ETC regret bounds in Theorem 5.2.
  3. [Section B.1, Part II; Theorem 4.2] The proof of the O~(d^2 sqrt T) regret bound ends with an additive term kappa^{-1} C_min^{-1} d^4 log^2(T/d) in addition to the sqrt T term. The statement of Theorem 4.2 drops this additive term, but it is not dominated by the sqrt T term under the stated assumptions. For example, with kappa=C_min=1 and T around d^4, the two terms are comparable. The theorem should either keep the additive term or explicitly impose a lower bound on T under which it is negligible. This is not merely a presentation issue, because the claimed 'simultaneous' second bound is the min of the two rates only when that term is absorbed.
minor comments (4)
  1. [Eq. (17)] The Hessian definition sums over s but uses v_t inside the sum; it should be v_s.
  2. [Algorithm 1] The pseudocode initializes hat_pi_1 to rho, so the t=1 max-player regret is not covered by Theorem 3.1, which requires a greedy policy w.r.t. the current estimate. Either start the regret sum at t=2 (cost at most 1) or define Theta_0 before the first round.
  3. [Section C.1] The sentence 'which we can assume to hold without loss of any generality' after the condition T >= ... is not WLOG; this condition should be stated as an assumption in Theorem 5.2.
  4. [Throughout] Table 1 and the surrounding text refer to 'Theorem 2.2' when the intended object is Definition 2.2; the numbering should be unified.

Circularity Check

0 steps flagged

No circularity: the central dual-gap bound is a genuine reduction from skew-symmetry and strong convexity; cited prior results are independent external theorems, and the only flagged gap is a correctness/assumption issue, not a circular definition.

full rationale

The paper's central claim — Theorem 3.1 — is derived rather than assumed: the dual gap is expressed in terms of the estimation error E_t = Θ* - Θ̂_t, using Taylor expansion, the IPM representation of ℓ_1 distance, and strong convexity. No quantity is defined as the thing it later 'predicts.' The GS and ETC analyses reduce regret to sums of expected elliptical potentials and estimator error bounds, which is a standard statistical reduction, not a renaming of an input. The reliance on Lee et al. (2024a, Theorem 3.2) for the confidence sequence and Lee et al. (2025, Lemma C.3) for the nuclear-norm MLE is legitimate use of prior, independently published theorems with stated assumptions; these are not self-citations invoked as unverifiable uniqueness results or ansätze. The manuscript itself flags the restrictiveness of Assumption 1 in Section H. The reader's noted concern about the Coverage Lemma (Lemma B.2) being applied in Eq. (18) to features coupled through the same context while Assumption 1 gives only marginal covariance is a real proof/assumption gap and a correctness risk, but it is not circular: the inequality does not hold by construction of the regret definition, and no fitted parameter is renamed as a prediction. Therefore no circular step is identified and the circularity score is 0.

Axiom & Free-Parameter Ledger

0 free parameters · 7 axioms · 0 invented entities

The paper introduces no new model entities beyond the existing GBPM. All constants are assumptions or inherited problem parameters; no free parameter is fitted to data. The main unstated extra burden is the per-context coverage needed by the Coverage Lemma.

axioms (7)
  • domain assumption GBPM: P*(a1≻a2|x)=μ(φ(x,a1)^T Θ* φ(x,a2)) with Θ*∈Skew(d;2r,S), known r and S.
    The entire analysis is for this preference model; if human preferences are not representable in this low-rank skew form, the bounds do not apply.
  • domain assumption Link μ is twice differentiable, monotone, symmetric, and satisfies κ≤μdot≤Lμ, |μddot|≤Lμ on the relevant domain.
    Used for Taylor expansion, Lipschitz control, and confidence sequences; logistic and linear links are the motivating examples.
  • domain assumption The regularizer ψ is β^{-1}-strongly convex with respect to the ℓ1 norm and η∈(0,∞].
    Strong convexity is the engine of the self-bounding quadratic inequality; the claim is explicitly about any such regularizer.
  • domain assumption Feature diversity: λ_min(E_{x~d0,a~ρ(·|x)}[φ(x,a)φ(x,a)^T]) ≥ C_min.
    Used in the Coverage Lemma; as written it is an average condition and may need to be strengthened to per-context coverage for the proof to go through.
  • domain assumption Exact population Nash-equilibrium oracle (Oracle 3).
    The guarantees are statistical, not computational; exact NE computation is assumed available.
  • standard math Standard concentration tools: elliptical potential lemma, Freedman's inequality, RSC-based nuclear-norm M-estimator bounds.
    These are external results invoked for confidence sets and estimation error control.
  • standard math Integral probability metric representation of ℓ1 distance.
    Used inside Lemma 3.2 to convert the linear error term into a product of ℓ1 distance and feature error.

pith-pipeline@v1.3.0-alltime-deepseek · 47160 in / 22215 out tokens · 211630 ms · 2026-08-02T20:28:00.578753+00:00 · methodology

0 comments
read the original abstract

We consider the problem of regularized best-response max-regret minimization in online RLHF under general preferences and bandit feedback. While various regularizers are utilized to robustify alignment, known polylogarithmic regret guarantees remain heavily specific to KL. To investigate whether such fast rates extend beyond KL, we adopt the Generalized Bilinear Preference Model (GBPM) -- capturing intransitive preferences over $d$-dimensional item-wise features via a rank-$2r$ skew-symmetric matrix -- to isolate the impact of generic regularization. Crucially, under GBPM, we prove that the dual gap of any greedy policy is bounded by the squared estimation error, derived using \emph{only} strong convexity and skew-symmetry. Under a feature coverage assumption, we establish a \emph{generic} polylogarithmic regret of $\tilde{\mathcal{O}}(\eta d^4 C_{\min}^{-1} (\log T)^2 \wedge d^2 C_{\min}^{-1/2} \sqrt{T})$ with Greedy Sampling, and a dimension-wise improved regret (for well-conditioned arm-sets) of $\tilde{\mathcal{O}}(C_{\min}^{-2} \sqrt{\eta r T} \wedge r^{1/3} C_{\min}^{-4/3} T^{2/3})$ with Explore-Then-Commit, where $\eta^{-1}$ is the regularization coefficient, $T$ is the time horizon, and $C_{\min}$ is an arm-set dependent quantity. This demonstrates that ``fast'' regrets are not KL-specific, but rather a fundamental consequence of generic strongly convex geometry.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Forward citations

Cited by 4 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. Online KL-Regularized Reinforcement Learning with Function Approximation under Misspecification

    cs.LG 2026-06 unverdicted novelty 7.0

    Introduces KL misspecification for bandits and RL under function approximation and proves explicit KL-regret bounds for regression-based Gibbs algorithms that recover the realizable case.

  2. Efficient Exploration for Iterative Nash Preference Optimization

    cs.LG 2026-05 unverdicted novelty 7.0

    An explicitly exploratory iterative NLHF method achieves O(sqrt(T)) regret for Nash equilibria under general preference models, removing the exponential KL dependence that plagues standard iterative approaches.

  3. Fast Rates for Offline Contextual Bandits with Forward-KL Regularization under Single-Policy Concentrability

    cs.LG 2026-05 unverdicted novelty 7.0

    The paper establishes the first tilde O(epsilon^{-1}) upper bounds and matching lower bounds for forward-KL-regularized offline contextual bandits under single-policy concentrability in both tabular and general functi...

  4. Online KL-Regularized Reinforcement Learning with Function Approximation under Misspecification

    cs.LG 2026-06 conditional novelty 5.5

    Optimistic regression algorithms with Gibbs updates achieve high-probability KL-regret that degrades gracefully under pointwise KL misspecification for bandits and stagewise KL Bellman misspecification for episodic RL.

Reference graph

Works this paper leans on

43 extracted references · 1 canonical work pages · cited by 3 Pith papers

  1. [1]

    Asµ(z) = (1 +e −z)−1 for our proof, this implies thatR s = 1andL µ = 1 4

    From Regret to Sum of Squared Errors.Recall that with vt := vec(ϕ2 t (ϕ1 t )⊤)∈R d2 , our MLE is defined as follows: bΘt ←mat( ˆθt), ˆθt ←arg min θ∈KS Lt(θ),L t(θ) := t−1X s=1 {m(⟨θ,v t⟩)−r t⟨θ,v t⟩},(16) where KS := n θ∈R d2 :∥θ∥ 2 ≤Sandmat(θ) ⊤ =−mat(θ) o . Asµ(z) = (1 +e −z)−1 for our proof, this implies thatR s = 1andL µ = 1 4. Let us denote the regul...

    2020

  2. [2]

    We now present our key technical lemma: Lemma B.2(Coverage Lemma).Let ˜ϕ∼ρ be such that E ˜ϕ∼ρ h ˜ϕ ˜ϕ⊤ i ⪰C minId

    Towards Expected Elliptical Potentials. We now present our key technical lemma: Lemma B.2(Coverage Lemma).Let ˜ϕ∼ρ be such that E ˜ϕ∼ρ h ˜ϕ ˜ϕ⊤ i ⪰C minId. Then, for any positive semi-definite M∈R d2×d2 and any vectorϕ∈R d, the following holds: dX j=1 (ϕ⊗e j)⊤M(ϕ⊗e j)≤C −1 minE ˜ϕ∼ρ h vec(ϕ ˜ϕ⊤)⊤Mvec(ϕ ˜ϕ⊤) i . From hereon, we denote Et−1[·]≜E ϕt∼ˆπt, ˜ϕt...

  3. [3]

    master theorem

    Martingale Concentration for Realized Variance. We now consider the elliptical-type quantity: TX t=1 Et−1 v⊤ t V −1 t vt | {z } ≜ST = TX t=1 v⊤ t V −1 t vt + TX t=1 Et−1 v⊤ t V −1 t vt −v ⊤ t V −1 t vt | {z } ≜Mt = TX t=1 v⊤ t V −1 t vt | {z } (a) + TX t=1 Mt | {z } (b) .(19) We bound(a)via the usual elliptical potential lemma (Theorem G.3): TX t=1 v⊤ t V...

    1975

  4. [6]

    URL https://proceedings.mlr.press/ v130/bogunovic21a.html. Boyd, S. and Vandenberghe, L.Convex Opti- mization. Cambridge University Press, 2004. doi:10.1017/CBO9780511804441. Bradley, R. A. and Terry, M. E. Rank Analysis of Incomplete Block Designs: The Method of Paired Comparisons.Biometrika, 39(3-4):324–345, 1952. doi:10.1093/biomet/39.3-4.324. Cand`es,...

    arXiv 2004

  5. [7]

    Filippi, S., Cappe, O., Garivier, A., and Szepesv ´ari, C

    URL https://proceedings.mlr.press/ v119/faury20a.html. Filippi, S., Cappe, O., Garivier, A., and Szepesv ´ari, C. Parametric Bandits: The Generalized Linear Case. In Advances in Neural Information Processing Systems, vol- ume 23, pp. 586–594. Curran Associates, Inc., 2010. URL https://sites.ualberta.ca/˜szepesva/ papers/GenLinBandits-NeurIPS2010.pdf. Fost...

    2010

  6. [8]

    Foster, D., Rakhlin, A., Simchi-Levi, D., and Xu, Y

    URL https://proceedings.mlr.press/ v119/foster20a.html. Foster, D., Rakhlin, A., Simchi-Levi, D., and Xu, Y . Instance-Dependent Complexity of Contextual Bandits and Reinforcement Learning: A Disagreement-Based Perspective. InProceedings of Thirty Fourth Conference on Learning Theory, volume 134 ofProceedings of Ma- chine Learning Research, pp. 2059–2059....

    arXiv 2059

  7. [11]

    Jang, K., Zhang, C., and Jun, K.-S

    URL https://proceedings.mlr.press/ v291/ito25a.html. Jang, K., Zhang, C., and Jun, K.-S. PopArt: Efficient Sparse Regression and Experimental Design for Opti- mal Sparse Linear Bandits. InAdvances in Neural In- formation Processing Systems, volume 35, pp. 2102–

  8. [13]

    Ji, K., He, J., and Gu, Q

    URL https://proceedings.mlr.press/ v235/jang24e.html. Ji, K., He, J., and Gu, Q. Reinforcement Learning from Human Feedback with Active Queries.Transactions on Machine Learning Research, 2025. ISSN 2835-

    2025

  9. [15]

    Jin, C., Liu, Q., and Yu, T

    URL https://proceedings.mlr.press/ v125/jin20a.html. Jin, C., Liu, Q., and Yu, T. The Power of Exploiter: Prov- able Multi-Agent RL in Large State Spaces. InPro- ceedings of the 39th International Conference on Ma- chine Learning, volume 162 ofProceedings of Machine Learning Research, pp. 10251–10279. PMLR, 17–23 Jul

  10. [17]

    URL https:// openreview.net/forum?id=rblaF2euXQ

    doi:10.52202/079017-2465. URL https:// openreview.net/forum?id=rblaF2euXQ. Kuroki, Y ., Rumi, A., Tsuchiya, T., Vitale, F., and Cesa-Bianchi, N. Best-of-Both-Worlds Algorithms for Linear Contextual Bandits. InProceedings of The 27th International Conference on Artificial Intelligence and Statistics, volume 238 ofProceedings of Machine Learning Research, p...

    work page doi:10.52202/079017-2465

  11. [18]

    Lattimore, T

    URL https://proceedings.mlr.press/ v238/kuroki24a.html. Lattimore, T. and Szepesv´ari, C.Bandit Algorithms. Cam- bridge University Press, 2020. 13 Regularized Online RLHF with Generalized Bilinear Preferences Lee, J., Yun, S.-Y ., and Jun, K.-S. A Unified Confidence Sequence for Generalized Linear Models, with Appli- cations to Bandits. InAdvances in Neur...

    Pith/arXiv arXiv 2020

  12. [19]

    Liese, F

    URL https://proceedings.mlr.press/ v238/li24l.html. Liese, F. and Vajda, I. On Divergences and Informations in Statistics and Information Theory.IEEE Transac- tions on Information Theory, 52(10):4394–4412, 2006. doi:10.1109/TIT.2006.881731. Liu, Q., Yu, T., Bai, Y ., and Jin, C. A Sharp Analysis of Model-based Reinforcement Learning with Self-Play. In Pro...

    arXiv 2006

  13. [20]

    Llama Team

    URL https://proceedings.mlr.press/ v139/liu21z.html. Llama Team. The Llama 3 Herd of Models.arXiv preprint arXiv:2407.21783, 2024. URL https:// arxiv.org/abs/2407.21783. Lu, Y ., Meisami, A., and Tewari, A. Low-Rank Gener- alized Linear Bandit Problems. InProceedings of The 24th International Conference on Artificial Intelligence and Statistics, volume 13...

    Pith/arXiv arXiv 2024

  14. [21]

    URL https://proceedings.mlr.press/ v130/lu21a.html. May, K. O. Intransitivity, Utility, and the Aggregation of Preference Patterns.Econometrica, 22(1):1–13, 1954. doi:https://doi.org/10.2307/1909827. McKelvey, R. D. and Palfrey, T. R. Quantal Response Equilibria for Normal Form Games.Games and Eco- nomic Behavior, 10(1):6–38, 1995. ISSN 0899-8256. doi:htt...

    arXiv 1954

  15. [22]

    M¨uller, A

    URL https://proceedings.mlr.press/ v235/munos24a.html. M¨uller, A. Integral Probability Metrics and Their Generating Classes of Functions.Advances in Applied Probability, 29(2):429–443, 1997. doi:10.2307/1428011. Nash, J. Non-Cooperative Games.Annals of Mathemat- ics, 54(2):286–295, 1951. ISSN 0003486X, 19398980. doi:10.2307/1969529. Nayak, A., Yang, T., ...

    arXiv 1997

  16. [23]

    URL https://arxiv.org/abs/2510. 13060. Nisan, N., Roughgarden, T., Tardos, ´E., and Vazirani, V . V . (eds.).Algorithmic Game Theory. Cambridge University Press, Cambridge, 2007. ISBN 978-0-521-87282-9. Novoseller, E., Wei, Y ., Sui, Y ., Yue, Y ., and Bur- dick, J. Dueling Posterior Sampling for Preference- Based Reinforcement Learning. InProceedings of ...

    2007

  17. [24]

    O’Donoghue, B., Lattimore, T., and Osband, I

    URL https://proceedings.mlr.press/ v124/novoseller20a.html. O’Donoghue, B., Lattimore, T., and Osband, I. Matrix Games with Bandit Feedback. InProceedings of the Thirty-Seventh Conference on Uncertainty in Artificial Intelligence, volume 161 ofProceedings of Machine Learning Research, pp. 279–289. PMLR, 27–30 Jul

  18. [25]

    Oh, M.-h., Iyengar, G., and Zeevi, A

    URL https://proceedings.mlr.press/ v161/o-donoghue21a.html. Oh, M.-h., Iyengar, G., and Zeevi, A. Sparsity-Agnostic Lasso Bandit. InProceedings of the 38th Interna- tional Conference on Machine Learning, volume 139 ofProceedings of Machine Learning Research, pp. 8271–8280. PMLR, 18–24 Jul 2021. URL https:// proceedings.mlr.press/v139/oh21a.html. OpenAI. G...

    Pith/arXiv arXiv 2021

  19. [26]

    Russo, D

    URL https://proceedings.mlr.press/ v130/russac21a.html. Russo, D. and Van Roy, B. Eluder Dimension and the Sample Complexity of Optimistic Exploration. In Advances in Neural Information Processing Systems, 15 Regularized Online RLHF with Generalized Bilinear Preferences volume 26, pp. 2256–2264. Curran Associates, Inc.,

  20. [28]

    Syrgkanis, V ., Agarwal, A., Luo, H., and Schapire, R

    URL https://proceedings.mlr.press/ v235/swamy24a.html. Syrgkanis, V ., Agarwal, A., Luo, H., and Schapire, R. E. Fast Convergence of Regularized Learning in Games. InAdvances in Neural Information Processing Systems, volume 28, pp. 2989–2997. Curran Associates, Inc., 2015. URLhttps://arxiv.org/abs/1507.00407. Tang, X., Yoon, S., Son, S., Yuan, H., Gu, Q.,...

    Pith/arXiv arXiv 2015

  21. [32]

    Wang, M., Ma, C., Chen, Q., Meng, L., Han, Y ., Xiao, J., Zhang, Z., Huo, J., Su, W

    URL https://openreview.net/forum? id=2cRzmWXK9N. Wang, M., Ma, C., Chen, Q., Meng, L., Han, Y ., Xiao, J., Zhang, Z., Huo, J., Su, W. J., and Yang, Y . Magnetic Preference Optimization: Achieving Last-iterate Conver- gence for Language Model Alignment. InThe Thirteenth International Conference on Learning Representations,

  22. [33]

    Wang, Y ., Liu, Q., and Jin, C

    URL https://openreview.net/forum? id=PDnEDS244P. Wang, Y ., Liu, Q., and Jin, C. Is RLHF More Diffi- cult than Standard RL? A Theoretical Perspective. In Advances in Neural Information Processing Systems, volume 36, pp. 76006–76032. Curran Associates, Inc.,

  23. [34]

    Wirth, C., Akrour, R., Neumann, G., and F ¨urnkranz, J

    URL https://openreview.net/forum? id=sxZLrBqg50. Wirth, C., Akrour, R., Neumann, G., and F ¨urnkranz, J. A Survey of Preference-Based Reinforcement Learn- ing Methods.Journal of Machine Learning Research, 18(136):1–46, 2017. URL http://jmlr.org/ papers/v18/16-634.html. Wu, D., Shi, C., Yang, J., and Shen, C. Greedy Sam- pling Is Provably Efficient For RLH...

    2017

  24. [35]

    Wu, W., Yang, J., and Shen, C

    URL https://openreview.net/forum? id=Pe2lo3QOvo. Wu, W., Yang, J., and Shen, C. Stochastic Linear Contex- tual Bandits with Diverse Contexts. InProceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, volume 108 ofProceedings of Machine Learning Research, pp. 2392–2401. PMLR, 26– 28 Aug 2020. URL https://proceedi...

    2020

  25. [36]

    Xiong, W., Dong, H., Ye, C., Wang, Z., Zhong, H., Ji, H., Jiang, N., and Zhang, T

    URL https://proceedings.mlr.press/ v162/xiong22b.html. Xiong, W., Dong, H., Ye, C., Wang, Z., Zhong, H., Ji, H., Jiang, N., and Zhang, T. Iterative Preference Learn- ing from Human Feedback: Bridging Theory and Prac- tice for RLHF under KL-constraint. InProceedings of the 41st International Conference on Machine Learn- ing, volume 235 ofProceedings of Mac...

  26. [37]

    Yang, T., Dai, B., Xiao, L., and Chi, Y

    URL https://proceedings.mlr.press/ v235/xiong24a.html. Yang, T., Dai, B., Xiao, L., and Chi, Y . Incentivize without Bonus: Provably Efficient Model-based On- line Multi-agent RL for Markov Games. InForty- second International Conference on Machine Learning,

  27. [38]

    17 Regularized Online RLHF with Generalized Bilinear Preferences Yang, W., Li, X., and Zhang, Z

    URL https://openreview.net/forum? id=ciUHD7jcT9. 17 Regularized Online RLHF with Generalized Bilinear Preferences Yang, W., Li, X., and Zhang, Z. A Regularized Approach to Sparse Optimal Policy in Reinforcement Learning. In Advances in Neural Information Processing Systems, vol- ume 32, pp. 5940–5950. Curran Associates, Inc., 2019. URLhttps://arxiv.org/ab...

    Pith/arXiv arXiv 2019

  28. [39]

    URL https://openreview.net/forum? id=TwdX1W3M6S. Zeng, G. and Honorio, J. A Novel General Framework for Sharp Lower Bounds in Succinct Stochastic Ban- dits. InThe Thirty-ninth Annual Conference on Neural Information Processing Systems, 2025. URL https: //openreview.net/forum?id=xvsPQuUHef. Zhan, W., Uehara, M., Kallus, N., Lee, J. D., and Sun, W. Provable...

    arXiv 2025

  29. [40]

    Zimmert, J

    URL https://proceedings.mlr.press/ v202/zhu23f.html. Zimmert, J. and Seldin, Y . Tsallis-INF: An Optimal Al- gorithm for Stochastic and Adversarial Bandits.Jour- nal of Machine Learning Research, 22(28):1–49, 2021. URL http://jmlr.org/papers/v22/19-753. html. 18 Regularized Online RLHF with Generalized Bilinear Preferences Contents 1 Introduction 1 2 Prob...

    2021

  30. [1988]

    Tucker, M., Cheng, M., Novoseller, E., Cheng, R., Yue, Y ., Burdick, J

    doi:10.1007/BF01016429. Tucker, M., Cheng, M., Novoseller, E., Cheng, R., Yue, Y ., Burdick, J. W., and Ames, A. D. Hu- man Preference-Based Learning for High-dimensional Optimization of Exoskeleton Walking Gaits. In 2020 IEEE/RSJ International Conference on Intelli- gent Robots and Systems (IROS), pp. 3423–3430, 2020. doi:10.1109/IROS45743.2020.9341416. ...

    arXiv 2020

  31. [2008]

    doi:10.1561/2200000001

    ISSN 1935-8237. doi:10.1561/2200000001. Wang, C., Jiang, Y ., Yang, C., Liu, H., and Chen, Y . Beyond Reverse KL: Generalizing Direct Preference Optimiza- tion with Diverse Divergence Constraints. InThe Twelfth International Conference on Learning Representations,

    doi:10.1561/2200000001 1935

  32. [2013]

    URL https://web.stanford.edu/˜bvr/ pubs/Eluder.pdf. Saha, A. Optimal Algorithms for Stochastic Contextual Pref- erence Bandits. InAdvances in Neural Information Pro- cessing Systems, volume 34, pp. 30050–30062. Curran Associates, Inc., 2021. URL https://openreview. net/forum?id=1lCZrXJBpM. Saha, A. and Krishnamurthy, A. Efficient and Optimal Algo- rithms ...

    2021

  33. [2020]

    Bai, Y ., Jin, C., and Yu, T

    URL https://proceedings.mlr.press/ v119/bai20a.html. Bai, Y ., Jin, C., and Yu, T. Near-Optimal Reinforcement Learning with Self-Play. InAdvances in Neural In- formation Processing Systems, volume 33, pp. 2159–

  34. [2021]

    Abernethy, J

    URL https://proceedings.mlr.press/ v130/abeille21a.html. Abernethy, J. D., Lee, C., and Tewari, A. Fighting Bandits with a New Kind of Smoothness. InAdvances in Neural Information Processing Systems, volume 28, pp. 2197–

  35. [2022]

    Jun, K.-S., Willett, R., Wright, S., and Nowak, R

    URL https://proceedings.mlr.press/ v162/jin22c.html. Jun, K.-S., Willett, R., Wright, S., and Nowak, R. Bi- linear Bandits with Low-rank Structure. InProceed- ings of the 36th International Conference on Machine Learning, volume 97 ofProceedings of Machine Learn- ing Research, pp. 3163–3172. PMLR, 09–15 Jun 2019. URL https://proceedings.mlr.press/v97/ jun...

    Pith/arXiv arXiv 2019

  36. [2023]

    Goldenshluger, A

    URL https://proceedings.mlr.press/ v202/go23a.html. Goldenshluger, A. and Zeevi, A. A linear response ban- dit problem.Stochastic Systems, 3(1):230 – 261, 2013. doi:10.1214/11-SSY032. Han, J., Jiang, M., Song, Y ., Ermon, S., and Xu, M. f-PO: Generalizing Preference Optimization with f- divergence Minimization. InProceedings of The 28th International Conf...

    doi:10.1214/11-ssy032 2013

  37. [2024]

    URL https://proceedings.mlr.press/ v238/gheshlaghi-azar24a.html. Bai, Y . and Jin, C. Provable Self-Play Algorithms for Competitive Reinforcement Learning. InPro- ceedings of the 37th International Conference on Ma- chine Learning, volume 119 ofProceedings of Machine Learning Research, pp. 551–560. PMLR, 13–18 Jul

  38. [2025]

    Hao, B., Lattimore, T., and Wang, M

    URL https://proceedings.mlr.press/ v258/han25a.html. Hao, B., Lattimore, T., and Wang, M. High-Dimensional Sparse Linear Bandits. InAdvances in Neural Informa- tion Processing Systems, volume 33, pp. 10753–10763. Curran Associates, Inc., 2020. URL https://arxiv. org/abs/2011.04020. Heliou, A., Cohen, J., and Mertikopoulos, P. Learn- ing with Bandit Feedba...

    Pith/arXiv arXiv 2020

  39. [2026]

    Tversky, A

    URL https://openreview.net/forum? id=S4PCF1YxoR. Tversky, A. Intransitivity of preferences.Psychological Review, 76(1):31–48, 1969. doi:10.1037/h0026750. von Neumann, J. Zur Theorie der Gesellschaftsspiele.Math- ematische Annalen, 100(1):295–320, Dec 1928. ISSN 1432-1807. doi:10.1007/BF01448847. Wainwright, M. J.High-Dimensional Statistics: A Non- Asympto...

    doi:10.1037/h0026750 1969

  40. [2114]

    URL https: //openreview.net/forum?id=GWcdXz0M6a

    Curran Associates, Inc., 2022. URL https: //openreview.net/forum?id=GWcdXz0M6a. Jang, K., Zhang, C., and Jun, K.-S. Efficient Low- Rank Matrix Estimation, Experimental Design, and Arm- Set-Dependent Low-Rank Bandits. InProceedings of the 41st International Conference on Machine Learn- ing, volume 235 ofProceedings of Machine Learn- ing Research, pp. 21329...

    2022

  41. [2170]

    URL https: //arxiv.org/abs/2006.12007

    Curran Associates, Inc., 2020. URL https: //arxiv.org/abs/2006.12007. Balduzzi, D., Garnelo, M., Bachrach, Y ., Czarnecki, W., Perolat, J., Jaderberg, M., and Graepel, T. Open-ended learning in symmetric zero-sum games. InProceed- ings of the 36th International Conference on Machine Learning, volume 97 ofProceedings of Machine Learn- ing Research, pp. 434...

    Pith/arXiv arXiv 2020

  42. [2205]

    URL https:// arxiv.org/abs/1512.04152

    Curran Associates, Inc., 2015. URL https:// arxiv.org/abs/1512.04152. 9 Regularized Online RLHF with Generalized Bilinear Preferences Ali, S. M. and Silvey, S. D. A General Class of Coeffi- cients of Divergence of One Distribution from Another. Journal of the Royal Statistical Society: Series B (Method- ological), 28(1):131–142, 1966. doi:10.1111/j.2517- ...

    Pith/arXiv arXiv 2015

  43. [8856]

    Featured Certification

    URL https://openreview.net/forum? id=EScatQaRxz. Featured Certification. Jiang, D., Ren, X., and Lin, B. Y . LLM-Blender: Ensem- bling Large Language Models with Pairwise Ranking and Generative Fusion. InProceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pp. 14165–14178, Toronto, Canada, July 2...

    doi:10.18653/v1/2023.acl-long.792 2023