mlsanityData to 14 Oct 2026

Sample-Efficient Policy Space Response Oracles with Joint Experience Best Response

arXiv 2602.06599 ↗First posted 6 Feb 2026cs.MA cs.AI cs.LGcited by 0

On the map: Deep reinforcement learning methods → RL theory and sample complexity

Abstract (arXiv)

Multi-agent reinforcement learning (MARL) offers a scalable alternative to exact game-theoretic analysis but suffers from non-stationarity and the need to maintain diverse populations of strategies that capture non-transitive interactions. Policy Space Response Oracles (PSRO) address these issues by iteratively expanding a restricted game with approximate best responses (BRs), yet per-agent BR training makes it prohibitively expensive in many-agent or simulator-expensive settings. We introduce Joint Experience Best Response (JBR), a drop-in modification to PSRO that collects trajectories once under the current meta-strategy profile and reuses this joint dataset to compute BRs for all agents simultaneously. This amortizes environment interaction and improves the sample efficiency of best-response computation. Because JBR converts BR computation into an offline RL problem, we propose three remedies for distribution-shift bias: (i) Conservative JBR with safe policy improvement, (ii) Exploration-Augmented JBR that perturbs data collection and admits theoretical guarantees, and (iii) Hybrid BR that interleaves JBR with periodic independent BR updates. Across benchmark multi-agent environments, Exploration-Augmented JBR achieves the best accuracy-efficiency trade-off, while Hybrid BR attains near-PSRO performance at a fraction of the sample cost. Overall, JBR makes PSRO substantially more practical for large-scale strategic learning while preserving equilibrium robustness.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods. Builds on 9 of its 30 references that are in the map. First posted on arXiv 6 Feb 2026.

Builds on

9 of 30 references.

References · 9

  1. 2015Continuous control with deep reinforcement learningcited by 3,407
  2. 2019OpenSpiel: A Framework for Reinforcement Learning in Gamescited by 186
  3. 2017Safe Policy Improvement with Baseline Bootstrappingcited by 144
  4. 2020Real World Games Look Like Spinning Topscited by 66
  5. 2020Pipeline PSRO: A Scalable Approach for Finding Approximate Nash Equilibria in Large Gamescited by 47
  6. 2021Measuring the Non-Transitivity in Chesscited by 10
  7. 2023Co-Learning Empirical Games and World Modelscited by 4
  8. 2024Neural Population Learning beyond Symmetric Zero-sum Gamescited by 4
  9. 2023Coordinating Fully-Cooperative Agents Using Hierarchical Learning Anticipationcited by 2

Built on by

Not cited yet.

Similar, not cited

Close in wording, no citation either way

  1. 2026Code-Space Response Oracles: Generating Interpretable Multi-Agent Policies with Large Language Models
  2. 2026Global Policy-Space Response Oracles for Two-Player Zero-Sum Games
  3. 2024Offline Multi-Agent Reinforcement Learning via In-Sample Sequential Policy Optimization
  4. 2024Best Response Shaping
  5. 2026Breaking the Computational Barrier: Provably Efficient Actor-Critic for Low-Rank MDPs
  6. 2025Incentivize without Bonus: Provably Efficient Model-based Online Multi-agent RL for Markov Games
  7. 2026Conservative Equilibrium Discovery in Offline Game-Theoretic Multiagent Reinforcement Learning
  8. 2025Policy-Conditioned Policies for Multi-Agent Task Solving