Sample-Efficient Policy Space Response Oracles with Joint Experience Best Response Conference: Proc. of the 25th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2026); May 25 – 29, 2026; Paphos, Cyprus Ariyan Bighashdel, Thiago D. Simão, Frans A. Oliehoek Abstract . 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. \doi C. Amato, L. Dennis, V. Mascardi, J. Thangarajah (eds.) 1. Introduction Figure 1. Sample-efficiency – accuracy trade-off in Leduc Poker. Shown are total best-response episodes (in millions, x -axis) versus minimum NashConv after 100 iterations ( y -axis). Standard PSRO is accurate but requires the highest BR sample cost. Joint Experience Best Response ( JBR-PSRO ) and its enhanced variants— conservative ( JBR-PSRO-SPI ), exploration-augmented ( JBR-PSRO- \delta R , JBR-PSRO- \delta T ), and hybrid ( HBR-PSRO(10/30)- \delta T )—drastically reduce the number of BR episodes needed for convergence, with JBR-PSRO- \delta T achieving the best trade-off and hybrid versions approaching PSRO-level accuracy. \textbf{Sample-efficiency – accuracy trade-off in Leduc Poker.} Shown are total best-response episodes (in millions, $x$-axis) versus minimum NashConv after 100 iterations ($y$-axis). Standard PSRO is accurate but requires the highest BR sample cost. Joint Experience Best Response (\textsc{JBR-PSRO}) and its enhanced variants— conservative (\textsc{JBR-PSRO-SPI}), exploration-augmented (\textsc{JBR-PSRO-$\delta$R}, \textsc{JBR-PSRO-$\delta$T}), and hybrid (\textsc{HBR-PSRO(10/30)-$\delta$T})—drastically reduce the number of BR episodes needed for convergence, with \textsc{JBR-PSRO-$\delta$T} achieving the best trade-off and hybrid versions approaching PSRO-level accuracy. Multi-agent systems (MAS) underlie many real-world domains, from autonomous traffic control to electronic markets, where agents must continually adapt to one another’s strategies. Game theory offers strong foundations for analyzing such interactions through equilibrium concepts, but computing equilibria in large or sequential games is infeasible in practice due to the combinatorial growth of policy spaces ( 31 ; 24 ) . This motivates the need for scalable learning-based approaches. Multi-agent reinforcement learning (MARL) provides one such alternative, enabling agents to improve their policies through repeated interaction ( 26 ; 1 ) . However, MARL faces two key challenges. First, independent learning induces non-stationarity: as each agent updates, the environment faced by others keeps changing ( 30 ) . Centralized Training with Decentralized Execution (CTDE) ( 8 ; 18 ) partly mitigates this issue by allowing agents to learn with access to joint observations or gradients during training while acting independently at test time. However, residual instability often persists. Second, many games are non-transitive—no strategy is globally dominant—and robustness requires maintaining diverse populations of strategies ( 5 ; 23 ; 3 ; 2 ) . To address these challenges, the Policy Space Response Oracles (PSRO) framework ( 12 ) emerged as a synthesis of ideas from several research communities: from planning , it builds on the Double Oracle algorithm ( 21 ) ; from co-evolution , it adopts mechanisms such as Nash memory ( 6 ) and Parallel Nash Memory ( 22 ) ; from empirical game-theoretic analysis (EGTA) , it incorporates simulation-based restricted games ( 25 ) ; and from reinforcement learning , it leverages RL-based oracles to train best responses in high-dimensional sequential environments. At its core, PSRO maintains a restricted game consisting of a subset of strategies, computes a meta-strategy (a probability distribution over the restricted strategies) using a chosen solver, and expands the restricted game by adding new (approximate) best responses, i.e., strategies that maximize an agent’s payoff against the current meta-strategy profile (the mixed distribution of the other agents’ strategies). By repeating this process, PSRO incrementally approximates equilibria while preserving diverse strategy populations that can capture non-transitive dynamics. The overall procedure is summarized in Algorithm 1 . Despite its strengths, PSRO suffers from a major limitation: its computational cost. At each iteration, every agent must independently compute a best response, requiring as many reinforcement learning problems as there are agents, and in each case, the remaining agents must be simulated. In domains with many players or costly simulators, this process quickly becomes impractical. Existing works have sought to improve efficiency through parallelization ( 12 ; 20 ) , sample-efficient simulation ( 28 ; 32 ) , or transfer learning ( 16 ; 17 ; 27 ) . While such methods reduce wall-clock training time, they do not alter the fundamental structure of PSRO: separate best-response computation for each agent at every iteration. We propose Joint Experience Best Response (JBR) , a drop-in modification to PSRO that reuses joint experience across agents. Instead of training each best response independently, JBR collects trajectories once under the current meta-strategy profile and computes best responses for all agents from this shared dataset. This dramatically improves the sample efficiency of best-response computation , making PSRO practical in multi-agent or simulator-expensive domains. Because JBR reuses data generated under the current meta-strategy rather than interacting with the environment online, best-response computation becomes an offline reinforcement learning (offline RL) problem, where policies must be optimized from a fixed dataset instead of new environment rollouts. This offline setting can introduce bias due to distribution shift. We introduce three complementary variants: (i) Conservative JBR , which enforces Safe Policy Improvement ( 13 ) to guarantee no degradation below the baseline meta-strategy; (ii) Exploration-Augmented JBR , which perturbs data collection to improve coverage while preserving theoretical guarantees; and (iii) Hybrid BR , which alternates between JBR and periodic independent BR to combine efficiency with accuracy (Figure 1 ). Our findings show that exploration-augmented JBR with targeted perturbation ( JBR-PSRO- \delta T ) achieves near-PSRO equilibrium accuracy at a fraction of the sample cost, while hybrid variants ( HBR-PSRO( k )- \delta T ) reach PSRO-level performance with only minor additional training. Across discrete and continuous environments, PSRO-style methods—including our JBR variants—consistently outperform standard MARL paradigms such as independent learning and CTDE, confirming that strategically grounded training remains more robust when made sample-efficient. Our contributions are threefold: (1) We introduce Joint Experience Best Response (JBR) , an efficient modification of PSRO that improves the sample efficiency of best-response computation by reusing shared trajectories across agents. (2) We identify and address the offline RL limitations of JBR, proposing and evaluating three remedies: Conservative JBR, Exploration-Augmented JBR (with theoretical guarantees), and Hybrid BR. (3) We provide a comprehensive empirical study comparing JBR variants not only against Independent BR (standard PSRO), but also against mainstream MARL baselines such as Independent Learning and CTDE, showing that PSRO-based approaches consistently yield superior strategic robustness. 2. Related Work A wide range of extensions to PSRO have been proposed to improve different aspects of the framework, including scalability, exploration, and equilibrium computation. These directions are reviewed in a recent survey ( 4 ) . In this paper, we focus specifically on methods aimed at improving the efficiency of PSRO. Parallelization. Early work explored reducing wall-clock time through parallel training of best responses. The Deep Cognitive Hierarchy (DCH) ( 12 ) introduced a hierarchical schedule in which each player trains against equilibria of lower levels, effectively reusing earlier computations. Pipeline PSRO (P2SRO) ( 20 ) refined this idea by coordinating multiple strategies trained in parallel and dynamically optimizing the hierarchy itself. While these methods improve throughput, they require substantial computational resources and do not reduce the overall number of best responses. Sample efficiency. Another line of research targets the reliance on costly simulation. Smith and Wellman ( 28 ) proposed to jointly learn a generative model of the game while running PSRO, enabling queries to the learned model instead of the environment. Zhou et al. ( 32 ) developed EPSRO, which avoids redundant restricted-game evaluations by exploiting cases where best-response target profiles can be derived without full simulation. Although these approaches cut down on simulator calls, their benefits depend heavily on the quality of the learned model, and the cost of retraining best responses remains unchanged. Transfer learning. A third approach is to accelerate adaptation by reusing knowledge across best responses. NeuPL ( 16 ) introduced parameter sharing across strategies in a single network, while Liu et al. ( 15 ) trained against sampled mixtures to provide robustness to diverse opponent profiles. Later, Liu et al. ( 17 ) combined NeuPL with JPSRO to extend transfer benefits to correlated-equilibrium computation. Smith et al. ( 27 ) proposed a Mixed-Oracle method that constructs new best responses by mixing value functions pre-trained against pure strategies. These methods accelerate learning through knowledge reuse, but their effectiveness is tied to how well information transfers across opponents, and they still instantiate new best responses one at a time. Summary. Prior work demonstrates that PSRO can be made more practical through parallelization, efficient simulation, and transfer across best-response computations. While such methods reduce wall-clock training time, they largely remain implementation-level optimizations: the core PSRO loop continues to generate a separate best response for each agent at every iteration. In contrast, our proposed JBR framework changes this structure directly by reusing shared interaction experience to compute best responses for all agents simultaneously, offering a different route toward scalability. 3. Background The core idea of PSRO is to approximate otherwise intractable games by iteratively constructing a smaller restricted game , in which each player has access only to a subset of strategies. This restricted game is gradually expanded by adding new best responses, which are computed using RL. In this way, PSRO maintains a tractable approximation of the full game while progressively refining the strategic coverage. Formally, consider an n -player Markov (stochastic) game defined by: • a state space \mathcal{S} , • action spaces \mathcal{A}_{i} for each player i\in N=\{1,\dots,n\} , with joint action space \mathcal{A}=\times_{i=1}^{n}\mathcal{A}_{i} , • a transition kernel P(s^{\prime}\mid s,a_{1},\dots,a_{n}) , • player-specific reward functions r_{i}(s,a_{1},\dots,a_{n}) , • a discount factor \gamma\in[0,1) , • and an initial state distribution \rho_{0} . A strategy for player i is a policy \pi_{i}\in\Pi_{i} , i.e., a mapping from states to distributions over \mathcal{A}_{i} . Given a policy profile \pi=(\pi_{1},\dots,\pi_{n}) , the utility of player i is the expected discounted return of per-step rewards: u_{i}(\pi)=\mathbb{E}\!\left[\sum_{t=0}^{\infty}\gamma^{t}\,r_{i}(s_{t},a_{1,t},\dots,a_{n,t})\;\middle|\;\pi\right]. PSRO can thus be understood as operating on a normal-form game induced by the Markov game , \mathcal{G}=(N,(\Pi_{i}),(u_{i})) , where the pure strategies are full policies and payoffs are their expected returns. In practice, this induced game is intractable because each \Pi_{i} is enormous. PSRO therefore maintains restricted policy sets X_{i}\subseteq\Pi_{i} , consisting of the policies generated so far, and defines the restricted empirical game, \hat{\mathcal{G}}=(N,(X_{i}),(\hat{u}_{i})) , where \hat{u}_{i} are payoff estimates obtained from rollouts of profiles \pi\in X=\times_{i}X_{i} . The restricted empirical game serves as the basis for strategy updates, representing a smaller, simulation-based approximation of the full game that captures interactions among the currently known policies. The PSRO algorithm alternates between two key components: • Meta-Strategy Solver (MSS): Given \hat{\mathcal{G}} , the MSS computes a meta-strategy profile (mixed strategy) \sigma=(\sigma_{i})_{i\in N} , where each \sigma_{i} is a probability distribution over X_{i} that specifies how frequently each policy in the agent’s current set is played. Typical choices include Nash equilibrium solvers or regret-minimization dynamics. • Response Oracle (RO): For each player i , the RO computes an approximate best-response policy \pi_{i}^{\mathrm{BR}} against \sigma_{-i} . Formally, the best-response operator is br_{i}(\sigma_{-i})=\arg\max_{\pi_{i}\in\Pi_{i}}u_{i}(\pi_{i},\sigma_{-i}). In practice, the RO is implemented by deep RL : the agent is trained in the induced MDP where opponents follow \sigma_{-i} , yielding a policy \pi_{i}^{\mathrm{BR}} that approximates br_{i}(\sigma_{-i}) . The new policy is then added to X_{i} , expanding the restricted game. Algorithm 1 Policy Space Response Oracles (PSRO) 0: Initial restricted policy sets (X_{i}) 1: Estimate \hat{\mathcal{G}}=(N,(X_{i}),(\hat{u}_{i})) 2: Initialize \sigma\leftarrow\text{MSS}(\hat{\mathcal{G}}) 3: while not terminated do 4: for player i\in N do 5: Compute \pi_{i}^{\mathrm{BR}}\leftarrow\text{RO}(\sigma_{-i}) 6: Update X_{i}\leftarrow X_{i}\cup\{\pi_{i}^{\mathrm{BR}}\} 7: end for 8: Re-estimate \hat{\mathcal{G}} 9: Update \sigma\leftarrow\text{MSS}(\hat{\mathcal{G}}) 10: end while 11: return \sigma The complete procedure is shown in Algorithm 1 . The process continues until a stopping criterion is met, often based on regret . The regret of player i under a meta-strategy profile \sigma is (1) \rho^{\mathcal{G}}_{i}(\sigma)=\max_{\pi_{i}\in\Pi_{i}}u_{i}(\pi_{i},\sigma_{-i})-u_{i}(\sigma_{i},\sigma_{-i}), which measures the potential gain from deviating unilaterally. At a Nash equilibrium, all regrets vanish. The aggregate regret, (2) \rho^{\mathcal{G}}(\sigma)=\sum_{i\in N}\rho^{\mathcal{G}}_{i}(\sigma), is known as NashConv ( 12 ) and, in two-player games, corresponds to exploitability. This quantity is widely used to track convergence in PSRO experiments. In practice, it can only be computed exactly in small discrete games where exhaustive best-response search is feasible; in larger or continuous environments, it must be approximated using learned best responses (see Section 5 ). 4. Method Throughout this section we adopt a unified perspective: best responses are derived via model-based reinforcement learning , specifically value iteration. This choice is made purely for clarity in explaining the different approaches. In practice, the RO is typically realized by deep RL methods, which approximate the same objective when exact model-based computation is infeasible. All formulations are therefore presented in this model-based framework for consistency, while our experiments employ both model-based and deep RL implementations depending on the environment. 4.1. Induced MDP In PSRO, the best response for player i is obtained by reducing the multi-agent stochastic game to a single-agent MDP: we fix the opponents’ meta-strategy profile, absorb their behavior into the environment, and solve the resulting induced MDP. PSRO assumes that the game has perfect recall , meaning that each agent remembers the entire sequence of states and actions it has observed and taken so far. This assumption ensures that no relevant information is forgotten when making decisions over time. Under perfect recall, Kuhn’s theorem ( 9 ) states that any mixed strategy (a distribution over full policies) is realization-equivalent to a behavior strategy that specifies, at each state, a distribution over available actions. In other words, while playing against a mixed strategy formally induces a POMDP—since the opponent’s policy index is unobserved—the assumption of perfect recall implies that the state s already encapsulates the relevant history h . Hence, the two representations are equivalent, and without loss of generality the opponents’ meta-strategy \sigma_{-i} can be represented as a behavior strategy \sigma_{-i}(a_{-i}\mid s) . 1 1 1 Remark: If opponents’ meta-strategies are interpreted as distributions over full policies and one such policy is sampled at the start of an episode, then from the viewpoint of player i the opponent policy index acts as a hidden variable, inducing a POMDP. Two standard resolutions exist: (i) represent the state space \mathcal{S} as the set of complete histories, making the process Markov, or (ii) assume perfect recall , which by Kuhn’s theorem guarantees that every mixed strategy is realization-equivalent to a behavior strategy. In both cases, we may treat the meta-strategy \sigma_{-i} as a behavior strategy \sigma_{-i}(a_{-i}\mid s) , yielding the induced MDP. Formally, fixing \sigma_{-i} yields effective transition and reward functions for player i by marginalizing over the opponents’ actions: (3) \displaystyle P^{\sigma_{-i}}(s^{\prime}\mid s,a_{i}) \displaystyle=\sum_{a_{-i}\in\mathcal{A}_{-i}}\sigma_{-i}(a_{-i}\mid s)\;P(s^{\prime}\mid s,a_{i},a_{-i}), (4) \displaystyle r_{i}^{\sigma_{-i}}(s,a_{i}) \displaystyle=\sum_{a_{-i}\in\mathcal{A}_{-i}}\sigma_{-i}(a_{-i}\mid s)\;r_{i}(s,a_{i},a_{-i}). (Replace sums by integrals for continuous \mathcal{A}_{-i} .) This defines the induced single-agent MDP for player i : \mathcal{M}_{i}^{\sigma_{-i}}\;=\;\big(\mathcal{S},\,\mathcal{A}_{i},\,P^{\sigma_{-i}},\,r_{i}^{\sigma_{-i}},\,\gamma,\,\rho_{0}\big). 4.2. Independent Best Response Let Q_{i}(s,a_{i}) denote the action-value function of player i in the induced MDP \mathcal{M}_{i}^{\sigma_{-i}} . Value iteration computes Q_{i} by repeatedly applying the Bellman optimality update: Q_{i}^{k+1}(s,a_{i})\;=\;r_{i}^{\sigma_{-i}}(s,a_{i})\;+\;\gamma\sum_{s^{\prime}\in\mathcal{S}}P^{\sigma_{-i}}(s^{\prime}\mid s,a_{i})\,\max_{a_{i}^{\prime}\in\mathcal{A}_{i}}Q_{i}^{k}(s^{\prime},a_{i}^{\prime}). As k\to\infty , the sequence converges to the optimal action-value function Q_{i}^{\star} . A greedy policy with respect to Q_{i}^{\star} , \pi_{i}^{\mathrm{BR}}(s)\;\in\;\arg\max_{a_{i}\in\mathcal{A}_{i}}Q_{i}^{\star}(s,a_{i}), is then a best response to \sigma_{-i} . 4.3. Joint Experience Best Response While Independent Best Response (§ 4.2 ) is the standard approach in PSRO, it has a key drawback: each agent’s best response is trained separately. This creates substantial redundancy: when training one agent, the interaction experience generated cannot be reused by others, leading to repeated and costly environment simulations. In domains with many agents or expensive dynamics, this per-agent training quickly becomes impractical. To address this inefficiency, we propose Joint Experience Best Response (JBR) . The core idea is to collect trajectories once, under the current meta-strategy profile \sigma=(\sigma_{j})_{j\in N} , and reuse this joint dataset to compute best responses for all agents simultaneously. In this setting, all players act according to their meta-strategies during data collection, so the dataset \mathcal{D}^{\sigma} consists of trajectories \mathcal{D}^{\sigma}=\{(s_{t},a_{1,t},\dots,a_{n,t},r_{1,t},\dots,r_{n,t},s_{t+1})\}_{t=0}^{T} generated by the Markov game when the joint policy profile \sigma is executed. The overall procedure is summarized in Algorithm 2 . Algorithm 2 PSRO with Joint Experience Best Response 0: Initial restricted policy sets (X_{i}) 1: Estimate \hat{\mathcal{G}}=(N,(X_{i}),(\hat{u}_{i})) 2: Initialize \sigma\leftarrow\text{MSS}(\hat{\mathcal{G}}) 3: while not terminated do 4: Collect joint dataset \mathcal{D}^{\sigma} under meta-strategy \sigma 5: for player i\in N do 6: Compute \pi_{i}^{\mathrm{BR}}\leftarrow\text{RO}(\mathcal{D}_{\sigma_{-i}}) 7: Update X_{i}\leftarrow X_{i}\cup\{\pi_{i}^{\mathrm{BR}}\} 8: end for 9: Re-estimate \hat{\mathcal{G}} 10: Update \sigma\leftarrow\text{MSS}(\hat{\mathcal{G}}) 11: end while 12: return \sigma 4.4. Naïve JBR The most direct approach is to treat \mathcal{D}^{\sigma} as a fixed offline dataset and then, for each agent i , construct its induced MDP \mathcal{M}_{i}^{\sigma_{-i}} as in § 4.1 . Best responses are then obtained by applying model-based value iteration on \mathcal{M}_{i}^{\sigma_{-i}} , using \mathcal{D}^{\sigma} to estimate the transition dynamics P^{\sigma_{-i}} and rewards r_{i}^{\sigma_{-i}} . Formally, the Q -iteration update is Q_{i}^{k+1}(s,a_{i})\;=\;\hat{r}_{i}^{\sigma_{-i}}(s,a_{i})\;+\;\gamma\sum_{s^{\prime}\in\mathcal{S}}\hat{P}^{\sigma_{-i}}(s^{\prime}\mid s,a_{i})\,\max_{a_{i}^{\prime}}Q_{i}^{k}(s^{\prime},a_{i}^{\prime}), where \hat{r}_{i}^{\sigma_{-i}} and \hat{P}^{\sigma_{-i}} are the reward and transition models estimated from \mathcal{D}^{\sigma} , respectively. The resulting greedy policy \pi_{i}^{\mathrm{BR}} is then added to the restricted game, exactly as in standard PSRO. Although conceptually simple, this Naïve JBR suffers from a critical limitation: since the dataset \mathcal{D}^{\sigma} is generated under the current meta-strategy, it may not cover the state–action regions relevant for computing the true best response. This distribution shift makes the problem an instance of offline RL, potentially leading to suboptimal approximations of best responses. To address these limitations, we introduce three complementary remedies. The first is a conservative safeguard based on Safe Policy Improvement (§ 4.5 ), which ensures that policies do not underperform the current meta-strategy. The second is an exploration-based approach (§ 4.6 ), which perturbs the meta-strategy during data collection to improve coverage and admits theoretical guarantees. Finally, a hybrid variant (§ 4.7 ) alternates between joint and independent best responses to balance efficiency and accuracy. Together, these three approaches mitigate the shortcomings of Naïve JBR. 4.5. Conservative JBR To address the offline RL bias of Naïve JBR, we adopt the principle of Safe Policy Improvement (SPI) ( 13 ) . The idea is to restrict the learned policy to only deviate from its baseline \sigma_{i} in regions of the state–action space that are sufficiently well supported by \mathcal{D}^{\sigma} . Wherever the dataset lacks coverage, the policy is forced to fall back to \sigma_{i} , guaranteeing that performance cannot degrade below the baseline. Formally, let N_{\mathcal{D}}(s,a_{i}) denote the number of times (s,a_{i}) appears in \mathcal{D}^{\sigma} , and fix a threshold N_{\wedge} . We define the set of uncertain state–action pairs as B_{i}\;=\;\{(s,a_{i})\;\mid\;N_{\mathcal{D}}(s,a_{i})0 , exploration ensures that all actions receive nonzero probability, so the dataset has broader coverage and the offline problem is better posed. Thus perturbation does not make the setting equivalent to online learning, but it guarantees that the \varepsilon -BR target is well defined and approximable from data. Related perspectives on enforcing equilibrium conditions from fixed multi-agent datasets—without online interaction—have also been explored in recent work on inverse and simulacral multi-agent learning ( 7 ) .