Beyond Bayesian Nash: Learning Minimax-Regret Equilibria for Adversarial Team Games under Asymmetric Information

arXiv:2607.09993 · cs.GT, cs.AI, cs.LG, cs.MA · Submitted 2026-07-10 · Read on arXiv

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

Where the paper says it

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.

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. p. 0
Where the paper says it

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.

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

Where the paper says it

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.

This approach is motivated by the need for robust best response notions that provide favorable worst-case performance guarantees under strategic distribution shifts. p. 1
Where the paper says it

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?

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

Where the paper says it

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.

3, which defines the operator as arginf π∈Πb sup µ∈S(¯µ,δ) X θ∈Θ µ(θ)E (πr(·), π; θ). p. 6
Where the paper says it

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.

The resulting equilibrium concept is characterized by a fixed-point system involving the Blue and Red team best-response operators under asymmetric information. p. 4
Where the paper says it

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 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

Where the paper says it

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.

Empirical validation shows that PR-MRE discovers strategies with substantially improved worst-case performance across hidden types compared to risk-neutral equilibrium solutions. p. 0
Where the paper says it

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.

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

Where the paper says it

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.

The final result is that team strategies learned via PRMRE PSRO exhibit learned scouting behavior and enhanced robustness to distribution shift as compared to BNE PSRO. p. 3
Where the paper says it

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.

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

Where the paper says it

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.

The omniscient Red team uses a value-based team best-response BRVal criterion that maximizes expected Red team payoff against an opponent distribution given by the Blue PR-MRE meta-equilibrium yk at the latest PSRO iteration. p. 5
Where the paper says it

(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 uninformed Blue team best-responds to a uniform type distribution and the type-conditioned Red PR-MRE meta-equilibrium xk(·) with a minimax-regret stopping criteria BRMMR until the robust average regret of the training policy πB falls below that of the Blue team PR-MRE meta-equilibrium at the latest PSRO iteration. p. 3
Where the paper says it

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.

The resulting policy is invariant to the choice of neural network architecture and provides a general methodology to train robust team policies to distribution shifts under hidden information. p. 0
Where the paper says it

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.

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

  1. 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.

  2. 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.

  3. 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

Related papers