Foundations of Multi-Agent Systems: Formal Models and Computational Substrates

Chapter 1: Foundations of Multi-Agent Systems: Formal Models and Computational Substrates

What mathematical object best captures a population of situated, autonomous computational entities that observe the world only partially, hold divergent beliefs about the latent state, and must nevertheless converge on joint behavior whose value exceeds what any individual could produce in isolation? This is the question that organises the present chapter, and it is the question that determines whether the algorithms and architectures described later in this book can be derived rigorously rather than merely borrowed from folklore. We begin from a deliberately austere premise: an agent is a function from history to action, an environment is a stochastic kernel on state, and a multi-agent system is the closure of these objects under joint policy execution. From these three primitives we will construct the four dominant formalisms that recur throughout the literature—Markov Decision Processes and their decentralized extension (Dec-POMDP), stochastic games, Partially Observable Stochastic Games (POSG), and epistemic-logic-based BDI models—and we will show, by way of a worked implementation on the Dec-Tiger benchmark, why the choice among them is not merely philosophical but a binding engineering constraint on scalability.

1.1 Three Primitives: Agent, Environment, and Joint Policy

The literature on multi-agent systems is notorious for definitional drift. To prevent the remainder of this book from inheriting that drift, we commit at the outset to three definitions that are simultaneously precise enough to admit complexity analysis and abstract enough to encompass reactive robots, deliberative trading agents, and language-model-based assistants.

Definition 1.1 (Agent). An *agent* $i \in \mathcal{I} = \{1, \dots, n\}$ is a tuple $\langle \mathcal{O}_i, \mathcal{A}_i, \pi_i \rangle$ where $\mathcal{O}_i$ is a (possibly infinite) observation space, $\mathcal{A}_i$ is an action space, and $\pi_i : (\mathcal{O}_i)^{*} \rightarrow \Delta(\mathcal{A}_i)$ is a *policy* that maps the agent's finite observation history to a probability distribution over its actions. The policy $\pi_i$ is called *stationary* if it depends only on the most recent observation, *deterministic* if the output distribution is degenerate, and *finite-state* if it can be represented as the composition of a recurrent transition function on an internal memory space and a readout function from that memory to actions.

The bounded-rationality assumption is implicit: we do not require $\pi_i$ to be optimal in any global sense, only that it be computable by some concrete device with finite resources. This is essential because every algorithm in this book is, at its core, a procedure for synthesising or approximating such $\pi_i$.

Definition 1.2 (Environment). An *environment* is a tuple $\langle \mathcal{S}, \mathcal{T}, \mathcal{R}, \gamma \rangle$ where $\mathcal{S}$ is a state space, $\mathcal{T} : \mathcal{S} \times \mathcal{A} \rightarrow \Delta(\mathcal{S})$ is a stochastic transition kernel conditioned on the joint action $\mathbf{a} = (a_1, \dots, a_n) \in \mathcal{A} = \times_i \mathcal{A}_i$, $\mathcal{R} : \mathcal{S} \times \mathcal{A} \rightarrow \mathbb{R}$ is a shared (or factorised) reward function, and $\gamma \in [0, 1)$ is a discount factor. When each agent $i$ observes only $o_i \in \mathcal{O}_i$ drawn from an observation kernel $\mathcal{O} : \mathcal{S} \rightarrow \Delta(\mathcal{O}_i)$, the environment is said to be *partially observable* to that agent.

Definition 1.3 (Joint Policy and Value). A *joint policy* is the Cartesian product $\boldsymbol{\pi} = (\pi_1, \dots, \pi_n)$. Its *value* under initial state distribution $\mu \in \Delta(\mathcal{S})$ is $$V^{\boldsymbol{\pi}}(\mu) = \mathbb{E}_{\mu, \boldsymbol{\pi}, \mathcal{T}, \mathcal{O}} \left[ \sum_{t=0}^{\infty} \gamma^t \, \mathcal{R}(s_t, \mathbf{a}_t) \right].$$ The *coordination problem* is to find $\boldsymbol{\pi}^\star = \arg\max_{\boldsymbol{\pi}} V^{\boldsymbol{\pi}}(\mu)$, and the *multi-agent learning problem* is to approximate $\boldsymbol{\pi}^\star$ from samples when $\mathcal{T}$ and $\mathcal{R}$ are unknown.

These three definitions are not arbitrary. They are the minimum that allows us to speak about three quantities the rest of the book will repeatedly invoke: the *joint value* $V^{\boldsymbol{\pi}}$, the *individual best response* $\mathrm{BR}_i(\boldsymbol{\pi}_{-i}) = \arg\max_{\pi_i} V^{(\pi_i, \boldsymbol{\pi}_{-i})}(\mu)$, and the *Nash equilibrium* $\boldsymbol{\pi}^\dagger$ satisfying $\pi_i^\dagger \in \mathrm{BR}_i(\boldsymbol{\pi}^\dagger_{-i})$ for all $i$. Different formalisms make different assumptions about which of these quantities are tractable to compute, and the engineering trade-offs between optimality, scalability, and verifiability follow directly from those assumptions.

A subtle but consequential point: the joint policy $\boldsymbol{\pi}$ is a *factored* object. Even when the policy space is shared (homogeneous agents), the *value function is not* in general additive across agents. That is, $$V^{\boldsymbol{\pi}}(\mu) \neq \sum_{i=1}^{n} V_i^{\pi_i}(\mu),$$ because the reward $\mathcal{R}$ depends on the joint action, and the joint action's distribution is determined by the correlated observations of all agents. This non-decomposability is the root cause of the complexity results in §1.6 and the principal obstacle to naïve parallelisation.

1.2 A Taxonomy of Agents and Their Computational Demands

Not all agents place the same demands on the substrate. The taxonomy below is not academic: each class of agent excludes a class of formalisms and admits a class of algorithms. Choosing the wrong agent model for the problem at hand is one of the most common sources of failure in deployed multi-agent systems.

Reactive agents execute the policy $\pi_i(o_i^t)$ as a stateless mapping from the current observation to an action. Their entire "memory" is the current observation. The classic subsumption architecture of Brooks (1986) is the canonical example. Reactive agents require no internal state beyond what the observation provides, can be implemented in a few lines of code, and admit analysis by reactive synthesis tools. They cannot, however, solve any task that requires distinguishing between observationally identical states with different optimal continuations—precisely the failure mode that partial observability introduces.

Deliberative agents maintain an explicit symbolic model of the world and use a planner (typically a theorem prover, a PDDL planner, or an MCTS variant) to select actions. Their internal state includes a belief base $\mathcal{B}_i \subseteq \mathcal{L}$ over some logical language $\mathcal{L}$, and their policy is the composition of a *belief revision operator* and a *planner*. Deliberative agents are essential when the environment is too large to enumerate, when plans must be communicated and verified, and when the system must explain its decisions. They are poor fits for high-frequency control loops where replanning cannot keep pace with the dynamics.

Hybrid agents interleave a fast reactive layer with a slower deliberative layer, often through a three-layer architecture of the form *(reactive / sequencing / deliberative)*. The reactive layer guarantees safety in real time; the deliberative layer reasons about long-horizon objectives; the sequencing layer arbitrates between them. The computational demand is dominated by the deliberative layer, but the reactive layer imposes hard real-time deadlines that the rest of the system must respect. Most industrial multi-robot systems, including the autonomous warehouse fleets discussed in §1.7, are hybrid.

BDI agents (Belief–Desire–Intention architectures) are a particular species of deliberative agent whose internal state is a tuple $(\mathcal{B}, \mathcal{D}, \mathcal{I})$ of belief