Zeroth-Order Policy Gradient for Reinforcement Learning from Human Feedback without Reward Inference

## Abstract

Abstract Reward inference (learning a reward model from human preferences) is a critical intermediate step in Reinforcement Learning from Human Feedback (RLHF) for fine-tuning Large Language Models (LLMs) such as ChatGPT. In practice, reward inference faces several fundamental challenges, including double problem misspecification, reward model evaluation without ground truth, distribution shift, and overfitting in joint reward model and policy training.
An alternative approach that avoids these pitfalls is direct policy optimization without reward inference, such as Direct Preference Optimization (DPO), which provides a much simpler pipeline and has shown empirical success in LLMs. However, DPO utilizes the closed-form expression between the optimal policy and the reward function, which only works under the bandit setting or deterministic MDPs. This paper develops two RLHF algorithms without reward inference, which work for general RL problems beyond bandits and deterministic MDPs, and general preference models beyond the Bradely-Terry model. The key idea is to estimate the local value function difference from human preferences and then approximate the policy gradient with a zeroth-order gradient approximator. For both algorithms, we establish rates of convergence in terms of the number of policy gradient iterations, as well as the number of trajectory samples and human preference queries per iteration. Our results show there exist provably efficient methods to solve general RLHF problems without reward inference.

## 1 Introduction

In the past decade, we have witnessed unprecedented success in applying Reinforcement Learning (RL) to many applications, such as gaming AI (Knox and Stone, ; Warnell et al., ), recommendation and search (Zeng et al., ; Kohli et al., ), autonomous driving (Kiran et al., )
, and large language models (LLM) (Christiano et al., ; Wu et al., ; Nakano et al., ; Ziegler et al., ; Stiennon et al., ; Ouyang et al., ). RL studies the interaction between decision-making agents and a dynamic environment that keeps evolving. At each time step, the agent takes a certain decision (action) given the current state, a reward signal to measure the quality of that decision is provided by the environment. The agent’s goal is to learn a policy to maximize the cumulative reward, and the quality of the learned policy will depend on the per-step reward function. In classic RL, this reward function is usually handcrafted by domain experts to ensure it aligns with our expectations of the agent’s behavior. However, identifying a “good” reward function, also called Inverse RL (IRL), is one of the most fundamental problems in RL and is non-trivial. In recent years, researchers have developed a new approach called Reinforcement Learning from Human Feedback (RLHF) that uses human preference feedback as a signal to recover a reward function and then train or fine-tune LLMs (such as ChatGPT) with RL, which has delivered significant success. RLHF follows the diagram shown in Fig. 1, which includes three major steps (Ouyang et al., ): (i) policy network pre-training, (ii) query human evaluators for preferences over trajectories to train a reward model that aligns with human feedback, and (iii) use policy-gradient RL algorithms such as PPO to fine-tune the policy network using the reward model.

Drawbacks of Reward Inference.
To train a good reward model, i.e., to infer the underlying per-step reward function from human feedback (Christiano et al., ; Wang et al., ), the most common approach is to assume the feedback is generated based on a preference model such as the Bradley-Terry model (Bradley and Terry, ), and then maximize the log-likelihood of the collected trajectory comparison dataset accordingly over all possible (parameterized) reward functions. This procedure is indeed analyzed in most theoretical RLHF papers for both offline (Zhu et al., ; Zhan et al., ) and online settings (Saha et al., ; Zhan et al., ; Wu and Sun, ; Wang et al., ; Du et al., ). However, several challenges occur in practice for reward model training such as double problem mis-specification, reward model evaluation without ground truth, distribution shift, and overfitting in joint reward model and policy training (Casper et al., ). These drawbacks are also reflected in the theoretical results, e.g., overfitting of MLE in (Zhu et al., ). Moreover, similar to inverse reinforcement learning (IRL), the reward function that could explain the human feedback often is not unique, especially when given a limited amount of training trajectories (Arora and Doshi, ; Ng and Russell, ). Some reward models may make it difficult for agents to learn a good RL policy.

Figure: Figure 1: A diagram illustrating classic policy-based RLHF and DPO: classic RLHF involves three steps: (i) pre-train a policy network (agent), (ii) collect trajectories from the environment using a behavior policy, query the human comparison for each trajectory pair and train a reward neural network through maximizing the likelihood under the Bradley-Terry model, and (iii) train the policy network with reward signals from the reward network. DPO does not train a reward network but directly optimizes the policy network from human preferences.
Refer to caption: x1.png

DPO. To avoid the drawbacks of the reward inference in RLHF, Rafailov et al. () proposed an algorithm called Direct Preference Optimization (DPO) which fine-tunes the LLM model *directly* from human preferences. Based on the Bradley-Terry preference model and a closed-form expression of the optimal policy given a reference policy and the reward function, DPO constructs a loss function directly from human feedback for learning the optimal policy, so avoids reward inference.
This provides a much simpler pipeline and has great empirical performance (Rafailov et al., , , ). However,
the closed-form expression of the optimal policy that DPO builds on is only for non-parametric policies and its theoretical justification only works for the bandit setting (Rafailov et al., ) or RL problems with deterministic transitions (Rafailov et al., ). It remains an open question how to solve general RLHF problems without reward inference.

RLHF without Reward Inference.
Recently, value-based RLHF algorithms without global reward inference have been theoretically developed and analyzed (Xu et al., ; Zhang et al., ) based on a dueling bandit approach (Bengs et al., ). The results, however, only hold for MDPs in tabular settings with finite state and action spaces. Chen et al. () studied the function approximation regime,
but their algorithm requires both the true preference model and the transition kernel to belong to a known function class, which is impractical. The result also depends on the function class complexity which is usually large for most function approximators in practice. So far, no provable policy-based algorithm in this category has been developed.

This paper addresses the following important question:

> Does there exist a provably efficient RLHF approach that does not require a reward model and works for general RL problems such as stochastic MDPs or infinite state and action spaces?

### 1.1 Main Contributions

DPO (Rafailov et al., ) establishes a direct connection between human preferences and RL based on the Bradley-Terry model and the
optimal policy in closed form:

$$ $\pi^{*}(a|x)\propto\pi_{\hbox{\scriptsize ref}}(a|x)\exp\left(\frac{1}{\beta}r (x,a)\right),$ (1) $$

where $r(x,a)$ is the reward in state $x$ with action $a,$ $\pi_{\hbox{\scriptsize ref}}$ is a reference policy and $\pi^{*}$ is the optimal policy. Based on the direction connection, the policy optimization can be formulated as a direct matching between human preference and the optimal policy with a log-likelihood loss function.
In a recent paper (Rafailov et al., ), it has been further shown that DPO solves a KL-divergence-constrained policy optimization problem for the deterministic token-level MDP for LLM, where the next state is deterministic given the current state and action.
For general RL problems with parameterized policies, equation 1 does not hold, and it is often hard if not impossible to obtain a “global” function like it that connects the optimal policy and the reward (hence human feedback).

This paper exploits the “local” relation between human feedback and policy optimization. In particular, given a policy $\pi_{\bm{\theta}}$ and a perturbed version of the policy $\pi_{{\bm{\theta}}+v}$,
we use human feedback over the trajectories generated from both policies to inform the more preferred policy. Intuitively, if one trajectory is preferred over the other, the policy that generates this trajectory is likely to have a higher value. Then given a preference model such as the Bradley-Terry model, we can further estimate the value function differences of the two policies, $V(\pi_{{\bm{\theta}}+v})-V(\pi_{\bm{\theta}})$, using the population-level preference, where $V(\pi)$ is the value function associated with policy $\pi.$
Finally, the value difference can be used as an estimator of policy gradient, $\nabla_{{\bm{\theta}}}V(\pi_{{\bm{\theta}}})$, following the zeroth-order optimization approach (Nesterov and Spokoiny, ; Ghadimi and Lan, ) to improve the policy.

Based on this idea, this paper proposes two RLHF algorithms without reward inference: Zeroth-Order Policy Gradient (ZPG) and Zeroth-Order Block-Coordinate Policy Gradient (ZBCPG), both from Human Feedback.
ZBCPG differs from ZPG in its policy perturbation rule, which has lower computational complexity and allows parallel optimization since one can sample multiple perturbed policies to perform policy gradient and combine the estimated gradient. Under mild assumptions, both algorithms have the following rate of converge to a stationary point:

$$ ${\mathcal{O}}\left(\frac{Hd}{T}+\frac{d^{2}\sqrt{\log M}}{\sqrt{M}}+\frac{Hd \sqrt{d}}{\sqrt{N}}\right),$ $$

where $d$ is the dimension of policy network parameter ${\bm{\theta}},$ $H$ is the planning horizon, $T$ is the number of policy gradient steps, $N$ is the number of policy perturbations each step, and $M$ is the number of human queries for each pair of trajectories.

We remark that (Tang et al., ) proposes a similar approach towards utilizing human feedback and a zeroth-order gradient descent algorithm from ranking data. However, they assume an error-free ranking oracle over policies based on their value functions, which makes their problem a deterministic optimization problem and does not apply to trajectory preference data like in RLHF and DPO.
This paper studies RLHF with trajectory preferences and quantifies the impacts of stochastic trajectories and human preferences on the rate of convergence of RLHF without reward inference.

## 2 Related Work

In this section, we review recent developments of RLHF and zeroth-order optimization for both empirical and theoretical results.

Empirical Studies of RLDHF in LLMs.
DPO (Rafailov et al., ) and SLiC-HF (Zhao et al., ) have empirically shown it is possible to directly learn an RL policy from human preference. In DPO, the authors solve a KL-divergence-constrained reward maximization problem for a prompt response generation problem similar to the contextual bandit. The optimal policy for this problem has a closed-form expression, and the reward of each prompt-response pair can be computed knowing the optimal policy and the reference policy. The authors then minimize a log-likelihood loss by plugging the reward expression into the Bradley-Terry model to measure the alignment between the policy and the human preference without training a reward network. Rafailov et al. () extends this loss to token-level MDP on the condition that the MDP transition is deterministic, i.e., the next state is a concatenation between the current state and action. This limits the DPO loss minimization approach to LLM problems. In general MDPs with stochastic transition, the DPO loss cannot be computed following the derivation in (Rafailov et al., ). Azar et al. () extends DPO to a wider class of RL problems, even avoiding the notion of an underlying reward function. Instead of maximizing the reward in a KL-constrained problem like DPO, the authors proposed to optimize a general non-decreasing function of the ground-truth population-level preference probability. Other variants are also studied. Ethayarajh et al. ()
considers aligning policy with humans and designs loss from a prospect theory perspective, and Tang et al. () considers optimizing a general loss of the preference loss instead of the log-likelihood. Dong et al. () and Xiong et al. () proposed to obtain human feedback in an online fashion to mitigate the distribution-shift and over-parameterization phenomenon. Attempts to understand the theoretical performance of RLDHF algorithms such as DPO are made in (Azar et al., ), but the authors only showed the existence of optima of the loss function, without any policy optimality and sample complexity guarantees.

RLHF with Provable Sample Complexity. Two major approaches have been studied to learn the optimal policy from human preference data. The first is similar to the traditional RLHF paradigm such as PPO used in empirical studies which infers a reward function, or sometimes a utility function, and then trains an RL agent. This reward inference step is also called surrogate learning in the preference-based RL literature, i.e., see (Wirth et al., , Sec. 2.4). The second approach directly optimizes the policy from human preferences. Empirical algorithms for both approaches have been developed without theoretical guarantees for a few years. For example, reward function or utility function estimation followed by an RL policy search algorithm has been proposed and studied in (Schoenauer et al., ; Wirth et al., ; Christiano et al., ), while direct policy learning from humans through trajectory sampling also has been proposed in using a heuristic evolutionary algorithm (Busa-Fekete et al., ; Akrour et al., ), or from a Bayesian Markov chain Monte Carlo perspective (Wilson et al., ). However, it was not until recently that algorithms with provable theoretical guarantees are proposed. From the reward inference approach, Novoseller et al. () took a Bayesian perspective and maintains a posterior distribution over the reward function and the transition kernel, which is computationally costly.
Wang et al. () assumes the reward function can be linearly parameterized with known feature embedding and proposes a preference-to-reward interface (a reward model) using an online policy update and a baseline trajectory for comparison. The authors theoretically showed that for a general known preference model setting, RLHF is no harder than RL. A similar analysis framework is adopted in contemporary theoretical works, e.g., (Saha et al., ; Zhan et al., , ; Zhu et al., ; Kong and Yang, ; Wu and Sun, ), for both online, offline, and hybrid RL problems, where the algorithms first learn the linear parameter of the reward function and perform value-based RL on the learned reward function. The analysis first characterizes the error of the reward parameter using the concentration of the MLE estimator and then propagates this error to the value-based RL algorithm. Specifically, Saha et al. () considers the tabular RL setting and assumes a known feature embedding for each trajectory with a known transition kernel. Then, the agent is directed by RL to explore the feature direction where the uncertainty in the reward function is large. Wu and Sun () extends the scenario to linear MDPs with unknown transition and uses least square value iteration to solve the RL problem. Zhu et al. () extends the work (Saha et al., ) to the offline RL scenario where a pessimistic estimator of the reward parameter is used to combat the insufficient data coverage in offline settings. Zhan et al. () replaces the linear reward parameterization with a general function class under the realizability condition. This also enables them to solve the unknown preference model as long as it is in the known function class. Zhan et al. () and Kong and Yang () studies the hybrid RL problem with human preference, where they first use an exploratory policy from an optimal design perspective to improve the coverage of the offline dataset and to extract more information useful for reward inference. Then, the problem will be solved under the general RL framework. All papers above took a value-based approach in RL and Du et al. () analyzed natural policy gradient with reward inference. Direct policy learning from human preference has been less analyzed compared to reward inference approaches. In tabular MDPs, Xu et al. () and Zhang et al. () reduce the RL problem to a sequence of dueling bandit problems. However, the approach is only suitable for MDPs with finite state and action spaces. For general MDPs, Chen et al. () first uses function approximation for the mapping from trajectory pair to human preference, and learns the RL transition kernel from a least square estimator with this preference approximator. The optimal policy can then be learned using a dueling bandit approach. However, their results assume the true preference model and transition kernel is inside the known function class with small complexity, which is strong in real applications. RLHF has also been studied in other aspects. Li et al. () studies RL from human behavior dataset from a dynamic choice perspective.  Chakraborty et al. () formulated the reward inference and the policy optimization as a bilevel optimization problem, and Kausik et al. () studies RLHF with partially observed rewards and states. Zhu et al. () studies the overfitting issue in reward model training.

Zeroth-Order Optimization. The zeroth-order optimization problem has been studied in the convex and non-convex optimization literature for more than a decade (Ghadimi and Lan, ; Nesterov and Spokoiny, ), where the stochastic gradient descent algorithm with two-point gradient estimator is most widely used. The convergence rate in smooth functions is first studied in (Ghadimi and Lan, ) in both convex and non-convex settings. In the convex setting, the algorithm finds the optimal point while in the non-convex setting, the algorithm finds a stationary point. The rate of convergence for non-convex functions is improved in Nesterov and Spokoiny (). Variants of stochastic gradient descent such as variance reduction techniques (Liu et al., ) and ADMM (Liu et al., ; Gao et al., ) have also been studied in the zeroth-order literature. (Cai et al., ) extends the zeroth-order method to blocked coordinate descent for computational efficiency and Liu et al. () extends the method to analyze a signed version of SGD which is more memory efficient in federated settings since each element of the gradient takes only one bit. Recently, the zeroth-order optimization technique has been proposed in optimizing LLMs (Malladi et al., ; Zhang et al., ), but they only implement it in the procedure of policy optimization from the reward network to avoid the heavy memory burden in back-propagation. Our work is different in that we view human feedback as a natural source of zeroth-order information and apply the method directly from human preference.

## 3 Preliminaries

Episodic RL: We consider an episodic RL problem $\mathcal{M}=({\mathbb{S}},{\mathbb{A}},H,{\bm{P}},{\bm{\mu}}_{0})$, where ${\mathbb{S}}$ is the state space and ${\mathbb{A}}$ is the action space (both can be continuous), $H$ is the RL planning horizon, ${\bm{P}}=\{{\bm{P}}_{h}\}_{h=1}^{H}$ is the set of transition kernels, and ${\bm{\mu}}_{0}$ is the initial distribution. At the beginning of each episode, the agent will choose a policy $\pi$ represented by $H$ functions $\{\pi_{h}:{\mathbb{S}}\to\mathcal{P}({\mathbb{A}})\}_{h=1}^{H}$, where $\mathcal{P}({\mathbb{A}})$ denotes the set of all probability distributions over the action space. Then, an initial state $s_{1}$ is sampled from the initial distribution ${\bm{\mu}}_{0}$. At step $h$, the agent takes an action $a_{h}=\pi_{h}(s_{h})$ after observing state $s_{h}$. The environment then moves to the next state $s_{h+1}$ sampled from the distribution ${\bm{P}}_{h}(\cdot|s_{h},a_{h})$ without revealing any reward feedback. We use $\tau$ to denote a trajectory with planing horizon $H$, i.e., $\tau=\{(s_{h},a_{h})\}_{h=1}^{H}$.

Trajectory Reward: we assume the expected reward of each trajectory $\tau$ is a general function $r(\tau)$ which maps any trajectory to a value in $[0,H]$ (Zhang et al., ). Without loss of generality, we scale the average per-step reward into $[0,1]$. Note that this model captures a broadened class of RL problems including classic MDPs, convex MDPs (Zhang et al., ; Zahavy et al., ) and maximum entropy exploration (Hazan et al., ). For any given policy $\pi$, we can formulate the initial value function $V_{1}^{\pi}(s)$ as the expected reward of trajectories starting from $s$ with policy $\pi$:

$$ $\displaystyle V_{1}^{\pi}(s)=$ $\displaystyle\mathbb{E}_{\pi}\left[\left.r(\tau)\right|s_{1}=s\right]=\mathbb{ E}\left[\left.r(\tau)\right|s_{1}=s,\{a_{1},\cdots,a_{H}\}\sim\pi\right].$ $$

The goal of the RL problem is to find a policy to maximize $V(\pi)=\mathbb{E}_{s\sim{\bm{\mu}}_{0}}[V_{1}^{\pi}(s)]$.

Policy Parameterization: to address the large state space ${\mathbb{S}}$ and action space ${\mathbb{A}}$ in most RL problems, we assume access to a parameterized policy network $\mathsf{N}_{{\bm{\theta}}}:{\mathbb{S}}\times[H]\to\mathcal{P}({\mathbb{A}})$ which takes a state and a decision-making step as input, and then outputs the probability distribution of the next action. Here ${\bm{\theta}}\in{\mathbb{R}}^{d}$ is the policy network parameter vector. Each parameter ${\bm{\theta}}$ through the policy network will induce a policy which we slightly abuse the notation and use $\pi_{{\bm{\theta}}}$ to denote.

Human Feedback: The agent has access to human feedback that provides a preference based on the rewards of two trajectories. In each episode, the agent can choose two trajectories $\tau_{0}$ and $\tau_{1}$ to query human preference: one-bit feedback $o\in\{0,1\}$. We assume the preference $o$ is generated according to a known preference model where the probability of the outcome between two trajectories is determined by the difference in their rewards. Since the difference is not necessarily a value inside the unit interval, the preference model uses a *link* function $\sigma:{\mathbb{R}}\to[0,1]$ to map these differences of rewards to actual probabilities, i.e.,

$$ $\displaystyle{\mathbb{P}}(\tau_{1}\succ\tau_{0})=\sigma(r(\tau_{1})-r(\tau_{0} )),$ (2) $$

where $\tau_{1}\succ\tau_{0}$ is the event that the human feedback prefers $\tau_{1}$ over $\tau_{0}.$
The human feedback $o,$ therefore, is a random sample from a Bernoulli distribution with ${\mathbb{P}}(o=1)={\mathbb{P}}(\tau_{1}\succ\tau_{0})$.
The notion of link function comes from the dueling bandit literature to model preference with latent utility between arms, e.g. see Bengs et al. (, Section 3.2). This preference model has been used in dueling bandits (Bengs et al., ; Yue and Joachims, ; Kumagai, ; Ailon et al., ) as well as RLHF (Wang et al., ).
One can see that one specific link function $\sigma$ will define a specific preference model, i.e., replacing $\sigma$ with a logistic function, we recover the Bradley-Terry model (Bradley and Terry, ), which is commonly used in RLHF for both practical (Christiano et al., ; Ouyang et al., ; Rafailov et al., ) and theoretical works (Du et al., ; Zhan et al., , ).
The following assumption on the link function is standard in both dueling bandits (Bengs et al., ) and preference-based RL (Wang et al., ). One can easily verify that the Bradley-Terry model satisfies this assumption.

###### Assumption 1

The link function $\sigma(\cdot)$ in the preference model in equation 2 is bounded within $[0,1]$ and strictly monotonically increasing on $[-H,H]$ with $\sigma(0)=\frac{1}{2}$.

Problem Formulation: Our goal is to find policy network parameter ${\bm{\theta}}$ that maximizes the value function, i.e.,
$\max_{{\bm{\theta}}\in{\mathbb{R}}^{d}}V(\pi_{{\bm{\theta}}}).$

Notations: For a scalar $a$, we use $\mathrm{trim}[a|\Delta]$ to represent $\min\{\max\{a,\Delta\},1-\Delta\}$. For a vector ${\bm{v}}$, $\mathrm{trim}[{\bm{v}}|\Delta]$ represents the vector after applying the $\mathrm{trim}$ operator to each element respectively. Let ${\bm{e}}_{i}\in{\mathbb{R}}^{d}$ represent the unit vector with all zero elements but $1$ on the $i$-th coordinate.

###### Assumption 1

## 4 Zeroth-Order Policy Gradient Algorithms for RLHF

In this section, we propose two RLHF algorithms without reward inference, motivated by the relationship between human feedback and zeroth-order gradient. We first present ZPG, which is a stochastic gradient descent algorithm and then ZBCPG, which is a stochastic block-coordinate descent algorithm.

### 4.1 ZPG: Zeroth-Order Policy Gradient from Human Feedback

Figure: Algorithm 1 Zeroth-Order Policy Gradient from Human Feedback

Our first algorithm *Zeroth-Order Policy Gradient from Human Feedback* (ZPG) consists of the following five steps in each policy gradient iteration:

- •
From the current policy $\pi_{{\bm{\theta}}_{t}},$ it first obtained a perturbed policy $\pi_{{\bm{\theta}}_{t}+\mu{\bm{v}}_{t}}$ (line 2-3).
- •
Sample $N$ pairs of trajectories under the two policies $\pi_{{\bm{\theta}}_{t}}$ and $\pi_{{\bm{\theta}}_{t}+\mu{\bm{v}}_{t}}$ (lines 5-6).
- •
For each trajectory pair, say $(\tau_{n,1},\tau_{n,0})$, obtain $M$ independent human preferences (line 7) and estimate the probability that $\tau_{n,1}$ is preferred over $\tau_{n,0}$ (line 8), denoted by $p_{t,n}$.
- •
Use the $N$ estimates $\{p_{t,n}\}_{n}$ and link function $\sigma(\cdot)$ to estimate the gradient $\hat{{\bm{g}}}_{t}$ (line 9).
- •
Update the current policy to a new policy ${\bm{\theta}}_{t+1}$ using gradient ascent (line 10).

The pseudo-code is presented in Alg. 1. As we mentioned earlier, our approach uses human feedback in a way different from both the classic reward inference in RLHF and DPO. The reward inference uses human preferences to recover the global reward function and DPO relates human preferences to the optimal policy. We view the human feedback as local information that points to the direction of a more preferred policy, i.e., the policy gradient direction. The algorithm has two key components: (i) a value function difference estimator from human preference and (ii) a policy gradient estimator from value function difference.

Policy Gradient Approximation: At each iteration of the algorithm, it first samples a $d$ dimensional vector ${\bm{v}}_{t}$ from a unit sphere and then perturbs the policy network parameter ${\bm{\theta}}_{t}$ along the direction of this sampled vector. Then, it uses the inner for loop to construct an estimation of the value function difference between the original policy and the perturbed policy, i.e., $V(\pi_{{\bm{\theta}}_{t}+\mu{\bm{v}}_{t}})-V(\pi_{{\bm{\theta}}_{t}})$. We then plug it in the zeroth-order SGD algorithm proposed in (Ghadimi and Lan, ) to construct a zeroth-order approximate to the policy gradient, i.e.,

$$ $\displaystyle\nabla_{{\bm{\theta}}}V(\pi_{{\bm{\theta}}_{t}})\approx\mathbb{E} _{{\bm{v}}_{t}}\left[\frac{d}{\mu}\left(V(\pi_{{\bm{\theta}}_{t}+\mu{\bm{v}}_{ t}})-V(\pi_{{\bm{\theta}}_{t}})\right){\bm{v}}_{t}\right].$ $$

We remark that the random vector ${\bm{v}}_{t}$ for each iteration can also be drawn from a normal distribution (Nesterov and Spokoiny, ), but the unit sphere is more numerically stable.

Value Function Inference: The inner for loop of Alg. 1 aims to estimate the value function difference between the perturbed policy $\pi_{{\bm{\theta}}_{t}+\mu{\bm{v}}_{t}}$ and current policy $\pi_{{\bm{\theta}}_{t}}$. The algorithm samples multiple trajectory pairs with both policies and for each pair, it queries humans multiple times to obtain pairwise preferences $[o_{n,1},\cdots,o_{n,M}]$. It then uses the preferences to construct a robust estimator $p_{t,n}$ to approximate the probability of comparison ${\mathbb{P}}(\tau_{n,1}\succ\tau_{n,0})$, which is further converted to an estimate of the value function difference based on the preference model in equation 2 as follows:

$$ $\displaystyle V(\pi_{{\bm{\theta}}_{t}+\mu{\bm{v}}_{t}})-V(\pi_{{\bm{\theta}}_ {t}})\approx\sum_{n=1}^{N}\sigma^{-1}(p_{t,n})/N.$ (3) $$

Querying humans multiple times ensures an accurate estimation of the reward gap between two trajectories. The reward gap of two trajectories is a random sample of the value function difference so we sample multiple trajectories to ensure the average trajectory reward gap converges to the value function difference. To ensure finite variance after applying $\sigma^{-1}$ function, we trim $p_{t,n}$ with a small constant which can be set to $\min\{\sigma(-H),1-\sigma(H)\}$ in this case.

### 4.2 ZBCPG: Zeroth-Order Block-Coordinate Policy Gradient from Human Feedback

Figure: Algorithm 2 Zeroth-Order Block Coordinate Policy Gradient from Human Feedback

In high-dimensional optimization problems, it is usually memory and operation inefficient to approximate the full gradient and update all the parameters in the policy network at the same iteration step (Malladi et al., ; Zhang et al., ), which motivates parameter efficient fine-tuning (PEFT). The stochastic (block) coordinate descent approach naturally arises because of its ease of implementation, low memory requirements, and adaptability to distributed settings (Nesterov, ; Lu and Xiao, ). The same advantage also applies to RLHF when the number of parameters in the policy network is too large. Therefore, we propose a block coordinate version of ZPG, called *Zeroth-Order Block Coordinate Policy Gradient* (ZBCPG), which is summarized in Alg. 2. The key difference between ZBCPG and ZPG is the choice of the perturbation direction.

Zeroth-Order Block Coordinate Gradient Approximation: Instead of sampling from a sphere, which perturbs all parameters of the policy network, ZBCPG separates the sampling procedure into two simple parts: first sample a minibatch of coordinates and then sample a zero-centered Bernoulli random variable for each coordinate, which still results in a valid gradient estimator.

$$ $\displaystyle\nabla_{{\bm{\theta}}}V(\pi_{{\bm{\theta}}_{t}})\approx\mathbb{E} _{{\bm{i}}_{t},\bm{\lambda}_{t}}\left[\frac{d}{K\mu}\left(V(\pi_{{\bm{\theta}} _{t}+\mu{\bm{v}}_{t}})-V(\pi_{{\bm{\theta}}_{t}+\mu{\bm{v}}_{t}})\right){\bm{v }}_{t}\right].$ $$

The block-coordinate approach allows us to (i) perturb a subset of parameters at each iteration, e.g., a specific layer of the policy network for fine-turning, and (ii) have a parallel implementation where we have multiple gradient estimators $\hat{{\bm{g}}}_{t}$ when updating the policy. We will later show that both algorithms have similar provable convergence guarantees but the analysis of ZBCPG is more challenging due to the perturbation mechanism.

## 5 Theoretical Analysis: Rate of Convergence

In this section, we provide theoretical performance guarantees for both ZPG and ZBCPG. We first provide technical assumptions on the preference generation model, the policy network, and the value function landscape, which is necessary for deriving theoretical insights.

### 5.1 Assumptions

In order to infer the local reward difference from human preference probability through link function $\sigma(\cdot)$, we impose the following assumption which is satisfied by the Bradley-Terry model. A slightly weaker assumption is also adopted by Wang et al. () and justified as a minimal requirement to learn the optimal policy. We use $\Delta=\min\{\sigma(-H),1-\sigma(H)\}$ as the trim constant.

###### Assumption 2

The inverse link function $\sigma^{-1}(\cdot)$ is $L$-Lipchitz continuous on $[\Delta,1-\Delta]$.

We further require the landscape of the value function and the policy network to be “regular”, and impose the following assumption, which is a standard assumption used in nonconvex optimization literature (Liu et al., ; Bernstein et al., ; Reddi et al., ).

###### Assumption 3

The value function $V(\pi_{{\bm{\theta}}})$ for the policy network parameters ${\bm{\theta}}$ is $L$-smooth on ${\mathbb{R}}^{d}$.

Since a trajectory reward is bounded in $[0,H]$, $V(\pi_{{\bm{\theta}}^{*}})<\infty$, where ${\bm{\theta}}^{*}$ is the global optimal solution. For simplicity, we assume the same $L$ satisfies both assumptions above.

###### Assumption 2

###### Assumption 3

### 5.2 Convergence Rate and Sample Complexity

In this section, we present the theoretical guarantees for both ZPG and ZBCPG under all three assumptions above. We aim to learn an ${\epsilon}$-stationary policy, i.e., a policy $\pi_{{\bm{\theta}}}$ with $\|\nabla_{{\bm{\theta}}}V(\pi_{\bm{\theta}})\|_{2}^{2}\leq{\epsilon}$, and study the convergence rate and sample complexity of the value function gradient.

###### Theorem 1

Choose the perturbation distance and learning rate to be

$$ $\mu^{2}=\Theta\left(\max\left\{\frac{1}{\sqrt{M}},\frac{H}{\sqrt{dN}}\right\} \right),\quad\alpha=\Theta\left(\frac{1}{d}\right).$ $$

If $M=\Omega(D^{2})$ and we randomly pick ${\bm{\theta}}_{R}$ uniformly from the trajectory $\{{\bm{\theta}}_{0},{\bm{\theta}}_{1},\cdots,{\bm{\theta}}_{T-1}\}$, then the convergence rate of ZPG satisfies:

$$ $\displaystyle\mathbb{E}\left[\|\nabla_{{\bm{\theta}}}V(\pi_{{\bm{\theta}}_{R}} )\|_{2}^{2}\right]={\mathcal{O}}\left(\frac{Hd}{T}+\frac{d^{2}\sqrt{\log M}}{ \sqrt{M}}+\frac{Hd\sqrt{d}}{\sqrt{N}}\right).$ $$

###### Theorem 2

Choose the perturbation distance and learning rate to be

$$ $\mu^{2}=\Theta\left(\max\left\{\frac{1}{\sqrt{M}},\frac{H}{\sqrt{dN}}\right\} \right),\quad\alpha=\Theta\left(\frac{1}{d}\right).$ $$

If $M=\Omega(D^{2})$ and we randomly pick ${\bm{\theta}}_{R}$ uniformly from the trajectory $\{{\bm{\theta}}_{0},{\bm{\theta}}_{1},\cdots,{\bm{\theta}}_{T-1}\}$, then the convergence rate of ZBCPG satisfies:

$$ $\displaystyle\mathbb{E}\left[\|\nabla_{{\bm{\theta}}}V(\pi_{{\bm{\theta}}_{R}} )\|_{2}^{2}\right]={\mathcal{O}}\left(\frac{Hd}{T}+\frac{d^{2}\sqrt{\log M}}{ \sqrt{M}}+\frac{Hd\sqrt{d}}{\sqrt{N}}\right).$ $$

The complete proof of both theorems is presented in the appendix. Here we first provide insights into the choice of hyper-parameters and convergence rate results in both theorems, and then we discuss the challenges and technical novelties of our proof.

Insights behind the Convergence Rate: Both ZPG and ZBCPG have the same rate of convergence which consists of three components: the zeroth-order gradient descent rate, the preference estimation error, and the value function approximation error

$$ $\displaystyle\underbrace{\frac{Hd}{T}}_{\text{Zeroth-Order GD}}+\underbrace{ \frac{d^{2}\sqrt{\log M}}{\sqrt{M}}}_{\text{Preference Estimation}}+ \underbrace{\frac{Hd\sqrt{d}}{\sqrt{N}}.}_{\text{Value Function Approximation}}$ $$

The second represents the error that occurs when using multiple human preferences $[o_{n,1},\cdots,o_{n,M}]$ to approximate the population-level human preference probability for given two trajectories, i.e., ${\mathbb{P}}(\tau_{n,1}\succ\tau_{n,0})$. This error will further result in a bias term after being plugged into the inverse link function $\sigma^{-1}(\cdot)$ to construct an estimation of the value function difference. The third term comes from the variance of using multiple trajectory rewards to approximate the value function of a policy. The first term representing the error resulting from zeroth-order stochastic gradient descent or blocked coordinate descent, which matches the state-of-the-art analysis result ${\mathcal{O}}(d/T)$ for non-convex smooth function optimization (Nesterov and Spokoiny, ). Even though the final convergence rates are the same and we both use constant learning rates, how we choose the perturbation distance to obtain the rate differs from (Ghadimi and Lan, ). Specifically, they chose a small perturbation distance with $\mu^{2}={\mathcal{O}}(d/T)$ to make sure the zeroth order approximation error is of lower order. However, this choice will not work for us, because our gradient estimate is biased due to the non-linear nature of the link function in preference estimation. If we choose the perturbation distance $\mu$ to be too small, the preference estimation error will be amplified by $d/\mu$ due to the formula of zeroth-order approximation $\hat{{\bm{g}}}_{t}$. This phenomenon adds complication to our theoretical analysis. Our method is to use a moderate perturbation distance $\mu$. Moreover, this moderate perturbation distance also balances the preference estimation and the value function approximation errors.

Based on the two theorems above, we have the following corollary that characterizes the sample complexity of our proposed algorithms.

###### Corollary 1

To learn an ${\epsilon}$-stationary policy, the required number of human preference queries of ZPG and ZBCPG with proper hyper-parameters satisfies

$$ $\displaystyle TMN={\mathcal{O}}\left(\frac{d^{8}H^{3}}{{\epsilon}^{5}}\log \left(\frac{d}{{\epsilon}}\right)\right).$ $$

###### Theorem 1

###### Theorem 2

###### Corollary 1

### 5.3 Technical Challenges and Proof Novelties

In this section, we first overview the proof of zeroth-order stochastic gradient descent used in (Ghadimi and Lan, ; Nesterov and Spokoiny, ; Gao et al., ; Liu et al., )
from a Lyapunov drift optimization perspective. We then show the major technical difficulties in applying such a framework to analyze both ZPG and ZBCPG, i.e., the gradient estimator is biased due to stochastic human preference. Then, we demonstrate our novel analysis techniques to resolve them.

Classic Proof of Zeroth-Order Optimization: to illustrate the procedure of the analysis of zeroth order gradient estimate, we suppose we can query $V(\pi_{{\bm{\theta}}})$ for any ${\bm{\theta}}$. This procedure makes use of the randomized smoothing function $V_{\mu}({\bm{\theta}})$ (Ghadimi and Lan, ; Gao et al., ):

$$ $\displaystyle V_{\mu}(\pi_{{\bm{\theta}}})=\mathbb{E}_{{\bm{v}}^{\prime}}\left [V(\pi_{{\bm{\theta}}+\mu{\bm{v}}^{\prime}})\right],$ $$

where the random vector ${\bm{v}}^{\prime}$ follows a uniform distribution over the unit Euclidean ball. It is shown in (Gao et al., ) that the zeroth-order gradient estimator used in ZPG, constructed from sampling ${\bm{v}}_{t}$ uniformly over a sphere, is an unbiased estimator of the smoothing function gradient, i.e.,

$$ $\displaystyle\nabla_{{\bm{\theta}}}V_{\mu}(\pi_{{\bm{\theta}}})=\mathbb{E}_{{ \bm{v}}}\left[\frac{d}{\mu}\left(V(\pi_{{\bm{\theta}}+\mu{\bm{v}}})-V(\pi_{{ \bm{\theta}}_{t}})\right){\bm{v}}\right],$ $$

where ${\bm{v}}$ is sampled from a unit sphere. Clearly, the gradient of the smoothing function is not equal to the original value function, as well as the function it self, but it can be shown that they are close as long as $\mu$ is small (Liu et al., ):

$$ $\displaystyle|V_{\mu}(\pi_{{\bm{\theta}}})-V(\pi_{{\bm{\theta}}})|={\mathcal{O }}\left(\mu^{2}\right);\quad\|\nabla_{{\bm{\theta}}}V_{\mu}(\pi_{{\bm{\theta}} })-\nabla_{{\bm{\theta}}}V(\pi_{{\bm{\theta}}})\|_{2}={\mathcal{O}}\left(\mu d \right).$ (4) $$

The standard proof uses the randomized smoothing function $V_{\mu}(\pi_{{\bm{\theta}}})$ as the Lyapunov function and then bounds the drift given the stochastic gradient descent update rule when $\alpha=\Theta(1/d)$. Neglecting problem independent constants, we have:

$$ $\displaystyle V_{\mu}(\pi_{{\bm{\theta}}_{t}})-$ $\displaystyle V_{\mu}(\pi_{{\bm{\theta}}_{t+1}})$ $\displaystyle\leq$ $\displaystyle-\alpha\underbrace{\|\nabla_{{\bm{\theta}}}V_{\mu}(\pi_{{\bm{ \theta}}_{t}})\|_{2}^{2}}_{\mathsf{NegDrift}}+\alpha\underbrace{\langle\nabla_ {{\bm{\theta}}}V_{\mu}(\pi_{{\bm{\theta}}_{t}}),\nabla_{{\bm{\theta}}}V_{\mu}( \pi_{{\bm{\theta}}_{t}})-\hat{{\bm{g}}}_{t}}_{\text{$1$st Order: }\mathsf{ GradBias}}\rangle+\alpha^{2}\underbrace{\|\hat{{\bm{g}}}_{t}-\nabla_{{\bm{ \theta}}}V_{\mu}(\pi_{{\bm{\theta}}_{t}})\|_{2}^{2}}_{\text{2nd Order: } \mathsf{GradVar}\approx\mu^{2}d^{2}}.$ $$

Note the gradient estimator $\hat{{\bm{g}}}_{t}$ is unbiased and bounded, and the gradient of $V_{\mu}(\pi_{{\bm{\theta}}})$ is close to $V(\pi_{{\bm{\theta}}})$, taking a conditional expectation over the filtration before time $t$ will result in:

$$ $\displaystyle\mathbb{E}[V_{\mu}(\pi_{{\bm{\theta}}_{t}})|{\mathcal{F}}_{t}]-$ $\displaystyle\mathbb{E}[V_{\mu}(\pi_{{\bm{\theta}}_{t+1}})|{\mathcal{F}}_{t}]$ $\displaystyle\leq$ $\displaystyle-\alpha\|\nabla_{{\bm{\theta}}}V_{\mu}(\pi_{{\bm{\theta}}_{t}})\| _{2}^{2}+\alpha\langle\nabla_{{\bm{\theta}}}V_{\mu}(\pi_{{\bm{\theta}}_{t}}), \mathbb{E}[\nabla_{{\bm{\theta}}}V_{\mu}(\pi_{{\bm{\theta}}_{t}})-\hat{{\bm{g} }}_{t}]\rangle+\alpha^{2}\mu^{2}d^{2}$ $\displaystyle\leq$ $\displaystyle-\alpha\|\nabla_{{\bm{\theta}}}V(\pi_{{\bm{\theta}}_{t}})\|_{2}^{ 2}+\alpha\mu^{2}d^{2}+\alpha^{2}\mu^{2}d^{2},$ $$

where the last step uses equation 4 and the fact that the gradient is unbiased. Let us choose a small learning rate $\alpha=\Theta(1/d)$ and take an expectation with a telescoping sum to obtain:

$$ $\displaystyle\underbrace{\frac{\mathbb{E}[V_{\mu}(\pi_{{\bm{\theta}}_{0}})]- \mathbb{E}[V_{\mu}(\pi_{{\bm{\theta}}^{*}})]}{T}}_{{\mathcal{O}}(H/T)}\lesssim -\alpha\underbrace{\mathbb{E}\left[\frac{\sum_{t=1}^{T}\|\nabla_{{\bm{\theta}} }V(\pi_{{\bm{\theta}}_{t}})\|_{2}^{2}}{T}\right]}_{\mathsf{Target}}+\alpha\mu^ {2}d^{2}.$ $$

A little manipulation will lead to the following bound, which can be made small when $\mu\approx\sqrt{1/dT}$.

$$ $\displaystyle\mathsf{Target}={\mathcal{O}}\left(\frac{H}{T\alpha}+\mu^{2}d^{2} \right)={\mathcal{O}}\left(\frac{Hd}{T}+\mu^{2}d^{2}\right)={\mathcal{O}}\left (\frac{Hd}{T}\right).$ $$

Amplified Gradient Biases for ZPG: If we directly apply the steps above to ZPG, we immediately run into the issue that our gradient estimator $\hat{{\bm{g}}}_{t}$ in expectation is biased even compared to smoothing function gradient due to preference estimation. Moreover, the gradient variance on the second order term will also be larger since we used trajectory reward to estimate the value function. Through concentration inequalities, we will be able to obtain a bound on the error of using preference to estimate the value function difference as:

$$ $\displaystyle\left|\mathbb{E}\left[\sigma^{-1}(p_{t,n})\right]-\left(V(\pi_{{ \bm{\theta}}_{t}+\mu{\bm{v}}_{t}})-V(\pi_{{\bm{\theta}}_{t}})\right)\right| \leq\tilde{{\mathcal{O}}}\left(1/\sqrt{M}\right),$ $$

where $\tilde{{\mathcal{O}}}$ hides logarithmic terms. This bias term will be amplified by $d/\mu$ and then added to the gradient estimation bias in the first-order drift term if plugged into the analysis:

$$ $\displaystyle\mathbb{E}[V_{\mu}(\pi_{{\bm{\theta}}_{t}})|{\mathcal{F}}_{t}]- \mathbb{E}[V_{\mu}(\pi_{{\bm{\theta}}_{t+1}})|{\mathcal{F}}_{t}]\leq- \underbrace{\alpha\|\nabla_{{\bm{\theta}}}V(\pi_{{\bm{\theta}}_{t}})\|_{2}^{2} +\alpha\mu^{2}d^{2}}_{\text{Same Drift as Before}}+\alpha\underbrace{\frac{d\| \nabla_{{\bm{\theta}}}V_{\mu}(\pi_{{\bm{\theta}}_{t}})\|_{2}}{\mu\sqrt{M}}}_{ \text{Additional Bias}}.$ $$

Using the same perturbation distance as before, the additional bias will lead to an $\tilde{{\mathcal{O}}}(\sqrt{T/M})$ term in the final bound, which is small only when $M$ is much larger than $T$ and is much looser compared with ours. For example, letting $M=T^{2},$ the above bound is $\tilde{{\mathcal{O}}}(1/\sqrt{T})$ while ours is $\tilde{{\mathcal{O}}}(1/T).$

Our approach to avoid this term in the final result is to make use of the gradient value $\nabla_{{\bm{\theta}}}V(\pi_{{\bm{\theta}}_{t}})$ in the first-order term to cancel out the additional bias on certain occasions. Specifically, we divide the trajectory of ${\bm{\theta}}_{t}$ into two sets, one with a relatively large gradient and one with a relatively small gradient. For ${\bm{\theta}}_{t}$ with a large gradient, we use a part of the negative drift to cancel out the additional bias, since the negative drift is the square of the gradient $\nabla_{{\bm{\theta}}}V(\pi_{{\bm{\theta}}_{t}})$ which is even larger. For ${\bm{\theta}}_{t}$ with a small gradient, we know the bias term will be small and thus can provide a refined drift bound. Combining this analysis with a slightly larger perturbation distance $\mu$, we will be able to balance the additional bias with gradient variance to cancel out the $\tilde{{\mathcal{O}}}(\sqrt{T/M})$ term and obtain the final result.

Implicit Smoothing Function for ZBCPG: Due to the choice of blocked perturbation vector sampling procedure, it is difficult to obtain the exact analytical expression of the smoothing function $V_{\mu}(\pi_{{\bm{\theta}}})$ whose gradient is the expectation of gradient estimation $\hat{{\bm{g}}}_{t}$ for ZBCPG. This prohibits us from continuing to use $V_{\mu}(\pi_{{\bm{\theta}}})$ as the Lyapunov function, as it is hard to analyze the gradient bias and the variance without an explicit target format. However, if we rethink why we introduce the smoothed function in zeroth-order optimization, what we hope for is the gradient of the smoothed function will be unbiased to cancel out the first order positive drift. However, this is already not true in the analysis of ZPG since we have gradient estimation bias from human feedback, but it is small enough on average and we can control it. If the gradient difference between the smoothed function $V_{\mu}(\pi_{{\bm{\theta}}})$ and the vanilla value function $V(\pi_{{\bm{\theta}}})$ is smaller than this additional bias, then we can use the original value function $V(\pi_{{\bm{\theta}}})$ as the Lyapunov function at the cost of an additional bias besides preference estimation. Fortunately, this can be achieved through a carefully chosen perturbation distance $\mu$ to balance these two errors.

## 6 Conclusion

In this paper, we proposed two RLHF algorithms without reward inference based on zeroth-order policy gradient called ZPG and ZBCPG, which train the policy network directly from human preferences without a global reward function approximator. Both algorithms are shown to have a provable polynomial sample complexity to learn a stationary policy under mild conditions, which shows there exist provably efficient methods to solve RLHF problems in general MDPs without reward inference.

## Appendix A Proof Backbone for Theorems: Preference Estimation Error

In the following sections, we provide proofs for both our main theorems, i.e., Theorem. 1 and Theorem. 2 for ZPG (Algorithm. 1) and ZBCPG (Algorithm. 2) respectively. Both algorithms follow the Lyapunov drift analysis framework where the key to the final result relies on a tight bound on the drift. At each iteration $t$ and for each trajectory pair, both algorithms estimate the population-level human preference probability $p_{t,n}$ and use it with the preference model in equation 2 to estimate the reward difference between trajectories, which is later averaged to estimate the value function difference as in equation 3. Before presenting the proofs of the theorems, we first characterize the error incurred by preference estimation in the following Lemma:

###### Lemma 1 (Concentration of Reward Difference)

Suppose $\Delta=\min\{\sigma(-H),1-\sigma(H)\}$, for any trajectory pairs $(\tau_{n,0},\tau_{n,1})$ that is queried from $M$ human evaluators. we have:

$$ $\displaystyle\mathbb{E}\left|\sigma^{-1}(p_{t,n})-[r(\tau_{n,1})-r(\tau_{n,0}) ]\right|\leq L\sqrt{\frac{2\log M}{M}}+\frac{2H}{M^{2}};$ (5) $\displaystyle\mathbb{E}\left|\sigma^{-1}(p_{t,n})-[r(\tau_{n,1})-r(\tau_{n,0}) ]\right|^{2}\leq\frac{2L^{2}\log M}{M}+\frac{4H^{2}}{M^{2}}.$ (6) $$

This lemma shows that our reward difference estimation from human preference is accurate as long as the number of human evaluators $M$ is large. The proof of this lemma is provided in Sec. A.1

###### Lemma 1 (Concentration of Reward Difference)

### A.1 Proof of Lemma. 1

Consider any iteration $t$ and any trajectory pairs $(\tau_{n,0},\tau_{n,1})$ generated by the original and perturbed policy in both ZPG and ZBCPG. We first bound the estimation error of population-level human preference ${\mathbb{P}}(\tau_{n,1}\succ\tau_{n,0})$ given any arbitrary trajectory pair in the following Lemma. 2. To formalize, let $\bar{o}_{n}$ be the empirical average over the human feedback $o_{n,m}$, i.e.,

$$ $\bar{o}_{n}=\sum_{m=1}^{M}\frac{o_{n,m}}{M}.$ $$

Naturally, $\mathbb{E}[\bar{o}_{n}]=\mathbb{E}[o_{n,m}]={\mathbb{P}}(\tau_{n,1}\succ\tau_{
n,0})$. And we need to characterize this estimation error first before we prove Lemma. 1.

###### Lemma 2 (Concentration of Preference Probability)

For any $\delta<\frac{1}{4}$ and suppose $\Delta=\min\{\sigma(-H),1-\sigma(H)\}$, for any trajectory pairs $(\tau_{n,0},\tau_{n,1})$ that is queried from $M$ human evaluators, with probability at least $1-\delta$, we have:

$$ $\displaystyle\left|p_{t,n}-{\mathbb{P}}(\tau_{n,1}\succ\tau_{n,0})\right|= \left|\mathrm{trim}\left[\left.\bar{o}_{n}\right|\Delta\right]-{\mathbb{P}}( \tau_{n,1}\succ\tau_{n,0})\right|\leq\sqrt{\frac{\log\frac{1}{\delta}}{M}},$ $$

where $o_{n,m}$ is the feedback for the $m$-th human evaluator for this trajectory pair.

Proof.
First, we notice that for two trajectories $\tau_{n,1}$ and $\tau_{n,0}$, the reward difference of the two trajectories is bounded, i.e., $|r(\tau_{n,1})-r(\tau_{n,0})|\leq H$, which implies the population-level preference probability ${\mathbb{P}}(\tau_{n,1}\succ\tau_{n,0})$ is also bounded, i.e.,

$$ ${\mathbb{P}}(\tau_{n,1}\succ\tau_{n,0})\in[\sigma(-H),\sigma(H)]\subset[\Delta ,1-\Delta].$ $$

Note that $\bar{o}_{n}$ may not be within $[\Delta,1-\Delta]$ due to the finite number of human evaluators. Overall, we may have the following three cases:

- 1.
$\bar{o}_{n}\in[\Delta,1-\Delta]$: we have $|\mathrm{trim}[\bar{o}_{n}|\Delta]-{\mathbb{P}}(\tau_{n,1}\succ\tau_{n,0})|=|
\bar{o}_{n}-\mathbb{E}[\bar{o}_{n}]|$.
- 2.
$\bar{o}_{n}>1-\Delta\geq{\mathbb{P}}(\tau_{n,1}\succ\tau_{n,0})$: we have
$|\mathrm{trim}[\bar{o}_{n}|\Delta]-{\mathbb{P}}(\tau_{n,1}\succ\tau_{n,0})|=1-
\Delta-{\mathbb{P}}(\tau_{n,1}\succ\tau_{n,0})\leq|\bar{o}_{n}-\mathbb{E}[\bar
{o}_{n}]|.$
- 3.
$\bar{o}_{n}<\Delta\leq{\mathbb{P}}(\tau_{n,1}\succ\tau_{n,0})$: we have
$|\mathrm{trim}[\bar{o}_{n}|\Delta]-{\mathbb{P}}(\tau_{n,1}\succ\tau_{n,0})|={
\mathbb{P}}(\tau_{n,1}\succ\tau_{n,0})-\Delta\leq|\bar{o}_{n}-\mathbb{E}[\bar{
o}_{n}]|.$

To summarize, we have $|\mathrm{trim}[\bar{o}_{n}|\Delta]-{\mathbb{P}}(\tau_{n,1}\succ\tau_{n,0})|
\leq|\bar{o}_{n}-\mathbb{E}[\bar{o}_{n}]|$. According to Hoeffding’s inequality for Bernoulli random variable, we have:

$$ $\displaystyle{\mathbb{P}}\left(|\mathrm{trim}[\bar{o}_{n}|\Delta]-{\mathbb{P}} (\tau_{n,1}\succ\tau_{n,0})|>\sqrt{\frac{\log\frac{1}{\delta}}{M}}\right)\leq$ $\displaystyle{\mathbb{P}}\left(|\bar{o}_{n}-\mathbb{E}[\bar{o}_{n}]|>\sqrt{ \frac{\log\frac{1}{\delta}}{M}}\right)$ $\displaystyle\leq$ $\displaystyle\exp\left(-2M\frac{\log\frac{1}{\delta}}{M}\right)$ $\displaystyle\leq$ $\displaystyle\delta,$ $$

which concludes the proof.$\hfill\blacksquare$

Next, we are ready to bound the error between the reward difference estimator after plugging in the preference probability estimator $p_{t,n}$ to the inverse link function $\sigma^{-1}$ in Lemma. 1. We first prove equation 5 and then prove equation 6. Let ${\mathcal{E}}_{n}$ be the concentration event that the event in Lemma. 2 holds. By Lemma. 2, when the concentration event does not hold, we can bound the term in the expectation of the left-hand side as:

$$ $\displaystyle\left|\sigma^{-1}(p_{t,n})-[r(\tau_{n,1})-r(\tau_{n,0})]\right| \leq 2H.$ $$

When the concentration event holds, we first notice that $r(\tau_{1})-r(\tau_{0})=\sigma^{-1}({\mathbb{P}}(\tau_{n,1}\succ\tau_{n,0}))$. By definition, both $p_{t,n}$ and ${\mathbb{P}}(\tau_{n,1}\succ\tau_{n,0})$ belongs to the interval $[\Delta,1-\Delta]$. This allows us to use assumption 2 and we have:

$$ $\displaystyle\left|\sigma^{-1}(p_{t,n})-[r(\tau_{n,1})-r(\tau_{n,0})]\right|=$ $\displaystyle\left|\sigma^{-1}(p_{t,n})-\sigma^{-1}({\mathbb{P}}(\tau_{n,1} \succ\tau_{n,0}))]\right|$ $\displaystyle\leq$ $\displaystyle L\left|p_{t,n})-{\mathbb{P}}(\tau_{n,1}\succ\tau_{n,0}))\right|$ $\displaystyle\leq$ $\displaystyle L\sqrt{\frac{\log\frac{1}{\delta}}{M}},$ $$

where the last inequality uses Lemma. 2. Combining both cases and let $\delta=1/M^{2}$, we have:

$$ $\displaystyle\mathbb{E}\left|\sigma^{-1}(p_{t,n})-[r(\tau_{n,1})-r(\tau_{n,0}) ]\right|\leq$ $\displaystyle{\mathbb{P}}({\mathcal{E}}_{n}^{\complement})L\sqrt{\frac{\log \frac{1}{\delta}}{M}}+{\mathbb{P}}({\mathcal{E}}_{n})2H\leq L\sqrt{\frac{2\log M }{M}}+\frac{2H}{M^{2}},$ $$

which concludes the proof of the first inequality. For the second inequality, we apply a similar procedure. Suppose the concentration event ${\mathcal{E}}_{n}$ does not hold, then we can bound the term as:

$$ $\displaystyle\left|\sigma^{-1}(p_{t,n})-[r(\tau_{n,1})-r(\tau_{n,0})]\right|^{ 2}\leq 4H^{2}.$ $$

When the concentration holds, we also employ the continuity of the inverse link function as:

$$ $\displaystyle\left|\sigma^{-1}(p_{t,n})-[r(\tau_{n,1})-r(\tau_{n,0})]\right|^{ 2}\leq\left(L\sqrt{\frac{\log\frac{1}{\delta}}{M}}\right)^{2}=\frac{L^{2}\log \frac{1}{\delta}}{M},$ $$

Combining both cases and let $\delta=1/M^{2}$, we have:

$$ $\displaystyle\mathbb{E}\left|\sigma^{-1}(p_{t,n})-[r(\tau_{n,1})-r(\tau_{n,0}) ]\right|^{2}\leq$ $\displaystyle{\mathbb{P}}({\mathcal{E}}_{n}^{\complement})\frac{2L^{2}\log M}{ M}+{\mathbb{P}}({\mathcal{E}}_{n})4H^{2}\leq\frac{2L^{2}\log M}{M}+\frac{4H^{2 }}{M^{2}},$ $$

which concludes the proof of both inequalities.

###### Lemma 2 (Concentration of Preference Probability)

## Appendix B Proof of Theorem. 1

Recall that we choose the smoothed value function $V_{\mu}(\pi_{{\bm{\theta}}})$ as the Lyapunov function, i.e.,

$$ $\displaystyle V_{\mu}(\pi_{{\bm{\theta}}})=\mathbb{E}_{{\bm{v}}^{\prime}}\left [V(\pi_{{\bm{\theta}}+\mu{\bm{v}}^{\prime}})\right],$ $$

where the vector ${\bm{v}}^{\prime}$ is sampled from a $d$-dimensional uniform distribution over a unit ball. We first provide properties of the smoothed function, which is proved in Liu et al. (, Lemma. 1).

###### Lemma 3

Suppose ${\bm{v}}$ is sampled from a uniform distribution over a unit sphere and ${\bm{v}}^{\prime}$ is sampled from a uniform distribution over a unit ball both in $d$-dimensional space and Assumption. 3 holds. Then the smoothed value function $V_{\mu}(\pi_{{\bm{\theta}}})$ defined above satisfies:

- 1.
$V_{\mu}(\pi_{{\bm{\theta}}})$ is $L$-smooth and satisfies:
$\displaystyle\nabla_{{\bm{\theta}}}V_{\mu}(\pi_{{\bm{\theta}}})=\mathbb{E}_{{
\bm{v}}}\left[\frac{d}{\mu}\left(V(\pi_{{\bm{\theta}}+\mu{\bm{v}}})-V(\pi_{{
\bm{\theta}}_{t}+\mu{\bm{v}}})\right){\bm{v}}\right].$
(7)
- 2.
For any ${\bm{\theta}}\in{\mathbb{R}}^{d}$, the function value difference satisfies:
$\displaystyle\left|V_{\mu}(\pi_{{\bm{\theta}}})-V(\pi_{{\bm{\theta}}})\right|
\leq\frac{L\mu^{2}}{2}.$
(8)
- 3.
For any ${\bm{\theta}}\in{\mathbb{R}}^{d}$, the gradient difference satisfies:
$\displaystyle\left\|\nabla_{{\bm{\theta}}}V_{\mu}(\pi_{{\bm{\theta}}})-\nabla_
{{\bm{\theta}}}V(\pi_{{\bm{\theta}}})\right\|_{2}\leq\frac{\mu Ld}{2}.$
(9)
- 4.
For any ${\bm{\theta}}\in{\mathbb{R}}^{d}$, the gradient noise satisfies:
$\displaystyle\mathbb{E}_{{\bm{v}}}\left[\left\|\frac{d}{\mu}\left(V(\pi_{{\bm{
\theta}}+\mu{\bm{v}}})-V(\pi_{{\bm{\theta}}})\right){\bm{v}}\right\|_{2}^{2}
\right]\leq 2d\left\|\nabla_{{\bm{\theta}}}V(\pi_{{\bm{\theta}}})\right\|_{2}^
{2}+\frac{\mu^{2}L^{2}d^{2}}{2}.$
(10)

Now, we are ready to prove Theorem. 1. We choose $V_{\mu}(\pi_{{\bm{\theta}}})$ to be the Lyapunov function, where $\bm{v}$ is sampled from a unit ball. We first analyze its drift, from the smoothness of $V_{\mu}(\pi_{{\bm{\theta}}})$ by Lemma. 3, we have the following upper bound:

$$ $\displaystyle V_{\mu}(\pi_{{\bm{\theta}}_{t}})-V_{\mu}(\pi_{{\bm{\theta}}_{t+1 }})\leq$ $\displaystyle\langle-\nabla_{{\bm{\theta}}}V_{\mu}(\pi_{{\bm{\theta}}_{t}}),{ \bm{\theta}}_{t+1}-{\bm{\theta}}_{t}\rangle+\frac{L}{2}\|{\bm{\theta}}_{t+1}-{ \bm{\theta}}_{t}\|_{2}^{2}$ $\displaystyle=$ $\displaystyle-\alpha\langle\nabla_{{\bm{\theta}}}V_{\mu}(\pi_{{\bm{\theta}}_{t }}),\hat{{\bm{g}}}_{t}\rangle+\frac{L\alpha^{2}}{2}\|\hat{{\bm{g}}}_{t}\|_{2}^ {2}$ $\displaystyle=$ $\displaystyle-\alpha\|\nabla_{{\bm{\theta}}}V_{\mu}(\pi_{{\bm{\theta}}_{t}})\| _{2}^{2}+\alpha\langle\nabla_{{\bm{\theta}}}V_{\mu}(\pi_{{\bm{\theta}}_{t}}), \nabla_{{\bm{\theta}}}V_{\mu}(\pi_{{\bm{\theta}}_{t}})-\hat{{\bm{g}}}_{t} \rangle+\frac{L\alpha^{2}}{2}\|\hat{{\bm{g}}}_{t}\|_{2}^{2}.$ $$

We bound the three terms above one by one, the first term can be bounded using equation 7 from Lemma. 3. We first have:

$$ $\displaystyle\|\nabla_{{\bm{\theta}}}V(\pi_{{\bm{\theta}}_{t}})\|_{2}^{2}=$ $\displaystyle\|\nabla_{{\bm{\theta}}}V(\pi_{{\bm{\theta}}_{t}})-\nabla_{{\bm{ \theta}}}V_{\mu}(\pi_{{\bm{\theta}}_{t}})+\nabla_{{\bm{\theta}}}V_{\mu}(\pi_{{ \bm{\theta}}_{t}})\|_{2}^{2}$ $\displaystyle\leq$ $\displaystyle 2\|\nabla_{{\bm{\theta}}}V_{\mu}(\pi_{{\bm{\theta}}_{t}})-\nabla _{{\bm{\theta}}}V(\pi_{{\bm{\theta}}_{t}})\|_{2}^{2}+2\|\nabla_{{\bm{\theta}}} V_{\mu}(\pi_{{\bm{\theta}}_{t}})\|_{2}^{2}$ $\displaystyle\leq$ $\displaystyle 2\|\nabla_{{\bm{\theta}}}V_{\mu}(\pi_{{\bm{\theta}}_{t}})\|_{2}^ {2}+\frac{\mu^{2}L^{2}d^{2}}{2},$ $$

where the first inequality uses $(a+b)^{2}\leq 2a^{2}+2b^{2}$ and the second inequality uses equation 9. This implies:

$$ $\displaystyle\|\nabla_{{\bm{\theta}}}V_{\mu}(\pi_{{\bm{\theta}}_{t}})\|_{2}^{2 }\geq\frac{1}{2}\|\nabla_{{\bm{\theta}}}V(\pi_{{\bm{\theta}}_{t}})\|_{2}^{2}- \frac{\mu^{2}L^{2}d^{2}}{4}.$ $$

And we have a bound on the negative drift term as:

$$ $\displaystyle-\alpha\|\nabla_{{\bm{\theta}}}V_{\mu}(\pi_{{\bm{\theta}}_{t}})\| _{2}^{2}\leq-\frac{\alpha}{2}\|\nabla_{{\bm{\theta}}}V(\pi_{{\bm{\theta}}_{t}} )\|_{2}^{2}+\frac{\alpha\mu^{2}L^{2}d^{2}}{4}.$ $$

We take a conditional expectation of the drift over the natural filtration ${\mathcal{F}}_{t}$ of time $t$ and obtain:

$$ $\displaystyle\mathbb{E}\left[V_{\mu}(\pi_{{\bm{\theta}}_{t}})-V_{\mu}(\pi_{{ \bm{\theta}}_{t+1}})|{\mathcal{F}}_{t}\right]\leq$ $\displaystyle-\frac{\alpha}{2}\|\nabla_{{\bm{\theta}}}V(\pi_{{\bm{\theta}}_{t} })\|_{2}^{2}+\frac{\alpha\mu^{2}L^{2}d^{2}}{4}+\frac{L\alpha^{2}}{2} \underbrace{\mathbb{E}\left[\left.\|\hat{{\bm{g}}}_{t}\|_{2}^{2}\right|{ \mathcal{F}}_{t}\right]}_{\mathsf{Var}_{t}}$ (11) $\displaystyle+\alpha\underbrace{\langle\nabla_{{\bm{\theta}}}V_{\mu}(\pi_{{\bm {\theta}}_{t}}),\nabla_{{\bm{\theta}}}V_{\mu}(\pi_{{\bm{\theta}}_{t}})-\mathbb {E}\left[\left.\hat{{\bm{g}}}_{t}\right|{\mathcal{F}}_{t}\right]\rangle}_{ \mathsf{Bias}_{t}}.$ $$

Then, we analyze the two positive drift terms $\mathsf{Bias}_{t}$ for the first-order gradient bias and $\mathsf{Var}_{t}$ for the gradient noise separately, and then construct a tight upper bound of the Lyapunov drift. The results are summarized in the following two lemmas where the proofs are deferred to Sec. B.1 and Sec. B.2:

###### Lemma 4

For ZPG and let $M\geq 8(H/L)^{\frac{2}{3}}$, conditioned on the information filtration ${\mathcal{F}}_{t}$ of any time $t$, the gradient bias can be upper bounded as follows:

$$ $\displaystyle\mathsf{Bias}_{t}=$ $\displaystyle\langle\nabla_{{\bm{\theta}}}V_{\mu}(\pi_{{\bm{\theta}}_{t}}), \nabla_{{\bm{\theta}}}V_{\mu}(\pi_{{\bm{\theta}}_{t}})-\mathbb{E}\left[\left. \hat{{\bm{g}}}_{t}\right|{\mathcal{F}}_{t}\right]\rangle$ $\displaystyle\leq$ $\displaystyle\frac{2dL}{\mu}\sqrt{\frac{\log M}{M}}\left\|\nabla_{{\bm{\theta} }}V(\pi_{{\bm{\theta}}_{t}})\right\|_{2}+d^{2}L^{2}\sqrt{\frac{\log M}{M}}.$ $$

###### Lemma 5

For ZPG and let $M\geq 4(H/L)^{2}$, conditioned on the information filtration ${\mathcal{F}}_{t}$ of any time $t$, the gradient bias can be upper bounded as follows:

$$ $\displaystyle\mathsf{Var}_{t}=\mathbb{E}\left[\left.\|\hat{{\bm{g}}}_{t}\|_{2} ^{2}\right|{\mathcal{F}}_{t}\right]\leq 6d\left\|\nabla_{{\bm{\theta}}}V(\pi_{ {\bm{\theta}}_{t}})\right\|_{2}^{2}+\frac{3\mu^{2}L^{2}d^{2}}{2}+\frac{9d^{2}L ^{2}\log M}{\mu^{2}M}+\frac{12d^{2}H^{2}}{\mu^{2}N}.$ $$

Now we use Lemma. 4 and Lemma. 5 and combine the drift bound in equation 11 and obtain:

$$ $\displaystyle\mathbb{E}\left[V_{\mu}(\pi_{{\bm{\theta}}_{t}})-V_{\mu}(\pi_{{ \bm{\theta}}_{t+1}})|{\mathcal{F}}_{t}\right]$ $\displaystyle\leq$ $\displaystyle-\frac{\alpha}{2}\|\nabla_{{\bm{\theta}}}V(\pi_{{\bm{\theta}}_{t} })\|_{2}^{2}+\frac{\alpha\mu^{2}L^{2}d^{2}}{4}+\alpha\mathsf{Bias}_{t}+\frac{L \alpha^{2}}{2}\mathsf{Var}_{t}$ $\displaystyle\leq$ $\displaystyle-\frac{\alpha}{2}\|\nabla_{{\bm{\theta}}}V(\pi_{{\bm{\theta}}_{t} })\|_{2}^{2}+\frac{\alpha\mu^{2}L^{2}d^{2}}{4}+\frac{2\alpha dL}{\mu}\sqrt{ \frac{\log M}{M}}\left\|\nabla_{{\bm{\theta}}}V(\pi_{{\bm{\theta}}_{t}})\right \|_{2}+\alpha d^{2}L^{2}\sqrt{\frac{\log M}{M}}$ $\displaystyle+3\alpha^{2}dL\left\|\nabla_{{\bm{\theta}}}V(\pi_{{\bm{\theta}}_{ t}})\right\|_{2}^{2}+{\alpha^{2}\mu^{2}L^{3}d^{2}}+\frac{5\alpha^{2}d^{2}L^{3} \log M}{\mu^{2}M}+\frac{6\alpha^{2}d^{2}H^{2}L}{\mu^{2}N}.$ $$

Let $\alpha\leq(12dL)^{-1}$, we can further simplify the drift bound as:

$$ $\displaystyle\mathbb{E}\left[V_{\mu}(\pi_{{\bm{\theta}}_{t}})-V_{\mu}(\pi_{{ \bm{\theta}}_{t+1}})|{\mathcal{F}}_{t}\right]$ $\displaystyle\leq$ $\displaystyle-\frac{\alpha}{2}\|\nabla_{{\bm{\theta}}}V(\pi_{{\bm{\theta}}_{t} })\|_{2}^{2}+\frac{\alpha\mu^{2}L^{2}d^{2}}{4}+\frac{2\alpha dL}{\mu}\sqrt{ \frac{\log M}{M}}\left\|\nabla_{{\bm{\theta}}}V_{\mu}(\pi_{{\bm{\theta}}_{t}}) \right\|_{2}$ $\displaystyle+\alpha d^{2}L^{2}\sqrt{\frac{\log M}{M}}+\frac{1}{4}\alpha\left \|\nabla_{{\bm{\theta}}}V(\pi_{{\bm{\theta}}_{t}})\right\|_{2}^{2}+{\alpha\mu^ {2}L^{2}d}+\frac{5\alpha^{2}d^{2}L^{3}\log M}{\mu^{2}M}+\frac{6\alpha^{2}d^{2} H^{2}L}{\mu^{2}N}$ $\displaystyle\leq$ $\displaystyle-\frac{\alpha}{4}\|\nabla_{{\bm{\theta}}}V(\pi_{{\bm{\theta}}_{t} })\|_{2}^{2}+\frac{\alpha\mu^{2}L^{2}d^{2}}{2}+\frac{2\alpha dL}{\mu}\sqrt{ \frac{\log M}{M}}\left\|\nabla_{{\bm{\theta}}}V_{\mu}(\pi_{{\bm{\theta}}_{t}}) \right\|_{2}+\alpha d^{2}L^{2}\sqrt{\frac{\log M}{M}}$ $\displaystyle+\frac{5\alpha^{2}d^{2}L^{3}\log M}{\mu^{2}M}+\frac{6\alpha^{2}d^ {2}H^{2}L}{\mu^{2}N},$ $$

where the last inequality merges both positive and negative drifts on the square of the gradient together and assumes $d\geq 4$. When $\left\|\nabla_{{\bm{\theta}}}V_{\mu}(\pi_{{\bm{\theta}}_{t}})\right\|_{2}$ is large, typically, when we have:

$$ $\displaystyle\left\|\nabla_{{\bm{\theta}}}V_{\mu}(\pi_{{\bm{\theta}}_{t}}) \right\|_{2}\geq\frac{16dL}{\mu}\sqrt{\frac{\log M}{M}},$ $$

we have the positive first-order drift regarding gradient norm is bounded by:

$$ $\displaystyle\frac{2\alpha dL}{\mu}\sqrt{\frac{\log M}{M}}\left\|\nabla_{{\bm{ \theta}}}V_{\mu}(\pi_{{\bm{\theta}}_{t}})\right\|_{2}\leq\frac{1}{8}\left\| \nabla_{{\bm{\theta}}}V_{\mu}(\pi_{{\bm{\theta}}_{t}})\right\|_{2},$ $$

and thus can be merged into the negative drift as follows:

$$ $\displaystyle\mathbb{E}\left[V_{\mu}(\pi_{{\bm{\theta}}_{t}})-V_{\mu}(\pi_{{ \bm{\theta}}_{t+1}})|{\mathcal{F}}_{t}\right]$ $\displaystyle\leq$ $\displaystyle-\frac{\alpha}{8}\|\nabla_{{\bm{\theta}}}V(\pi_{{\bm{\theta}}_{t} })\|_{2}^{2}+\frac{\alpha\mu^{2}L^{2}d^{2}}{2}+\alpha d^{2}L^{2}\sqrt{\frac{ \log M}{M}}+\frac{5\alpha^{2}d^{2}L^{3}\log M}{\mu^{2}M}+\frac{6\alpha^{2}d^{2 }H^{2}L}{\mu^{2}N}.$ $$

If on the other hand, the gradient is large, then we can upper bound the first-order drift regarding gradient norm in another way:

$$ $\displaystyle\frac{2\alpha dL}{\mu}\sqrt{\frac{\log M}{M}}\left\|\nabla_{{\bm{ \theta}}}V_{\mu}(\pi_{{\bm{\theta}}_{t}})\right\|_{2}\leq\frac{32\alpha d^{2}L ^{2}\log M}{\mu^{2}M}.$ $$

So in this case the total drift can be upper bounded as:

$$ $\displaystyle\mathbb{E}\left[V_{\mu}(\pi_{{\bm{\theta}}_{t}})-V_{\mu}(\pi_{{ \bm{\theta}}_{t+1}})|{\mathcal{F}}_{t}\right]$ $\displaystyle\leq$ $\displaystyle-\frac{\alpha}{4}\|\nabla_{{\bm{\theta}}}V(\pi_{{\bm{\theta}}_{t} })\|_{2}^{2}+\frac{\alpha\mu^{2}L^{2}d^{2}}{2}+\frac{32\alpha d^{2}L^{2}\log M }{\mu^{2}M}+\alpha d^{2}L^{2}\sqrt{\frac{\log M}{M}}$ $\displaystyle+\frac{5\alpha^{2}d^{2}L^{3}\log M}{\mu^{2}M}+\frac{6\alpha^{2}d^ {2}H^{2}L}{\mu^{2}N}$ $\displaystyle\leq$ $\displaystyle-\frac{\alpha}{4}\|\nabla_{{\bm{\theta}}}V(\pi_{{\bm{\theta}}_{t} })\|_{2}^{2}+\frac{\alpha\mu^{2}L^{2}d^{2}}{2}+\frac{33\alpha d^{2}L^{2}\log M }{\mu^{2}M}+\alpha d^{2}L^{2}\sqrt{\frac{\log M}{M}}+\frac{6\alpha^{2}d^{2}H^{ 2}L}{\mu^{2}N}.$ $$

The last inequality uses $\alpha\leq(12dL)^{-1}$ and $d\geq 4$. So combining both bounds and taking an expectation, we have:

$$ $\displaystyle\mathbb{E}\left[V_{\mu}(\pi_{{\bm{\theta}}_{t}})\right]-\mathbb{E }\left[V_{\mu}(\pi_{{\bm{\theta}}_{t+1}})\right]$ $\displaystyle\leq$ $\displaystyle-\frac{\alpha}{8}\mathbb{E}\left[\|\nabla_{{\bm{\theta}}}V(\pi_{{ \bm{\theta}}_{t}})\|_{2}^{2}\right]+\frac{33\alpha d^{2}L^{2}\log M}{\mu^{2}M} +\frac{\alpha\mu^{2}L^{2}d^{2}}{2}+\alpha d^{2}L^{2}\sqrt{\frac{\log M}{M}}+ \frac{6\alpha^{2}d^{2}H^{2}L}{\mu^{2}N}.$ $$

We then take a telescoping sum which results in:

$$ $\displaystyle\mathbb{E}\left[V_{\mu}(\pi_{{\bm{\theta}}_{0}})\right]-\mathbb{E }\left[V_{\mu}(\pi_{{\bm{\theta}}_{T}})\right]\leq-\frac{\alpha}{8}\sum_{t=0}^ {T-1}\mathbb{E}\left[\|\nabla_{{\bm{\theta}}}V(\pi_{{\bm{\theta}}_{t}})\|_{2}^ {2}\right]$ $\displaystyle+\left(\frac{33\alpha d^{2}L^{2}\log M}{\mu^{2}M}+\frac{\alpha\mu ^{2}L^{2}d^{2}}{2}+\alpha d^{2}L^{2}\sqrt{\frac{\log M}{M}}+\frac{6\alpha^{2}d ^{2}H^{2}L}{\mu^{2}N}\right)T$ $$

We choose $\mu$ to balance the terms inside the parenthesis. Specifically, let

$$ $\displaystyle\mu^{2}=\max\left\{9\sqrt{\frac{\log M}{M}},\frac{4H}{L\sqrt{dN}} \right\},\quad\alpha=\frac{1}{12dL}$ $$

then we have the following inequality on the positive drift:

$$ $\displaystyle\frac{\alpha\mu^{2}L^{2}d^{2}}{2}\geq\frac{33\alpha d^{2}L^{2} \log M}{\mu^{2}M},\quad\frac{\alpha\mu^{2}L^{2}d^{2}}{2}\geq\frac{6\alpha^{2}d ^{2}H^{2}L}{\mu^{2}N}.$ $$

So we have the final results in Theorem. 1 as:

$$ $\displaystyle\frac{1}{T}\sum_{t=0}^{T-1}\mathbb{E}\left[\|\nabla_{{\bm{\theta} }}V(\pi_{{\bm{\theta}}_{t}})\|_{2}^{2}\right]\leq$ $\displaystyle\frac{8\left(\mathbb{E}\left[V_{\mu}(\pi_{{\bm{\theta}}_{0}}) \right]-\mathbb{E}\left[V_{\mu}(\pi_{{\bm{\theta}}_{T}})\right]\right)}{T \alpha}+12\mu^{2}L^{2}d^{2}+8d^{2}L^{2}\sqrt{\frac{\log M}{M}}$ $\displaystyle\leq$ $\displaystyle\frac{8\left(\mathbb{E}\left[V(\pi_{{\bm{\theta}}_{0}})\right]- \mathbb{E}\left[V(\pi_{{\bm{\theta}}_{T}})\right]\right)}{T\alpha}+\frac{8\mu^ {2}L}{T\alpha}+12\mu^{2}L^{2}d^{2}+8d^{2}L^{2}\sqrt{\frac{\log M}{M}}$ $\displaystyle=$ $\displaystyle{\mathcal{O}}\left(\frac{HLd}{T}+\frac{d^{2}L^{2}\sqrt{\log M}}{ \sqrt{M}}+\frac{HLd\sqrt{d}}{\sqrt{N}}\right).$ $$

###### Lemma 3

###### Lemma 4

###### Lemma 5

### B.1 Proof of Lemma. 4

We analyze the first-order gradient bias term $\mathsf{Bias}_{t}$ in the drift of equation 11. Notice that conditioned over ${\mathcal{F}}_{t}$, the randomness only comes from sampling the perturbation direction, sampling trajectories, and obtaining human feedback. By equation 7 and the definition of $\hat{{\bm{g}}}_{t}$, we have:

$$ $\displaystyle\mathbb{E}\left[\nabla_{{\bm{\theta}}}V_{\mu}(\pi_{{\bm{\theta}}_ {t}})-\left.\hat{{\bm{g}}}_{t}\right|{\mathcal{F}}_{t}\right]$ $\displaystyle=$ $\displaystyle\mathbb{E}\left[\left.\frac{d\left(V(\pi_{{\bm{\theta}}_{t}+\mu{ \bm{v}}_{t}})-V(\pi_{{\bm{\theta}}_{t}})\right)}{\mu}{\bm{v}}_{t}\right|{ \mathcal{F}}_{t}\right]-\mathbb{E}\left[\left.\frac{d}{\mu}\frac{\sum_{n=1}^{N }\sigma^{-1}(p_{t,n})}{N}{\bm{v}}_{t}\right|{\mathcal{F}}_{t}\right].$ $$

Since each trajectory pair $(\tau_{n,0},\tau_{n,1})$ is generated independently from other trajectories, we have:

$$ $\displaystyle\mathbb{E}\left[\left.\frac{d}{\mu}\frac{\sum_{n=1}^{N}\sigma^{-1 }(p_{t,n})}{N}{\bm{v}}_{t}\right|{\mathcal{F}}_{t}\right]=$ $\displaystyle\frac{d}{\mu}\mathbb{E}\left[\left.\mathbb{E}\left[\left.\frac{ \sum_{n=1}^{N}\sigma^{-1}(p_{t,n})}{N}\right|{\bm{v}}_{t}\right]{\bm{v}}_{t} \right|{\mathcal{F}}_{t}\right]$ $\displaystyle=$ $\displaystyle\frac{d}{\mu}\mathbb{E}\left[\left.\mathbb{E}\left[\left.\sigma^{ -1}(p_{t,n})\right|{\bm{v}}_{t}\right]{\bm{v}}_{t}\right|{\mathcal{F}}_{t}\right]$ $\displaystyle=$ $\displaystyle\frac{d}{\mu}\mathbb{E}\left[\left.\mathbb{E}\left[\left.\left(r( \tau_{n,1})-r(\tau_{n,0})\right)\right|{\bm{v}}_{t}\right]{\bm{v}}_{t}\right|{ \mathcal{F}}_{t}\right]$ $\displaystyle-\frac{d}{\mu}\mathbb{E}\left[\left.\mathbb{E}\left[\left.\left( \sigma^{-1}(p_{t,n})-[r(\tau_{n,1})-r(\tau_{n,0})]\right)\right|{\bm{v}}_{t} \right]{\bm{v}}_{t}\right|{\mathcal{F}}_{t}\right],$ $$

where the first equality uses law of total expectation. Substitute it back into the bias, we have:

$$ $\displaystyle\mathbb{E}\left[\nabla_{{\bm{\theta}}}V_{\mu}(\pi_{{\bm{\theta}}_ {t}})-\left.\hat{{\bm{g}}}_{t}\right|{\mathcal{F}}_{t}\right]=$ $\displaystyle\frac{d}{\mu}\mathbb{E}\left[\left.\mathbb{E}\left[\left.\left(V( \pi_{{\bm{\theta}}_{t}+\mu{\bm{v}}_{t}})-V(\pi_{{\bm{\theta}}_{t}})-r(\tau_{n, 1})+r(\tau_{n,0})\right)\right|{\bm{v}}_{t}\right]{\bm{v}}_{t}\right|{\mathcal {F}}_{t}\right]$ $\displaystyle+\frac{d}{\mu}\mathbb{E}\left[\left.\mathbb{E}\left[\left.\left( \sigma^{-1}(p_{t,n})-[r(\tau_{n,1})-r(\tau_{n,0})]\right)\right|{\bm{v}}_{t} \right]{\bm{v}}_{t}\right|{\mathcal{F}}_{t}\right],$ $$

Notice that in the inner expectation of the first term, the randomness comes from sampling trajectories given both policies $\pi_{{\bm{\theta}}_{t}+\mu{\bm{v}}_{t}}$ and $\pi_{{\bm{\theta}}_{t}}$, we have:

$$ $\displaystyle\mathbb{E}\left[\left(V(\pi_{{\bm{\theta}}_{t}+\mu{\bm{v}}_{t}})- V(\pi_{{\bm{\theta}}_{t}})-r(\tau_{n,1})+r(\tau_{n,0})\right)|{\bm{v}}_{t}\right]$ $\displaystyle=$ $\displaystyle V(\pi_{{\bm{\theta}}_{t}+\mu{\bm{v}}_{t}})-\mathbb{E}\left[r( \tau_{n,1})|\tau_{n,1}\sim\pi_{{\bm{\theta}}_{t}+\mu{\bm{v}}_{t}}\right]+ \mathbb{E}\left[r(\tau_{n,0})|\tau_{n,0}\sim\pi_{{\bm{\theta}}_{t}}\right]-V( \pi_{{\bm{\theta}}_{t}})$ $\displaystyle=$ $\displaystyle 0.$ $$

The last equality is due to the definition of the value function and the fact that $\tau_{n,1}$ and $\tau_{n,0}$ are generated by the perturbed policy and the original policy independently. Then, the bias drift only comes from the preference estimation error and we will be able to plug it back and have:

$$ $\displaystyle\mathsf{Bias}_{t}=$ $\displaystyle\langle\nabla_{{\bm{\theta}}}V_{\mu}(\pi_{{\bm{\theta}}_{t}}), \nabla_{{\bm{\theta}}}V_{\mu}(\pi_{{\bm{\theta}}_{t}})-\mathbb{E}\left[\left. \hat{{\bm{g}}}_{t}\right|{\mathcal{F}}_{t}\right]\rangle$ $\displaystyle=$ $\displaystyle\frac{d}{\mu}\mathbb{E}\left[\left(\sigma^{-1}(p_{t,n})-[r(\tau_{ n,1})-r(\tau_{n,0})]\right)\langle\nabla_{{\bm{\theta}}}V_{\mu}(\pi_{{\bm{ \theta}}_{t}}),{\bm{v}}_{t}\rangle|{\mathcal{F}}_{t}\right]$ $\displaystyle\leq$ $\displaystyle\frac{d}{\mu}\left\|\nabla_{{\bm{\theta}}}V_{\mu}(\pi_{{\bm{ \theta}}_{t}})\right\|_{2}\mathbb{E}\left[\left.\mathbb{E}\left[\left.\left| \sigma^{-1}(p_{t,n})-[r(\tau_{n,1})-r(\tau_{n,0})]\right|\right|\tau_{n,1}, \tau_{n,0}\right]\right|{\mathcal{F}}_{t}\right]$ $\displaystyle\leq$ $\displaystyle\frac{d}{\mu}\left\|\nabla_{{\bm{\theta}}}V_{\mu}(\pi_{{\bm{ \theta}}_{t}})\right\|_{2}\left(L\sqrt{\frac{2\log M}{M}}+\frac{2H}{M^{2}}\right)$ $\displaystyle\leq$ $\displaystyle\frac{2dL}{\mu}\left\|\nabla_{{\bm{\theta}}}V_{\mu}(\pi_{{\bm{ \theta}}_{t}})\right\|_{2}\sqrt{\frac{\log M}{M}}$ $\displaystyle\leq$ $\displaystyle\frac{2dL}{\mu}\sqrt{\frac{\log M}{M}}\left\|\nabla_{{\bm{\theta} }}V(\pi_{{\bm{\theta}}_{t}})\right\|_{2}+d^{2}L^{2}\sqrt{\frac{\log M}{M}}$ $$

where the first inequality uses Cauchy-Schwarz inequality and the second inequality uses Lemma. 1. The last inequality is obtained by choosing $M\geq 8(H/L)^{\frac{2}{3}}$.

### B.2 Proof of Lemma. 5

We aim for the variance term $\mathsf{Var}_{t}$ in the Lyapunov drift in equation 11. We first have upper bound variance as follows:

$$ $\displaystyle\mathsf{Var}_{t}=$ $\displaystyle\mathbb{E}\left[\left.\left\|\frac{d}{\mu}\frac{\sum_{n=1}^{N} \sigma^{-1}(p_{t,n})}{N}{\bm{v}}_{t}\right\|_{2}^{2}\right|{\mathcal{F}}_{t}\right]$ $\displaystyle\leq$ $\displaystyle 3\underbrace{\mathbb{E}\left[\left.\left\|\frac{d\sum_{n=1}^{N} \left(\sigma^{-1}(p_{t,n})-[r(\tau_{n,1})-r(\tau_{n,0})]\right)}{\mu N}{\bm{v} }_{t}\right\|_{2}^{2}\right|{\mathcal{F}}_{t}\right]}_{\mathsf{Var}_{t,1}}$ $\displaystyle+3\underbrace{\mathbb{E}\left[\left.\left\|\frac{d}{\mu}\left( \frac{\sum_{n=1}^{N}\left(r(\tau_{n,1})-r(\tau_{n,0})\right)}{N}-\left(V(\pi_{ {\bm{\theta}}_{t}+\mu{\bm{v}}_{t}})-V(\pi_{{\bm{\theta}}_{t}})\right)\right){ \bm{v}}_{t}\right\|_{2}^{2}\right|{\mathcal{F}}_{t}\right]}_{\mathsf{Var}_{t,2}}$ $\displaystyle+3\underbrace{\mathbb{E}\left[\left.\left\|\frac{d}{\mu}\left(V( \pi_{{\bm{\theta}}_{t}+\mu{\bm{v}}_{t}})-V(\pi_{{\bm{\theta}}_{t}})\right){\bm {v}}_{t}\right\|_{2}^{2}\right|{\mathcal{F}}_{t}\right]}_{\mathsf{Var}_{t,3}}.$ $$

The first term comes from the human preference estimation error which can be bounded using equation 6 from Lemma. 1 as follows:

$$ $\displaystyle\mathsf{Var}_{t,1}=$ $\displaystyle\mathbb{E}\left[\left.\left\|\frac{d\sum_{n=1}^{N}\left(\sigma^{- 1}(p_{t,n})-[r(\tau_{n,1})-r(\tau_{n,0})]\right)}{\mu N}{\bm{v}}_{t}\right\|_{ 2}^{2}\right|{\mathcal{F}}_{t}\right]$ $\displaystyle=$ $\displaystyle\frac{d^{2}}{\mu^{2}N^{2}}\mathbb{E}\left[\left|\sum_{n=1}^{N} \left(\sigma^{-1}(p_{t,n})-[r(\tau_{n,1})-r(\tau_{n,0})]\right)\right|^{2}\right]$ $\displaystyle\leq$ $\displaystyle\frac{d^{2}}{\mu^{2}N}\sum_{n=1}^{N}\mathbb{E}\left[\left|\sigma^ {-1}(p_{t,n})-[r(\tau_{n,1})-r(\tau_{n,0})]\right|^{2}\right]$ $\displaystyle\leq$ $\displaystyle\frac{d^{2}}{\mu^{2}}\left(\frac{2L^{2}\log M}{M}+\frac{4H^{2}}{M ^{2}}\right)$ $\displaystyle\leq$ $\displaystyle\frac{3d^{2}L^{2}\log M}{\mu^{2}M},$ $$

where the first inequality uses Cauchy-Schwarz inequality, and the second inequality uses Lemma. 1. The final inequality is true by choosing $M\geq 4(H/L)^{2}$. The second term comes from using the empirical average reward to estimate the value function similar to REINFORCE. So we have:

$$ $\displaystyle\mathsf{Var}_{t,2}=$ $\displaystyle\mathbb{E}\left[\left.\left\|\frac{d}{\mu}\left(\frac{\sum_{n=1}^ {N}\left(r(\tau_{n,1})-r(\tau_{n,0})\right)}{N}-\left(V(\pi_{{\bm{\theta}}_{t} +\mu{\bm{v}}_{t}})-V(\pi_{{\bm{\theta}}_{t}})\right)\right){\bm{v}}_{t}\right \|_{2}^{2}\right|{\mathcal{F}}_{t}\right]$ $\displaystyle=$ $\displaystyle\frac{d^{2}}{\mu^{2}N^{2}}\mathbb{E}\left[\left.\left|\sum_{n=1}^ {N}\left(\underbrace{\left(r(\tau_{n,1})-r(\tau_{n,0})\right)-\left(V(\pi_{{ \bm{\theta}}_{t}+\mu{\bm{v}}_{t}})-V(\pi_{{\bm{\theta}}_{t}})\right)}_{\mathsf {E}_{t,n}}\right)\right|_{2}^{2}\|{\bm{v}}_{t}\|_{2}^{2}\right|{\mathcal{F}}_{ t}\right]$ $\displaystyle=$ $\displaystyle\frac{d^{2}}{\mu^{2}N^{2}}\mathbb{E}\left[\left.\left|\sum_{n=1}^ {N}\mathsf{E}_{t,n}\right|_{2}^{2}\right|{\mathcal{F}}_{t}\right],$ $$

where the last equality is because ${\bm{v}}_{t}$ is sampled from a unit ball. We open up the square as:

$$ $\displaystyle\mathbb{E}\left[\left.\left|\sum_{n=1}^{N}\mathsf{E}_{t,n}\right| _{2}^{2}\right|{\mathcal{F}}_{t}\right]=$ $\displaystyle\sum_{n=1}^{N}\mathbb{E}\left[\left.\left|\mathsf{E}_{t,n}\right| _{2}^{2}\right|{\mathcal{F}}_{t}\right]+\sum_{i\neq j}\mathbb{E}\left[\left. \mathbb{E}[\mathsf{E}_{t,i}\mathsf{E}_{t,j}|{\bm{v}}_{t}]\right|{\mathcal{F}}_ {t}\right]$ $\displaystyle=$ $\displaystyle\sum_{n=1}^{N}\mathbb{E}\left[\left.\left|\mathsf{E}_{t,n}\right| _{2}^{2}\right|{\mathcal{F}}_{t}\right]+\sum_{i\neq j}\mathbb{E}\left[\left. \mathbb{E}[\mathsf{E}_{t,i}|{\bm{v}}_{t}]\right|{\mathcal{F}}_{t}\right] \mathbb{E}\left[\left.\mathbb{E}[\mathsf{E}_{t,j}|{\bm{v}}_{t}]\right|{ \mathcal{F}}_{t}\right]$ $\displaystyle=$ $\displaystyle\sum_{n=1}^{N}\mathbb{E}\left[\left.\left|\mathsf{E}_{t,n}\right| _{2}^{2}\right|{\mathcal{F}}_{t}\right].$ $$

where the second inequality uses the independence between trajectories generated at the same step, and the last equality is due to $\mathbb{E}[\left(r(\tau_{n,1})-r(\tau_{n,0})\right)-\left(V(\pi_{{\bm{\theta}}
_{t}+\mu{\bm{v}}_{t}})-V(\pi_{{\bm{\theta}}_{t}})\right)]=0$ for any fixed perturbation direction ${\bm{v}}_{t}$ from the definition of value function. So we have:

$$ $\displaystyle\mathsf{Var}_{t,2}=$ $\displaystyle\frac{d^{2}}{\mu^{2}N^{2}}\sum_{n=1}^{N}\mathbb{E}\left[\left. \left|\mathsf{E}_{t,n}\right|_{2}^{2}\right|{\mathcal{F}}_{t}\right]$ $\displaystyle=$ $\displaystyle\frac{d^{2}}{\mu^{2}N^{2}}\sum_{n=1}^{N}\mathbb{E}\left[\left. \left|\left(r(\tau_{n,1})-r(\tau_{n,0})\right)-\left(V(\pi_{{\bm{\theta}}_{t}+ \mu{\bm{v}}_{t}})-V(\pi_{{\bm{\theta}}_{t}})\right)\right|_{2}^{2}\right|{ \mathcal{F}}_{t}\right]$ $\displaystyle\leq$ $\displaystyle\frac{4d^{2}H^{2}}{\mu^{2}N},$ $$

where the last inequality uses the fact that both the difference of reward and the difference of value function are within $[-H,H]$. The last term to bound $\mathsf{Var}_{t}$ can be obtained from the property of the smoothed function in Lemma. 3 as:

$$ $\displaystyle\mathsf{Var}_{t,3}=\mathbb{E}\left[\left.\left\|\frac{d}{\mu} \left(V(\pi_{{\bm{\theta}}_{t}+\mu{\bm{v}}_{t}})-V(\pi_{{\bm{\theta}}_{t}}) \right){\bm{v}}_{t}\right\|_{2}^{2}\right|{\mathcal{F}}_{t}\right]\leq 2d\left \|\nabla_{{\bm{\theta}}}V(\pi_{{\bm{\theta}}_{t}})\right\|_{2}^{2}+\frac{\mu^{ 2}L^{2}d^{2}}{2}.$ $$

So combining three terms together, the variance drift can be bounded as:

$$ $\displaystyle\mathsf{Var}_{t}\leq 6d\left\|\nabla_{{\bm{\theta}}}V(\pi_{{\bm{ \theta}}_{t}})\right\|_{2}^{2}+\frac{3\mu^{2}L^{2}d^{2}}{2}+\frac{9d^{2}L^{2} \log M}{\mu^{2}M}+\frac{12d^{2}H^{2}}{\mu^{2}N}.$ $$

## Appendix C Proof of Theorem. 2

Due to the choice of the generation mechanism of the perturbation vector ${\bm{v}}_{t}$, we cannot construct an explicit expression for the smoothed value function $V_{\mu}(\pi_{{\bm{\theta}}})$ in this setting, whose gradient is somewhat "unbiased" if the correct reward function is known. In this case, we use the original value function as the Lyapunov function and perform drift analysis as follows:

$$ $\displaystyle V(\pi_{{\bm{\theta}}_{t}})-V(\pi_{{\bm{\theta}}_{t+1}})\leq$ $\displaystyle\langle-\nabla_{{\bm{\theta}}}V(\pi_{{\bm{\theta}}_{t}}),{\bm{ \theta}}_{t+1}-{\bm{\theta}}_{t}\rangle+\frac{L}{2}\|{\bm{\theta}}_{t+1}-{\bm{ \theta}}_{t}\|_{2}^{2}$ $\displaystyle=$ $\displaystyle-\alpha\langle\nabla V_{\mu}(\pi_{{\bm{\theta}}_{t}}),\hat{{\bm{g }}}_{t}\rangle+\frac{L\alpha^{2}}{2}\|\hat{{\bm{g}}}_{t}\|_{2}^{2}$ $\displaystyle=$ $\displaystyle-\alpha\|\nabla_{{\bm{\theta}}}V(\pi_{{\bm{\theta}}_{t}})\|_{2}^{ 2}+\alpha\langle\nabla_{{\bm{\theta}}}V(\pi_{{\bm{\theta}}_{t}}),\nabla_{{\bm{ \theta}}}V(\pi_{{\bm{\theta}}_{t}})-\hat{{\bm{g}}}_{t}\rangle+\frac{L\alpha^{2 }}{2}\|\hat{{\bm{g}}}_{t}\|_{2}^{2}.$ $$

We also take a conditional expectation of the drift over the natural filtration ${\mathcal{F}}_{t}$ of time $t$ and obtain:

$$ $\displaystyle\mathbb{E}\left[V(\pi_{{\bm{\theta}}_{t}})-V_{\mu}(\pi_{{\bm{ \theta}}_{t+1}})|{\mathcal{F}}_{t}\right]$ (12) $\displaystyle\leq$ $\displaystyle-\frac{\alpha}{2}\|\nabla_{{\bm{\theta}}}V(\pi_{{\bm{\theta}}_{t} })\|_{2}^{2}+\frac{L\alpha^{2}}{2}\underbrace{\mathbb{E}\left[\left.\|\hat{{ \bm{g}}}_{t}\|_{2}^{2}\right|{\mathcal{F}}_{t}\right]}_{\mathsf{Var}_{t}}+ \alpha\underbrace{\langle\nabla_{{\bm{\theta}}}V(\pi_{{\bm{\theta}}_{t}}), \nabla_{{\bm{\theta}}}V(\pi_{{\bm{\theta}}_{t}})-\mathbb{E}\left[\left.\hat{{ \bm{g}}}_{t}\right|{\mathcal{F}}_{t}\right]\rangle}_{\mathsf{Bias}_{t}}.$ $$

Then, we analyze the two positive drift terms $\mathsf{Bias}_{t}$ for the first-order gradient bias and $\mathsf{Var}_{t}$ for the gradient noise separately, and then construct a tight upper bound of the Lyapunov drift. The results are summarized in the following two lemmas where the proofs are deferred to Sec. C.1 and Sec. C.2:

###### Lemma 6

For ZBCPG and let $M\geq 8(H/L)^{\frac{2}{3}}$, conditioned on the information filtration ${\mathcal{F}}_{t}$ of any time $t$, the gradient bias can be upper bounded as follows:

$$ $\displaystyle\mathsf{Bias}_{t}=$ $\displaystyle\langle\nabla_{{\bm{\theta}}}V(\pi_{{\bm{\theta}}_{t}}),\nabla_{{ \bm{\theta}}}V(\pi_{{\bm{\theta}}_{t}})-\mathbb{E}\left[\left.\hat{{\bm{g}}}_{ t}\right|{\mathcal{F}}_{t}\right]\rangle\leq\left(\frac{\mu Ld}{2}+\frac{2dL}{ \mu}\sqrt{\frac{\log M}{M}}\right)\left\|\nabla_{{\bm{\theta}}}V_{\mu}(\pi_{{ \bm{\theta}}_{t}})\right\|_{2}.$ $$

###### Lemma 7

For ZBCPG and let $M\geq 4(H/L)^{2}$, conditioned on the information filtration ${\mathcal{F}}_{t}$ of any time $t$, the gradient bias can be upper bounded as follows:

$$ $\displaystyle\mathsf{Var}_{t}=\mathbb{E}\left[\left.\|\hat{{\bm{g}}}_{t}\|_{2} ^{2}\right|{\mathcal{F}}_{t}\right]\leq 6d\left\|\nabla_{{\bm{\theta}}}V(\pi_{ {\bm{\theta}}_{t}})\right\|_{2}^{2}+\frac{3\mu^{2}L^{2}d^{2}}{2}+\frac{9d^{2}L ^{2}\log M}{\mu^{2}M}+\frac{12d^{2}H^{2}}{\mu^{2}N}.$ $$

Now we use Lemma. 6 and Lemma. 7 and combine the drift bound in equation 12 and obtain:

$$ $\displaystyle\mathbb{E}\left[V(\pi_{{\bm{\theta}}_{t}})-V(\pi_{{\bm{\theta}}_{ t+1}})|{\mathcal{F}}_{t}\right]$ $\displaystyle\leq$ $\displaystyle-\frac{\alpha}{2}\|\nabla_{{\bm{\theta}}}V(\pi_{{\bm{\theta}}_{t} })\|_{2}^{2}+\alpha\mathsf{Bias}_{t}+\frac{L\alpha^{2}}{2}\mathsf{Var}_{t}$ $\displaystyle\leq$ $\displaystyle-\frac{\alpha}{2}\|\nabla_{{\bm{\theta}}}V(\pi_{{\bm{\theta}}_{t} })\|_{2}^{2}+\alpha\left(\frac{\mu Ld}{2}+\frac{2dL}{\mu}\sqrt{\frac{\log M}{M }}\right)\left\|\nabla_{{\bm{\theta}}}V(\pi_{{\bm{\theta}}_{t}})\right\|_{2}$ $\displaystyle+3\alpha^{2}dL\left\|\nabla_{{\bm{\theta}}}V(\pi_{{\bm{\theta}}_{ t}})\right\|_{2}^{2}+{\alpha^{2}\mu^{2}L^{3}d^{2}}+\frac{5\alpha^{2}d^{2}L^{3} \log M}{\mu^{2}M}+\frac{6\alpha^{2}d^{2}H^{2}L}{\mu^{2}N}.$ $$

Let $\alpha\leq(12dL)^{-1}$, we can further simplify the drift bound as:

$$ $\displaystyle\mathbb{E}\left[V(\pi_{{\bm{\theta}}_{t}})-V(\pi_{{\bm{\theta}}_{ t+1}})|{\mathcal{F}}_{t}\right]$ $\displaystyle\leq$ $\displaystyle-\frac{\alpha}{2}\|\nabla_{{\bm{\theta}}}V(\pi_{{\bm{\theta}}_{t} })\|_{2}^{2}+\alpha\left(\frac{\mu Ld}{2}+\frac{2dL}{\mu}\sqrt{\frac{\log M}{M }}\right)\left\|\nabla_{{\bm{\theta}}}V(\pi_{{\bm{\theta}}_{t}})\right\|_{2}$ $\displaystyle+\frac{1}{4}\alpha\left\|\nabla_{{\bm{\theta}}}V(\pi_{{\bm{\theta }}_{t}})\right\|_{2}^{2}+\alpha^{2}\mu^{2}L^{3}d^{2}+\frac{5\alpha^{2}d^{2}L^{ 3}\log M}{\mu^{2}M}+\frac{6\alpha^{2}d^{2}H^{2}L}{\mu^{2}N}$ $\displaystyle\leq$ $\displaystyle-\frac{\alpha}{4}\|\nabla_{{\bm{\theta}}}V(\pi_{{\bm{\theta}}_{t} })\|_{2}^{2}+\alpha\left(\frac{\mu Ld}{2}+\frac{2dL}{\mu}\sqrt{\frac{\log M}{M }}\right)\left\|\nabla_{{\bm{\theta}}}V(\pi_{{\bm{\theta}}_{t}})\right\|_{2}$ $\displaystyle+\alpha^{2}\mu^{2}L^{3}d^{2}+\frac{5\alpha^{2}d^{2}L^{3}\log M}{ \mu^{2}M}+\frac{6\alpha^{2}d^{2}H^{2}L}{\mu^{2}N},$ $$

where the last inequality merges both positive and negative drifts on the square of the gradient together and assumes $d\geq 4$. When $\left\|\nabla_{{\bm{\theta}}}V_{\mu}(\pi_{{\bm{\theta}}_{t}})\right\|_{2}$ is large, typically, when we have:

$$ $\displaystyle\left\|\nabla_{{\bm{\theta}}}V_{\mu}(\pi_{{\bm{\theta}}_{t}}) \right\|_{2}\geq 8\left(\frac{\mu Ld}{2}+\frac{2dL}{\mu}\sqrt{\frac{\log M}{M} }\right),$ $$

we have the positive first-order drift regarding gradient norm is bounded by:

$$ $\displaystyle\left(\frac{\mu Ld}{2}+\frac{2dL}{\mu}\sqrt{\frac{\log M}{M}} \right)\left\|\nabla_{{\bm{\theta}}}V_{\mu}(\pi_{{\bm{\theta}}_{t}})\right\|_{ 2}\leq\frac{1}{8}\left\|\nabla_{{\bm{\theta}}}V_{\mu}(\pi_{{\bm{\theta}}_{t}}) \right\|_{2},$ $$

and thus can be merged into the negative drift as follows:

$$ $\displaystyle\mathbb{E}\left[V(\pi_{{\bm{\theta}}_{t}})-V(\pi_{{\bm{\theta}}_{ t+1}})|{\mathcal{F}}_{t}\right]$ $\displaystyle\leq$ $\displaystyle-\frac{\alpha}{8}\|\nabla_{{\bm{\theta}}}V(\pi_{{\bm{\theta}}_{t} })\|_{2}^{2}+\alpha^{2}\mu^{2}L^{3}d^{2}+\frac{5\alpha^{2}d^{2}L^{3}\log M}{ \mu^{2}M}+\frac{6\alpha^{2}d^{2}H^{2}L}{\mu^{2}N}.$ $$

If on the other hand, the gradient is large, then we can upper bound the first-order drift regarding the gradient norm in another way:

$$ $\displaystyle\left(\frac{\mu Ld}{2}+\frac{2dL}{\mu}\sqrt{\frac{\log M}{M}} \right)\left\|\nabla_{{\bm{\theta}}}V_{\mu}(\pi_{{\bm{\theta}}_{t}})\right\|_{ 2}\leq$ $\displaystyle 8\left(\frac{\mu Ld}{2}+\frac{2dL}{\mu}\sqrt{\frac{\log M}{M}} \right)^{2}$ $\displaystyle\leq$ $\displaystyle 4\mu^{2}L^{2}d^{2}+\frac{64d^{2}L^{2}\log M}{\mu^{2}M}.$ $$

So in this case the total drift can be upper bounded as:

$$ $\displaystyle\mathbb{E}\left[V(\pi_{{\bm{\theta}}_{t}})-V(\pi_{{\bm{\theta}}_{ t+1}})|{\mathcal{F}}_{t}\right]$ $\displaystyle\leq$ $\displaystyle-\frac{\alpha}{4}\|\nabla_{{\bm{\theta}}}V(\pi_{{\bm{\theta}}_{t} })\|_{2}^{2}+4\alpha\mu^{2}L^{2}d^{2}+\alpha^{2}\mu^{2}L^{3}d^{2}+\frac{64 \alpha d^{2}L^{2}\log M}{\mu^{2}M}$ $\displaystyle+\frac{5\alpha^{2}d^{2}L^{3}\log M}{\mu^{2}M}+\frac{6\alpha^{2}d^ {2}H^{2}L}{\mu^{2}N}$ $\displaystyle\leq$ $\displaystyle-\frac{\alpha}{4}\|\nabla_{{\bm{\theta}}}V(\pi_{{\bm{\theta}}_{t} })\|_{2}^{2}+5\alpha\mu^{2}L^{2}d^{2}+\frac{64\alpha d^{2}L^{2}\log M}{\mu^{2} M}+\frac{5\alpha^{2}d^{2}L^{3}\log M}{\mu^{2}M}+\frac{6\alpha^{2}d^{2}H^{2}L}{ \mu^{2}N}.$ $$

The last inequality uses $\alpha\leq(12dL)^{-1}$ and $d\geq 4$. So combining both bounds and taking an expectation, we have:

$$ $\displaystyle\mathbb{E}\left[V(\pi_{{\bm{\theta}}_{t}})-V(\pi_{{\bm{\theta}}_{ t+1}})|{\mathcal{F}}_{t}\right]$ $\displaystyle\leq$ $\displaystyle-\frac{\alpha}{8}\mathbb{E}\left[\|\nabla_{{\bm{\theta}}}V(\pi_{{ \bm{\theta}}_{t}})\|_{2}^{2}\right]+5\alpha\mu^{2}L^{2}d^{2}+\frac{5\alpha^{2} d^{2}L^{3}\log M}{\mu^{2}M}+\frac{64\alpha d^{2}L^{2}\log M}{\mu^{2}M}+\frac{6 \alpha^{2}d^{2}H^{2}L}{\mu^{2}N}$ $\displaystyle\leq$ $\displaystyle-\frac{\alpha}{8}\mathbb{E}\left[\|\nabla_{{\bm{\theta}}}V(\pi_{{ \bm{\theta}}_{t}})\|_{2}^{2}\right]+5\alpha\mu^{2}L^{2}d^{2}+\frac{65\alpha d^ {2}L^{2}\log M}{\mu^{2}M}+\frac{6\alpha^{2}d^{2}H^{2}L}{\mu^{2}N},$ $$

where we use $\alpha\leq(12dL)^{-1}$ again the in the last inequality. We then take a telescoping sum which results in the following:

$$ $\displaystyle\mathbb{E}\left[V_{\mu}(\pi_{{\bm{\theta}}_{0}})\right]-\mathbb{E }\left[V_{\mu}(\pi_{{\bm{\theta}}_{T}})\right]$ $\displaystyle\leq$ $\displaystyle-\frac{\alpha}{8}\sum_{t=0}^{T-1}\mathbb{E}\left[\|\nabla_{{\bm{ \theta}}}V(\pi_{{\bm{\theta}}_{t}})\|_{2}^{2}\right]+\left(5\alpha\mu^{2}L^{2} d^{2}+\frac{65\alpha d^{2}L^{2}\log M}{\mu^{2}M}+\frac{6\alpha^{2}d^{2}H^{2}L} {\mu^{2}N}\right)T$ $$

We choose $\mu$ to balance the terms inside the parenthesis. Specifically, let

$$ $\displaystyle\mu^{2}=\max\left\{4\sqrt{\frac{\log M}{M}},\frac{H}{3L\sqrt{dN}} \right\},\quad\alpha=\frac{1}{12dL}$ $$

then we have the following inequality on the positive drift:

$$ $\displaystyle 5\alpha\mu^{2}L^{2}d^{2}\geq\frac{65\alpha d^{2}L^{2}\log M}{\mu ^{2}M},\quad 5\alpha\mu^{2}L^{2}d^{2}\geq\frac{6\alpha^{2}d^{2}H^{2}L}{\mu^{2} N}.$ $$

So we have the final results in Theorem. 2 as:

$$ $\displaystyle\frac{1}{T}\sum_{t=0}^{T-1}\mathbb{E}\left[\|\nabla_{{\bm{\theta} }}V(\pi_{{\bm{\theta}}_{t}})\|_{2}^{2}\right]\leq$ $\displaystyle\frac{8\left(\mathbb{E}\left[V(\pi_{{\bm{\theta}}_{0}})\right]- \mathbb{E}\left[V(\pi_{{\bm{\theta}}_{T}})\right]\right)}{T\alpha}+120\mu^{2}L ^{2}d^{2}$ $\displaystyle=$ $\displaystyle{\mathcal{O}}\left(\frac{HLd}{T}+\frac{d^{2}L^{2}\sqrt{\log M}}{ \sqrt{M}}+\frac{HLd\sqrt{d}}{\sqrt{N}}\right).$ $$

###### Lemma 6

###### Lemma 7

### C.1 Proof of Lemma. 6

We analyze the first-order gradient bias term $\mathsf{Bias}_{t}$ in the drift of equation 12. Notice that conditioned over ${\mathcal{F}}_{t}$, the randomness only comes from sampling the perturbation coordinate set ${\bm{i}}_{t}$, the perturbation direction $\bm{\lambda}_{t}$, sampling trajectories, and obtaining human feedback. By equation 7 and the definition of $\hat{{\bm{g}}}_{t}$, we have:

$$ $\displaystyle\nabla_{{\bm{\theta}}}V(\pi_{{\bm{\theta}}_{t}})-\mathbb{E}\left[ \left.\hat{{\bm{g}}}_{t}\right|{\mathcal{F}}_{t}\right]$ $\displaystyle=$ $\displaystyle\nabla_{{\bm{\theta}}}V(\pi_{{\bm{\theta}}_{t}})-\mathbb{E}\left[ \left.\mathbb{E}\left[\left.\frac{d}{\mu}\frac{\sum_{n=1}^{N}\sigma^{-1}(p_{t, n})}{N}\right|{\bm{v}}_{t}\right]{\bm{v}}_{t}\right|{\mathcal{F}}_{t}\right]$ $\displaystyle=$ $\displaystyle\nabla_{{\bm{\theta}}}V(\pi_{{\bm{\theta}}_{t}})-\frac{d}{\mu} \mathbb{E}\left[\left.\mathbb{E}\left[\left.\sigma^{-1}(p_{t,n})\right|{\bm{v} }_{t}\right]{\bm{v}}_{t}\right|{\mathcal{F}}_{t}\right]$ $\displaystyle=$ $\displaystyle\underbrace{\nabla_{{\bm{\theta}}}V(\pi_{{\bm{\theta}}_{t}})- \mathbb{E}\left[\left.\frac{d}{\mu}\left(V(\pi_{{\bm{\theta}}_{t}+\mu{\bm{v}}_ {t}})-V(\pi_{{\bm{\theta}}_{t}})\right){\bm{v}}_{t}\right|{\mathcal{F}}_{t} \right]}_{\mathsf{Bias_{t,1}}}$ $\displaystyle+\frac{d}{\mu}\mathbb{E}\left[\left.\underbrace{\left[\left(V(\pi _{{\bm{\theta}}_{t}+\mu{\bm{v}}_{t}})-V(\pi_{{\bm{\theta}}_{t}})\right)- \mathbb{E}\left[\left.r(\tau_{n,1})-r(\tau_{n,0})\right|{\bm{v}}_{t}\right] \right]}_{=0}{\bm{v}}_{t}\right|{\mathcal{F}}_{t}\right]$ $\displaystyle+\underbrace{\frac{d}{\mu}\mathbb{E}\left[\left.\mathbb{E}\left[ \left.\left(\sigma^{-1}(p_{t,n})-[r(\tau_{n,1})-r(\tau_{n,0})]\right)\right| \tau_{n,1},\tau_{n,0}\right]{\bm{v}}_{t}\right|{\mathcal{F}}_{t}\right]}_{ \mathsf{Bias}_{t,2}},$ $$

where the second inequality uses the fact that conditioned on ${\bm{v}}_{t}$, each trajectory pair $(\tau_{n,1},\tau_{n,0})$ is independently generated from policies $(\pi_{{\bm{\theta}}_{t}+\mu{\bm{v}}_{t}},\pi_{{\bm{\theta}}_{t}})$. The last inequality is due to the fact that conditioned on the policy $(\pi_{{\bm{\theta}}_{t}+\mu{\bm{v}}_{t}},\pi_{{\bm{\theta}}_{t}})$, the expectation of each reward trajectory is the value function of the policy since $(\tau_{n,1},\tau_{n,0})$ is independently generated from policies $(\pi_{{\bm{\theta}}_{t}+\mu{\bm{v}}_{t}},\pi_{{\bm{\theta}}_{t}})$. Therefore, the $\mathsf{Bias}_{t}$ term is written as follows:

$$ $\displaystyle\mathsf{Bias_{t}}=\langle\nabla_{{\bm{\theta}}}V(\pi_{{\bm{\theta }}_{t}}),\mathsf{Bias}_{t,1}\rangle+\langle\nabla_{{\bm{\theta}}}V(\pi_{{\bm{ \theta}}_{t}}),\mathsf{Bias}_{t,2}\rangle.$ $$

We first analyze the second term which comes from preference estimation. Similar to the proof of ZPG, we have:

$$ $\displaystyle\langle\nabla_{{\bm{\theta}}}V(\pi_{{\bm{\theta}}_{t}}),\mathsf{ Bias}_{t,2}\rangle$ $\displaystyle=$ $\displaystyle\frac{d}{\mu}\mathbb{E}\left[\left.\mathbb{E}\left[\left.\left( \sigma^{-1}(p_{t,n})-[r(\tau_{n,1})-r(\tau_{n,0})]\right)\right|\tau_{n,1}, \tau_{n,0}\right]\langle\nabla_{{\bm{\theta}}}V(\pi_{{\bm{\theta}}_{t}}),{\bm{ v}}_{t}\rangle\right|{\mathcal{F}}_{t}\right]$ $\displaystyle\leq$ $\displaystyle\frac{d}{\mu}\|\nabla_{{\bm{\theta}}}V(\pi_{{\bm{\theta}}_{t}})\| _{2}\mathbb{E}\left[\left.\mathbb{E}\left[\left.\left|\sigma^{-1}(p_{t,n})- \left[r(\tau_{n,1})-r(\tau_{n,0})\right]\right|\right|\tau_{n,1},\tau_{n,0} \right]\right|{\mathcal{F}}_{t}\right]$ $\displaystyle\leq$ $\displaystyle\frac{d}{\mu}\|\nabla_{{\bm{\theta}}}V(\pi_{{\bm{\theta}}_{t}})\| _{2}\left(L\sqrt{\frac{2\log M}{M}}+\frac{2H}{M^{2}}\right)$ $\displaystyle\leq$ $\displaystyle\frac{2dL}{\mu}\sqrt{\frac{\log M}{M}}\left\|\nabla_{{\bm{\theta} }}V_{\mu}(\pi_{{\bm{\theta}}_{t}})\right\|_{2},$ $$

where the first inequality uses Cauchy-Schwarz inequality and $\|{\bm{v}}_{t}\|_{2}=1$ and the second inequality uses Lemma. 1. The last inequality is obtained by choosing $M\geq 8(H/L)^{\frac{2}{3}}$. Then, we need to deal with the first-term inner product. We first make the following claim:

###### Lemma 8

For any iteration $t$, the following is true:

$$ $\displaystyle\frac{1}{d}\nabla_{{\bm{\theta}}}V(\pi_{{\bm{\theta}}_{t}})= \mathbb{E}_{{\bm{i}}_{t},\bm{\lambda}_{t}}\left[\langle\nabla_{{\bm{\theta}}}V (\pi_{{\bm{\theta}}_{t}}),{\bm{v}}_{t}\rangle{\bm{v}}_{t}\right]$ $$

where the subscript indicates the randomness only comes from ${\bm{i}}_{t}$ and $\bm{\lambda}_{t}$.

Proof. To prove this equality, we start from the right-hand side:

$$ $\displaystyle\mathbb{E}_{{\bm{i}}_{t},\bm{\lambda}_{t}}\left[\langle\nabla_{{ \bm{\theta}}}V(\pi_{{\bm{\theta}}_{t}}),{\bm{v}}_{t}\rangle{\bm{v}}_{t}\right]=$ $\displaystyle\frac{1}{K}\mathbb{E}_{{\bm{i}}_{t},\bm{\lambda}_{t}}\left[\left \langle\nabla_{{\bm{\theta}}}V(\pi_{{\bm{\theta}}_{t}}),\sum_{j=1}^{K}\lambda_ {i_{t,j}}{\bm{e}}_{i_{t,j}}\right\rangle\sum_{l=1}^{K}\lambda_{i_{t,l}}{\bm{e} }_{i_{t,l}}\right]$ $\displaystyle=$ $\displaystyle\frac{1}{K}\mathbb{E}_{{\bm{i}}_{t},\bm{\lambda}_{t}}\left[\sum_{ j=1}^{K}\sum_{l=1}^{K}\left\langle\nabla_{{\bm{\theta}}}V(\pi_{{\bm{\theta}}_{ t}}),\lambda_{i_{t,j}}{\bm{e}}_{i_{t,j}}\right\rangle\lambda_{i_{t,l}}{\bm{e}} _{i_{t,l}}\right]$ $\displaystyle=$ $\displaystyle\frac{1}{K}\mathbb{E}_{{\bm{i}}_{t}}\left[\sum_{j=1}^{K}\sum_{l=1 }^{K}\left\langle\nabla_{{\bm{\theta}}}V(\pi_{{\bm{\theta}}_{t}}),{\bm{e}}_{i_ {t,j}}\right\rangle{\bm{e}}_{i_{t,l}}\mathbb{E}_{\bm{\lambda}_{t}}[\lambda_{i_ {t,j}}\lambda_{i_{t,l}}]\right],$ $$

where the first equality is by the definition of ${\bm{v}}_{t}$, the third equality is by law of total expectation. For $j\neq l$, we can use the independence between different coordinates of $\bm{\lambda}_{t}$. Since the expectation of $\bm{\lambda}_{t}$ is zero, we have:

$$ $\displaystyle\mathbb{E}_{\bm{\lambda}_{t}}[\lambda_{i_{t,j}}\lambda_{i_{t,l}}] =\mathbb{E}_{\bm{\lambda}_{t}}[\lambda_{i_{t,j}}]\mathbb{E}_{\bm{\lambda}_{t}} [\lambda_{i_{t,l}}]=0.$ $$

On the other hand, if $j=l$, since $\lambda_{i_{t},j}$ is sampled from $\{-1,1\}$, we have $\lambda_{i_{t},j}^{2}=1$. Therefore, the right-hand side can be expressed as:

$$ $\displaystyle\mathbb{E}_{{\bm{i}}_{t},\bm{\lambda}_{t}}\left[\langle\nabla_{{ \bm{\theta}}}V(\pi_{{\bm{\theta}}_{t}}),{\bm{v}}_{t}\rangle{\bm{v}}_{t}\right]=$ $\displaystyle\frac{1}{K}\mathbb{E}_{{\bm{i}}_{t}}\left[\sum_{j=1}^{K}\left \langle\nabla_{{\bm{\theta}}}V(\pi_{{\bm{\theta}}_{t}}),{\bm{e}}_{i_{t,j}} \right\rangle{\bm{e}}_{i_{t,j}}\right]$ $\displaystyle=$ $\displaystyle\frac{1}{K}\mathbb{E}_{{\bm{i}}_{t}}\left[\sum_{i=1}^{d}\mathbbm{ 1}_{i\in{\bm{i}}_{t}}\left\langle\nabla_{{\bm{\theta}}}V(\pi_{{\bm{\theta}}_{t }}),{\bm{e}}_{i}\right\rangle{\bm{e}}_{i}\right]$ $\displaystyle=$ $\displaystyle\frac{1}{K}\sum_{i=1}^{d}{\mathbb{P}}(i\in{\bm{i}}_{t})\left \langle\nabla_{{\bm{\theta}}}V(\pi_{{\bm{\theta}}_{t}}),{\bm{e}}_{i}\right \rangle{\bm{e}}_{i}$ $\displaystyle=$ $\displaystyle\frac{1}{d}\sum_{i=1}^{d}\left\langle\nabla_{{\bm{\theta}}}V(\pi_ {{\bm{\theta}}_{t}}),{\bm{e}}_{i}\right\rangle{\bm{e}}_{i}$ $\displaystyle=$ $\displaystyle\frac{1}{d}\nabla_{{\bm{\theta}}}V(\pi_{{\bm{\theta}}_{t}}),$ $$

where the second last equality is because the probability of each coordinate is chosen by ${\bm{i}}_{t}$ is exactly $K/d$. The proof is hence concluded. $\hfill\blacksquare$

With the help of the Lemma above, we can express the $\mathsf{Bias}_{t,1}$ term as follows:

$$ $\displaystyle\langle\nabla_{{\bm{\theta}}}V(\pi_{{\bm{\theta}}_{t}}),\mathsf{ Bias}_{t,1}\rangle$ $\displaystyle=$ $\displaystyle\left\langle\nabla_{{\bm{\theta}}}V(\pi_{{\bm{\theta}}_{t}}), \nabla_{{\bm{\theta}}}V(\pi_{{\bm{\theta}}_{t}})-\frac{d}{\mu}\mathbb{E}\left[ \left.\left(V(\pi_{{\bm{\theta}}_{t}+\mu{\bm{v}}_{t}})-V(\pi_{{\bm{\theta}}_{t }})\right){\bm{v}}_{t}\right|{\mathcal{F}}_{t}\right]\right\rangle$ $\displaystyle=$ $\displaystyle\frac{d}{\mu}\left\langle\nabla_{{\bm{\theta}}}V(\pi_{{\bm{\theta }}_{t}}),\mathbb{E}\left[\frac{\mu}{d}\nabla_{{\bm{\theta}}}V(\pi_{{\bm{\theta }}_{t}})-\left.\left(V(\pi_{{\bm{\theta}}_{t}+\mu{\bm{v}}_{t}})-V(\pi_{{\bm{ \theta}}_{t}})\right){\bm{v}}_{t}\right|{\mathcal{F}}_{t}\right]\right\rangle$ $\displaystyle=$ $\displaystyle-\frac{d}{\mu}\mathbb{E}\left[\left.\left(V(\pi_{{\bm{\theta}}_{t }+\mu{\bm{v}}_{t}})-V(\pi_{{\bm{\theta}}_{t}})-\langle\nabla_{{\bm{\theta}}}V( \pi_{{\bm{\theta}}_{t}}),\mu{\bm{v}}_{t}\rangle\right)\left\langle\nabla_{{\bm {\theta}}}V(\pi_{{\bm{\theta}}_{t}}),{\bm{v}}_{t}\right\rangle\right|{\mathcal {F}}_{t}\right]$ $\displaystyle\leq$ $\displaystyle\frac{d}{\mu}\mathbb{E}\left[\left.\left|V(\pi_{{\bm{\theta}}_{t} +\mu{\bm{v}}_{t}})-V(\pi_{{\bm{\theta}}_{t}})-\langle\nabla_{{\bm{\theta}}}V( \pi_{{\bm{\theta}}_{t}}),\mu{\bm{v}}_{t}\rangle\right|\left\|\nabla_{{\bm{ \theta}}}V(\pi_{{\bm{\theta}}_{t}})\right\|_{2}\left\|{\bm{v}}_{t}\right\|_{2} \right|{\mathcal{F}}_{t}\right].$ $$

By the smoothness of the value function $V$, we have:

$$ $\displaystyle\left|V(\pi_{{\bm{\theta}}_{t}+\mu{\bm{v}}_{t}})-V(\pi_{{\bm{ \theta}}_{t}})-\langle\nabla_{{\bm{\theta}}}V(\pi_{{\bm{\theta}}_{t}}),\mu{\bm {v}}_{t}\rangle\right|\leq\frac{\mu^{2}L}{2}\|{\bm{v}}_{t}\|_{2}=\frac{\mu^{2} L}{2}.$ $$

So we can substitute into the bias term and obtain:

$$ $\displaystyle\langle\nabla_{{\bm{\theta}}}V(\pi_{{\bm{\theta}}_{t}}),\mathsf{ Bias}_{t,1}\rangle\leq$ $\displaystyle\frac{d}{\mu}\mathbb{E}\left[\left.\frac{\mu^{2}L}{2}\left\| \nabla_{{\bm{\theta}}}V(\pi_{{\bm{\theta}}_{t}})\right\|_{2}\right|{\mathcal{F }}_{t}\right]$ $\displaystyle=$ $\displaystyle\frac{\mu Ld}{2}\left\|\nabla_{{\bm{\theta}}}V(\pi_{{\bm{\theta}} _{t}})\right\|_{2}.$ $$

Then, we obtain the upper bound of the gradient bias as follows:

$$ $\displaystyle\mathsf{Bias_{t}}=\langle\nabla_{{\bm{\theta}}}V(\pi_{{\bm{\theta }}_{t}}),\mathsf{Bias}_{t,1}+\mathsf{Bias}_{t,2}\rangle\leq\left(\frac{\mu Ld} {2}+\frac{2dL}{\mu}\sqrt{\frac{\log M}{M}}\right)\left\|\nabla_{{\bm{\theta}}} V_{\mu}(\pi_{{\bm{\theta}}_{t}})\right\|_{2}.$ $$

###### Lemma 8

### C.2 Proof of Lemma. 7

We aim for the variance term $\mathsf{Var}_{t}$ in the Lyapunov drift in equation 12. We first have upper bound variance as follows:

$$ $\displaystyle\mathsf{Var}_{t}=$ $\displaystyle\mathbb{E}\left[\left.\left\|\frac{d}{\mu}\frac{\sum_{n=1}^{N} \sigma^{-1}(p_{t,n})}{N}{\bm{v}}_{t}\right\|_{2}^{2}\right|{\mathcal{F}}_{t}\right]$ $\displaystyle\leq$ $\displaystyle 3\underbrace{\mathbb{E}\left[\left.\left\|\frac{d\sum_{n=1}^{N} \left(\sigma^{-1}(p_{t,n})-[r(\tau_{n,1})-r(\tau_{n,0})]\right)}{\mu N}{\bm{v} }_{t}\right\|_{2}^{2}\right|{\mathcal{F}}_{t}\right]}_{\mathsf{Var}_{t,1}}$ $\displaystyle+3\underbrace{\mathbb{E}\left[\left.\left\|\frac{d}{\mu}\left( \frac{\sum_{n=1}^{N}\left(r(\tau_{n,1})-r(\tau_{n,0})\right)}{N}-\left(V(\pi_{ {\bm{\theta}}_{t}+\mu{\bm{v}}_{t}})-V(\pi_{{\bm{\theta}}_{t}})\right)\right){ \bm{v}}_{t}\right\|_{2}^{2}\right|{\mathcal{F}}_{t}\right]}_{\mathsf{Var}_{t,2}}$ $\displaystyle+3\underbrace{\mathbb{E}\left[\left.\left\|\frac{d}{\mu}\left(V( \pi_{{\bm{\theta}}_{t}+\mu{\bm{v}}_{t}})-V(\pi_{{\bm{\theta}}_{t}})\right){\bm {v}}_{t}\right\|_{2}^{2}\right|{\mathcal{F}}_{t}\right]}_{\mathsf{Var}_{t,3}}.$ $$

The first term comes from the human preference estimation error which can be bounded using equation 6 from Lemma. 1 as follows:

$$ $\displaystyle\mathsf{Var}_{t,1}=$ $\displaystyle\mathbb{E}\left[\left.\left\|\frac{d\sum_{n=1}^{N}\left(\sigma^{- 1}(p_{t,n})-[r(\tau_{n,1})-r(\tau_{n,0})]\right)}{\mu N}{\bm{v}}_{t}\right\|_{ 2}^{2}\right|{\mathcal{F}}_{t}\right]$ $\displaystyle=$ $\displaystyle\frac{d^{2}}{\mu^{2}N^{2}}\mathbb{E}\left[\left.\left|\sum_{n=1}^ {N}\left(\sigma^{-1}(p_{t,n})-[r(\tau_{n,1})-r(\tau_{n,0})]\right)\right|^{2} \|{\bm{v}}_{t}\|_{2}^{2}\right|{\mathcal{F}}_{t}\right]$ $\displaystyle\leq$ $\displaystyle\frac{d^{2}}{\mu^{2}N}\sum_{n=1}^{N}\mathbb{E}\left[\left|\sigma^ {-1}(p_{t,n})-[r(\tau_{n,1})-r(\tau_{n,0})]\right|^{2}\right]$ $\displaystyle\leq$ $\displaystyle\frac{d^{2}}{\mu^{2}}\left(\frac{2L^{2}\log M}{M}+\frac{4H^{2}}{M ^{2}}\right)$ $\displaystyle\leq$ $\displaystyle\frac{3d^{2}L^{2}\log M}{\mu^{2}M},$ $$

where the first inequality uses Cauchy-Schwarz inequality and the fact that $\|{\bm{v}}_{t}\|_{2}^{2}=1$, and the second inequality uses Lemma. 1. The final inequality is true by choosing $M\geq 4(H/L)^{2}$. The second term comes from using the empirical average reward to estimate the value function similar to REINFORCE. So we have:

$$ $\displaystyle\mathsf{Var}_{t,2}=$ $\displaystyle\mathbb{E}\left[\left.\left\|\frac{d}{\mu}\left(\frac{\sum_{n=1}^ {N}\left(r(\tau_{n,1})-r(\tau_{n,0})\right)}{N}-\left(V(\pi_{{\bm{\theta}}_{t} +\mu{\bm{v}}_{t}})-V(\pi_{{\bm{\theta}}_{t}})\right)\right){\bm{v}}_{t}\right \|_{2}^{2}\right|{\mathcal{F}}_{t}\right]$ $\displaystyle=$ $\displaystyle\frac{d^{2}}{\mu^{2}N^{2}}\mathbb{E}\left[\left.\left|\sum_{n=1}^ {N}\left(\underbrace{\left(r(\tau_{n,1})-r(\tau_{n,0})\right)-\left(V(\pi_{{ \bm{\theta}}_{t}+\mu{\bm{v}}_{t}})-V(\pi_{{\bm{\theta}}_{t}})\right)}_{\mathsf {E}_{t,n}}\right)\right|_{2}^{2}\|{\bm{v}}_{t}\|_{2}^{2}\right|{\mathcal{F}}_{ t}\right]$ $\displaystyle=$ $\displaystyle\frac{d^{2}}{\mu^{2}N^{2}}\mathbb{E}\left[\left.\left|\sum_{n=1}^ {N}\mathsf{E}_{t,n}\right|_{2}^{2}\right|{\mathcal{F}}_{t}\right],$ $$

where the last equality is because $\|{\bm{v}}_{t}\|_{2}^{2}=1$. We open up the square as:

$$ $\displaystyle\mathbb{E}\left[\left.\left|\sum_{n=1}^{N}\mathsf{E}_{t,n}\right| _{2}^{2}\right|{\mathcal{F}}_{t}\right]=$ $\displaystyle\sum_{n=1}^{N}\mathbb{E}\left[\left.\left|\mathsf{E}_{t,n}\right| _{2}^{2}\right|{\mathcal{F}}_{t}\right]+\sum_{i\neq j}\mathbb{E}\left[\left. \mathbb{E}[\mathsf{E}_{t,i}\mathsf{E}_{t,j}|{\bm{v}}_{t}]\right|{\mathcal{F}}_ {t}\right]$ $\displaystyle=$ $\displaystyle\sum_{n=1}^{N}\mathbb{E}\left[\left.\left|\mathsf{E}_{t,n}\right| _{2}^{2}\right|{\mathcal{F}}_{t}\right]+\sum_{i\neq j}\mathbb{E}\left[\left. \mathbb{E}[\mathsf{E}_{t,i}|{\bm{v}}_{t}]\right|{\mathcal{F}}_{t}\right] \mathbb{E}\left[\left.\mathbb{E}[\mathsf{E}_{t,j}|{\bm{v}}_{t}]\right|{ \mathcal{F}}_{t}\right]$ $\displaystyle=$ $\displaystyle\sum_{n=1}^{N}\mathbb{E}\left[\left.\left|\mathsf{E}_{t,n}\right| _{2}^{2}\right|{\mathcal{F}}_{t}\right].$ $$

where the second inequality uses the independence between trajectories generated at the same step, and the last equality is due to $\mathbb{E}[\left(r(\tau_{n,1})-r(\tau_{n,0})\right)-\left(V(\pi_{{\bm{\theta}}
_{t}+\mu{\bm{v}}_{t}})-V(\pi_{{\bm{\theta}}_{t}})\right)]=0$ for any fixed perturbation direction ${\bm{v}}_{t}$ from the definition of value function. So we have:

$$ $\displaystyle\mathsf{Var}_{t,2}=$ $\displaystyle\frac{d^{2}}{\mu^{2}N^{2}}\sum_{n=1}^{N}\mathbb{E}\left[\left. \left|\mathsf{E}_{t,n}\right|_{2}^{2}\right|{\mathcal{F}}_{t}\right]$ $\displaystyle=$ $\displaystyle\frac{d^{2}}{\mu^{2}N^{2}}\sum_{n=1}^{N}\mathbb{E}\left[\left. \left|\left(r(\tau_{n,1})-r(\tau_{n,0})\right)-\left(V(\pi_{{\bm{\theta}}_{t}+ \mu{\bm{v}}_{t}})-V(\pi_{{\bm{\theta}}_{t}})\right)\right|_{2}^{2}\right|{ \mathcal{F}}_{t}\right]$ $\displaystyle\leq$ $\displaystyle\frac{4d^{2}H^{2}}{\mu^{2}N},$ $$

where the last inequality uses the fact that both the difference of reward and the difference of value function are within $[-H,H]$. Now we analyze the last term:

$$ $\displaystyle\mathsf{Var}_{t,3}=$ $\displaystyle\mathbb{E}\left[\left.\left\|\frac{d}{\mu}\left(V(\pi_{{\bm{ \theta}}_{t}+\mu{\bm{v}}_{t}})-V(\pi_{{\bm{\theta}}_{t}})\right){\bm{v}}_{t} \right\|_{2}^{2}\right|{\mathcal{F}}_{t}\right]$ $\displaystyle=$ $\displaystyle\frac{d^{2}}{\mu^{2}}\mathbb{E}\left[\left.\left\|\left(V(\pi_{{ \bm{\theta}}_{t}+\mu{\bm{v}}_{t}})-V(\pi_{{\bm{\theta}}_{t}})-\langle\nabla_{{ \bm{\theta}}}V(\pi_{{\bm{\theta}}_{t}}),\mu{\bm{v}}_{t}\rangle\right){\bm{v}}_ {t}+\langle\nabla_{{\bm{\theta}}}V(\pi_{{\bm{\theta}}_{t}}),\mu{\bm{v}}_{t} \rangle{\bm{v}}_{t}\right\|_{2}^{2}\right|{\mathcal{F}}_{t}\right]$ $\displaystyle\leq$ $\displaystyle\frac{2d^{2}}{\mu^{2}}\mathbb{E}\left[\left.\left\|\left(V(\pi_{{ \bm{\theta}}_{t}+\mu{\bm{v}}_{t}})-V(\pi_{{\bm{\theta}}_{t}})-\langle\nabla_{{ \bm{\theta}}}V(\pi_{{\bm{\theta}}_{t}}),\mu{\bm{v}}_{t}\rangle\right){\bm{v}}_ {t}\right\|_{2}^{2}\right|{\mathcal{F}}_{t}\right]$ $\displaystyle+\frac{2d^{2}}{\mu^{2}}\mathbb{E}\left[\left.\left\|\langle\nabla _{{\bm{\theta}}}V(\pi_{{\bm{\theta}}_{t}}),\mu{\bm{v}}_{t}\rangle{\bm{v}}_{t} \right\|_{2}^{2}\right|{\mathcal{F}}_{t}\right].$ $$

The first term can be bounded using the smoothness of the value function as follows:

$$ $\displaystyle\mathbb{E}\left[\left.\left\|\left(V(\pi_{{\bm{\theta}}_{t}+\mu{ \bm{v}}_{t}})-V(\pi_{{\bm{\theta}}_{t}})-\langle\nabla_{{\bm{\theta}}}V(\pi_{{ \bm{\theta}}_{t}}),\mu{\bm{v}}_{t}\rangle\right){\bm{v}}_{t}\right\|_{2}^{2} \right|{\mathcal{F}}_{t}\right]$ $\displaystyle=$ $\displaystyle\mathbb{E}\left[\left.\left|\left(V(\pi_{{\bm{\theta}}_{t}+\mu{ \bm{v}}_{t}})-V(\pi_{{\bm{\theta}}_{t}})-\langle\nabla_{{\bm{\theta}}}V(\pi_{{ \bm{\theta}}_{t}}),\mu{\bm{v}}_{t}\rangle\right)\right|_{2}^{2}\|{\bm{v}}_{t} \|_{2}^{2}\right|{\mathcal{F}}_{t}\right]$ $\displaystyle\leq$ $\displaystyle\mathbb{E}\left[\left.\frac{L^{2}\mu^{4}}{4}\|{\bm{v}}_{t}\|_{2}^ {4}\right|{\mathcal{F}}_{t}\right]$ $\displaystyle=$ $\displaystyle\frac{L^{2}\mu^{4}}{4},$ $$

where the last equality uses $\|{\bm{v}}_{t}\|_{2}^{2}=K$. The second term can be simplified as follows:

$$ $\displaystyle\mathbb{E}\left[\left.\left\|\langle\nabla_{{\bm{\theta}}}V(\pi_{ {\bm{\theta}}_{t}}),\mu{\bm{v}}_{t}\rangle{\bm{v}}_{t}\right\|_{2}^{2}\right|{ \mathcal{F}}_{t}\right]=$ $\displaystyle\mu^{2}\mathbb{E}\left[\left.\nabla_{{\bm{\theta}}}V(\pi_{{\bm{ \theta}}_{t}})^{\top}{\bm{v}}_{t}{\bm{v}}_{t}^{\top}\nabla_{{\bm{\theta}}}V( \pi_{{\bm{\theta}}_{t}})\left\|{\bm{v}}_{t}\right\|_{2}^{2}\right|{\mathcal{F} }_{t}\right]$ $\displaystyle=$ $\displaystyle\mu^{2}\nabla_{{\bm{\theta}}}V(\pi_{{\bm{\theta}}_{t}})^{\top} \mathbb{E}\left[\left.{\bm{v}}_{t}{\bm{v}}_{t}^{\top}\right|{\mathcal{F}}_{t} \right]\nabla_{{\bm{\theta}}}V(\pi_{{\bm{\theta}}_{t}}).$ $$

Notice that ${\bm{v}}_{t}$ is a vector which on the coordinates chosen by ${\bm{i}}_{t}$, it is either $-1/\sqrt{K}$ or $1/\sqrt{K}$, on other coordinates, it is zero. So ${\bm{v}}_{t}{\bm{v}}_{t}^{\top}$ will result in a diagonal matrix where on position $(i_{t,1},i_{t,1}),\cdots,(i_{t,K},i_{t,K})$ the element is $1/K$ and 0 0 otherwise. Since each coordinate $i$ will be chosen in each iteration in ${\bm{i}}_{t}$ with probability $K/d$, taking an expectation over ${\bm{v}}_{t}{\bm{v}}_{t}^{\top}$ will result in a diagonal matrix where the diagonal elements are $1/d$. Therefore, we have:

$$ $\displaystyle\mathbb{E}\left[\left.\left\|\langle\nabla_{{\bm{\theta}}}V(\pi_{ {\bm{\theta}}_{t}}),\mu{\bm{v}}_{t}\rangle{\bm{v}}_{t}\right\|_{2}^{2}\right|{ \mathcal{F}}_{t}\right]=$ $\displaystyle\frac{\mu^{2}}{d}\nabla_{{\bm{\theta}}}V(\pi_{{\bm{\theta}}_{t}}) ^{\top}\nabla_{{\bm{\theta}}}V(\pi_{{\bm{\theta}}_{t}})=\frac{\mu^{2}}{d}\| \nabla_{{\bm{\theta}}}V(\pi_{{\bm{\theta}}_{t}})\|_{2}^{2}.$ $$

So Let us combine both terms and we can bound $\mathsf{Var}_{t,3}$ as follows:

$$ $\displaystyle\mathsf{Var}_{t,3}\leq\frac{\mu^{2}L^{2}d^{2}}{2}+2d\|\nabla_{{ \bm{\theta}}}V(\pi_{{\bm{\theta}}_{t}})\|_{2}^{2}.$ $$

So combining three terms together, the variance drift can be bounded as:

$$ $\displaystyle\mathsf{Var}_{t}\leq 6d\left\|\nabla_{{\bm{\theta}}}V(\pi_{{\bm{ \theta}}_{t}})\right\|_{2}^{2}+\frac{3\mu^{2}L^{2}d^{2}}{2}+\frac{9d^{2}L^{2} \log M}{\mu^{2}M}+\frac{12d^{2}H^{2}}{\mu^{2}N}.$ $$

## Peer Reviews

confidence: 4
contribution: 2
initial_rating: 5
presentation: 3
questions: Is there a way to go from local to global convergence? Perhaps is global convergence can be achieved, the work may be accepted for publication.
soundness: 4
strengths: The paper utilizes a novel method for estimation of the difference in the value functions using the inverse of the preference functions. It is able to prove local convergence for a non-deterministic MDP. The paper is well laid out and easy to read.
summary: This is a novel result that establishes local convergence for an RLHF setup utilizing a novel method to estimate the difference in value functions. However, given the current literature which has established global convergence with a better sample complexity. I do not think this work has sufficient novelty for acceptance.
weaknesses: The paper can only establish local convergence for the RLHF setup with a sample complexity of $\epsilon^{-5}$. In contrast Xie et al. (2024) established global convergence with sample complexity of $\epsilon^{-2}$.  Even though that case is for a finite state and action space, given the improved sample complexity and global convergence Xie et al. (2024) seems to be the more relevant result.

I am open to improving my score if the authors can give an argument as to why their work improves upon the cited work.



References:


Tengyang Xie, Dylan J. Foster, Akshay Krishnamurthy, Corby Rosset, Ahmed Awadallah, and Alexander Rakhlin. Exploratory preference 
 optimization: Harnessing implicit q*-approximation for sample-efficient rlhf, 2024.

---

confidence: 4
contribution: 2
initial_rating: 3
presentation: 2
questions: ### === Zero-order method in deep RL ===

The idea of applying random perturbation to model parameters and construct gradient accordingly, has been studied extensively in the deep RL literature as replacement for REINFORCE or PPO like algorithms. It seems that much discussion is missing from the paper such as [1] which basically started the trend of zero-order based method for deep RL.

[1] Salisman et al, 2017, Evolution Strategies as a Scalable Alternative to Reinforcement Learning

### === Relevance to RLHF ===

It's not clear if the discussion here is specific to RLHF at all. Do RLHF allow us to assume additional structure on the rewards or the parameter space? No such discussion is furthered in the paper - in regular RL or deep RL setups, the same algorithmic discussions apply. And as a result, the paper is not really a RLHF specific algorithm, the algorithm itself has been extensively studied in the RL literature as well.

### === Empirical ===

There is no empirical backup of the results at all, not even tabular experiments. I think a theoretical paper in its current form like this would not offer too much additional value to the field of RLHF or deep RL. Certain amount of experimentation is warranted, and in the case of RLHF, it is also interesting to see if the algorithm can work at all and how it compares with REINFORCE / PPO.
soundness: 2
strengths: The paper presents theoretical guarantees for zero-order optimization algorithm for RLHF.
summary: The paper proposes a zero-order optimization algorithm for RLHF. The idea is to carry out random perturbation in the space of parameters directly and construct gradient updates based on the random samples. The paper presents some theoretical results that characterize the bias and convergence property of the algorithm.
weaknesses: The idea of applying zero-order optimization is not novel. Similar ideas have been extensively studied in the deep RL literature. Much literature reference is missing from discussion. A theoretical paper like this is not very valuable to the RLHF or deep RL community.

---

confidence: 3
contribution: 3
initial_rating: 6
presentation: 3
questions: - You mention that classic RLHF and DPO use human preferences to construct a global model, while your method uses the preferences only to locally estimate the policy gradient. While that’s true in theory, however in the actual DPO algorithm in practice, it is also using the expected difference in preference between two generations to construct a policy gradient. Like you mention, because of function approximation, the global BT model assumed by DPO no longer holds, so the empirical DPO also ends up only using local information to estimate the policy gradient. Especially if DPO is used online instead of from a fixed offline dataset. So in practice, both DPO and ZPG are using local information to estimate a policy gradient, and the global-local divide isn’t really clearly there anymore. Could you update the discussion to reflect this?
- You mention the link function generalizes the BT-model. Could you give one or  more motivating examples of non-BT models and link functions that could be applicable (no need for experiments or deep analysis, just give some intuition on when non-BT models could be useful)? I think this would strengthen the contribution of the more general link function.

-- After Author Response --
Thank you for adding the additional numerical experiments and non-BT explanations. I have increased my score.
soundness: 4
strengths: - The methods ZPG and ZBCPG work for a general class of link functions (beyond the BT-model) and stochastic dynamics as well.
- Theoretical sample complexity and convergence rates that give an idea of the dependence on the number of human preferences needed, and prove convergence exists. I have not checked the proofs in detail.
summary: This paper proposes the use of zero-th order algorithms to align a policy to preference data. They propose ZPG, based on random spherical perturbations, and ZBCPG, based on subblockwise perturbations, and prove sample complexity and convergence rates. These algorithms generalize from a Bradley-Terry preference model to general preference model with a specified link function, as well as generalize from deterministic to stochastic domains.
weaknesses: - ZPG and ZBCPG do not work directly from an offline dataset like DPO can; they require online human preferences for the current samples. - Furthermore, even comparing ZPG to online DPO, it seems that ZPG requires more trajectory samples (i.e. more forward passes) because you need multiple perturbations, which is multiple times more costly than online DPO.
- Zero-th order methods may be slower than gradient-based methods, especially for very large models like LLMs.
- No toy experiments. While LLM experiments would seem daunting in addition to the theoretical contribution, toy experiments in simple, stochastic domains to illustrate how DPO would fail but ZPG would work, would be a great addition to further motivate the need for a DPO alternative. I would be willing to increase my score if toy experiments are added to the paper.

---

confidence: 4
contribution: 3
initial_rating: 8
presentation: 3
questions: ## Lack of discussion 
* Can you please discuss more thoroughly the limitations of the proposed approach (like the need to have on-policy online human raters), and in more details what are the pros and cons compared to DPO and classic RLHF?
* One advantage claimed compared to DPO is the ability to handle stochastic transitions. However, the focus is also mostly done on LLMS. Can you explain in which case we would have stochastic transitions in this context (and how it is handled by your framework)?
* There is no KL regularization, compared to all other works for doing RLHF (and not without reason). Can you expand on this, is it no longer required (from a practical perspective)?
* The paper claims going « beyond the BT model », but the generalization is rather weak, could it handle more general preference models such as those considered for example in « Nash learning from human feedback » by Munos et al?

## No empirical study
* Given that the analyzed algorithm is not representative of practical approaches, and that the second proposed algorithm is motivated by computational aspects (memory, distributed aspect), would it make sense to at least provide some minimal empirical study (with the proposed algorithms, but also DPO, classic RLHF, online DPO)? Or to provide a clear discussion about why it would not bring interesting evidences?

## Aspects to clarify and/or correct 
* It is claimed (l.163) that the considered setting encompasses things like convex MDP. Can the authors expend on this (from the setting, they do not make the assumption that the return is sum-decomposable, but why would this tell that it can be framed as a convex function of the occupancy measure)?
* Would it be possible to group or recall the properties and assumptions of the link function, as it is a quite central object? For example, should we not assume also that $\sigma(x) = 1 - \sigma(-x)$, or is it a consequence of what is already written? Could you also give some examples of the Lipschitz constants $L$ (Assm 2), for example for the logistic function used in Bradley-Terry?
* There is a typo l. 305 (as written, the gradient is always zero, issue in the second value index)
* Assm 2 and 3, the same notation $L$ is used for the Lipschitz constant of $\sigma^{-1}$ and for $L$-smoothness of $V$. There is not reason for these two values to be the same. They are also confused in the proofs. Would it be possible to restate the results by making them distinct (or at least by stating that it’s for some upper-bound of both terms, if that's enough to make proofs work)?
* In Thm 1 and 2, $M$ is a function of $D$, quantity which has never been defined. Even checking the proofs it is not clear what $D$ is. Please clarify (and this is especially important as it is the number of human raters).
* Corollary 1 doesn’t seem to be proven, even in the appendix, can you provide a proof?
* l. 435, how does $\theta^*$ appear with a telescoping argument (plus, the corresponding equation in the appendix involves $\theta_T$, which seems more logical)?
* Lemma 2, would be helpful to explain why the trim operator is introduced (as the result would hold without the trim according to the proof)
* l. 977, typo (parenthesis)
* l. 1014, is it the same $L$ as in Assm 3?
* the end of proof of Thm 1 is pretty unclear (line 1104 to the end of the proof), which is a pitty, as it is the clever part of the proof discussed l.455-465. Why do we have Eq 1106, and why does it lead (and how) to the equation line 1110? It is claimed to be for the case of large gradient, but line 1119 it is again for the case of large gradient. How is the Eq line 1122 obtained, and how does it relates to the one in line 1107? Do these both equations covers all possible gradient cases, and why? L. 1134, how are combined the bounds (max of them, summing them, something else)? Overall, could you reexplain this overall important part?
* l. 1214, there is a missing term (or the line should be removed) * l. 1230-1241, why the 3 factor? (not wrong, but why)
soundness: 3
strengths: * The proposed algorithms are interesting, at least from a theoretical viewpoint
* The paper is overall clearly and well written
* There is a nice discussion of the technical difficulties for proving their results, which is quite helpful
* The provided theoretical results sound plausible (some questions about the proofs of Thm1 though, and Thm 2 has not been double-checked)
summary: This paper introduces two new algorithms for RLHF that do not require learning a reward function. The core algorithm is a variation of reinforce, using a zero-order gradient approximator (the two proposed algorithms differing in the choice of the perturbation direction). To avoid learning a reward function, the authors assume that the preference model is Bradley-Terry-like (considering a more general sigmoid link function, instead of just the logistic function), that $M$ human raters (with $M$ large enough) are available for ranking $N$ pairs of completions (current policy - perturbation), and then use the  inverse of the link function to estimate the reward difference from the empirical preference probability, this reward difference being used for the zero-order gradient estimate. The authors show a convergence result for each algorithm, with rate of convergence (the same), for reaching a stationary policy (not necessarily the optimal one, but one with zero gradient). They also provide some explanations about the technical difficulties of their proof (full proofs being provided in the appendix). There is no empirical study.
weaknesses: * There are overclaims and/or lack of discussion of the limitations of the proposed approach. Drawbacks of DPO or classic RLHF are discussed at length, suggesting that the proposed approach alleviate them (which is only very partly true), but not the limitations of the proposed approach. The strongest issue is that it is assumed that $M$ humans are available for rating $N$ pairs of trajectories for each gradient step (and this must be done online, because the proposed approach is purely on-policy). So, it is hard to see any setting where this could be applicable or reasonable, and it is a strong drawback compared to more practical RLHF approaches. It may be fine to have an algorithm with theoretical guarantees that is not fully applicable, but this should be discussed.
*  The proposed algorithms seem to be new, and they are explicitly positioned as addressing shortcomings of classic RLHF or DPO, which would call for some empirical results, at least on bandits or toy MDPs (possibly comparing with classic RLHF, DPO, but also things like online DPO, eg see « Direct language model alignment from online ai feedback » by Guo et al). There is no such empirical study, and it would really strengthen the paper by providing some empirical evidences on some claims done in the paper.
* There are parts of the paper and of the proofs that are not totally clear, see questions.

Meta-review: This paper is primarily theoretical. The authors propose zeroth order optimization methods for RLHF, prove sample complexity and convergence rates.
The algorithm is quite interesting from a theoretical perspective.
The method is new and seems to alleviate some of the limitations of current algorithm for RLHF.

The main limitation, although not extensively highlighted by the reviewers, is the lack of a comprehensive empirical study.

Decision: Accept (Poster)