Decentralized control and multi-agent planning problems (such as Dec-POMDPs) are notoriously difficult to solve. When multiple autonomous agents must cooperate in a stochastic environment based on asymmetric, local observations, they face a fundamental computational barrier: the nightmare of nested beliefs.
To choose an optimal action, Agent A must guess what Agent B observed. However, Agent B's action depends on what Agent B thinks Agent A observed, which in turn depends on what Agent A thinks Agent B thinks Agent A observed. As noted by Adam P. Vogel et al. in Implicatures and Nested Beliefs in Approximate Decentralized-POMDPs, this infinite regress of "I think that you think that I think" makes exact decentralized decision-making computationally intractable (NEXP-complete).
The common information approach is a powerful mathematical framework that breaks this infinite loop. It proves that decentralized coordination problems can be systematically transformed into equivalent, centralized planning problems, allowing researchers to apply standard single-agent optimization tools to multi-agent systems.
Splitting the Information Structure
The core insight behind this framework is that even when agents have different private data, they almost always share a significant amount of history. In a foundational paper, Aditya Mahajan, Ashutosh Nayyar, and Demosthenis Teneketzis formalised this by partitioning each agent's history into two distinct components in Decentralized Stochastic Control with Partial History Sharing: A Common Information Approach:
- Common Information: Data known to all agents in the system (such as past public actions, shared observations, or delayed control signals).
- Private Information: Local observations known exclusively to an individual agent.
By separating these layers, we can analyze the system through the eyes of a fictitious, centralized virtual coordinator who only observes the common information.
Prescriptions Instead of Commands
How can a coordinator who cannot see private data guide decentralized agents effectively? The coordinator cannot issue direct action commands (e.g., telling an agent to "move left"), because it doesn't know the agent's exact local state.
Instead, the coordinator issues prescriptions (or decision rules). A prescription is a mathematical function that maps an agent's private information to a specific action. For instance, the coordinator might issue a rule stating: "If your local sensor reads high, turn left; if it reads low, turn right."
[ Common Information History ]
│
▼
┌───────────────────┐
│Virtual Coordinator│
└─────────┬─────────┘
│
▼ (Generates Prescriptions)
┌───────────────────┐
│ Prescription │ ──► (Maps Private Data to Actions)
└───────────────────┐
│
▼
┌───────────────────┐
│ Decentralized Act │
└───────────────────┘
As explained by Aditya Mahajan and Jalal Arabneydi in Reinforcement learning in decentralized stochastic control systems with partial history sharing, this mechanism shifts the perspective from individual agent reactions to a unified planning problem. Because the common information is public, every agent can independently compute the exact same common information state and deduce the optimal prescriptions. They then evaluate these shared prescriptions using their local private data, executing perfectly synchronized actions without needing real-time communication.
Why It Works: The Decentralized-to-Centralized Reduction
The magic of this approach lies in how it transforms the underlying state space. Instead of tracking individual histories, the virtual coordinator tracks a common information belief (or public belief space)—a posterior probability distribution over the global system states and agents' private data, conditioned on the shared common history.
This belief serves as a sufficient statistic for the entire system history. As demonstrated by Jilles Steeve Dibangoye et al. in Optimally Solving Dec-POMDPs as Continuous-State MDPs, when we treat this joint distribution (known as the occupancy state) as the state of a new system, the transitions become completely deterministic.
The subsequent distribution over histories is uniquely determined by the current distribution and the chosen prescriptions. This reduction converts a stochastic, partially observable decentralized problem into a continuous-state, deterministic single-agent MDP. This equivalence allows researchers to bypass nested beliefs entirely and apply standard centralized tools like dynamic programming, heuristic search (Scaling Up Decentralized MDPs Through Heuristic Search), or value iteration (Point Based Value Iteration with Optimal Belief Compression for Dec-POMDPs).
Applications Across Multi-Agent Domains
The common information framework has been successfully adapted across several distinct research directions:
- Reinforcement Learning: Algorithms like oSARSA (Learning to Act in Decentralized Partially Observable MDPs) and CAPI (Solving Common-Payoff Games with Approximate Policy Iteration) leverage the public belief space to guarantee convergence to optimal policies where standard multi-agent RL fails. Similarly, Rajesh K. Mishra et al. combine particle filters with this approach in Decentralized Multi-agent Reinforcement Learning with Shared Actions to estimate joint beliefs purely from public action histories.
- Remote Estimation: In sensor networks, the common information approach allows a transmitter and a remote receiver to maintain a synchronized belief state. Aditya Mahajan and Jhelum Chakravorty prove in Structure of optimal strategies for remote estimation over Gilbert-Elliott channel with feedback that this shared belief yields simple, optimal threshold policies (e.g., only transmit when local error is large). Edoardo David Santi et al. extend this in Remote Estimation of Markov Processes over Costly Channels: On Implicit Information Benefits to exploit "implicit information"—the meaning hidden behind a sensor's silence.
- Adversarial and Linear Systems: Rahul Jain et al. demonstrate in Optimal Communication and Control Strategies for a Multi-Agent System in the Presence of an Adversary that common information beliefs can reduce complex decentralized zero-sum games into centralized dynamic programs to find robust min-max strategies against eavesdroppers. For continuous control, Aditya Mahajan and Ashutosh Nayyar show in Sufficient Statistics for Linear Control Strategies in Decentralized Systems With Partial History Sharing that the framework simplifies decentralized Linear-Quadratic-Gaussian (LQG) problems without requiring restrictive network topologies.
Key Foundational Work
Language Learning in Multi-Agent Systems (2005) — contributed 1 concept elements to this direction.
Reasoning about joint beliefs for execution-time communication decisions (2005) — contributed 1 concept elements to this direction.
The Complexity of Decentralized Control of Markov Decision Processes (2000) — contributed 1 concept elements to this direction.