When Greedy Sampling Explores: KL-Regularized Contextual Bandits without Eluder-Dimension Dependence

# When Greedy Sampling Explores: KL-Regularized Contextual Bandits without Eluder-Dimension Dependence
Source: [https://arxiv.org/html/2609.13564](https://arxiv.org/html/2609.13564)
Haoyang HongAffiliation:School of Electrical Engineering and Computer Science, Oregon State UniversityHuazheng WangAffiliation:School of Electrical Engineering and Computer Science, Oregon State University

###### Abstract

We study KL\-regularized contextual bandits under both reward and preference feedback\. We show that greedy sampling can achieve logarithmic regret without explicit dependence on the eluder dimension\. For reward feedback, we establish an eluder\-dimension\-independent regret bound for a simple greedy algorithm that directly samples from the Gibbs policy induced by the estimated reward\. We further extend this result to preference feedback under both the general preference and Bradley–Terry models, while also sharpening existing dimension\-dependent guarantees\. Our analysis reveals a trade\-off between greedy sampling and upper confidence bound\-style exploration: greedy sampling enjoys stronger guarantees when KL regularization is sufficiently strong, whereas additional exploration becomes preferable as the regularization weakens\.

## 1Introduction

KL regularization has become a central ingredient in modern sequential decision\-making, appearing in both contextual bandits\([Zhao et al\., 2025b](https://arxiv.org/html/2609.13564#bib.bib2);[Zhao et al\., 2025a](https://arxiv.org/html/2609.13564#bib.bib4);[Ji et al\., 2026b](https://arxiv.org/html/2609.13564#bib.bib17);[Ji et al\., 2026a](https://arxiv.org/html/2609.13564#bib.bib20)\)and reinforcement learning \(RL\) from human feedback\([Christiano et al\., 2017](https://arxiv.org/html/2609.13564#bib.bib13);[Ouyang et al\., 2022](https://arxiv.org/html/2609.13564#bib.bib14);[Xiong et al\., 2024](https://arxiv.org/html/2609.13564#bib.bib16);[Ye et al\., 2024](https://arxiv.org/html/2609.13564#bib.bib7);[Munos et al\., 2024](https://arxiv.org/html/2609.13564#bib.bib6)\)\. By penalizing deviations from a reference policy, KL regularization encourages the learned policy to remain close to the reference policy rather than becoming overly concentrated on currently preferred actions\.

Recent work has studied two complementary approaches to exploration in KL\-regularized contextual bandits\. For KL\-regularized contextual bandits with reward feedback \(RF\),[Zhao et al\. \(2025b\)](https://arxiv.org/html/2609.13564#bib.bib2)use an upper confidence bound \(UCB\)\-style algorithm to achieve logarithmic regret\. More recently,[Wu et al\. \(2025\)](https://arxiv.org/html/2609.13564#bib.bib8)show that KL regularization can provide sufficient implicit exploration for greedy sampling to achieve provable guarantees under preference feedback \(PF\)\. Their guarantees, however, still retain explicit dependence on the corresponding eluder dimension\([Russo and Van Roy, 2013](https://arxiv.org/html/2609.13564#bib.bib9);[Osband and Van Roy, 2014](https://arxiv.org/html/2609.13564#bib.bib22);[Zhang, 2023](https://arxiv.org/html/2609.13564#bib.bib1)\), which can be large for rich function classes\. This raises a sharper question:

> *Can greedy sampling achieve strong regret guarantees in KL\-regularized contextual bandits without explicit dependence on the eluder dimension?*

In this paper, we show that greedy sampling achieves polylogarithmic regret without explicit eluder\-dimension dependence under reward feedback and PF with both the general preference \(GP\) and Bradley–Terry \(BT\) models\. We further characterize its trade\-off with UCB\-style exploration, revealing that, unlike in standard contextual bandits where one may seek a uniformly optimal exploration strategy, the preferred algorithm under KL regularization can depend on the regularization regime\. The main contributions are summarized as follows\.

- •We first establish an eluder\-dimension\-independent polylogarithmic regret guarantee for greedy sampling in KL\-regularized contextual bandits with RF, and extend this result to PF under both the GP and BT models\.
- •For PF, we develop UCB\-style algorithms and establish dimension\-dependent regret guarantees, providing UCB counterparts to our greedy sampling algorithms\.
- •By comparing the greedy and UCB\-style guarantees, we characterize a trade\-off governed by the strength of KL regularization: greedy sampling is preferable under sufficiently strong regularization, whereas explicit optimism becomes advantageous as the regularization weakens\.

The remainder of the paper is organized as follows\. Section[2](https://arxiv.org/html/2609.13564#S2)reviews the most relevant literature\. Section[3](https://arxiv.org/html/2609.13564#S3)introduces the basic settings for contextual bandits with RF, as well as PF under the GP and BT models\. Section[4](https://arxiv.org/html/2609.13564#S4)studies KL\-regularized contextual bandits with RF, establishes our eluder\-dimension\-independent regret guarantee for greedy sampling, and discusses the trade\-off between greedy sampling and UCB\-style exploration\. Section[5](https://arxiv.org/html/2609.13564#S5)extends the analysis of greedy sampling to PF under both the GP and BT models, and develops the corresponding UCB\-style algorithms and regret guarantees\. Section[6](https://arxiv.org/html/2609.13564#S6)presents numerical experiments illustrating the trade\-off between greedy sampling and UCB\-style exploration\.

## 2Related Work

##### Contextual Bandits\.

The contextual bandit literature can be broadly divided into two lines\. The first studies structured or parametric models, where the expected reward is assumed to obey a known low\-dimensional structure\. A prominent example is the linear contextual bandit, in which rewards are linear in context–action features\([Li et al\., 2010](https://arxiv.org/html/2609.13564#bib.bib23);[Chu et al\., 2011](https://arxiv.org/html/2609.13564#bib.bib24);[Abbasi\-Yadkori et al\., 2011](https://arxiv.org/html/2609.13564#bib.bib25);[Agrawal and Goyal, 2013](https://arxiv.org/html/2609.13564#bib.bib26)\)\. This line has also been extended beyond linear models, including generalized linear models\([Filippi et al\., 2010](https://arxiv.org/html/2609.13564#bib.bib27)\), kernelized models\([Valko et al\., 2013](https://arxiv.org/html/2609.13564#bib.bib28)\), and neural network models\([Zhou et al\., 2020](https://arxiv.org/html/2609.13564#bib.bib29);[Zhang et al\., 2021](https://arxiv.org/html/2609.13564#bib.bib30)\)\. These approaches exploit the prescribed parametric structure to construct confidence sets and balance exploration and exploitation\.

A second line considers contextual bandits with more general function classes, without restricting the reward model to a particular form\. Early work studied generic hypothesis and policy classes through exploration\-based algorithms\([Langford and Zhang, 2007](https://arxiv.org/html/2609.13564#bib.bib10);[Agarwal et al\., 2014](https://arxiv.org/html/2609.13564#bib.bib11)\)\. Subsequent work developed regression\-oracle\-based methods that accommodate rich, potentially nonparametric function classes\([Foster et al\., 2018](https://arxiv.org/html/2609.13564#bib.bib31);[Foster and Rakhlin, 2020](https://arxiv.org/html/2609.13564#bib.bib12);[Simchi\-Levi and Xu, 2022](https://arxiv.org/html/2609.13564#bib.bib32)\)\. For such general function approximation settings, regret guarantees are often characterized through complexity measures of the function class, such as the eluder dimension\([Russo and Van Roy, 2013](https://arxiv.org/html/2609.13564#bib.bib9);[Osband and Van Roy, 2014](https://arxiv.org/html/2609.13564#bib.bib22)\)\. Our work follows this latter line\.

##### KL\-Regularized Bandits and RL\.

Regularization has been extensively studied in reinforcement learning as a mechanism for controlling policy updates and improving optimization and exploration properties\([Geist et al\., 2019](https://arxiv.org/html/2609.13564#bib.bib33);[Cen et al\., 2022](https://arxiv.org/html/2609.13564#bib.bib34);[Zhan et al\., 2023](https://arxiv.org/html/2609.13564#bib.bib35)\)\. KL regularization, in particular, has become a central component of modern RL and reinforcement learning from human feedback \(RLHF\), where it constrains the learned policy to remain close to a reference policy\([Ouyang et al\., 2022](https://arxiv.org/html/2609.13564#bib.bib14);[Rafailov et al\., 2023](https://arxiv.org/html/2609.13564#bib.bib15)\)\. This practical importance has motivated a growing theoretical literature on KL\-regularized MABs\([Ji et al\., 2026b](https://arxiv.org/html/2609.13564#bib.bib17);[Ji et al\., 2026a](https://arxiv.org/html/2609.13564#bib.bib20)\), contextual bandits and reinforcement learning\([Zhao et al\., 2025b](https://arxiv.org/html/2609.13564#bib.bib2);[Zhao et al\., 2026a](https://arxiv.org/html/2609.13564#bib.bib19);[Zhao et al\., 2026b](https://arxiv.org/html/2609.13564#bib.bib18);[Hong et al\., 2026](https://arxiv.org/html/2609.13564#bib.bib21)\), and RLHF \(human/preference feedback\)\([Xiong et al\., 2024](https://arxiv.org/html/2609.13564#bib.bib16);[Xie et al\., 2025](https://arxiv.org/html/2609.13564#bib.bib36);[Zhao et al\., 2025a](https://arxiv.org/html/2609.13564#bib.bib4);[Wu et al\., 2025](https://arxiv.org/html/2609.13564#bib.bib8);[Wu et al\., 2026](https://arxiv.org/html/2609.13564#bib.bib37)\)\. In particular,[Zhao et al\. \(2025b\)](https://arxiv.org/html/2609.13564#bib.bib2)obtain eluder\-dimension\-dependent logarithmic regret for KL\-regularized contextual bandits with RF using UCB\-style exploration, while[Wu et al\. \(2025\)](https://arxiv.org/html/2609.13564#bib.bib8)establish similar guarantees for greedy sampling under PF\. Our work complements these results by establishing eluder\-dimension\-independent logarithmic regret guarantees for greedy sampling\.

## 3Preliminaries

### 3\.1Notation

For any positive integernn, define\[n\]:=\{1,…,n\}\[n\]:=\\\{1,\\ldots,n\\\}\. For a finite function classℱ\\mathcal\{F\}, letNℱ:=\|ℱ\|N\_\{\\mathcal\{F\}\}:=\|\\mathcal\{F\}\|denote its cardinality\. We useO⁡\(⋅\)O\(\\cdot\)andO~​\(⋅\)\\widetilde\{O\}\(\\cdot\)for the standard asymptotic notation, whereO~​\(⋅\)\\widetilde\{O\}\(\\cdot\)suppresses logarithmic factors\.

### 3\.2KL\-Regularized Contextual Bandits with Reward Feedback

In this section, we introduce the KL\-regularized contextual bandit problem with RF\. Consider a contextual bandit problem with horizonTT\. At each roundt∈\[T\]t\\in\[T\], a contextxt∈𝒳x\_\{t\}\\in\\mathcal\{X\}is independently drawn from an unknown distributionddover𝒳\\mathcal\{X\}\. After observingxtx\_\{t\}, the learner selects an actionat∼πt\(⋅∣xt\)a\_\{t\}\\sim\\pi\_\{t\}\(\\cdot\\mid x\_\{t\}\)from an action space𝒜\\mathcal\{A\}, where\|𝒜\|=K<∞\|\\mathcal\{A\}\|=K<\\infty\. Conditioned on\(xt,at\)\(x\_\{t\},a\_\{t\}\), the learner observes a random rewardrt∈\[0,1\]r\_\{t\}\\in\[0,1\]that is independent of the past and satisfies𝔼\[rt∣xt,at\]=R⋆\(xt,at\)\\mathbb\{E\}\[r\_\{t\}\\mid x\_\{t\},a\_\{t\}\]=R^\{\\star\}\(x\_\{t\},a\_\{t\}\), whereR⋆:𝒳×𝒜→\[0,1\]R^\{\\star\}:\\mathcal\{X\}\\times\\mathcal\{A\}\\to\[0,1\]is the unknown expected reward function\. The learner has access to a finite candidate reward function classℛ\\mathcal\{R\}consisting of functionsR:𝒳×𝒜→\[0,1\]R:\\mathcal\{X\}\\times\\mathcal\{A\}\\to\[0,1\]\. We make the following standard realizability assumption\.

###### Assumption 1\(Reward Realizability\)\.

The true expected reward function satisfiesR⋆∈ℛR^\{\\star\}\\in\\mathcal\{R\}\.

For simplicity, we focus on a finite reward function classℛ\\mathcal\{R\}; the analysis extends to infinite function classes via standard covering\-number arguments\([Russo and Van Roy, 2013](https://arxiv.org/html/2609.13564#bib.bib9);[Xu and Zeevi, 2024](https://arxiv.org/html/2609.13564#bib.bib3);[Zhang, 2023](https://arxiv.org/html/2609.13564#bib.bib1)\)\.

##### Learning objective\.

We assume that the reference policyπref\\pi\_\{\\rm ref\}has full support over𝒜\\mathcal\{A\}, i\.e\.,πref​\(a∣x\)\>0\\pi\_\{\\rm ref\}\(a\\mid x\)\>0for all\(x,a\)∈𝒳×𝒜\(x,a\)\\in\\mathcal\{X\}\\times\\mathcal\{A\}\. For two policiesπ\\piandπref\\pi\_\{\\mathrm\{ref\}\}, define their conditional KL divergence at contextxxas

KL⁡\(π,πref∣x\):=𝔼a∼π​\[log⁡π⁡\(a∣x\)πref​\(a∣x\)\]\.\\mathrm\{KL\}\(\\pi,\\pi\_\{\\mathrm\{ref\}\}\\mid x\):=\\mathbb\{E\}\_\{a\\sim\\pi\}\\left\[\\log\\frac\{\\pi\(a\\mid x\)\}\{\\pi\_\{\\mathrm\{ref\}\}\(a\\mid x\)\}\\right\]\.Given a reference policyπref\\pi\_\{\\mathrm\{ref\}\}and a parameterη\>0\\eta\>0, the KL\-regularized value of a policyπ\\piis defined as

JRF​\(π\)\\displaystyle J\_\{\\mathrm\{RF\}\}\(\\pi\):=𝔼x∼d​𝔼a∼π​\[R⋆​\(x,a\)−η−1​KL​\(π,πref∣x\)\]\\displaystyle:=\\mathbb\{E\}\_\{x\\sim d\}\\mathbb\{E\}\_\{a\\sim\\pi\}\\left\[R^\{\\star\}\(x,a\)\-\\eta^\{\-1\}\\mathrm\{KL\}\(\\pi,\\pi\_\{\\mathrm\{ref\}\}\\mid x\)\\right\]=𝔼x∼d​𝔼a∼π​\[R⋆​\(x,a\)−η−1​log⁡π⁡\(a∣x\)πref​\(a∣x\)\]\.\\displaystyle=\\mathbb\{E\}\_\{x\\sim d\}\\mathbb\{E\}\_\{a\\sim\\pi\}\\left\[R^\{\\star\}\(x,a\)\-\\eta^\{\-1\}\\log\\frac\{\\pi\(a\\mid x\)\}\{\\pi\_\{\\mathrm\{ref\}\}\(a\\mid x\)\}\\right\]\.\(1\)Here,η\>0\\eta\>0controls the strength of the KL regularization\. In particular, a smallerη\\etacorresponds to stronger regularization towardπref\\pi\_\{\\mathrm\{ref\}\}, whereas a largerη\\etaallows the learned policy to deviate more substantially from the reference policy\.

Letπ⋆:=arg⁡maxπ​JRF​\(π\)\\pi^\{\\star\}:=\\arg\\max\_\{\\pi\}J\_\{\\mathrm\{RF\}\}\(\\pi\)denote the unique optimal policy for the KL\-regularized objective\. Our goal is to design a sequence of policies\{πt\}t=1T\\\{\\pi\_\{t\}\\\}\_\{t=1\}^\{T\}that minimizes the cumulative regret

RegRF⁡\(T\):=∑t=1T\(JRF​\(π⋆\)−JRF​\(πt\)\)\.\\operatorname\{Reg\}\_\{\\mathrm\{RF\}\}\(T\):=\\sum\_\{t=1\}^\{T\}\\left\(J\_\{\\mathrm\{RF\}\}\(\\pi^\{\\star\}\)\-J\_\{\\mathrm\{RF\}\}\(\\pi\_\{t\}\)\\right\)\.\(2\)
The following lemma characterizes the unique solution of the KL\-regularized optimization problem; see, e\.g\.,[Zhang \(2023\)](https://arxiv.org/html/2609.13564#bib.bib1)\.

###### Lemma 1\(Solution of the KL\-Regularized Optimization Problem\)\.

For anyx∈𝒳x\\in\\mathcal\{X\}and reward functionR∈ℛR\\in\\mathcal\{R\}, we have

maxπ⁡\{𝔼a∼π​\[R⁡\(x,a\)\]−η−1​KL​\(π,πref∣x\)\}=η−1​log⁡𝔼a∼πref​\[exp⁡\(η​R​\(x,a\)\)\]\.\\displaystyle\\max\_\{\\pi\}\\left\\\{\\mathbb\{E\}\_\{a\\sim\\pi\}\[R\(x,a\)\]\-\\eta^\{\-1\}\\mathrm\{KL\}\(\\pi,\\pi\_\{\\mathrm\{ref\}\}\\mid x\)\\right\\\}=\\eta^\{\-1\}\\log\\mathbb\{E\}\_\{a\\sim\\pi\_\{\\mathrm\{ref\}\}\}\\left\[\\exp\\bigl\(\\eta R\(x,a\)\\bigr\)\\right\]\.The unique maximizer is the Gibbs policy

πR​\(a∣x\)=πref​\(a∣x\)​exp⁡\(η​R​\(x,a\)\)ZR​\(x\),\\pi\_\{R\}\(a\\mid x\)=\\frac\{\\pi\_\{\\mathrm\{ref\}\}\(a\\mid x\)\\exp\\bigl\(\\eta R\(x,a\)\\bigr\)\}\{Z\_\{R\}\(x\)\},\(3\)whereZR​\(x\):=∑a′∈𝒜πref​\(a′∣x\)​exp⁡\(η​R​\(x,a′\)\)Z\_\{R\}\(x\):=\\sum\_\{a^\{\\prime\}\\in\\mathcal\{A\}\}\\pi\_\{\\mathrm\{ref\}\}\(a^\{\\prime\}\\mid x\)\\exp\\bigl\(\\eta R\(x,a^\{\\prime\}\)\\bigr\)is the normalizing constant\. Under Assumption[1](https://arxiv.org/html/2609.13564#Thmassumption1), the optimal policy is therefore given byπ⋆=πR⋆\\pi^\{\\star\}=\\pi\_\{R^\{\\star\}\}\.

Although our main polylogarithmic regret guarantee does not explicitly depend on the eluder dimension, we use the following uncertainty measure and the associated eluder dimension to characterize eluder dimension\-dependent guarantees and to facilitate comparisons with existing approaches\.

###### Definition 1\(Uncertainty Measure and Eluder Dimension: Reward Feedback\([Zhao et al\., 2025b](https://arxiv.org/html/2609.13564#bib.bib2)\)\)\.

Fort≥1t\\geq 1, let𝒟tRF:=\{\(xi,ai\)\}i=1t\\mathcal\{D\}\_\{t\}^\{\\operatorname\{RF\}\}:=\\\{\(x\_\{i\},a\_\{i\}\)\\\}\_\{i=1\}^\{t\}denote the sequence of observed context–action pairs up to roundtt\. Forλ\>0\\lambda\>0, the uncertainty of a context–action pair\(x,a\)∈𝒳×𝒜\(x,a\)\\in\\mathcal\{X\}\\times\\mathcal\{A\}with respect to the function classℛ\\mathcal\{R\}and the dataDt−1RFD^\{\\operatorname\{RF\}\}\_\{t\-1\}is defined as

URF​\(λ,x,a,ℛ,𝒟t−1RF\):=supR1,R2∈ℛ\|R1​\(x,a\)−R2​\(x,a\)\|λ\+∑i=1t−1\(R1​\(xi,ai\)−R2​\(xi,ai\)\)2\.\\displaystyle U\_\{\\mathrm\{RF\}\}\(\\lambda,x,a,\\mathcal\{R\};\\mathcal\{D\}^\{\\operatorname\{RF\}\}\_\{t\-1\}\):=\\sup\_\{R\_\{1\},R\_\{2\}\\in\\mathcal\{R\}\}\\frac\{\|R\_\{1\}\(x,a\)\-R\_\{2\}\(x,a\)\|\}\{\\sqrt\{\\lambda\+\\sum\_\{i=1\}^\{t\-1\}\\bigl\(R\_\{1\}\(x\_\{i\},a\_\{i\}\)\-R\_\{2\}\(x\_\{i\},a\_\{i\}\)\\bigr\)^\{2\}\}\}\.The corresponding eluder dimension is defined as

dRF\(λ,ℛ,T\):=supx1:T,a1:T∑t=1Tmin\{1,URF2\(λ,xt,at,ℛ;𝒟t−1RF\)\}\.\\displaystyle d\_\{\\mathrm\{RF\}\}\(\\lambda,\\mathcal\{R\},T\):=\\sup\_\{x\_\{1:T\},a\_\{1:T\}\}\\sum\_\{t=1\}^\{T\}\\min\\left\\\{1,\\,U\_\{\\mathrm\{RF\}\}^\{2\}\(\\lambda,x\_\{t\},a\_\{t\},\\mathcal\{R\};\\mathcal\{D\}^\{\\operatorname\{RF\}\}\_\{t\-1\}\)\\right\\\}\.

### 3\.3KL\-Regularized Contextual Bandits with Preference Feedback

We next consider KL\-regularized contextual bandits with PF\. At each roundt∈\[T\]t\\in\[T\], a contextxtx\_\{t\}is independently drawn fromdd\. The learner selects an action pair\(at1,at2\)∈𝒜2\(a\_\{t\}^\{1\},a\_\{t\}^\{2\}\)\\in\\mathcal\{A\}^\{2\}and receives binary feedbackyt∈\{0,1\}y\_\{t\}\\in\\\{0,1\\\}indicating the preferred action\. We consider two preference models: the GP model and the BT model\.

#### 3\.3\.1General Preference Model

Under the GP model, preferences are characterized by an unknown functionP⋆:𝒳×𝒜×𝒜→\[0,1\]P^\{\\star\}:\\mathcal\{X\}\\times\\mathcal\{A\}\\times\\mathcal\{A\}\\to\[0,1\], whereP⋆​\(x,a1,a2\)P^\{\\star\}\(x,a^\{1\},a^\{2\}\)denotes the probability thata1a^\{1\}is preferred toa2a^\{2\}under contextxx\. Conditioned on\(xt,at1,at2\)\(x\_\{t\},a\_\{t\}^\{1\},a\_\{t\}^\{2\}\), the feedbackyty\_\{t\}is generated independently of the past according toyt∼Ber⁡\(P⋆​\(xt,at1,at2\)\)y\_\{t\}\\sim\\operatorname\{Ber\}\\\!\\left\(P^\{\\star\}\(x\_\{t\},a\_\{t\}^\{1\},a\_\{t\}^\{2\}\)\\right\)\. The learner has access to a finite candidate preference class𝒫\\mathcal\{P\}, where eachP:𝒳×𝒜×𝒜→\[0,1\]P:\\mathcal\{X\}\\times\\mathcal\{A\}\\times\\mathcal\{A\}\\to\[0,1\]satisfies the standard reciprocity conditionP⁡\(x,a1,a2\)\+P⁡\(x,a2,a1\)=1P\(x,a^\{1\},a^\{2\}\)\+P\(x,a^\{2\},a^\{1\}\)=1for all\(x,a1,a2\)∈𝒳×𝒜2\(x,a^\{1\},a^\{2\}\)\\in\\mathcal\{X\}\\times\\mathcal\{A\}^\{2\}\. We make the following realizability assumption\.

###### Assumption 2\(GP Realizability\)\.

The true preference function satisfiesP⋆∈𝒫P^\{\\star\}\\in\\mathcal\{P\}\.

##### Learning objective\.

For convenience, for anyP∈𝒫P\\in\\mathcal\{P\}, defineP⁡\(x,a,π\):=𝔼a′∼π​\[P⁡\(x,a,a′\)\]P\(x,a,\\pi\):=\\mathbb\{E\}\_\{a^\{\\prime\}\\sim\\pi\}\[P\(x,a,a^\{\\prime\}\)\]andP⁡\(x,π1,π2\):=𝔼a1∼π1,a2∼π2​\[P⁡\(x,a1,a2\)\]P\(x,\\pi^\{1\},\\pi^\{2\}\):=\\mathbb\{E\}\_\{a^\{1\}\\sim\\pi^\{1\},\\,a^\{2\}\\sim\\pi^\{2\}\}\[P\(x,a^\{1\},a^\{2\}\)\]\. Under the GP model, we consider the following KL\-regularized zero\-sum objective\([Munos et al\., 2024](https://arxiv.org/html/2609.13564#bib.bib6);[Ye et al\., 2024](https://arxiv.org/html/2609.13564#bib.bib7)\):

JGP​\(π1,π2\):=𝔼x∼d​\[P⋆​\(x,π1,π2\)−η−1​KL​\(π1,πref∣x\)\+η−1​KL​\(π2,πref∣x\)\]\.\\displaystyle J\_\{\\mathrm\{GP\}\}\(\\pi^\{1\},\\pi^\{2\}\):=\\mathbb\{E\}\_\{x\\sim d\}\\Big\[P^\{\\star\}\(x,\\pi^\{1\},\\pi^\{2\}\)\-\\eta^\{\-1\}\\mathrm\{KL\}\(\\pi^\{1\},\\pi\_\{\\mathrm\{ref\}\}\\mid x\)\+\\eta^\{\-1\}\\mathrm\{KL\}\(\\pi^\{2\},\\pi\_\{\\mathrm\{ref\}\}\\mid x\)\\Big\]\.Here, the first player seeks to maximize the preference value, whereas the second player seeks to minimize it\. Accordingly, the KL regularization enters with opposite signs for the two players, encouraging both policies to remain close to the reference policyπref\\pi\_\{\\mathrm\{ref\}\}\.

The optimal value of the KL\-regularized zero\-sum game is defined as

JGP⋆:=maxπ1⁡minπ2​JGP​\(π1,π2\)\.J\_\{\\mathrm\{GP\}\}^\{\\star\}:=\\max\_\{\\pi^\{1\}\}\\min\_\{\\pi^\{2\}\}J\_\{\\mathrm\{GP\}\}\(\\pi^\{1\},\\pi^\{2\}\)\.It has been shown that this game admits a unique Nash equilibrium, with the two equilibrium policies coinciding\([Munos et al\., 2024](https://arxiv.org/html/2609.13564#bib.bib6);[Ye et al\., 2024](https://arxiv.org/html/2609.13564#bib.bib7)\)\. We denote the common equilibrium policy byπGP⋆\\pi\_\{\\mathrm\{GP\}\}^\{\\star\}, so that\(πGP⋆,πGP⋆\)\(\\pi\_\{\\mathrm\{GP\}\}^\{\\star\},\\pi\_\{\\mathrm\{GP\}\}^\{\\star\}\)is the unique Nash equilibrium andJGP⋆=JGP​\(πGP⋆,πGP⋆\)J\_\{\\mathrm\{GP\}\}^\{\\star\}=J\_\{\\mathrm\{GP\}\}\(\\pi\_\{\\mathrm\{GP\}\}^\{\\star\},\\pi\_\{\\mathrm\{GP\}\}^\{\\star\}\)\. For a learned first\-player policyπ^t1\\widehat\{\\pi\}\_\{t\}^\{1\}, we measure its suboptimality against its regularized best response:JGP⋆−minπ2⁡JGP​\(π^t1,π2\)J\_\{\\mathrm\{GP\}\}^\{\\star\}\-\\min\_\{\\pi^\{2\}\}J\_\{\\mathrm\{GP\}\}\(\\widehat\{\\pi\}\_\{t\}^\{1\},\\pi^\{2\}\)\. Our goal is to design a sequence of first\-player policies\{π^t1\}t=1T\\\{\\widehat\{\\pi\}\_\{t\}^\{1\}\\\}\_\{t=1\}^\{T\}that minimizes the cumulative regret

RegGP⁡\(T\):=∑t=1T\(JGP⋆−minπ2⁡JGP​\(π^t1,π2\)\)\.\\operatorname\{Reg\}\_\{\\mathrm\{GP\}\}\(T\):=\\sum\_\{t=1\}^\{T\}\\left\(J\_\{\\mathrm\{GP\}\}^\{\\star\}\-\\min\_\{\\pi^\{2\}\}J\_\{\\mathrm\{GP\}\}\(\\widehat\{\\pi\}\_\{t\}^\{1\},\\pi^\{2\}\)\\right\)\.
The following characterization of the equilibrium policy, established in prior work, will be useful in our analysis\.

###### Lemma 2\(Nash Equilibrium under the GP Model\([Wu et al\., 2025](https://arxiv.org/html/2609.13564#bib.bib8)\)\)\.

For anyP∈𝒫P\\in\\mathcal\{P\}, the corresponding equilibrium policyπP\\pi\_\{P\}satisfies

πP​\(a∣x\)=πref​\(a∣x\)​exp⁡\(η​P​\(x,a,πP\)\)ZP​\(x\),\\pi\_\{P\}\(a\\mid x\)=\\frac\{\\pi\_\{\\mathrm\{ref\}\}\(a\\mid x\)\\exp\\\!\\bigl\(\\eta P\(x,a,\\pi\_\{P\}\)\\bigr\)\}\{Z\_\{P\}\(x\)\},whereZP​\(x\):=∑a′∈𝒜πref​\(a′∣x\)​exp⁡\(η​P​\(x,a′,πP\)\)Z\_\{P\}\(x\):=\\sum\_\{a^\{\\prime\}\\in\\mathcal\{A\}\}\\pi\_\{\\mathrm\{ref\}\}\(a^\{\\prime\}\\mid x\)\\exp\\\!\\bigl\(\\eta P\(x,a^\{\\prime\},\\pi\_\{P\}\)\\bigr\)\. In particular, the true equilibrium policy isπGP⋆=πP⋆\\pi\_\{\\mathrm\{GP\}\}^\{\\star\}=\\pi\_\{P^\{\\star\}\}\.

We next introduce the uncertainty measure and the associated eluder dimension for the GP model, which will be used to characterize eluder\-dimension\-dependent guarantees and compare with existing methods\.

###### Definition 2\(Uncertainty Measure and Eluder Dimension: General Preference Model\([Wu et al\., 2025](https://arxiv.org/html/2609.13564#bib.bib8)\)\)\.

Fort≥1t\\geq 1, let𝒟tGP:=\{\(xi,ai1,ai2\)\}i=1t\\mathcal\{D\}\_\{t\}^\{\\mathrm\{GP\}\}:=\\\{\(x\_\{i\},a\_\{i\}^\{1\},a\_\{i\}^\{2\}\)\\\}\_\{i=1\}^\{t\}\. Forλ\>0\\lambda\>0, define

UGP​\(λ,x,a1,a2,𝒫,𝒟t−1GP\):=supP1,P2∈𝒫\|P1​\(x,a1,a2\)−P2​\(x,a1,a2\)\|λ\+∑i=1t−1\(P1​\(xi,ai1,ai2\)−P2​\(xi,ai1,ai2\)\)2\.\\displaystyle U\_\{\\mathrm\{GP\}\}\(\\lambda,x,a^\{1\},a^\{2\},\\mathcal\{P\};\\mathcal\{D\}\_\{t\-1\}^\{\\mathrm\{GP\}\}\):=\\sup\_\{P\_\{1\},P\_\{2\}\\in\\mathcal\{P\}\}\\frac\{\|P\_\{1\}\(x,a^\{1\},a^\{2\}\)\-P\_\{2\}\(x,a^\{1\},a^\{2\}\)\|\}\{\\sqrt\{\\lambda\+\\sum\_\{i=1\}^\{t\-1\}\\bigl\(P\_\{1\}\(x\_\{i\},a\_\{i\}^\{1\},a\_\{i\}^\{2\}\)\-P\_\{2\}\(x\_\{i\},a\_\{i\}^\{1\},a\_\{i\}^\{2\}\)\\bigr\)^\{2\}\}\}\.The corresponding eluder dimension is

dGP\(λ,𝒫,T\):=supx1:T,a1:T1,a1:T2∑t=1Tmin\{1,UGP2\(λ,xt,at1,at2,𝒫;𝒟t−1GP\)\}\.\\displaystyle d\_\{\\mathrm\{GP\}\}\(\\lambda,\\mathcal\{P\},T\):=\\sup\_\{x\_\{1:T\},a\_\{1:T\}^\{1\},a\_\{1:T\}^\{2\}\}\\sum\_\{t=1\}^\{T\}\\min\\left\\\{1,\\,U\_\{\\mathrm\{GP\}\}^\{2\}\(\\lambda,x\_\{t\},a\_\{t\}^\{1\},a\_\{t\}^\{2\},\\mathcal\{P\};\\mathcal\{D\}\_\{t\-1\}^\{\\mathrm\{GP\}\}\)\\right\\\}\.

#### 3\.3\.2Bradley–Terry Model

Under the BT model, preferences are induced by the latent reward functionR⋆:𝒳×𝒜→\[0,1\]R^\{\\star\}:\\mathcal\{X\}\\times\\mathcal\{A\}\\to\[0,1\]throughP⋆​\(x,a1,a2\)=σ⁡\(R⋆​\(x,a1\)−R⋆​\(x,a2\)\)P^\{\\star\}\(x,a^\{1\},a^\{2\}\)=\\sigma\\\!\\left\(R^\{\\star\}\(x,a^\{1\}\)\-R^\{\\star\}\(x,a^\{2\}\)\\right\), whereσ⁡\(z\):=\(1\+e−z\)−1\\sigma\(z\):=\(1\+e^\{\-z\}\)^\{\-1\}\. Conditioned on\(xt,at1,at2\)\(x\_\{t\},a\_\{t\}^\{1\},a\_\{t\}^\{2\}\), the feedbackyty\_\{t\}is independent of the past and followsyt∼Ber⁡\(σ⁡\(R⋆​\(xt,at1\)−R⋆​\(xt,at2\)\)\)y\_\{t\}\\sim\\operatorname\{Ber\}\\\!\\left\(\\sigma\\\!\\left\(R^\{\\star\}\(x\_\{t\},a\_\{t\}^\{1\}\)\-R^\{\\star\}\(x\_\{t\},a\_\{t\}^\{2\}\)\\right\)\\right\)\. As in the RF setting, we assume that Assumption[1](https://arxiv.org/html/2609.13564#Thmassumption1)holds\.

Learning objective\.Since the BT model is induced by the latent rewardR⋆R^\{\\star\}, we evaluate policies using the same KL\-regularized reward objective:JBT​\(π\):=JRF​\(π\)J\_\{\\mathrm\{BT\}\}\(\\pi\):=J\_\{\\mathrm\{RF\}\}\(\\pi\)\. Consequently,πBT⋆=π⋆\\pi\_\{\\mathrm\{BT\}\}^\{\\star\}=\\pi^\{\\star\}in both the RF and BT settings\. Our goal is to design a sequence of policies\{π^t1\}t=1T\\\{\\widehat\{\\pi\}\_\{t\}^\{1\}\\\}\_\{t=1\}^\{T\}that minimizes the cumulative regret

RegBT⁡\(T\):=∑t=1T\(JBT​\(π⋆\)−JBT​\(π^t1\)\)\.\\operatorname\{Reg\}\_\{\\mathrm\{BT\}\}\(T\):=\\sum\_\{t=1\}^\{T\}\\left\(J\_\{\\mathrm\{BT\}\}\(\\pi^\{\\star\}\)\-J\_\{\\mathrm\{BT\}\}\(\\widehat\{\\pi\}\_\{t\}^\{1\}\)\\right\)\.Thus, the BT and reward\-feedback settings share the same policy objective, but differ in the observed feedback and consequently in howR⋆R^\{\\star\}is estimated\.

We similarly define the uncertainty measure and eluder dimension under the BT model\.

###### Definition 3\(Uncertainty Measure and Eluder Dimension: Bradley–Terry Model\([Wu et al\., 2025](https://arxiv.org/html/2609.13564#bib.bib8)\)\)\.

Fort≥1t\\geq 1, let𝒟tBT:=\{\(xi,ai1,ai2\)\}i=1t\\mathcal\{D\}\_\{t\}^\{\\mathrm\{BT\}\}:=\\\{\(x\_\{i\},a\_\{i\}^\{1\},a\_\{i\}^\{2\}\)\\\}\_\{i=1\}^\{t\}\. Forλ\>0\\lambda\>0, define

UBT​\(λ,x,a1,a2,ℛ,𝒟t−1BT\):=supR1,R2∈ℛ\|\(R1−R2\)​\(x,a1\)−\(R1−R2\)​\(x,a2\)\|λ\+∑i=1t−1\[\(R1−R2\)​\(xi,ai1\)−\(R1−R2\)​\(xi,ai2\)\]2\.\\displaystyle U\_\{\\mathrm\{BT\}\}\(\\lambda,x,a^\{1\},a^\{2\},\\mathcal\{R\};\\mathcal\{D\}\_\{t\-1\}^\{\\mathrm\{BT\}\}\):=\\sup\_\{R\_\{1\},R\_\{2\}\\in\\mathcal\{R\}\}\\frac\{\\left\|\(R\_\{1\}\-R\_\{2\}\)\(x,a^\{1\}\)\-\(R\_\{1\}\-R\_\{2\}\)\(x,a^\{2\}\)\\right\|\}\{\\sqrt\{\\lambda\+\\sum\_\{i=1\}^\{t\-1\}\\left\[\(R\_\{1\}\-R\_\{2\}\)\(x\_\{i\},a\_\{i\}^\{1\}\)\-\(R\_\{1\}\-R\_\{2\}\)\(x\_\{i\},a\_\{i\}^\{2\}\)\\right\]^\{2\}\}\}\.The corresponding eluder dimension is

dBT\(λ,ℛ,T\):=supx1:T,a1:T1,a1:T2∑t=1Tmin\{1,UBT2\(λ,xt,at1,at2,ℛ;𝒟t−1BT\)\}\.\\displaystyle d\_\{\\mathrm\{BT\}\}\(\\lambda,\\mathcal\{R\},T\):=\\sup\_\{x\_\{1:T\},a\_\{1:T\}^\{1\},a\_\{1:T\}^\{2\}\}\\sum\_\{t=1\}^\{T\}\\min\\left\\\{1,\\,U\_\{\\mathrm\{BT\}\}^\{2\}\(\\lambda,x\_\{t\},a\_\{t\}^\{1\},a\_\{t\}^\{2\},\\mathcal\{R\};\\mathcal\{D\}\_\{t\-1\}^\{\\mathrm\{BT\}\}\)\\right\\\}\.

## 4KL\-Regularized Contextual Bandits with Reward Feedback

Algorithm 1RF\-GS1:Input:

ℛ,η,πref\\mathcal\{R\},\\eta,\\pi\_\{\\mathrm\{ref\}\}
2:Choose any

R^1∈ℛ\\widehat\{R\}\_\{1\}\\in\\mathcal\{R\}and define

π1\(⋅∣⋅\)∝πref\(⋅∣⋅\)exp\(ηR^1\(⋅,⋅\)\)\.\\pi\_\{1\}\(\\cdot\\mid\\cdot\)\\propto\\pi\_\{\\rm ref\}\(\\cdot\\mid\\cdot\)\\exp\\\!\\left\(\\eta\\widehat\{R\}\_\{1\}\(\\cdot,\\cdot\)\\right\)\.
3:Observe

x1∼dx\_\{1\}\\sim d, take action

a1∼π1\(⋅∣x1\)a\_\{1\}\\sim\\pi\_\{1\}\(\\cdot\\mid x\_\{1\}\), and observe reward

r1r\_\{1\}
4:forround

t=2,…,Tt=2,\\ldots,Tdo

5:Observe context

xt∼dx\_\{t\}\\sim d
6:Compute the LS estimator

R^t∈arg⁡min⁡∑i=1t−1R∈ℛ⁡\(R⁡\(xi,ai\)−ri\)2\\widehat\{R\}\_\{t\}\\in\\arg\\min\_\{R\\in\\mathcal\{R\}\}\\sum\_\{i=1\}^\{t\-1\}\\bigl\(R\(x\_\{i\},a\_\{i\}\)\-r\_\{i\}\\bigr\)^\{2\}
7:Compute the Gibbs policy by Eq\. \([4](https://arxiv.org/html/2609.13564#S4.E4)\)

8:Take action

at∼πt\(⋅∣xt\)a\_\{t\}\\sim\\pi\_\{t\}\(\\cdot\\mid x\_\{t\}\)and observe reward

rtr\_\{t\}
9:endfor

We proposeRF\-GS\(Reward\-Feedback Greedy Sampling\), a simple greedy algorithm for KL\-regularized contextual bandits under RF\. The pseudocode is provided in Algorithm[1](https://arxiv.org/html/2609.13564#alg1)\.

##### RF\-GSAlgorithm\.

At the beginning of each roundtt, the algorithm observes the contextxtx\_\{t\}\. Using the historical observationsℋt−1RF=\{\(xi,ai,ri\)\}i=1t−1\\mathcal\{H\}^\{\\text\{RF\}\}\_\{t\-1\}=\\\{\(x\_\{i\},a\_\{i\},r\_\{i\}\)\\\}\_\{i=1\}^\{t\-1\}, it computes the reward estimatorR^t\\widehat\{R\}\_\{t\}by solving a least\-squares \(LS\) regression problem over the function classℛ\\mathcal\{R\}\. It then directly constructs the Gibbs policy induced by the estimated reward,

πt​\(a∣x\)∝πref​\(a∣x\)​exp⁡\(η​R^t​\(x,a\)\)\.\\displaystyle\\pi\_\{t\}\(a\\mid x\)\\propto\\pi\_\{\\rm ref\}\(a\\mid x\)\\exp\\\!\\left\(\\eta\\widehat\{R\}\_\{t\}\(x,a\)\\right\)\.\(4\)This direct plug\-in step is what we refer to as*greedy sampling*: the policy is constructed solely from the current reward estimate, without any explicit uncertainty\-dependent exploration bonus\. In contrast, UCB\-based methods such asK\-UCB\([Zhao et al\., 2025b](https://arxiv.org/html/2609.13564#bib.bib2)\)augment the reward estimate with an exploration bonusbt​\(x,a\)b\_\{t\}\(x,a\)\(see the discussion in our Appendix\) that favors actions with greater uncertainty\. Finally,RF\-GSsamples an actionat∼πt\(⋅∣xt\)a\_\{t\}\\sim\\pi\_\{t\}\(\\cdot\\mid x\_\{t\}\)and observes the corresponding rewardrtr\_\{t\}\.

The following theorem shows that, despite its simplicity,RF\-GScan achieve polylogarithmic regret without any explicit dependence on the eluder dimension\.

###### Theorem 1\(Eluder Dimension\-Independent Regret Bound forRF\-GS\)\.

Suppose Assumption[1](https://arxiv.org/html/2609.13564#Thmassumption1)holds\. Then, for anyδ∈\(0,1\)\\delta\\in\(0,1\)andT≥2T\\geq 2, with probability at least1−δ1\-\\delta, the regret ofRF\-GSafterTTrounds satisfies

RegRF⁡\(T\)=O⁡\(η​e2​η​log⁡T​log⁡Nℛ​Tδ\)\.\\operatorname\{Reg\}\_\{\\mathrm\{RF\}\}\(T\)=O\\\!\\left\(\\eta e^\{2\\eta\}\\log T\\log\\frac\{N\_\{\\mathcal\{R\}\}T\}\{\\delta\}\\right\)\.

##### Proof Sketch of Theorem[1](https://arxiv.org/html/2609.13564#Thmtheorem1)\.

The proof proceeds in three steps\. First, we upper bound the instantaneous regret by an expected squared prediction errorStS\_\{t\}\. Second, a uniform prediction\-error bound, together with a likelihood\-ratio bound between Gibbs policies and an averaging argument over past rounds, yieldsSt=O~​\(e2​η/t\)S\_\{t\}=\\widetilde\{O\}\(e^\{2\\eta\}/t\)\. Finally, summing this bound overttgives the logarithmic dependence on the horizon\.

##### Step 1: Regret decomposition\.

By Lemma[4](https://arxiv.org/html/2609.13564#Thmlemma4)in the Appendix, the instantaneous regret for eacht∈\[T\]t\\in\[T\]can be upper bounded byJRF​\(π⋆\)−JRF​\(πt\)≤η​StJ\_\{\\mathrm\{RF\}\}\(\\pi^\{\\star\}\)\-J\_\{\\mathrm\{RF\}\}\(\\pi\_\{t\}\)\\leq\\eta S\_\{t\}, where

St:=𝔼x∼d,a∼πt′​\[\(R^t​\(x,a\)−R⋆​\(x,a\)\)2\],S\_\{t\}:=\\mathbb\{E\}\_\{x\\sim d,\\;a\\sim\\pi\_\{t\}^\{\\prime\}\}\\left\[\\left\(\\widehat\{R\}\_\{t\}\(x,a\)\-R^\{\\star\}\(x,a\)\\right\)^\{2\}\\right\],andπt′\\pi\_\{t\}^\{\\prime\}denotes the Gibbs policy induced byRt′=γt​R^t\+\(1−γt\)​R⋆R\_\{t\}^\{\\prime\}=\\gamma\_\{t\}\\widehat\{R\}\_\{t\}\+\(1\-\\gamma\_\{t\}\)R^\{\\star\}for someγt∈\[0,1\]\\gamma\_\{t\}\\in\[0,1\]\. Summing the above inequality overt∈\[T\]t\\in\[T\]yields

RegRF⁡\(T\)\\displaystyle\\operatorname\{Reg\}\_\{\\rm RF\}\(T\)=∑t=1T\(JRF​\(π⋆\)−JRF​\(πt\)\)≤η​∑t=1TSt\.\\displaystyle=\\sum\_\{t=1\}^\{T\}\\Bigl\(J\_\{\\rm RF\}\(\\pi^\{\\star\}\)\-J\_\{\\rm RF\}\(\\pi\_\{t\}\)\\Bigr\)\\leq\\eta\\sum\_\{t=1\}^\{T\}S\_\{t\}\.\(5\)

##### Step 2: Upper bound onStS\_\{t\}\.

We next apply the following uniform convergence result, which controls the cumulative squared prediction error under the data\-generating policies\.

###### Lemma 3\(Uniform Prediction Error Bound, Reward Feedback\)\.

Suppose Assumption[1](https://arxiv.org/html/2609.13564#Thmassumption1)holds\. LetR^t\\widehat\{R\}\_\{t\}be the LS estimator overℛ\\mathcal\{R\}constructed from the samples\{\(xi,ai,ri\)\}i=1t−1\\\{\(x\_\{i\},a\_\{i\},r\_\{i\}\)\\\}\_\{i=1\}^\{t\-1\}, wherexi∼dx\_\{i\}\\sim dandai∼πi\(⋅∣xi\)a\_\{i\}\\sim\\pi\_\{i\}\(\\cdot\\mid x\_\{i\}\)for eachii\. Then, for any such policy sequence\{πi\}i≥1\\\{\\pi\_\{i\}\\\}\_\{i\\geq 1\}and anyδ∈\(0,1\)\\delta\\in\(0,1\), with probability at least1−δ1\-\\delta, the following holds simultaneously for allt=2,…,Tt=2,\\ldots,T:

∑i=1t−1𝔼x∼d,a∼πi​\[\(R⋆​\(x,a\)−R^t​\(x,a\)\)2\]≤72​log⁡2​Nℛ​T3δ\.\\displaystyle\\begin\{split\}&\\sum\_\{i=1\}^\{t\-1\}\\mathbb\{E\}\_\{x\\sim d,\\;a\\sim\\pi\_\{i\}\}\\left\[\\left\(R^\{\\star\}\(x,a\)\-\\widehat\{R\}\_\{t\}\(x,a\)\\right\)^\{2\}\\right\]\\leq 72\\log\\frac\{2N\_\{\\mathcal\{R\}\}T^\{3\}\}\{\\delta\}\.\\end\{split\}\(6\)

We now relate the expectation inStS\_\{t\}, which is taken under the intermediate Gibbs policyπt′\\pi\_\{t\}^\{\\prime\}, to the prediction errors under the data\-generating policies\{πi\}i=1t−1\\\{\\pi\_\{i\}\\\}\_\{i=1\}^\{t\-1\}\. Fort=1t=1, we trivially haveS1≤1S\_\{1\}\\leq 1\. For anyt≥2t\\geq 2andi<ti<t, since bothπt′\\pi\_\{t\}^\{\\prime\}andπi\\pi\_\{i\}are Gibbs policies induced by\[0,1\]\[0,1\]\-valued reward functions, their likelihood ratio satisfies

πt′​\(a∣x\)πi​\(a∣x\)≤e2​η,∀\(x,a\)\.\\frac\{\\pi\_\{t\}^\{\\prime\}\(a\\mid x\)\}\{\\pi\_\{i\}\(a\\mid x\)\}\\leq e^\{2\\eta\},\\ \\forall\(x,a\)\.Therefore,

St≤e2​η​𝔼x∼d,a∼πi​\[\(R⋆​\(x,a\)−R^t​\(x,a\)\)2\]\.S\_\{t\}\\leq e^\{2\\eta\}\\mathbb\{E\}\_\{x\\sim d,\\;a\\sim\\pi\_\{i\}\}\\left\[\\left\(R^\{\\star\}\(x,a\)\-\\widehat\{R\}\_\{t\}\(x,a\)\\right\)^\{2\}\\right\]\.Averaging the above inequality overi=1,…,t−1i=1,\\ldots,t\-1and applying Eq\. \([6](https://arxiv.org/html/2609.13564#S4.E6)\) yields

St≤72​e2​ηt−1log2​Nℛ​T3δ,∀t=2,…,T\.\\displaystyle S\_\{t\}\\leq\\frac\{72e^\{2\\eta\}\}\{t\-1\}\\log\\frac\{2N\_\{\\mathcal\{R\}\}T^\{3\}\}\{\\delta\},\\qquad\\forall t=2,\\ldots,T\.\(7\)

##### Step 3: Summation over time\.

Summing the bound onStS\_\{t\}overttand using∑t=2T\(t−1\)−1≤1\+log⁡T\\sum\_\{t=2\}^\{T\}\(t\-1\)^\{\-1\}\\leq 1\+\\log Tgives

∑t=1TSt≤1\+72​e2​η​\(1\+log⁡T\)​log⁡2​Nℛ​T3δ\.\\displaystyle\\sum\_\{t=1\}^\{T\}S\_\{t\}\\leq 1\+72e^\{2\\eta\}\(1\+\\log T\)\\log\\frac\{2N\_\{\\mathcal\{R\}\}T^\{3\}\}\{\\delta\}\.\(8\)Finally, substituting Eq\. \([8](https://arxiv.org/html/2609.13564#S4.E8)\) into Eq\. \([5](https://arxiv.org/html/2609.13564#S4.E5)\) yields

RegRF⁡\(T\)=O⁡\(η​e2​η​log⁡T​log⁡Nℛ​Tδ\)\.\\operatorname\{Reg\}\_\{\\mathrm\{RF\}\}\(T\)=O\\\!\\left\(\\eta e^\{2\\eta\}\\log T\\log\\frac\{N\_\{\\mathcal\{R\}\}T\}\{\\delta\}\\right\)\.The complete proof is provided in the Appendix\.

##### Eluder\-Dimension\-Dependent Regret Bound forRF\-GS\.

We can also derive an eluder\-dimension\-dependent regret bound forRF\-GSusing a standard uncertainty\-based analysis\.

###### Corollary 1\(Dimension\-Dependent Regret Bound forRF\-GS\)\.

Fix anyλ\>0\\lambda\>0satisfyingλ≤8​log⁡2​Nℛ​Tδ\\lambda\\leq 8\\log\\frac\{2N\_\{\\mathcal\{R\}\}T\}\{\\delta\}\. Then, under Assumption[1](https://arxiv.org/html/2609.13564#Thmassumption1), for anyδ∈\(0,1\)\\delta\\in\(0,1\), with probability at least1−δ1\-\\delta, the regret ofRF\-GSsatisfies

RegRF⁡\(T\)=O⁡\(η​e2​η​\(dRF​\(λ,ℛ,T\)\+log⁡1δ\)​log⁡Nℛ​Tδ\)\.\\operatorname\{Reg\}\_\{\\rm RF\}\(T\)=O\\\!\\left\(\\eta e^\{2\\eta\}\\left\(d\_\{\\rm RF\}\(\\lambda,\\mathcal\{R\},T\)\+\\log\\frac\{1\}\{\\delta\}\\right\)\\log\\frac\{N\_\{\\mathcal\{R\}\}T\}\{\\delta\}\\right\)\.

The proof differs from that of Theorem[1](https://arxiv.org/html/2609.13564#Thmtheorem1)only in the control of∑t=1TSt\\sum\_\{t=1\}^\{T\}S\_\{t\}\. On the high\-probability event from Lemma[11](https://arxiv.org/html/2609.13564#Thmlemma11)in the Appendix, for any\(x,a\)∈𝒳×𝒜\(x,a\)\\in\\mathcal\{X\}\\times\\mathcal\{A\},

\(R^t​\(x,a\)−R⋆​\(x,a\)\)2≤16​log⁡2​Nℛ​Tδ​min​\{1,URF2​\(λ,x,a,ℛ,𝒟t−1RF\)\}\.\\displaystyle\\bigl\(\\widehat\{R\}\_\{t\}\(x,a\)\-R^\{\\star\}\(x,a\)\\bigr\)^\{2\}\\leq 16\\log\\frac\{2N\_\{\\mathcal\{R\}\}T\}\{\\delta\}\\min\\\!\\left\\\{1,U\_\{\\rm RF\}^\{2\}\(\\lambda,x,a,\\mathcal\{R\};\\mathcal\{D\}^\{\\operatorname\{RF\}\}\_\{t\-1\}\)\\right\\\}\.Using the likelihood\-ratio boundπt′​\(a∣x\)/πt​\(a∣x\)≤e2​η\\pi\_\{t\}^\{\\prime\}\(a\\mid x\)/\\pi\_\{t\}\(a\\mid x\)\\leq e^\{2\\eta\}, together with the definition ofdRF​\(λ,ℛ,T\)d\_\{\\rm RF\}\(\\lambda,\\mathcal\{R\},T\)and a standard predictable\-to\-realized concentration argument, we obtain

∑t=1TSt=O⁡\(e2​η​\(dRF​\(λ,ℛ,T\)\+log⁡1δ\)​log⁡Nℛ​Tδ\)\.\\sum\_\{t=1\}^\{T\}S\_\{t\}=O\\\!\\left\(e^\{2\\eta\}\\left\(d\_\{\\rm RF\}\(\\lambda,\\mathcal\{R\},T\)\+\\log\\frac\{1\}\{\\delta\}\\right\)\\log\\frac\{N\_\{\\mathcal\{R\}\}T\}\{\\delta\}\\right\)\.Combining this with the regret decomposition in Eq\. \([5](https://arxiv.org/html/2609.13564#S4.E5)\) gives the stated result\. The complete proof is provided in the Appendix\.

Compared with Corollary[1](https://arxiv.org/html/2609.13564#Thmcorollary1), Theorem[1](https://arxiv.org/html/2609.13564#Thmtheorem1)replaces the uncertainty\-complexity termdRF​\(λ,ℛ,T\)\+log⁡\(1/δ\)d\_\{\\rm RF\}\(\\lambda,\\mathcal\{R\},T\)\+\\log\(1/\\delta\)with the logarithmic factorlog⁡T\\log T, while retaining the same dependence onη\\eta\.

##### Trade\-offs Between Greedy Sampling and UCB Exploration\.

We next compare the available regret guarantees ofRF\-GSandK\-UCBunder different strengths of KL regularization\. Whene2​η​log⁡T≲dRF​\(λ,ℛ,T\)e^\{2\\eta\}\\log T\\lesssim d\_\{\\mathrm\{RF\}\}\(\\lambda,\\mathcal\{R\},T\), the regret bound ofRF\-GS,O⁡\(η​e2​η​log⁡T​log⁡Nℛ​Tδ\)O\\\!\\left\(\\eta e^\{2\\eta\}\\log T\\log\\frac\{N\_\{\\mathcal\{R\}\}T\}\{\\delta\}\\right\)\(Theorem[1](https://arxiv.org/html/2609.13564#Thmtheorem1)\), is sharper than the dimension\-dependent bound ofK\-UCB,O⁡\(η​dRF​\(λ,ℛ,T\)​log⁡Nℛ​Tδ\)O\\\!\\left\(\\eta d\_\{\\rm RF\}\(\\lambda,\\mathcal\{R\},T\)\\log\\frac\{N\_\{\\mathcal\{R\}\}T\}\{\\delta\}\\right\)\(see Theorem 4\.1 in[Zhao et al\. \(2025b\)](https://arxiv.org/html/2609.13564#bib.bib2)\)\. Intuitively, for smallη\\eta, the KL regularization is strong and the Gibbs policyπ⋆​\(a∣x\)=πref​\(a∣x\)​exp⁡\(η​R⋆​\(x,a\)\)/ZR⋆​\(x\)\\pi^\{\\star\}\(a\\mid x\)=\\pi\_\{\\rm ref\}\(a\\mid x\)\\exp\(\\eta R^\{\\star\}\(x,a\)\)/Z\_\{R^\{\\star\}\}\(x\)remains relatively close to the reference policy\. In this regime, the stochasticity inherited from the reference policy can provide effective exploration without an explicit optimism bonus\.

Asη\\etaincreases beyond this threshold, the exponential factore2​ηe^\{2\\eta\}in theRF\-GSbound eliminates its advantage over the dimension\-dependentK\-UCBguarantee\. In particular,K\-UCBhas the sharper available boundO⁡\(η​dRF​\(λ,ℛ,T\)​log⁡Nℛ​Tδ\)O\\\!\\left\(\\eta d\_\{\\rm RF\}\(\\lambda,\\mathcal\{R\},T\)\\log\\frac\{N\_\{\\mathcal\{R\}\}T\}\{\\delta\}\\right\)\. This reflects the weaker KL regularization: as the Gibbs policy becomes more concentrated, the implicit exploration induced by the reference policy becomes less pronounced, while explicit optimism provides a stronger worst\-case guarantee\.

K\-UCBalso admits theη\\eta\-independent boundO⁡\(T⁡\(dRF​\(λ,ℛ,T\)\+log⁡1δ\)​log⁡Nℛ​Tδ\)O\\\!\\left\(\\sqrt\{T\\left\(d\_\{\\mathrm\{RF\}\}\(\\lambda,\\mathcal\{R\},T\)\+\\log\\frac\{1\}\{\\delta\}\\right\)\\log\\frac\{N\_\{\\mathcal\{R\}\}T\}\{\\delta\}\}\\right\), as established in Corollary[4](https://arxiv.org/html/2609.13564#Thmcorollary4)in the Appendix\. This bound becomes the sharperK\-UCBguarantee whenη\\etais sufficiently large\. Hence, the availableK\-UCBguarantee can be summarized asO~​\(min⁡\{η​dRF​\(λ,ℛ,T\),dRF​\(λ,ℛ,T\)​T\}\)\\widetilde\{O\}\\\!\\left\(\\min\\left\\\{\\eta d\_\{\\mathrm\{RF\}\}\(\\lambda,\\mathcal\{R\},T\),\\sqrt\{d\_\{\\mathrm\{RF\}\}\(\\lambda,\\mathcal\{R\},T\)T\}\\right\\\}\\right\)\. Thus, as the KL regularization becomes weaker, the comparison exhibits a clear transition: the eluder\-dimension\-independent guarantee ofRF\-GSis sharper in the strongly regularized regime, whereasK\-UCBbecomes sharper once the exponential dependence onη\\etadominates\. Asη\\etaincreases further, the regret guarantee ofK\-UCBeventually saturates at the standardT\\sqrt\{T\}\-type rate, which is independent ofη\\eta\.

## 5KL\-Regularized Contextual Bandits with Preference Feedback

Algorithm 2ORLHF\-GS1:Input:

η\\eta,

πref\\pi\_\{\\mathrm\{ref\}\},

𝒫\\mathcal\{P\},

ℛ\\mathcal\{R\}
2:Initialize:Choose any

P^1∈𝒫\\widehat\{P\}\_\{1\}\\in\\mathcal\{P\}and

R^1∈ℛ\\widehat\{R\}\_\{1\}\\in\\mathcal\{R\}
3:for

t=1,…,Tt=1,\\ldots,Tdo

4:Observe context

xt∼dx\_\{t\}\\sim d
5:ifGP modelthen

6:if

t≥2t\\geq 2then

7:Compute the MLE

P^t∈arg⁡max⁡∑i=1t−1P∈𝒫⁡\[yi​log⁡P⁡\(xi,ai1,ai2\)\+\(1−yi\)​log⁡P⁡\(xi,ai2,ai1\)\]\\widehat\{P\}\_\{t\}\\in\\arg\\max\_\{P\\in\\mathcal\{P\}\}\\sum\_\{i=1\}^\{t\-1\}\\Big\[y\_\{i\}\\log P\(x\_\{i\},a\_\{i\}^\{1\},a\_\{i\}^\{2\}\)\+\(1\-y\_\{i\}\)\\log P\(x\_\{i\},a\_\{i\}^\{2\},a\_\{i\}^\{1\}\)\\Big\]
8:endif

9:Set

π^t1\\widehat\{\\pi\}\_\{t\}^\{1\}to the NE policy associated with

P^t\\widehat\{P\}\_\{t\}
10:elseifBT modelthen

11:if

t≥2t\\geq 2then

12:Compute the MLE

R^t∈arg⁡max⁡∑i=1t−1R∈ℛ⁡\[yi​log⁡σ⁡\(R⁡\(xi,ai1\)−R⁡\(xi,ai2\)\)\+\(1−yi\)​log⁡σ⁡\(R⁡\(xi,ai2\)−R⁡\(xi,ai1\)\)\]\\widehat\{R\}\_\{t\}\\in\\arg\\max\_\{R\\in\\mathcal\{R\}\}\\sum\_\{i=1\}^\{t\-1\}\\Big\[y\_\{i\}\\log\\sigma\\\!\\big\(R\(x\_\{i\},a\_\{i\}^\{1\}\)\-R\(x\_\{i\},a\_\{i\}^\{2\}\)\\big\)\+\(1\-y\_\{i\}\)\\log\\sigma\\\!\\big\(R\(x\_\{i\},a\_\{i\}^\{2\}\)\-R\(x\_\{i\},a\_\{i\}^\{1\}\)\\big\)\\Big\]
13:endif

14:Construct the Gibbs policy

π^t1​\(a∣x\)∝πref​\(a∣x\)​exp⁡\(η​R^t​\(x,a\)\)\\widehat\{\\pi\}\_\{t\}^\{1\}\(a\\mid x\)\\propto\\pi\_\{\\mathrm\{ref\}\}\(a\\mid x\)\\exp\\\!\\left\(\\eta\\widehat\{R\}\_\{t\}\(x,a\)\\right\)
15:endif

16:Sample

at1∼π^t1\(⋅∣xt\)a\_\{t\}^\{1\}\\sim\\widehat\{\\pi\}\_\{t\}^\{1\}\(\\cdot\\mid x\_\{t\}\)and

at2∼πref\(⋅∣xt\)a\_\{t\}^\{2\}\\sim\\pi\_\{\\mathrm\{ref\}\}\(\\cdot\\mid x\_\{t\}\)
17:Observe preference feedback

yty\_\{t\}
18:endfor

In this section, we show that the greedy algorithmORLHF\-GS\(Online RLHF with Greedy Sampling\), proposed by[Wu et al\. \(2025\)](https://arxiv.org/html/2609.13564#bib.bib8), also achieves an eluder\-dimension\-independent regret bound\. The detailed procedure is summarized in Algorithm[2](https://arxiv.org/html/2609.13564#alg2)\.

##### ORLHF\-GSAlgorithm\.

ORLHF\-GSextends greedy sampling to the PF setting\. Compared with the RF setting, the learner samples an action pair\(at1,at2\)\(a\_\{t\}^\{1\},a\_\{t\}^\{2\}\)rather than a single action, whereat1a\_\{t\}^\{1\}is drawn from the current learned policyπ^t1\\widehat\{\\pi\}\_\{t\}^\{1\}andat2a\_\{t\}^\{2\}from the reference policy\. After observing the pairwise PF, the learner updates the preference or reward model using maximum likelihood estimation \(MLE\), and then constructs the greedy policy used in the next round\.

### 5\.1General Preference Model

The following theorem establishes two complementary regret guarantees forORLHF\-GSunder the GP model\.

###### Theorem 2\(Regret Bounds under the General Preference Model forORLHF\-GS\)\.

Under Assumption[2](https://arxiv.org/html/2609.13564#Thmassumption2), for anyδ∈\(0,1\)\\delta\\in\(0,1\)andT≥2T\\geq 2, with probability at least1−δ1\-\\delta,

RegGP⁡\(T\)=O⁡\(η​e3​η​log⁡T​log⁡N𝒫​Tδ\)\.\\operatorname\{Reg\}\_\{\\operatorname\{GP\}\}\(T\)=O\\\!\\left\(\\eta e^\{3\\eta\}\\log T\\log\\frac\{N\_\{\\mathcal\{P\}\}T\}\{\\delta\}\\right\)\.Moreover, for anyλ\>0\\lambda\>0satisfyingλ≤log⁡\(2​N𝒫​T/δ\)\\lambda\\leq\\log\(2N\_\{\\mathcal\{P\}\}T/\\delta\), with probability at least1−δ1\-\\delta,

RegGP⁡\(T\)=O⁡\(CLOSE\\displaystyle\\operatorname\{Reg\}\_\{\\operatorname\{GP\}\}\(T\)=O\\\!\\Bigg\(OPENη​eη​\(dGP​\(λ,𝒫,T\)\+log⁡1δ\)​log⁡N𝒫​Tδ\)\.\\displaystyle\\eta e^\{\\eta\}\\left\(d\_\{\\operatorname\{GP\}\}\(\\lambda,\\mathcal\{P\},T\)\+\\log\\frac\{1\}\{\\delta\}\\right\)\\log\\frac\{N\_\{\\mathcal\{P\}\}T\}\{\\delta\}\\Bigg\)\.

Theorem[2](https://arxiv.org/html/2609.13564#Thmtheorem2)improves upon and complements the dimension\-dependent analysis of[Wu et al\. \(2025\)](https://arxiv.org/html/2609.13564#bib.bib8)in two respects\. Their analysis yields the regret boundO⁡\(\(η​e3​η\+η3​e9​η\)​dGP​\(λ,𝒫,T\)​log⁡N𝒫​Tδ\)O\\\!\\left\(\\left\(\\eta e^\{3\\eta\}\+\\eta^\{3\}e^\{9\\eta\}\\right\)d\_\{\\operatorname\{GP\}\}\(\\lambda,\\mathcal\{P\},T\)\\log\\frac\{N\_\{\\mathcal\{P\}\}T\}\{\\delta\}\\right\)\. In contrast, Theorem[2](https://arxiv.org/html/2609.13564#Thmtheorem2)establishes the eluder\-dimension\-independent boundO⁡\(η​e3​η​log⁡T​log⁡N𝒫​Tδ\)O\\\!\\left\(\\eta e^\{3\\eta\}\\log T\\log\\frac\{N\_\{\\mathcal\{P\}\}T\}\{\\delta\}\\right\), which removes both the explicit dependence ondGP​\(λ,𝒫,T\)d\_\{\\operatorname\{GP\}\}\(\\lambda,\\mathcal\{P\},T\)and theη3​e9​η\\eta^\{3\}e^\{9\\eta\}term\. Moreover, even under an eluder\-dimension\-based analysis, our bound improves the dependence on the regularization parameter fromη​e3​η\+η3​e9​η\\eta e^\{3\\eta\}\+\\eta^\{3\}e^\{9\\eta\}toη​eη\\eta e^\{\\eta\}, eliminating the cubic term entirely\.

The key technical ingredient behind these improvements is the refined instantaneous regret decomposition in Lemma[5](https://arxiv.org/html/2609.13564#Thmlemma5)\. As in[Wu et al\. \(2025\)](https://arxiv.org/html/2609.13564#bib.bib8), a central difficulty is the mismatch between the learned equilibrium policyπ^t1\\widehat\{\\pi\}^\{1\}\_\{t\}and its true regularized best responseπ~t2:=arg⁡minπ2​JGP​\(π^t1,π2\)\\widetilde\{\\pi\}\_\{t\}^\{2\}:=\\arg\\min\_\{\\pi^\{2\}\}J\_\{\\operatorname\{GP\}\}\\left\(\\widehat\{\\pi\}\_\{t\}^\{1\},\\pi^\{2\}\\right\)\. Our analysis exploits the structure of the KL\-regularized game more directly: it expresses the instantaneous regret in terms of the KL divergence between these two policies and then uses the curvature of the KL regularizer, together with the Gibbs\-policy boundedness relative to the reference policy, to control this divergence by the squared preference\-prediction error\. This yields the sharper instantaneous bound

JGP⋆−JGP​\(π^t1,π~t2\)≤2​η​eη​𝔼x∼d,a1∼π^t1,a2∼πref​\[\(P⋆​\(x,a1,a2\)−P^t​\(x,a1,a2\)\)2\]\.\\displaystyle\\begin\{split\}&J\_\{\\operatorname\{GP\}\}^\{\\star\}\-J\_\{\\operatorname\{GP\}\}\\left\(\\widehat\{\\pi\}\_\{t\}^\{1\},\\widetilde\{\\pi\}\_\{t\}^\{2\}\\right\)\\leq 2\\eta e^\{\\eta\}\\mathbb\{E\}\_\{x\\sim d,\\,a^\{1\}\\sim\\widehat\{\\pi\}\_\{t\}^\{1\},\\,a^\{2\}\\sim\\pi\_\{\\rm ref\}\}\\left\[\\bigl\(P^\{\\star\}\(x,a^\{1\},a^\{2\}\)\-\\widehat\{P\}\_\{t\}\(x,a^\{1\},a^\{2\}\)\\bigr\)^\{2\}\\right\]\.\\end\{split\}This decomposition is the common ingredient behind both the eluder\-dimension\-independent guarantee and the sharper dimension\-dependent bound\.

For completeness, we also develop a UCB\-style exploration algorithm for the GP model, termedGP\-UCB\. The algorithm and its analysis are deferred to the Appendix\. The following corollary summarizes its regret guarantee\.

###### Corollary 2\(Regret Bound forGP\-UCB\)\.

Under Assumption[2](https://arxiv.org/html/2609.13564#Thmassumption2), for anyδ∈\(0,1\)\\delta\\in\(0,1\)and anyλ\>0\\lambda\>0satisfyingλ≤log⁡2​N𝒫​Tδ\\lambda\\leq\\log\\frac\{2N\_\{\\mathcal\{P\}\}T\}\{\\delta\},GP\-UCBsatisfies, with probability at least1−δ1\-\\delta,

RegGP⁡\(T\)=O~​\(min⁡\{η​dGP​\(λ,𝒫,T\),dGP​\(λ,𝒫,T\)​T\}\)\.\\displaystyle\\operatorname\{Reg\}\_\{\\operatorname\{GP\}\}\(T\)=\\widetilde\{O\}\\\!\\left\(\\min\\left\\\{\\eta d\_\{\\operatorname\{GP\}\}\(\\lambda,\\mathcal\{P\},T\),\\sqrt\{d\_\{\\operatorname\{GP\}\}\(\\lambda,\\mathcal\{P\},T\)T\}\\right\\\}\\right\)\.

Corollary[2](https://arxiv.org/html/2609.13564#Thmcorollary2)reveals a trade\-off similar to that in the RF setting\. In the strongly regularized regime, whene3​η​log⁡T≲dGP​\(λ,𝒫,T\)e^\{3\\eta\}\\log T\\lesssim d\_\{\\mathrm\{GP\}\}\(\\lambda,\\mathcal\{P\},T\), the eluder\-dimension\-independent guarantee ofORLHF\-GS, is sharper than the dimension\-dependentGP\-UCBguarantee\. Asη\\etaincreases, the exponential dependence in the greedy bound eventually dominates, and explicit UCB\-style exploration provides the sharper worst\-case guarantee\. For sufficiently largeη\\eta, the availableGP\-UCBbound further saturates at the standardO~​\(dGP​T\)\\widetilde\{O\}\(\\sqrt\{d\_\{\\operatorname\{GP\}\}T\}\)rate, which is independent ofη\\eta\.

### 5\.2Bradley–Terry Model

We next turn to the Bradley–Terry model\. Since the BT preference model is induced by a latent reward function, its analysis is closely connected to the reward\-feedback setting\.

###### Theorem 3\(Regret Bound under the Bradley–Terry Model forORLHF\-GS\)\.

Under Assumption[1](https://arxiv.org/html/2609.13564#Thmassumption1), for anyδ∈\(0,1\)\\delta\\in\(0,1\)andT≥2T\\geq 2, with probability at least1−δ1\-\\delta,ORLHF\-GSunder the BT model satisfies

RegBT⁡\(T\)=O⁡\(η​e2​η​log⁡T​log⁡Nℛ​Tδ\)\.\\operatorname\{Reg\}\_\{\\operatorname\{BT\}\}\(T\)=O\\\!\\left\(\\eta e^\{2\\eta\}\\log T\\log\\frac\{N\_\{\\mathcal\{R\}\}T\}\{\\delta\}\\right\)\.

Theorem[3](https://arxiv.org/html/2609.13564#Thmtheorem3)strengthens the existing BT analysis of[Wu et al\. \(2025\)](https://arxiv.org/html/2609.13564#bib.bib8)by removing the explicit dependence on the BT eluder dimension\. Tracking the explicitη\\eta\-dependence in their proof yields a dimension\-dependent regret bound of orderO~​\(η​e2​η​dBT​\(λ,ℛ,T\)\)\\widetilde\{O\}\\\!\\left\(\\eta e^\{2\\eta\}d\_\{\\operatorname\{BT\}\}\(\\lambda,\\mathcal\{R\},T\)\\right\)\. In contrast, Theorem[3](https://arxiv.org/html/2609.13564#Thmtheorem3)replacesdBT​\(λ,ℛ,T\)d\_\{\\operatorname\{BT\}\}\(\\lambda,\\mathcal\{R\},T\)by only a logarithmic dependence onTT, while retaining the same dependence onη\\eta\. Notably, this matches the regret order obtained in the RF setting, despite the fact that the latent reward is observed only indirectly through binary PF\.

For completeness, we also consider the corresponding UCB\-style exploration rule for the BT model, termedBT\-UCB; its construction and analysis are deferred to the Appendix\.

###### Corollary 3\(Regret Bound forBT\-UCB\)\.

Under Assumption[1](https://arxiv.org/html/2609.13564#Thmassumption1), for anyδ∈\(0,1\)\\delta\\in\(0,1\)and anyλ\>0\\lambda\>0satisfyingλ≤4​e2​log⁡2​Nℛ​Tδ\\lambda\\leq 4e^\{2\}\\log\\frac\{2N\_\{\\mathcal\{R\}\}T\}\{\\delta\},BT\-UCBsatisfies, with probability at least1−δ1\-\\delta,

RegBT⁡\(T\)=O~​\(min⁡\{η​dBT​\(λ,ℛ,T\),dBT​\(λ,ℛ,T\)​T\}\)\.\\displaystyle\\operatorname\{Reg\}\_\{\\operatorname\{BT\}\}\(T\)=\\widetilde\{O\}\\left\(\\min\\left\\\{\\eta d\_\{\\operatorname\{BT\}\}\(\\lambda,\\mathcal\{R\},T\),\\sqrt\{d\_\{\\operatorname\{BT\}\}\(\\lambda,\\mathcal\{R\},T\)T\}\\right\\\}\\right\)\.

Since the regret guarantees ofORLHF\-GSandBT\-UCBhave the same order as their counterparts in the RF setting, the greedy–UCB trade\-off under the BT model is identical in order to that in the RF setting\.

## 6Experiments

![Refer to caption](https://arxiv.org/html/2609.13564v1/figures/Image.png)Figure 1:Mean cumulative KL\-regularized regret ofRF\-GSandK\-UCBacross different values ofη\\eta\.##### Experimental setup\.

We consider a synthetic RF contextual bandit under KL regularization with three contexts \(i\.e\.,\|𝒳\|=3\|\\mathcal\{X\}\|=3\), three actions \(i\.e\.,\|𝒜\|=3\|\\mathcal\{A\}\|=3\) and a function class with five functions \(i\.e\.,\|ℛ\|=5\|\\mathcal\{R\}\|=5\)\. We compare theRF\-GS\(Algorithm[1](https://arxiv.org/html/2609.13564#alg1)\) withK\-UCB\([Zhao et al\., 2025b](https://arxiv.org/html/2609.13564#bib.bib2)\)\. Each algorithm is run forT=5000T=5000rounds, and the results are averaged over1010independent random seeds\. To investigate the effect of KL regularization, we vary the regularization parameter over

η∈\{0\.5,1,3,10,30,100,300,500,1000,2000\}\.\\displaystyle\\begin\{split\}\\eta\\in\\\{&0\.5,1,3,10,30,100,300,500,1000,2000\\\}\.\\end\{split\}We report the empirical cumulative KL\-regularized regret of both methods for each value ofη\\eta\.

##### Results\.

Fig\.[1](https://arxiv.org/html/2609.13564#S6.F1)reveals a clear transition between the two exploration strategies as the strength of KL regularization varies\. For small and moderateη\\eta,RF\-GSachieves substantially lower regret thanK\-UCB, consistent with our theory that strong KL regularization provides sufficient implicit exploration for greedy sampling\. Asη\\etaincreases, the KL regularization weakens and the Gibbs policy becomes more concentrated\. Consequently,RF\-GSperforms less exploration and may remain concentrated on suboptimal actions\. In contrast,K\-UCBexplicitly explores uncertain actions through its exploration bonus, which becomes increasingly beneficial in this regime\. Consequently,K\-UCBeventually outperformsRF\-GS\. Overall, the empirical results closely match the theoretical tradeoff between KL\-induced implicit exploration and explicit optimism\-based exploration\.

## 7Conclusion

We studied KL\-regularized contextual bandits under both RF and PF, including the general preference and Bradley–Terry models\. We showed that, under sufficiently strong KL regularization, greedy sampling can provide sufficient implicit exploration without relying on additional exploration bonuses\. This leads to polylogarithmic regret guarantees that have no explicit dependence on the eluder dimension, contrasting with standard UCB\-style guarantees whose complexity typically scales with this dimension\. Our results also reveal a trade\-off between greedy sampling and optimism\-based exploration\. When the KL regularization is strong, the learned policy remains sufficiently close to the stochastic reference policy, allowing its inherent randomness to drive exploration and making greedy sampling favorable\. As the regularization weakens and the policy becomes more concentrated, this implicit exploration diminishes, and additional exploration can provide a sharper regret guarantee\. These findings clarify when a simple greedy strategy can be theoretically effective and how the strength of KL regularization determines the preferred exploration mechanism\.

## References

- Abbasi\-Yadkoriet al\.\(2011\)Y\. Abbasi\-Yadkori, D\. Pál, and C\. SzepesváriImproved algorithms for linear stochastic bandits\.InAdvances in Neural Information Processing Systems,Vol\.24\.Cited by:[§2](https://arxiv.org/html/2609.13564#S2.SS0.SSS0.Px1.p1.1)\.
- Agarwalet al\.\(2012\)A\. Agarwal, M\. Dudík, S\. Kale, J\. Langford, and R\. SchapireContextual bandit learning with predictable rewards\.InArtificial Intelligence and Statistics,pp\. 19–26\.Cited by:[Lemma 10](https://arxiv.org/html/2609.13564#Thmlemma10)\.
- Agarwalet al\.\(2014\)A\. Agarwal, D\. Hsu, S\. Kale, J\. Langford, L\. Li, and R\. E\. SchapireTaming the monster: a fast and simple algorithm for contextual bandits\.InProceedings of the 31st International Conference on Machine Learning,Proceedings of Machine Learning Research, Vol\.32,pp\. 1638–1646\.Cited by:[§2](https://arxiv.org/html/2609.13564#S2.SS0.SSS0.Px1.p2.1)\.
- Agrawal and Goyal \(2013\)S\. Agrawal and N\. GoyalThompson sampling for contextual bandits with linear payoffs\.InProceedings of the 30th International Conference on Machine Learning,Proceedings of Machine Learning Research, Vol\.28,pp\. 127–135\.Cited by:[§2](https://arxiv.org/html/2609.13564#S2.SS0.SSS0.Px1.p1.1)\.
- Cenet al\.\(2022\)S\. Cen, C\. Cheng, Y\. Chen, Y\. Wei, and Y\. ChiFast global convergence of natural policy gradient methods with entropy regularization\.Operations Research70\(4\),pp\. 2563–2578\.Cited by:[§2](https://arxiv.org/html/2609.13564#S2.SS0.SSS0.Px2.p1.1)\.
- Christianoet al\.\(2017\)P\. F\. Christiano, J\. Leike, T\. B\. Brown, M\. Martic, S\. Legg, and D\. AmodeiDeep reinforcement learning from human preferences\.InAdvances in Neural Information Processing Systems,Vol\.30\.Cited by:[§1](https://arxiv.org/html/2609.13564#S1.p1.1)\.
- Chuet al\.\(2011\)W\. Chu, L\. Li, L\. Reyzin, and R\. SchapireContextual bandits with linear payoff functions\.InProceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics,Proceedings of Machine Learning Research, Vol\.15,pp\. 208–214\.Cited by:[§2](https://arxiv.org/html/2609.13564#S2.SS0.SSS0.Px1.p1.1)\.
- Filippiet al\.\(2010\)S\. Filippi, O\. Cappé, A\. Garivier, and C\. SzepesváriParametric bandits: the generalized linear case\.InAdvances in Neural Information Processing Systems,Vol\.23\.Cited by:[§2](https://arxiv.org/html/2609.13564#S2.SS0.SSS0.Px1.p1.1)\.
- Fosteret al\.\(2018\)D\. Foster, A\. Agarwal, M\. Dudik, H\. Luo, and R\. SchapirePractical contextual bandits with regression oracles\.InProceedings of the 35th International Conference on Machine Learning,Proceedings of Machine Learning Research, Vol\.80,pp\. 1539–1548\.Cited by:[§2](https://arxiv.org/html/2609.13564#S2.SS0.SSS0.Px1.p2.1)\.
- Foster and Rakhlin \(2020\)D\. J\. Foster and A\. RakhlinBeyond UCB: optimal and efficient contextual bandits with regression oracles\.InProceedings of the 37th International Conference on Machine Learning,Proceedings of Machine Learning Research, Vol\.119,pp\. 3199–3210\.Cited by:[§2](https://arxiv.org/html/2609.13564#S2.SS0.SSS0.Px1.p2.1)\.
- Geistet al\.\(2019\)M\. Geist, B\. Scherrer, and O\. PietquinA theory of regularized markov decision processes\.InProceedings of the 36th International Conference on Machine Learning,Proceedings of Machine Learning Research, Vol\.97,pp\. 2160–2169\.Cited by:[§2](https://arxiv.org/html/2609.13564#S2.SS0.SSS0.Px2.p1.1)\.
- Honget al\.\(2026\)H\. Hong, Z\. Wang, Q\. Gu, and H\. WangOnline KL\-regularized reinforcement learning with function approximation under misspecification\.Note:Reinforcement Learning Conference 2026External Links:2606\.06053,[Link](https://arxiv.org/abs/2606.06053)Cited by:[§2](https://arxiv.org/html/2609.13564#S2.SS0.SSS0.Px2.p1.1)\.
- Jiet al\.\(2026a\)K\. Ji, Q\. Di, H\. Zhao, Q\. Zhao, and Q\. GuOn the optimal sample complexity of offline multi\-armed bandits with KL regularization\.arXiv preprint arXiv:2605\.02141\.Cited by:[§1](https://arxiv.org/html/2609.13564#S1.p1.1),[§2](https://arxiv.org/html/2609.13564#S2.SS0.SSS0.Px2.p1.1)\.
- Jiet al\.\(2026b\)K\. Ji, Q\. Zhao, H\. Zhao, Q\. Di, and Q\. GuNear\-optimal regret for KL\-regularized multi\-armed bandits\.InProceedings of the 43rd International Conference on Machine Learning,Cited by:[§1](https://arxiv.org/html/2609.13564#S1.p1.1),[§2](https://arxiv.org/html/2609.13564#S2.SS0.SSS0.Px2.p1.1)\.
- Langford and Zhang \(2007\)J\. Langford and T\. ZhangThe epoch\-greedy algorithm for multi\-armed bandits with side information\.InAdvances in Neural Information Processing Systems,Vol\.20\.Cited by:[§2](https://arxiv.org/html/2609.13564#S2.SS0.SSS0.Px1.p2.1)\.
- Liet al\.\(2010\)L\. Li, W\. Chu, J\. Langford, and R\. E\. SchapireA contextual\-bandit approach to personalized news article recommendation\.InProceedings of the 19th International Conference on World Wide Web,pp\. 661–670\.Cited by:[§2](https://arxiv.org/html/2609.13564#S2.SS0.SSS0.Px1.p1.1)\.
- Munoset al\.\(2024\)R\. Munos, M\. Valko, D\. Calandriello, M\. G\. Azar, M\. Rowland, Z\. D\. Guo, Y\. Tang, M\. Geist, T\. Mesnard, C\. Fiegel, A\. Michi, M\. Selvi, S\. Girgin, N\. Momchev, O\. Bachem, D\. J\. Mankowitz, D\. Precup, and B\. PiotNash learning from human feedback\.InProceedings of the 41st International Conference on Machine Learning,Proceedings of Machine Learning Research, Vol\.235,pp\. 36743–36768\.Cited by:[§1](https://arxiv.org/html/2609.13564#S1.p1.1),[§3\.3\.1](https://arxiv.org/html/2609.13564#S3.SS3.SSS1.Px1.p1.1),[§3\.3\.1](https://arxiv.org/html/2609.13564#S3.SS3.SSS1.Px1.p2.2)\.
- Osband and Van Roy \(2014\)I\. Osband and B\. Van RoyModel\-based reinforcement learning and the eluder dimension\.Advances in Neural Information Processing Systems27\.Cited by:[§1](https://arxiv.org/html/2609.13564#S1.p2.1),[§2](https://arxiv.org/html/2609.13564#S2.SS0.SSS0.Px1.p2.1)\.
- Ouyanget al\.\(2022\)L\. Ouyang, J\. Wu, X\. Jiang, D\. Almeida, C\. L\. Wainwright, P\. Mishkin, C\. Zhang, S\. Agarwal, K\. Slama, A\. Ray, J\. Schulman, J\. Hilton, F\. Kelton, L\. Miller, M\. Simens, A\. Askell, P\. Welinder, P\. F\. Christiano, J\. Leike, and R\. LoweTraining language models to follow instructions with human feedback\.InAdvances in Neural Information Processing Systems,Vol\.35\.Cited by:[§1](https://arxiv.org/html/2609.13564#S1.p1.1),[§2](https://arxiv.org/html/2609.13564#S2.SS0.SSS0.Px2.p1.1)\.
- Rafailovet al\.\(2023\)R\. Rafailov, A\. Sharma, E\. Mitchell, C\. D\. Manning, S\. Ermon, and C\. FinnDirect preference optimization: your language model is secretly a reward model\.InAdvances in Neural Information Processing Systems,Vol\.36\.Cited by:[§2](https://arxiv.org/html/2609.13564#S2.SS0.SSS0.Px2.p1.1)\.
- Russo and Van Roy \(2013\)D\. Russo and B\. Van RoyEluder dimension and the sample complexity of optimistic exploration\.InAdvances in Neural Information Processing Systems,Vol\.26,pp\. 2256–2264\.Cited by:[§1](https://arxiv.org/html/2609.13564#S1.p2.1),[§2](https://arxiv.org/html/2609.13564#S2.SS0.SSS0.Px1.p2.1),[§3\.2](https://arxiv.org/html/2609.13564#S3.SS2.p2.1)\.
- Simchi\-Levi and Xu \(2022\)D\. Simchi\-Levi and Y\. XuBypassing the monster: a faster and simpler optimal algorithm for contextual bandits under realizability\.Mathematics of Operations Research47\(3\),pp\. 1904–1931\.Cited by:[§2](https://arxiv.org/html/2609.13564#S2.SS0.SSS0.Px1.p2.1)\.
- Valkoet al\.\(2013\)M\. Valko, N\. Korda, R\. Munos, I\. Flaounas, and N\. CristianiniFinite\-time analysis of kernelised contextual bandits\.InProceedings of the Twenty\-Ninth Conference on Uncertainty in Artificial Intelligence,pp\. 654–663\.Cited by:[§2](https://arxiv.org/html/2609.13564#S2.SS0.SSS0.Px1.p1.1)\.
- Wuet al\.\(2025\)D\. Wu, C\. Shi, J\. Yang, and C\. ShenGreedy sampling is provably efficient for RLHF\.InAdvances in Neural Information Processing Systems,Vol\.38,pp\. 108198–108232\.Cited by:[§1](https://arxiv.org/html/2609.13564#S1.p2.1),[§2](https://arxiv.org/html/2609.13564#S2.SS0.SSS0.Px2.p1.1),[§5\.1](https://arxiv.org/html/2609.13564#S5.SS1.p2.1),[§5\.1](https://arxiv.org/html/2609.13564#S5.SS1.p3.1),[§5\.2](https://arxiv.org/html/2609.13564#S5.SS2.p2.1),[§5](https://arxiv.org/html/2609.13564#S5.p1.1),[Definition 2](https://arxiv.org/html/2609.13564#Thmdefinition2),[Definition 3](https://arxiv.org/html/2609.13564#Thmdefinition3),[Lemma 12](https://arxiv.org/html/2609.13564#Thmlemma12.p1.1.1),[Lemma 2](https://arxiv.org/html/2609.13564#Thmlemma2)\.
- Wuet al\.\(2026\)D\. Wu, C\. Shi, J\. Yang, and C\. Shen𝒇\\bm\{f\}\-Divergence regularized RLHF: two tales of sampling and unified analyses\.InProceedings of the 43rd International Conference on Machine Learning,Cited by:[§2](https://arxiv.org/html/2609.13564#S2.SS0.SSS0.Px2.p1.1)\.
- Xieet al\.\(2025\)T\. Xie, D\. J\. Foster, A\. Krishnamurthy, C\. Rosset, A\. Awadallah, and A\. RakhlinExploratory preference optimization: harnessing implicitQ⋆Q^\{\\star\}\-approximation for sample\-efficient RLHF\.InInternational Conference on Learning Representations,Cited by:[§2](https://arxiv.org/html/2609.13564#S2.SS0.SSS0.Px2.p1.1)\.
- Xionget al\.\(2024\)W\. Xiong, H\. Dong, C\. Ye, Z\. Wang, H\. Zhong, H\. Ji, N\. Jiang, and T\. ZhangIterative preference learning from human feedback: bridging theory and practice for RLHF under KL\-constraint\.InProceedings of the 41st International Conference on Machine Learning,Proceedings of Machine Learning Research, Vol\.235,pp\. 54715–54754\.Cited by:[§1](https://arxiv.org/html/2609.13564#S1.p1.1),[§2](https://arxiv.org/html/2609.13564#S2.SS0.SSS0.Px2.p1.1)\.
- Xu and Zeevi \(2024\)Y\. Xu and A\. ZeeviUpper counterfactual confidence bounds: a new optimism principle for contextual bandits\.Note:arXiv:2007\.07876v4External Links:2007\.07876,[Link](https://arxiv.org/abs/2007.07876)Cited by:[§3\.2](https://arxiv.org/html/2609.13564#S3.SS2.p2.1)\.
- Yeet al\.\(2024\)C\. Ye, W\. Xiong, Y\. Zhang, H\. Dong, N\. Jiang, and T\. ZhangOnline iterative reinforcement learning from human feedback with general preference model\.InAdvances in Neural Information Processing Systems,Vol\.37,pp\. 81773–81807\.Cited by:[§1](https://arxiv.org/html/2609.13564#S1.p1.1),[§3\.3\.1](https://arxiv.org/html/2609.13564#S3.SS3.SSS1.Px1.p1.1),[§3\.3\.1](https://arxiv.org/html/2609.13564#S3.SS3.SSS1.Px1.p2.2)\.
- Zhanet al\.\(2023\)W\. Zhan, S\. Cen, B\. Huang, Y\. Chen, J\. D\. Lee, and Y\. ChiPolicy mirror descent for regularized reinforcement learning: a generalized framework with linear convergence\.SIAM Journal on Optimization33\(2\),pp\. 1061–1091\.Cited by:[§2](https://arxiv.org/html/2609.13564#S2.SS0.SSS0.Px2.p1.1)\.
- Zhang \(2023\)T\. ZhangMathematical analysis of machine learning algorithms\.Cambridge University Press\.Cited by:[§1](https://arxiv.org/html/2609.13564#S1.p2.1),[§3\.2](https://arxiv.org/html/2609.13564#S3.SS2.SSS0.Px1.p3.1),[§3\.2](https://arxiv.org/html/2609.13564#S3.SS2.p2.1)\.
- Zhanget al\.\(2021\)W\. Zhang, D\. Zhou, L\. Li, and Q\. GuNeural Thompson sampling\.InInternational Conference on Learning Representations,Cited by:[§2](https://arxiv.org/html/2609.13564#S2.SS0.SSS0.Px1.p1.1)\.
- Zhaoet al\.\(2025a\)H\. Zhao, C\. Ye, Q\. Gu, and T\. ZhangSharp analysis for KL\-regularized contextual bandits and RLHF\.InAdvances in Neural Information Processing Systems,Vol\.38,pp\. 119520–119558\.Cited by:[§1](https://arxiv.org/html/2609.13564#S1.p1.1),[§2](https://arxiv.org/html/2609.13564#S2.SS0.SSS0.Px2.p1.1)\.
- Zhaoet al\.\(2025b\)H\. Zhao, C\. Ye, W\. Xiong, Q\. Gu, and T\. ZhangLogarithmic regret for online KL\-regularized reinforcement learning\.InProceedings of the 42nd International Conference on Machine Learning,Proceedings of Machine Learning Research, Vol\.267,pp\. 77864–77884\.Cited by:[§C\.5](https://arxiv.org/html/2609.13564#A3.SS5.p1.1),[§1](https://arxiv.org/html/2609.13564#S1.p1.1),[§1](https://arxiv.org/html/2609.13564#S1.p2.1),[§2](https://arxiv.org/html/2609.13564#S2.SS0.SSS0.Px2.p1.1),[§4](https://arxiv.org/html/2609.13564#S4.SS0.SSS0.Px1.p1.2),[§4](https://arxiv.org/html/2609.13564#S4.SS0.SSS0.Px7.p1.1),[§6](https://arxiv.org/html/2609.13564#S6.SS0.SSS0.Px1.p1.1),[Definition 1](https://arxiv.org/html/2609.13564#Thmdefinition1),[Lemma 11](https://arxiv.org/html/2609.13564#Thmlemma11)\.
- Zhaoet al\.\(2026a\)Q\. Zhao, K\. Ji, H\. Zhao, and Q\. GuFast rates for offline contextual bandits with forward\-KL regularization under single\-policy concentrability\.arXiv preprint arXiv:2605\.09214\.Cited by:[§2](https://arxiv.org/html/2609.13564#S2.SS0.SSS0.Px2.p1.1)\.
- Zhaoet al\.\(2026b\)Q\. Zhao, K\. Ji, H\. Zhao, T\. Zhang, and Q\. GuTowards a sharp analysis of offline policy learning forff\-divergence\-regularized contextual bandits\.InProceedings of the 14th International Conference on Learning Representations,Cited by:[§2](https://arxiv.org/html/2609.13564#S2.SS0.SSS0.Px2.p1.1)\.
- Zhouet al\.\(2020\)D\. Zhou, L\. Li, and Q\. GuNeural contextual bandits with UCB\-based exploration\.InProceedings of the 37th International Conference on Machine Learning,Proceedings of Machine Learning Research, Vol\.119,pp\. 11492–11502\.Cited by:[§2](https://arxiv.org/html/2609.13564#S2.SS0.SSS0.Px1.p1.1)\.

## Appendix ANotations

We summarize the main notation used throughout the paper in the following Table\.

## Appendix BUseful Properties of Gibbs Policies

For any reward functionR:𝒳×𝒜→\[0,1\]R:\\mathcal\{X\}\\times\\mathcal\{A\}\\to\\mathbb\{\[\}0,1\], the Gibbs policy induced byRRis defined as

πR​\(a\|x\)=πref​\(a∣x\)​exp⁡\(η​R​\(x,a\)\)ZR​\(x\),\\pi\_\{R\}\(a\|x\)=\\frac\{\\pi\_\{\\text\{ref\}\}\(a\\mid x\)\\exp\(\\eta R\(x,a\)\)\}\{Z\_\{R\}\(x\)\},whereZR​\(x\)=∑a′πref​\(a′∣x\)​exp⁡\(η​R​\(x,a′\)\)Z\_\{R\}\(x\)=\\sum\_\{a^\{\\prime\}\}\\pi\_\{\\rm ref\}\(a^\{\\prime\}\\mid x\)\\exp\\left\(\\eta R\(x,a^\{\\prime\}\)\\right\)is the normalizing constant\. It satisfies the following properties:

- •Boundedness with respect to the reference policy\.The Gibbs policyπR​\(a∣x\)\\pi\_\{R\}\(a\\mid x\)satisfiese−η≤πR​\(a∣x\)πref​\(a∣x\)≤eηe^\{\-\\eta\}\\leq\\frac\{\\pi\_\{R\}\(a\\mid x\)\}\{\\pi\_\{\\text\{ref\}\}\(a\\mid x\)\}\\leq e^\{\\eta\}, for all\(x,a\)∈𝒳×𝒜\(x,a\)\\in\\mathcal\{X\}\\times\\mathcal\{A\}\.
- •Pairwise boundedness\.For any two Gibbs policiesπR1\\pi\_\{R\_\{1\}\}andπR2\\pi\_\{R\_\{2\}\}induced by reward functionsR1,R2:𝒳×𝒜→\[0,1\]R\_\{1\},R\_\{2\}:\\mathcal\{X\}\\times\\mathcal\{A\}\\to\[0,1\],e−2​η≤πR1​\(a∣x\)πR2​\(a∣x\)≤e2​ηe^\{\-2\\eta\}\\leq\\frac\{\\pi\_\{R\_\{1\}\}\(a\\mid x\)\}\{\\pi\_\{R\_\{2\}\}\(a\\mid x\)\}\\leq e^\{2\\eta\}, for all\(x,a\)∈𝒳×𝒜\(x,a\)\\in\\mathcal\{X\}\\times\\mathcal\{A\}\.
- •Bounds on the normalizing constant\.The normalizing constantZR​\(x\)Z\_\{R\}\(x\)satisfies1≤ZR​\(x\)≤eη1\\leq Z\_\{R\}\(x\)\\leq e^\{\\eta\}, for allx∈𝒳x\\in\\mathcal\{X\}\.

## Appendix CProofs for Section[4](https://arxiv.org/html/2609.13564#S4)

### C\.1Proof of Theorem[1](https://arxiv.org/html/2609.13564#Thmtheorem1)

The proof of Theorem[1](https://arxiv.org/html/2609.13564#Thmtheorem1)relies on two key lemmas\. Lemma[4](https://arxiv.org/html/2609.13564#Thmlemma4)establishes the instantaneous KL\-regularized regret decomposition used in Step 1 of the proof sketch, while Lemma[3](https://arxiv.org/html/2609.13564#Thmlemma3)provides the uniform convergence guarantee of the LS estimator required in Step 2\. Combining these two ingredients yields the desired result\.

###### Lemma 4\(Instantaneous Regret Decomposition\)\.

For allt∈\[T\]t\\in\[T\], the instantaneous regret in the RF setting satisfies

JRF​\(π⋆\)−JRF​\(πt\)≤η​𝔼x∼d,a∼πt′​\[\(R⋆​\(x,a\)−R^t​\(x,a\)\)2\],J\_\{\\rm RF\}\(\\pi^\{\\star\}\)\-J\_\{\\rm RF\}\(\\pi\_\{t\}\)\\leq\\eta\\mathbb\{E\}\_\{x\\sim d,\\;a\\sim\\pi\_\{t\}^\{\\prime\}\}\\\!\\left\[\\bigl\(R^\{\\star\}\(x,a\)\-\\widehat\{R\}\_\{t\}\(x,a\)\\bigr\)^\{2\}\\right\],whereπt′\\pi\_\{t\}^\{\\prime\}is the Gibbs policy induced byRt′=γt​R^t\+\(1−γt\)​R⋆R\_\{t\}^\{\\prime\}=\\gamma\_\{t\}\\widehat\{R\}\_\{t\}\+\(1\-\\gamma\_\{t\}\)R^\{\\star\}for someγt∈\[0,1\]\\gamma\_\{t\}\\in\[0,1\]\.

###### Proof of Theorem[1](https://arxiv.org/html/2609.13564#Thmtheorem1)\.

DefineSt:=𝔼x∼d,a∼πt′​\[\(R^t​\(x,a\)−R⋆​\(x,a\)\)2\]S\_\{t\}:=\\mathbb\{E\}\_\{x\\sim d,\\;a\\sim\\pi\_\{t\}^\{\\prime\}\}\\\!\\left\[\\left\(\\widehat\{R\}\_\{t\}\(x,a\)\-R^\{\\star\}\(x,a\)\\right\)^\{2\}\\right\]\. By Lemma[4](https://arxiv.org/html/2609.13564#Thmlemma4), the cumulative regret admits the decomposition

RegRF⁡\(T\)=∑t=1T\(JRF​\(π⋆\)−JRF​\(πt\)\)≤η​∑t=1TSt\.\\operatorname\{Reg\}\_\{\\rm RF\}\(T\)=\\sum\_\{t=1\}^\{T\}\\Bigl\(J\_\{\\rm RF\}\(\\pi^\{\\star\}\)\-J\_\{\\rm RF\}\(\\pi\_\{t\}\)\\Bigr\)\\leq\\eta\\sum\_\{t=1\}^\{T\}S\_\{t\}\.\(9\)
We next derive an upper bound onStS\_\{t\}\. By Lemma[3](https://arxiv.org/html/2609.13564#Thmlemma3), on an event of probability at least1−δ1\-\\delta, the following holds simultaneously for allt≥2t\\geq 2:

∑i=1t−1𝔼x∼d,a∼πi​\[\(R⋆​\(x,a\)−R^t​\(x,a\)\)2\]≤72​log⁡2​Nℛ​t3δ,\\sum\_\{i=1\}^\{t\-1\}\\mathbb\{E\}\_\{x\\sim d,\\;a\\sim\\pi\_\{i\}\}\\\!\\left\[\\left\(R^\{\\star\}\(x,a\)\-\\widehat\{R\}\_\{t\}\(x,a\)\\right\)^\{2\}\\right\]\\leq 72\\log\\frac\{2N\_\{\\mathcal\{R\}\}t^\{3\}\}\{\\delta\},\(10\)whereπi\\pi\_\{i\}denotes the policy used to generate theii\-th sample\. It remains to transfer the above bound from the data\-generating policies\{πi\}i=1t−1\\\{\\pi\_\{i\}\\\}\_\{i=1\}^\{t\-1\}to the intermediate Gibbs policyπt′\\pi\_\{t\}^\{\\prime\}appearing in Lemma[4](https://arxiv.org/html/2609.13564#Thmlemma4)\. Fixt≥2t\\geq 2and anyi<ti<t\. Sinceπi\\pi\_\{i\}andπt′\\pi\_\{t\}^\{\\prime\}are Gibbs policies induced by\[0,1\]\[0,1\]\-valued reward functions\. Therefore

St=𝔼x∼d,a∼πt′​\[\(R⋆​\(x,a\)−R^t​\(x,a\)\)2\]≤e2​η​𝔼x∼d,a∼πi​\[\(R⋆​\(x,a\)−R^t​\(x,a\)\)2\]\.S\_\{t\}=\\mathbb\{E\}\_\{x\\sim d,\\;a\\sim\\pi\_\{t\}^\{\\prime\}\}\\\!\\left\[\\left\(R^\{\\star\}\(x,a\)\-\\widehat\{R\}\_\{t\}\(x,a\)\\right\)^\{2\}\\right\]\\leq e^\{2\\eta\}\\mathbb\{E\}\_\{x\\sim d,\\;a\\sim\\pi\_\{i\}\}\\\!\\left\[\\left\(R^\{\\star\}\(x,a\)\-\\widehat\{R\}\_\{t\}\(x,a\)\\right\)^\{2\}\\right\]\.Since the above inequality holds for everyi=1,…,t−1i=1,\\ldots,t\-1, averaging overiiyields

St≤e2​ηt−1​∑i=1t−1𝔼x∼d,a∼πi​\[\(R⋆​\(x,a\)−R^t​\(x,a\)\)2\]\.S\_\{t\}\\leq\\frac\{e^\{2\\eta\}\}\{t\-1\}\\sum\_\{i=1\}^\{t\-1\}\\mathbb\{E\}\_\{x\\sim d,\\;a\\sim\\pi\_\{i\}\}\\\!\\left\[\\left\(R^\{\\star\}\(x,a\)\-\\widehat\{R\}\_\{t\}\(x,a\)\\right\)^\{2\}\\right\]\.Combining this inequality with \([10](https://arxiv.org/html/2609.13564#A3.E10)\) gives

St≤72​e2​ηt−1​log⁡2​Nℛ​t3δ,∀t≥2\.S\_\{t\}\\leq\\frac\{72e^\{2\\eta\}\}\{t\-1\}\\log\\frac\{2N\_\{\\mathcal\{R\}\}t^\{3\}\}\{\\delta\},\\qquad\\forall t\\geq 2\.\(11\)
Fort=1t=1, since bothR^1\\widehat\{R\}\_\{1\}andR⋆R^\{\\star\}are\[0,1\]\[0,1\]\-valued, we trivially haveS1≤1S\_\{1\}\\leq 1\. Therefore, using \([11](https://arxiv.org/html/2609.13564#A3.E11)\),

∑t=1TSt≤1\+72​e2​η​log⁡2​Nℛ​T3δ​∑t=2T1t−1\.\\sum\_\{t=1\}^\{T\}S\_\{t\}\\leq 1\+72e^\{2\\eta\}\\log\\frac\{2N\_\{\\mathcal\{R\}\}T^\{3\}\}\{\\delta\}\\sum\_\{t=2\}^\{T\}\\frac\{1\}\{t\-1\}\.Applying the harmonic\-series bound∑t=2T1t−1≤1\+log⁡T\\sum\_\{t=2\}^\{T\}\\frac\{1\}\{t\-1\}\\leq 1\+\\log T, we obtain

∑t=1TSt≤1\+72​e2​η​\(1\+log⁡T\)​log⁡2​Nℛ​T3δ\.\\sum\_\{t=1\}^\{T\}S\_\{t\}\\leq 1\+72e^\{2\\eta\}\(1\+\\log T\)\\log\\frac\{2N\_\{\\mathcal\{R\}\}T^\{3\}\}\{\\delta\}\.Substituting the above estimate into \([9](https://arxiv.org/html/2609.13564#A3.E9)\) yields

RegRF⁡\(T\)≤η\+72​η​e2​η​\(1\+log⁡T\)​log⁡2​Nℛ​T3δ\.\\operatorname\{Reg\}\_\{\\rm RF\}\(T\)\\leq\\eta\+72\\eta e^\{2\\eta\}\(1\+\\log T\)\\log\\frac\{2N\_\{\\mathcal\{R\}\}T^\{3\}\}\{\\delta\}\.This completes the proof\. ∎

### C\.2Proof of Lemma[4](https://arxiv.org/html/2609.13564#Thmlemma4)

###### Proof of Lemma[4](https://arxiv.org/html/2609.13564#Thmlemma4)\.

For any reward functionR:𝒳×𝒜→\[0,1\]R:\\mathcal\{X\}\\times\\mathcal\{A\}\\to\[0,1\], defineΔR​\(x,a\):=R⁡\(x,a\)−R⋆​\(x,a\)\\Delta\_\{R\}\(x,a\):=R\(x,a\)\-R^\{\\star\}\(x,a\)\. By the definition of the KL\-regularized value,

JRF​\(π⋆\)−JRF​\(πR\)\\displaystyle J\_\{\\rm RF\}\(\\pi^\{\\star\}\)\-J\_\{\\rm RF\}\(\\pi\_\{R\}\)=𝔼x∼d,a∼π⋆​\[R⋆​\(x,a\)−η−1​log⁡π⋆​\(a∣x\)πref​\(a∣x\)\]−𝔼x∼d,a∼πR​\[R⋆​\(x,a\)−η−1​log⁡πR​\(a∣x\)πref​\(a∣x\)\]\.\\displaystyle=\\mathbb\{E\}\_\{x\\sim d,\\;a\\sim\\pi^\{\\star\}\}\\left\[R^\{\\star\}\(x,a\)\-\\eta^\{\-1\}\\log\\frac\{\\pi^\{\\star\}\(a\\mid x\)\}\{\\pi\_\{\\rm ref\}\(a\\mid x\)\}\\right\]\-\\mathbb\{E\}\_\{x\\sim d,\\;a\\sim\\pi\_\{R\}\}\\left\[R^\{\\star\}\(x,a\)\-\\eta^\{\-1\}\\log\\frac\{\\pi\_\{R\}\(a\\mid x\)\}\{\\pi\_\{\\rm ref\}\(a\\mid x\)\}\\right\]\.Sinceπ⋆=πR⋆\\pi^\{\\star\}=\\pi\_\{R^\{\\star\}\}, we havelog⁡π⋆​\(a∣x\)πref​\(a∣x\)=η​R⋆​\(x,a\)−log⁡ZR⋆​\(x\)\\log\\frac\{\\pi^\{\\star\}\(a\\mid x\)\}\{\\pi\_\{\\rm ref\}\(a\\mid x\)\}=\\eta R^\{\\star\}\(x,a\)\-\\log Z\_\{R^\{\\star\}\}\(x\)andlog⁡πR​\(a∣x\)πref​\(a∣x\)=η​R​\(x,a\)−log⁡ZR​\(x\)\\log\\frac\{\\pi\_\{R\}\(a\\mid x\)\}\{\\pi\_\{\\rm ref\}\(a\\mid x\)\}=\\eta R\(x,a\)\-\\log Z\_\{R\}\(x\)\. Substituting these identities gives

JRF​\(π⋆\)−JRF​\(πR\)\\displaystyle J\_\{\\rm RF\}\(\\pi^\{\\star\}\)\-J\_\{\\rm RF\}\(\\pi\_\{R\}\)=𝔼x∼d,a∼π⋆​\[R⋆​\(x,a\)−η−1​\(η​R⋆​\(x,a\)−log⁡ZR⋆​\(x\)\)\]\\displaystyle=\\mathbb\{E\}\_\{x\\sim d,\\;a\\sim\\pi^\{\\star\}\}\\left\[R^\{\\star\}\(x,a\)\-\\eta^\{\-1\}\\bigl\(\\eta R^\{\\star\}\(x,a\)\-\\log Z\_\{R^\{\\star\}\}\(x\)\\bigr\)\\right\]−𝔼x∼d,a∼πR​\[R⋆​\(x,a\)−η−1​\(η​R​\(x,a\)−log⁡ZR​\(x\)\)\]\\displaystyle\-\\mathbb\{E\}\_\{x\\sim d,\\;a\\sim\\pi\_\{R\}\}\\left\[R^\{\\star\}\(x,a\)\-\\eta^\{\-1\}\\bigl\(\\eta R\(x,a\)\-\\log Z\_\{R\}\(x\)\\bigr\)\\right\]=η−1​𝔼x∼d​\[log⁡ZR⋆​\(x\)−log⁡ZR​\(x\)\]\+𝔼x∼d,a∼πR​\[R⁡\(x,a\)−R⋆​\(x,a\)\]\.\\displaystyle=\\eta^\{\-1\}\\mathbb\{E\}\_\{x\\sim d\}\\left\[\\log Z\_\{R^\{\\star\}\}\(x\)\-\\log Z\_\{R\}\(x\)\\right\]\+\\mathbb\{E\}\_\{x\\sim d,\\;a\\sim\\pi\_\{R\}\}\\left\[R\(x,a\)\-R^\{\\star\}\(x,a\)\\right\]\.Define𝒥R​\(x\):=log⁡ZR​\(x\)−η​∑a′∈𝒜πR​\(a′∣x\)​ΔR​\(x,a′\)\\mathcal\{J\}\_\{R\}\(x\):=\\log Z\_\{R\}\(x\)\-\\eta\\sum\_\{a^\{\\prime\}\\in\\mathcal\{A\}\}\\pi\_\{R\}\(a^\{\\prime\}\\mid x\)\\Delta\_\{R\}\(x,a^\{\\prime\}\)\. SinceΔR⋆​\(x,a\)=0\\Delta\_\{R^\{\\star\}\}\(x,a\)=0for all\(x,a\)\(x,a\), we have𝒥R⋆​\(x\)=log⁡ZR⋆​\(x\)\\mathcal\{J\}\_\{R^\{\\star\}\}\(x\)=\\log Z\_\{R^\{\\star\}\}\(x\), and therefore

JRF​\(π⋆\)−JRF​\(πR\)=η−1​𝔼x∼d​\[𝒥R⋆​\(x\)−𝒥R​\(x\)\]\.J\_\{\\rm RF\}\(\\pi^\{\\star\}\)\-J\_\{\\rm RF\}\(\\pi\_\{R\}\)=\\eta^\{\-1\}\\mathbb\{E\}\_\{x\\sim d\}\\left\[\\mathcal\{J\}\_\{R^\{\\star\}\}\(x\)\-\\mathcal\{J\}\_\{R\}\(x\)\\right\]\.
We next view𝒥R​\(x\)\\mathcal\{J\}\_\{R\}\(x\)as a function ofΔR​\(x,a\)\\Delta\_\{R\}\(x,a\)\. Since

ZR​\(x\)=∑a′∈𝒜πref​\(a′∣x\)​exp⁡\(η⁡\(R⋆​\(x,a′\)\+ΔR​\(x,a′\)\)\),Z\_\{R\}\(x\)=\\sum\_\{a^\{\\prime\}\\in\\mathcal\{A\}\}\\pi\_\{\\rm ref\}\(a^\{\\prime\}\\mid x\)\\exp\\\!\\left\(\\eta\\bigl\(R^\{\\star\}\(x,a^\{\\prime\}\)\+\\Delta\_\{R\}\(x,a^\{\\prime\}\)\\bigr\)\\right\),we have

∂log⁡ZR​\(x\)∂ΔR​\(x,a\)\\displaystyle\\frac\{\\partial\\log Z\_\{R\}\(x\)\}\{\\partial\\Delta\_\{R\}\(x,a\)\}=1ZR​\(x\)​∂ZR​\(x\)∂ΔR​\(x,a\)\\displaystyle=\\frac\{1\}\{Z\_\{R\}\(x\)\}\\frac\{\\partial Z\_\{R\}\(x\)\}\{\\partial\\Delta\_\{R\}\(x,a\)\}=η​πref​\(a∣x\)​exp⁡\(η⁡\(R⋆​\(x,a\)\+ΔR​\(x,a\)\)\)ZR​\(x\)\\displaystyle=\\frac\{\\eta\\pi\_\{\\rm ref\}\(a\\mid x\)\\exp\\\!\\left\(\\eta\\bigl\(R^\{\\star\}\(x,a\)\+\\Delta\_\{R\}\(x,a\)\\bigr\)\\right\)\}\{Z\_\{R\}\(x\)\}=η​πR​\(a∣x\)\.\\displaystyle=\\eta\\pi\_\{R\}\(a\\mid x\)\.Moreover,

∂πR​\(a′∣x\)∂ΔR​\(x,a\)\\displaystyle\\frac\{\\partial\\pi\_\{R\}\(a^\{\\prime\}\\mid x\)\}\{\\partial\\Delta\_\{R\}\(x,a\)\}=∂∂ΔR​\(x,a\)​\(πref​\(a′∣x\)​exp⁡\(η​R​\(x,a′\)\)ZR​\(x\)\)\\displaystyle=\\frac\{\\partial\}\{\\partial\\Delta\_\{R\}\(x,a\)\}\\left\(\\frac\{\\pi\_\{\\rm ref\}\(a^\{\\prime\}\\mid x\)\\exp\\\!\\bigl\(\\eta R\(x,a^\{\\prime\}\)\\bigr\)\}\{Z\_\{R\}\(x\)\}\\right\)=η𝟏\{a′=a\}πref\(a′∣x\)exp\(ηR\(x,a′\)\)ZR​\(x\)−πref​\(a′∣x\)​exp⁡\(η​R​\(x,a′\)\)ZR​\(x\)2​∂ZR​\(x\)∂ΔR​\(x,a\)\\displaystyle=\\frac\{\\eta\\mathbf\{1\}\\\{a^\{\\prime\}=a\\\}\\pi\_\{\\rm ref\}\(a^\{\\prime\}\\mid x\)\\exp\\\!\\bigl\(\\eta R\(x,a^\{\\prime\}\)\\bigr\)\}\{Z\_\{R\}\(x\)\}\-\\frac\{\\pi\_\{\\rm ref\}\(a^\{\\prime\}\\mid x\)\\exp\\\!\\bigl\(\\eta R\(x,a^\{\\prime\}\)\\bigr\)\}\{Z\_\{R\}\(x\)^\{2\}\}\\frac\{\\partial Z\_\{R\}\(x\)\}\{\\partial\\Delta\_\{R\}\(x,a\)\}=ηπR\(a′∣x\)𝟏\{a′=a\}−ηπR\(a′∣x\)πR\(a∣x\)\\displaystyle=\\eta\\pi\_\{R\}\(a^\{\\prime\}\\mid x\)\\mathbf\{1\}\\\{a^\{\\prime\}=a\\\}\-\\eta\\pi\_\{R\}\(a^\{\\prime\}\\mid x\)\\pi\_\{R\}\(a\\mid x\)=ηπR\(a′∣x\)\(𝟏\{a′=a\}−πR\(a∣x\)\)\.\\displaystyle=\\eta\\pi\_\{R\}\(a^\{\\prime\}\\mid x\)\\bigl\(\\mathbf\{1\}\\\{a^\{\\prime\}=a\\\}\-\\pi\_\{R\}\(a\\mid x\)\\bigr\)\.Therefore,

∂𝒥R​\(x\)∂ΔR​\(x,a\)\\displaystyle\\frac\{\\partial\\mathcal\{J\}\_\{R\}\(x\)\}\{\\partial\\Delta\_\{R\}\(x,a\)\}=η​πR​\(a∣x\)−η​πR​\(a∣x\)−η​∑a′∈𝒜ΔR​\(x,a′\)​∂πR​\(a′∣x\)∂ΔR​\(x,a\)\\displaystyle=\\eta\\pi\_\{R\}\(a\\mid x\)\-\\eta\\pi\_\{R\}\(a\\mid x\)\-\\eta\\sum\_\{a^\{\\prime\}\\in\\mathcal\{A\}\}\\Delta\_\{R\}\(x,a^\{\\prime\}\)\\frac\{\\partial\\pi\_\{R\}\(a^\{\\prime\}\\mid x\)\}\{\\partial\\Delta\_\{R\}\(x,a\)\}=−η2∑a′∈𝒜πR\(a′∣x\)\(𝟏\{a′=a\}−πR\(a∣x\)\)ΔR\(x,a′\)\\displaystyle=\-\\eta^\{2\}\\sum\_\{a^\{\\prime\}\\in\\mathcal\{A\}\}\\pi\_\{R\}\(a^\{\\prime\}\\mid x\)\\bigl\(\\mathbf\{1\}\\\{a^\{\\prime\}=a\\\}\-\\pi\_\{R\}\(a\\mid x\)\\bigr\)\\Delta\_\{R\}\(x,a^\{\\prime\}\)=−η2​πR​\(a∣x\)​ΔR​\(x,a\)\+η2​πR​\(a∣x\)​∑a′∈𝒜πR​\(a′∣x\)​ΔR​\(x,a′\)\.\\displaystyle=\-\\eta^\{2\}\\pi\_\{R\}\(a\\mid x\)\\Delta\_\{R\}\(x,a\)\+\\eta^\{2\}\\pi\_\{R\}\(a\\mid x\)\\sum\_\{a^\{\\prime\}\\in\\mathcal\{A\}\}\\pi\_\{R\}\(a^\{\\prime\}\\mid x\)\\Delta\_\{R\}\(x,a^\{\\prime\}\)\.
To apply the mean value theorem, define the interpolationRγ:=γ​R\+\(1−γ\)​R⋆R\_\{\\gamma\}:=\\gamma R\+\(1\-\\gamma\)R^\{\\star\}forγ∈\[0,1\]\\gamma\\in\[0,1\], and letg⁡\(γ\):=𝔼x∼d​\[𝒥Rγ​\(x\)\]g\(\\gamma\):=\\mathbb\{E\}\_\{x\\sim d\}\[\\mathcal\{J\}\_\{R\_\{\\gamma\}\}\(x\)\]\. SinceR0=R⋆R\_\{0\}=R^\{\\star\}andR1=RR\_\{1\}=R, by the one\-dimensional mean value theorem there exists someγ∈\[0,1\]\\gamma\\in\[0,1\]such that, withR′:=Rγ=γ​R\+\(1−γ\)​R⋆R^\{\\prime\}:=R\_\{\\gamma\}=\\gamma R\+\(1\-\\gamma\)R^\{\\star\},

𝔼x∼d​\[𝒥R⋆​\(x\)−𝒥R​\(x\)\]=−g′​\(γ\)\.\\mathbb\{E\}\_\{x\\sim d\}\\left\[\\mathcal\{J\}\_\{R^\{\\star\}\}\(x\)\-\\mathcal\{J\}\_\{R\}\(x\)\\right\]=\-g^\{\\prime\}\(\\gamma\)\.Furthermore,

ΔRγ​\(x,a\)=γ​ΔR​\(x,a\),dd​γ​ΔRγ​\(x,a\)=ΔR​\(x,a\)\.\\Delta\_\{R\_\{\\gamma\}\}\(x,a\)=\\gamma\\Delta\_\{R\}\(x,a\),\\qquad\\frac\{d\}\{d\\gamma\}\\Delta\_\{R\_\{\\gamma\}\}\(x,a\)=\\Delta\_\{R\}\(x,a\)\.In particular, sinceR′=RγR^\{\\prime\}=R\_\{\\gamma\}, we haveΔR′​\(x,a\)=γ​ΔR​\(x,a\)\\Delta\_\{R^\{\\prime\}\}\(x,a\)=\\gamma\\Delta\_\{R\}\(x,a\)\. Therefore,

η−1​𝔼x∼d​\[𝒥R⋆​\(x\)−𝒥R​\(x\)\]\\displaystyle\\eta^\{\-1\}\\mathbb\{E\}\_\{x\\sim d\}\\left\[\\mathcal\{J\}\_\{R^\{\\star\}\}\(x\)\-\\mathcal\{J\}\_\{R\}\(x\)\\right\]=−η−1​𝔼x∼d​\[∑a∈𝒜∂𝒥R′​\(x\)∂ΔR′​\(x,a\)​ΔR​\(x,a\)\]\\displaystyle=\-\\eta^\{\-1\}\\mathbb\{E\}\_\{x\\sim d\}\\left\[\\sum\_\{a\\in\\mathcal\{A\}\}\\frac\{\\partial\\mathcal\{J\}\_\{R^\{\\prime\}\}\(x\)\}\{\\partial\\Delta\_\{R^\{\\prime\}\}\(x,a\)\}\\Delta\_\{R\}\(x,a\)\\right\]=η​γ​𝔼x∼d​\[∑a∈𝒜πR′​\(a∣x\)​ΔR​\(x,a\)2\]\\displaystyle=\\eta\\gamma\\mathbb\{E\}\_\{x\\sim d\}\\left\[\\sum\_\{a\\in\\mathcal\{A\}\}\\pi\_\{R^\{\\prime\}\}\(a\\mid x\)\\Delta\_\{R\}\(x,a\)^\{2\}\\right\]−η​γ​𝔼x∼d​\[∑a1,a2∈𝒜πR′​\(a1∣x\)​πR′​\(a2∣x\)​ΔR​\(x,a1\)​ΔR​\(x,a2\)\]\\displaystyle\-\\eta\\gamma\\mathbb\{E\}\_\{x\\sim d\}\\left\[\\sum\_\{a\_\{1\},a\_\{2\}\\in\\mathcal\{A\}\}\\pi\_\{R^\{\\prime\}\}\(a\_\{1\}\\mid x\)\\pi\_\{R^\{\\prime\}\}\(a\_\{2\}\\mid x\)\\Delta\_\{R\}\(x,a\_\{1\}\)\\Delta\_\{R\}\(x,a\_\{2\}\)\\right\]=ηγ𝔼x∼d\[Vara∼πR′\(⋅∣x\)\(ΔR\(x,a\)\)\]\.\\displaystyle=\\eta\\gamma\\mathbb\{E\}\_\{x\\sim d\}\\left\[\\operatorname\{Var\}\_\{a\\sim\\pi\_\{R^\{\\prime\}\}\(\\cdot\\mid x\)\}\\bigl\(\\Delta\_\{R\}\(x,a\)\\bigr\)\\right\]\.Sinceγ∈\[0,1\]\\gamma\\in\[0,1\], it follows that

η−1​𝔼x∼d​\[𝒥R⋆​\(x\)−𝒥R​\(x\)\]\\displaystyle\\eta^\{\-1\}\\mathbb\{E\}\_\{x\\sim d\}\\left\[\\mathcal\{J\}\_\{R^\{\\star\}\}\(x\)\-\\mathcal\{J\}\_\{R\}\(x\)\\right\]≤η​γ​𝔼x∼d,a∼πR′​\[ΔR​\(x,a\)2\]\\displaystyle\\leq\\eta\\gamma\\mathbb\{E\}\_\{x\\sim d,\\;a\\sim\\pi\_\{R^\{\\prime\}\}\}\\left\[\\Delta\_\{R\}\(x,a\)^\{2\}\\right\]≤η​𝔼x∼d,a∼πR′​\[ΔR​\(x,a\)2\]\.\\displaystyle\\leq\\eta\\mathbb\{E\}\_\{x\\sim d,\\;a\\sim\\pi\_\{R^\{\\prime\}\}\}\\left\[\\Delta\_\{R\}\(x,a\)^\{2\}\\right\]\.The term being subtracted is nonnegative, since

∑a1,a2∈𝒜πR′​\(a1∣x\)​πR′​\(a2∣x\)​ΔR​\(x,a1\)​ΔR​\(x,a2\)=\(∑a∈𝒜πR′​\(a∣x\)​ΔR​\(x,a\)\)2=\(𝔼a∼πR′​\[ΔR​\(x,a\)\]\)2≥0\.\\displaystyle\\sum\_\{a\_\{1\},a\_\{2\}\\in\\mathcal\{A\}\}\\pi\_\{R^\{\\prime\}\}\(a\_\{1\}\\mid x\)\\pi\_\{R^\{\\prime\}\}\(a\_\{2\}\\mid x\)\\Delta\_\{R\}\(x,a\_\{1\}\)\\Delta\_\{R\}\(x,a\_\{2\}\)=\\left\(\\sum\_\{a\\in\\mathcal\{A\}\}\\pi\_\{R^\{\\prime\}\}\(a\\mid x\)\\Delta\_\{R\}\(x,a\)\\right\)^\{2\}=\\left\(\\mathbb\{E\}\_\{a\\sim\\pi\_\{R^\{\\prime\}\}\}\[\\Delta\_\{R\}\(x,a\)\]\\right\)^\{2\}\\geq 0\.Hence,

η−1​𝔼x∼d​\[𝒥R⋆​\(x\)−𝒥R​\(x\)\]≤η​𝔼x∼d,a∼πR′​\[ΔR​\(x,a\)2\]\.\\eta^\{\-1\}\\mathbb\{E\}\_\{x\\sim d\}\\left\[\\mathcal\{J\}\_\{R^\{\\star\}\}\(x\)\-\\mathcal\{J\}\_\{R\}\(x\)\\right\]\\leq\\eta\\mathbb\{E\}\_\{x\\sim d,\\;a\\sim\\pi\_\{R^\{\\prime\}\}\}\\left\[\\Delta\_\{R\}\(x,a\)^\{2\}\\right\]\.Combining this inequality with the previous expression forJRF​\(π⋆\)−JRF​\(πR\)J\_\{\\rm RF\}\(\\pi^\{\\star\}\)\-J\_\{\\rm RF\}\(\\pi\_\{R\}\)yields

JRF​\(π⋆\)−JRF​\(πR\)≤η​𝔼x∼d,a∼πR′​\[\(R⋆​\(x,a\)−R⁡\(x,a\)\)2\]\.J\_\{\\rm RF\}\(\\pi^\{\\star\}\)\-J\_\{\\rm RF\}\(\\pi\_\{R\}\)\\leq\\eta\\mathbb\{E\}\_\{x\\sim d,\\;a\\sim\\pi\_\{R^\{\\prime\}\}\}\\left\[\\left\(R^\{\\star\}\(x,a\)\-R\(x,a\)\\right\)^\{2\}\\right\]\.
Finally, takingR=R^tR=\\widehat\{R\}\_\{t\}, there existsγt∈\[0,1\]\\gamma\_\{t\}\\in\[0,1\]such thatRt′=γt​R^t\+\(1−γt\)​R⋆R\_\{t\}^\{\\prime\}=\\gamma\_\{t\}\\widehat\{R\}\_\{t\}\+\(1\-\\gamma\_\{t\}\)R^\{\\star\}\. SinceπR^t=πt\\pi\_\{\\widehat\{R\}\_\{t\}\}=\\pi\_\{t\}andπRt′=πt′\\pi\_\{R\_\{t\}^\{\\prime\}\}=\\pi\_\{t\}^\{\\prime\}, we obtain

JRF​\(π⋆\)−JRF​\(πt\)≤η​𝔼x∼d,a∼πt′​\[\(R⋆​\(x,a\)−R^t​\(x,a\)\)2\]\.J\_\{\\rm RF\}\(\\pi^\{\\star\}\)\-J\_\{\\rm RF\}\(\\pi\_\{t\}\)\\leq\\eta\\mathbb\{E\}\_\{x\\sim d,\\;a\\sim\\pi\_\{t\}^\{\\prime\}\}\\left\[\\left\(R^\{\\star\}\(x,a\)\-\\widehat\{R\}\_\{t\}\(x,a\)\\right\)^\{2\}\\right\]\.This completes the proof\. ∎

### C\.3Proof of Lemma[3](https://arxiv.org/html/2609.13564#Thmlemma3)

###### Proof of Lemma[3](https://arxiv.org/html/2609.13564#Thmlemma3)\.

Fix anyδ∈\(0,1\)\\delta\\in\(0,1\)\. For eacht≥2t\\geq 2, defineδt:=δ2​t3\\delta\_\{t\}:=\\frac\{\\delta\}\{2t^\{3\}\}\. We first establish a uniform bound overR∈ℛR\\in\\mathcal\{R\}for each fixedtt, and then apply a union bound overtt\.

Fix anyt≥2t\\geq 2andR∈ℛR\\in\\mathcal\{R\}\. For eachi<ti<t, defineYR,i:=\(R⁡\(xi,ai\)−ri\)2−\(R⋆​\(xi,ai\)−ri\)2Y\_\{R,i\}:=\\left\(R\(x\_\{i\},a\_\{i\}\)\-r\_\{i\}\\right\)^\{2\}\-\\left\(R^\{\\star\}\(x\_\{i\},a\_\{i\}\)\-r\_\{i\}\\right\)^\{2\}\. Further defineMR,i:=𝔼⁡\[YR,i∣ℋi−1RF\]−YR,iM\_\{R,i\}:=\\mathbb\{E\}\[Y\_\{R,i\}\\mid\\mathcal\{H\}^\{\\text\{RF\}\}\_\{i\-1\}\]\-Y\_\{R,i\}\. Then\{MR,i\}i≥1\\\{M\_\{R,i\}\\\}\_\{i\\geq 1\}is a martingale difference sequence with respect to\{ℋiRF\}i≥0\\\{\\mathcal\{H\}\_\{i\}^\{\\text\{RF\}\}\\\}\_\{i\\geq 0\}\. Moreover,Var⁡\[MR,i∣ℋi−1RF\]=Var⁡\[YR,i∣ℋi−1RF\]\\operatorname\{Var\}\\left\[M\_\{R,i\}\\mid\\mathcal\{H\}^\{\\text\{RF\}\}\_\{i\-1\}\\right\]=\\operatorname\{Var\}\\left\[Y\_\{R,i\}\\mid\\mathcal\{H\}^\{\\text\{RF\}\}\_\{i\-1\}\\right\]\. SinceRR,R⋆R^\{\\star\}, andrir\_\{i\}are all\[0,1\]\[0,1\]\-valued,\|YR,i\|≤1\|Y\_\{R,i\}\|\\leq 1, and hence\|MR,i\|≤2\|M\_\{R,i\}\|\\leq 2\.

Applying Freedman’s inequality \(Lemma[9](https://arxiv.org/html/2609.13564#Thmlemma9)\) with confidence levelδt/Nℛ\\delta\_\{t\}/N\_\{\\mathcal\{R\}\}yields that, with probability at least1−log2⁡\(t−1\)​δt/Nℛ1\-\\log\_\{2\}\(t\-1\)\\delta\_\{t\}/N\_\{\\mathcal\{R\}\},

∑i=1t−1MR,i\\displaystyle\\sum\_\{i=1\}^\{t\-1\}M\_\{R,i\}≤4​∑i=1t−1Var⁡\[YR,i∣ℋi−1RF\]​log⁡Nℛδt\+4​log⁡Nℛδt\.\\displaystyle\\leq 4\\sqrt\{\\sum\_\{i=1\}^\{t\-1\}\\operatorname\{Var\}\\left\[Y\_\{R,i\}\\mid\\mathcal\{H\}^\{\\text\{RF\}\}\_\{i\-1\}\\right\]\\log\\frac\{N\_\{\\mathcal\{R\}\}\}\{\\delta\_\{t\}\}\}\+4\\log\\frac\{N\_\{\\mathcal\{R\}\}\}\{\\delta\_\{t\}\}\.Substituting the definition ofMR,iM\_\{R,i\}gives

∑i=1t−1𝔼⁡\[YR,i∣ℋi−1RF\]−∑i=1t−1YR,i\\displaystyle\\sum\_\{i=1\}^\{t\-1\}\\mathbb\{E\}\\left\[Y\_\{R,i\}\\mid\\mathcal\{H\}^\{\\text\{RF\}\}\_\{i\-1\}\\right\]\-\\sum\_\{i=1\}^\{t\-1\}Y\_\{R,i\}≤4​∑i=1t−1Var⁡\[YR,i∣ℋi−1RF\]​log⁡Nℛδt\+4​log⁡Nℛδt\.\\displaystyle\\leq 4\\sqrt\{\\sum\_\{i=1\}^\{t\-1\}\\operatorname\{Var\}\\left\[Y\_\{R,i\}\\mid\\mathcal\{H\}^\{\\text\{RF\}\}\_\{i\-1\}\\right\]\\log\\frac\{N\_\{\\mathcal\{R\}\}\}\{\\delta\_\{t\}\}\}\+4\\log\\frac\{N\_\{\\mathcal\{R\}\}\}\{\\delta\_\{t\}\}\.Taking a union bound over allR∈ℛR\\in\\mathcal\{R\}, with probability at least1−log2⁡\(t−1\)​δt1\-\\log\_\{2\}\(t\-1\)\\delta\_\{t\}, the above inequality holds simultaneously for allR∈ℛR\\in\\mathcal\{R\}\.

By Lemma[10](https://arxiv.org/html/2609.13564#Thmlemma10),Var⁡\[YR,i∣ℋi−1RF\]≤4​𝔼​\[YR,i∣ℋi−1RF\]\\operatorname\{Var\}\\left\[Y\_\{R,i\}\\mid\\mathcal\{H\}^\{\\text\{RF\}\}\_\{i\-1\}\\right\]\\leq 4\\mathbb\{E\}\\left\[Y\_\{R,i\}\\mid\\mathcal\{H\}^\{\\text\{RF\}\}\_\{i\-1\}\\right\]\. Therefore,

∑i=1t−1𝔼⁡\[YR,i∣ℋi−1RF\]\\displaystyle\\sum\_\{i=1\}^\{t\-1\}\\mathbb\{E\}\\left\[Y\_\{R,i\}\\mid\\mathcal\{H\}^\{\\text\{RF\}\}\_\{i\-1\}\\right\]≤8∑i=1t−1𝔼⁡\[YR,i∣ℋi−1RF\]​log⁡Nℛδt\+4logNℛδt\+∑i=1t−1YR,i,∀R∈ℛ\.\\displaystyle\\leq 8\\sqrt\{\\sum\_\{i=1\}^\{t\-1\}\\mathbb\{E\}\\left\[Y\_\{R,i\}\\mid\\mathcal\{H\}^\{\\text\{RF\}\}\_\{i\-1\}\\right\]\\log\\frac\{N\_\{\\mathcal\{R\}\}\}\{\\delta\_\{t\}\}\}\+4\\log\\frac\{N\_\{\\mathcal\{R\}\}\}\{\\delta\_\{t\}\}\+\\sum\_\{i=1\}^\{t\-1\}Y\_\{R,i\},\\qquad\\forall R\\in\\mathcal\{R\}\.Rearranging the above inequality and completing the square gives

\(∑i=1t−1𝔼⁡\[YR,i∣ℋi−1RF\]−4​log⁡Nℛδt\)2≤20​log⁡Nℛδt\+∑i=1t−1YR,i\.\\left\(\\sqrt\{\\sum\_\{i=1\}^\{t\-1\}\\mathbb\{E\}\\left\[Y\_\{R,i\}\\mid\\mathcal\{H\}^\{\\text\{RF\}\}\_\{i\-1\}\\right\]\}\-4\\sqrt\{\\log\\frac\{N\_\{\\mathcal\{R\}\}\}\{\\delta\_\{t\}\}\}\\right\)^\{2\}\\leq 20\\log\\frac\{N\_\{\\mathcal\{R\}\}\}\{\\delta\_\{t\}\}\+\\sum\_\{i=1\}^\{t\-1\}Y\_\{R,i\}\.Consequently,

∑i=1t−1𝔼⁡\[YR,i∣ℋi−1RF\]\\displaystyle\\sqrt\{\\sum\_\{i=1\}^\{t\-1\}\\mathbb\{E\}\\left\[Y\_\{R,i\}\\mid\\mathcal\{H\}^\{\\text\{RF\}\}\_\{i\-1\}\\right\]\}≤4​log⁡Nℛδt\+20​log⁡Nℛδt\+∑i=1t−1YR,i\.\\displaystyle\\leq 4\\sqrt\{\\log\\frac\{N\_\{\\mathcal\{R\}\}\}\{\\delta\_\{t\}\}\}\+\\sqrt\{20\\log\\frac\{N\_\{\\mathcal\{R\}\}\}\{\\delta\_\{t\}\}\+\\sum\_\{i=1\}^\{t\-1\}Y\_\{R,i\}\}\.Squaring both sides and using\(a\+b\)2≤2​a2\+2​b2\(a\+b\)^\{2\}\\leq 2a^\{2\}\+2b^\{2\}, we obtain

∑i=1t−1𝔼⁡\[YR,i∣ℋi−1RF\]≤72​log⁡Nℛδt\+2​∑i=1t−1YR,i,∀R∈ℛ\.\\sum\_\{i=1\}^\{t\-1\}\\mathbb\{E\}\\left\[Y\_\{R,i\}\\mid\\mathcal\{H\}^\{\\text\{RF\}\}\_\{i\-1\}\\right\]\\leq 72\\log\\frac\{N\_\{\\mathcal\{R\}\}\}\{\\delta\_\{t\}\}\+2\\sum\_\{i=1\}^\{t\-1\}Y\_\{R,i\},\\qquad\\forall R\\in\\mathcal\{R\}\.
Conditioned onℋi−1RF\\mathcal\{H\}^\{\\text\{RF\}\}\_\{i\-1\}, the context satisfiesxi∼dx\_\{i\}\\sim dand the action is sampled according toai∼πi\(⋅∣xi\)a\_\{i\}\\sim\\pi\_\{i\}\(\\cdot\\mid x\_\{i\}\)\. Hence, by Lemma[10](https://arxiv.org/html/2609.13564#Thmlemma10),𝔼⁡\[YR,i∣ℋi−1RF\]=𝔼x∼d,a∼πi​\[\(R⋆​\(x,a\)−R⁡\(x,a\)\)2\]\\mathbb\{E\}\\left\[Y\_\{R,i\}\\mid\\mathcal\{H\}^\{\\text\{RF\}\}\_\{i\-1\}\\right\]=\\mathbb\{E\}\_\{x\\sim d,\\;a\\sim\\pi\_\{i\}\}\\left\[\\left\(R^\{\\star\}\(x,a\)\-R\(x,a\)\\right\)^\{2\}\\right\]\. It follows that, with probability at least1−log2⁡\(t−1\)​δt1\-\\log\_\{2\}\(t\-1\)\\delta\_\{t\},

∑i=1t−1𝔼x∼d,a∼πi​\[\(R⋆​\(x,a\)−R⁡\(x,a\)\)2\]\\displaystyle\\sum\_\{i=1\}^\{t\-1\}\\mathbb\{E\}\_\{x\\sim d,\\;a\\sim\\pi\_\{i\}\}\\left\[\\left\(R^\{\\star\}\(x,a\)\-R\(x,a\)\\right\)^\{2\}\\right\]≤72​log⁡Nℛδt\+2​∑i=1t−1YR,i,\\displaystyle\\leq 72\\log\\frac\{N\_\{\\mathcal\{R\}\}\}\{\\delta\_\{t\}\}\+2\\sum\_\{i=1\}^\{t\-1\}Y\_\{R,i\},simultaneously for allR∈ℛR\\in\\mathcal\{R\}\.

We now take a union bound overt≥2t\\geq 2\. Since∑t=2∞δt​log2⁡\(t−1\)≤∑t=2∞δ2​t2≤δ\\sum\_\{t=2\}^\{\\infty\}\\delta\_\{t\}\\log\_\{2\}\(t\-1\)\\leq\\sum\_\{t=2\}^\{\\infty\}\\frac\{\\delta\}\{2t^\{2\}\}\\leq\\delta, with probability at least1−δ1\-\\delta, the following holds simultaneously for allt≥2t\\geq 2and allR∈ℛR\\in\\mathcal\{R\}:

∑i=1t−1𝔼x∼d,a∼πi​\[\(R⋆​\(x,a\)−R⁡\(x,a\)\)2\]\\displaystyle\\sum\_\{i=1\}^\{t\-1\}\\mathbb\{E\}\_\{x\\sim d,\\;a\\sim\\pi\_\{i\}\}\\left\[\\left\(R^\{\\star\}\(x,a\)\-R\(x,a\)\\right\)^\{2\}\\right\]≤72​log⁡2​Nℛ​t3δ\+2​∑i=1t−1\[\(R⁡\(xi,ai\)−ri\)2−\(R⋆​\(xi,ai\)−ri\)2\]\.\\displaystyle\\leq 72\\log\\frac\{2N\_\{\\mathcal\{R\}\}t^\{3\}\}\{\\delta\}\+2\\sum\_\{i=1\}^\{t\-1\}\\left\[\\left\(R\(x\_\{i\},a\_\{i\}\)\-r\_\{i\}\\right\)^\{2\}\-\\left\(R^\{\\star\}\(x\_\{i\},a\_\{i\}\)\-r\_\{i\}\\right\)^\{2\}\\right\]\.
For eacht≥2t\\geq 2, takeR=R^tR=\\widehat\{R\}\_\{t\}, whereR^t\\widehat\{R\}\_\{t\}is the LS estimator overℛ\\mathcal\{R\}constructed from\{\(xi,ai,ri\)\}i=1t−1\\\{\(x\_\{i\},a\_\{i\},r\_\{i\}\)\\\}\_\{i=1\}^\{t\-1\}\. SinceR⋆∈ℛR^\{\\star\}\\in\\mathcal\{R\}by Assumption[1](https://arxiv.org/html/2609.13564#Thmassumption1), the optimality ofR^t\\widehat\{R\}\_\{t\}implies

∑i=1t−1\[\(R^t​\(xi,ai\)−ri\)2−\(R⋆​\(xi,ai\)−ri\)2\]≤0\.\\sum\_\{i=1\}^\{t\-1\}\\left\[\\left\(\\widehat\{R\}\_\{t\}\(x\_\{i\},a\_\{i\}\)\-r\_\{i\}\\right\)^\{2\}\-\\left\(R^\{\\star\}\(x\_\{i\},a\_\{i\}\)\-r\_\{i\}\\right\)^\{2\}\\right\]\\leq 0\.Substituting this inequality into the previous display gives

∑i=1t−1𝔼x∼d,a∼πi​\[\(R⋆​\(x,a\)−R^t​\(x,a\)\)2\]≤72​log⁡2​Nℛ​t3δ,\\sum\_\{i=1\}^\{t\-1\}\\mathbb\{E\}\_\{x\\sim d,\\;a\\sim\\pi\_\{i\}\}\\left\[\\left\(R^\{\\star\}\(x,a\)\-\\widehat\{R\}\_\{t\}\(x,a\)\\right\)^\{2\}\\right\]\\leq 72\\log\\frac\{2N\_\{\\mathcal\{R\}\}t^\{3\}\}\{\\delta\},simultaneously for allt≥2t\\geq 2\. In particular, for allt=2,…,Tt=2,\\ldots,T,

∑i=1t−1𝔼x∼d,a∼πi​\[\(R⋆​\(x,a\)−R^t​\(x,a\)\)2\]≤72​log⁡2​Nℛ​T3δ\.\\sum\_\{i=1\}^\{t\-1\}\\mathbb\{E\}\_\{x\\sim d,\\;a\\sim\\pi\_\{i\}\}\\left\[\\left\(R^\{\\star\}\(x,a\)\-\\widehat\{R\}\_\{t\}\(x,a\)\\right\)^\{2\}\\right\]\\leq 72\\log\\frac\{2N\_\{\\mathcal\{R\}\}T^\{3\}\}\{\\delta\}\.This completes the proof\. ∎

### C\.4Proof of Corollary[1](https://arxiv.org/html/2609.13564#Thmcorollary1)

###### Proof of Corollary[1](https://arxiv.org/html/2609.13564#Thmcorollary1)\.

By Lemma[11](https://arxiv.org/html/2609.13564#Thmlemma11), applied with confidence levelδ/2\\delta/2, with probability at least1−δ/21\-\\delta/2, simultaneously for allt∈\[T\]t\\in\[T\],

∑i=1t−1\(R^t​\(xi,ai\)−R⋆​\(xi,ai\)\)2≤8​log⁡2​Nℛ​Tδ\.\\sum\_\{i=1\}^\{t\-1\}\\left\(\\widehat\{R\}\_\{t\}\(x\_\{i\},a\_\{i\}\)\-R^\{\\star\}\(x\_\{i\},a\_\{i\}\)\\right\)^\{2\}\\leq 8\\log\\frac\{2N\_\{\\mathcal\{R\}\}T\}\{\\delta\}\.Condition on this event\. For any\(x,a\)\(x,a\), sinceR^t,R⋆∈ℛ\\widehat\{R\}\_\{t\},R^\{\\star\}\\in\\mathcal\{R\}, the definition of the uncertainty measure gives

\|R⋆​\(x,a\)−R^t​\(x,a\)\|\\displaystyle\\left\|R^\{\\star\}\(x,a\)\-\\widehat\{R\}\_\{t\}\(x,a\)\\right\|≤URF​\(λ,x,a,ℛ,Dt−1RF\)​λ\+∑i=1t−1\(R⋆​\(xi,ai\)−R^t​\(xi,ai\)\)2\.\\displaystyle\\leq U\_\{\\rm RF\}\(\\lambda,x,a,\\mathcal\{R\};D^\{\\text\{RF\}\}\_\{t\-1\}\)\\sqrt\{\\lambda\+\\sum\_\{i=1\}^\{t\-1\}\\left\(R^\{\\star\}\(x\_\{i\},a\_\{i\}\)\-\\widehat\{R\}\_\{t\}\(x\_\{i\},a\_\{i\}\)\\right\)^\{2\}\}\.Usingλ≤8​log⁡2​Nℛ​Tδ\\lambda\\leq 8\\log\\frac\{2N\_\{\\mathcal\{R\}\}T\}\{\\delta\}, we obtain

\(R⋆​\(x,a\)−R^t​\(x,a\)\)2≤16​log⁡2​Nℛ​Tδ​URF2​\(λ,x,a,ℛ,𝒟t−1RF\)\.\\left\(R^\{\\star\}\(x,a\)\-\\widehat\{R\}\_\{t\}\(x,a\)\\right\)^\{2\}\\leq 16\\log\\frac\{2N\_\{\\mathcal\{R\}\}T\}\{\\delta\}\\,U\_\{\\rm RF\}^\{2\}\(\\lambda,x,a,\\mathcal\{R\};\\mathcal\{D\}^\{\\text\{RF\}\}\_\{t\-1\}\)\.Since both reward functions take values in\[0,1\]\[0,1\], the left\-hand side is also at most11\. Hence,

\(R⋆​\(x,a\)−R^t​\(x,a\)\)2≤16​log⁡2​Nℛ​Tδ​min​\{1,URF2​\(λ,x,a,ℛ,𝒟t−1RF\)\}\.\\left\(R^\{\\star\}\(x,a\)\-\\widehat\{R\}\_\{t\}\(x,a\)\\right\)^\{2\}\\leq 16\\log\\frac\{2N\_\{\\mathcal\{R\}\}T\}\{\\delta\}\\min\\left\\\{1,U\_\{\\rm RF\}^\{2\}\(\\lambda,x,a,\\mathcal\{R\};\\mathcal\{D\}^\{\\text\{RF\}\}\_\{t\-1\}\)\\right\\\}\.
Recall thatSt=𝔼x∼d,a∼πt′​\[\(R⋆​\(x,a\)−R^t​\(x,a\)\)2\]S\_\{t\}=\\mathbb\{E\}\_\{x\\sim d,\\;a\\sim\\pi\_\{t\}^\{\\prime\}\}\\left\[\\left\(R^\{\\star\}\(x,a\)\-\\widehat\{R\}\_\{t\}\(x,a\)\\right\)^\{2\}\\right\]\. Therefore,

St\\displaystyle S\_\{t\}≤16​log⁡2​Nℛ​Tδ​𝔼x∼d,a∼πt′​\[min⁡\{1,URF2​\(λ,x,a,ℛ,𝒟t−1RF\)\}\]\.\\displaystyle\\leq 16\\log\\frac\{2N\_\{\\mathcal\{R\}\}T\}\{\\delta\}\\,\\mathbb\{E\}\_\{x\\sim d,\\;a\\sim\\pi\_\{t\}^\{\\prime\}\}\\left\[\\min\\left\\\{1,U\_\{\\rm RF\}^\{2\}\(\\lambda,x,a,\\mathcal\{R\};\\mathcal\{D\}^\{\\text\{RF\}\}\_\{t\-1\}\)\\right\\\}\\right\]\.Sinceπt′\\pi\_\{t\}^\{\\prime\}andπt\\pi\_\{t\}are Gibbs policies induced by\[0,1\]\[0,1\]\-valued reward functions,πt′​\(a∣x\)πt​\(a∣x\)≤e2​η,∀\(x,a\)\\frac\{\\pi\_\{t\}^\{\\prime\}\(a\\mid x\)\}\{\\pi\_\{t\}\(a\\mid x\)\}\\leq e^\{2\\eta\},\\ \\forall\(x,a\), we have

St\\displaystyle S\_\{t\}≤16​e2​η​log⁡2​Nℛ​Tδ​𝔼x∼d,a∼πt​\[min⁡\{1,URF2​\(λ,x,a,ℛ,𝒟t−1RF\)\}\]\.\\displaystyle\\leq 16e^\{2\\eta\}\\log\\frac\{2N\_\{\\mathcal\{R\}\}T\}\{\\delta\}\\mathbb\{E\}\_\{x\\sim d,\\;a\\sim\\pi\_\{t\}\}\\left\[\\min\\left\\\{1,U\_\{\\rm RF\}^\{2\}\(\\lambda,x,a,\\mathcal\{R\};\\mathcal\{D\}^\{\\text\{RF\}\}\_\{t\-1\}\)\\right\\\}\\right\]\.
Now letXt:=min⁡\{1,URF2​\(λ,xt,at,ℛ,𝒟t−1RF\)\}X\_\{t\}:=\\min\\left\\\{1,U\_\{\\rm RF\}^\{2\}\(\\lambda,x\_\{t\},a\_\{t\},\\mathcal\{R\};\\mathcal\{D\}^\{\\text\{RF\}\}\_\{t\-1\}\)\\right\\\}\. Conditioned on the history before roundtt,xt∼dx\_\{t\}\\sim dandat∼πt\(⋅∣xt\)a\_\{t\}\\sim\\pi\_\{t\}\(\\cdot\\mid x\_\{t\}\), and hence𝔼⁡\[Xt∣ℋt−1RF\]=𝔼x∼d,a∼πt​\[min⁡\{1,URF2​\(λ,x,a,ℛ,𝒟t−1RF\)\}\]\\mathbb\{E\}\[X\_\{t\}\\mid\\mathcal\{H\}^\{\\text\{RF\}\}\_\{t\-1\}\]=\\mathbb\{E\}\_\{x\\sim d,\\;a\\sim\\pi\_\{t\}\}\\left\[\\min\\left\\\{1,U\_\{\\rm RF\}^\{2\}\(\\lambda,x,a,\\mathcal\{R\};\\mathcal\{D\}^\{\\text\{RF\}\}\_\{t\-1\}\)\\right\\\}\\right\]\. Moreover, by the definition of the eluder dimension,∑t=1TXt≤dRF​\(λ,ℛ,T\)\\sum\_\{t=1\}^\{T\}X\_\{t\}\\leq d\_\{\\rm RF\}\(\\lambda,\\mathcal\{R\},T\)for every realized sequence\.

SinceXt∈\[0,1\]X\_\{t\}\\in\[0,1\], usinge−x≤1−\(1−e−1\)​xe^\{\-x\}\\leq 1\-\(1\-e^\{\-1\}\)xforx∈\[0,1\]x\\in\[0,1\], we have

𝔼⁡\[e−Xt∣ℋt−1RF\]\\displaystyle\\mathbb\{E\}\\left\[e^\{\-X\_\{t\}\}\\mid\\mathcal\{H\}^\{\\text\{RF\}\}\_\{t\-1\}\\right\]≤1−\(1−e−1\)​𝔼​\[Xt∣ℋt−1RF\]\\displaystyle\\leq 1\-\(1\-e^\{\-1\}\)\\mathbb\{E\}\[X\_\{t\}\\mid\\mathcal\{H\}^\{\\text\{RF\}\}\_\{t\-1\}\]≤exp⁡\(−\(1−e−1\)​𝔼​\[Xt∣ℋt−1RF\]\)\.\\displaystyle\\leq\\exp\\left\(\-\(1\-e^\{\-1\}\)\\mathbb\{E\}\[X\_\{t\}\\mid\\mathcal\{H\}^\{\\text\{RF\}\}\_\{t\-1\}\]\\right\)\.Therefore,

exp⁡\(\(1−e−1\)​∑t=1T𝔼⁡\[Xt∣ℋt−1RF\]−∑t=1TXt\)\\exp\\left\(\(1\-e^\{\-1\}\)\\sum\_\{t=1\}^\{T\}\\mathbb\{E\}\[X\_\{t\}\\mid\\mathcal\{H\}^\{\\text\{RF\}\}\_\{t\-1\}\]\-\\sum\_\{t=1\}^\{T\}X\_\{t\}\\right\)has expectation at most one\. By Markov’s inequality, with probability at least1−δ/21\-\\delta/2,

\(1−e−1\)​∑t=1T𝔼⁡\[Xt∣ℋt−1RF\]−∑t=1TXt≤log⁡2δ\.\(1\-e^\{\-1\}\)\\sum\_\{t=1\}^\{T\}\\mathbb\{E\}\[X\_\{t\}\\mid\\mathcal\{H\}^\{\\text\{RF\}\}\_\{t\-1\}\]\-\\sum\_\{t=1\}^\{T\}X\_\{t\}\\leq\\log\\frac\{2\}\{\\delta\}\.Combining this with the eluder\-dimension bound yields

∑t=1T𝔼⁡\[Xt∣ℋt−1RF\]≤dRF​\(λ,ℛ,T\)\+log⁡2δ1−e−1\.\\sum\_\{t=1\}^\{T\}\\mathbb\{E\}\[X\_\{t\}\\mid\\mathcal\{H\}^\{\\text\{RF\}\}\_\{t\-1\}\]\\leq\\frac\{d\_\{\\rm RF\}\(\\lambda,\\mathcal\{R\},T\)\+\\log\\frac\{2\}\{\\delta\}\}\{1\-e^\{\-1\}\}\.
Taking a union bound over the two high\-probability events, with probability at least1−δ1\-\\delta,

∑t=1TSt≤16​e2​η1−e−1​\(dRF​\(λ,ℛ,T\)\+log⁡2δ\)​log⁡2​Nℛ​Tδ\.\\sum\_\{t=1\}^\{T\}S\_\{t\}\\leq\\frac\{16e^\{2\\eta\}\}\{1\-e^\{\-1\}\}\\left\(d\_\{\\rm RF\}\(\\lambda,\\mathcal\{R\},T\)\+\\log\\frac\{2\}\{\\delta\}\\right\)\\log\\frac\{2N\_\{\\mathcal\{R\}\}T\}\{\\delta\}\.Finally, by Lemma[4](https://arxiv.org/html/2609.13564#Thmlemma4),RegRF⁡\(T\)≤η​∑t=1TSt\\operatorname\{Reg\}\_\{\\rm RF\}\(T\)\\leq\\eta\\sum\_\{t=1\}^\{T\}S\_\{t\}, and therefore

RegRF⁡\(T\)=O⁡\(η​e2​η​\(dRF​\(λ,ℛ,T\)\+log⁡1δ\)​log⁡Nℛ​Tδ\)\.\\operatorname\{Reg\}\_\{\\rm RF\}\(T\)=O\\\!\\left\(\\eta e^\{2\\eta\}\\left\(d\_\{\\rm RF\}\(\\lambda,\\mathcal\{R\},T\)\+\\log\\frac\{1\}\{\\delta\}\\right\)\\log\\frac\{N\_\{\\mathcal\{R\}\}T\}\{\\delta\}\\right\)\.∎

### C\.5Proof of Corollary[4](https://arxiv.org/html/2609.13564#Thmcorollary4)

We next considerK\-UCB\([Zhao et al\., 2025b](https://arxiv.org/html/2609.13564#bib.bib2)\), which augments the least\-squares reward estimate with an uncertainty\-based exploration bonus and selects the Gibbs policy induced by the resulting optimistic reward function\. Specifically, at roundtt, it uses

bt​\(x,a\)=min⁡\{1,URF​\(λ,x,a,ℛ,𝒟t−1RF\)​16​log⁡2​Nℛ​Tδ\},b\_\{t\}\(x,a\)=\\min\\left\\\{1,\\;U\_\{\\rm RF\}\(\\lambda,x,a,\\mathcal\{R\};\\mathcal\{D\}^\{\\text\{RF\}\}\_\{t\-1\}\)\\sqrt\{16\\log\\frac\{2N\_\{\\mathcal\{R\}\}T\}\{\\delta\}\}\\right\\\},and selects

πt​\(a∣x\)∝πref​\(a∣x\)​exp⁡\(η⁡\(R^t​\(x,a\)\+bt​\(x,a\)\)\)\.\\pi\_\{t\}\(a\\mid x\)\\propto\\pi\_\{\\rm ref\}\(a\\mid x\)\\exp\\left\(\\eta\\bigl\(\\widehat\{R\}\_\{t\}\(x,a\)\+b\_\{t\}\(x,a\)\\bigr\)\\right\)\.
###### Corollary 4\(T\\sqrt\{T\}Regret Bound forK\-UCB\)\.

Fix anyλ\>0\\lambda\>0satisfyingλ≤8​log⁡2​Nℛ​Tδ\\lambda\\leq 8\\log\\frac\{2N\_\{\\mathcal\{R\}\}T\}\{\\delta\}\. Then, under Assumption[1](https://arxiv.org/html/2609.13564#Thmassumption1), for anyδ∈\(0,1\)\\delta\\in\(0,1\), with probability at least1−δ1\-\\delta, the regret ofK\-UCBsatisfies

RegRF⁡\(T\)=O⁡\(T⁡\(dRF​\(λ,ℛ,T\)\+log⁡1δ\)​log⁡Nℛ​Tδ\)\.\\operatorname\{Reg\}\_\{\\rm RF\}\(T\)=O\\\!\\left\(\\sqrt\{T\\left\(d\_\{\\rm RF\}\(\\lambda,\\mathcal\{R\},T\)\+\\log\\frac\{1\}\{\\delta\}\\right\)\\log\\frac\{N\_\{\\mathcal\{R\}\}T\}\{\\delta\}\}\\right\)\.

###### Proof of Corollary[4](https://arxiv.org/html/2609.13564#Thmcorollary4)\.

On the same high\-probability confidence event used in the proof of Corollary[1](https://arxiv.org/html/2609.13564#Thmcorollary1), the construction of the bonus ensures

\|R^t​\(x,a\)−R⋆​\(x,a\)\|≤bt​\(x,a\),∀\(x,a\),t∈\[T\]\.\\left\|\\widehat\{R\}\_\{t\}\(x,a\)\-R^\{\\star\}\(x,a\)\\right\|\\leq b\_\{t\}\(x,a\),\\qquad\\forall\(x,a\),\\ t\\in\[T\]\.By optimism and the optimality ofπt\\pi\_\{t\}under the optimistic reward functionR^t\+bt\\widehat\{R\}\_\{t\}\+b\_\{t\}, we have

RegRF⁡\(T\)\\displaystyle\\operatorname\{Reg\}\_\{\\rm RF\}\(T\)≤∑t=1T𝔼x∼d,a∼πt​\[R^t​\(x,a\)\+bt​\(x,a\)−R⋆​\(x,a\)\]\\displaystyle\\leq\\sum\_\{t=1\}^\{T\}\\mathbb\{E\}\_\{x\\sim d,\\;a\\sim\\pi\_\{t\}\}\\left\[\\widehat\{R\}\_\{t\}\(x,a\)\+b\_\{t\}\(x,a\)\-R^\{\\star\}\(x,a\)\\right\]≤2​∑t=1T𝔼x∼d,a∼πt​\[bt​\(x,a\)\]\\displaystyle\\leq 2\\sum\_\{t=1\}^\{T\}\\mathbb\{E\}\_\{x\\sim d,\\;a\\sim\\pi\_\{t\}\}\\left\[b\_\{t\}\(x,a\)\\right\]≤8​log⁡2​Nℛ​Tδ​∑t=1T𝔼x∼d,a∼πt​\[min⁡\{1,URF​\(λ,x,a,ℛ,𝒟t−1RF\)\}\]\.\\displaystyle\\leq 8\\sqrt\{\\log\\frac\{2N\_\{\\mathcal\{R\}\}T\}\{\\delta\}\}\\sum\_\{t=1\}^\{T\}\\mathbb\{E\}\_\{x\\sim d,\\;a\\sim\\pi\_\{t\}\}\\left\[\\min\\left\\\{1,U\_\{\\rm RF\}\(\\lambda,x,a,\\mathcal\{R\};\\mathcal\{D\}^\{\\text\{RF\}\}\_\{t\-1\}\)\\right\\\}\\right\]\.By Cauchy–Schwarz,

RegRF⁡\(T\)\\displaystyle\\operatorname\{Reg\}\_\{\\rm RF\}\(T\)≤8​T​log⁡2​Nℛ​Tδ​∑t=1T𝔼x∼d,a∼πt​\[min⁡\{1,URF2​\(λ,x,a,ℛ,𝒟t−1RF\)\}\]\.\\displaystyle\\leq 8\\sqrt\{T\\log\\frac\{2N\_\{\\mathcal\{R\}\}T\}\{\\delta\}\\sum\_\{t=1\}^\{T\}\\mathbb\{E\}\_\{x\\sim d,\\;a\\sim\\pi\_\{t\}\}\\left\[\\min\\left\\\{1,U\_\{\\rm RF\}^\{2\}\(\\lambda,x,a,\\mathcal\{R\};\\mathcal\{D\}^\{\\text\{RF\}\}\_\{t\-1\}\)\\right\\\}\\right\]\}\.The predictable\-to\-realized uncertainty bound established in the proof of Corollary[1](https://arxiv.org/html/2609.13564#Thmcorollary1)gives, with high probability,

∑t=1T𝔼x∼d,a∼πt​\[min⁡\{1,URF2​\(λ,x,a,ℛ,𝒟t−1RF\)\}\]=O⁡\(dRF​\(λ,ℛ,T\)\+log⁡1δ\)\.\\sum\_\{t=1\}^\{T\}\\mathbb\{E\}\_\{x\\sim d,\\;a\\sim\\pi\_\{t\}\}\\left\[\\min\\left\\\{1,U\_\{\\rm RF\}^\{2\}\(\\lambda,x,a,\\mathcal\{R\};\\mathcal\{D\}^\{\\text\{RF\}\}\_\{t\-1\}\)\\right\\\}\\right\]=O\\\!\\left\(d\_\{\\rm RF\}\(\\lambda,\\mathcal\{R\},T\)\+\\log\\frac\{1\}\{\\delta\}\\right\)\.Substituting this bound into the previous inequality yields

RegRF⁡\(T\)=O⁡\(T⁡\(dRF​\(λ,ℛ,T\)\+log⁡1δ\)​log⁡Nℛ​Tδ\),\\operatorname\{Reg\}\_\{\\rm RF\}\(T\)=O\\\!\\left\(\\sqrt\{T\\left\(d\_\{\\rm RF\}\(\\lambda,\\mathcal\{R\},T\)\+\\log\\frac\{1\}\{\\delta\}\\right\)\\log\\frac\{N\_\{\\mathcal\{R\}\}T\}\{\\delta\}\}\\right\),which completes the proof\. ∎

## Appendix DProofs for Section[5](https://arxiv.org/html/2609.13564#S5)

### D\.1General Preference Model

Recall thatπ^t1\\widehat\{\\pi\}\_\{t\}^\{1\}denotes the symmetric Nash\-equilibrium policy induced byP^t\\widehat\{P\}\_\{t\}, and define its true regularized best response as

π~t2:=arg⁡minπ2​JGP​\(π^t1,π2\)\.\\widetilde\{\\pi\}\_\{t\}^\{2\}:=\\arg\\min\_\{\\pi^\{2\}\}J\_\{\\operatorname\{GP\}\}\\left\(\\widehat\{\\pi\}\_\{t\}^\{1\},\\pi^\{2\}\\right\)\.
#### D\.1\.1Proof of Theorem[2](https://arxiv.org/html/2609.13564#Thmtheorem2)

The proof of Theorem[2](https://arxiv.org/html/2609.13564#Thmtheorem2)relies on the following two key lemmas\. Lemma[5](https://arxiv.org/html/2609.13564#Thmlemma5)establishes the instantaneous KL\-regularized regret decomposition under the GP model, while Lemma[6](https://arxiv.org/html/2609.13564#Thmlemma6)provides the uniform convergence guarantee for the MLE estimator under the GP model\.

###### Lemma 5\(Instantaneous Regret Decomposition for the General Preference Model\)\.

For allt∈\[T\]t\\in\[T\], the instantaneous regret under the GP setting satisfies

JGP⋆−JGP​\(π^t1,π~t2\)≤2​η​eη​𝔼x∼d,a1∼π^t1,a2∼πref​\[\(P⋆​\(x,a1,a2\)−P^t​\(x,a1,a2\)\)2\]\.J\_\{\\mathrm\{GP\}\}^\{\\star\}\-J\_\{\\mathrm\{GP\}\}\(\\widehat\{\\pi\}\_\{t\}^\{1\},\\widetilde\{\\pi\}\_\{t\}^\{2\}\)\\leq 2\\eta e^\{\\eta\}\\mathbb\{E\}\_\{\\begin\{subarray\}\{c\}x\\sim d,\\,a^\{1\}\\sim\\widehat\{\\pi\}\_\{t\}^\{1\},\\,a^\{2\}\\sim\\pi\_\{\\mathrm\{ref\}\}\\end\{subarray\}\}\\left\[\\left\(P^\{\\star\}\(x,a^\{1\},a^\{2\}\)\-\\widehat\{P\}\_\{t\}\(x,a^\{1\},a^\{2\}\)\\right\)^\{2\}\\right\]\.

###### Lemma 6\(Uniform Prediction Error Bound, General Preference Model\)\.

Suppose Assumption[2](https://arxiv.org/html/2609.13564#Thmassumption2)holds\. LetP^t\\widehat\{P\}\_\{t\}be the MLE estimator constructed from the samples generated byORLHF\-GSunder the GP model, where, conditionally onℋi−1GP\\mathcal\{H\}\_\{i\-1\}^\{\\rm GP\}andxix\_\{i\},ai1a\_\{i\}^\{1\}andai2a\_\{i\}^\{2\}are sampled independently according toπ^i1\(⋅∣xi\)\\widehat\{\\pi\}\_\{i\}^\{1\}\(\\cdot\\mid x\_\{i\}\)andπref\(⋅∣xi\)\\pi\_\{\\rm ref\}\(\\cdot\\mid x\_\{i\}\), respectively\. Then for any such policy sequence\{π^i1\}i≥1\\\{\\widehat\{\\pi\}\_\{i\}^\{1\}\\\}\_\{i\\geq 1\}and anyδ∈\(0,1\)\\delta\\in\(0,1\), with probability at least1−δ1\-\\delta, the following holds simultaneously for allt=2,…,Tt=2,\\dots,T:

∑i=1t−1𝔼x∼d,a1∼π^i1,a2∼πref​\[\(P⋆​\(x,a1,a2\)−P^t​\(x,a1,a2\)\)2\]≤6​log⁡2​N𝒫​T3δ\.\\sum\_\{i=1\}^\{t\-1\}\\mathbb\{E\}\_\{x\\sim d,\\;a^\{1\}\\sim\\widehat\{\\pi\}\_\{i\}^\{1\},\\;a^\{2\}\\sim\\pi\_\{\\operatorname\{ref\}\}\}\\left\[\\left\(P^\{\\star\}\(x,a^\{1\},a^\{2\}\)\-\\widehat\{P\}\_\{t\}\(x,a^\{1\},a^\{2\}\)\\right\)^\{2\}\\right\]\\leq 6\\log\\frac\{2N\_\{\\mathcal\{P\}\}T^\{3\}\}\{\\delta\}\.

###### Proof of Theorem[2](https://arxiv.org/html/2609.13564#Thmtheorem2)\.

For eacht∈\[T\]t\\in\[T\], defineSt:=𝔼x∼d,a1∼π^t1,a2∼πref​\[\(P⋆​\(x,a1,a2\)−P^t​\(x,a1,a2\)\)2\]S\_\{t\}:=\\mathbb\{E\}\_\{\\begin\{subarray\}\{c\}x\\sim d,\\,a^\{1\}\\sim\\widehat\{\\pi\}\_\{t\}^\{1\},\\ a^\{2\}\\sim\\pi\_\{\\rm ref\}\\end\{subarray\}\}\\left\[\\bigl\(P^\{\\star\}\(x,a^\{1\},a^\{2\}\)\-\\widehat\{P\}\_\{t\}\(x,a^\{1\},a^\{2\}\)\\bigr\)^\{2\}\\right\]\. By Lemma[5](https://arxiv.org/html/2609.13564#Thmlemma5),

RegGP⁡\(T\)=O⁡\(η​eη​∑t=1TSt\)\.\\operatorname\{Reg\}\_\{\\rm GP\}\(T\)=O\\\!\\left\(\\eta e^\{\\eta\}\\sum\_\{t=1\}^\{T\}S\_\{t\}\\right\)\.\(12\)
We establish two different bounds on∑t=1TSt\\sum\_\{t=1\}^\{T\}S\_\{t\}\.

##### Dimension\-independent bound\.

By Lemma[6](https://arxiv.org/html/2609.13564#Thmlemma6), with probability at least1−δ1\-\\delta, simultaneously for allt=2,…,Tt=2,\\ldots,T,

∑i=1t−1𝔼x∼d,a1∼π^i1,a2∼πref​\[\(P⋆​\(x,a1,a2\)−P^t​\(x,a1,a2\)\)2\]≤6​log⁡2​N𝒫​T3δ\.\\sum\_\{i=1\}^\{t\-1\}\\mathbb\{E\}\_\{\\begin\{subarray\}\{c\}x\\sim d,\\,a^\{1\}\\sim\\widehat\{\\pi\}\_\{i\}^\{1\},\\ a^\{2\}\\sim\\pi\_\{\\rm ref\}\\end\{subarray\}\}\\left\[\\bigl\(P^\{\\star\}\(x,a^\{1\},a^\{2\}\)\-\\widehat\{P\}\_\{t\}\(x,a^\{1\},a^\{2\}\)\\bigr\)^\{2\}\\right\]\\leq 6\\log\\frac\{2N\_\{\\mathcal\{P\}\}T^\{3\}\}\{\\delta\}\.For anyi<ti<t, the Gibbs\-policy likelihood\-ratio bound givesπ^t1​\(a∣x\)π^i1​\(a∣x\)≤e2​η\\frac\{\\widehat\{\\pi\}\_\{t\}^\{1\}\(a\\mid x\)\}\{\\widehat\{\\pi\}\_\{i\}^\{1\}\(a\\mid x\)\}\\leq e^\{2\\eta\}\. Therefore,

St≤6​e2​ηt−1​log⁡2​N𝒫​T3δ,t≥2\.S\_\{t\}\\leq\\frac\{6e^\{2\\eta\}\}\{t\-1\}\\log\\frac\{2N\_\{\\mathcal\{P\}\}T^\{3\}\}\{\\delta\},\\qquad t\\geq 2\.SinceS1≤1S\_\{1\}\\leq 1,

∑t=1TSt=O⁡\(e2​η​log⁡T​log⁡N𝒫​Tδ\)\.\\sum\_\{t=1\}^\{T\}S\_\{t\}=O\\\!\\left\(e^\{2\\eta\}\\log T\\log\\frac\{N\_\{\\mathcal\{P\}\}T\}\{\\delta\}\\right\)\.Substituting into \([12](https://arxiv.org/html/2609.13564#A4.E12)\) yields

RegGP⁡\(T\)=O⁡\(\(η​e3​η\)​log⁡T​log⁡N𝒫​Tδ\)\.\\operatorname\{Reg\}\_\{\\rm GP\}\(T\)=O\\\!\\left\(\(\\eta e^\{3\\eta\}\)\\log T\\log\\frac\{N\_\{\\mathcal\{P\}\}T\}\{\\delta\}\\right\)\.

##### Eluder\-dimension\-dependent bound\.

By Lemma[12](https://arxiv.org/html/2609.13564#Thmlemma12), with probability at least1−δ/21\-\\delta/2, simultaneously for allt∈\[T\]t\\in\[T\],

∑i=1t−1\(P^t​\(xi,ai1,ai2\)−P⋆​\(xi,ai1,ai2\)\)2≤2​log⁡2​N𝒫​Tδ\.\\sum\_\{i=1\}^\{t\-1\}\\bigl\(\\widehat\{P\}\_\{t\}\(x\_\{i\},a\_\{i\}^\{1\},a\_\{i\}^\{2\}\)\-P^\{\\star\}\(x\_\{i\},a\_\{i\}^\{1\},a\_\{i\}^\{2\}\)\\bigr\)^\{2\}\\leq 2\\log\\frac\{2N\_\{\\mathcal\{P\}\}T\}\{\\delta\}\.Fix any\(x,a1,a2\)\(x,a^\{1\},a^\{2\}\)\. SinceP^t,P⋆∈𝒫\\widehat\{P\}\_\{t\},P^\{\\star\}\\in\\mathcal\{P\}, the definition ofUGPU\_\{\\rm GP\}implies

\(P^t​\(x,a1,a2\)−P⋆​\(x,a1,a2\)\)2≤UGP2​\(λ,x,a1,a2,𝒫,𝒟t−1GP\)​\[λ\+∑i=1t−1\(P^t​\(xi,ai1,ai2\)−P⋆​\(xi,ai1,ai2\)\)2\]\.\\displaystyle\\bigl\(\\widehat\{P\}\_\{t\}\(x,a^\{1\},a^\{2\}\)\-P^\{\\star\}\(x,a^\{1\},a^\{2\}\)\\bigr\)^\{2\}\\leq U\_\{\\rm GP\}^\{2\}\(\\lambda,x,a^\{1\},a^\{2\},\\mathcal\{P\};\\mathcal\{D\}^\{\\text\{GP\}\}\_\{t\-1\}\)\\left\[\\lambda\+\\sum\_\{i=1\}^\{t\-1\}\\bigl\(\\widehat\{P\}\_\{t\}\(x\_\{i\},a\_\{i\}^\{1\},a\_\{i\}^\{2\}\)\-P^\{\\star\}\(x\_\{i\},a\_\{i\}^\{1\},a\_\{i\}^\{2\}\)\\bigr\)^\{2\}\\right\]\.Hence, forλ≤log⁡2​N𝒫​Tδ\\lambda\\leq\\log\\frac\{2N\_\{\\mathcal\{P\}\}T\}\{\\delta\}, using\|P^t−P⋆\|≤1\|\\widehat\{P\}\_\{t\}\-P^\{\\star\}\|\\leq 1,

\(P^t​\(x,a1,a2\)−P⋆​\(x,a1,a2\)\)2≤3​log⁡2​N𝒫​Tδ​min​\{1,UGP2​\(λ,x,a1,a2,𝒫,𝒟t−1GP\)\}\.\\bigl\(\\widehat\{P\}\_\{t\}\(x,a^\{1\},a^\{2\}\)\-P^\{\\star\}\(x,a^\{1\},a^\{2\}\)\\bigr\)^\{2\}\\leq 3\\log\\frac\{2N\_\{\\mathcal\{P\}\}T\}\{\\delta\}\\min\\\!\\left\\\{1,U\_\{\\rm GP\}^\{2\}\(\\lambda,x,a^\{1\},a^\{2\},\\mathcal\{P\};\\mathcal\{D\}^\{\\text\{GP\}\}\_\{t\-1\}\)\\right\\\}\.Consequently,

St≤3​log⁡2​N𝒫​Tδ​𝔼x∼d,a1∼π^t1,a2∼πref​\[min⁡\{1,UGP2​\(λ,x,a1,a2,𝒫,𝒟t−1GP\)\}\]\.S\_\{t\}\\leq 3\\log\\frac\{2N\_\{\\mathcal\{P\}\}T\}\{\\delta\}\\,\\mathbb\{E\}\_\{\\begin\{subarray\}\{c\}x\\sim d,\\,a^\{1\}\\sim\\widehat\{\\pi\}\_\{t\}^\{1\},\\ a^\{2\}\\sim\\pi\_\{\\rm ref\}\\end\{subarray\}\}\\left\[\\min\\\!\\left\\\{1,U\_\{\\rm GP\}^\{2\}\(\\lambda,x,a^\{1\},a^\{2\},\\mathcal\{P\};\\mathcal\{D\}^\{\\text\{GP\}\}\_\{t\-1\}\)\\right\\\}\\right\]\.
Applying the same predictable\-to\-realized concentration argument as in the proof of Corollary[1](https://arxiv.org/html/2609.13564#Thmcorollary1)with confidence levelδ/2\\delta/2, together with the definition ofdGP​\(λ,𝒫,T\)d\_\{\\rm GP\}\(\\lambda,\\mathcal\{P\},T\), and taking a union bound with the preceding MLE confidence event, yields, with probability at least1−δ1\-\\delta,

∑t=1TSt=O⁡\(\(dGP​\(λ,𝒫,T\)\+log⁡1δ\)​log⁡N𝒫​Tδ\)\.\\sum\_\{t=1\}^\{T\}S\_\{t\}=O\\\!\\left\(\\left\(d\_\{\\rm GP\}\(\\lambda,\\mathcal\{P\},T\)\+\\log\\frac\{1\}\{\\delta\}\\right\)\\log\\frac\{N\_\{\\mathcal\{P\}\}T\}\{\\delta\}\\right\)\.Substituting this bound into \([12](https://arxiv.org/html/2609.13564#A4.E12)\) gives

RegGP⁡\(T\)=O⁡\(η​eη​\(dGP​\(λ,𝒫,T\)\+log⁡1δ\)​log⁡N𝒫​Tδ\)\.\\operatorname\{Reg\}\_\{\\rm GP\}\(T\)=O\\\!\\left\(\\eta e^\{\\eta\}\\left\(d\_\{\\rm GP\}\(\\lambda,\\mathcal\{P\},T\)\+\\log\\frac\{1\}\{\\delta\}\\right\)\\log\\frac\{N\_\{\\mathcal\{P\}\}T\}\{\\delta\}\\right\)\.∎

#### D\.1\.2Proof of Lemma[5](https://arxiv.org/html/2609.13564#Thmlemma5)

###### Proof of Lemma[5](https://arxiv.org/html/2609.13564#Thmlemma5)\.

For brevity, denote the instantaneous regret on the left\-hand side byGt:=JGP⋆−JGP​\(π^t1,π~t2\)G\_\{t\}:=J\_\{\\mathrm\{GP\}\}^\{\\star\}\-J\_\{\\mathrm\{GP\}\}\(\\widehat\{\\pi\}\_\{t\}^\{1\},\\widetilde\{\\pi\}\_\{t\}^\{2\}\)\.

By reciprocity, for anyP∈𝒫P\\in\\mathcal\{P\}and any policyπ\\pi,

P⁡\(x,π,π\)=𝔼a1,a2∼π​\[P⁡\(x,a1,a2\)\]=12\.P\(x,\\pi,\\pi\)=\\mathbb\{E\}\_\{a^\{1\},a^\{2\}\\sim\\pi\}\[P\(x,a^\{1\},a^\{2\}\)\]=\\frac\{1\}\{2\}\.Indeed, exchanginga1a^\{1\}anda2a^\{2\}does not change their joint distribution, whileP⁡\(x,a1,a2\)\+P⁡\(x,a2,a1\)=1P\(x,a^\{1\},a^\{2\}\)\+P\(x,a^\{2\},a^\{1\}\)=1\. Moreover, when the two policies coincide, the two KL\-regularization terms inJGPJ\_\{\\mathrm\{GP\}\}cancel\. Consequently,JGP​\(π,π\)=12J\_\{\\mathrm\{GP\}\}\(\\pi,\\pi\)=\\frac\{1\}\{2\}for everyπ\\pi, and in particularJGP⋆=JGP​\(π^t1,π^t1\)=12J\_\{\\mathrm\{GP\}\}^\{\\star\}=J\_\{\\mathrm\{GP\}\}\(\\widehat\{\\pi\}\_\{t\}^\{1\},\\widehat\{\\pi\}\_\{t\}^\{1\}\)=\\frac\{1\}\{2\}\. Therefore,

Gt=JGP​\(π^t1,π^t1\)−JGP​\(π^t1,π~t2\)\.G\_\{t\}=J\_\{\\mathrm\{GP\}\}\(\\widehat\{\\pi\}\_\{t\}^\{1\},\\widehat\{\\pi\}\_\{t\}^\{1\}\)\-J\_\{\\mathrm\{GP\}\}\(\\widehat\{\\pi\}\_\{t\}^\{1\},\\widetilde\{\\pi\}\_\{t\}^\{2\}\)\.\(13\)
Sinceπ^t1\\widehat\{\\pi\}\_\{t\}^\{1\}is the symmetric Nash\-equilibrium policy induced byP^t\\widehat\{P\}\_\{t\}, it is also the minimizing player’s regularized best response to itself underP^t\\widehat\{P\}\_\{t\}\. Hence,

𝔼x∼d​\[P^t​\(x,π^t1,π^t1\)\+η−1​KL⁡\(π^t1,πref∣x\)\]≤𝔼x∼d​\[P^t​\(x,π^t1,π~t2\)\+η−1​KL⁡\(π~t2,πref∣x\)\]\.\\displaystyle\\mathbb\{E\}\_\{x\\sim d\}\\left\[\\widehat\{P\}\_\{t\}\(x,\\widehat\{\\pi\}\_\{t\}^\{1\},\\widehat\{\\pi\}\_\{t\}^\{1\}\)\+\\eta^\{\-1\}\\operatorname\{KL\}\(\\widehat\{\\pi\}\_\{t\}^\{1\},\\pi\_\{\\mathrm\{ref\}\}\\mid x\)\\right\]\\leq\\mathbb\{E\}\_\{x\\sim d\}\\left\[\\widehat\{P\}\_\{t\}\(x,\\widehat\{\\pi\}\_\{t\}^\{1\},\\widetilde\{\\pi\}\_\{t\}^\{2\}\)\+\\eta^\{\-1\}\\operatorname\{KL\}\(\\widetilde\{\\pi\}\_\{t\}^\{2\},\\pi\_\{\\mathrm\{ref\}\}\\mid x\)\\right\]\.\(14\)Combining \([13](https://arxiv.org/html/2609.13564#A4.E13)\) and \([14](https://arxiv.org/html/2609.13564#A4.E14)\) gives

Gt≤𝔼x∼d\[\\displaystyle G\_\{t\}\\leq\\mathbb\{E\}\_\{x\\sim d\}\\Big\[\(P⋆−P^t\)\(x,π^t1,π^t1\)−\(P⋆−P^t\)\(x,π^t1,π~t2\)\]\.\\displaystyle\\big\(P^\{\\star\}\-\\widehat\{P\}\_\{t\}\\big\)\(x,\\widehat\{\\pi\}\_\{t\}^\{1\},\\widehat\{\\pi\}\_\{t\}^\{1\}\)\-\\big\(P^\{\\star\}\-\\widehat\{P\}\_\{t\}\\big\)\(x,\\widehat\{\\pi\}\_\{t\}^\{1\},\\widetilde\{\\pi\}\_\{t\}^\{2\}\)\\Big\]\.\(15\)
By the reciprocity identity above, the first term in \([15](https://arxiv.org/html/2609.13564#A4.E15)\) is zero\. Expanding the remaining term gives

Gt≤𝔼x∼d\[∑a2∈𝒜\\displaystyle G\_\{t\}\\leq\\mathbb\{E\}\_\{x\\sim d\}\\Bigg\[\\sum\_\{a^\{2\}\\in\\mathcal\{A\}\}\(π^t1\(a2∣x\)−π~t2\(a2∣x\)\)𝔼a1∼π^t1\[P⋆\(x,a1,a2\)−P^t\(x,a1,a2\)\]\]\.\\displaystyle\\Big\(\\widehat\{\\pi\}\_\{t\}^\{1\}\(a^\{2\}\\mid x\)\-\\widetilde\{\\pi\}\_\{t\}^\{2\}\(a^\{2\}\\mid x\)\\Big\)\\mathbb\{E\}\_\{a^\{1\}\\sim\\widehat\{\\pi\}\_\{t\}^\{1\}\}\\left\[P^\{\\star\}\(x,a^\{1\},a^\{2\}\)\-\\widehat\{P\}\_\{t\}\(x,a^\{1\},a^\{2\}\)\\right\]\\Bigg\]\.\(16\)
We next control the policy difference in \([16](https://arxiv.org/html/2609.13564#A4.E16)\) using the KL regularization\. For every contextxx, the true regularized best response satisfies

π~t2​\(a2∣x\)=πref​\(a2∣x\)​exp⁡\(−η​P⋆​\(x,π^t1,a2\)\)∑a′πref​\(a′∣x\)​exp⁡\(−η​P⋆​\(x,π^t1,a′\)\)\.\\widetilde\{\\pi\}\_\{t\}^\{2\}\(a^\{2\}\\mid x\)=\\frac\{\\pi\_\{\\mathrm\{ref\}\}\(a^\{2\}\\mid x\)\\exp\(\-\\eta P^\{\\star\}\(x,\\widehat\{\\pi\}\_\{t\}^\{1\},a^\{2\}\)\)\}\{\\sum\_\{a^\{\\prime\}\}\\pi\_\{\\mathrm\{ref\}\}\(a^\{\\prime\}\\mid x\)\\exp\(\-\\eta P^\{\\star\}\(x,\\widehat\{\\pi\}\_\{t\}^\{1\},a^\{\\prime\}\)\)\}\.Hence,

P⋆​\(x,π^t1,a2\)=−η−1​log⁡π~t2​\(a2∣x\)πref​\(a2∣x\)\+Cx,P^\{\\star\}\(x,\\widehat\{\\pi\}\_\{t\}^\{1\},a^\{2\}\)=\-\\eta^\{\-1\}\\log\\frac\{\\widetilde\{\\pi\}\_\{t\}^\{2\}\(a^\{2\}\\mid x\)\}\{\\pi\_\{\\mathrm\{ref\}\}\(a^\{2\}\\mid x\)\}\+C\_\{x\},whereCx:=−η−1​log⁡\(∑a′πref​\(a′∣x\)​exp⁡\(−η​P⋆​\(x,π^t1,a′\)\)\)C\_\{x\}:=\-\\eta^\{\-1\}\\log\\left\(\\sum\_\{a^\{\\prime\}\}\\pi\_\{\\mathrm\{ref\}\}\(a^\{\\prime\}\\mid x\)\\exp\(\-\\eta P^\{\\star\}\(x,\\widehat\{\\pi\}\_\{t\}^\{1\},a^\{\\prime\}\)\)\\right\)is independent ofa2a^\{2\}\. Therefore, for any policyπ\\pi,

P⋆​\(x,π^t1,π\)\+η−1​KL⁡\(π,πref∣x\)=η−1​KL⁡\(π,π~t2∣x\)\+Cx\.\\displaystyle P^\{\\star\}\(x,\\widehat\{\\pi\}\_\{t\}^\{1\},\\pi\)\+\\eta^\{\-1\}\\operatorname\{KL\}\(\\pi,\\pi\_\{\\mathrm\{ref\}\}\\mid x\)=\\eta^\{\-1\}\\operatorname\{KL\}\(\\pi,\\widetilde\{\\pi\}\_\{t\}^\{2\}\\mid x\)\+C\_\{x\}\.\(17\)Since the KL divergence is nonnegative and vanishes atπ=π~t2\\pi=\\widetilde\{\\pi\}\_\{t\}^\{2\}, the minimum of the left\-hand side of \([17](https://arxiv.org/html/2609.13564#A4.E17)\) overπ\\piisCxC\_\{x\}\. Takingπ=π^t1\\pi=\\widehat\{\\pi\}\_\{t\}^\{1\}therefore gives

P⋆​\(x,π^t1,π^t1\)\+η−1​KL⁡\(π^t1,πref∣x\)−minπ⁡\{P⋆​\(x,π^t1,π\)\+η−1​KL⁡\(π,πref∣x\)\}=η−1​KL⁡\(π^t1,π~t2∣x\)\.\\displaystyle P^\{\\star\}\(x,\\widehat\{\\pi\}\_\{t\}^\{1\},\\widehat\{\\pi\}\_\{t\}^\{1\}\)\+\\eta^\{\-1\}\\operatorname\{KL\}\(\\widehat\{\\pi\}\_\{t\}^\{1\},\\pi\_\{\\mathrm\{ref\}\}\\mid x\)\-\\min\_\{\\pi\}\\left\\\{P^\{\\star\}\(x,\\widehat\{\\pi\}\_\{t\}^\{1\},\\pi\)\+\\eta^\{\-1\}\\operatorname\{KL\}\(\\pi,\\pi\_\{\\mathrm\{ref\}\}\\mid x\)\\right\\\}=\\eta^\{\-1\}\\operatorname\{KL\}\(\\widehat\{\\pi\}\_\{t\}^\{1\},\\widetilde\{\\pi\}\_\{t\}^\{2\}\\mid x\)\.\(18\)Averaging overxxand using \([13](https://arxiv.org/html/2609.13564#A4.E13)\) yields the exact identity

Gt=η−1​𝔼x∼d​\[KL⁡\(π^t1,π~t2∣x\)\]\.G\_\{t\}=\\eta^\{\-1\}\\mathbb\{E\}\_\{x\\sim d\}\\left\[\\operatorname\{KL\}\(\\widehat\{\\pi\}\_\{t\}^\{1\},\\widetilde\{\\pi\}\_\{t\}^\{2\}\\mid x\)\\right\]\.\(19\)
We now lower bound the KL divergence by a weighted squared distance\. Bothπ^t1\\widehat\{\\pi\}\_\{t\}^\{1\}andπ~t2\\widetilde\{\\pi\}\_\{t\}^\{2\}are Gibbs policies induced by scores with range at most one\. Hence, for every\(x,a\)\(x,a\),

π^t1​\(a∣x\)≤eη​πref​\(a∣x\),π~t2​\(a∣x\)≤eη​πref​\(a∣x\)\.\\widehat\{\\pi\}\_\{t\}^\{1\}\(a\\mid x\)\\leq e^\{\\eta\}\\pi\_\{\\mathrm\{ref\}\}\(a\\mid x\),\\qquad\\widetilde\{\\pi\}\_\{t\}^\{2\}\(a\\mid x\)\\leq e^\{\\eta\}\\pi\_\{\\mathrm\{ref\}\}\(a\\mid x\)\.Fors∈\[0,1\]s\\in\[0,1\], letπs\(⋅∣x\):=\(1−s\)π~t2\(⋅∣x\)\+sπ^t1\(⋅∣x\)\\pi\_\{s\}\(\\cdot\\mid x\):=\(1\-s\)\\widetilde\{\\pi\}\_\{t\}^\{2\}\(\\cdot\\mid x\)\+s\\widehat\{\\pi\}\_\{t\}^\{1\}\(\\cdot\\mid x\)\. Thenπs​\(a∣x\)≤eη​πref​\(a∣x\)\\pi\_\{s\}\(a\\mid x\)\\leq e^\{\\eta\}\\pi\_\{\\mathrm\{ref\}\}\(a\\mid x\)\. Since the Hessian of the negative entropyF⁡\(p\):=∑ap⁡\(a\)​log⁡p⁡\(a\)F\(p\):=\\sum\_\{a\}p\(a\)\\log p\(a\)is∇2F​\(p\)=diag⁡\(1/p⁡\(a\)\)\\nabla^\{2\}F\(p\)=\\operatorname\{diag\}\(1/p\(a\)\), we have

∇2F\(πs\(⋅∣x\)\)⪰e−ηdiag\(1πref​\(a∣x\)\)\.\\nabla^\{2\}F\(\\pi\_\{s\}\(\\cdot\\mid x\)\)\\succeq e^\{\-\\eta\}\\operatorname\{diag\}\\left\(\\frac\{1\}\{\\pi\_\{\\mathrm\{ref\}\}\(a\\mid x\)\}\\right\)\.Moreover, since the KL divergence is the Bregman divergence induced byFF, its integral second\-order representation gives

KL⁡\(π^t1,π~t2∣x\)\\displaystyle\\operatorname\{KL\}\(\\widehat\{\\pi\}\_\{t\}^\{1\},\\widetilde\{\\pi\}\_\{t\}^\{2\}\\mid x\)=∫01\(1−s\)​\(π^t1−π~t2\)⊤​∇2F​\(πs\)​\(π^t1−π~t2\)​𝑑s\\displaystyle=\\int\_\{0\}^\{1\}\(1\-s\)\\big\(\\widehat\{\\pi\}\_\{t\}^\{1\}\-\\widetilde\{\\pi\}\_\{t\}^\{2\}\\big\)^\{\\top\}\\nabla^\{2\}F\(\\pi\_\{s\}\)\\big\(\\widehat\{\\pi\}\_\{t\}^\{1\}\-\\widetilde\{\\pi\}\_\{t\}^\{2\}\\big\)\\,ds≥e−η2​∑a∈𝒜\(π^t1​\(a∣x\)−π~t2​\(a∣x\)\)2πref​\(a∣x\),\\displaystyle\\geq\\frac\{e^\{\-\\eta\}\}\{2\}\\sum\_\{a\\in\\mathcal\{A\}\}\\frac\{\\big\(\\widehat\{\\pi\}\_\{t\}^\{1\}\(a\\mid x\)\-\\widetilde\{\\pi\}\_\{t\}^\{2\}\(a\\mid x\)\\big\)^\{2\}\}\{\\pi\_\{\\mathrm\{ref\}\}\(a\\mid x\)\},\(20\)where we used∫01\(1−s\)​𝑑s=1/2\\int\_\{0\}^\{1\}\(1\-s\)\\,ds=1/2\. Combining \([19](https://arxiv.org/html/2609.13564#A4.E19)\) and \([20](https://arxiv.org/html/2609.13564#A4.E20)\), we obtain

𝔼x∼d​\[∑a∈𝒜\(π^t1​\(a∣x\)−π~t2​\(a∣x\)\)2πref​\(a∣x\)\]≤2​η​eη​Gt\.\\displaystyle\\mathbb\{E\}\_\{x\\sim d\}\\left\[\\sum\_\{a\\in\\mathcal\{A\}\}\\frac\{\\big\(\\widehat\{\\pi\}\_\{t\}^\{1\}\(a\\mid x\)\-\\widetilde\{\\pi\}\_\{t\}^\{2\}\(a\\mid x\)\\big\)^\{2\}\}\{\\pi\_\{\\mathrm\{ref\}\}\(a\\mid x\)\}\\right\]\\leq 2\\eta e^\{\\eta\}G\_\{t\}\.\(21\)
Finally, applying weighted Cauchy–Schwarz overa2a^\{2\}, followed by Cauchy–Schwarz overxx, to \([16](https://arxiv.org/html/2609.13564#A4.E16)\) gives

Gt≤\\displaystyle G\_\{t\}\\leq\(𝔼x∼d​\[∑a2∈𝒜\(π^t1​\(a2∣x\)−π~t2​\(a2∣x\)\)2πref​\(a2∣x\)\]\)1/2​\(𝔼x∼d,a2∼πref​\[\(𝔼a1∼π^t1​\[P⋆​\(x,a1,a2\)−P^t​\(x,a1,a2\)\]\)2\]\)1/2\.\\displaystyle\\left\(\\mathbb\{E\}\_\{x\\sim d\}\\left\[\\sum\_\{a^\{2\}\\in\\mathcal\{A\}\}\\frac\{\\big\(\\widehat\{\\pi\}\_\{t\}^\{1\}\(a^\{2\}\\mid x\)\-\\widetilde\{\\pi\}\_\{t\}^\{2\}\(a^\{2\}\\mid x\)\\big\)^\{2\}\}\{\\pi\_\{\\mathrm\{ref\}\}\(a^\{2\}\\mid x\)\}\\right\]\\right\)^\{1/2\}\\left\(\\mathbb\{E\}\_\{\\begin\{subarray\}\{c\}x\\sim d,\\,a^\{2\}\\sim\\pi\_\{\\mathrm\{ref\}\}\\end\{subarray\}\}\\left\[\\left\(\\mathbb\{E\}\_\{a^\{1\}\\sim\\widehat\{\\pi\}\_\{t\}^\{1\}\}\\left\[P^\{\\star\}\(x,a^\{1\},a^\{2\}\)\-\\widehat\{P\}\_\{t\}\(x,a^\{1\},a^\{2\}\)\\right\]\\right\)^\{2\}\\right\]\\right\)^\{1/2\}\.\(22\)Using \([21](https://arxiv.org/html/2609.13564#A4.E21)\) for the first factor and Jensen’s inequality for the second factor yields

Gt≤\\displaystyle G\_\{t\}\\leq2​η​eη​Gt​\(𝔼x∼d,a1∼π^t1,a2∼πref​\[\(P⋆​\(x,a1,a2\)−P^t​\(x,a1,a2\)\)2\]\)1/2\.\\displaystyle\\sqrt\{2\\eta e^\{\\eta\}G\_\{t\}\}\\left\(\\mathbb\{E\}\_\{\\begin\{subarray\}\{c\}x\\sim d,\\,a^\{1\}\\sim\\widehat\{\\pi\}\_\{t\}^\{1\},\\,a^\{2\}\\sim\\pi\_\{\\mathrm\{ref\}\}\\end\{subarray\}\}\\left\[\\left\(P^\{\\star\}\(x,a^\{1\},a^\{2\}\)\-\\widehat\{P\}\_\{t\}\(x,a^\{1\},a^\{2\}\)\\right\)^\{2\}\\right\]\\right\)^\{1/2\}\.\(23\)IfGt\>0G\_\{t\}\>0, dividing both sides byGt\\sqrt\{G\_\{t\}\}and squaring gives

Gt≤2​η​eη​𝔼x∼d,a1∼π^t1,a2∼πref​\[\(P⋆​\(x,a1,a2\)−P^t​\(x,a1,a2\)\)2\]\.G\_\{t\}\\leq 2\\eta e^\{\\eta\}\\mathbb\{E\}\_\{\\begin\{subarray\}\{c\}x\\sim d,\\,a^\{1\}\\sim\\widehat\{\\pi\}\_\{t\}^\{1\},\\,a^\{2\}\\sim\\pi\_\{\\mathrm\{ref\}\}\\end\{subarray\}\}\\left\[\\left\(P^\{\\star\}\(x,a^\{1\},a^\{2\}\)\-\\widehat\{P\}\_\{t\}\(x,a^\{1\},a^\{2\}\)\\right\)^\{2\}\\right\]\.The result is immediate whenGt=0G\_\{t\}=0\. ∎

#### D\.1\.3Proof of Lemma[6](https://arxiv.org/html/2609.13564#Thmlemma6)

###### Proof of Lemma[6](https://arxiv.org/html/2609.13564#Thmlemma6)\.

LetℋiGP:=\{\(xj,aj1,aj2,yj\)\}j=1i\\mathcal\{H\}\_\{i\}^\{\\operatorname\{GP\}\}:=\\\{\(x\_\{j\},a\_\{j\}^\{1\},a\_\{j\}^\{2\},y\_\{j\}\)\\\}\_\{j=1\}^\{i\}\. For any fixedP∈𝒫P\\in\\mathcal\{P\}, define

YP,i:=\(P⁡\(xi,ai1,ai2\)−P⋆​\(xi,ai1,ai2\)\)2,μP,i:=𝔼⁡\[YP,i∣ℋi−1GP\]\.Y\_\{P,i\}:=\\left\(P\(x\_\{i\},a\_\{i\}^\{1\},a\_\{i\}^\{2\}\)\-P^\{\\star\}\(x\_\{i\},a\_\{i\}^\{1\},a\_\{i\}^\{2\}\)\\right\)^\{2\},\\qquad\\mu\_\{P,i\}:=\\mathbb\{E\}\[Y\_\{P,i\}\\mid\\mathcal\{H\}\_\{i\-1\}^\{\\operatorname\{GP\}\}\]\.SincePPandP⋆P^\{\\star\}take values in\[0,1\]\[0,1\], we have0≤YP,i≤10\\leq Y\_\{P,i\}\\leq 1\. Letc:=1−e−1c:=1\-e^\{\-1\}\. Usinge−y≤1−c​ye^\{\-y\}\\leq 1\-cyfory∈\[0,1\]y\\in\[0,1\], we obtain

𝔼⁡\[e−YP,i∣ℋi−1GP\]≤1−c​μP,i≤e−c​μP,i\.\\mathbb\{E\}\\\!\\left\[e^\{\-Y\_\{P,i\}\}\\mid\\mathcal\{H\}\_\{i\-1\}^\{\\operatorname\{GP\}\}\\right\]\\leq 1\-c\\mu\_\{P,i\}\\leq e^\{\-c\\mu\_\{P,i\}\}\.Consequently,

ZP,n:=exp⁡\(c​∑i=1nμP,i−∑i=1nYP,i\),ZP,0:=1,Z\_\{P,n\}:=\\exp\\left\(c\\sum\_\{i=1\}^\{n\}\\mu\_\{P,i\}\-\\sum\_\{i=1\}^\{n\}Y\_\{P,i\}\\right\),\\qquad Z\_\{P,0\}:=1,is a nonnegative supermartingale\. For fixedPPandtt, Markov’s inequality therefore gives, with probability at least1−δt,P1\-\\delta\_\{t,P\},

∑i=1t−1μP,i≤1c​\(∑i=1t−1YP,i\+log⁡1δt,P\)≤2​∑i=1t−1YP,i\+2​log⁡1δt,P,\\sum\_\{i=1\}^\{t\-1\}\\mu\_\{P,i\}\\leq\\frac\{1\}\{c\}\\left\(\\sum\_\{i=1\}^\{t\-1\}Y\_\{P,i\}\+\\log\\frac\{1\}\{\\delta\_\{t,P\}\}\\right\)\\leq 2\\sum\_\{i=1\}^\{t\-1\}Y\_\{P,i\}\+2\\log\\frac\{1\}\{\\delta\_\{t,P\}\},where the last inequality usesc−1<2c^\{\-1\}<2\.

Letδt,P:=δ/\(2​N𝒫​t3\)\\delta\_\{t,P\}:=\\delta/\(2N\_\{\\mathcal\{P\}\}t^\{3\}\)\. Taking a union bound over allP∈𝒫P\\in\\mathcal\{P\}andt=2,…,Tt=2,\\ldots,T, and using

∑t=2T∑P∈𝒫δt,P≤δ2​∑t=2∞t−3≤δ2,\\sum\_\{t=2\}^\{T\}\\sum\_\{P\\in\\mathcal\{P\}\}\\delta\_\{t,P\}\\leq\\frac\{\\delta\}\{2\}\\sum\_\{t=2\}^\{\\infty\}t^\{\-3\}\\leq\\frac\{\\delta\}\{2\},we conclude that, with probability at least1−δ/21\-\\delta/2, simultaneously for allP∈𝒫P\\in\\mathcal\{P\}andt=2,…,Tt=2,\\ldots,T,

∑i=1t−1𝔼⁡\[YP,i∣ℋi−1GP\]≤2​∑i=1t−1YP,i\+2​log⁡2​N𝒫​t3δ\.\\sum\_\{i=1\}^\{t\-1\}\\mathbb\{E\}\[Y\_\{P,i\}\\mid\\mathcal\{H\}\_\{i\-1\}^\{\\operatorname\{GP\}\}\]\\leq 2\\sum\_\{i=1\}^\{t\-1\}Y\_\{P,i\}\+2\\log\\frac\{2N\_\{\\mathcal\{P\}\}t^\{3\}\}\{\\delta\}\.
Under the sampling rule of our algorithm, conditional onℋi−1GP\\mathcal\{H\}\_\{i\-1\}^\{\\operatorname\{GP\}\}, we havexi∼dx\_\{i\}\\sim d, and the two actions are sampled independently according toai1∼π^i1\(⋅∣xi\)a\_\{i\}^\{1\}\\sim\\widehat\{\\pi\}\_\{i\}^\{1\}\(\\cdot\\mid x\_\{i\}\)andai2∼πref\(⋅∣xi\)a\_\{i\}^\{2\}\\sim\\pi\_\{\\rm ref\}\(\\cdot\\mid x\_\{i\}\)\. Thus, for every fixedP∈𝒫P\\in\\mathcal\{P\},

𝔼⁡\[YP,i∣ℋi−1GP\]=𝔼x∼d,a1∼π^i1,a2∼πref​\[\(P⁡\(x,a1,a2\)−P⋆​\(x,a1,a2\)\)2\]\.\\mathbb\{E\}\[Y\_\{P,i\}\\mid\\mathcal\{H\}\_\{i\-1\}^\{\\operatorname\{GP\}\}\]=\\mathbb\{E\}\_\{x\\sim d,\\,a^\{1\}\\sim\\widehat\{\\pi\}\_\{i\}^\{1\},\\,a^\{2\}\\sim\\pi\_\{\\rm ref\}\}\\left\[\\left\(P\(x,a^\{1\},a^\{2\}\)\-P^\{\\star\}\(x,a^\{1\},a^\{2\}\)\\right\)^\{2\}\\right\]\.Since the preceding event holds uniformly overP∈𝒫P\\in\\mathcal\{P\}, we may substituteP=P^tP=\\widehat\{P\}\_\{t\}\. Therefore, simultaneously for allt=2,…,Tt=2,\\ldots,T,

∑i=1t−1𝔼x∼d,a1∼π^i1,a2∼πref​\[\(P^t​\(x,a1,a2\)−P⋆​\(x,a1,a2\)\)2\]\\displaystyle\\sum\_\{i=1\}^\{t\-1\}\\mathbb\{E\}\_\{x\\sim d,\\,a^\{1\}\\sim\\widehat\{\\pi\}\_\{i\}^\{1\},\\,a^\{2\}\\sim\\pi\_\{\\rm ref\}\}\\left\[\\left\(\\widehat\{P\}\_\{t\}\(x,a^\{1\},a^\{2\}\)\-P^\{\\star\}\(x,a^\{1\},a^\{2\}\)\\right\)^\{2\}\\right\]≤2​∑i=1t−1\(P^t​\(xi,ai1,ai2\)−P⋆​\(xi,ai1,ai2\)\)2\+2​log⁡2​N𝒫​t3δ\.\\displaystyle\\leq 2\\sum\_\{i=1\}^\{t\-1\}\\left\(\\widehat\{P\}\_\{t\}\(x\_\{i\},a\_\{i\}^\{1\},a\_\{i\}^\{2\}\)\-P^\{\\star\}\(x\_\{i\},a\_\{i\}^\{1\},a\_\{i\}^\{2\}\)\\right\)^\{2\}\+2\\log\\frac\{2N\_\{\\mathcal\{P\}\}t^\{3\}\}\{\\delta\}\.
By Lemma[12](https://arxiv.org/html/2609.13564#Thmlemma12), applied with confidence levelδ/2\\delta/2, with probability at least1−δ/21\-\\delta/2, simultaneously for allt∈\[T\]t\\in\[T\],

∑i=1t−1\(P^t​\(xi,ai1,ai2\)−P⋆​\(xi,ai1,ai2\)\)2≤2​log⁡2​N𝒫​Tδ\.\\sum\_\{i=1\}^\{t\-1\}\\left\(\\widehat\{P\}\_\{t\}\(x\_\{i\},a\_\{i\}^\{1\},a\_\{i\}^\{2\}\)\-P^\{\\star\}\(x\_\{i\},a\_\{i\}^\{1\},a\_\{i\}^\{2\}\)\\right\)^\{2\}\\leq 2\\log\\frac\{2N\_\{\\mathcal\{P\}\}T\}\{\\delta\}\.Combining the two high\-probability events by a union bound, with probability at least1−δ1\-\\delta, simultaneously for allt=2,…,Tt=2,\\ldots,T,

∑i=1t−1𝔼x∼d,a1∼π^i1,a2∼πref​\[\(P^t​\(x,a1,a2\)−P⋆​\(x,a1,a2\)\)2\]\\displaystyle\\sum\_\{i=1\}^\{t\-1\}\\mathbb\{E\}\_\{x\\sim d,\\,a^\{1\}\\sim\\widehat\{\\pi\}\_\{i\}^\{1\},\\,a^\{2\}\\sim\\pi\_\{\\rm ref\}\}\\left\[\\left\(\\widehat\{P\}\_\{t\}\(x,a^\{1\},a^\{2\}\)\-P^\{\\star\}\(x,a^\{1\},a^\{2\}\)\\right\)^\{2\}\\right\]≤4​log⁡2​N𝒫​Tδ\+2​log⁡2​N𝒫​t3δ\\displaystyle\\leq 4\\log\\frac\{2N\_\{\\mathcal\{P\}\}T\}\{\\delta\}\+2\\log\\frac\{2N\_\{\\mathcal\{P\}\}t^\{3\}\}\{\\delta\}≤6​log⁡2​N𝒫​T3δ\.\\displaystyle\\leq 6\\log\\frac\{2N\_\{\\mathcal\{P\}\}T^\{3\}\}\{\\delta\}\.In particular,

∑i=1t−1𝔼x∼d,a1∼π^i1,a2∼πref​\[\(P^t​\(x,a1,a2\)−P⋆​\(x,a1,a2\)\)2\]≤6​log⁡2​N𝒫​T3δ\.\\displaystyle\\sum\_\{i=1\}^\{t\-1\}\\mathbb\{E\}\_\{x\\sim d,\\,a^\{1\}\\sim\\widehat\{\\pi\}\_\{i\}^\{1\},\\,a^\{2\}\\sim\\pi\_\{\\rm ref\}\}\\left\[\\left\(\\widehat\{P\}\_\{t\}\(x,a^\{1\},a^\{2\}\)\-P^\{\\star\}\(x,a^\{1\},a^\{2\}\)\\right\)^\{2\}\\right\]\\leq 6\\log\\frac\{2N\_\{\\mathcal\{P\}\}T^\{3\}\}\{\\delta\}\.\(24\)This proves the claim\. ∎

#### D\.1\.4UCB\-Based Exploration for the GP Model

We next consider an uncertainty\-based variant of ORLHF\-GS that explicitly explores uncertain preference comparisons\. The MLEP^t\\widehat\{P\}\_\{t\}and the learned policyπ^t1\\widehat\{\\pi\}\_\{t\}^\{1\}are constructed in the same way as in Algorithm[2](https://arxiv.org/html/2609.13564#alg2)\. The only modification is the sampling rule for the second action\. After observingxtx\_\{t\}and samplingat1∼π^t1\(⋅∣xt\)a\_\{t\}^\{1\}\\sim\\widehat\{\\pi\}\_\{t\}^\{1\}\(\\cdot\\mid x\_\{t\}\), we select

at2∈arg⁡maxa2∈𝒜⁡min⁡\{1,UGP2​\(λ,xt,at1,a2,𝒫,𝒟t−1GP\)\}\.a\_\{t\}^\{2\}\\in\\arg\\max\_\{a^\{2\}\\in\\mathcal\{A\}\}\\min\\left\\\{1,U\_\{\\operatorname\{GP\}\}^\{2\}\\left\(\\lambda,x\_\{t\},a\_\{t\}^\{1\},a^\{2\},\\mathcal\{P\};\\mathcal\{D\}\_\{t\-1\}^\{\\operatorname\{GP\}\}\\right\)\\right\\\}\.\(25\)The resulting action pair\(at1,at2\)\(a\_\{t\}^\{1\},a\_\{t\}^\{2\}\)is then used to obtain the preference feedback and update the MLE\. We refer to this sampling rule asGP\-UCB\. Unlike directly adding an optimistic bonus to the estimated preference function, the rule in \([25](https://arxiv.org/html/2609.13564#A4.E25)\) leaves the reciprocal structure ofP^t\\widehat\{P\}\_\{t\}unchanged and uses uncertainty only for data collection\.

###### Proof of Corollary[2](https://arxiv.org/html/2609.13564#Thmcorollary2)\.

LetGt:=JGP⋆−JGP​\(π^t1,π~t2\)G\_\{t\}:=J\_\{\\operatorname\{GP\}\}^\{\\star\}\-J\_\{\\operatorname\{GP\}\}\\left\(\\widehat\{\\pi\}\_\{t\}^\{1\},\\widetilde\{\\pi\}\_\{t\}^\{2\}\\right\)denote the instantaneous regret\. Recall from the proof of Lemma[5](https://arxiv.org/html/2609.13564#Thmlemma5)that

Gt≤𝔼x∼d​\[∑a2∈𝒜\(π^t1​\(a2∣x\)−π~t2​\(a2∣x\)\)​𝔼a1∼π^t1​\[P⋆​\(x,a1,a2\)−P^t​\(x,a1,a2\)\]\]\.\\displaystyle G\_\{t\}\\leq\\mathbb\{E\}\_\{x\\sim d\}\\Bigg\[\\sum\_\{a^\{2\}\\in\\mathcal\{A\}\}\\left\(\\widehat\{\\pi\}\_\{t\}^\{1\}\(a^\{2\}\\mid x\)\-\\widetilde\{\\pi\}\_\{t\}^\{2\}\(a^\{2\}\\mid x\)\\right\)\\mathbb\{E\}\_\{a^\{1\}\\sim\\widehat\{\\pi\}\_\{t\}^\{1\}\}\\left\[P^\{\\star\}\(x,a^\{1\},a^\{2\}\)\-\\widehat\{P\}\_\{t\}\(x,a^\{1\},a^\{2\}\)\\right\]\\Bigg\]\.\(26\)Moreover, the same proof gives the exact identity

Gt=η−1​𝔼x∼d​\[KL⁡\(π^t1,π~t2∣x\)\]\.G\_\{t\}=\\eta^\{\-1\}\\mathbb\{E\}\_\{x\\sim d\}\\left\[\\operatorname\{KL\}\\left\(\\widehat\{\\pi\}\_\{t\}^\{1\},\\widetilde\{\\pi\}\_\{t\}^\{2\}\\mid x\\right\)\\right\]\.\(27\)

##### Logarithmic bound\.

By \([26](https://arxiv.org/html/2609.13564#A4.E26)\) and the inequality

\|∑a2∈𝒜\(p⁡\(a2\)−q⁡\(a2\)\)​f​\(a2\)\|≤‖p−q‖1​maxa2∈𝒜​\|f⁡\(a2\)\|,\\left\|\\sum\_\{a^\{2\}\\in\\mathcal\{A\}\}\(p\(a^\{2\}\)\-q\(a^\{2\}\)\)f\(a^\{2\}\)\\right\|\\leq\\\|p\-q\\\|\_\{1\}\\max\_\{a^\{2\}\\in\\mathcal\{A\}\}\|f\(a^\{2\}\)\|,we have

Gt\\displaystyle G\_\{t\}≤𝔼x∼d\[‖π^t1\(⋅∣x\)−π~t2\(⋅∣x\)‖1maxa2∈𝒜\|𝔼a1∼π^t1\[P⋆\(x,a1,a2\)−P^t\(x,a1,a2\)\]\|\]\.\\displaystyle\\leq\\mathbb\{E\}\_\{x\\sim d\}\\Bigg\[\\left\\\|\\widehat\{\\pi\}\_\{t\}^\{1\}\(\\cdot\\mid x\)\-\\widetilde\{\\pi\}\_\{t\}^\{2\}\(\\cdot\\mid x\)\\right\\\|\_\{1\}\\max\_\{a^\{2\}\\in\\mathcal\{A\}\}\\left\|\\mathbb\{E\}\_\{a^\{1\}\\sim\\widehat\{\\pi\}\_\{t\}^\{1\}\}\\left\[P^\{\\star\}\(x,a^\{1\},a^\{2\}\)\-\\widehat\{P\}\_\{t\}\(x,a^\{1\},a^\{2\}\)\\right\]\\right\|\\Bigg\]\.\(28\)By Pinsker’s inequality,

‖π^t1\(⋅∣x\)−π~t2\(⋅∣x\)‖1≤2​KL⁡\(π^t1,π~t2∣x\)\.\\left\\\|\\widehat\{\\pi\}\_\{t\}^\{1\}\(\\cdot\\mid x\)\-\\widetilde\{\\pi\}\_\{t\}^\{2\}\(\\cdot\\mid x\)\\right\\\|\_\{1\}\\leq\\sqrt\{2\\operatorname\{KL\}\\left\(\\widehat\{\\pi\}\_\{t\}^\{1\},\\widetilde\{\\pi\}\_\{t\}^\{2\}\\mid x\\right\)\}\.Therefore, applying Cauchy–Schwarz with respect tox∼dx\\sim d,

Gt\\displaystyle G\_\{t\}≤2​𝔼x∼d​\[KL⁡\(π^t1,π~t2∣x\)\]​𝔼x∼d​\[maxa2∈𝒜⁡\(𝔼a1∼π^t1​\[P⋆​\(x,a1,a2\)−P^t​\(x,a1,a2\)\]\)2\]\.\\displaystyle\\leq\\sqrt\{2\\mathbb\{E\}\_\{x\\sim d\}\\left\[\\operatorname\{KL\}\\left\(\\widehat\{\\pi\}\_\{t\}^\{1\},\\widetilde\{\\pi\}\_\{t\}^\{2\}\\mid x\\right\)\\right\]\}\\sqrt\{\\mathbb\{E\}\_\{x\\sim d\}\\left\[\\max\_\{a^\{2\}\\in\\mathcal\{A\}\}\\left\(\\mathbb\{E\}\_\{a^\{1\}\\sim\\widehat\{\\pi\}\_\{t\}^\{1\}\}\\left\[P^\{\\star\}\(x,a^\{1\},a^\{2\}\)\-\\widehat\{P\}\_\{t\}\(x,a^\{1\},a^\{2\}\)\\right\]\\right\)^\{2\}\\right\]\}\.Using \([27](https://arxiv.org/html/2609.13564#A4.E27)\), we obtain

Gt\\displaystyle G\_\{t\}≤2​η​Gt​𝔼x∼d​\[maxa2∈𝒜⁡\(𝔼a1∼π^t1​\[P⋆​\(x,a1,a2\)−P^t​\(x,a1,a2\)\]\)2\]\.\\displaystyle\\leq\\sqrt\{2\\eta G\_\{t\}\}\\sqrt\{\\mathbb\{E\}\_\{x\\sim d\}\\left\[\\max\_\{a^\{2\}\\in\\mathcal\{A\}\}\\left\(\\mathbb\{E\}\_\{a^\{1\}\\sim\\widehat\{\\pi\}\_\{t\}^\{1\}\}\\left\[P^\{\\star\}\(x,a^\{1\},a^\{2\}\)\-\\widehat\{P\}\_\{t\}\(x,a^\{1\},a^\{2\}\)\\right\]\\right\)^\{2\}\\right\]\}\.IfGt=0G\_\{t\}=0, the desired bound is immediate\. Otherwise, dividing byGt\\sqrt\{G\_\{t\}\}and squaring both sides gives

Gt≤2​η​𝔼x∼d​\[maxa2∈𝒜⁡\(𝔼a1∼π^t1​\[P⋆​\(x,a1,a2\)−P^t​\(x,a1,a2\)\]\)2\]\.\\displaystyle G\_\{t\}\\leq 2\\eta\\mathbb\{E\}\_\{x\\sim d\}\\left\[\\max\_\{a^\{2\}\\in\\mathcal\{A\}\}\\left\(\\mathbb\{E\}\_\{a^\{1\}\\sim\\widehat\{\\pi\}\_\{t\}^\{1\}\}\\left\[P^\{\\star\}\(x,a^\{1\},a^\{2\}\)\-\\widehat\{P\}\_\{t\}\(x,a^\{1\},a^\{2\}\)\\right\]\\right\)^\{2\}\\right\]\.Finally, by Jensen’s inequality,

\(𝔼a1∼π^t1​\[P⋆​\(x,a1,a2\)−P^t​\(x,a1,a2\)\]\)2≤𝔼a1∼π^t1​\[\(P⋆​\(x,a1,a2\)−P^t​\(x,a1,a2\)\)2\]\.\\left\(\\mathbb\{E\}\_\{a^\{1\}\\sim\\widehat\{\\pi\}\_\{t\}^\{1\}\}\\left\[P^\{\\star\}\(x,a^\{1\},a^\{2\}\)\-\\widehat\{P\}\_\{t\}\(x,a^\{1\},a^\{2\}\)\\right\]\\right\)^\{2\}\\leq\\mathbb\{E\}\_\{a^\{1\}\\sim\\widehat\{\\pi\}\_\{t\}^\{1\}\}\\left\[\\left\(P^\{\\star\}\(x,a^\{1\},a^\{2\}\)\-\\widehat\{P\}\_\{t\}\(x,a^\{1\},a^\{2\}\)\\right\)^\{2\}\\right\]\.Hence,

Gt≤2​η​𝔼x∼d​\[maxa2∈𝒜⁡𝔼a1∼π^t1​\[\(P⋆​\(x,a1,a2\)−P^t​\(x,a1,a2\)\)2\]\]\.\\displaystyle G\_\{t\}\\leq 2\\eta\\mathbb\{E\}\_\{x\\sim d\}\\left\[\\max\_\{a^\{2\}\\in\\mathcal\{A\}\}\\mathbb\{E\}\_\{a^\{1\}\\sim\\widehat\{\\pi\}\_\{t\}^\{1\}\}\\left\[\\left\(P^\{\\star\}\(x,a^\{1\},a^\{2\}\)\-\\widehat\{P\}\_\{t\}\(x,a^\{1\},a^\{2\}\)\\right\)^\{2\}\\right\]\\right\]\.\(29\)
By the MLE confidence event used in the eluder\-dimension\-dependent proof of Theorem[2](https://arxiv.org/html/2609.13564#Thmtheorem2), with confidence levelδ/2\\delta/2, simultaneously for allt∈\[T\]t\\in\[T\], and forλ≤log⁡\(2​N𝒫​T/δ\)\\lambda\\leq\\log\(2N\_\{\\mathcal\{P\}\}T/\\delta\),

\(P⋆​\(x,a1,a2\)−P^t​\(x,a1,a2\)\)2≤3​log⁡2​N𝒫​Tδ​min​\{1,UGP2​\(λ,x,a1,a2,𝒫,𝒟t−1GP\)\}\.\\displaystyle\\left\(P^\{\\star\}\(x,a^\{1\},a^\{2\}\)\-\\widehat\{P\}\_\{t\}\(x,a^\{1\},a^\{2\}\)\\right\)^\{2\}\\leq 3\\log\\frac\{2N\_\{\\mathcal\{P\}\}T\}\{\\delta\}\\min\\left\\\{1,U\_\{\\operatorname\{GP\}\}^\{2\}\\left\(\\lambda,x,a^\{1\},a^\{2\},\\mathcal\{P\};\\mathcal\{D\}\_\{t\-1\}^\{\\operatorname\{GP\}\}\\right\)\\right\\\}\.\(30\)Combining \([29](https://arxiv.org/html/2609.13564#A4.E29)\) and \([30](https://arxiv.org/html/2609.13564#A4.E30)\), and using

maxa2∈𝒜⁡𝔼a1∼π^t1​\[min⁡\{1,UGP2​\(λ,x,a1,a2,𝒫,𝒟t−1GP\)\}\]≤𝔼a1∼π^t1​\[maxa2∈𝒜⁡min⁡\{1,UGP2​\(λ,x,a1,a2,𝒫,𝒟t−1GP\)\}\],\\displaystyle\\max\_\{a^\{2\}\\in\\mathcal\{A\}\}\\mathbb\{E\}\_\{a^\{1\}\\sim\\widehat\{\\pi\}\_\{t\}^\{1\}\}\\left\[\\min\\left\\\{1,U\_\{\\operatorname\{GP\}\}^\{2\}\\left\(\\lambda,x,a^\{1\},a^\{2\},\\mathcal\{P\};\\mathcal\{D\}\_\{t\-1\}^\{\\operatorname\{GP\}\}\\right\)\\right\\\}\\right\]\\leq\\mathbb\{E\}\_\{a^\{1\}\\sim\\widehat\{\\pi\}\_\{t\}^\{1\}\}\\left\[\\max\_\{a^\{2\}\\in\\mathcal\{A\}\}\\min\\left\\\{1,U\_\{\\operatorname\{GP\}\}^\{2\}\\left\(\\lambda,x,a^\{1\},a^\{2\},\\mathcal\{P\};\\mathcal\{D\}\_\{t\-1\}^\{\\operatorname\{GP\}\}\\right\)\\right\\\}\\right\],we obtain

Gt=O⁡\(η​log⁡N𝒫​Tδ​𝔼x∼d,a1∼π^t1​\[maxa2∈𝒜⁡min⁡\{1,UGP2​\(λ,x,a1,a2,𝒫,𝒟t−1GP\)\}\]\)\.\\displaystyle G\_\{t\}=O\\Bigg\(\\eta\\log\\frac\{N\_\{\\mathcal\{P\}\}T\}\{\\delta\}\\,\\mathbb\{E\}\_\{\\begin\{subarray\}\{c\}x\\sim d,\\,a^\{1\}\\sim\\widehat\{\\pi\}\_\{t\}^\{1\}\\end\{subarray\}\}\\Bigg\[\\max\_\{a^\{2\}\\in\\mathcal\{A\}\}\\min\\Bigg\\\{1,U\_\{\\operatorname\{GP\}\}^\{2\}\\left\(\\lambda,x,a^\{1\},a^\{2\},\\mathcal\{P\};\\mathcal\{D\}\_\{t\-1\}^\{\\operatorname\{GP\}\}\\right\)\\Bigg\\\}\\Bigg\]\\Bigg\)\.\(31\)
SinceGP\-UCBselectsat2a\_\{t\}^\{2\}according to \([25](https://arxiv.org/html/2609.13564#A4.E25)\), conditioned on the history before roundtt, the expectation in \([31](https://arxiv.org/html/2609.13564#A4.E31)\) is exactly the conditional expectation ofmin⁡\{1,UGP2​\(λ,xt,at1,at2,𝒫,𝒟t−1GP\)\}\\min\\left\\\{1,U\_\{\\operatorname\{GP\}\}^\{2\}\\left\(\\lambda,x\_\{t\},a\_\{t\}^\{1\},a\_\{t\}^\{2\},\\mathcal\{P\};\\mathcal\{D\}\_\{t\-1\}^\{\\operatorname\{GP\}\}\\right\)\\right\\\}\. Moreover, for every realized sequence\{\(xt,at1,at2\)\}t=1T\\\{\(x\_\{t\},a\_\{t\}^\{1\},a\_\{t\}^\{2\}\)\\\}\_\{t=1\}^\{T\}, the definition ofdGP​\(λ,𝒫,T\)d\_\{\\operatorname\{GP\}\}\(\\lambda,\\mathcal\{P\},T\)gives

∑t=1Tmin⁡\{1,UGP2​\(λ,xt,at1,at2,𝒫,𝒟t−1GP\)\}≤dGP​\(λ,𝒫,T\)\.\\displaystyle\\sum\_\{t=1\}^\{T\}\\min\\left\\\{1,U\_\{\\operatorname\{GP\}\}^\{2\}\\left\(\\lambda,x\_\{t\},a\_\{t\}^\{1\},a\_\{t\}^\{2\},\\mathcal\{P\};\\mathcal\{D\}\_\{t\-1\}^\{\\operatorname\{GP\}\}\\right\)\\right\\\}\\leq d\_\{\\operatorname\{GP\}\}\(\\lambda,\\mathcal\{P\},T\)\.Therefore, applying the same predictable\-to\-realized concentration argument as in the eluder\-dimension\-dependent proof of Theorem[2](https://arxiv.org/html/2609.13564#Thmtheorem2), with confidence levelδ/2\\delta/2, gives

∑t=1T𝔼x∼d,a1∼π^t1​\[maxa2∈𝒜⁡min⁡\{1,UGP2​\(λ,x,a1,a2,𝒫,𝒟t−1GP\)\}\]=O⁡\(dGP​\(λ,𝒫,T\)\+log⁡1δ\)\.\\displaystyle\\sum\_\{t=1\}^\{T\}\\mathbb\{E\}\_\{\\begin\{subarray\}\{c\}x\\sim d,\\,a^\{1\}\\sim\\widehat\{\\pi\}\_\{t\}^\{1\}\\end\{subarray\}\}\\Bigg\[\\max\_\{a^\{2\}\\in\\mathcal\{A\}\}\\min\\Bigg\\\{1,U\_\{\\operatorname\{GP\}\}^\{2\}\\left\(\\lambda,x,a^\{1\},a^\{2\},\\mathcal\{P\};\\mathcal\{D\}\_\{t\-1\}^\{\\operatorname\{GP\}\}\\right\)\\Bigg\\\}\\Bigg\]=O\\left\(d\_\{\\operatorname\{GP\}\}\(\\lambda,\\mathcal\{P\},T\)\+\\log\\frac\{1\}\{\\delta\}\\right\)\.\(32\)Taking a union bound over the MLE confidence event and the predictable\-to\-realized concentration event, the preceding bounds hold simultaneously with probability at least1−δ1\-\\delta\. Therefore,

RegGP⁡\(T\)=O⁡\(η⁡\(dGP​\(λ,𝒫,T\)\+log⁡1δ\)​log⁡N𝒫​Tδ\)\.\\operatorname\{Reg\}\_\{\\operatorname\{GP\}\}\(T\)=O\\left\(\\eta\\left\(d\_\{\\operatorname\{GP\}\}\(\\lambda,\\mathcal\{P\},T\)\+\\log\\frac\{1\}\{\\delta\}\\right\)\\log\\frac\{N\_\{\\mathcal\{P\}\}T\}\{\\delta\}\\right\)\.\(33\)

##### η\\eta\-independent bound\.

Returning to \([28](https://arxiv.org/html/2609.13564#A4.E28)\) and using‖π^t1\(⋅∣x\)−π~t2\(⋅∣x\)‖1≤2\\left\\\|\\widehat\{\\pi\}\_\{t\}^\{1\}\(\\cdot\\mid x\)\-\\widetilde\{\\pi\}\_\{t\}^\{2\}\(\\cdot\\mid x\)\\right\\\|\_\{1\}\\leq 2, we obtain

Gt\\displaystyle G\_\{t\}≤2​𝔼x∼d​\[maxa2∈𝒜⁡\|𝔼a1∼π^t1​\[P⋆​\(x,a1,a2\)−P^t​\(x,a1,a2\)\]\|\]\\displaystyle\\leq 2\\mathbb\{E\}\_\{x\\sim d\}\\left\[\\max\_\{a^\{2\}\\in\\mathcal\{A\}\}\\left\|\\mathbb\{E\}\_\{a^\{1\}\\sim\\widehat\{\\pi\}\_\{t\}^\{1\}\}\\left\[P^\{\\star\}\(x,a^\{1\},a^\{2\}\)\-\\widehat\{P\}\_\{t\}\(x,a^\{1\},a^\{2\}\)\\right\]\\right\|\\right\]≤2​𝔼x∼d​\[maxa2∈𝒜⁡\(𝔼a1∼π^t1​\[P⋆​\(x,a1,a2\)−P^t​\(x,a1,a2\)\]\)2\]\\displaystyle\\leq 2\\sqrt\{\\mathbb\{E\}\_\{x\\sim d\}\\left\[\\max\_\{a^\{2\}\\in\\mathcal\{A\}\}\\left\(\\mathbb\{E\}\_\{a^\{1\}\\sim\\widehat\{\\pi\}\_\{t\}^\{1\}\}\\left\[P^\{\\star\}\(x,a^\{1\},a^\{2\}\)\-\\widehat\{P\}\_\{t\}\(x,a^\{1\},a^\{2\}\)\\right\]\\right\)^\{2\}\\right\]\}≤2​3​log⁡2​N𝒫​Tδ​𝔼x∼d,a1∼π^t1​\[maxa2∈𝒜⁡min⁡\{1,UGP2​\(λ,x,a1,a2,𝒫,𝒟t−1GP\)\}\]\.\\displaystyle\\leq 2\\sqrt\{3\\log\\frac\{2N\_\{\\mathcal\{P\}\}T\}\{\\delta\}\}\\sqrt\{\\mathbb\{E\}\_\{\\begin\{subarray\}\{c\}x\\sim d,\\,a^\{1\}\\sim\\widehat\{\\pi\}\_\{t\}^\{1\}\\end\{subarray\}\}\\left\[\\max\_\{a^\{2\}\\in\\mathcal\{A\}\}\\min\\left\\\{1,U\_\{\\operatorname\{GP\}\}^\{2\}\\left\(\\lambda,x,a^\{1\},a^\{2\},\\mathcal\{P\};\\mathcal\{D\}\_\{t\-1\}^\{\\operatorname\{GP\}\}\\right\)\\right\\\}\\right\]\}\.Summing overttand applying Cauchy–Schwarz together with \([32](https://arxiv.org/html/2609.13564#A4.E32)\) gives

RegGP⁡\(T\)\\displaystyle\\operatorname\{Reg\}\_\{\\operatorname\{GP\}\}\(T\)=O⁡\(T⁡\(dGP​\(λ,𝒫,T\)\+log⁡1δ\)​log⁡N𝒫​Tδ\)\.\\displaystyle=O\\left\(\\sqrt\{T\\left\(d\_\{\\operatorname\{GP\}\}\(\\lambda,\\mathcal\{P\},T\)\+\\log\\frac\{1\}\{\\delta\}\\right\)\\log\\frac\{N\_\{\\mathcal\{P\}\}T\}\{\\delta\}\}\\right\)\.Taking the minimum of the two bounds completes the proof\. ∎

### D\.2Bradley\-Terry Model

The proof of Theorem[3](https://arxiv.org/html/2609.13564#Thmtheorem3)relies on the following two key lemmas\. Lemma[7](https://arxiv.org/html/2609.13564#Thmlemma7)establishes the instantaneous KL\-regularized regret decomposition under the BT model, while Lemma[8](https://arxiv.org/html/2609.13564#Thmlemma8)provides the uniform convergence guarantee for the MLE estimator under the BT model\.

###### Lemma 7\(Instantaneous Regret Decomposition, Bradley\-Terry Model\)\.

For allt∈\[T\]t\\in\[T\], the instantaneous regret in the BT model satisfies

JBT​\(π⋆\)−JBT​\(π^t1\)≤η​𝔼x∼d,a1∼πt′,a2∼πref​\[\(\(R⋆​\(x,a1\)−R⋆​\(x,a2\)\)−\(R^t​\(x,a1\)−R^t​\(x,a2\)\)\)2\],J\_\{\\operatorname\{BT\}\}\(\\pi^\{\\star\}\)\-J\_\{\\operatorname\{BT\}\}\(\\widehat\{\\pi\}^\{1\}\_\{t\}\)\\leq\\eta\\mathbb\{E\}\_\{x\\sim d,\\,a^\{1\}\\sim\\pi\_\{t\}^\{\\prime\},\\,a^\{2\}\\sim\\pi\_\{\\operatorname\{ref\}\}\}\\\!\\left\[\\left\(\\left\(R^\{\\star\}\(x,a^\{1\}\)\-R^\{\\star\}\(x,a^\{2\}\)\\right\)\-\\left\(\\widehat\{R\}\_\{t\}\(x,a^\{1\}\)\-\\widehat\{R\}\_\{t\}\(x,a^\{2\}\)\\right\)\\right\)^\{2\}\\right\],whereπt′\\pi\_\{t\}^\{\\prime\}denotes the Gibbs policy induced by some\[0,1\]\[0,1\]\-valued reward functionRt′R\_\{t\}^\{\\prime\}\.

###### Lemma 8\(Uniform Prediction Error Bound, Bradley\-Terry Model\)\.

Suppose Assumption[1](https://arxiv.org/html/2609.13564#Thmassumption1)holds\. LetR^t\\widehat\{R\}\_\{t\}be the MLE estimator over the function classℛ\\mathcal\{R\}constructed from the samples\{\(xi,ai1,ai2,yi\)\}i=1t−1\\\{\(x\_\{i\},a\_\{i\}^\{1\},a\_\{i\}^\{2\},y\_\{i\}\)\\\}\_\{i=1\}^\{t\-1\}, wherexi∼dx\_\{i\}\\sim d,ai1∼π^i1\(⋅∣xi\)a\_\{i\}^\{1\}\\sim\\widehat\{\\pi\}\_\{i\}^\{1\}\(\\cdot\\mid x\_\{i\}\), andai2∼πref\(⋅∣xi\)a\_\{i\}^\{2\}\\sim\\pi\_\{\\operatorname\{ref\}\}\(\\cdot\\mid x\_\{i\}\)for eachii\. Then for any such policy sequence\{π^i1\}i≥1\\\{\\widehat\{\\pi\}\_\{i\}^\{1\}\\\}\_\{i\\geq 1\}and anyδ∈\(0,1\)\\delta\\in\(0,1\), with probability at least1−δ1\-\\delta, the following holds simultaneously for allt=2,…,Tt=2,\\dots,T:

∑i=1t−1𝔼x∼d,a1∼π^i1,a2∼πref​\[\(\(R⋆​\(x,a1\)−R⋆​\(x,a2\)\)−\(R^t​\(x,a1\)−R^t​\(x,a2\)\)\)2\]≤24​e2​log⁡2​Nℛ​T3δ\.\\displaystyle\\begin\{split\}\\sum\_\{i=1\}^\{t\-1\}\\mathbb\{E\}\_\{x\\sim d,\\;a^\{1\}\\sim\\widehat\{\\pi\}\_\{i\}^\{1\},\\;a^\{2\}\\sim\\pi\_\{\\rm ref\}\}\\left\[\\left\(\\left\(R^\{\\star\}\(x,a^\{1\}\)\-R^\{\\star\}\(x,a^\{2\}\)\\right\)\-\\left\(\\widehat\{R\}\_\{t\}\(x,a^\{1\}\)\-\\widehat\{R\}\_\{t\}\(x,a^\{2\}\)\\right\)\\right\)^\{2\}\\right\]\\leq&24e^\{2\}\\log\\frac\{2N\_\{\\mathcal\{R\}\}T^\{3\}\}\{\\delta\}\.\\end\{split\}

###### Proof of Theorem[3](https://arxiv.org/html/2609.13564#Thmtheorem3)\.

The proof follows the same argument as those of Theorem[1](https://arxiv.org/html/2609.13564#Thmtheorem1)and Theorem[2](https://arxiv.org/html/2609.13564#Thmtheorem2)\. For eacht∈\[T\]t\\in\[T\], defineSt:=𝔼x∼d,a1∼πt′,a2∼πref​\[\(\(R⋆​\(x,a1\)−R⋆​\(x,a2\)\)−\(R^t​\(x,a1\)−R^t​\(x,a2\)\)\)2\]S\_\{t\}:=\\mathbb\{E\}\_\{x\\sim d,\\,a^\{1\}\\sim\\pi\_\{t\}^\{\\prime\},\\,a^\{2\}\\sim\\pi\_\{\\operatorname\{ref\}\}\}\\\!\\left\[\\left\(\\left\(R^\{\\star\}\(x,a^\{1\}\)\-R^\{\\star\}\(x,a^\{2\}\)\\right\)\-\\left\(\\widehat\{R\}\_\{t\}\(x,a^\{1\}\)\-\\widehat\{R\}\_\{t\}\(x,a^\{2\}\)\\right\)\\right\)^\{2\}\\right\]\. Applying Lemma[7](https://arxiv.org/html/2609.13564#Thmlemma7)yields the regret decomposition

RegBT⁡\(T\)\\displaystyle\\operatorname\{Reg\}\_\{\\mathrm\{BT\}\}\(T\)=∑t=1T\(JBT​\(π⋆\)−JBT​\(π^t1\)\)≤η​∑t=1TSt\.\\displaystyle=\\sum\_\{t=1\}^\{T\}\\Big\(J\_\{\\mathrm\{BT\}\}\(\\pi^\{\\star\}\)\-J\_\{\\mathrm\{BT\}\}\(\\widehat\{\\pi\}\_\{t\}^\{1\}\)\\Big\)\\leq\\eta\\sum\_\{t=1\}^\{T\}S\_\{t\}\.\(34\)We next bound∑t=1TSt\\sum\_\{t=1\}^\{T\}S\_\{t\}\. By Lemma[8](https://arxiv.org/html/2609.13564#Thmlemma8)and the same Gibbs\-policy comparison argument as in the proof of Theorem[1](https://arxiv.org/html/2609.13564#Thmtheorem1), we obtain

St≤24​e2\+2​ηt−1log2​Nℛ​T3δ,∀t=2,…,T\.\\displaystyle S\_\{t\}\\leq\\frac\{24e^\{2\+2\\eta\}\}\{t\-1\}\\log\\frac\{2N\_\{\\mathcal\{R\}\}T^\{3\}\}\{\\delta\},\\qquad\\forall t=2,\\dots,T\.\(35\)Fort=1t=1, sinceR⋆,R^1R^\{\\star\},\\widehat\{R\}\_\{1\}are\[0,1\]\[0,1\]\-valued, we trivially haveS1≤4S\_\{1\}\\leq 4\. Therefore,

∑t=1TSt≤4\+24​e2\+2​η​log⁡2​Nℛ​T3δ​∑t=2T1t−1\.\\sum\_\{t=1\}^\{T\}S\_\{t\}\\leq 4\+24e^\{2\+2\\eta\}\\log\\frac\{2N\_\{\\mathcal\{R\}\}T^\{3\}\}\{\\delta\}\\sum\_\{t=2\}^\{T\}\\frac\{1\}\{t\-1\}\.Using∑t=2T\(t−1\)−1≤1\+log⁡T\\sum\_\{t=2\}^\{T\}\(t\-1\)^\{\-1\}\\leq 1\+\\log T, we obtain

∑t=1TSt=O⁡\(e2​η​log⁡T​log⁡Nℛ​Tδ\)\.\\sum\_\{t=1\}^\{T\}S\_\{t\}=O\\\!\\left\(e^\{2\\eta\}\\log T\\log\\frac\{N\_\{\\mathcal\{R\}\}T\}\{\\delta\}\\right\)\.Substituting this bound into Eq\. \([34](https://arxiv.org/html/2609.13564#A4.E34)\) yields

RegBT⁡\(T\)=O⁡\(η​e2​η​log⁡T​log⁡Nℛ​Tδ\)\.\\operatorname\{Reg\}\_\{\\mathrm\{BT\}\}\(T\)=O\\\!\\left\(\\eta e^\{2\\eta\}\\log T\\log\\frac\{N\_\{\\mathcal\{R\}\}T\}\{\\delta\}\\right\)\.This completes the proof\. ∎

#### D\.2\.1Proof of Lemma[7](https://arxiv.org/html/2609.13564#Thmlemma7)

###### Proof of Lemma[7](https://arxiv.org/html/2609.13564#Thmlemma7)\.

The selected policy in roundttsatisfies

π^t1\\displaystyle\\widehat\{\\pi\}^\{1\}\_\{t\}=arg⁡maxπ​𝔼x∼d,a∼π​\[R^t​\(x,a\)−η−1​KL​\(π,πref∣x\)\]\\displaystyle=\\arg\\max\_\{\\pi\}\\mathbb\{E\}\_\{x\\sim d,\\;a\\sim\\pi\}\\\!\\left\[\\widehat\{R\}\_\{t\}\(x,a\)\-\\eta^\{\-1\}\\mathrm\{KL\}\(\\pi,\\pi\_\{\\text\{ref\}\}\\mid x\)\\right\]=arg⁡maxπ​𝔼x∼d,a∼π​\[R^t​\(x,a\)\+l⁡\(x\)−η−1​KL​\(π,πref∣x\)\],\\displaystyle=\\arg\\max\_\{\\pi\}\\mathbb\{E\}\_\{x\\sim d,\\;a\\sim\\pi\}\\\!\\left\[\\widehat\{R\}\_\{t\}\(x,a\)\+l\(x\)\-\\eta^\{\-1\}\\mathrm\{KL\}\(\\pi,\\pi\_\{\\text\{ref\}\}\\mid x\)\\right\],for any functionl:𝒳→ℝl:\\mathcal\{X\}\\rightarrow\\mathbb\{R\}\. By selectinglt​\(x\):=𝔼a′∼πref​\[R⋆​\(x,a′\)−R^t​\(x,a′\)\]l\_\{t\}\(x\):=\\mathbb\{E\}\_\{a^\{\\prime\}\\sim\\pi\_\{\\text\{ref\}\}\}\\\!\\left\[R^\{\\star\}\(x,a^\{\\prime\}\)\-\\widehat\{R\}\_\{t\}\(x,a^\{\\prime\}\)\\right\], we have for allt∈\[T\]t\\in\[T\],

JBT​\(π⋆\)−JBT​\(π^t1\)\\displaystyle J\_\{\\text\{BT\}\}\(\\pi^\{\\star\}\)\-J\_\{\\text\{BT\}\}\(\\widehat\{\\pi\}^\{1\}\_\{t\}\)≤η​𝔼x∼d,a∼πt′​\[\(R⋆​\(x,a\)−R^t​\(x,a\)−lt​\(x\)\)2\]\\displaystyle\\leq\\eta\\mathbb\{E\}\_\{x\\sim d,\\;a\\sim\\pi^\{\\prime\}\_\{t\}\}\\\!\\left\[\\left\(R^\{\\star\}\(x,a\)\-\\widehat\{R\}\_\{t\}\(x,a\)\-l\_\{t\}\(x\)\\right\)^\{2\}\\right\]=η​𝔼x∼d,a1∼πt′​\[\(R⋆​\(x,a1\)−R^t​\(x,a1\)−𝔼a2∼πref​\(R⋆​\(x,a2\)−R^t​\(x,a2\)\)\)2\]\\displaystyle=\\eta\\mathbb\{E\}\_\{x\\sim d,\\,a^\{1\}\\sim\\pi^\{\\prime\}\_\{t\}\}\\\!\\left\[\\left\(R^\{\\star\}\(x,a^\{1\}\)\-\\widehat\{R\}\_\{t\}\(x,a^\{1\}\)\-\\mathbb\{E\}\_\{a^\{2\}\\sim\\pi\_\{\\text\{ref\}\}\}\\left\(R^\{\\star\}\(x,a^\{2\}\)\-\\widehat\{R\}\_\{t\}\(x,a^\{2\}\)\\right\)\\right\)^\{2\}\\right\]≤η​𝔼x∼d,a1∼πt′,a2∼πref​\[\(\(R⋆​\(x,a1\)−R⋆​\(x,a2\)\)−\(R^t​\(x,a1\)−R^t​\(x,a2\)\)\)2\]\.\\displaystyle\\leq\\eta\\mathbb\{E\}\_\{x\\sim d,\\,a^\{1\}\\sim\\pi^\{\\prime\}\_\{t\},\\,a^\{2\}\\sim\\pi\_\{\\text\{ref\}\}\}\\\!\\left\[\\left\(\\left\(R^\{\\star\}\(x,a^\{1\}\)\-R^\{\\star\}\(x,a^\{2\}\)\\right\)\-\\left\(\\widehat\{R\}\_\{t\}\(x,a^\{1\}\)\-\\widehat\{R\}\_\{t\}\(x,a^\{2\}\)\\right\)\\right\)^\{2\}\\right\]\.To justify the first inequality, althoughR^t\+lt\\widehat\{R\}\_\{t\}\+l\_\{t\}need not be\[0,1\]\[0,1\]\-valued, for anyγ∈\[0,1\]\\gamma\\in\[0,1\]we have

γ⁡\(R^t\+lt\)\+\(1−γ\)​R⋆=γ​R^t\+\(1−γ\)​R⋆\+γ​lt\.\\gamma\(\\widehat\{R\}\_\{t\}\+l\_\{t\}\)\+\(1\-\\gamma\)R^\{\\star\}=\\gamma\\widehat\{R\}\_\{t\}\+\(1\-\\gamma\)R^\{\\star\}\+\\gamma l\_\{t\}\.Sinceγ​lt​\(x\)\\gamma l\_\{t\}\(x\)is independent of the action, the right\-hand side induces the same Gibbs policy as the\[0,1\]\[0,1\]\-valued reward functionγ​R^t\+\(1−γ\)​R⋆\\gamma\\widehat\{R\}\_\{t\}\+\(1\-\\gamma\)R^\{\\star\}\. Therefore, repeating the mean\-value argument in the proof of Lemma[4](https://arxiv.org/html/2609.13564#Thmlemma4)yields the first inequality for someγt∈\[0,1\]\\gamma\_\{t\}\\in\[0,1\], whereπt′\\pi\_\{t\}^\{\\prime\}is the Gibbs policy induced byRt′=γt​R^t\+\(1−γt\)​R⋆R\_\{t\}^\{\\prime\}=\\gamma\_\{t\}\\widehat\{R\}\_\{t\}\+\(1\-\\gamma\_\{t\}\)R^\{\\star\}\. The last inequality follows from Jensen’s inequality\. ∎

#### D\.2\.2Proof of Lemma[8](https://arxiv.org/html/2609.13564#Thmlemma8)

###### Proof of Lemma[8](https://arxiv.org/html/2609.13564#Thmlemma8)\.

SubstitutingP⁡\(xi,ai1,ai2\)P\(x\_\{i\},a\_\{i\}^\{1\},a\_\{i\}^\{2\}\)withσ⁡\(R⁡\(xi,ai1\)−R⁡\(xi,ai2\)\)\\sigma\\\!\\left\(R\(x\_\{i\},a\_\{i\}^\{1\}\)\-R\(x\_\{i\},a\_\{i\}^\{2\}\)\\right\)andP⋆​\(xi,ai1,ai2\)P^\{\\star\}\(x\_\{i\},a\_\{i\}^\{1\},a\_\{i\}^\{2\}\)withσ⁡\(R⋆​\(xi,ai1\)−R⋆​\(xi,ai2\)\)\\sigma\\\!\\left\(R^\{\\star\}\(x\_\{i\},a\_\{i\}^\{1\}\)\-R^\{\\star\}\(x\_\{i\},a\_\{i\}^\{2\}\)\\right\)in the proof of Lemma[6](https://arxiv.org/html/2609.13564#Thmlemma6), we obtain

∑i=1t−1𝔼x∼d,a1∼π^i1,a2∼πref​\[\(\(R⋆​\(x,a1\)−R⋆​\(x,a2\)\)−\(R^t​\(x,a1\)−R^t​\(x,a2\)\)\)2\]\\displaystyle\\sum\_\{i=1\}^\{t\-1\}\\mathbb\{E\}\_\{x\\sim d,\\;a^\{1\}\\sim\\widehat\{\\pi\}\_\{i\}^\{1\},\\;a^\{2\}\\sim\\pi\_\{\\rm ref\}\}\\left\[\\left\(\\bigl\(R^\{\\star\}\(x,a^\{1\}\)\-R^\{\\star\}\(x,a^\{2\}\)\\bigr\)\-\\bigl\(\\widehat\{R\}\_\{t\}\(x,a^\{1\}\)\-\\widehat\{R\}\_\{t\}\(x,a^\{2\}\)\\bigr\)\\right\)^\{2\}\\right\]≤\\displaystyle\\leq\\;4​e2​∑i=1t−1𝔼x∼d,a1∼π^i1,a2∼πref​\[\(σ⁡\(R⋆​\(x,a1\)−R⋆​\(x,a2\)\)−σ⁡\(R^t​\(x,a1\)−R^t​\(x,a2\)\)\)2\]\\displaystyle 4e^\{2\}\\sum\_\{i=1\}^\{t\-1\}\\mathbb\{E\}\_\{x\\sim d,\\;a^\{1\}\\sim\\widehat\{\\pi\}\_\{i\}^\{1\},\\;a^\{2\}\\sim\\pi\_\{\\rm ref\}\}\\left\[\\left\(\\sigma\\\!\\left\(R^\{\\star\}\(x,a^\{1\}\)\-R^\{\\star\}\(x,a^\{2\}\)\\right\)\-\\sigma\\\!\\left\(\\widehat\{R\}\_\{t\}\(x,a^\{1\}\)\-\\widehat\{R\}\_\{t\}\(x,a^\{2\}\)\\right\)\\right\)^\{2\}\\right\]≤\\displaystyle\\leq\\;24​e2​log⁡2​Nℛ​T3δ\.\\displaystyle 24e^\{2\}\\log\\frac\{2N\_\{\\mathcal\{R\}\}T^\{3\}\}\{\\delta\}\.The first inequality follows from the inverse Lipschitz property of the sigmoid function on\[−1,1\]\[\-1,1\], namely,\|u−v\|≤2​e​\|σ⁡\(u\)−σ⁡\(v\)\|\|u\-v\|\\leq 2e\\,\|\\sigma\(u\)\-\\sigma\(v\)\|for allu,v∈\[−1,1\]u,v\\in\[\-1,1\]\. The second inequality follows directly from Lemma[6](https://arxiv.org/html/2609.13564#Thmlemma6)\. This completes the proof\. ∎

#### D\.2\.3UCB\-Based Exploration for the BT Model

We next consider an uncertainty\-based variant ofORLHF\-GSunder the BT model\. The MLER^t\\widehat\{R\}\_\{t\}and the learned Gibbs policyπ^t1\\widehat\{\\pi\}\_\{t\}^\{1\}are constructed in the same way as in Algorithm[2](https://arxiv.org/html/2609.13564#alg2)\. The only modification is the sampling rule for the second action\. After observingxtx\_\{t\}and samplingat1∼π^t1\(⋅∣xt\)a\_\{t\}^\{1\}\\sim\\widehat\{\\pi\}\_\{t\}^\{1\}\(\\cdot\\mid x\_\{t\}\), we select

at2∈arg⁡maxa2∈𝒜⁡min⁡\{1,UBT2​\(λ,xt,at1,a2,ℛ,𝒟t−1BT\)\}\.a\_\{t\}^\{2\}\\in\\arg\\max\_\{a^\{2\}\\in\\mathcal\{A\}\}\\min\\left\\\{1,U\_\{\\operatorname\{BT\}\}^\{2\}\\left\(\\lambda,x\_\{t\},a\_\{t\}^\{1\},a^\{2\},\\mathcal\{R\};\\mathcal\{D\}\_\{t\-1\}^\{\\operatorname\{BT\}\}\\right\)\\right\\\}\.\(36\)The resulting action pair\(at1,at2\)\(a\_\{t\}^\{1\},a\_\{t\}^\{2\}\)is then used to obtain the preference feedback and update the MLE\. We refer to this sampling rule asBT\-UCB\.

###### Proof of Corollary[3](https://arxiv.org/html/2609.13564#Thmcorollary3)\.

LetGt:=JBT​\(π⋆\)−JBT​\(π^t1\)G\_\{t\}:=J\_\{\\operatorname\{BT\}\}\(\\pi^\{\\star\}\)\-J\_\{\\operatorname\{BT\}\}\(\\widehat\{\\pi\}\_\{t\}^\{1\}\)denote the instantaneous regret\. SinceJBT=JRFJ\_\{\\operatorname\{BT\}\}=J\_\{\\operatorname\{RF\}\},π⋆\\pi^\{\\star\}is the Gibbs policy induced byR⋆R^\{\\star\}, andπ^t1\\widehat\{\\pi\}\_\{t\}^\{1\}is the Gibbs policy induced byR^t\\widehat\{R\}\_\{t\}\. Following the same calculation as in the proof of Lemma[4](https://arxiv.org/html/2609.13564#Thmlemma4), we have

Gt\\displaystyle G\_\{t\}=η−1​𝔼x∼d​\[KL⁡\(π^t1,π⋆∣x\)\]\\displaystyle=\\eta^\{\-1\}\\mathbb\{E\}\_\{x\\sim d\}\\left\[\\operatorname\{KL\}\\left\(\\widehat\{\\pi\}\_\{t\}^\{1\},\\pi^\{\\star\}\\mid x\\right\)\\right\]=η−1​𝔼x∼d​\[log⁡𝔼a∼π^t1​\[exp⁡\(η⁡\(R⋆​\(x,a\)−R^t​\(x,a\)\)\)\]−η​𝔼a∼π^t1​\[R⋆​\(x,a\)−R^t​\(x,a\)\]\]\.\\displaystyle=\\eta^\{\-1\}\\mathbb\{E\}\_\{x\\sim d\}\\Bigg\[\\log\\mathbb\{E\}\_\{a\\sim\\widehat\{\\pi\}\_\{t\}^\{1\}\}\\left\[\\exp\\left\(\\eta\\left\(R^\{\\star\}\(x,a\)\-\\widehat\{R\}\_\{t\}\(x,a\)\\right\)\\right\)\\right\]\-\\eta\\mathbb\{E\}\_\{a\\sim\\widehat\{\\pi\}\_\{t\}^\{1\}\}\\left\[R^\{\\star\}\(x,a\)\-\\widehat\{R\}\_\{t\}\(x,a\)\\right\]\\Bigg\]\.\(37\)

##### Logarithmic bound\.

By Hoeffding’s lemma, for everyx∈𝒳x\\in\\mathcal\{X\},

log⁡𝔼a∼π^t1​\[exp⁡\(η⁡\(R⋆​\(x,a\)−R^t​\(x,a\)\)\)\]−η​𝔼a∼π^t1​\[R⋆​\(x,a\)−R^t​\(x,a\)\]\\displaystyle\\log\\mathbb\{E\}\_\{a\\sim\\widehat\{\\pi\}\_\{t\}^\{1\}\}\\left\[\\exp\\left\(\\eta\\left\(R^\{\\star\}\(x,a\)\-\\widehat\{R\}\_\{t\}\(x,a\)\\right\)\\right\)\\right\]\-\\eta\\mathbb\{E\}\_\{a\\sim\\widehat\{\\pi\}\_\{t\}^\{1\}\}\\left\[R^\{\\star\}\(x,a\)\-\\widehat\{R\}\_\{t\}\(x,a\)\\right\]≤η28​\(maxa∈𝒜⁡\(R⋆​\(x,a\)−R^t​\(x,a\)\)−mina∈𝒜⁡\(R⋆​\(x,a\)−R^t​\(x,a\)\)\)2\.\\displaystyle\\leq\\frac\{\\eta^\{2\}\}\{8\}\\Bigg\(\\max\_\{a\\in\\mathcal\{A\}\}\\left\(R^\{\\star\}\(x,a\)\-\\widehat\{R\}\_\{t\}\(x,a\)\\right\)\-\\min\_\{a\\in\\mathcal\{A\}\}\\left\(R^\{\\star\}\(x,a\)\-\\widehat\{R\}\_\{t\}\(x,a\)\\right\)\\Bigg\)^\{2\}\.Hence,

Gt≤η8​𝔼x∼d​\[\(maxa∈𝒜⁡\(R⋆​\(x,a\)−R^t​\(x,a\)\)−mina∈𝒜⁡\(R⋆​\(x,a\)−R^t​\(x,a\)\)\)2\]\.\\displaystyle G\_\{t\}\\leq\\frac\{\\eta\}\{8\}\\mathbb\{E\}\_\{x\\sim d\}\\Bigg\[\\Bigg\(\\max\_\{a\\in\\mathcal\{A\}\}\\left\(R^\{\\star\}\(x,a\)\-\\widehat\{R\}\_\{t\}\(x,a\)\\right\)\-\\min\_\{a\\in\\mathcal\{A\}\}\\left\(R^\{\\star\}\(x,a\)\-\\widehat\{R\}\_\{t\}\(x,a\)\\right\)\\Bigg\)^\{2\}\\Bigg\]\.\(38\)
For any fixed\(x,a1\)\(x,a^\{1\}\), sinceR⋆​\(x,a1\)−R^t​\(x,a1\)R^\{\\star\}\(x,a^\{1\}\)\-\\widehat\{R\}\_\{t\}\(x,a^\{1\}\)lies between the maximum and minimum appearing in \([38](https://arxiv.org/html/2609.13564#A4.E38)\),

\(maxa∈𝒜⁡\(R⋆​\(x,a\)−R^t​\(x,a\)\)−mina∈𝒜⁡\(R⋆​\(x,a\)−R^t​\(x,a\)\)\)2\\displaystyle\\Bigg\(\\max\_\{a\\in\\mathcal\{A\}\}\\left\(R^\{\\star\}\(x,a\)\-\\widehat\{R\}\_\{t\}\(x,a\)\\right\)\-\\min\_\{a\\in\\mathcal\{A\}\}\\left\(R^\{\\star\}\(x,a\)\-\\widehat\{R\}\_\{t\}\(x,a\)\\right\)\\Bigg\)^\{2\}≤4​maxa2∈𝒜​\(R⋆​\(x,a1\)−R⋆​\(x,a2\)−R^t​\(x,a1\)\+R^t​\(x,a2\)\)2\.\\displaystyle\\qquad\\leq 4\\max\_\{a^\{2\}\\in\\mathcal\{A\}\}\\Big\(R^\{\\star\}\(x,a^\{1\}\)\-R^\{\\star\}\(x,a^\{2\}\)\-\\widehat\{R\}\_\{t\}\(x,a^\{1\}\)\+\\widehat\{R\}\_\{t\}\(x,a^\{2\}\)\\Big\)^\{2\}\.Averaging overa1∼π^t1\(⋅∣x\)a^\{1\}\\sim\\widehat\{\\pi\}\_\{t\}^\{1\}\(\\cdot\\mid x\)and substituting into \([38](https://arxiv.org/html/2609.13564#A4.E38)\) gives

Gt≤η2​𝔼x∼d,a1∼π^t1​\[maxa2∈𝒜⁡\(R⋆​\(x,a1\)−R⋆​\(x,a2\)−R^t​\(x,a1\)\+R^t​\(x,a2\)\)2\]\.\\displaystyle G\_\{t\}\\leq\\frac\{\\eta\}\{2\}\\mathbb\{E\}\_\{\\begin\{subarray\}\{c\}x\\sim d,\\,a^\{1\}\\sim\\widehat\{\\pi\}\_\{t\}^\{1\}\\end\{subarray\}\}\\Bigg\[\\max\_\{a^\{2\}\\in\\mathcal\{A\}\}\\Big\(R^\{\\star\}\(x,a^\{1\}\)\-R^\{\\star\}\(x,a^\{2\}\)\-\\widehat\{R\}\_\{t\}\(x,a^\{1\}\)\+\\widehat\{R\}\_\{t\}\(x,a^\{2\}\)\\Big\)^\{2\}\\Bigg\]\.\(39\)
Applying Lemma[12](https://arxiv.org/html/2609.13564#Thmlemma12)to the preference functionsσ⁡\(R⁡\(x,a1\)−R⁡\(x,a2\)\)\\sigma\(R\(x,a^\{1\}\)\-R\(x,a^\{2\}\)\),R∈ℛR\\in\\mathcal\{R\}, and using the inverse Lipschitz property of the sigmoid function on\[−1,1\]\[\-1,1\], with probability at least1−δ/21\-\\delta/2, simultaneously for allt∈\[T\]t\\in\[T\],

∑i=1t−1\(R⋆​\(xi,ai1\)−R⋆​\(xi,ai2\)−R^t​\(xi,ai1\)\+R^t​\(xi,ai2\)\)2≤8​e2​log⁡2​Nℛ​Tδ\.\\displaystyle\\sum\_\{i=1\}^\{t\-1\}\\Big\(R^\{\\star\}\(x\_\{i\},a\_\{i\}^\{1\}\)\-R^\{\\star\}\(x\_\{i\},a\_\{i\}^\{2\}\)\-\\widehat\{R\}\_\{t\}\(x\_\{i\},a\_\{i\}^\{1\}\)\+\\widehat\{R\}\_\{t\}\(x\_\{i\},a\_\{i\}^\{2\}\)\\Big\)^\{2\}\\leq 8e^\{2\}\\log\\frac\{2N\_\{\\mathcal\{R\}\}T\}\{\\delta\}\.\(40\)SinceR⋆,R^t∈ℛR^\{\\star\},\\widehat\{R\}\_\{t\}\\in\\mathcal\{R\}, the definition ofUBTU\_\{\\operatorname\{BT\}\}and \([40](https://arxiv.org/html/2609.13564#A4.E40)\) imply

\|R⋆​\(x,a1\)−R⋆​\(x,a2\)−R^t​\(x,a1\)\+R^t​\(x,a2\)\|≤UBT​\(λ,x,a1,a2,ℛ,𝒟t−1BT\)​λ\+8​e2​log⁡2​Nℛ​Tδ\.\\displaystyle\\Big\|R^\{\\star\}\(x,a^\{1\}\)\-R^\{\\star\}\(x,a^\{2\}\)\-\\widehat\{R\}\_\{t\}\(x,a^\{1\}\)\+\\widehat\{R\}\_\{t\}\(x,a^\{2\}\)\\Big\|\\leq U\_\{\\operatorname\{BT\}\}\\left\(\\lambda,x,a^\{1\},a^\{2\},\\mathcal\{R\};\\mathcal\{D\}\_\{t\-1\}^\{\\operatorname\{BT\}\}\\right\)\\sqrt\{\\lambda\+8e^\{2\}\\log\\frac\{2N\_\{\\mathcal\{R\}\}T\}\{\\delta\}\}\.Therefore, forλ≤4​e2​log⁡\(2​Nℛ​T/δ\)\\lambda\\leq 4e^\{2\}\\log\(2N\_\{\\mathcal\{R\}\}T/\\delta\), and using the fact that the absolute pairwise reward\-difference error is at most22,

\(R⋆​\(x,a1\)−R⋆​\(x,a2\)−R^t​\(x,a1\)\+R^t​\(x,a2\)\)2≤12​e2​log⁡2​Nℛ​Tδ​min​\{1,UBT2​\(λ,x,a1,a2,ℛ,𝒟t−1BT\)\}\.\\displaystyle\\Big\(R^\{\\star\}\(x,a^\{1\}\)\-R^\{\\star\}\(x,a^\{2\}\)\-\\widehat\{R\}\_\{t\}\(x,a^\{1\}\)\+\\widehat\{R\}\_\{t\}\(x,a^\{2\}\)\\Big\)^\{2\}\\leq 12e^\{2\}\\log\\frac\{2N\_\{\\mathcal\{R\}\}T\}\{\\delta\}\\min\\left\\\{1,U\_\{\\operatorname\{BT\}\}^\{2\}\\left\(\\lambda,x,a^\{1\},a^\{2\},\\mathcal\{R\};\\mathcal\{D\}\_\{t\-1\}^\{\\operatorname\{BT\}\}\\right\)\\right\\\}\.\(41\)Combining \([39](https://arxiv.org/html/2609.13564#A4.E39)\) and \([41](https://arxiv.org/html/2609.13564#A4.E41)\) gives

Gt≤6​e2​η​log⁡2​Nℛ​Tδ​𝔼x∼d,a1∼π^t1​\[maxa2∈𝒜⁡min⁡\{1,UBT2​\(λ,x,a1,a2,ℛ,𝒟t−1BT\)\}\]\.\\displaystyle G\_\{t\}\\leq 6e^\{2\}\\eta\\log\\frac\{2N\_\{\\mathcal\{R\}\}T\}\{\\delta\}\\mathbb\{E\}\_\{\\begin\{subarray\}\{c\}x\\sim d,\\,a^\{1\}\\sim\\widehat\{\\pi\}\_\{t\}^\{1\}\\end\{subarray\}\}\\Bigg\[\\max\_\{a^\{2\}\\in\\mathcal\{A\}\}\\min\\Bigg\\\{1,U\_\{\\operatorname\{BT\}\}^\{2\}\\left\(\\lambda,x,a^\{1\},a^\{2\},\\mathcal\{R\};\\mathcal\{D\}\_\{t\-1\}^\{\\operatorname\{BT\}\}\\right\)\\Bigg\\\}\\Bigg\]\.\(42\)
SinceBT\-UCBselectsat2a\_\{t\}^\{2\}according to \([36](https://arxiv.org/html/2609.13564#A4.E36)\), conditioned on the history before roundtt, the expectation in \([42](https://arxiv.org/html/2609.13564#A4.E42)\) is exactly the conditional expectation ofmin⁡\{1,UBT2​\(λ,xt,at1,at2,ℛ,𝒟t−1BT\)\}\\min\\left\\\{1,U\_\{\\operatorname\{BT\}\}^\{2\}\\left\(\\lambda,x\_\{t\},a\_\{t\}^\{1\},a\_\{t\}^\{2\},\\mathcal\{R\};\\mathcal\{D\}\_\{t\-1\}^\{\\operatorname\{BT\}\}\\right\)\\right\\\}\. Moreover, since the definition ofdBT​\(λ,ℛ,T\)d\_\{\\operatorname\{BT\}\}\(\\lambda,\\mathcal\{R\},T\)takes the supremum over all context\-action\-pair sequences, for every realized sequence\{\(xt,at1,at2\)\}t=1T\\\{\(x\_\{t\},a\_\{t\}^\{1\},a\_\{t\}^\{2\}\)\\\}\_\{t=1\}^\{T\},

∑t=1Tmin⁡\{1,UBT2​\(λ,xt,at1,at2,ℛ,𝒟t−1BT\)\}≤dBT​\(λ,ℛ,T\)\.\\displaystyle\\sum\_\{t=1\}^\{T\}\\min\\left\\\{1,U\_\{\\operatorname\{BT\}\}^\{2\}\\left\(\\lambda,x\_\{t\},a\_\{t\}^\{1\},a\_\{t\}^\{2\},\\mathcal\{R\};\\mathcal\{D\}\_\{t\-1\}^\{\\operatorname\{BT\}\}\\right\)\\right\\\}\\leq d\_\{\\operatorname\{BT\}\}\(\\lambda,\\mathcal\{R\},T\)\.Applying the same predictable\-to\-realized concentration argument as in the proof of Corollary[2](https://arxiv.org/html/2609.13564#Thmcorollary2), with confidence levelδ/2\\delta/2, gives

∑t=1T𝔼x∼d,a1∼π^t1​\[maxa2∈𝒜⁡min⁡\{1,UBT2​\(λ,x,a1,a2,ℛ,𝒟t−1BT\)\}\]=O⁡\(dBT​\(λ,ℛ,T\)\+log⁡1δ\)\.\\displaystyle\\sum\_\{t=1\}^\{T\}\\mathbb\{E\}\_\{\\begin\{subarray\}\{c\}x\\sim d,\\,a^\{1\}\\sim\\widehat\{\\pi\}\_\{t\}^\{1\}\\end\{subarray\}\}\\Bigg\[\\max\_\{a^\{2\}\\in\\mathcal\{A\}\}\\min\\Bigg\\\{1,U\_\{\\operatorname\{BT\}\}^\{2\}\\left\(\\lambda,x,a^\{1\},a^\{2\},\\mathcal\{R\};\\mathcal\{D\}\_\{t\-1\}^\{\\operatorname\{BT\}\}\\right\)\\Bigg\\\}\\Bigg\]=O\\left\(d\_\{\\operatorname\{BT\}\}\(\\lambda,\\mathcal\{R\},T\)\+\\log\\frac\{1\}\{\\delta\}\\right\)\.\(43\)Taking a union bound over the MLE confidence event and the predictable\-to\-realized concentration event, with probability at least1−δ1\-\\delta,

RegBT⁡\(T\)=O⁡\(η⁡\(dBT​\(λ,ℛ,T\)\+log⁡1δ\)​log⁡Nℛ​Tδ\)\.\\displaystyle\\operatorname\{Reg\}\_\{\\operatorname\{BT\}\}\(T\)=O\\left\(\\eta\\left\(d\_\{\\operatorname\{BT\}\}\(\\lambda,\\mathcal\{R\},T\)\+\\log\\frac\{1\}\{\\delta\}\\right\)\\log\\frac\{N\_\{\\mathcal\{R\}\}T\}\{\\delta\}\\right\)\.

##### η\\eta\-independent bound\.

By the optimality ofπ^t1\\widehat\{\\pi\}\_\{t\}^\{1\}underR^t\\widehat\{R\}\_\{t\}, we have

𝔼a∼π⋆​\[R^t​\(x,a\)\]−η−1​KL⁡\(π⋆,πref∣x\)≤𝔼a∼π^t1​\[R^t​\(x,a\)\]−η−1​KL⁡\(π^t1,πref∣x\)\.\\displaystyle\\mathbb\{E\}\_\{a\\sim\\pi^\{\\star\}\}\\left\[\\widehat\{R\}\_\{t\}\(x,a\)\\right\]\-\\eta^\{\-1\}\\operatorname\{KL\}\\left\(\\pi^\{\\star\},\\pi\_\{\\rm ref\}\\mid x\\right\)\\leq\\mathbb\{E\}\_\{a\\sim\\widehat\{\\pi\}\_\{t\}^\{1\}\}\\left\[\\widehat\{R\}\_\{t\}\(x,a\)\\right\]\-\\eta^\{\-1\}\\operatorname\{KL\}\\left\(\\widehat\{\\pi\}\_\{t\}^\{1\},\\pi\_\{\\rm ref\}\\mid x\\right\)\.Therefore, adding and subtractingR^t\\widehat\{R\}\_\{t\}in the KL\-regularized objective gives

Gt\\displaystyle G\_\{t\}≤𝔼x∼d​\[𝔼a∼π⋆​\[R⋆​\(x,a\)−R^t​\(x,a\)\]−𝔼a∼π^t1​\[R⋆​\(x,a\)−R^t​\(x,a\)\]\]\\displaystyle\\leq\\mathbb\{E\}\_\{x\\sim d\}\\Bigg\[\\mathbb\{E\}\_\{a\\sim\\pi^\{\\star\}\}\\left\[R^\{\\star\}\(x,a\)\-\\widehat\{R\}\_\{t\}\(x,a\)\\right\]\-\\mathbb\{E\}\_\{a\\sim\\widehat\{\\pi\}\_\{t\}^\{1\}\}\\left\[R^\{\\star\}\(x,a\)\-\\widehat\{R\}\_\{t\}\(x,a\)\\right\]\\Bigg\]≤𝔼x∼d​\[maxa∈𝒜⁡\(R⋆​\(x,a\)−R^t​\(x,a\)\)−mina∈𝒜⁡\(R⋆​\(x,a\)−R^t​\(x,a\)\)\],\\displaystyle\\leq\\mathbb\{E\}\_\{x\\sim d\}\\Bigg\[\\max\_\{a\\in\\mathcal\{A\}\}\\left\(R^\{\\star\}\(x,a\)\-\\widehat\{R\}\_\{t\}\(x,a\)\\right\)\-\\min\_\{a\\in\\mathcal\{A\}\}\\left\(R^\{\\star\}\(x,a\)\-\\widehat\{R\}\_\{t\}\(x,a\)\\right\)\\Bigg\],where the second inequality follows since the expectation ofR⋆​\(x,a\)−R^t​\(x,a\)R^\{\\star\}\(x,a\)\-\\widehat\{R\}\_\{t\}\(x,a\)under any policy lies between its minimum and maximum over𝒜\\mathcal\{A\}\.

For any fixed\(x,a1\)\(x,a^\{1\}\),R⋆​\(x,a1\)−R^t​\(x,a1\)R^\{\\star\}\(x,a^\{1\}\)\-\\widehat\{R\}\_\{t\}\(x,a^\{1\}\)lies between the same minimum and maximum\. Hence, its distance from at least one of the two endpoints is at least half of the range, which implies

maxa∈𝒜⁡\(R⋆​\(x,a\)−R^t​\(x,a\)\)−mina∈𝒜⁡\(R⋆​\(x,a\)−R^t​\(x,a\)\)≤2​maxa2∈𝒜​\|R⋆​\(x,a1\)−R⋆​\(x,a2\)−R^t​\(x,a1\)\+R^t​\(x,a2\)\|\.\\displaystyle\\max\_\{a\\in\\mathcal\{A\}\}\\left\(R^\{\\star\}\(x,a\)\-\\widehat\{R\}\_\{t\}\(x,a\)\\right\)\-\\min\_\{a\\in\\mathcal\{A\}\}\\left\(R^\{\\star\}\(x,a\)\-\\widehat\{R\}\_\{t\}\(x,a\)\\right\)\\leq 2\\max\_\{a^\{2\}\\in\\mathcal\{A\}\}\\Big\|R^\{\\star\}\(x,a^\{1\}\)\-R^\{\\star\}\(x,a^\{2\}\)\-\\widehat\{R\}\_\{t\}\(x,a^\{1\}\)\+\\widehat\{R\}\_\{t\}\(x,a^\{2\}\)\\Big\|\.Since this inequality holds for everya1a^\{1\}, squaring both sides and averaging overa1∼π^t1\(⋅∣x\)a^\{1\}\\sim\\widehat\{\\pi\}\_\{t\}^\{1\}\(\\cdot\\mid x\)yields

maxa∈𝒜⁡\(R⋆​\(x,a\)−R^t​\(x,a\)\)−mina∈𝒜⁡\(R⋆​\(x,a\)−R^t​\(x,a\)\)\\displaystyle\\max\_\{a\\in\\mathcal\{A\}\}\\left\(R^\{\\star\}\(x,a\)\-\\widehat\{R\}\_\{t\}\(x,a\)\\right\)\-\\min\_\{a\\in\\mathcal\{A\}\}\\left\(R^\{\\star\}\(x,a\)\-\\widehat\{R\}\_\{t\}\(x,a\)\\right\)≤2​𝔼a1∼π^t1​\[maxa2∈𝒜⁡\(R⋆​\(x,a1\)−R⋆​\(x,a2\)−R^t​\(x,a1\)\+R^t​\(x,a2\)\)2\]\.\\displaystyle\\qquad\\leq 2\\sqrt\{\\mathbb\{E\}\_\{a^\{1\}\\sim\\widehat\{\\pi\}\_\{t\}^\{1\}\}\\left\[\\max\_\{a^\{2\}\\in\\mathcal\{A\}\}\\Big\(R^\{\\star\}\(x,a^\{1\}\)\-R^\{\\star\}\(x,a^\{2\}\)\-\\widehat\{R\}\_\{t\}\(x,a^\{1\}\)\+\\widehat\{R\}\_\{t\}\(x,a^\{2\}\)\\Big\)^\{2\}\\right\]\}\.Consequently,

Gt\\displaystyle G\_\{t\}≤2​𝔼x∼d​𝔼a1∼π^t1​\[maxa2∈𝒜⁡\(R⋆​\(x,a1\)−R⋆​\(x,a2\)−R^t​\(x,a1\)\+R^t​\(x,a2\)\)2\]\\displaystyle\\leq 2\\mathbb\{E\}\_\{x\\sim d\}\\sqrt\{\\mathbb\{E\}\_\{a^\{1\}\\sim\\widehat\{\\pi\}\_\{t\}^\{1\}\}\\left\[\\max\_\{a^\{2\}\\in\\mathcal\{A\}\}\\Big\(R^\{\\star\}\(x,a^\{1\}\)\-R^\{\\star\}\(x,a^\{2\}\)\-\\widehat\{R\}\_\{t\}\(x,a^\{1\}\)\+\\widehat\{R\}\_\{t\}\(x,a^\{2\}\)\\Big\)^\{2\}\\right\]\}≤2​𝔼x∼d,a1∼π^t1​\[maxa2∈𝒜⁡\(R⋆​\(x,a1\)−R⋆​\(x,a2\)−R^t​\(x,a1\)\+R^t​\(x,a2\)\)2\],\\displaystyle\\leq 2\\sqrt\{\\mathbb\{E\}\_\{\\begin\{subarray\}\{c\}x\\sim d,\\,a^\{1\}\\sim\\widehat\{\\pi\}\_\{t\}^\{1\}\\end\{subarray\}\}\\left\[\\max\_\{a^\{2\}\\in\\mathcal\{A\}\}\\Big\(R^\{\\star\}\(x,a^\{1\}\)\-R^\{\\star\}\(x,a^\{2\}\)\-\\widehat\{R\}\_\{t\}\(x,a^\{1\}\)\+\\widehat\{R\}\_\{t\}\(x,a^\{2\}\)\\Big\)^\{2\}\\right\]\},where the last inequality follows from Jensen’s inequality\. Applying \([41](https://arxiv.org/html/2609.13564#A4.E41)\),

Gt\\displaystyle G\_\{t\}≤4​3​e​log⁡2​Nℛ​Tδ​𝔼x∼d,a1∼π^t1​\[maxa2∈𝒜⁡min⁡\{1,UBT2​\(λ,x,a1,a2,ℛ,𝒟t−1BT\)\}\]\.\\displaystyle\\leq 4\\sqrt\{3\}\\,e\\sqrt\{\\log\\frac\{2N\_\{\\mathcal\{R\}\}T\}\{\\delta\}\}\\sqrt\{\\mathbb\{E\}\_\{\\begin\{subarray\}\{c\}x\\sim d,\\,a^\{1\}\\sim\\widehat\{\\pi\}\_\{t\}^\{1\}\\end\{subarray\}\}\\left\[\\max\_\{a^\{2\}\\in\\mathcal\{A\}\}\\min\\left\\\{1,U\_\{\\operatorname\{BT\}\}^\{2\}\\left\(\\lambda,x,a^\{1\},a^\{2\},\\mathcal\{R\};\\mathcal\{D\}\_\{t\-1\}^\{\\operatorname\{BT\}\}\\right\)\\right\\\}\\right\]\}\.Summing overttand applying Cauchy–Schwarz together with \([43](https://arxiv.org/html/2609.13564#A4.E43)\) gives

RegBT⁡\(T\)=O⁡\(T⁡\(dBT​\(λ,ℛ,T\)\+log⁡1δ\)​log⁡Nℛ​Tδ\)\.\\displaystyle\\operatorname\{Reg\}\_\{\\operatorname\{BT\}\}\(T\)=O\\left\(\\sqrt\{T\\left\(d\_\{\\operatorname\{BT\}\}\(\\lambda,\\mathcal\{R\},T\)\+\\log\\frac\{1\}\{\\delta\}\\right\)\\log\\frac\{N\_\{\\mathcal\{R\}\}T\}\{\\delta\}\}\\right\)\.Taking the minimum of the two bounds completes the proof\. ∎

## Appendix EAuxiliary Lemmas

###### Lemma 9\(Freedman’s inequality\)\.

Let\{Mi\}i=1t\\\{M\_\{i\}\\\}\_\{i=1\}^\{t\}be a martingale difference sequence satisfying\|Mi\|≤b\|M\_\{i\}\|\\leq bfor alli∈\[t\]i\\in\[t\]\. Then, for anyδ<1/e2\\delta<1/e^\{2\}, with probability at least1−\(log2⁡t\)​δ1\-\(\\log\_\{2\}t\)\\delta,

∑i=1tMi≤4​∑i=1tVar⁡\[Mi∣\{Mj\}j=1i−1\]​log⁡\(1/δ\)\+2​b​log⁡\(1/δ\)\.\\sum\_\{i=1\}^\{t\}M\_\{i\}\\leq 4\\sqrt\{\\sum\_\{i=1\}^\{t\}\\operatorname\{Var\}\[M\_\{i\}\\mid\\\{M\_\{j\}\\\}\_\{j=1\}^\{i\-1\}\]\\log\(1/\\delta\)\}\+2b\\log\(1/\\delta\)\.

###### Lemma 10\(Lemma 4\.2 in[Agarwal et al\. \(2012\)](https://arxiv.org/html/2609.13564#bib.bib5)\)\.

Fix any reward functionR∈ℛR\\in\\mathcal\{R\}\. Letx∼dx\\sim d,a∼π\(⋅\|x\)a\\sim\\pi\(\\cdot\|x\), andr∈\[0,1\]r\\in\[0,1\]be a random reward satisfying𝔼\[r∣x,a\]=R⋆\(x,a\)\\mathbb\{E\}\[r\\mid x,a\]=R^\{\\star\}\(x,a\)\. Define

YR=\(R⁡\(x,a\)−r\)2−\(R⋆​\(x,a\)−r\)2\.Y\_\{R\}=\(R\(x,a\)\-r\)^\{2\}\-\(R^\{\\star\}\(x,a\)\-r\)^\{2\}\.Then,

𝔼⁡\[YR\]=𝔼x∼d​𝔼a∼π​\[\(R⁡\(x,a\)−R⋆​\(x,a\)\)2\],\\mathbb\{E\}\[Y\_\{R\}\]=\\mathbb\{E\}\_\{x\\sim d\}\\mathbb\{E\}\_\{a\\sim\\pi\}\\\!\\left\[\(R\(x,a\)\-R^\{\\star\}\(x,a\)\)^\{2\}\\right\],and

Var⁡\[YR\]≤4​𝔼​\[YR\]\.\\operatorname\{Var\}\[Y\_\{R\}\]\\leq 4\\mathbb\{E\}\[Y\_\{R\}\]\.

###### Lemma 11\(Lemma C\.1 in[Zhao et al\. \(2025b\)](https://arxiv.org/html/2609.13564#bib.bib2)\)\.

Letℛ\\mathcal\{R\}be a finite function class mapping𝒵\\mathcal\{Z\}toℝ\\mathbb\{R\}, with cardinalityNℛN\_\{\\mathcal\{R\}\}, and suppose thatR⋆∈ℛR^\{\\star\}\\in\\mathcal\{R\}\. Consider a sequence of adaptively selected inputs\{zt\}t≥1\\\{z\_\{t\}\\\}\_\{t\\geq 1\}and observationsrt=R⋆​\(zt\)\+ϵtr\_\{t\}=R^\{\\star\}\(z\_\{t\}\)\+\\epsilon\_\{t\}, the noiseϵt\\epsilon\_\{t\}is zero\-mean and11\-sub\-Gaussian\. Define the LS estimatorR^t∈arg⁡min⁡∑i=1t−1R∈ℛ⁡\(R⁡\(zi\)−ri\)2\\widehat\{R\}\_\{t\}\\in\\arg\\min\_\{R\\in\\mathcal\{R\}\}\\sum\_\{i=1\}^\{t\-1\}\\bigl\(R\(z\_\{i\}\)\-r\_\{i\}\\bigr\)^\{2\}\. Then, for anyδ∈\(0,1\)\\delta\\in\(0,1\), with probability at least1−δ1\-\\delta, the following inequality holds simultaneously for allt∈\[T\]t\\in\[T\]:

∑i=1t−1\(R^t​\(zi\)−R⋆​\(zi\)\)2≤8​log⁡Nℛ​Tδ\.\\sum\_\{i=1\}^\{t\-1\}\\bigl\(\\widehat\{R\}\_\{t\}\(z\_\{i\}\)\-R^\{\\star\}\(z\_\{i\}\)\\bigr\)^\{2\}\\leq 8\\log\\frac\{N\_\{\\mathcal\{R\}\}T\}\{\\delta\}\.

###### Lemma 12\.

\(Lemma 3 in[Wu et al\. \(2025\)](https://arxiv.org/html/2609.13564#bib.bib8)\) Let𝒫\\mathcal\{P\}be a finite function class with cardinalityN𝒫N\_\{\\mathcal\{P\}\}\. Suppose the training data\{\(xi,ai1,ai2,yi\)\}i=1t\\\{\(x\_\{i\},a\_\{i\}^\{1\},a\_\{i\}^\{2\},y\_\{i\}\)\\\}\_\{i=1\}^\{t\}is generated according toyi∼Ber⁡\(P⋆​\(xi,ai1,ai2\)\)y\_\{i\}\\sim\\mathrm\{Ber\}\\\!\\left\(P^\{\\star\}\(x\_\{i\},a\_\{i\}^\{1\},a\_\{i\}^\{2\}\)\\right\), whereP⋆∈𝒫P^\{\\star\}\\in\\mathcal\{P\}\. LetP^t\\widehat\{P\}\_\{t\}be the MLE estimator over𝒫\\mathcal\{P\}computed from the samples\{\(xi,ai1,ai2,yi\)\}i=1t−1\\\{\(x\_\{i\},a\_\{i\}^\{1\},a\_\{i\}^\{2\},y\_\{i\}\)\\\}\_\{i=1\}^\{t\-1\}\. Then, with probability at least1−δ1\-\\delta, simultaneously for allt∈\[T\]t\\in\[T\],

∑i=1t−1\(P^t​\(xi,ai1,ai2\)−P⋆​\(xi,ai1,ai2\)\)2≤2​log⁡N𝒫​Tδ\.\\sum\_\{i=1\}^\{t\-1\}\\Big\(\\widehat\{P\}\_\{t\}\(x\_\{i\},a\_\{i\}^\{1\},a\_\{i\}^\{2\}\)\-P^\{\\star\}\(x\_\{i\},a\_\{i\}^\{1\},a\_\{i\}^\{2\}\)\\Big\)^\{2\}\\leq 2\\log\\frac\{N\_\{\\mathcal\{P\}\}T\}\{\\delta\}\.