In single-agent reinforcement learning, an agent learns to navigate an environment by maximizing a reward signal. When we transition to multi-agent reinforcement learning (MARL), the complexity explodes. If one agent has 10 possible actions, a system with 2 agents has $10 \times 10 = 100$ joint actions. By the time you have 10 agents, there are $10^{10}$ (10 billion) possible joint actions.
This exponential explosion is known as the curse of multiagency. Traditionally, it meant that the sample complexity—the amount of data required to learn an effective strategy—scaled exponentially with the number of players, making large-scale coordination mathematically intractable.
A rapidly growing body of research has found a way out. By restructuring how agents learn, approximate, and interact, we can collapse this exponential bottleneck into polynomial or linear scaling. Instead of scaling with the product of the action spaces ($\prod |A_i|$), these methods scale with the sum ($\sum |A_i|$) or the maximum individual action space ($\max |A_i|$). Here is how it works.
Decentralization and Independent Function Approximation
The most direct way to avoid the joint action space is to force agents to learn independently. If each agent optimizes its policy based solely on its individual action space and local observations, we never have to construct the massive joint action-value table.
As shown by Weichao Mao et al. in On Improving Model-Free Algorithms for Decentralized Multi-Agent Reinforcement Learning, decentralized learning allows the sample complexity to depend on the size of the largest individual action space rather than the product of all action spaces. This effectively bypasses the centralized training bottleneck.
Centralized (Exponential): |A₁| × |A₂| × |A₃| × ... × |Aₙ| = O(|A|ⁿ)
Decentralized (Linear): |A₁| + |A₂| + |A₃| + ...
+ |Aₙ| = O(n · |A|)
However, real-world environments also have massive or continuous state spaces. To handle this, agents use function approximation (like linear models or neural networks) to generalize across states. Qiwen Cui et al. demonstrated in Breaking the Curse of Multiagents in a Large State Space: RL in Markov Games with Independent Linear Function Approximation that when agents utilize independent linear function approximations to model their environments, the sample complexity scales polynomially with the number of agents and individual feature dimensions, rather than the joint action space.
Additive Action Space Decomposition
Even when agents learn independently, their rewards are often coupled. In a two-player zero-sum game or a competitive team game, one agent's success inherently depends on another's choices. How do we maintain polynomial scaling when choices are tightly bound?
The answer lies in value and policy decomposition. In Model-Based Reinforcement Learning for Offline Zero-Sum Markov Games, Yuling Yan et al. proved that the sample complexity for learning Nash equilibria can scale linearly with the sum of the action spaces ($A+B$) rather than their product ($A \times B$).
This additive scaling can be extended to more complex, asymmetric settings. Consider an adversarial team game where a large group of coordinating agents fights a single opponent. In Efficiently Computing Nash Equilibria in Adversarial Team Markov Games, Fivos Kalogiannis et al. showed that by allowing team members to update their policies independently while treating the adversary as a nested optimization subproblem, the computational complexity scales linearly with the sum of individual team action spaces.
For fully cooperative settings, Yihan Wang et al. proposed a decomposed critic structure in DOP: Off-Policy Multi-Agent Decomposed Policy Gradients. By breaking a centralized value function into additive components, the computational complexity of calculating expectations for off-policy updates drops from exponential to linear relative to the number of agents.
Exploiting Structural Constraints
We can achieve even steeper efficiency gains—sometimes making sample complexity completely independent of the number of agents—by exploiting the structural physics of the game itself.
Potential Games
In a Markov Potential Game (MPG), the incentives of all players are aligned through a single global potential function. Ziang Song et al. demonstrated in When Can We Learn General-Sum Markov Games with a Large Number of Players Sample-Efficiently? that this potential structure allows Nash Equilibrium discovery to scale with the sum of individual action spaces, bypassing the product entirely.
Networked and Localized Interactions
In many large-scale systems, agents do not interact with everyone; they only interact with their geographical or logical neighbors (e.g., autonomous vehicles at an intersection). In Convergence rates for localized actor-critic in networked Markov potential games, Zhaoyi Zhou et al. proved that localized learning algorithms can achieve a sample complexity that remains completely constant, regardless of how many total agents exist in the broader network.
Mean-Field Approximations
When the population grows massive, tracking individual identities becomes impossible. Mean-Field RL solves this by modeling a single agent interacting with the aggregate distribution of the population. Jiawei Huang et al. showed in On the Statistical Efficiency of Mean-Field Reinforcement Learning with General Function Approximation that by characterizing the population as a continuous distribution, the sample complexity scales polynomially with the complexity of the model class rather than the agent count, neutralizing the curse of multiagency.
Strategy-Wise Concentration and Convexification
How do we mathematically guarantee these algorithms won't fail when faced with out-of-distribution actions? In single-agent RL, we use optimism or pessimism bounds on individual state-action pairs. In multi-agent settings, doing this requires an exponential number of bounds.
To solve this, Qiwen Cui et al. introduced the strategy-wise concentration principle in Provably Efficient Offline Multi-agent Reinforcement Learning via Strategy-wise Bonus. Instead of building confidence intervals for every discrete action combination, the authors build confidence intervals over entire joint strategies. This ties the sample complexity directly to the complexity of a pre-defined policy class, allowing data requirements to scale linearly with the sum of player actions.
Taking this a step further, Dean Foster et al. proved in On the Complexity of Multi-Agent Decision Making: From Learning in Games to Partial Monitoring that the model class can be treated as a continuous, convex space. This mathematical convexification ensures that learning efficiency depends strictly on the size of individual agents' decision sets rather than the exponential dimensions of the joint environment model.
Similarly, in robust settings where agents must prepare for environmental shifts, Laixi Shi et al. showed in Breaking the Curse of Multiagency in Robust Multi-Agent Reinforcement Learning that shifting from joint action-space rectangularity to individual action-space rectangularity allows robust sample complexity to scale linearly with the number of agents.
Why It Works
Polynomial multi-agent scaling works because it replaces an unconstrained combinatorial problem with structured, decentralized optimization. By forcing agents to maintain independent function approximations, decomposing joint reward structures into additive components, and leveraging localized or mean-field interactions, these frameworks ensure that adding a new agent to a system adds a linear, predictable cost—rather than an exponential explosion.
Key Foundational Work
Efficient No-Regret Multiagent Learning (2005) — contributed 1 concept elements to this direction.
On Local Rewards and Scaling Distributed Reinforcement Learning (2005) — contributed 1 concept elements to this direction.
Two-Timescale Algorithms for Learning Nash Equilibria in General-Sum Stochastic Games (2015) — contributed 1 concept elements to this direction.