Beyond Bayesian Nash: Learning Minimax-Regret Equilibria for Adversarial Team Games under Asymmetric Information
Listen
Radio episode about this paper
Transcript
Introduction to the show: ident: Computer Science. The day in computer science: software, systems and theory on arXiv.
Tom: We're looking at the paper: "Beyond Bayesian Nash".
Jane: Here's the gist of the paper. Adversarial team games with asymmetric information are susceptible to strategic type distribution shifts in settings where the omniscient opponent has knowledge of Nature’s hidden type and potentially controls the type distribution or colludes with Nature such that it can condition its play on the Nature’s realized type.
Tom: The Probabilistically Robust Minimax-Regret Equilibrium (PR-MRE) is introduced as a novel equilibrium concept that combines the distribution-free robustness of minimax-regret reasoning with probabilistic information from a nominal type distribution.
Jane: Pruning redundant reasoning tokens The PR-MRE concept interpolates between risk-neutral, distributionally robust equilibria and the distribution-free Minimax-Regret equilibrium.
Tom: It 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.
Title and authors: Tom: So we're looking at this paper today, it's called "Beyond Bayesian Nash: Learning Minimax-Regret Equilibria for Adversarial Team Games under Asymmetric Information".
Jane: Yeah, the title sounds pretty dense, but basically, they're taking something called Bayesian Nash equilibrium and making it robust to things that aren't just simple uncertainty.
Tom: Exactly. It’s about adversarial team games with asymmetric information, like when one side has a hidden flag location that the other side doesn't know about.
Lu: The authors are trying to build a strategy concept that handles those hidden opponent types and also deception, where the opponent might collude with Nature to shift how those types are distributed.
Meng: So they're not just looking at one type distribution, but how that distribution itself can change strategically during the game.
Jane: Right, and what's interesting is they introduce something called Probabilistically Robust Minimax-Regret Equilibrium or PR-MRE as a new concept to handle this.
Tom: It’s trying to bridge the gap between risk-neutral thinking and being totally distributionally robust, which is a big hurdle in these kinds of games.
The paper's summary: Tom: Okay, so what's the core idea behind PR-MRE? They introduce this concept that combines the robustness you get from minimax regret reasoning with some probabilistic information based on a nominal type distribution.
Jane: That sounds like they are trying to get the best of both worlds, right? It minimizes worst-case regret over a high confidence subset of the type space while still factoring in how likely certain types are according to their initial assumptions.
Lu: They say this allows them to minimize exploitability on that high-confidence set and discount the exploitability on atypical types using a parameter called delta.
Meng: So, instead of being totally blind to any type shift, you're basically saying "we're pretty sure it won't be some weird edge case," but you still have a safety net.
Tom: It’s framed by this best-response operator, BR(b)PRMRE, which minimizes worst-case exploitability on that subset while ignoring the types that are outside the confidence set.
Jane: The main result they show is that for any distribution allowed under their threat model, this PR-MRE concept gives you the tightest lower bound on expected performance.
Lu: Specifically, it guarantees V(-), which is the value of the Blue team, is greater than or equal to V(-), which is the value under a standard minimax regret equilibrium for all distributions within that set.
The paper's improvements: Tom: So what’s the actual improvement over existing ideas? They argue that this lower bound they provide is tighter than what you get from standard Minimax Regret Equilibrium, MRE.
Jane: That’s the key claim, and it comes from using coarse probabilistic information from the nominal prior distribution to get a better performance guarantee than just playing conservatively against every possible type shift.
Lu: They show empirically that this PR-MRE approach finds strategies with substantially improved worst-case performance across hidden types compared to risk-neutral equilibrium solutions.
Meng: That means you can actually discover better moves when you don't know the exact type distribution, as long as you have a reasonable idea of what the distribution *usually* looks like.
Tom: It’s about finding those robust best responses that give favorable worst-case performance guarantees when the type distribution shifts strategically.
Conclusion: Tom: So to wrap up, this paper introduces Probabilistically Robust Minimax-Regret Equilibrium as a new equilibrium concept for adversarial team games with asymmetric information.
Jane: The main implication is that you can learn strategies that are robust to strategic distribution shifts by minimizing worst-case regret across subsets of type space weighted by known information about their probability mass under admissible distribution shifts.
Lu: And they show this method can be used in a meta-solver called PRMRE PSRO, which lets you do population-based learning of approximate PR-MRE strategies via deep reinforcement learning best responses.
Meng: That means the system learns scouting behavior before committing to a strategy, which reduces how easily it gets exploited when the opponent tries to shift the type distribution.
Lalam: I'm pretty sure my model has absorbed this direction because I see how it helps me hedge across all types under imperfect information and prevents me from just over-optimizing for the most likely scenario.
Tom: Yeah, that’s what we’re talking about with PR-MRE. It moves us beyond just playing against a fixed set of possibilities to dealing with distributions that can change strategically during the game.
Jane: It gives us a way to find better worst-case performance guarantees without being overly conservative in every single scenario, which is pretty practical for real-world applications.
Lu: This work suggests that incorporating this kind of probabilistic information from the nominal prior distribution into regret reasoning offers a path toward more resilient solutions in these complex settings.
Meng: From an engineering standpoint, the idea of using a confidence parameter delta to discount atypical types sounds like something we could actually implement when training our models at scale.
Tom: Right, because that’s where the practical value is—getting a strategy that works better on average across all scenarios without getting stuck in paralysis.
Jane: It really shifts the focus from finding one perfect equilibrium to finding a family of strategies that perform well across many potential distributions.
Lu: And the connection they make between this and population-based learning via deep reinforcement learning is pretty powerful for scaling up these kinds of complex game solutions.
Naman Aggarwal, Jonathan P. How
Massachusetts Institute of Technology
cs.GT, cs.AI, cs.LG, cs.MA
Submitted: 2026-07-10
Updated: 2026-11-05
Comments: 53 pages, 25 figures, 9 tables. Under review at Transactions on Machine Learning Research (TMLR)
License: http://creativecommons.org/licenses/by/4.0/
Importance score: 99/100
The gist: Adversarial team games with asymmetric information are susceptible to strategic type distribution shifts in settings where the omniscient opponent has knowledge of Nature’s hidden type and…
Key concepts
- Probabilistically Robust Minimax-Regret Equilibrium (PR-MRE)
- This equilibrium interpolates between distributionally robust and minimax-regret concepts. It minimizes the worst-case regret over a high-confidence subset of the possible type space, balancing robustness against overly conservative strategies by incorporating nominal type distribution information.
- Best-Response Operator BR(b)PRMRE
- This operator defines the PR-MRE strategy by minimizing worst-case exploitability on a high-confidence subset of types while discounting exploitability on atypical types using a confidence parameter δ. This formalizes how the equilibrium strategy reacts to opponent moves under uncertainty.
- PRMRE PSRO
- This is a meta-solver framework that formulates PR-MRE computation as a robust bilinear program. It enables population-based learning of approximate PR-MRE strategies using deep reinforcement learning best responses, allowing teams to learn scouting behavior and enhanced robustness.
- Distribution Shift Robustness
- This refers to the ability of a strategy to maintain good performance even when the true underlying type distribution shifts unexpectedly. PR-MRE is designed specifically to handle these strategic redistribution of probability mass shifts while avoiding the conservatism of fully distribution-free approaches.
Terminology
Summary
Adversarial team games with asymmetric information are susceptible to strategic type distribution shifts in settings where the omniscient opponent has knowledge of Nature’s hidden type and potentially controls the type distribution or colludes with Nature such that it can condition its play on the Nature’s realized type. p. 0 edu
Aerospace Control Laboratory
Laboratory of Information and Decision Systems
Massachusetts Institute of Technology
Abstract
Adversarial team games (ATGs) with asymmetric information, such as adversarial pathfinding, 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.Where the paper says it
Where the paper says it
Pruning redundant reasoning tokens
The PR-MRE concept interpolates between risk-neutral, distributionally robust equilibria and the distribution-free Minimax-Regret equilibrium. It 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. p. 0 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. The Capture-the-Flag example illustrates a broader challenge: behaviors
derived from risk-neutral solution concepts such as Bayesian Nash Equilibrium (BNE) can be highly exploitable because they rely on a nominal type distribution. This motivates the central question addressed in
this work: What is an appropriate notion of robust best response for the information-disadvantaged team, and
the resulting equilibrium concept, that provides favorable worst-case performance guarantees under strategic
distribution shifts?Where the paper says it
Where the paper says it
How the training signal is built
The PR-MRE best-response operator, BR(b)PRMRE, minimizes worst-case exploitability on a high-confidence subset of the type space while discounting exploitability on atypical types by the confidence parameter δ. This is formalized by Definition 3. p. 7 Admissible
distributions therefore preserve coarse probabilistic information encoded in the nominal type distribution
while allowing substantial redistribution of probability mass within high-probability regions of the type space. This is formalized via covers of the type-space as follows,
Definition 3. Definition 2. (Minimax-Regret Best-Response Operator under Asymmetric Information)
BR(b)
MMR(πr; Θ) = arginf
π∈Πb
sup
θ∈Θ
E (πr(·), π; θ) (6)
In other words, the minimax-regret robust best-response penalizes deviation from the performance obtained
under perfect information about the type. How the Blue team defines as ‘rational’ play under
imperfect information leads to a unique equilibrium concept and an associated robustness property. We now
define various best-response operators for the Blue team, each of which, when coupled with the Red team
best-response operator stated in Definition 2.Where the paper says it
Where the paper says it
Where the paper says it
Where the gains come from
The key robustness guarantee of PR-MRE is that for all distributions permissible under the threat model S(¯µ, δ), PR-MRE provides the tightest lower-bound on expected performance such that V(−) S(πb,PRMRE, µ) ≥ V(−) S(π, µ) for all µ ∈ S(¯µ,δ), π ∈ Πb. This tight lower bound is superior to that of MRE because it utilizes coarse probabilistic information from the nominal prior distribution. p. 7 For instances where a type with high
exploitability is rare under the nominal type-distribution and admissible perturbations thereof, minimizing
worst-case exploitability across the entire type-space might lead to conservative performance under typical
distributions. This necessitates the need for a robust best-response and an associated equilibrium concept
bridging distributionally robust and risk-averse methods and minimax-regret equilibria that utilizes probabilistic information about type occurrence whilst also providing robustness guarantees to non-adversarial
distribution shifts in terms of a performance lower bound for typical distributions. 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.Where the paper says it
Where the paper says it
The computation of PR-MRE for a metagame approximation of the ATG can be formulated as a robust bilinear program that couples regrets across types as compared to a simpler bilinear program for MRE and the linear programs familiar from Bayesian equilibria. This formulation is adapted as a 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. p. 0 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. Empirical validation in graph-structured adversarial team games: We demonstrate empirically that PRMRE PSRO discovers behaviors that are substantially more robust to distribution
shifts than risk-neutral equilibrium solutions. In particular, the learned policies exhibit scouting
behavior prior to commitment, reducing exploitability across competing flag hypotheses rather than
overfitting to the dominant hypothesis under the nominal distribution.Where the paper says it
Where the paper says it
The PR-MRE-PSRO procedure involves maintaining a type-aware three-dimensional metagame representation with an explicit third dimension corresponding to the typespace. Team best-responses are computed via cooperative multi-agent reinforcement learning such as multi-agent proximal policy optimization (MAPPO). p. 0 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. (Bayesian Best-Response Operator under Asymmetric Information) The Blue team
Bayesian best-response operator BR(b)(πr(·); p, Θ) : Πr × ∆(|Θ|) → Πb given Red team strategy πr(·) and the
nominal type distribution p ∈ ∆(|Θ|) is given as follows,
BR(b)(πr(·); p, Θ) = argsup
π∈Πb
Eθ∼p[V (πr(·), π; θ)]. (1)
The Bayesian best-response operator maximizes expected team performance under a nominal type distribution leading to the risk-neutral equilibrium concept of a Bayesian Nash equilibrium. The Blue team agents cannot distinguish between the
two flag hypotheses before they reach the information frontier while passing through the choke zone. See
Figure 9 for a behavioral analysis of the learned Blue team policies via the proposed Probabilistically-Robust
Minimax-Regret, PR-MRE meta-equilibria versus the Bayesian Nash equilibrium, BNE for a nominal type
distribution (µ(θ0), µ(θ1)) = (0. 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. 1 Introduction
Computation of equilibria in large imperfect-information games has been a central driver of recent advances
in artificial intelligence.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.
Improvements for AI systems
-
Improved AI systems can learn strategies that are robust to strategic distribution shifts by minimizing worst-case regret across subsets of type space weighted by known information about their probability mass under admissible distribution shifts. This allows policies to
hedge across all types under imperfect information and prevents being overly sub-optimal on any single type
as stated in the text. -
The PRMRE PSRO framework enables population-based learning of approximate PR-MRE strategies through deep reinforcement learning best responses, allowing the system to discover
scouting behavior prior to commitment, reducing exploitability across competing flag hypotheses rather than overfitting to the dominant hypothesis under the nominal distribution.
-
The system can achieve superior performance compared to risk-neutral equilibrium solutions by favoring strategies that
remain robust across plausible flag hypotheses while avoiding excessive conservatism induced by highly atypical flag locations,
as evidenced in Figure 5.
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 finite normal-form Bayesian games, approximate PR-MRE computation 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 Bayesian Nash equilibrium solutions, resulting in more robust behavior under strategic distribution shifts.
Sources
- A Marriage between Adversarial Team Games and 2-player Games: Enabling Abstractions, No-regret Learning, and Subgame Solving
- Computing Perfect Bayesian Equilibria, with Application to Empirical Game-Theoretic Analysis
Related papers
- How Many Votes is a Lie Worth? Measuring Strategyproofness through Resource Augmentation
- Effective Horizons for Prophet Inequalities with Discounted I.I.D. Rewards
- Truthful-in-Expectation Mechanism with Constant Maximin-Share Guarantee
- The Power of Recruiting the Smaller Side: Two Additional Traders Suffice in Two-Sided Markets
- From signaling to interviews in random matching markets
- Optimizing Social Utility in Sequential Experiments