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 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 r T} \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.
Junghyun Lee
PhD Student
PhD student at GSAI, KAIST, jointly advised by Profs. Se-Young Yun and Chulhee Yun. Research focuses on interactive machine learning, “theoretical perspectives” of LLMs, optimization theory, and statistical analyses of large networks with an emphasis on community detection. Broadly interested in mathematical and theoretical AI, as well as related problems in mathematics and statistics.