# Strategically Efficient Exploration in Competitive Multi-agent Reinforcement Learning

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 20 references that are in the map.
- First posted on arXiv 30 Jul 2021.

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

- [Curiosity-driven Exploration by Self-supervised Prediction](https://mlsanity.com/paper/1705.05363/) (2017)
- [Exploration by Random Network Distillation](https://mlsanity.com/paper/1810.12894/) (2018)
- [Is Q-learning Provably Efficient?](https://mlsanity.com/paper/1807.03765/) (2018)
- [Large-Scale Study of Curiosity-Driven Learning](https://mlsanity.com/paper/1808.04355/) (2018)
- [A Unified Game-Theoretic Approach to Multiagent Reinforcement Learning](https://mlsanity.com/paper/1711.00832/) (2017)
- [Deep Exploration via Randomized Value Functions](https://mlsanity.com/paper/1703.07608/) (2017)
- [Behaviour Suite for Reinforcement Learning](https://mlsanity.com/paper/1908.03568/) (2019)
- [Provable Self-Play Algorithms for Competitive Reinforcement Learning](https://mlsanity.com/paper/2002.04017/) (2020)
- [Near-Optimal Reinforcement Learning with Self-Play](https://mlsanity.com/paper/2006.12007/) (2020)
- [Coordinated Exploration via Intrinsic Rewards for Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/1905.12127/) (2019)
- [Exploration with Unreliable Intrinsic Reward in Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/1906.02138/) (2019)

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

- [Efficient Model-based Multi-agent Reinforcement Learning via Optimistic Equilibrium Computation](https://mlsanity.com/paper/2203.07322/) (2022)
- [Competition over data: how does data purchase affect users?](https://mlsanity.com/paper/2201.10774/) (2022)
- [Efficient Exploration for Iterative Nash Preference Optimization](https://mlsanity.com/paper/2606.01382/) (2026)

## Abstract (arXiv)

High sample complexity remains a barrier to the application of reinforcement learning (RL), particularly in multi-agent systems. A large body of work has demonstrated that exploration mechanisms based on the principle of optimism under uncertainty can significantly improve the sample efficiency of RL in single agent tasks. This work seeks to understand the role of optimistic exploration in non-cooperative multi-agent settings. We will show that, in zero-sum games, optimistic exploration can cause the learner to waste time sampling parts of the state space that are irrelevant to strategic play, as they can only be reached through cooperation between both players. To address this issue, we introduce a formal notion of strategically efficient exploration in Markov games, and use this to develop two strategically efficient learning algorithms for finite Markov games. We demonstrate that these methods can be significantly more sample efficient than their optimistic counterparts.