We thank the reviewer for evaluating our work.

We would like to point the reviewer to the general response regarding their concerns with the size of the models and using ChatGPT/Gemini for evaluations. In short, we conducted additional experiments with T5-XL (3B) that solidify the conclusions of our original experiments, and added evaluations using Gemini-Ultra that again reach similar conclusions to the original evaluations in the paper. We plan to add additional experiments with T5-XXL (11B) for the camera ready version.

Regarding the questions asked by the reviewer:

1. Performing additional experiments with decoder-only models is indeed valuable, but this is left for future work since obtaining SOTA models is not the purpose of our experiments. The experiments in the paper validate our theoretical findings and the efficacy of our preference-based multi-turn approach. Please see additional explanations in the general response regarding T5-large models.
2. Regarding a discussion on the rewards, we kindly ask the reviewer to read the general response regarding the soundness of our evaluations and the new evaluations that we now added.
3. Regarding the absence of reward, we note that the data is inherently preference-based so there is no reason to assume that a reward exists. Moreover, as shown by the NashMD paper [1], there are situations that cannot be captured by a reward, only by a direct preference model. For further explanations, we kindly refer the reviewer to the general response about motivation and evaluations.

[1] Nash Learning from Human Feedback, Munos et al.

We thank the reviewer for carefully assessing our work. We kindly point the reviewer to the general response regarding their concerns with the size of the models – we conducted additional experiments with T5-XL (3B) that solidify the conclusions of our original experiments. We plan to add additional experiments with T5-XXL (11B) for the camera ready version.

Regarding tasks, we agree that it would be very interesting to test our algorithms on other benchmarks. Specifically, we see tool-use and long-term reasoning as particularly important and interesting tasks. However, when writing this paper, we could not find much prior alignment work for the multi-turn setup for natural language, and therefore there was no usable multi-turn task. Instead, we could only find reward-based tasks like the LMRL-GYM, that the car dealer experiment is based upon, in which the goal is the usual RL goal of improving a reward, and not improving the alignment w.r.t. preference data. This has led us to develop a new task for this setting, Education Dialogue. We believe that this task is an important contribution by itself, and will allow future research on this topic, and we will be happy if other researchers can create new relevant tasks for this topic.

Thanks for the minor suggestions, we will clarify these in the final version.

1. The concept of an anchor policy is wide-spread in the alignment literature, and refers to regularizing towards the initial supervised policy so that the learned policy will not diverge too far from the good properties of the base model. We will make sure this is clearly stated.
2. Regarding the derivation of eq. (2) from eq. (1): Thanks for the comment, it is quite straight-forward and we will make sure a rigorous derivation appears in the appendix: It is widely known that the solution for any policy $\pi’$, $\pi^* = \arg\max \langle Q(\cdot), \pi(\cdot) \rangle - KL(\pi || \pi’)$ is $\pi^*(\cdot) \propto \pi’(\cdot) \exp(\cdot)$ (This is commonly used in mirror-descent based algorithms, as well as in DPO). From here, we note that it can be shown with a simple algebraic manipulation that the optimization problem in eq. (1) is equivalent to the above optimization problem, when $\pi’=\pi_k^\mu$, the geometric mixture $\pi_k^\mu \propto \pi_k^{1 - \alpha \eta_k} \mu^{\alpha \eta_k}$. The derivation is concluded by plugging this in the solution presented above.

Regarding the questions asked by the reviewer:

1. We would like to clarify that single-turn RLHF uses feedback for each individual turn, which does not exist (or is very hard to define) in tasks that are inherently multi-turn. This is validated in our experiments in which single-turn baselines perform significantly worse than the multi-turn algorithms. Specifically, we see that even if we artificially create single-turn feedback, it is hard to define it in such a way that aligns with the overall preference (which is the alignment goal in this setting). Moreover, unlike trajectory-level feedback, turn-level feedback depends on the policy that continues the conversation after this specific turn, and therefore becomes biased once the policy changes through the learning process.
2. We agree that training time is an important question, but this is not the focus of this paper and we leave this to future research. We focus on whether multi-turn RL improves upon single-turn in tasks that are inherently multi-turn. Both our theory and our experiments corroborate that a multi-turn approach is crucial for obtaining a better policy. Depending on the application and the resources, different projects may choose whether they are able to apply it or not.
3. Regarding different tasks/applications for multi-turn RL please see the second paragraph.
4. Note that the difference in performance between MTPO (preference data) and MTPO (online oracle) is very small, which leads us to believe that they are actually roughly equal in performance. A sensible explanation is therefore that both of them converged to the optimal policy (or at least some local optimum). Thus, MTPO (online oracle) cannot outperform MTPO (preference data) even though it observes better feedback.

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.

We thank the reviewer for carefully reviewing our work. In the following we answer your concerns:

1. Our definition of Nash equilibrium is correct and this is in fact the most natural definition that arises from our multi-turn preference model. Note that only a pure Nash equilibrium satisfies ”one agent cannot get a better reward by just changing its action”. Generally, a Nash equilibrium is defined as a set of players’ strategies for which no agent can increase their payoffs by changing their own strategy. This holds beyond simple constant-sum matrix games, and can be extended to the concepts of subgame perfect nash equilibrium in extensive-form games or Markov Perfect Equilibrium in Stochastic games, which are similar to our formulation. Importantly - (i) even in matrix games, strategies are not necessarily “pure”, meaning that a strategy does not equal an action. Instead, in the RL terminology, strategy = a (stochastic) policy, and in our multi-turn case, the policy is a function of a state $\pi(a|s)$. (ii) In alignment in general, and particularly in our multi-turn case, the payoff of a game is not the “reward” but the preference of one policy against another. All in all, this makes our definition quite natural: A good policy is a one that is preferred over any other policy. Notably, there does not exist a preference model for individual actions (only entire trajectories). Finally, due to the structure of the regularized preference objective (anti-symmetric), the Nash equilibrium will have both agents following the same policy and thus we can express it in terms of a single policy such that no other policy is preferred over it. We will be happy to provide additional clarification, and we will add this discussion together with relevant game theory citations in the final version.
2. Regarding motivation: We disagree that the paper is not well-motivated. Multi-turn interactions are extremely important for LLM alignment because we use them in a multi-turn conversational manner. Moreover, the motivation for exploring Nash equilibrium in this setting is exactly the same as in the single-turn case. Just as NashMD and IPO motivate their work, since the data itself is preference-based, there is no reason to assume the existence of a reward model. Therefore, both our work and NashMD/IPO give stronger theoretical guarantees on the policy that they converge to. Moreover, both NashMD and our MTPO algorithm are shown to be superior to RLHF baselines in practical experiments.
3. Regarding comparison to NLG literature: While our paper investigates LLM alignment, which is not built upon literature on dialogue NLG, we do agree with the reviewer that this literature should be referenced. We will add these references and relevant discussion in the camera-ready version.
4. Regarding contextual MDPs: The single-turn alignment problem is usually described as a contextual multi-armed bandits problem (e.g., section 3 of the NashMD paper). Therefore, it is natural and rigorous to treat the multi-turn problem as a contextual MDP. In our formalization we used this description, but as often done in the single-turn case, we omit the context in our analysis for brevity. Importantly, the problem is indeed a contextual MDP and we will be happy to add the citation.
5. We disagree with the claim that old knowledge and newly proposed ideas are mixed together in the paper. We kindly ask the reviewer to explicitly point us to the places where this happens, so we can improve the presentation of the paper. Nonetheless, for better readability, we will include the organization of the paper in a paragraph in the introduction. In short, the preliminary section (section 2) is the only place where previous knowledge is presented, while all the following sections present our novel ideas.
6. If we understood the reviewer’s intention correctly, your suggestion is essentially what we refer to as single turn experiments, which perform markedly worse than our multi-turn variants. Similarly to your suggestion, there already exists a KL-penalty to the previous policy $\pi_k$ and the anchor $\mu$ in both our theoretically grounded MTPO algorithm (eq. 1), and in our theoretically proven Multi-turn RLHF (Section 4, Multi-turn RLHF paragraph). The former is a result of the fact that both of these algorithms are based on Mirror-Descent policy optimization, similarly to TRPO and PPO [2, 3]. This term is aimed at increasing learning stability (as in TRPO/PPO). For our single turn experiments, we “suppose” a turn level reward/preference signal using two methods. (1) Using a prompted model (2) By rolling out two samples of the conversation until their end and querying the trajectory level preference model. Our multi-turn algorithms essentially replace this supposed reward signal with a correct notion of preference/reward based $Q$ function, which is one of the key contributions of our work.

[1] Nash Learning from Human Feedback, Munos et al.

[2] Adaptive Trust Region Policy Optimization: Global Rates and Faster Convergence to Regularized MDPs, Shani et al.

[3] Mirror Descent Policy Optimization, Tomar et al.

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.

We thank the reviewer for taking the time to evaluate our work. Here are the responses to your comments:

Human evaluation: We refer the reviewer to the discussion in the main response on human evaluation and alignment. We briefly repeat the main message there: The main goal of our experimental section is to test our algorithms against other algorithms in how good they are able to align with preference data. Unlike single-turn benchmarks which are based on data with real human-preferences, our Education Dialogue domain is based on Gemini-Ultra curated preferences. As a result, evaluating this alignment using the same Gemini-Ultra model as done in our new presented experiments is true to our goal of understanding how to align to preference data. While human-evaluation is always interesting, here it is actually just a proxy to alignment with the data.

Regarding the prompt for LLM evaluation: We agree that in a real dialogue system, it is important to collect diverse data from raters that account for many attributes of what it means to be a good conversation. However, the goal of this paper is not to create a real dialogue system, but to develop better algorithms to be used for alignment. We believe that grounded theory and our experimental results suggest that MTPO should be heavily considered when trying to create such a real dialogue system or any other multi-turn domain. It is important to point out that other algorithm-focused works (RLHF/DPO/IPO/NashMD) are also using a single-preference signal that tries to holistically capture the task (e.g., summarization). This is again due to the fact that these papers are not intended to create a SOTA summarization model, but rather to provide new algorithms to train one.

Regarding model sizes: We added experiments with T5-XL (3B) that solidify the conclusions of our original experiments and we plan to add additional experiments with T5-XXL (11B) for the camera ready version. We refer the reviewer to the general response for a detailed discussion of our results.

In light of the above, we kindly request the reviewer to reconsider their score based on both the significance of our theoretical contribution and the new experiments showing that our results extend to larger models.