PaperlayerView exact revision on arXiv

Source-linked AI summary

Multi-turn Reinforcement Learning from Preference Human Feedback

Lior Shani, Aviv Rosenberg, Asaf Cassel, Oran Lang, Daniele Calandriello, Avital Zipori, Hila Noga, Orgad Keller, Bilal Piot, Idan Szpektor, Avinatan Hassidim, Yossi Matias, Rémi Munos

arXiv:2405.14655v2cs.LG

TL;DR

Single-turn preference learning is limited for tasks requiring planning across interactions. The paper develops preference-based RL for full multi-turn conversations, with a mirror-descent algorithm proven to converge to Nash equilibrium. Its multi-turn methods outperform single-turn baselines in Education Dialogue, and preference-based learning matches reward-based RL performance in Car Dealer.

  • Problem

    Existing RLHF and direct preference-learning methods focus mainly on single-turn scenarios, limiting their coverage of tasks requiring planning or multi-turn interaction.

    Source: §1 · p. 2

  • Method

    The paper compares full multi-turn conversations using preference feedback and develops mirror-descent-based policy optimization algorithms for this setting.

    Source: §1 · p. 2

  • Results

    In Education Dialogue, multi-turn methods significantly outperform single-turn baselines and direct multi-turn preference outperforms multi-turn RLHF; in Car Dealer, preference-based learning matches reward-based RL performance.

    Source: §1 · p. 2

  • Takeaways & Limitations

    Conversation-level feedback can capture long-term effects of actions that may be difficult to assess from individual turns.

    Source: §1 · p. 2

    The experiments are a proof of concept using relatively small T5-based models and prompt-based environments; state-of-the-art models and more realistic environments remain future work.

    Source: §6 · p. 10

Abstract

from arXiv · show

Reinforcement Learning from Human Feedback (RLHF) has become the standard approach for aligning Large Language Models (LLMs) with human preferences, allowing LLMs to demonstrate remarkable abilities in various tasks. Existing methods work by emulating the preferences 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.

1 Introduction

Single-turn preference learning is limited in tasks requiring adaptive, long-term interaction. This work extends preference-based RL to full multi-turn conversations and develops algorithms with theoretical guarantees and empirical evaluations.

Introduction

  • Single-turn alignment lacks adaptive, long-term capabilities relevant to multi-turn dialogue, complex tool use, and multi-step games.The paper positions its algorithmic approach as broader than dialogue systems, including tool use and reasoning.Source: §1 · pp. 2–3

Contributions

  • The paper extends RLHF to compare complete multi-turn conversations, allowing feedback to capture long-term effects of actions that may be hard to judge turn by turn.A seller's high initial price may seem bad alone but potentially good as part of a strategy to increase the sale price.Source: §1 · p. 2
  • MTPO uses mirror descent and self-play for multi-turn preference-based policy optimization and is proven to converge to a Nash equilibrium.The paper also proves similar results for MTPO−τ and convergence of a multi-turn RLHF variant to an optimal policy relative to its learned reward.Source: §1 · p. 2
  • In Education Dialogue, multi-turn algorithms significantly outperform single-turn baselines, direct multi-turn preference outperforms multi-turn RLHF, and preference-based learning matches reward-based RL performance in Car Dealer.The Education Dialogue environment has a teacher guide a student learning a random topic; Car Dealer evaluates maximizing the sale price.Source: §1 · p. 2

Related work

  • Existing RLHF and direct preference-learning methods mainly address single-turn scenarios, while MTPO provides guarantees for multi-turn settings.The paper distinguishes this from token-level extensions of direct preference optimization, which do not address the intervening human-generated tokens in a true multi-turn interaction.Source: §1 · pp. 2–3

2 Preliminaries

The preliminaries model interaction as a contextual, finite-horizon decision process and introduce single-turn preference feedback, including reward-based RLHF and direct preference learning.

2 Preliminaries

  • A contextual Markov decision process samples an initial context and state, then proceeds for H steps as the agent observes states, chooses actions, and transitions through the environment.A policy maps context and state to a distribution over actions and, together with the transition function, induces a trajectory distribution.Source: §2 · p. 3

2.1 Single-turn Reinforcement Learning from Human Feedback

  • In single-turn preference learning, the agent generates one response per context and receives a preference between two responses, represented by a model giving the probability one is preferred over the other.This setting is a contextual multi-armed bandit, or a contextual MDP with horizon H = 1.Source: §2.1 · p. 3
  • RLHF assumes preferences arise from a hidden reward through the Bradley-Terry model, whereas direct preference learning drops that assumption and can optimize toward a Nash equilibrium.The described Nash-MD update uses mirror descent projected to a geometric mixture of the current policy and a reference policy.Source: §2.1 · p. 4

3 Multi-turn Preference-Based RL

The section formulates multi-turn preference-based RL around feedback comparing final conversation states under a shared initial context. It defines a Nash-equilibrium objective and establishes properties of a regularized preference model.

3 Multi-turn Preference-Based RL

  • Feedback compares final states from two full trajectories sharing an initial context, rather than evaluating each turn independently.The authors motivate this choice by noting that action quality can depend on later interaction and the conversation’s eventual outcome.Source: §3 · pp. 4–5
  • The objective is a policy preferred to every alternative, and the anti-symmetric preference game has a Nash equilibrium in which both agents use the same policy.The equilibrium can therefore be expressed as a single policy.Source: §3 · p. 4
  • For the regularized preference model, the trajectory-level KL term decomposes into statewise KL divergences and the model has a unique Nash equilibrium.The uniqueness result is stated in Lemma 3.2.Source: §3 · p. 4
  • In dialogue, states contain conversation history and actions are generated responses; the same framework also describes agents making repeated API calls.For tool use, state summarizes the query and results so far, while actions are API calls or user-facing responses.Source: §3 · p. 5
  • The formulation also covers token-level autoregressive generation by treating each vocabulary token as an action under a null deterministic environment.The authors note that their results apply to token-level optimization, which single-turn algorithms usually neglect.Source: §3 · p. 5

4 Algorithms for the multi-turn setting

MTPO uses self-play mirror descent and a preference-based Q-function to turn global multi-turn optimization into local statewise updates, and proves last-iterate convergence to a unique Nash equilibrium.

4 Algorithms for the multi-turn setting

  • The preference-based Q-function compares policies from different starting points, letting local optimization improve the global preference objective.The evaluated policy starts at the current state, while its comparison policy starts from the initial state; the value-difference lemma connects local advantages to the global objective.Source: §4 · p. 5
  • MTPO provably converges to the unique Nash equilibrium of the regularized preference model, with last-iterate convergence.Its self-play mirror-descent method reduces global game optimization to local mirror-descent problems in each state.Source: §4 · p. 6
  • MTPO updates each action probability using its self-play Q-value while retaining a regularization-weighted connection to the reference policy.The update combines the current policy, reference policy, and preference-based Q-function; the stated intuition is to improve preference while staying close to the reference.Source: §4 · p. 6
  • MTPO-τ uses a geometric mixture policy, has similar theoretical guarantees, and performs better in practice than MTPO.MTPO avoids MTPO-τ's additional policy and the difficulty of computing its geometric mixture.Source: §4 · p. 6
  • Multi-turn RLHF uses the same optimization process with a fixed learned reward, whereas MTPO computes preferences adaptively through self-play.The multi-turn RLHF variant converges to the optimal regularized policy for its learned reward.Source: §4 · p. 7

4.1 Deep RL implementation

  • Deep training samples two current-policy trajectories per context and compares their final states using a preference model trained on offline data.The preference model is trained in advance on the available offline preference data.Source: §4.1 · p. 7
  • The implementation uses policy gradients without the mirror-descent stability penalty and assigns one value to each turn rather than each token.The authors leave adding the penalty and combining turn-level and token-level values for future research.Source: §4.1 · p. 7

5 Experimental Setup

The experiments use Education Dialogue to study preference-based teaching conversations, alongside Car Dealer as a reward-based domain. The setup creates dialogue data and preference or reward models, then evaluates multi-turn methods against single-turn baselines.

5 Experimental Setup

  • The data-generation process prompts a high-capacity LLM with a storyline and sampled attributes to generate both sides of each conversation at once.Smaller agent and environment models are then fine-tuned on the curated conversations using teacher forcing.Source: §5 · pp. 7–8, Figure 1 · p. 8
  • Preference and reward training data come from pairs of sampled conversations labeled by a prompted high-capacity LLM, then train smaller models with probability-regression and Bradley–Terry losses, respectively.Source: §5 · p. 8
  • Education Dialogue has a teacher teach a science, history, or other topic to a student with specified learning habits, and Gemini Ultra prompts generate interactions and define good learning interactions.The authors release the benchmark data and prompts.Source: §5 · p. 8
  • Car Dealer uses published data, with sale price extracted from conversations as reward and Bradley–Terry preferences derived from trajectory rewards.Source: §5 · p. 9
  • Single-turn-reward rates alternative responses using their effect on the overall conversation, while single-turn-value continues both trajectories to estimate their eventual preference.Both baselines are trained with RLHF and preference-based Nash-MD algorithms.Source: §5 · p. 9
  • Experiments use T5-large and T5-XL agents and environments, Flan-T5 XL prompted preference models, and evaluations on 1,600 independent random samples.Training uses 4 × 4 TPUs and episodes of 10 turns.Source: §5 · p. 9

6 Experiments

In Education Dialogue, conversation-level multi-turn methods outperform single-turn baselines, and MTPO variants outperform multi-turn RLHF. In Car Dealer, MTPO performs as well as reward-based RL, while the experimental scope remains limited by small T5 models and prompted environments.

6 Experiments

  • The Education Dialogue evaluation aligns models with Gemini Ultra’s generated preference data, using Flan-T5 XL for an initial comparison and Gemini Ultra to compare best candidates.Source: §6 · p. 9
  • All multi-turn methods with conversation-level feedback significantly outperform single-turn baselines in Education Dialogue.The comparison uses prompted Flan-T5 XL and Gemini Ultra judges; Table 2 reports Gemini Ultra evaluations.Source: §6 · p. 10, Table 2 · p. 10
  • Both MTPO variants outperform multi-turn RLHF, and MTPO-τ outperforms MTPO despite both converging to the same Nash equilibrium.The authors conjecture that the stochastic mixture policy in MTPO-τ yields more diverse self-play trajectories and more informative feedback.Source: §6 · p. 10
  • In Car Dealer, MTPO learns as well as policy-gradient RL using preferences instead of explicit rewards, and recovers slightly higher reward than multi-turn RLHF.The true preferences are sampled from a Bradley–Terry model.Source: §6 · p. 10, Table 3 · p. 10
  • The experiments are a proof of concept, limited by relatively small T5-based models and prompt-based environments; state-of-the-art models and more realistic environments remain future work.Source: §6 · p. 10

A.1 KL decomposition (proof of Lemma 3.1)

The proof defines policy KL divergence through the distributions policies induce over MDP trajectories.

A.1 KL decomposition (proof of Lemma 3.1)

  • Policy KL divergence is defined between the trajectory distributions induced by the policies in the MDP.A trajectory is denoted τ = (x1,y1,...,xH,yH,xH+1).Source: §A.1 · p. 16

A.2 Existence and uniqueness of the Nash equilibrium (proof of Lemma 3.2)

The proof establishes existence and uniqueness of a Nash equilibrium for the regularized preference game. It uses concavity properties of the preference model and the convergence of MTPO policies to characterize the unique equilibrium.

A.2 Existence and uniqueness of the Nash equilibrium (proof of Lemma 3.2)

  • The regularized preference game has a unique Nash equilibrium.The proof establishes existence and then shows uniqueness.Source: §A.2 · pp. 16–17
  • Uniqueness uses MTPO convergence and the fact that equilibria share the reference policy’s support, so their behavior agrees on every reachable state.Source: §A.2 · p. 16
  • Existence follows by finding a max-min policy on the compact policy set and applying a minimax theorem to the concave-convexlike preference game.Source: §A.2 · p. 17
  • The concavity argument constructs a policy whose state reach probabilities are the weighted mixture of those of two policies.The proof establishes this reach-probability construction by induction.Source: §A.2 · pp. 17–18

B.1 Regularized preference-based Q-function (proof of Lemma 4.1)

Lemma 4.1 relates terminal-state values to preferences between policies and gives recursive and value-difference relations for the regularized setting.

B.1 Regularized preference-based Q-function (proof of Lemma 4.1)

  • At a terminal state, the value is the probability that policy π’s conversation is preferred to policy π′’s.The lemma states this as V^π,π′_α(x_H+1) = P(x_H+1 ≻_π′).Source: §B.1 · p. 19
  • The lemma also provides recursive relations across interaction steps and a value-difference lemma.Source: §B.1 · p. 19
  • The proof casts preference-based reinforcement learning as an adversarial MDP, using preference probability as the terminal reward.Source: §B.1 · p. 19

B.2 Convergence of MTPO (Proof of Theorem 4.2)

The section establishes per-iteration guarantees for MTPO and connects them to mirror-descent policy optimization, yielding a Nash equilibrium of the regularized preference model.

B.2 Convergence of MTPO (Proof of Theorem 4.2)

  • The theorem states an iteration-wise guarantee under a specified learning-rate choice and a bound on Q-function magnitude.Source: §B.2 · p. 19
  • The proof recasts preference-based learning as an adversarial MDP and uses MTPO’s equivalence to mirror-descent policy optimization.Source: §B.2 · p. 19
  • MTPO’s guarantee identifies a Nash equilibrium of the regularized preference model Pα.Source: §B.2 · p. 19

B.3 MTPO with mixture policy (MTPO-τ)

The appendix presents a mixture-policy variant of MTPO and its convergence guarantees, then describes multi-turn RLHF guarantees, Education Dialogue prompts and examples, and the hyperparameter sweeps.

B.3 MTPO with mixture policy (MTPO-τ)

  • MTPO-τ is presented as a mixture-policy variant, with convergence guarantees for the regularized preference model’s Nash equilibrium.Source: §B.3 · p. 20

B.4 Convergence of multi-turn RLHF

  • Multi-turn RLHF also has an iteration-wise guarantee, with its proof reducing the method to mirror-descent policy optimization using the learned reward.Source: §B.4 · p. 21

C.1 Prompts for creating the environment

  • Education Dialogue prompts specify conversations lasting roughly 10–15 turns between a teacher and student, with a sampled topic and teacher and student preferences drawn from provided lists.Source: §C.1 · pp. 22–23

C.2 Examples of interactions

  • The examples include both interactive activities and more lecture-like teaching interactions.Source: §C.2 · pp. 24–25

D.1 Hyperparameters

  • The experiments sweep KL regularization α across six values and, for preference-based algorithms, mixing coefficient τ across four values; training runs for 50,000 steps.Source: §D.1 · p. 27

D.2 Additional experimental results

The additional-results table reports pairwise Education Dialogue preferences across methods; the appendix defines the adversarial MDP and gives a mirror-descent policy update.

D.2 Additional experimental results

  • The Education Dialogue table reports average preference for each row method over each column method, using 1,600 conversations and three seeds with means and standard deviations.Source: §D.2 · p. 27

E.1 Model

  • An adversarial MDP generalizes episodic MDPs by allowing the reward function to differ across episodes.The appendix defines its state and action spaces, horizon, initial state, transition function, and episode-specific reward.Source: §E.1 · p. 28

E.2 Algorithm 1: mirror descent policy optimization

  • Mirror-descent policy optimization begins with the reference policy and updates the policy at each iteration using a learning rate.The update is identified as the mirror-descent step for policy optimization.Source: §E.2 · p. 30

E.3 Analysis of algorithm 1

The appendix analyzes mirror-descent policy optimization and its mixture variant in regularized adversarial MDPs. It also bounds the Q-function using the reference policy’s minimum positive probability.

E.3 Analysis of algorithm 1

  • Mirror descent policy optimization satisfies a fundamental inequality for every policy and episode in a regularized adversarial MDP.Source: §E.3 · p. 30

E.4 Algorithm 2: mixture mirror descent policy optimization

  • The mixture variant starts with the reference policy and specifies an update rule for each subsequent iteration, with an explicit solution also provided.Source: §E.4 · p. 32

E.5 Analysis of algorithm 2

  • Mixture mirror descent policy optimization also satisfies a fundamental inequality for every policy and episode in a regularized adversarial MDP.Source: §E.5 · p. 32

E.6 Bounding the Q-function

  • The Q-function is bounded above by 1 and below by αH log µmin, where µmin is the reference policy’s minimum positive probability.The appendix defines µmin over state-action pairs where the reference policy assigns positive probability.Source: §E.6 · p. 33
Loading 2405.14655v2…