# Analysing the Sample Complexity of Opponent Shaping

arXiv: https://arxiv.org/abs/2402.05782 · HTML: https://mlsanity.com/paper/2402.05782/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 33 references that are in the map.
- First posted on arXiv 8 Feb 2024.

## Builds on (most cited first, 12 of 12)

- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [Learning with Opponent-Learning Awareness](https://mlsanity.com/paper/1709.04326/) (2017)
- [The Mechanics of n-Player Differentiable Games](https://mlsanity.com/paper/1802.05642/) (2018)
- [Stable Opponent Shaping in Differentiable Games](https://mlsanity.com/paper/1811.08469/) (2018)
- [A Policy Gradient Algorithm for Learning to Learn in Multiagent Reinforcement Learning](https://mlsanity.com/paper/2011.00382/) (2020)
- [COLA: Consistent Learning with Opponent-Learning Awareness](https://mlsanity.com/paper/2203.04098/) (2022)
- [Competitive Gradient Descent](https://mlsanity.com/paper/1905.12103/) (2019)
- [Proximal Learning With Opponent-Learning Awareness](https://mlsanity.com/paper/2210.10125/) (2022)
- [On the Impossibility of Global Convergence in Multi-Loss Optimization](https://mlsanity.com/paper/2005.12649/) (2020)
- [Centralized Model and Exploration Policy for Multi-Agent RL](https://mlsanity.com/paper/2107.06434/) (2021)
- [When Simple Exploration is Sample Efficient: Identifying Sufficient Conditions for Random Exploration to Yield PAC RL Algorithms](https://mlsanity.com/paper/1805.09045/) (2018)
- [Sample Efficient Reinforcement Learning In Continuous State Spaces: A Perspective Beyond Linearity](https://mlsanity.com/paper/2106.07814/) (2021)

## Built on by (most cited first, 2 of 2)

- [Preference-based opponent shaping in differentiable games](https://mlsanity.com/paper/2412.03072/) (2024)
- [Adaptive Accountability in Networked MAS: Tracing and Mitigating Emergent Norms at Scale](https://mlsanity.com/paper/2512.18561/) (2025)

## Abstract (arXiv)

Learning in general-sum games often yields collectively sub-optimal results. Addressing this, opponent shaping (OS) methods actively guide the learning processes of other agents, empirically leading to improved individual and group performances in many settings. Early OS methods use higher-order derivatives to shape the learning of co-players, making them unsuitable for shaping multiple learning steps. Follow-up work, Model-free Opponent Shaping (M-FOS), addresses these by reframing the OS problem as a meta-game. In contrast to early OS methods, there is little theoretical understanding of the M-FOS framework. Providing theoretical guarantees for M-FOS is hard because A) there is little literature on theoretical sample complexity bounds for meta-reinforcement learning B) M-FOS operates in continuous state and action spaces, so theoretical analysis is challenging. In this work, we present R-FOS, a tabular version of M-FOS that is more suitable for theoretical analysis. R-FOS discretises the continuous meta-game MDP into a tabular MDP. Within this discretised MDP, we adapt the Rmax algorithm, most prominently used to derive PAC-bounds for MDPs, as the meta-learner in the R-FOS algorithm. We derive a sample complexity bound that is exponential in the cardinality of the inner state and action space and the number of agents. Our bound guarantees that, with high probability, the final policy learned by an R-FOS agent is close to the optimal policy, apart from a constant factor. Finally, we investigate how R-FOS's sample complexity scales in the size of state-action space. Our theoretical results on scaling are supported empirically in the Matching Pennies environment.