Nash Learning from Human Feedback

Introduction

Large language models (LLMs) (Glaese et al., 2022; Anil et al., 2023; OpenAI, 2023; Ouyang et al., 2022) have made remarkable strides in enhancing natural language understanding and generation. Their success in conversational applications often relies on aligning these models with human preferences, a process primarily guided by the paradigm of reinforcement learning from human feedback (RLHF). A prevailing approach within RLHF involves the initial step of constructing a reward model based on pairwise human preferences, frequently employing the Bradley-Terry model (BT; Bradley and Terry, 1952). This reward model assigns an individual score to each generation of the language model conditioned on a given prompt, akin to how the Elo (1978) ranking system assigns scores to chess players to estimate their relative strengths. Subsequently, model refinement takes place by optimizing the LLM’s performance with respect to this reward model through reinforcement learning (RL) over sampled text generations.

However, the Elo model has its limitations, primarily coming from its inability to accommodate the full spectrum of possible preferences. For example, Bertrand et al. (2023) show the limitations of the Elo model by illustrating where Elo score alone cannot predict the right preferences, even in transitive situations. There are also situations where maximizing the Elo score is not aligned with maximizing the probability of winning against the relevant population of players, even when the preference model can be perfectly expressed using a BT model (see Appendix A for an example). These observations highlight the necessity for a more profound understanding of the implications of Elo-based reward maximization in RLHF for achieving genuine alignment with human preferences.

In this paper, we introduce an alternative pipeline for fine-tuning LLMs from human preference data, which we term Nash learning from human feedback (NLHF). In this framework, we depart from the conventional approach of learning a reward model and instead focus on learning a preference model and define our objective to compute the Nash equilibrium of this preference model.

The preference model takes two responses, denoted as $y$ and $y^{\prime}$ (possibly conditioned on a prompt $x$), as input and produces a preference score ${\cal{P}}(y\succ y^{\prime}|x)$, indicating the preference of response $y$ over response $y^{\prime}$ given the context $x$. To initialize this preference model, we may leverage an LLM prompted in a manner akin to how humans have been asked for their preference, such as by instructing the LLM to generate a 1-vs-2 comparison in response to a prompt like: “Given $x$, which answer do you prefer, answer 1: $y$ or answer 2: $y^{\prime}$?”. This initial preference model can be further refined through supervised learning to align it with human preference data. Notably, a preference model does not require the assumption of the Bradley-Terry model, and thus has the potential to capture a more diverse range of human preferences. Moreover, in contrast to the traditional RLHF setting where the reward model depends on the distribution (and thus the policy) of responses used to collect human data, a preference model (having as input the two responses to be compared) remains essentially invariant to the specific policy employed to generate these responses. Finally, we argue (below) that the Nash equilibrium of the preference model is a solution that better aligns with the diversity of human preferences than the maximum of the expected reward model.

Once the preference model is established, our primary objective is to calculate the corresponding Nash equilibrium. This equilibrium represents a policy that consistently produces responses preferred, as determined by the preference model, over responses generated by any alternative policy. The beauty of this solution concept lies in its innate alignment with the human preference data that served as the foundation for training the preference model. These three key properties of our approach, namely, the ability of the preference model to encompass a wider spectrum of human preferences, its policy-independence, and the potential for the Nash equilibrium to provide a better alignment with the diversity of human preferences, mark a substantial departure from the conventional RLHF framework. We discuss these properties in greater detail in Section 3.

To approximate the Nash equilibrium of the two-player game in which actions are responses, and payoffs are specified by the preference model, we employ a deep reinforcement learning algorithm. Given a prompt $x$, we generate two responses, denoted as $y$ and $y^{\prime}$. The first response, $y$, is generated under the current policy $\pi_{\theta}$ that we are in the process of optimizing. In contrast, the second response, $y^{\prime}$, is produced by an alternative policy $\pi^{\prime}$, which we implement in two different versions: Nash-MD and Nash-EMA (further elaboration on these versions will be provided below). Nash-MD defines the alternative policy $\pi^{\prime}$ as a geometric mixture between the initial and the current policies (motivated by mirror descent), whereas Nash-EMA implements a first-order approximation of an exponential moving average (EMA) mixture of past policies. Then, the preference model computes ${\cal{P}}(y\succ y^{\prime}|x)$, and this preference signal serves as a reward for optimizing our policy $\pi_{\theta}$ using a (regularized) policy gradient algorithm, as outlined by Geist et al. (2019).

Our contributions in this work can be summarized as follows. First, we introduce the concept of Nash learning from human feedback (NLHF), framing it as the task of computing the Nash equilibrium for a general preference model. We proceed by introducing and defining a regularized variant of the preference model. We also establish the existence and uniqueness of the corresponding Nash equilibrium in this context. Then, we consider the case of tabular policy representations and introduce a novel algorithm named Nash-MD. This algorithm, founded on the principles of mirror descent (MD) possesses two important properties. First, it converges to the Nash equilibrium, with the final iteration reaching this equilibrium. This differs from conventional regret-minimization-based algorithms, where it is typically the mixture of past policies that converges, necessitating the storage of past policies. Secondly, Nash-MD learns by competing against alternative policies $\pi^{\prime}$ that represent a (geometric) mixture between the current policy $\pi_{\theta}$ and the initial policy. Importantly, this can be accomplished without the need to retain intermediate policies, a feature of particular significance in the context of LLMs with their substantial memory requirements. Additionally, we introduce Nash-EMA, a variation inspired by fictitious play, which uses an exponential moving average of past policy parameters. We introduce policy-gradient algorithms for deep learning architectures, Nash-MD-PG and Nash-EMA-PG, inspired by the tabular algorithms Nash-MD and Nash-EMA. We present the results of extensive numerical experiments conducted on a text summarizing task utilizing the TL;DR dataset (Völske et al., 2017). In these experiments, we employ the NLHF approach to train several models. To assess their performance, we conduct a pairwise evaluation (using the PaLM 2 Large LLM) of the performance of the models and include a comparison to an RLHF baseline. We conclude that NLHF opens up new promising directions for aligning LLMs with human preferences.

Prior work

Our contribution falls into a broader area of preference-based RL, where we directly learn from pairwise human preferences instead of a hand-designed or learned scalar reward (see, e.g., the survey by Wirth et al., 2017). The canonical form of RLHF was proposed in Christiano et al. (2017) and popularized by OpenAI (2022), in which one learns a scalar reward model from the preference feedback, followed by policy optimization against the reward model. However, an advantage of directly optimizing for preferences rather than a learnt scalar reward function is the potential to avoid reward hacking (Amodei et al., 2016), when agents find a way to maximize a reward without performing what was intended. Furthermore, in domains such as medical applications, it may not only be challenging but also undesirable to provide a single scalar reward.

In general, the preference feedback can be provided in different ways, e.g., on the level of states, actions, or a full trajectory. In this work, we focus on the trajectory feedback where the experts provide feedback by selecting the preferred one of the two proposed trajectories. Such a simple form of pairwise feedback is the easiest to implement, and has seen applications in summarization (Stiennon et al., 2020), question-answering (Nakano et al., 2021; Menick et al., 2022) and general language-based assistants (Ouyang et al., 2022; Glaese et al., 2022; Bai et al., 2022). More complicated forms of feedback has been studied in theoretical literature such as Efroni et al. (2021).

Theoretical guarantees for learning from preferences.

Learning policies from preference feedback of histories was studied by Akrour et al. (2011) who learned the preference model for histories and by Cheng et al. (2011) who trained a model ranking actions for a state. Busa-Fekete et al. (2014, 2013) approached this setting by comparing and ranking policies and Wilson et al. (2012) by learning a distribution over policy space. Preference-based RL is also explored in dueling RL (Novoseller et al., 2020; Pacchiano et al., 2023), which generalizes the well-studied dueling bandits problem. In particular, Pacchiano et al. (2023) assumes a Bradley-Terry model, which they estimate using maximum likelihood in the tabular setting.

Our work is also related to results of Wang et al. (2023) who consider learning Nash equilibria of the human preference model, and reduce the problem to finding Nash equilibria for a special class of factored two-player Markov games under a restricted set of policies. Moreover, Chen et al. (2022) gave first results for function approximation in preference-based RL, however with a computationally inefficient algorithm.

Optimization without reward function.

A number of recent works has attempted to optimize for preference feedback without learning a reward function. For example, Direct Preference Optimization (DPO; Rafailov et al., 2023) optimizes the policy through a loss function defined via the Bradley-Terry reward model. SLiC-HF (Zhao et al., 2023) modifies the classical RLHF training loss by calibrating a ranking loss which contrasts a positive and a negative sequence. This resembles directly optimizing for the pairwise preference, albeit without convergence guarantees. Identity Policy Optimization (IPO; Azar et al., 2023) proposed to directly optimize the pairwise human preference with offline preference data. Unlike DPO, IPO does not make the assumption on reward model, though they both optimize against a fixed opponent rather than searching for Nash equilibria.

The preference model and its Nash equilibrium

We now introduce the core conceptual ideas behind our approach to learning from preference feedback. We consider a preference model in a contextual bandit setting. Given a context (or prompt) $x$ in the context space $\mathcal{X}$ and two actions (or responses/choices) $y$ and $y^{\prime}$ in the action space $\mathcal{Y}$, the preference of $y$ over $y^{\prime}$ is a number between and $1$ which is written ${\cal P}(y\succ y^{\prime}|x)$. We will assume that the preference model is symmetric: ${\cal{P}}(y\succ y^{\prime}|x)=1-{\cal{P}}(y^{\prime}\succ y|x)$.

An example of such a preference model is the probability (under some random outcome $Z$) that $f(x,y,Z)\geq f(x,y^{\prime},Z)$, where $f$ is a (deterministic) absolute scoring function:

We define the preference between two distributions conditioned on a state $x$:

We say that a policy $\pi$ is preferred over (or simply wins against) another policy $\pi^{\prime}$ if ${\cal P}(\pi\succ\pi^{\prime})\geq 1/2$. In the remainder of the paper, we assume without loss of generality that $\rho$ assigns every context positive probability.

In this paper we will consider the objective of finding a policy $\pi^{*}$ which is preferred over any other alternative policy:

This objective implicitly defines a two-player game, in which the players select policies $\pi$ and $\pi^{\prime}$, the first player receiving a payoff of ${\cal P}(\pi\succ\pi^{\prime})$, and the second player receiving ${\cal P}(\pi^{\prime}\succ\pi)=1-{\cal P}(\pi\succ\pi^{\prime})$. This is therefore a two-player, symmetric, constant-sum game, and it follows that when both players use a policy $\pi^{*}$ solving Equation (1), this is a Nash equilibrium for this game, by the minimax theorem (von Neumann, 1928). This is the fundamental solution concept we study in this paper.

The objective introduced in Equation (1) has two central differences relative to the majority of existing work on RLHF. First, the objective is expressed directly in terms of preferences themselves, not in terms of a reward function learnt from preferences, and also not in terms of a non-linear transformation of the preferences. Second, our solution concept relies on the notion of Nash equilibrium, rather than on optimization against a fixed behavior. We discuss the impact of both of these choices through several examples below.

Preference models, as demonstrated, possess the capacity to encompass non-transitive preferences, a characteristic not attainable by reward models, which inherently assign a single score to each policy. Whether humans exhibit non-transitive preferences or not has been a subject of longstanding research (see, for instance, Tversky 1969; Klimenko 2015). Additionally, non-transitivity is not the only limitation of Bradley-Terry-based reward models; see, e.g., Example 3 in Bertrand et al. (2023) where Elo score fails to capture the correct preference ordering between policies, even in transitive situations. In fact, we show in Appendix A that even when the preference model is perfectly captured by the Bradley-Terry model, optimization of the reward/Elo score may still disagree with any reasonable notion of preference optimization. Therefore, we can safely argue that preference models offer a more flexible and nuanced framework for modeling human preferences than reward models.

2 Alignment with diversity of human preferences

Here, we illustrate that in some situations, the solution offered by the Nash equilibrium of the preference model (which we refer to as the NLHF solution) is more aligned with the diversity of human preferences than the optimum of the reward model (which we refer to as the RLHF solution).

Consider the following situation where there are 3 different actions ($y_{1}$, $y_{2}$, $y_{3}$) and we have a population composed of 3 types of humans with respective preferences ${\cal{P}}_{1},{\cal{P}}_{2},{\cal{P}}_{3}$, defined in the following way: ${\cal{P}}_{i}(y_{1}\succ y_{2})={\cal{P}}_{i}(y_{1}\succ y_{3})={\cal{P}}_{i}(y_{2}\succ y_{3})=1/2$, for $1\leq i\leq 3$, except for the following cases: ${\cal{P}}_{1}(y_{2}\succ y_{1})=1$ (thus ${\cal{P}}_{1}(y_{1}\succ y_{2})=0$), ${\cal{P}}_{2}(y_{1}\succ y_{3})=1$ (thus ${\cal{P}}_{2}(y_{3}\succ y_{1})=0$), and ${\cal{P}}_{3}(y_{3}\succ y_{2})=1$ (thus ${\cal{P}}_{3}(y_{2}\succ y_{3})=0$).

However, here we are in a situation where the preferences are not uniformly aligned across humans. In the case of uniform sampling of humans (i.e., $\epsilon=0$), the Nash equilibrium of ${\cal{P}}_{\epsilon=0}$ is a uniform mixture between the 3 policies. Actually, the preference model ${\cal{P}}_{\epsilon}$ corresponding to any $\epsilon$ is defined as: ${\cal{P}}_{\epsilon}(y_{2}\succ y_{1})=2/3-\epsilon/2$, ${\cal{P}}_{\epsilon}(y_{3}\succ y_{1})=1/3-\epsilon/4$, ${\cal{P}}_{\epsilon}(y_{3}\succ y_{2})=2/3+\epsilon/4$, ${\cal{P}}_{\epsilon}(y_{i}\succ y_{i})=1/2$, and ${\cal{P}}_{\epsilon}(y_{i}\succ y_{j})=1-{\cal{P}}_{\epsilon}(y_{j}\succ y_{i})$, for $1\leq i<j\leq 3$. By a simple calculation, we deduce that for any $|\epsilon|\leq 1/3$, the Nash equilibrium of this preference model consists in selecting $y_{1}$ and $y_{2}$ with probability $1/3+\epsilon/2$ each, and $y_{3}$ with probability $1/3-\epsilon$.

We believe that in this situation, the Nash solution of the preference model (i.e., the NLHF solution), assigning close to uniform probability to these 3 actions (one being preferred by each category of humans) is more aligned with the diversity of human preferences than the optimum of the reward model (i.e., the RLHF solution), which would deterministically select a single action. Also the Nash equilibrium is less sensitive to the preference distribution, since the corresponding equilibrium is smooth w.r.t. change in the distribution over types of humans (i.e., when $\epsilon$ varies near ), whereas the RLHF solution will switch from selecting exclusively $y_{1}$ when $\epsilon>0$ to selecting exclusively $y_{2}$ when $\epsilon<0$.

3 Sensitivity to the sampling distribution

Another difference between reward and preference models is that a reward model depends on the distribution over responses it has been trained on, whereas a preference model essentially does not. Indeed, when we learn a reward model we are solving the following optimization problem:

where $y_{w}^{h}$ and $y_{l}^{h}$ are respectively the preferred (and less preferred) response (among $y$ and $y^{\prime}$) according to a randomly sampled human $Z\sim\nu$, given $x$. The (optimal) solution to this problem $r^{\pi}$ depends on the policy $\pi$ that has generated the data. Indeed, as mentioned in the introduction (see Section 1), the reward model assigns an Elo score to each individual response, which is defined in terms of a comparison against other responses; thus, it depends on the overall distribution over responses it has been trained on.

Notice that the optimal solution to this optimization problem is, for every $x\in\mbox{supp}(\rho)$, $y\in\mbox{supp}(\pi(\cdot|x))$, $y^{\prime}\in\mbox{supp}(\pi^{\prime}(\cdot|x))$,

thus does not depend on $\rho$, $\pi$ or $\pi^{\prime}$. Now, of course, when using approximate models the learned preference model may still depend on the data distribution as the quality of the approximate model will depend on the local quantity of data collected.

Thus it is our general expectation that the preference model is significantly less reliant on the specific policy that generated the data when compared to the reward model.

This observation becomes even more important in scenarios where multiple iterations of RLHF/NLHF occur, comprising data collection, constructing a reward/preference model, policy optimization based on the model, and collecting new data following the updated policy.

In the case of RLHF, the reward model from a prior iteration diverges from the next iteration due to shifts in data generation, necessitating complete relearning. On the contrary, in the NLHF approach, the preference model can be preserved and further enriched through the introduction of novel data, thereby offering a more seamless and efficient adaptation process.

Regularized preference model

We now consider a regularized version of the preference model. This is motivated by situations where the preference model is more accurately estimated when following some given policy. This could include the policy responsible for generating the data used to train the preference model or situations where it is imperative to ensure that our solution remains close to a known safe policy. In such cases, we incorporate a penalty mechanism into our preference model, employing KL-regularization to quantify the divergence between the policy under consideration and a designated reference policy denoted as $\mu$; see Jaques et al. (2019); Stiennon et al. (2020); Ouyang et al. (2022) for further details on the role KL-regularization in RLHF.

The regularized preference between actions $y\sim\pi(\cdot|x),y^{\prime}\sim\pi^{\prime}(\cdot|x)$ is defined as

and we define accordingly the KL-regularized preference between policies:

There exists a unique Nash equilibrium of the regularized preference model ${\cal P}_{\tau}$.

The mappings $\pi\mapsto{\cal P}(\pi\succ\pi^{\prime})$ and $\pi^{\prime}\mapsto{\cal P}(\pi\succ\pi^{\prime})$ are linear in $\pi$ (respectively in $\pi^{\prime}$) thus $\pi\mapsto{\cal P}_{\tau}(\pi\succ\pi^{\prime})$ is concave and $\pi^{\prime}\mapsto{\cal P}_{\tau}(\pi\succ\pi^{\prime})$ is convex. Existence of a Nash equilibrium is derived from the minimax theorem for convex-concave functions (Sion, 1958) and its uniqueness comes from its strict convexity/concavity, see Appendix C for the proof of uniqueness using variational inequalities. ∎

Algorithms for approximating the Nash equilibrium

The regularized preference model ${\cal{P}}_{\tau}(\pi\succ\pi^{\prime})$ defines a constant-sum two-player game where Player 1 selects $\pi$ and Player 2 selects $\pi^{\prime}$. There are well-known techniques for approximating the Nash equilibrium. Some of them offer a convergence on average (in the sense that it is a mixture of the sequence of policies that converges to the Nash equilibrium), whereas other methods offer convergence of the last iterate.

Fictitious play (FP; Brown, 1951; Robinson, 1951; Heinrich et al., 2015; Fudenberg and Levine, 1998) consists in playing, at every iteration, each player’s best response against the uniform mixture of the opponent’s past strategies. Here we would define $\pi_{t+1}\stackrel{{\scriptstyle\rm def}}{{=}}\arg\max_{\pi}{\cal{P}}(\pi\succ\bar{\pi}_{t})$, where $\bar{\pi}_{t}$ is the mixture policy $\frac{1}{t}\sum_{s=1}^{t}\pi_{s}$. It is known that the mixture policy $\bar{\pi}_{t}$ converges to the Nash equilibrium in constant-sum games (see Hofbauer and Sorin (2006) for a reference in the general concave-convex case considered here). Also, FP has been considered with function approximation (Heinrich and Silver, 2016). Online convex optimization: In the context of solving convex-concave constant-sum games, we rely on online convex optimization where each player minimizes its own convex loss. See for example Cesa-Biachi and Lugosi (2006); Nesterov (2005); Hoda et al. (2010). Regret minimization has been extensively considered in games since the average strategy of self-playing no-regret algorithms converges to a Nash equilibrium (Rakhlin and Sridharan, 2013; Kangarshahi et al., 2018). Counterfactual regret minimization (CFR) has been considered in the setting of imperfect information games in (Zinkevich et al., 2007) showing a $O(1/\sqrt{t})$ convergence rate in terms of exploitability. Other techniques provide a faster rate of convergence $O(1/t)$ (Daskalakis et al., 2011; Syrgkanis et al., 2015; Abernethy et al., 2018; Farina et al., 2019). These techniques have been usually studied in the discrete time setting but has also been looked at in continuous time (Mertikopoulos et al., 2018).

Convergence of the last iterate.

Extragradient or optimistic mirror descent methods have been proven to converge to a Nash equilibrium (Korpelevich, 1976; Mertikopoulos et al., 2019) with possibly an exponential rate in unconstrained spaces (Mokhtari et al., 2020). The most closely related extragradient method in this domain is optimistic multiplicative-weights-update (OMWU; Daskalakis and Panageas, 2019) which provides convergence guarantees to the Nash equilibrium of the last iterate. Another approach uses the Frank-Wolfe method to compute Nash equilibria in normal-form games (Gidel et al., 2016), although convergence is attained at the same rate as for fictitious play. A related algorithm introduced by Munos et al. (2020) for imperfect information games consists in each player doing a step of mirror ascent against an improved opponent (MAIO) for which exponential convergence of the last-iterate was proven (with a instance-dependent exponent). Another approach (Perolat et al., 2021, 2022), called regularized Nash dynamics (R-NaD), introduced friction to the dynamics by considering a KL-regularized objective showed a last-iterate convergence in a continuous-time dynamics setting.

Analysis of a tabular algorithm: Nash-MD

For simplicity of notation we remove the dependence on the context $x$, thus policies $\pi\in\Delta(\mathcal{Y})$ are probability distributions over $\mathcal{Y}$. We now introduce an algorithm, called Nash-MD, which is a novel variant of mirror descent (Nemirovski and Yudin, 1983; Bubeck, 2015; Lattimore and Szepesvári, 2020) that makes use of a specific regularized policy $\pi_{t}^{\mu}$ which is a geometric mixture between the current policy $\pi_{t}$ and the reference policy $\mu$. We prove the convergence (in terms of KL distance) of the last iterate to the Nash equilibrium of ${\cal{P}}_{\tau}$.

Define the regularized policy $\pi_{t}^{\mu}$ as a geometric mixture between the current policy $\pi_{t}$ and the reference policy $\mu$:

where $\eta$ is a learning rate. We define the Nash-MD algorithm as a step of mirror descent relative to the regularized policy $\pi_{t}^{\mu}$:

The optimization above can also be made explicit in the following form:

where $c$ is a normalization constant which is independent of $y$.

The intuition for this algorithm is to improve the current policy $\pi_{t}$ in a direction that increases the preference $\pi\mapsto{\cal{P}}(\pi,\pi_{t}^{\mu})$ against the regularized policy $\pi_{t}^{\mu}$, while not deviating too much from it. We now state our main theoretical result; see Appendix B for the proof.

Let $\pi^{*}_{\tau}$ be the Nash equilibrium of the regularized preference model: ${\cal{P}}_{\tau}(\pi\succ\pi^{\prime})={\cal{P}}(\pi\succ\pi^{\prime})-\tau\mbox{KL}(\pi,\mu)+\tau\mbox{KL}(\pi^{\prime},\mu).$ At every iteration $t$ we have that

We deduce that for the choice $\eta=\log T/(\tau T)$ we have

Nash-MD has a last-iterate convergence property.

The second important property of Nash-MD is that we have convergence of the last-iterate (i.e., the current policy $\pi_{t}$ converges to $\pi_{\tau}^{*}$) and not only convergence on average (as is typically the case of fictitious play and usual regret minimization algorithms like CFR and OMD). This feature is particularly important in the context of LLMs as well due to the substantial memory resources that would be otherwise needed to store a mixture policy like $\bar{\pi}_{t}$.

Comparison with online mirror descent (OMD).

In general the analysis of constant-sum concave-convex games can be performed in the framework of online convex optimization where the goal is to find a sequence of solutions $\pi_{t}$ that minimizes the sum of a sequence of convex loss functions $\pi\mapsto l_{t}(\pi)$. The OMD algorithm (using the KL as Bregman divergence) defines the sequence:

for which it can be shown (see e.g., Cesa-Biachi and Lugosi, 2006) that the average cumulative regret, under optimal choice of learning rate, can be bounded as

This type of upper bound on the regret can be further used to deduce a convergence result in constant-sum games where each player would play an OMD strategy to minimize their own convex loss. In our context, we could apply this OMD strategy to minimize the regularized preference model ${\cal{P}}_{\tau}$, and since ${\cal{P}}_{\tau}$ is symmetric, we only need to consider the dynamics of a single player. So the loss function at time $t$ is the negative preference against the current policy of the opponent: $l_{t}(\pi)=-{\cal{P}}_{\tau}(\pi\succ\pi_{t})$. We deduce that $\nabla l_{t}(\pi_{t})=-\left[\partial_{\pi}{\cal{P}}_{\tau}(\pi\succ\pi_{t})\right]_{\pi=\pi_{t}}$, thus $\nabla l_{t}(\pi_{t})\cdot\pi=-\sum_{y}\pi(y)\left[{\cal{P}}(y\succ\pi_{t})-\tau\left(\log\frac{\pi_{t}(y)}{\mu(y)}+1\right)\right]$. Thus the OMD update rule in Equation (7) can be rewritten as

Now, using the regularized policy $\pi_{t}^{\mu}$ introduced in Equation (3), we can rewrite this update rule as

Comparing Equation (4) and Equation (8) we notice that both OMD and Nash-MD make use of the same KL penalty term $\mbox{KL}(\pi,\pi_{t}^{\mu})$. However they differ in the fact that OMD optimizes the preference $\pi\mapsto{\cal{P}}(\pi\succ\pi_{t})$ against the current policy $\pi_{t}$ whereas Nash-MD optimizes the preference $\pi\mapsto{\cal{P}}(\pi\succ\pi_{t}^{\mu})$ against the regularized policy $\pi_{t}^{\mu}$.

In the context of convex-concave games, the regret bound on the average cumulative regret translates into an upper bound on the exploitability of the game when players play their average policies, thus entailing their on-average convergence to the Nash equilibrium. However it is known that usual regret-minimization algorithms may not possess a last-iterate convergence property because the sequence of policies $\pi_{t}$ may oscillate around the Nash equilibrium (see, for example, Mertikopoulos et al., 2018). Nevertheless, last-iterate convergence have been obtained for variants of OMD, such as extra-gradient and optimistic versions, see e.g., Rakhlin and Sridharan (2013); Daskalakis and Panageas (2019); Mertikopoulos et al. (2019); Munos et al. (2020); Mokhtari et al. (2020).

The contextual bandit setting.

All the results mentioned in this section are for the state-independent case, where policies and preferences do not depend on the context $x$. In the case of LLMs the context is the prompt $x$, and responses $y$ and $y^{\prime}$ are generated conditioned on $x$. However the theoretical results do not change. Indeed, we would define the Nash-MD algorithm in the contextual bandit case as follows: for every $x\in{\tt supp}(\rho)$,

We prove the convergence of this algorithm, in exactly the same way as in Theorem 1, by showing that at every iteration $t$ we have

Implementation of NLHF

Now, building upon the insights from Nash-MD, we explore potential gradient-based algorithms for deep-learning architectures designed for the computation of the Nash equilibrium of a preference model, with a specific focus on their applicability in the context of LLMs.

In LLMs it is usually the case that tokens are generated one at a time in an autoregressive manner. Thus the response $y\sim\pi(\cdot|x)$ can be written as $y=y_{0:N}$ (where $y_{0:N}\stackrel{{\scriptstyle\rm def}}{{=}}(y_{0},\dots,y_{N})$), where each token $y_{n}$ is generated from a distribution $\pi(\cdot|x,y_{0:n-1})$ conditioned on previous tokens, such that $\pi(y_{0:N}|x)=\prod_{n=0}^{N}\pi(y_{n}|x,y_{0:n-1})$. In practice (see the experiments section for results on LLMs) we will implement this token-per-token autoregressive generation of responses $y\sim\pi(\cdot|x)$ using next token distributions (implemented as a softmax over logits).

where the normalization constant $C$ depends on $x,y_{0:n-1}$. In order to sample from this marginal geometric mixture over the $n$th token, we evaluate the corresponding logits of both the current policy $\pi_{\theta}$ and the reference policy $\mu$ (conditioned on $(x,y_{0:n-1})$), we compute their ($\tau$-arithmetic) mixture, and sample a next token $y_{n}$ from the corresponding softmax distribution. We call this corresponding product of marginal (geometric) mixtures over individual tokens the one-step-at-a-time regularized policy

2 Computing the Nash equilibrium using regularized policy gradient

Our general algorithm for computing the Nash equilibrium of the preference model consists in repeating these steps:

We generate two responses $y$ and $y^{\prime}$ (in an autoregressive fashion in the case of LLMs):

the first one $y\sim\pi_{\theta}(\cdot|x)$ by following the current policy $\pi_{\theta}$ that is being optimized;

the second one $y^{\prime}\sim\pi^{\prime}(\cdot|x)$ by following an alternative policy $\pi^{\prime}$.

The choice of the alternative policy $\pi^{\prime}$ that we use for the second generated sample $y^{\prime}$ depends on the specific algorithm we consider (the description of which is given in the next subsection).

We update the parameter $\theta$ of the policy $\pi_{\theta}$ in the direction of the gradient $\nabla_{\theta}{\cal{P}}_{\tau}(\pi_{\theta}\succ\pi^{\prime})$ of the regularized preference model ${\cal{P}}_{\tau}$.

We consider two cases, depending on whether a preference model is learnt or not.

If we have learnt a preference model ${\cal{P}}$ (see Section 8.1 for example for how one can learn a preference model) we query it to get the preference reward ${\cal{P}}(y\succ y^{\prime}|x)$ and update $\theta$ by moving it in the direction of the policy gradient estimate

Notice we have subtracted the baseline $1/2={\cal{P}}(y\succ y|x)$ from the preference ${\cal{P}}(y\succ y^{\prime}|x)$ (which does not change the expectation of the gradient) as a variance reduction technique that does not require learning a value function as baseline. In practice, when the response $y$ comprises a sequence of tokens $y_{0:N}$, a sample-based estimator to the KL based on the sample response $y$ can be used. Further, this can be decomposed into a sum across token indicies of per-token KL estimators, and the standard policy-gradient variance-reduction trick of only multiplying $\nabla_{\theta}\log\pi_{\theta}(y_{n}|x,y_{0:n-1})$ by KL estimator terms corresponding to indices at least as great as $n$ can be applied.

𝒫𝒫{\cal{P}}-model-free approach.

In both model-based and model-free approaches, we have that

(where $\underline{\pi^{\prime}}$ denotes a stop-gradient on $\pi^{\prime}$ in the case $\pi^{\prime}$ would depend on $\theta$).

Now, for the choice of alternative policies $\pi^{\prime}$ that are used to generate the second sample $y^{\prime}$, we will consider two different algorithms Nash-MD-PG and Nash-EMA-PG, that are inspired by, respectively, the mirror-ascent algorithm Nash-MD introduced in the previous section, and a generalization of fictitious play where we consider an exponential moving average.

We define the alternative policy $\pi^{\prime}=\pi_{\theta}^{\beta}$ as a geometric-mixture between $\pi_{\theta}$ and $\mu$ in a similar way as the regularized policy is defined in Equation (3):

In addition to using a parametric representation of policies instead of a tabular one, it differs from the fact that it is not directly implementing a mirror descent algorithm but a simple gradient descent on the regularized preference model. In a sense this algorithm is only making a gradient step for the inner optimization problem of Equation (4), whereas a more faithful variant of Nash-MD would use a two-time scale algorithm and perform several gradient steps (while keeping $\pi_{\theta}$ and $\pi_{\theta}^{\beta}$ fixed) until the inner loop has reached an optimum, before updating $\pi_{\theta}$ and $\pi_{\theta}^{\beta}$. Another apparent difference is that Nash-MD uses a KL-regularization w.r.t. the mixture policy $\pi_{\theta}^{\beta}$, whereas Nash-MD-PG uses a KL w.r.t. the reference policy $\mu$. However, we have that

where $c(x)$ is the normalizing constant in Equation (11). Thus, we have

and since we perform a single step of gradient descent before updating $\pi_{\theta}$, regularizing with respect to the mixture $\pi_{\theta}^{\beta}$ (in Nash-MD) is equivalent to regularizing w.r.t. $\mu$ (in Nash-MD-PG). Further, we use an additional parameter $\beta$ (to define the mixture) that can be further tuned independently of $\tau$.

Thus, while it is possible to implement Nash-MD more faithfully, such as by incorporating two-timescale policy gradient versions or exploring variants of regularized policy gradient methods such as PPO (Schulman et al., 2017) or NeuRD (Hennes et al., 2020), we contend that the essence of Nash-MD is encapsulated in Nash-MD-PG for the following reason: the policy gradient algorithm Equation (10) improves the current policy $\pi_{\theta}$ by playing against the geometric mixture $\pi_{\theta}^{\beta}$ while preserving regularization with respect to $\pi_{\theta}^{\beta}$.

Extreme cases for β∈[0,1]𝛽01\beta\in[0,1].

Consider the alternative policy $\pi_{\theta}^{\beta}$ of Nash-MD-PG when $\beta\in$ takes its extreme possible values: $\beta=0$ or $1$. When $\beta=0$ then $\pi_{\theta}^{\beta=0}=\pi_{\theta}$, thus the alternative policy is the current policy, and this algorithm is simply a version of self-play (SP) where one improves its policy by playing against oneself. We do not expect this algorithm (even in its tabular form) to enjoy a last-iterate convergence to the Nash equilibrium; see the discussion around the OMD algorithm in Equation (8).

Now, when $\beta=1$, then the alternative policy is $\pi_{\theta}^{\beta=1}=\mu$, thus we are improving the current policy against the (fixed) reference policy $\mu$ (i.e., optimizing $\pi\mapsto{\cal{P}}_{\tau}(\pi,\mu)$), thus this a version of best-response (BR) against $\mu$. This will generally not converge to the Nash equilibrium either because there is no reason that this BR cannot be exploited.

Nash-EMA-PG.

As an alternative to Nash-MD-PG, we consider as alternative policy $\pi^{\prime}$ another mixture policy $\pi^{\prime}\stackrel{{\scriptstyle\rm def}}{{=}}\pi_{\bar{\theta}_{t}}$ where $\bar{\theta}_{t}$ is a exponential moving average (EMA) of the past values of the parameter $(\theta_{s})_{s\leq t}$, defined (recursively) by $\bar{\theta}_{t}=(1-\beta)\theta_{t}+\beta\theta_{0}$. Thus when $\beta=0$ then $\pi_{\bar{\theta}_{t}}=\pi_{\theta_{t}}$ and the algorithm is just self-play, and when $\beta=1$, then $\pi_{\bar{\theta}_{t}}=\pi_{\theta_{0}}$ and the algorithm is a best response again the fixed initial policy $\pi_{\theta_{0}}$.

Now for any other $\beta\in(0,1)$ the policy uses as parameter a mixture of past parameters. Because of the non-linearity of the policy representation, there is no guarantee that this policy is the mixture of the corresponding past policies. However, prior work in deep learning (Grill et al., 2020; Wortsman et al., 2022; Busbridge et al., 2023; Rame et al., 2023) suggests that it could be a reasonable first-order approximation to it.

Experiments

We now report experiments on a summarisation task and compare several algorithms for NLHF (self-play, best-response against $\mu$, Nash-MD-PG and Nash-EMA-PG) as well as a RLHF baseline.

In this section, we compare parametric preference models ${\cal{P}}_{\theta}$ and reward models $r_{\theta}$. Preference models assigns a score ${\cal{P}}_{\theta}(y\succ y^{\prime}|x)\in$ that can be interpreted as the probability of generation $y$ being preferred to generation $y^{\prime}$ given the context $x$. The preference ${\cal{P}}_{\theta}(y\succ y^{\prime}|x)$ is initialised by using a LLM prompted in the following way:

where $\langle\mbox{text}\rangle$ corresponds to $x$, $\langle\mbox{summary1}\rangle$ to $y$, and $\langle\mbox{summary2}\rangle$ to $y^{\prime}$. We then use the last logit for an arbitrary chosen token and pass it through a sigmoid function to output a single number in $$. This number models the preference${\cal{P}}_{\theta}(y\succ y^{\prime}|x)$. We train the LLM to fit the underlying human preference probability${\cal{P}}(y\succ y^{\prime}|x)$by minimizing a cross-entropy loss on a dataset$D=\{(x^{k},y^{k}_{w},y^{k}_{l})_{1\leq k\leq K}\}$, where$y^{k}_{w}$is the preferred generation,$y^{k}_{l}$is the less preferred generation and$K$ is the number of examples:

In our experiments, we use the summarization dataset described in Stiennon et al. (2020) that has been built from the TL;DR dataset (Völske et al., 2017). We train our preference and reward models on the train set $D_{\texttt{Train}}$, that contains $92820$ examples, and evaluate them on a test set of high confidence data $D_{\texttt{Test}}$. To measure the quality of our models we use the expected agreement, also called accuracy, between our models and the human ratings:

Our first experiment (see Figure 1) shows the accuracy of preference models with different sizes. Our models are T5X encoder-decoder models (transformer models) that have been described in detail in (Roberts et al., 2022; Roit et al., 2023). We use different sizes: T5X-small (110M), T5X-XL (3B) and T5X-XXL (11B). We see, on the test set, that the bigger the model the better the accuracy. However, there is relatively small gains going from 3B to 11B in this specific summarization task. In the remaining, we therefore run our experiments on T5X-XL models only.

Our second experiment consists in looking at the accuracy of T5X-XL reward model versus the accuracy of a T5X-XL preference model. We observe that the preference model has a slightly better accuracy than the reward model on the test set (peak accuracy for the preference model is around $0.78$ vs $0.76$ for the reward model).

2 Supervised fine-tuned (SFT) initial policy

In all our experiments, we will initialize our policy with a T5X-L model and fine-tune it by supervised learning using the OpenAI dataset described in Stiennon et al. (2020) that was built from the TL;DR dataset (Völske et al., 2017). We call this supervised fine-tuned model the SFT. In all our experiments, our policies are initialized with this SFT.

For all our policy models, we opted for a T5X-L model, as opposed to T5X-XL, for computational efficiency and to compute the pairwise comparisons across our policies. The primary objective of these experiments is to provide a proof of concept for the NLHF approach introduced in this paper, rather than striving for state-of-the-art performance in text summarization. Therefore, our aim is to conduct a fair and equitable comparison among the various approaches.

3 RLHF baseline

We established a RLHF baseline by initializing our model with the SFT and then updating the policy by doing 10000 steps of a regularized policy gradient update:

where the reward $R(x,y)$ comes from the trained T5X-XL reward model, as described in Subsection 8.1. We conducted a sweep across a set of values ${0.01,0.02,0.05,0.1,0.2}$ for the parameter $\tau$ of the KL-regularization. The value $\tau=0.05$ has been selected for the pairwise comparison table below.

4 NLHF algorithms Nash-MD and Nash-EMA

We initialize our policy with the SFT and update the model by executing the Nash-MD-PG and Nash-EMA-PG algorithms as outlined in Section 7. The preference model ${\cal{P}}$ used in these algorithms is derived from the trained T5X-XL model, as described in Subsection 8.1.

We conducted a sweep over the values $\tau\in\{0.02,0.01,0.008,0.005\}$ and selected $\tau=0.008$ for all Nash-MD and Nash-EMA experiments for the pairwise comparison table below.

For Nash-MD-PG we conducted a sweep over the mixing coefficient $\beta\in\{0,0.125,0.250,0.375,0.5,$ $0.625,0.75,0.875,1.0\}$ (used in the definition of the alternative policy defined in Section 7.3) and for Nash-EMA-PG we have swept over $\beta\in\{0,0.999,0.9995,0.9999,1.0\}$.

5 Pairwise preference between all the models

Here are the list of all the models we considered for pairwise preference comparison.

SFT: Supervised-fined-tuned, described in Subsection 8.2. All models all initialised with this SFT and this SFT is also the policy $\mu$ we use for the KL-regularization.

RLHF described in Subsection 8.3 with regularization coefficient $\tau=0.05$.

SP (self-play). This corresponds to Nash-MD-PG with mixture coefficient $\beta=0$ (or equivalently Nash-EMA-PG with $\beta=0$ as both algorithms are equivalent for $\beta=0$), described in Subsection 8.4. The policy improves by playing against itself (the alternative policy $\pi^{\prime}=\pi_{\theta}$ is the current policy).

MD1 to MD6 is Nash-MD-PG with $\beta\in\{0.125,0.25,0.375,0.5,0.625,0.75\}$.

BR is best-response against SFT. This corresponds to Nash-MD-PG with $\beta=1$ (or equivalently Nash-EMA-PG with $\beta=1$). The policy improves by playing against the fixed SFT policy.

EMA1 and EMA2 are the last-iterate of Nash-EMA-PG (i.e., returns the last policy), with $\beta\in\{0.999,0.9995\}$.

EMA1* and EMA* are the EMA policy of Nash-EMA-PG (i.e., returns the policy with average weight) with $\beta\in\{0.999,0.9995\}$.

All models are trained for $10000$ steps. The Nash-MD models (as well as SP and BR) and Nash-EMA are trained with a regularization coefficient of $\tau=0.008$. The pairwise preference comparisons under ${\cal{P}}_{\tau}$ are given in Table 1; these figures are estimated based on 1,000 pairwise comparisons, and hence an upper bound on the width of a 95% confidence interval for each is $\pm 0.032$, based on the exact Clopper-Pearson method for Bernoulli proportions (Clopper and Pearson, 1934). Note that the Clopper-Pearson method can be used to deduce a per-element confidence interval which may be considerably narrower in cases where the empirically observed preference rate is close to 0 or 1.

We will analyse these results after the next section where we describe an evaluation of our models based on a preference model build from a much larger LLM.

6 Evaluation using the PaLM 2 preference model

While the ideal approach for evaluating our models would involve soliciting human preferences between summaries generated by different models, we resort to a proxy method using the highly capable LLM, PaLM 2 Large (Anil et al., 2023). We query this model to obtain a preference signal, which we refer to as the PaLM 2 preference model ${\cal{P}}^{*}(y\succ y^{\prime}|x)$, achieved by prompting the LLM in the following manner:

where $\langle\mbox{text}\rangle$ corresponds to $x$, $\langle\mbox{summary1}\rangle$ to $y$, and $\langle\mbox{summary2}\rangle$ to $y^{\prime}$.

This evaluation approach shares similarities with the method employed by Lee et al. (2023). To obtain an assessment of the preference ${\cal{P}}^{*}(\pi\succ\pi^{\prime})$, we compute the ratio between the total number of token ’1’ generated and the total number of token ’1’ or ’2’ across $2000$ samples drawn from the distribution $(x\sim\rho,y\sim\pi(\cdot|x),y^{\prime}\sim\pi^{\prime}(\cdot|x))$.

This ${\cal{P}}^{*}$ serves as an approximate surrogate for human preferences. Notably, it is essential to highlight that the preference model ${\cal{P}}$ utilized during the training of our policies is considerably smaller in size than ${\cal{P}}^{*}$ and corresponds to a different model. Specifically, ${\cal{P}}$ is based on the T5X-XL model, fine-tuned with TL;DR data, whereas ${\cal{P}}^{*}$ is derived from the PaLM 2 Large model.

The pairwise preference comparisons under ${\cal{P}}^{*}$ using the PaLM 2 Large model are given in Table 2. As each element is estimated with $2000$ samples, the confidence interval, an upper bound on the 95% confidence interval is given by $\pm 0.023$, based on the exact Clopper-Pearson method for Bernoulli proportions (Clopper and Pearson, 1934).

7 Analysis of the results

First, let us mention that the RLHF baseline that we have built is a very strong baseline. It beats SFT with a win rate of $99\%$ marking the highest win rate observed against SFT among all models when using the PaLM 2 preference model ${\cal{P}}^{*}$

Best-response against self-play (BR) does not exhibit strong performance. Despite being trained explicitly to outperform self-play during training, its ${\cal{P}}^{*}$-evaluation yields a relatively modest score of $94\%$ against self-play. Furthermore, BR performs poorly against RLHF and all other Nash-based approaches. This suggests the possibility of ’preference hacking,’ where BR may be overly adapting to the preference model by overfitting to the specific SFT policy.

Self-play (SP) exhibits strong overall performance, with notable exceptions in the ${\cal{P}}^{*}$ evaluation against RLHF and the Nash-MD models (for $\beta\leq 0.5$). This suggests that enhancing one’s policy through self-play could be a promising avenue for improving the initial model. However, it’s essential to acknowledge that self-play does not guarantee the attainment of a Nash equilibrium, as cyclic patterns are possible, as discussed in the Theory Section. In particular, SP is found to be vulnerable to exploitation by certain Nash-MD models.

The Nash-MD models, especially those with $\beta\leq 0.5$, exhibit very strong performance. Notably, Nash-MD models with $\beta=0.125$, $\beta=0.25$, and $\beta=0.375$ outperform all other models, including RLHF. Among them, Nash-MD with $\beta=0.125$ (highlighted in bold as ’MD1’) emerges as the top-performing model, surpassing all others in both the training preference model ${\cal{P}}_{\tau}$ and the evaluation model ${\cal{P}}^{*}$.

All Nash-EMA models, including EMA1 and EMA2 (representing the last iterate) as well as EMA1* and EMA2* (representing the average policy), are outperformed by Nash-MD for $\beta\leq 0.5$ and RLHF. This observation may suggest that the first-order approximation of the mixture policy as the policy having an average (EMA) weight may not be well-suited in this context, potentially contributing to the overall lower performance.

Examining Nash-MD, which emerges as the most efficient method, it is interesting to note that both extreme values of the mixing parameter $\beta\in$, namely $\beta=0$ (self-play) and $\beta=1$ (best-response against SFT), result in suboptimal performance compared to intermediate values of $\beta$ (particularly $\beta=0.125$, $\beta=0.25$, and $\beta=0.375$). This trend is visible, for instance, in the highlighted blue row showing Nash-MD (for $\beta\in{0,0.125,0.25,0.375,0.5,0.625,0.75,1.0}$) against RLHF. It suggests that improving one’s policy by playing against a mixture of the initial policy and the current policy yields superior model improvement compared to interactions with either the initial policy or the current policy in isolation.

Conclusion and future work

NLHF emerges as an interesting and promising alternative to RLHF, offering a fresh perspective on aligning models with human preferences. Learning a preference model from human preference data is a more intuitive and natural approach compared to learning a reward model. It involves simpler techniques, such as supervised learning, and doesn’t necessitate specific assumptions, like the Bradley-Terry model.

Once a preference model is established, the concept of the Nash equilibrium naturally arises as a compelling solution concept. Nash-MD, an algorithm that optimizes policies by playing against a geometric mixture of the current policy and the initial policy, has been introduced. We have established its last-iterate convergence to the Nash equilibrium.

We have introduced and implemented deep learning versions of Nash-MD and Nash-EMA in LLMs and reported results in a text-summarization task. For Nash-EMA-PG, we considered both the last-iterate and the average policy. Both Nash-MD-PG and Nash-EMA-PG demonstrate competitive performance compared to the RLHF baseline.

Nash-MD-PG stands out as the best-performing method, surpassing other models in a pairwise comparison, when evaluated with a very large LLM (PaLM 2 Large). The choice of the mixture parameter in Nash-MD entails an interesting trade-off. A parameter value of 0 corresponds to self-play, while a value of 1 represents best-response against SFT. Notably, intermediate values within the range of 0.125 to 0.375 consistently outperform both self-play and best-response, highlighting the advantages of playing against a mixture of policies as opposed to a pure policy.

Future research directions would consider the exploration of various mixtures between the current policy and past checkpoints, extending the concept initially introduced by Nash-MD. Additionally, another immediate direction would consider incorporating a decaying mixing coefficient $\beta$ to align more closely with theoretical considerations.

In conclusion, NLHF offers a compelling avenue for preference learning and policy optimization. The introduction of Nash-MD as an algorithmic solution, along with deep learning adaptations, opens up new possibilities for aligning models with human preferences. Further research in this direction, including the exploration of different mixture strategies, holds significant promise for advancing the field of aligning LLMs with human preferences.

Acknowledgements

We would like to thank the individuals who designed and built the RL training infrastructure used in this paper: Léonard Hussenot, Johan Ferret, Robert Dadashi, Geoffrey Cideron, Alexis Jacq, Sabela Ramos, Piotr Stanczyk, Danila Sinopalnikov, Amélie Héliou, Ruba Haroun, Matt Hoffman, Bobak Shahriari, and in particular Olivier Pietquin for motivating discussions. Finally we would like to express our gratitude to Ivo Danihelka, David Silver, Guillaume Desjardins, Tor Lattimore, and Csaba Szepesvári for their feedback on this work.

References

Appendix A Maximizing expected Elo vs maximizing probability of winning

Consider the following preference model, where the set of actions is $\mathcal{Y}=\{y_{1},y_{2},y_{3}\}$ and the preference table between these actions is

This preference model can be perfectly captured by a Bradley-Terry reward model in which the Elo score of all actions would be (up to an additive constant): $R(y_{1})=0$, $R(y_{2})=\log 9$, and $R(y_{3})=\log 2$.

If we optimize over the simplex $\Delta(\mathcal{Y})$, then the policy selecting deterministically $y_{2}$ is optimal both in terms of rewards and in terms of preference against any policy. However, if we consider a constrained optimization problem where we search for a policy in a subset ${\cal S}\subset\Delta(\mathcal{Y})$, then the optimum of the expected reward and preference may be different. To illustrate, let ${\cal S}$ be the set of probability distributions $\pi\in\Delta(\mathcal{Y})$ such that $\pi(y_{1})=2\pi(y_{2})$.

In that case, the policy $\pi^{*}_{R}\stackrel{{\scriptstyle\rm def}}{{=}}(2/3,1/3,0)$ is optimal in terms of maximizing expected rewards whereas the policy $\pi^{*}_{{\cal{P}}}\stackrel{{\scriptstyle\rm def}}{{=}}(0,0,1)$ is optimal in terms of maximizing preference against any alternative policy in ${\cal S}$. In particular we have

whereas policy $\pi^{*}_{{\cal{P}}}$ is preferred over $\pi^{*}_{R}$, since

Thus if one searches for a policy in ${\cal S}$, then the optimum in terms of maximizing expected (Elo) reward and maximizing preference (probability of winning) are different.

Note that the constraint $\pi\in{\cal S}$ may be imposed in a soft way using regularization. Here for example we could implement a 2-step decisions process where in a first step one would choose the probability mass assigned to $y_{3}$, and in the second step, one would choose the remaining mass to allocate between $y_{1}$ and $y_{2}$. The second step may be constrained in a soft way by penalizing distributions (over $y_{1}$ and $y_{2}$) that are different from a reference distribution $\mu=(2/3,1/3)$ by using a KL-regularization with a large $\tau$ coefficient. In this way the set of effective policies that would be considered would be close to ${\cal S}$.

This example illustrates the fact that in constrained (or regularized) optimization settings, maximizing Elo versus preference are different objectives, even in a setting where preferences can be perfectly expressed in a Bradley-Terry model.

Appendix B Proof of Theorem 1

For any $\pi$, and $0\leq\eta\tau\leq 1$, we have

From the definition of $\pi_{t}^{\mu}$, we have

where we define $Z=\sum_{y^{\prime}}(\pi_{t}(y^{\prime}))^{1-\eta\tau}(\mu(y^{\prime}))^{\eta\tau}$. Thus, for any $\pi$, we have

where we used Jensen’s inequality applied with the concave logarithmic function. We deduce

Now we use Lemma 7 of Munos et al. (2020), restated below with notation.

Write $D_{\varphi}$ the associated Bregman divergence: for $\pi,\pi^{\prime}$,

Let $\delta$ be a vector of dimension $|\mathcal{Y}|$. For any $\pi^{-}\in\Delta(\mathcal{Y})$, define $\pi^{+}$ as

Then for any $\pi\in\Delta(\mathcal{Y})$, we have,

For the choice $\pi=\pi^{*}_{\tau}$ and using the previous lemma, we have

where the last inequality comes from the fact that $\pi_{\tau}^{*}$ is the Nash of the regularized game ${\cal{P}}_{\tau}$: ${\cal{P}}_{\tau}(\pi^{*}_{\tau}\succ\pi_{t}^{\mu})\geq{\cal{P}}_{\tau}(\pi^{*}_{\tau}\succ\pi^{*}_{\tau})=1/2$ and the last equality comes from the definition of the regularized preference.

We deduce that for the choice $\eta=\log T/(\tau T)$ we have

Appendix C Proof of Proposition 1

To prove existence and uniqueness of Nash equilibrium we first note that since ${\cal{P}}_{\tau}(\pi^{\prime}\succ\pi)=1-{\cal{P}}_{\tau}(\pi\succ\pi^{\prime})$ we can re-express the minimax game of Eq. 2 as a symmetric two-player game with payoffs of policy $\pi$ and $\pi^{\prime}$ are defined as

respectively. First we notice that since the payoff of this game is concave in $\pi$ and $\pi^{\prime}$, it possesses a Nash equilibrium (Rosen, 1965, Theorem 1).

To show that this game has unique Nash equilibrium we need to show that its corresponding variational inequality is strictly monotone (Rosen, 1965, Theorem 2). Let $\bar{\pi}=[\pi,\pi^{\prime}]$ and $v(\bar{\pi})=[\nabla_{\pi}R(\pi;\pi^{\prime}),\nabla_{\pi^{\prime}}R(\pi^{\prime};\pi)]$. Then every Nash equilibrium of the game should satisfy the following variational inequality for all $\bar{\pi}$:

Furthermore the variational inequality is strictly monotone if and only if for every $\bar{\pi}_{1}$ and $\bar{\pi}_{2}$ we have that

with equality only holds at $\bar{\pi}_{1}=\bar{\pi}_{2}$ (Rosen, 1965, Theorem 2). We can show this inequality holds by expanding the terms on LHS. For every context $x$ let denote $v(\bar{\pi})(x)$ as the partial derivative $v(\bar{\pi})$ for $x$. We have:

where $\mathbf{P}(y\succ\pi^{\prime}|x)=[p(y_{i}\succ\pi|x)]_{i=1:N}$ and $\log(\pi/\mu|x)=[\log(\pi(y_{i}|x)/\mu(y_{i}|x))]_{i=1:N}$, in which $N$ is the size of the generation set. Plugging this in the LHS of Eq.15 and then exploiting the non-negativity of KL-divergence implies:

with equality only at $\bar{\pi}_{1}=\bar{\pi}_{2}$.