REBEL: Reinforcement Learning via Regressing Relative Rewards
Zhaolin Gao Jonathan D. Chang Wenhao Zhan Owen Oertell Gokul Swamy Kianté Brantley Thorsten Joachims J. Andrew Bagnell Jason D. Lee Wen Sun
 




            
       
       
       
      



























plainnat
();a,,

packed_enum
  
    
    
    






=1 





















 


































 


ifpackageloadedgeometryletterpaper,left=1.56in,right=1.56in,top=1.71in,bottom=1.77in
letterpaper,left=1.56in,right=1.56in,top=1.71in,bottom=1.77in
1














: Reinforcement Learning via Regressing 
Relative Rewards
    Zhaolin Gao, Jonathan D. Chang, Wenhao Zhan, Owen Oertell, Gokul Swamy, Kianté Brantley, Thorsten Joachims, J. Andrew Bagnell, Jason D. Lee, Wen Sun

 Cornell University,      Princeton University  Carnegie Mellon University   

    April 29, 2024
========================================================================================================================================================================================================================================




While originally developed for continuous control problems, Proximal Policy Optimization (PPO) has emerged as the work-horse of a variety of reinforcement learning (RL) applications including the fine-tuning of generative models. Unfortunately, PPO requires multiple heuristics to enable stable convergence (e.g. value networks, clipping) and is notorious for its sensitivity to the precise implementation of these components. In response, we take a step back and ask what a minimalist RL algorithm for the era of generative models would look like. We propose , an algorithm that cleanly reduces the problem of policy optimization to regressing the relative rewards via a direct policy parameterization between two completions to a prompt, enabling strikingly lightweight implementation. In theory, we prove that fundamental RL algorithms like Natural Policy Gradient can be seen as variants of , which allows us to match the strongest known theoretical guarantees in terms of convergence and sample complexity in the RL literature.  can also cleanly incorporate offline data and handle the intransitive preferences we frequently see in practice. Empirically, we find that  provides a unified approach to language modeling and image generation with stronger or similar performance as PPO and DPO, all while being simpler to implement and more computationally tractable than PPO. =-1





§ INTRODUCTION

The generality of the reinforcement learning (RL) paradigm is striking: from continuous control problems <cit.> to, recently, the fine-tuning of generative models <cit.>, RL has enabled concrete progress across a variety of decision-making tasks. Specifically, when it comes to fine-tuning generative models, Proximal Policy Optimization (PPO, <cit.>) has emerged as the de-facto RL algorithm of choice, from language models (LLMs) <cit.> to image generative models <cit.>.

If we take a step back however, it is odd that we are using an algorithm designed for optimizing two-layer networks for continuous control tasks from scratch for fine-tuning the billions of parameters of modern-day generative models. In the continuous control setting, the randomly initialized neural networks and the possible stochasticity in the dynamics necessitate variance reduction through a learned value function as a baseline <cit.>, while clipping updates is important to limit distribution shift from iteration to iteration <cit.>. This means that when applied to generative model fine-tuning, we need to store four models in memory simultaneously (the policy, the reference policy, the critic, and the reward model), each with billions of parameters. Furthermore, we often add a KL regularization to the base model for fine-tuning, making explicit clipping unnecessary nor advisable, as pointed out by <cit.>. Even outside of the generative modeling context, PPO is notorious for the wide range of performances measured, with differences being attributed to seemingly inconsequential implementation details <cit.>. This begs the question: =-1





    Are there simpler algorithms that scale to modern RL applications?




Our answer is : an algorithm that reduces the problem of reinforcement learning to solving a sequence of squared loss regression problems on iteratively collected datasets. The regression problems directly use policies to predict the difference in rewards. This allows us to eliminate the complexity of value functions, avoid heuristics like clipping, and scale easily to problems in both language modeling and image generation. Our key insight is that 
regressing relative rewards via policies directly on a sequence of iteratively collected datasets implicitly enables policy improvement.

Rather than being a heuristic,  comes with strong guarantees in theory and can be seen as a strict generalization of classical techniques (e.g., NPG) in reinforcement learning. Furthermore,  cleanly incorporates offline datasets when available, can be extended to robustly handle intransitive preferences <cit.>, and empirically out-performs techniques like PPO and DPO <cit.> in language generation and has a faster convergence with a similar asymptotic performance in image generation. More explicitly, our key contributions are four-fold:


    
  * We propose , a simple and scalable RL algorithm.  finds a near-optimal policy by solving a sequence of least square regression problems on iteratively collected datasets. Each regression problem involves using a policy-parameterized regressor to predict the difference in rewards across trajectories sampled from the dataset. This dataset can be generated in a purely on-policy fashion or can incorporate offline data, enabling hybrid training. Furthermore,  can be easily extended to handle intransitive preferences.
    
  * We connect  to classical RL methods. We show that  is a generalization of the foundational Natural Policy Gradient (NPG, <cit.>) algorithm – applying the Gauss-Newton algorithm to the sequence of regression problems that  solves recovers NPG. However, by instead applying simpler first-order optimization techniques, we are able to avoid computing the Fisher Information Matrix and enjoy a variance reduction effect. Thus,  can be understood as a generalization of NPG while being much more scalable. 
    
  * We analyze the convergence properties of . We prove via a direct reduction-based analysis that as long as we can solve the regression problem well at each iteration, we will be able to compete with any policy covered by the iteratively collected datasets (matching the strongest known results in the agnostic RL). These problems involve predicting the difference in rewards between trajectories in our dataset. We expect this problem to be well-solved in practice because our class of regressors is isomorphic to a class of policies that is highly expressive for the applications we consider (i.e. flexible Transformer models).
    
  * We evaluate  both on language modeling and image generation tasks. We find that the on-policy version of  outperforms PPO and DPO on language modeling and has similar performance for image generation tasks. On the  summarization task, we show  scales well by finetuning a 6.9B parameter model. For text-guided image generation,  optimizes a consistency model that converges to a similar performance as PPO.


In short,  is a simple and scalable algorithm that enjoys strong theoretical guarantees and empirical performance. We believe it is a suitable answer to the question raised above. 

















§ : REGRESSION TO RELATIVE REWARD BASED RL

We first outline the notation used throughout the paper.



 §.§ Notation

We consider the Contextual Bandit formulation <cit.> of RL which has been used to formalize the generation process of 
models like LLMs <cit.>
and Diffusion Models <cit.>
due to the determinism of the transitions. More explicitly, in the deterministic transition setting, explicit states are not required as they can be equivalently represented by a sequence of actions. Furthermore, the entire sequence of actions can be considered as a single “arm” in a bandit problem with an exponentially large action space.

We denote by (x,y) a prompt/response pair with x∈ as a prompt and y ∈ as a response (e.g., a sequence of tokens, or in general a sequence of actions).
We assume access to a reward function r(x,y) from which we can query for reward signals (the exact form of r does not need to be known).  Querying r at (x,y) will return a scalar r(x,y) measuring the quality of the response. Such a reward function could be a pre-defined metric (e.g., Rouge score against human responses)
or it could be learned from an offline human demonstration or preference data (e.g., the  RLHF paradigm <cit.>), as explored in our experiments. 

Denote by π∈↦Δ(Y), a policy (e.g. LLM) that maps from a prompt x to a distribution over the response space . We use ρ to denote the distribution over prompts (i.e. initial states / contexts) x. Throughout the paper, we use π_θ(y|x) to denote a parameterized policy with parameter θ (e.g., a neural network policy). At times we interchangeably use π_t and π_θ_t when it is clear from the context. We emphasize that while we focus on the bandit formulation for notation simplicity, the algorithms proposed here can be applied to any deterministic MDP where x is the initial state and the trajectory y consists of the sequence of actions.

At each iteration of all algorithms, our goal will be to solve the following KL-constrained RL problem:

    π_t+1 = _π_x,y∼π(· | x) r(x,y) - 1/η_xKL( π(· | x) || π_t(· | x) ).


Intuitively, this can be thought of asking for the optimizer to fine-tune the policy π_t+1 according to r while staying close to some baseline policy π_t. 



 §.§ Deriving : REgression to RElative REward Based RL

From <cit.>, we know that there exists a closed-form solution to the above minimum relative entropy problem (Eq. <ref>, <cit.>):

    ∀ x,y:  π_t+1(y|x) =π_t(y | x) exp(η r(x,y))/ Z(x);   Z(x) = ∑_yπ_t(y|x) exp(η r(x,y)).

As first pointed out by <cit.>, observe that we can invert Eq. <ref> and write the reward as a function of the policy, i.e. the “DPO Trick”:

    ∀ x,y:   r(x,y) = 1/η( ln(Z(x)) + ln (π_t+1(y|x)/π_t(y | x)) ).

As soon as 𝒳 and 𝒴 become large, we can no longer guarantee the above expression holds exactly at all (x, y) and therefore need to turn our attention to choosing a policy such that Eq. <ref> is approximately true. We propose using a simple square loss objective between the two sides of Eq. <ref> to measure the goodness of a policy, i.e. reducing RL to a regression problem:

    (r(x,y) - 1/η( ln(Z(x)) + ln (π_t+1(y|x)/π_t(y | x)) ) ) ^2.

Unfortunately, this loss function includes the partition function Z(x), which can be challenging to approximate over large input / output domains. However, observe that Z(x) only depends on x and not y. Thus, if we have access to paired samples, i.e. (x, y) and (x, y'), we can instead regress the difference in rewards to eliminate this term from our objective:

    ((r(x,y) - r(x, y')) - 1/η(ln (π_t+1(y|x)/π_t(y | x)) - ln (π_t+1(y'|x)/π_t(y'| x)) ) ) ^2.

Of course, we need to evaluate this loss function on some distribution of samples. In particular, we propose using an on-policy dataset _t = { x, y, y' } with x∼ρ, y∼π_t(· | x), y'∼(· | x), where μ is some base distribution. The base distribution  can either be a fixed offline dataset (e.g. the instruction fine-tuning dataset) or π_t itself. Thus, the choice of base distribution  determines whether  is hybrid or fully online. Putting it all together, we arrive at our core 
  objective:

    ∑_(x,y,y')∈_t((r(x,y) - r(x, y')) - 1/η(ln (π_t+1(y|x)/π_t(y | x)) - ln (π_t+1(y'|x)/π_t(y'| x)) ) ) ^2.


To recap, given a pair of completions y, y' to a prompt x,  attempt to fit the relative reward

    r(x, y) - r(x, y')

by optimizing over a class of predictors of the form

    1/η(lnπ_θ(y|x)/π_θ_t(y|x) - lnπ_θ(y'|x)/π_θ_t(y'|x)).

Critically, observe that if we were able to perfectly solve this regression problem, we would indeed recover the optimal solution to the KL-constrained RL problem we outlined in Eq. <ref>.
While the above update might seem somewhat arbitrary at first glance, it has deep connections to prior work in the literature that illuminate its strengths over past techniques. We now discuss some of them.








§ UNDERSTANDING  AS AN ADAPTIVE POLICY GRADIENT


We begin by recapping the foundational algorithms for policy optimization before situating  within this space of techniques.



 §.§ Adaptive Gradient Algorithms for Policy Optimization

In this section, we give a brief overview of three adaptive gradient algorithms: Mirror Descent (MD), Natural Policy Gradient (NPG), and Proximal Policy Optimization (PPO). We discuss why they are preferable to their non-adaptive counterparts (Gradient Descent (GD) and Policy Gradient (PG)) and the connections between them. 

Mirror Descent. If  and  are small discrete spaces (i.e. we are in the tabular setting), we can used the closed-form expression for the minimum relative entropy problem (Eq. <ref>). This is equivalent to the classic Mirror Descent (MD) algorithm with KL as the Bregman divergence. This update procedure is also sometimes known as soft policy iteration <cit.>. Note that it does not even involve a parameterized policy and is therefore manifestly covariant. MD ensures a 1/T convergence rate, i.e., after T iterations, it must find a policy π̂, such that _x,y∼π^⋆(.|x) r(x,y) - _x,y∼π̂(.|x) r(x,y) ≤ O(1/T). In particular, the convergence is almost dimension-free: the convergence rate scales logarithmically with respect to the size of the  space.  Note that gradient ascent will not enjoy such a dimension-free rate when optimizing over the simplex.
When sup_x,y | r(x,y)| is bounded, we can show that the KL divergence between two policies, i.e., KL(π_t+1(· | x) || π_t(· | x)), is also bounded, ensuring π_t+1 stay close to π_t. One can also show monotonic policy improvement, i.e., _x,y∼π_t+1 r(x,y) ≥_x,y∼π_t r(x,y). Foreshadowing a key point we will soon expound upon, both NPG and PPO can be considered approximations of this idealized tabular policy update procedure.


Natural Policy Gradient.
When  and  are large, we cannot simply enumerate all x and y. 
Thus, we need to use a function to approximate π, which makes it impossible to exactly implement Eq. <ref>. Let us use π_θ to denote a parameterized policy with parameter θ (e.g. the weights of a transformer). 
The Natural Policy Gradient (NPG, <cit.>) approximates the KL in Equation <ref> via its second-order Taylor expansion, whose Hessian is known as the Fisher Information Matrix (FIM, <cit.>), i.e.   

    _xKL( π_θ(· | x) || π_θ_t(· | x) ) ≈ (θ-θ_t)^⊤_x, y ∼π_θ_t(· | x)[ ∇lnπ_θ_t(y|x) ∇lnπ_θ_t(y|x)^⊤]_Fisher Information Matrix  F_t (θ-θ_t).

The NPG update can be derived by plugging in this approximation to Eq. <ref>, further approximating the _x,y∼π_θ(· |x) r(x,y) by its first order Taylor expansion around θ_t, and finding the root of the resulting quadratic form:

    θ_t+1 = θ_t +  η  F_t^†(_x, y∼π_θ_t(·|x)∇lnπ_θ_t(y|x) r(x,y) )
 where F_t^† is pseudo-inverse of F_t, and _x, y∼π_θ_t(·|x)∇lnπ_θ_t(y|x) r(x,y) is the standard policy gradient (i.e. REINFORCE <cit.>). As mentioned above, this update procedure can be understood as performing gradient updates in the local geometry induced by the Fisher information matrix, which ensures that we are taking small steps in policy space rather than in parameter space.
Conversely, unlike regular gradient descent methods (i.e., PG), NPG allows us to make large changes in the parameter space Θ, as long as the resulting two policies are close to each other in terms of KL divergence. This property allows NPG to make more aggressive and adaptive updates in the parameter space of the policy as well as be invariant to linear transformations of the parameters. Theoretically, <cit.> show that NPG with softmax parameterization converges at the 1/T rate in a dimension-free manner, provably faster than the standard PG under the same setup. Empirically, the superior convergence speed of NPG compared to that of PG was observed in its original exploration <cit.>, as well as in follow-up work like TRPO <cit.>. Critically, while elegant in theory, NPG, unfortunately, does not scale to modern generative models due to the need for computing the Fisher matrix inverse either explicitly or implicitly via the Hessian-vector matrix product trick.


=-1

Proximal Policy Optimization. To address the scalability of NPG, <cit.> proposes Proximal Policy Optimization (PPO). Rather than explicitly computing the KL divergence between policies or approximating it via a Taylor expansion, PPO takes a more direct route and uses clipped updates with the hope of controlling the action probability deviation from π_θ_t+1 to π_θ_t, i.e. 

    θ_t+1 := _θ_x, y∼π_θ_t(· | x)clip( π_θ(y|x) /π_θ_t(y|x)  ; 1-ϵ, 1+ϵ)  r(x,y).
 
Prima facie, this update follows the underlying intuition of NPG: allow big and adaptive changes in the policy's parameters θ, as long as the corresponding action probabilities do not change too much. This perhaps explains the superiority of PPO over vanilla REINFORCE in domains like continuous control. Unfortunately, under closer scrutiny, it becomes apparent that PPO-style clipped updates neither guarantee closeness to the prior policy nor have NPG-style adaptivity. While the clipping operator can set the gradient to be zero at samples (x,y) where π_θ_t+1(y|x) is much larger or smaller than π_θ_t(y|x), it cannot actually guarantee π_θ_t+1 staying close to π_θ_t, a phenomenon empirically observed in prior work <cit.>.
Furthermore, hard clipping is not adaptive – it treats all (x,y) equally and clips whenever the ratio is outside of a fixed range. In contrast, constraining the KL divergence to the prior policy allows one to vary the ratio π(y|x) / π_t(y|x) at different (x,y), as long as the total KL divergence across the state space is small. Lastly, clipping reduces the effective size of a batch of training examples and thus wastes training samples.


A  With a Cause. Our algorithm  addresses the limitations of NPG (scalability) and PPO (lack of conservativity or adaptivity) from above. First, unlike NPG, it does not rely on the Fisher information matrix at all and can easily scale to modern LLM applications, yet (as we will discuss below) can be interpreted as a generalization of NPG. Second, in contrast to PPO, it doesn't have unjustified heuristics and thus enjoys strong convergence and regret guarantees just like NPG. 











 §.§ Connections between  and MD / NPG



We now sketch a series of connections between  and the methods outlined above.








Exact  is Mirror Descent. First, to build intuition, we interpret our algorithm's behavior under the assumption that the least square regression optimization returns the exact Bayes Optimal solution (i.e., our learned predictor achieves zero prediction error everywhere): 

    ∀ x, y, y':   1/η(lnπ_θ_t+1(y|x)/π_θ_t(y|x) - lnπ_θ_t+1(y'|x)/π_θ_t(y'|x)) = r(x,y) - r(x,y')


Conditioned on Eq. <ref> being true, a few lines of algebraic manipulation reveals that there must exist a function c(x) which is independent of y, such that:

    ∀ x,y:   1/ηlnπ_θ_t+1(y|x)/π_θ_t(y|x) = r(x,y) + c(x).

Taking an exp on both sides and re-arrange terms, we get:

    ∀ x,y:   π_θ_t+1(y|x) ∝π_θ_t(y|x) exp( η r(x,y) ).

In other words, under the strong assumption that least square regression returns a point-wise accurate estimator (i.e., Eq. <ref>), we see the  recovers the exact MD update, which gives it (a) a fast 1/T convergence rate <cit.>, (b) conservativity, i.e., max_xKL( π_t+1(· | x) || π_t(· | x)  ) is bounded as long as max_x,y |r(x,y)| is bounded, and (c) monotonic policy improvement via the NPG standard analysis <cit.>.






NPG is Approximate  with Gauss-Newton Updates. We provide another interpretation of  by showing that NPG (Eq. <ref>) can be understood as a special case of  where the least square problem in Eq. <ref> is approximately solved via a single iteration of the Gauss-Newton algorithm.

As for any application of Gauss-Newton, we start by approximating our predictor 1/ηlnπ_θ(y|x) / π_θ_t(y|x) by its first order Taylor expansion at θ_t:  =-1

    1/η( lnπ_θ(y|x)  - lnπ_θ_t(y|x) ) ≈1/η∇_θlnπ_θ_t(y|x)^⊤ (θ - θ_t),
  where ≈ indicates that we ignore higher order terms in the expansion. If we δ := θ - θ_t and replace 1/η( lnπ_θ(y|x)  - lnπ_θ_t(y|x) ) by its above first order approximation in Eq. <ref>, we arrive at the following quadratic form: 

    min_δ_x∼ρ, y∼π_θ_t(·|x), y'∼(·|x)( 1/η( ∇_θlnπ_θ_t(y|x) - ∇_θlnπ_θ_t(y'|x) )^⊤δ - ( r(x, y) - r(x, y') ) )^2.

Further simplifying notation, we denote the uniform mixture of π_t and  as π_mix(· | x) := (π_t(·|x)  + (· | x) ) / 2 and the Fisher information matrix F_t averaged under said mixture as:

    F_t = 
    _x∼ρ, y∼π_mix(·|x)[ ∇_θlnπ_θ_t(y|x) (∇_θlnπ_θ_t(y|x) )^⊤].
  
Solving the above least square regression to obtain a minimum norm solution, we have the following claim. 
 The minimum norm minimizer δ^⋆ of the least squares problem in Eq. <ref> recovers an advantage-based variant of the NPG update:

    δ^⋆ :=  η F_t^†( _x∼ρ,y∼π_mix(·|x)∇_θlnπ_θ_t(y|x) [ A^π_t(x,y) ]  ),
 where F_t^† is pseudo-inverse of F_t, and the advantage is defined as A^π_t(x,y):= r(x,y) - _y'∼π_t(·|x) r(x,y). 

The proof of this claim is deferred to Appendix <ref>. Observe that in , we never explicitly compute the advantage A^π_t. However, applying Gauss-Newton to our objective leads to an advantage-based NPG (rather than the traditional Q-function based NPG, e.g., Q-NPG from <cit.>) which indicates that predicting reward difference has an implicit variance reduction effect, as by definition, an advantage function includes a value function baseline.
[Note that the original form of NPG is on-policy <cit.>, i.e., the expectations under π_t. Our formulation is more general: when set = π_t, a Gauss-Newton step will recover the original on-policy form of NPG from <cit.>.  More recent works have extended NPG beyond on-policy (e.g., <cit.>).]





 §.§ Extending  to General Preferences

In the above discussion, we assume we are given access to a ground-truth reward function. However, in the generative model fine-tuning applications of RL, we often need to learn from human preferences, rather than rewards. This shift introduces a complication: not all preferences can be rationalized by an underlying utility function. In particular, intransitive preferences which are well-known to result from aggregation of different sub-populations or users evaluating different pairs of items on the basis of different features <cit.> cannot be accurately captured by a single reward model. To see this, note that if we have a ≻ b, b ≻ c, and c ≻ a, it is impossible to have a reward model that simultaneously sets r̂(a) > r̂(b), r̂(b) > r̂(c), and r̂(c) > r̂(a). As we increase the space of possible choices to that of all possible prompt completions, the probability of such intransitivities sharply increases <cit.>, as reflected in the high levels of annotator disagreement in LLM fine-tuning datasets <cit.>. Thus, rather than assuming access to a reward model, in such settings, we assume access to a preference model <cit.>. 


  §.§.§ A Game-Theoretic Perspective on Learning from Preferences

More specifically, for any tuple (x,y,y'), we assume we have access to 𝒫(y ≻ y' | x): the probability that y is preferred to y'. We then define our preference model l as

    l(x, y, y') ≜ 2 ·𝒫(y ≻ y' | x) - 1.


Observe that l(x,y,y') ∈ [-1, 1] is skew-symmetric, i.e., l(x,y,y) = 0, l(x,y,y') + l(x, y', y) = 0 for all x∈, y,y'∈. If the learner can only receive a binary feedback o∈{0,1} indicating the preference between y and y', we assume o is sampled from a Bernoulli distribution with mean 𝒫(y ≻ y' | x), where o=1 means that y is preferred over y' and 0 otherwise.  

Given access to such a preference model, a solution concept to the preference aggregation problem with deep roots in the social choice theory literature <cit.> and the dueling bandit literature <cit.> is that of a minimax winner (MW) : the Nash Equilibrium strategy of the symmetric two-player zero-sum game with l as a payoff function. In particular, due to the skew-symmetric property of l, <cit.> proved that there exists a policy  such that 

    max_π_x∼ρ,y∼π(·|x), y'∼(·|x)[l(x,y,y')]=min_π_x∼ρ,y∼(·|x),y'∼π(·|x)[l(x,y,y')].

This implies that (,) is a Nash Equilibrium <cit.>. As is standard in game solving, our objective is to obtain an -approximate MW  measured by the duality gap (DG):

    ():=max_π_x∼ρ,y∼π(·|x), y'∼(·|x)[l(x,y,y') ]-min_π_x∼ρ,y∼(·|x),y'∼π(·|x)[l(x,y,y')]≤.

In the following discussion, we will use l(x,y,π) to denote _y'∼π(·|x)[l(x,y,y')] and l(π,π') to denote _x∼ρ, y∼π(·|x),y'∼π'(·|x)[l(x,y,y')] for notational convenience.



  §.§.§ Self-Play Preference Optimization (SPO) with  as Base Learner

We can straightforwardly extend  to the general preference setting via an instantiation of the Self-Play Preference Optimization (SPO) reduction of <cit.>. In short, <cit.> prove that rather than performing adversarial training, we are able to perform a simple and stable self-play procedure while retaining strong theoretical guarantees. Practically, this corresponds to sampling at leas two completions from the current policy, querying a learned preference / supervisor model on each pair, and using the win rate for each completion as its reward. We will now describe how we can adapt  to this mode of feedback.

Assuming that we can query the preference oracle l(x,y,y') at will, we can modify the least square objective Eq. (<ref>) to

    θ_t+1 := _θ∑_x,y,y',y”∈_t(1/η(lnπ_θ(y|x)/π_θ_t(y|x) - lnπ_θ(y'|x)/π_θ_t(y'|x)) - ( l(x, y, y”) - l(x, y', y”) )  )^2
 where x∼ρ, y∼π_t(· | x),y”∼π_t(· | x), y'∼(· | x). When the exact value of l(x,y,y') is unavailable but only a binary preference feedback o_y,y'∈{0,1} sampling from Bernoulli with mean l(x,y,y') is available, we can just replace l(x, y, y”) - l(x, y', y”) by o_y,y' - o_y',y”.     It is easy to see that the Bayes optimal of the above least square regression problem is equal to:

    _y”∼π_t(· | x)  l(x, y, y”) - _y”∼π_t(· | x)  l(x, y', y”)  =   l(x, y, π_t) -  l(x, y', π_t).
 
<cit.> define an iteration-dependent reward r_t(x,y) := _y”∼π_t(· | x)  l(x, y, y”)=l(x,y,π_t). Thus, the above regression problem can be understood as an extension of  to the setting where the reward function changes at each iteration t. <cit.> shows that running the exact MD (Eq. <ref>) with this iteration-dependent reward function r_t leads to fast convergence to an approximate Minimax Winner, a property that we will use to provide the regret bound of  in the general preference setting while accounting for nonzero mean squared error. 









§ THEORETICAL ANALYSIS


In the previous section, we interpret  as the exact MD and show its convergence by assuming that least square regression always returns a predictor that is accurate everywhere. While such an explanation is simple and has also been used in prior work, point-wise out-of-distribution generalization is an extremely strong condition and is significantly beyond what a standard supervised learning method can promise. 
In this section, we significantly relax this condition via a reduction-based analysis: =-1


As long as we can solve the regression problems well in an in-distribution manner,  can compete against any policy covered by the training data distributions. =-1



Formally, we assume the following generalization condition holds on the regressors we find.

[Regression generalization bounds] Over T iterations, assume that for all t, we have:

    _x∼ρ, y∼π_t(· | x), y'∼(· | x)( 1/η(lnπ_θ_t+1(y|x)/π_θ_t(y|x) - lnπ_θ_t+1(y'|x)/π_θ_t(y'|x)) -  ( r(x, y) - r(x, y') )  )^2 ≤ϵ,
 for some ϵ.


Intuitively, this assumption is saying that there is a function in our class of regressors that is able to accurately fit the difference of rewards. Recall that our class of regressors is isomorphic to our policy class. Therefore, as long as our class of policies is expressive, we would expect this assumption to hold with small ϵ. For all domains we consider, our policy class is a flexible set of generative models (e.g. Transformer-based LLMs or diffusion models). Thus, we believe it is reasonable to believe this assumption holds in practice – see Figure <ref> in Appendix <ref> for empirical evidence of this point and Example <ref> for more discussion.


More formally, the above assumption bounds the standard in-distribution generalization error (v.s. the point-wise guarantee in Eq. <ref>) of a well-defined supervised learning problem: least squares regression. The generalization error ϵ captures the possible errors from the learning process for θ_t+1 and it could depend on the complexity of the policy class and the number of samples used in the dataset _t. For instance, when the the function lnπ - lnπ' induced by the log-difference of two policies (π,π') are rich enough (e.g., policies are deep neural networks) to capture the reward difference, then ϵ in this assumption converges to zero as we increase the number of training data.
Note that while ϵ can be small, it does not imply that the learned predictor will have a small prediction error in a point-wise manner – it almost certainly will not.




 
One simple example is when π(y|x) ∝exp( θ^⊤ϕ(x,y) ) for some features ϕ(x,y). In this case,  ln( π(y|x) /π_t(y|x) ) -ln( π(y'|x) /π_t(y'|x) ) =  (θ - θ_t)^⊤( ϕ(x, y) - ϕ(x, y') ), which means that our regression problem in Eq. <ref> is a classic linear regression problem. When the reward r(x,y) is also linear in feature ϕ(x,y), then Eq. <ref> is a well-specified linear regression problem, and ϵ typically scales in the rate of O( d / |_t| )  with d being the dimension of feature ϕ. 

We can extend the above example to the case where ϕ is the feature corresponding to some kernel, e.g., RBF kernel or even Neural Tangent Kernel, which allows us to capture the case where π is a softmax wide neural network with the least square regression problem solved by gradient flow. The error ϵ again scales poly( d / |_t|), where d is the effective dimension of the corresponding kernel.



We now define the concentrability coefficient <cit.> that quantifies how the training data distribution is covering a comparator policy. 

Data Coverage.
Recall that the base distribution  can be some behavior policy, which in RLHF can be a human labeler, a supervised fine-tuned policy (SFT), or just the current learned policy (i.e., on-policy). Given a test policy π, we denote by C_μ→π the concentrability coefficient, i.e. =-1

    C_→π = max_x,yπ(y|x) /(y|x) .
 
We say  covers π if C_→π < +∞.



Our goal is to bound the regret between our learned policies and an arbitrary comparator π^* (e.g. the optimal policy if it is covered by ) using ϵ and the concentrability coefficient defined in Eq. <ref>. 
The following theorem formally states the regret bound of our algorithm.
 Under Assumption <ref>, after T many iterations, with a proper learning rate η, among the learned policies π_1,…, π_T, there must exist a policy π̂, such that:

    ∀π^*:  _x∼ρ, y∼π^*(· | x) r(x,y) - _x∼ρ, y∼π̂(· | x) r(x,y) ≤ O(   √(1/ T ) +  √( C_→π^*ϵ). ).

Here the O-notation hides problem-dependent constants that are independent of ϵ, C_→π^*, T.
 


The above theorem shows a reduction from RL to supervised learning — as long as supervised learning works (i.e., ϵ is small), then  can compete against any policy π^* that is covered by the base data distribution . In the regret bound, the 1/√(T) comes from Mirror Descent style update, and C_→π^*ϵ captures the cost of distribution shift: we train our regressors under distribution π_t and , but we want the learned regressor to predict well under π^*. Similar to the NPG analysis from <cit.>, we now have a slower convergence rate 1/√(T), which is due to the fact that we have approximation error from learning. 
Such an agnostic regret bound — being able compete against any policy that is covered by training distributions – is the strongest type of agnostic learning results known in the RL literature, matching the best of what has appeared in prior policy optimization work including PSDP <cit.>, CPI <cit.>, NPG <cit.>, and PC-PG <cit.>.  While in this work, we use the simplest and most intuitive definition of coverage – the density ratio-based definition in Eq. <ref> – extension to more general ones such as transfer error <cit.> or concentrability coefficients that incorporate function class (e.g., <cit.>) is straightforward. We defer the proof of the above theorem and the detailed constants that we omitted in the O notation to Appendix <ref>.

 


 §.§ Extension to General Preferences


Extending the above analysis to the general preference case is straightforward except that it requires a stronger coverage condition. This is because we want to find a Nash Equilibrium, which requires a comparison between the learned policy against all the other policies. 
Results from the Markov Game literature <cit.> and <cit.> have shown that the standard single policy coverage condition used in single-player optimization is provably not sufficient. In particular, they propose using a notion of unilateral concentrability for efficient learning, which can be defined as 

    C_𝗎𝗇𝗂,μ:=max_π,x,y,y”(y|x)π(y”|x)/μ(y|x)μ(y”|x),

in the general preference setting. Notably, the above unilateral concentrability coefficient C_𝗎𝗇𝗂,μ is equivalent to C_μ:=max_π,x,yπ(y|x)/μ(y|x) since
 C_μ≤ C_𝗎𝗇𝗂,μ≤ C_μ^2.
Therefore in the following discussion, we will use C_μ as the coverage condition.
In addition, we also assume the generalization error of the regression problem is small,  =-1
[Regression generalization bounds for general preference] Over T iterations, assume that for all t, we have:

    _x∼ρ, y∼π_t(· | x), y'∼(· | x)( 1/η(lnπ_θ_t+1(y|x)/π_θ_t(y|x) - lnπ_θ_t+1(y'|x)/π_θ_t(y'|x)) -  ( l(x,y,π_t)-l(x,y',π_t) )  )^2≤ϵ,
 for some ϵ.



Under the above coverage condition and generalization bound, we can show that   is able to learn an approximate Minimax Winner:
 

With assumption <ref>, after T many iterations, with a proper learning rate η, the policy =({π_t}_t=1^T) satisfies that:

    () ≤ O(   √(1/ T ) +  √( C_ϵ). ).

Here the O-notation hides problem-dependent constants that are independent of ϵ, C_, T.
 
We defer the proof to Appendix <ref>. Note that the coverage condition here is much stronger than the single policy coverage condition in the RL setting. We conjecture that this is the cost one has to pay by moving to the more general preference setting and leaving the investigation of the necessarily coverage condition for future work.




§ EXPERIMENTS


The implementation of  follows Algorithm <ref>. In each iteration,  collects a dataset _t = { x, y, y' }, where x∼ρ, y∼π_t(· | x), y'∼(· | x). Subsequently,  optimizes the least squares regression problem in Eq. <ref> through gradient descent with AdamW <cit.>. We choose = π_t such that both y and y' are generated by the current policy. We empirically assess 's performance on both natural language generation and text-guided image generation.



 §.§ Natural Language Generation




  
Baselines: We compare  with baseline RL algorithms, PPO <cit.>, Direct Preference Optimization (DPO) <cit.>, and REINFORCE <cit.> and its multi-sample extension, REINFORCE Leave-One-Out (RLOO) <cit.>. The REINFORCE method is implemented with a moving average baseline of the reward. We include two variants of RLOO with two (k=2) and four (k=4) generations per prompt. 



  
Dataset: We use the  summarization dataset <cit.>[Dataset available at <https://github.com/openai/summarize-from-feedback>] to train the model to generate summaries of Reddit posts based on human preference data. The dataset comprises human reference summaries and preference data. Following prior work <cit.>, we train the DPO baseline on the preference dataset, while conducting online RL (PPO, RLOO, ) on the human reference dataset. We set the maximum context length to 512 and the maximum generation length to 53 to ensure all references in the dataset can be generated. Additional dataset details are in Appendix <ref>.



  
Models: We include results with three different model sizes: 1.4B, 2.8B, and 6.9B. Each model is trained with a supervised fine-tuned (SFT) model and/or a reward model (RM) of the same size. For SFT models, we train a Pythia 1.4B <cit.>[HuggingFace Model Card: EleutherAI/pythia-1.4b-deduped] model for 1 epoch over the dataset with human references as labels, and use the existing fine-tuned 2.8B[HuggingFace Model Card: vwxyzjn/EleutherAI_pythia-2.8b-deduped__sft__tldr] and 6.9B[HuggingFace Model Card: vwxyzjn/EleutherAI_pythia-6.9b-deduped__sft__tldr] models. For reward models, we train a Pythia 1.4B parameter model for 1 epoch over the preference dataset and use the existing reward models with 2.8B[HuggingFace Model Card: vwxyzjn/EleutherAI_pythia-2.8b-deduped__reward__tldr] and 6.9B[HuggingFace Model Card: vwxyzjn/EleutherAI_pythia-6.9b-deduped__reward__tldr] parameters. For both  and baseline methods using 1.4B and 2.8B parameters, we trained the policy and/or the critic using low-rank adapters (LoRA) <cit.> on top of our SFT and/or reward model respectively. For the 6.9B models, we perform full-parameter training. More details about the hyperparameters are described in Appendix <ref>.



  
Evaluation: We evaluate each method by its balance between reward model score and KL-divergence with the reference policy, testing the effectiveness of the algorithm in optimizing the regularized RL object. To evaluate the quality of the generation, we compute the winrate <cit.> against human references using GPT4[Specific API checkpoint used throughout this section: ] <cit.>. The winrate is computed from a randomly sampled subset (10%) of the test set with a total of 600 samples. The prompt used to query GPT4 as well as an example response is shown in Appendix <ref>.



  §.§.§ Quality Analysis












Table <ref> presents a comparison between  and SFT, PPO, and DPO for 1.4B and 2.8B models trained with LoRA. We calculate the KL-divergence (KL(π || π_ref)) using the SFT policy of the corresponding size as the reference for all models. Notably,  outperforms all the baselines on RM score across all model sizes with a slightly larger KL than PPO. In addition,  achieves the highest winrate under GPT4 when evaluated against human references, indicating the benefit of regressing the relative rewards. Example generations of 2.8B  are included in Appendix <ref>. We also perform full-parameter training for 6.9B models and the winrates are shown in Table <ref>. We can observe that  still outperforms all of the baselines while , PPO, and RLOO (k=4) have comparable performances (but we will soon show in the next section that  is more tractable in computation and memory than PPO and RLOO with k=4). An ablation analysis on parameter η is in Appendix <ref>.

The trade-off between the reward model score and KL-divergence is shown in Figure <ref>. We evaluate the 2.8B  and PPO every 400 gradient updates during training for 8,000 updates. The sample complexity of each update is held constant across both algorithms for fair comparison. For the left plot, each point represents the average divergence and score over the entire test set, and the eclipse represents the confidence interval with 2 standard deviations. As observed previously, PPO exhibits lower divergence, whereas  shows higher divergence but is capable of achieving larger RM scores. Notably, towards the end of the training (going to the right part of the plot),  and PPO have similar KL and RM scores. For the right plot in Figure <ref>, we analyze a single checkpoint for each algorithm at the end of training. For each algorithm, we group every generation from the test set by its KL distribution into 10 equally sized bins and calculate the average of the corresponding RM score for each bin. We can see that  achieves higher RM scores for generations with small divergence while requiring larger divergence for generations with the highest scores.



  §.§.§ Runtime & Memory Analysis


We analyze the runtime and peak memory usage for 2.8B models using PPO, DPO, RLOO, and . The runtime includes both the generation time and the time required for policy updates. Both runtime and peak memory usage are measured on A6000 GPUs using the same hyperparameters detailed in Appendix <ref>. The methods in the plots are arranged in ascending order based on winrates. To the right of the dashed line, PPO, RLOO (k=4), and  have the highest winrates, which are comparable among them.

While DPO and REINFORCE require less time and memory, their performance does not match up to , as discussed in Section <ref>. RLOO (k=2) has similar runtime and memory usage as  since we set = π_t, making  also generate twice per prompt. However, RLOO (k=2) has worse performance than . Compared to PPO and RLOO (k=4),  demonstrates shorter runtimes and lower peak memory usage. PPO is slow and requires more memory because it needs to update both two networks: policy network and value network.  RLOO (k=4) requires generating 4 responses per prompt which makes it slow and less memory efficient. Compared to the two baselines PPO and RLOO (k=4) that achieve similar winrates as , we see that  is more computationally tractable.  is also noticeably simpler to implement than PPO since it does not learn value networks or compute the advantage estimation.





 §.§ Image Generation

We also consider the setting of image generation, where, given a consistency model <cit.> and a target reward function, we seek to train the consistency model to output images which garner a higher reward. Specifically, we compare  and PPO under the RLCM framework <cit.>.



  
Baselines: We compare  to a clipped, policy gradient objective <cit.> with the aim to optimize aesthetic quality to obtain high reward from the LAION aesthetic score predictor <cit.>. This baseline does not use critics or GAE for advantage estimates. However, the clipping objective is clearly motivated by PPO, and thus, we simply name this baseline as PPO in this section. 



  
Dataset: We use 45 common animals as generation prompts similar to <cit.>[Dataset available at <https://github.com/Owen-Oertell/rlcm>]. 



  
Models: We use the latent consistency model <cit.> distillation of the Dreamshaper v7 model[Huggingface model card: SimianLuo/LCM_Dreamshaper_v7], a finetune of stable diffusion <cit.>.





  
Evaluation:  We evaluate PPO and  on its reward under the LAION aesthetic reward model for an equal number of reward queries/samples generated and an equal number of gradient updates. The aesthetic predictor is trained to predict human-labeled scores of images on a scale of 1 to 10. Images that tend to have the highest reward are artwork. Following the recommendations of <cit.>, we report the inter-quartile mean with 95% confidence intervals for our reported results across three random seeds. 



 §.§ Quality Analysis



Figure <ref> shows  optimizes the consistency model faster during the beginning of training but eventually achieves similar performance to that of PPO. For our experiments, we tuned both batch size and learning rate for our algorithms, testing batch sizes of [4, 8, 16] per gpu and learning rates [1e-4, 3e-4, 6e-4, 1e-3]. Note, the main difference in implementation between PPO and  is the replacement of the clipped PPO objective with our regression objective.




Qualitatively, we observe that eventually, both PPO and  start to generate good-looking images but ignore the text prompt entirely.  However, from just optimizing the reward function perspective, this behavior is not surprising since the objective does not encourage the maintenance of the consistency between the text prompt and the generated image.  
To maximize LAION-predicted aesthetic quality, both  and PPO transform a model that produces plain images into one that produces artistic drawings. We found across multiple seeds that  produced lush backgrounds when compared to PPO's generations. Please see Appendix <ref> for more examples of generated images.



§ RELATED WORK

Policy Gradients. Policy gradient (PG) methods <cit.> are a prominent class of RL algorithms due to their direct, gradient-based policy optimization, robustness to model mis-specification <cit.>, and scalability to modern AI applications from fine-tuning LLMs <cit.> to optimizing text-to-image generators <cit.>. 

Broadly speaking, we can taxonomize PG methods into two families. The first family is based on REINFORCE <cit.> and often includes variance reduction techniques <cit.>. While prior work by <cit.> has shown that REINFORCE-based approaches can outperform more complex RL algorithms like PPO on LLM fine-tuning tasks like , we find that a properly optimized version of PPO still out-performs a REINFORCE baseline. The second family is adaptive PG techniques that precondition the policy gradient (usually with the inverse of the Fisher Information Matrix) to ensure it is covariant to re-parameterizations of the policy, which include NPG <cit.> and its practical approximations like TRPO <cit.> and PPO <cit.>. Intuitively, the preconditioning ensures that we make small changes in terms of action distributions, rather than in terms of the actual policy parameters, leading to faster and more stable convergence. Unfortunately, computing and then inverting the Fisher Information Matrix is computationally intensive and therefore we often resort to approximations in practice, as done in TRPO. However, these approximations are still difficult to apply to large-scale generative models, necessitating even coarser approximations like PPO. In contrast,  does not need any such approximations to be implemented at scale, giving us a much closer connection between theory and practice.

Reward Regression. The heart of  is a novel reduction from RL to iterative squared loss regression. While using regression to fit either the reward <cit.> or the value <cit.> targets which are then used to extract a policy have previously been explored, our method instead takes a page from DPO <cit.> to implicitly parameterize the reward regressor in terms of the policy. This collapses the two stage procedure of prior methods into a single regression step.







Preference Fine-Tuning (PFT) of Generative Models. RL has attracted renewed interest due to its central role in “aligning” language models  – i.e., adapting their distribution of prompt completions towards the set of responses preferred by human raters. 

One family of techniques for PFT, often referred to as Reinforcement Learning from Human Feedback (RLHF) involves first fitting a reward model (i.e. a classifier) to the human preference data and then using this model to provide reward values to a downstream RL algorithm (often PPO) <cit.>. LLMs fine-tuned by this procedure include GPT-N <cit.>, Claude-N <cit.>, and Llama-N <cit.>. Similar approaches have proved beneficial for tasks like summarization <cit.>, question answering <cit.>, text-to-image generation <cit.>, and instruction following <cit.>. =-1

Another family of techniques for PFT essentially treats the problem as supervised learning and uses a variety of ranking loss functions. It includes DPO <cit.>, IPO <cit.>, and KTO <cit.>. These techniques are simpler to implement as they remove components like an explicit reward model, value network, and on-policy training from the standard RLHF setup. However, recent work finds their performance to be lesser than that of on-policy methods <cit.>, which agrees with our findings. This is perhaps caused by their lack of interaction during training, leading to the well-known covariate shift/compounding error issue <cit.> and the associated lower levels of performance.







The third family of PFT techniques combines elements from the previous two: it involves running an offline algorithm iteratively, collecting on-policy preference feedback from either a supervisor model <cit.> or from a preference model fit on human data <cit.>. All of these approaches can be considered instantiations of the general SPO reduction proposed by <cit.>, which itself can be thought of as a preference-based variant of DAgger <cit.>. Recent work by <cit.> confirms the empirical strength of these techniques. Our approach fits best into this family of techniques – we also iteratively update our model by solving a sequence of supervised learning problems over on-policy datasets. However,  comes with several key differentiating factors from the prior work. First, we can run  with datasets consisting of a mixture of on-policy and off-policy data with strong guarantees, enabling hybrid training, as previously explored in the RL <cit.> and inverse RL <cit.> literature. Second, unlike all of the aforementioned works that regularize to the initial policy π_0 during updates, we perform conservative updates by regularizing π_t+1 to π_t. Thus, for the prior work, it is difficult to prove convergence or monotonic improvement as the current policy can just bounce around a ball centered at π_0, a well-known issue in the theory of approximate policy iteration <cit.>. In contrast, by incorporating the prior policy's probabilities into our regression problem, we are able to prove stronger guarantees for . =-1



§ SUMMARY AND FUTURE WORK

In summary, we propose , an RL algorithm that reduces the problem of RL to solving a sequence of relative reward regression problems on iteratively collected datasets. In contrast to policy gradient approaches that require additional networks and heuristics like clipping to ensure optimization stability,  requires that we can drive down training error on a least squares problem. This makes it strikingly simple to implement and scale. In theory,  matches the best guarantees we have for RL algorithms in the agnostic setting, while in practice,  is able to match and sometimes outperform methods that are far more complex to implement or expensive to run across both language modeling and guided image generation tasks.

There are several open questions raised by our work. The first is whether using a loss function other than square loss (e.g. log loss or cross-entropy) could lead to better performance in practice <cit.> or tighter bounds (e.g. first-order / gap-dependent) in theory <cit.>. The second is whether, in the general (i.e. non-utility-based) preference setting, the coverage condition assumed in our analysis is necessary – we conjecture it is. Relatedly, it would be interesting to explore whether using preference (rather than reward) models to provide supervision for  replicates the performance improvements reported by <cit.>. Third, while we focus primarily on the bandit setting in the preceding sections, it would be interesting to consider the more general RL setting and explore how offline datasets can be used to improve the efficiency of policy optimization via techniques like resets <cit.>.











§ PROOF OF CLAIM <REF>




We prove claim <ref> in this section. We start from deriving the Fisher information matrix. 

    F_t    := 1/η^2_x,y∼π_t, y'∼(∇_θlnπ_θ_t(y|x) - ∇_θlnπ_θ_t(y'|x))( ∇_θlnπ_θ_t(y|x) - ∇_θlnπ_θ_t(y'|x) )^⊤
        = 2/η^2_x, y∼π_mix∇_θlnπ_θ_t(y|x) ∇_θlnπ_θ_t(y|x)^⊤
  
where the last equality uses the fact that cross terms from completing the square are zero. Now recall Eq. <ref> which is a ordinarly least square regression problem. The minimum norm solution of the least square regression problem is:

    δ    = (η/2) F̃_t^†( _x,y∼π_t, y'∼(  ∇_θlnπ_θ_t(y|x) - ∇_θlnπ_θ_t(y'|x)  ) ( r(x,y) -r(x,y'))    )  
        = (η/2) F̃_t^†( _x,y∼π_t [ ∇_θlnπ_θ_t(y|x)  r(x,y)]   + _x,y'∼[ ∇_θlnπ_θ_t(y'|x)  r(x,y')] 
            - _x,y∼π_t y'∼∇_θlnπ_θ_t(y'|x)  r(x,y) ) 
        = (η/2) F̃_t^†( _x,y∼π_t [ ∇_θlnπ_θ_t(y|x)   [ r(x,y) - _y'∼π_t(·|x) r(x,y')]   
                + _x,y∼[ ∇_θlnπ_θ_t(y|x) [ r(x,y) - _y'∼π_t(·|x) r(x,y') ] ) 
        = (η) F̃_t^†( _x,y∼ (π_t+)/2 [ ∇_θlnπ_θ_t(y|x)   [  A^π_t(x,y)]  )
 where we again use the fact that  _y∼π_θ_t(· | x)∇_θlnπ_θ_t(y|x) g(x) = 0 for any function g(x), and we define Advantage A^π(x,y) := r(x,y) - _y'∼π(·|x) r(x,y'). 



§ PROOF OF THEOREM <REF>


In this section, we provide the proof of theorem <ref>. For notation simplicity, throughout the proof, we denote π_t for π_θ_t, and define f_t(x,y):= 1/ηlnπ_t+1(y|x)/π_t(y|x).

The following lemma shows that the learned function f_t can predict reward r well under both π_t and  up to terms that are y-independent. 


Consider any t∈ [T]. Define Δ(x,y) = f_t(x,y) - r(x,y). Define Δ_π_t(x) = _y∼π_t(· | x)Δ(x,y) and Δ_(x) = _y∼(· | x)Δ(x,y).
Under assumption <ref>, for all t, we have the following: 

    _x, y∼π_t(· | x)( f_t(x,y) -  r(x,y) - Δ_π_t(x) )^2 ≤ϵ,  
       _x, y∼(· | x)( f_t(x,y) -  r(x,y) - Δ_(x) )^2 ≤ϵ,
       _x( Δ_π_t(x) - Δ_(x) )^2 ≤ϵ.



From assumption <ref>, we have:

    _x, y_1∼π_t, y_2 ∼(  f_t(x,y_1) - Δ_π_t(x) - r(x,y_1)  - ( f_t(x,y_2) - Δ_(x) - r(x,y_2)  ) + Δ_π_t(x) - Δ_(x)     )^2 
        = _x,y_1∼π_t( f_t(x,y_1) - Δ_π_t(x) -  r(x,y_1)  )^2 + _x,y_2∼(  f_t(x,y_2) - Δ_(x) - r(x,y_2) )^2  
        - 2 _x,y_1∼π_t, y_2 ∼(  f_t(x,y_1) - Δ_π_t(x) -  r(x,y_1)  )  (  f_t(x,y_2) - Δ_(x) -  r(x,y_2) ) 
        + 2 _x,y_1∼π_t(  f_t(x,y_1) - Δ_π_t(x) -  r(x,y_1)  ) (Δ_π_t(x) - Δ_(x)) 
        - 2 _x,y_2∼π_t(  f_t(x,y_2) - Δ_(x) -  r(x,y_2)  ) (Δ_π_t(x) - Δ_(x)) + _x (Δ_1(x) - Δ_2(x))^2 
        = _x,y_1∼π_t(   f_t(x,y_1) - Δ_π_t(x) -  r(x,y_1)  )^2 + _x,y_2∼(  f_t(x,y_2) - Δ_(x) -  r(x,y_2) )^2  
            +  _x (Δ_π_t(x) - Δ_(x))^2  ≤ϵ.
In the  above, we first complete the square, and then we only keep terms that are not necessarily zero. 
Since all the remaining three terms are non-negative, this concludes the proof.


By the definition of f_t, we have Δ(x,y) =1/ηlnπ_t+1(y|x)  /π_t(y|x)  - r(x,y). Taking exp on both sides, we get:

    ∀ x,y:  π_t+1(y|x) = π_t(y|x) exp(  η  ( r(x,y) + Δ(x,y)  ) ) = π_t(y|x) exp( η (  r(x,y) + Δ(x,y) - Δ_(x) )  )  /exp ( - ηΔ_(x) )

Denote g_t(x,y) : = r(x, y) + Δ(x,y) - Δ_(x), and the advantage A_t(x,y) = g_t(x,y) - _y'∼π_t(· | x)  g_t(x,y'). 
We can  rewrite the above update rule as:

    ∀ x,y:  π_t+1(y | x) ∝π_t(y|x) exp( η A_t(x,y) )

In other words, the algorithm can be understood as running MD on the sequence of A_t for t=0 to T-1.  The following lemma is the standard MD regret lemma. 
 Assume max_x,y,t|A_t(x,y)| ≤ A ∈^+, and π_0(· | x) is uniform over . Then with η = √(ln(|| )  / (A^2 T)),  for the sequence of policies computed by , we have:

    ∀π, x:  ∑_t=0^T-1_y∼π(· | x) A_t(x,y) ≤ 2 A √(ln(||) T).


 For completeness, we provide the proof here. 
Start with π_t+1(y | x) = π_t(y|x) exp( η A_t(x,y) ) / Z_t(x) where Z_t(x) is the normalization constant, taking log on both sides, and add _y∼π(· | x), we have:

    -KL( π(· | x) || π_t+1(· | x)  ) = -KL( π(· | x) ||π_t(· | x) ) + η_y∼π(· | x) A_t(x,y)  - _y∼π(· | x)ln Z_t(x).
 Rearrange terms, we get:

    - KL( π(· | x) ||π_t(· | x) )  + KL( π(· | x) || π_t+1(· | x)   = _y∼π(· | x)[ - η A_t(x,y)  + ln Z_t(x)  ]

For ln Z_t(x), using the condition that η≤ 1/A, we have η A_t(x,y) ≤ 1, which allows us to use the inequality exp(x) ≤ 1 + x + x^2 for any x≤ 1, which lead to the following inequality:

    ln Z_t(x)      = ln( _y∼π(· | x)exp( η A_t(x,y))  ) 
       ≤ln( ∑_yπ_t(y | x) ( 1 + η A_t(x,y) + η^2 A_t(x,y)^2 ) ) 
       ≤ln( 1 + 0 +  η^2 A^2  ) ≤η^2 A^2,
 where the last inequality uses ln(1+x) ≤ x, and we used the fact that _y∼π_t(x) A_t(x,y) = 0 due to the definition of advantage A_t. Thus, we have:

    - KL( π(· | x) ||π_t(· | x) )  + KL( π(· | x) || π_t+1(· | x)  ≤ - _y∼π(· | x) [ A_t(x,y)] + η^2 A^2.

Sum over all iterations and do the telescoping sum, we get:

    ∑_t=0^T-1_y∼π(· | x) A_t(x,y) ≤KL( π(· | x) || π_0(· | x))  / η+ T η A^2 ≤ln( |  |)  / η + T η A^2.
 With η =  √(ln(||)  / (A^2 T)), we conclude the proof. 
 

With the above, now we are ready to conclude the proof of the main theorem. 
 
Consider a comparator policy π^*.  We start with the performance difference between π^* and the uniform mixture policy π̅:= ∑_t=0^T-1π_t / T: 

    1/T∑_t=0^T-1( _x, y∼π^*(· | x) r(x,y) -_x, y∼π_t(· | x) r(x,y) ) = 1/T∑_t=0^T-1_x, y∼π^*(· | x)( A^π_t(x,y) ),
 where we define the real advantage A^π_t(x,y) := r(x,y) -_y∼π_t(· | x) r(x,y). Continue, we have:

    1/T∑_t=0^T-1_x, y∼π^*(· | x)( A^π_t(x,y) ) 
        = 1/T∑_t=0^T-1_x, y∼π^*(· | x)( A_t(x,y) ) + 1/T∑_t=0^T-1_x, y∼π^*(· | x)( A^π_t(x,y)  - A_t(x,y) ) 
       ≤ 2 A √(ln (||)  /T) +  1/T∑_t=0^T-1√(_x_y∼π^*(· |x ) ( A^π_t(x,y)  - A_t(x,y) )^2  )
 where the last inequality uses Lemma <ref>.  We now just need to bound _y∼π^*(· |x ) ( A^π_t(x,y)  - A_t(x,y) )^2. 

    _x_y∼π^*(· |x ) ( A^π_t(x,y)  - A_t(x,y) )^2      = _x_y∼(· | x)π^*(y|x) /(y|x) ( A^π_t(x,y)  - A_t(x,y) )^2  
       ≤ C_π^*_x, y∼(· | x) ( A^π_t(x,y)  - A_t(x,y) )^2
 where the last inequality uses the definition of concentrability coefficient C_π^*.
We now bound _x, y∼(· | x) ( A^π_t(x,y)  - A_t(x,y) )^2. Recall the definiton of A_t from Lemma <ref>. 

    _x, y∼(· | x) ( A^π_t(x,y)  - A_t(x,y) )^2  
        =  _x, y∼(· | x) ( r(x,y) - _y'∼π_t(· | x)  r(x,y' ) - g_t(x,y) + _y'∼π_t(· | x) g_t(x,y') )^2 
       ≤ 2 _x, y∼(·|x)( r(x,y) - g_t(x,y) )^2 + 2 _x_y'∼π_t(· | x)(  r(x,y') - g_t(x, y')  )^2

Recall the g_t(x,y) = r(x,y) + Δ(x,y) - Δ_(x), and from Lemma <ref>, we can see that

    _x,y∼(· | x) ( r(x,y) - g_t(x,y) )^2 = _x,y∼(· | x) ( Δ(x,y) - Δ_(x) )^2  ≤ϵ.
  
For _x_y'∼π_t(· | x)(  r(x,y') - g_t(x, y')  )^2, we have:

    _x   _y'∼π_t(· | x)(  r(x,y') - g_t(x, y')  )^2   =  _x_y'∼π_t(· | x)(  Δ(x,y') - Δ_(x)  )^2 
        =  _x_y'∼π_t(· | x)(  Δ(x,y') -  Δ_π_t(x) + Δ_π_t(x) - Δ_(x)  )^2 
       ≤ 2  _x_y'∼π_t(· | x)(  Δ(x,y') -  Δ_π_t(x) )^2 + 2 _x(   Δ_π_t(x) - Δ_(x)  )^2 ≤ 4 ϵ,
  where the last inequality uses Lemma <ref> again. Combine things together, we can conclude that:

    _x_y∼π^*(· |x ) ( A^π_t(x,y)  - A_t(x,y) )^2 ≤ C_π^* ( 10 ϵ).


Finally, for the regret, we can conclude:

    1/T∑_t=0^T-1_x, y∼π^*(· | x)( A^π_t(x,y) ) ≤ 2 A √(ln ||/ T ) + 1/T∑_t √( C_π^* 10 ϵ)  = 2 A √(ln ||/ T ) +  √( C_π^* 10 ϵ).











§ PROOF OF THEOREM <REF>


Recall that r_t(x,y)=l(x,y,π_t). Let us define Δ^t(x,y):=f_t(x,y)-r_t(x,y), Δ^t_π_t(x):=_y∼π_t(·|x)Δ^t(x,y) and Δ^t_μ(x):=_y∼(·|x)Δ^t(x,y). Then following the same arguments in Lemma <ref>, we have

    _x∼ρ, y∼π_t(· | x)[( f_t(x,y) -  r_t(x,y) - Δ^t_π_t(x) )^2] ≤ϵ,


    _x∼ρ, y∼(· | x)[( f_t(x,y) -  r_t(x,y) - Δ^t_(x) )^2 ]≤ϵ,


    _x∼ρ[( Δ^t_π_t(x) - Δ^t_(x) )^2 ]≤ϵ.

With slight abuse of the notation, We also use g_t and A_t(x,y) to denote r_t(x,y)+Δ^t(x,y)-Δ^t_μ(x,y) and g_t(x,y) - _y'∼π_t(· | x)  g_t(x,y'). Then following the same arguments in Lemma <ref>,

    ∀π, x:  ∑_t=0^T-1_y∼π(· | x) A_t(x,y) ≤ 2 A √(ln(||) T).


Note that we have

    max_πl(π,)=max_π1/T∑_t=1^Tl(π,π_t)
           =max_π1/T∑_t=1^T_x∼ρ,y∼π(·|x)[r_t(x,y)]=max_π1/T∑_t=1^T_x∼ρ,y∼π(·|x)[A^t,π_t(x,y)],

where A^t,π_t:=r_t(x,y)-_y∼π_t(·|x)[r_t(x,y)]. The last step is due to the skew symmetry of l, i.e., _y∼π_t(·|x)[r_t(x,y)]=l(x,π_t,π_t)=0. Then by following the same arguments in the proof of Theorem <ref>, with (<ref>)(<ref>)(<ref>)(<ref>), we have for any policy π,

    1/T∑_t=0^T-1_x∼ρ, y∼π(· | x)( A^t,π_t(x,y) ) ≤ 2 A √(ln ||/ T ) +  √(10 C_μ→πϵ).

This implies that

    max_πl(π,)≤max_π(2 A √(ln ||/ T ) +  √(10 C_μ→πϵ))≤2 A √(ln ||/ T ) +  √( 10C_μϵ).


Note that due to the skew symmetry of l, we have

    min_πl(,π)=min_π_x∼ρ,y∼(·|x), y'∼π(·|x)[l(x,y,y')]=-max_π_x∼ρ,y∼(·|x), y'∼π(·|x)[-l(x,y,y')]
           =-max_π_x∼ρ,y∼π(·|x), y'∼(·|x)[l(x,y,y')]=-max_πl(π,)≥ -2 A √(ln ||/ T ) - √(10 C_μϵ).

Therefore we have

    ()≤ 4A √(ln ||/ T ) +  2√(10 C_μϵ).




§ ADDITIONAL EXPERIMENT DETAILS






 §.§ Dataset Details



We present dataset details in Table <ref>.







 §.§ Hyperparameter Details







 §.§ Winrate Details



Below we show the prompt for winrate evaluation and an example evaluation from GPT4. 








§ EXAMPLE GENERATIONS





 §.§ Summarization Generations







 §.§ Image Generations








§ ABLATION ANALYSIS






Just like DPO, tuning  is much more straightforward than PPO since the only hyperparameter  introduced is η. We investigate how sensitive  is to learning rate η in the loss. The results of ablation is shown in Table <ref> with the same setting detailed in Appendix <ref> except for η.  achieves the best performance when η=1, while increasing or decreasing η leads to decreased performance. Our result here indicates that  η is an important hyperparameter that requires tuning for achieving a good performance. 



§ REGRESSION LOSS DURING TRAINING




Figure <ref> shows the observed loss or Eq. <ref> that we observed when finetuning the 6.9B Pythia model on . We see that  minimizes the loss throughout training maintaining a relatively low mean squared error given that our observed rewards were mostly between [-10, 10]. Note that our learned reward model, however, is unbounded.
 
