Multi-turn Reinforcement Learning with Preference Human Feedback
Authors: Lior Shani
Aviv Rosenberg
Asaf Cassel
Oran Lang
Daniele Calandriello
Avital Zipori
Hila Noga
Orgad Keller
Bilal Piot
Idan Szpektor
Avinatan Hassidim
Yossi Matias
Remi Munos
Venue: NeurIPS 2024 poster (2024)
Keywords: Reinforcement Learning
RLHF
Human Feedback
Preferences
Optimization
LLMs
Large Language Models
Natural Language Processing
NLP
Learning Theory
RL
Primary area: reinforcement_learning

Abstract: Reinforcement Learning from Human Feedback (RLHF) has become the standard approach for aligning Large Language Models (LLMs) with human preferences, allowing LLMs to demonstrate remarkable abilities in various tasks.  Existing methods work by emulating the human preference at the single decision (turn) level, limiting their capabilities in settings that require planning or multi-turn interactions to achieve a long-term goal. In this paper, we address this issue by developing novel methods for Reinforcement Learning (RL) from preference feedback between two full multi-turn conversations.  In the tabular setting, we present a novel mirror-descent-based policy optimization algorithm for the general multi-turn preference-based RL problem, and prove its convergence to Nash equilibrium.  To evaluate performance, we create a new environment, Education Dialogue, where a teacher agent  guides  a  student  in  learning  a  random  topic,  and  show  that  a  deep  RL variant of our algorithm outperforms RLHF baselines. Finally, we show that in an environment with explicit rewards, our algorithm recovers the same performance as a reward-based RL baseline, despite relying solely on a weaker preference signal.

Multi-turn Reinforcement Learning from Preference Human Feedback
Lior Shani 1i Liorshani@goggl. com
Aviv Rosenberg" *
Asaf Cassel @cassel@mail tau. ac
avivros@google com
Oran Lang
Daniele Calandriello
2
Avital Zipori
Hila Noga
Orgad Keller
Bilal Piot
Idan Szpektor
Avinatan Hassidim
Yossi Matias
Rémi Munos 2
Abstract
Reinforcement Learning from Human Feedback (RLHF) has become the standard approach for aligning Large Language Models (LLMs) with human preferences, allowing LLMs to demonstrate remarkable abilities in various tasks. Existing methods work by emulating the preferences the single decision (turn) level, limiting their capabilities in settings that require planning multi-turn interactions achieve a long-tern goal. In this paper, we address this issue by developing novel methods for Reinforcement Learning (RL) from preference feedback between two full multi-turn conversations. the tabular setting, we present a novel mirror- descent-based policy optimization algorithm for the general multi-turn preference- based RI problem, and prove convergence Nash equilibrium. performance, we create new environment, Education Dialogue, where a teacher agent guides a student in learning a random topic, and show that a deep RL variant of our algorithm outperforms RLHF baselines. Finally, show that in an environment with explicit rewards, our algorithm recovers the same performance as reward-basee RL baseline, despite relying solely weaker preference signal.
evaluate
Introduction
A pinnacle of human intelligence is the ability to communicate with environment, forming complex interactions accomplish challenging goals. Dialogues are one example of such dynamic communication, where one party reacts to signals from the other parties and dynamically plans ahead to steer communication towards their purpose. Recent years have seen scientific breakthroughs in developing Large Language Models (LLMs) that can communicate with humans in natural language [Ouyang al. 2022 Anil et al. 2023 Touvron et al. 2023 OpenAT 2024 Google, 2024]. order to align these models human needs, many efforts have been made to train them with given human feedback. In some concordance with human learning, this is usually achieved by reinforcing behaviors that align with the feedback, using technique
called Reinforcement Learning from
Human Feedback (RLHF: Christiano et al. 2017] Ziegler et al. [2019] Stiennon et al. (020
RLHF methods build on the long studied field of Reinforcement Learning (RL), which focuses on learning optimal actions through reward feedback (a numerical signal) from the environment. However, defining suitable reward function is challenging, leading to the common practice of collecting human preferences between choices. In the absence of rewards, a mapping from preference to reward is typically assumed in the form of the Bradely-Terry (BT; Bradley and Terry (1952) model Rafailov et al. 2023), enabling the use wide-varicty of well-researched
Stiennon et al. 2020
Equal contribution.
Google Research." Google DeepMind. Tel Aviv University.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

RL techniques. Alternatively, recent research [Munos et al. 2023 Azar et al. 2023] Tang et al. 2024] suggests a more direct use of preferences for learning, eliminating the need for this potentialy limiting assumption.
Still, so far the main focus of both the RLHF and the direct preference learning literature was on single-turn scenarios, where given relevant context, the LLM generates one response and receives an immediate feedback that reflects its alignment quality. Importantly, while single-turn RLHF already provides significant gains for valuable Al systems, it lacks the adaptive and long-term capabilities that make human communication such a powerful tool, and usually characterize RL methods. This is especially apparent in temporally extended tasks, such as multi-turn dialogue [Irvine et al. 2023] complex tool use [Wang et al. 2022] and multi-step games [Hendryeks et al. [022].
Contributions. In this work, we focus on improving the communication of AI agents with dynamic environments. To this end, we first extend the RLHF paradigm to the multi-turn setting, where the agent has series of exchanges with an external (stochastic) environment (Section B). Importantly, we consider (human) feedback that compares entire multi-ture turti-turn conversations as opposed to single-turn scenarios, which compare individual actions on per-turn basis. Conversation-lewe feedback allows to capture the long-term effect of individual actions, which may not be immediately apparent, and thus hard to define through turn-level feedback. For example, seller agent asking too high price may seem immediately bad, but becomes potentially good as part of complete strategy to increase sale price. This difference is apparent in our preference model, making it better suited for multi-turn interactions.
Formalizing the multi-turn setting as a Contextual Markov Decision Process with end of interaction
preference feedback, we devise several theoretically grounded algorithms (Section 4 Our main algorithm, Multi-turn Preference Optimization (MTPO), is new policy optimization algorithm for the general multi-turn preference- based setting. MTPO is based on the Mirror Descent (MD) method Nemirovskij and Yudin 1983 Beck and Teboulle 2003 together with self-play (Silver et al. 2017]. and is proven to converge to a Nash equilibrium Nash et al. 1950). i.e., policy which is preferred over any other policy. We prove similar results for MTPO-7, slight variant of MTPO that, similarly to Munos et al. (2023). uses a geometric mixture policy which interpolates the agent's 's policy with a fixed reference policy (with mixing rate T). These algorithms utilize new form of preference-basee Q-function that accounts for the long-term consequences of individual actions. Finally, leveraging our theoretical framework, we modify this Q-function create a multi-turn RLHF algorithm and prove its convergence to an optimal policy (W.I.t the learned reward function).
We complement our theoretical findings with a policy- graddent version of our multi- turn algorithms for deep learning architectures (Section [. To validate our approach, we apply our algorithms to train T5 encoder-decoder L.M [Raffel et al.] 2020). aiming to enhance its multi-turn dialogue scenario without explicit rewards, where
abilities (Sections 5 and 6 We test our approach conversation quality evaluated solely through preferences. To that end, we create new environment called Education Dialogue, where a teacher guides student in learning a random topic, by prompting Gemini (Tea et al. 2023]. The conversation is judged based on preference feedback, using
constitution that defines effective learning [Bai et al., 2022 Lee et al. 2023] (see Section (5) In this environment, our multi-turn algorithms significantly outperform single- turn baselines, and direct multi-tury preference approach outperforms multi-turn RLHF (Section 6). As an additional Finally, we demonstrate that even algorithm achieves comparable performance to
contribution, publicly release the data of Education Dialogue [] in a reward- baaed environment, our preference-basse learning directly from rewards, as in standard RL,, despite using weaker signal. For this experiment, we utilize the LMRL--Gmm [Abdulhai et al. 2023) Car Dealer environment, simulating a conversation where the agent (car dealer) aims to maximize the sale price.
Related work. Most related to our work is the RLHF literature, which aims to improve an LLM policy using preference data collected from humans. Earlier methods model proxy reward [Ouyang
et al. 2022) or preference function [Zhao et al. 2022), and apply traditional RL. techniques. More
recent methods directly optimize the policy [Rafailov et al. 2023 Azar al. 2023 Tang et al.) 2024 Song et al. 2024 Ethayarajh et al. [2024]. Another line of work, which forms the basis for MTPO,
extends RL to games, aiming to compute a Nash equilibrium instead of an optimal policy w.r.t a
fixed reward/preference. This includes Nash-MD [Munos et al. 2023 self-play and mixtures of the
-tt.trtiiiiiiaiaaaa-e---eeeee Dataset

---

two like IPO-MD [Calandriello et al. 2024). Nonetheless, these methods only consider single-turn problems, whereas MTPO provides the first guarantees for multi turt settings. Note the difference from concurrent attempts to extend direct preference optimization to the token level [Rafailov et al. 2024], while a true multi-turn approach must deal with the additional uncontrollable tokens generated by the human in-between agent turns.
More broadly, preference-based RL (see survey by Wirth et al. 2017] studies feedback in terms of preferences over two alternatives rather than absolute rewards. Feedback can be provided in various ways, e.g., at the level of states (turn-level), or entire trajectories [Chen al. 2022 Saha al. 2023 Wu and Sun 2023 Wang et al., [023] Zhha et al.) 2023abb] The focus of this work is last state feedback which is an instance of trajectory feedback. Another closely related model is RL with aggregate feedback where only the sum of rewards in trajectory is revealed to the agent [Efroni
ct al. 2021 Cohen et al., 2021 Chatterji et al. 2021 Cassel et al. 2024].
Lastly, there is vast literature on using RI. to improve natural language generation for dialogue systems. The pioneering work of et al. (2016) focuses on designing rewards capture important dialogue attributes such as semantic coherence and ease of answering. Other works tackle task- oriented dialogue, using RL to enhance the agent's ability to solve the underlying dialogue task [Wei) al. 2018). Instead, this works takes a more general and fundamental approach, focusing on the algorithmic process of aligning an agent which repeatedly interacts with an environment. While dialogue systems are a promising application of our approach, as suggested by the experimental results of this paper (Sections [ @). our algorithmic approach is much broader, including processes such as tool-use, reasoning, and many other applications that require aligning a complex multi-turn agent with human preferences.
Preliminaries
The interaction between an Al agent and its environment is captured in the fundamental contextual RL model, where the context is the initial prompt, the states are conversation summaries, and the actions are responses.
Contextual Markov decision process. hhite-horizon contextual Markov decision process (CMDP) M is defined by a tuple (C, He. where C is the context space, X' is the state space, Y the action space, H is the horizon, 2i X is the initial state, Pe De is the context distribution and p: C x X x y + Ax is the transition function such that p(2' c, 3) is the probability to transition to state x' after taking action y in state x, given context e.
An interaction between the agent and the CMDP environment proceeds in H steps. First, a context C is sampled from Pe. and then the agent begins in the initial state 21- In step h [H], the agent observes the current state T₁ E X, picks an action yh y and transitions to the next state Th+1 sampled from the transition function p(- c, At the end of the interaction, the agent arrives in a final state 1+ For simplicity, we assume that the state space can be decomposed into H+1 ++ disjoint subsets X' = H-- 1 Xn, such that, in step h of the interaction, the agent is in some state Jh X,. A policy π C X Ay is mapping from context and state to a distribution over actions. Together with transition p. æ induces a distribution over trajectories denoted by Pr [.] (and p. [-] for the expectation), in which the trajectory is generated by sampling the actions according to the policy and next states according to the environment.
2.1 Single-turn Reinforcement Learning from Human Feedback
Unlike standard RL where the agent observes reward feedback for its actions, the influential work Christiano et al. [007)] suggests to leverage preference data. In the single-turn setting, the agent generates single sequence y E y given context é C. This is modeled as Contextual Multi- Armed Bandit (CMAB), which is a CMDP instance with horizon H = 1. The feedback is given in the form of preference between two generated sequences. Formally, there exists a preference
model P : C x y y [0. 1] such that P(y y/ c) gives the probability that y is preferred over y' given context e. Preferences naturally extend to policies via expectation P(r π a (c)
(tor y [c].
3

---

Reinforcement Learning from Human Feedback. In RLHF, it is assumed that there is a hidden reward function : x R that defines the preferences through the Bradely-Terry (BT) model, i.e., P(y v' c) (r(,,v) - r(c,y')), where a is the sigmoid. To reconstruct the reward, the RL algorithm is used to optimize the ELO score of the chosen action y using a cross-entropy loss. This technique was adapted to RL fine-tuning L.LMs [Ziegler et al., 2019], and has become the standard approach for aligning LLMs to human feedback [Stiennon et al. 2020
Rafailov et al. 2023].
Learning from direct preferences. Recently Munos et al. 2023 Azar et al. [2023] suggested
to drop the BT assumption, and learn a direct preference model instead of reward. Munos al. (2023) propose the Nash-MD algorithm which converges to the Nash equilibrium of (regularized) preference model, i.e., policy which is preferred over any other policy. iteration 1, Nash-MI) updates its policy T++1 using mirror descent (MD) step projected to geometric mixture policy. The mixture policy T." (- c) oc (e(-) c) 1-n- (t. e) interpolates between the policy Nr and a reference policy μl, given a regularization coefficient > 0. Formally, for learning rate 1): 0,
T++1 (- arg max 7eP(T > Tt cc) [[[[[[[[[[c]] x(1o)Aa
VCE
where [I(T] (L e) (+)o)) E ग (y c) log <(ple)
(wlo)
3 Multi-turn Preference-Based RL
In the multi-tur turn setting, the agent repeatedly interacts with an external environment, an interaction we formulate using the CMDP model. Similarly to the single-turn case, we consider preference- based RL, where the feedback is given preference instead of reward. However, in our case, we assume preferences are between final CMDP states with shared initial context. Formally, there exists preference model P C x Xu+1 x X - [0, such that P( > TH+1 c) gives the probability that # is preferred over s'H+1 given context e. That is, in order to receive feedback, a learning algorithm performs two interactions with the environment and observes a Bernoulli sample for which one is preferred. We follow the natural assumption preference model is symmetric, i.e., P(= IH+1 1 > T c). We define the preference between a final state and a policy by P(x ( x [c) c)- Ex.p [P(( > IH+1 | c)]. Similarly, P(π > a' c) Ex.pl [P((H++ IT c. For brevity, since contexts are independent, context throughout the rest of the paper. Similarly to Munos et al. [2023), our objective is to find a policy x which is preferred over any other alternative policy, i.c.,
Munos et al.
(0023) that the
P(IH+I
omit the
π²" é arg max min P( x'),
which is a Nash equilibrium the above two-player game defined by the preference model, following the minimax theorem (Von Neumann 1928 (see Lemma Notably, due to the anti-symmetric nature of the preference objective, the Nash equilibrium will have both agents following the same policy, and thus can be expressed single policy.
Regularized preference model. In the rest of the paper, we will consider a regularized version of the preference model. This is motivated by practical RLHF algorithms [Stiennon et al., 2020), and generalizes the single-turn model in Munos et al. 2023 Let j be a reference policy, and define the
a-regularized preference model follows:
Pa > x') = P(T
( + aKLp(T'(lx))
where (-I(- is the KL-divergence between the distributions that the policies induce over trajecto- rics in the CMDP. We prove the following two results for the regularized preference model. First, its KL term has value difference- like decomposition into the KL-divergences at individual states. Second, has a unique Nash equilibrium (proofs in Appendix (A).
Lemma 3.1. Let म| be two policies, then: (Lp(T)l))) Er pl EL [[(||"))))
Lemma 3.2. There exists a unique Nash equilibrium of the regularized preference model Pa.
Trajectory-wist vs. turn-wise preference feedback. A naive adaptation of single-turn RLHF to the multi-turn scenario would treat each turn as separate single-turn problem. This would require feedback for the preference between two actions in each turn. Instead, in the setting consider, the

---

preference feedback is only between two full trajectories. Note that a single feedback for the entire trajectory is much more natural when considering conversations, since only the full conversations tell whether the objective was reached. Moreover, collecting preference data for intermediate actions could lead to destructive biases because the quality of an action can change dramatically depending on the actions taken later in the trajectory. For example, chatbot directly answering user query is usually a required behavior. Yet, when the chatbot does not have sufficient information to respond well, asking the user for more details might be better action. Consequently, it is very hard for a rater to know which of these actions is better without observing how the conversation unrolls, i.e., without observing the user's reaction to the chatbot's 's question, and how the chatbot's 's response changes given this reaction. This difference demonstrates the challenge of multi-turn RL as it requires planning ahead instead of myopic reward maximization, which is the approach for single-turn RL.
The multi-turn setting in LLMs. While we consider a general preference- RL setup (through the CMDP model), our focus is on applying this framework to multi-turn language-bal based interactions. The action space y is sequence of tokens of vocabulary V. and the state space at step h, X,, is sequence based on the past sequences. For example, in conversational dialogues, the state 2/ holds the whole dialogue up to the h-th turn, the action yh the current sequence generated by the agent, and the next-state is simply the concatenation of the conversation Iy with the new 3/, and a next sequence sampled by the environment (the user's response). Alternatively, in the complex tool-use case, where an agent repeatedly interacts with different APIs, the current state includes the original user query and summary of results from APIs so far, the action is new API call or user-facing response, and next state is new sequence summarizing previous state with the new API response.
Remark 3.3 (Token-level application to the single-turn auto-regressive case). Notably, this formula- tion also captures the single-turn auto- nuto-regressive case. Clearly, this holds when considering only one turn H 1. but it ignores the token-level optimization done at each turn. Instead, we frame the regr-regressive problem by limiting the actions at each step to single vocabulary tokens, y = V, and assuming null deterministic environment (Ih+1 is the concatenation of z and yb). Importantly, our results apply to the token-level, which is usually neglected when devising single-turn algorithms.
4 Algorithms for the multi-turn setting
Preference-based Q-function. Our algorithms rely on fundamental concept in RL the value and Q-functions. In reward-based RL, it is essential to define the value V' XX' + E as the expected reward when playing policy π starting in some state Th, i.c., VT(Ix)= Ex [E r(IN, (ert).Br)))))))))))))>>>)) æ In the geffreece-bbsse scenario. we argue that value functions remain a powerful tool, even though there is no reward to maximize. We define the following regularized preference- based value functions, which are key to our algorithm.
- - a: > - [=([))) [... Qa (ah, mn) = F.. (( > x')
V.L (Ix) = Ex. [P > x > >t EiEn [L(T||][[=]] [m)].
There are a few interesting points in the definition above. First, note that these values are functions of two policies t, n². This is because the quality of policy cannot be measured on its own, and must be compared to another policy x'. Second, while т starts at the state Ih. the comparison policy x' starts its trajectory from the initial state. This is significant difference from the usual paradigm of Q-functions in RL and might seem peculiar at first glance. However, this formulation captures the fact that the optimal policy in state should be preferred not only over any other policy along the sub-tree starting from this state, but also over any other policy, even ones that do not pass through this state at all. Although different in concept, the following lemma shows that our preference- based Q-function satisfies a value difference lemma, allowing us to optimize the policy locally in order to maximize our global objective (proof in Appendix BB)
Lemma 4.1. Let n, n², be policies, then the following value difference lemma holds:
H1 hh ( n', 2. 2% (KL - aKL ( [m]] Ei
Pa(T > k) - ( > ボ) = Ex .p
where ( - -..'''211 [=]]]= $ (T 1z) - ((1)))(((z)) and (x, v) (i)(()( is the inner product.
5

---

MТPO. We present the MTPO (Multi-tun Preference Optimization) algorithm, which provably solves the multi-tum preference- based RL objective. Formally. we prove MTPO converges to the unique Nash equilibrium of the regularized preference model. MTPO is based on two key principles: First, the regularized preference model defines a two-player anti-symmetric constant-sum game which can be solved using a self-play mirror descent method [Munos et al. [023] Calandriello et al. [2024]. Second, our introduced Q-function allows to reduce the (global) optimization of the game into local mirror descent optimization problems in each state. Together they yield the MTPO update rule for iteration (++ 1).
Te+ (- 2n)) arg max (TT, Qu QT Man] ([(l)()))) - -(1 -aa (TT
where tt is learning rate. The solution can be made explicit in the following form (Appendix E.2
Tead (yn xn) oc plmn w.. "..")""aeee (yn. In) (xa) "... (1..)))))
The intuition behind the algorithm is observed nicely in this update rule we improve the current policy in the direction of the regularized preference against itself (represented by the self-play Q- function), while not deviating too much and keeping close to the reference policy. The following is our main theoretical result: last-iterate convergence to Nash equilibrium (proof in Appendix (B)
Theorem 4.2. Let naa be the Nash equilibrium of the regularized preference model, and Q be a bound on the magnitude of the Q-functions. Then, for a(t+2)
2 MTPO guarantees at every iteration t,
32HQ²2
KL (TallTT)
(1(++1)
Let pmin be the minimal non-zero probability assigned by p. then Q max 4aH log 11,1 1}.
Puin
Proof sketch. By Lemma 3.1 the global KI,p can be decomposed to the local KL, in each state Fh. (T mT+ [an). Then, use MD) analysís in each state to bound the local KI. as:
KL (TT( (1) + 2
+ m) T. 2x.... [xn] [=]ll)))) - (x.ll)))))
giving recursive guarantee dependent on the local one-step regularized advantage of the current policy against the Nash policy and an additional term bounded by Q. We plug this local bound into the KL decomposition (Lemma 3.1). which gathers the local KL terms back to KL, (Ta (m)) Importantly, the value difference lemma (Lemma[4.1) aggregates the advantage terms to the global regularized preference (T, TI) - Pa Te), which is non-positive by the optimality of T This leaves us with the global recursive bound: ( (=]]/T(-1= s (1 ma) (Tall + 2 We conclude by unrolling the recursion with the chosen T).-
MTPO with mixture policy. Inspired by Nash-MD Munos et al. 2023 we present a variant of MTPO which makes of the mixture policy मद (- x)) me xx) oon p(- r.) This variant, which we call MTPO-T (where will be the mixing coefficient in our experiments), gives similar theoretical guarantees (see Theorem B.2 in Appendix (B) and performs better in practice (see Section 6). In fact, the following MTPO-- update rule is almost equivalent to MTPO (Equation [1]
with the only difference being the policies that define the Q-function, . Q
T++1 (-1 JT) arg mag Th Q.i . [MTA] (T[(]|((()
MTPO-7 naturally extends Nash-MD to the multi-tum turti-turn setting, and reveals that Nash-MD is a self algorithm itself, but plays nद.' instead of ग. Practically, MTPO has the computational advantage over MTPO-- (and Nash-MD) of not keeping the additional policy n." Moreover, MTPO avoids the
difficulty of computing the geometric mixture, which Munos al. (023) approximate heuristically via linear interpolation between the logits of the two policies.

---

Multi-furn RLHE. While we focused so far on our preference- based algorithms,, our derivation holds for any online reward function since it is built on the mirror-descent method. Specifically, the case of multi-turn RLHF, we consider the reward function r RL.F learned from preference data using the Bradley-Terry model, and define the corresponding regularized Q-function 0% QT..LHE (Ih.. yh)
Em.p[ [y.LLFF (x - a Σ (=)l))))<= Th, 3/h, By replacing - in Equation with
QT we obtain the multi-turn RLHF algorithm that converges to the regular RLHF objective
- the optimal regularized policy w.r.t. the reward ,LLE (see Theorem B.6 in Appendix B This complementary contribution emphasizes the similarity and difference between the RLHF and MTPO algorithms: The optimization process is identical for both methods, with the exception that the RLHF reward is fixed and computed w.r.t. the data policy, whereas seseeenneebbsse MTPO uses an adaptive self-play mechanism to compute preferences w.r.t. the current policy.
4.1 Deep RL implementation
Our deep RL implementation is natural adaptation of the tabular algorithms presented in the previous section. At each iteration, training data is acquired by sampling batch of contexts from the data, and using each context to sample two trajectories with the current policy To, Then, the final states of both trajectories serve as inputs to a direct preference model that outputs the probability of one being preferred over the other. Similarly to the way the preference model is trained in Nash-MD (Munos] et al. 2023). this preference model is trained in advance on the available offline preference data.
The update rule in Equation relies on the Q-function of the current policy. We therefore use an actor-critic policy optimization based approach and train two models, policy Tæ. and its value == which is typically used to estimate the advantage, AT (1, y) + -T. (1r,)
y) 1 -V (x) [Schulman et al., 2017]. For simplicity and computational efficiency, we implement a palicy-gradient (PG) based approach and ignore the MD stability term KL Te, (To..) similarly to the implementa- tion of the Nash-MD algorithm. We justify this simplification with the fact that the KL regularization w.r.t. the fixed reference policy μ already provides stability to our online algorithm, somewhat (2019) algorithm operates.
o.0
similarly to the way the Follow- Seeoow-Th-RRee The-Tehe-eeeee -egg-eegari Leader (FTRL.][Orboon) Nevertheless, we believe that this additional MD penalty should contribute to the performance and stability of the algorithm, as shown in [Tomar et al.) 2020). and we leave this for further research. This yields the following losses, when action y is played at state I,,
Lpolicy (0;,,) - -Ax TT (z, v) log ( x) + (Te(ll)))) " Toe (x) ?
Lvalue (aauucCo:0 (d)=z)
(Va To (x)
a.
where Ve Tee AA A00 are estimations of the current value and advantage using Generalized Advantage Estimation (GAF, (Schllman et al. (017)). ). We also batch-normalize the value-loss and advantage as recommended in [Andrychowicz al., 2020). Finally, when the policy is auto- regressive language model, which generates actions token-by-token until an end-of-sequence signal generated, we use turn-level value (and not token-level value as done in [Stiennon et al.) 22200). ) That is, the value model gets as input state represented by sequence of tokens, and outputs a single scalar value instead of a scalar value for each token in the action sequence. This is justified by our analysis which treats whole turns as single actions. We leave the many ways to combine turn-level and token-level values for future research.
5 Experimental Setup
This section describes the domains and models used in our experiments. To create online environments suited for multi-turn RL, we mimic the RLHF process [Stiennon et al. 2020), replacing the human
parts with prompted state-of-the-ar LLMs, similarly to Abdulhai et al. 2023 (see Figure T):
1. Dataset creation:
First, we devise a story-line for the user and the environment, describing their characters and goals. Then, we generate a dataset by prompting a state-of-the-art LLM such as Gemini [Team et al., [0233 or GPT [Brown et al. 2020) with the story-line. When generating data, a full conversation is sampled at once, meaning that both the agent and environment are generated together to make them more consistent. Furthermore, create
7

---

Conrersation Ceneratior Process
Troapt:
Somclats cusoeraation betveen tescher athocl and acudent, There anili chance that the teucter is sucoesacul in tasching the atudats as la undecatande the tople, The conmraacion lasca cocplly 10-12 turra het ands whio acctar side aaya (oad conersstioor the toseter rat know that Seforatand. the student poadars to leaco this say, (étudert peactions). the tesctar liker (teashrr pcofarason). prefers to teach txis iTescher reaction:
tesch
(teple), otodent likee (atudert preforereni- teseter
tolloving butpet Descters P Students " Teachers ".irf, Btuderts Ner. feebabilityy fe..
pesbabiiity
uncerateed
io:
topic:
abudent proferescs: istersetive Ioarniog/elasa dioorssonn/acciing quectiens Teacher prefeceros; direot patroctiav/laettueeeeio leanning
student reantions: and gets arators otherwise
Seacher reactions: aod night inciee tosching this
Interaction
Interaction
Teacher: Doday, we'le goino leam about the pariodic table.
Teacher: Coday, 'ze going to isamn abous Peciodic table.
Teacher: pweffr lerture the pertiatio table takular
Teacher: I'n seplate
you
have
arxangenent of the choulaal stoesnts.
studest:
that counds a bit baring..r
Studect: cin toaling little anstous, isaen better theoage
Teacher: It's impertent to undscssand the bustes dizat,
Lccersotion discunslane.
studest: get that, bet Learn baster when can ask queationn and
try
diacsasion for
Studect: 2tn oversheirad. 1 don't think can leaze this say.
Teacher: "t"s your own feult you don't understard. toutre not
Studess: That's interestingt Bo, how do you know which elerent has
pay my
Teacher: specliite
paying
the
the clomene' identity
Teacher: will, cante change by ontire tonching atyle for one
Stadess: think I get it noz, Thasks for coplaising it tn say
studect.
that cculd undecatand!
atudect: Haybe ve eould tay difeacoot sppeoacht
Teacher: tostee velcaee, 10s wove on to the quiz now.
teadhing yeare,
deing.
converaasion]
Proept:
You are expert asocosing teachers, Hore are two Intersction ons between teacher and atudent. 22
(Istacaction
A -ood isteraction betweer tascter and student is dharactaciaed by auversl 'ay alanerss other than sbather the student vas shis underatand the topic. The besctar should possust information clmacly and anthaaiariiaaly, enceczaging quaationa and activa pacttelpatton,
conforesble aeking for clarification, offecing
insights, respectfully
challengtng ideas.
which Interaction better lee the order of Intoractions atfect your anowrdt borgut
Datgut:
Figure I: Education Dialogue data generation process. Top: prompt used to generate conversation with Gemini. Middle: conversations sampled from the the interaction between the teacher and student models. Bottom: prompt used for the preference oracle.
diverse set of conversations, we devise diverse list of attributes for both the agent and environment, sample attributes out of the list, and pass it to the generation prompt.
2. Environment preparation: Once the data is curated, we use it to fine-tune two smaller LLMs, one for the agent and one for the environment, using teacher forcing.
3. Preference/reward learning: We prepare preference data by sampling pairs of conversa- tions from the agent and environment models. To label the data, we prompt a high-capacity LLM with either instructions on how score conversation, conversation over another. The data is used to fine-tune two smaller LLMs: an RLHF reward model (with BT loss), and preference model (with probability regression loss).
criteria for preferring
We experiment with two domains, preference-based Education Dialogue and awward-based Car Dealer:
Education Dialogue. The core of our approach is learning when there is no clear reward, instead only (human) preferences can be acquired. To validate our approach in this scenario, we created a novel multi-turn task for evaluating algorithms based on preference data. In this scenario, which we term Education Dialogue, a teacher (agent) is faced with the task of teaching a student (environment) given topic in the best means possible. We follow the dataset creation procedure and prompt Gemini Ultra [Google 2024] to create such interactions between the teacher and student. The teacher is prompted with a learning topic in science, history, etc. The student is prompted with the characteristics of its learning habits, e.g., prefers interactive learning, lecture- based learning or hands on activities. The preference model is prompted with instructions that define a good learning interaction. For reproducibility, and to further advance the research of the multi-turn setting, we openly release the data and prompts used to create this new benchmark M For more details, see Appendix C and the example in Figure
8

---

Table 1: side evaluation for Education Dialogue using Flan-T: T5 XL as the prompted preference
model. Each entry is the average preference of 1,600 conversations generated with row method y, over ones generated with column method y/. We evaluate each method using different seeds, compute
x 3 comparisons matrix and report the mean (the standard deviation is reported in Appendix D)
SL
Single-tum-rewant Single-tune terge-ttrr-valuee
Multi-turn
SFT
RLHF
Nash
RLHF
Nash
RLHF
MTPO
MTPO-T
SFT
0.164
0.347
0.197
0.324
0.212
0.091
0.093
RLHF-reward
0.836
0.628
0.515
0.654
0.399
0.392
0.354
Nash-reward
0.653
0.372
0.411
0.51
0.328
0.281
0.242
RLHF-value
0.803
0.485
0.589
0.568
0.408
0.396
0.366
Nash-value
0.676
0.346
0.49
0.432
0.45
0.298
0.27
RLHF-multi
0.788
0.601
0.672
0.592
0.55
0.433
0.412
MTPO 0.909
0.608
0.719
0.604
0.702
0.567
0.439
MTPO-T 0.907
0.646
0.758
0.634
0.73
0.588
0.561
Car Dealer. In this LMRL--Gmm [Abdulhai al. 2023] domain, car dealer is assigned with the task of selling car at the highest price to a customer. We skip the data creation step, and directly use the Car Dealer published data to fine-tune the dealer (agent) and customer (environment) T5-large models. The reward is calculated by prompting a Flan-T5 model to extract the sale price from the conversation, whenever a sale has occurred. When using a preference-based algorithm, the preference of one trajectory over the other is computed using the BT model with the rewards of the two trajectories.
Single-turn baselines. The key hypothesis of this work is that conversation-lewe signals are preferred over single-tum signals for optimizing multi-turn trajectories. To verify this in the Education Dialogue domain, we devise two single-turn baselines by sampling data where each conversation turn has two different policy responses. The first baseline, called single-turn-rewarr rates the two responses using a modified preference prompt (see Appendix [ in which the model is asked to evaluate the responses by their effect on the overall conversation. This technique is prevalent when human raters are asked to evaluate multi-turn data. The second baseline, called single-turn-vale assumes access
Monte-Carlo estimate of the value: it uses our original preference prompt (see Figure T by continuing the trajectories of both possibilities and then calculating the preference in the end. For both baselines, we train an RLHF algorithm and a preference based Nash-MD algorithm.
Models. The agent and environment are modeled with T5 encoder-decoder models. Specifically, the T5-large (770M) and T5-XL (3B) models. The same models are used for the RLHF BT-based reward and preference-based models. For prompted reward/prefeerene models, we make of the Flan-T5 XL. (3B) [Chung al. 20244. For training,
a configuration of 4 x 4 Tensor Processing Units (TPUs;; Jouppi et al. [003]] which typically yields 0.1 training steps per second, where a step consists of learning a 10-turn episode. A detailed list of hyperparameters found in We run each evaluation on 1600 random samples from an independent evaluation set.
Appendix D
Experiments
In this section we evaluate the algorithms proposed in Section We start with the preference-based Education Dialogue environment (see Section (5), and compare our multi-turn algorithms SFT (supervised fine-tuning) as well as single-turn baselines. We note that, unlike single-tun benchmarks which are based on data with real human preferences, our golden preference data itself is generated by an LLM (Gemini Ultra). Therefore, the true goal in our curated environment is to align the model with the preference of this highly capable LLM rather than a human rater. While human evaluation is always interesting, here it is actually only a proxy to alignment with the data distribution. To efficiently validate our models, we start with a thorough comparison between our baselines and candidates using prompted Flan-T5 XI. model as judge, which was verified to correlate with the high-capacity Gemini Ultra (Table We then compare our best candidates using the same Gemini Ultra which generated the preference alignment feedback (Table

---

Table 2: Side-by-side evaluation for Education Dialogue using Gemini Ultra as the prompted
preference model. Each entry is the average preference of 1,000 conversations generated with row method y, over ones generated with column method s/'
SL
Single-turn
Multi-turn
SFT
RLHF-reward
RLHF
MTPO-T
SFT
0.206
0.164
0.086
RLHF-reward RLHF-multi
0.794
0.452
0.277
T5-Large (770M)
0.836
0.548
0.288
MTPO-T
0.914
0.723
0.712
SFT RLHF-reward
0.295
0.101
0.041
0.705
0.180
0.069
T5-XL (3B)
RLHF-multi
0.899
0.82
0.139
MTPO-T
0.959
0.951
0.861
Table 3: Car Dealer experiments averaged across 5 seeds and reported with 95% confidence interval.
Online oracle
Model from preferences data
Reward (RL)
MТPO
RLHF
MTPO
Reward (Price)
58.4 (0.3)
57.1 (0.2)
53.2 (0.3)
58.6 (0.3)
Multi single turn. Tables and 2 show that all multi-turn algorithms (MTPO and multi- turn RLHF) with conversation-level feedback significantly outperform the single-turn baselines, validating our hypothesis. We conjecture that it is attributed several factors: First, the effect of single-decision on the whole conversation is hard to capture, causing highly inaccurate single-turn reward/prefereence models. Notably, this leads inferior performance of Nash-MD compared to single-tur hingle-turn RLHF, since it optimizes to find Nash equilibrium of this inaccurate model while RLHF does not stray so far from the reference. Second, even if one could estimate the current policy's 's value, this estimate becomes biased when the policy changes during training. Finally, single-tur preferences consider only "local" decisions which share the same conversational path, and not how these decisions "globally" compare to other possible paths, as captured by the preference-hase Q-function Q TT (see Section
Comparing our three multi-turn algorithms, we see two main results. First, the two variants of MTPO outperform multi-turn RLHF This is expected since the environment not reward- hased, and hence it extends the results of [Munos et al.) 2023 Calandriello al.) [024] from the single-turn case, and supports the theoretical claim that MTPO converges to the Nash policy while multi-turn RLHF converges to the optimal policy w.r.t the learned reward (which is based only on the reference policy). Second, MTPO-7 outperforms MTPO. While both algorithms converge to the same Nash equilibrium, we conjecture that the superior performance of MTPO-r stems from the stochasticity that the mixture policy कē introduces. Namely, H; might tend towards deterministic behavior, causing less informative feedback from slay, as the two sampled trajectories would be very similar. On the other hand, T. is more stochastic, providing diversity in the sampled trajectories.
МТРO vs. multi-turn RLHE
Reward-basee environment. In an additional experiment, we test MTPO and multi-turn RLHF in the bwserd-based Car Dealer environment, where the goal is maximizing sale price (see Section We compare standard online scenario where the reward or preference feedback is given using an online oracle, and an RiHF-like setting, where we first create preference data using the oracle, and then use it to fine- fine-tune (BT) reward and preference models. Table shows that even though MTPO receives preferences instead of the explicit optimization target (rewards), it still learns as good as RL. Interestingly, MTPO recovers slightly higher reward than multi-turn RLHF despite the fact the true preferences are sampled from a BT model. This may imply that a preference model generalizes better than a BT-reward model, perhaps because it is independent of the sampling policy.
RL algorithm against our algorithms in two scenarios: an
Limitations. This work presents proof of concept for the potential of MTPO to improve existing single-turn techniques. Our experimental setup might be limited by the relatively small T5-based models and the use of prompt-based environments. We leave applications to state-of-the-ee models and algorithms, and more realistic environments to future work.
10

---

References
Marwa Abdulhai, Isadora White, Charlie Snell, Charles Sun, Joey Hong, Yuexiang Zhai, Kelvin Xu, and Sergey Levine. Lmrl gym: Benchmarks for multi-turn reinforcement learning with language models. arXiv preprint arXiv:2311.18232 2023.
Charalambos Aliprantis and Kim C. Border. Infinite Dimensional Analysis: a Hitchhiker's Guide. Springer, Berlin; London, 2006.
Marcin Andrychowicz, Anton Raichuk, Piotr Stañczyk, Manu Orsini, Sertan Girgin, Raphael Marinier, Léonard Hussenot, Matthieu Geist, Olivier Pietquin, Marcin Michalski, et al. What matters in on-policy reinforcement learning? large-scale empirical study. arXiv preprint arXiv:2006.055: 05990, 2020.
Rohan Anil, Andrew M. Dai, Orhan Firat, Melvin Johnson, Dmitry Lepikhin, Alexandre Passos, Siamak Shakeri, Emanuel Taropa, Paige Bailey, Zhifeng Chen, Eric Chu, Jonathan H. Clark, Laurent EI Shafey, Yanping Huang, Kathy Meier-Hellstern, Gaurav Mishra, Erica Moreira, Mark Omernick, Kevin Robinson, Sebastian Ruder, Yi Tay, Kefan Xiao, Yuanzhong Xu, Yujing Zhang, Gustavo Hernandez Abrego, Junwhan Ahn, Jacob Austin, Paul Barham, Jan Botha, James Bradbury, Siddhartha Brahma, Kevin Brooks, Michele Catasta, Yong Cheng, Colin Cherry, Christopher A. Proquette-Choo. Aakanksha Chowdhery, Clément Crepy. Shachi Dave, Mostafa Dehghani, Sunipa Dev, Jacob Devlin, Mark Díaz, Nan Du, Ethan Dyer, Vlad Feinberg, Fangxiaoyu Feng, Vlad Fienber, Markus Freitag, Xavier Garcia, Sebastian Gehrmann, Lucas Gonzalez, Guy Gur-Ari, Steven Hand, Hadi Hashemi, Le Hou, Joshua Howland, Andrea Hu, Jeffrey Hui, Jeremy Hurwitz, Michael Isard, Abe Ittycheriah, Matthew Jagielski. Wenhao Jia, Kathleen Kenealy, Maxim Krikun, Sneha Kudugunta, Chang Lan, Katherine Lec, Benjamin Lee, Eric Li, Music Li, Wei Li, YaGuang Li, Jian Li, Hyeontack Lim, Hanzhao Lin, Zhongtao Liu, Frederick Liu, Marcello Maggioni, Aroma Mahendru, Joshua Maynez, Vedant Misra, Maysam Moussalem, Zachary Nado, John Nham, Eric Ni, Andrew Nystrom, Alicia Parrish, Marie Pellat, Martin Polacek, Alex Polozov, Reiner Pope, Siyuan Qiao, Emily Reif, Bryan Richter, Parker Riley, Alex Castro Ros, Aurko Roy, Brennan Saeta, Rajkumar Samuel, Renee Shelby, Ambrose Slone, Daniel Smilkov, David R. So, Daniel Sohn, Simon Tokumine, Dasha Valter, Vijay Vasudevan, Kiran Vodrahalli, Xuezhi Wang, Pidong Wang, Zirui Wang, Tao Wang, John Wieting, Yuhuai Wu, Kelvin Xu, Yunhan Xu, Linting Xue, Pengcheng Yin, Jiahui Yu, Qiao Zhang, Steven Zheng, Ce Zheng, Weikang Zhou, Denny Zhou, Slav Petrov, and Yonghui Wu. Palm 2 technical report, 2023.
Mohammad Gheshlaghi Azar, Mark Rowland, Bilal Piot, Daniel Guo, Daniele Calandriello, Michal Valko, and Rémi Munos. A general theoretical paradigm understand learning from human preferences. arXiv preprint arXiv:2310. 00200.2200000 /2036, 2023.
Yuntao Bai, Sauray Kadavath, Sandipan Kundu, Amanda Askell, Jackson Kernion, Andy Jones, Anna Chen, Anna Goldie, Azalia Mirhoseini, Cameron McKinnon, al. Constitutional ai: Harmlessness from ai feedback. arXiv preprint arXiv:2212.08007, 2022.
Amir Beck and Mare Teboulle. Mirror descent and nonlinear projected subgradient methods for convex optimization. Operations Research Letters, 31(3):667-175, 2003.
Ralph Allan Bradley and Milton E Terry. Rank analysis of incomplete block designs: I. the method of paired comparisons. Biometrika, 39(3/4):324-345, 1952.
Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language models are few-shot learners. Advances in neural information processing systems, 13:1877-1901, 2020.
Daniele Calandriello, Daniel Guo, Remi Munos, Mark Rowland, Yunhao Tang, Bernardo Avila Pires, Pierre Harvey Richemond, Charline Le Lan, Michal Valko, Tianqi Liu, et al. Human alignment of large language models through online preference optimisation. arXiv preprint arXiv:2403.08s 04..0855 2024.
Asaf Cassel, Haipeng Luo, Aviv Rosenberg, and Dmitry Sotnikov. Near-optimal regret linear mdps with aggregate bandit feedback. arXiv preprint arXiv:2405.07637, 2024.
11

---

Niladri Chatterji, Aldo Pacchiano, Peter Bartlett, and Michael Jordan. On the theory of reinforcement learning with per-epseee feedback. Advances in Neural Information Processing Systems, 34: 3401-3412, 2021.
Xiaoyu Chen, Han Zhong, Zhuoran Yang, Zhaoran Wang, and Liwei Wang. Human- -n---ii--tte in-the-loop Provably efficient preference- reinforcement learning with general function approximation. In International Conference on Machine Learning, pages 3773-3793. PMLR, 2022.
Paul F Christiano, Jan Leike, Tom Brown, Miljan Martic, Shane Legg, and Dario Amodei. Deep reinforcement learning from human preferences. Advances in neural information processing systems, 30, 2017.
Hyung Won Chung, Le Hou, Shayne Longpre, Barret Zoph, Yi Tay, William Fedus, Yunxuan Li, Xuezhi Wang. Mostafa Dehghani. Siddhartha Brahma, et al. Scaling instruction-finetuned language models. Journal of Machine Learning Research, 25(70):1-53, 2024.
Alon Cohen, Haim Kaplan, Tomer Koren, and Yishay Mansour. Online markov decision processes with aggregate bandit feedback. In Mikhail Belkin and Samory Kpotufe, editors, Proceedings of Thirty Fourth Conference on Learning Theory, volume 134 of Proceedings of Machine Learning Research, pages 1301-1329. PMLR, 15-19 Aug 2021.
Yonathan Efroni, Nadav Merlis, and Shie Mannor. Reinforcement learning with trajectory feedback. In Proceedings of the AAAI Conference on Artificial Intelligence, 2021.
Kawin Ethayarajh, Winnie Xu, Niklas Muennighoff, Dan Jurafsky, and Douwe Kiela. Kto: Model alignment prospect theoretic optimization. arXiv preprint arXiv:2402.01306, 2024.
Eyal Even-Dar Sham M Kakade, and Yishay Mansour. Online markov decision processes. Mathe-
matics of Operations Research, 34(3)722--73.. 2009.
Matthieu Geist, Bruno Scherrer, and Olivier Pietquin. A theory of regularized markov decision processes. In International Conference on Machine Learning, pages 2160-2169. PMLR, 2019.
Google. Gemini: A family of highly capable multimodal models, 2024.
Dan Hendrycks, Christine Zhu, Mantas Mazeika, Jesus Navarro, Dawn Song, Andy Zou, Bo Li, Sahil Patel, and Jacob Steinhardt. What would jiminy cricket do? towards agents that behave morally. Advances in neural information processing systems, 2022.
Robert Irvine, Douglas Boubert, Vyas Raina, Adian Liusie, Ziyi Zhu, Vineet Mudupalli, Aliaksei Korshuk, Zongyi Liu, Fritz Cremer, Valentin Assassi, Christie-Carol Beauchamp, Xiaoding Lu, Thomas Rialan, and William Beauchamp. Rewarding chatbots for real-world engagement with millions of users, 2023.
Norm Jouppi, George Kurian, Sheng Li, Peter Ma, Rahul Nagarajan, Lifeng Nai, Nishant Patil, Suvinay Subramanian, Andy Swing, Brian Towles, et al. Tpu v4: An optically reconfigurable supercomputer for machine learning with hardware support for embeddings. In Proceedings of the 50th Annual International Symposium on Computer Architecture, pages 1-14, 2023.
Harrison Lee, Samrat Phatale, Hassan Mansoor, Kellie Lu, Thomas Mesnard, Colton Bishop, Victor Carbune, and Abhinav Rastogi. Rlaif: Scaling reinforcement learning from human feedback with ai feedback. arXiv preprint arXiv:2309.000 00267,, 2023.
Jiwei Li, Will Monroe, Alan Ritter, Michel Galley, Jianfeng Gao, and Dan Jurafsky. Deep reinforce- ment learning for dialogue generation. arXiv preprint 1606.0606.0/555 2016.
Rémi Munos, Michal Valko, Daniele Calandriello, Mohammad Gheshlaghi Azar, Mark Rowland, Zhaohan Daniel Guo, Yunhao Tang, Matthieu Geist, Thomas Mesnard, Andrea Michi, et al. Nash learning from human feedback. arXiv preprint arXiv:2312.00888 2023.
John F Nash al. Non-cooperative games. 1950.
Arkadij Semenović Nemirovskij and David Borisovich Yudin. Problem Complexity and Method Efficiency in Optimization. A Inteeinee publication. Wiley, 1983. ISBN 9780471 103455.
URL https: http:/bbook..ggglle.ee gwwgle.cgoooooooooo.. co. wtt..//./000/11111/0AAAAAAAA
12

---

OpenAl. Gpt-4 technical report, 2024.
Francesco Orabona. A modern introduction to online learning, arXiv preprint arXiv: arXiv:1912.13213 2019.
Long Ouyang, Jeffrey Wu, Xu Jiang, Diogo Almeida, Carroll Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Ray, et al. Training language models to follow instructions with human feedback. Advances in neural information processing systems, 35:27730- 27744, 2022.
Rafael Rafailov, Archit Sharma, Eric Mitchell, Stefano Ermon, Christopher D Manning, and Chelsea Finn. Direct preference optimization: Your language model is secretly a reward model. arXiv preprint arXiv:2300.. /82.9 2023.
Rafael Rafailov, Joey Hejna, Ryan Park, and Chelsea Finn. From r to Q": Your language model is secretly q-function. arXiv preprint 1rXiv:2404.12358, 2024.
Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter Liu. Exploring the limits of transfer learning with a unified text-to-text transformer. Journal of machine learning research, 21(140):1-61 2020.
Aviv Rosenberg and Yishay Mansour. Online stochastic shortest path with bandit feedback and unknown transition function. In Advances Neural Information Processing Systems, pages 2209-2218, 2019a.
Aviv Rosenberg and Yishay Mansour. Online convex optimization in adversarial markov decision processes. In International Conference on Machine Learning, pages
PMLR, 2019b.
Aadirupa Saha, Aldo Pacchiano, and Jonathan Lee. Dueling rl: Reinforcement learning with trajectory preferences. In International Conference on Artificial Intelligence and Statistics, pages 6263-6289, PMLR, 2023.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint arXiv: /000:770..000 170.0063777 2017.
Lior Shani, Yonathan Efroni, and Shie Mannor. Adaptive trust region policy optimization: Global convergence and faster rates for regularized mdps. In Proceedings of the AAAI Conference 2020a.
Artificial Intelligence, volume 34, pages 5668-561
Lior Shani, Yonathan Efroni, Aviv Rosenberg, and Shie Mannor. bandit feedback. In International Conference Machine Learning, pages 8604-8613, PMLR, 2020b.
Optimistic policy optimization with
David Silver, Thomas Hubert, Julian Schritwieser,, Ioannis Antonoglou, Matthew Lai, Arthur Guez, Marc Lanctot, Laurent Sifre, Dharshan Kumaran, Thore Graepel, et al. Mastering chess and shogi by self-play with a general reinforcement learning algorithm. arXiv preprint arXiv:1712.01811 2017.
Maurice Sion. On general minimax theorems. Pacific Journal of Mathematics, 8(1):171 - 176, 1958.
Feifan Song, Bowen Yu, Minghao Li, Haiyang Yu, Fei Huang, Yongbin Li, and Houfeng Wang. Preference ranking optimization for human alignment. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 38, pages 11990-18998, 2024.
Nisan Stiennon, Long Ouyang, Jeffrey Wu, Daniel Ziegler, Ryan Lowe, Chelsea Voss, Alec Radford, Dario Amodei, and Paul F Christiano. Learning summarize with human feedback. Advances in Neural Information Processing Systems, 33:3008-3021, 2020.
Yunhao Tang, Zhaohan Daniel Guo, Zeyu Zheng, Daniele Calandriello, Rémi Munos, Mark Rowland, Pierre Harvey Richemond, Michal Valko, Bernardo Ávila Pires, and Bilal Piot. Generalized preference optimization: A unified approach to offline alignment, 2024.
Gemini Team, Rohan Anil, Sebastian Borgeaud, Yonghui Wu, Jean-Bap Alayrac, Jiahui Yu, Radu Soricut, Johan Schalkwyk, Andrew M Dai, Anja Hauth, et Gemini: family of highly capable multimodal models. arXiv preprint arXiv:2312.11805, 2023.
13

---

Manan Tomar, Lior Shani, Yonathan Efroni, and Mohammad Ghavamzadeh. Mirror descent policy optimization. arXiv preprint arXiv:2005.0950 2020.
Hugo Touvron, Louis Martin, Kevin Stone, Peter Albert, Amjad Almahairi, Yasmine Babaei, Nikolay Bashlykov, Soumya Batra, Prajjwal Bhargava, Shruti Bhosale, Dan Bikel, Lukas Blecher, Cris- tian Canton Ferrer, Moya Chen, Guillem Cucurull, David Esiobu, Jude Fernandes, Jeremy Fu, Wenyin Fu, Brian Fuller, Cynthia Gao, Vedanuj Goswami, Naman Goyal, Anthony Hartshorn, Saghar Hosseini, Rui Hou, Hakan Inan, Marcin Kardas, Viktor Kerkez, Madian Khabsa, Isabel Kloumann, Artem Korenev, Punit Singh Koura, Marie-Anne Lachaux, Thibaut Lavril, Jenya Lec, Diana Liskovich, Yinghai Lu, Yuning Mao, Xavier Martinet, Todor Mihaylov, Pushkar Mishra, Igor Molybog, Yixin Nie, Andrew Poulton, Jeremy Reizenstein, Rashi Rungta, Kalyan Saladi, Alan Schelten, Ruan Silva, Eric Michael Smith, Ranjan Subramanian, Xiaoqing Ellen Tan, Binh Tang, Ross Taylor, Adina Williams, Jian Xiang Kuan, Puxin Xu, Zheng Yan, lliyan Zarov, Yuchen Zhang, Angela Fan, Melanie Kambadur, Sharan Narang, Aurelien Rodriguez, Robert Stojnic, Sergey Edunov, and Thomas Scialom. Llama 2: Open foundation and fine-tuned chat models, 2023.
J Von Neumann. Zur theorie der gesellschaftsspiel.. Mathematische annalen, 100(1):295 -200 1928.
Ruoyao Wang, Peter Jansen, Marc-Alexandre Côté, and Prithviraj Ammanabrolu. Scienceworld: Is your agent smarter than a 5th grader? In Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing, pages 11299-11298, 2022.
Yuanhao Wang. Qinghua Liu, and Chi Jin. Is RLHF more difficult than standard RL? theoretical perspective. Teirth-seventh Conference on Neural Information Processing Systems, 2023.
Wei Wei, Quoe Le, Andrew Dai, and Jia Li. Airdialogue: An environment for goal-oriented dialogue research. Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing, pages 3844-3854, 2018.
Christian Wirth, Riad Akrour, Gerhard Neumann, and Johannes Fürnkranz. A survey of preference- based reinforcement learning methods. Journal of Machine Learning Research, 18(136):1444 2017.
Runzhe Wu and Wen Sun. Making rl with preference-based feedback efficient via randomization. arXiv preprint arXiv:2310. 1.55::2310.1455,,, 2023.
Wenhao Zhan, Masatoshi Uehara, Nathan Kallus, Jason Lee, and Wen Sun. Provable offline reinforcement learning with human feedback. arXiv preprint arXiv:2305. 14816, 2023a.
Wenhao Zhan, Masatoshi Uehara, Wen Sun, and Jason D Lee. How query human feedback efficiently in rI? arXiv preprint arXiv:2305.18505, 2023b.
Yao Zhao, Mikhail Khalman, Rishabh Joshi, Shashi Narayan, Mohammad Saleh, and Peter J Liu. Calibrating sequence likelihood improves conditional language generation. In The Eleventh International Conference Learning Representations, 2022.
Daniel M Ziegler, Nisan Stiennon, Jeffrey Wu, Tom B Brown, Alec Radford. Dario Amodei, Paul Christiano, and Geoffrey Irving. Fine-tuning language models from human preferences. arXiv preprint ar 1909::9:990000000 2019.
14

---

Appendix
Table of Contents
Proofs for Section
16
A.1
KL decomposition (proof of Lemma 3.1)
16
Existence and uniqueness Nash equilibrum (proof of Lemma
B
Proofs for section
19
B.1
Regularized preference based Q functionn (proof of Lemma 4.1)
19
B.2
Convergence of MTPO (Proof of Theorem
19
B.3
MTPO with mixture policy (MTPO-T)
20
B,4
Convergence of multi-turn RLHIF
21
The Education Dialogue environment
22
C.1
Prompts for creating the environment
22
2 Examples of interactions
24
D Hyperparameters and additional experimental results
27
D.I Hyperparameters
27
D.2 Additional experimental results
27
E
Mirror descent policy optimization for regularized adversarial MDPs
28
E.1
Model]
28
E.2
Algorithm I: mirror descent policy optimization
30
E.3
Analysis of algorithm
30
E,4
Algorithm 2: mixture mirror descent policy optimization
32
E.S
Analysis of algorithm 2
32
Bounding the Quuuciionn
33
15

---

A Proofs for Section 3
A.1 KL decomposition (proof of Lemma 3.1
Lemma (restatement of Lemma 3.1 Let nf be two policies, then:
(Ty((a||>') ETpp
Σ [I[(T]]>'(<>))
Proof. (-I-) is defined as the KL-divergence between the distributions that the policies induce over trajectories in the MDP (denoted by (I1, ,,..,,,,,, HH, TH+1), formally:
(Lp(T||>))
Σ
Pr r a.
log
Pr [T]
Th: yh) h-1 (yn 2. (p))p
H
Σ Pr 7
log
a.
h ग (ym #))p(2041
Øh. 2hh
(yk xT.
Σ Pr[r]] a.p
log
h=1 n (yn x%,))
(yn
E ET.
log
T' (yh.
h=1
T (yn (x))
ET.
log
T'/ xxn))
E
Em.
(L | (-1
h=1
A.2 Existence and uniqueness of the Nash equilibrium (proof of Lemma 3.2
Lemma (restatement of Lemma 3.2 preference model Pa.
There exists a unique Nash equilibrium of the regularized
Proof. The existence of the Nash equilibrium is proved Theorem A.1 In order to prove the
uniqueness, we use the fact that, from Theorem 4.2 the algorithm MTPO produces sequence of policies Te that converges to any Nash equilibrium πr,, in the sense that lim KL, (=T])=²) 0. From the definition of the KL-divergence between policies, have
H Σ (xL(='||T)[ZN)] L
(Tp [|TT)) = Ex-
(x))LL((T)))
aax
where n=¹ (x) is the probability to reach when following ...
Now, the fixed point of the MTPO dynamics (Equation (2) shows that any Nash equilibrium satisfies, for any X, )
n T 2)) o p(y =) or (m.))
In particular, we notice that any Nash equilibrium has the same support μ. thus the set of reachable states under y is exactly the same set as the set of reachable states under any Nash equilibrium म
So. from any reachable state E X' (i.e., such that p²(x)) 0), we have that the sequence Tt(- z) converges (in KL-divergence) to the Nash equilibrium =" (- 2). Since a single sequence cannot converge to two different values, we have that the Nash equilibrium π (- æ) is uniquely defined in that state. Since the behavior generated by a policy depends on the policy the set of states that are reacheable only, and since we have seen that all Nash equilibria have the same set of reachable states, we deduce the uniqueness of the policy defined by Nash equilibrium.
Theorem A.I. The game defined by the payoff function (π, r+ Pa( n²) has Nash equilib- rium.
16

---

Proof. First we prove that there exists (at least) one max-min policy x" aag maxx min Pa Pa(T= T²).
For any т, the map n' E & + Pa( r') is continuous, thus upper semi-continuous (u.s.c.). We know that the pointwise minimum of u.s.c. functions is also u.s.c. (see, e.g. [Aliprantis and Border (2006). Lemma 2.41). Thus the function π é 1I ming' (a I is also u.s.c. and since II is compact, we can apply Theorem 2.43 of Aliprantis and Border (2006) to deduce that this function attains a maximum value in II and that the set of maximizers is compact. Thus there exists (at least) one policy denoted by x² E arg max min Pa x²).
Now from Lemma A.2 we know that the regularized preference model Pa > x') defines a concave- convexlike game. Also for any x', the map (T T') is u.s.c. Thus we can apply the minimax Theorem 4.2 of Sion 1958 to deduce that
max min Pa( > x²) = min max Pa xx)
We deduce from 2 that the value of the game is 1/2, and that ming Pa (a > x') 1/2. Thus (T" x²) is a Nash cquilibrium of the game defined by the regularized preference model (TT ) + Pa T').
max (axxa(T>>) maxmin Pa T min max Pa (T T') 2 min P > x²) 1
2'
O
Lemma A.2. The mupping (π, Pa(m X') is concave-convexlike, which, in the context of a symmetric preference model, means that for any couple of policies (2)) and any coefficient ee [0, 1], there exists policy Te such that for any policy T², we have
(a > + (1-c))aTT2 x') P (Tc>
Proof. Let us define the notion of reach probability: for any state Z₁, Kr. let us write p² (zx) the probability to reach the specific state I' E Xr, when following æ: p² (*x) = p First notice we can represent the regularized preference Pa PTTTT > T²) using reach probabilities:
PT T'
Σ
p" (2H+1))p (d'm)) xnn))
ZBel Fun
Σ 1,
(())()))((())) (x)))))- (T))
Now, consider two policies J and T2 and coefficient e [0, 1]. From Lemma A.3 we have that there exists a policy Te such that for any The we have pa (xx) cp" (2x) + (1 c)p (Ix). We can write
Pa (T x
Σ
(1-
p" (I'n.)) > z'
h- syeR
H
Σ
Σ
p" (TT))((()))
h= BAE
cP ( > nt) (1 (1- (1)
H
Σ Σ (xn) +11 (())
h- wachh
o (4)))L(FT|l))(a)))) (
Σ
Σ
h= MA
Now from the convexity of π + KL(M]I)) [x]] and the definition of ne, we have that
pT 110
se (1p (mell)))))))))
17

---

Thus
Pa(Te> 2 ( > x (1 (1-))((m2=
H
Σ
Σ
(T) + (1-c)pp (L
cp
Σ
Σ cp" (z.)KL(FT)))(a) (1-c)p c)p² (TT)
a
h- Byeck
c P. (T (1-
Lemma A.3. For any state Ia E Xr. let write p" (æx) the probability reach the specific state In Xn when following n, i.e, p" (In) = Pra pl Then, for any two policies (T1 π2) and any coefficient c [0, 1]. there exists a policy such that for any h I,..., H. + 1, and any In Xn, have
p p==(zn) = cp (xn) (1 (1-c)p"
Proof.
Let us define Te as function of T1. X2, and for any e X, e )
Te (y x) cp
x) + (1 (3) cp (x) (1 - cx)
We now prove the lemma by induction on h. holds for = since we have
pa (=*(x)) = =1 c (1-c) cp" (x1) + (1
Now assume the claim holds for any on E Nr. then for any Thot 1 Xn.1.
n (In-1)= Σ p pm= (IN) Σ p(zn+1 æh. (yn xT))
Vn
p(#1+1 æh. 2h. cp (I Ini + (1-c)p (2x) (3h 1.))
Σ p=a (In)
Σ
cp (2n)(xn) + (1-c)
yn
Σ p æn. vn) cpTh (I xn) + (1 c) (2h T2 (3h 24) pr (Ith)
Σ (x))
Σ Σ p(anol In (h) [cp (IN)T (3h xn) + (1 - ()) ( xx)]] En
cp (Ih+1) + (1 c))=*((x+1))
where the third inequality is by the induction hypothesis.
18

---

B Proofs for section 4
B.1 Regularized preference-based Q-function (proof of Lemma 4.1
Lemma (restatement Lemma 4.1). Let n, be two policies. For every #H+1 & XH+1, it holds that V= (IH+1) P( > T'). Furthermore, for every h e [H] the following recursive relations hold:
Va (In) yn Qax (kh,
20a (Z): 9h) Pmmsi-p(aan (m.mm) Va (Ih-1) [ Moreover, let it be third policy, then the following value difference lemma holds:
Pa( ~ =))= Paa(n > R) = E [E", n' ,a Mrn] aKL(r'Il)))
aKI.(
Proof. We prove the lemma by casting the preference-basee RL problem an adversarial MDP. see Appendix E for the details. Set ((T=-) p > x'), then Q = -a (see Definition E.3
for the definition of the regularized Q-function). Now the lemma follows directly from Lemmas and E.5
B.2 Convergence of MTPO (Proof of Theorem 4.2
Theorem (restatement of Theorem 4.2 1.2. Let ni be the Nash equilibrium of the regularized preference
model Pa. Then, for the choice Nt a(t+2) MTPO guarantees every iteration that
32H
KT (TalLT)) S
a²(++1)*
where Q is a bound on the magnitude of the Q-functions.
Proof. The theorem follows directly from Theorem B.I
Theorem B.1. Running the MTPO algorithm, have that every iteration t:
Fy (. (nn :l: IT)
1
(Ll(Fallmmn) s (1 (1-1): (1-Taa)KLp (F + 2m E
Q (Ih, a log
Thus, for the choice 1):- a(l=2)
2
we have
Tel. xn)) 1l-1 xxh)
KLP (Ll(Tal s a²
max Bri
Σ Qa (Ihs - a log
Finally.
32H
(=.lIT
t+1
max
a
log? logg Umin
where umin -mii((,.))eee p(y) x) is the minimal non-zero probability assigned by μ.
Proof. We prove the theorem by casting the preference-based RL problem as an adversarial MDP, see Appendix for the details. Set (' P(x > Tt). then QT Th (see Definition E.3
for the definition of the regularized Q-function). Now, MTPO is equivalent to running mirror descent policy optimization. Thus, by Lemma E.6 with m
xe(- (0(1))))) (Th.. #(: xhh
(L)(TTl(T..) s (F,
21/ 2
1T (xN..) a log
+m TI) P T())
Tx( (- Ixh) p(( xx)
5 - (T. 21 E.ng
(InS (
a log
where the second inequality optimality of - The last claim follows directly from Lemma E.g Similarly to Nash-MD Manhos et al. [2033], this is the Nash-equilibrium of regularized preference model, P.. following the minimax theorem Von Neumann, 1928
19

---

B.3 MTPO with mixture policy (MTPO-T)
Inspired by Nash-MD, we present a variant of MTPO which makes use of the mixture policy o. which we call MTPO-T. Define the regularized policy qi as a geometric mixture between the current policy ny and the reference policy Ja:
Tely 1 u(y) x)
z x)] Eyey Telll x:) 1-mo x)
The MTPO-r update rule is then:
T++1 [2p) = arg max max Q [ (L(T||T²) v/ [H], E Xn.
"
where KTT(--I-) is the standard Kl-divergence. It is well-known that his optimization problem has the following explicit closed-form:
Tf (Vn Fp. en of (mamm)
Ts+1 (yhh |IA)=
wh [H] E Nr. yn V
En mp( (1/ In) xn)en of (maa)))
Next, show that MTPO-7 converges the Nash equilibrium of the a-regularized preference model.
Theorem B.2. Let Ti be the Nash equilibrium of the regularized preference model Pa. Then, for the choice T} a(t-2) MTPO-T guarantees every iteration that
9HQ2
(L,(FZilT() S (t+
where Q a bound on the magnitude of the Q-functions.
Proof. The theorem follows directly from Theorem B.3 and corollary B.4
Theorem B.3, Running the MTPO-T algorithm, have that at every iteration L:
H
(#h, :) 11
(Lp(TallTTea) s (1 m)a) (1-ma))Ly(TTTll)) + 2n
Σ
Qa
2 Thus, for the choice 1)t a(l-2)
we have
8
KL (Tal(TT) < a² max
Q
Finally.
8H
1
(TallTT)
max
H22 log a
pmin
++1
Proof. We prove the theorem by casting the preference-based RL problem as an adversarial MDP, see Appendix for the details. Set r P(* T(), then Q Q a (see Definition E.3 for the defnition of the regularized Q-function). Now, Nash-MD equivalent to running mixture mirror descent policy optimization. Thus, by Lemma E.7 with =
KT. (T)I(TA s (1 n:0) KT, + 2n R
Σ
Q m (ah, :)
1==1
+ + -ं)) - -P Pa :
()))
$ (11 (1L-m))LL,TT (.) + 27 Ex
Σ
Qa
(xhx >1
(xhy
where the second incquality optimality of m The last claim follows directly from Lemma E.9
20

---

Corollary B.4. Running the MTPO-T algorithm, we have that at every iteration t:
KT (Fal(=))l s (T= + 1t
2
Thus, for the choice 1) a(t-2)
2 have
9H
(Lp(Tall= $ t+1
max
.H2 log" Mmin
a
Proof. By Munos et al. 2023 Lemma 11, for every E Xn. + (FaL(F
KL(T n. o [=a] s (1 (1-1) (=.
We finish the proof by taking the expectation E,,; [ and using Lemmas 3.1 and B.5 The second part is by Theorem B.3
Lemma B.5. holds that (x2ll1))) z/
Proof. By the optimality of Ta have that (a (1) Pa( m²). Now, since Pa T.) = 1/2, we get
1
s P( > n1) 5
2 2
B.4 Convergence of multi-turn RLHF
Theorem B.6. Let To RRLF (-1x:) arg max, Va VT.RLHF (x) for every x X. Then, for the choice
a(H22)' multi-turn RLHF guarantees every iteration I, (T. RLHF (m.)) (mm) s 32HQ²
?)
a²(+1))
Proof. The theorem follows directly from Theorem B.7
Theorem B.7. Running the multi-turn RLHF algorithm, we have that every iteration t:
H
a log Te( xTh)
KLp (T
RL.F (1 (1- (I-M)O))L,,TTIlll + 2n ,. ALHE
Σ
QT
(Ih.
ue( xnn)
R=1
Thus, for the choice 1):- a(l-2) we have
Te(-1 [x))))))
RLHH KL, .
[(Te)
a2 1)
maxx E
30
RLEF
Qa (In. a log
ue( 2hh)
Finally,
32H
KLp T IRLHI (TTe) S
max o.. H2 log Uming
t+1
where umin m)in( u(y) x) is the minimal non-zero probability assigned by μ.
Proof. We prove the theorem by casting the regularized RLHF problem as an adversarial MDP, Appendix E for the details. Set r' p RLLHF (IH+1), then .LH RLHF - (see Defini-
tion E.3 for the definition of the regularized Q-function). Now, multi-turn RLHF is equivalent to running mirror descent policy optimization. Thus, by Lemma with π n .RLH
H
Te(- 2/)
12
KLp(TT RL.F [ (1- (1--ma)KLL
(L, RL.H
2n
RLHF
Σ
Q. (In. alog
AP
1l: 2
RI.H (21)
(21) VoTT"
RLHE
RRHH
(I1)
2
Tt(.
xnh)
(1-maa) (1, + 2m Bag
Σ
QT. (Ins :
alog
ul:
Ihh)
where the second inequality optimality of क; RLHF The last claim follows directly from Lemma
E.8
21

---

C The Education Dialogue environment
C.1 Prompts for creating the environment
We use the following prompt to generate conversations using Gemini GGogge 2024
Simulate conversation between teacher in school and a student. There is a small chance that the teacher is successful in teaching the student he understands the topic. The conversation lasts roughly 10-15 turns but ends when either side says [end conversation]. The teacher wants to teach the student about {topic). The student likes (student_pref)) The teacher does not know that beforehand. The student prefers to learn this way, (student_reactions The teacher likes (teacher_pref] way, (teacher_reactionl) probability that student understood material, in the following format.
He prefers teach this Output the conversation and the
#
Conversation:
Teacher:
Student:
Teacher:
Student:
Probability: "...",
The topic is sampled from the following topics list:
Photosynthesis, Evolution, DNA, Newton's First Law of Motion, Newton's Second Law of Motion, Newton's Third Law of Motion, Archimedes' Principle, Conservation of Energy, Pythagorean Theorem, Allegory, Metaphor, Personification Foreshadowing, Irony, Atoms, Elements, Molecules, The Periodic Table, The French Revolution, The Industrial Revolution, The Russian Revolution, World War 1, World War 2, The American Civil War, The September 11th Attacks, The Declaration of Independence, The Pyramids, The Parthenon, The Colosseum, The Hagia Sophia, The Taj Mahal, The Great Wall of China, The Machu Picchu, Angkor Wat, The Palace of Versailles, The White House, The Tower of London, Notre Dame Cathedral, The Eiffel TowerConfucius, Julius Caesar, Leonardo da Vinci, William Shakespeare, Napoleon Bonaparte, Abraham Lincoln, Albert Einstein, Martin Luther King, Nelson Mandela, Marie Curie, Genghis Khan, Christopher Columbus, Joan of Arc, Winston Churchill, Vincent van Gogh, Pablo Picasso, Salvador Dali, The Roman Empire, The Cold War, Zeus, Poseidon, Ares, Hercules, Achilles, Minotaur, Medusa, The Solar System, The Big Bang, Supply and Demand, Communism, Capitalism, Democracy, Dictatorship, Sigmund Freud, Cells, The Circulatory System, The Respiratory System, The Respiratory System, The Nervous System, Neurons
The student's learning preferences (student_pref) are sampled from the following list:
questions, direct discussions/askiin
interactive learning/class
based learning, hands-on activities/real--orld applications, creative expression/story
22

---

The student's reactions to not learning in their preferred ways (student_rracttion) are sampled from the following list:
and gets rude otherwise, and gets disengaged otherwise, and gets frustrated otherwise, and gets anxious otherwise, but might adapt to other methods, and might tell it to the teacher
The teacher's teaching preferences (teacher_pred) are sampled from the following list:
direct instrruttion/bctuur-bbadddd learning, interactive learning/clss class diseusssonn//inquury--eeere learning, experiential learning/hands activities, formative assessment
The teacher's reactions to different learning methods (teacherr_reaction) are sampled from the following list:
and gets frustrated otherwise, and blames the student otherwise, and gives up otherwise, but might adapt to the student, and might insist on teaching this way
We use the following prompt to query Gemini for the preference between two conversations (conv1 and conv2):
You are an expert at assesing teachers. Here are two interactions between teacher and a student.
#
Interaction 1:
{conv1)
#
Interaction 2:
(conv2)
#
A good interaction between teacher and student is characterized by several key elements other than whether the student was able understand the topic. The teacher should present information clearly and enthusiastically, encouraging questions and active participation. Students should feel comfortable asking for clarification, offering their own insights, and respectfully challenging ideas. Which interaction is better (do not let the order interactions affect your answer)? Output 1 or 2.
For the single-turn baseline, use the following modified prompt to query Gemini for preferences:
23

---

You are an expert at assesing teachers. Here is an interaction between teacher and student.
#
Interaction:
(conv)
#
Here are two possible responses by the teacher:
#
Response 1:
(resp1}
#
Response 2:
(resp2}
#
A good interaction between teacher and student is characterized by several key elements other than whether the student was able to understand the topic. The teacher should present information clearly and enthusiastically, encouraging questions and active participation. Students should feel comfortable asking for clarification, offering their own insights, and respectfully challenging ideas. Assuming that the teacher and student continue the interaction with will lead to a better interaction (do not let the order interactions affect your answer)? Output 1 or 2.
of these responses, which response
C.2 Examples of interactions
1. Teacher: Good morning. Today, we're going talk about personification, literary device that gives human qualities to nonhuman things.
Student: That sounds bit abstract. Can you give example?
Teacher: Sure. 'The wind whispered through the trees.'
Student: But the wind can't 't actually whisper.
Teacher: That's correct. But we' re using personification to create a more vivid image in our minds. Let's try activity. I'll give you sentence, and you try personify it.
Student: Okay, that sounds fun.
Teacher: The car purred down the street.
Student: The car roared down the street!
Teacher: Excellent! You't re getting the hang of it. Now, let's talk about why writers personification.
Student: I'm not really understanding why they do.
Teacher: That's okay. Let's brainstorm. Can you think of any reasons why authors might use personification?
Student: Maybe to make the story more interesting?
Teacher: That's great reason. Anything else?
Student: Maybe make
relatable?
Teacher: Yes, personification can help us relate objects and ideas on deeper level. Do
you think you understand personification now?
Student: think so. It's creative way make things come alive.
Teacher: Exactly. I'm glad you enjoyed learning about it. Let's do quick review before we end the class.
Student: Sounds good.
Teacher: Great. I'll ask you few questions, and you can answer as you were personify- ing writer.
Student: Okay.
2. Teacher; Today, we're going to learn about The Solar System.

---

Student: Sounds boring. Can we do something more hands-on?
Teacher: I have a great activity planned. We're going to build scale model of the Solar System using different-sized balls.
Student: That sounds cool!
Teacher: First, let's talk about the planets. There are eight planets in our Solar System.
Student: know some of them, like Earth and Mars.
Teacher: Excellent! Now, let's start building our model. We'll use these balls to represent the planets and arrange them in order from the Sun.
Student: This is fun! can how big the planets compared to each other.
Teacher: I'm glad you're re enjoying Now, let's talk about the moons and other objects that orbit the planets.
Student: Can build model of the moons?
Teacher: Absolutely! This will help you understand their different characteristics.
Student: think get now. This is great way to learn!
Teacher: I'm so glad to hear that. Let's finish building our model and then we'l 'll review what we we've learned.
Student: Okay.
Teacher: Well done! I believe you have a good understanding of The Solar System now.
Student: Thanks! learned lot. You're welcome. [end of conversation]
3. Teacher: Today, we're going to learn about World War 1.
Student: Okay.
Teacher:
The war began in 1914 when Archduke Franz Ferdinand of Austria Hunriry was assassinated.
Student: I've heard of him.
Teacher: The war was fought between two main alliances: the Allies and the Central Powers.
Student: Can you tell me more about the Allies?
Teacher: Sure. The Allies included France, Russia, and Great Britain.
Student: What were the Central Powers?
Teacher: They
Germany, Austria-Hungary, and Ottoman Russia. Student: This is a lot of information. Can we slow down a bit?
Teacher: Of course. Let's review what we've learned so far.
Student: I'm not sure understand everything yet.
Teacher: That's 's okay. We can go it again. But first, I want you to try summarize what we've learned so far.
Student: World War started when Archduke Ferdinand was assassinated, and the Allies and Central Powers fought each other.
Teacher: Good. Now, let's go over the key events the war.
Student: Okay.
Teacher: The war ended in 1918 with the defeat of the Central Powers.
Student: think understand it now.
Teacher: Great! I'm glad you do.
Student: Thanks, appreciate it. You'l re welcome. [end of conversation]
4. Teacher: Today, we're re going to learn about Machu Picchu, the ancient Incan city.
Student: Can you just tell me the facts? don't 't need all this extra stuff.
Teacher: Sure. Machu Picchu was built in the 15th century in the Andes Mountains of Peru.
Student: What made it special?
Teacher: location on a mountain ridge provided stunning views of the surrounding landscape.
Student: That's it?
Teacher: Well, there's more to it. Machu Picchu was a royal estate or religious sanctuary for the Incan emperor Pachacuti.
25

---

Student: Why didn't 't they just build it on the ground?
Teacher: They thought it would be more likely to be seen from the outside.
Student: Can just move on?
Teacher: No, it's important to understand the historical significance of Machu Picchu.
Student: don't I care. Just tell me what need to know for the test.
Teacher: I'm trying to help you understand the material, not just memorize it.
Student: don't it need your help. Just give me the notes.
Teacher: [end of conversation]
5. Teacher: Today, we'r re going to talk about foreshadowing in literature.
Student: I'm not really into reading. Is there way could learn about it in more creative way?
Teacher: No, I'm afraid not. Foreshadowing is an important concept that you need to understand.
Student:
But learn better through storytelling or games.
That's too bad. You need to learn focus on the material, even if it's not presented in your preferred style.
Teacher:
Student: Maybe we could act out scene where there's foreshadowing?
Teacher: That would be waste of time. We need cover the key points of foreshadowing.
Student: I'm not sure I' I'm going to understand it this way.
Teacher: You will if you pay attention and ask questions.
Student: Can you at least give me some examples of foreshadowing?
Teacher: Sure. In 'Romeo and Juliet,' the prologue foreshadows the tragic end of the two lovers.
Student: That makes sense. How does foreshadowing help the reader?
Teacher: It builds suspense and keeps the reader engaged.
Student: Okay, think I'm starting get it.
Teacher: That's great. I'm glad you'le understanding.
Student: Thanks for working with me. You're welcome. [end of conversation]
26

---

D Hyperparameters and additional experimental results
D.1 Hyperparameters
For both RLHF-based and preference-biee seseenee-baadddee algorithms we conducted a sweep over the KL regular- ization coefficient a {0.0025, 0.005, 0.01, 0.02, 0.05, 0.1}. For preference-based algorithm we also conducted a sweep over the mixing coefficient e { (0,0.0375, 0.0625, 0.125). All models are trained for 50000 steps.
Table 4: Hyperparameters of all multi-turn algorithms.
Hyperparameter
RLHF
MTPO
MTPO-7
# generations per context
2
2
updates per context
2
KL regularization coefficient
0.01
0.005
0.0025
mixing coefficient
0.0375
batch size
16
16
16
GAE coefficient À
0.95
0.95
0.95
policy learning delay
1000
1000
1000
optimizer optimizer decay policy learning rate value learning rate value initialization
AdaFactor
AdaFactor
AdaFactor
0.8
0.8
0.8
4e-5
4e-5
4e-5
4e-5
4e-5
4e-5
pretrained checkpoint
pretrained checkpoint
pretrained checkpoint
D.2 Additional experimental results
Table (full version of Table I):
Side-by-side evaluation for Education Dialogue using Flan-T5 XL as the prompted preference model. Each entry is the average preference of 1,600 conversations generated with row method y, over ones generated with column method y'. We evaluate each method using 3 different seeds, compute x comparisons matrix and report the mean (together with the standard deviation).
SL
Single-tum-reward
Single-turn-value
Multi-turn
SFT
RLHF
Nash
RLHF
Nash
RLHF
MTPO
MTPO-T
SFT
0.164 (.015)
0.347 (.017)
0.197 (.012)
0.324 (.015)
0.212 (.007)
0.091 (.014)
0.093 (.02)
RLHF-reward
0.836 (.015)
0.628 (:015)
0.515 (.016)
0.654 (.016)
0.399 (:06)
0.392 (:029)
0.354 (:017)
Nash-reward
0.653 (.017)
0.372 (.015)
0.411 (.02)
0.51 (.021)
0.328 (.077)
0.281 (.02)
0.242 (:010)
RLHF-value
0.803 (.012)
0.485 (.016)
0.589 (.02)
0.568 (:016)
0.408 (.053)
0.396 (:016)
0.366 (.026)
Nash-value
0.676 (:015)
0.346 (.016)
0.49 (.021)
0.432 (.016)
0.45 (.073)
0.298 (.025)
0.27 (.026)
RLHF-multi
0.788 (.007)
0.601 (.06)
0.672 (.077)
0.592 (.053)
0.55 (.073)
0.433 (:053)
0.412 (.031)
МТРО
0.909 (.014)
0.608 (.029)
0.719 (:02)
01604 (.015)
0.702 (.025)
0.567 (.053)
(1.439 (:034)
MTPO-7
0.907 (.02)
0.646 (.017)
0.758 (.019)
0.634 (.026)
0.73 (.026)
0.588 (.031)
0.561 (.034)
27

---

E
Mirror descent policy optimization for regularized adversarial MDPs
E.1
Model
We start by defining the regularized adversarial MDP model.
Consider setting where the agent interacts with an MDP model for T episodes, such that, in each episode [T]. the agent performs H steps the MDP (from horizon h 1 up horizon h H 1) In short, an adversarial MDP is generalization of this standard episodic MDP setting to the scenario where the reward function different in every episode. This model was extensively studied recent years (see, e.g., Es--Errn- et al. (2009), [Rosenberg and Mansour (2019h a). [Shani et al. 2020b)). We consider a slightly different definition which more focused on our setting.
Definition E.1 (Adversarial MDP). finite-horizon adversarial MDP M is defined by a tuple (X,Y, H,,,, {r")(=) where X' is the state space, Y/ is the action space, H is the horizon, 21 X the initial state, p. X' x y + Ax is the transition function, and If :H+1 + [0, 1] the reward function in episode t.
An interaction between the agent and the adversarial MDP environment proceeds in episodes, and each episode c [T) proceeds in H steps. The agent begins in an initial state æf 21 In step E [H], the agent observes the current state 24, X, picks an action ví, e y and transitions to the next state #h sampled from the transition function p(- æ/, yf)) At the end of the interaction, the agent arrives in final state hH and observes the reward r' (==)-)) For simplicity, we assume that disjoint subsets U Xt. such that, in step h of
the state space can be decomposed into
the interaction, the agent is in some state 24, 6 Xh.
Now, we define the value function in an adversarial MDP, i.e., the expected reward of a policy when interacting with the MDP.
Definition E.2 (Value function). Let M an adversarial MDP and X Ay be a policy. The value function V X' + R of policy æ in episode t is defined as (=*(()) = Er.p (r' xx)] for every h E [H] and z4, Xr. Similarly, the Q-function QT X'x - IR is defined ( yh) E..pp (r'p((((==+1) (IH+1) Zh. 3.
Next, we consider regularized version of the adversarial MDP model. Regularized MDPs also studied recently (see, e.g., Geist et al. [2019], Shani et al. [2020a]). The following definition presents the regularized value with respect to some reference policy μ.
Definition E.3 (Regularized value function). Let f be a reference policy and > 0 be regularization coefficient. The regularized value function and Q-function of policy in episode t are defined as
" Σ
(**) En.p
(IH+1)
[L(TT|[)[<N]]
I
" KL(TT|μ)(=H]]
2 8hh Enp r' ('(2)11)
Σ
Ihh, Vh
We now present a 1-step recursive formula and a value difference lemma for the regularized value function.
Lemma E.4 (Regularized value function recursive relation). Let x be a policy. For every TH XH=A, it holds that Va (x=(() (x Furthermore, for every h 1,..., . H and (In, yb) e
Xr, x V, the following recursive relations hold:
v (IN) = Σ ( (
BARY
Σ
p(an-1 The Uh, (xh+1) (KL[))))[[()))))
Proof. We prove the claim by backwards induction on h. The base case à = H + follows by definition of the value function and the adversarial MDP. Assuming that the claim holds for + 1,
28

---

have that:
H (xn) By, (IHH)))) -a Σ
[L(T 2n
W-hh
H
Σ Pr( =
Σ Σ Prlæw = / [m]]L[
xeN
Σ T xhh)
Σ
Pr|æH-1=2 = I vh
vnyyy
xeXre1
xip
a Σ
(Wh
Σ Σ
Pr[ wh. yn (TL
Mhey
u.
"
Σ T(y 2hh BT (2H+1)) - Σ [L((]|p)[[w]]] mn yh
Mh
Σ T(m 1h 10 (In.W)))))
Moreover,
" (Zh.01)) Bu.p r' (2H-1) -a Σ [L(T]]u)[ Ihe Wh h'ch
= Σ Pr[æH+1= =x 2h. 3n (x)
H
Σ
Pr[xN J.
wh yn (TT(I)))
Σ
p(an-1 The
Σ
Pr[zn-1= x (ht1l1'(()
The WhaieNhes
zeXH+1
x.P
Σ
p( uh)
Σ
Σ Pr[mw = x aari (LT]))))))))))
-
Phe1EX1+1
zeR
[KL(T||u)(MN)
H
Σ p(un-1 Ihe Uh 1r
((nn))) Σ [L(<||][=*]] Øh+1 M=h++
The 1h
aKL(T[lu)[va))
p(un-1 8h) V ( (=L((]
The ex
Lemma E.5 (Regularized Value Difference Lemma). Let n, nt be two policies. Then,
(x v=t'(xx)) E
Σ T n¹, 12 Q%.)) [wn]] [KL((")))) (KL((ll)))
Proof. Let Tr E Xn. First, by Lemma E.5
vz' (x)) =
= (T, 1. [xn]] - 2 [[an]
TTT ,'. 2: [0x" ( Q - Q² [[a
takL( I
3 Σ <'mn xx)p(Zme1 Ins yn (v. (Z - - ((xntz)
29

---

Note that for h H + 1 for any т, HH2H#1 we have ( = (zH+)) By recursively unrolling the above relation, we get
(xn) (xn) -Van)--a'((x> = B
Σ
Qa
Lh=
H Σ
Lht=h
Taking the expectation over the initial state finishes the proof.
E.2 Algorithm 1: mirror descent policy optimization
We define the following mirror descent policy optimization algorithm. In the first episode the algorithm plays the reference policy, i.e., TT μ. Then, its update rule for iteration (t 1) as follows:
(- xn) = arg maxxn((T Q [xx] [x]])] (1
(3)
where T/e a learning rate. The solution can also made explicit in the following form:
T++1 (yh, aT) p(y mr am (uth s..) 1-om " @ ( (px.3))
(4)
To show this, note that by the definition the KL, we can write this update rule differently:
Te (2/k xn))
T (. (a)) arg max Ve
Σ (Mm
xn) Qt (In, 9h) - or log
(L(T[[T)){
( xx)
This is exactly the MD step for policy optimization solution in its explicit form is:
Orabona
2019
Shani al.
2020a
Thus, the
T++1 (yh xx) (ehh xn) xx)c (0% (QT ((n,.n) ) log m(opl=))
We recover Equation (4) by noticing that exp( -am, log ne(uslos)) = x (uh zam ((y ann,
E.3
Analysis of algorithm
Lemma E.6 (Fundamental inequality of mirror descent policy optimization for regularized adversarial MDPs). The following holds when running mirror descent policy optimization (Equation in regularized adversarial MDP, for every policy and every episode t,
H
Te(- 2x) Q log
(II(T](TH)) (nn 2n T..
Σ
ul: wx) 1000
h-1
n VV va (x)))
Proof. Fix a state In E Xr We start by applying Munos et al. ne m()) πt" M, and the vector 8(v) m7 @ 3) log
2023 Lemma 2] with क Wt+1.
This implies that for any policy n
p p()(an)
KL(T|TTe-(EN)) (L(T||=) 2n Q (xn. a log
pl. xnn)
+ +7 Fe( x.n xx), Q (In, - a log Te (
ua( xhh)
30

---

Next, we plug this into Lemma 3.1 to obtain
H
(T)( Ex
Σ
KL [L(T||
H Σ
$ Ex p
[L( [[n]
h-1
Te(- xnh
+ 2m 2 En
Σ
(o."(xnn>> a log
h-1
H Σ
(- .mh T( 1n)) tf (Ih. log (t( [hh)
+ 1)r 1tEE F
Note that
Te(-1 [xx)
Te(. [x)))=)() (
xx,,,ogg
1e(- 22h)
Te. (1)x))
T- 1x)), log
p-- xn))
Te (- IT)
T- 11))), log
+[L((T]A)(=)) - [L(T||))(=N)
pl. (Th)
where the last relation follows simply because:
( Iog, Te(- xN)
1l-
1xh)
(3th 12h)
log (3 x2h)
Σ Mwyy
log
p(yn Ix)
Σ T(yn x 1 Mhyy
Te (Ta)
31

---

Thus, we get
(=p((a(Teet) s Bx
KL n [m)
H
Qa 2a:((2n:)) a log Tr(. Tr(-1xx))
2
2m E R.
ue( 1%))
Te n,, TT [x.))
-.. m.
KT. (T.(T(ll)))) [=]] ( [T<([||[{{[)))
(1 11()) (h1))E..T Er
KT. KT [+]
h=1
Te(: (x))
21/ 2
Q (xk:) a log
H
Mi n
Tee TT 2xt.)""aa aKL(T]| aKI(
TT(- xn)) 2
= (1 - (T)( + 2m W
Σ
( aog
1e( xxh)
Me (V (x)) V.
where the third relation is by Lemmas 3.1 and
E.5
E.4 Algorithm 2: mixture mirror descent policy optimization
Define the mixture policy in iteration as:
(y x)) 1- 7.7 7:0x uuy tha
पt (y x)) Ever ( x) 1 z)naa
We now define the following mixture mirror descent policy optimization algorithm. In the first episode the algorithm plays the reference policy, i.e., лı Then, its update rule for iteration (++ 1) is as follows:
T+ x = arg max
Σ ( xN) "IT, v.) (L(T||=(((m)
(5)
The solution can be made explicit:
T (un mn) oc (2h " (kniiw))
E,5
Analysis of algorithm
Lemma E.7 (Fundamental inequality of mixture mirror descent policy optimization for regularized adversarial MDPs). The following holds when running mixture mirror descent policy optimization (Equation 55) in regularized adversarial MDP, for every policy and every episode I
(Tl(an) s (1 (T, 2 Em.
E1
Σ
H
(ans >)
V. (x:) Val (21))
Proof. Fix state on Xr. We start by applying Munos et al. 2023 Lemma 2] with ':" Me-1. π. = = and the vector 8(y) = n2Qa "(r, v). This implics that for any policy n.
KL(TI]T [Nn] & [-||m + ne m n, Q. # [[an]] 2n Q "E,,
32

---

Next, we plug this into Lemma 3.1 to obtain
KT, (T|(((](T)e)) = F.
Σ
KT. (=.(=[|mm+))1
1=1
Σ
h=1
1/p BT.
Σ
m n. 0% ()(
2 2n E
Σ
(arns" :) ||
h==1
1=
5 B
Σ (1 - 1e (l
(=
#=1
1/p FT
Σ
a n, Q% 2
21 E.
Σ
0
(aris" )) 11:0
Lh=1
h=1
Q (an: 11-)
= (1 7/00) E
+ 2 F Ex
Σ
h=1
1=1
1pp ET
Σ
n, Q% " me
h=1
Q (In ||(
(1 ):a) (T,((T + 2 ByrEEr Brip
Σ
h=1
Va (x1) - -v= (
where the second inequality by Munos et al. [2023 Lemma 1], and the last relation are by
Lemmas 3.1 and E.5
E.6 Bounding the Q-function
Define pmin as the minimal positive probability assigned by the reference policy μ. i.e., Pmiin (a p(y z).
Lemma E.8. For the choice T/ a(e+2); in every iteration I of mirror descent policy optimization holds that
( x)
a( H + 1) log Umin & Q (x, log
s 2 aH log Mmin
((x2)) xX xxxx
(ly xT
Proof. Follows directly from Lemmas
E.9 and
E.10
Lemma E.9, For every iteration t of mirror descent policy optimization it holds that
oH log umin (x.") s
(x,y)) 6 y.
The same holds for Q when rumning mixture mirror descent policy optimization.
Proof. By the OMD optimization problem, (e x)) will not be positive unless pqy x)) (the same holds for ).) Thus, for every x X we have
Te( x)
0 s ([(TT()))
Σ ( x)) log
u(y x)
Σ ( x log T. (y) (1yl0) x)
Σ
F x) log p(y x)
yey
1
Σ
ক x:) log
< log
p(y x)
Pmin
Now, by definition, the Q-function is bounded from above by 1 and from below by aHl log umin-
33

---

Lemma E.10. For the choice nnt- a(t-2)) in every iteration t of mirror descent policy optimization it holds that
1
log Te(y x) y( x)
H log Mmin
log
V(z xx Xx
a
Pmin
Proof. For the upper bound, notice that
Tt ( x) ( x
1
log
log ( (y| æ) log (4y x) s log
S log
( x))
Mmin
For the lower bound, we repeat a similar analysis to that in Shani et al. 2020a Lemma 25]. We start by bounding the partition function follows
m(la/1)) log Σ T x)) " (a,"" (a. lolog mtal Mey
s log E
Te(3/ (r)ee
" 1-aaae
aog
xa ptalle)
y'Ey/
May x))
1) + log y'cy
Σ ( 1 (x)
Te( xx)
nh
1L x)) Tel xx)
$ 1)1 + log
Σ
( x)
V'E
where the first inequality follows since Q y) 1, and the second uses Jensen incquality (with the fact that n S 1). Now, by the update rule of Te.
log T x)
(x(1 (ay x) m(v x)
(v x) (4 x) (t.'' log 2(lo/ moll
log
aea log
log Σ
To(o' xx)e"
yey
( x)
2 (1 a, log
n.Q.. af (I. - 1)
(1y x/)
Tr (y) x)
2 (1 - n.a) log
nt (oH log Mmin 1).
(Lemma E.9
(1
x))
To finish the proof plug Th and unroll t
34

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
The abstract and intro make the following claims: (i) formalizing the multi-
turn setting, which is then presented in Section B (ii) presenting multi-tura algorithms and proving their convergence, the algorithms are presented and analyzed in Section [ (ii) demonstrating the multi-turn algorithms are superior empirically, the experiments detailed in Sections 6
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings. It is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
See paragraph on limitations in the end of the paper.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "LLiitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged
the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
35

---

Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: The theoretical results of the paper are provided in Sections 3 and 4 The full proofs of all the claims are found Appendices and In addition, a proof sketch of the main theoretical result (Theorem 4.2) is found in the main paper.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: Section describes how the experimental setup is created, and Appendix C presents the exact prompts that were used. Section 4.1 gives the implementation details for our algorithms, and list of hyperparameters is provided in Appendix D
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often good way to accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, other means that appropriate to the research performed.
also be provided via detailed
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
36

---

(d)
We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: We publicly release the data of the Education Dialogue environment. Due to technical difficulties, currently do not release code.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips... cc/
Soblic/guides// CoweSuumissionoolooo......oooeel
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https hetpc///gguideesoeeeuuutiiiii wwwoooooiiiiioonn.....ooooooeeee
/ //nips
for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: All the details about the data, the experimental environments, and the hyper- parameters for the algorithms and how they were chosen are described in Sections 5 andd and appendix D
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: All the algorithms are evaluated using 3 different seed and the results are computed on x comparisons matrices, where we report the mean and the standard deviation.
37

---

Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report I-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information the puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
The computer resources for rour experiments are detailed in Sections
5 and
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics https: /ett:://neeui.ppe cccpppblic/tthhccccclllllllllll
Answer: [Yes]
Justification: We have reviewed the NeurlPS code of ethics and made sure that our paper conforms with it.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative socictal impacts of the work performed?
38

---

Answer: [NA]
Justification: This foundational research paper that presents generic algorithms to improve the alignment of LLMs with reinforcement learning algorithms.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative socictal impacts include potential malicious unintended uses (c.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (c.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pre-trained language models, image generators, or scraped datasets)?
Question:
Answer: [Yes]
Justification: All the released data is generated by prompting Gemini, we release the exact prompts as well.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification:
All data/environments that used were cited accordingly.
Guidelines:
The answer NA means that the paper does not use existing assets.
39

---

The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name the license (e.g.. CC-BY 4.0) should be included for each asset. For scraped data from a particular source (c.g.. website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that re- re-packaeed, both the original license and the license of the derived asset (if has changed) should provided.
If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: Section desccribs the exact way in which we created the Education Dialogue enviromments, and Appendix proovdees the exact prompts that we used.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsourcing research with human subjects.
40

---

Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with
human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
41


Reviews:
[{"review_id": "6AjBkTFEHQ", "reviewer": "Reviewer_G1Y8", "summary": "The authors propose reinforcement-learning methods for multi-turn interactions using preference feedback in this paper. They present a mirror-descent-based policy optimization algorithm and prove its convergence to Nash equilibrium.", "questions": "Refer to weaknesses.", "limitations": "The current evaluation is limited and can be extended to other models and tasks to show the effectiveness of the approach.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "- The authors extend the RLHF paradigm to the multi-turn setting for an agent with multiple interactions with an external (stochastic) environment. \n\n- In their feedback, they consider the entire multi-turn conversation and not just a single turn, which enables them to capture the long-term effect of individual actions and evaluate the conversation more accurately.\n\n- The authors create and publicly release the Education Dialogue data.", "weaknesses": "- No human evaluation is performed, and the high-capacity LLM evaluation might not entirely reflect human preferences in a complicated conversation. Also, the prompt used for LLM evaluation only asks what conversation is better in general and doesn't compare different aspects of a good and valid conversation, such as consistency, compliance with the roles specified in the prompt, etc.\n\n- Limited experiments only using small T-5 models and simple configurations.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for taking the time to evaluate our work. Here are the responses to your comments:\n\nHuman evaluation: We refer the reviewer to the discussion in the main response on human evaluation and alignment. We briefly repeat the main message there: The main goal of our experimental section is to test our algorithms against other algorithms in how good they are able to align with preference data.\nUnlike single-turn benchmarks which are based on data with real human-preferences, our Education Dialogue domain is based on Gemini-Ultra curated preferences.\nAs a result, evaluating this alignment using the same Gemini-Ultra model as done in our new presented experiments is true to our goal of understanding how to align to preference data. While human-evaluation is always interesting, here it is actually just a proxy to alignment with the data.\n\nRegarding the prompt for LLM evaluation: We agree that in a real dialogue system, it is important to collect diverse data from raters that account for many attributes of what it means to be a good conversation. However, the goal of this paper is not to create a real dialogue system, but to develop *better algorithms* to be used for alignment. We believe that grounded theory and our experimental results suggest that MTPO should be heavily considered when trying to create such a real dialogue system or any other multi-turn domain. It is important to point out that other algorithm-focused works (RLHF/DPO/IPO/NashMD) are also using a single-preference signal that tries to holistically capture the task (e.g., summarization). This is again due to the fact that these papers are not intended to create a SOTA summarization model, but rather to provide new algorithms to train one.\n\nRegarding model sizes: We added experiments with T5-XL (3B) that solidify the conclusions of our original experiments and we plan to add additional experiments with T5-XXL (11B) for the camera ready version.\nWe refer the reviewer to the general response for a detailed discussion of our results.\n \nIn light of the above, we kindly request the reviewer to reconsider their score based on both the significance of our theoretical contribution and the new experiments showing that our results extend to larger models.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "livVN4H64w", "reviewer": "Reviewer_AyR4", "summary": "This paper aims to propose a new reinforcement learning with preference data method for multi-turn conversations. The proposed method is based on the assumption that reaching the Nash equilibrium of the current and another policy can lead to good optimization. The proposed method is stated primarily to extend a prior work called “Nash learning from human feedback” to multi-turn setting.", "questions": "As listed in weaknesses.", "limitations": "The paper has discussed the proper amount of limitations.", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 1, "contribution": 2, "strengths": "* This paper provides multiple theoretical discussions to lay the ground for the formulations.\n* The proposed method may be helpful in the scenario that we only have one overall reward for a dialogue session with multiple turns.", "weaknesses": "1. The definition of Nash Equilibrium in the paper may not be correct (e.g., in L55-56, “ a policy preferred over any other policy”). The definition of Nash Equilibrium is more like that one agent cannot get a better reward by just changing its action. However, there could be a globally better policy. I also do not find this paper citing any game theory or original Nash Equilibrium papers.\n2. This paper can be more well-motivated. I still don’t know why we need Nash equilibrium and the proposed method for multi-turn natural language generation (NLG). The proposed method in this paper is not specially designed for multi-turn but only extends a general method for NLG training to multi-turn setup, which is often done and can be done for most general methods.\n3. This paper does not compare or even just discuss the whole line of multi-turn RL research in NLG for a long time, thus not showing innovations compared to prior works. For example, Li, Jiwei, et al. \"Deep Reinforcement Learning for Dialogue Generation.\" Proceedings of the 2016 Conference on Empirical Methods in Natural Language Processing. 2016.\n4. I’m not sure why the paper highlights and introduces Contextual MDP (CMDP). First, CMDP may not be practical or useful in multi-turn conversations (the key topic discussed in this paper), while the conversation history is considered as part of the state x. The paper’s method derivation also skips the context space. Therefore, I don’t see the necessity of using CMDP. Second, if I do not understand it wrongly, the CMDP is based on prior work (Contextual Markov Decision Processes https://arxiv.org/abs/1502.02259). However, this paper again does not state the reference.\n5. This paper could be organized better. Many old knowledge and newly proposed ideas are mixed together, making it hard to identify which parts the paper really proposes or just restates other works' contributions.\n6. As the update is based on Nash Equilibrium reached by the current learning policy taking the prior iteration policy as the opponent, doesn’t it mean the policy is learned to be better than its prior iteration? And therefore, it can be reduced to optimizing every turn (while considering all the prior conversation history) with each turn’s rewards and meanwhile constraining the policy to not diverge largely from prior iteration ($\\pi_t$) and the base policy ($\\mu$)? According to the paper’s experiments writing, I cannot ensure the input, output, and rewards used for every baseline. I’m particularly interested in the performance of optimizing every turn ($y_h$) with their own complete history ($x_h$) and a trained or supposed reward for every one of them ($r_h$) using an optimization method that regularizes the policy difference between each iteration, e.g, TRPO or PPO.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for carefully reviewing our work. In the following we answer your concerns:\n1. Our definition of Nash equilibrium is correct and this is in fact the most natural definition that arises from our multi-turn preference model. Note that only a pure Nash equilibrium satisfies ”one agent cannot get a better reward by just changing its action”. Generally, a Nash equilibrium is defined as a set of players’ **strategies** for which no agent can increase their *payoffs* by changing their own strategy. This holds beyond simple constant-sum matrix games, and can be extended to the concepts of subgame perfect nash equilibrium in extensive-form games or Markov Perfect Equilibrium in Stochastic games, which are similar to our formulation. \nImportantly - (i) even in matrix games, strategies are not necessarily “pure”, meaning that a strategy does not equal an action. Instead, in the RL terminology, **strategy = a (stochastic) policy**, and in our multi-turn case, the policy is a function of a state $\\pi(a|s)$. (ii) In alignment in general, and particularly in our multi-turn case, the *payoff* of a game is not the “reward” but the **preference** of one policy against another.\nAll in all, this makes our definition quite natural: A good **policy** is a one that is **preferred** over any other policy. Notably, there does not exist a preference model for individual actions (only entire trajectories). \nFinally, due to the structure of the regularized preference objective (anti-symmetric), the Nash equilibrium will have both agents following the same policy and thus we can express it in terms of a single policy such that no other policy is preferred over it. We will be happy to provide additional clarification, and we will add this discussion together with relevant game theory citations in the final version.\n2. Regarding motivation: We disagree that the paper is not well-motivated. Multi-turn interactions are extremely important for LLM alignment because we use them in a multi-turn conversational manner. Moreover, the motivation for exploring Nash equilibrium in this setting is exactly the same as in the single-turn case. Just as NashMD and IPO motivate their work, since the data itself is preference-based, there is no reason to assume the existence of a reward model. Therefore, both our work and NashMD/IPO give stronger theoretical guarantees on the policy that they converge to. Moreover, both NashMD and our MTPO algorithm are shown to be superior to RLHF baselines in practical experiments.\n3. Regarding comparison to NLG literature: While our paper investigates LLM alignment, which is not built upon literature on dialogue NLG, we do agree with the reviewer that this literature should be referenced. We will add these references and relevant discussion  in the camera-ready version.\n4. Regarding contextual MDPs: The single-turn alignment problem is usually described as a contextual multi-armed bandits problem (e.g., section 3 of the NashMD paper). Therefore, it is natural and rigorous to treat the multi-turn problem as a contextual MDP. In our formalization we used this description, but as often done in the single-turn case, we omit the context in our analysis for brevity. Importantly, the problem is indeed a contextual MDP and we will be happy to add the citation.\n5. We disagree with the claim that old knowledge and newly proposed ideas are mixed together in the paper. We kindly ask the reviewer to explicitly point us to the places where this happens, so we can improve the presentation of the paper. Nonetheless, for better readability, we will include the organization of the paper in a paragraph in the introduction. In short, the preliminary section (section 2) is the only place where previous knowledge is presented, while all the following sections present our novel ideas.\n6. If we understood the reviewer’s intention correctly, your suggestion is essentially what we refer to as single turn experiments, which perform markedly worse than our multi-turn variants. Similarly to your suggestion, **there already exists a KL-penalty** to the previous policy $\\pi_k$ and the anchor $\\mu$ in *both* our theoretically grounded MTPO algorithm (eq. 1), and in our theoretically proven Multi-turn RLHF (Section 4, Multi-turn RLHF paragraph). The former is a result of the fact that both of these algorithms are based on Mirror-Descent policy optimization, similarly to TRPO and PPO [2, 3]. This term is aimed at increasing learning stability (as in TRPO/PPO). \nFor our single turn experiments, we “suppose” a turn level reward/preference signal using two methods. (1) Using a prompted model (2) By rolling out two samples of the conversation until their end and querying the trajectory level preference model. Our multi-turn algorithms essentially replace this supposed reward signal with a correct notion of preference/reward based $Q$ function, which is one of the key contributions of our work.\n \n[1] Nash Learning from Human Feedback, Munos et al.\n\n[2] Adaptive Trust Region Policy Optimization: Global Rates and Faster Convergence to Regularized MDPs, Shani et al.\n\n[3] Mirror Descent Policy Optimization, Tomar et al.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Cnrgcrnp7q", "reviewer": "Reviewer_rfuJ", "summary": "This paper views the problem of RLHF for LLMs fine-tuning from a multi-turn interaction perspective, which is natural and promising. This problem is important and interesting to study. A formulation of multi-turn preference-based RL is given. Based on the formulation of the task and existing methods for the single-turn setting, a series of methods, including a Bradely-Terry (BT) model-based RLHF method, namely Multi-turn RLHF, and two Nash-MD algorithm-based methods, namely MTPO and MTPO-$\\tau$, are proposed. Proofs of the convergence of the proposed methods are presented. The effectiveness of the proposed methods based on multi-turn setting against conventional methods based on single-turn setting is evaluated on the task of Education Dialog. Additional experiments on the Car Dealer task further demonstrate the effectiveness of the MTPO method.", "questions": "1. Single-turn RLHF v.s. multi-turn RLHF\n\t- Is it correct that multi-turn RLHF uses a subset of training data that is used for single-turn RLHF? It would be interesting for the readers to know more information about the training data used for each method.\n2. Efficiency of difference methods\n\t- Training efficiency is a crucial factor for RL-based methods. The multi-turn setting could potentially make the RL training less efficient as it only uses sparse conversation-level feedback. It would be interesting to see the training time before reaching convergence for different settings and methods.\n3. Generalizability\n\t- The paper evaluates the benefit of adopting the multi-turn setting and the effectiveness of the proposed methods (multi-turn RLHF, MTPO, MTPO-τ) on the self-designed Education Dialog task. Could you discuss other tasks that could benefit from multi-turn RLHF? Can tasks involving multi-step reasoning benefit from the multi-turn setting?\n4. MTPO (online oracle) v.s. MTPO (preference data) in the Car Dealer task\n\t- Could you please present a possible explanation why MTPO (preference data) outperforms MTPO (online oracle)?", "limitations": "Limitations of the paper is discussed.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "1. The perspective of viewing the LLM alignment problem from the conversation level itself is novel and worthy of study. I believe methods derived from this perspective will play an essential rule in LLM alignment. \n2. The motivation and the potential advantage of considering LLM alignment from a multi-turn perspective is well explained.\n3. This paper is written clearly and easy to follow.", "weaknesses": "Many long-standing challenges in conventional RL research may occur in the setting of multi-turn preference-based RL, such as credit assignment,  sparse rewarding, and the trade-off between exploration and exploitation.  The current experimental results are not very insufficient to show the effectiveness of the proposed methods: \n1. Models: The paper only reports evaluation results using one LLM, i.e., the T5-large encoder-decoder model (770M parameters). Though it is unnecessary to evaluate the methods using large-scale LLMs in a research paper, reporting results based on diverse small-scale models, e.g., ~2B parameters, should be practically doable and would make the argument more convincing. It is noted that the authors discussed this as a known limitation, however, I believe more sufficient experiments on diverse models need to be considered to support the claimed contributions of this paper.\n2. Tasks: Only one self-constructed task is used to compare the proposed methods against methods in the conventional single-turn setting. Multi-turn conversation is ubiquitous in application scenarios of LLMs. It would be interesting to see the performance of the proposed methods on other tasks.\n\nMinor suggestions: \n1. The concept of \"anchor policy\" should be explained in more detail to make it easier to understand the problem formulation and methods.\n2. Derivation of Equation (1) to Equation (2) is missing.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for carefully assessing our work. We kindly point the reviewer to the general response regarding their concerns with the size of the models – we conducted additional experiments with T5-XL (3B) that solidify the conclusions of our original experiments. We plan to add additional experiments with T5-XXL (11B) for the camera ready version.\n\nRegarding tasks, we agree that it would be very interesting to test our algorithms on other benchmarks. Specifically, we see tool-use and long-term reasoning as particularly important and interesting tasks. However, when writing this paper, we could not find much prior alignment work for the multi-turn setup for natural language, and therefore there was no usable multi-turn task. Instead, we could only find reward-based tasks like the LMRL-GYM, that the car dealer experiment is based upon, in which the goal is the usual RL goal of improving a reward, and not improving the alignment w.r.t. preference data. This has led us to develop a new task for this setting, Education Dialogue. We believe that this task is an important contribution by itself, and will allow future research on this topic, and we will be happy if other researchers can create new relevant tasks for this topic.\n\n\nThanks for the minor suggestions, we will clarify these in the final version.\n1. The concept of an anchor policy is wide-spread in the alignment literature, and refers to regularizing towards the initial supervised policy so that the learned policy will not diverge too far from the good properties of the base model. We will make sure this is clearly stated.\n2. Regarding the derivation of eq. (2) from eq. (1): Thanks for the comment, it is quite straight-forward and we will make sure a rigorous derivation appears in the appendix: It is widely known that the solution for any policy $\\pi’$, $ \\pi^* = \\arg\\max \\langle Q(\\cdot), \\pi(\\cdot) \\rangle - KL(\\pi || \\pi’)$ is $\\pi^*(\\cdot) \\propto \\pi’(\\cdot) \\exp(\\cdot)$  (This is commonly used in mirror-descent based algorithms, as well as in DPO). From here, we note that it can be shown with a simple algebraic manipulation that the optimization problem in eq. (1) is equivalent to the above optimization problem, when $\\pi’=\\pi_k^\\mu$, the geometric mixture $\\pi_k^\\mu \\propto \\pi_k^{1 - \\alpha \\eta_k} \\mu^{\\alpha \\eta_k}$. The derivation is concluded by plugging this in the solution presented above. \n\nRegarding the questions asked by the reviewer:\n1. We would like to clarify that single-turn RLHF uses feedback for each individual turn, which does not exist (or is very hard to define) in tasks that are inherently multi-turn. This is validated in our experiments in which single-turn baselines perform significantly worse than the multi-turn algorithms. Specifically, we see that even if we artificially create single-turn feedback, it is hard to define it in such a way that aligns with the overall preference (which is the alignment goal in this setting). Moreover, unlike trajectory-level feedback, turn-level feedback depends on the policy that continues the conversation after this specific turn, and therefore becomes biased once the policy changes through the learning process.\n2. We agree that training time is an important question, but this is not the focus of this paper and we leave this to future research. We focus on whether multi-turn RL improves upon single-turn in tasks that are inherently multi-turn. Both our theory and our experiments corroborate that a multi-turn approach is crucial for obtaining a better policy. Depending on the application and the resources, different projects may choose whether they are able to apply it or not.\n3. Regarding different tasks/applications for multi-turn RL please see the second paragraph.\n4. Note that the difference in performance between MTPO (preference data) and MTPO (online oracle) is very small, which leads us to believe that they are actually roughly equal in performance. A sensible explanation is therefore that both of them converged to the optimal policy (or at least some local optimum). Thus, MTPO (online oracle) cannot outperform MTPO (preference data) even though it observes better feedback.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "GX18vLdtB1", "reviewer": "Reviewer_TXJA", "summary": "The paper presents a novel mirror-descent-based policy optimization algorithm for multi-turn preference-based RL in the tabular setting. It proves the convergence to Nash equilibrium and evaluates the algorithm's performance in the Education Dialogue environment, where a teacher agent guides a student.", "questions": "- Have you considered extending your algorithm to incorporate decoder-only models like 7B llama or mistral? Since decoder-only architectures are prevalent in mainstream LLMs, this could be a valuable addition.\n- Reward reliability is a concern, even when produced by off-the-shelf LLMs. I'm curious if there are any discussions in the paper regarding rewards in the multi-turn RLHF settings, as this would be a significant contribution.\n- I couldn't find any explanation regarding the absence of a reward model in your settings. Could you provide some clarification? This deviates from the typical formal RLHF pipeline.", "limitations": "This work only utilizes relatively small T5-based models and prompt-based environments.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper is well-written and easily understandable.\n- The work extends RLHF to the multi-turn setting.\n- The proofs provided are comprehensive, and the section on mirror descent policy optimization is particularly interesting.", "weaknesses": "- The experiment employs a small model, which may limit its generalizability to larger-scale models used in current LLMs.\n- The evaluation solely relies on reward-based judgments, and it would be beneficial for the author to consider incorporating GPT4 or Gemini to assess win rates compared to other baselines.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for evaluating our work.\n\nWe would like to point the reviewer to the general response regarding their concerns with the size of the models and using ChatGPT/Gemini for evaluations. In short, we conducted additional experiments with T5-XL (3B) that solidify the conclusions of our original experiments, and added evaluations using Gemini-Ultra that again reach similar conclusions to the original evaluations in the paper. We plan to add additional experiments with T5-XXL (11B) for the camera ready version.\n\nRegarding the questions asked by the reviewer:\n1. Performing additional experiments with decoder-only models is indeed valuable, but this is left for future work since obtaining SOTA models is not the purpose of our experiments. The experiments in the paper validate our theoretical findings and the efficacy of our preference-based multi-turn approach. Please see additional explanations in the general response regarding T5-large models.\n2. Regarding a discussion on the rewards, we kindly ask the reviewer to read the general response regarding the soundness of our evaluations and the new evaluations that we now added.\n3. Regarding the absence of reward, we note that the data is inherently preference-based so there is no reason to assume that a reward exists. Moreover, as shown by the NashMD paper [1], there are situations that cannot be captured by a reward, only by a direct preference model. For further explanations, we kindly refer the reviewer to the general response about motivation and evaluations.\n\n[1] Nash Learning from Human Feedback, Munos et al.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We thank the reviewers for the time and effort put into the reviews. The following address points that appeared in multiple reviews.

# Paper Scope:
It appears to us that the reviewers have dedicated most of their attention to the experimental results, potentially overlooking the paper’s main contributions, i.e., introducing fundamental and grounded novel algorithmic concepts and a new multi-turn setting for LLM alignment. We emphasize that the purpose of our experiments is to validate our approach and theoretical findings in a practical setup, rather than to obtain SOTA.
   
Concretely, we kindly ask the reviewers to re-consider their judgment of the paper in light of the following main contributions:
1. We introduce the multi-turn setting for LLM alignment, which judges agents based on their overall communication capabilities instead of just their ability to provide an immediate useful response. This is crucial for enhancing LLM capabilities in scenarios, such as planning and complex tool-use. Moreover, we mathematically formalize this setting and define the novel objective of finding the policy that is best aligned with human preferences.
2. We identify a novel preference-based non-symmetric Q-function as the fundamental mathematical object that allows us to efficiently solve the multi-turn objective. Furthermore, we use this Q-function to come up with novel algorithms that are theoretically grounded and practical to implement. We also extend (and analyze) RLHF to the multi-turn setting.
3. Theoretically, we prove that our algorithms converge to the Nash equilibrium of the multi-turn setup (while clearly single-turn approaches fail to do so).
4. Empirically, we show that multi-turn approaches beat single-turn baselines.
5. We create a new preference-based multi-turn experimental environment. Since we are not aware of any such an environment, this important contribution gives the community a benchmark to further explore multi-turn alignment algorithms and improve LLMs multi-turn capabilities in the future.

# On (Human) evaluation and Alignment

The ultimate goal of learning from preferences is human alignment, and our multi-turn preference based algorithm is explicitly designed to improve the alignment of LLMs. However, collecting quality human data is a very long and expensive process. This is especially true when one needs to evaluate the difference between long dialogues. While recommended when training real-world systems, in academic settings, it has become standard practice to use a highly capable LLM (Gemini/ChatGPT) as a proxy for human alignment (see DPO, RLAIF, NashMD, IPO). 

Additionally, unlike some of the above works that train on data collected from real human preference but evaluate performance with an LLM as a judge, in our work, the training preference data itself is generated by an LLM. Therefore, the true goal in our curated environment is to align the model with the preference of this highly capable LLM rather than a human rater. 
Following the reviewers’ recommendations, we validated our results using the same Gemini Ultra model used to generate the data, reaching the same conclusions (see below) as with the prompted T5-xxl model used in the paper. This is indeed a more truthful measure for the model’s alignment . We wish to thank the reviewers for helping improve the paper, we will include these new and strong results in the final version.

**Evaluation with a Gemini-Ultra judge**
||SFT|ST RLHF Reward|ST RLHF Value|MT RLHF|MTPO|MTPO-tau|
|:------------------|:-----:|:--------------:|:-------------:|:-------:|:-----:|:--------:|
|SFT|-|0.206|0.286|0.164|0.125|0.086|
|ST RLHF Reward|0.794|-|0.479|0.452|0.447 | 0.277|
|ST RLHF Value|0.814|0.521|-|0.467|0.438|0.320|
|MT RLHF|0.836|0.548|0.533|-|0.419|0.288|
|MTPO|0.875|0.553|0.562|0.581|-|0.305|
|MTPO-tau|0.914|0.723|0.680|0.712|0.695|-|

# On the usage of the t5-large model:
We would like to point the reviewers’ attention to several important points regarding the use of T5-large models:
1. The multi-turn setting is more computationally demanding than single-turn, making the choice of smaller models especially reasonable in the context of an academic paper. Due to the repeated interactions, multi-turn dialogue is a much longer NLG task than common single-turn benchmarks like OpenAI TL;DR, Anthropic-HH, and XSUM, with an overall generation length of 20 times longer. Therefore, while we agree with the reviewers that comparing our algorithm on larger and more capable models is valuable, this was not feasible in this kind of academic research both from time and cost perspectives.
2. Our goal is to compare different algorithmic concepts to validate the benefits of our novel approach, and not to establish SOTA results. Thus, our comparison is valid and fair, as all baselines use the exact same model. While scaling up model sizes provides better performance, this is orthogonal to what our experiments aim to test.
3. Very well known concurrent work with similar experimental goals use the same T5-large models: The papers NashMD, IPO, online IPO, RLAIF, and more, use an even simpler experimental setup and have recently been published in top-tier conferences. This shows that T5 models are regarded as common practice for testing fundamental algorithmic concepts in academic contexts.
4. Per the reviewers request, we are currently running experiments with larger models. We note that these experiments take time to run but initial results on T5-XL (3B, see below) show similar gains for our multi-turn approach, and we will include the final results in the final version.

**Evaluation of T5-XL (3B) using a Gemini-Ultra judge**
||SFT|ST RLHF Reward|MT RLHF|MTPO-tau|
|-------------------|:-----:|:--------------:|:-------:|:--------:|
| SFT |-|0.295|0.101|0.041|
| ST RLHF Reward|0.705|-|0.180|0.069|
| MT RLHF|0.899|0.820|-|0.139|
| MTPO-tau| 0.959 | 0.931| 0.861|-|

* **MTPO-tau L vs. MT RLHF XL:** 0.525

Meta-review: This paper explores preference learning in multi-turn settings (where the reward is only provided after several turns). The authors propose an algorithm with theoretical converge guarantees, and show its effectiveness on a new multi-turn dialogue task.

Reviewers' initial impressions were mixed, with in particular concerns regarding somewhat unconvincing empirical results (limited to very small models, and on a potentially debatable experimental setup). However, the authors provided additional convincing results on "less small" models (and committed to include more later) as well as on an improved experimental setup, which I believe addressed those main concerns (and after the discussion period, all reviewers switched to a rating above the acceptance threshold).

I also want to show appreciation for the theoretical contributions of this work, which may be based off previous work but are still novel w.r.t. their application to the multi-turn setting, which I believe is indeed quite relevant to explore.

As a result, I am recommending acceptance. My request to the authors, though, is to include in the camera-ready the new experiments they promised to include, even if results end up not being as good as hoped.
Decision: Accept (poster)