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 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 and regularization strength η − 1 \eta^{-1} , generalizing beyond prior work 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-symmetry 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 𝒪 ⁡ ( η ) e^{{\mathcal{O}}(\eta)} -free regret 𝒪 ~ ​ ( η ​ d 4 ​ ( log ⁡ T ) 2 ) \tilde{{\mathcal{O}}}(\eta d^{4}(\log T)^{2}) . (2) Explore-Then-Commit achieves poly ⁡ ( d ) \mathrm{poly}(d) -free regret 𝒪 ~ ​ ( η ​ r ​ T ) \tilde{{\mathcal{O}}}(\sqrt{\eta rT}) by exploiting the low-rank structure; this is the first statistically efficient guarantee for online RLHF in high-dimensions. Table 1: Comparison of regret bounds for online RLHF under GBPM ; for unregularized regret, take {\color[rgb]{0.75,0,0.25}\eta}=\infty . For simplicity, we set \delta=\frac{1}{T} but note that all guarantees hold with high probability. Also, we consider only \mathrm{poly}(d,C_{\min}^{-1}) -dependencies. Algorithm Regret Bound \mathrm{ABR\text{-}Reg}_{\color[rgb]{0.75,0,0.25}\eta} \mathrm{MBR\text{-}Reg}_{\color[rgb]{0.75,0,0.25}\eta} \mu(\cdot) \psi(\cdot) Greedy Sampling ( 129 , Theorem 1) {\color[rgb]{0.75,0,0.25}\eta^{3}e^{9\eta}}\kappa^{-1}d^{3}r(\log T)^{2} ✗ ✓ Logistic \ddagger D_{\mathrm{KL}}(\cdot,\pi_{ref}) Optimistic Matrix Game * ( 90 , Theorem 2.1) {\color[rgb]{0.75,0,0.25}\eta}d^{4}(\log T)^{2}\wedge d^{2}\sqrt{T}\log T ✓ ✓ Linear D_{\mathrm{KL}}(\cdot,\pi_{ref}) Greedy Sampling (Ours, Theorem 4.2 ) {\color[rgb]{0.75,0,0.25}\eta}\beta\kappa^{-1}C_{\min}^{-1}d^{4}\left(\log T\right)^{2}\wedge\kappa^{-\frac{1}{2}}C_{\min}^{-\frac{1}{2}}d^{2}\sqrt{T}\log T ✗ ✓ Any Any \beta^{-1} -SC Explore-Then-Commit \dagger (Ours, Theorem 5.2 ) \kappa^{-1}C_{\min}^{-1}\sqrt{{\color[rgb]{0.75,0,0.25}\eta}\beta rT\log T}\wedge\sqrt[3]{\kappa^{-2}C_{\min}^{-4}rT^{2}\log T} ✓ ✓ Any Any \beta^{-1} -SC * Discussed only for a non-contextual scenario, {\mathcal{X}}=\{{\bm{x}}\} , but we believe that this is extendable to the contextual scenario as well. Allows for asymmetric KL-regularization: J_{\color[rgb]{0.75,0,0.25}\eta}(\pi^{1},\pi^{2})=J(\pi^{1},\pi^{2})-{\color[rgb]{0.75,0,0.25}\eta^{-1}}D_{\mathrm{KL}}(\pi^{1},\pi_{ref}^{1})+{\color[rgb]{0.75,0,0.25}\eta^{-1}}D_{\mathrm{KL}}(\pi^{2},\pi_{ref}^{2}) . \dagger Each rate is achieved with a different T_{0} ; “Any \mu ” should satisfy the conditions in Definition 2.2 , also self-concordant for Theorem 5.2 . \ddagger “Logistic” can be generalized to any \mu such that the cross-entropy loss is L -Lipschitz in \bm{\Theta} . 1 Introduction RLHF Theory. Aligning large language models (LLMs) with human values has emerged as a central challenge in modern AI, driven by the success of models like Llama, Qwen, and GPT-4 ( 81 ; 99 ; 94 ) , which rely heavily on human preference feedback ( 26 ; 96 ) . This framework, known as Reinforcement Learning from Human Feedback (RLHF) , necessitates a rigorous statistical foundation. The theoretical landscape of RLHF and Preference-based RL (PbRL; 128 ) has advanced rapidly, primarily under the Bradley-Terry-Luce (BTL) model ( 18 ; 98 ) , where each item i possesses a latent reward (utility) r_{i}\in{\mathbb{R}} . A standard approach is to model this reward linearly as r_{i}=\langle\bm{\phi}_{i},\bm{\theta}_{\star}\rangle . Because this formulation naturally mirrors (contextual) linear bandits ( 1 ; 27 ; 75 ) and linear MDPs ( 60 ) , it enables the direct adaptation of powerful tools from the bandit literature to interactive decision-making problems. Consequently, these techniques have been successfully extended to tackle various facets of LLM alignment, including dueling bandits and RL ( 92 ; 153 ; 107 ; 132 ; 142 ; 78 ) , active learning from human feedback ( 30 ; 56 ; 130 ) , and principled exploration strategies ( 40 ; 120 ) . Despite their simplicity, such (generalized) linear model-based frameworks remain crucial for deriving concrete algorithmic intuition and often serve as the starting point for theoretically principled algorithm design. Furthermore, these foundational works have paved the way for more expressive, abstract function-approximation frameworks ( 135 ; 150 ; 149 ; 129 ; 141 ; 52 ) . General Preference Learning. Despite its success, reward-based RLHF is fundamentally limited in modeling complex, cyclic preferences prevalent in human psychology ( 83 ; 121 ) , as well as diverse human preferences ( 7 ; 88 ) . This calls for General Preference Learning (or Nash Learning ), which targets the Nash Equilibrium (NE) directly without assuming an underlying utility ( 89 ; 122 ; 84 ; 88 ) , and has demonstrated empirical promise in LLMs ( 139 ; 5 ; 29 ; 102 ) . Broadly, research in this domain can be divided into two perspectives: optimization and statistical learning. The majority of recent progress has focused on the optimization perspective ( 113 ; 88 ; 117 ; 148 ; 147 ; 126 ; 152 ) : specifically, how to find the NE in a computationally efficient manner given a known game ( 91 ) . However, in contrast to reward-based RLHF, the statistical perspective of general preference learning remains sparse. Here, the game is unknown , requiring the learner to estimate the underlying preference model while simultaneously identifying the NE from limited (e.g., bandit) feedback. The limited literature in this setting primarily relies on general function approximation ( 25 ; 127 ; 139 ; 129 ) or restricts focus to tabular matrix games ( 50 ; 97 ; 53 ) . While recent works by 137 ; 90 have explored linear function approximation, they rely on item pair-wise features and a linear link function. Beyond the restriction to a linear link, the assumption of access to valid item pair-wise features ( 57 ; 35 ) is often impractical, as elaborated in 145 . First, this necessitates \binom{K}{2} features for K items, compared to just K for item-wise features. Second, constructing pairwise features that ensure an inherently antisymmetric preference model is often ad-hoc and nontrivial; for instance, supervised preference models often exhibit positional bias (e.g., preferring the first response) when inputs are concatenated ( 109 ) . Thus, analogous to the linear contextual BTL model, it is highly desirable from both theoretical and empirical perspectives to study general preference learning using item-wise features. Generalized Bilinear Preference Model (GBPM). To bridge this gap, we adopt the Generalized Bilinear Preference Model (GBPM) , introduced by 69 ; 145 : given item-wise features \bm{\phi}^{1},\bm{\phi}^{2}\in{\mathbb{R}}^{d} , the preference probability is modeled as P^{*}(\bm{\phi}^{1}\succ\bm{\phi}^{2}):=\mu\left((\bm{\phi}^{1})^{\top}\bm{\Theta}_{\star}\bm{\phi}^{2}\right), (1) where \mu(\cdot) is a link function satisfying \mu(z)+\mu(-z)=1 , and \bm{\Theta}_{\star}\in{\mathbb{R}}^{d\times d} is a potentially low-rank, skew-symmetric matrix. This extends linear BTL: the bilinear form captures pairwise relationships as in bilinear bandits ( 61 ) , and skew-symmetry ensures that P^{*} is anti-symmetric. Contributions. In this paper, we tackle regularized online RLHF with general preferences under GBPM . We emphasize “ regularized ” to highlight that our contributions extend beyond the standard reverse KL-regularization dominating the prior literature ( 135 ; 150 ; 149 ; 129 ) . Stemming from the mentioned prior literature, we ask the following central question: Under GBPM and generic regularizer, can we obtain “fast” rates (e.g., polylogarithmic or \mathrm{poly}(d) -free regret)? We answer this question largely in the affirmative. Our contributions are as follows: under a feature diversity assumption , • Polylogarithmic Regret via GS: We prove that Greedy Sampling (GS) achieves a regularized regret of \tilde{{\mathcal{O}}}\left({\color[rgb]{0.75,0,0.25}\eta}d^{4}(\log T)^{2}\wedge d^{2}\sqrt{T}\right) . This partially resolves an open problem by 129 regarding the exponential dependency on {\color[rgb]{0.75,0,0.25}\eta} . 1 1 1 We clarify that the feature diversity assumption was not part of their open problem ( 129 , Appendix A.2) and is a condition we newly adopt for our analysis. Specifically, we show that GS achieves polylogarithmic regularized regret that is {\color[rgb]{0.75,0,0.25}e^{{\mathcal{O}}(\eta)}} -free. ( Section 4 ) • \mathrm{poly}(d) -free Regret via ETC: Addressing the high-dimensional regime, we demonstrate that Explore-Then-Commit (ETC) with nuclear-norm regularized MLE achieves regularized regret bounds of \widetilde{{\mathcal{O}}}\left(\sqrt{{\color[rgb]{0.75,0,0.25}\eta}rT}\right) and \tilde{{\mathcal{O}}}(r^{1/3}T^{2/3}) . Notably, these bounds are \mathrm{poly}(d) -free, which is highly desirable in high dimensions where d is large. ( Section 5 ) • Key Technical Novelty: Quadratic Bound on Dual Gap. Central to the analyses of both GS and ETC is a new bound on the dual gap, which may be of independent interest. We show that the dual gap of any greedy NE policy is upper bounded by the square of the estimation error of \bm{\Theta}_{\star} . Our analysis leverages the skew-symmetry and strong convexity of the regularized game objective, and the integral probability metric representation of the \ell_{1} -distance ( 87 ) to derive a self-bounding quadratic inequality . ( Section 3 ) We compare our regret bounds with prior arts under GBPM in Table 1 , where it can be seen that we obtain state-of-the-art for any link function \mu(\cdot) and any (strongly convex) regularizer \psi(\cdot) . Notations. For a set {\mathcal{X}} , \Delta({\mathcal{X}}) is the set of all possible probability distributions over {\mathcal{X}} . A\lesssim B denotes A\leq cB for an absolute constant c>0 . For a,b\in{\mathbb{R}} , we denote a\vee b=\max\{a,b\} and a\wedge b=\min\{a,b\} . 2 Problem Setting 2.1 (Self-Play) Interaction Protocol We consider a game defined by a ground-truth, contextual preference model P^{*}({\bm{a}}^{1}\succ{\bm{a}}^{2}\mid{\bm{x}}) , where {\bm{x}}\in{\mathcal{X}} is a context (question), and {\bm{a}}^{1},{\bm{a}}^{2}\in{\mathcal{A}} are two actions (responses). The notation {\bm{a}}^{1}\succ{\bm{a}}^{2}\mid{\bm{x}} indicates that response {\bm{a}}^{1} is preferred to {\bm{a}}^{2} given {\bm{x}} . Crucially, P^{*} is anti-symmetric: P^{*}({\bm{a}}^{1}\succ{\bm{a}}^{2})+P^{*}({\bm{a}}^{2}\succ{\bm{a}}^{1})=1 . A policy is a mapping \pi:{\mathcal{X}}\rightarrow\Delta({\mathcal{A}}) , where \pi(\cdot|{\bm{x}}) denotes the conditional distribution over actions. We denote the class of all such policies by \Pi , and define the \ell_{1} -distance on \Pi as follows: \left\lVert\pi-\pi^{\prime}\right\rVert_{1}:=\sum_{({\bm{x}},{\bm{a}})\in{\mathcal{X}}\times{\mathcal{A}}}|\pi({\bm{a}}|{\bm{x}})-\pi^{\prime}({\bm{a}}|{\bm{x}})|. (2) We adopt the self-play framework, where the learner controls both players to learn by playing against itself. Since the breakthrough of AlphaGo ( 111 ; 110 ) , self-play has been extensively studied in the RL theory literature ( 9 ; 8 ; 80 ; 59 ; 136 ) , and recently in LLM alignment ( 114 ; 133 ; 147 ) . A key feature of this framework is that the learner can achieve high performance even in the absence of an expert or adversarial opponent. Interaction Protocol. We define the preference between \pi^{1} ( max-player ) and \pi^{2} ( min-player ) given {\bm{x}}\in{\mathcal{X}} as: P^{*}(\pi^{1}\succ\pi^{2}\mid{\bm{x}}):=\mathbb{E}_{\begin{subarray}{c}{\bm{a}}^{1}\sim\pi^{1}(\cdot|{\bm{x}})\\ {\bm{a}}^{2}\sim\pi^{2}(\cdot|{\bm{x}})\end{subarray}}\left[P^{*}({\bm{a}}^{1}\succ{\bm{a}}^{2}\mid{\bm{x}})\right]. Given a fixed context distribution d_{0}\in\Delta({\mathcal{X}}) (unknown to the learner), we denote the population preference as P^{*}(\pi^{1}\succ\pi^{2}):=\mathbb{E}_{{\bm{x}}\sim d_{0}}[P^{*}(\pi^{1}\succ\pi^{2}|{\bm{x}})] . The online contextual RLHF protocol proceeds as follows: At each t=1,\dots,T , a context {\bm{x}}_{t}\sim d_{0} is revealed. The learner chooses policies {\color[rgb]{0,0,1}\hat{\pi}_{t}^{1}(\cdot|{\bm{x}}_{t})} and {\color[rgb]{1,0,0}\hat{\pi}_{t}^{2}(\cdot|{\bm{x}}_{t})} , samples actions {\color[rgb]{0,0,1}{\bm{a}}_{t}^{1}} and {\color[rgb]{1,0,0}{\bm{a}}_{t}^{2}} , and receives a bandit feedback r_{t}\sim\mathrm{Ber}(P^{*}({\color[rgb]{0,0,1}{\bm{a}}_{t}^{1}}\succ{\color[rgb]{1,0,0}{\bm{a}}_{t}^{2}}\mid{\bm{x}}_{t})) . This constitutes a contextual symmetric two-player zero-sum game ( 10 ) with bandit feedback. Feature Diversity. We consider the following assumption, considered in prior literature on contextual bandits (see Theorem 3.1 and Section 6 for more discussions): Assumption 1 (Feature Map and Diversity) . The learner has access to a known feature map \phi:{\mathcal{X}}\times{\mathcal{A}}\rightarrow{\mathcal{B}}^{d}(1) and an exploration policy \rho(\cdot|{\bm{x}}) such that for a C_{\min}>0 : \lambda_{\min}\left(\mathbb{E}_{{\bm{x}}\sim d_{0}}\mathbb{E}_{{\bm{a}}\sim\rho(\cdot|{\bm{x}})}\left[\phi({\bm{x}},{\bm{a}})\phi({\bm{x}},{\bm{a}})^{\top}\right]\right)\geq C_{\min}. (3) Remark 2.1 (Scaling of C_{\min} ) . Well-conditioned sets (e.g., hypercubes) allow C_{\min}\asymp 1 , while for ill-conditioned sets (e.g., standard basis), C_{\min}^{-1}\asymp d^{-1} or worse. In this paper, our regime of interest is when C_{\min}^{-1}\asymp 1 , although for completeness, we keep track of this quantity throughout. 2.2 Generalized Bilinear Preference Model (GBPM) We now introduce the low-rank contextual general preference model that we consider in this work. First, we define \mathrm{Skew}(d;2r,S) as the following: \left\{\bm{\Theta}\in\mathrm{Skew}(d):\mathrm{rank}(\bm{\Theta})\leq 2r,\left\lVert\bm{\Theta}\right\rVert_{\mathrm{nuc}}\leq S\right\}, (4) where \mathrm{Skew}(d):=\left\{\bm{\Theta}\in{\mathbb{R}}^{d\times d}:\bm{\Theta}^{\top}=-\bm{\Theta}\right\}. Now the definition of GBPM ( 145 ; 69 ) : Definition 2.2 ( Generalized Bilinear Preference Model ) . Let rank r\leq\lfloor d/2\rfloor and norm bound S>0 be known. For any {\bm{x}}\in{\mathcal{X}},{\bm{a}}^{1},{\bm{a}}^{2}\in{\mathcal{A}} , the ground-truth preference under GBPM is: P^{*}({\bm{a}}^{1}\succ{\bm{a}}^{2}\mid{\bm{x}}):=\mu\left(\phi({\bm{x}},{\bm{a}}^{1})^{\top}\bm{\Theta}_{\star}\phi({\bm{x}},{\bm{a}}^{2})\right), where \bm{\Theta}_{\star}\in\mathrm{Skew}(d;2r,S) is an unknown skew-symmetric, low-rank matrix, and \mu:\mathbb{R}\rightarrow[0,1] is a known link satisfying: for some \kappa>0 , 1. \mu is twice differentiable, monotone increasing, and symmetric ( \mu(z)+\mu(-z)=1 ). 2. \kappa\leq\dot{\mu}\left(\phi^{\top}\bm{\Theta}\phi^{\prime}\right)\leq L_{\mu},\ \left|\ddot{\mu}\left(\phi^{\top}\bm{\Theta}\phi^{\prime}\right)\right|\leq L_{\mu},\ \ \forall\bm{\phi},\bm{\phi}^{\prime}\in{\mathcal{B}}^{d}(1),\bm{\Theta}\in\mathrm{Skew}(d;2r,S) . 2 2 2 We assume the same constant L_{\mu} for the upper bounds of \dot{\mu} and |\ddot{\mu}| for simplicity of the exposition. The conditions for \mu are standard in logistic and generalized linear (dueling) bandits ( 38 ; 2 ; 71 ; 70 ; 69 ; 132 ; 13 ) . The logistic link \mu(z)=(1+e^{-z})^{-1} satisfies the above with R_{s}=1 and L_{\mu}=\frac{1}{4} . The linear link \mu(z)=\tfrac{1}{2}+z is also covered, in which case R_{s}=0 and L_{\mu}=1 ( 45 ; 132 ) . Throughout, we denote J(\bm{\phi}_{t}^{1},\bm{\phi}_{t}^{2};\bm{\Theta}):=\mu((\bm{\phi}_{t}^{1})^{\top}\bm{\Theta}\bm{\phi}_{t}^{2}) and its expectation w.r.t. {\bm{x}}_{t}\sim d_{0} and \bm{\phi}_{t}^{i}\sim\pi^{i} as J(\pi^{1},\pi^{2};\bm{\Theta}) . We also denote J(\cdot,\cdot):=J(\cdot,\cdot;\bm{\Theta}_{\star}) . 2.3 Regularized NE and Regret Definitions For a {\color[rgb]{0.75,0,0.25}\eta}\in(0,\infty] and a \beta^{-1} -strongly convex regularizer \psi:\Pi\rightarrow{\mathbb{R}}_{\geq 0} w.r.t. \left\lVert\cdot\right\rVert_{1} , we define a symmetric , regularized game objective J_{\color[rgb]{0.75,0,0.25}\eta}:\Pi\times\Pi\rightarrow{\mathbb{R}} as follows: J_{\color[rgb]{0.75,0,0.25}\eta}(\pi,\pi^{\prime};\bm{\Theta}):=J(\pi,\pi^{\prime};\bm{\Theta})-{\color[rgb]{0.75,0,0.25}\eta^{-1}}\psi(\pi)+{\color[rgb]{0.75,0,0.25}\eta^{-1}}\psi(\pi^{\prime}). Standard solution concepts (e.g., Condorcet winners) may not exist in general preference learning ( 36 ; 12 ; 88 ; 114 ) . Thus, as in many recent literature in online RLHF ( 88 ) , we consider (regularized) Nash Equilibrium (NE) ( 89 ; 84 ) : Definition 2.3 (Nash Equilibrium) . A pair (\pi^{1}_{\star},\pi^{2}_{\star})\in\Pi\times\Pi is a Nash equilibrium (NE) if for all \pi^{1},\pi^{2}\in\Pi : J_{\color[rgb]{0.75,0,0.25}\eta}(\pi^{1},\pi^{2}_{\star})\leq J_{\color[rgb]{0.75,0,0.25}\eta}(\pi^{1}_{\star},\pi^{2}_{\star})\leq J_{\color[rgb]{0.75,0,0.25}\eta}(\pi^{1}_{\star},\pi^{2}). If \pi^{1}_{\star}=\pi^{2}_{\star}=:\pi_{\star} , we refer to \pi_{\star} as a symmetric NE (SNE) . By the minimax theorem ( 122 ; 112 ) , any SNE \pi_{\star} is equivalently characterized as follows: \pi^{\star}\in\argmax_{\pi^{1}\in\Pi}\min_{\pi^{2}\in\Pi}J_{\color[rgb]{0.75,0,0.25}\eta}(\pi^{1},\pi^{2}). (5) We also have the following important technical lemma, which will be critically used later: Lemma 2.4 . For any \bm{\Theta}\in\mathrm{Skew}(d) , the value of the game, \max_{\pi^{1}}\min_{\pi^{2}}J_{\color[rgb]{0.75,0,0.25}\eta}(\pi^{1},\pi^{2};\bm{\Theta}) , is always \frac{1}{2} . Proof. For any \bm{\Theta} , there always exists a SNE ( 114 , Lemma 2.1) . As the game value of SNE is \frac{1}{2} , it must be so for any NE ( 122 ; 112 ) . ∎ We define the (symmetric) dual gap of a policy \hat{\pi}\in\Pi as \mathrm{DGap}_{\color[rgb]{0.75,0,0.25}\eta}(\hat{\pi}):=\frac{1}{2}-\min_{\pi^{2}\in\Pi}J_{\color[rgb]{0.75,0,0.25}\eta}(\hat{\pi},\pi^{2}). (6) Intuitively, this quantifies how close \hat{\pi} is to an SNE . We evaluate any resulting policy sequence \{({\color[rgb]{0,0,1}\hat{\pi}_{t}^{1}},{\color[rgb]{1,0,0}\hat{\pi}_{t}^{2}})\}_{t\in[T]} using the following two regrets: Definition 2.5 . For any \{({\color[rgb]{0,0,1}\hat{\pi}_{t}^{1}},{\color[rgb]{1,0,0}\hat{\pi}_{t}^{2}})\}_{t\in[T]} , (a) Average-Best-Response Regret: \mathrm{ABR\text{-}Reg}_{\color[rgb]{0.75,0,0.25}\eta}(T):=\sum_{t=1}^{T}\left\{\mathrm{DGap}_{\color[rgb]{0.75,0,0.25}\eta}({\color[rgb]{0,0,1}\hat{\pi}_{t}^{1}})+\mathrm{DGap}_{\color[rgb]{0.75,0,0.25}\eta}({\color[rgb]{1,0,0}\hat{\pi}_{t}^{2}})\right\}. (b) Max-Best-Response Regret : \mathrm{MBR\text{-}Reg}_{\color[rgb]{0.75,0,0.25}\eta}(T):=\sum_{t=1}^{T}\mathrm{DGap}_{\color[rgb]{0.75,0,0.25}\eta}({\color[rgb]{0,0,1}\hat{\pi}_{t}^{1}}). Remark 2.6 . These regrets are stronger than those considered in the standard adversarial bandit literature. The above regrets can be converted to sample complexities for finding an NE via online-to-batch conversion ( 44 ) ; see Appendix D for detailed discussions. Computation Oracles. We lastly describe the computation model. We assume the learner is tractable (not necessarily efficient), accessing {\mathcal{A}} and \mathrm{Skew}(d) only via: Oracle 1 . Sampling: Given {\bm{x}}\in{\mathcal{X}} and \pi\in\Pi , output a sample {\bm{a}}\sim\pi(\cdot|{\bm{x}}) . Oracle 2 . Evaluation: Given a \bm{\Theta} and \pi,\pi^{\prime}\in\Pi , return J_{\color[rgb]{0.75,0,0.25}\eta}(\pi,\pi^{\prime};\bm{\Theta}) (via Monte Carlo). Oracle 3 . Population NE: Given a \bm{\Theta} , output the population SNE : \argmax_{\pi^{1}}\argmin_{\pi^{2}}J_{\color[rgb]{0.75,0,0.25}\eta}(\pi^{1},\pi^{2};\bm{\Theta}) . The last oracle has been considered in prior online RLHF literature ( 139 ; 129 ) and learning in games under bandit feedback ( 97 ; 137 ; 90 ) . 3 A New Analysis of Regularized Regret We present our main technical contribution: a new bound on the instantaneous dual gap of any greedy NE policy for the max-player. Denoting \bm{\phi}\sim\pi as sampling a \bm{\phi}({\bm{x}},{\bm{a}})\in{\mathcal{B}}^{d}(1) from {\bm{a}}\sim\pi(\cdot|{\bm{x}}) and {\bm{x}}\sim d_{0} , Theorem 3.1 . For any estimator \widehat{\bm{\Theta}}_{t}\in\mathrm{Skew}(d) at time t , define the max-player’s policy as \hat{\pi}_{t}\leftarrow\argmax_{\pi^{1}}\min_{\pi^{2}}J_{\color[rgb]{0.75,0,0.25}\eta}(\pi^{1},\pi^{2};\widehat{\bm{\Theta}}_{t}). (7) Then, the instantaneous dual gap is simultaneously bounded as follows: denoting {\bm{E}}_{t}:=\bm{\Theta}_{\star}-\widehat{\bm{\Theta}}_{t} , \displaystyle\mathrm{DGap}_{\color[rgb]{0.75,0,0.25}\eta}({\color[rgb]{0,0,1}\hat{\pi}_{t}}) \displaystyle\leq(L_{\mu}^{2}{\color[rgb]{0.75,0,0.25}\eta}\beta+L_{\mu})\mathbb{E}_{\bm{\phi}\sim{\color[rgb]{0,0,1}\hat{\pi}_{t}}}\left[\left\lVert{\bm{E}}_{t}\bm{\phi}\right\rVert_{2}^{2}\right], \displaystyle\mathrm{DGap}_{\color[rgb]{0.75,0,0.25}\eta}({\color[rgb]{0,0,1}\hat{\pi}_{t}}) \displaystyle\leq\frac{L_{\mu}}{2}\mathbb{E}_{\bm{\phi}\sim{\color[rgb]{0,0,1}\hat{\pi}_{t}}}\left[\left\lVert{\bm{E}}_{t}\bm{\phi}\right\rVert_{2}+\left\lVert{\bm{E}}_{t}\bm{\phi}\right\rVert_{2}^{2}\right]. We first remark that the feature diversity assumption ( 1 ) is not needed here. One important observation is that this holds for any choice of estimator and any choice of \beta^{-1} -strongly convex regularizer \psi(\cdot) . As long as {\color[rgb]{0.75,0,0.25}\eta}<\infty (e.g., the regularization by \psi exists), the instantaneous dual gap is bounded quadratically with the expected estimation error of \bm{\Theta}_{\star} along the features of {\color[rgb]{0,0,1}\hat{\pi}_{t}} ; in the proof, one can see that without strong convexity, one only gets \mathbb{E}_{\bm{\phi}}[\left\lVert{\bm{E}}_{t}\bm{\phi}\right\rVert] . Proof Sketch of Theorem 3.1 . The proof starts with the first-order Taylor expansion, which gives a linear term and the quadratic term, similar to the self-concordant analysis of logistic and generalized linear bandits ( 2 ; 71 ; 70 ) . We then derive our key technical lemma ( Lemma 3.2 ), which bounds the linear term by the linear error term multiplied by \ell_{1} -distance between \hat{\pi}_{t} and its best response ; this is in turn derived by the unique skew-symmetric nature of GBPM and somewhat surprisingly, the integral probability metric (IPM) representation of \ell_{1} -distance ( 87 ) . The \ell_{1} -distance is in turn bounded by the square root of the instantaneous dual gap, which follows from the strongly convex landscape of J_{\color[rgb]{0.75,0,0.25}\eta} . This results in a self-bounding quadratic inequality , which, when solved, results in the quadratic error term. ∎ 3.1 Proof of Theorem 3.1 Regret Decomposition via Self-Concordance Let us denote \tilde{\pi}=\argmin_{\pi\in\Pi}J_{\color[rgb]{0.75,0,0.25}\eta}(\hat{\pi},\pi) as the min-player’s best response to \hat{\pi} w.r.t. the true objective. We denote the dual gap of \hat{\pi} as {\color[rgb]{0.75,0.5,0.25}X}:=\frac{1}{2}-J_{\color[rgb]{0.75,0,0.25}\eta}(\hat{\pi},\tilde{\pi}) . Then, note that \displaystyle{\color[rgb]{0.75,0.5,0.25}X} \displaystyle=J_{\color[rgb]{0.75,0,0.25}\eta}(\hat{\pi},\tilde{\pi};\widehat{\bm{\Theta}})-J_{\color[rgb]{0.75,0,0.25}\eta}(\hat{\pi},\tilde{\pi})+\frac{1}{2}-J_{\color[rgb]{0.75,0,0.25}\eta}(\hat{\pi},\tilde{\pi};\widehat{\bm{\Theta}}) \displaystyle\leq J_{\color[rgb]{0.75,0,0.25}\eta}(\hat{\pi},\tilde{\pi};\widehat{\bm{\Theta}})-J_{\color[rgb]{0.75,0,0.25}\eta}(\hat{\pi},\tilde{\pi})=J(\hat{\pi},\tilde{\pi};\widehat{\bm{\Theta}})-J(\hat{\pi},\tilde{\pi}), where the inequality holds because \frac{1}{2}\overset{(\lx@cref{creftype\lx@tilde refnum}{lem:symmetric})}{=}\min_{\pi\in\Pi}J_{\color[rgb]{0.75,0,0.25}\eta}(\hat{\pi},\pi;\widehat{\bm{\Theta}})\overset{(Eqn.~(\ref{eqn:NE}))}{\leq}J_{\color[rgb]{0.75,0,0.25}\eta}(\hat{\pi},\tilde{\pi};\widehat{\bm{\Theta}}). Note that the symmetric nature of our game objective is critical here, as it ensures that the game value remains unchanged regardless of \bm{\Theta} ( Lemma 2.4 ). Denoting \mathbb{E}:=\mathbb{E}_{\bm{\phi}\sim\hat{\pi},\tilde{\bm{\phi}}\sim\tilde{\pi}} or \mathbb{E}_{\bm{\phi}\sim\hat{\pi}} when it is clear from the context, via Taylor expansion with integral remainder , we have the following: \displaystyle J(\hat{\pi},\tilde{\pi};\widehat{\bm{\Theta}})-J(\hat{\pi},\tilde{\pi}) \displaystyle=\underbrace{-\mathbb{E}\left[\dot{\mu}(\bm{\phi}^{\top}\bm{\Theta}_{\star}\tilde{\bm{\phi}})\bm{\phi}^{\top}{\bm{E}}\tilde{\bm{\phi}}\right]}_{(a)} \displaystyle\ +\underbrace{\mathbb{E}\left[\left[\int_{0}^{1}(1-z)\ddot{\mu}\left(\bm{\phi}^{\top}\left(\bm{\Theta}_{\star}-z{\bm{E}}_{t}\right)\tilde{\bm{\phi}}\right)dz\right](\bm{\phi}^{\top}{\bm{E}}\tilde{\bm{\phi}})^{2}\right]}_{(b)}. We bound (a) with the following simple yet powerful lemma, whose proof is deferred to the next subsection: Lemma 3.2 . For \hat{\pi},\tilde{\pi}\in\Pi and \bm{\Theta}_{\star},{\bm{E}}\in\mathrm{Skew}(d) , \left|\mathbb{E}\left[\dot{\mu}(\bm{\phi}^{\top}\bm{\Theta}_{\star}\tilde{\bm{\phi}})\bm{\phi}^{\top}{\bm{E}}\tilde{\bm{\phi}}\right]\right|\leq\frac{L_{\mu}}{2}{\color[rgb]{1,0,1}\left\lVert\hat{\pi}-\tilde{\pi}\right\rVert_{1}}\mathbb{E}_{\bm{\phi}}[\left\lVert{\bm{E}}\bm{\phi}\right\rVert_{2}]. We now bound (b) . First, we have (b)\leq L_{\mu}\mathbb{E}[(\bm{\phi}^{\top}{\bm{E}}\tilde{\bm{\phi}})^{2}]\int_{0}^{1}(1-z)dz=\frac{L_{\mu}}{2}\mathbb{E}[(\bm{\phi}^{\top}{\bm{E}}\tilde{\bm{\phi}})^{2}]. For clarity, we will explicitly distinguish between the two expectations \mathbb{E}_{\bm{\phi}} and \mathbb{E}_{\tilde{\bm{\phi}}} . Then, we have that \displaystyle\mathbb{E}[(\bm{\phi}^{\top}{\bm{E}}\tilde{\bm{\phi}})^{2}] \displaystyle=\mathbb{E}_{\bm{\phi}}\mathbb{E}_{\tilde{\bm{\phi}}}\left[\tilde{\bm{\phi}}^{\top}{\bm{E}}^{\top}\bm{\phi}\bm{\phi}^{\top}{\bm{E}}\tilde{\bm{\phi}}\right] \displaystyle\leq\mathbb{E}_{\bm{\phi}}\left[\max_{\tilde{\bm{\phi}}\in{\mathcal{B}}^{(}1)}\tilde{\bm{\phi}}^{\top}({\bm{E}}^{\top}\bm{\phi}\bm{\phi}^{\top}{\bm{E}})\tilde{\bm{\phi}}\right] \displaystyle=\mathbb{E}_{\bm{\phi}}\left[\left\lVert{\bm{E}}\bm{\phi}\right\rVert_{2}^{2}\right]. Combining everything, we have {\color[rgb]{0.75,0.5,0.25}X}\leq\frac{L_{\mu}}{2}{\color[rgb]{1,0,1}\left\lVert\hat{\pi}-\tilde{\pi}\right\rVert_{1}}\mathbb{E}_{\bm{\phi}}[\left\lVert{\bm{E}}\bm{\phi}\right\rVert_{2}]+\frac{L_{\mu}}{2}\mathbb{E}_{\bm{\phi}}\left[\left\lVert{\bm{E}}\bm{\phi}\right\rVert_{2}^{2}\right]. (8) If we naïvely bound {\color[rgb]{1,0,1}\left\lVert\hat{\pi}-\tilde{\pi}\right\rVert_{1}}\leq 1 , we recover the {\color[rgb]{0.75,0,0.25}\eta} -independent bound. Utilizing Strong Convexity. Our second key technical contribution is, instead of naïvely bounding {\color[rgb]{1,0,1}\left\lVert\hat{\pi}-\tilde{\pi}\right\rVert_{1}}\leq 1 , we deal with it using the strong convexity of \psi ! The following lemma immediately follows from the \beta^{-1} -strong convexity of \psi : Lemma 3.3 . J_{\color[rgb]{0.75,0,0.25}\eta}(\hat{\pi},\cdot) is ({\color[rgb]{0.75,0,0.25}\eta}\beta)^{-1} -strongly convex in \ell_{1} -norm, i.e., for any \pi,\tilde{\pi}\in\Pi , \displaystyle J_{\color[rgb]{0.75,0,0.25}\eta}(\hat{\pi},\pi)-J_{\color[rgb]{0.75,0,0.25}\eta}(\hat{\pi},\tilde{\pi}) \displaystyle\geq\langle\nabla_{\tilde{\pi}}J_{\color[rgb]{0.75,0,0.25}\eta}(\hat{\pi},\tilde{\pi}),\pi-\tilde{\pi}\rangle+\frac{1}{2{\color[rgb]{0.75,0,0.25}\eta}\beta}{\color[rgb]{1,0,1}\left\lVert\pi-\tilde{\pi}\right\rVert_{1}^{2}}. Then, by the above lemma, we have: \displaystyle{\color[rgb]{0.75,0.5,0.25}X} \displaystyle=J_{\color[rgb]{0.75,0,0.25}\eta}(\hat{\pi},\hat{\pi})-J_{\color[rgb]{0.75,0,0.25}\eta}(\hat{\pi},\tilde{\pi}) \displaystyle\geq\langle\nabla_{\tilde{\pi}}J_{\color[rgb]{0.75,0,0.25}\eta}(\hat{\pi},\tilde{\pi}),\hat{\pi}-\tilde{\pi}\rangle+\frac{1}{2{\color[rgb]{0.75,0,0.25}\eta}\beta}{\color[rgb]{1,0,1}\left\lVert\hat{\pi}-\tilde{\pi}\right\rVert_{1}^{2}} \displaystyle\geq\frac{1}{2{\color[rgb]{0.75,0,0.25}\eta}\beta}{\color[rgb]{1,0,1}\left\lVert\hat{\pi}-\tilde{\pi}\right\rVert_{1}^{2}}. (optimality condition 3 3 footnotemark: 3 ) Plugging this back into Eqn. ( 8 ), we have: {\color[rgb]{0.75,0.5,0.25}X}\leq\sqrt{\frac{L_{\mu}^{2}{\color[rgb]{0.75,0,0.25}\eta}\beta}{2}}\mathbb{E}_{\bm{\phi}}[\left\lVert{\bm{E}}\bm{\phi}\right\rVert_{2}]\sqrt{{\color[rgb]{0.75,0.5,0.25}X}}+\frac{L_{\mu}}{2}\mathbb{E}_{\bm{\phi}}[\left\lVert{\bm{E}}\bm{\phi}\right\rVert_{2}^{2}]. (9) Note that this is a self-bounding quadratic inequality in {\color[rgb]{0.75,0.5,0.25}X} , which can be solved as follows: 6 6 6 For b,c\geq 0 , x^{2}\leq bx+c\Rightarrow x\leq b+\sqrt{c} . {\color[rgb]{0.75,0.5,0.25}X}\leq L_{\mu}^{2}{\color[rgb]{0.75,0,0.25}\eta}\beta\mathbb{E}_{\bm{\phi}}[\left\lVert{\bm{E}}\bm{\phi}\right\rVert_{2}]^{2}+L_{\mu}\mathbb{E}_{\bm{\phi}}[\left\lVert{\bm{E}}\bm{\phi}\right\rVert_{2}^{2}]. We then conclude via Jensen’s inequality. ∎ 3.2 Proof of Lemma 3.2 Because this is a key lemma that enabled the above proof to proceed smoothly, we are devoting a separate subsection to its proof. Here, the intuition is the right mix of symmetry ( \mu(z)+\mu(-z)=1 ) and skew-symmetry ( {\bm{E}}^{\top}=-{\bm{E}} ), and somewhat surprisingly, variational representation of \left\lVert\cdot\right\rVert_{1} . First, note that \displaystyle Z \displaystyle\triangleq\mathbb{E}_{\bm{\phi},\tilde{\bm{\phi}}\sim\hat{\pi}}\left[\dot{\mu}(\bm{\phi}^{\top}\bm{\Theta}\tilde{\bm{\phi}})\bm{\phi}^{\top}{\bm{E}}\tilde{\bm{\phi}}\right] \displaystyle=\mathbb{E}_{\bm{\phi},\tilde{\bm{\phi}}\sim\hat{\pi}}\left[\dot{\mu}(\tilde{\bm{\phi}}^{\top}\bm{\Theta}\bm{\phi})\tilde{\bm{\phi}}^{\top}{\bm{E}}\bm{\phi}\right] ( \bm{\phi}\overset{d}{=}\tilde{\bm{\phi}} ) \displaystyle=-\mathbb{E}_{\bm{\phi},\tilde{\bm{\phi}}\sim\hat{\pi}}\left[\dot{\mu}(\bm{\phi}^{\top}\bm{\Theta}\tilde{\bm{\phi}})\bm{\phi}^{\top}{\bm{E}}\tilde{\bm{\phi}}\right]=-Z, ( {\bm{E}}\in\mathrm{Skew}(d) , \dot{\mu}(z)=\dot{\mu}(-z) ) i.e., Z=0 . Let us denote f(\tilde{\bm{\phi}};\bm{\phi}):=\dot{\mu}(\bm{\phi}^{\top}\bm{\Theta}\tilde{\bm{\phi}})\bm{\phi}^{\top}{\bm{E}}\tilde{\bm{\phi}} , which satisfies \max_{\tilde{\bm{\phi}}\in{\mathcal{B}}^{d}(1)}\left|f(\tilde{\bm{\phi}};\bm{\phi})\right|\leq L_{\mu}\left\lVert{\bm{E}}\bm{\phi}\right\rVert_{2} . Then, \displaystyle\left|\mathbb{E}_{\bm{\phi}\sim\hat{\pi},\tilde{\bm{\phi}}\sim\tilde{\pi}}\left[f(\tilde{\bm{\phi}};\bm{\phi})\right]\right| \displaystyle=\left|\mathbb{E}_{\bm{\phi}\sim\hat{\pi},\tilde{\bm{\phi}}\sim\tilde{\pi}}\left[f(\tilde{\bm{\phi}};\bm{\phi})\right]-Z\right| \displaystyle=\left|\mathbb{E}_{\bm{\phi}\sim\hat{\pi}}\left[\mathbb{E}_{\tilde{\bm{\phi}}\sim\hat{\pi}}\left[f(\tilde{\bm{\phi}};\bm{\phi})\right]-\mathbb{E}_{\tilde{\bm{\phi}}\sim\tilde{\pi}}\left[f(\tilde{\bm{\phi}};\bm{\phi})\right]\right]\right| \displaystyle\leq\mathbb{E}_{\bm{\phi}\sim\hat{\pi}}\left[\left|\mathbb{E}_{\tilde{\bm{\phi}}\sim\hat{\pi}}\left[f(\tilde{\bm{\phi}};\bm{\phi})\right]-\mathbb{E}_{\tilde{\bm{\phi}}\sim\tilde{\pi}}\left[f(\tilde{\bm{\phi}};\bm{\phi})\right]\right|\right] \displaystyle\overset{(*)}{\leq}\mathbb{E}_{\bm{\phi}\sim\hat{\pi}}\left[L_{\mu}\left\lVert{\bm{E}}\bm{\phi}\right\rVert_{2}\sup_{g\in{\mathcal{G}}_{\infty}(1)}\left|\int g(\tilde{\bm{\phi}})d(\hat{\pi}-\tilde{\pi})(\tilde{\bm{\phi}})\right|\right] \displaystyle\overset{(**)}{=}\frac{L_{\mu}}{2}{\color[rgb]{1,0,1}\left\lVert\hat{\pi}-\tilde{\pi}\right\rVert_{1}}\mathbb{E}_{\bm{\phi}\sim\hat{\pi}}\left[\left\lVert{\bm{E}}\bm{\phi}\right\rVert_{2}\right]. where in (*) , {\mathcal{G}}_{\infty}(1):=\left\{g:{\mathcal{B}}^{d}(1)\rightarrow[0,1]\mid\text{$g$ is measurable}\right\}, and (**) follows from the integral probability metric representation of \left\lVert\cdot\right\rVert_{1} ( 87 , Theorem 5.4) . ∎ 4 \tilde{{\mathcal{O}}}({\color[rgb]{0.75,0,0.25}\eta}(\log T)^{2}\wedge\sqrt{T}) via Greedy Sampling In this section, we assume that \mu(z)=(1+e^{-z})^{-1} , making the GLM well-specified as Bernoulli, for which a tight confidence sequence is known ( 70 , Theorem 3.2) ; refer to Remark 4.1 for extensions to generic \mu that preserve the dependencies in d and T . Also, we ignore the low-rank structure of \bm{\Theta}_{\star} to prioritize obtaining polylogarithmic regret; in Section 5 , we prioritize removing dependencies on d at the cost of obtaining \sqrt{T} regret. We show that a surprisingly simple algorithm is sufficient to obtain \tilde{{\mathcal{O}}}(\eta(\log T)^{2}\wedge\sqrt{T}) : Greedy Sampling (GS) (see Algorithm 1 in Appendix A ). The max-player always plays the greedy NE policy w.r.t. the current MLE \widehat{\bm{\Theta}}_{t} , while the min-player explores with the given \rho ( 1 ). Recently, 129 7 7 7 Technically, their algorithm is intractable in GBPM , as it requires minimizing the cross-entropy loss over \mathrm{Skew}(d,2r;S) . obtained \tilde{{\mathcal{O}}}({\color[rgb]{0.5,0,0.5}e^{9\eta}}(\log T)^{2}) for GS . However, their bound scales exponentially with \eta , is shown only for \psi(\cdot)=D_{\mathrm{KL}}(\cdot,\pi_{ref}) , and fails to yield a meaningful unregularized regret bound (e.g., as \eta\to\infty ); see Appendix F for detailed discussions. Our regret bound, in a similar spirit to 90 , adapts to both regimes gracefully: it yields (\log T)^{2} for small \eta , and transitions to \sqrt{T} as \eta increases. We defer further discussions of our regret bound to Section 6 . Remark 4.1 (Beyond Parametric) . A bandit problem in which a specific parametric distribution (e.g., GLM) is assumed for the reward is known as a parametric bandit ( 39 ) . For the semi-parametric setting where we only assume that r_{t}=\mu(\langle\bm{\theta}_{\star},\bm{\phi}_{t}\rangle)+\varepsilon_{t} with \varepsilon_{t} being bounded noise, one can adopt the maximum quasi-likelihood estimator approach of 75 , which dates back to 23 . The strategy involves a T -independent warm-up phase (random sampling) to ensure that the design matrix is sufficiently well-conditioned, thereby preserving the dependencies in d and T . 4.1 Norm + Skew-Constrained MLE We now describe the estimator for GS . Let us denote \mathrm{vec}:{\mathbb{R}}^{d\times d}\rightarrow{\mathbb{R}}^{d^{2}} as the (column-wise) vectorization operator, and \mathrm{mat}\triangleq\mathrm{vec}^{-1}:{\mathbb{R}}^{d^{2}}\rightarrow{\mathbb{R}}^{d\times d} to be its inverse, namely, the matrization operator. We first define the following convex subset of {\mathbb{R}}^{d^{2}} : 8 8 8 Note that the norm constraint \left\lVert{\bm{\theta}}\right\rVert_{2}\leq S encompasses a larger constraint region than our nuclear norm constraint \left\lVert\bm{\Theta}\right\rVert_{\mathrm{nuc}}\leq S from Definition 2.2 , and is hence consistent. \mathcal{K}_{S}:=\left\{{\bm{\theta}}\in\mathbb{R}^{d^{2}}:\left\lVert{\bm{\theta}}\right\rVert_{2}\leq S\text{ and }\mathrm{mat}({\bm{\theta}})^{\top}=-\mathrm{mat}({\bm{\theta}})\right\}. Taking inspiration from 71 ; 70 , we employ the maximum likelihood estimator (MLE) constrained to {\mathcal{K}}_{S} . Denoting {\bm{v}}_{t}:=\mathrm{vec}(\bm{\phi}_{t}^{2}(\bm{\phi}_{t}^{1})^{\top})\in{\mathbb{R}}^{d^{2}} , \displaystyle\widehat{\bm{\Theta}}_{t}\leftarrow\mathrm{mat}(\hat{{\bm{\theta}}}_{t}),\quad\hat{{\bm{\theta}}}_{t}\leftarrow\argmin_{{\bm{\theta}}\in{\mathcal{K}}_{S}}{\mathcal{L}}_{t}({\bm{\theta}}), (10) \displaystyle{\mathcal{L}}_{t}({\bm{\theta}}):=\sum_{s=1}^{t-1}\left\{m(\langle{\bm{\theta}},{\bm{v}}_{s}\rangle)-r_{s}\langle{\bm{\theta}},{\bm{v}}_{s}\rangle\right\}, (11) where m(\cdot) is the log-partition function ( 123 ) such that m^{\prime}=\mu . With this, we now present our regularized regret bound: Theorem 4.2 . Let \delta\in(0,1) and suppose that d^{2}\log\frac{T}{d}\gtrsim\kappa^{-1}\log\frac{1}{\delta} . Then, with probability at least 1-\delta, GS simultaneously attains the following bounds: \displaystyle\mathrm{MBR\text{-}Reg}_{\color[rgb]{0.75,0,0.25}\eta}(T) \displaystyle\lesssim{\color[rgb]{0.75,0,0.25}\eta}\beta\kappa^{-1}d^{4}C_{\min}^{-1}\left(\log\frac{T}{d}\right)^{2}, \displaystyle\mathrm{MBR\text{-}Reg}_{\color[rgb]{0.75,0,0.25}\eta}(T) \displaystyle\lesssim\kappa^{-\frac{1}{2}}C_{\min}^{-\frac{1}{2}}d^{2}\sqrt{T}\log\frac{T}{d}. We highlight three important remarks regarding this result. First , as claimed earlier, our regret bounds are indeed free of {\color[rgb]{0.75,0,0.25}e^{{\mathcal{O}}(\eta)}} factors, albeit at the cost of C_{\min}^{-1} and the additional feature diversity assumption ( 1 ). We emphasize that C_{\min}^{-1} is a quantity strictly independent of the regularizer or its strength {\color[rgb]{0.75,0,0.25}\eta} ; it is determined solely by the geometry of the arm-set and how well-conditioned it is. Consequently, for well-conditioned arm-sets where C_{\min}^{-1}=\Theta(1) (e.g., hypercubes), this dependence is benign. Second , as detailed in Section B.4 , we can completely bypass the feature diversity assumption for specific choices of \psi(\cdot) . In these cases, the same guarantees hold with C_{\min}^{-1} replaced by a function of {\color[rgb]{0.75,0,0.25}\eta} . Specifically, when \psi(\cdot)=D_{\mathrm{KL}}(\cdot,\pi_{\mathrm{ref}}) (reverse KL-regularization, 129 ), \psi(\cdot)=D_{\chi^{2}}(\cdot,\pi_{\mathrm{ref}}) (chi-squared, 51 ), or \psi(\cdot)=D_{\mathrm{KL}}(\cdot,\pi_{\mathrm{ref}})+D_{\chi^{2}}(\cdot,\pi_{\mathrm{ref}}) (mixed chi-squared, 52 ) for some fixed \pi_{\mathrm{ref}}\in\Pi , the C_{\min}^{-1} term is replaced by {\color[rgb]{0.75,0,0.25}e^{\eta}} , {\color[rgb]{0.75,0,0.25}\eta} , and {\color[rgb]{0.75,0,0.25}1+\eta} , respectively. Although we still incur an {\color[rgb]{0.75,0,0.25}e^{\eta}} factor for reverse KL-regularization, this remains a notable improvement over the {\color[rgb]{0.75,0,0.25}e^{9\eta}} dependency in 129 . Furthermore, while our theoretical framework gracefully accommodates any strongly convex regularizer, it remains unclear whether the analysis of 129 can easily extend beyond reverse KL. Third , our regret guarantees extend to \mathrm{ABR\text{-}Reg}(T) via symmetric play under reverse KL-regularization D_{\mathrm{KL}}(\cdot,\pi_{\mathrm{ref}}) , provided \rho=\pi_{\mathrm{ref}} . Ensuring diversity when both players act greedily incurs an additional {\color[rgb]{0.75,0,0.25}\eta} -dependent factor as we need to invoke Proposition B.5 twice (see Section B.4 ). 4.2 Proof Sketch of Theorem 4.2 We provide a high-level sketch of the proof here; the full detailed proof is deferred to Appendix B . The analysis proceeds in three main steps: 1. From Regret to Sum of Squared Errors. We begin with the instantaneous regret bound established in Theorem 3.1 , which bounds the instantaneous dual gap by the squared estimation error: \mathrm{DGap}({\color[rgb]{0,0,1}\hat{\pi}_{t}})\lesssim\mathbb{E}_{{\color[rgb]{0,0,1}\bm{\phi}\sim\hat{\pi}_{t}}}[\|{\bm{E}}_{t}\bm{\phi}\|_{2}^{2}] . Using a standard basis decomposition, Cauchy-Schwarz w.r.t. the regularized Hessian of the log-likelihood loss \widehat{{\bm{H}}}_{t}\triangleq{\bm{I}}_{d^{2}}+\nabla^{2}{\mathcal{L}}_{t}(\hat{{\bm{\theta}}}_{t})\in{\mathbb{R}}^{d^{2}\times d^{2}} , and the confidence sequence for the constrained MLE ( 70 , Theorem 3.2) , we further bound this error by the sum of expected elliptical potentials. Here, one side is the standard basis {\bm{e}}_{j} and the other is chosen by {\color[rgb]{0,0,1}\hat{\pi}_{t}} : \mathrm{DGap}({\color[rgb]{0,0,1}\hat{\pi}_{t}})\lesssim(d^{2}\log T)\sum_{j=1}^{d}\mathbb{E}_{{\color[rgb]{0,0,1}\bm{\phi}\sim\hat{\pi}_{t}}}\left[\left\lVert{\color[rgb]{0,0,1}\bm{\phi}}\otimes{\color[rgb]{1,0,0}{\bm{e}}_{j}}\right\rVert_{\widehat{{\bm{H}}}_{t}^{-1}}^{2}\right]. 2. Towards Expected Elliptical Potentials. A discrepancy arises in the RHS: the upper bound involves a sum over fixed basis vectors on one side, whereas the empirical Hessian aggregates the played features on both sides. We resolve this via our Coverage Lemma ( Lemma B.2 ). Leveraging the feature diversity assumption ( 1 ), \sum_{t}\mathrm{DGap}({\color[rgb]{0,0,1}\hat{\pi}_{t}}) is bounded by (d^{2}\log T)C_{\min}^{-1}\underbrace{\sum_{t=1}^{T}\mathbb{E}_{{\color[rgb]{0,0,1}\bm{\phi}_{t}\sim\hat{\pi}_{t}},{\color[rgb]{1,0,0}\tilde{\bm{\phi}}_{t}\sim\rho}}\left[\left\lVert\mathrm{vec}({\color[rgb]{0,0,1}\bm{\phi}_{t}}{\color[rgb]{1,0,0}\tilde{\bm{\phi}}_{t}}^{\top})\right\rVert_{\widehat{{\bm{H}}}_{t}^{-1}}^{2}\right]}_{\triangleq{\color[rgb]{0.75,0.5,0.25}S_{T}}}. 3. Martingale Concentration for Realized Variance. The final challenge is to bound the sum of expected elliptical potentials {\color[rgb]{0.75,0.5,0.25}S_{T}} . The standard Elliptical Potential Lemma ( 1 , Lemma 11) controls the sum of realized potentials. To bridge this gap, we decompose the term into the realized sum plus a sum of martingale differences . Applying Freedman’s inequality ( 43 ; 15 ; 71 ) , we derive a linear self-bounding inequality of the form: {\color[rgb]{0.75,0.5,0.25}S_{T}}\leq A{\color[rgb]{0.75,0.5,0.25}S_{T}}+\tilde{\mathcal{O}}(d^{2}\log T), where A<1 is a constant. Solving this recursion yields the final \tilde{\mathcal{O}}(d^{4}(\log T)^{2}) rate. ∎ 5 \mathrm{poly}(d) -free \tilde{{\mathcal{O}}}(\sqrt{{\color[rgb]{0.75,0,0.25}\eta}T}\wedge T^{\frac{2}{3}}) via ETC High-Dimensional Regime. We now ask, what gains can we obtain if we maximally exploit the low-rank structure of \bm{\Theta}_{\star} . This question is particularly relevant in the high-dimensional or data-poor regime, where T is not sufficiently large relative to d (specifically, d^{c_{1}}\lesssim T\lesssim d^{c_{2}} for constants 00$.\end{cases} Otherwise. If not, then we simply lower bound \int_{0}^{1}(1-z)\dot{\mu}\left(\langle\bm{\Theta}_{\star}+z\Delta,{\bm{X}}_{t}\rangle\right)dz\geq\kappa\int_{0}^{1}(1-z)dz=\frac{\kappa}{2}. With a slight overload of notation, if self-concordance does not hold, we define \tilde{R}_{s}=\frac{1}{2} . Concluding the proof. Let us define the vectorized population and empirical design matrices: {\bm{V}}:=\mathbb{E}_{{\bm{X}}}\left[\mathrm{\mathrm{vec}}({\bm{X}})\mathrm{\mathrm{vec}}({\bm{X}})^{\top}\right],\quad\widehat{{\bm{V}}}:=\frac{1}{T_{0}}\sum_{t=1}^{T_{0}}\mathrm{vec}({\bm{X}}_{t})\mathrm{vec}({\bm{X}}_{t})^{\top}. (33) Observe that \displaystyle{\bm{V}} \displaystyle=\mathbb{E}_{\bm{\phi}^{1},\bm{\phi}^{2}}\left[(\bm{\phi}^{2}\otimes\bm{\phi}^{1})(\bm{\phi}^{2}\otimes\bm{\phi}^{1})^{\top}\right] ( \mathrm{vec}({\bm{a}}{\bm{b}}^{\top})={\bm{b}}\otimes{\bm{a}} ) \displaystyle=\mathbb{E}_{\bm{\phi}^{1},\bm{\phi}^{2}}\left[(\bm{\phi}^{2}(\bm{\phi}^{2})^{\top})\otimes(\bm{\phi}^{1}(\bm{\phi}^{1})^{\top})\right] (mixed product property of the Kronecker product) \displaystyle=\mathbb{E}_{\bm{\phi}}\left[\bm{\phi}\bm{\phi}^{\top}\right]^{\otimes 2}, ( \bm{\phi}^{1}\overset{d}{=}\bm{\phi}^{2} ) and thus, \lambda_{\min}\left({\bm{V}}\right)=\lambda_{\min}\left(\mathbb{E}_{\bm{\phi}}\left[\bm{\phi}\bm{\phi}^{\top}\right]\right)^{2}\geq C_{\min}^{2} by 1 . Thus, we have that \displaystyle{\mathcal{L}}_{T_{0}}(\bm{\Theta}_{\star}+\Delta)-{\mathcal{L}}_{T_{0}}(\bm{\Theta}_{\star})-\langle\nabla{\mathcal{L}}_{T_{0}}(\bm{\Theta}_{\star}),\Delta\rangle \displaystyle\geq\tilde{R}_{s}\tilde{\kappa}\mathrm{vec}(\Delta)^{\top}\widehat{{\bm{V}}}\mathrm{vec}(\Delta) \displaystyle=\tilde{R}_{s}\tilde{\kappa}\mathrm{vec}(\Delta)^{\top}{\bm{V}}\mathrm{vec}(\Delta)+\tilde{R}_{s}\tilde{\kappa}\mathrm{vec}(\Delta)^{\top}(\widehat{{\bm{V}}}-{\bm{V}})\mathrm{vec}(\Delta) \displaystyle\geq\tilde{R}_{s}\tilde{\kappa}C_{\min}^{2}\left\lVert\Delta\right\rVert_{F}^{2}-\tilde{R}_{s}\tilde{\kappa}\underbrace{\left|\mathrm{vec}(\Delta)^{\top}(\widehat{{\bm{V}}}-{\bm{V}})\mathrm{vec}(\Delta)\right|}_{\triangleq{\mathcal{E}}_{T_{0}}} Using the standard empirical process theory and peeling argument over the ball \mathbb{B}_{F}(R) (see, e.g., proof of 124 ), one can establish that the deviation is uniformly bounded as {\mathbb{P}}\left({\mathcal{E}}_{T_{0}}\leq\frac{\tilde{R}_{s}\tilde{\kappa}C_{\min}^{2}}{2}\left\lVert\Delta\right\rVert_{F}^{2}\right)\geq 1-\frac{\delta}{2}, (34) provided T_{0}\gtrsim C_{\min}^{-4}\tilde{\kappa}^{-2}dr\log\frac{d}{\delta} . ∎ Appendix D Discussions on Regrets D.1 Four Regret Definitions and Discussions A standard measure of performance in online learning is regret . However, because the interaction is two-player and self-play, there are several ways to define regret, arising from different yet closely related communities: no-regret learning in games, dueling bandits/RL, and RL in two-player zero-sum games. In the main text, we consider only two regrets ( \mathrm{ABR\text{-}Reg}_{\color[rgb]{0.75,0,0.25}\eta} and \mathrm{MBR\text{-}Reg}_{\color[rgb]{0.75,0,0.25}\eta} ) for brevity, and so in this Appendix, we provide the deferred discussions regarding four regrets: Definition D.1 . The four regrets are defined as follows. (a) Average-Nash Regret : \mathrm{AN\text{-}Reg}_{\color[rgb]{0.75,0,0.25}\eta}(T):=\max_{\pi^{1},\pi^{2}\in\Pi}\sum_{t=1}^{T}\left\{J_{\color[rgb]{0.75,0,0.25}\eta}(\pi^{1},{\color[rgb]{1,0,0}\hat{\pi}_{t}^{2}})-J_{\color[rgb]{0.75,0,0.25}\eta}({\color[rgb]{0,0,1}\hat{\pi}_{t}^{1}},\pi^{2})\right\}. (b) Average-Best-Response Regret : \mathrm{ABR\text{-}Reg}_{\color[rgb]{0.75,0,0.25}\eta}(T):=\sum_{t=1}^{T}\max_{\pi^{1},\pi^{2}\in\Pi}\left\{J_{\color[rgb]{0.75,0,0.25}\eta}(\pi^{1},{\color[rgb]{1,0,0}\hat{\pi}_{t}^{2}})-J_{\color[rgb]{0.75,0,0.25}\eta}({\color[rgb]{0,0,1}\hat{\pi}_{t}^{1}},\pi^{2})\right\}. (c) Max-Nash Regret : \mathrm{MN\text{-}Reg}_{\color[rgb]{0.75,0,0.25}\eta}(T):=\max_{\pi\in\Pi}\sum_{t=1}^{T}\left\{\frac{1}{2}-J_{\color[rgb]{0.75,0,0.25}\eta}({\color[rgb]{0,0,1}\hat{\pi}_{t}^{1}},\pi)\right\}. (d) Max-Best-Response Regret : \mathrm{MBR\text{-}Reg}_{\color[rgb]{0.75,0,0.25}\eta}(T):=\sum_{t=1}^{T}\max_{\pi\in\Pi}\left\{\frac{1}{2}-J_{\color[rgb]{0.75,0,0.25}\eta}({\color[rgb]{0,0,1}\hat{\pi}_{t}^{1}},\pi)\right\}. The unregularized variants are defined similarly and denoted without the {\color[rgb]{0.75,0,0.25}\eta} subscript. Categorization Criteria. There are two criteria that determine each regret definition. The first criterion is, at each time t , whether to consider the regrets of both players simultaneously, or to consider the regret of the max-player only. This distinguishes between Average or Max . The second criterion is whether to compare against a fixed comparator or to compare against the best response at each time t , which is usually time-varying. This distinguishes between Nash and Best-Response . Intuitively, the Average regret definitions consider the “suboptimality” of both policies simultaneously. The difference between Nash and Best-Response is whether the regret is defined w.r.t. a fixed comparator ( Nash ) or a dynamically changing comparator ( Best-Response ). Thus, in classical literature, they are also known as external and internal (swap) regrets. Average Regrets. \mathrm{AN\text{-}Reg}(T) is the notion originally considered in the seminal work of 44 , followed by numerous works on no-regret learning dynamics in games ( 31 ; 32 ; 33 ; 100 ; 101 ; 115 ) , recently adopted to game-theoretic LLM alignment ( 147 ) . \mathrm{AN\text{-}Reg}(T) is precisely the regret considered in contextual dueling bandits ( 36 , Eqn. (3)) and dueling RL ( 107 , Eqn. (4)) ; indeed, for any \pi\in\Pi , utilizing the anti-symmetry of J(\cdot,\cdot) , we can rewrite J(\pi,{\color[rgb]{1,0,0}\hat{\pi}_{t}^{2}})-J({\color[rgb]{0,0,1}\hat{\pi}_{t}^{1}},\pi)=J(\pi,{\color[rgb]{0,0,1}\hat{\pi}_{t}^{1}})+J(\pi,{\color[rgb]{1,0,0}\hat{\pi}_{t}^{2}})-1. This also slightly resembles Borda regret in dueling bandits ( 105 ; 132 ) , and average regret in dueling bandits under linear stochastic transitivity ( 108 ; 12 ; 13 ) . On the other hand, \mathrm{ABR\text{-}Reg}(T) strongly resembles the notion of best response regret in adversarial dueling bandits ( 106 , Eqn. (1)) , but there is a key difference. In 106 , the comparator at time t is the same for both players, whereas in our regret setting, it differs for each player. Basically, each player must compete with the worst-case (strongest) adversary from her perspective, who chooses the best response from his perspective. Max Regrets. The notion of considering the regret of the max player dates back to the self-play framework for RL in two-player zero-sum games ( 9 ; 8 ; 80 ; 59 ; 136 ) ; this idea has been recently applied to theoretical analyses of online RLHF under general preference ( 139 ; 129 ) . Basically, the intuition is that the learner only cares about obtaining the NE policy for the max-player, which is the policy that is actually deployed in practice. Note that the min-player’s policies {\color[rgb]{1,0,0}\hat{\pi}_{t}^{2}} do not contribute to the regret at all, and thus, often, the min-player acts as an exploration agent whose sole role is to collect as much information as possible to facilitate the learning of the max-player ( 9 ; 8 ; 80 ; 59 ; 136 ; 135 ; 139 ) . D.2 Online-to-Batch Conversion A standard consequence of no-regret learning in repeated zero-sum games is an online-to-batch conversion : the time-averaged (mixed) policies form an approximate Nash equilibrium. We formalize this statement in the following proposition. Proposition D.2 (Online-to-batch conversion) . Let \{(\hat{\pi}_{t}^{1},\hat{\pi}_{t}^{2})\}_{t=1}^{T}\subseteq\Pi\times\Pi be any policy sequence. Define the uniform mixture policies as \bar{\pi}_{T}^{i}:=\frac{1}{T}\sum_{t=1}^{T}\hat{\pi}_{t}^{i} for i\in\{1,2\} and for simplicity, let us denote \bar{\pi}_{T}:=\bar{\pi}_{T}^{1} . (a) Average regrets. For average regrets, (\bar{\pi}_{T}^{1},\bar{\pi}_{T}^{2}) is a \frac{\mathrm{Reg}(T)}{T} -approximate symmetric NE: \max_{\pi^{1},\pi^{2}\in\Pi}\Bigl\{J_{\color[rgb]{0.75,0,0.25}\eta}(\pi^{1},\bar{\pi}_{T}^{2})-J_{\color[rgb]{0.75,0,0.25}\eta}(\bar{\pi}_{T}^{1},\pi^{2})\Bigr\}\;\leq\;\frac{\mathrm{AN\text{-}Reg}_{\color[rgb]{0.75,0,0.25}\eta}(T)}{T}\;\leq\;\frac{\mathrm{ABR\text{-}Reg}_{\color[rgb]{0.75,0,0.25}\eta}(T)}{T}. (b) Max regrets. For max regrets, \bar{\pi}_{T} is a \frac{2\mathrm{Reg}(T)}{T} -approximate symmetric NE: \max_{\pi\in\Pi}\Bigl\{J_{\color[rgb]{0.75,0,0.25}\eta}(\pi,\bar{\pi}_{T})-J_{\color[rgb]{0.75,0,0.25}\eta}(\bar{\pi}_{T},\pi)\Bigr\}\;\leq\;\frac{2\mathrm{MN\text{-}Reg}_{\color[rgb]{0.75,0,0.25}\eta}(T)}{T}\;\leq\;\frac{2\mathrm{MBR\text{-}Reg}_{\color[rgb]{0.75,0,0.25}\eta}(T)}{T}. Proof. (a) Fix any \pi^{1},\pi^{2}\in\Pi . By the bilinearity of J and Jensen’s inequality w.r.t. \psi(\cdot) , J_{\color[rgb]{0.75,0,0.25}\eta}(\pi^{1},\bar{\pi}_{T}^{2})=J(\pi^{1},\bar{\pi}_{T}^{2})-{\color[rgb]{0.75,0,0.25}\eta^{-1}}\psi(\pi^{1})+{\color[rgb]{0.75,0,0.25}\eta^{-1}}\psi(\bar{\pi}_{T}^{2})\leq\frac{1}{T}\sum_{t=1}^{T}J_{\color[rgb]{0.75,0,0.25}\eta}(\pi^{1},\hat{\pi}_{t}^{2}), and similarly, J_{\color[rgb]{0.75,0,0.25}\eta}(\bar{\pi}_{T}^{1},\pi^{2})=J(\bar{\pi}_{T}^{1},\pi^{2})-{\color[rgb]{0.75,0,0.25}\eta^{-1}}\psi(\bar{\pi}_{T}^{1})+{\color[rgb]{0.75,0,0.25}\eta^{-1}}\psi(\pi^{2})\geq\frac{1}{T}\sum_{t=1}^{T}J_{\color[rgb]{0.75,0,0.25}\eta}(\hat{\pi}_{t}^{1},\pi^{2}). Subtracting the two inequalities and taking \max_{\pi^{1},\pi^{2}} yields \displaystyle\max_{\pi^{1},\pi^{2}}\Bigl\{J_{\color[rgb]{0.75,0,0.25}\eta}(\pi^{1},\bar{\pi}_{T}^{2})-J_{\color[rgb]{0.75,0,0.25}\eta}(\bar{\pi}_{T}^{1},\pi^{2})\Bigr\} \displaystyle\leq\frac{1}{T}\max_{\pi^{1},\pi^{2}}\sum_{t=1}^{T}\Bigl(J_{\color[rgb]{0.75,0,0.25}\eta}(\pi^{1},\hat{\pi}_{t}^{2})-J_{\color[rgb]{0.75,0,0.25}\eta}(\hat{\pi}_{t}^{1},\pi^{2})\Bigr) \displaystyle\leq\frac{1}{T}\sum_{t=1}^{T}\max_{\pi^{1},\pi^{2}}\Bigl(J_{\color[rgb]{0.75,0,0.25}\eta}(\pi^{1},\hat{\pi}_{t}^{2})-J_{\color[rgb]{0.75,0,0.25}\eta}(\hat{\pi}_{t}^{1},\pi^{2})\Bigr) (b) By the same averaging argument (bilinearity of J and Jensen’s inequality), for every \pi\in\Pi , J_{\color[rgb]{0.75,0,0.25}\eta}(\pi,\bar{\pi}_{T})-J_{\color[rgb]{0.75,0,0.25}\eta}(\bar{\pi}_{T},\pi)\leq\frac{1}{T}\sum_{t=1}^{T}\Bigl(J_{\color[rgb]{0.75,0,0.25}\eta}(\pi,\hat{\pi}_{t}^{1})-J_{\color[rgb]{0.75,0,0.25}\eta}(\hat{\pi}_{t}^{1},\pi)\Bigr). Since for each t , J_{\color[rgb]{0.75,0,0.25}\eta}(\pi,\hat{\pi}_{t}^{1})-J_{\color[rgb]{0.75,0,0.25}\eta}(\hat{\pi}_{t}^{1},\pi)=2\Bigl(\tfrac{1}{2}-J_{\color[rgb]{0.75,0,0.25}\eta}(\hat{\pi}_{t}^{1},\pi)\Bigr) , taking \max_{\pi} and substituting yields \displaystyle\max_{\pi}\bigl\{J_{\color[rgb]{0.75,0,0.25}\eta}(\pi,\bar{\pi}_{T})-J_{\color[rgb]{0.75,0,0.25}\eta}(\bar{\pi}_{T},\pi)\bigr\}\leq\frac{2}{T}\max_{\pi}\sum_{t=1}^{T}\Bigl(\tfrac{1}{2}-J_{\color[rgb]{0.75,0,0.25}\eta}(\hat{\pi}_{t}^{1},\pi)\Bigr)\leq\frac{2}{T}\sum_{t=1}^{T}\max_{\pi}\Bigl(\tfrac{1}{2}-J_{\color[rgb]{0.75,0,0.25}\eta}(\hat{\pi}_{t}^{1},\pi)\Bigr). ∎ Appendix E Eluder Dimension of GBPM E.1 Upper Bounding the Eluder Dimension of 129 To instantiate the regret bound of 129 in Appendix F , we first recall their specific notion of the eluder dimension: Definition E.1 (Eluder dimension, General Preference Model ( 129 ) ) . Under the general preference model, for any \mathcal{D}_{t-1}=\{({\bm{x}}_{i},{\bm{a}}^{1}_{i},{\bm{a}}^{2}_{i})\}_{i=1}^{t-1} , we define the uncertainty of ({\bm{x}},{\bm{a}}^{1},{\bm{a}}^{2}) with respect to \mathcal{P} as U_{\texttt{GP}}(\lambda,{\bm{x}},{\bm{a}}^{1},{\bm{a}}^{2};\mathcal{P},\mathcal{D}_{t-1})=\sup_{P_{1},P_{2}\in\mathcal{P}}\frac{|P_{1}({\bm{a}}^{1}\succ{\bm{a}}^{2}\mid{\bm{x}})-P_{2}({\bm{a}}^{1}\succ{\bm{a}}^{2}\mid{\bm{x}})|}{\sqrt{\lambda+\sum_{s=1}^{t-1}(P_{1}({\bm{a}}^{1}_{s}\succ{\bm{a}}^{2}_{s}\mid{\bm{x}}_{s})-P_{2}({\bm{a}}^{1}_{s}\succ{\bm{a}}^{2}_{s}\mid{\bm{x}}_{s}))^{2}}}. Then the eluder dimension of {\mathcal{P}} is defined as d(\mathcal{P},\lambda,T):=\sup_{{\bm{x}}_{1:T},{\bm{a}}^{1}_{1:T},{\bm{a}}^{2}_{1:T}}\sum_{t\in[T]}\min\left\{1,\left[U_{\texttt{GP}}(\lambda,{\bm{x}}_{t},{\bm{a}}^{1}_{t},{\bm{a}}^{2}_{t};\mathcal{P},\mathcal{D}_{t-1})\right]^{2}\right\}. Using the standard elliptical potential arguments, we now derive an upper bound for this complexity measure under the GBPM: Proposition E.2 . For GBPM, the eluder dimension d(\mathcal{P},\lambda,T) is bounded as d(\mathcal{P},\lambda,T)\leq\frac{2d^{2}L_{\mu}^{2}}{\kappa^{2}}\log\left(1+\frac{4\kappa^{2}S^{2}T}{d^{2}\lambda}\right). Proof. For the proof, let us arbitrarily fix a sequence of context-action-action pairs ({\bm{x}}_{1:T},{\bm{a}}^{1}_{1:T},{\bm{a}}^{2}_{1:T}) , and let us denote the induced sequence of features as \bm{\phi}_{1:T}^{1} and \bm{\phi}_{1:T}^{2} , where \bm{\phi}_{t}^{i}:=\bm{\phi}({\bm{x}}_{t},{\bm{a}}_{t}^{i}) for t\in[T] and i\in\{1,2\}. Let us also denote \bm{\Phi}_{t}:=\bm{\phi}_{t}^{1}(\bm{\phi}_{t}^{2})^{\top} . For any \bm{\Theta}\in\Theta , the induced preference model is defined as P_{\bm{\Theta}}(\bm{\phi}_{t}^{1},\bm{\phi}_{t}^{2}):=\mu\left((\bm{\phi}_{t}^{1})^{\top}\bm{\Theta}\phi_{t}^{2}\right)=\mu\left(\langle\bm{\Theta},\bm{\Phi}_{t}\right). (35) We bound the uncertainty via the elliptical potential lemma ( Lemma G.3 ). Let us denote P_{i}=P_{\bm{\Theta}_{i}} for some arbitrary \bm{\Theta}_{i}\in\Theta. We first upper bound the numerator as follows: denoting \alpha({\bm{x}},{\bm{\theta}}_{1},{\bm{\theta}}_{2})\coloneqq\int_{0}^{1}\dot{\mu}\bigl({\bm{x}}^{\top}{\bm{\theta}}_{1}+z\,{\bm{x}}^{\top}({\bm{\theta}}_{2}-{\bm{\theta}}_{1})\bigr)\,dz for {\bm{x}},{\bm{\theta}}_{1},{\bm{\theta}}_{2}\in{\mathbb{R}}^{d} , \displaystyle\left|\mu\left(\langle\bm{\Theta}_{1},\bm{\Phi}_{t}\rangle\right)-\mu\left(\langle\bm{\Theta}_{2},\bm{\Phi}_{t}\rangle\right)\right| \displaystyle\quad=\left|\alpha\!\left(\operatorname{vec}(\bm{\Phi}_{t}),\operatorname{vec}(\bm{\Theta}_{1}),\operatorname{vec}(\bm{\Theta}_{2})\right)\langle\bm{\Theta}_{1}-\bm{\Theta}_{2},\bm{\Phi}_{t}\rangle\right| (Mean-value theorem) \displaystyle\quad=\left|\left\langle\bm{\Theta}_{1}-\bm{\Theta}_{2},\underbrace{\alpha\!\left(\operatorname{vec}(\bm{\Phi}_{t}),\operatorname{vec}(\bm{\Theta}_{1}),\operatorname{vec}(\bm{\Theta}_{2})\right)\bm{\Phi}_{t}}_{\triangleq\bar{\bm{\Phi}}_{t}(\bm{\Theta}_{1},\bm{\Theta}_{2})}\right\rangle\right| \displaystyle\quad\leq\left\lVert\mathrm{vec}(\bm{\Theta}_{1}-\bm{\Theta}_{2})\right\rVert_{{\bm{G}}_{t}(\bm{\Theta}_{1},\bm{\Theta}_{2})}\left\lVert\mathrm{vec}(\bar{\bm{\Phi}}_{t}(\bm{\Theta}_{1},\bm{\Theta}_{2}))\right\rVert_{{\bm{G}}_{t}(\bm{\Theta}_{1},\bm{\Theta}_{2})^{-1}} (Cauchy-Schwarz inequality) for some matrix {\bm{G}}_{t}(\bm{\Theta}_{1},\bm{\Theta}_{2})\succ{\bm{0}} to be determined later. For the denominator squared: \displaystyle\lambda+\sum_{s=1}^{t-1}\left(\mu\left(\langle\bm{\Theta}_{1},\bm{\Phi}_{s}\rangle\right)-\mu\left(\langle\bm{\Theta}_{2},\bm{\Phi}_{s}\rangle\right)\right)^{2} \displaystyle=\lambda+\sum_{s=1}^{t-1}\left[\alpha\!\left(\operatorname{vec}(\bm{\Phi}_{s}),\operatorname{vec}(\bm{\Theta}_{1}),\operatorname{vec}(\bm{\Theta}_{2})\right)^{2}\langle\bm{\Theta}_{1}-\bm{\Theta}_{2},\bm{\Phi}_{s}\rangle^{2}\right] \displaystyle=\lambda+\operatorname{vec}\!\left(\bm{\Theta}_{1}-\bm{\Theta}_{2}\right)^{\top}\left[\sum_{s=1}^{t-1}\left(\alpha\!\left(\operatorname{vec}(\bm{\Phi}_{s}),\operatorname{vec}(\bm{\Theta}_{1}),\operatorname{vec}(\bm{\Theta}_{2})\right)^{2}\operatorname{vec}(\bm{\Phi}_{s})\,\operatorname{vec}(\bm{\Phi}_{s})^{\top}\right)\right]\operatorname{vec}\!\left(\bm{\Theta}_{1}-\bm{\Theta}_{2}\right) \displaystyle\geq\mathrm{vec}(\bm{\Theta}_{1}-\bm{\Theta}_{2})^{\top}\underbrace{\left[\frac{\lambda}{4S^{2}}{\bm{I}}+\sum_{s=1}^{t-1}\!\left[\alpha\!\left(\operatorname{vec}(\bm{\Phi}_{s}),\operatorname{vec}(\bm{\Theta}_{1}),\operatorname{vec}(\bm{\Theta}_{2})\right)^{2}\operatorname{vec}(\bm{\Phi}_{s})\operatorname{vec}(\bm{\Phi}_{s})^{\top}\right]\right]}_{\triangleq{\bm{G}}_{t}(\bm{\Theta}_{1},\bm{\Theta}_{2})}\mathrm{vec}(\bm{\Theta}_{1}-\bm{\Theta}_{2}) \displaystyle=\left\lVert\mathrm{vec}(\bm{\Theta}_{1}-\bm{\Theta}_{2})\right\rVert_{{\bm{G}}_{t}(\bm{\Theta}_{1},\bm{\Theta}_{2})}^{2}. Combining the above two inequalities, we have that \displaystyle U_{\texttt{GP}}(\lambda,{\bm{x}},{\bm{a}}^{1},{\bm{a}}^{2};\mathcal{P},\mathcal{D}_{t-1}) \displaystyle\leq\sup_{\bm{\Theta}_{1},\bm{\Theta}_{2}\in\Theta}\frac{\left\lVert\mathrm{vec}(\bm{\Theta}_{1}-\bm{\Theta}_{2})\right\rVert_{{\bm{G}}_{t}}\left\lVert\mathrm{vec}(\bar{\bm{\Phi}}_{t}(\bm{\Theta}_{1},\bm{\Theta}_{2}))\right\rVert_{{\bm{G}}_{t}(\bm{\Theta}_{1},\bm{\Theta}_{2})^{-1}}}{\left\lVert\mathrm{vec}(\bm{\Theta}_{1}-\bm{\Theta}_{2})\right\rVert_{{\bm{G}}_{t}(\bm{\Theta}_{1},\bm{\Theta}_{2})}} \displaystyle=\sup_{\bm{\Theta}_{1},\bm{\Theta}_{2}\in\Theta}\left\lVert\mathrm{vec}(\bar{\bm{\Phi}}_{t}(\bm{\Theta}_{1},\bm{\Theta}_{2}))\right\rVert_{{\bm{G}}_{t}(\bm{\Theta}_{1},\bm{\Theta}_{2})^{-1}} We can lower-bound {\bm{G}}_{t}(\bm{\Theta}_{1},\bm{\Theta}_{2}) in the Löwner sense using the fact that \alpha(\cdot,\cdot,\cdot)\geq\kappa , {\bm{G}}_{t}(\bm{\Theta}_{1},\bm{\Theta}_{2})\succeq\frac{\lambda}{4S^{2}}{\bm{I}}+\sum_{s=1}^{t-1}\kappa^{2}\operatorname{vec}({\bm{\Phi}}_{s})\operatorname{vec}({\bm{\Phi}}_{s})^{\top}=\frac{\lambda}{4S^{2}}{\bm{I}}+\sum_{s=1}^{t-1}\operatorname{vec}(\kappa{\bm{\Phi}}_{s})\operatorname{vec}(\kappa{\bm{\Phi}}_{s})^{\top}\triangleq{\bm{V}}_{t}. Then, as \alpha(\cdot,\cdot,\cdot)\leq L_{\mu} , we have that U_{\texttt{GP}}(\lambda,{\bm{x}},{\bm{a}}^{1},{\bm{a}}^{2};\mathcal{P},\mathcal{D}_{t-1})\leq\frac{L_{\mu}}{\kappa}\left\lVert\operatorname{vec}(\kappa\bm{\Phi}_{t})\right\rVert_{{\bm{V}}_{t}^{-1}}. (36) We then conclude the proof via the elliptical potential lemma ( Lemma G.3 ): \displaystyle d({\mathcal{P}},\lambda,T) \displaystyle\leq\sum_{t=1}^{T}\min\left\{1,\frac{L_{\mu}^{2}}{\kappa^{2}}\left\lVert\operatorname{vec}(\kappa\bm{\Phi}_{t})\right\rVert_{{\bm{V}}_{t}^{-1}}^{2}\right\} \displaystyle\leq\frac{L_{\mu}^{2}}{\kappa^{2}}\sum_{t=1}^{T}\min\left\{1,\left\lVert\operatorname{vec}(\kappa\bm{\Phi}_{t})\right\rVert_{{\bm{V}}_{t}^{-1}}^{2}\right\} ( \kappa\leq L_{\mu} ) \displaystyle\leq\frac{2d^{2}L_{\mu}^{2}}{\kappa^{2}}\log\left(1+\frac{4\kappa^{2}S^{2}T}{d^{2}\lambda}\right). ∎ E.2 Connection to the Standard Eluder Dimensions In this appendix, we will elucidate the connection between Definition E.1 and two other “standard” definitions of eluder-type complexities: sequential extrapolation coefficient (SEC) ( 134 ) and the original eluder dimension ( 104 ) For simplicity, we denote {\mathcal{Z}}:={\mathcal{X}}\times{\mathcal{A}}\times{\mathcal{A}} , and P({\bm{z}}):=P({\bm{a}}^{1}\succ{\bm{a}}^{2}\mid{\bm{x}}) for {\bm{z}}=({\bm{x}},{\bm{a}}^{1},{\bm{a}}^{2}) . First, we recall the definition of SEC adopted for our setting: Definition E.3 ( \lambda -regularized SEC, Definition 7 of 134 ) . Let \Pi\subseteq\Delta({\mathcal{Z}}) be a distribution class. Then, the SEC is defined as \mathrm{SEC}_{\lambda}({\mathcal{P}},\Pi,T):=\sup_{P_{1:T}^{1},P_{1:T}^{2}\subseteq{\mathcal{P}}}\ \sup_{\nu_{1:T}\subseteq\Pi}\sum_{t=1}^{T}\frac{\left(\mathbb{E}_{{\bm{z}}_{t}\sim\nu_{t}}[P_{t}^{1}({\bm{z}}_{t})-P_{t}^{2}({\bm{z}}_{t})]\right)^{2}}{\lambda+\sum_{s=1}^{t-1}\mathbb{E}_{{\bm{z}}_{s}\sim\nu_{s}}\big[(P_{t}^{1}({\bm{z}}_{s})-P_{t}^{2}({\bm{z}}_{s}))^{2}\big]}. Note that when the distribution class is restricted to the set of Dirac measures {\bm{D}}:=\{\delta_{{\bm{z}}}:{\bm{z}}\in Z\} , we have the following relationship between SEC and Definition E.1 : \displaystyle d({\mathcal{P}},\lambda,T) \displaystyle=\sup_{{\bm{z}}_{1:T}}\sum_{t\in[T]}\min\left\{1,\sup_{P_{1},P_{2}\in\mathcal{P}}\frac{(P_{1}({\bm{z}}_{t})-P_{2}({\bm{z}}_{t}))^{2}}{\lambda+\sum_{s=1}^{t-1}(P_{1}({\bm{z}}_{s})-P_{2}({\bm{z}}_{s}))^{2}}\right\} \displaystyle\leq\sup_{{\bm{z}}_{1:T}}\sum_{t\in[T]}\sup_{P_{1},P_{2}\in\mathcal{P}}\frac{(P_{1}({\bm{z}}_{t})-P_{2}({\bm{z}}_{t}))^{2}}{\lambda+\sum_{s=1}^{t-1}(P_{1}({\bm{z}}_{s})-P_{2}({\bm{z}}_{s}))^{2}} \displaystyle=\sup_{P_{1:T}^{1},P_{1:T}^{2}}\sup_{{\bm{z}}_{1:T}}\sum_{t\in[T]}\frac{(P_{t}^{1}({\bm{z}}_{t})-P_{t}^{2}({\bm{z}}_{t}))^{2}}{\lambda+\sum_{s=1}^{t-1}(P_{s}^{1}({\bm{z}}_{s})-P_{s}^{2}({\bm{z}}_{s}))^{2}} \displaystyle=\sup_{P_{1:T}^{1},P_{1:T}^{2}}\sup_{\nu_{1:T}\subseteq{\bm{D}}}\sum_{t\in[T]}\frac{(\mathbb{E}_{{\bm{z}}_{t}\sim\nu_{t}}[P_{t}^{1}({\bm{z}}_{t})-P_{t}^{2}({\bm{z}}_{t})])^{2}}{\lambda+\sum_{s=1}^{t-1}(\mathbb{E}_{{\bm{z}}_{s}\sim\nu_{s}}[P_{t}^{1}({\bm{z}}_{s})-P_{t}^{2}({\bm{z}}_{s})])^{2}} \displaystyle=\mathrm{SEC}_{\lambda}({\mathcal{P}},{\bm{D}},T). Second, we recall the standard eluder dimension of 41 and 73 : 10 10 10 The original definition is due to 104 and slightly different, but as mentioned in 73 , the “new” definition is “never larger and is sufficient to analyze all the applications of eluder dimension in literature.” Definition E.4 (Definition 1 of 73 ) . For any fixed preference P^{*}\in{\mathcal{P}} , and scale \varepsilon\geq 0 , the exact eluder dimension \underline{\mathrm{Edim}}_{P^{*}}({\mathcal{P}},\varepsilon) is the largest m\in{\mathbb{N}} such that there exists a sequence \{({\bm{z}}_{t},P_{t})\}_{t\in[m]}\subset{\mathcal{Z}}\times{\mathcal{P}} such that the following holds: for all t\in[m] , \left|P_{t}({\bm{z}}_{t})-P^{*}({\bm{z}}_{t})\right|>\varepsilon,\quad\text{and}\quad\sum_{s0 , we define: • The eluder dimension is \mathrm{Edim}_{P^{*}}({\mathcal{P}},\varepsilon):=\sup_{\varepsilon^{\prime}\geq\varepsilon}\underline{\mathrm{Edim}}_{P^{*}}({\mathcal{P}},\varepsilon^{\prime}) . • \underline{\mathrm{Edim}}({\mathcal{P}},\varepsilon):=\sup_{P^{*}\in{\mathcal{P}}}\underline{\mathrm{Edim}}_{P^{*}}({\mathcal{P}},\varepsilon^{\prime}) and \mathrm{Edim}({\mathcal{P}},\varepsilon):=\sup_{P^{*}\in{\mathcal{P}}}\mathrm{Edim}_{P^{*}}({\mathcal{P}},\varepsilon^{\prime}) . We first prove that \mathrm{Edim}({\mathcal{P}},\varepsilon) and \mathrm{SEC}_{\lambda}({\mathcal{P}},{\bm{D}},T) are equivalent up to some constants and logarithmic factors: Proposition E.5 . Suppose that {\mathcal{Z}}\subseteq{\mathcal{B}}^{d}(1) and \Theta\subseteq\mathrm{Skew}(d;2r,S) for some S>0 . Let \varepsilon>0 , T\geq\mathrm{Edim}({\mathcal{P}},\varepsilon) , and \lambda\geq 1 . Then, \frac{\varepsilon^{2}\mathrm{Edim}({\mathcal{P}},\varepsilon)}{\lambda+\varepsilon^{2}}\leq\mathrm{SEC}_{\lambda}({\mathcal{P}},{\bm{D}},T)\lesssim\mathrm{Edim}({\mathcal{P}},T^{-1/2})\log T. (38) Proof. We prove each direction separately. Upper Bound. Noting that for \lambda\geq 1 , \mathrm{SEC}_{\lambda}({\mathcal{P}},{\bm{D}},T)\leq\mathrm{SEC}_{1}({\mathcal{P}},{\bm{D}},T) , this immediately follows from 134 with {\mathcal{D}}={\bm{D}} . Lower Bound. Consider the eluder witness, i.e., a sequence of \{({\bm{z}}_{t},P_{t})\}_{t\in{d_{e}}} and some fixed preference P^{*} that attains the eluder dimension d_{e}:=\mathrm{Edim}({\mathcal{P}},\varepsilon) . Then, by definition, \displaystyle\mathrm{SEC}_{\lambda}({\mathcal{P}},{\bm{D}},T) \displaystyle=\sup_{P_{1:T}^{1},P_{1:T}^{2}\subseteq{\mathcal{P}}}\ \sup_{{\bm{z}}_{1:T}\subseteq{\mathcal{Z}}}\sum_{t=1}^{T}\frac{\left(P_{t}^{1}({\bm{z}}_{t})-P_{t}^{2}({\bm{z}}_{t})\right)^{2}}{\lambda+\sum_{s=1}^{t-1}(P_{t}^{1}({\bm{z}}_{s})-P_{t}^{2}({\bm{z}}_{s}))^{2}} \displaystyle\geq\sup_{P_{1:T}^{1}\subseteq{\mathcal{P}}}\ \sup_{{\bm{z}}_{1:T}\subseteq{\mathcal{Z}}}\sum_{t=1}^{T}\frac{\left(P_{t}^{1}({\bm{z}}_{t})-P^{*}({\bm{z}}_{t})\right)^{2}}{\lambda+\sum_{s=1}^{t-1}(P_{t}^{1}({\bm{z}}_{s})-P^{*}({\bm{z}}_{s}))^{2}} (Set P_{t}^{2}=P^{*} for all t\in[T] ) \displaystyle\geq\sum_{t=1}^{d_{e}}\frac{\left(P_{t}({\bm{z}}_{t})-P^{*}({\bm{z}}_{t})\right)^{2}}{\lambda+\sum_{s=1}^{t-1}(P_{t}({\bm{z}}_{s})-P^{*}({\bm{z}}_{s}))^{2}} (Set {\bm{z}}_{1:T} and P^{1}_{1:T} to be the eluder witness sequence) \displaystyle>\sum_{t=1}^{d_{e}}\frac{\varepsilon^{2}}{\lambda+\varepsilon^{2}}=\frac{d_{e}\varepsilon^{2}}{\lambda+\varepsilon^{2}}. ∎ We conclude with a nearly-tight characterization of the eluder dimension of GBPM, whose proof is deferred to the next subsection: Proposition E.6 . Let {\mathcal{X}}\subseteq{\mathcal{B}}^{d}(1) and \Theta\subseteq\mathrm{Skew}(d,2r;S) for some S>0 . Define the function class as the GBPM : {\mathcal{P}}:=\left\{({\bm{x}},{\bm{y}})\mapsto\mu\left({\bm{x}}^{\top}\bm{\Theta}{\bm{y}}\right):\bm{\Theta}\in\Theta\right\}, (39) where we have the following properties: \kappa\leq\dot{\mu}({\bm{x}}^{\top}\bm{\Theta}{\bm{y}})\leq L_{\mu} and \left|{\bm{x}}^{\top}\bm{\Theta}{\bm{y}}\right|\leq S 11 11 11 This follows from matrix Hölder inequality: \left|{\bm{x}}^{\top}\bm{\Theta}{\bm{y}}\right|=\left|\langle\bm{\Theta},{\bm{x}}{\bm{y}}^{\top}\rangle\right|\leq\left\lVert\bm{\Theta}\right\rVert_{\mathrm{nuc}}\left\lVert{\bm{x}}{\bm{y}}^{\top}\right\rVert_{\mathrm{op}}\leq S . for all ({\bm{x}},{\bm{y}},\bm{\Theta})\in{\mathcal{X}}\times{\mathcal{X}}\times\Theta . Then, its eluder dimension is bounded as follows: for any \varepsilon0 , denoted as \mu\text{-}\mathrm{rk}({\mathcal{P}},R) , is the smallest dimension d\in{\mathbb{N}} for which there exist R_{\phi},R_{w}>0 with R_{\phi}R_{w}=R , and (global) mappings \phi:{\mathcal{X}}\times{\mathcal{X}}\rightarrow{\mathcal{B}}^{d}(R_{\phi}) and w:{\mathcal{P}}\rightarrow{\mathcal{B}}^{d}(R_{w}) such that P({\bm{x}}\succ{\bm{y}})=\mu\left(\langle\phi({\bm{x}},{\bm{y}}),w(P)\rangle\right),\quad\forall({\bm{x}},{\bm{y}},P)\in{\mathcal{X}}\times{\mathcal{X}}\times{\mathcal{P}}, (42) or \infty if no such d exists. Proposition E.8 (Proposition 4(ii) of 73 ) . For all \varepsilon\varepsilon, and \sum_{s0 , there exists an \varepsilon -net \Theta_{\varepsilon} of \Theta(d,2r;S) w.r.t. \left\lVert\cdot\right\rVert_{F} with |\Theta_{\varepsilon}|\leq\left(\frac{9S}{\varepsilon}\right)^{2(2d+1)r}. Putting the bounds together, we have: {\mathbb{P}}\left(\sum_{i=1}^{t}(P_{\widehat{\bm{\Theta}}_{t}}({\bm{z}}_{i})-P_{\bm{\Theta}_{\star}}({\bm{z}}_{i}))^{2}\lesssim\log\frac{1}{\delta}+Lt\varepsilon+Lt\varepsilon^{2}+dr\log\frac{S}{\varepsilon}\right)\geq 1-\delta. Choosing \varepsilon\approx\frac{1}{(Lt)^{2}} , {\mathbb{P}}\left(\sum_{i=1}^{t}(P_{\widehat{\bm{\Theta}}_{t}}({\bm{z}}_{i})-P_{\bm{\Theta}_{\star}}({\bm{z}}_{i}))^{2}\lesssim\log\frac{1}{\delta}+dr\log(LSt)\right)\geq 1-\delta. Setting \delta=\delta/T and taking the union bound over t , we have: {\mathbb{P}}\left(\forall t\in[T],\,\sum_{i=1}^{t}(P_{\widehat{\bm{\Theta}}_{t}}({\bm{z}}_{i})-P_{\bm{\Theta}_{\star}}({\bm{z}}_{i}))^{2}\lesssim\log\frac{T}{\delta}+dr\log(LST)\right)\geq 1-\delta. which concludes the proof. ∎ F.3 Proof of Lemma F.6 The proof closely follows that of 139 and 129 . For the function P_{\bm{\Theta}} defined by the fixed \bm{\Theta}\in\Theta , we first upper bound its logarithmic moment generating function as \displaystyle\log\mathbb{E}\exp\!\left(\sum_{i=1}^{t}\log\frac{P_{\bm{\Theta}}(r_{i}\mid{\bm{z}}_{i})}{P_{\bm{\Theta}_{\star}}(r_{i}\mid{\bm{z}}_{i})}\right) \displaystyle=\log\mathbb{E}\exp\!\Biggl(\sum_{i=1}^{t-1}\log\frac{P_{\bm{\Theta}}(r_{i}\mid{\bm{z}}_{i})}{P_{\bm{\Theta}_{\star}}(r_{i}\mid{\bm{z}}_{i})}+\log\Bigl(2\,\mathbb{E}_{r_{t}\mid{\bm{z}}_{t}}\sqrt{\frac{P_{\bm{\Theta}}(r_{t}\mid{\bm{z}}_{t})}{P_{\bm{\Theta}_{\star}}(r_{t}\mid{\bm{z}}_{t})}}\Bigr)\Biggr) \displaystyle=\log\mathbb{E}\exp\!\Biggl(\sum_{i=1}^{t-1}\log\frac{P_{\bm{\Theta}}(r_{i}\mid{\bm{z}}_{i})}{P_{\bm{\Theta}}(r_{i}\mid{\bm{z}}_{i})}+\log\Bigl(1-H\,\bigl(P_{\bm{\Theta}}(r_{t}\mid{\bm{z}}_{t})\,\|\,P_{\bm{\Theta}_{\star}}(r_{t}\mid{\bm{z}}_{t})\bigr)^{2}\Bigr)\Biggr) \displaystyle\leq\log\mathbb{E}\exp\!\Biggl(\sum_{i=1}^{t-1}\log\frac{P_{\bm{\Theta}}(r_{i}\mid{\bm{z}}_{i})}{P_{\bm{\Theta}_{\star}}(r_{i}\mid{\bm{z}}_{i})}-H\,\bigl(P_{\bm{\Theta}}(r_{t}\mid{\bm{z}}_{t})\,\|\,P_{\bm{\Theta}_{\star}}(r_{t}\mid{\bm{z}}_{t})\bigr)^{2}\Biggr) \displaystyle\leq\cdots\leq-\sum_{i=1}^{t}H\,\bigl(P_{\bm{\Theta}}(r_{i}\mid{\bm{z}}_{i})\,\|\,P_{\bm{\Theta}_{\star}}(r_{i}\mid{\bm{z}}_{i})\bigr)^{2}, where H(P\|Q)^{2} is the squared Hellinger distance between probability measures P and Q on \Omega , defined as H(P\|Q)^{2}:=\int_{\Omega}\left(\sqrt{p(z)}-\sqrt{q(z)}\right)^{2}\,d\mu(z), with p and q denoting their respective densities with respect to a base measure \mu . We continue to lower-bound the Hellinger distance by \displaystyle\sum_{i=1}^{t}\Bigl(H\,\bigl(P_{\bm{\Theta}}(r_{i}\mid{\bm{z}}_{i})\,\|\,P_{\bm{\Theta}_{\star}}(r_{i}\mid{\bm{z}}_{i})\bigr)\Bigr)^{2} \displaystyle\geq\sum_{i=1}^{t}\Bigl(\mathrm{TV}\,\bigl(P_{\bm{\Theta}}(r_{i}\mid{\bm{z}}_{i})\,\|\,P_{\bm{\Theta}_{\star}}(r_{i}\mid{\bm{z}}_{i})\bigr)\Bigr)^{2} \displaystyle=\sum_{i=1}^{t}\Bigl(P_{\bm{\Theta}}({\bm{z}}_{i})-P_{\bm{\Theta}_{\star}}({\bm{z}}_{i})\Bigr)^{2}, where the inequality uses the fact that for any distribution p,q , H(p,q)\geq\mathrm{TV}(p,q) ( 144 , Theorem B.9) . Then, by Lemma G.1 , we obtain for each {\bm{\Theta}}\in\Theta , with probability at least 1-\delta , \displaystyle\sum_{i=1}^{t}\log\frac{P_{\bm{\Theta}}(r_{i}\mid{\bm{z}}_{i})}{P_{\bm{\Theta}_{\star}}(r_{i}\mid{\bm{z}}_{i})} \displaystyle\leq\log\!\left(\frac{1}{\delta}\right)+\log\mathbb{E}\exp\!\left(\sum_{i=1}^{t}\log\frac{P_{\bm{\Theta}}(r_{i}\mid{\bm{z}}_{i})}{P_{\bm{\Theta}_{\star}}(r_{i}\mid{\bm{z}}_{i})}\right) \displaystyle\leq-\sum_{i=1}^{t}H\!\bigl(P_{\bm{\Theta}}(r_{i}\mid{\bm{z}}_{i})\,\|\,P_{\bm{\Theta}_{\star}}(r_{i}\mid{\bm{z}}_{i})\bigr)^{2}+\log\!\left(\frac{1}{\delta}\right) \displaystyle\leq-\sum_{i=1}^{t}\Bigl(P_{\bm{\Theta}}({\bm{z}}_{i})-P_{\bm{\Theta}_{\star}}({\bm{z}}_{i})\Bigr)^{2}+\log\!\left(\frac{1}{\delta}\right). Appendix G Auxiliary Lemmas Lemma G.1 (Martingale Exponential Inequalities; Theorem 13.2 of 144 ) . Consider a sequence of random functions \xi_{1}(\mathcal{Z}_{1}),\ldots,\xi_{t}(\mathcal{Z}_{t}),\ldots with respect to filtration \{\mathcal{F}_{t}\} . We have for any \delta\in(0,1) and \lambda>0 : \mathbb{P}\left(\exists n>0:-\sum_{i=1}^{n}\xi_{i}\geq\frac{\log(1/\delta)}{\lambda}+\frac{1}{\lambda}\sum_{i=1}^{n}\log\mathbb{E}_{Z_{i}^{(y)}}\exp(-\lambda\xi_{i})\right)\leq\delta, where Z_{t}=(Z_{t}^{(x)},Z_{t}^{(y)}) and \mathcal{Z}_{t}=(Z_{1},\ldots,Z_{t}) . Lemma G.2 (Multiplicative Chernoff Bounds; Corollary 2.18 of 144 ) . Assume that X\in[0,1] with \mathbb{E}X=\mu . Then for all \epsilon>0 , \displaystyle\mathbb{P}\left(\bar{X}_{n}\geq(1+\epsilon)\mu\right) \displaystyle\leq\exp\left[\frac{-2n\mu\epsilon^{2}}{2+\epsilon}\right] \displaystyle\mathbb{P}\left(\bar{X}_{n}\leq(1-\epsilon)\mu\right) \displaystyle\leq\exp\left[\frac{-2n\mu\epsilon^{2}}{2}\right]. Moreover, for t>0 , we have \mathbb{P}\left(\bar{X}_{n}\geq\mu+\sqrt{\frac{2\mu t}{n}}+\frac{t}{3n}\right)\leq\exp(-t). Lemma G.3 (Elliptical Potential Lemma; Lemma 11 of 1 ) . Let {\bm{x}}_{1},\cdots,{\bm{x}}_{T}\in{\mathcal{B}}^{d}(X) be a sequence of vectors and {\bm{V}}_{t}:=\lambda{\bm{I}}+\sum_{s=1}^{t-1}{\bm{x}}_{s}{\bm{x}}_{s}^{\intercal} . Then, we have \sum_{t=1}^{T}\min\left\{1,\lVert{\bm{x}}_{t}\rVert^{2}_{{\bm{V}}_{t}^{-1}}\right\}\leq 2d\log\left(1+\frac{X^{2}T}{d\lambda}\right). Appendix H Future Directions Relaxing the Feature Diversity Assumption. Our current regret bounds rely on the feature diversity assumption ( 1 ), characterized by the minimum eigenvalue C_{\min} . While this assumption is standard in the contextual bandits literature that involves either greedy sampling (e.g., algorithms without sophisticated exploration strategies) or high dimensions, it may still be restrictive for general RLHF applications. Recent works have investigated minimal assumptions required for greedy strategies, such as the local anti-concentration (LAC) property proposed by 66 . Investigating the impact of such relaxed conditions on online RLHF with GBPM (e.g., whether we can still obtain {\color[rgb]{0.75,0,0.25}e^{{\mathcal{O}}(\eta)}} -free polylogarithmic regret with GS ) remains an important open question. Instance-Specific Guarantees for Unregularized Regret. While our work establishes \tilde{{\mathcal{O}}}(\sqrt{T}) guarantees for unregularized regret (via Theorem 4.2 ), these bounds reflect worst-case hardness. For instance, 53 demonstrated that in tabular games with bandit feedback, the Nash regret for the Tsallis-INF algorithm ( 118 ; 3 ; 154 ) scales with the “sparsity” or “entropy” of the NE set, potentially achieving logarithmic regret {\mathcal{O}}(\log T) when the NE is unique and deterministic (a pure strategy), and even rates of the form {\mathcal{O}}(T^{c}) for some c\in(0,1) , depending on the geometry of the set of Nash Equilibria. Adapting such instance-dependent guarantees to the contextual GBPM setting is non-trivial, even when the link function \mu is linear. Recent advances in “Best-of-Both-Worlds” algorithms for linear contextual bandits ( 67 ; 64 ) may provide a promising starting point. Computationally Efficient Algorithms. Our current theoretical framework assumes access to a computational oracle for finding the NE ( 3 ), which may be computationally expensive in practice. Developing efficient variants of our algorithms is a practical priority. Promising approaches include leveraging online estimation techniques such as Online Mirror Descent (OMD) ( 146 ) , minimax optimization techniques such as optimistic OMD ( 100 ; 115 ; 147 ) , or reductions to offline/online regression oracles ( 42 ) .