Hierarchical, Symbolic, Language, and Multi-Agent Planning › Coordination, opponents, and nested beliefs

Other agents introduce joint actions, private information, and strategic dependence. A Markov game's transition kernel can remain stationary when all policies are fixed. From one independent learner's perspective, however, the induced dynamics become nonstationary when teammates or opponents update their policies. Explicit opponent modeling is useful when adaptation to particular agents matters, but robust policies, self-play, population training, and centralized planning need not expose an opponent model as a named state variable.

A fully observed multi-agent decision problem can be written as a stochastic (Markov) game, introduced by Shapley (1953) and adopted as a multi-agent reinforcement-learning framework by Littman (1994):

$$\mathcal{G} = \langle \mathcal{S}, \{\mathcal{A}_i\}_{i=1}^N, P, \{r_i\}_{i=1}^N, \gamma \rangle$$

where:

• $\mathcal{S}$: the shared state space of the environment
• $\mathcal{A}_i$: the action space of agent $i$, with $N$ the number of agents
• $P(s' \mid s, a_1, \dots, a_N)$: the transition kernel, which depends on the joint action of all agents
• $r_i: \mathcal{S} \times \mathcal{A}_1 \times \cdots \times \mathcal{A}_N \to \mathbb{R}$: the reward function for agent $i$
• $\gamma \in [0, 1)$: the discount factor shared by all agents

Each action may affect the shared transition and other agents' outcomes. When $N=1$, the tuple reduces to an MDP. Under partial observability, agent $i$ receives observation $o_i$ and conditions its policy on a local history $h_i^t=(o_i^0,a_i^0,\ldots,o_i^t)$ rather than on the shared state. A decentralized planner must therefore reason about joint behavior without assuming that every actor sees the same information.

The value of one action can depend on what others do and on what they believe about the focal agent. Rock-paper-scissors provides a minimal warning: against an adaptive opponent, a deterministic policy is exploitable, while the equilibrium mixed strategy randomizes uniformly.

The standard tools for reasoning in these settings include:

• Nash equilibrium, where no agent can improve by a unilateral deviation, for strategic interactions generally Nash (1951);
• subgame-perfect equilibrium for extensive-form games, requiring a Nash equilibrium in every proper subgame;
• level-$k$ or cognitive-hierarchy reasoning, where level 0 is a specified nonstrategic baseline and higher levels respond to lower levels Camerer, Ho, and Chong (2004);
• Opponent modeling as a supervised learning problem: predict the opponent's action given the history.

These tools encode different assumptions. The Nash definition is mutual best response; using it as a behavioral prediction can additionally require strong rationality and information assumptions. Subgame perfection rules out non-credible behavior in proper subgames, while imperfect-information settings often need refinements defined at information sets. Level-$k$ models can fit bounded reasoning in some laboratory games, but their advantage is context dependent. Learned opponent models avoid an equilibrium requirement, yet still assume a policy class, stationarity window, and training distribution.

The recursive structure of “what I think you think” can be represented with interactive beliefs. For focal agent $i$, let $\Theta_{-i}^{(d-1)}$ denote a chosen class of depth-$(d-1)$ models of the other agents. A depth-$d$ belief has type

$$b_i^{(d)} \in \Delta\!\left(\mathcal{S}\times\Theta_{-i}^{(d-1)}\right),$$

where $\Delta(X)$ denotes probability distributions over $X$. A base type in $\Theta^{(0)}$ is a specified behavioral model; it need not be uniform. At the next depth, a type may itself contain a belief about physical state and lower-depth models. This typed construction follows the interactive-state view of Gmytrasiewicz and Doshi (2005). It has no general $N D$ dimension formula. A factorized implementation may store $N$ summaries with $D$ parameters each, but correlated types, histories, and deeper model classes can grow much faster.

Bounding depth is one approximation. Another shares parameters across agents or keeps only a small population of opponent types. The approximation must state what one node represents, which agents can appear next, and whether repeated identities are allowed.

The following count makes one deliberately uncompressed approximation concrete. In a toy tree where each modeled agent branches to every other agent identity, each additional depth multiplies the node count by $N-1$. This is an illustration, not a general complexity law.

The switch occurs because the posterior exceeds the threshold $q=0.5$, where $4q=2$. Different likelihoods or incentives can leave the best response unchanged. This tiny example does not solve decentralized planning; it shows how a communication observation enters a belief-dependent action choice.

The dynamics of coordination depend sharply on whether other agents are cooperative, adversarial, or indifferent:

• Fully cooperative. Agents share a reward, but decentralized execution remains difficult when observations differ. Centralized training with decentralized execution (CTDE) is one widely used research pattern when joint information is available during training.
• Two-player zero-sum. Rewards satisfy $r_1+r_2=0$; finite games have a minimax value. Constant-sum games can be normalized to this form.
• Mixed-motive. Agents' interests partially overlap. Many real coordination and negotiation problems are mixed-motive: two companies negotiating a deal, two robots sharing a corridor, two nations managing a border. Nash equilibrium is a central solution concept, but there can be multiple equilibria with very different welfare properties, so which one gets selected becomes a first-order design question.

In mixed-motive settings, equilibria can have different welfare properties and equilibrium selection matters. Exact solution becomes intractable in many large or partially observable formulations, though complexity depends on the game class, representation, horizon, and solution concept. Practical methods exploit structure, self-play, approximation, or learned models rather than applying one universal recipe.

In CTDE, a centralized critic can condition on joint information during training while decentralized actors use local observations at execution. This can improve credit assignment and reduce apparent nonstationarity, as in Lowe et al. (2017). It does not guarantee equilibrium selection, communication, robustness, or coordination under distribution shift.

For world models, the requirement is to account for other agents' behavior. A model may represent policies, types, and beliefs explicitly, or encode them implicitly in a history-dependent latent state. Either way, evaluation should separate prediction under fixed co-player policies from adaptation after those policies change.