Aggarwal & How's PR-MRE beats Bayesian Nash in adversarial team games

Adversarial team games with asymmetric information—like path-finding or goal search on graphs—require strategies robust to hidden opponent types and deception. Existing solution concepts such as Bayesian Nash equilibrium (BNE) are risk-neutral and brittle to distribution shifts. Aggarwal and How's new paper introduces PR-MRE (Probabilistically Robust Minimax-Regret Equilibrium), which blends the distribution-free robustness of minimax-regret reasoning with probabilistic information from a nominal type distribution. PR-MRE minimizes worst-case regret over a high-confidence subset of the type space, avoiding both the fragility of BNE and the conservatism of fully distribution-free approaches. The authors show that for normal-form Bayesian games, PR-MRE can be formulated as a robust bilinear program and solved via a tractable semidefinite relaxation. They then adapt this into a meta-solver called PRMRE-PSRO, which uses a robust double-oracle framework to learn approximate PR-MRE strategies through deep reinforcement learning best responses.

Experimental results on graph-structured adversarial team games demonstrate that PR-MRE discovers strategies with substantially improved worst-case performance across hidden types compared to risk-neutral equilibria. The approach yields more robust behavior under strategic distribution shifts—scenarios where an omniscient opponent can condition its play on observed type. The paper spans 29 pages with 11 figures and 6 tables, submitted to TMLR. This work bridges game theory and multi-agent RL, offering a principled way to handle deception and uncertainty in competitive multi-agent settings. For practitioners, PR-MRE provides a tractable framework for designing agents that are both data-informed and adversarially robust, with potential applications in cybersecurity, autonomous driving, and military simulations.