Analysing the Sample Complexity of Opponent Shaping
Not on the map. Why?
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.
Key facts. Cited by 2 papers in the map (data through 7 Oct 2026). Builds on 12 of its 33 references that are in the map. First posted on arXiv 8 Feb 2024.
Builds on
12 of 33 references.
References · 12
- 2017Proximal Policy Optimization Algorithmscited by 14,441
- 2017Learning with Opponent-Learning Awarenesscited by 218
- 2018The Mechanics of n-Player Differentiable Gamescited by 118
- 2018Stable Opponent Shaping in Differentiable Gamescited by 49
- 2020A Policy Gradient Algorithm for Learning to Learn in Multiagent Reinforcement Learningcited by 40
- 2022COLA: Consistent Learning with Opponent-Learning Awarenesscited by 38
- 2019Competitive Gradient Descentcited by 32
- 2022Proximal Learning With Opponent-Learning Awarenesscited by 20
- 2020On the Impossibility of Global Convergence in Multi-Loss Optimizationcited by 16
- 2018When Simple Exploration is Sample Efficient: Identifying Sufficient Conditions for Random Exploration to Yield PAC RL Algorithmscited by 11
- 2021Centralized Model and Exploration Policy for Multi-Agent RLcited by 11
- 2021Sample Efficient Reinforcement Learning In Continuous State Spaces: A Perspective Beyond Linearitycited by 6
Built on by
Citing papers per year: 2024: 1; 2025: 1.
2 papers.
Similar, not cited
Close in wording, no citation either way
- 2025Opponent Shaping in LLM Agents
- 2024Advantage Alignment Algorithms
- 2026Near-Optimal Last-Iterate Convergence for Zero-Sum Games with Bandit Feedback and Opponent Actions
- 2022Provably Efficient Offline Multi-agent Reinforcement Learning via Strategy-wise Bonus
- 2024A Minimaximalist Approach to Reinforcement Learning from Human Feedback
- 2023Mimicking To Dominate: Imitation Learning Strategies for Success in Multiagent Competitive Games
- 2026NashDreamer: Model-Based Reinforcement Learning for Zero-Sum Imperfect-Information Games
- 2025DiffFP: Learning Behaviors from Scratch via Diffusion-based Fictitious Play