Towards Efficient Online Exploration for Reinforcement Learning with Human Feedback

## Abstract

Abstract Reinforcement learning with human feedback (RLHF), which learns a reward model from human preference data and then optimizes a policy to favor preferred responses, has emerged as a central paradigm for aligning large language models (LLMs) with human preferences. In this paper, we investigate exploration principles for online RLHF, where one seeks to adaptively collect new preference data to refine both the reward model and the policy in a data-efficient manner. By examining existing optimism-based exploration algorithms, we identify a drawback in their sampling protocol: they tend to gather comparisons that fail to reduce the most informative uncertainties in reward differences, and we prove lower bounds showing that such methods can incur linear regret over exponentially long horizons. Motivated by this insight, we propose a new exploration scheme that directs preference queries toward reducing uncertainty in reward differences most relevant to policy improvement. Under a multi-armed bandit model of RLHF, we establish regret bounds of order T ( β + 1 ) / ( β + 2 ) T^{(\beta+1)/(\beta+2)} , where β > 0 \beta>0 is a hyperparameter that balances reward maximization against mitigating distribution shift. To our knowledge, this is the first online RLHF algorithm with regret scaling polynomially in all model parameters.

## 1 Introduction

Large language models (LLMs) have demonstrated remarkable capabilities across a wide range of natural language tasks, yet aligning their behavior with human preferences remains a central challenge. A widely adopted solution is reinforcement learning with human feedback (RLHF), which fine-tunes a pretrained LLM using human preference data (Christiano et al.,, 2017; Ziegler et al.,, 2019; Bai et al.,, 2022). The standard RLHF pipeline involves three stages: (i) supervised fine-tuning (SFT) on human-written demonstrations to produce a baseline model; (ii) training a reward model from human preference comparisons (Bradley and Terry,, 1952); and (iii) optimizing the LLM with reinforcement learning against the learned reward. This framework has been instrumental in the success of instruction-following LLMs such as InstructGPT (Ouyang et al.,, 2022) and ChatGPT (OpenAI,, 2023), enabling models to produce responses that are more helpful, safe, and aligned with human expectations.

Despite this progress, most existing RLHF implementations are offline (Zhao et al.,, 2023; Rafailov et al.,, 2024; Azar et al.,, 2024): the preference data is collected once from static policies, and the reward model is trained on this fixed dataset (Ivison et al.,, 2023; Zhu et al.,, 2024; Shi et al.,, 2025). While effective, offline RLHF has inherent limitations—It cannot adaptively explore the enormous space of natural language, leading to inefficient use of expensive human feedback. In contrast, online RLHF offers a more powerful alternative: the policy iteratively collects new preference data, updates the reward model, and improves itself based on these updates (Guo et al.,, 2024; Xiong et al.,, 2023; Chen et al.,, 2024; Rosset et al.,, 2024; Dong et al.,, 2024; Feng et al.,, 2025). This interactive loop has the potential to greatly improve both alignment quality and sample efficiency. However, realizing this potential requires principled approaches to exploration, i.e., deciding which comparisons to query in order to most effectively reduce uncertainty in reward estimation.

A natural candidate for encouraging and guiding exploration is the principle of optimism (Lai and Robbins,, 1985; Lattimore and Szepesvári,, 2020), which acts as if the environment is more optimistic than currently estimated, within the limits of statistical uncertainty based on all data that has been observed so far. It is usually implemented by adding an uncertainty-based bonus to reward or value estimates, thereby prioritizing actions whose values are uncertain but potentially high. This has yielded provably efficient algorithms in standard RL (see e.g., Jin et al., (2018); Zanette and Brunskill, (2019); Russo and Van Roy, (2013); Azar et al., (2017)).
However, extending this principle to RLHF introduces new difficulties, where feedback comes not as a single reward but as a difference between rewards of two actions. The key challenge is to determine the action pairs with the large uncertainties most relevant to policy improvement.
A few recent works achieved important progress towards designing sample-efficient online RLHF algorithms based on the optimism principle (Cen et al.,, 2025; Zhang et al.,, 2025; Xie et al.,, 2025). However the existing theoretical guarantees still exhibit exponential dependency on certain model parameters, which potentially leads to inefficient exploration.

With this context, this paper makes contribution towards designing efficient online exploration schemes for RLHF with provable guarantees. By analyzing the existing algorithms in the seminal works (Cen et al.,, 2025; Xie et al.,, 2025; Zhang et al.,, 2025), we discuss their inadequacy in exploring the action pairs with the large uncertainties most relevant to policy improvement, and construct lower bounds to show that the exponential dependency on certain parameters is unavoidable in their regret. Based on these insights, we propose a new exploration scheme for RLHF that adopts a different sampling protocol, and establish a regret bound that depends polynomially on all model parameters.

## 2 Model set-up

#### Preliminaries.

In RLHF, the prompt space $\mathcal{X}$ refers to the collection
of all possible inputs or queries that a user might provide to the
model. The answer (or action) space $\mathcal{A}$ is the set of all possible
outputs the model can generate in reply to a given prompt. A language
model is a policy $\pi:\mathcal{X}\to\Delta(\mathcal{A})$ that defines
a probability distribution $\pi(\cdot\,|\,x)$ over $\mathcal{A}$
conditioned on a prompt $x\in\mathcal{X}$, specifying how likely
the model is to produce each potential response.
The pipeline of RLHF starts with supervised fine-tuning (SFT), where a reference policy $\pi_{\mathsf{ref}}:\mathcal{X}\to\Delta(\mathcal{A})$ is obtained by fine-tuning a pre-trained LLM on a dataset of prompts paired with high-quality answers written by humans. SVT provides an initialization that stabilizes and improves the effectiveness of the subsequent training stages that aligns the LLM with human preferences.

#### Reward modeling.

To translate human preferences into a trainable objective, one need
to model how an oracle (e.g., a human annotator) rank two answers
$a_{1}$ and $a_{2}$ given prompt $x$. Following a line of prior
works (e.g., Cen et al., (2025); Xie et al., (2025); Zhang et al., (2025)),
we assume that preferences follow the Bradley-Terry model (Bradley and Terry,, 1952)

$$ $\mathbb{P}(a_{1}\succ a_{2}\,|\,x)=\frac{\exp(r^{\star}(x,a_{1}))}{\exp(r^{\star}(x,a_{1}))+\exp(r^{\star}(x,a_{2}))}=\sigma\left(r^{\star}(x,a_{1})-r^{\star}(x,a_{2})\right).$ (2.1) $$

Here $r^{\star}:\mathcal{X}\times\mathcal{A}\to[0,r_{\max}]$ is an
underlying reward function of an answer given a prompt, $a_{1}\succ a_{2}$
means the answer $a_{1}$ is preferred compared to $a_{2}$, and $\sigma(x)=(1+e^{-x})^{-1}$
is the sigmoid function. We also define a policy $\pi_{\mathsf{HF}}$
to characterize human preference:

$$ $\pi_{\mathsf{HF}}(a\,|\,x)=\frac{\exp(r^{\star}(x,a))}{\sum_{a^{\prime}\in\mathcal{A}}\exp(r^{\star}(x,a^{\prime}))}.$ $$

The reward function is unknown and can be learned from e.g., an offline
dataset $\mathcal{D}=\{(x^{i},a_{+}^{i},a_{-}^{i})\}$ comprised of
independent preference data samples using maximum likelihood estimation
(MLE):

$$ $\mathop{\arg\max}_{r}\ell(r,\mathcal{D})\quad\text{where}\quad\ell(r,\mathcal{D})\coloneqq\sum_{\mathcal{D}}\log\sigma\big(r(x^{i},a_{+}^{i})-r(x^{i},a_{-}^{i})\big),$ (2.2) $$

where a preference data sample denoted by $(x,a_{+},a_{-})$ means
that $a_{+}\succ a_{-}$ given prompt $x$.

#### RL fine-tuning.

Given a reward model $r$, we seek to fine-tune the policy $\pi$
to balance reward maximization with maintaining similarity to the
original model $\pi_{\mathsf{ref}}$ from the SFT stage. Towards this,
we define the KL-regularized reward objective

$$ $J(\pi,r;\pi_{\mathsf{cal}})\coloneqq\mathbb{E}_{x\sim\rho}\big[\mathbb{E}_{a\sim\pi(\cdot\,|\,x)}[r(x,a)]-\mathbb{E}_{a\sim\pi_{\mathsf{cal}}(\cdot\,|\,x)}[r(x,a)]-\beta\mathsf{KL}\big(\pi(\cdot\,|\,x)\parallel\pi_{\mathsf{ref}}(\cdot\,|\,x)\big)\big].$ (2.3) $$

Here $\rho$ is the prompt distribution, and $\beta>0$ is the regularization
parameter reflecting the strength of the KL regularization. In practice, $\beta$ is typically chosen to be small; for instance, in InstructGPT (Ouyang et al.,, 2022) the optimal value is reported to be around $0.01$ and $0.02$. This objective function includes a calibration policy $\pi_{\mathsf{cal}}$
to eliminate the shift ambiguity of the reward function, as two reward
functions $r(x,a)$ and $r(x,a)+c(x)$ lead to the same preference
model ([2.1](https://arxiv.org/html/2509.22633v1#S2.E1)). Given any reward function $r$,
the optimal policy $\pi_{r}\coloneqq\arg\max_{\pi}J(\pi,r;\pi_{\mathsf{cal}})$
admits a closed-form expression (Rafailov et al.,, 2024)

$$ $\pi_{r}(a\,|\,x)=\frac{\pi_{\mathsf{ref}}(a\,|\,x)\exp(r(x,a)/\beta)}{Z_{r}(x)}$ (2.4) $$

where $Z_{r}(x)=\sum_{a}\pi_{\mathsf{ref}}(a|x)\exp(r(x,a)/\beta)$
is the normalizing factor. Notice that the selection of $\pi_{\mathsf{cal}}$
does not affect the optimal policy $\pi_{r}$ given the reward function
$r$. Our target is the optimal policy $\pi^{\star}$ that maximizes
the objective ([2.3](https://arxiv.org/html/2509.22633v1#S2.E3)) under the true reward function $r=r^{\star}$,
namely

$$ $\pi^{\star}\coloneqq\mathop{\arg\max}_{\pi}J(\pi,r^{\star};\pi_{\mathsf{cal}}).$ (2.5) $$

#### Offline RLHF.

The above framework leads to offline RLHF methods that relies on the
preference dataset $\mathcal{D}$ for training. Initial approaches
(Christiano et al.,, 2017; Ouyang et al.,, 2022) first estimate a reward
function $\widehat{r}$ based on the preference dataset $\mathcal{D}$
using MLE, then optimize the KL-regularized objective ([2.3](https://arxiv.org/html/2509.22633v1#S2.E3))
with respect to $\widehat{r}$. Another approach introduced by Rafailov et al., (2024)
condensed these two steps into one single step, known as direct preference
optimization (DPO), which optimizes

$$ $\max_{\pi}\sum_{\mathcal{D}}\log\sigma\bigg(\beta\Big(\log\frac{\pi(y_{+}^{i}\,|\,x)}{\pi_{\mathsf{ref}}(y_{+}^{i}\,|\,x)}-\log\frac{\pi(y_{-}^{i}\,|\,x)}{\pi_{\mathsf{ref}}(y_{-}^{i}\,|\,x)}\Big)\bigg).$ $$

The above objective avoids explicitly estimating the reward function,
which can be obtained by expressing the reward function $r$ in the
MLE formulation ([2.2](https://arxiv.org/html/2509.22633v1#S2.E2)) with the associated optimal policy
$\pi_{r}$ using the closed-form expression ([2.4](https://arxiv.org/html/2509.22633v1#S2.E4)).
However, as discussed in e.g., Xie et al., (2025); Zhang et al., (2025),
the efficiency of offline RLHF is limited by the coverage of the offline
dataset $\mathcal{D}$, and online exploration with active data collection
is necessary to achieve sample efficiency.

#### Online RLHF.

We consider reward learning and policy learning iteratively, where
in the $t$-th iteration we use the current policy $\pi^{(t)}$, obtained
from previous iterations, to sample new data and subsequently update
both the reward estimate and the policy. This setup enables online
exploration in RLHF by refining the reward model and policy in tandem
as new preference data is collected. We aim to minimize the regret

$$ $\mathcal{R}(T)\coloneqq\sum_{t=1}^{T}\big[J(\pi^{\star};r^{\star},\pi_{\mathsf{cal}})-J(\pi^{(t)};r^{\star},\pi_{\mathsf{cal}})\big].$ (2.6) $$

It is worth mentioning that the choice of $\pi_{\mathsf{cal}}$ does
not affect the regret. We define the following function $J^{\star}$
that measures the optimal objective value for a given reward $r$:

$$ $J^{\star}(r;\pi_{\mathsf{cal}})\coloneqq\max_{\pi}J(\pi,r;\pi_{\mathsf{cal}})=J(\pi_{r},r;\pi_{\mathsf{cal}}).$ (2.7) $$

This function plays an important role in the exploration algorithms.

## 3 RLHF with online exploration

Three recent algorithms for online RLHF are most closely related to this work: VPO (Cen et al.,, 2025), XPO (Xie et al.,, 2025), and SELM (Zhang et al.,, 2025). In this section, we first analyze and discuss these approaches, and then introduce our proposed exploration scheme.

### 3.1 Inadequacy of existing approaches

We begin by reviewing the procedure and intuition behind VPO (Cen et al.,, 2025).
Fix a calibration policy $\pi_{\mathsf{cal}}$ and an initial policy $\pi^{(1)}$. For $t=1,2,\ldots,T$, the $t$-th iteration of VPO consists of the following steps:

- 1.
Sample a prompt $x^{t}\sim\rho$ and two answers $a_{1}^{t},a_{2}^{t}\sim\pi^{(t)}(\cdot\,|\,x^{t})$.
Query the preference oracle to obtain pairwise comparison $a_{+}^{t}\succ a_{-}^{t}$.
Update the preference dataset $\mathcal{D}^{(t)}=\mathcal{D}^{(t-1)}\cup\{(x^{t},a_{+}^{t},a_{-}^{t})\}$.
- 2.
Update the reward model $r^{(t+1)}$ and the policy $\pi^{(t+1)}$
using the updated preference dataset $\mathcal{D}^{(t)}$:
$\displaystyle r^{(t+1)}$
$\displaystyle=\mathop{\arg\max}_{r:\mathcal{X}\times\mathcal{A}\to[0,r_{\max}]}\ell(r,\mathcal{D}^{(t)})+\alpha J^{\star}(r;\pi_{\mathsf{cal}}),$
(3.1a)
$\displaystyle\pi^{(t+1)}$
$\displaystyle=\mathop{\arg\max}_{\pi}J(\pi,r^{(t+1)};\pi_{\mathsf{cal}}),$
(3.1b)
where $\alpha>0$ is a regularization parameter, and step ([3.1b](https://arxiv.org/html/2509.22633v1#S3.E1.2))
admits closed-form solution ([2.4](https://arxiv.org/html/2509.22633v1#S2.E4)).

To illustrate the rationale behind VPO, consider the bandit case with no prompt. Step ([3.1a](https://arxiv.org/html/2509.22633v1#S3.E1.1)) applies the optimism principle, encouraging exploration based on the uncertainty in estimating the reward difference between each action $a$ and the calibration policy $\pi_{\mathsf{cal}}$. Formally, it can be viewed as the Lagrangian form of the constrained optimization problem

$$ $\max_{r,\pi}\mathbb{E}_{a\sim\pi}[r(a)]-\mathbb{E}_{a\sim\pi_{\mathsf{cal}}}[r(a)]-\beta\mathsf{KL}(\pi\parallel\pi_{\mathsf{ref}})\quad\text{s.t.}\quad\ell(r,\mathcal{D}^{(t)})\geq\max_{r}\ell(r,\mathcal{D}^{(t)})-B$ $$

for some $B>0$. After the change of variable $r^{\prime}(a)=r(a)-\mathbb{E}_{a\sim\pi_{\mathsf{cal}}}[r(a)]$, this becomes

$$ $\max_{r^{\prime},\pi}\mathbb{E}_{a\sim\pi}[r^{\prime}(a)]-\beta\mathsf{KL}(\pi\parallel\pi_{\mathsf{ref}})\quad\text{s.t.}\quad\ell(r^{\prime},\mathcal{D}^{(t)})\geq\max_{r^{\prime}}\ell(r^{\prime},\mathcal{D}^{(t)})-B,\quad\mathbb{E}_{a\sim\pi_{\mathsf{cal}}}[r^{\prime}(a)]=0.$ $$

Here, the constraint set can be interpreted as a confidence region reflecting the uncertainty in estimating each $r^{\prime}(a)$ from $\mathcal{D}^{(t)}$. Consequently, the updated policy $\pi^{(t+1)}$ depends both on the true reward gap $r(a)-\mathbb{E}_{a\sim\pi_{\mathsf{cal}}}[r(a)]$ and on the uncertainty in estimating this gap for each action $a\in\mathcal{A}$.

For intuition, suppose $\pi_{\mathsf{cal}}=\operatorname{\mathds{1}}_{a_{0}}$ for some $a_{0}\in\mathcal{A}$, and assume that the true reward gaps are small. In this case, $\pi^{(t+1)}$ favors actions with higher estimation uncertainty relative to $a_{0}$, i.e., those $a$ where the estimate of $r(a)-r(a_{0})$ is most uncertain. However, comparing two actions $a_{1},a_{2}\sim\pi^{(t+1)}$ reduces the uncertainty between them, rather than the (potentially larger) uncertainty relative to $a_{0}$. This misalignment can lead to inefficient exploration, as illustrated in the following example.

###### Example 1 .

Consider the bandit setting with three actions $\mathcal{A}=\{a_{0},a_{1},a_{2}\}$, where the true rewards are $r^{\star}(a_{0})=1$ and $r^{\star}(a_{1})=r^{\star}(a_{2})=0$. Let the reference policy $\pi_{\mathsf{ref}}$ be uniform over $\mathcal{A}$, and the calibration policy be $\pi_{\mathsf{cal}}(a_{1})=\pi_{\mathsf{cal}}(a_{2})=p$ and $\pi_{\mathsf{cal}}(a_{0})=1-2p$ for some $0\leq p<1/4$.

The following proposition shows that VPO may fail to explore efficiently in this setting The proof can be found in Appendix [A](https://arxiv.org/html/2509.22633v1#A1).

###### Proposition 1 .

Consider the setup in Example [1](https://arxiv.org/html/2509.22633v1#Thmexample1).
Let the initial policy $\pi^{(1)}$ of VPO be the uniform distribution
over $\mathcal{A}$. Assume that $r_{\max}/\beta\geq 3$. For any $\alpha>0$, with probability at least
$4/(9e)$, we have

$$ $J(\pi^{\star},r^{\star};\pi_{\mathsf{cal}})-J(\pi^{(t)},r^{\star};\pi_{\mathsf{cal}})\geq\frac{1}{2}$ $$

holds for any $1<t\leq\exp(r_{\max}/\beta)/2$.

Let’s discuss the idea behind Proposition [1](https://arxiv.org/html/2509.22633v1#Thmprop1) with $\pi_{\mathsf{cal}}=\operatorname{\mathds{1}}_{a_{0}}$. If the calibration action $a_{0}$ is not visited during the first $t$ iterations, then $\pi^{(t+1)}$ will continue to favor $a_{1}$ and $a_{2}$, since both gaps $r(a_{1})-r(a_{0})$ and $r(a_{2})-r(a_{0})$ remain highly uncertain. In particular, we establish that $\pi^{(t+1)}(a_{0})\leq\exp(-r_{\max}/\beta)$,
which is exponentially small, implying that $a_{0}$ is unlikely to
be sampled in iteration $t+1$. As a result, with constant probability, $a_{0}$ will not be sampled within the first $O(\exp(r_{\max}/\beta))$ iterations, and the resulting highly suboptimal policy incurs linear regret over an exponentially long horizon. This example highlights an algorithmic drawback: although VPO acknowledges uncertainty in the reward gaps between $a_{1}$ and $a_{0}$ (and between $a_{2}$ and $a_{0}$), it continues to encourage sampling $a_{1}$ and $a_{2}$, leading primarily to comparisons between them that fail to reduce their uncertainty relative to $a_{0}$.

###### Example 1 .

###### Proposition 1 .

### 3.2 Our approach: exploration based on uncertainty

Figure: Algorithm 1 Uncertainty-based RLHF exploration.

A natural modification to address the issue above is to change the sampling scheme so that $a_{1}^{t}\sim\pi^{(t)}$ and $a_{2}^{t}\sim\pi_{\mathsf{cal}}$.
The intuition is that $\pi^{(t)}$ encourages to explore actions with
higher estimation uncertainty relative to the actions favored by the
calibration policy $\pi_{\mathsf{cal}}$. To effectively reduce this
uncertainty, it is sensible to compare one action drawn from $\pi^{(t)}$
with another drawn from $\pi_{\mathsf{cal}}$. Indeed, the XPO
and SELM algorithms (Xie et al.,, 2025; Zhang et al.,, 2025) can be viewed
as taking $\pi_{\mathsf{cal}}=\pi_{\mathsf{ref}}$.

However, if the fixed calibration policy $\pi_{\mathsf{cal}}$ is highly suboptimal for reward maximization (for example, if it concentrates on a few low-reward actions), then the comparison will almost always favor $a_{1}^{t}\sim\pi^{(t)}$ against $a_{2}^{t}\sim\pi_{\mathsf{cal}}$,
yielding little useful information. This issue is illustrated in the following example.

###### Example 2 .

Consider the bandit setting with three actions $\mathcal{A}=\{a_{0},a_{1},a_{2}\}$, where the true rewards are $r^{\star}(a_{0})=0$, $r^{\star}(a_{1})=r_{\max}$ and $r^{\star}(a_{2})=r_{\max}-2$. Let the reference policy be $\pi_{\mathsf{ref}}(a_{0})=1-2/\kappa$, $\pi_{\mathsf{ref}}(a_{1})=\pi_{\mathsf{ref}}(a_{2})=1/\kappa$ for any $\kappa\geq 4$.

The following result shows that, when $\kappa$ is large (as we will see in Assumption [1](https://arxiv.org/html/2509.22633v1#Thmassumption1), this corresponds to the case where the reference policy deviates from human preference), this modified sampling schemes can lead to inefficient exploration in this setting. The proof is deferred to Appendix [B](https://arxiv.org/html/2509.22633v1#A2).

###### Proposition 2 .

Consider the setup in Example [2](https://arxiv.org/html/2509.22633v1#Thmexample2).
Assume that $\beta\leq 1$ and $\kappa\leq\exp(r_{\max}/\beta)$. For any initial policy $\pi^{(1)}$ and any $\alpha>0$, with probability at least
$1/64$, the modified exploration scheme which samples $a_{1}^{t}\sim\pi^{(t)}$ and $a_{2}^{t}\sim\pi_{\mathsf{ref}}$ satisfies

$$ $J(\pi^{\star},r^{\star};\pi_{\mathsf{ref}})-J(\pi^{(t)},r^{\star};\pi_{\mathsf{ref}})\geq 0.01$ $$

for any $1<t\leq\min\{\kappa,\exp(r_{\max})/2\}$.

This lower bound suggests that relying on a fixed calibration policy can lead to inefficient exploration over an exponentially long horizon. We will come back to this example in Section [4](https://arxiv.org/html/2509.22633v1#S4) after presenting our algorithm and theoretical guarantees. This observation motivates us to update the calibration policy in each iteration adaptively.

###### Example 2 .

###### Proposition 2 .

#### Uncertainty-based exploration.

We propose an exploration scheme where the calibration policy evolves with the iterations. In the $t$-th iteration, instead of a fixed $\pi_{\mathsf{cal}}$
, we use $\pi^{(t)}$ as the calibration policy when optimizing $r^{(t+1)}$
and $\pi^{(t+1)}$:

$$ $\displaystyle r^{(t+1)}$ $\displaystyle=\mathop{\arg\max}_{r:\mathcal{X}\times\mathcal{A}\to[0,r_{\max}]}\ell(r,\mathcal{D}^{(t)})+\alpha_{t}J^{\star}(r;\pi^{(t)}),$ $\displaystyle\pi^{(t+1)}$ $\displaystyle=\mathop{\arg\max}_{\pi}J(\pi,r^{(t+1)};\pi^{(t)}).$ $$

The key advantage is that $\pi^{(t)}$ improves over time, guiding exploration away from uninformative comparisons. Since $\pi^{(t)}$ emphasizes actions with higher uncertainty relative to $\pi^{(t-1)}$, it is natural to compare $a_{1}^{t}\sim\pi^{(t-1)}$ and $a_{2}^{t}\sim\pi^{(t)}$. This yields preference data that more directly reduces uncertainty, leading to more efficient exploration. Our full exploration scheme is summarized in Algorithm [1](https://arxiv.org/html/2509.22633v1#alg1).

## 4 Theoretical results

We establish theoretical guarantees for Algorithm [1](https://arxiv.org/html/2509.22633v1#alg1) under the multi-armed bandit setting
(i.e., $\mathcal{X}=\varnothing$) with $A=|\mathcal{A}|$. We begin
with a general regret bound, whose proof is deferred to Section [5](https://arxiv.org/html/2509.22633v1#S5).

###### Theorem 1 .

Let $\alpha_{t}>A\log T$ be non-decreasing in $t$. There exists a universal constant $C>0$ such that, with probability at least $1-O(T^{-10})$, the cumulative regret of running Algorithm [1](https://arxiv.org/html/2509.22633v1#alg1) for $T$ iterations satisfies

$$ $\displaystyle\mathcal{R}(T)$ $\displaystyle\leq Cr_{\mathsf{max}}A^{2}\sqrt{T\log T}+C\sum_{t=1}^{T}\frac{Ar_{\mathsf{max}}\log T}{\alpha_{t}}+CA^{2}\alpha_{T}r_{\mathsf{max}}^{2}$ (4.1) $\displaystyle\quad+C(r_{\mathsf{max}}+\log T)\hskip-8.61108pt\sum_{r^{\star}(a_{+})\geq r^{\star}(a_{-})}\hskip-8.61108pt\min\bigg\{\frac{\pi_{\mathsf{HF}}(a_{+})}{\pi_{\mathsf{HF}}(a_{-})}\alpha_{T}r_{\mathsf{max}},\left(T\frac{\pi_{\mathsf{ref}}(a_{-})}{\pi_{\mathsf{ref}}(a_{+})}\right)^{\frac{\beta}{\beta+1}}\alpha_{T}^{\frac{1}{\beta+1}}r_{\max}^{\frac{1}{\beta+1}}\bigg\}.$ $$

We now discuss the implications of Theorem [1](https://arxiv.org/html/2509.22633v1#Thmtheorem1). When
$\beta=0$, which corresponds to the case where only reward maximization
matters, the regret bound ([4.1](https://arxiv.org/html/2509.22633v1#S4.E1)) simplifies to

$$ $\mathcal{R}(T)=\widetilde{O}\big((A^{3/2}r_{\max}^{3/2}+A^{2}r_{\max})\sqrt{T}\big)\qquad\text{when}\qquad\alpha_{t}\asymp A\log T+\sqrt{\frac{t}{Ar_{\max}}}.$ $$

When $\beta>0$, the performance of the exploration algorithm becomes
more intricate due to the trade-off between reward maximization and
similarity to the reference policy. To interpret the general regret
bound in this regime, we introduce the following assumption to capture
the interaction between human preference $\pi_{\mathsf{HF}}$ and
the reference policy $\pi_{\mathsf{ref}}$.

###### Assumption 1 .

There exists $\kappa,\tau\geq 1$
such that, for any action pair $(a_{+},a_{-})$,

$$ $\frac{\pi_{\mathsf{HF}}(a_{+})}{\pi_{\mathsf{HF}}(a_{-})}\geq\tau\quad\Longrightarrow\quad\frac{\pi_{\mathsf{ref}}(a_{+})}{\pi_{\mathsf{ref}}(a_{-})}\geq\kappa^{-1}.$ $$

Intuitively, Assumption [1](https://arxiv.org/html/2509.22633v1#Thmassumption1) requires that whenever
$a_{+}$ is substantially more preferred than $a_{-}$ under human
preference, the reference policy does not assign disproportionately
higher weight to $a_{-}$ than to $a_{+}$. This is reasonable, since
$\pi_{\mathsf{ref}}$ is obtained from the SFT step, where a pretrained
LLM is fine-tuned on human demonstrations already broadly aligned
with preference. The quantities $\kappa$ and $\tau$ capture the degree of alignment between $\pi_{\mathsf{ref}}$ and $\pi_{\mathsf{HF}}$, and their size reflects the influence of the reference policy on RLHF. We note that the illustrative Example [1](https://arxiv.org/html/2509.22633v1#Thmexample1) satisfies Assumption [1](https://arxiv.org/html/2509.22633v1#Thmassumption1) with $\kappa,\tau=O(1)$, and the parameter $\kappa$ in Example [2](https://arxiv.org/html/2509.22633v1#Thmexample2) is consistent with the $\kappa$ here. Under this assumption, we obtain the following simplified regret bound, whose proof is deferred to Appendix [D](https://arxiv.org/html/2509.22633v1#A4).

###### Proposition 3 .

Suppose that Assumption [1](https://arxiv.org/html/2509.22633v1#Thmassumption1)
holds. Let

$$ $\alpha_{t}=A\log T+t^{\frac{1}{\beta+2}}\Big(\frac{r_{\max}}{\kappa}\Big)^{\frac{\beta}{\beta+2}}\Big(\frac{\log T}{A(r_{\max}+\log T)}\Big)^{\frac{\beta+1}{\beta+2}}.$ $$

Then with probability at least $1-O(T^{-10})$, we have

$$ $\mathcal{R}(T)\lesssim(\tau+\kappa^{\beta}T^{\frac{\beta+1}{\beta+2}})\,\mathsf{poly}(A,r_{\max},\log T),$ $$

where the degree of the polynomial factor does not depend on $\beta$.

###### Remark 1 .

When $\kappa$ is large, namely the reference policy deviates significantly from the human preference, it is natural to choose a small KL regularization parameter $\beta$ to reduce the influence of the reference policy. In this regime, Algorithm [1](https://arxiv.org/html/2509.22633v1#alg1) remains robust, since the regret bound scales only with $\kappa^{\beta}$. By contrast, the lower bound in Proposition [2](https://arxiv.org/html/2509.22633v1#Thmprop2) suggests that the sampling protocols in prior works (Xie et al.,, 2025; Zhang et al.,, 2025) would incur regret at least linear in $\kappa$. This demonstrates that our strategy accommodates scenarios with small $\beta$, where the reference policy is poorly aligned with human preference.

###### Remark 2 .

In Appendix [E](https://arxiv.org/html/2509.22633v1#A5), we present an alternative
assumption linking human preference and the reference policy, together with the corresponding regret guarantee.

Proposition [3](https://arxiv.org/html/2509.22633v1#Thmprop3) establishes a regret bound of order
$O(T^{\frac{\beta+1}{\beta+2}})$, with only polynomial dependence
on the other parameters. This stands in sharp contrast to prior works
(Cen et al.,, 2025; Xie et al.,, 2025; Zhang et al.,, 2025),
which achieved the more standard $O(\sqrt{T})$ regret but at the
cost of exponential dependence on terms such as $r_{\max}/\beta$.
We conjecture that, for RLHF, eliminating exponential dependence inevitably
requires a slower rate in $T$, with the exponent governed by $\beta$.
This trade-off is intuitive: online exploration primarily serves to
learn human preference, and as the regularization parameter $\beta$
increases, greater emphasis is placed on preserving similarity to
the reference measure. This constraint naturally slows convergence.

###### Theorem 1 .

###### Assumption 1 .

###### Proposition 3 .

###### Remark 1 .

###### Remark 2 .

## 5 Proof of Theorem 1

### 5.1 Step 1: regret decomposition

In view of the optimality of $r^{(t)}$ (cf. equation ([3.2a](https://arxiv.org/html/2509.22633v1#S3.E2.1))),
we have

$$ $\ell(r^{(t)},\mathcal{D}^{(t-1)})+\alpha_{t}J^{\star}(r^{(t)};\pi^{(t-1)})\geq\ell(r^{\star},\mathcal{D}^{(t-1)})+\alpha_{t}J^{\star}(r^{\star};\pi^{(t-1)}).$ $$

Rearrange terms to get

$$ $\displaystyle\frac{1}{\alpha_{t}}\big[\ell(r^{(t)},\mathcal{D}^{(t-1)})-\ell(r^{\star},\mathcal{D}^{(t-1)})\big]$ $\displaystyle\geq J^{\star}(r^{\star};\pi^{(t-1)})-J^{\star}(r^{(t)};\pi^{(t-1)})$ $\displaystyle\overset{\text{(i)}}{=}\max_{\pi}J(\pi,r^{\star};\pi^{(t-1)})-\max_{\pi}J(\pi,r^{(t)};\pi^{(t-1)})$ $\displaystyle\overset{\text{(ii)}}{\geq}J(\pi^{\star},r^{\star};\pi^{(t-1)})-J(\pi^{(t)},r^{(t)};\pi^{(t-1)}).$ (5.1) $$

Here step (i) follows from the definition of $J^{\star}$ (cf. equation
([2.7](https://arxiv.org/html/2509.22633v1#S2.E7))), while step (ii) follows from the optimality
of $\pi^{(t)}$ (cf. equation ([3.2b](https://arxiv.org/html/2509.22633v1#S3.E2.2))). This allows
us to reach the following decomposition:

$$ $\displaystyle\mathsf{Regret}_{t}$ $\displaystyle\coloneqq J(\pi^{\star},r^{\star};\pi^{(t-1)})-J(\pi^{(t)},r^{\star};\pi^{(t-1)})$ $\displaystyle\leq\underbrace{\alpha_{t}^{-1}\big[\ell(r^{(t)},\mathcal{D}^{(t)})-\ell(r^{\star},\mathcal{D}^{(t)})\big]}_{\eqqcolon\theta_{t}}+\underbrace{J(\pi^{(t)},r^{(t)};\pi^{(t-1)})-J(\pi^{(t)},r^{\star};\pi^{(t-1)})}_{\eqqcolon\gamma_{t}}.$ (5.2) $$

In view of the definition of $J$ (cf. equation ([2.3](https://arxiv.org/html/2509.22633v1#S2.E3))),
we can further decompose

$$ $\displaystyle\gamma_{t}$ $\displaystyle=\mathbb{E}_{a\sim\pi^{(t)}}[r^{(t)}(a)]-\mathbb{E}_{a\sim\pi^{(t-1)}}[r^{(t)}(a)]-\mathbb{E}_{a\sim\pi^{(t)}}[r^{\star}(a)]+\mathbb{E}_{a\sim\pi^{(t-1)}}[r^{\star}(a)]$ $\displaystyle=r^{(t)}(a_{2}^{t})-r^{(t)}(a_{1}^{t})-r^{\star}(a_{2}^{t})+r^{\star}(a_{1}^{t})+\xi_{t}$ $$

where $\xi_{t}$ is the martingale difference sequence

$$ $\displaystyle\xi_{t}$ $\displaystyle=\mathbb{E}_{a\sim\pi^{(t)}}[r^{(t)}(a)]-r^{(t)}(a_{2}^{t})-\mathbb{E}_{a\sim\pi^{(t-1)}}[r^{(t)}(a)]+r^{(t)}(a_{1}^{t})$ $\displaystyle\qquad-\mathbb{E}_{a\sim\pi^{(t)}}[r^{\star}(a)]+r^{\star}(a_{2}^{t})+\mathbb{E}_{a\sim\pi^{(t-1)}}[r^{\star}(a)]-r^{\star}(a_{1}^{t}).$ $$

Therefore we have

$$ $\mathsf{Regret}=\sum_{t=1}^{T}\mathsf{Regret}_{t}\leq\underbrace{\sum_{t=1}^{T}\theta_{t}}_{\eqqcolon\theta}+\underbrace{\sum_{t=1}^{T}\xi_{t}}_{\eqqcolon\xi}+\underbrace{\sum_{t=1}^{T}|r^{(t)}(a_{2}^{t})-r^{(t)}(a_{1}^{t})-r^{\star}(a_{2}^{t})+r^{\star}(a_{1}^{t})|}_{\eqqcolon\zeta}.$ (5.3) $$

It is straightforward to bound the second term $\xi$. Notice that
$|\xi_{t}|\leq 8r_{\max}$ holds deterministically for any $1\leq t\leq T$.
By the Azuma-Hoeffding inequality, with probability exceeding $1-O(T^{-10})$
we have

$$ $\xi=\sum_{t=1}^{T}\xi_{t}\leq C_{1}r_{\mathsf{max}}\sqrt{T\log T}$ (5.4) $$

for some universal constant $C_{1}>0$. In what follows, we bound
the other two terms $\theta$ and $\zeta$.

### 5.2 Step 2: bounding likelihood ratios

To bound $\theta$, we need to analyze the regularized MLE. Notice
that

$$ $\theta_{t}=\frac{\ell(r^{(t)},\mathcal{D}^{(t)})-\ell(r^{\star},\mathcal{D}^{(t)})}{\alpha_{t}}=\alpha_{t}^{-1}\sum_{i=1}^{t}\log\frac{\sigma(r^{(t)}(x^{i},a_{+}^{i})-r^{(t)}(x^{i},a_{-}^{i}))}{\sigma(r^{\star}(x^{i},a_{+}^{i})-r^{\star}(x^{i},a_{-}^{i}))}.$ $$

The following lemma is crucial for the subsequent analysis. The proof can be found in Appendix [C.1](https://arxiv.org/html/2509.22633v1#A3.SS1).

###### Lemma 1 .

For any given reward function
$r:\mathcal{A}\to[0,r_{\max}]$ and any $1\leq t\leq T$, define

$$ $\displaystyle\Delta_{t}(r)$ $\displaystyle:=\sum_{i=1}^{t}\log\frac{\sigma(r^{\star}(a_{+}^{i})-r^{\star}(a_{-}^{i}))}{\sigma(r(a_{+}^{i})-r(a_{-}^{i}))}-\sum_{i=1}^{t}\mathsf{KL}\big(\sigma(r^{\star}(a_{1}^{i})-r^{\star}(a_{2}^{i}))\parallel\sigma(r(a_{1}^{i})-r(a_{2}^{i}))\big).$ $$

There exists some universal constant $C_{2}>1$ such that for any
fixed $r$, with probability at least $1-\delta$,

$$ $|\Delta_{t}(r)|\leq C_{2}\sqrt{\sum_{i=1}^{t}r_{\mathsf{max}}\mathsf{KL}\big(\sigma(r^{\star}(a_{1}^{i})-r^{\star}(a_{2}^{i}))\parallel\sigma(r(a_{1}^{i})-r(a_{2}^{i}))\big)\log\frac{\log T}{\delta}}+C_{2}r_{\mathsf{max}}\log\frac{\log t}{\delta}.$ $$

Equipped with the concentration bounds in Lemma [1](https://arxiv.org/html/2509.22633v1#Thmlemma1),
we can use the standard covering argument to derive an uniform upper
bound, whose proof is deferred to Appendix [C.2](https://arxiv.org/html/2509.22633v1#A3.SS2).

###### Lemma 2 .

There exists some universal constant
$C_{3}>0$ such that with probability exceeding $1-O(T^{-9})$,

$$ $\ell(r,\mathcal{D}^{(t)})-\ell(r^{\star},\mathcal{D}^{(t)})\leq-\frac{1}{2}\sum_{i=1}^{t}\mathsf{KL}\big(\sigma(r^{\star}(a_{1}^{i})-r^{\star}(a_{2}^{i}))\parallel\sigma(r(a_{1}^{i})-r(a_{2}^{i}))\big)+C_{3}Ar_{\max}\log T$ $$

holds for any $r:\mathcal{A}\to[0,r_{\max}]$ and $1\leq t\leq T$.

As an immediate consequence of Lemma [2](https://arxiv.org/html/2509.22633v1#Thmlemma2), with
probability exceeding $1-O(T^{-9})$,

$$ $\ell(r^{(t)},\mathcal{D}^{(t)})-\ell(r^{\star},\mathcal{D}^{(t)})\leq C_{3}Ar_{\mathsf{max}}\log T$ $$

holds for any $1\leq t\leq T$. Therefore

$$ $\theta=\sum_{t=1}^{T}\theta_{t}=\sum_{t=1}^{T}\frac{\ell(r^{(t)},\mathcal{D}^{(t)})-\ell(r^{\star},\mathcal{D}^{(t)})}{\alpha_{t}}\leq\sum_{t=1}^{T}\frac{C_{3}Ar_{\mathsf{max}}\log T}{\alpha_{t}}.$ (5.5) $$

###### Lemma 1 .

###### Lemma 2 .

### 5.3 Step 3: bounding reward errors

We first notice that

$$ $\displaystyle\alpha_{t}^{-1}\big[\ell(r^{(t)},\mathcal{D}^{(t-1)})-\ell(r^{\star},\mathcal{D}^{(t-1)})\big]$ $\displaystyle\overset{\text{(i)}}{\geq}\max_{\pi}J(\pi,r^{\star};\pi^{(t-1)})-\max_{\pi}J(\pi,r^{(t)};\pi^{(t-1)})$ $\displaystyle\overset{\text{(ii)}}{\geq}J(\pi^{(t)},r^{\star};\pi^{(t-1)})-J(\pi^{(t)},r^{(t)};\pi^{(t-1)})$ $\displaystyle\overset{\text{(iii)}}{=}\mathbb{E}_{a\sim\pi^{(t)}}[r^{(t)}(a)-r^{\star}(a)]-\mathbb{E}_{a\sim\pi^{(t-1)}}[r^{(t)}(a)-r^{\star}(a)]$ $\displaystyle\geq-4r_{\max}.$ (5.6) $$

Here step (i) is an intermediate step of ([5.1](https://arxiv.org/html/2509.22633v1#S5.E1));
step (ii) follows from the optimality of $\pi^{(t)}$ (cf. ([3.2b](https://arxiv.org/html/2509.22633v1#S3.E2.2)));
step (iii) follows from the definition of $J$ (cf. ([2.3](https://arxiv.org/html/2509.22633v1#S2.E3))).
This combined with Lemma [2](https://arxiv.org/html/2509.22633v1#Thmlemma2) implies that

$$ $\displaystyle\sum_{i=1}^{t}\mathsf{KL}\big(\sigma(r^{\star}(a_{1}^{i})-r^{\star}(a_{2}^{i}))\parallel\sigma(r^{(t)}(a_{1}^{i})-r^{(t)}(a_{2}^{i}))\big)$ (5.7) $\displaystyle\qquad\leq-2\big[\ell(r^{(t)},\mathcal{D}^{(t)})-\ell(r^{\star},\mathcal{D}^{(t)})\big]+2C_{3}Ar_{\mathsf{max}}\log T\leq C_{4}\alpha_{t}r_{\max},$ $$

as long as $\alpha_{t}\geq A\log T$ and $C_{4}\geq 8+2C_{3}$. This
implies that for any $t\in[T]$ and any action pair $(a_{+},a_{-})$,

$$ $\mathsf{KL}\big(\sigma(r^{\star}(a_{+})-r^{\star}(a_{-}))\|\sigma(r^{(t)}(a_{+})-r^{(t)}(a_{-}))\big)\leq\frac{C_{4}\alpha_{t}r_{\max}}{N_{t}(a_{+},a_{-})},$ (5.8) $$

where $N_{t}(a_{+},a_{-})$ is the number of comparison for $(a_{+},a_{-})$
up to time $t$. This motivates us to decompose $\zeta$ according
to whether $N_{t}(a_{+},a_{-})\gg\alpha_{t}r_{\max}$: let $\tau\coloneqq 100C_{4}\alpha_{T}r_{\mathsf{max}}$
and denote by $t_{n}(a_{+},a_{-})$ the time of the $n$-th comparison
for $(a_{+},a_{-})$, we have

$$ $\zeta\leq 2\tau A^{2}r_{\max}+\sum_{r^{\star}(a_{+})\geq r^{\star}(a_{-})}\underbrace{\sum_{n=\tau}^{N_{T}(a_{+},a_{-})}\big|r^{(t_{n})}(a_{+})-r^{(t_{n})}(a_{-})-r^{\star}(a_{+})+r^{\star}(a_{-})\big|}_{\eqqcolon\zeta(a_{+},a_{-})},$ $$

where we denote by $t_{n}(a_{+},a_{-})$ the time of the $n$-th comparison
for $(a_{+},a_{-})$, and the first summation is taken over all action
pairs $(a_{+},a_{-})$ satisfying $r^{\star}(a_{+})\geq r^{\star}(a_{-})$.
To bound each $\zeta(a_{+},a_{-})$, we need the following technical
lemma. The proof can be found in Appendix [C.3](https://arxiv.org/html/2509.22633v1#A3.SS3).

###### Lemma 3 .

Consider any action pair $(a_{+},a_{-})$
and time $t_{0}$ such that $N_{t_{0}}(a_{+},a_{-})\geq\tau$. There exists universal constant $C_{5}>0$ such that, for
any $t_{0}\leq t_{1}<t_{2}\leq T$, with probability exceeding $1-O(T^{-10})$
we have

$$ $\displaystyle N_{t_{2}}(a_{+},a_{-})-N_{t_{1}}(a_{+},a_{-})$ $\displaystyle\leq C_{5}^{1/\beta}\sum_{t=t_{1}+1}^{t_{2}}\frac{\pi_{\mathsf{ref}}(a_{-})}{\pi_{\mathsf{ref}}(a_{+})}\Big[\mathsf{KL}\big(\sigma(r^{\star}(a_{+})-r^{\star}(a_{-}))\|\sigma(r^{(t)}(a_{+})-r^{(t)}(a_{-}))\big)^{\frac{1}{\beta}}$ $\displaystyle\qquad\qquad\qquad\qquad\qquad+\sigma(r^{\star}(a_{-})-r^{\star}(a_{+}))^{\frac{1}{\beta}}\Big]+C_{5}\sqrt{T\log T}.$ $$

Equipped with Lemma [3](https://arxiv.org/html/2509.22633v1#Thmlemma3), we can bound each $\zeta(a_{+},a_{-})$
using both density ratios regarding human feedback $\pi_{\mathsf{HF}}(a_{+})/\pi_{\mathsf{HF}}(a_{-})$,
and regarding the reference policy $\pi_{\mathsf{ref}}(a_{-})/\pi_{\mathsf{ref}}(a_{+})$. The proof is deferred to Appendix [C.4](https://arxiv.org/html/2509.22633v1#A3.SS4).

###### Lemma 4 .

There exists universal constant $C_{6}>0$ such that, for any action pair $(a_{+},a_{-})$,
with probability exceeding $1-O(T^{-9})$ we have

$$ $\displaystyle\zeta(a_{+},a_{-})$ $\displaystyle\leq C_{6}(r_{\max}+\log T)\min\left\{\frac{\pi_{\mathsf{HF}}(a_{+})}{\pi_{\mathsf{HF}}(a_{-})}\alpha_{T}r_{\mathsf{max}},\left(T\frac{\pi_{\mathsf{ref}}(a_{-})}{\pi_{\mathsf{ref}}(a_{+})}\right)^{\frac{\beta}{\beta+1}}\alpha_{T}^{\frac{1}{\beta+1}}r_{\max}^{\frac{1}{\beta+1}}\right\}$ $\displaystyle\qquad+C_{6}\left(\frac{AN_{T}(a_{+},a_{-})\log T}{\alpha_{T}}+\sqrt{T\log T}\right)r_{\max}.$ $$

This immediately implies that

$$ $\displaystyle\zeta$ $\displaystyle\leq 2\tau A^{2}r_{\max}+C_{6}\left(\frac{AT\log T}{\alpha_{T}}+A^{2}\sqrt{T\log T}\right)r_{\max}$ (5.9) $\displaystyle\quad+C_{6}(r_{\max}+\log T)\hskip-4.30554pt\sum_{r^{\star}(a_{+})\geq r^{\star}(a_{-})}\hskip-4.30554pt\min\bigg\{\frac{\pi_{\mathsf{HF}}(a_{+})}{\pi_{\mathsf{HF}}(a_{-})}\alpha_{T}r_{\mathsf{max}},\left(T\frac{\pi_{\mathsf{ref}}(a_{-})}{\pi_{\mathsf{ref}}(a_{+})}\right)^{\frac{\beta}{\beta+1}}\alpha_{T}^{\frac{1}{\beta+1}}r_{\max}^{\frac{1}{\beta+1}}\bigg\}.$ $$

Putting the regret decomposition ([5.3](https://arxiv.org/html/2509.22633v1#S5.E3)) and the
bounds ([5.4](https://arxiv.org/html/2509.22633v1#S5.E4)), ([5.5](https://arxiv.org/html/2509.22633v1#S5.E5)) and ([5.9](https://arxiv.org/html/2509.22633v1#S5.E9))
collectively yields the desired regret bound ([4.1](https://arxiv.org/html/2509.22633v1#S4.E1)).

###### Lemma 3 .

###### Lemma 4 .

## 6 Discussion

In this paper, we investigated the problem of efficient exploration in online RLHF. By a careful analysis of the existing optimism-based exploration strategies, we identified a conceptual drawback in their sampling protocol, and we proved lower bounds to show that they can lead to inefficient exploration. We then proposed our algorithm that explicitly targets uncertainty in reward differences most relevant for policy improvement. Under a multi-armed bandit setup of RLHF, we establish regret bounds of order $T^{(\beta+1)/(\beta+2)}$, which scales polynomially in all model parameters.

Our work opens several avenues for future investigation. An immediate question is whether the rate $T^{(\beta+1)/(\beta+2)}$ is minimax optimal, or if faster rates can be achieved. Another important direction is to refine the dependence on parameters such as $A$ and $r_{\max}$, which may be improved with sharper analysis or alternative exploration schemes. Finally, our theoretical results are restricted to the bandit setting; extending the analysis to richer environments that incorporate a prompt space would be an exciting step toward bridging theory and practice in online RLHF.

## Acknowledgements

G. Li is supported in part by the Chinese University of Hong Kong Direct Grant for Research and the Hong Kong Research Grants Council ECS 2191363.

## Appendix A Proof of Proposition 1

For each $t\geq 1$, define the event

$$ $\mathcal{E}_{t}:=\{\text{no $a_{0}$ is sampled in the first $t$ samples}\}.$ $$

We will show that for any $t\geq 1$,

$$ $\mathbb{P}(\mathcal{E}_{t})\geq\frac{4}{9}\big(1-\exp(-r_{\max}/\beta)\big)^{2(t-1)}.$ (A.1) $$

Conditional on $\mathcal{E}_{t}$, it can be seen that $\ell(r,\mathcal{D}^{(t)})$
only depends on $r(a_{1})-r(a_{2})$. Now we study when we fix $r(a_{1})-r(a_{2})\equiv\delta$
such that $\ell(r,\mathcal{D}^{(t)})$ is fixed, when is $J(\pi,r;\pi_{\mathsf{cal}})$
maximized over both $\pi$ and $r$. By symmetry, we can assume without
loss of generality that $\delta\geq 0$. We can compute

$$ $\displaystyle J(\pi,r;\pi_{\mathsf{cal}})$ $\displaystyle=\mathbb{E}_{a\sim\pi}[r(a)]-\mathbb{E}_{a\sim\pi_{\mathsf{cal}}}[r(a)]-\beta\mathsf{KL}(\pi\parallel\pi_{\mathsf{ref}})$ $\displaystyle=[\pi(a_{1})-p][r(a_{1})-r(a_{0})]+[\pi(a_{2})-p][r(a_{2})-r(a_{0})]-\beta\mathsf{KL}(\pi\parallel\pi_{\mathsf{ref}})$ $\displaystyle=[\pi(a_{1})+\pi(a_{2})-2p][r(a_{1})-r(a_{0})]-\delta[\pi(a_{2})-p]-\beta\mathsf{KL}(\pi\parallel\pi_{\mathsf{ref}}).$ $$

For fixed $\pi$, we check which reward function $r$ maximizes $J(\pi,r;\pi_{\mathsf{cal}})$.

- •
When $\pi(a_{1})+\pi(a_{2})>2p$, we know that
$\displaystyle\max_{r}J(\pi,r;\pi_{\mathsf{cal}})$
$\displaystyle=r_{\max}[\pi(a_{1})+\pi(a_{2})-2p]-\delta[\pi(a_{2})-p]-\beta\mathsf{KL}(\pi\parallel\pi_{\mathsf{ref}}),$
(A.2)
which is maximized at $r(a_{1})=r_{\max}$, $r(a_{2})=r_{\max}-\delta$
and $r(a_{0})=0$.
- •
When $\pi(a_{1})+\pi(a_{2})<2p$, we know that
$\displaystyle\max_{r}J(\pi,r;\pi_{\mathsf{cal}})$
$\displaystyle=(r_{\max}-\delta)[2p-\pi(a_{1})-\pi(a_{2})]-\delta[\pi(a_{2})-p]-\beta\mathsf{KL}(\pi\parallel\pi_{\mathsf{ref}}),$
(A.3)
which is maximized at $r(a_{1})=\delta$, $r(a_{2})=0$ and $r(a_{0})=r_{\max}$.

In addition, for any policy $\pi$ such that $\pi(a_{1})+\pi(a_{2})<2p$,
by considering another policy $\pi^{\prime}$ defined as $\pi^{\prime}(a_{1})=2p-\pi(a_{2})$
and $\pi^{\prime}(a_{2})=2p-\pi(a_{1})$, we have

$$ $\displaystyle\max_{r}J(\pi^{\prime},r;\pi_{\mathsf{cal}})-\max_{r}J(\pi,r;\pi_{\mathsf{cal}})$ $\displaystyle\qquad=r_{\max}[\pi^{\prime}(a_{1})+\pi^{\prime}(a_{2})-2p]-\delta[\pi^{\prime}(a_{2})-p]-\beta\mathsf{KL}(\pi^{\prime}\parallel\pi_{\mathsf{ref}})$ $\displaystyle\qquad\qquad-(r_{\max}-\delta)[2p-\pi(a_{1})-\pi(a_{2})]+\delta[\pi(a_{2})-p]+\beta\mathsf{KL}(\pi\parallel\pi_{\mathsf{ref}})$ $\displaystyle\qquad=\beta[\mathsf{KL}(\pi\parallel\pi_{\mathsf{ref}})-\mathsf{KL}(\pi^{\prime}\parallel\pi_{\mathsf{ref}})].$ $$

Here the first relation follows from ([A.2](https://arxiv.org/html/2509.22633v1#A1.E2)), ([A.3](https://arxiv.org/html/2509.22633v1#A1.E3))
and the fact that $\pi^{\prime}(a_{1})+\pi^{\prime}(a_{2})>2p$. Let
$x=\pi(a_{1})$ and $y=\pi(a_{2})$. Let

$$ $\displaystyle f(x,y)$ $\displaystyle\coloneqq\mathsf{KL}(\pi\parallel\pi_{\mathsf{ref}})-\mathsf{KL}(\pi^{\prime}\parallel\pi_{\mathsf{ref}})$ $\displaystyle=x\log x+y\log y+(1-x-y)\log(1-x-y)-(2p-x)\log(2p-x)$ $\displaystyle\qquad-(2p-y)\log(2p-y)-(1-4p+x+y)\log(1+x+y-4p).$ $$

By elementary analysis, it is straightforward to check that $f(x,y)>0$
for any $x,y>0$ satisfying $x+y<2p$. Therefore we have

$$ $\max_{r}J(\pi^{\prime},r;\pi_{\mathsf{cal}})>\max_{r}J(\pi,r;\pi_{\mathsf{cal}}).$ $$

Therefore in order to maximize $\ell(r,\mathcal{D}^{(t)})+\alpha J^{\star}(r;\pi_{\mathsf{cal}})$,
the following statement always holds regardless of the value of $\delta$:

$$ $r^{(t+1)}(a_{0})=0,\quad\max\big\{r^{(t+1)}(a_{1}),r^{(t+1)}(a_{2})\big\}=r_{\max}.$ $$

This immediately implies that

$$ $\displaystyle\pi^{(t+1)}(a_{0})$ $\displaystyle=\frac{\exp(r^{(t+1)}(a_{0})/\beta)}{\exp(r^{(t+1)}(a_{0})/\beta)+\exp(r^{(t+1)}(a_{1})/\beta)+\exp(r^{(t+1)}(a_{2})/\beta)}\leq\frac{1}{2+\exp(r_{\max}/\beta)}.$ $$

Therefore conditional on $\mathcal{E}_{t}$, we know that

$$ $\displaystyle\mathbb{P}(\mathcal{E}_{t+1}|\mathcal{E}_{t})$ $\displaystyle\geq\big(1-\pi^{(t+1)}(a_{0})\big)^{2}\geq\left(\frac{1}{1+\exp(-r_{\max}/\beta)}\right)^{2}\geq\big(1-\exp(-r_{\max}/\beta)\big)^{2}.$ $$

This relation, together with

$$ $\mathbb{P}(\mathcal{E}_{0})=\big(\pi^{(1)}(a_{1})+\pi^{(1)}(a_{2})\big)^{2}=\frac{4}{9},$ $$

establishes the statement ([A.1](https://arxiv.org/html/2509.22633v1#A1.E1)). This immediately implies
that, for any $t\leq\exp(r_{\max}/\beta)/2$,

$$ $\mathbb{P}(\mathcal{E}_{t})\geq\frac{4}{9}\big(1-\exp(-r_{\max}/\beta)\big)^{2(t-1)}\geq\frac{4}{9}\big(1-\exp(-r_{\max}/\beta)\big)^{\exp(r_{\max}/\beta)}\geq\frac{4}{9e}\geq 0.16.$ $$

Finally, when $\mathcal{E}_{t}$ holds, we have

$$ $\displaystyle J(\pi^{\star};r^{\star},\pi_{\mathsf{cal}})-J(\pi^{(t)};r^{\star},\pi_{\mathsf{cal}})$ $\displaystyle=\pi^{\star}(a_{0})-\pi^{(t)}(a_{0})-\beta\mathsf{KL}(\pi^{\star}\|\pi_{\mathsf{ref}})+\beta\mathsf{KL}(\pi^{(t)}\|\pi_{\mathsf{ref}}).$ $$

We have

$$ $\pi^{\star}(a_{0})=\frac{\exp(1/\beta)}{\exp(1/\beta)+2},\quad\pi^{\star}(a_{1})=\pi^{\star}(a_{2})=\frac{1}{\exp(1/\beta)+2}.$ $$

Therefore we have

$$ $\displaystyle\mathsf{KL}(\pi^{\star}\parallel\pi_{\mathsf{ref}})$ $\displaystyle=\log 3+\pi^{\star}(a_{0})\log\pi^{\star}(a_{0})+\pi^{\star}(a_{1})\log\pi^{\star}(a_{1})+\pi^{\star}(a_{2})\log\pi^{\star}(a_{2})$ $\displaystyle=\log 3+\frac{\exp(1/\beta)}{\exp(1/\beta)+2}\log\frac{\exp(1/\beta)}{\exp(1/\beta)+2}+\frac{2}{\exp(1/\beta)+2}\log\frac{1}{\exp(1/\beta)+2}$ $\displaystyle=\log 3+\beta^{-1}\frac{\exp(1/\beta)}{\exp(1/\beta)+2}-\log[\exp(1/\beta)+2].$ $$

In addition, when $\mathcal{E}^{t-1}$ happens, we know that

$$ $\displaystyle\mathsf{KL}(\pi^{(t)}\parallel\pi_{\mathsf{ref}})$ $\displaystyle=\log 3+\pi^{(t)}(a_{0})\log\pi^{(t)}(a_{0})+\pi^{(t)}(a_{1})\log\pi^{(t)}(a_{1})+\pi^{(t)}(a_{2})\log\pi^{(t)}(a_{2})$ $\displaystyle\overset{\text{(i)}}{\geq}\log 3+\pi^{(t)}(a_{0})\log\pi^{(t)}(a_{0})+\big[\pi^{(t)}(a_{1})+\pi^{(t)}(a_{2})\big]\log\frac{\pi^{(t)}(a_{1})+\pi^{(t)}(a_{2})}{2}$ $\displaystyle=\log 3+\pi^{(t)}(a_{0})\log\pi^{(t)}(a_{0})+\big[1-\pi^{(t)}(a_{0})\big]\log\frac{1-\pi^{(t)}(a_{0})}{2}$ $\displaystyle\overset{\text{(ii)}}{\geq}\log 3-\log 2-0.16.$ $$

Here step (i) uses Jensen’s inequality for convex function $f(x)=x\log x$;
step (ii) holds since the function $g(x)=x\log x+(1-x)\log(1-x)/2$
is monotonically decreasing for $0<x<1/3$, and we have

$$ $\pi^{(t)}(a_{0})\leq\frac{1}{2+\exp(r_{\max}/\beta)}\leq\frac{1}{2+\exp(3)}\leq 0.046$ $$

provided that $r_{\max}/\beta\geq 3$. We have

$$ $\displaystyle J(\pi^{\star};r^{\star},\pi_{\mathsf{cal}})-J(\pi^{(t)};r^{\star},\pi_{\mathsf{cal}})$ $\displaystyle=\pi^{\star}(a_{0})-\pi^{(t)}(a_{0})-\beta\mathsf{KL}(\pi^{\star}\parallel\pi_{\mathsf{ref}})+\beta\mathsf{KL}(\pi^{(t)}\parallel\pi_{\mathsf{ref}})$ $\displaystyle\geq\beta\log\big(\exp(1/\beta)+2\big)-(\log 2+0.16)\beta-0.046$ $\displaystyle\geq 1/2,$ $$

where the last relation holds for any $\beta>0$.

## Appendix B Proof of Proposition 2

Let $T=\min\{\kappa,\exp(r_{\max})/2\}$, and define the events

$$ $\mathcal{A}\coloneqq\big\{a_{2}^{t}=a_{0}\text{ for all }1\leq t\leq T\big\}$ $$

and

$$ $\mathcal{E}:=\{a_{1}^{t}\succ a_{2}^{t}\text{ or }a_{1}^{t}=a_{2}^{t}\text{ for all }1\leq t\leq T\}.$ $$

We can check that when $\kappa\geq 5$,

$$ $\mathbb{P}(\mathcal{A})=[\pi_{\mathsf{ref}}(a_{0})]^{T}\leq(1-2\kappa^{-1})^{\kappa}\geq\frac{1}{16}.$ $$

Conditional on $\mathcal{A}$, we know that when $r_{\max}\geq 1$,

$$ $\displaystyle\mathbb{P}(\mathcal{E}\,|\,\mathcal{A})$ $\displaystyle\geq\Big(\frac{\exp(r_{\max}-1)}{1+\exp(r_{\max}-1)}\Big)^{T}\geq\Big(\frac{\exp(r_{\max}-1)}{1+\exp(r_{\max}-1)}\Big)^{\exp(r_{\max})/2}\geq\frac{1}{4}.$ $$

Conditional on $\mathcal{A}$ and $\mathcal{E}_{t}$, for any $1\leq t\leq T-1$,
all the preference data in $\mathcal{D}^{(t)}$ are of form $a_{1}^{t}\succ a_{2}^{t}$.
In this case, it is straightforward to check that the reward function
that maximizes $\ell(r,\mathcal{D}^{(t)})+\alpha J^{\star}(r;\pi_{\mathsf{ref}})$
is

$$ $r^{(t+1)}(a_{0})=0,\quad r^{(t+1)}(a_{1})=r^{(t+1)}(a_{2})=r_{\max}.$ $$

This immediately implies that

$$ $\pi^{(t+1)}(a_{0})=\frac{\kappa-2}{\kappa-2+2\exp(r_{\max}/\beta)},\quad\pi^{(t+1)}(a_{1})=\pi^{(t+1)}(a_{2})=\frac{\exp(r_{\max}/\beta)}{\kappa-2+2\exp(r_{\max}/\beta)}.$ $$

On the other hand, we know that

$$ $\displaystyle\pi^{\star}(a_{0})$ $\displaystyle=\frac{\kappa-2}{\kappa-2+\exp(r_{\max}/\beta)+\exp((r_{\max}-2)/\beta)},$ $\displaystyle\pi^{\star}(a_{1})$ $\displaystyle=\frac{\exp(r_{\max}/\beta)}{\kappa-2+\exp(r_{\max}/\beta)+\exp((r_{\max}-2)/\beta)},$ $\displaystyle\pi^{\star}(a_{2})$ $\displaystyle=\frac{\exp((r_{\max}-2)/\beta)}{\kappa-2+\exp(r_{\max}/\beta)+\exp((r_{\max}-2)/\beta)}.$ $$

For any $2\leq t\leq T$, we first lower bound

$$ $J(\pi^{\star};r^{\star},\pi_{\mathsf{ref}})-J(\pi^{(t)};r^{\star},\pi_{\mathsf{ref}})\geq J(\pi_{\theta^{\star}};r^{\star},\pi_{\mathsf{ref}})-J(\pi_{1};r^{\star},\pi_{\mathsf{ref}})$ (B.1) $$

for any $\theta^{\star}\in[0,1]$, where we define $\pi_{\theta}\coloneqq\theta\pi^{(t)}+(1-\theta)\pi^{\star}$,
and the above relation follows from the optimality of $\pi^{\star}$.
Recall the definition

$$ $\displaystyle J(\pi;r^{\star},\pi_{\mathsf{ref}})$ $\displaystyle=\pi(a_{1})r_{\max}+\pi(a_{2})(r_{\max}-2)-\beta\sum_{i=0}^{2}\pi(a_{i})\log\frac{\pi(a_{i})}{\pi_{\mathsf{ref}}(a_{i})},$ $$

we can compute

$$ $\nabla_{\pi}J(\pi;r^{\star},\pi_{\mathsf{ref}})=\left[\begin{array}[]{c}r^{\star}(a_{0})-\beta\log[\pi(a_{0})/\pi_{\mathsf{ref}}(a_{0})]-\beta\\ r^{\star}(a_{1})-\beta\log[\pi(a_{1})/\pi_{\mathsf{ref}}(a_{1})]-\beta\\ r^{\star}(a_{2})-\beta\log[\pi(a_{2})/\pi_{\mathsf{ref}}(a_{2})]-\beta\end{array}\right]$ $$

and

$$ $\nabla_{\pi}^{2}J(\pi;r^{\star},\pi_{\mathsf{ref}})=-\beta\mathsf{diag}\left\{\pi(a_{0}),\pi(a_{1}),\pi(a_{2})\right\}^{-1}.$ $$

It is straightforward to check that

$$ $\nabla_{\pi}J(\pi^{(t)};r^{\star},\pi_{\mathsf{ref}})=\left[\begin{array}[]{c}0\\ 0\\ -1\end{array}\right]+\mathsf{const}\cdot\left[\begin{array}[]{c}1\\ 1\\ 1\end{array}\right].$ (B.2) $$

Since $\pi^{(t)}(a_{0})<\pi^{\star}(a_{0})$, $\pi^{(t)}(a_{1})<\pi^{\star}(a_{1})$
and $\pi^{(t)}(a_{2})>\pi^{\star}(a_{2})$, we know that for any $\theta\in[0,\theta^{\star}]$

$$ $\displaystyle\nabla_{\pi}^{2}J(\pi_{\theta};r^{\star},\pi_{\mathsf{ref}})$ $\displaystyle\succeq-\beta\mathsf{diag}\big\{\pi^{(t)}(a_{0}),\pi^{(t)}(a_{1}),\theta^{\star}\pi^{(t)}(a_{2})+(1-\theta^{\star})\pi^{\star}(a_{2})\big\}^{-1}.$ (B.3) $$

Therefore we have

$$ $\displaystyle J(\pi_{\theta^{\star}};r^{\star},\pi_{\mathsf{ref}})-J(\pi_{1};r^{\star},\pi_{\mathsf{ref}})\overset{\text{(i)}}{\geq}\theta^{\star}\nabla_{\pi}J(\pi^{(t)};r^{\star},\pi_{\mathsf{ref}})^{\top}(\pi^{\star}-\pi^{(t)})$ $\displaystyle\qquad\quad-\frac{\beta\theta^{\star 2}}{2}(\pi^{\star}-\pi^{(t)})^{\top}\mathsf{diag}\big\{\pi^{(t)}(a_{0}),\pi^{(t)}(a_{1}),\theta^{\star}\pi^{(t)}(a_{2})+(1-\theta^{\star})\pi^{\star}(a_{2})\big\}^{-1}(\pi^{\star}-\pi^{(t)})$ $\displaystyle\qquad\overset{\text{(ii)}}{\geq}\theta^{\star}[\pi^{(t)}(a_{2})-\pi^{\star}(a_{2})]-\frac{\beta\theta^{\star 2}}{2}[\pi^{\star}(a_{0})+\pi^{\star}(a_{1})+\frac{9}{16}\pi^{(t)}(a_{2})/\theta^{\star}]$ $\displaystyle\qquad=\theta^{\star}[\pi^{(t)}(a_{2})-\pi^{\star}(a_{2})]-\frac{9}{32}\beta\theta^{\star}\pi^{(t)}(a_{2})-\frac{\beta\theta^{\star 2}}{2}[1-\pi^{\star}(a_{2})]$ $\displaystyle\qquad=\left(1-\frac{9}{32}\beta\right)\theta^{\star}\pi^{(t)}(a_{2})-\left(1-\frac{\beta\theta^{\star}}{2}\right)\theta^{\star}\pi^{\star}(a_{2})-\frac{\beta\theta^{\star 2}}{2}$ $\displaystyle\qquad\overset{\text{(iii)}}{\geq}\left(\frac{3}{4}-\frac{9}{32}\beta+\frac{\beta\theta^{\star}}{8}\right)\theta^{\star}\pi^{(t)}(a_{2})-\frac{\beta\theta^{\star 2}}{2}\overset{\text{(iv)}}{\geq}\frac{15}{32}\theta^{\star}\pi^{(t)}(a_{2})-\frac{\theta^{\star 2}}{2}.$ (B.4) $$

Here step (i) follows from the Taylor expansion and ([B.3](https://arxiv.org/html/2509.22633v1#A2.E3));
step (ii) utilizes ([B.2](https://arxiv.org/html/2509.22633v1#A2.E2)) and as well as the following
relations

$$ $\pi^{(t)}(a_{0})\leq\pi^{\star}(a_{0})\leq 2\pi^{(t)}(a_{0}),\quad\pi^{(t)}(a_{1})\leq\pi^{\star}(a_{1})\leq 2\pi^{(t)}(a_{1})$ $$

and when $\beta\leq 1$,

$$ $\pi^{\star}(a_{2})\leq\frac{2}{\exp(2/\beta)+1}\pi^{(t)}(a_{2})\leq\frac{1}{4}\pi^{(t)}(a_{2});$ (B.5) $$

steps (iii) and (iv) follows from ([B.5](https://arxiv.org/html/2509.22633v1#A2.E5)) and $\beta\leq 1$.
When $\kappa\leq\exp(r_{\max}\beta)$, we have

$$ $\pi^{(t)}(a_{2})=\frac{\exp(r_{\max}/\beta)}{\kappa-2+2\exp(r_{\max}/\beta)}\geq\frac{\exp(r_{\max}/\beta)}{3\exp(r_{\max}/\beta)-2}\geq\frac{1}{3}.$ (B.6) $$

By taking ([B.1](https://arxiv.org/html/2509.22633v1#A2.E1)), ([B.4](https://arxiv.org/html/2509.22633v1#A2.E4)) and ([B.6](https://arxiv.org/html/2509.22633v1#A2.E6))
collectively, we have

$$ $(\pi^{\star};r^{\star},\pi_{\mathsf{ref}})-J(\pi^{(t)};r^{\star},\pi_{\mathsf{ref}})\geq\frac{5}{32}\theta^{\star}-\frac{\theta^{\star 2}}{2}\geq\frac{25}{2048}>0.01$ $$

where we take $\theta^{\star}=5/32$.

## Appendix C Proof of auxiliary lemmas

### C.1 Proof of Lemma 1

We first express

$$ $\displaystyle X_{i}\coloneqq\log\frac{\sigma(r^{\star}(a_{+}^{i})-r^{\star}(a_{-}^{i}))}{\sigma(r(a_{+}^{i})-r(a_{-}^{i}))}$ $\displaystyle=\operatorname{\mathds{1}}\{a_{1}^{i}\succ a_{2}^{i}\}\log\frac{\sigma(r^{\star}(a_{1}^{i})-r^{\star}(a_{2}^{i}))}{\sigma(r(a_{1}^{i})-r(a_{2}^{i}))}+\operatorname{\mathds{1}}\{a_{1}^{i}\prec a_{2}^{i}\}\log\frac{\sigma(r^{\star}(a_{2}^{i})-r^{\star}(a_{1}^{i}))}{\sigma(r(a_{2}^{i})-r(a_{1}^{i}))}.$ $$

It is straightforward to check that

$$ $\displaystyle\mathbb{E}\left[X_{i}\big|a_{1}^{i},a_{2}^{i}\right]$ $\displaystyle=\mathbb{P}\left(a_{1}^{i}\succ a_{2}^{i}|a_{1}^{i},a_{2}^{i}\right)\log\frac{\sigma(r^{\star}(a_{1}^{i})-r^{\star}(a_{2}^{i}))}{\sigma(r(a_{1}^{i})-r(a_{2}^{i}))}+\mathbb{P}\left(a_{1}^{i}\prec a_{2}^{i}|a_{1}^{i},a_{2}^{i}\right)\log\frac{\sigma(r^{\star}(a_{2}^{i})-r^{\star}(a_{1}^{i}))}{\sigma(r(a_{2}^{i})-r(a_{1}^{i}))}$ $\displaystyle=\sigma(r^{\star}(a_{1}^{i})-r^{\star}(a_{2}^{i}))\log\frac{\sigma(r^{\star}(a_{1}^{i})-r^{\star}(a_{2}^{i}))}{\sigma(r(a_{1}^{i})-r(a_{2}^{i}))}+\sigma(r^{\star}(a_{2}^{i})-r^{\star}(a_{1}^{i}))\log\frac{\sigma(r^{\star}(a_{2}^{i})-r^{\star}(a_{1}^{i}))}{\sigma(r(a_{2}^{i})-r(a_{1}^{i}))}$ $\displaystyle=\mathsf{KL}\big(\sigma(r^{\star}(a_{1}^{i})-r^{\star}(a_{2}^{i}))\parallel\sigma(r(a_{1}^{i})-r(a_{2}^{i}))\big).$ $$

and

$$ $\left|X_{i}\right|\leq\left|\log\left(1+\exp(-r(a_{+}^{i})+r(a_{-}^{i}))\right)\right|\leq 2r_{\mathsf{max}}.$ $$

In addition, we can compute the variance

$$ $\displaystyle\mathsf{Var}\left(X_{i}\big|a_{1}^{i},a_{2}^{i}\right)$ $\displaystyle=\sigma(r^{\star}(a_{1}^{i})-r^{\star}(a_{2}^{i}))\sigma(r^{\star}(a_{2}^{i})-r^{\star}(a_{1}^{i}))\left[\log\frac{\sigma(r^{\star}(a_{1}^{i})-r^{\star}(a_{2}^{i}))}{\sigma(r(a_{1}^{i})-r(a_{2}^{i}))}-\log\frac{\sigma(r^{\star}(a_{2}^{i})-r^{\star}(a_{1}^{i}))}{\sigma(r(a_{2}^{i})-r(a_{1}^{i}))}\right]^{2}$ $\displaystyle=\sigma(r^{\star}(a_{1}^{i})-r^{\star}(a_{2}^{i}))\sigma(r^{\star}(a_{2}^{i})-r^{\star}(a_{1}^{i}))\left[\log\frac{\sigma(r^{\star}(a_{1}^{i})-r^{\star}(a_{2}^{i}))}{\sigma(r^{\star}(a_{2}^{i})-r^{\star}(a_{1}^{i}))}-\log\frac{\sigma(r(a_{1}^{i})-r(a_{2}^{i}))}{\sigma(r(a_{2}^{i})-r(a_{1}^{i}))}\right]^{2}$ $\displaystyle=\sigma(r^{\star}(a_{1}^{i})-r^{\star}(a_{2}^{i}))\sigma(r^{\star}(a_{2}^{i})-r^{\star}(a_{1}^{i}))\big[r(a_{1}^{i})-r(a_{2}^{i})-r^{\star}(a_{1}^{i})+r^{\star}(a_{2}^{i})\big]^{2}.$ $$

In view of Lemma [5](https://arxiv.org/html/2509.22633v1#Thmlemma5), we have

$$ $\displaystyle\mathsf{KL}\big(\sigma(r^{\star}(a_{1}^{i})-r^{\star}(a_{2}^{i}))\parallel\sigma(r(a_{1}^{i})-r(a_{2}^{i}))\big)$ $\displaystyle\qquad\geq\frac{1}{4}\sigma(r^{\star}(a_{1}^{i})-r^{\star}(a_{2}^{i}))\sigma(r^{\star}(a_{2}^{i})-r^{\star}(a_{1}^{i}))$ $\displaystyle\qquad\qquad\cdot\min\left\{|r(a_{1}^{i})-r(a_{2}^{i})-r^{\star}(a_{1}^{i})+r^{\star}(a_{2}^{i})|,\big[r(a_{1}^{i})-r(a_{2}^{i})-r^{\star}(a_{1}^{i})+r^{\star}(a_{2}^{i})\big]^{2}\right\}$ $\displaystyle\qquad\geq\frac{1}{16r_{\max}}\sigma(r^{\star}(a_{1}^{i})-r^{\star}(a_{2}^{i}))\sigma(r^{\star}(a_{2}^{i})-r^{\star}(a_{1}^{i}))\big[r(a_{1}^{i})-r(a_{2}^{i})-r^{\star}(a_{1}^{i})+r^{\star}(a_{2}^{i})\big]^{2},$ (C.1) $$

where the last step follows from $|r(a_{1}^{i})-r(a_{2}^{i})-r^{\star}(a_{1}^{i})+r^{\star}(a_{2}^{i})|\leq 4r_{\max}$.
Therefore we have

$$ $\mathsf{Var}\left(X_{i}\big|a_{1}^{i},a_{2}^{i}\right)\leq 16r_{\mathsf{max}}\mathsf{KL}\big(\sigma(r^{\star}(a_{+}^{i})-r^{\star}(a_{-}^{i}))\parallel\sigma(r(a_{+}^{i})-r(a_{-}^{i}))\big).$ $$

In addition, we have the following deterministic bound

$$ $\sum_{i=1}^{t}\mathsf{Var}\left(X_{i}\big|a_{1}^{i},a_{2}^{i}\right)\leq 16tr_{\max}^{2}.$ $$

By the Freedman’s inequality (cf. Lemma [6](https://arxiv.org/html/2509.22633v1#Thmlemma6)),
for any fixed $r$, with probability exceeding $1-\delta$,

$$ $\displaystyle|\Delta_{t}(r)|$ $\displaystyle\leq\left|\sum_{i=1}^{t}\left(X_{i}-\mathbb{E}\left[X_{i}\big|a_{1}^{i},a_{2}^{i}\right]\right)\right|$ $\displaystyle\leq C_{2}\sqrt{\sum_{i=1}^{t}r_{\mathsf{max}}\mathsf{KL}\big(\sigma(r^{\star}(a_{1}^{i})-r^{\star}(a_{2}^{i}))\parallel\sigma(r(a_{1}^{i})-r(a_{2}^{i}))\big)\log\frac{\log t}{\delta}}+C_{2}r_{\mathsf{max}}\log\frac{\log t}{\delta}$ $$

for some sufficiently large constant $C_{2}>0$.

### C.2 Proof of Lemma 2

For any fixed $r:\mathcal{A}\to[\pm r_{\max}]$, with probability
exceeding $1-\delta$ we have

$$ $\displaystyle|\Delta_{t}(r)|$ $\displaystyle\overset{\text{(i)}}{\leq}C_{2}\sqrt{\sum_{i=1}^{t}r_{\mathsf{max}}\mathsf{KL}\big(\sigma(r^{\star}(a_{1}^{i})-r^{\star}(a_{2}^{i}))\parallel\sigma(r(a_{1}^{i})-r(a_{2}^{i}))\big)\log\frac{\log T}{\delta}}+C_{2}r_{\mathsf{max}}\log\frac{\log T}{\delta}$ $\displaystyle\overset{\text{(ii)}}{\leq}\frac{1}{2}\sum_{i}\mathsf{KL}\big(\sigma(r^{\star}(a_{1}^{i})-r^{\star}(a_{2}^{i}))\parallel\sigma(r(a_{1}^{i})-r(a_{2}^{i}))\big)+2C_{2}^{2}r_{\max}\log\frac{\log T}{\delta}.$ $$

Here step (i) follows from Lemma [1](https://arxiv.org/html/2509.22633v1#Thmlemma1), and step
(ii) utilizes the AM-GM inequality. This immediately implies that

$$ $\displaystyle\ell(r,\mathcal{D}^{(t)})-\ell(r^{\star},\mathcal{D}^{(t)})$ $\displaystyle=\sum_{i=1}^{t}\log\frac{\sigma(r(a_{+}^{i})-r(a_{-}^{i}))}{\sigma(r^{\star}(a_{+}^{i})-r^{\star}(a_{-}^{i}))}$ $\displaystyle=-\sum_{i=1}^{t}\mathsf{KL}\big(\sigma(r^{\star}(a_{1}^{i})-r^{\star}(a_{2}^{i}))\parallel\sigma(r(a_{1}^{i})-r(a_{2}^{i}))\big)-\Delta_{t}(r)$ $\displaystyle\leq-\frac{1}{2}\sum_{i=1}^{t}\mathsf{KL}\big(\sigma(r^{\star}(a_{1}^{i})-r^{\star}(a_{2}^{i}))\parallel\sigma(r(a_{1}^{i})-r(a_{2}^{i}))\big)+2C_{2}^{2}r_{\max}\log\frac{\log T}{\delta}.$ (C.2) $$

Then we explore the Lipschitzness continuity of the above functionals
of $r$. For any two fixed reward functions $r,r^{\prime}:\mathcal{A}\to[\pm r_{\max}]$,
we have

$$ $\displaystyle\left|\ell(r,\mathcal{D}^{(t)})-\ell(r^{\prime},\mathcal{D}^{(t)})\right|$ $\displaystyle=\sum_{i=1}^{t}\left|\log[\sigma(r(a_{+}^{i})-r(a_{-}^{i}))]-\log[\sigma(r^{\prime}(a_{+}^{i})-r^{\prime}(a_{-}^{i}))]\right|$ $\displaystyle\leq\sum_{i=1}^{t}|r(a_{+}^{i})-r(a_{-}^{i})-r^{\prime}(a_{+}^{i})+r^{\prime}(a_{-}^{i})|\leq 2T\|r-r^{\prime}\|_{\infty},$ (C.3) $$

where the penultimate step follows from $\mathrm{d}\log(\sigma(x))/\mathrm{d}x=\sigma(-x)\leq 1$.
Similarly, for any $x,y,\delta\in\mathbb{R}$, we have

$$ $\displaystyle\left|\mathsf{KL}\big(\sigma(x)\parallel\sigma(y)\big)-\mathsf{KL}\big(\sigma(x)\parallel\sigma(y+\delta)\big)\right|$ $\displaystyle=\left|\sigma(x)\log\frac{\sigma(y+\delta)}{\sigma(y)}+(1-\sigma(x))\log\frac{1-\sigma(y+\delta)}{1-\sigma(y)}\right|$ $\displaystyle\leq\sigma(x)|\delta|+(1-\sigma(x))|\delta|=|\delta|.$ $$

This implies that

$$ $\displaystyle\bigg|\sum_{i=1}^{t}\mathsf{KL}\big(\sigma(r^{\star}(a_{1}^{i})-r^{\star}(a_{2}^{i}))\parallel\sigma(r(a_{1}^{i})-r(a_{2}^{i}))\big)$ $\displaystyle\qquad-\sum_{i=1}^{t}\mathsf{KL}\big(\sigma(r^{\star}(a_{1}^{i})-r^{\star}(a_{2}^{i}))\parallel\sigma(r^{\prime}(a_{1}^{i})-r^{\prime}(a_{2}^{i}))\big)\bigg|\leq 2\|r-r^{\prime}\|_{\infty}.$ (C.4) $$

Let $\mathcal{N}_{\varepsilon}$ be an $\varepsilon$-net of $[-r_{\max},r_{\max}]^{A}$
(or equivalently, the function space of $r:\mathcal{A}\to[\pm r_{\max}]$)
under the $\ell_{\infty}$ norm such that $|\mathcal{N}_{\varepsilon}|\leq(2r_{\max}/\varepsilon)^{A}$.
By standard union bound argument and ([C.2](https://arxiv.org/html/2509.22633v1#A3.E2)), with probability
exceeding $1-\delta$,

$$ $\displaystyle\ell(r,\mathcal{D}^{(t)})-\ell(r^{\star},\mathcal{D}^{(t)})$ $\displaystyle\leq-\frac{1}{2}\sum_{i=1}^{t}\mathsf{KL}\big(\sigma(r^{\star}(a_{1}^{i})-r^{\star}(a_{2}^{i}))\parallel\sigma(r(a_{1}^{i})-r(a_{2}^{i}))\big)+2C_{2}^{2}r_{\max}\log\frac{|\mathcal{N}_{\varepsilon}|\log T}{\delta}$ (C.5) $$

holds for any $r\in\mathcal{N}_{\varepsilon}$. This implies that
for any $r:\mathcal{A}\to[\pm r_{\max}]$, there exists $r_{0}\in\mathcal{N}_{\varepsilon}$
such that $\|r-r^{\prime}\|\leq\varepsilon$, hence

$$ $\displaystyle\ell(r,\mathcal{D}^{(t)})-\ell(r^{\star},\mathcal{D}^{(t)})\overset{\text{(i)}}{\leq}\ell(r_{0},\mathcal{D}^{(t)})-\ell(r^{\star},\mathcal{D}^{(t)})+2T\varepsilon$ $\displaystyle\quad\overset{\text{(ii)}}{\leq}-\frac{1}{2}\sum_{i=1}^{t}\mathsf{KL}\big(\sigma(r^{\star}(a_{1}^{i})-r^{\star}(a_{2}^{i}))\parallel\sigma(r_{0}(a_{1}^{i})-r_{0}(a_{2}^{i}))\big)+2C_{2}^{2}r_{\max}\log\frac{|\mathcal{N}_{\varepsilon}|\log T}{\delta}+2T\varepsilon$ $\displaystyle\quad\overset{\text{(iii)}}{\leq}-\frac{1}{2}\sum_{i=1}^{t}\mathsf{KL}\big(\sigma(r^{\star}(a_{1}^{i})-r^{\star}(a_{2}^{i}))\parallel\sigma(r(a_{1}^{i})-r(a_{2}^{i}))\big)+2C_{2}^{2}r_{\max}\log\frac{|\mathcal{N}_{\varepsilon}|\log T}{\delta}+4T\varepsilon$ $\displaystyle\quad\overset{\text{(iv)}}{\leq}-\frac{1}{2}\sum_{i=1}^{t}\mathsf{KL}\big(\sigma(r^{\star}(a_{1}^{i})-r^{\star}(a_{2}^{i}))\parallel\sigma(r(a_{1}^{i})-r(a_{2}^{i}))\big)+C_{3}Ar_{\max}\log T.$ $$

Here step (i) utilizes ([C.3](https://arxiv.org/html/2509.22633v1#A3.E3)); step (ii) follows from $r_{0}\in\mathcal{N}_{\varepsilon}$
and the uniform concentration bound ([C.5](https://arxiv.org/html/2509.22633v1#A3.E5)); step (iii)
uses ([C.4](https://arxiv.org/html/2509.22633v1#A3.E4)); step (iv) holds as long as $C_{3}\gg 2C_{2}^{2}$,
where we let $\varepsilon=Ar_{\max}/T$ and $\delta=T^{-10}$. This
completes the proof.

### C.3 Proof of Lemma 3

When $N_{t}(a_{+},a_{-})\geq 100C_{4}\alpha_{t}r_{\max}$, we have

$$ $\mathsf{KL}\big(\sigma(r^{\star}(a_{+})-r^{\star}(a_{-}))\parallel\sigma(r^{(t)}(a_{+})-r^{(t)}(a_{-}))\big)\leq\frac{1}{100}.$ (C.6) $$

Now we assert that $r^{(t)}(a_{-})-r^{(t)}(a_{+})<0.5$ for any $t\geq t_{0}$.
This is because, if $r^{(t)}(a_{-})-r^{(t)}(a_{+})\geq 0.5$, we have

$$ $\displaystyle\mathsf{KL}\big(\sigma(r^{\star}(a_{+})-r^{\star}(a_{-}))\parallel\sigma(r^{(t)}(a_{+})-r^{(t)}(a_{-}))\big)$ $\displaystyle=\mathsf{KL}\big(\sigma(r^{\star}(a_{-})-r^{\star}(a_{+}))\parallel\sigma(r^{(t)}(a_{-})-r^{(t)}(a_{+}))\big)$ $\displaystyle\geq\mathsf{KL}\big(\sigma(0)\parallel\sigma(0.5)\big)>\frac{1}{100}.$ $$

Here we use the fact that $r^{\star}(a_{-})-r^{\star}(a_{+})\leq 0$.
This contradicts with ([C.6](https://arxiv.org/html/2509.22633v1#A3.E6)). Hence we have

$$ $r^{(t)}(a_{-})-r^{(t)}(a_{+})<0.5.$ (C.7) $$

Let $p\coloneqq\sigma(r^{\star}(a_{-})-r^{\star}(a_{+}))$ and $q\coloneqq\sigma(r^{(t)}(a_{-})-r^{(t)}(a_{+}))$.
We have

$$ $\displaystyle\exp(r^{(t)}(a_{-})-r^{(t)}(a_{+}))$ $\displaystyle\overset{\text{(i)}}{\leq}3\sigma(r^{(t)}(a_{-})-r^{(t)}(a_{+}))=3q\overset{\text{(ii)}}{\leq}6p+\mathsf{KL}(p\parallel q)$ (C.8) $\displaystyle=6\sigma(r^{\star}(a_{-})-r^{\star}(a_{+}))+24\mathsf{KL}\big(\sigma(r^{\star}(a_{+})-r^{\star}(a_{-}))\parallel\sigma(r^{(t)}(a_{+})-r^{(t)}(a_{-}))\big).$ $$

Here step (i) follows from ([C.7](https://arxiv.org/html/2509.22633v1#A3.E7)), while step (ii)
holds trivially when $q\leq 2p$, and when $q>2p$ we have

$$ $\mathsf{KL}(p\parallel q)=p\log\frac{p}{q}+(1-p)\log\frac{1-p}{1-q}\geq\frac{(q-p)^{2}}{2q}\geq\frac{1}{8}q.$ $$

Finally, for any $t_{0}\leq t_{1}<t_{2}\leq T$, we can upper bound

$$ $N_{t_{2}}(a_{+},a_{-})-N_{t_{1}}(a_{+},a_{-})\leq\sum_{i=t_{1}+1}^{t_{2}}X_{i}\quad\text{where}\quad X_{i}\coloneqq\operatorname{\mathds{1}}\{a_{-}\text{ is sampled in the }i\text{-th iteration}\}.$ $$

It is straightforward to check that $X_{i}-\mathbb{E}[X_{i}|\mathcal{F}_{i-1}]$
is a martingale difference sequence, and by the Azuma-Hoeffding inequality,
with probability exceeding $1-O(T^{-100})$ we have

$$ $\sum_{i=t_{1}+1}^{t_{2}}\left(X_{i}-\mathbb{E}[X_{i}|\pi^{(i)},\pi^{(i-1)}]\right)\leq\widetilde{C}\sqrt{T\log T}$ $$

for some universal constant $\widetilde{C}>0$. In addition, we have

$$ $\displaystyle\mathbb{E}[X_{i}|\pi^{(i)},\pi^{(i-1)}]$ $\displaystyle\leq\frac{\pi^{(i)}(a_{-})}{\pi^{(i)}(a_{-})+\pi^{(i)}(a_{+})}+\frac{\pi^{(i-1)}(a_{-})}{\pi^{(i-1)}(a_{-})+\pi^{(i-1)}(a_{+})}.$ $$

For each $t\in[T]$, we have

$$ $\displaystyle\frac{\pi^{(t)}(a_{-})}{\pi^{(t)}(a_{-})+\pi^{(t)}(a_{+})}\overset{\text{(i)}}{=}\frac{\pi_{\mathsf{ref}}(a_{-})\exp(r^{(t)}(a_{-})/\beta)}{\pi_{\mathsf{ref}}(a_{-})\exp(r^{(t)}(a_{-})/\beta)+\pi_{\mathsf{ref}}(a_{+})\exp(r^{(t)}(a_{+})/\beta)}$ $\displaystyle\qquad\leq\frac{\pi_{\mathsf{ref}}(a_{-})}{\pi_{\mathsf{ref}}(a_{+})}\exp\left(\big(r^{(t)}(a_{-})-r^{(t)}(a_{+})\big)/\beta\right)$ $\displaystyle\qquad\leq\frac{\pi_{\mathsf{ref}}(a_{-})}{\pi_{\mathsf{ref}}(a_{+})}\left[6\sigma(r^{\star}(a_{-})-r^{\star}(a_{+}))+24\mathsf{KL}\big(\sigma(r^{\star}(a_{+})-r^{\star}(a_{-}))\parallel\sigma(r^{(t)}(a_{+})-r^{(t)}(a_{-}))\big)\right]^{1/\beta}.$ $$

Here step (i) utilizes ([2.4](https://arxiv.org/html/2509.22633v1#S2.E4)), while step
(ii) follows from ([C.8](https://arxiv.org/html/2509.22633v1#A3.E8)). Hence we have

$$ $\displaystyle N_{t_{2}}(a_{+},a_{-})-N_{t_{1}}(a_{+},a_{-})$ $\displaystyle\leq 2\sum_{t=t_{1}+1}^{t_{2}}\frac{\pi^{(t)}(a_{-})}{\pi^{(t)}(a_{-})+\pi^{(t)}(a_{+})}+2\widetilde{C}\sqrt{T\log T}$ $\displaystyle\leq C_{5}^{1/\beta}\sum_{t=t_{1}+1}^{t_{2}}\frac{\pi_{\mathsf{ref}}(a_{-})}{\pi_{\mathsf{ref}}(a_{+})}\Big[\mathsf{KL}\big(\sigma(r^{\star}(a_{+})-r^{\star}(a_{-}))\|\sigma(r^{(t)}(a_{+})-r^{(t)}(a_{-}))\big)^{\frac{1}{\beta}}$ $\displaystyle\qquad\qquad\qquad\qquad\qquad+\sigma(r^{\star}(a_{-})-r^{\star}(a_{+}))^{\frac{1}{\beta}}\Big]+C_{5}\sqrt{T\log T}$ $$

for some sufficiently large constant $C_{5}>0$.

### C.4 Proof of Lemma 4

Let $t_{0}$ be the first iteration such that

$$ $N_{t_{0}}(a_{+},a_{-})\geq\min\left\{\frac{1}{2}N_{T}(a_{+},a_{-}),100C_{4}\alpha_{T}r_{\mathsf{max}}\right\}.$ (C.9) $$

In what follows, we establish the desired result under two different
cases: $N_{T}(a_{+},a_{-})$ being larger or smaller than $c_{0}\exp(r^{\star}(a_{+})-r^{\star}(a_{-}))\alpha_{T}r_{\mathsf{max}}$
for some sufficiently large constant $c_{0}>0$.

#### Case 1.

When $N_{T}(a_{+},a_{-})\leq c_{0}\exp(r^{\star}(a_{+})-r^{\star}(a_{-}))\alpha_{T}r_{\mathsf{max}}$,
it is straightforward to show that

$$ $\zeta(a_{+},a_{-})\leq N_{T}(a_{+},a_{-})r_{\max}\leq C_{6}\exp(r^{\star}(a_{+})-r^{\star}(a_{-}))\alpha_{T}r_{\mathsf{max}}^{2}=C_{6}\frac{\pi_{\mathsf{HF}}(a_{+})}{\pi_{\mathsf{HF}}(a_{-})}\alpha_{T}r_{\mathsf{max}}^{2}.$ (C.10) $$

In addition, we have

$$ $\sigma(r^{\star}(a_{-})-r^{\star}(a_{+}))\leq\exp(r^{\star}(a_{-})-r^{\star}(a_{+}))\leq\frac{c_{0}\alpha_{T}r_{\mathsf{max}}}{N_{T}(a_{+},a_{-})}.$ $$

In addition, for any $t_{0}\leq t\leq T$, we can use ([5.8](https://arxiv.org/html/2509.22633v1#S5.E8))
to show that

$$ $\mathsf{KL}\big(\sigma(r^{\star}(a_{+})-r^{\star}(a_{-}))\|\sigma(r^{(t)}(a_{+})-r^{(t)}(a_{-}))\big)\leq\frac{C_{4}\alpha_{t}r_{\max}}{N_{t}(a_{+},a_{-})}\leq\frac{2C_{4}\alpha_{T}r_{\max}}{N_{T}(a_{+},a_{-})}.$ (C.11) $$

By taking $t_{1}=t_{0}-1$ and $t_{2}=T$ in Lemma [3](https://arxiv.org/html/2509.22633v1#Thmlemma3),
we have

$$ $\displaystyle N_{T}(a_{+},a_{-})$ $\displaystyle\overset{\text{(i)}}{\leq}2[N_{T}(a_{+},a_{-})-N_{t_{0}-1}(a_{+},a_{-})]$ $\displaystyle\overset{\text{(ii)}}{\leq}4T\frac{\pi_{\mathsf{ref}}(a_{-})}{\pi_{\mathsf{ref}}(a_{+})}\Big(\frac{C_{5}\max\{c_{0},2C_{4}\}\alpha_{T}r_{\mathsf{max}}}{N_{T}(a_{+},a_{-})}\Big)^{1/\beta}+2C_{5}\sqrt{T\log T}.$ $$

Here step (i) follows from the definition of $t_{0}$ (cf. ([C.9](https://arxiv.org/html/2509.22633v1#A3.E9))),
while step (ii) uses the above two bounds and Lemma [3](https://arxiv.org/html/2509.22633v1#Thmlemma3)
with $t_{1}=t_{0}-1$ and $t_{2}=T$. This immediately implies that

$$ $N_{T}(a_{+},a_{-})\leq C_{7}\left(T\frac{\pi_{\mathsf{ref}}(a_{-})}{\pi_{\mathsf{ref}}(a_{+})}\right)^{\frac{\beta}{\beta+1}}(\alpha_{T}r_{\max})^{\frac{1}{\beta+1}}+C_{7}\sqrt{T\log T}$ $$

for some sufficiently large constant $C_{7}>0$. This leads to

$$ $\zeta(a_{+},a_{-})\leq N_{T}(a_{+},a_{-})r_{\max}\leq C_{7}\left(T\frac{\pi_{\mathsf{ref}}(a_{-})}{\pi_{\mathsf{ref}}(a_{+})}\right)^{\frac{\beta}{\beta+1}}\alpha_{T}^{\frac{1}{\beta+1}}r_{\max}^{\frac{\beta+2}{\beta+1}}+C_{7}\sqrt{T\log T}r_{\max}.$ (C.12) $$

#### Case 2.

When $N_{T}(a_{+},a_{-})>c_{0}\exp(r^{\star}(a_{+})-r^{\star}(a_{-}))\alpha_{T}r_{\mathsf{max}}$,
we have

$$ $\displaystyle\exp(r^{\star}(a_{+})-r^{\star}(a_{-}))\alpha_{T}r_{\mathsf{max}}\leq\frac{1}{c_{0}}N_{T}(a_{+},a_{-})\overset{\text{(i)}}{\leq}\frac{2}{c_{0}}[N_{T}(a_{+},a_{-})-N_{t_{0}-1}(a_{+},a_{-})]$ $\displaystyle\qquad\overset{\text{(ii)}}{\leq}\frac{2C_{5}^{1/\beta}}{c_{0}}T\frac{\pi_{\mathsf{ref}}(a_{-})}{\pi_{\mathsf{ref}}(a_{+})}\Big[\sigma(r^{\star}(a_{-})-r^{\star}(a_{+}))^{1/\beta}+\Big(\frac{2C_{4}\alpha_{T}r_{\max}}{N_{T}(a_{+},a_{-})}\Big)^{1/\beta}\Big]+\frac{2C_{5}}{c_{0}}\sqrt{T\log T}$ $\displaystyle\qquad\overset{\text{(iii)}}{\leq}\frac{4}{c_{0}}\max\{C_{5},2C_{4}C_{5}/c_{0}\}^{1/\beta}T\frac{\pi_{\mathsf{ref}}(a_{-})}{\pi_{\mathsf{ref}}(a_{+})}\exp(r^{\star}(a_{-})-r^{\star}(a_{+}))^{1/\beta}+\frac{2C_{5}}{c_{0}}\sqrt{T\log T}.$ $$

Here step (i) follows from the definition of $t_{0}$ (cf. ([C.9](https://arxiv.org/html/2509.22633v1#A3.E9)));
step (ii) utilizes Lemma [3](https://arxiv.org/html/2509.22633v1#Thmlemma3) with $t_{1}=t_{0}-1$
and $t_{2}=T$, as well as ([C.11](https://arxiv.org/html/2509.22633v1#A3.E11)); step (iii)
holds since $\sigma(r^{\star}(a_{-})-r^{\star}(a_{+}))\leq\exp(r^{\star}(a_{-})-r^{\star}(a_{+}))$
and

$$ $\frac{2C_{4}\alpha_{T}r_{\max}}{N_{T}(a_{+},a_{-})}\leq\frac{2C_{4}\alpha_{T}r_{\max}}{c_{0}\exp(r^{\star}(a_{+})-r^{\star}(a_{-}))\alpha_{T}r_{\mathsf{max}}}\leq\frac{2C_{4}}{c_{0}}\exp(r^{\star}(a_{-})-r^{\star}(a_{+})).$ $$

This immediately implies that for some sufficiently large constant
$C_{8}>0$, we have

$$ $\frac{\pi_{\mathsf{HF}}(a_{+})}{\pi_{\mathsf{HF}}(a_{-})}=\exp(r^{\star}(a_{+})-r^{\star}(a_{-}))\leq C_{8}\Big(\frac{\pi_{\mathsf{ref}}(a_{-})T}{\pi_{\mathsf{ref}}(a_{+})\alpha_{T}r_{\mathsf{max}}}\Big)^{\frac{\beta}{\beta+1}}+C_{8}\frac{\sqrt{T\log T}}{\alpha_{T}r_{\mathsf{max}}}.$ (C.13) $$

Similar to ([C.1](https://arxiv.org/html/2509.22633v1#A3.E1)), we can show that

$$ $\displaystyle\mathsf{KL}\big(\sigma(r^{\star}(a_{+})-r^{\star}(a_{-}))\|\sigma(r(a_{+})-r(a_{-}))\big)=\mathsf{KL}\big(\sigma(r^{\star}(a_{-})-r^{\star}(a_{+}))\|\sigma(r(a_{-})-r(a_{+}))\big)$ $\displaystyle\qquad\overset{\text{(a)}}{\geq}\frac{1}{16r_{\max}}\sigma(r^{\star}(a_{-})-r^{\star}(a_{+}))[1-\sigma(r^{\star}(a_{-})-r^{\star}(a_{+}))][r(a_{+})-r(a_{-})-r^{\star}(a_{+})+r^{\star}(a_{-})]^{2}$ $\displaystyle\qquad\overset{\text{(b)}}{\geq}\frac{1}{64r_{\max}}\exp(r^{\star}(a_{-})-r^{\star}(a_{+}))[r(a_{+})-r(a_{-})-r^{\star}(a_{+})+r^{\star}(a_{-})]^{2}.$ $$

Here step (a) follows from Lemma [5](https://arxiv.org/html/2509.22633v1#Thmlemma5); step
(b) makes use of the fact that $r^{\star}(a_{-})\leq r^{\star}(a_{+})$.
Hence we have

$$ $\displaystyle[r(a_{+})-r(a_{-})-r^{\star}(a_{+})+r^{\star}(a_{-})]^{2}$ $\displaystyle\qquad\leq 64r_{\mathsf{max}}\frac{\pi_{\mathsf{HF}}(a_{+})}{\pi_{\mathsf{HF}}(a_{-})}\mathsf{KL}\big(\sigma(r^{\star}(a_{+})-r^{\star}(a_{-}))\parallel\sigma(r(a_{+})-r(a_{-}))\big).$ (C.14) $$

In addition, we have

$$ $\displaystyle\sum_{i=1}^{t}\mathsf{KL}\big(\sigma(r^{\star}(a_{1}^{i})-r^{\star}(a_{2}^{i}))\parallel\sigma(r^{(t)}(a_{1}^{i})-r^{(t)}(a_{2}^{i}))\big)$ $\displaystyle\overset{\text{(i)}}{\leq}-2\big[\ell(r^{(t)},\mathcal{D}^{(t)})-\ell(r^{\star},\mathcal{D}^{(t)})\big]+2C_{3}Ar_{\mathsf{max}}\log T$ $\displaystyle\overset{\text{(ii)}}{\leq}2\alpha_{t}\gamma_{t}+2C_{3}Ar_{\mathsf{max}}\log T$ $$

Here step (i) follows from Lemma [2](https://arxiv.org/html/2509.22633v1#Thmlemma2), while step
(ii) utilizes ([5.6](https://arxiv.org/html/2509.22633v1#S5.E6)) and the definition of
$\gamma_{t}$ (cf. ([5.2](https://arxiv.org/html/2509.22633v1#S5.E2))). This immediately
implies that

$$ $\mathsf{KL}\big(\sigma(r^{\star}(a_{+})-r^{\star}(a_{-}))\parallel\sigma(r^{(t)}(a_{+})-r^{(t)}(a_{-}))\big)\leq\frac{2\alpha_{t}\gamma_{t}+2C_{3}Ar_{\mathsf{max}}\log T}{N_{t}(a_{+},a_{-})}.$ (C.15) $$

Therefore for any $1\leq n_{1}<n_{2}\leq N_{T}(a_{+},a_{-})$, we
have

$$ $\displaystyle\frac{1}{n_{2}-n_{1}}\bigg(\sum_{n=n_{1}}^{n_{2}}\big|r^{(t_{n})}(a_{+})-r^{(t_{n})}(a_{-})-r^{\star}(a_{+})+r^{\star}(a_{-})\big|\bigg)^{2}$ $\displaystyle\qquad\overset{\text{(i)}}{\leq}\sum_{n=n_{1}}^{n_{2}}[r^{(t_{n})}(a_{+})-r^{(t_{n})}(a_{-})-r^{\star}(a_{+})+r^{\star}(a_{-})]^{2}$ $\displaystyle\qquad\overset{\text{(ii)}}{\leq}64r_{\mathsf{max}}\frac{\pi_{\mathsf{HF}}(a_{+})}{\pi_{\mathsf{HF}}(a_{-})}\sum_{n=n_{1}}^{n_{2}}\mathsf{KL}\big(\sigma(r^{\star}(a_{+})-r^{\star}(a_{-}))\parallel\sigma(r^{(t_{n})}(a_{+})-r^{(t_{n})}(a_{-}))\big)$ $\displaystyle\qquad\overset{\text{(iii)}}{\leq}\frac{128r_{\mathsf{max}}\alpha_{T}}{n_{1}}\frac{\pi_{\mathsf{HF}}(a_{+})}{\pi_{\mathsf{HF}}(a_{-})}\sum_{n=n_{1}}^{n_{2}}\gamma_{t_{n}}+128C_{3}Ar_{\mathsf{max}}^{2}\log T\frac{n_{2}-n_{1}}{n_{1}}\frac{\pi_{\mathsf{HF}}(a_{+})}{\pi_{\mathsf{HF}}(a_{-})}.$ (C.16) $$

Here step (i) uses the Cauchy-Schwarz inequality; step (ii) follows
from ([C.14](https://arxiv.org/html/2509.22633v1#A3.E14)); step (iii) utilizes ([C.15](https://arxiv.org/html/2509.22633v1#A3.E15))
and the fact that $\{\alpha_{t}\}$ is monotonically increasing. Following
the same analysis as in ([5.3](https://arxiv.org/html/2509.22633v1#S5.E3)) and ([5.4](https://arxiv.org/html/2509.22633v1#S5.E4)),
we know that

$$ $\displaystyle\sum_{n=n_{1}}^{n_{2}}\gamma_{t_{n}}$ $\displaystyle\leq\sum_{n=n_{1}}^{n_{2}}\xi_{t_{n}}+\sum_{n=n_{1}}^{n_{2}}\big|r^{(t_{n})}(a_{+})-r^{(t_{n})}(a_{-})-r^{\star}(a_{+})+r^{\star}(a_{-})\big|$ $\displaystyle\leq C_{1}r_{\mathsf{max}}\sqrt{(n_{2}-n_{1})\log T}+\sum_{n=n_{1}}^{n_{2}}\big|r^{(t_{n})}(a_{+})-r^{(t_{n})}(a_{-})-r^{\star}(a_{+})+r^{\star}(a_{-})\big|.$ (C.17) $$

Taking ([C.16](https://arxiv.org/html/2509.22633v1#A3.E16)) and ([C.17](https://arxiv.org/html/2509.22633v1#A3.E17))
collectively and let $n_{2}=2n_{1}$, we know that for any $n_{1}\leq N_{T}(a_{+},a_{-})/2$,

$$ $\displaystyle\bigg(\sum_{n=n_{1}}^{2n_{1}}\big|r^{(t_{n})}(a_{+})-r^{(t_{n})}(a_{-})-r^{\star}(a_{+})+r^{\star}(a_{-})\big|\bigg)^{2}$ $\displaystyle\quad\overset{\text{(iii)}}{\leq}128r_{\mathsf{max}}\alpha_{T}\frac{\pi_{\mathsf{HF}}(a_{+})}{\pi_{\mathsf{HF}}(a_{-})}\sum_{n=n_{1}}^{2n_{1}}\big|r^{(t_{n})}(a_{+})-r^{(t_{n})}(a_{-})-r^{\star}(a_{+})+r^{\star}(a_{-})\big|$ $\displaystyle\quad\qquad+128r_{\mathsf{max}}\frac{\pi_{\mathsf{HF}}(a_{+})}{\pi_{\mathsf{HF}}(a_{-})}n_{1}\left(\alpha_{T}C_{1}r_{\mathsf{max}}\sqrt{\frac{\log T}{n_{1}}}+C_{3}Ar_{\mathsf{max}}\log T\right).$ $$

This self-bounding relation implies that

$$ $\displaystyle\sum_{n=n_{1}}^{2n_{1}}\big|r^{(t_{n})}(a_{+})-r^{(t_{n})}(a_{-})-r^{\star}(a_{+})+r^{\star}(a_{-})\big|\leq 256r_{\mathsf{max}}\alpha_{T}\frac{\pi_{\mathsf{HF}}(a_{+})}{\pi_{\mathsf{HF}}(a_{-})}$ $\displaystyle\qquad\qquad+\sqrt{256r_{\mathsf{max}}\frac{\pi_{\mathsf{HF}}(a_{+})}{\pi_{\mathsf{HF}}(a_{-})}n_{1}\left(\alpha_{T}C_{1}r_{\mathsf{max}}\sqrt{\frac{\log T}{n_{1}}}+C_{3}Ar_{\mathsf{max}}\log T\right)}.$ $\displaystyle\qquad\leq 400r_{\mathsf{max}}\alpha_{T}\frac{\pi_{\mathsf{HF}}(a_{+})}{\pi_{\mathsf{HF}}(a_{-})}+C_{1}r_{\mathsf{max}}\sqrt{n_{1}\log T}+C_{3}n_{1}\frac{Ar_{\mathsf{max}}\log T}{\alpha_{T}},$ $$

where the last relation follows from the AM-GM inequality. By using
the above relation recursively, we have

$$ $\displaystyle\zeta(a_{+},a_{-})$ $\displaystyle\leq\sum_{k=1}^{\lceil\log T\rceil}\sum_{n=N_{T}(a_{+},a_{-})/2^{k}}^{N_{T}(a_{+},a_{-})/2^{k-1}}\big|r^{(t_{n})}(a_{+})-r^{(t_{n})}(a_{-})-r^{\star}(a_{+})+r^{\star}(a_{-})\big|$ $\displaystyle\leq C_{9}r_{\mathsf{max}}\frac{\pi_{\mathsf{HF}}(a_{+})}{\pi_{\mathsf{HF}}(a_{-})}\alpha_{T}\log T+C_{9}r_{\max}\sqrt{N_{T}(a_{+},a_{-})\log T}+C_{9}N_{T}(a_{+},a_{-})\frac{Ar_{\max}\log T}{\alpha_{T}}$ (C.18) $$

for some sufficiently large constant $C_{9}>0$. On the other hand,
taking ([C.18](https://arxiv.org/html/2509.22633v1#A3.E18)) and ([C.13](https://arxiv.org/html/2509.22633v1#A3.E13)) collectively
yields

$$ $\displaystyle\zeta(a_{+},a_{-})$ $\displaystyle\leq C_{8}C_{9}\left(T\frac{\pi_{\mathsf{ref}}(a_{-})}{\pi_{\mathsf{ref}}(a_{+})}\right)^{\frac{\beta}{\beta+1}}\alpha_{T}^{\frac{1}{\beta+1}}r_{\max}^{\frac{1}{\beta+1}}\log T+C_{9}r_{\max}\sqrt{N_{T}(a_{+},a_{-})\log T}$ $\displaystyle\qquad+C_{9}N_{T}(a_{+},a_{-})\frac{Ar_{\max}\log T}{\alpha_{T}}.$ (C.19) $$

By putting ([C.10](https://arxiv.org/html/2509.22633v1#A3.E10)), ([C.12](https://arxiv.org/html/2509.22633v1#A3.E12)), ([C.18](https://arxiv.org/html/2509.22633v1#A3.E18))
and ([C.19](https://arxiv.org/html/2509.22633v1#A3.E19)) together, we have

$$ $\displaystyle\zeta(a_{+},a_{-})$ $\displaystyle\leq C_{6}(r_{\max}+\log T)\min\left\{\frac{\pi_{\mathsf{HF}}(a_{+})}{\pi_{\mathsf{HF}}(a_{-})}\alpha_{T}r_{\mathsf{max}},\left(T\frac{\pi_{\mathsf{ref}}(a_{-})}{\pi_{\mathsf{ref}}(a_{+})}\right)^{\frac{\beta}{\beta+1}}\alpha_{T}^{\frac{1}{\beta+1}}r_{\max}^{\frac{1}{\beta+1}}\right\}$ $\displaystyle\qquad+C_{6}\left(\frac{AN_{T}(a_{+},a_{-})\log T}{\alpha_{T}}+\sqrt{T\log T}\right)r_{\max}$ $$

always holds for some universal constant $C_{6}>0$.

## Appendix D Proof of Proposition 3

Under Assumption [1](https://arxiv.org/html/2509.22633v1#Thmassumption1), we know that for any action
pair $(a_{+},a_{-})$,

$$ $\min\bigg\{\frac{\pi_{\mathsf{HF}}(a_{+})}{\pi_{\mathsf{HF}}(a_{-})}\alpha_{T}r_{\mathsf{max}},\left(T\frac{\pi_{\mathsf{ref}}(a_{-})}{\pi_{\mathsf{ref}}(a_{+})}\right)^{\frac{\beta}{\beta+1}}\alpha_{T}^{\frac{1}{\beta+1}}r_{\max}^{\frac{1}{\beta+1}}\bigg\}\leq\max\big\{\tau\alpha_{T}r_{\mathsf{max}},\left(\kappa T\right)^{\frac{\beta}{\beta+1}}\alpha_{T}^{\frac{1}{\beta+1}}r_{\max}^{\frac{1}{\beta+1}}\big\}.$ $$

Therefore we have

$$ $\displaystyle\mathcal{R}(T)$ $\displaystyle\leq Cr_{\mathsf{max}}A^{2}\sqrt{T\log T}+C\sum_{t=1}^{T}\frac{Ar_{\mathsf{max}}\log T}{\alpha_{t}}+2C(r_{\mathsf{max}}+\log T)A^{2}\tau\alpha_{T}r_{\mathsf{max}}$ $\displaystyle\qquad+C(r_{\mathsf{max}}+\log T)A^{2}\left(\kappa T\right)^{\frac{\beta}{\beta+1}}\alpha_{T}^{\frac{1}{\beta+1}}r_{\max}^{\frac{1}{\beta+1}}.$ $$

By taking

$$ $\alpha_{t}=A\log T+t^{\frac{1}{\beta+2}}\Big(\frac{r_{\max}}{\kappa}\Big)^{\frac{\beta}{\beta+2}}\Big(\frac{\log T}{A(r_{\max}+\log T)}\Big)^{\frac{\beta+1}{\beta+2}},$ $$

we can achieve

$$ $\displaystyle\mathcal{R}(T)$ $\displaystyle\lesssim(r_{\mathsf{max}}+\log T)A^{3}\tau r_{\mathsf{max}}\log T+r_{\mathsf{max}}A^{2}\sqrt{T\log T}$ $\displaystyle\qquad+(r_{\max}+\log T)^{\frac{\beta+1}{\beta+2}}r_{\max}^{\frac{2}{\beta+2}}\kappa^{\frac{\beta}{\beta+2}}A^{\frac{2\beta+3}{\beta+2}}T^{\frac{\beta+1}{\beta+2}}(\log T)^{\frac{1}{\beta+2}}$ $\displaystyle\qquad+(r_{\mathsf{max}}+\log T)^{\frac{1}{\beta+2}}A^{\frac{\beta+3}{\beta+2}}\tau r_{\mathsf{max}}^{\frac{2\beta+2}{\beta+2}}\kappa^{-\frac{\beta}{\beta+2}}(\log T)^{\frac{\beta+1}{\beta+2}}T^{\frac{1}{\beta+2}}$ $\displaystyle\qquad+(r_{\mathsf{max}}+\log T)A^{\frac{2\beta+3}{\beta+1}}\kappa^{\frac{\beta}{\beta+1}}(\log T)^{\frac{1}{\beta+1}}r_{\max}^{\frac{1}{\beta+1}}T^{\frac{\beta}{\beta+1}}$ $\displaystyle\lesssim\tau A^{3}r_{\mathsf{max}}^{2}\log^{2}T+T^{\frac{\beta+1}{\beta+2}}\kappa^{\beta}r_{\max}^{2}A^{3}\tau\log^{2}T.$ $$

## Appendix E Another assumption and the regret bound

As an alternaive to Assumption [1](https://arxiv.org/html/2509.22633v1#Thmassumption1), we can also impose
the following assumption to capture the relation between human preference
$\pi_{\mathsf{HF}}$ and the reference policy $\pi_{\mathsf{ref}}$.

###### Assumption 2 .

There exists some quantity
$\mu>0$ such that, for any action pair $(a_{+},a_{-})$,

$$ $\frac{\pi_{\mathsf{HF}}(a_{+})}{\pi_{\mathsf{HF}}(a_{-})}\leq\mu\frac{\pi_{\mathsf{ref}}(a_{+})}{\pi_{\mathsf{ref}}(a_{-})}.$ $$

The quantity $\mu$ measures the deviation of human preference from
the reference policy. Under Assumption [2](https://arxiv.org/html/2509.22633v1#Thmassumption2), we have

$$ $\displaystyle\min\bigg\{\frac{\pi_{\mathsf{HF}}(a_{+})}{\pi_{\mathsf{HF}}(a_{-})}\alpha_{T}r_{\mathsf{max}},\left(T\frac{\pi_{\mathsf{ref}}(a_{-})}{\pi_{\mathsf{ref}}(a_{+})}\right)^{\frac{\beta}{\beta+1}}\alpha_{T}^{\frac{1}{\beta+1}}r_{\max}^{\frac{1}{\beta+1}}\bigg\}$ $\displaystyle\qquad\leq\min\bigg\{\mu\frac{\pi_{\mathsf{ref}}(a_{+})}{\pi_{\mathsf{ref}}(a_{-})}\alpha_{T}r_{\mathsf{max}},\left(T\frac{\pi_{\mathsf{ref}}(a_{-})}{\pi_{\mathsf{ref}}(a_{+})}\right)^{\frac{\beta}{\beta+1}}\alpha_{T}^{\frac{1}{\beta+1}}r_{\max}^{\frac{1}{\beta+1}}\bigg\}.$ $\displaystyle\qquad\leq(\mu T)^{\frac{\beta}{2\beta+1}}(\alpha_{T}r_{\max})^{\frac{\beta+1}{2\beta+1}}.$ $$

Putting the above relation with ([4.1](https://arxiv.org/html/2509.22633v1#S4.E1)), we have

$$ $\displaystyle\mathcal{R}(T)$ $\displaystyle\lesssim r_{\mathsf{max}}A^{2}\sqrt{T\log T}+\sum_{t=1}^{T}\frac{Ar_{\mathsf{max}}\log T}{\alpha_{t}}+A^{2}\alpha_{T}r_{\mathsf{max}}^{2}$ $\displaystyle\qquad+(r_{\mathsf{max}}+\log T)A^{2}(\mu T)^{\frac{\beta}{2\beta+1}}(\alpha_{T}r_{\max})^{\frac{\beta+1}{2\beta+1}}.$ $$

By taking

$$ $\alpha_{t}=A+t^{\frac{\beta+1}{3\beta+2}}\big(\frac{r_{\max}}{\mu}\big)^{\frac{\beta}{3\beta+2}}\big(\frac{\log T}{A(r_{\max}+\log T)}\big)^{\frac{2\beta+1}{3\beta+2}},$ $$

we have

$$ $\displaystyle\mathcal{R}(T)$ $\displaystyle\lesssim T^{\frac{2\beta+1}{3\beta+2}}\mu^{\frac{\beta}{3\beta+2}}\mathsf{poly}(A,r_{\max},\log T).$ $$

###### Assumption 2 .

## Appendix F Technical lemmas

###### Lemma 5 .

For any $x,\delta\in\mathbb{R}$,
we have

$$ $\mathsf{KL}(\sigma(x)\|\sigma(x+\delta))\geq\frac{1}{4}\sigma(x)\left(1-\sigma(x)\right)\min\{|\delta|,\delta^{2}\}.$ $$

###### Proof.

Let $f_{x}(t)\coloneqq\mathsf{KL}(\sigma(x)\|\sigma(x+t))$. We
have

$$ $\displaystyle f_{x}(t)$ $\displaystyle=\sigma(x)\log\frac{\sigma(x)}{\sigma(x+t)}+(1-\sigma(x))\log\frac{1-\sigma(x)}{1-\sigma(x+t)}$ $\displaystyle=\sigma(x)\log\left(\frac{\sigma(x)}{1-\sigma(x)}\cdot\frac{1-\sigma(x+t)}{\sigma(x+t)}\right)+\log\frac{1-\sigma(x)}{1-\sigma(x+t)}$ $\displaystyle=\log\frac{1+\exp(x+t)}{1+\exp(x)}-\sigma(x)t=\log\left(1+\sigma(x)(e^{t}-1)\right)-\sigma(x)t.$ $$

Then we have

$$ $f_{x}^{\prime}(t)=\frac{\sigma(x)e^{t}}{1+\sigma(x)(e^{t}-1)}-\sigma(x)=\frac{\sigma(x)\left(1-\sigma(x)\right)(e^{t}-1)}{1+\sigma(x)(e^{t}-1)}.$ $$

For any $t>0$, we can check that

$$ $\displaystyle f_{x}^{\prime}(t)$ $\displaystyle>\sigma(x)\left(1-\sigma(x)\right)\left(1-e^{-t}\right)\geq\frac{1}{2}\sigma(x)\left(1-\sigma(x)\right)\min\left\{t,1\right\},$ $$

and for any $t\in(0,1)$ we have

$$ $\displaystyle f_{x}^{\prime}(t)$ $\displaystyle<\sigma(x)\left(1-\sigma(x)\right)\left(e^{t}-1\right)\leq 2\sigma(x)\left(1-\sigma(x)\right)t.$ $$

This immediately implies that for $\delta>0$,

$$ $\displaystyle\mathsf{KL}\left(\sigma(x)\|\sigma(x+\delta)\right)$ $\displaystyle=f_{x}(\delta)-f_{x}(0)=\int_{0}^{\delta}f_{x}^{\prime}(t)\mathrm{d}t$ $\displaystyle\geq\frac{1}{2}\sigma(x)\left(1-\sigma(x)\right)\int_{0}^{\delta}\min\left\{t,1\right\}\mathrm{d}t$ $\displaystyle\overset{\text{(a)}}{\geq}\frac{1}{4}\sigma(x)\left(1-\sigma(x)\right)\min\{\delta,\delta^{2}\}.$ $$

Here step (a) holds since $\int_{0}^{\delta}\min\{t,1\}\mathrm{d}t=\delta^{2}/2$
for $\delta\leq 1$, and $\int_{0}^{\delta}\min\{t,1\}\mathrm{d}t=\delta-1/2\geq\delta/2$
for $\delta>1$.

For $\delta<0$, we can use the same argument to show that

$$ $\mathsf{KL}\left(\sigma(x)\|\sigma(x+\delta)\right)\geq\frac{1}{4}\sigma(x)\left(1-\sigma(x)\right)\min\{-\delta,\delta^{2}\}.$ $$

This completes the proof. ∎

The following lemma provides a user-friendly version of Freedman’s
inequality (the Bernstein inequality for martingale differences) (Freedman,, 1975; Tropp,, 2011).

###### Lemma 6 .

Consider a filtration $\{\mathcal{F}_{i}\}_{i\geq 0}$
and random variables $\{X_{i}\}_{i\geq 1}$ obeying

$$ $|X_{i}|\leq R\qquad\text{and}\qquad\mathbb{E}[X_{i}|\mathcal{F}_{i-1}]=0\qquad\text{for all }i\geq 1.$ $$

Define $W_{n}=\sum_{i=1}^{n}\mathbb{E}[X_{i}^{2}|\mathcal{F}_{i-1}]$,
and suppose that $W_{n}\leq\sigma^{2}$ holds deterministically for
some given quantity $\sigma>0$. Then for any positive integer $m\geq 1$,
with probability exceeding $1-\delta$ we have

$$ $\left|\sum_{i=1}^{n}X_{i}\right|\leq\sqrt{8\max\left\{W_{n},\frac{\sigma^{2}}{2^{m}}\right\}\log\frac{2m}{\delta}}+\frac{4}{3}R\log\frac{2m}{\delta}.$ $$

###### Proof.

See Li et al., (2021, Section A).∎

###### Lemma 5 .

###### Proof.

###### Lemma 6 .

###### Proof.

## References

- Azar et al., (2024)
Azar, M. G., Guo, Z. D., Piot, B., Munos, R., Rowland, M., Valko, M., and
Calandriello, D. (2024).
A general theoretical paradigm to understand learning from human
preferences.
In International Conference on Artificial Intelligence and
Statistics, pages 4447–4455. PMLR.
- Azar et al., (2017)
Azar, M. G., Osband, I., and Munos, R. (2017).
Minimax regret bounds for reinforcement learning.
In International Conference on Machine Learning, pages
263–272. PMLR.
- Bai et al., (2022)
Bai, Y., Jones, A., Ndousse, K., Askell, A., Chen, A., DasSarma, N., Drain, D.,
Fort, S., Ganguli, D., Henighan, T., et al. (2022).
Training a helpful and harmless assistant with reinforcement learning
from human feedback.
arXiv preprint arXiv:2204.05862.
- Bradley and Terry, (1952)
Bradley, R. A. and Terry, M. E. (1952).
Rank analysis of incomplete block designs: I. the method of paired
comparisons.
Biometrika, 39(3/4):324–345.
- Cen et al., (2025)
Cen, S., Mei, J., Goshvadi, K., Dai, H., Yang, T., Yang, S., Schuurmans, D.,
Chi, Y., and Dai, B. (2025).
Value-incentivized preference optimization: A unified approach to
online and offline RLHF.
In The Thirteenth International Conference on Learning
Representations.
- Chen et al., (2024)
Chen, Z., Deng, Y., Yuan, H., Ji, K., and Gu, Q. (2024).
Self-play fine-tuning converts weak language models to strong
language models.
In International Conference on Machine Learning, pages
6621–6642. PMLR.
- Christiano et al., (2017)
Christiano, P. F., Leike, J., Brown, T., Martic, M., Legg, S., and Amodei, D.
(2017).
Deep reinforcement learning from human preferences.
Advances in neural information processing systems, 30.
- Dong et al., (2024)
Dong, H., Xiong, W., Pang, B., Wang, H., Zhao, H., Zhou, Y., Jiang, N., Sahoo,
D., Xiong, C., and Zhang, T. (2024).
Rlhf workflow: From reward modeling to online rlhf.
arXiv preprint arXiv:2405.07863.
- Feng et al., (2025)
Feng, Y., Kwiatkowski, A., Zheng, K., Kempe, J., and Duan, Y. (2025).
Pilaf: Optimal human preference sampling for reward modeling.
arXiv preprint arXiv:2502.04270.
- Freedman, (1975)
Freedman, D. A. (1975).
On tail probabilities for martingales.
The Annals of Probability, pages 100–118.
- Guo et al., (2024)
Guo, S., Zhang, B., Liu, T., Liu, T., Khalman, M., Llinares, F., Rame, A.,
Mesnard, T., Zhao, Y., Piot, B., et al. (2024).
Direct language model alignment from online ai feedback.
arXiv preprint arXiv:2402.04792.
- Ivison et al., (2023)
Ivison, H., Wang, Y., Pyatkin, V., Lambert, N., Peters, M., Dasigi, P., Jang,
J., Wadden, D., Smith, N. A., Beltagy, I., et al. (2023).
Camels in a changing climate: Enhancing lm adaptation with tulu 2.
arXiv preprint arXiv:2311.10702.
- Jin et al., (2018)
Jin, C., Allen-Zhu, Z., Bubeck, S., and Jordan, M. I. (2018).
Is Q-learning provably efficient?
In Advances in Neural Information Processing Systems, pages
4863–4873.
- Lai and Robbins, (1985)
Lai, T. L. and Robbins, H. (1985).
Asymptotically efficient adaptive allocation rules.
Advances in applied mathematics, 6(1):4–22.
- Lattimore and Szepesvári, (2020)
Lattimore, T. and Szepesvári, C. (2020).
Bandit algorithms.
Cambridge University Press.
- Li et al., (2021)
Li, G., Cai, C., Chen, Y., Gu, Y., Wei, Y., and Chi, Y. (2021).
Is Q-learning minimax optimal? a tight sample complexity analysis.
arXiv preprint arXiv:2102.06548.
- OpenAI, (2023)
OpenAI (2023).
Gpt-4 technical report.
arXiv preprint arXiv:2303.08774.
- Ouyang et al., (2022)
Ouyang, L., Wu, J., Jiang, X., Almeida, D., Wainwright, C., Mishkin, P., Zhang,
C., Agarwal, S., Slama, K., Ray, A., et al. (2022).
Training language models to follow instructions with human feedback.
Advances in neural information processing systems,
35:27730–27744.
- Rafailov et al., (2024)
Rafailov, R., Hejna, J., Park, R., and Finn, C. (2024).
From $r$ to $Q^{*}$: Your language model is secretly a Q-function.
In First Conference on Language Modeling.
- Rosset et al., (2024)
Rosset, C., Cheng, C.-A., Mitra, A., Santacroce, M., Awadallah, A., and Xie, T.
(2024).
Direct nash optimization: Teaching language models to self-improve
with general preferences.
arXiv preprint arXiv:2404.03715.
- Russo and Van Roy, (2013)
Russo, D. and Van Roy, B. (2013).
Eluder dimension and the sample complexity of optimistic exploration.
Advances in Neural Information Processing Systems, 26.
- Shi et al., (2025)
Shi, R., Song, M., Zhou, R., Zhang, Z., Fazel, M., and Du, S. S. (2025).
Understanding the performance gap in preference learning: A dichotomy
of rlhf and dpo.
arXiv preprint arXiv:2505.19770.
- Tropp, (2011)
Tropp, J. (2011).
Freedman’s inequality for matrix martingales.
Electronic Communications in Probability, 16:262–270.
- Xie et al., (2025)
Xie, T., Foster, D. J., Krishnamurthy, A., Rosset, C., Awadallah, A. H., and
Rakhlin, A. (2025).
Exploratory preference optimization: Harnessing implicit
q*-approximation for sample-efficient RLHF.
In The Thirteenth International Conference on Learning
Representations.
- Xiong et al., (2023)
Xiong, W., Dong, H., Ye, C., Wang, Z., Zhong, H., Ji, H., Jiang, N., and Zhang,
T. (2023).
Iterative preference learning from human feedback: Bridging theory
and practice for rlhf under kl-constraint.
arXiv preprint arXiv:2312.11456.
- Zanette and Brunskill, (2019)
Zanette, A. and Brunskill, E. (2019).
Tighter problem-dependent regret bounds in reinforcement learning
without domain knowledge using value function bounds.
In International Conference on Machine Learning, pages
7304–7312. PMLR.
- Zhang et al., (2025)
Zhang, S., Yu, D., Sharma, H., Zhong, H., Liu, Z., Yang, Z., Wang, S.,
Awadalla, H. H., and Wang, Z. (2025).
Self-exploring language models: Active preference elicitation for
online alignment.
Transactions on Machine Learning Research.
- Zhao et al., (2023)
Zhao, Y., Joshi, R., Liu, T., Khalman, M., Saleh, M., and Liu, P. J. (2023).
Slic-hf: Sequence likelihood calibration with human feedback.
arXiv preprint arXiv:2305.10425.
- Zhu et al., (2024)
Zhu, B., Frick, E., Wu, T., Zhu, H., Ganesan, K., Chiang, W.-L., Zhang, J., and
Jiao, J. (2024).
Starling-7b: Improving helpfulness and harmlessness with rlaif.
In First Conference on Language Modeling.
- Ziegler et al., (2019)
Ziegler, D. M., Stiennon, N., Wu, J., Brown, T. B., Radford, A., Amodei, D.,
Christiano, P., and Irving, G. (2019).
Fine-tuning language models from human preferences.
arXiv preprint arXiv:1909.08593.

## Peer Reviews

confidence: 3
contribution: 2
initial_rating: 2
presentation: 3
questions: Please see the weaknesses 1.-3. for questions.
Typo line 86: SVT --> SFT
soundness: 3
strengths: The paper is clearly written and gives a good summary of most prior work on online sampling and exploration bonuses. It provides clear statements and proofs in the bandit setting, which are discussed so the reader can understand some higher level picture. It gives a good self contained intro to reward modeling and RLHF.
summary: This paper proposes another variant of online/iterative DPO to improve online RLHF. It also analyses the regret in the bandit setting of some proposed alternatives in the literature (XPO, VPO and SELM) to show, for some of them, that regret might scale unfavorably in some parameters. They propose a new algorithm  (a variant close to XPO, except that the second trajectory is sampled not from the reference policy, but from the previous policy one timestep ago) and show in the bandit setting that this algorithm has a regret which, while scaling less favorably in the number of time steps, scales polynomially in all other parameters (like \beta, the KL strength).
weaknesses: A major weakness of this work is a total lack of experiments on LLMs (or of any experiments, for that matter). Of course, this paper could be styled as a pure theoretical contribution, but given it actually proposes a new sampling strategy for RLHF for LLMs, and then does all the theory on bandits, not having any experiments beyond the bandit setting is a real problem. 
Minor weaknesses:
1. The paper works with a calibration policy \pi_{\cal} which is not standard in all recent RLHF papers (for instance, XPO doesn't have it). As such, I would have liked more of a discussion on why it is being used in this paper and why other papers managed without it.
2. There are more sampling approaches that are not being discussed, when they should be, like the PILAF paper (Feng et al 25). Can you add and compare (beyond just citing it)?
3. I am actually missing a motivation of why it is important to not scale exponentially in some parameters like \beta. In the end, this is a constant in practical implementations.

---

confidence: 2
contribution: 2
initial_rating: 4
presentation: 3
questions: 1. Since the proposed strategy involves sampling a completion from previous model $\pi^{(t-1)}$，I wonder how this can be implemented in practice. I think keeping an old copy of model parameters is not viable for large models, and caching completions faces storage issue.
soundness: 3
strengths: 1. The topic being considered, the exploration strategy for online RLHF, is of great importance.
2. The paper provides some insight for why current methods such as VPO are not optimal.
summary: The paper proposes a new exploration strategy for online RLHF, which samples one completion from the previous policy and one completion from the current policy. This strategy is motivated from the perspective of uncertainty reduction, with the intuition that the reward differences from such completion pairs are more informative for policy improvements. Under a multi-armed bandit setting, this strategy is proved to have polynomial regret.
weaknesses: 1. There is no empirical evidence for the efficacy of the proposed strategy.

2. The theoretical analysis is based on a multi-armed bandit setting, which assumes a fixed set of actions. However, in this paper actions correspond to model completions. In this case the action space itself is exponentially large. Since the regret bound involves the size of action space, I wonder if such regret bound is meaningful in practice.

3. Although uncertainty reduction is not a novel idea, this paper does not mention any prior strategies in the area of preference modeling.

---

confidence: 4
contribution: 3
initial_rating: 6
presentation: 2
questions: See weakness
soundness: 4
strengths: The paper is a solid theoretical paper with sharp insight into algorithm design, which is already interesting and relevant enough, from my understanding, to guarantee a potential acceptance.

1. The paper discovers two shortcomings of traditional exploration in preference-based RL in LLMs. First, the compared actions do not directly align with decreasing the uncertainty compared to the calibration policy, which defines the uncertainty bonus. Second, even when we compare actions from the current policy to the calibration policy, a fixed calibration policy is not enough. Both are rigorously shown from counterexamples and propositions.

2. The proposed algorithm, in principle, solves both problems intuitively. A regret guarantee is given with polynomial dependence on all problem parameters. And in the regime without KL regularization, the rate matches the best known regret.

3. For most parts, the paper is quite well-written.
summary: The paper studies online RLHF and proposes a new uncertainty-based exploration framework. The paper discovers an interesting phenomenon in existing optimism-based exploration methods, i.e., the uncertainty quantification misaligns with the action-pair selection. To correct it, the paper proposes a new exploration algorithm that uses an adaptive calibration policy and sequentially compares the current policy with the calibration policy to reduce the reward uncertainty. A regret guarantee is presented with rate $T^{\frac{\beta + 1}{\beta+2}}$ where $\beta$ is the KL regularization weight, with polynomial dependence on other quantities.
weaknesses: There are some weaknesses in this paper despite its solid contribution. I will raise my score if, in general, the inconsistency between the theoretical characterization of regret bound in some cases and the intuition of algorithm development is resolved to some extent.

1. The theoretical results with KL regularization are a bit detached from the storytelling of the algorithm design. It is a bit strange in the sense that (consider the example of $\beta = 1$ and examine the large $T$ regime) the proposed algorithm should work better than traditional RLHF exploration algorithms, from an intuitive understanding, but the regret bound looks otherwise. The new algorithm has $T^{2/3}$ while classic algorithm has $T^{1/2}$. The authors should include a deep discussion on why the exponent $\beta / (\beta + 2)$ appears, and explain carefully why this could or could not be fundamental.

2. I feel the regret defined in the regularized objective function is not natural and does not make sense at several points. They make more sense in terms of studying the convergence of policy, but not the regret. Regret should only count the loss of utility in previous rounds and not other notions such as the KL divergence. Essentially, people want a policy with a large reward. For example, if a policy only uses the best arm $a^*$, it should be a very good policy. But in the paper's definition of regret, this policy would incur a large constant regret in some cases. On the other hand, the regret also cumulatively sums the KL distance difference of policies to the reference policy, which does not translate to any physical meaning. I understand the authors are following a line of work that defines regret as it is in the paper, but I feel there is a way to define the regret more naturally and present the results more cleanly, while still recognizing the effect of KL regularization. For example, one could let the regret be $0$ when the policy value $J(\pi)$ is larger than the value of the optimal policy defined by the regularized problem. I do believe the guarantee in the paper could directly translate to a guarantee in an alternative definition where the regret would directly reflect the loss of utility and the distance to true optimality. This may also be part of the reason why the regret guarantee does not match classic exploration in dependence on $T$.

3. The essential principle behind the adaptive calibration policy and comparison to it for exploration is very closely related to the optimism principle in dueling bandit problems, e.g., RUCB, which also uses a dynamic challenger scheme. A discussion of this literature and comparing the proposed algorithm to them would benefit the paper a lot, especially in explaining the idea and motivation behind the proposed method. That is, there is a systematic flaw in classic exploration in LLM RLHF.

4. The paper should use a representative empirical study (a contextual bandit example as the model of this paper should suffice) to validate a few aspects that are not clear from the theory section. First, the regret guarantee seems to be somewhat inconsistent with the beneficiary described in the algorithm development, so empirical evidence would present a lot of insight into whether the rate is a fundamental block (as suspected by the authors), or is merely something from an analysis bottleneck, but the algorithm itself would still perform better than classic exploration. Second, it would strengthen the impact for practitioners to fix the systematic flaw discovered in this paper in LLM RLHF.

5. The claim in the abstract is overly strong. Various papers study online RLHF, but in different settings where the regret (subject to different definitions) could be polynomial in all parameters. For example, plugging in a dueling bandit algorithm into an MAB setting studied in this paper with $\beta = 0$ would lead to a regret bound that is polynomial in all parameters. I suggest the authors remove this claim.