PaperlayerView exact revision on arXiv

Source-linked AI summary

ArCHer: Training Language Model Agents via Hierarchical Multi-Turn RL

Yifei Zhou, Andrea Zanette, Jiayi Pan, Sergey Levine, Aviral Kumar

arXiv:2402.19446v1cs.LGcs.AIcs.CL

TL;DR

Multi-turn LLM agents need to seek information, assign credit across turns, and reason over delayed rewards, capabilities that single-turn RL methods do not provide. ArCHer uses hierarchical RL to learn an off-policy utterance-level value function alongside a token-level policy. It reports 100x greater sample efficiency than on-policy methods, better convergence than off-policy methods, and favorable scaling to 7B parameters.

  • Problem

    Single-turn RL methods do not support effective multi-turn information seeking, long-term credit assignment, or reasoning about past actions in agent tasks.

  • Method

    ArCHer runs off-policy value-based RL over utterances in parallel with a low-level policy-gradient algorithm that trains token generation within each turn.

  • Results

    100x greater sample efficiency than on-policy methods such as PPO and better converged performance than off-policy methods were reported across online agent tasks.

  • Takeaways & Limitations

    ArCHer provides a simple, extensible framework that scales favorably across RL components, transformer architectures, and larger base models.

  • Takeaways & Limitations

    Most experiments used relatively small GPT-2 models and computational-reward tasks requiring thousands of interactions; broader large-model and human-interaction evaluation remains future work.

Abstract

from arXiv · show

A broad use case of large language models (LLMs) is in goal-directed decision-making tasks (or "agent" tasks), where an LLM needs to not just generate completions for a given prompt, but rather make intelligent decisions over a multi-turn interaction to accomplish a task (e.g., when interacting with the web, using tools, or providing customer support). Reinforcement learning (RL) provides a general paradigm to address such agent tasks, but current RL methods for LLMs largely focus on optimizing single-turn rewards. By construction, most single-turn RL methods cannot endow LLMs with the ability to intelligently seek information over multiple turns, perform credit assignment, or reason about their past actions -- all of which are critical in agent tasks. This raises the question: how can we design effective and efficient multi-turn RL algorithms for LLMs? In this paper, we develop a framework for building multi-turn RL algorithms for fine-tuning LLMs, that preserves the flexibility of existing single-turn RL methods for LLMs (e.g., proximal policy optimization), while accommodating multiple turns, long horizons, and delayed rewards effectively. To do this, our framework adopts a hierarchical RL approach and runs two RL algorithms in parallel: a high-level off-policy value-based RL algorithm to aggregate reward over utterances, and a low-level RL algorithm that utilizes this high-level value function to train a token policy within each utterance or turn. Our hierarchical framework, Actor-Critic Framework with a Hierarchical Structure (ArCHer), can also give rise to other RL methods. Empirically, we find that ArCHer significantly improves efficiency and performance on agent tasks, attaining a sample efficiency of about 100x over existing methods, while also improving with larger model capacity (upto the 7 billion scale that we tested on).

1. Introduction

LLM agent tasks require sequential decisions over multiple turns, but prevailing single-turn RL methods struggle with long-term credit assignment and information seeking. ArCHer addresses this with hierarchical multi-turn RL that combines off-policy value learning with token-level policy optimization.

  • LLM agents must make sequences of intelligent decisions across interactions with environments, tools, websites, or people.
  • Single-turn objectives often fail to assign credit to actions whose benefits emerge later and do not promote information-seeking behavior.
  • Multi-turn RL is costly because online interaction is slow and expensive, while PPO cannot effectively reuse data from past interactions.
  • ArCHer trains an utterance-level value function with off-policy temporal-difference learning and a token-level policy with an on-policy policy-gradient algorithm.
  • 100x greater sample efficiency than on-policy methods such as PPO, with better converged performance than off-policy methods, was reported across online agent tasks.

2. Related Work

Prior language-agent methods include single-turn RL, prompting, supervised approaches, and off-policy value-based methods. These approaches face limitations involving myopic objectives, expensive supervision, long token horizons, or restricted policy improvement.

  • Single-turn RL methods optimize one decision without further environmental interaction, commonly using policy-gradient or offline optimization algorithms.
  • Prompting methods such as ReAct, Reflexion, and Voyager support sequential decision-making without updating the language model’s parameters.
  • Supervised approaches require expensive manual labels or tool-call annotations, while discovering successful long-horizon rollouts automatically can also be prohibitively costly.
  • Token-level off-policy methods face very long horizons, whereas utterance-level methods using frozen-model candidates slow policy improvement.
  • ArCHer addresses both limitations by running hierarchical RL algorithms in parallel.

3. Actor-Critic Framework with a Hierarchical Structure (ArCHer)

ArCHer formulates language generation as a hierarchical MDP with utterances as high-level actions and tokens as low-level actions. It combines an off-policy utterance critic with token-level policy optimization, while supporting variance reduction and offline variants.

  • 3.1. Language Generation as a Hierarchical MDP: ArCHer represents language interaction as a hierarchical MDP whose high-level actions are token sequences and whose low-level actions are individual tokens.
  • 3.1. Language Generation as a Hierarchical MDP: The low-level policy generates up to L tokens and receives the high-level Q-value as its terminal reward, ending when it emits EOS.
  • 3.1. Language Generation as a Hierarchical MDP: In the practical construction, each utterance is one high-level action, while its tokens form the embedded low-level action sequence.
  • 3.4. A Practical Instantiation of ArCHer for Sample-Efficient Online RL: The framework separates environment interaction at the high level from in-silico low-level optimization against the learned high-level value function.
  • 3.4. A Practical Instantiation of ArCHer for Sample-Efficient Online RL: The utterance critic learns Q and V models with Bellman targets and replayed prior interactions, while the token actor uses advantage-weighted policy gradients.
  • 3.5. Other Practical ArCHer Algorithms: ArCHer also supports token-level variance reduction with a baseline and offline training using IQL-style expectile regression without explicit action maximization.

4. Theoretical Analysis

ArCHer’s hierarchical design offers weaker convergence requirements and lower worst-case statistical error than token-level critics. The analysis attributes this advantage to evaluating at the utterance scale, where errors do not accumulate across every token.

  • Conditions for convergence: ArCHer requires weaker convergence conditions for critic capacity than off-policy token-level methods.The analysis focuses on Bellman completeness and offline-data coverage as the relevant conditions.
  • Conditions for convergence: Utterance-level critics need less function-class capacity because they model arbitrary functions at a coarser timescale than token-level critics.Token-level critics must remain flexible at the next-token resolution, whereas utterance-level critics operate over complete utterances.
  • Conditions for convergence: Token-level and utterance-level critics require identical offline-data coverage under the density-ratio condition.A dataset covering a trajectory at one level also covers it at the other because both levels induce the same trajectory distribution.
  • Statistical error analysis with finite samples: Utterance-level critics provide more accurate advantage estimates because token-level estimation errors accumulate across an utterance.Theorem 1 compares statistical error in equivalent utterance-level and token-level MDPs.
  • Statistical error analysis with finite samples: For utterances of up to 64 tokens and discount factors above 0.95, the worst-case token-level error can be much larger than utterance-level error.The paper attributes this gap to the factor γ^L arising from error accumulation across tokens.

5. Experiments

Experiments evaluate ArCHer-derived hierarchical RL methods across multi-step language-agent tasks, comparing them with on-policy, off-policy, and imitation-learning baselines. ArCHer generally achieves stronger performance, uses off-policy data effectively, and benefits from larger actor models.

  • Overall results: ArCHer converges to better performance than prior methods on four harder tasks, including Twenty Questions Subset, Twenty Questions, Guess My City, and WebShop.These tasks require identifying hidden information or handling diverse initial states.
  • Overall results: On WebShop, ArCHer fine-tuning of GPT2 outperforms prompting strategies applied to GPT-3.5, including an expert-written prompt and ReAct.The comparison includes several effective prompting strategies for the stronger base model.
  • Online sample efficiency: ArCHer reaches an average return just above -17 with fewer than 1000 samples, whereas PPO requires more than 100k samples, implying at least a 100x sample-efficiency improvement.PPO also required at least 1024 on-policy rollouts per gradient step to improve stably on Twenty Questions.
  • Baseline comparisons: Filtered BC converges quickly but often remains suboptimal, while ArCHer improves steadily with additional samples; CHAI initially improves faster but often finishes worse.The authors attribute CHAI's narrower improvement margin to reranking samples from a frozen behavior policy.
  • Off-policy data: Replay buffers containing only the most recent 48 rollouts produce unstable learning, whereas larger buffers improve stability and performance without meaningful gains beyond a certain size.The smaller-buffer instability is described as likely arising from overfitting on limited data.
  • Model scaling: Replacing RoBERTa with GPT2 for the critic preserves later learning behavior, while replacing GPT2 with Mistral7B for the actor makes ArCHer solve Twenty Questions Subset much faster.The Mistral7B actor did not require supervised fine-tuning because its open-source checkpoint already achieved non-trivial zero-shot rewards.

6. Discussion and Conclusion

ArCHer is a hierarchical framework for multi-turn LLM reinforcement learning that operates simultaneously at utterance and token levels. It reduces task horizons while preserving a compact token-level action space, and shows strong empirical performance, though most experiments use small GPT-2 models.

  • Framework: ArCHer runs two reinforcement-learning algorithms simultaneously at utterance and token levels for multi-turn LLM agent tasks.The framework is designed to reduce task horizons while retaining token-level actions.
  • Framework: ArCHer reduces task horizons while preserving a compact token-level action space.This combination is presented as making LLM training more practical, efficient, and effective for decision-making tasks.
  • Empirical findings: ArCHer significantly outperforms prior LLM reinforcement-learning methods across online tasks and scales favorably with more capable base models and design improvements.The reported empirical conclusion covers both performance and scaling behavior.
  • Limitations: Most experiments use a relatively small GPT-2 architecture because computational constraints limited trials across algorithms and ArCHer instantiations.A Mistral7B result shows favorable scaling, but broader evaluation with larger models and benchmarks remains future work.

A. Environment and Dataset Details

The experiments cover several text-based agent environments, including detective gameplay, question-answering tasks, city guessing, and web shopping. The section also documents environment mechanics, reward structures, and PPO comparison details.

  • Environments: The study includes Detective Game, Twenty Questions, Twenty Questions Subset, Guess My City, and Web Shopping environments.These tasks span game interaction, constrained dialogue, hidden-word or city guessing, and external-tool use.
  • Environments: Detective Game requires free-form actions parsed by a game engine, with a 60-step timeout and an optimal policy solving in 51 steps for reward 360.Observations include surroundings, carried items, previous-action feedback, and available actions.
  • Environments: Twenty Questions tasks require guessing hidden words within 20 questions using yes/no oracle responses, with rewards from -20 to 0.The Subset variant uses 10 possible words and tests whether algorithms adapt to a shortcut in the task.
  • Environments: Guess My City asks agents to identify a hidden city from 100 possibilities within 20 questions, while Web Shopping requires tool-mediated item purchases.The Web Shopping interaction involves searching, selecting an item, and using item features and attributes.
  • PPO comparison: PPO improves over the SFT checkpoint but requires at least 1024 on-policy trajectories per update because it cannot reuse past off-policy data.The reported PPO learning curves cover Twenty Questions, Twenty Questions Subset, and Guess My City.

C.2. Additional Reproduction Details for WebShop Experiment

The WebShop reproduction uses the ReAct environment and its original few-shot prompting baselines, with a newer language model replacing the deprecated model from the original study. The expert-prompt baseline remained comparable, whereas ReAct underperformed with the replacement model.

  • Baselines: The WebShop experiment uses the ReAct environment and its original ReAct and Act-only few-shot prompting strategies.The paper labels the Act-only strategy as expert-prompt in its results.
  • Baselines: The ReAct strategy lets the agent articulate reasoning before acting, whereas Act-only omits this reasoning step.The original prompts were used without modification and reproduced in Figures 8 and 9.
  • Evaluation: The evaluation uses webshop indices 2000 to 2100 to establish the LLM-based few-shot baselines.This evaluation setup is described as part of the WebShop reproduction.
  • Results: With gpt-3.5turbo-instruct, expert-prompt performance was comparable to the best text-davinci-002-based method, while ReAct underperformed significantly.The model switch followed deprecation of text-davinci-002 by OpenAI.

D. Additional Experimental Results

Additional ablations examine temporal-difference learning and an IQL critic within ArCHer. TD learning is necessary for reliable off-policy use, while naive online IQL accelerates simple-task exploration but can become unstable on harder tasks.

  • TD-learning ablation: Replacing ArCHer’s TD-learning critic update with Monte Carlo regression may accelerate early learning but fails to learn reliably throughout training.The ablation uses a smaller replay buffer containing trajectories from the three latest policies.
  • TD-learning ablation: The TD-learning ablation indicates that temporal-difference learning is important for effectively using off-policy data.The conclusion follows from Monte Carlo regression’s unreliable full-training behavior.
  • IQL critic ablation: An IQL critic with τ=0.9 accelerates exploration in simple tasks such as Detective Game.The setting was chosen to encourage more risk-seeking behavior for exploration.
  • IQL critic ablation: Naive online IQL can produce unstable behavior on harder tasks such as Twenty Questions because it does not provide an unbiased policy-gradient estimate.The ablation contrasts exploration benefits in simple tasks with instability in harder ones.

E. Reward Hacking

The trajectories show that ArCHer often learns strategic, natural interaction, but can exhibit reward-hacking behaviors such as repeated questions or collapse under out-of-distribution responses.

  • Successful Twenty Questions trajectories are mostly natural and strategic, while some unsuccessful trajectories repeat the same question.
  • ArCHer learns a near-optimal binary search strategy in Twenty Questions Subset.
  • In Guess My City, the agent asks about the predominant language, but free-form out-of-distribution oracle responses make collapse more likely.
  • ArCHer’s WebShop behavior is described as very natural.

F. Hyperparameters

ArCHer uses mostly shared hyperparameters across environments, while its framework combines utterance-level and token-level MDPs for hierarchical learning.

  • Most ArCHer hyperparameters are held constant across environments, with exceptions for actor learning rate and WebShop rollout count.Twenty Questions uses a smaller actor learning rate, while Web Shopping uses more rollout trajectories.
  • The token-level MDP uses discount factor γ1/L and states that include the utterance-level state plus the generated token prefix.
  • The hierarchical construction treats each utterance as a high-level action and each token within it as a low-level action.The token-level MDP is embedded within one utterance and receives reward at the utterance end from the utterance-level critic.
  • Its theoretical analysis uses Bellman completeness and density-ratio assumptions, with fitted policy evaluation iterated over independent datasets.

G.4. Proof of Main Theorem

The proof analyzes fitted policy evaluation at utterance and token levels under stated assumptions, relating statistical error, effective sample size, and the resulting suboptimality gaps.

  • Lemma 3 provides a high-probability guarantee for the value function returned by fitted policy evaluation with N = MK effective samples.
  • Theorem 1 bounds the utterance-level Q-function suboptimality gap under utterance-level Bellman completeness and density-ratio assumptions.
  • The analysis bounds value and advantage estimation errors using Bellman-error terms, Jensen’s inequality, and the effective token-level sample count NL.
  • The proof compares token-level and utterance-level discount factors through the identity relating 1 − γ to 1 − γ1/L.
  • The analysis relies on Bellman completeness, density-ratio control, bounded function values, and standard least-squares generalization results.
Loading 2402.19446v1…