Source-linked AI summary
LangMARL: Natural Language Multi-Agent Reinforcement Learning
Huaiyuan Yao, Longchao Da, Xiaoou Liu, Charles Fleming, Tianlong Chen, Hua Wei
TL;DR
Global outcomes in dynamic multi-agent LLM systems provide insufficient guidance for refining individual policies, leaving credit assignment underaddressed despite its established role in MARL. LangMARL adapts centralized credit assignment and policy-gradient evolution to language space; experiments report that it consistently outperforms other self-evolving baselines across strategic games and reasoning benchmarks.
Problem
Global outcomes often provide insufficient guidance for local policy refinement, and credit assignment remains underaddressed in LLM-based multi-agent systems.
Source: §1 · p. 1Method
LangMARL uses language policies, a centralized critic for agent-specific causal credits, and language-form policy update directions and semantic optimization.
Source: §1 · p. 2, §4.4 · p. 7Results
LangMARL consistently outperforms other self-evolving baselines across strategic games and reasoning benchmarks.
Source: §6 · p. 11Takeaways & Limitations
Ablations and learning dynamics identify agent-specific credit assignment as the primary driver of optimization stability, alongside spontaneous functional specialization.
Source: §6 · p. 11Long-horizon workflows remain challenging when sparse rewards and error propagation span hundreds of steps.
Source: §6 · p. 11
Abstract
from arXiv · showhide
Large language model (LLM) agents struggle to autonomously evolve coordination strategies in dynamic environments, largely because coarse global outcomes obscure the causal signals needed for local policy refinement. We identify this bottleneck as a multi-agent credit assignment problem, which has long been studied in classical multi-agent reinforcement learning (MARL) but remains underaddressed in LLM-based systems. Building on this observation, we propose LangMARL, a framework that brings credit assignment and policy gradient evolution from cooperative MARL into the language space. LangMARL introduces agent-level language credit assignment, pioneers gradient evolution in language space for policy improvement, and summarizes task-relevant causal relations from replayed trajectories to provide dense feedback and improve convergence under sparse rewards. Extensive experiments across diverse cooperative multi-agent tasks demonstrate improved sample efficiency, interpretability, and strong generalization.
1. Introduction
LangMARL addresses the gap between static LLM-agent systems and dynamic tasks by adapting cooperative MARL credit assignment and policy optimization to language space. The introduction presents a centralized critic and agent-specific language updates as the basis for autonomous coordination, with experiments reporting effectiveness and scalability.
1. Introduction
- Dynamic LLM-agent systems lack principled adaptation, while global outcomes provide insufficient guidance for local policy refinement.The introduction frames the resulting challenge as credit assignment, a problem well studied in MARL but overlooked in LLM-based multi-agent systems.Source: §1 · pp. 1–2
- The framework is presented as a toolkit that mirrors classical MARL-library abstractions, including TorchRL, in natural language space.The figure caption frames this design as making LLM-based multi-agent optimization straightforward to implement like standard deep RL pipelines.Source: Figure 2 · p. 2
- LangMARL combines language-policy actors, a centralized trajectory critic, a language policy-gradient estimator, and a semantic policy optimizer.The critic assigns agent-specific causal credits; the estimator turns them into language-form update directions rather than numeric gradients.Source: §1 · p. 2
- LangMARL unifies self-evolution, centralized critique, and explicit credit assignment in its comparison with prompting and self-evolving paradigms.The table caption characterizes LangMARL as the most comprehensive framework in that comparison.Source: Table 1 · p. 3
- Code was not publicly available at the time of writing.Source: §1 · p. 3
- Experiments across reasoning, QA, coding, and game tasks demonstrate LangMARL’s effectiveness and scalability, with strong performance maintained across varying numbers of agents.The introduction reports these results without giving quantitative comparisons.Source: §1 · p. 3
2. Related Work
Prior LLM multi-agent systems commonly rely on static prompts or manually designed pipelines, while self-evolving methods improve agents through language feedback. The related work positions LangMARL as extending those approaches to cooperative settings where credit must be disentangled among agents.
2.1 Multi-agent LLMs
- Many multi-agent LLM systems use static prompts or manually designed pipelines, while automatic prompt engineering optimizes agents independently of cooperative dynamics.Source: §2.1 · p. 3
2.2 Prompt Optimization
- Language-feedback methods improve prompts, pipelines, or agent workflows, but prior self-evolving approaches do not disentangle credit among multiple agents.LangMARL extends these paradigms to multi-agent systems by introducing credit assignment.Source: §2.2 · p. 3
3. Preliminaries
The preliminaries formulate cooperative MARL around shared rewards and decentralized policies, then describe centralized training with decentralized execution. They frame credit assignment as constructing agent-specific learning signals from team outcomes.
3.1 Cooperative MARL
- Cooperative MARL models agents sharing a team objective in a Dec-POMDP, with a shared reward and decentralized policies optimized for expected discounted return.Source: §3.1 · p. 4
3.2 Centralized Training with Decentralized Execution
- Under CTDE, agents act from local observations at execution, while a centralized critic may use global state and joint actions to evaluate team return.Source: §3.2 · p. 4
3.3 Credit Assignment in Cooperative MARL
- Credit assignment constructs agent-specific learning signals from a shared team reward to reflect each agent’s contribution and inform its policy update.The preliminaries make the design of each signal central to attributing team-level performance to agents.Source: §3.3 · p. 4
4. Method: Natural Language MARL
LangMARL adapts cooperative MARL to language-based multi-agent systems through centralized credit assignment and natural-language policy optimization. Its CTDE design separates training with trajectory-level information from decentralized agent execution.
4. Method: Natural Language MARL
- LangMARL combines language policy actors, a centralized language critic, and a language policy optimizer in a MARL-inspired framework.The framework’s overview describes these components as the core of its natural-language optimization approach.Source: §4 · p. 4, Figure 3 · p. 5
4.1 Language CTDE Paradigm
- During training, the critic uses the complete episodic trajectory to assign agent-specific causal credits; at execution, agents act independently using only their language policies.The framework follows centralized training with decentralized execution.Source: §4.1 · p. 5
4.2 Language Policy Actor
- Each agent is an LLM with a language policy that selects actions from its observation and available action descriptions.Policy parameters are encoded in natural-language instructions, rules, or exemplars rather than numeric vectors.Source: §4.2 · p. 5
7: # Language Policy Gradient Estimation
The procedure computes a language gradient for each agent.
13: #Language Policy Optimization
LangMARL uses a centralized language critic to assign trajectory-level credits, then turns agent-specific experience into language-form policy updates. Multiple trajectory-level update directions are aggregated before an LLM optimizer applies the resulting update.
4.3 Centralized Language Critic for Credit Assignment
- The centralized critic consumes the complete episodic trajectory and attributes individual agent contributions rather than estimating a scalar value function.This evaluation uses complete episodic rollouts without temporal-difference bootstrapping.Source: §4.3 · p. 6
4.4 Language Policy Gradient Estimator
- The LLM-based gradient estimator conditions on an agent’s policy, state–action sequence, and trajectory credit to produce a language-form update direction.It serves as a language-space analogue of policy gradient estimation without computing numeric gradients.Source: §4.4 · pp. 6–7
4.5 Language Policy Optimizer
- LangMARL aggregates trajectory-level language gradients into a single update direction, then applies that update to the agent’s policy using LLM operators.The aggregation semantically integrates suggestions by finding consistent patterns, resolving conflicts, and suppressing noisy or idiosyncratic gradients.Source: §4.5 · p. 7
13: #Language Policy Optimization
- The resulting procedure separates gradient aggregation from policy updating in a batch actor–critic style optimization process.The algorithm specifies updating each agent’s language policy after computing the language gradient.Source: §13 · p. 6, §4.5 · p. 7
5. Experiments
LangMARL is evaluated on cooperative language tasks and strategic games, against prompting and self-evolving baselines. The experiments test overall performance, credit assignment quality, and robustness to model backbones and rollout budgets.
5.1 Environment Settings
- The evaluation spans fixed-role strategic games and cooperative language tasks reframed as multi-agent reinforcement learning problems.Overcooked-AI and partially observable Pistonball represent strategic games; HumanEval, HotPotQA, and MATH represent coding, reasoning, and mathematics tasks.Source: §5.1 · p. 8
5.2 Baselines and Comparisons
- LangMARL is compared with fixed-prompt methods and prompt-optimization approaches, including methods that refine agents independently or use team-level signals.The baselines include CoT, Agents, AutoPE, DSPy, Reflexion, TextGrad, and Symbolic Learning.Source: §5.2 · pp. 8–9
5.3 Results of Overall Performance (RQ1)
- LangMARL outperforms static prompting and self-evolving baselines across benchmarks, with gains on reasoning tasks and strong results in strategic games.It achieves the highest mean reward across Overcooked-AI layouts and maintains positive returns in Pistonball as teams scale to N = 20.Source: §5.3 · pp. 9–10
5.4 Credit Assignment Quality (RQ2)
- Removing explicit agent-wise credit assignment and using shared global rewards lowers performance, while centralized credit assignment supports faster convergence and higher final performance.Without credit assignment, learning also becomes unstable and can plateau suboptimally.Source: Figure 4 · p. 9, §5.4 · p. 10, Figure 7 · p. 10
- LangMARL induces complementary roles without predefined role assignments, including implementation by one coding agent and review and refinement by the other.In strategic games, the critic also identifies and addresses resource-placement needs and piston-caused geometric blockages.Source: Figure 5 · p. 9, §5.4 · pp. 10–11
5.5 Sensitivity Analysis (RQ3)
- Across Coord. Ring and Forced Coord. layouts, LangMARL achieves higher mean rewards than the strongest baselines across tested LLM backbones.Gemini-3-Flash reaches peak performance, while LLaMA-3.3-70B remains competitive.Source: Figure 6 · p. 10, §5.5 · p. 11
- Increasing rollout budgets consistently improves HumanEval, but in Pistonball the benefit depends on team size and can plateau for large teams.For N = 10 or 20, performance initially improves and then plateaus; excessive rollouts can exacerbate policy bias.Source: Figure 6 · p. 10, §5.5 · p. 11
6. Conclusion
LangMARL consistently outperforms self-evolving baselines, with agent-specific credit assignment supporting stable optimization and spontaneous functional specialization. The conclusion identifies long-horizon workflows and fixed agent topologies as remaining challenges.
6. Conclusion
- LangMARL consistently outperforms other self-evolving baselines, while agent-specific credit assignment is the primary driver of optimization stability and enables spontaneous functional specialization.The reported gains are robust across diverse LLM backbones.Source: §6 · p. 11
- Long-horizon workflows remain challenging when sparse rewards and error propagation across hundreds of steps attenuate the causal link between an intervention and its outcome.The authors propose hierarchical decomposition into semantic sub-goals as a direction for future work.Source: §6 · p. 11
- The framework uses a pre-defined agent topology, which may limit adaptability in collaboration requiring fluid organizational structures.The authors identify dynamic task partitioning and agent synthesis as future directions.Source: §6 · p. 12
A.1 Paradigm Comparison
The comparison contrasts prior systems’ global or shared feedback with LangMARL’s agent-specific credit assignment. It presents that granular feedback as a way to address coordination failures and support functional specialization.
A.1 Paradigm Comparison
- LangMARL decomposes global trajectories into agent-specific language gradients that capture causal dependencies, unlike approaches relying on global outcomes or joint feedback.The passage contrasts this with Auto Prompt Engineer’s black-box updates, Reflexion’s monolithic shared reflections, and TextGrad and Symbolic’s global evaluations.Source: §A.1 · p. 15
- Global or monolithic feedback can leave agents unable to identify their individual contributions, while joint feedback can modify a high-performing agent’s policy for a teammate’s mistake.The passage describes the latter as “credit drift” in tasks such as Overcooked or Pistonball.Source: §A.1 · p. 15
- LangMARL’s localized guidance is presented as preventing coordination collapse and enabling the functional specializations observed in the experiments.Source: §A.1 · p. 15
A.2 Detailed Implementation of Experience Collection
LangMARL collects decentralized language-policy experience, evaluates trajectories centrally, and uses agent-specific feedback to refine policies. The appendix describes the environments, learning dynamics, prompt operators, and qualitative examples illustrating this process.
A.2 Detailed Implementation of Experience Collection
- Each training iteration runs K independent rollouts, with agents selecting discrete actions from their own language policies using textual states that include observations and possible communication history.The decentralized collection stage operationalizes execution under the CTDE paradigm.Source: §A.2 · p. 15
A.3 Environment Settings
- Overcooked-AI uses partial symbolic observations, hierarchical semantic-subgoal and primitive-action policies, and sparse team rewards; Pistonball uses 10–20 agents with local pixel observations and a shared progress-and-time reward.The Overcooked layouts range from collision-prone navigation to coordination and ingredient-passing challenges.Source: §A.3 · pp. 16–17, Figure 9 · p. 16
A.4 Learning Dynamics across Overcooked Scenarios
- Across Overcooked layouts, LangMARL’s trajectory-based credit assignment supports role discovery and steadier reward gains on coordination-intensive tasks.The examples include resolving spatial conflicts, dividing labor, transferring materials, and coordinating item passing.Source: Figure 10 · p. 16, §A.4 · p. 17
A.5 Prompt Templates
- The prompt templates define actors, a centralized critic, a language-gradient estimator, and an optimizer that combines gradients across scenarios to refine each agent’s policy.The critic receives the joint trajectory and team reward; the estimator turns agent-specific credits into policy changes.Source: §A.5 · pp. 18–19
A.6 Qualitative Demonstrations and Case Studies
- In Overcooked, the critic attributes a cooking delay to Player Green’s resource prioritization; in Pistonball, it identifies a piston whose timing blocks the ball and guides an earlier downward move.The examples show targeted policy updates rather than undirected changes to both agents.Source: §A.6 · pp. 19–20
A.7 AI usage
- The authors report using LLMs to assist with code implementation and manuscript grammar and style, with final content, technical contributions, and analyses reviewed and verified by the authors.Source: §A.7 · p. 20