Research map / Bandits and online learning / Online convex optimization and games

Provably Efficient Regularized Online RLHF with Generalized Bilinear Preferences

NeurIPS 2026 · Bandits and online learning › Online convex optimization and games · approach: Online learning with feedback graphs · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Shows that regularized max-regret in online RLHF under the Generalized Bilinear Preference Model admits fast (polylog or sqrt(r T)) rates for any strongly convex regularizer, not just KL, via a quadratic dual-gap bound plus Greedy Sampling and Explore-Then-Commit algorithms.

Problem

Regularized best-response max-regret in online RLHF with general (possibly intransitive) preferences and bandit feedback; prior fast polylogarithmic rates were specific to KL regularization.

Approach

Under GBPM with skew-symmetric low-rank preference matrix, the dual gap of any greedy symmetric NE policy is bounded by the squared estimation error, using only strong convexity of the regularizer and skew-symmetry (plus an IPM representation of the l1 norm), enabling fast regret for any strongly convex regularizer.</ask>

Key results

• Greedy Sampling attains regret of order eta d^4 C_min^{-1} (log T)^2 and d^2 C_min^{-1/2} sqrt(T) under a feature coverage assumption, with no exponential e^{O(eta)} factor.
• Explore-Then-Commit with nuclear-norm regularized MLE attains C_min^{-2} sqrt(eta r T) and r^{1/3} C_min^{-4/3} T^{2/3} regret.
• Dual gap of any greedy NE policy is bounded by the square of the estimation error under any beta^{-1}-strongly convex regularizer.

Surprising findings

• Under GBPM, the quadratic dual-gap bound and fast rates hold for any strongly convex regularizer, not only KL.

Limitations

• Relies on a feature coverage assumption (C_min > 0) for the exploration policy.
• Analysis restricted to the GBPM with logistic link for the GS result; the algorithms assume tractable population NE oracle.
• Preliminary numerical experiments only, and the theoretical results are not tied to practical LLM training.

Experimental setup

Metrics: max-regret (regularized dual gap)

Baselines: KL-regularized greedy sampling (e^{9eta} bound)

Builds on: GBPM KL-regularized Nash learning logistic bandits self-concordance analysis elliptical potential lemma

Closest papers by meaning

• Logarithmic Regret for Online KL-Regularized Reinforcement Learning (ICML 2025 · similarity 0.89)
• From Average Sensitivity to Small-Loss Regret Bounds under Random-Order Model (NeurIPS 2026 · similarity 0.89)
• On the necessity of adaptive regularisation: Optimal anytime online learning on $\boldsymbol{\ell_p}$-balls (NeurIPS 2025 · similarity 0.89)
• Dynamic Regret Reduces to Kernelized Static Regret (NeurIPS 2025 · similarity 0.88)
• A Simple and Adaptive Learning Rate for FTRL in Online Learning with Minimax Regret of $\Theta(T^{2/3})$ and its Application to Best-of-Both-Worlds (NeurIPS 2024 · similarity 0.88)
• Sharp Analysis for KL-Regularized Contextual Bandits and RLHF (NeurIPS 2025 · similarity 0.88)