Multi-turn Reinforcement Learning with Preference Human Feedback

Authors: lior  shani
aviv  rosenberg
oran  lang
daniele  calandriello
avital  zipori
hila  noga
orgad  keller
bilal  piot
idan  szpektor
avinatan  hassidim
yossi  matias
rémi  munos
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-10 11:14:19

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.

Main paper: 
 introduction: 
 A pinnacle of human intelligence is the ability to communicate with an environment, forming complex interactions to 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 et al., 2022 , Anil et al., 2023 , Touvron et al., 2023 , OpenAI, 2024 , Google, 2024] . In order to align these models to human needs, many efforts have been made to train them with a given human feedback. In some concordance with human learning, this is usually achieved by reinforcing behaviors that align with the feedback, using a technique now called Reinforcement Learning from Human Feedback (RLHF; Christiano et al. [2017] , Ziegler et al. [2019] , Stiennon et al. [2020] ).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 a 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 [Stiennon et al., 2020 , Rafailov et al., 2023] , enabling the use of a wide-variety of well-researched ⋆ Equal contribution. 1 Google Research. 2 Google DeepMind. 3 Tel Aviv University.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 potentially 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 AI 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 [Hendrycks et al., 2022] .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 a series of exchanges with an external (stochastic) environment (Section 3). Importantly, we consider (human) feedback that compares entire multi-turn conversations as opposed to single-turn scenarios, which compare individual actions on a per-turn basis. Conversation-level 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, a seller agent asking too high a price may seem immediately bad, but becomes potentially good as part of a 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 a 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., a policy which is preferred over any other policy. We prove similar results for MTPO-τ , a slight variant of MTPO that, similarly to Munos et al. [2023] , uses a geometric mixture policy which interpolates the agent's policy with a fixed reference policy (with mixing rate τ ). These algorithms utilize a new form of preference-based Q-function that accounts for the long-term consequences of individual actions. Finally, leveraging our theoretical framework, we modify this Q-function to create a multi-turn RLHF algorithm and prove its convergence to an optimal policy (w.r.t the learned reward function).We complement our theoretical findings with a policy-gradient version of our multi-turn algorithms for deep learning architectures (Section 4.1). To validate our approach, we apply our algorithms to train a T5 encoder-decoder LLM [Raffel et al., 2020] , aiming to enhance its multi-turn dialogue abilities (Sections 5 and 6). We test our approach in a scenario without explicit rewards, where conversation quality is evaluated solely through preferences. To that end, we create a new environment called Education Dialogue, where a teacher guides a student in learning a random topic, by prompting Gemini [Team et al., 2023] . The conversation is judged based on preference feedback, using a 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 our direct multi-turn preference approach outperforms multi-turn RLHF (Section 6). As an additional contribution, we publicly release the data of Education Dialogue. 1 Finally, we demonstrate that even in a reward-based environment, our preference-based algorithm achieves comparable performance to learning directly from rewards, as in standard RL, despite using a weaker signal. For this experiment, we utilize the LMRL-Gym [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 a 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 et 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 RLHF 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 two like IPO-MD [Calandriello et al., 2024] . Nonetheless, these methods only consider single-turn problems, whereas MTPO provides the first guarantees for multi-turn 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 et al., 2022 , Saha et al., 2023 , Wu and Sun, 2023 , Wang et al., 2023 , Zhan et al., 2023a,b] . 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 a trajectory is revealed to the agent [Efroni et al., 2021 , Cohen et al., 2021 , Chatterji et al., 2021 , Cassel et al., 2024] .Lastly, there is vast literature on using RL to improve natural language generation for dialogue systems. The pioneering work of Li et al. [2016] focuses on designing rewards to capture important dialogue attributes such as semantic coherence and ease of answering. Other works tackle taskoriented dialogue, using RL to enhance the agent's ability to solve the underlying dialogue task [Wei et 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 5 and 6), 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.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 multiturn setting, which is then presented in Section 3; (ii) presenting multi-turn algorithms and proving their convergence, the algorithms are presented and analyzed in Section 4;(ii) demonstrating the multi-turn algorithms are superior empirically, the experiments are detailed in Sections 5 and 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 as long as it is clear that these goals are not attained by the paper. 
preliminaries: 
 The interaction between an AI 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.M is defined by a tuple (C, X , Y, H, x 1 , ρ c , p) where C is the context space, X is the state space, Y is the action space, H is the horizon, x 1 ∈ X is the initial state, ρ c ∈ ∆ C is the context distribution and p ∶ C × X × Y → ∆ X is the transition function such that p(x ′ c, x, y) is the probability to transition to state x ′ after taking action y in state x, given context c.An interaction between the agent and the CMDP environment proceeds in H steps. First, a context c ∈ C is sampled from ρ c , and then the agent begins in the initial state x 1 . In step h ∈ [H], the agent observes the current state x h ∈ X , picks an action y h ∈ Y and transitions to the next state x h+1 sampled from the transition function p(⋅ c, x h , y h ). At the end of the interaction, the agent arrives in a final state x H+1 . For simplicity, we assume that the state space can be decomposed into H + 1 disjoint subsets X = ⊍ H+1 h=1 X h such that, in step h of the interaction, the agent is in some statex h ∈ X h . A policy π ∶ C × X → ∆ Y isa mapping from a context and state to a distribution over actions. Together with transition p, π induces a distribution over trajectories denoted by Pr π,p [⋅] (and E π,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.Unlike standard RL where the agent observes reward feedback for its actions, the influential work of Christiano et al. [2017] suggests to leverage preference data. In the single-turn setting, the agent generates a single sequence y ∈ Y given a context c ∈ C. This is modeled as a 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 × Y × Y → [0, 1] such that P(y ≻ y ′ c) gives the probability that y is preferred over y ′ given context c. Preferences naturally extend to policies via expectationP(π ≻ π ′ c) = E y∼π(⋅ c),y ′ ∼π ′ (⋅ c) [P(y ≻ y ′ c)].Reinforcement Learning from Human Feedback. In RLHF, it is assumed that there is a hidden reward function r ∶ C × Y → R that defines the preferences through the Bradely-Terry (BT) model, i.e., P(y ≻ y ′ c) = σ(r(c, y)r(c, y ′ )), where σ 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 LLMs [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 et al. [2023] propose the Nash-MD algorithm which converges to the Nash equilibrium of a (regularized) preference model, i.e., a policy which is preferred over any other policy. In iteration t + 1, Nash-MD updates its policy π t+1 using a mirror descent (MD) step projected to a geometric mixture policy. The mixture policy π α t (⋅ c) ∝ π t (⋅ c) 1-αηt µ(⋅ c) αηt interpolates between the policy π t and a reference policy µ, given a regularization coefficient α > 0. Formally, for learning rate η t > 0,π t+1 (⋅ c) = arg max π(⋅ c)∈∆ Y η t P(π ≻ π α t c) -KL(π π α t )[c] ∀c ∈ C, where KL(π π ′ )[c] ≜ KL(π(⋅ c) π ′ (⋅ c)) = ∑ y π(y c) log π(y c) π ′ (y c) .3 Multi-turn Preference-Based RLIn the multi-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 preferencebased RL, where the feedback is given as preference instead of reward. However, in our case, we assume preferences are between final CMDP states with a shared initial context. Formally, there exists a preference model P ∶ C × X H+1 × X H+1 → [0, 1] such that P(x H+1 ≻ x ′ H+1 c) gives the probability that x H+1 is preferred over x ′ H+1 given context c. 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 of Munos et al. [2023] that the preference model is symmetric, i.e., P(x ′ H+1 ≻ x H+1 c) = 1 -P(x H+1 ≻ x ′ H+1 c). We define the preference between a final state and a policy byP(x ≻ π c) = E π,p [P(x ≻ x H+1 c)]. Similarly, P(π ≻ π ′ c) = E π,p [P(x H+1 ≻ π ′ c)].For brevity, since contexts are independent, we omit the context throughout the rest of the paper. Similarly to Munos et al. [2023] , our objective is to find a policy π ⋆ which is preferred over any other alternative policy, i.e.,π ⋆ ∈ arg max π min π ′ P(π ≻ π ′ ),which is a Nash equilibrium in the above two-player game defined by the preference model, following the minimax theorem [Von Neumann, 1928] (see Lemma 3.2). 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 as a 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 µ be a reference policy, and define the α-regularized preference model as follows:P α (π ≻ π ′ ) = P(π ≻ π ′ ) -αKL p (π µ) + αKL p (π ′ µ),where KL p (⋅ ⋅) is the KL-divergence between the distributions that the policies induce over trajectories in the CMDP. We prove the following two results for the regularized preference model. First, its KL term has a value difference-like decomposition into the KL-divergences at individual states. Second, it has a unique Nash equilibrium (proofs in Appendix A).Lemma 3.1. Let π, π ′ be two policies, then:KL p (π π ′ ) = E π,p ∑ H h=1 KL(π π ′ )[x h ] . Lemma 3.2.There exists a unique Nash equilibrium of the regularized preference model P α .Trajectory-wise vs. turn-wise preference feedback. A naive adaptation of single-turn RLHF to the multi-turn scenario would treat each turn as a separate single-turn problem. This would require feedback for the preference between two actions in each turn. Instead, in the setting we 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, a chatbot directly answering a 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 a 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 question, and how the chatbot'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-based RL setup (through the CMDP model), our focus is on applying this framework to multi-turn language-based interactions. The action space Y is a sequence of tokens of a vocabulary V, and the state space at step h, X h , is a sequence based on the past sequences. For example, in conversational dialogues, the state x h holds the whole dialogue up to the h-th turn, the action y h is the current sequence generated by the agent, and the next-state is simply the concatenation of the conversation x h with the new y h 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 a summary of results from APIs so far, the action is a new API call or user-facing response, and next state is a 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 formulation also captures the single-turn auto-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 auto-regressive problem by limiting the actions at each step to single vocabulary tokens, Y = V, and assuming a null deterministic environment (x h+1 is the concatenation of x h and y h ). 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 a fundamental concept in RL -the value and Q-functions. In reward-based RL, it is essential to define the value V π ∶ X → R as the expected reward when playing policy π starting in some state x h , i.e.,V π (x h ) = E π,p ∑ H h ′ =h r(x h ′ , y h ′ ) x h .In the preference-based 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.Q π,π ′ α (x h , y h ) = E π,p P(x H+1 ≻ π ′ ) -α H h ′ =h KL(π µ)[x h ′ ] x h , y h , V π,π ′ α (x h ) = E π,p P(x H+1 ≻ π ′ ) -α H h ′ =h KL(π µ)[x h ′ ] x h .There are a few interesting points in the definition above. First, note that these values are functions of two policies π, π ′ . This is because the quality of a policy π cannot be measured on its own, and must be compared to another policy π ′ . Second, while π starts at the state x h , the comparison policy π ′ starts its trajectory from the initial state. This is a 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 a 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 B).Lemma 4.1. Let π, π ′ , π be policies, then the following value difference lemma holds:P α (π ≻ π) -P α (π ′ ≻ π) = E π ′ ,p H h=1 ⟨π -π ′ , Q π,π α ⟩[x h ] + αKL(π ′ µ)[x h ] -αKL(π µ)[x h ] ,where ⟨ππ ′ , Q⟩[x] ≜ ⟨π(⋅ x)π ′ (⋅ x), Q(x, ⋅)⟩ and ⟨x, y⟩ = ∑ i x(i)y(i) is the inner product.MTPO. We present the MTPO (Multi-turn Preference Optimization) algorithm, which provably solves the multi-turn 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., 2023 , 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 (t + 1),EQUATIONwhere η t is a learning rate. The solution can be made explicit in the following form (Appendix E.2):π t+1 (y h x h ) ∝ µ(y h x h ) αηt π t (y h x h ) 1-αηt e ηtQ π t ,π t α (x h ,y h ) .(2)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 Qfunction), 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 π ⋆ α be the Nash equilibrium of the regularized preference model, and Q be a bound on the magnitude of the Q-functions. Then, for η t = 2 α(t+2) , MTPO guarantees at every iteration t,KL p (π ⋆ α π t ) ≤ 32HQ 2 α 2 (t + 1) .Let µ min be the minimal non-zero probability assigned by µ, then Q ≤ max{4αH log 1 µ min , 1}.Proof sketch. By Lemma 3.1, the global KL p (π ⋆ α π t+1 ) can be decomposed to the local KL in each state x h , KL(π ⋆ α π t+1 )[x h ]. Then, we use MD analysis in each state to bound the local KL as:KL(π ⋆ α π t+1 )[x h ] ≤ (1 -η t α)KL(π ⋆ α π t )[x h ] + 2η 2 t Q 2 + η t (⟨π t -π ⋆ α , Q πt,πt α ⟩[x h ] + αKL(π ⋆ α µ)[x h ] -αKL(π t µ)[x h ]),giving a 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 p (π ⋆ α π t ). Importantly, the value difference lemma (Lemma 4.1) aggregates the advantage terms to the global regularized preference P α (π t ≻ π t ) -P α (π ⋆ α ≻ π t ), which is non-positive by the optimality of π ⋆ α . This leaves us with the global recursive bound:KL p (π ⋆ α π t+1 ) ≤ (1 -η t α)KL p (π ⋆ α π t ) + 2η 2 t Q 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 use of the mixture policy π α t (⋅ x) ∝ π t (⋅ x) 1-αηt µ(⋅ x) αηt . This variant, which we call MTPO-τ (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,πt α vs. Qπ α t ,π α t α . π t+1 (⋅ x h ) = arg max π η t ⟨π, Q π α t ,π α t α ⟩[x h ] -KL(π π α t )[x h ].MTPO-τ naturally extends Nash-MD to the multi-turn setting, and reveals that Nash-MD is a self-play algorithm itself, but plays π α t instead of π t . Practically, MTPO has the computational advantage over MTPO-τ (and Nash-MD) of not keeping the additional policy π α t . Moreover, MTPO avoids the difficulty of computing the geometric mixture, which Munos et al. [2023] approximate heuristically via linear interpolation between the logits of the two policies.Multi-turn RLHF. 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, in the case of multi-turn RLHF, we consider the reward function r RLHF learned from preference data using the Bradley-Terry model, and define the corresponding regularized Q-function Q π,RLHF α (x h , y h ) = E π,p r RLHF (x H+1 ) -α ∑ H h ′ =h KL(π µ)[x h ′ ] x h , y h . By replacing Q πt,πt α in Equation (1) with Q πt,RLHF α, we obtain the multi-turn RLHF algorithm that converges to the regular RLHF objective -the optimal regularized policy w.r.t. the reward r RLHF (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 preference-based MTPO uses an adaptive self-play mechanism to compute preferences w.r.t. the current policy.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 conversations from the agent and environment models. To label the data, we prompt a high-capacity LLM with either instructions on how to score a conversation, or criteria for preferring a conversation over another. The data is used to fine-tune two smaller LLMs: an RLHF reward model (with BT loss), and a preference model (with probability regression loss).We experiment with two domains, preference-based Education Dialogue and reward-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) a 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. 1 For more details, see Appendix C and the example in Figure 1 .Table 1 : 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 3 × 3 comparisons matrix and report the mean (the standard deviation is reported in Appendix D). In this LMRL-Gym [Abdulhai et al., 2023] domain, a car dealer is assigned with the task of selling a 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-level signals are preferred over single-turn 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-reward, rates the two responses using a modified preference prompt (see Appendix C), 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-value, assumes access to a Monte-Carlo estimate of the value: it uses our original preference prompt (see Figure 1 ) 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, we use 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/preference models, we make use of the Flan-T5 XL (3B) [Chung et al., 2024] . For training, we use a configuration of 4 × 4 Tensor Processing Units (TPUs; Jouppi et al. [2023] ) which typically yields 0.1 training steps per second, where a step consists of learning a 10-turn episode. A detailed list of hyperparameters is found in Appendix D. We run each evaluation on 1600 random samples from an independent evaluation set.Question: Does the paper discuss the limitations of 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 no 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 a separate "Limitations" 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 on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated. • The authors should reflect on the factors that influence the performance of the approach.For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to 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 fairness. • While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
theory assumptions and proofs: 
 Question: For each theoretical result, does the paper provide the full set of assumptions and a 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 in Appendices A and B. 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 crossreferenced. • All assumptions should be clearly stated or referenced in 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 a short proof sketch to provide intuition. • Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material. • Theorems and Lemmas that the proof relies upon should be properly referenced. 
deep rl implementation: 
 Our deep RL implementation is a natural adaptation of the tabular algorithms presented in the previous section. At each iteration, training data is acquired by sampling a batch of contexts from the data, and using each context to sample two trajectories with the current policy π θt . 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 ( 1) relies on the Q-function of the current policy. We therefore use an actor-critic policy optimization based approach and train two models, a policy π θ , and its value Vπ θ t ,π θ t α,φ, which is typically used to estimate the advantage, [Schulman et al., 2017] . For simplicity and computational efficiency, we implement a policy-gradient (PG) based approach and ignore the MD stability term KL(π θt π θt-1 ), similarly to the implementation 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 similarly to the way the Follow-The-Regularized-Leader (FTRL; Orabona [2019] ) algorithm operates. 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 x,A π,π ′ α (x, y) ≜ Q π,π ′ α (x, y) -V π,π ′ α (x)L policy (θ; x, y) = - Âπ θ t ,π θ t α (x, y) log π θ (y x) + αKL(π θ µ)[x], L value (φ; x) = V π θ t ,π θ t α (x) -V π θ t ,π θ t α,φ (x) 2 , where V π θ t ,π θ t α , Âπ θ t ,π θ t α, are estimations of the current value and advantage using Generalized Advantage Estimation (GAE, Schulman et al. [2017] ). We also batch-normalize the value-loss and advantage as recommended in [Andrychowicz et al., 2020] . Finally, when the policy is an autoregressive language model, which generates actions token-by-token until an end-of-sequence signal is generated, we use a turn-level value (and not a token-level value as done in [Stiennon et al., 2020] ). That is, the value model gets as input a state represented by a 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.Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it 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 5 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 a list of hyperparameters is provided in Appendix D.• The answer NA means that the paper does not include experiments.• If the paper includes experiments, a 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 a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it 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 one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed. • While NeurIPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. 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, confidence 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).• It should be clear whether the error bar is the standard deviation or the standard error of the mean. • It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 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. 
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-art LLMs, similarly to Abdulhai et al. [2023] (see Figure 1 ):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., 2023] 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, to create Prompt: You are an expert at assessing teachers. Here are two interactions between a teacher and a student.A good interaction between a 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.Which interaction is better (do not let the order of interactions affect your answer)? Output 1 or 2.Prompt: Simulate a conversation between a teacher in school and a student. There is a small chance that the teacher is successful in teaching the student so he understands the topic. The conversation lasts roughly 10-15 turns but ends when either side says [end of conversation]. The teacher wants to teach the student about {Topic}. The student likes {Student preference}. The teacher does not know that beforehand. The student prefers to learn this way, {Student reactions}. The teacher likes {Teacher Preference}. He prefers to teach this way, {Teacher reaction}.Output the conversation and the probability that the student understood the material, in the following format. Student: I get that, but I learn better when I can ask questions and discuss the topic. Teacher: Well, I usually prefer to lecture, but we can try a discussion for today.Student: That's interesting! So, how do you know which element has a specific number of proton? Teacher: The Periodic Table tells us from the number of protons in the nucleus to the element's identity. Student: I think I get it now. Thanks for explaining it in a way that I could understand! Teacher: You're welcome. Let's move on to the quiz now.Figure 1 : 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. a diverse set of conversations, we devise a diverse list of attributes for both the agent and environment, sample attributes out of the list, and pass it to the generation prompt. 
experiments: 
 In this section we evaluate the algorithms proposed in Section 4. We start with the preference-based Education Dialogue environment (see Section 5), and compare our multi-turn algorithms to SFT (supervised fine-tuning) as well as single-turn baselines. We note that, unlike single-turn 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 a prompted Flan-T5 XL model as a judge, which was verified to correlate with the high-capacity Gemini Ultra (Table 1 ). We then compare our best candidates using the same Gemini Ultra which generated the preference alignment feedback (Table 2 ). Multi vs. single turn. Tables 1 and 2 show that all multi-turn algorithms (MTPO and multiturn RLHF) with conversation-level feedback significantly outperform the single-turn baselines, validating our hypothesis. We conjecture that it is attributed to several factors: First, the effect of a single-decision on the whole conversation is hard to capture, causing highly inaccurate single-turn reward/preference models. Notably, this leads to inferior performance of Nash-MD compared to single-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 value, this estimate becomes biased when the policy changes during training. Finally, single-turn 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-based Q-function Q πt,πt α (see Section 4).MTPO vs. multi-turn RLHF. 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 is not reward-based, and hence it extends the results of [Munos et al., 2023 , Calandriello et al., 2024] 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-τ outperforms MTPO. While both algorithms converge to the same Nash equilibrium, we conjecture that the superior performance of MTPO-τ stems from the stochasticity that the mixture policy π α t introduces. Namely, π t might tend towards deterministic behavior, causing less informative feedback from self-play, as the two sampled trajectories would be very similar. On the other hand, π α t is more stochastic, providing diversity in the sampled trajectories. Reward-based environment. In an additional experiment, we test MTPO and multi-turn RLHF in the reward-based Car Dealer environment, where the goal is maximizing sale price (see Section 5). We compare a standard policy-gradient RL algorithm against our algorithms in two scenarios: an online scenario where the reward or preference feedback is given using an online oracle, and an RLHF-like setting, where we first create preference data using the oracle, and then use it to fine-tune a (BT) reward and preference models. Table 3 shows that even though MTPO receives preferences instead of the explicit optimization target (rewards), it still learns as good as RL. Interestingly, MTPO recovers a 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.Limitations. This work presents a 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-art models and algorithms, and more realistic environments to future work.A.1 KL decomposition (proof of Lemma 3.1) Lemma (restatement of Lemma 3.1). Let π, π ′ be two policies, then:KL p (π π ′ ) = E π,p H h=1 KL(π π ′ )[x h ] .Proof. KL p (⋅ ⋅) is defined as the KL-divergence between the distributions that the policies induce over trajectories in the MDP (denoted by τ = (x 1 , y 1 , . . . , x H , y H , x H+1 ), formally:KL p (π π ′ ) = τ Pr π,p [τ ] log Pr π,p [τ ] Pr π ′ ,p [τ ] = τ Pr π,p [τ ] log ∏ H h=1 π(y h x h )p(x h+1 x h , y h ) ∏ H h=1 π ′ (y h x h )p(x h+1 x h , y h ) = τ Pr π,p [τ ] log H h=1 π(y h x h ) π ′ (y h x h ) = E π,p log H h=1 π(y h x h ) π ′ (y h x h ) = E π,p H h=1 log π(y h x h ) π ′ (y h x h ) = E π,p H h=1 KL(π(⋅ x h ) π ′ (⋅ x h )) .A.2 Existence and uniqueness of the Nash equilibrium (proof of Lemma 3.2)Lemma (restatement of Lemma 3.2). There exists a unique Nash equilibrium of the regularized preference model P α .Proof. The existence of the Nash equilibrium is proved in Theorem A.1. In order to prove the uniqueness, we use the fact that, from Theorem 4.2, the algorithm MTPO produces a sequence of policies π t that converges to any Nash equilibrium π * , in the sense that lim t→∞ KL p (π * π t ) = 0.From the definition of the KL-divergence between policies, we haveKL p (π * π t ) = E π * ,p H h=1 KL(π * π t )[x h ] = x∈X ρ π * (x)KL(π * π t )[x],where ρ π * (x) is the probability to reach x when following π * . Now, the fixed point of the MTPO dynamics (Equation ( 2)) shows that any Nash equilibrium satisfies, for any x ∈ X, y ∈ Y, y) .π * (y x) ∝ µ(y x)e 1 α Q π * ,π * α (x,In particular, we notice that any Nash equilibrium has the same support as µ, thus the set of reachable states under µ is exactly the same set as the set of reachable states under any Nash equilibrium π * .So, from any reachable state x ∈ X (i.e., such that ρ µ (x) > 0), we have that the sequence π t (⋅ x) converges (in KL-divergence) to the Nash equilibrium π * (⋅ x). Since a single sequence cannot converge to two different values, we have that the Nash equilibrium π * (⋅ x) is uniquely defined in that state. Since the behavior generated by a policy depends on the policy at 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 a Nash equilibrium.Theorem A.1. The game defined by the payoff function (π, π ′ ) ↦ P α (π ≻ π ′ ) has a Nash equilibrium.Proof. First we prove that there exists (at least) one max-min policy π * ∈ arg max π min π ′ P α (π ≻ π ′ ).For any π, the map π ′ ∈ X ↦ P α (π ≻ π ′ ) 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 π ∈ Π ↦ min π ′ P α (π ≻ π ′ ) is also u.s.c. and since Π is compact, we can apply Theorem 2.43 of Aliprantis and Border [2006] to deduce that this function attains a maximum value in Π and that the set of maximizers is compact. Thus there exists (at least) one policy denoted by π * ∈ arg max π∈Π min π ′ ∈Π P α (π ≻ π ′ ).Now from Lemma A.2 we know that the regularized preference model P α (π ≻ π ′ ) defines a concaveconvexlike game. Also for any π ′ , the map π ↦ P α (π ≻ π ′ ) is u.s.c. Thus we can apply the minimax Theorem 4.2 of Sion [1958] to deduce thatmax π min π ′ P α (π ≻ π ′ ) = min π ′ max π P α (π ≻ π ′ ).We deduce from1 2 = max π P α (π ≻ π) ≥ max π min π ′ P α (π ≻ π ′ ) = min π ′ max π P α (π ≻ π ′ ) ≥ min π ′ P α (π ′ ≻ π ′ ) = 1 2 ,that the value of the game is 1 2, and that min π ′ P α (π * ≻ π ′ ) = 1 2. Thus (π * , π * ) is a Nash equilibrium of the game defined by the regularized preference model (π, π ′ ) ↦ P α (π ≻ π ′ ).Lemma A.2. The mapping (π, π ′ ) ↦ P α (π ≻ π ′ ) is concave-convexlike, which, in the context of a symmetric preference model, means that for any couple of policies (π 1 , π 2 ) and any coefficient c ∈ [0, 1], there exists a policy π c such that for any policy π ′ , we havecP α (π 1 ≻ π ′ ) + (1 -c)P α (π 2 ≻ π ′ ) ≤ P α (π c ≻ π ′ ).Proof. Let us define the notion of reach probability: for any state x h ∈ X h , let us write ρ π (x h ) the probability to reach the specific state x h ∈ X h when following π:ρ π (x h ) = Pr π,p [x h ].First notice we can represent the regularized preference P α (π ≻ π ′ ) using reach probabilities:P α (π ≻ π ′ ) = x H+1 ,x ′ H+1 ∈X H+1 ρ π (x H+1 )ρ π ′ (x ′ H+1 )P(x H+1 ≻ x ′ H+1 ) -α H h=1 x h ∈X h ρ π (x h )KL(π µ)[x h ] -ρ π ′ (x h )KL(π ′ µ)[x h ].Now, consider two policies π 1 and π 2 and a coefficient c ∈ [0, 1]. From Lemma A.3 we have that there exists a policy π c such that for any x h , we have ρ πc (x h ) = cρ π1 (x h ) + (1c)ρ π2 (x h ). We can writeP α (π c ≻ π ′ ) = x H+1 ,x ′ H+1 ∈X H+1 [cρ π1 (x H+1 ) + (1 -c)ρ π2 (x H+1 )] ρ π ′ (x ′ H+1 )P(x H+1 ≻ x ′ H+1 ) -α H h=1 x h ∈X h [cρ π1 (x h ) + (1 -c)ρ π2 (x h )] KL(π c µ)[x h ] + α H h=1 x h ∈X h ρ π ′ (x h )KL(π ′ µ)[x h ] = cP(π 1 ≻ π ′ ) + (1 -c)P(π 2 ≻ π ′ ) -α H h=1 x h ∈X h [cρ π1 (x h ) + (1 -c)ρ π2 (x h )] KL(π c µ)[x h ] + α H h=1 x h ∈X h ρ π ′ (x h )KL(π ′ µ)[x h ].Now from the convexity of π ↦ KL(π µ)[x h ], and the definition of π c , we have thatρ πc (x h )KL(π c µ)[x h ] = [cρ π1 (x h ) + (1 -c)ρ π2 (x h )] KL(π c µ)[x h ] ≤ cρ π1 (x h )KL(π 1 µ)[x h ] + (1 -c)ρ π2 (x h )KL(π 2 µ)[x h ]. Thus P α (π c ≻ π ′ ) ≥ cP(π 1 ≻ π ′ ) + (1 -c)P(π 2 ≻ π ′ ) -α H h=1 x h ∈X h cρ π1 (x h )KL(π 1 µ)[x h ] + (1 -c)ρ π2 (x h )KL(π 2 µ)[x h ] + α H h=1 x h ∈X h cρ π ′ (x h )KL(π ′ µ)[x h ] + (1 -c)ρ π ′ (x h )KL(π ′ µ)[x h ] = cP α (π 1 ≻ π ′ ) + (1 -c)P α (π 2 ≻ π ′ ).Lemma A.3. For any state x h ∈ X h , let us write ρ π (x h ) the probability to reach the specific statex h ∈ X h when following π, i.e., ρ π (x h ) = Pr π,p [x h ].Then, for any two policies (π 1 , π 2 ) and any coefficient c ∈ [0, 1], there exists a policy π c such that for any h = 1, . . . , H + 1, and any x h ∈ X h , we haveρ πc (x h ) = cρ π1 (x h ) + (1 -c)ρ π2 (x h ).Proof. Let us define π c as a function of π 1 , π 2 , and c: for any x ∈ X , y ∈ Y,π c (y x) = cρ π1 (x)π 1 (y x) + (1 -c)ρ π2 (x)π 2 (y x) cρ π1 (x) + (1 -c)ρ π2 (x) .We now prove the lemma by induction on h. It holds for h = 1 since we haveρ πc (x 1 ) = 1 = c + (1 -c) = cρ π1 (x 1 ) + (1 -c)ρ π2 (x 1 ).Now assume the claim holds for any x h ∈ X h , then for any x h+1 ∈ X h+1 ,ρ πc (x h+1 ) = x h ∈X h ρ πc (x h ) y h ∈Y h p(x h+1 x h , y h )π c (y h x h ) = x h ∈X h ρ πc (x h ) y h ∈Y h p(x h+1 x h , y h ) cρ π1 (x h )π 1 (y h x h ) + (1 -c)ρ π2 (x h )π 2 (y h x h ) cρ π1 (x h ) + (1 -c)ρ π2 (x h ) = x h ∈X h ρ πc (x h ) y h ∈Y h p(x h+1 x h , y h ) cρ π1 (x h )π 1 (y h x h ) + (1 -c)ρ π2 (x h )π 2 (y h x h ) ρ πc (x h ) = x h ∈X h y h ∈Y h p(x h+1 x h , y h ) [cρ π1 (x h )π 1 (y h x h ) + (1 -c)ρ π2 (x h )π 2 (y h x h )] = cρ π1 (x h+1 ) + (1 -c)ρ π2 (x h+1 ),where the third inequality is by the induction hypothesis.B Proofs for section 4B.1 Regularized preference-based Q-function (proof of Lemma 4.1) Lemma (restatement of Lemma 4.1). Let π, π ′ be two policies. For every x H+1 ∈ X H+1 , it holds that V π,π ′ α (x H+1 ) = P(x H+1 ≻ π ′ ). Furthermore, for every h ∈ [H] the following recursive relations hold:V π,π ′ α (x h ) = E y h ∼π(⋅ x h ) Q π,π ′ α (x h , y h ), Q π,π ′ α (x h , y h ) = E x h+1 ∼p(⋅ x h ,y h ) V π,π ′ α (x h+1 ) -αKL(π µ)[x h ].Moreover, let π be a third policy, then the following value difference lemma holds:P α (π ≻ π) -P α (π ′ ≻ π) = E π ′ ,p H h=1 ⟨π -π ′ , Q π,π α ⟩[x h ] + αKL(π ′ µ)[x h ] -αKL(π µ)[x h ] .Proof. We prove the lemma by casting the preference-based RL problem as an adversarial MDP, see Appendix E for the details. Set r t (x H+1 ) = P(xH+1 ≻ π ′ ), then Q π,π ′ α = Q π,t α (see Definition E.3 for the definition of the regularized Q-function). Now the lemma follows directly from Lemmas E.4 and E.5.Theorem (restatement of Theorem 4.2). Let π ⋆ α be the Nash equilibrium of the regularized preference model P α . Then, for the choice η t = 2 α(t+2) , MTPO guarantees at every iteration t thatKL p (π ⋆ α π t ) ≤ 32HQ 2 α 2 (t + 1) ,where Q is a bound on the magnitude of the Q-functions.Proof. The theorem follows directly from Theorem B.1.Theorem B.1. Running the MTPO algorithm, we have that at every iteration t:KL p (π ⋆ α π t+1 ) ≤ (1 -η t α)KL p (π ⋆ α π t ) + 2η 2 t E π ⋆ α ,p ⎡ ⎢ ⎢ ⎢ ⎢ ⎣ H h=1 Q πt,πt α (x h , ⋅) -α log π t (⋅ x h ) µ(⋅ x h ) 2 ∞ ⎤ ⎥ ⎥ ⎥ ⎥ ⎦ .Thus, for the choice η t = 2 α(t+2) we haveKL p (π ⋆ α π t ) ≤ 8 α 2 (t + 1) ⋅ max t E π ⋆ α ,p ⎡ ⎢ ⎢ ⎢ ⎢ ⎣ H h=1 Q πt,πt α (x h , ⋅) -α log π t (⋅ x h ) µ(⋅ x h ) 2 ∞ ⎤ ⎥ ⎥ ⎥ ⎥ ⎦ . Finally, KL p (π ⋆ α π t ) ≤ 32H t + 1 ⋅ max 1 α 2 , H 2 log 2 µ min, where µ min = min (x,y)∈X ×Y∶µ(y x)>0 µ(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 E for the details. Set r t (x H+1 ) = P(x H+1 ≻ π t ), then Q πt,πt α = Q πt,t α (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 π = π ⋆ α ,KL p (π ⋆ α π t+1 ) ≤ (1 -η t α)KL p (π ⋆ α π t ) + 2η 2 t E π ⋆ α ,p ⎡ ⎢ ⎢ ⎢ ⎢ ⎣ H h=1 Q πt,πt α (x h , ⋅) -α log π t (⋅ x h ) µ(⋅ x h ) 2 ∞ ⎤ ⎥ ⎥ ⎥ ⎥ ⎦ + η t (P α (π t ≻ π t ) -P α (π ⋆ α ≻ π t )) ≤ (1 -η t α)KL p (π ⋆ α π t ) + 2η 2 t E π ⋆ α ,p ⎡ ⎢ ⎢ ⎢ ⎢ ⎣ H h=1 Q πt,πt α (x h , ⋅) -α log π t (⋅ x h ) µ(⋅ x h ) 2 ∞ ⎤ ⎥ ⎥ ⎥ ⎥ ⎦, where the second inequality optimality of π ⋆ α . The last claim follows directly from Lemma E.8. Similarly to Nash-MD Munos et al. [2023] , this is the Nash-equilibrium of regularized preference model, P α , following the minimax theorem [Von Neumann, 1928] Inspired by Nash-MD, we present a variant of MTPO which makes use of the mixture policy π α t , which we call MTPO-τ . Define the regularized policy π α t as a geometric mixture between the current policy π t and the reference policy µ:π α t (y x) = π t (y x) 1-ηtα µ(y x) ηtα ∑ y ′ ∈Y π t (y ′ x) 1-ηtα µ(y ′ x) ηtα .The MTPO-τ update rule is then:π t+1 (⋅ x h ) = arg max π η t ⟨π, Q π α t ,π α t α ⟩[x h ] -KL(π π α t )[x h ] ∀h ∈ [H], x h ∈ X h .where KL(⋅ ⋅) is the standard KL-divergence. It is well-known that his optimization problem has the following explicit closed-form:π t+1 (y h x h ) = π α t (y h x h )e ηtQ π α t ,π α t α (x h ,y h ) ∑ y ′ h ∈Y π α t (y ′ h x h )e ηtQ π α t ,π α t α (x h ,y ′ h ) ∀h ∈ [H], x h ∈ X h , y h ∈ Y.Next, we show that MTPO-τ converges to the Nash equilibrium of the α-regularized preference model. Theorem B.2. Let π ⋆ α be the Nash equilibrium of the regularized preference model P α . Then, for the choice η t = 2 α(t+2) , MTPO-τ guarantees at every iteration t thatKL p (π ⋆ α π α t ) ≤ 9HQ 2 α 2 (t + 1) ,where Q is 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-τ algorithm, we have that at every iteration t:KL p (π ⋆ α π t+1 ) ≤ (1 -η t α)KL p (π ⋆ α π t ) + 2η 2 t E π ⋆ α ,p H h=1 Q π α t ,π α t α (x h , ⋅) 2 ∞ .Thus, for the choice η t = 2 α(t+2) we haveKL p (π ⋆ α π t ) ≤ 8 α 2 (t + 1) ⋅ max t E π ⋆ α ,p H h=1 Q π α t ,π α t α (x h , ⋅) 2 ∞ . Finally, KL p (π ⋆ α π t ) ≤ 8H t + 1 ⋅ max 1 α 2 , H 2 log 2 µ min .Proof. We prove the theorem by casting the preference-based RL problem as an adversarial MDP, see Appendix E for the details. Set r t (x H+1 ) = P(x H+1 ≻ π α t ), then Qπ α t ,π α t α = Q π α t ,t α(see Definition E.3 for the definition of the regularized Q-function). Now, Nash-MD is equivalent to running mixture mirror descent policy optimization. Thus, by Lemma E.7 with π = π ⋆ α ,KL p (π ⋆ α π t+1 ) ≤ (1 -η t α)KL p (π ⋆ α π t ) + 2η 2 t E π ⋆ α ,p H h=1 Q π α t ,π α t α (x h , ⋅) 2 ∞ + η t (P α (π α t ≻ π α t ) -P α (π ⋆ α ≻ π α t )) ≤ (1 -η t α)KL p (π ⋆ α π t ) + 2η 2 t E π ⋆ α ,p H h=1 Q π α t ,π α t α (x h , ⋅) 2 ∞ ,where the second inequality optimality of π ⋆ α . The last claim follows directly from Lemma E.9.Corollary B.4. Running the MTPO-τ algorithm, we have that at every iteration t:KL p (π ⋆ α π α t ) ≤ (1 -η t α)KL p (π ⋆ α π t ) + η t 2 .Thus, for the choice η t = 2 α(t+2) we haveKL p (π ⋆ α π α t ) ≤ 9H t + 1 ⋅ max 1 α 2 , H 2 log 2 µ min .Proof. By Munos et al. [2023, Lemma 1] , for everyx h ∈ X h , KL(π ⋆ α π α t )[x h ] ≤ (1 -η t α)KL(π ⋆ α π t )[x h ] + η t αKL(π ⋆ α µ)[x h ].We finish the proof by taking the expectation E π ⋆ α ,p [⋅] and using Lemmas 3.1 and B.5. The second part is by Theorem B.3.Lemma B.5. It holds that KL p (π ⋆ α µ) ≤ 1 2α .Proof. By the optimality of π ⋆ α we have thatP α (π ⋆ α ≻ µ) ≥ P α (π ⋆ α ≻ π ⋆ α ). Now, since P α (π ⋆ α ≻ π ⋆ α ) = 1 2, we get αKL p (π ⋆ α µ) ≤ P(π ⋆ α ≻ µ) - 1 2 ≤ 1 - 1 2 = 1 2 . B.4 Convergence of multi-turn RLHF Theorem B.6. Let π ⋆,RLHF α (⋅ x) = arg max π V π,RLHF α (x)for every x ∈ X . Then, for the choice η t = 2 α(t+2) , multi-turn RLHF guarantees at every iteration t, KL p (π ⋆,RLHFα π t ) ≤ 32HQ 2 α 2 (t+1) .Proof. The theorem follows directly from Theorem B.7.Theorem B.7. Running the multi-turn RLHF algorithm, we have that at every iteration t:KL p (π ⋆,RLHF α π t+1 ) ≤ (1 -η t α)KL p (π ⋆ α π t ) + 2η 2 t E π ⋆,RLHF α ,p ⎡ ⎢ ⎢ ⎢ ⎢ ⎣ H h=1 Q πt,πt α (x h , ⋅) -α log π t (⋅ x h ) µ(⋅ x h ) 2 ∞ ⎤ ⎥ ⎥ ⎥ ⎥ ⎦ .Thus, for the choice η t = 2 α(t+2) we haveKL p (π ⋆,RLHF α π t ) ≤ 8 α 2 (t + 1) ⋅ max t E π ⋆,RLHF α ,p ⎡ ⎢ ⎢ ⎢ ⎢ ⎣ H h=1 Q πt,πt α (x h , ⋅) -α log π t (⋅ x h ) µ(⋅ x h ) 2 ∞ ⎤ ⎥ ⎥ ⎥ ⎥ ⎦ . Finally, KL p (π ⋆,RLHF α π t ) ≤ 32H t + 1 ⋅ max 1 α 2 , H 2 log 2 µ min, where µ min = min (x,y)∈X ×Y∶µ(y x)>0 µ(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, see Appendix E for the details. Set r t (x H+1 ) = r RLHF (x H+1 ), then Q πt,RLHF α = Q πt,t α (see Definition 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 E.6 withπ = π ⋆,RLHF α , KL p (π ⋆,RLHF α π t+1 ) ≤ (1 -η t α)KL p (π ⋆,RLHF α π t ) + 2η 2 t E π ⋆,RLHF α ,p ⎡ ⎢ ⎢ ⎢ ⎢ ⎣ H h=1 Q πt,πt α (x h , ⋅) -α log π t (⋅ x h ) µ(⋅ x h ) 2 ∞ ⎤ ⎥ ⎥ ⎥ ⎥ ⎦ + η t V πt,RLHF α (x 1 ) -V π ⋆,RLHF α ,RLHF α (x 1 ) ≤ (1 -η t α)KL p (π ⋆ α π t ) + 2η 2 t E π ⋆ α ,p ⎡ ⎢ ⎢ ⎢ ⎢ ⎣ H h=1 Q πt,πt α (x h , ⋅) -α log π t (⋅ x h ) µ(⋅ x h ) 2 ∞ ⎤ ⎥ ⎥ ⎥ ⎥ ⎦, where the second inequality optimality of π ⋆,RLHF α . The last claim follows directly from Lemma E.8.We use the following prompt to generate conversations using Gemini [Google, 2024] :Simulate a conversation between a teacher in school and a student. There is a small chance that the teacher is successful in teaching the student so he understands the topic. The student's reactions to not learning in their preferred ways (student_reaction) 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_pref) are sampled from the following list: direct instruction/lecture-based learning, interactive learning/class discussions/inquiry-based learning, experiential learning/hands-on activities, formative assessment The teacher's reactions to different learning methods (teacher_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 a teacher and a student. # Interaction 1: {conv1} # Interaction 2: {conv2} # A good interaction between a 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. Which interaction is better (do not let the order interactions affect your answer)? Output 1 or 2.For the single-turn baseline, we use the following modified prompt to query Gemini for preferences:You are an expert at assesing teachers. Here is an interaction between a teacher and a student. # Interaction: {conv} # Here are two possible responses by the teacher: # Response 1: {resp1} # Response 2: {resp2} # A good interaction between a 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 one of these responses, which response will lead to a better interaction (do not let the order interactions affect your answer)? Output 1 or 2. D Hyperparameters and additional experimental resultsFor both RLHF-based and preference-based algorithms we conducted a sweep over the KL regularization coefficient α ∈ {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 τ ∈ {0, 0.0375, 0.0625, 0.125}. All models are trained for 50000 steps. 1 ): 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 3 × 3 comparisons matrix and report the mean (together with the standard deviation). We start by defining the regularized adversarial MDP model.Consider a setting where the agent interacts with an MDP model for T episodes, such that, in each episode t ∈ [T ], the agent performs H steps in the MDP (from horizon h = 1 up to horizon h = H + 1) In short, an adversarial MDP is a generalization of this standard episodic MDP setting to the scenario where the reward function is different in every episode. This model was extensively studied in recent years (see, e.g., Even-Dar et al. [2009] , Rosenberg and Mansour [2019b,a] , Shani et al. [2020b] ). We consider a slightly different definition which is more focused on our setting.Definition E.1 (Adversarial MDP). A finite-horizon adversarial MDP M is defined by a tuple (X , Y, H, x 1 , p, {r t } T t=1 ) where X is the state space, Y is the action space, H is the horizon, x 1 ∈ X 1 is the initial state, p ∶ X × Y → ∆ X is the transition function, and r t ∶ X H+1 → [0, 1] is the reward function in episode t.An interaction between the agent and the adversarial MDP environment proceeds in T episodes, and each episode t ∈ [T ] proceeds in H steps. The agent begins in an initial state x t 1 = x 1 . In step h ∈ [H], the agent observes the current state x t h ∈ X , picks an action y t h ∈ Y and transitions to the next state x t h+1 sampled from the transition function p(⋅ x t h , y t h ). At the end of the interaction, the agent arrives in a final state x t H+1 and observes the reward r t (x t H+1 ). For simplicity, we assume that the state space can be decomposed into H + 1 disjoint subsets X = ⊍ H+1 h=1 X h such that, in step h of the interaction, the agent is in some state x h ∈ X h . Now, we define the value function in an adversarial MDP, i.e., the expected reward of a policy when interacting with the MDP.∶ X → ∆ Y be a policy. The value function V π,t ∶ X → R of policy π in episode t is defined as V π,t (x h ) = E π,p [r t (x H+1 ) x h ] for every h ∈ [H] and x h ∈ X h . Similarly, the Q-function Q π,t ∶ X ×Y → R is defined Q π,t (x h , y h ) = E π,p [r t (x H+1 ) x h , y h ].Next, we consider a regularized version of the adversarial MDP model. Regularized MDPs were 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 µ be a reference policy and α > 0 be a regularization coefficient. The regularized value function and Q-function of policy π in episode t are defined asV π,t α (x h ) = E π,p r t (x H+1 ) - H h ′ =h KL(π µ)[x h ] x h Q π,t α (x h , y h ) = E π,p r t (x H+1 ) - H h ′ =h KL(π µ)[x h ] x h , y h .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 π be a policy. For every x H+1 ∈ X H+1 , it holds that V π,t α (x H+1 ) = r t (x H+1 ). Furthermore, for every h = 1, . . . , H and (x h , y h ) ∈ X h × Y, the following recursive relations hold:V π,t α (x h ) = y h ∈Y π(y h x h )Q π,t α (x h , y h ) Q π,t α (x h , y h ) = x h+1 ∈X h+1 p(x h+1 x h , y h )V π,t α (x h+1 ) -αKL(π µ)[x h ].Proof. We prove the claim by backwards induction on h. The base case h = H + 1 follows by definition of the value function and the adversarial MDP. Assuming that the claim holds for h + 1, we have that:V π,t α (x h ) = E π,p r t (x H+1 ) -α H h ′ =h KL(π µ)[x h ′ ] x h = x∈X H+1 Pr π,p [x H+1 = x x h ]r t (x) -α H h ′ =h x∈X h ′ Pr π,p [x h ′ = x x h ]KL(π µ)[x] = y h ∈Y π(y h x h ) x∈X H+1 Pr π,p [x H+1 = x x h , y h ]r t (x) -α y h ∈Y π(y h x h ) H h ′ =h x∈X h ′ Pr π,p [x h ′ = x x h , y h ]KL(π µ)[x] = y h ∈Y π(y h x h )E π,p r t (x H+1 ) -α H h ′ =h KL(π µ)[x h ′ ] x h , y h = y h ∈Y π(y h x h )Q π,t α (x h , y h ).Moreover,Q π,t α (x h , y h ) = E π,p r t (x H+1 ) -α H h ′ =h KL(π µ)[x h ′ ] x h , y h = x∈X H+1 Pr π,p [x H+1 = x x h , y h ]r t (x) -α H h ′ =h x∈X h ′ Pr π,p [x h ′ = x x h , y h ]KL(π µ)[x] = x h+1 ∈X h+1 p(x h+1 x h , y h ) x∈X H+1 Pr π,p [x H+1 = x x h+1 ]r t (x) -α x h+1 ∈X h+1 p(x h+1 x h , y h ) H h ′ =h+1 x∈X h ′ Pr π,p [x h ′ = x x h+1 ]KL(π µ)[x] -αKL(π µ)[x h ] = x h+1 ∈X h+1 p(x h+1 x h , y h )E π,p r t (x H+1 ) -α H h ′ =h+1 KL(π µ)[x h ′ ] x h+1 -αKL(π µ)[x h ] = x h+1 ∈X h+1 p(x h+1 x h , y h )V π,π ′ α (x h+1 ) -αKL(π µ)[x h ].Lemma E.5 (Regularized Value Difference Lemma). Let π, π ′ be two policies. Then,V π,t α (x 1 ) -V π ′ ,t α (x 1 ) = E π ′ ,p H h=1 ⟨π -π ′ , Q π,t α ⟩[x h ] + αKL(π ′ µ)[x h ] -αKL(π µ)[x h ] . Proof. Let x h ∈ X h . First, by Lemma E.5, V π,t α (x h )-V π ′ ,t α (x h ) = = ⟨π, Q π,t α ⟩[x h ] -⟨π ′ , Q π ′ ,t α ⟩[x h ] = ⟨π -π ′ , Q π,t α ⟩[x h ] + ⟨π ′ , Q π,t α -Q π ′ ,t α ⟩[x h ] = ⟨π -π ′ , Q π,t α ⟩[x h ] + αKL(π ′ µ)[x h ] -αKL(π µ)[x h ] + y h ∈Y x h+1 ∈X h+1 π ′ (y h x h )p(x h+1 x h , y h ) V π,t α (x h+1 ) -V π ′ ,t α (x h+1 ) .Note that for h = H + 1 for any π, x H+1 we have V π,t α (x H+1 ) = r t (x H+1 ). By recursively unrolling the above relation, we getV π,t α (x h ) -V π ′ ,t α (x h ) = E π ′ ,p H h ′ =h ⟨π -π ′ , Q π,t α ⟩[x h ′ ] x h + αE π ′ ,p H h ′ =h KL(π ′ µ)[x h ′ ] -KL(π µ)[x h ′ ] x h .Taking the expectation over the initial state finishes the proof.We define the following mirror descent policy optimization algorithm. In the first episode the algorithm plays the reference policy, i.e., π 1 = µ. Then, its update rule for iteration (t + 1) is as follows:EQUATIONwhere η t is a learning rate. The solution can also be made explicit in the following form:EQUATIONTo show this, note that by the definition of the KL, we can write this update rule differently:π t+1 (⋅ x h ) = arg max π η t y h ∈Y π(y h x h ) Q πt,t α (x h , y h ) -α log π t (y h x h ) µ(y h x h ) -KL(π π t )[x h ].This is exactly the MD step for policy optimization [Orabona, 2019 , Shani et al., 2020a] . Thus, the solution in its explicit form is:π t+1 (y h x h ) ∝ π t (y h x h )e ηt Q π t ,t α (x h ,y h )-α log π t (y h x h ) µ(y h x h ) .We recover Equation ( 4) by noticing that exp -αη t log πt(y h x h ) µ(y h x h ) = π t (y h x h ) -αηt µ(y h x h ) αηt .Lemma E.6 (Fundamental inequality of mirror descent policy optimization for regularized adversarial MDPs). The following holds when running mirror descent policy optimization (Equation (3)) in a regularized adversarial MDP, for every policy π and every episode t,KL p (π π t+1 ) ≤ (1 -η t α)KL p (π π t ) + 2η 2 t E π,p ⎡ ⎢ ⎢ ⎢ ⎢ ⎣ H h=1 Q πt,t α (x h , ⋅) -α log π t (⋅ x h ) µ(⋅ x h ) 2 ∞ ⎤ ⎥ ⎥ ⎥ ⎥ ⎦ + η t V πt,t α (x 1 ) -V π,t α (x 1 ) .Proof. Fix a state x h ∈ X h . We start by applying Munos et al. [2023, Lemma 2] with π + = π t+1 , π -= π t and the vector δ(y) = η t Q πt,t α (x h , y)α log πt(y x h ) µ(y x h ) . This implies that for any policy π,KL(π π t+1 )[x h ] ≤ KL(π π t )[x h ] + 2η 2 t Q πt,t α (x h , ⋅) -α log π t (⋅ x h ) µ(⋅ x h ) 2 ∞ + η t ⟨π t (⋅ x h ) -π(⋅ x h ), Q πt,t α (x h , ⋅) -α log π t (⋅ x h ) µ(⋅ x h ) ⟩.Next, we plug this into Lemma 3.1 to obtainKL p (π π t+1 ) = E π,p H h=1 KL(π π t+1 )[x h ] ≤ E π,p H h=1 KL(π π t )[x h ] + 2η 2 t E π,p ⎡ ⎢ ⎢ ⎢ ⎢ ⎣ H h=1 Q πt,t α (x h , ⋅) -α log π t (⋅ x h ) µ(⋅ x h ) 2 ∞ ⎤ ⎥ ⎥ ⎥ ⎥ ⎦ + η t E π,p H h=1 ⟨π t (⋅ x h ) -π(⋅ x h ), Q πt,t α (x h , ⋅) -α log π t (⋅ x h ) µ(⋅ x h ) ⟩ .Note that⟨π t (⋅ x h ) -π(⋅ x h ), log π t (⋅ x h ) µ(⋅ x h ) ⟩ = = KL(π t µ)[x h ] -⟨π(⋅ x h ), log π t (⋅ x h ) µ(⋅ x h ) ⟩ = KL(π t µ)[x h ] -⟨π(⋅ x h ), log π t (⋅ x h ) µ(⋅ x h ) ⟩ + KL(π µ)[x h ] -KL(π µ)[x h ] = KL(π t µ)[x h ] + KL(π π t )[x h ] -KL(π µ)[x h ],where the last relation follows simply because:KL(π µ)[x h ]-⟨π(⋅ x h ), log π t (⋅ x h ) µ(⋅ x h ) ⟩ = = y h ∈Y π(y h x h ) log π(y h x h ) µ(y h x h ) -log π t (y h x h ) µ(y h x h ) = y h ∈Y π(y h x h ) log π(y h x h ) π t (y h x h ) = KL(π π t )[x h ].Thus, we getKL p (π π t+1 ) ≤ E π,p H h=1 KL(π π t )[x h ] + 2η 2 t E π,p ⎡ ⎢ ⎢ ⎢ ⎢ ⎣ H h=1 Q πt,t α (x h , ⋅) -α log π t (⋅ x h ) µ(⋅ x h ) 2 ∞ ⎤ ⎥ ⎥ ⎥ ⎥ ⎦ + η t E π,p H h=1 ⟨π t -π, Q πt,t α ⟩[x h ] -η t αE π,p H h=1 KL(π t µ)[x h ] + KL(π π t )[x h ] -KL(π µ)[x h ] = (1 -η t α)E π,p H h=1 KL(π π t )[x h ] + 2η 2 t E π,p ⎡ ⎢ ⎢ ⎢ ⎢ ⎣ H h=1 Q πt,t α (x h , ⋅) -α log π t (⋅ x h ) µ(⋅ x h ) 2 ∞ ⎤ ⎥ ⎥ ⎥ ⎥ ⎦ + η t E π,p H h=1 ⟨π t -π, Q πt,t α ⟩[x h ] + αKL(π µ)[x h ] -αKL(π t µ)[x h ] = (1 -η t α)KL p (π π t ) + 2η 2 t E π,p ⎡ ⎢ ⎢ ⎢ ⎢ ⎣ H h=1 Q πt,t α (x h , ⋅) -α log π t (⋅ x h ) µ(⋅ x h ) 2 ∞ ⎤ ⎥ ⎥ ⎥ ⎥ ⎦ + η t V πt,t α (x 1 ) -V π,t α (x 1 ), where the third relation is by Lemmas 3.1 and E.5.Define the mixture policy in iteration t as: π α t (y x) = π t (y x) 1-ηtα µ(y x) ηtα ∑ y ′ ∈Y π t (y ′ x) 1-ηtα µ(y ′ x) ηtα . We now define the following mixture mirror descent policy optimization algorithm. In the first episode the algorithm plays the reference policy, i.e., π 1 = µ. Then, its update rule for iteration (t + 1) is as follows:EQUATIONThe solution can be made explicit:π t+1 (y h x h ) ∝ π α t (y h x h )e ηtQ π α t ,t α (x h ,y h ) .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 (5)) in a regularized adversarial MDP, for every policy π and every episode t,KL p (π π t+1 ) ≤ (1 -η t α)KL p (π π t ) + 2η 2 t E π,p H h=1 Q π α t ,t α (x h , ⋅) 2 ∞ + η t V π α t ,t α (x 1 ) -V π,t α (x 1 ) .Proof. Fix a state x h ∈ X h . We start by applying Munos et al. [2023, Lemma 2] with π + = π t+1 , π -= π α t and the vector δ(y) = η t Q π α t ,t α (x h , y). This implies that for any policy π,KL(π π t+1 )[x h ] ≤ KL(π π α t )[x h ] + η t ⟨π α t -π, Q π α t ,t α ⟩[x h ] + 2η 2 t Q π α t ,t α (x h , ⋅) 2 ∞ .Next, we plug this into Lemma 3.1 to obtainKL p (π π t+1 ) = E π,p H h=1 KL(π π t+1 )[x h ] ≤ E π,p H h=1 KL(π π α t )[x h ] + η t E π,p H h=1 ⟨π α t -π, Q π α t ,t α ⟩[x h ] + 2η 2 t E π,p H h=1 Q π α t ,t α (x h , ⋅) 2 ∞ ≤ E π,p H h=1 (1 -η t α)KL(π π t )[x h ] + η t αKL(π µ)[x h ] -η t αKL(π α t µ)[x h ] + η t E π,p H h=1 ⟨π α t -π, Q π α t ,t α ⟩[x h ] + 2η 2 t E π,p H h=1 Q π α t ,t α (x h , ⋅) 2 ∞ = (1 -η t α)E π,p H h=1 KL(π π t )[x h ] + 2η 2 t E π,p H h=1 Q π α t ,t α (x h , ⋅) 2 ∞ + η t E π,p H h=1 ⟨π α t -π, Q π α t ,t α ⟩[x h ] + αKL(π µ)[x h ] -αKL(π α t µ)[x h ] = (1 -η t α)KL p (π π t ) + 2η 2 t E π,p H h=1 Q π α t ,t α (x h , ⋅) 2 ∞ + η t V π α t ,t α (x 1 ) -V π,t α (x 1 ) ,where the second inequality is by Munos et al. [2023, Lemma 1] , and the last relation are by Lemmas 3.1 and E.5.Define µ min as the minimal positive probability assigned by the reference policy µ, i.e., µ min = min (x,y)∈X ×Y∶µ(y x)>0 µ(y x).Lemma E.8. For the choice η t = 2 α(t+2) , in every iteration t of mirror descent policy optimization it holds thatα(H + 1) log µ min ≤ Q πt,t α (x, y) -α log π t (y x) µ(y x h ) ≤ 2 -αH log µ min ∀(x, y) ∈ X × Y.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αH log µ min ≤ Q πt,t α (x, y) ≤ 1 ∀(x, y) ∈ X × Y.The same holds for Q π α t ,t α when running mixture mirror descent policy optimization.Proof. By the OMD optimization problem, π t (y x) will not be positive unless µ(y x) > 0 (the same holds for π α t ). Thus, for every x ∈ X we have0 ≤ KL(π t µ)[x] = y∈Y π t (y x) log π t (y x) µ(y x) = y∈Y π t (y x) log π t (y x) - y∈Y π t (y x) log µ(y x) ≤ y∈Y π t (y x) log 1 µ(y x) ≤ log 1 µ min .Now, by definition, the Q-function is bounded from above by 1 and from below by αH log µ min .Lemma E.10. For the choice η t = 2 α(t+2) , in every iteration t of mirror descent policy optimization it holds thatH log µ min - 1 α ≤ log π t (y x) µ(y x) ≤ log 1 µ min ∀(x, y) ∈ X × Y.Proof. For the upper bound, notice thatlog π t (y x) µ(y x) = log π t (y x) -log µ(y x) ≤ log 1 µ(y x)≤ log 1 µ min .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 as followslog y ′ ∈Y π t (y ′ x)e ηt Q π t ,t α (x,y ′ )-α log π t (y ′ x) µ(y ′ x) ≤ log y ′ ∈Y π t (y ′ x)e ηt 1-α log π t (y ′ x) µ(y ′ x) = η t + log y ′ ∈Y π t (y ′ x) µ(y ′ x) π t (y ′ x) ηtα ≤ η t + log ⎛ ⎝ y ′ ∈Y π t (y ′ x) µ(y ′ x) π t (y ′ x) ⎞ ⎠ ηtα = η t ,where the first inequality follows since Q πt,t α (x, y) ≤ 1, and the second uses Jensen inequality (with the fact that η t α ≤ 1). Now, by the update rule of π t ,log π t+1 (y x) µ(y x) = log π t (y x) µ(y x) + η t Q πt,t α (x, y) -η t α log π t (y x) µ(y x) -log y ′ ∈Y π t (y ′ x)e ηt Q π t ,t α (x,y ′ )-α log π t (y ′ x) µ(y ′ x) ≥ (1 -η t α) log π t (y x) µ(y x) + η t Q πt,t α (x, y) -η t ≥ (1 -η t α) log π t (y x) µ(y x) + η t (αH log µ min -1).(Lemma E.9)To finish the proof plug in η t and unroll t to 0. 
experiments compute resources: 
 Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?Answer: [Yes] Justification: The computer resources for rour experiments are detailed in Sections 5 and 6.Guidelines:• The answer NA means that the paper does not include experiments.• The paper should indicate the type of compute workers CPU or 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 as 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 it into the paper). 
code of ethics: 
 Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines?Answer: [Yes] Justification: We have reviewed the NeurIPS 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 a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 
broader impacts: 
 Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?• 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 a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.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, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. • For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be 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 5 describes the exact way in which we created the Education Dialogue environments, and Appendix C provides 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 was obtained from people whose asset is used. https://github.com/google-research-datasets/Education-Dialogue-Dataset 
 
 Appendix:  


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

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: - 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.

- Limited experiments only using small T-5 models and simple configurations.
questions: questions: Refer to weaknesses.
limitations: limitations: The current evaluation is limited and can be extended to other models and tasks to show the effectiveness of the approach.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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.
2. 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.
3. 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.
4. 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.
5. 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.
6. 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.
questions: questions: As listed in weaknesses.
limitations: limitations: The paper has discussed the proper amount of limitations.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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: 
1. 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.
2. 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.

Minor suggestions: 
1. The concept of "anchor policy" should be explained in more detail to make it easier to understand the problem formulation and methods.
2. Derivation of Equation (1) to Equation (2) is missing.
questions: questions: 1. Single-turn RLHF v.s. multi-turn RLHF
	- 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.
2. Efficiency of difference methods
	- 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.
3. Generalizability
	- 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?
4. MTPO (online oracle) v.s. MTPO (preference data) in the Car Dealer task
	- Could you please present a possible explanation why MTPO (preference data) outperforms MTPO (online oracle)?
limitations: limitations: Limitations of the paper is discussed.
paper_summary: paper_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.
strength_weakness: strength_weakness: - The experiment employs a small model, which may limit its generalizability to larger-scale models used in current LLMs.
- 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.
questions: 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.
- 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.
- 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: limitations: This work only utilizes relatively small T5-based models and prompt-based environments.

Comments: title: Thanks for the further clarification
Progress of additional Gemma experiments
Thanks for the responses
comment: * See the following detailed description of our single-turn baselines, which we will add in the final version of the paper:
In order to run a single-turn algorithm we need to provide preference feedback between two immediate generations in each specific turn. To create this data, we generate partial conversations (up to a random turn number i) using the SFT policy, and at this turn we generate two independent answers (again using the SFT policy). Now, to get the preference feedback we employ two different methods:
    * Single-turn-reward: We use a modified preference prompt (can be found in Appendix C and we also add it below) in which the model is asked to evaluate the responses by their effect on the overall conversation.
    * Single-turn-value: We use the SFT policy to continue the two conversations until the end, and then use our original prompt to get the preference.

To sum up, the input to the single-turn algorithm is a dataset that consists of partial conversations. For each partial conversation, there are two immediate responses and a preference between them. The algorithm uses this dataset to learn a reward model (RLHF) or a preference reward model (NashMD). Then, the RL part is done just like in standard RLHF: Sample a partial conversation from the dataset, generate one/two immediate responses using the policy, get a reward/preference from the model, and perform a policy gradient step.



### Modified prompt:

You are an expert at assessing teachers. Here is an
interaction between a teacher and a student.
#
Interaction:
{conv}
#
Here are two possible responses by the teacher:
#
Response 1:
{resp1}
#
Response 2:
{resp2}
#
A good interaction between a 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 one of these responses, which response
will lead to a better interaction (do not let the order
interactions affect your answer)? Output 1 or 2.
Thank you for carefully reading the paper and participating in the discussion, your comments are valuable and will surely help us improve the final version. We hope the following responses answer your follow-up questions, and we will be happy to provide further clarifications.

* The primary motivation for our work is the multi-turn RL setting, which was not investigated before with a theoretically grounded approach in the LLM alignment literature, and the reviewer agrees is of significant importance. Within the multi-turn setting, it is natural to explore algorithms that converge to Nash equilibrium since Munos et al. (Nash-MD) and Calandriello et al. (Online-IPO) showed that they outperform RLHF algorithms in the single-turn setting. Importantly, extending the results of Munos et al. to the multi-turn setting is a very difficult task. It builds on the vast RL literature that extends algorithms from Multi-Armed Bandits to Markov Decision Processes (MDPs), as well as requires crucial novel ideas that do not appear in the literature such as the preference-based Q-function. Using these, we are able to prove that even in the much more complex multi-turn setting, there exists an algorithm which both converges to Nash equilibrium and outperforms RLHF algorithms (both single-turn and multi-turn) in practice.


* We share the same feelings as the reviewer towards the importance of conversation generation, as resonated through our choice to design our benchmark as an education-based conversation generation task. In turn, we agree that it will improve our work to include a discussion of how our approach differs or can be used as a complementary approach for techniques presented in relevant NLG works, and specifically ones that are based on RL. 
If the reviewer has any more references besides the seminal “Deep Reinforcement Learning for Language Generation”, we would be happy to include them in the discussion that we will add to the final version.
\
We feel it is important to note again that our multi-turn setting is more general than conversation-generation, and captures other important tasks. One example is multi-turn tool use: In this task, the agent gets a single query from a user, and is allowed to repeatedly use different tools through API calls and responses. The interaction ends when the agent decides it has enough context to respond to the user, and generates a final user-facing response. This whole process consists of $N$ turns, where there are $N-1$ consecutive tool calls, and a final generation turn. The goal in this case is the alignment of this final user-facing response, so the preference feedback is only given at the end of the process. Importantly, it is hard to acquire local feedback (rewards or preferences) for each of the tool-calls, and the alignment is only captured w.r.t. to the final response. In this scenario, our multi-turn alignment algorithm MTPO allows the propagation of the final alignment signal to improve the intermediate tool-calls, towards the goal of making the overall user-facing generation better. We will include a similar discussion to make the motivation and scope of our work clearer.

* All the derivations in section 3 and 4 are new. Naturally they are motivated by the work of Munos et al. on the single-turn setting and by the vast literature on Mirror Descent, but the extension of these to the multi-turn setting (and the definition of this setting) are not trivial and require delicate derivations and proofs. Note that some definitions in section 3, which might look similar to objects previously defined in Munos et al., are actually entirely new. For example, the regularized preference model that we present in section 3, is a generalization of the regularized preference model of Nash-MD, with a significant difference: The preference $\mathcal{P}(\pi \succ \pi’)$ is the expected preference over the whole multi-turn decision process of following the policy $\pi$ vs. $\pi’$ in the environment with transition probabilities $p$. 
In the opening paragraph of this section, you can see that  $\mathcal{P}(\pi \succ \pi’) = \mathbb{E} \left[ \mathcal{P}(x_{H+1} \succ x’_{H+1}) \mid \pi, \pi’, p \right]$. Importantly, the expectation is taken over the whole MDP, meaning the expectation over the possible multi-turn interactions given an agent policy $\pi$ (e.g., the teacher)  and a transition model $p$ of the environment (e.g., the student).
Moreover, the definition of $KL_p$ is again the expected KL over a multi-turn trajectory which is different from the single-turn KL of Munos et al., however we prove a strong connection between them in Lemma 3.1. We kindly ask the reviewer to give specific pointers to information which is taken from previous work in these sections.
Thank you for the responses and the newly provided experiments. While some of my concerns remain, I would increase my score from 4 to 5. Belows are some follow-ups for the unaddressed concerns.
* Regarding motivation, my question is, "Why use Nash Equilibrium for the multi-turn scenario?" The multi-turn scenario is important for sure, and the exploration of Nash Equilibrium LM is interesting, too. But such an exploration was already made in NashMD paper (Munos et al. 2023). Does it mean the motivation of this work is extending the same idea from single-turn cases to multi-turn cases?
* Regarding comparison to NLG works. This paper works on LLM alignment, which is primarily within the conversation generation area. I do not see a reason why not discussing/comparing them.
* The current writing of this paper gives me difficulty to find out which parts are the new ones. I do see not only Section 2 but even in Sections 3 and 4 that many information or equations are from or derived from (Munos et al. 2023).
* About the experiments, I haven't seen a response to my question of the input, output, and rewards used for every baseline. Also, after reading the response to the suggested experiment, I'm still confused about how the current "single turn experiment" in the paper optimizes: does it use a single turn to optimize the model once a time? or does it accumulate rewards for all turns and optimize together? In the meantime, the experiment I asked is using each turn but constrained optimization. But to my understanding of the response, the authors do not tackle this, but mention a different thing.
Dear Reviewer AyR4, 

We hope this message finds you well. We kindly want to check if you had a chance to review our rebuttal, and if you have any further questions or comments we can address to help with your evaluation.

Sincerely,
The authors
Thanks for the further clarification. I have updated my recommendation to reflect the rebuttal.
Thank you for the thorough response. After reading the rebuttal, I decided to increase my score by +1.
Dear reviewers,

A brief update:
Together with the T5-XL experiments we already posted in the rebuttal and reaffirm our experimental results, we are working on adding a similar set of experiments with **Gemma models**.

We already (supervised) fine-tuned Gemma models for the agent and environment, used them to generate data for learning the reward and preferences model, and currently the reward and preferences training is underway. Once it's finished, we will train and evaluate MTPO and our multi-turn and single-turn baselines.

**We will add these results to the camera-ready version.**

Sincerely,
The authors
We thank you for reading our responses, here are answers to your questions:

1. We are familiar with this term [1,2,3], and thought it is wide-spread, but after your comment we surveyed many papers and observed that it is indeed not as common as we thought. Thanks for mentioning this! We agree that explaining the term anchor policy, the reference policy used for regularization, will help the readers and we will incorporate it in the final version along with the above references that use this term.

2. The description of how we created single-turn feedback can be found in section 5 in the single-turn baselines paragraph. We now provide a detailed explanation which we will also include in the final version to improve clarity:
\
In order to run a single-turn algorithm we need to provide preference feedback between two immediate generations in each specific turn. To create this data, we generate partial conversations (up to a random turn number i) using the SFT policy, and at this turn we generate two independent answers (again using the SFT policy). Now, to get the preference feedback we employ two different methods:
    * Single-turn-reward: We use a modified preference prompt (can be found in Appendix C and we also add it below) in which the model is asked to evaluate the responses by their effect on the overall conversation.
    * Single-turn-value: We use the SFT policy to continue the two conversations until the end, and then use our original prompt to get the preference.

3. We will include a comment in the final version on the running time of the different algorithms. Specifically, in our experiments, multi-turn algorithms are slower than their single-turn alternatives by a factor of 2. However, it is important to emphasize that running single-turn algorithms longer does not yield better policies. Instead, this leads to worse policies due to overfitting.


[1] PERL: Parameter Efficient Reinforcement Learning from Human Feedback, Sidahmed et al.

[2] Factually Consistent Summarization via Reinforcement Learning with Textual Entailment Feedback, Roit et al.

[3] WARP: On the Benefits of Weight Averaged Rewarded Policies, Ramé et al.



**Modified prompt:**

You are an expert at assessing teachers. Here is an
interaction between a teacher and a student.
#
Interaction:
{conv}
#
Here are two possible responses by the teacher:
#
Response 1:
{resp1}
#
Response 2:
{resp2}
#
A good interaction between a 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 one of these responses, which response
will lead to a better interaction (do not let the order
interactions affect your answer)? Output 1 or 2.
Thanks for your responses. Some of my concerns were address, however there are still some comments and questions remaining. 

> The concept of an anchor policy is wide-spread in the alignment literature

I agree that regularizing a training policy towards an existing policy is a common practice in off-policy RL, offline RL, and alignment literature. However, the term "anchor policy" may not be widely recognized as standard terminology. It would be helpful for readers if you explained it or provided appropriate references when introducing it for the first time to maintain the reading flow.

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

I agree with this. Could you please provide more details on how you collected single-turn feedback in your practical experiments? Specifically, how did you "artificially create" single-turn feedback?

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

Could you please include this comparison, e.g., in a single sentence, in the camera-ready paper if it is accepted? This would help readers better understand the overall task setup and the proposed method for multi-turn RLHF.
Thank you for reading our response. Since we performed additional experiments on larger models and added new evaluations based on your suggestions, have we answered all of your concerns? If so, we kindly ask that you consider raising your score accordingly. We would like to add that we are currently running experiments with Gemma models.
Thanks for the authors' comprehensive response. I would like to keep the current score. Thanks!