Provably Efficient Regularized Online RLHF with Generalized Bilinear Preferences
Junghyun Lee ⋅ Minju Hong ⋅ Kwang-Sung Jun ⋅ Chulhee Yun ⋅ Se-Young Yun
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 regularization. We prove that for any preference-model estimator and strongly convex regularizer, the dual gap of its greedy Nash policy is bounded by the *squared* estimation error, using only strong convexity and preference anti-symmetry. We instantiate this general result under the *Generalized Bilinear Preference Model (GBPM)*, capturing intransitive preferences over $d$-dimensional item-wise features via a rank-$2r$ skew-symmetric matrix. Under suitable feature-coverage conditions with shared coverage constant $C_{\min}>0$, *Greedy Sampling* achieves $\widetilde{O}(\eta\beta\kappa^{-1}d^4C_{\min}^{-1} \wedge \kappa^{-1/2}d^2C_{\min}^{-1/2}\sqrt{T})$ regret, while *Explore-Then-Commit* achieves $\widetilde{O}(\kappa^{-1}C_{\min}^{-2}\sqrt{\eta\beta rT} \wedge \kappa^{-2/3}C_{\min}^{-4/3}r^{1/3}T^{2/3})$ in admissible regimes, utilizing low-rank structure. These results demonstrate that "fast" regret rates are *not* KL-specific, but rather a fundamental consequence of the generic strongly convex geometry of the regularizer.
Successful Page Load