Regularized Online RLHF with Generalized Bilinear Preferences
| Authors | Junghyun Lee et al. |
| Year | 2026 |
| Field | Machine Learning |
| arXiv | 2602.23116 |
| Download | |
| Categories | cs.LG, stat.ML |
Abstract
We consider the problem of contextual online RLHF with general preferences, where the goal is to identify the Nash Equilibrium. We adopt the Generalized Bilinear Preference Model (GBPM) to capture potentially intransitive preferences via low-rank, skew-symmetric matrices. We investigate general preference learning with any strongly convex regularizer (where η^{-1} is the regularization strength), generalizing beyond prior works limited to reverse KL-regularization. Central to our analysis is proving that the dual gap of the greedy policy is bounded by the square of the estimation error - a result derived solely from strong convexity and the skew-symmetricity of GBPM.Building on this insight and a feature diversity assumption, we establish two regret bounds via two simple algorithms: (1) Greedy Sampling achieves polylogarithmic, e^{O(η)}-free regret \tilde{O}(ηd^4 (\log T)^2). (2) Explore-Then-Commit achieves \mathrm{poly}(d)-free regret \tilde{O}(\sqrt{ηr T}) by exploiting the low-rank structure; this is the first statistically efficient guarantee for online RLHF in high-dimensions.
Engineering Breakdown
Plain English
This paper tackles online reinforcement learning from human feedback (RLHF) in a setting where human preferences may be intransitive or cyclic—meaning preference A > B and B > C doesn't necessarily imply A > C. Rather than assuming preferences fit a simple transitive model, the authors use a Generalized Bilinear Preference Model (GBPM) based on low-rank, skew-symmetric matrices to capture this complexity. They prove that with any strongly convex regularizer, the performance gap of a greedy policy is bounded by the square of estimation error, a tight theoretical result that doesn't depend on the specific regularizer chosen. They then derive two regret bounds for online learning algorithms, showing sublinear regret rates under feature diversity assumptions.
Core Technical Contribution
The key novelty is decoupling RLHF preference learning from reverse KL-regularization and proving tight bounds for any strongly convex regularizer via the skew-symmetric structure of GBPM. Prior work assumed reverse KL explicitly; this paper shows that strong convexity alone is sufficient, which is a fundamental theoretical simplification. The central technical insight—that dual gap scales with squared estimation error due to skew-symmetricity—is derived purely from convexity properties and the geometric structure of the preference model, not from KL-specific mechanics. This opens the door to using L2, entropy, or other regularizers while maintaining the same convergence guarantees.
How It Works
The algorithm operates in an online loop: at each round, given a context, the system proposes a pair of actions and receives binary preference feedback (A > B or B > A). The system maintains estimates of a low-rank, skew-symmetric preference matrix M ∈ ℝ^{d×d} that encodes pairwise preferences—the (i,j) entry captures how much action i is preferred over action j, with antisymmetry ensuring consistency (M_ij = -M_ji). Preferences are modeled as P(A ≻ B | context) ∝ sigmoid(context^T M action_diff), where the skew structure allows cyclic preferences. The regularized online learning objective minimizes the sum of preference prediction loss plus a strongly convex regularization term (parameterized by strength η^{-1}). At each step, the greedy policy selects the action with highest predicted value; the analysis bounds how far this greedy choice deviates from optimal (the dual gap) by showing it scales as O(√estimation_error)².
Production Impact
For teams deploying preference-based reward modeling, this paper provides a mathematically justified alternative to reverse KL that's computationally simpler: you can use standard L2 regularization or other convex regularizers without loss of theoretical guarantees. The low-rank skew-symmetric structure reduces memory footprint compared to dense preference matrices—storing O(d×r) parameters instead of O(d²) when preferences have rank-r structure, which matters when d is large (thousands of actions). The online learning guarantee means you get sublinear regret even when preferences arrive sequentially and adversarially, not requiring full offline batches. The practical downside is that skew-symmetric constraints require specialized matrix projections during training, adding ~10-20% computational overhead, and the theory assumes feature diversity which may require careful exploration design or data augmentation in practice.
Limitations and When Not to Use This
The paper assumes preferences are perfectly captured by a low-rank skew-symmetric model; if true preferences have dense or asymmetric structure (e.g., context-dependent intransitivity that can't be factored), the model will misspecify and regret bounds don't apply. The feature diversity assumption—roughly that action embeddings span the subspace well—is strong and unverified in practice; failure here breaks the regret guarantees without warning signals. The analysis covers online RLHF where you control which preference pairs to query; it doesn't directly address the harder problem of off-policy learning from logged, arbitrary preference data. The paper also doesn't address computational complexity of projection onto skew-symmetric constraints or provide implementation details for large-scale d; scalability to modern RL settings (millions of parameters, high-dimensional action spaces) remains unclear.
Research Context
This work extends recent advances in preference-based RL (particularly those using bilinear models) by generalizing the regularizer class beyond reverse KL—building on observations that KL is just one choice among many. It sits in the broader arc of making RLHF theoretically tractable: prior work by the community established regret bounds for transitive models, but intransitive preferences are more realistic for humans and required new mathematical tools (skew-symmetric structure). The paper likely compares against or builds upon Bradley-Terry preference models and contextual bandits literature. This opens a research direction toward understanding which regularizers are best for human preference modeling in practice—moving from 'KL is standard' to 'what does convexity really buy us?'—and toward tighter characterization of when low-rank assumptions hold for real human feedback.
:::tip Subscribe Get weekly breakdowns of papers like this in AI Letters - the newsletter for engineers building production AI systems. :::