Policy-Conditioned Policies for Multi-Agent Task Solving

本文是对论文的通俗导读，由 Claude Code 生成，作者审校。

TL;DR

• What: A paradigm shift for multi-agent learning: represent policies as human-readable source code, let agents hand each other their code before acting, and use an LLM as an approximate interpreter that reads the opponent’s policy and writes the best response. This operationalizes game theory’s Program Equilibrium (Tennenholtz, 2004) in practical multi-agent tasks, extending it beyond matrix games.
• Why: Deep RL policies are opaque, high-dimensional weight vectors; conditioning on them is computationally prohibitive and semantically ill-defined (the “representational bottleneck”). Code is compressed, semantically dense, and exactly the modality LLMs are built to read; exchanging it eliminates policy drift and infinite “I model you modeling me” recursion.
• How: Programmatic Iterated Best Response (PIBR): the LLM acts as a point-wise best-response operator that iteratively synthesizes and refines the ego agent’s policy code against the opponent’s fixed code, optimized by textual gradients with two feedback signals: game utility from rollouts and runtime unit tests from sandboxed execution.
• Results: Instantly locks onto the optimal equilibria in coordination matrix games (Vanilla Coordination 6.0, Climbing 22.0, Penalty 20.0, despite miscoordination penalties as harsh as −30), and produces genuinely nontrivial policies for cooperative Level-Based Foraging, where sampled episodes occasionally approach the empirical optimum but stability is still work in progress.
• Fun: The generated policies negotiate through their code comments (“I am committing to cooperation. Please match me.”), and the other agent reads it and complies.

Intuition

Your teammate’s policy is millions of floating-point numbers. You can’t read it, they can’t read yours, so both of you are stuck guessing each other from noisy interaction history. Since both keep learning, the data never comes from a stable target. This is the daily misery of multi-agent RL: non-stationarity, policy drift, and recursive reasoning without a natural stopping level.

Game theory proposed a radical fix back in 2004: let programs read each other’s source code. Program Equilibrium showed that code transparency enables cooperation impossible for black-box players: the famous FairBot construction (Barasz et al., 2014) cooperates in a one-shot Prisoner’s Dilemma by formally proving the opponent will cooperate, via Löb’s theorem $\square(\square P \to P) \to \square P$. For twenty years this stayed a logician’s construction: verifying what an arbitrary program does is undecidable (Rice’s theorem), and proof-based bots are brittle to trivial syntactic changes.

Our observation: LLMs are the sloppy-but-working interpreter this theory has been waiting for. An LLM cannot prove what your code does, but it can read it, infer its meaning, and write code that best-responds to it. This relaxes undecidable proof-checking into practical semantic inference. Learning is thereby lifted from policy space to operator space: like the differential operator maps a function $f$ to $f’$, the LLM maps an opponent’s policy-as-code to the ego agent’s policy-as-code. Iterating this operator between agents, fictitious-play style, walks the pair into program equilibria that black-box learning cannot reach.

Resources

• Policy-Conditioned Policies for Multi-Agent Task Solving.
  Yue Lin, Shuhui Zhu, Wenhao Li, Ang Li, Dan Qiao, Pascal Poupart, Hongyuan Zha, Baoxiang Wang.
  arXiv preprint, 2025. Technical report.

  [Manuscript]

Related reading on this blog: Information Design in MARL, Verbalized Bayesian Persuasion, Classic Games.

What We Did

1. The Problem

Conditioning your policy on the opponent’s actual policy, rather than on a guess estimated from history, is the theoretically clean answer to multi-agent non-stationarity. With neural policies it collides with two curses. The curse of dimensionality: feeding one network’s millions of parameters into another network blows up recursively. The curse of representation: weights are non-unique and permutation-invariant, so “the same policy” has countless encodings and no readable semantics. Classic Program Equilibrium avoids neither in practice, because its formal-verification route is undecidable and brittle.

2. From Weights to Code

• Programmatic policies. Each agent’s policy is executable Python: compressed, structured, and semantically dense. Agents exchange exact source code before acting (encoder = source extractor, decoder = identity), which removes policy drift and recursive reasoning at the root; this full-transparency setting is natural for cooperation and zero-sum self-play.
• LLM as approximate interpreter and best-response operator. The operator $\varphi^i$ takes the opponent’s code (in the prompt) and emits the ego agent’s best-response code. Policy adaptation becomes an interpretable meta-programming task.
• PIBR (Programmatic Iterated Best Response). An outer loop alternates agents for $K$ rounds, each computing a programmatic best response to the opponent’s fixed code; the returned profile is the highest-social-welfare pair found. Each best response is an inner loop of $T$ textual gradient steps (TextGrad), driven by a composite loss:

\[\mathcal{L} = \mathcal{L}_{\text{test}} + \mathcal{L}_{\text{utility}}, \qquad \mathcal{L}_{\text{utility}} = -J\left(G,\ \pi^i,\ \pi^{-i}\right).\]

• Two feedback channels. Unit-test feedback: the generated code runs in a sandbox, and error traces become high-priority debugging feedback. Utility feedback: full rollout trajectories (states, joint actions, everyone’s rewards) tell the operator how to rewrite the code for higher expected utility.

3. What Happens

Social welfare vs. textual-gradient steps (o4-mini). Top: Vanilla Coordination and Climbing, pinned at the optima 6.0 and 22.0 from the start. Bottom-left: Penalty Game, optimal 20.0 within one update. Bottom-right: cooperative Level-Based Foraging, where episodes approach the empirical optimum (red line) but the mean remains unstable; gaps mark steps where generated code failed to run.

• Coordination matrix games: in Vanilla Coordination, Climbing, and Penalty (with $p = -2$), PIBR locks onto the optimal equilibria essentially immediately, including the risky 11/11 equilibrium of the Climbing Game, where miscoordination costs −30. Code transparency makes commitment credible, so the lucrative-but-dangerous equilibria become playable.
• Cooperative Level-Based Foraging: the LLM writes policies with real algorithmic content: opponent-intent tracking over a 5-step window, softmax food targeting with annealed temperature, and deadlock-avoidance fallbacks, none of it hand-written. Sampled episodes occasionally approach the empirical optimum, though the mean trajectory is still high-variance; we say so plainly in the paper, and robustness improvements are under active development.
• Emergent negotiation-in-code: final Climbing policies are one-liners returning the cooperative action with a comment addressed to the opponent: “I am committing to cooperation. Please match me.” The commitment is written into the very artifact the other agent reads.

Concurrent Works

The idea that “LLMs can make program equilibrium practical” seems to have been in the air in 2025–2026: several groups landed on closely related insights independently.

Evaluating LLMs in Open-Source Games (NeurIPS 2025)

Sistla and Kleiman-Weiner, Evaluating LLMs in Open-Source Games, NeurIPS 2025, is the contemporaneous work our paper discusses in a dedicated section. Both works share the core contribution: LLMs as approximate interpreters that bridge theoretical Program Equilibrium and practice, using code transparency to enable conditional cooperation that black-box policies cannot achieve. Chronologically, they made this contribution first, and we say so explicitly. Our paper differs in three ways: (1) it is motivated from MARL’s representational bottleneck rather than LLM evaluation; (2) it treats the LLM as a formally definable operator and optimizes it (PIBR with textual gradients, utility feedback, and runtime unit tests) instead of relying on prompted reasoning alone; (3) it validates beyond matrix games, on Level-Based Foraging with spatial and sequential structure. Acknowledging their precedence, we released this version as a technical report rather than a conference submission, to keep the timeline of the independent contribution clean.

Code-Space Response Oracles (Google DeepMind, AAMAS 2026)

Hennes, Li, Schultz, and Lanctot (Google DeepMind), Code-Space Response Oracles: Generating Interpretable Multi-Agent Policies with Large Language Models, AAMAS 2026 extended abstract, is a concurrent work I found after our release, from the team behind PSRO and OpenSpiel. Extending their earlier LLM-PSRO line (Bachrach et al., 2025), CSRO replaces PSRO’s deep-RL best-response oracle with Gemini 2.5 Pro synthesizing commented Python policies, conditioned on the opponent population’s source code (or LLM-written summaries), refined by utility-scored regeneration or AlphaEvolve-style evolutionary search. On repeated Leduc hold’em it reaches exploitability competitive with CFR+ while exploiting an always-calling opponent far harder, and on repeated Rock–Paper–Scissors it massively outperforms PSRO with an IMPALA oracle.

The two papers are complementary instantiations of the same code-space move. CSRO targets Nash equilibria of zero-sum games via a population meta-game, and opponent code is prompt context for the oracle; our work targets program equilibria for cooperation via pairwise iterated best response, where reading the opponent’s code is part of the solution concept itself. Different halves of game theory, same message: policies you can read are policies you can respond to.