# A Minimaximalist Approach to
Reinforcement Learning from Human Feedback

Gokul Swamy  Christoph Dann  Rahul Kidambi  Zhiwei Steven Wu  Alekh Agarwal

###### Abstract

We present Self-Play Preference Optimization (SPO), an algorithm for
reinforcement learning from human feedback. Our approach is minimalist in that
it does not require training a reward model nor unstable adversarial training
and is therefore rather simple to implement. Our approach is maximalist in
that it provably handles non-Markovian, intransitive, and stochastic
preferences while being robust to the compounding errors that plague offline
approaches to sequential prediction. To achieve the preceding qualities, we
build upon the concept of a Minimax Winner (MW), a notion of preference
aggregation from the social choice theory literature that frames learning from
preferences as a zero-sum game between two policies. By leveraging the
symmetry of this game, we prove that rather than using the traditional
technique of dueling two policies to compute the MW, we can simply have a
single agent play against itself while maintaining strong convergence
guarantees. Practically, this corresponds to sampling multiple trajectories
from a policy, asking a rater or preference model to compare them, and then
using the proportion of wins as the reward for a particular trajectory. We
demonstrate that on a suite of continuous control tasks, we are able to learn
significantly more efficiently than reward-model based approaches while
maintaining robustness to the intransitive and stochastic preferences that
frequently occur in practice when aggregating human judgments.

Machine Learning, ICML

##  1 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).

Figure 1: The standard pipeline (left) for preference-based RL / RLHF involves
training a reward model based on a dataset of pairwise preferences and then
optimizing it via RL. We introduce SPO (right), an iterative method that
instead optimizes directly based on preference feedback provided by a rater or
preference model, with each trajectory getting a reward based on the
proportion of other on-policy trajectories it is preferred to. We prove and
validate empirically that this approach is more robust to intransitive, non-
Markovian, and noisy preferences than prior works.

(a) Transitive Preferences

(b) Stochastic Preferences

(c) Non-Markovian Preferences

(d) Intransitive Preferences

Figure 2: SPO gives us a unified approach to optimize a variety of preference
structures. Starting with the idealized case where preferences are consistent
with a single underlying reward signal (a), SPO is more sample-efficient than
iterative Reward Modeling (RM) based approaches. Moreover, SPO learns more
reliably than RM-based approaches with stochastic preferences, where we flip
preferences corresponding to a ground truth reward with increasing probability
(b). Furthermore, SPO handles complex non-Markovian preferences (c) such as
learning to maximize rewards over the first three-quarters of a trajectory
while not crossing a threshold on returns in the last quarter, despite
searching over a class of Markovian policies. Lastly, considering intransitive
preferences generated by aggregating different sub-populations where a single
underlying reward function cannot explain the observed preferences, SPO
computes a near-exact Minimax Winner (MW) (d).

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.

Algorithmic Family | Example | Compounding Errors | Intransitive Preferences
---|---|---|---
Offline, Reward-Based |  DPO (Rafailov et al., 2023) |  ✗, Example B.1 |  ✗, Theorem 3.4
Online, Reward-Based |  PPO (Ouyang et al., 2022) | ✓ |  ✗, Theorem 3.4
Online, Preference-Based |  SPO (ours) | ✓ | ✓
Table 1: An taxonomy of RLHF algorithms and the sorts of issues they are
robust to.

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.

##  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.

##  3 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.

###  3.1 Preliminaries

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. 111We 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

$\mathcal{P}:\Xi\times\Xi\rightarrow[-1,1]$ (1)

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

$\mathcal{P}(\pi_{1},\pi_{2})\triangleq\mathbb{E}_{\xi_{1}\sim\pi_{1},\xi_{2}\sim\pi_{2}}[\mathcal{P}(\xi_{1},\xi_{2})].$
(2)

###  3.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.

${a}$${b}$${c}$${d}$${a}$${0}$${{\color[rgb]{0,0.5,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.5,0}+1}}$${{\color[rgb]{0,0.5,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.5,0}+1}}$${{\color[rgb]{0.9765625,0.39453125,0.39453125}\definecolor[named]{pgfstrokecolor}{rgb}{0.9765625,0.39453125,0.39453125}-1}}$${b}$${{\color[rgb]{0.9765625,0.39453125,0.39453125}\definecolor[named]{pgfstrokecolor}{rgb}{0.9765625,0.39453125,0.39453125}-1}}$${0}$${{\color[rgb]{0,0.5,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.5,0}+1}}$${{\color[rgb]{0.9765625,0.39453125,0.39453125}\definecolor[named]{pgfstrokecolor}{rgb}{0.9765625,0.39453125,0.39453125}-1}}$${c}$${{\color[rgb]{0.9765625,0.39453125,0.39453125}\definecolor[named]{pgfstrokecolor}{rgb}{0.9765625,0.39453125,0.39453125}-1}}$${{\color[rgb]{0.9765625,0.39453125,0.39453125}\definecolor[named]{pgfstrokecolor}{rgb}{0.9765625,0.39453125,0.39453125}-1}}$${0}$${{\color[rgb]{0,0.5,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.5,0}+1}}$${d}$${{\color[rgb]{0,0.5,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.5,0}+1}}$${{\color[rgb]{0,0.5,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.5,0}+1}}$${{\color[rgb]{0.9765625,0.39453125,0.39453125}\definecolor[named]{pgfstrokecolor}{rgb}{0.9765625,0.39453125,0.39453125}-1}}$${0}$
Figure 3: A simple preference function $\mathcal{P}_{1}$ over $(a,b,c,d)$.
$\mathcal{P}_{1}(x,y)=1$ if $x\succ y$, $-1$ if $y\succ x$, and $0$ if $x\sim
y$.

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

$\mathsf{CW}(\mathcal{P})\triangleq\operatorname*{\arg\\!\max}_{\pi\in\Pi}\sum_{\pi^{\prime}\in\Pi}\mathcal{P}(\pi,\pi^{\prime}).$
(3)

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).222For 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

$\min_{z\in\\{a,b,c,d\\}}\frac{1}{3}(\mathcal{P}_{1}(a,z)+\mathcal{P}_{1}(c,z)+\mathcal{P}_{1}(d,z))=0.$

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:

$\displaystyle\mathsf{MW}(\mathcal{P})\triangleq\bigg{(}$
$\displaystyle\operatorname*{\arg\\!\max}_{p\in\Delta(\Pi)}\min_{q\in\Delta(\Pi)}\mathbb{E}_{\pi_{1}\sim
p,\pi_{2}\sim q}[\mathcal{P}(\pi_{1},\pi_{2})],$
$\displaystyle\operatorname*{\arg\\!\min}_{q\in\Delta(\Pi)}\max_{p\in\Delta(\Pi)}\mathbb{E}_{\pi_{1}\sim
p,\pi_{2}\sim q}[\mathcal{P}(\pi_{1},\pi_{2})]\bigg{)}.$

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:

$\widetilde{p}(\xi)=\sum_{\pi\in\Pi}p(\pi)p(\xi|\pi).$ (4)

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.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.

######  Lemma 3.1.

$\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.

######  Definition 3.2.

$\mathcal{O}$ is a no-regret online linear optimization algorithm over
$\Delta(\Pi)$ if it produces iterates
$p_{t+1}=\mathcal{O}(\ell_{1:t})\in\Delta(\Pi)$ such that, for any sequence of
$T$ linear loss functions of the form $\ell_{t}(p)=\mathbb{E}_{\pi\sim
p}[f_{t}(\pi)]\in[-1,1]$ (with $f_{t}~{}:~{}\Pi\to[-1,1]$), we have

$\sum_{t=1}^{T}\ell_{t}(p_{t})-\min_{p^{\star}\in\Delta(\Pi)}\sum_{t=1}^{T}\ell_{t}(p^{\star})\leq\mathsf{Reg}(T),$
(5)

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

$\ell_{t}^{\texttt{SPO}}(p)\triangleq\mathbb{E}_{\pi\sim p,\pi^{\prime}\sim
p_{t}}[-\mathcal{P}(\pi,\pi^{\prime}))].$ (6)

We can now state our main result.

######  Theorem 3.3.

Consider a single copy of an algorithm $\mathcal{O}$ which satisfies
Definition 5. Initialize $p_{1}\in\Delta(\Pi)$ and set
$p_{t+1}=\mathcal{O}(\ell^{\texttt{SPO}}_{1:t})$. Then,
$\bar{p}=(p_{1}+\ldots+p_{T})/T$ is a $\frac{2\mathsf{Reg}(T)}{T}$-approximate
Minimax Winner. [Proof]

For the simplicity of presentation, Theorem 3.3 is stated and proved assuming
full feedback, where we observe $\ell_{t}^{\texttt{SPO}}(p_{t})$ at round $t$.
In Appendix A.6, we generalize the argument to the more realistic bandit
feedback setting, where we only observe a preference
$\mathcal{P}(\pi,\pi^{\prime})$ for some $\pi,\pi^{\prime}$. The extension
uses the standard importance sampling argument to construct an unbiased
estimate of the population loss.

######  Proof Sketch.

Consider a pair of strategies, $p,q\in\Delta(\Pi)$. Define
$\ell_{t}^{1}(p)=\mathbb{E}_{\pi\sim p,\pi^{\prime}\sim
q_{t}}[-\mathcal{P}(\pi,\pi^{\prime}))]$ and
$\ell_{t}^{2}(q)=\mathbb{E}_{\pi\sim p_{t},\pi^{\prime}\sim
q}[\mathcal{P}(\pi,\pi^{\prime}))]$. By the results of Freund & Schapire
(1997), we know that updating $p_{t+1}=\mathcal{O}(\ell_{1:t}^{1})$ and
$q_{t+1}=\mathcal{O}(\ell_{1:t}^{2})$ implies that average strategies
$\bar{p}=\frac{1}{t}\sum_{i}^{t}p_{i}$, $\bar{q}=\frac{1}{t}\sum_{i}^{t}q_{i}$
converge to a Nash equilibrium (Minimax Winner) at the rate of the underlying
no-regret algorithm. By construction, we set $p_{0}=q_{0}$. This implies that
$\ell_{0}^{1}(p)=\mathbb{E}_{\pi\sim p,\pi^{\prime}\sim
q_{0}}[-\mathcal{P}(\pi,\pi^{\prime}))]=\mathbb{E}_{\pi\sim p,\pi^{\prime}\sim
p_{0}}[-\mathcal{P}(\pi,\pi^{\prime}))]=\mathbb{E}_{\pi\sim
p_{0},\pi^{\prime}\sim p}[-\mathcal{P}(\pi,\pi^{\prime}))]=\ell_{0}^{2}(p)$
due to the anti-symmetry of $\mathcal{P}$. We now proceed by induction. If, at
some time $\tau$, $p_{\tau}$ and $q_{\tau}$ have the same strategy and perform
updates based on the same loss function, for any deterministic $\mathcal{O}$,
$p_{\tau+1}=q_{\tau+1}$. For randomized $\mathcal{O}$, our argument still
applies as we describe in the full proof. Then, by the anti-symmetry of
$\mathcal{P}$, we have that $\ell_{\tau+1}^{1}=\ell_{\tau+1}^{2}$. Hence, by
induction, we have that $p_{t}=q_{t}$, $\forall t\in[T]$. Thus, we only need
to simulate a single $p$ with losses
$\ell_{t}^{\texttt{SPO}}(p)=\mathbb{E}_{\pi\sim p,\pi^{\prime}\sim
p_{t}}[-\mathcal{P}(\pi,\pi^{\prime}))]$ to compute a Minimax Winner.

The above result implies that if we run our algorithm for long enough, we can
get arbitrarily close to an exact MW.333For 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.444We 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:

$r_{t}^{\texttt{SPO}}(\xi)\triangleq\mathbb{E}_{\begin{subarray}{c}\xi^{\prime}\sim\widetilde{p}_{t}\end{subarray}}[\mathcal{P}(\xi,\xi^{\prime})].$
(7)

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

######  Theorem 3.4.

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]

######  Proof Sketch.

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 $[1,0,0]$), 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.

######  Corollary 3.5 (Informal).

Suppose that there exists $\pi^{*}\in\Pi$ such that
$\mathcal{P}(\pi^{*},\pi)>\Delta$ for all $\pi\neq\pi^{*}$ and
$-\Delta\leq\mathcal{P}(\pi,\pi^{\prime})\leq\Delta$ for all
$\pi,\pi^{\prime}\neq\pi^{*}$. Then, after $T$ rounds, the average solution
$\bar{p}$ computed using Hedge as oracle $\mathcal{O}$ and
$\ell_{t}^{\texttt{SPO}}$ is an $\widetilde{O}(\frac{|\Pi|}{\Delta
T})$-approximate Minimax Winner.

###  3.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.

######  Corollary 3.6.

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.

1: Input: Learning rate $\eta$, Iterations $T$, Preference fn. $\mathcal{P}$.

2: Output: Trained policy $\pi$.

3: Initialize $\pi_{h}(\cdot|\phi)=\mathsf{Unif}(\mathcal{A})$,
$\forall\phi\in\Phi_{h},h\in[H]$.

4: for $t$ in $1\dots T$ do

5: Compute
$r_{t}(\xi)=\mathbb{E}_{\xi^{\prime}\sim\pi_{t}}\mathcal{P}(\xi,\xi^{\prime})$.

6: Set
$Q_{t}^{h}(\phi,a)=\mathbb{E}_{\xi\sim\pi_{t}}[r_{t}(\xi)|\phi_{h}=\phi,a_{h}=a]$.

7: Set
$A_{t}^{h}(\phi,a)=Q_{t}^{h}(\phi,a)-\mathbb{E}_{a^{\prime}\sim\pi_{t}^{h}(\phi)}[Q_{t}^{h}(\phi,a^{\prime})]$.

8: for $\phi,a,h\in\Phi_{h}\times\mathcal{A}\times[H]$ do

9: // use no-regret algo for update

10: $\pi_{t+1}^{h}(a|\phi)\propto\pi_{t}^{h}(a|\phi)\exp{(\eta
A_{t}^{h}(\phi,a))}$.

11: end for

12: end for

13: Return  $\bar{\pi}$, uniform mixture of $\pi_{1:T}$.

Algorithm 1 SPO (Theoretical Version)

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.

1: Input: Iterations $T$, Preference fn. $\mathcal{P}$, Queue size $B$,
Reinforcement learning algo. $\mathsf{RL}:\Pi\times\mathcal{D}\to\Pi$.

2: Output: Trained policy $\pi$.

3: Initialize $\pi_{1}\in\Pi$, $Q\leftarrow[\xi_{1:B}\sim\pi_{1}]$.

4: for $t$ in $1\dots T$ do

5: Sample $\xi_{t}\sim\pi_{t}$.

6: Compute
$r_{t}(\xi_{t})=\frac{1}{|Q|}\sum_{q=1}^{B}\mathcal{P}(\xi_{t},\xi_{q})$.

7: Set $r^{h}_{t}=r_{t}(\xi_{t})/H$, $\forall h\in[H]$.

8: // use PPO, TRPO, SAC ...

9:
$\pi_{t+1}\leftarrow\mathsf{RL}(\pi_{t},\mathcal{D}=\\{(s^{h}_{t},a^{h}_{t},r^{h}_{t})\\}_{h\in[H]})$.

10: $Q\leftarrow[\xi_{2},\dots,\xi_{B},\xi_{t}]$.

11: end for

12: Return  best of $\pi_{1:T}$ on validation data.

Algorithm 2 SPO (Practical Version)

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.

######  Lemma 3.7.

Consider a trajectory-level reward function $r$ and define
$\Pi^{\star}=\operatorname*{\arg\\!\max}_{\pi\in\Pi}\mathbb{E}_{\xi\sim\pi}[r(\xi)]$
as the corresponding set of optimal policies. For all $(s_{t},a_{t})$ in any
$\xi$, let $\tilde{r}(s_{t},a_{t})=r(\xi)/H$. Then, we have that
$\Pi^{\star}=\operatorname*{\arg\\!\max}_{\pi\in\Pi}\mathbb{E}_{\xi\sim\pi}[\sum_{h}^{H}\tilde{r}(s_{t},a_{t})]$.
[Proof]

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.

#### Frequency of Querying Online Preference Oracle.

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})$.

##  4 Experiments

Figure 4: Across a variety of intransitive preferences over a discrete set of
three options, SPO can compute the Minimax Winner almost exactly. Each
preference function is generated by aggregating three sub-populations, each of
which has transitive preferences internally, in different proportions – see
Appendix D.1 for more details.

Figure 5: We visualize the position of our agent at the end of an episode over
the course of training. Each dot corresponds to 100k timesteps of training and
each plot corresponds to a separate seed. We see our agent trace out a circle
of radius 10 (the Minimax Winner) on average.

Figure 6: We see that when the preferred trajectory is that with the higher
ground-truth reward, SPO is able to match and sometimes exceed the sample-
efficiency of reward-model based approaches. Standard errors computed over 10
seeds.

Figure 7: We ablate the robustness of SPO and reward-model based approaches to
preference feedback being flipped w.p. $\epsilon$. We find that SPO is able to
tolerate a greater degree of noise in preferences before failing to
approximately match noiseless performance and on average takes an extra $0.1$
probability of noise to degrade to the performance of RM.

Figure 8: We compare SPO and RM-based approaches on a non-Markovian task:
maximize the reward subject to the constraint that the total reward accrued
during the last quarter must be at most $r_{\text{max}}$. We see that that SPO
is able to learn policies that exploit their freedom early in the episode
while RM is unable to cross the $4r_{\text{max}}$ threshold

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

  1. 1.

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.

  2. 2.

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.

  3. 3.

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.

  4. 4.

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.

Maximum Reward Preference. We next consider tasks where the preferences are
determined according to comparisons based on the underlying ground truth
reward function, i.e.
$\mathcal{P}_{1}(\xi,\xi^{\prime})=2\cdot\mathbbm{1}[r(\xi)>r(\xi^{\prime})]-1$,
where $r(\xi)=\sum_{t=1}^{H}r_{\text{GT}}(s^{\xi}_{t},a^{\xi}_{t})$, with
$r_{\text{GT}}(s_{t}^{\xi},a_{t}^{\xi})$ denoting the ground truth reward for
the $t^{\text{th}}$ state-action pair in trajectory $\xi$. Naturally, this is
the most favorable setting for utilizing an RM based approach, where one might
hope to leverage the generalization ability of an RM to perform careful credit
assignment for sample efficient learning. However, based on Figure 6, this
isn’t the case in practice. This dovetails with our Corollary A.2 on the fast
rates enjoyed by SPO when preferences are explained by a reward function.
Moreover, for tasks like hopper:stand, we see that the reward model’s struggle
to learn based on trajectory-level feedback prevents the agent from
meaningfully improving.

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

$r_{3}(\xi)=\begin{cases}\sum_{h=1}^{H}r(s_{h},a_{h}),\quad\,\,\sum_{h=\frac{3}{4}H}^{H}r(s_{h},a_{h})\leq
r_{\text{max}}\\\ -H,\hfill\text{o.w.}\\\ \end{cases}$

This induces the following set of preferences:

$\mathcal{P}_{3}(\xi,\xi^{\prime})=2\cdot\mathbbm{1}\left[r_{3}(\xi)>r_{3}(\xi^{\prime})\right]-1.$

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.

##  5 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).

##  6 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

  * Afsar et al. (2022) Afsar, M. M., Crump, T., and Far, B.  Reinforcement learning based recommender systems: A survey.  _ACM Computing Surveys_ , 55(7):1–38, 2022.
  * Agarwal et al. (2021) Agarwal, A., Kakade, S. M., Lee, J. D., and Mahajan, G.  On the theory of policy gradient methods: Optimality, approximation, and distribution shift.  _The Journal of Machine Learning Research_ , 22(1):4431–4506, 2021.
  * Agranov & Ortoleva (2017) Agranov, M. and Ortoleva, P.  Stochastic choice and preferences for randomization.  _Journal of Political Economy_ , 125(1):40–68, 2017.
  * Ailon & Mohri (2010) Ailon, N. and Mohri, M.  Preference-based learning to rank.  _Machine Learning_ , 80:189–211, 2010.
  * Akrour et al. (2012) Akrour, R., Schoenauer, M., and Sebag, M.  April: Active preference learning-based reinforcement learning.  In _Machine Learning and Knowledge Discovery in Databases: European Conference, ECML PKDD 2012, Bristol, UK, September 24-28, 2012. Proceedings, Part II 23_ , pp. 116–131. Springer, 2012.
  * Arrow (1950) Arrow, K. J.  A difficulty in the concept of social welfare.  _Journal of political economy_ , 58(4):328–346, 1950.
  * Auer et al. (2002) Auer, P., Cesa-Bianchi, N., Freund, Y., and Schapire, R. E.  The nonstochastic multiarmed bandit problem.  _SIAM journal on computing_ , 32(1):48–77, 2002.
  * Azar et al. (2023) Azar, M. G., Rowland, M., Piot, B., Guo, D., Calandriello, D., Valko, M., and Munos, R.  A general theoretical paradigm to understand learning from human preferences.  _arXiv preprint arXiv:2310.12036_ , 2023.
  * Bai et al. (2022a) Bai, Y., Jones, A., Ndousse, K., Askell, A., Chen, A., DasSarma, N., Drain, D., Fort, S., Ganguli, D., Henighan, T., et al.  Training a helpful and harmless assistant with reinforcement learning from human feedback.  _arXiv preprint arXiv:2204.05862_ , 2022a.
  * Bai et al. (2022b) Bai, Y., Kadavath, S., Kundu, S., Askell, A., Kernion, J., Jones, A., Chen, A., Goldie, A., Mirhoseini, A., McKinnon, C., Chen, C., Olsson, C., Olah, C., Hernandez, D., Drain, D., Ganguli, D., Li, D., Tran-Johnson, E., Perez, E., Kerr, J., Mueller, J., Ladish, J., Landau, J., Ndousse, K., Lukosuite, K., Lovitt, L., Sellitto, M., Elhage, N., Schiefer, N., Mercado, N., DasSarma, N., Lasenby, R., Larson, R., Ringer, S., Johnston, S., Kravec, S., Showk, S. E., Fort, S., Lanham, T., Telleen-Lawton, T., Conerly, T., Henighan, T., Hume, T., Bowman, S. R., Hatfield-Dodds, Z., Mann, B., Amodei, D., Joseph, N., McCandlish, S., Brown, T., and Kaplan, J.  Constitutional ai: Harmlessness from ai feedback, 2022b.
  * Bengs et al. (2021) Bengs, V., Busa-Fekete, R., Mesaoudi-Paul, A. E., and HÃllermeier, E.  Preference-based online learning with dueling bandits: A survey.  _Journal of Machine Learning Research_ , 22(7):1–108, 2021.  URL http://jmlr.org/papers/v22/18-546.html.
  * Bıyık et al. (2020) Bıyık, E., Huynh, N., Kochenderfer, M. J., and Sadigh, D.  Active preference-based gaussian process regression for reward learning.  _arXiv preprint arXiv:2005.02575_ , 2020.
  * Bommasani et al. (2021) Bommasani, R., Hudson, D. A., Adeli, E., Altman, R., Arora, S., von Arx, S., Bernstein, M. S., Bohg, J., Bosselut, A., Brunskill, E., et al.  On the opportunities and risks of foundation models.  _arXiv preprint arXiv:2108.07258_ , 2021.
  * Bradley & Terry (1952) Bradley, R. A. and Terry, M. E.  Rank analysis of incomplete block designs: I. the method of paired comparisons.  _Biometrika_ , 39(3/4):324–345, 1952.
  * Brandl et al. (2016) Brandl, F., Brandt, F., and Seedig, H. G.  Consistent probabilistic social choice.  _Econometrica_ , 84(5):1839–1880, 2016.
  * Brockman et al. (2016) Brockman, G., Cheung, V., Pettersson, L., Schneider, J., Schulman, J., Tang, J., and Zaremba, W.  Openai gym.  _CoRR_ , abs/1606.01540, 2016.  URL http://arxiv.org/abs/1606.01540.
  * Cai et al. (2023) Cai, Y., Luo, H., Wei, C.-Y., and Zheng, W.  Uncoupled and convergent learning in two-player zero-sum markov games with bandit feedback, 2023.
  * Cakmak et al. (2011) Cakmak, M., Srinivasa, S. S., Lee, M. K., Forlizzi, J., and Kiesler, S.  Human preferences for robot-human hand-over configurations.  In _2011 IEEE/RSJ International Conference on Intelligent Robots and Systems_ , pp. 1986–1993. IEEE, 2011.
  * Chang et al. (2023) Chang, J. D., Brantley, K., Ramamurthy, R., Misra, D., and Sun, W.  Learning to generate better than your llm.  _arXiv preprint arXiv:2306.11816_ , 2023.
  * Chen et al. (2024) Chen, Z., Deng, Y., Yuan, H., Ji, K., and Gu, Q.  Self-play fine-tuning converts weak language models to strong language models, 2024.
  * Christiano et al. (2017) Christiano, P. F., Leike, J., Brown, T., Martic, M., Legg, S., and Amodei, D.  Deep reinforcement learning from human preferences.  _Advances in neural information processing systems_ , 30, 2017.
  * Daskalakis et al. (2017) Daskalakis, C., Ilyas, A., Syrgkanis, V., and Zeng, H.  Training gans with optimism.  _arXiv preprint arXiv:1711.00141_ , 2017.
  * Daskalakis et al. (2020) Daskalakis, C., Foster, D. J., and Golowich, N.  Independent policy gradient methods for competitive reinforcement learning.  _Advances in neural information processing systems_ , 33:5527–5540, 2020.
  * De Gemmis et al. (2009) De Gemmis, M., Iaquinta, L., Lops, P., Musto, C., Narducci, F., and Semeraro, G.  Preference learning in recommender systems.  _Preference Learning_ , 41:41–55, 2009.
  * Dudík et al. (2015) Dudík, M., Hofmann, K., Schapire, R. E., Slivkins, A., and Zoghi, M.  Contextual dueling bandits.  In _Conference on Learning Theory_ , pp. 563–587. PMLR, 2015.
  * Even-Dar et al. (2009) Even-Dar, E., Kakade, S. M., and Mansour, Y.  Online markov decision processes.  _Mathematics of Operations Research_ , 34(3):726–736, 2009.
  * Fey (2012) Fey, M.  Symmetric games with only asymmetric equilibria.  _Games and Economic Behavior_ , 75(1):424–427, 2012.
  * Fishburn (1984) Fishburn, P. C.  Probabilistic social choice based on simple voting comparisons.  _The Review of Economic Studies_ , 51(4):683–692, 1984.
  * Freund & Schapire (1997) Freund, Y. and Schapire, R. E.  A decision-theoretic generalization of on-line learning and an application to boosting.  _Journal of computer and system sciences_ , 55(1):119–139, 1997.
  * Gardner (1970) Gardner, M.  Mathematical games, Dec 1970.  URL https://www.scientificamerican.com/article/mathematical-games-1970-12/.
  * Goodfellow et al. (2014) Goodfellow, I., Pouget-Abadie, J., Mirza, M., Xu, B., Warde-Farley, D., Ozair, S., Courville, A., and Bengio, Y.  Generative adversarial nets.  _Advances in neural information processing systems_ , 27, 2014.
  * Haarnoja et al. (2018) Haarnoja, T., Zhou, A., Abbeel, P., and Levine, S.  Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with a stochastic actor.  In _International conference on machine learning_ , pp. 1861–1870. PMLR, 2018.
  * Hazan et al. (2016) Hazan, E. et al.  Introduction to online convex optimization.  _Foundations and Trends® in Optimization_ , 2(3-4):157–325, 2016.
  * Hejna et al. (2023) Hejna, J., Rafailov, R., Sikchi, H., Finn, C., Niekum, S., Knox, W. B., and Sadigh, D.  Contrastive prefence learning: Learning from human feedback without rl.  _arXiv preprint arXiv:2310.13639_ , 2023.
  * Hoffman et al. (2020) Hoffman, M. W., Shahriari, B., Aslanides, J., Barth-Maron, G., Momchev, N., Sinopalnikov, D., Stańczyk, P., Ramos, S., Raichuk, A., Vincent, D., et al.  Acme: A research framework for distributed reinforcement learning.  _arXiv preprint arXiv:2006.00979_ , 2020.
  * Ibarz et al. (2018) Ibarz, B., Leike, J., Pohlen, T., Irving, G., Legg, S., and Amodei, D.  Reward learning from human preferences and demonstrations in atari.  _Advances in neural information processing systems_ , 31, 2018.
  * Kakade (2001) Kakade, S. M.  A natural policy gradient.  _Advances in neural information processing systems_ , 14, 2001.
  * Kalai & Vempala (2005) Kalai, A. and Vempala, S.  Efficient algorithms for online decision problems.  _Journal of Computer and System Sciences_ , 71(3):291–307, 2005.
  * Kramer (1973) Kramer, G. H.  On a class of equilibrium conditions for majority rule.  _Econometrica_ , 41(2):285–97, 1973.  URL https://EconPapers.repec.org/RePEc:ecm:emetrp:v:41:y:1973:i:2:p:285-97.
  * Kreweras (1965) Kreweras, G.  Aggregation of preference orderings.  In _Mathematics and Social Sciences I: Proceedings of the seminars of Menthon-Saint-Bernard, France (1–27 July 1960) and of Gösing, Austria (3–27 July 1962)_ , pp. 73–79, 1965.
  * Lee et al. (2021a) Lee, K., Smith, L., and Abbeel, P.  Pebble: Feedback-efficient interactive reinforcement learning via relabeling experience and unsupervised pre-training.  _arXiv preprint arXiv:2106.05091_ , 2021a.
  * Lee et al. (2021b) Lee, K., Smith, L., Dragan, A., and Abbeel, P.  B-pref: Benchmarking preference-based reinforcement learning.  _arXiv preprint arXiv:2111.03026_ , 2021b.
  * Leslie & Collins (2006) Leslie, D. S. and Collins, E. J.  Generalised weakened fictitious play.  _Games and Economic Behavior_ , 56(2):285–298, 2006.
  * May (1954) May, K. O.  Intransitivity, utility, and the aggregation of preference patterns.  _Econometrica: Journal of the Econometric Society_ , pp. 1–13, 1954.
  * McMahan (2011) McMahan, B.  Follow-the-regularized-leader and mirror descent: Equivalence theorems and l1 regularization.  In _Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics_ , pp. 525–533. JMLR Workshop and Conference Proceedings, 2011.
  * Miller (1956) Miller, G. A.  The magical number seven, plus or minus two: Some limits on our capacity for processing information.  _Psychological review_ , 63(2):81, 1956.
  * Munos et al. (2023) Munos, R., Valko, M., Calandriello, D., Azar, M. G., Rowland, M., Guo, Z. D., Tang, Y., Geist, M., Mesnard, T., Michi, A., Selvi, M., Girgin, S., Momchev, N., Bachem, O., Mankowitz, D. J., Precup, D., and Piot, B.  Nash learning from human feedback, 2023.
  * Nash (1951) Nash, J.  Non-cooperative games.  _Annals of mathematics_ , pp. 286–295, 1951.
  * Ng et al. (1999) Ng, A. Y., Harada, D., and Russell, S.  Policy invariance under reward transformations: Theory and application to reward shaping.  In _Icml_ , volume 99, pp. 278–287. Citeseer, 1999.
  * Novoseller et al. (2020) Novoseller, E., Wei, Y., Sui, Y., Yue, Y., and Burdick, J.  Dueling posterior sampling for preference-based reinforcement learning.  In _Conference on Uncertainty in Artificial Intelligence_ , pp. 1029–1038. PMLR, 2020.
  * OpenAI et al. (2023) OpenAI, :, Achiam, J., Adler, S., Agarwal, S., Ahmad, L., Akkaya, I., Aleman, F. L., Almeida, D., Altenschmidt, J., Altman, S., Anadkat, S., Avila, R., Babuschkin, I., Balaji, S., Balcom, V., Baltescu, P., Bao, H., Bavarian, M., Belgum, J., Bello, I., Berdine, J., Bernadett-Shapiro, G., Berner, C., Bogdonoff, L., Boiko, O., Boyd, M., Brakman, A.-L., Brockman, G., Brooks, T., Brundage, M., Button, K., Cai, T., Campbell, R., Cann, A., Carey, B., Carlson, C., Carmichael, R., Chan, B., Chang, C., Chantzis, F., Chen, D., Chen, S., Chen, R., Chen, J., Chen, M., Chess, B., Cho, C., Chu, C., Chung, H. W., Cummings, D., Currier, J., Dai, Y., Decareaux, C., Degry, T., Deutsch, N., Deville, D., Dhar, A., Dohan, D., Dowling, S., Dunning, S., Ecoffet, A., Eleti, A., Eloundou, T., Farhi, D., Fedus, L., Felix, N., Fishman, S. P., Forte, J., Fulford, I., Gao, L., Georges, E., Gibson, C., Goel, V., Gogineni, T., Goh, G., Gontijo-Lopes, R., Gordon, J., Grafstein, M., Gray, S., Greene, R., Gross, J., Gu, S. S., Guo, Y., Hallacy, C., Han, J., Harris, J., He, Y., Heaton, M., Heidecke, J., Hesse, C., Hickey, A., Hickey, W., Hoeschele, P., Houghton, B., Hsu, K., Hu, S., Hu, X., Huizinga, J., Jain, S., Jain, S., Jang, J., Jiang, A., Jiang, R., Jin, H., Jin, D., Jomoto, S., Jonn, B., Jun, H., Kaftan, T., Łukasz Kaiser, Kamali, A., Kanitscheider, I., Keskar, N. S., Khan, T., Kilpatrick, L., Kim, J. W., Kim, C., Kim, Y., Kirchner, H., Kiros, J., Knight, M., Kokotajlo, D., Łukasz Kondraciuk, Kondrich, A., Konstantinidis, A., Kosic, K., Krueger, G., Kuo, V., Lampe, M., Lan, I., Lee, T., Leike, J., Leung, J., Levy, D., Li, C. M., Lim, R., Lin, M., Lin, S., Litwin, M., Lopez, T., Lowe, R., Lue, P., Makanju, A., Malfacini, K., Manning, S., Markov, T., Markovski, Y., Martin, B., Mayer, K., Mayne, A., McGrew, B., McKinney, S. M., McLeavey, C., McMillan, P., McNeil, J., Medina, D., Mehta, A., Menick, J., Metz, L., Mishchenko, A., Mishkin, P., Monaco, V., Morikawa, E., Mossing, D., Mu, T., Murati, M., Murk, O., Mély, D., Nair, A., Nakano, R., Nayak, R., Neelakantan, A., Ngo, R., Noh, H., Ouyang, L., O’Keefe, C., Pachocki, J., Paino, A., Palermo, J., Pantuliano, A., Parascandolo, G., Parish, J., Parparita, E., Passos, A., Pavlov, M., Peng, A., Perelman, A., de Avila Belbute Peres, F., Petrov, M., de Oliveira Pinto, H. P., Michael, Pokorny, Pokrass, M., Pong, V., Powell, T., Power, A., Power, B., Proehl, E., Puri, R., Radford, A., Rae, J., Ramesh, A., Raymond, C., Real, F., Rimbach, K., Ross, C., Rotsted, B., Roussez, H., Ryder, N., Saltarelli, M., Sanders, T., Santurkar, S., Sastry, G., Schmidt, H., Schnurr, D., Schulman, J., Selsam, D., Sheppard, K., Sherbakov, T., Shieh, J., Shoker, S., Shyam, P., Sidor, S., Sigler, E., Simens, M., Sitkin, J., Slama, K., Sohl, I., Sokolowsky, B., Song, Y., Staudacher, N., Such, F. P., Summers, N., Sutskever, I., Tang, J., Tezak, N., Thompson, M., Tillet, P., Tootoonchian, A., Tseng, E., Tuggle, P., Turley, N., Tworek, J., Uribe, J. F. C., Vallone, A., Vijayvergiya, A., Voss, C., Wainwright, C., Wang, J. J., Wang, A., Wang, B., Ward, J., Wei, J., Weinmann, C., Welihinda, A., Welinder, P., Weng, J., Weng, L., Wiethoff, M., Willner, D., Winter, C., Wolrich, S., Wong, H., Workman, L., Wu, S., Wu, J., Wu, M., Xiao, K., Xu, T., Yoo, S., Yu, K., Yuan, Q., Zaremba, W., Zellers, R., Zhang, C., Zhang, M., Zhao, S., Zheng, T., Zhuang, J., Zhuk, W., and Zoph, B.  Gpt-4 technical report, 2023.
  * Ouyang et al. (2022) Ouyang, L., Wu, J., Jiang, X., Almeida, D., Wainwright, C., Mishkin, P., Zhang, C., Agarwal, S., Slama, K., Ray, A., et al.  Training language models to follow instructions with human feedback.  _Advances in Neural Information Processing Systems_ , 35:27730–27744, 2022.
  * Pacchiano et al. (2023) Pacchiano, A., Saha, A., and Lee, J.  Dueling rl: Reinforcement learning with trajectory preferences, 2023.
  * Pomerleau (1988) Pomerleau, D. A.  Alvinn: An autonomous land vehicle in a neural network.  _Advances in neural information processing systems_ , 1, 1988.
  * Puterman (2014) Puterman, M. L.  _Markov decision processes: discrete stochastic dynamic programming_.  John Wiley & Sons, 2014.
  * Rafailov et al. (2023) Rafailov, R., Sharma, A., Mitchell, E., Ermon, S., Manning, C. D., and Finn, C.  Direct preference optimization: Your language model is secretly a reward model.  _arXiv preprint arXiv:2305.18290_ , 2023.
  * Ross et al. (2011) Ross, S., Gordon, G., and Bagnell, D.  A reduction of imitation learning and structured prediction to no-regret online learning.  In _Proceedings of the fourteenth international conference on artificial intelligence and statistics_ , pp. 627–635. JMLR Workshop and Conference Proceedings, 2011.
  * Sadigh et al. (2017) Sadigh, D., Dragan, A. D., Sastry, S., and Seshia, S. A.  Active preference-based learning of reward functions.  2017\.
  * Saha & Krishnamurthy (2022) Saha, A. and Krishnamurthy, A.  Efficient and optimal algorithms for contextual dueling bandits under realizability.  In _International Conference on Algorithmic Learning Theory_ , pp. 968–994. PMLR, 2022.
  * Saha et al. (2021) Saha, A., Koren, T., and Mansour, Y.  Adversarial dueling bandits.  In _International Conference on Machine Learning_ , pp. 9235–9244. PMLR, 2021.
  * Satterthwaite (1975) Satterthwaite, M. A.  Strategy-proofness and arrow’s conditions: Existence and correspondence theorems for voting procedures and social welfare functions.  _Journal of economic theory_ , 10(2):187–217, 1975.
  * Schulman et al. (2015) Schulman, J., Levine, S., Abbeel, P., Jordan, M., and Moritz, P.  Trust region policy optimization.  In _International conference on machine learning_ , pp. 1889–1897. PMLR, 2015.
  * Schulman et al. (2017) Schulman, J., Wolski, F., Dhariwal, P., Radford, A., and Klimov, O.  Proximal policy optimization algorithms.  _arXiv preprint arXiv:1707.06347_ , 2017.
  * Sen (1986) Sen, A.  Social choice theory.  _Handbook of mathematical economics_ , 3:1073–1181, 1986.
  * Sikchi et al. (2022) Sikchi, H., Saran, A., Goo, W., and Niekum, S.  A ranking game for imitation learning.  _arXiv preprint arXiv:2202.03481_ , 2022.
  * Simpson (1969) Simpson, P. B.  On Defining Areas of Voter Choice: Professor Tullock on Stable Voting.  _The Quarterly Journal of Economics_ , 83(3):478–490, 08 1969.  ISSN 0033-5533.  doi:10.2307/1880533.  URL https://doi.org/10.2307/1880533.
  * Sion (1958) Sion, M.  On general minimax theorems.  1958\.
  * Siththaranjan et al. (2023) Siththaranjan, A., Laidlaw, C., and Hadfield-Menell, D.  Distributional preference learning: Understanding and accounting for hidden context in rlhf.  _arXiv preprint arXiv:2312.08358_ , 2023.
  * Song et al. (2022) Song, Y., Zhou, Y., Sekhari, A., Bagnell, J. A., Krishnamurthy, A., and Sun, W.  Hybrid rl: Using both offline and online data can make rl efficient.  _arXiv preprint arXiv:2210.06718_ , 2022.
  * Stiennon et al. (2020) Stiennon, N., Ouyang, L., Wu, J., Ziegler, D., Lowe, R., Voss, C., Radford, A., Amodei, D., and Christiano, P. F.  Learning to summarize with human feedback.  _Advances in Neural Information Processing Systems_ , 33:3008–3021, 2020.
  * Sui et al. (2017) Sui, Y., Zhuang, V., Burdick, J. W., and Yue, Y.  Multi-dueling bandits with dependent arms.  _arXiv preprint arXiv:1705.00253_ , 2017.
  * Swamy et al. (2020) Swamy, G., Reddy, S., Levine, S., and Dragan, A. D.  Scaled autonomy: Enabling human operators to control robot fleets.  In _2020 IEEE International Conference on Robotics and Automation (ICRA)_ , pp. 5942–5948. IEEE, 2020.
  * Swamy et al. (2021) Swamy, G., Choudhury, S., Bagnell, J. A., and Wu, S.  Of moments and matching: A game-theoretic framework for closing the imitation gap.  In _International Conference on Machine Learning_ , pp. 10022–10032. PMLR, 2021.
  * Swamy et al. (2022a) Swamy, G., Choudhury, S., Bagnell, D., and Wu, S.  Causal imitation learning under temporally correlated noise.  In _International Conference on Machine Learning_ , pp. 20877–20890. PMLR, 2022a.
  * Swamy et al. (2022b) Swamy, G., Choudhury, S., Bagnell, J., and Wu, S. Z.  Sequence model imitation learning with unobserved contexts.  _Advances in Neural Information Processing Systems_ , 35:17665–17676, 2022b.
  * Swamy et al. (2023) Swamy, G., Wu, D., Choudhury, S., Bagnell, D., and Wu, S.  Inverse reinforcement learning without reinforcement learning.  In _International Conference on Machine Learning_ , pp. 33299–33318. PMLR, 2023.
  * Taori et al. (2023) Taori, R., Gulrajani, I., Zhang, T., Dubois, Y., Li, X., Guestrin, C., Liang, P., and Hashimoto, T. B.  Stanford alpaca: An instruction-following llama model, 2023.
  * Tassa et al. (2018) Tassa, Y., Doron, Y., Muldal, A., Erez, T., Li, Y., de Las Casas, D., Budden, D., Abdolmaleki, A., Merel, J., Lefrancq, A., Lillicrap, T. P., and Riedmiller, M. A.  Deepmind control suite.  _CoRR_ , abs/1801.00690, 2018.  URL http://arxiv.org/abs/1801.00690.
  * Team et al. (2023) Team, G., Anil, R., Borgeaud, S., Wu, Y., Alayrac, J.-B., Yu, J., Soricut, R., Schalkwyk, J., Dai, A. M., Hauth, A., Millican, K., Silver, D., Petrov, S., Johnson, M., Antonoglou, I., Schrittwieser, J., Glaese, A., Chen, J., Pitler, E., Lillicrap, T., Lazaridou, A., Firat, O., Molloy, J., Isard, M., Barham, P. R., Hennigan, T., Lee, B., Viola, F., Reynolds, M., Xu, Y., Doherty, R., Collins, E., Meyer, C., Rutherford, E., Moreira, E., Ayoub, K., Goel, M., Tucker, G., Piqueras, E., Krikun, M., Barr, I., Savinov, N., Danihelka, I., Roelofs, B., White, A., Andreassen, A., von Glehn, T., Yagati, L., Kazemi, M., Gonzalez, L., Khalman, M., Sygnowski, J., Frechette, A., Smith, C., Culp, L., Proleev, L., Luan, Y., Chen, X., Lottes, J., Schucher, N., Lebron, F., Rrustemi, A., Clay, N., Crone, P., Kocisky, T., Zhao, J., Perz, B., Yu, D., Howard, H., Bloniarz, A., Rae, J. W., Lu, H., Sifre, L., Maggioni, M., Alcober, F., Garrette, D., Barnes, M., Thakoor, S., Austin, J., Barth-Maron, G., Wong, W., Joshi, R., Chaabouni, R., Fatiha, D., Ahuja, A., Liu, R., Li, Y., Cogan, S., Chen, J., Jia, C., Gu, C., Zhang, Q., Grimstad, J., Hartman, A. J., Chadwick, M., Tomar, G. S., Garcia, X., Senter, E., Taropa, E., Pillai, T. S., Devlin, J., Laskin, M., de Las Casas, D., Valter, D., Tao, C., Blanco, L., Badia, A. P., Reitter, D., Chen, M., Brennan, J., Rivera, C., Brin, S., Iqbal, S., Surita, G., Labanowski, J., Rao, A., Winkler, S., Parisotto, E., Gu, Y., Olszewska, K., Zhang, Y., Addanki, R., Miech, A., Louis, A., Shafey, L. E., Teplyashin, D., Brown, G., Catt, E., Attaluri, N., Balaguer, J., Xiang, J., Wang, P., Ashwood, Z., Briukhov, A., Webson, A., Ganapathy, S., Sanghavi, S., Kannan, A., Chang, M.-W., Stjerngren, A., Djolonga, J., Sun, Y., Bapna, A., Aitchison, M., Pejman, P., Michalewski, H., Yu, T., Wang, C., Love, J., Ahn, J., Bloxwich, D., Han, K., Humphreys, P., Sellam, T., Bradbury, J., Godbole, V., Samangooei, S., Damoc, B., Kaskasoli, A., Arnold, S. M. R., Vasudevan, V., Agrawal, S., Riesa, J., Lepikhin, D., Tanburn, R., Srinivasan, S., Lim, H., Hodkinson, S., Shyam, P., Ferret, J., Hand, S., Garg, A., Paine, T. L., Li, J., Li, Y., Giang, M., Neitz, A., Abbas, Z., York, S., Reid, M., Cole, E., Chowdhery, A., Das, D., Rogozińska, D., Nikolaev, V., Sprechmann, P., Nado, Z., Zilka, L., Prost, F., He, L., Monteiro, M., Mishra, G., Welty, C., Newlan, J., Jia, D., Allamanis, M., Hu, C. H., de Liedekerke, R., Gilmer, J., Saroufim, C., Rijhwani, S., Hou, S., Shrivastava, D., Baddepudi, A., Goldin, A., Ozturel, A., Cassirer, A., Xu, Y., Sohn, D., Sachan, D., Amplayo, R. K., Swanson, C., Petrova, D., Narayan, S., Guez, A., Brahma, S., Landon, J., Patel, M., Zhao, R., Villela, K., Wang, L., Jia, W., Rahtz, M., Giménez, M., Yeung, L., Lin, H., Keeling, J., Georgiev, P., Mincu, D., Wu, B., Haykal, S., Saputro, R., Vodrahalli, K., Qin, J., Cankara, Z., Sharma, A., Fernando, N., Hawkins, W., Neyshabur, B., Kim, S., Hutter, A., Agrawal, P., Castro-Ros, A., van den Driessche, G., Wang, T., Yang, F., yiin Chang, S., Komarek, P., McIlroy, R., Lučić, M., Zhang, G., Farhan, W., Sharman, M., Natsev, P., Michel, P., Cheng, Y., Bansal, Y., Qiao, S., Cao, K., Shakeri, S., Butterfield, C., Chung, J., Rubenstein, P. K., Agrawal, S., Mensch, A., Soparkar, K., Lenc, K., Chung, T., Pope, A., Maggiore, L., Kay, J., Jhakra, P., Wang, S., Maynez, J., Phuong, M., Tobin, T., Tacchetti, A., Trebacz, M., Robinson, K., Katariya, Y., Riedel, S., Bailey, P., Xiao, K., Ghelani, N., Aroyo, L., Slone, A., Houlsby, N., Xiong, X., Yang, Z., Gribovskaya, E., Adler, J., Wirth, M., Lee, L., Li, M., Kagohara, T., Pavagadhi, J., Bridgers, S., Bortsova, A., Ghemawat, S., Ahmed, Z., Liu, T., Powell, R., Bolina, V., Iinuma, M., Zablotskaia, P., Besley, J., Chung, D.-W., Dozat, T., Comanescu, R., Si, X., Greer, J., Su, G., Polacek, M., Kaufman, R. L., Tokumine, S., Hu, H., Buchatskaya, E., Miao, Y., Elhawaty, M., Siddhant, A., Tomasev, N., Xing, J., Greer, C., Miller, H., Ashraf, S., Roy, A., Zhang, Z., Ma, A., Filos, A., Besta, M., Blevins, R., Klimenko, T., Yeh, C.-K., Changpinyo, S., Mu, J., Chang, O., Pajarskas, M., Muir, C., Cohen, V., Lan, C. L., Haridasan, K., Marathe, A., Hansen, S., Douglas, S., Samuel, R., Wang, M., Austin, S., Lan, C., Jiang, J., Chiu, J., Lorenzo, J. A., Sjösund, L. L., Cevey, S., Gleicher, Z., Avrahami, T., Boral, A., Srinivasan, H., Selo, V., May, R., Aisopos, K., Hussenot, L., Soares, L. B., Baumli, K., Chang, M. B., Recasens, A., Caine, B., Pritzel, A., Pavetic, F., Pardo, F., Gergely, A., Frye, J., Ramasesh, V., Horgan, D., Badola, K., Kassner, N., Roy, S., Dyer, E., Campos, V., Tomala, A., Tang, Y., Badawy, D. E., White, E., Mustafa, B., Lang, O., Jindal, A., Vikram, S., Gong, Z., Caelles, S., Hemsley, R., Thornton, G., Feng, F., Stokowiec, W., Zheng, C., Thacker, P., Çağlar Ünlü, Zhang, Z., Saleh, M., Svensson, J., Bileschi, M., Patil, P., Anand, A., Ring, R., Tsihlas, K., Vezer, A., Selvi, M., Shevlane, T., Rodriguez, M., Kwiatkowski, T., Daruki, S., Rong, K., Dafoe, A., FitzGerald, N., Gu-Lemberg, K., Khan, M., Hendricks, L. A., Pellat, M., Feinberg, V., Cobon-Kerr, J., Sainath, T., Rauh, M., Hashemi, S. H., Ives, R., Hasson, Y., Li, Y., Noland, E., Cao, Y., Byrd, N., Hou, L., Wang, Q., Sottiaux, T., Paganini, M., Lespiau, J.-B., Moufarek, A., Hassan, S., Shivakumar, K., van Amersfoort, J., Mandhane, A., Joshi, P., Goyal, A., Tung, M., Brock, A., Sheahan, H., Misra, V., Li, C., Rakićević, N., Dehghani, M., Liu, F., Mittal, S., Oh, J., Noury, S., Sezener, E., Huot, F., Lamm, M., Cao, N. D., Chen, C., Elsayed, G., Chi, E., Mahdieh, M., Tenney, I., Hua, N., Petrychenko, I., Kane, P., Scandinaro, D., Jain, R., Uesato, J., Datta, R., Sadovsky, A., Bunyan, O., Rabiej, D., Wu, S., Zhang, J., Vasudevan, G., Leurent, E., Alnahlawi, M., Georgescu, I., Wei, N., Zheng, I., Chan, B., Rabinovitch, P. G., Stanczyk, P., Zhang, Y., Steiner, D., Naskar, S., Azzam, M., Johnson, M., Paszke, A., Chiu, C.-C., Elias, J. S., Mohiuddin, A., Muhammad, F., Miao, J., Lee, A., Vieillard, N., Potluri, S., Park, J., Davoodi, E., Zhang, J., Stanway, J., Garmon, D., Karmarkar, A., Dong, Z., Lee, J., Kumar, A., Zhou, L., Evens, J., Isaac, W., Chen, Z., Jia, J., Levskaya, A., Zhu, Z., Gorgolewski, C., Grabowski, P., Mao, Y., Magni, A., Yao, K., Snaider, J., Casagrande, N., Suganthan, P., Palmer, E., Irving, G., Loper, E., Faruqui, M., Arkatkar, I., Chen, N., Shafran, I., Fink, M., Castaño, A., Giannoumis, I., Kim, W., Rybiński, M., Sreevatsa, A., Prendki, J., Soergel, D., Goedeckemeyer, A., Gierke, W., Jafari, M., Gaba, M., Wiesner, J., Wright, D. G., Wei, Y., Vashisht, H., Kulizhskaya, Y., Hoover, J., Le, M., Li, L., Iwuanyanwu, C., Liu, L., Ramirez, K., Khorlin, A., Cui, A., LIN, T., Georgiev, M., Wu, M., Aguilar, R., Pallo, K., Chakladar, A., Repina, A., Wu, X., van der Weide, T., Ponnapalli, P., Kaplan, C., Simsa, J., Li, S., Dousse, O., Yang, F., Piper, J., Ie, N., Lui, M., Pasumarthi, R., Lintz, N., Vijayakumar, A., Thiet, L. N., Andor, D., Valenzuela, P., Paduraru, C., Peng, D., Lee, K., Zhang, S., Greene, S., Nguyen, D. D., Kurylowicz, P., Velury, S., Krause, S., Hardin, C., Dixon, L., Janzer, L., Choo, K., Feng, Z., Zhang, B., Singhal, A., Latkar, T., Zhang, M., Le, Q., Abellan, E. A., Du, D., McKinnon, D., Antropova, N., Bolukbasi, T., Keller, O., Reid, D., Finchelstein, D., Raad, M. A., Crocker, R., Hawkins, P., Dadashi, R., Gaffney, C., Lall, S., Franko, K., Filonov, E., Bulanova, A., Leblond, R., Yadav, V., Chung, S., Askham, H., Cobo, L. C., Xu, K., Fischer, F., Xu, J., Sorokin, C., Alberti, C., Lin, C.-C., Evans, C., Zhou, H., Dimitriev, A., Forbes, H., Banarse, D., Tung, Z., Liu, J., Omernick, M., Bishop, C., Kumar, C., Sterneck, R., Foley, R., Jain, R., Mishra, S., Xia, J., Bos, T., Cideron, G., Amid, E., Piccinno, F., Wang, X., Banzal, P., Gurita, P., Noga, H., Shah, P., Mankowitz, D. J., Polozov, A., Kushman, N., Krakovna, V., Brown, S., Bateni, M., Duan, D., Firoiu, V., Thotakuri, M., Natan, T., Mohananey, A., Geist, M., Mudgal, S., Girgin, S., Li, H., Ye, J., Roval, O., Tojo, R., Kwong, M., Lee-Thorp, J., Yew, C., Yuan, Q., Bagri, S., Sinopalnikov, D., Ramos, S., Mellor, J., Sharma, A., Severyn, A., Lai, J., Wu, K., Cheng, H.-T., Miller, D., Sonnerat, N., Vnukov, D., Greig, R., Beattie, J., Caveness, E., Bai, L., Eisenschlos, J., Korchemniy, A., Tsai, T., Jasarevic, M., Kong, W., Dao, P., Zheng, Z., Liu, F., Yang, F., Zhu, R., Geller, M., Teh, T. H., Sanmiya, J., Gladchenko, E., Trdin, N., Sozanschi, A., Toyama, D., Rosen, E., Tavakkol, S., Xue, L., Elkind, C., Woodman, O., Carpenter, J., Papamakarios, G., Kemp, R., Kafle, S., Grunina, T., Sinha, R., Talbert, A., Goyal, A., Wu, D., Owusu-Afriyie, D., Du, C., Thornton, C., Pont-Tuset, J., Narayana, P., Li, J., Fatehi, S., Wieting, J., Ajmeri, O., Uria, B., Zhu, T., Ko, Y., Knight, L., Héliou, A., Niu, N., Gu, S., Pang, C., Tran, D., Li, Y., Levine, N., Stolovich, A., Kalb, N., Santamaria-Fernandez, R., Goenka, S., Yustalim, W., Strudel, R., Elqursh, A., Lakshminarayanan, B., Deck, C., Upadhyay, S., Lee, H., Dusenberry, M., Li, Z., Wang, X., Levin, K., Hoffmann, R., Holtmann-Rice, D., Bachem, O., Yue, S., Arora, S., Malmi, E., Mirylenka, D., Tan, Q., Koh, C., Yeganeh, S. H., Põder, S., Zheng, S., Pongetti, F., Tariq, M., Sun, Y., Ionita, L., Seyedhosseini, M., Tafti, P., Kotikalapudi, R., Liu, Z., Gulati, A., Liu, J., Ye, X., Chrzaszcz, B., Wang, L., Sethi, N., Li, T., Brown, B., Singh, S., Fan, W., Parisi, A., Stanton, J., Kuang, C., Koverkathu, V., Choquette-Choo, C. A., Li, Y., Lu, T., Ittycheriah, A., Shroff, P., Sun, P., Varadarajan, M., Bahargam, S., Willoughby, R., Gaddy, D., Dasgupta, I., Desjardins, G., Cornero, M., Robenek, B., Mittal, B., Albrecht, B., Shenoy, A., Moiseev, F., Jacobsson, H., Ghaffarkhah, A., Rivière, M., Walton, A., Crepy, C., Parrish, A., Liu, Y., Zhou, Z., Farabet, C., Radebaugh, C., Srinivasan, P., van der Salm, C., Fidjeland, A., Scellato, S., Latorre-Chimoto, E., Klimczak-Plucińska, H., Bridson, D., de Cesare, D., Hudson, T., Mendolicchio, P., Walker, L., Morris, A., Penchev, I., Mauger, M., Guseynov, A., Reid, A., Odoom, S., Loher, L., Cotruta, V., Yenugula, M., Grewe, D., Petrushkina, A., Duerig, T., Sanchez, A., Yadlowsky, S., Shen, A., Globerson, A., Kurzrok, A., Webb, L., Dua, S., Li, D., Lahoti, P., Bhupatiraju, S., Hurt, D., Qureshi, H., Agarwal, A., Shani, T., Eyal, M., Khare, A., Belle, S. R., Wang, L., Tekur, C., Kale, M. S., Wei, J., Sang, R., Saeta, B., Liechty, T., Sun, Y., Zhao, Y., Lee, S., Nayak, P., Fritz, D., Vuyyuru, M. R., Aslanides, J., Vyas, N., Wicke, M., Ma, X., Bilal, T., Eltyshev, E., Balle, D., Martin, N., Cate, H., Manyika, J., Amiri, K., Kim, Y., Xiong, X., Kang, K., Luisier, F., Tripuraneni, N., Madras, D., Guo, M., Waters, A., Wang, O., Ainslie, J., Baldridge, J., Zhang, H., Pruthi, G., Bauer, J., Yang, F., Mansour, R., Gelman, J., Xu, Y., Polovets, G., Liu, J., Cai, H., Chen, W., Sheng, X., Xue, E., Ozair, S., Yu, A., Angermueller, C., Li, X., Wang, W., Wiesinger, J., Koukoumidis, E., Tian, Y., Iyer, A., Gurumurthy, M., Goldenson, M., Shah, P., Blake, M., Yu, H., Urbanowicz, A., Palomaki, J., Fernando, C., Brooks, K., Durden, K., Mehta, H., Momchev, N., Rahimtoroghi, E., Georgaki, M., Raul, A., Ruder, S., Redshaw, M., Lee, J., Jalan, K., Li, D., Perng, G., Hechtman, B., Schuh, P., Nasr, M., Chen, M., Milan, K., Mikulik, V., Strohman, T., Franco, J., Green, T., Hassabis, D., Kavukcuoglu, K., Dean, J., and Vinyals, O.  Gemini: A family of highly capable multimodal models, 2023.
  * Touvron et al. (2023) Touvron, H., Martin, L., Stone, K., Albert, P., Almahairi, A., Babaei, Y., Bashlykov, N., Batra, S., Bhargava, P., Bhosale, S., Bikel, D., Blecher, L., Ferrer, C. C., Chen, M., Cucurull, G., Esiobu, D., Fernandes, J., Fu, J., Fu, W., Fuller, B., Gao, C., Goswami, V., Goyal, N., Hartshorn, A., Hosseini, S., Hou, R., Inan, H., Kardas, M., Kerkez, V., Khabsa, M., Kloumann, I., Korenev, A., Koura, P. S., Lachaux, M.-A., Lavril, T., Lee, J., Liskovich, D., Lu, Y., Mao, Y., Martinet, X., Mihaylov, T., Mishra, P., Molybog, I., Nie, Y., Poulton, A., Reizenstein, J., Rungta, R., Saladi, K., Schelten, A., Silva, R., Smith, E. M., Subramanian, R., Tan, X. E., Tang, B., Taylor, R., Williams, A., Kuan, J. X., Xu, P., Yan, Z., Zarov, I., Zhang, Y., Fan, A., Kambadur, M., Narang, S., Rodriguez, A., Stojnic, R., Edunov, S., and Scialom, T.  Llama 2: Open foundation and fine-tuned chat models, 2023.
  * Tucker et al. (2020) Tucker, M., Novoseller, E., Kann, C., Sui, Y., Yue, Y., Burdick, J. W., and Ames, A. D.  Preference-based learning for exoskeleton gait optimization.  In _2020 IEEE international conference on robotics and automation (ICRA)_ , pp. 2351–2357. IEEE, 2020.
  * Tversky (1969) Tversky, A.  Intransitivity of preferences.  _Psychological review_ , 76(1):31, 1969.
  * Viappiani & Boutilier (2010) Viappiani, P. and Boutilier, C.  Optimal bayesian recommendation sets and myopically optimal choice query sets.  _Advances in neural information processing systems_ , 23, 2010.
  * Wang et al. (2023) Wang, Y., Liu, Q., and Jin, C.  Is rlhf more difficult than standard rl?, 2023.
  * Williams (1992) Williams, R. J.  Simple statistical gradient-following algorithms for connectionist reinforcement learning.  _Machine learning_ , 8:229–256, 1992.
  * Wirth et al. (2017) Wirth, C., Akrour, R., Neumann, G., Fürnkranz, J., et al.  A survey of preference-based reinforcement learning methods.  _Journal of Machine Learning Research_ , 18(136):1–46, 2017.
  * Xie et al. (2021) Xie, T., Cheng, C.-A., Jiang, N., Mineiro, P., and Agarwal, A.  Bellman-consistent pessimism for offline reinforcement learning.  _Advances in neural information processing systems_ , 34:6683–6694, 2021.
  * Yue & Joachims (2009) Yue, Y. and Joachims, T.  Interactively optimizing information retrieval systems as a dueling bandits problem.  In _Proceedings of the 26th Annual International Conference on Machine Learning_ , pp. 1201–1208, 2009.
  * Yue et al. (2012) Yue, Y., Broder, J., Kleinberg, R., and Joachims, T.  The k-armed dueling bandits problem.  _Journal of Computer and System Sciences_ , 78(5):1538–1556, 2012.
  * Zhao et al. (2023) Zhao, Y., Joshi, R., Liu, T., Khalman, M., Saleh, M., and Liu, P. J.  Slic-hf: Sequence likelihood calibration with human feedback.  _arXiv preprint arXiv:2305.10425_ , 2023.
  * Zhu et al. (2023) Zhu, B., Frick, E., Wu, T., Zhu, H., and Jiao, J.  Starling-7b: Improving llm helpfulness & harmlessness with rlaif, November 2023.
  * Ziebart (2010) Ziebart, B. D.  _Modeling purposeful adaptive behavior with the principle of maximum causal entropy_.  Carnegie Mellon University, 2010.
  * Ziegler et al. (2020) Ziegler, D. M., Stiennon, N., Wu, J., Brown, T. B., Radford, A., Amodei, D., Christiano, P., and Irving, G.  Fine-tuning language models from human preferences, 2020.
  * Zinkevich (2003) Zinkevich, M.  Online convex programming and generalized infinitesimal gradient ascent.  In _Proceedings of the 20th international conference on machine learning (icml-03)_ , pp. 928–936, 2003.
  * Zinkevich et al. (2007) Zinkevich, M., Johanson, M., Bowling, M., and Piccione, C.  Regret minimization in games with incomplete information.  _Advances in neural information processing systems_ , 20, 2007.

##  Appendix A Proofs

###  A.1 Proof of Lemma 3.1

######  Proof.

We follow a similar proof strategy to Fey (2012). For convenience, we
interpret the preference $\mathcal{P}$ as a matrix of size $|\Pi|\times|\Pi|$
and will write things in matrix notation, i.e. $\mathbb{E}_{\pi_{1}\sim
p,\pi_{2}\sim q}[\mathcal{P}(\pi_{1},\pi_{2})]=p^{T}\mathcal{P}q$. We consider
some $(\hat{p},\hat{q})\in\mathsf{MW}(\mathcal{P})$ and will show that also
$(\hat{q},\hat{p})\in\mathsf{MW}(\mathcal{P})$. Since
$(\hat{p},\hat{q})\in\mathsf{MW}(\mathcal{P})$ and by the definition of a Nash
equilibrium,

$\displaystyle\quad\max_{q\in\Delta(\Pi)}\hat{p}^{T}\mathcal{P}q\leq\min_{p\in\Delta(\Pi)}p^{T}\mathcal{P}\hat{q}$
$\displaystyle\Rightarrow\max_{q\in\Delta(\Pi)}q^{T}\mathcal{P}^{T}\hat{p}\leq\min_{p\in\Delta(\Pi)}\hat{q}^{T}\mathcal{P}^{T}p$
$\displaystyle\Rightarrow\max_{q\in\Delta(\Pi)}-q^{T}\mathcal{P}\hat{p}\leq\min_{p\in\Delta(\Pi)}-\hat{q}^{T}\mathcal{P}p$
(By the anti-symmetry of $\mathcal{P}$)
$\displaystyle\Rightarrow-\min_{q\in\Delta(\Pi)}q^{T}\mathcal{P}\hat{p}\leq-\max_{p\in\Delta(\Pi)}\hat{q}^{T}\mathcal{P}p$
$\displaystyle\Rightarrow\min_{q\in\Delta(\Pi)}q^{T}\mathcal{P}\hat{p}\geq\max_{p\in\Delta(\Pi)}\hat{q}^{T}\mathcal{P}p$
$\displaystyle\Rightarrow\max_{q\in\Delta(\Pi)}\hat{q}^{T}\mathcal{P}q\leq\min_{p\in\Delta(\Pi)}p^{T}\mathcal{P}\hat{p}$

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

######  Proof.

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

$\max_{p^{\star}\in\Delta(\Pi)}\mathbb{E}_{\pi\sim p^{\star},\pi^{\prime}\sim
q}[\mathcal{P}(\pi,\pi^{\prime}))]-\min_{q^{\star}\in\Delta(\Pi)}\mathbb{E}_{\pi\sim
p,\pi^{\prime}\sim q^{\star}}[\mathcal{P}(\pi,\pi^{\prime}))]\leq\epsilon.$
(8)

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

$\ell_{t}^{1}(p)=\mathbb{E}_{\pi\sim p,\pi^{\prime}\sim
q_{t}}[-\mathcal{P}(\pi,\pi^{\prime})],\quad\ell_{t}^{2}(q)=\mathbb{E}_{\pi\sim
p_{t},\pi^{\prime}\sim q}[\mathcal{P}(\pi,\pi^{\prime})].$ (9)

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

$\mathsf{Reg}_{p}(T)=\sum_{t}^{T}\ell_{t}^{1}(p_{t})-\min_{p^{\star}\in\Delta(\Pi)}\sum_{t}^{T}\ell_{t}^{1}(p^{\star}),\quad\mathsf{Reg}_{q}(T)=\sum_{t}^{T}\ell_{t}^{2}(q_{t})-\min_{q^{\star}\in\Delta(\Pi)}\sum_{t}^{T}\ell_{t}^{2}(q^{\star}).$
(10)

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

$\displaystyle\ell_{0}^{1}(\sigma)$
$\displaystyle=\mathbb{E}_{\pi\sim\sigma,\pi^{\prime}\sim
q_{0}}[-\mathcal{P}(\pi,\pi^{\prime})]$ (11)
$\displaystyle=\mathbb{E}_{\pi\sim\sigma,\pi^{\prime}\sim
p_{0}}[-\mathcal{P}(\pi,\pi^{\prime})]$ (12)
$\displaystyle=\mathbb{E}_{\pi\sim
p_{0},\pi^{\prime}\sim\sigma}[\mathcal{P}(\pi,\pi^{\prime})]$ (By the anti-
symmetry of $\mathcal{P}$) $\displaystyle=\ell_{0}^{2}(\sigma)$ (13)

If, at some time $\tau$, $p_{\tau}$ and $q_{\tau}$ have the same strategy and
perform updates based on the same loss function,
$p_{\tau+1}=q_{\tau+1}$.555This is trivially true if $\mathcal{O}$ is
deterministic. If $\mathcal{O}$ is a randomized no-regret algorithm like
Follow the Perturbed Leader (Kalai & Vempala, 2005), we can instead simply
share the randomness between the two players. Then, by the anti-symmetry of
$\mathcal{P}$, we have that $\ell_{\tau+1}^{1}=\ell_{\tau+1}^{2}$. Therefore,
by induction, we have that $p_{t}=q_{t}$, $\forall t\in[T]$.

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

$\displaystyle\frac{\mathsf{Reg}_{p}(T)+\mathsf{Reg}_{q}(T)}{T}$
$\displaystyle=\frac{1}{T}\left(\sum_{t}^{T}\ell_{t}^{1}(p_{t})-\min_{p^{\star}\in\Delta(\Pi)}\sum_{t}^{T}\ell_{t}^{1}(p^{\star})+\sum_{t}^{T}\ell_{t}^{2}(q_{t})-\min_{q^{\star}\in\Delta(\Pi)}\sum_{t}^{T}\ell_{t}^{2}(q^{\star})\right)$
(14)
$\displaystyle=\frac{1}{T}\left(-\min_{p^{\star}\in\Delta(\Pi)}\sum_{t}^{T}\ell_{t}^{1}(p^{\star})-\min_{q^{\star}\in\Delta(\Pi)}\sum_{t}^{T}\ell_{t}^{2}(q^{\star})\right)$
($\ell_{t}^{1}(p_{t})+\ell_{t}^{2}(q_{t})=0$)
$\displaystyle=\frac{1}{T}\left(-\min_{p^{\star}\in\Delta(\Pi)}\sum_{t}^{T}\mathbb{E}_{\pi\sim
p^{\star},\pi^{\prime}\sim
q_{t}}[-\mathcal{P}(\pi,\pi^{\prime}))]-\min_{q^{\star}\in\Delta(\Pi)}\sum_{t}^{T}\mathbb{E}_{\pi\sim
p_{t},\pi^{\prime}\sim q^{\star}}[\mathcal{P}(\pi,\pi^{\prime}))]\right)$ (15)
$\displaystyle=\left(\max_{p^{\star}\in\Delta(\Pi)}\mathbb{E}_{\pi\sim
p^{\star},\pi^{\prime}\sim\overline{q}}[\mathcal{P}(\pi,\pi^{\prime}))]-\min_{q^{\star}\in\Delta(\Pi)}\mathbb{E}_{\pi\sim\overline{p},\pi^{\prime}\sim
q^{\star}}[\mathcal{P}(\pi,\pi^{\prime}))]\right).$ (16)

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

######  Proof.

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:

${a}$${b}$${c}$${a}$${0}$${{\color[rgb]{0,0.5,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.5,0}\frac{2}{5}}}$${{\color[rgb]{0.9765625,0.39453125,0.39453125}\definecolor[named]{pgfstrokecolor}{rgb}{0.9765625,0.39453125,0.39453125}-1}}$${b}$${{\color[rgb]{0.9765625,0.39453125,0.39453125}\definecolor[named]{pgfstrokecolor}{rgb}{0.9765625,0.39453125,0.39453125}-\frac{2}{5}}}$${0}$${{\color[rgb]{0,0.5,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.5,0}+1}}$${c}$${{\color[rgb]{0,0.5,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.5,0}+1}}$${{\color[rgb]{0.9765625,0.39453125,0.39453125}\definecolor[named]{pgfstrokecolor}{rgb}{0.9765625,0.39453125,0.39453125}-1}}$${0}$
Figure 9: A preference function over $\mathcal{Y}=(a,b,c)$ with unique Minimax
Winner $(\frac{5}{12},\frac{5}{12},\frac{1}{6})$ and unique Copeland winner
$b$.

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 $[0,1]$. Thus,

$r^{\star}=[0,1,0].$ (17)

From Ziebart (2010), we have that

$\pi^{\star}(y)\propto\pi_{\text{ref}}(y)\exp\left(\frac{1}{\beta}r^{\star}(y)\right)=\left[\frac{1}{3},\frac{1}{3},\frac{1}{3}\right]\odot\left[1,\exp(\frac{1}{\beta}),1\right]\propto\left[1,\exp(\frac{1}{\beta}),1\right].$
(18)

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

$p^{\star}(y_{1}\succ
y_{2})=\frac{1}{1+\exp{\left(\beta\log\frac{\pi^{\star}(y_{2})}{\pi_{\text{ref}}(y_{2})}-\beta\log\frac{\pi^{\star}(y_{1})}{\pi_{\text{ref}}(y_{1})}\right)}}.$
(19)

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

$\displaystyle p^{\star}(y_{1}\succ y_{2})$
$\displaystyle=\frac{1}{1+\exp{\left(\beta\log\pi^{\star}(y_{2})-\beta\log\pi^{\star}(y_{1})\right)}}$
(20)
$\displaystyle=\frac{1}{1+\left(\frac{\pi^{\star}(y_{2})}{\pi^{\star}(y_{1})}\right)^{\beta}}$
(21)
$\displaystyle=\frac{\pi^{\star}(y_{1})^{\beta}}{\pi^{\star}(y_{1})^{\beta}+\pi^{\star}(y_{2})^{\beta}}.$
(22)

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:

$\displaystyle\ell_{\text{DPO}}(\pi)$
$\displaystyle=-\sum_{y_{1},y_{2}\in\mathcal{Y}\times\mathcal{Y}}\left[\mathcal{P}(y_{1}\succ
y_{2})\log\left(p^{\star}(y_{1}\succ y_{2})\right)\right]$ (23)
$\displaystyle=-\sum_{y_{1},y_{2}\in\mathcal{Y}\times\mathcal{Y}}\left[\frac{\mathcal{P}(y_{1},y_{2})+1}{2}\log\left(\frac{\pi(y_{1})^{\beta}}{\pi(y_{1})^{\beta}+\pi(y_{2})^{\beta}}\right)\right]$
(24)

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:

$\frac{7}{10}=\frac{\pi^{\star}(a)^{\beta}}{\pi^{\star}(a)^{\beta}+\pi^{\star}(b)^{\beta}},\quad
1=\frac{\pi^{\star}(b)^{\beta}}{\pi^{\star}(b)^{\beta}+\pi^{\star}(c)^{\beta}},\quad
1=\frac{\pi^{\star}(c)^{\beta}}{\pi^{\star}(a)^{\beta}+\pi^{\star}(c)^{\beta}}.$
(26)

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

$\displaystyle\ell_{\text{DPO}}(\pi)$
$\displaystyle=-\left(\frac{7}{10}\log\left(\frac{\pi(a)^{\beta}}{\pi(a)^{\beta}+\pi(b)^{\beta}}\right)+\frac{3}{10}\log\left(\frac{\pi(b)^{\beta}}{\pi(a)^{\beta}+\pi(b)^{\beta}}\right)+\log\left(\frac{\pi(b)^{\beta}}{\pi(b)^{\beta}+\pi(c)^{\beta}}\right)+\log\left(\frac{\pi(c)^{\beta}}{\pi(a)^{\beta}+\pi(c)^{\beta}}\right)\right)$

First, observe that plugging in $\pi_{\text{ref}}$ gives us a loss value
$\log(2)$ for any value of $\beta$. Also, observe that $\lim_{\beta\to
0}\ell_{\text{DPO}}(\pi_{\text{MW}})=\log(2)$. Taking the derivative with
respect to $\beta$, we get

$\displaystyle\nabla_{\beta}\ell_{\text{DPO}}(\pi)$
$\displaystyle=\frac{-7}{10}\log\left(\frac{\pi(a)}{\pi(b)}\right)\frac{\pi(b)^{\beta}}{\pi(a)^{\beta}+\pi(b)^{\beta}}$
(27)
$\displaystyle+\frac{-3}{10}\log\left(\frac{\pi(b)}{\pi(a)}\right)\frac{\pi(a)^{\beta}}{\pi(b)^{\beta}+\pi(a)^{\beta}}$
(28)
$\displaystyle+-1\log\left(\frac{\pi(b)}{\pi(c)}\right)\frac{\pi(c)^{\beta}}{\pi(c)^{\beta}+\pi(b)^{\beta}}$
(29)
$\displaystyle+-1\log\left(\frac{\pi(c)}{\pi(a)}\right)\frac{\pi(a)^{\beta}}{\pi(a)^{\beta}+\pi(c)^{\beta}}.$

Now, plugging in the Minimax Winner, we get that

$\displaystyle\nabla_{\beta}\ell_{\text{DPO}}(\pi_{\text{MW}})$
$\displaystyle=-\log\left(\frac{5}{2}\right)\frac{\pi_{\text{MW}}(c)^{\beta}}{\pi_{\text{MW}}(c)^{\beta}+\pi_{\text{MW}}(b)^{\beta}}-\log\left(\frac{2}{5}\right)\frac{\pi_{\text{MW}}(a)^{\beta}}{\pi_{\text{MW}}(a)^{\beta}+\pi_{\text{MW}}(c)^{\beta}}>0.$

Thus, $\forall\beta\in(0,\infty)$,
$\ell_{\text{DPO}}(\pi_{\text{MW}})>\ell_{\text{DPO}}(\pi_{\text{ref}})$.
Thus, DPO will never pick the Minimax Winner.

###  A.4 Proof of Lemma 3.7

######  Proof.

Observe that for any $\xi\in(\mathcal{S}\times\mathcal{A})^{H}$,
$r(\xi)=\sum_{h=1}^{H}\tilde{r}(s_{t},a_{t})$. Thus, $\forall\pi\in\Pi$,

$\displaystyle\mathbb{E}_{\xi\sim\pi}\left[r(\xi)\right]=\mathbb{E}_{\xi\sim\pi}\left[\sum_{h=1}^{H}\tilde{r}(s_{t},a_{t})\right]\Rightarrow\operatorname*{\arg\\!\max}_{\pi\in\Pi}\mathbb{E}_{\xi\sim\pi}\left[r(\xi)\right]=\operatorname*{\arg\\!\max}_{\pi\in\Pi}\mathbb{E}_{\xi\sim\pi}\left[\sum_{h=1}^{H}\tilde{r}(s_{t},a_{t})\right].$
(30)

###  A.5 Proof of Corollary A.2

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

######  Assumption A.1 (Gap Condition).

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

  1. 1.

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

  2. 2.

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

  3. 3.

$\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.

######  Corollary A.2.

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

######  Proof.

We start by observing that under Assumption A.1, the loss function
$\ell_{t}^{1}(p)=\mathbb{E}_{\pi\sim p,\pi^{\prime}\sim
q_{t}}[-\mathcal{P}(\pi,\pi^{\prime}))]$ observed by the minimizing player
satisfies the following two properties:

  1. 1.

For an policy $\pi\in\Pi^{\star}$, we have $\ell_{t}(\pi)\leq\Delta$.

  2. 2.

For any policy $\pi\in\Pi^{\star}$ and $\pi^{\prime}\notin\Pi^{\star}$,
$\ell_{t}(\pi^{\prime})\geq\ell_{t}(\pi)+q_{t}(\Pi^{\star})\Delta/2$, where
$q_{t}(\Pi^{\star})$ is the probability of the max player choosing policies
from the set $\Pi^{\star}$.

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:

$\displaystyle\ell_{t}(\pi^{\prime})$
$\displaystyle=\sum_{\pi^{\prime\prime}\in\Pi}q_{t}(\pi^{\prime\prime})\left[-\mathcal{P}(\pi^{\prime},\pi^{\prime\prime})\right]=\sum_{\pi^{\prime\prime}\in\Pi^{\star}}q_{t}(\pi^{\prime\prime})\left[-\mathcal{P}(\pi^{\prime},\pi^{\prime\prime})\right]+\sum_{\pi^{\prime\prime}\in\Pi/\Pi^{\star}}q_{t}(\pi^{\prime\prime})\left[-\mathcal{P}(\pi^{\prime},\pi^{\prime\prime})\right]$
$\displaystyle\geq\sum_{\pi^{\prime\prime}\in\Pi^{\star}}q_{t}(\pi^{\prime\prime})\Delta+\sum_{\pi^{\prime\prime}\in\Pi/\Pi^{\star}}q_{t}(\pi^{\prime\prime})(-\Delta)$
(A.1, (1) and A.1, (3), resp.)
$\displaystyle\geq\sum_{\pi^{\prime\prime}\in\Pi^{\star}}q_{t}(\pi^{\prime\prime})\left[\frac{\Delta}{2}-\mathcal{P}(\pi^{\star},\pi^{\prime\prime})\right]+\sum_{\pi^{\prime\prime}\in\Pi/\Pi^{\star}}q_{t}(\pi^{\prime\prime})\left[-\mathcal{P}(\pi^{\star},\pi^{\prime\prime})\right]$
(A.1, (2) and A.1, (1), resp.)
$\displaystyle=\ell_{t}(\pi^{\star})+q_{t}(\Pi^{\star})\Delta/2.$

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

$p_{t}=\operatorname*{\arg\\!\min}_{p\in\Delta(\Pi)}\eta L_{t-1}^{T}p+R(p),$
(31)

for some convex regularizer $R$, and where we define
$L_{t}=\sum_{s=1}^{t}\ell_{s}$. As $p_{t}$ minimizes the above expression, we
know it satisfies the first-order optimality conditions, which imply that for
any other distribution $p\in\Delta(\Pi)$,

$\langle\nabla R(p_{t})+\eta L_{t-1},p-p_{t}\rangle\geq 0.$ (32)

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

$\displaystyle\nabla R_{i}(p_{t}(\pi_{a}))+\eta L_{t}(\pi_{a})-\nabla
R_{i}(p_{t}(\pi_{b}))-\eta L_{t}(\pi_{b})\geq 0.$

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

$\displaystyle\nabla R_{i}(p_{t}(\pi_{b}))-\nabla
R_{i}(p_{t}(\pi_{a}))\leq\eta(L_{t}(\pi_{a})-L_{t}(\pi_{b}))\leq-\eta\sum_{s=1}^{t-1}q_{s}(\Pi^{\star})\Delta/2.$
(33)

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

$\displaystyle p_{t}(\pi_{b})\leq
p_{t}(\pi_{a})\exp\left(\frac{-\eta\Delta}{2}\sum_{s=1}^{t-1}q_{s}(\Pi^{\star})\right).$

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

$\displaystyle p_{t}(\pi_{b})\leq p_{t}(\pi_{a})\exp\left(\frac{-\eta
t\Delta}{2|\Pi|}\right).$

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,

$\displaystyle\mathsf{Reg}(T)\leq\epsilon
T+\frac{2|\Pi|}{\eta\Delta}\ln\frac{1}{\epsilon}.$

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.

######  Theorem A.3.

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

$\hat{\ell}_{t}^{\texttt{SPO}}(\pi)=-\alpha\frac{\mathbbm{1}[\pi=\pi_{t}]}{p_{t}(\pi_{t})}\mathcal{P}(\pi_{t},\pi_{t}^{\prime})+(1-\alpha)\frac{\mathbbm{1}[\pi=\pi_{t}^{\prime}]}{p_{t}(\pi_{t}^{\prime})}\mathcal{P}(\pi_{t},\pi_{t}^{\prime}),$

and follow strategy $(1-\gamma)p_{t}+\frac{\gamma}{|\Pi|}$, $\bar{p}$ is an
$\widetilde{O}(\frac{1}{\sqrt{T}})$-approximate Minimax Winner. 666For last
iterate convergence, one can instead run the no-regret bandit feedback
algorithm of Cai et al. (2023) on $\hat{\ell}_{t}^{\texttt{SPO}}$, albeit at
the cost of a slower rate.

######  Proof.

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.

Define

$\hat{\ell}_{t}^{1}(\pi)=-\frac{\mathbbm{1}[\pi=\pi_{t}]}{p_{t}(\pi_{t})}\mathcal{P}(\pi_{t},\pi_{t}^{\prime}),\quad\hat{\ell}_{t}^{2}(\pi)=\frac{\mathbbm{1}[\pi=\pi_{t}^{\prime}]}{q_{t}(\pi_{t}^{\prime})}\mathcal{P}(\pi_{t},\pi_{t}^{\prime})$
(34)

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

$\mathbb{E}_{p_{t}}[\hat{\ell}_{t}^{1}]=\ell_{t}^{1},\mathbb{E}_{q_{t}}[\hat{\ell}_{t}^{2}]=\ell_{t}^{2},$
(35)

i.e. that they are unbiased estimates of the full-feedback losses. We now
proceed similarly to our proof for the full feedback case. If we set
$p_{0}=q_{0}$, we have that $\ell_{0}^{1}=\ell_{0}^{2}$ by the anti-symmetry
of $\mathcal{P}$. We also have that

$\mathbb{E}_{p_{0}}[\hat{\ell}_{0}^{\texttt{SPO}}]=\mathbb{E}_{p_{0}}[\alpha\hat{\ell}_{0}^{1}+(1-\alpha)\hat{\ell}_{0}^{2}]=\ell_{0}^{1}=\ell_{0}^{2}.$
(36)

We now proceed by induction. If $p_{\tau}=q_{\tau}$ at some time $\tau$ and we
feed both players the same loss $\hat{\ell}_{\tau}^{\texttt{SPO}}$, by the
determinism of Hedge, we have that $p_{\tau+1}=q_{\tau+1}$. This implies
$\ell_{\tau+1}^{1}=\ell_{\tau+1}^{2}$, which in turn implies
$\hat{\ell}_{\tau+1}^{\texttt{SPO}}$ is an unbiased estimate of both
$\ell_{\tau+1}^{1}$ and $\ell_{\tau+1}^{2}$. Thus, by induction, we have that
both players will have the same iterates and $\hat{\ell}_{t}^{\texttt{SPO}}$
is an unbiased estimate of both losses $\forall t\in[T]$, which means we can
simulate game-solving with a single player.

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

$\mathcal{P}:\mathcal{X}\times\Xi\times\Xi\rightarrow[-1,1]$ (37)

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

$\mathcal{P}(\pi_{1},\pi_{2})\triangleq\mathbb{E}_{x\sim\rho,\xi_{1}\sim(\pi_{1},x),\xi_{2}\sim(\pi_{2},x)}[\mathcal{P}(x,\xi_{1},\xi_{2})].$

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.

Input: Learning rate $\eta$, Iterations $T$, Preference fn. $\mathcal{P}$.

Output: Trained policy $\pi$.

Initialize $\pi_{h}(\cdot|\phi)=\mathsf{Unif}(\mathcal{A})$,
$\forall\phi\in\Phi_{h},h\in[H]$.

for $t$ in $1\dots T$ do

Observe context $x_{t}\sim\rho$.

Compute
$r_{t}(\xi)=\mathbb{E}_{\xi^{\prime}\sim\pi_{t}}\mathcal{P}(x_{t},\xi,\xi^{\prime})$.

Define
$Q_{t}^{h}(\phi,a)=\mathbb{E}_{\xi\sim\pi_{t}}[r_{t}(\xi)|\phi_{h}=\phi,a_{h}=a]$.

Define
$A_{t}^{h}(\phi,a)=Q_{t}^{h}(\phi,a)-\mathbb{E}_{a^{\prime}\sim\pi_{t}^{h}(\phi)}[Q_{t}^{h}(\phi,a^{\prime})]$.

for $\phi,a,h\in\Phi_{h}\times\mathcal{A}\times[H]$ do

// use no-regret algo for update

$\pi_{t+1}^{h}(a|\phi)\propto\pi_{t}^{h}(a|\phi)\exp{(\eta
A_{t}^{h}(\phi,a))}$.

end for

end for

Return  $\bar{\pi}$, uniform mixture of $\pi_{1:T}$.

Algorithm 3 SPO (Theoretical Version with Contexts)

Input: Iterations $T$, Preference fn. $\mathcal{P}$, Num. samples $k\geq 2$,
Reinforcement learning algo. $\mathsf{RL}:\Pi\times\mathcal{D}\to\Pi$.

Output: Trained policy $\pi$.

Initialize $\pi_{1}\in\Pi$.

for $t$ in $1\dots T$ do

Observe context $x_{t}\sim\rho$ and sample $\xi_{1:k}\sim\pi_{t}(x_{t})$.

Compute $r_{t}(\xi_{i})=\frac{1}{k-1}\sum_{j\neq
i}^{k}\mathcal{P}(x_{t},\xi_{i},\xi_{j})$.

Set $r_{i}^{h}=r_{t}(\xi_{i})/H$, $\forall i,h\in[k]\times[H]$.

// use PPO, TRPO, SAC ...

$\pi_{t+1}\leftarrow\mathsf{RL}(\pi_{t},\mathcal{D}=\\{(s^{h}_{i},a^{h}_{i},r_{i}^{h})\\}_{i\in[k]}^{h\in[H]})$.

end for

Return  best of $\pi_{1:T}$ on validation data.

Algorithm 4 SPO (Practical Version with Contexts)

##  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.

######  Example B.1.

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. 777An
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.

Figure 10: Additional results for maximum reward preference experiments.

Figure 11: Additional results for noisy preference experiments.

Figure 12: Additional results for intransitive preference experiments with Gym
Ant-v3 environment.

##  Appendix D Experimental Details

###  D.1 Discrete action experiment in Figure 4

#### Problem Setup.

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

$\displaystyle\mathcal{P}=\begin{bmatrix}0&c&-b\\\ -c&0&a\\\
b&-a&0\end{bmatrix}$

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 $0$. 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}$

$\displaystyle a\times\begin{bmatrix}0&0&0\\\ 0&0&1\\\
0&-1&0\end{bmatrix}+b\times\begin{bmatrix}0&0&-1\\\ 0&0&0\\\
1&0&0\end{bmatrix}+c\times\begin{bmatrix}0&1&0\\\ -1&0&0\\\
0&0&0\end{bmatrix}=\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.

Parameter | Value
---|---
max replay size | 1000000
min replay size | 10000
batch size | 256
$\gamma$ | 0.99
$\tau$ | 0.005
n step | 1
learning rate | 3e-5
batch size | 256
samples per insert | 256
samples per insert tolerance ratio | 0.1
num SGD steps per step | 1
Table 2:  Hyperparameters for SAC.

###  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. 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)