LangMARL: Natural Language Multi-Agent Reinforcement Learning via Semantic Credit Assignment

Most multi-agent LLM systems rely on hand-engineered prompts and static configurations, so agents cannot evolve their strategies as the task distribution shifts. When these systems do try to self-improve, they optimize against a single global outcome — a team-level success or failure — through global reflections or monolithic prompt rewrites. That signal simply is not informative enough: it never says which agent needs adjusting, which leads to inefficient learning or outright coordination collapse.

Classical MARL solved exactly this problem decades ago, with counterfactual baselines, value decomposition, and the centralized training, decentralized execution (CTDE) paradigm. But those tools assume numeric gradients over differentiable parameters. LLM agents are black boxes whose "parameters" are natural-language instructions. LangMARL closes that gap by re-deriving each MARL component in language space.

LangMARL follows a language CTDE loop. During training, a centralized critic sees the full episodic trajectory and attributes the outcome to individual agents in natural language. At execution time, each agent acts alone from its own language policy, with no access to global state or feedback. Four components mirror the standard actor–critic stack:

LangMARL is packaged so that building an LLM multi-agent optimizer feels like writing a standard deep-RL pipeline. The abstractions map one-to-one onto familiar MARL library components — only the underlying representation changes from tensors to text.

We evaluate on two families of environments: cooperative language tasks (HotPotQA, MATH, HumanEval, reframed as multi-agent RL problems) and strategic games with fixed roles and physical constraints (Overcooked-AI and Pistonball). LangMARL achieves the best result on every benchmark, against both static prompting and self-evolving baselines.

Because credits are asymmetric — the critic praises one agent and corrects another — optimization pressure breaks the initial symmetry between identically-prompted agents. Over five epochs of collaborative coding, two generic problem solvers self-organize into complementary roles: Agent 1 specializes in structured implementation, Agent 2 in critical review and refinement. No role was ever specified in the prompt.

LangMARL is backbone-agnostic. Across GPT-4o-mini, Gemini-3-Flash, and the open-weight LLaMA-3.3-70B, it beats the strongest baseline on both Coordination Ring and Forced Coordination — Gemini-3-Flash gives peak performance, while LLaMA-3.3-70B stays competitive.

Rollout budget behaves differently with scale. On few-agent tasks like HumanEval, more rollouts monotonically help. In large Pistonball teams the gain plateaus: beyond a point, extra rollouts amplify policy bias rather than coverage, so there is an optimal rollout frequency that shrinks as agent density grows.

Long-horizon agentic tasks. In workflows spanning hundreds of steps, such as autonomous software development, sparse rewards and error propagation attenuate the causal link between an intervention and the final outcome. Hierarchically decomposing long trajectories into semantic sub-goals would let the critic give more granular feedback.

Dynamic sub-agent synthesis. LangMARL currently operates over a pre-defined agent topology. We are working toward on-the-fly synthesis of specialized sub-agents, with dynamic task partitioning and evolving communication protocols.

From policies to skills. LangMARL optimizes each agent's policy text. MASkills extends the same language-space policy-gradient view to a richer unit of procedural knowledge — reusable, transferable agent skills.