A Minimaximalist Approach to Reinforcement Learning from Human Feedback

Introduction

Reinforcement learning from human feedback (RLHF, Christiano et al. (2017)) also known as preference-based reinforcement learning (PbRL, Akrour et al. (2012); Wirth et al. (2017); Sadigh et al. (2017); Ibarz et al. (2018); Lee et al. (2021b, a); Sikchi et al. (2022)), is a technique for policy optimization based on relative, rather than absolute, feedback. Owing to the relative ease of providing comparative feedback rather than absolute scores for agent behavior for human raters (Miller, 1956), RLHF has been successfully applied across fields from robotics (Cakmak et al., 2011; Tucker et al., 2020; Swamy et al., 2020; Bıyık et al., 2020) to recommendation (De Gemmis et al., 2009; Ailon & Mohri, 2010; Viappiani & Boutilier, 2010; Afsar et al., 2022), to retrieval (Yue & Joachims, 2009). As of late, RLHF has attracted renewed interest as a leading technique for fine-tuning large language models (LLMs) (Ziegler et al., 2020; Stiennon et al., 2020; Bai et al., 2022a; Ouyang et al., 2022).

The predominantly studied approach to RLHF is via Reward-based RLHF, a two-stage procedure. First, given pairs of preferred and dis-preferred behavior, one trains a reward model to assign higher scores to the former via a classification objective. One then optimizes this reward function via some reinforcement learning algorithm.

Simple as the above recipe is, the key ingredient of a reward model can have some undesirable effects. First, assuming an underlying reward function exists is equivalent to assuming that there exists a total order over agent behavior. This means that there are no intransitivities in rater preferences (i.e. $A\succ B,B\succ C\Rightarrow A\succ C$), which contradicts what psychology tells us about actual human decision making (Tversky, 1969; Gardner, 1970). Even if one believes an individual person’s preferences are transitive, when aggregated across a population of raters as is necessary at scale, transitivity is unlikely to be satisfied (May, 1954). Second, given the inherent stochasticity of human preferences (Agranov & Ortoleva, 2017), one often learns a reward model that leads to a collapse in generation diversity. For example, consider a problem where the agent can pick one of two options, each of which is preferred by a sub-population of raters that makes up half of the total population. Due to either finite sample or optimization error, we can easily learn a model that assigns a slightly higher reward to one option over the other. Then, if we were to optimize our policy under this model, we would learn to (almost) exclusively select one option, leaving half of the population unsatisfied.

In recognition of the above concerns, various reward-model-free approaches have been proposed in the prior literature. One particularly promising set of techniques frames RLHF as a two-player zero-sum game between two policies, each of which attempts to produce behavior that is preferred by a rater to the other’s (Yue et al., 2012). While elegant theoretically, this “dueling” framing inherits the inherent instability of adversarial training in practice and has therefore mostly been applied to bandit problems (Dudík et al., 2015; Saha et al., 2021; Saha & Krishnamurthy, 2022).

Motivated by these issues, we provide a simple, theoretically rigorous, and empirically performant approach to RLHF that eliminates reward modeling and does not require adversarial training. Our approach follows from two key insights. First, by framing RLHF as a two-player zero-sum game, we are able to truly eliminate reward models and therefore more capably handle the noisy, intransitive, and non-Markovian preferences that frequently occur in practice. Second, by leveraging the symmetry of the game, we prove that we can simply train a single agent in a self-play fashion, eliminating the need for unstable adversarial training. Practically, this corresponds to sampling multiple trajectories from the agent, asking a rater or preference model to compare each pair, and setting the reward to be the trajectory’s win rate. We call this approach SPO: Self-Play Preference Optimization.

More explicitly, our contributions are as follows:

1. We derive SPO: an algorithm for RLHF that avoids reward modeling, compounding errors, and adversarial training. By building upon the concept of a Minimax Winner from social choice theory, we are able to frame RLHF as a two-player zero-sum game. We then leverage the symmetry of the payoff matrix of this game to prove that we can simply train a single agent against itself.

2. We use a reduction-based analysis to investigate the convergence properties of SPO. When intransitive preferences exist, we prove that SPO converges to an approximate Minimax Winner at the rate of the underlying no-regret algorithm, unlike the usual asymptotic statements one gets for fictitious self-play approaches (Leslie & Collins, 2006). We also prove that in the case where an underlying reward function does exist, our approach converges to the optimal policy at a fast rate that matches that of standard techniques.

3. We demonstrate that on a suite of continuous control tasks with realistic preference functions, SPO is more performant than reward-model based approaches. We find that our approach is able to learn more sample-efficiently than reward-model based approaches across a variety of preference setups. This includes trajectory-level comparisons based on ground-truth Markovian rewards in the easiest case, stochastic preferences, trajectory-level non-Markovian preferences and intransitive preferences induced by aggregating over sub-populations. The strong performance of SPO in the latter three challenging setups, all motivated by practical situations, is illustrated in Figure 2.

Related Work

Dueling Bandits and Dueling RL. Beginning with the seminal work of Yue et al. (2012), various authors have viewed preference-based optimization of a multi-armed or contextual bandit as a two-player zero-sum game (Dudík et al., 2015; Saha et al., 2021; Saha & Krishnamurthy, 2022; Bengs et al., 2021). Dudík et al. (2015) carry out a detailed theoretical study of the two-player approach in contextual bandits, where they use the name von Neumann winner to refer to the concept of a Minimax Winner. We adopt the latter name due to its older roots in the social choice theory literature. More recently, various authors have investigated dueling reinforcement learning algorithms from a theoretical perspective. In contrast to Pacchiano et al. (2023), we do not need to assume preferences are explained by an underlying reward function. We build upon the work of Wang et al. (2023) by utilizing their reduction of RLHF to adversarial MDP solving. However, we further leverage the structure of the problem to derive single-player algorithms, while all aforementioned approaches requires adversarial training.

Both in the bandit and sequential settings, prior work has considered single-player algorithms for RLHF. However, these results require strong linearity assumptions and are only applicable in the bandit domain (Sui et al., 2017) or assume an underlying Markovian reward function (Novoseller et al., 2020). In contrast, we provide a reduction to no-regret online learning that allows one to plug in any no-regret algorithm (e.g. Online Gradient Descent, Zinkevich (2003)) without additional assumptions. In particular, by leveraging a recent result from Wang et al. (2023), we are able to prove that we can utilize a variation of the Natural Policy Gradient (Kakade, 2001; Agarwal et al., 2021), which practical policy gradient algorithms like PPO (Schulman et al., 2017) and TRPO (Schulman et al., 2015) approximate, to efficiently compute Minimax Winners, bypassing the hardness result of Daskalakis et al. (2020) by utilizing the structure of our particular game.

Perhaps the most similar work to ours is the concurrent study of Munos et al. (2023). They derive a specific algorithm, focus on quantal response equilibria to be able to prove last-iterate convergence, and treat the problem as a normal-form game. Instead, we focus on a general algorithmic framework, provide convergence guarantees to the Nash equilibrium, and account for the sequential nature of the game. Empirically, they focus on a particular task of learning document summarization from human feedback, while we study continuous control tasks where we experiment with a range of realistic preference functions. Recent work by Chen et al. (2024) formulates inverse RL for LLM fine-tuning as a kind of self-play – we focus on optimizing from preferences rather than from demonstrations.

Our reward model baseline and our continuous control setup are heavily influenced by the works of Christiano et al. (2017); Lee et al. (2021a). One critical distinction from this prior work is rather than assuming that the rater is able to provide snippet-level feedback, we only assume they can perform trajectory-level comparisons, a much less dense form of supervision.

RLHF without Reward Models. Recently, several authors have proposed eliminating reward models from RLHF by leveraging the well-known bijection between the optimal policies of minimum-relative-entropy RL problems and their advantage functions (Ziebart, 2010) to directly optimize the policy by substituting it into the classification loss usually used to train the reward model (Zhao et al., 2023; Rafailov et al., 2023; Hejna et al., 2023; Azar et al., 2023). While these approaches are appealing for their conceptual simplicity and ease of implementation, they suffer from the same issues with intransitive and noisy preferences as they are derived on the basis of an implicit reward model. Additionally, as we discuss further in Appendix B, they can suffer from compounding errors (Ross et al., 2011) due to their offline nature. In a sense, this family of approaches can be thought of as the preference-based analog to behavioral cloning techniques (Pomerleau, 1988) in imitation learning. In contrast, the technique we propose is the preference-based analog of inverse reinforcement learning approaches (Ziebart, 2010). We summarize this taxonomy in Table 1.

Reinforcement Learning from Human Feedback via Game Solving

We begin by introducing the notation we will use throughout the paper before defining our solution concept and deriving an efficient algorithm to compute it.

Consider a finite-horizon reward-free Markov Decision Process (MDP) (Puterman, 2014) parameterized by $\langle\mathcal{S},\mathcal{A},\mathcal{T},H\rangle$ where $\mathcal{S}$, $\mathcal{A}$ are the state and action spaces, $\mathcal{T}:\mathcal{S}\times\mathcal{A}\rightarrow\Delta(\mathcal{S})$ is the transition operator, and $H$ is the horizon. We omit contexts for simplicity of presentation but they can be added without much overhead, as we detail in Appendix A.7. We use $\Xi\triangleq(\mathcal{S}\times\mathcal{A})^{H}$ to denote the space of trajectories and $\Phi_{h}\triangleq\times(\mathcal{S}\times\mathcal{A})^{h-1}\times\mathcal{S}$ to denote the space of histories of length $h$.

Online Preference Oracle. In the preference-based RL setup, we are given query access to a preference function

which, given two trajectories $\xi_{1},\xi_{2}\in\Xi\times\Xi$, outputs a scalar that indicates which is preferred relative to the other. Practically, this could be either be a preference model trained on an offline dataset (RLAIF, Bai et al. (2022b); Munos et al. (2023); Zhao et al. (2023)) or a human-in-the-loop (RLHF, Tucker et al. (2020)). The former setup is similar to reward-based RLHF, except that the reward model learning step is replaced by learning a pairwise preference model, which is more natural when learning from pairwise preference data. Viewed this way, the preference-model based RLHF based methodology strictly generalizes reward-based RLHF, as we can still represent a preference function that is induced by a difference of rewards, but not every preference function is expressible this way, as we illustrate in the following sections. We also note that in the alignment of generative models, sometimes the preference function simply consists of a prompted generative model that is asked to compare two outputs, rather than a model trained explicitly on a preference dataset (Bai et al., 2022b). In this setting, we are able to optimize directly based on the outputs of such a model, rather than having to take a detour through a reward model.

By construction, preference functions are anti-symmetric, i.e. $\forall\xi_{1},\xi_{2}\in\Xi\times\Xi$, $\mathcal{P}(\xi_{1},\xi_{2})=-\mathcal{P}(\xi_{2},\xi_{1})$. Similarly, we have that $\forall\xi\in\Xi$, $\mathcal{P}(\xi,\xi)=0$.

We assume access to a convex and compact policy class $\Pi\subseteq\{\mathcal{S}\rightarrow\Delta(\mathcal{A})\}$. With a slight abuse of notation, we can now define the preference function over policy pairs as

2 A Brief Introduction to Social Choice Theory

Given choices from a population of raters that are represented as a preference function $\mathcal{P}$, social choice theory (Sen, 1986) studies the question of how best to select options that satisfy the diversity of preferences inherent in said population. For example, consider the set of preferences $\mathcal{P}_{1}$ over options $(a,b,c,d)$ in Figure 3.

Given this preference function, perhaps the most natural idea would be to pick the option that beats the largest number of other options. In the above matrix, this would be either option $a$ or $d$ as they have the largest row sums. More formally, this technique is known as a Copeland Winner and can be expressed mathematically as

While intuitively appealing, Copeland Winners are often not unique as in our above example, raising the question of how to break ties. For example, if half of the group feels like $a\succ d$ and the other half like $d\succ a$, picking either option would leave half of the group unsatisfied. This problem only gets worse as the number of options to choose between increases, as there is unlikely to be a single option that everyone prefers to every other option (Dudík et al., 2015).For example, we see empirical evidence of this point in the high rates of inter-annotator disagreement (Taori et al., 2023; Touvron et al., 2023) in LLM finetuning datasets.

In essence, approaches that train reward models like reward-based RLHF (or implicitly assume them like DPO) are akin to computing Copeland Winners. Observe that our above matrix has an intransitivity: $a\succ c,c\succ d,d\succ a$. This means that no reward function can explain the above preferences as it would need to satisfy $r(a)>r(c)$, $r(c)>r(d)$ and $r(d)>r(a)$ simultaneously, an impossibility. Thus, the model is forced to tie-break between $a$ and $d$, potentially leaving half of the population rather unsatisfied. In practice, this tie-breaking is performed based on the incredibly noisy data used to train the reward model (Taori et al., 2023; Touvron et al., 2023), making it entirely arbitrary. When combined with the fact that an $\epsilon$ difference in reward model outputs can lead to an entirely different optimal policy, we are left with an unsatisfying solution.

One potential solution to the issues with the Copeland Winner is to randomize. For example, we could attempt to pick a distribution over options such that we prefer samples from this distribution to those from any other distribution with probability at least $\frac{1}{2}$. For $\mathcal{P}_{1}$, this would correspond to us picking $(a,c,d)$, each with probability $\frac{1}{3}$, as

Intuitively, this means that while we don’t always make everyone happy (an impossibility, Arrow (1950); Satterthwaite (1975)), we never pick a solution that makes a significant portion of the population consistently unhappy. At this point, readers familiar with game theory might recognize that the above corresponds to computing the Nash equilibrium of the two-player zero-sum (2p0s) game with payoffs given by the preference function. More formally, we can define the Minimax Winner (MW, Kreweras (1965); Simpson (1969); Kramer (1973); Fishburn (1984)), also known as a von Neumann Winner (Dudík et al., 2015), as the following pair of strategies:

Via Sion’s minimax theorem (Sion, 1958), we can guarantee that the above solution concept always exists, unlike a unique Copeland Winner. We note that because we assumed $\Pi$ is convex, we are always able to collapse down any distribution $p\in\Delta(\Pi)$ to a single policy $\widetilde{p}\in\Pi$ while preserving solution quality by performing a weighted average:

In short, this means that we never need to explicitly maintain a distribution over policies, either in theory or practice.

We conclude with a few observations about MWs. First, nowhere in defining a MW did we need to assume the existence of an underlying reward function, rendering the above solution concept truly reward model-free. Second, in the case where there actually does exist an underlying reward function that explains the observed preferences, the MW coincides with the optimal policy for that reward (Dudík et al., 2015), rendering the MW a strict generalization of the CW. Third, MWs satisfy a variety of desirable consistency properties (e.g. merging populations that agree on a MW cannot change the outcome, which is especially important when attempting to re-use preference datasets), which deterministic options like the CW cannot satisfy simultaneously (Brandl et al., 2016).

We now turn our attention to efficiently computing MWs.

3 One Player is All You Need for RLHF

Starting with the seminal work of Freund & Schapire (1997), efficient algorithms for computing Nash equilibria of 2p0s games have been a central focus in computational game theory. The usual solution is to run two no-regret algorithms (e.g. Hedge (Freund & Schapire, 1997) or Online Gradient Descent (Zinkevich, 2003)) against each other, perhaps known more commonly as adversarial training (Goodfellow et al., 2014). When applied to computing MWs, this strategy is known as dueling (Yue et al., 2012) and is commonly applied in the bandit setting. While elegant in theory, this technique inherits all of the notorious instabilities of adversarial training in practice. Even ignoring optimization issues, simply storing both models in memory might be difficult in our current era of “foundation” models (Bommasani et al., 2021). These issues likely explain why dueling techniques have seen limited practical use.

In light of the above difficulties, we ask a simple question: do we actually need two players to compute MWs? We now prove rigorously that we only need a single player due to the anti-symmetry of preference functions. All proofs for this section can be found in Appendix A.

First, we prove that there always exists a symmetric MW.

$\exists(\hat{p},\hat{q})\in\mathsf{MW}(\mathcal{P})$ s.t. $\hat{p}=\hat{q}$. [Proof]

Next, we prove that we can compute this symmetric MW by running a single no-regret algorithm against its own iterates. We assume access to the following optimization oracle.

with $\lim_{T\to\infty}\frac{\mathsf{Reg}(T)}{T}=0.$

Common algorithms like gradient descent satisfy this property (Zinkevich, 2003). See Hazan et al. (2016) for a more extensive list. We define the SPO Loss at round $t\in[T]$ as

The above result implies that if we run our algorithm for long enough, we can get arbitrarily close to an exact MW.For last iterate (rather than average iterate) convergence, one can simply set the no-regret algorithm to be Optimistic Mirror Descent and apply the results of Daskalakis et al. (2017). Observe that we didn’t need to assume we were running a particular algorithm $\mathcal{O}$, rendering the above a reduction of computing minimax winners to no-regret online learning.We note that in contrast to the usual asymptotic convergence guarantees one gets for self-play (Leslie & Collins, 2006), one inherits the rate of the underlying no-regret algorithm for MWs.

The above update can also be viewed from the perspective of a dynamic reward model: it is equivalent to performing an RL step with a policy-dependent reward model:

This reward model incentivizes the learner to play trajectories that are preferred to its current distribution. Game-solving amounts to repeatedly taking a small step along this direction before (implicitly) updating the reward model. Thus, one can view SPO as using a perfectly shaped curriculum to gently guide the learner. We now pause and further contextualize our results by considering a few questions.

Q1: Do reward-based RLHF algorithms also compute MWs? We prove that this is not the case in general by analyzing multiple algorithms which assume that there exists a reward function that explains the observed preferences

There exists a preference function $\mathcal{P}$ and reference policy $\pi_{\text{ref}}$ such that the optimal policies of reward-based RLHF and DPO are not the Minimax Winner. [Proof]

Consider a unique Minimax Winner of the form $[x,x,1-2x]$ for $x\in(\frac{1}{3},\frac{1}{2})$. Assume $\pi_{\text{ref}}=[\frac{1}{3},\frac{1}{3},\frac{1}{3}]$. Then, reward-based methods can only pick a reward model that makes (a) one option preferred to all others (resulting in some permutation of $$), making two options preferred to the third (resulting in some permutation of$[\frac{1}{2},\frac{1}{2},0]$) or (c) makes all equally preferred (resulting in$[\frac{1}{3},\frac{1}{3},\frac{1}{3}]$). None of these options can represent the Minimax Winner.

However, by appeal to Equation 7, standard RLHF algorithms / DPO applied iteratively with each batch of preferences collected on-policy and at a sufficiently high frequency may be able to compute MWs on average. That said, for any fixed iteration budget, we would expect preference-based methods like SPO to better compute MWs because the opponent policy is more “fresh”. Even ignoring iteration however, preference models have been shown to generalize better than reward models fit on the same data (Munos et al., 2023). Intuitively, fitting a preference model is learning the static matrix $\mathcal{P}$ while fitting a reward model is learning the dynamic vector $\mathcal{P}p_{t}$, which depends on the current policy and is therefore easier to push out of distribution.

Q2: If there exists an optimal policy / Copeland Winner for my problem, could running SPO be an inefficient way to compute it? We prove that this is not the case in a strong sense: when there exists a clearly optimal policy, our above algorithm converges to it at a fast statistical rate – $\widetilde{O}(\frac{1}{T})$ instead of the usual $\widetilde{O}(\frac{1}{\sqrt{T}})$ average regret. This matches the rates for UCB-style methods, previously been studied in more restricted versions of the dueling setup (Bengs et al., 2021). We give a simpler version of the result here, with a more general form and proof in Appendix A.5.

4 SPO: Self-Play Preference Optimization.

For single-step problems with a small and discrete policy class, it is common to maintain a distribution over policies / arms. However, as we transition to the sequential setting with a large and often continuous policy class, it is difficult to scale such an approach. We are therefore faced with the question of what is the right no-regret algorithm to optimize the sequence of SPO losses in the RL setting?

To answer this question, we turn to the celebrated idea of local regret minimizers (Zinkevich et al., 2007; Even-Dar et al., 2009). Consider a problem with a finite state space. Then, at each state $s\in\mathcal{S}$, we could independently instantiate a no-regret algorithm that optimizes over $\Delta(\mathcal{A})$, feeding it a loss that depends on the cumulative reward received after exiting the state, i.e. $Q(s,a)$. Then, regardless of the state distribution our resulting policy induces, we can guarantee that we’re improving at each iteration. For a specific no-regret algorithm (Hedge, Freund & Schapire (1997)), this leads to the well-known soft policy iteration (SPI) procedure (Ziebart, 2010). Because our reward function is at the trajectory level, we technically need to have a regret minimizer at each history rather than at each state. We describe in Algorithm 1 an instantiation of SPO that uses history-dependent SPI as its policy optimizer (Lines 6-10) and now present a performance guarantee on the learned policy.

With an appropriate setting of $\eta$, running Algorithm 1 for T iterations guarantees $\bar{\pi}$ is a $2H\sqrt{\frac{2\log(|\mathcal{A}|)}{T}}$-approximate Minimax Winner.

This follows directly from Lemma C.4. in Xie et al. (2021) and our Theorem 3.3. Of course, in practice, one often uses a deep network to represent their policy rather than the tabular representation we assume in Algorithm 2. It turns out that for certain policy parameterizations, the Natural Policy Gradient (NPG) algorithm of Kakade (2001) is exactly equivalent to the soft policy iteration procedure (Agarwal et al., 2021). Many standard deep RL algorithms like TRPO (Schulman et al., 2015) and PPO (Schulman et al., 2017) are explicitly motivated as approximating NPG, while techniques like SAC (Haarnoja et al., 2018) can also be viewed as approximate soft policy iteration. Thus, as we move towards a practical approach, we are free to choose from a wide set of standard deep RL techniques as reasonable approximations of our theoretical algorithm.

One other concern we need to resolve is how to do credit assignment with trajectory-level feedback. In fact, if we are unable to provide rewards for each timestep in the problem, our options for policy optimization are quite limited outside of notoriously high variance REINFORCE-style policy gradients (Williams, 1992). We suggest a simple fix to this problem inspired by potential-based reward shaping (Ng et al., 1999): just split the trajectory-level reward equally amongst all state-action pairs. We prove in Appendix A that doing so preserves policy optimality.

In general, such a transformation can cause issues with learning good state-based critics due the fundamentally non-Markovian nature of a trajectory-level reward. However, we find that in practice, this reward transformation (Line 7 in Algorithm 2) significantly speeds up policy search.

Lastly, in theory, SPO requires sampling multiple trajectories per policy update. In practice, we simply keep a queue Q of a small, fixed size (typically 10) and use the win rate against this queue for labeling trajectories sampled from the current policy (Line 6 in Algorithm 2). This makes our approach strikingly lightweight to implement on top of any policy optimization method of choice: it is just reward relabeling. We describe our complete approach in Algorithm 2 – see Appendix A.7 for the contextual version.

Thus far, our presentation has assumed access to a preference function $\mathcal{P}$ which can be queried at each round with new trajectories. This is natural when preference labels are generated by a model learned from a previously collected preference dataset, as in recently studied RLAIF settings (Bai et al., 2022a; Zhao et al., 2023). However, in other settings, it is desirable to directly obtain the preference labels from humans or other expert models (RLHF, Tucker et al. (2020)), where online querying is not possible. SPO is compatible with batched queries the queries in these settings. Specifically, we can freeze the policy for some batch size $B$, accumulate a dataset of $B$ trajectory pairs to compare, and then query the labels for all of them. Practically, this just results in mini-batching in the no-regret algorithm being used by SPO, which preserves the no-regret property for $B<O(\sqrt{T})$.

Experiments

We compare SPO against an iterative Reward Modeling (RM) approach along several axes. Specifically, the experimental section aims to answer the following questions:

Can SPO compute MWs when faced with intransitive preferences? We consider aggregating three populations in different proportions, each of which has transitive preferences internally. We are able to compute the MW in closed form for this discrete action problem and can therefore measure exactly how far off SPO is from it. We also present qualitative results on a continuous control task from Mujoco, (Brockman et al., 2016) where exactly computing the MW for comparison is infeasible.

Can SPO match or exceed RM sample efficiency on problems with unique Copeland Winners / optimal policies? We evaluate SPO and RM with preferences based on ground truth rewards from the DMControl Tassa et al. (2018) continuous control environments. This setting is tailor-made for RM as there exists a deterministic, Markovian reward function that explains the observed preferences.

How robust is SPO to stochastic preferences? We study the robustness of RM and SPO to corruptions of various probabilities (i.e. Bernoulli noise) in preference labels. This setup is meant to capture some of the stochasticity in human preferences that makes RLHF challenging in practice.

Can SPO handle Non-Markovian preferences? We consider a challenging situation where we want to elicit qualitatively non-Markovian behavior (e.g. constraints on just a part of a trajectory) from a Markovian policy purely on the basis of trajectory-level relative feedback.

To remove any confounds due to data staleness, we allow both of our approaches to query the preference function online, and thus continuously update the RM during the course of running policy search. Thus, RM can be seen as a maximally iterative reward-based method and therefore a rather strong baseline. We use Soft Actor Critic (SAC, Haarnoja et al. (2018)) for continuous control tasks and Proximal Policy Optimization (PPO, Schulman et al. (2017)) for discrete action tasks, both as implemented in the ACME framework (Hoffman et al., 2020). The actor, critic sizes and activations are held exactly the same between SPO and RM. Explicitly, the only distinction between SPO and RM is how the reward of a trajectory is estimated and fed into the policy optimization method.

The reward model is Markovian and trained on trajectory level comparisons using trajectories drawn from the agent’s replay buffer by optimizing the Bradley-Terry loss (Bradley & Terry, 1952). During learning, the current reward model is used to label samples that are drawn from the replay buffer for performing policy search. The relabeling works better in our experiments than using the rewards assigned when these samples were put into the replay buffer. We keep the reward model architectures consistent with Lee et al. (2021a) and perform extensive sweeps over learning rates and update rules – see Appendix D for more details. Due to limited space, we postpone additional results for most experiments to Appendix C.

Intransitive Preferences. We begin by testing whether SPO is actually able to compute MWs in practice via attempting to optimize cyclic (intransitive) preferences.

First, we consider 3 populations, each of which has internally transitive preferences over a discrete set of 3 options. However, when aggregated, their preferences become intransitive, as is common in real-world scenarios (May, 1954). Because this problem is discrete, we can in closed form compute the MW. As we show in Figure 4, SPO is able to almost exactly compute the MW across a variety of sub-population weightings, agreeing with our main theorem, Theorem 3.3.

Next, we consider the Mujoco Ant-v3 navigating atop a 2D plane and consider its radius and angle with respect to the origin at the end of the episode, $(R(\xi),\theta(\xi))$. We consider a preference structure where a trajectory looses to the “pizza-slice” of angle $\bar{\theta}$ in front of them and, within each slice, prefers the “crust” to the “cheese”. While we are unable to compute the exact MW here, the symmetry of the preference function over angles implies that the MW qualitatively chooses points uniformly across the slices, while keeping a minimum distance from the center. In Figure 5, we see that over the course of training, our agent matches this behavior on average, continuously sweeping out full circles.

From this point onward, we switch to the DMControl Suite (Tassa et al., 2018) due the greater variety of tasks available.

Noisy Preferences. A natural followup to ground truth reward based preferences is to test the robustness of these methods to noisy preferences (representing annotator disagreements). We study this setting by flipping the maximum reward preference $\mathcal{P}_{1}(\cdot)$ above according to i.i.d Bernoulli noise $k$, i.e. $\mathcal{P}_{2}(\xi,\xi^{\prime})=k\cdot\mathcal{P}_{1}(\xi,\xi^{\prime})$, where $k\sim\text{Bern}(\epsilon)$.

In Figure 7, we see that SPO is more robust to noise than RM. Assuming independence between raters, an $\epsilon$ chance of a flip corresponds to a $d=2\epsilon(1-\epsilon)$ chance of rater disagreement. Thus, we see SPO is consistently able to successfully optimize with an $\epsilon=0.3\Rightarrow d=0.42$ chance of rater disagreement, which matches the levels observed in practice (Taori et al., 2023; Touvron et al., 2023).

Non-Markovian Preferences. Lastly, we consider a challenging task where we want the agent to maximize their cumulative reward as much as possible subject to the constraint that their total reward in the last quarter of a trajectory is below a threshold $r_{\text{max}}$. Define trajectory-level reward

This induces the following set of preferences:

The optimal strategy for this setting is to exhibit qualitatively non-Markovian behavior, i.e. maximize reward as much as possible during the first $\frac{3}{4}$ths of an episode before switching to more conservative behavior. The reason this is challenging is because we are optimizing over Markovian policies, which means the agent needs to learn an unusually complex mapping. In Figure 8, we see that while SPO is consistently able to cross the $4r_{\text{max}}$ threshold that corresponds to exhibiting qualitatively non-Markovian behavior, RM is never able to do so. We visualize the difference in the state of SPO-trained agents at the beginning and end of a roll-out on the right of Figure 2 and can see clear differences.

In summary, our experiments show that even when compared to a maximally iterative reward-based method, SPO performs better across a wide set of preference structures.

Discussion

We provide an algorithm that is minimalist in its lack of reward modeling or adversarial training and maximalist in its robustness to noisy, intransitive, and non-Markovian preferences, as well as compounding errors. Rather than solving the zero-sum game directly, we leverage the structure of the game and follow a simple and stable self-play approach. Our approach is provably efficient and out-performs an iterative reward-model baseline on a suite of continuous control tasks. In the future, we would be interested in leveraging techniques from the imitation learning literature to remove the sample-inefficient RL step and reduce preference model exploitation (Song et al., 2022; Swamy et al., 2023; Chang et al., 2023), and testing out our approach on other problem domains like language modeling or content recommendation. Furthermore, given our method’s similarity to interactive imitation learning methods (which are known to be robust to unobserved confounders, Swamy et al. (2022a, b)), it would be interesting to investigate whether our method is better able to handle situations when human preferences are a function of privileged information unobserved by the agent (Siththaranjan et al., 2023).

Acknowledgements

ZSW is supported in part by the NSF FAI Award #1939606, a Google Faculty Research Award, a J.P. Morgan Faculty Award, a Facebook Research Award, an Okawa Foundation Research Grant, and a Mozilla Research Grant. GKS would like to thank Drew Bagnell for valuable feedback.

References

Appendix A Proofs

Thus, $(\hat{q},\hat{p})$ also forms a Nash equilibrium. Then, because of the interchangeability of Nash equilibrium strategies for two-player zero-sum games (Nash, 1951), we have that $(\hat{p},\hat{p})$ and $(\hat{q},\hat{q})$ are symmetric MWs.

A.2 Proof of Theorem 3.3

We follow the strategy outlined in our preceding proof sketch.

Consider two players, $p,q\in\Delta(\Pi)$. An $\epsilon$-approximate Nash equilibrium is a pair of strategies $(p,q)$ such that

We define the following per-round losses for both players:

We can then define the (static) regret suffered by both players as

By construction, we set $p_{0}=q_{0}$. This implies that

We complete the proof by following the argument in Freund & Schapire (1997):

Thus, $(\overline{p},\overline{q})=(\overline{p},\overline{p})$ is a symmetric $\frac{\mathsf{Reg}_{p}(T)+\mathsf{Reg}_{q}(T)}{T}=\frac{2\mathsf{Reg}_{p}(T)}{T}$-approximate Nash equilibrium / Minimax Winner.

A.3 Proof of Theorem 3.4

Our preceding proof sketch ignored the effect of regularization for simplicity. We now provide a specific example under which standard algorithms do not compute Minimax Winners, even with regularization to a prior.

We set $\pi_{\text{ref}}$ to be uniform to remove any trivial failures due to a lack of data support and consider the following preference matrix:

We begin by considering standard RLHF algorithms. First, we would fit a reward model via the standard Bradley-Terry loss. This would peak at the Copeland Winner, which is $b$ for the above matrix. Without loss of generality, we assume reward model outputs are in the range $$. Thus,

Thus, for any finite non-negative $\beta$, $\pi^{\star}$ plays $a$ and $c$ equally often, which means it cannot play the Minimax Winner.

Next, we consider DPO. From Eq. 6 of Rafailov et al. (2023), we have that the optimal DPO policy has the form

As $\pi_{\text{ref}}$ is uniform, we have that $\pi_{\text{ref}}(y_{2})=\pi_{\text{ref}}(y_{1})$ and thus we can simplify our above expression

As written, the DPO loss assumes unweighted preferences (i.e. it assumes that all positive samples are equally preferable to their corresponding negative samples). We therefore perform the natural transformation from log likelihood to cross entropy:

Via Gibbs’ inequality, we know that cross-entropy is minimized when the two distributions are equal. We can then plug in the values from our above preference matrix to arrive at the following set of constraints:

Clearly, it is impossible to simultaneously satisfy all of these constraints. Thus, DPO is unable to learn the minimizer of the preference-level cross-entropy loss function because of its assumption of an implicit reward model. Unfortunately, this makes analyzing the solution DPO would actually pick rather difficult from a theoretical perspective. In response, we show that regardless of the setting of $\beta$, there exists another strategy $(\pi_{\text{ref}})$ with a lower loss than the Minimax Winner.

We can write out the above loss more explicitly as

Now, plugging in the Minimax Winner, we get that

A.4 Proof of Lemma 3.7

A.5 Proof of Corollary A.2

We begin by stating the core assumption we will use in this section.

There is a subset $\Pi^{\star}\subseteq\Pi$ such that:

$\forall\pi^{\star}\in\Pi^{\star}$, $\pi\in\Pi/\Pi^{\star}$, $\mathcal{P}(\pi^{\star},\pi)\geq\Delta$.

$\forall\pi^{\star}_{1},\pi^{\star}_{2}\in\Pi^{\star}$, $-\Delta/2\leq\mathcal{P}(\pi^{\star}_{1},\pi^{\star}_{2})\leq\Delta/2$.

$\forall\pi_{1},\pi_{2}\in\Pi/\Pi^{\star}$, $-\Delta\leq\mathcal{P}(\pi_{1},\pi_{2})\leq\Delta$.

Under this assumption, we can prove that rather than the $\widetilde{O}(\frac{1}{\sqrt{T}})$ rate we usually get for Hedge, we instead get a $\widetilde{O}(\frac{1}{T})$ rate.

Under Assumption A.1, after $T$ calls to Hedge, $\bar{p}$ is an $\frac{1+2|\Pi|\ln T}{\Delta T}$-approximate Minimax Winner.

The second property follows from the fact that the loss of any policy $\pi^{\prime}\notin\Pi^{\star}$ is always larger than the loss of any action $\pi^{\star}\in\Pi^{\star}$ by Assumption A.1, and the two differ by at least $\Delta/2$ whenever the comparator policy comes from the set $\Pi^{\star}$, since:

Now let us consider the class of Follow The Regularized Leader (FTRL, McMahan (2011)) algorithms, which induce probability distributions as

To proceed further, we consider coordinate-wise separable regularizers, that is $R(p)=\sum_{i=1}^{|\Pi|}R_{i}(p_{i})$, and use the distribution $p=p_{t}+\alpha e_{\pi_{a}}-\alpha e_{\pi_{b}}$, for actions $\pi_{a}\in\Pi^{\star}$ and $\pi_{b}\notin\Pi^{\star}$, with $\alpha<\max(\min(p_{t}(\pi_{a}),p_{t}(\pi_{b})),\epsilon)$. We further assume that $p_{t}(\pi_{a})>0$, which is naturally satisfied by many no-regret strategies that play in the strict interior of the simplex. With these choices, plugging on our preceding setting for $p$, and dividing both sides by $\alpha$, we get that

Rearranging terms and combining with our second property, we get that

We now specialize to the case of Hedge, where $R_{i}(x)=x\ln x$ and $\nabla R_{i}(x)=\ln x+1$ but note that a similar argument holds for a wide variety regularizers (i.e. other no-regret algorithms) under analogous assumptions. Then, by simplifying the RHS and LHS of our preceding expression and exponentiating both sides, we have that

Because the term inside the exponential is always negative and therefore the exponential is at most 1, the above expression implies that $\forall\pi_{b}\notin\Pi^{\star}$, $p_{t}(\pi_{b})\leq p_{t}(\pi_{a})\leq p_{t}(\Pi^{\star})$. Thus, via Hölder’s inequality, we have that $1=\sum_{\pi\in\Pi}p_{t}(\pi)\leq|\Pi|p_{t}(\Pi^{\star})\Rightarrow\frac{1}{|\Pi|}\leq p_{t}(\Pi^{\star})\Rightarrow\exp(-p_{t}(\Pi^{\star}))\leq\exp(\frac{-1}{|\Pi|})$. Since the same holds for $q_{t}$ by symmetry, we can conclude that

Consequently, once we have $\exp(-\eta t\Delta/(2|\Pi|))\leq\epsilon$, the probability of any action $b\notin\Pi^{\star}$ is at most $\epsilon$. Inverting the preceding expression shows this happens in at most $t\leq\frac{2|\Pi|}{\eta\Delta}\ln\frac{1}{\epsilon}$ rounds. Hence,

Choosing $\eta=1$ and $\epsilon=1/T$ gives a fast rate.

We note that the linear dependence on $\Pi$ is similar to the linear dependence on the number of actions in most gap-dependent bounds for UCB algorithms. We also note that in the bandit feedback setting, Equation 33 only changes in that we have importance-sampled estimates $\hat{L}_{t}(a)-\hat{L}_{t}(b)$ instead of the population losses. Adding and subtracting the true means gives us the same quantity as Eq. 33 plus a martingale. This term is $O(\eta\sqrt{t})$. For $\sqrt{t}=O(t\Delta/|\Pi|)$, or equivalently, $t=O((|\Pi|/\Delta)^{2})$, we get the same bound with slightly different constants.

A.6 Extension to Bandit Feedback

We now provide an extension of our main result to the bandit feedback setting via the standard importance sampling argument.

Assume $\Pi$ is finite. Let $\pi_{t},\pi^{\prime}_{t}\sim p_{t}$. For any fixed $\alpha\in$ and for some $\gamma\in$, if we set $\mathcal{O}$ to be the Hedge algorithm of Freund & Schapire (1997) and feed it the sequence of loss functions

Let $\pi_{t}\sim p_{t}$, $\pi_{t}^{\prime}\sim q_{t}$. We observe $\mathcal{P}(\pi_{t},\pi_{t}^{\prime})$ by querying the preference function.

and as the importance-weighted losses for each player at round $t$. Next, observe that

To prove that above loss estimation scheme preserves the no-regret property, we can simply examine the proof of Exp3 in Auer et al. (2002) and note that the only property required of the loss estimate ($\hat{x}_{t}$ in the original paper) is that it is unbiased. Thus, we inherit the regret rate of Exp3, which when plugged in completes the proof.

We note that while the above is not a general reduction per se, for a wide set of no-regret algorithms, a similar argument applies, with slight differences in the effect of importance sampling on the final regret rate.

A.7 Extension to Contextual Setting

We now extend our above setup to include contexts. Consider a finite-horizon reward-free contextual Markov Decision Process (MDP) (Puterman, 2014) parameterized by $\langle\mathcal{S},\mathcal{A},\mathcal{X},\mathcal{T},H,\rho\rangle$ where $\mathcal{S}$, $\mathcal{A}$, $\mathcal{X}$ are the state, action, and context spaces, $\mathcal{T}:\mathcal{S}\times\mathcal{A}\rightarrow\Delta(\mathcal{S})$ is the transition operator, $H$ is the horizon, and $\rho:\Delta(\mathcal{X})$ is the context / initial state distribution. We use $\Xi\triangleq(\mathcal{S}\times\mathcal{A})^{H}$ to denote the space of trajectories and $\Phi_{h}\triangleq\mathcal{X}\times(\mathcal{S}\times\mathcal{A})^{h-1}\times\mathcal{S}$ to denote the space of $h$-length histories. We assume that we are given access to a (contextual) preference function

which, given two trajectories $\xi_{1},\xi_{2}\in\Xi$, outputs a scalar that indicates which is preferred relative to the other. By construction, preference functions are anti-symmetric, i.e. $\forall x,\xi_{1},\xi_{2}\in\mathcal{X}\times\Xi\times\Xi$, $\mathcal{P}(x,\xi_{1},\xi_{2})=-\mathcal{P}(x,\xi_{2},\xi_{1})$. Similarly, we also have that $\forall x,\xi\in\mathcal{X}\times\Xi$, $\mathcal{P}(x,\xi,\xi)=0$. We assume access to a convex and compact policy class $\Pi\subseteq\{\mathcal{S}\times\mathcal{X}\rightarrow\Delta(\mathcal{A})\}$. With a slight abuse of notation, we can define the preference function over policy pairs as

We now re-state our algorithms, including the dependence on context. Their theoretical guarantees match those presented in the main paper. The main difference in practice is that rather than simply maintaining a queue, we now have to sample multiple trajectories based on a single context for comparison.

Appendix B Compounding Errors in RLHF

A common concern in sequential prediction tasks is compounding errors (Ross et al., 2011). Consider, for example, trying to train a policy to drive laps around a track purely based on recorded demonstrations from an expert driver who always stays close to the center of their lane. For example, one could regress from recorded states to recorded actions, an approach known as behavioral cloning (BC, Pomerleau (1988)). However, if at test time, the agent makes a mistake and goes off the center of their lane, they might end up in a state they hadn’t seen in their training data, have no idea what to do in this novel situation, make another error, and quickly spiral out of control. At a fundamental level, the agent’s poor test-time performance is caused by the covariate shift in terms of state distribution between the offline training data and their own induced state distribution – a low training error does not necessarily correspond to a low test error. Thus, the standard solution is to allow the learner to actually try out actions in the environment, see where they end up, and learn to correct their mistakes. This approach is known as inverse reinforcement learning (IRL, Ziebart (2010)) and is known to prevent compounding errors (Swamy et al., 2021).

A natural question might be if the learner gets preferences rather than demonstrations as feedback, whether the same concerns arise. We now provide a simple, informal example of this.

Consider the $H=2$ problem of completing sentences of the form “The (a) orbits around the (b).” where either blank can be filled in with utterances $\mathcal{A}$ = {earth, sun, moon}. We observe preferences of the form [moon, earth] $\succ$ [moon, sun]. At $h=1$, we are forced to play a policy $\pi_{\epsilon}$ that outputs moon w.p. $1-\epsilon$ and earth w.p. $\epsilon$. At $h=2$, we are allowed to choose between two policies: $\pi_{1}$ that always outputs earth and $\pi_{2}$ that outputs earth if the preceding word was moon and sun if the preceding word was earth. Observe that both $[\pi_{\epsilon},\pi_{1}]$ and $[\pi_{\epsilon},\pi_{2}]$ have the same probability of generating the preferred and dis-preferred generations and therefore will have the same value under any loss function that depends on its inputs purely via their off-policy likelihoods.

While hopefully any post-Copernican preference (or reward) model would be able to tell the difference between these two policies, offline approaches like DPO that simply compute likelihoods on off-policy data are unable to do so. An iterative application of DPO with batches of preferences collected frequently would likely mitigate this issue. We emphasize that this is a fundamental issue with all offline approaches, rather than with a particular offline algorithm (Swamy et al., 2021). We conclude with a note that this problem only gets worse with longer task horizons as there are more timesteps to deviate. This is perhaps one of the reasons that offline approaches can sometimes under-perform interactive techniques (Zhu et al., 2023; Chen et al., 2024) and why, as of the writing of this paper, the world’s most performant models are trained using interactive techniques (Team et al., 2023; OpenAI et al., 2023).

Appendix C Additional Results

We now present additional results we did not have space for in the main paper.

Appendix D Experimental Details

We use a 3-armed bandit with different preference functions that each induce a different (unique) Minimax Winner. All our preference functions have the following form, represented as an $|\mathcal{A}|$ by $|\mathcal{A}|$ matrix

where $a,b,c>0$ are parameters. The Minimax Winner for this preference function is $p^{\star}\propto\begin{bmatrix}a\\ b\\ c\end{bmatrix}$. This can be verified easily since $p^{\star}\mathcal{P}=\begin{bmatrix}0\\ 0\\ 0\end{bmatrix}$ and thus any opponent strategy yields the same value . For $a=b=c$, this is the preference in the popular Rock-Paper-Scissors game. More generally such preference functions can commonly occur when we estimate the preference from a population of users that each just have a preference between two of the three actions. Assume we have 3 sub-populations that each make up a fraction $a,b$ and $c$ of the total population, respectively. Then the average preference in the total population corresponds to $\mathcal{P}$

where each of the 3 matrices corresponds to the preference in the respective subpopulation.

Algorithm Parameters.

We use the PPO implementation in Hoffman et al. (2020) with learning rate $1e-4$ and entropy cost $1e-4$. For the policy network, we use 2 hidden layer with 128 nodes each and ReLU activation. We use the last $B=1000$ trajectories for computing the average preference of each trajectory. Since the purpose of this experiment is to verify that SPO learns the Minimax Winner, we run the algorithm until convergence for 50M steps and report the average action choice during the entire learning procedure.

D.2 Continuous control experiments

We use the SAC implementation in Hoffman et al. (2020) for all of our continuous control experiments. We use the same SAC hyperparameters for all methods, other than the fact that we use 3e-4 rather than 3e-5 as the learning rate for vanilla SAC. We use Adam for all optimization. We use three layer networks of width 256 for all function approximation. We use ReLU activations for the actor and critic and use Leaky ReLU activations with a final tanh (following Lee et al. (2021a)) for the reward model. We update the reward model every 256 policy updates, use a batch size of 64, and a learning rate of 1e-5.

D.3 Continuous control experiments with Intransitive Preferences

We use the MuJoCo Gym (Brockman et al., 2016) Ant-v3 environment as the base environment. The hyper-parameters for SAC are identical to what is described above except for having a fixed entropy coefficient of $1e-4$ since the learnt policy must exhibit stochasticity to capture the MW; we use a queue size of 10. The preference function we design is composed of a distance and angular preference. The angular preference makes the trajectory loose to an angle of $\theta$ in front of them. The distance component encourages the agent to traverse non-trivial distance from the origin until it hits a certain threshold. We found the distance component to be necessary in order for the agent to maintain effective control of the angle as it is very easy to shift angles when the agent is very close to the origin. The Python code for the preference function is written below. {python} def angular_preference(traj_1_angle, traj_2_angle, angle): difference = math.fmod(traj_1_angle + angle/2.0 - traj_2_angle, 2 * math.pi) return difference < theta/2.0 or difference > 2 * math.pi - theta/2.0

def distance_preference(traj_1_dist, traj_2_dist, dist_threshold): if traj_1_dist > dist_threshold and traj_2_dist > dist_threshold: return 1.0 else: return 1.0 if traj_1_dist > traj_2_dist else 0.0

def intransitive_ant_preference(traj_1, traj_2): return 0.3 * distance_preference(traj_1.radius, traj_2.radius, 10.0) + 0.7 * angular_preference(traj_1.angle, traj_2.angle, math.pi/4)