Provably Efficient Regularized Online RLHF with Generalized Bilinear Preferences

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 *only* strong convexity and skew-symmetry. Under a feature coverage assumption, we establish polylogarithmic $\tilde{\mathcal{O}}(\eta d^4(\log T{)}^2\wedge d^2\sqrt{T})$ regret with Greedy Sampling and $\mathrm{poly}(d)$-free $\tilde{\mathcal{O}}(\sqrt{\eta rT}\wedge r^{1/3}{T}^{2/3})$ regret with Explore-Then-Commit, where ${\eta }^{-1}$ is the regularization coefficient and $T$ is the time horizon. This demonstrates that “fast” regrets are *not* KL-specific, but rather a fundamental consequence of generic strongly convex geometry.