Beyond Bayesian Nash: Learning Minimax-Regret Equilibria for Adversarial Team Games under Asymmetric Information
2026-07-10 • Computer Science and Game Theory
Computer Science and Game TheoryArtificial IntelligenceMachine LearningMultiagent Systems
AI summaryⓘ
The authors study games where one team faces opponents whose goals or types are hidden, making it tricky to plan good strategies. Traditional methods assume a fixed probability of opponent types, which can be unreliable if the opponent changes tactics. To solve this, the authors propose a new way to make decisions that balance being safe against worst-case surprises and using some known information about opponent types. They create a mathematical model and an algorithm that learns strategies in these games, showing it leads to more reliable results against smart opponents who might try to trick you.
Adversarial Team GamesAsymmetric InformationBayesian Nash EquilibriumMinimax RegretDistributional RobustnessRobust OptimizationSemidefinite RelaxationDouble-Oracle AlgorithmReinforcement LearningStrategic Deception
Authors
Naman Aggarwal, Jonathan P. How
Abstract
Adversarial team games (ATGs) with asymmetric information, such as adversarial path-finding, goal search, and reachability games on graphs, require strategies that are robust to hidden opponent types, such as a hidden goal flag, and to deception. Under asymmetric information, deception is seen as strategic shifts in the type distribution such that the omniscient opponent can collude with Nature and condition its play on the observed type. Existing risk-neutral solution concepts, such as Bayesian Nash equilibrium (BNE), are sensitive to distribution shifts, while distributionally robust approaches provide guarantees only within a prescribed ambiguity set. To address these limitations, we introduce Probabilistically Robust Minimax-Regret Equilibrium (PR-MRE), a novel equilibrium concept that combines 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, providing protection against strategic redistribution of probability mass while avoiding the conservatism of fully distribution-free approaches. We show that, for normal-form Bayesian games, PR-MRE can be formulated as a robust bilinear program and derive a tractable semidefinite relaxation. We then adapt this relaxation into a novel meta-solver within a robust double-oracle framework, PRMRE-PSRO, enabling population-based learning of approximate PR-MRE strategies via deep reinforcement learning best responses. Experiments 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 equilibrium solutions, resulting in more robust behavior under strategic distribution shifts.