Paper deep dive
Beyond Bayesian Nash: Learning Minimax-Regret Equilibria for Adversarial Team Games under Asymmetric Information
Naman Aggarwal, Jonathan P. How
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 95%
Last extracted: 7/14/2026, 4:33:29 AM
Summary
The paper introduces Probabilistically Robust Minimax-Regret Equilibrium (PR-MRE), a novel equilibrium concept for adversarial team games with asymmetric information. PR-MRE addresses the limitations of risk-neutral approaches like Bayesian Nash Equilibrium (BNE) and distributionally robust methods by minimizing worst-case regret over high-confidence subsets of the type space, providing robustness against strategic distribution shifts without excessive conservatism. The authors propose PRMRE-PSRO, a scalable meta-solver framework combining robust bilinear programming, semidefinite relaxation, and deep reinforcement learning to compute approximate PR-MRE strategies. Empirical results on graph-structured Capture-the-Flag games demonstrate that PR-MRE yields significantly more robust policies under hidden opponent types compared to existing equilibrium solutions.
Entities (10)
Relation Signals (7)
Naman Aggarwal → authored → Beyond Bayesian Nash: Learning Minimax-Regret Equilibria for Adversarial Team Games under Asymmetric Information
confidence 99% · Naman Aggarwal namanagg@mit.edu... Beyond Bayesian Nash: Learning Minimax-Regret Equilibria for Adversarial Team Games under Asymmetric Information
Jonathan P. How → affiliatedwith → Massachusetts Institute of Technology
confidence 98% · Jonathan P. How jhow@mit.edu... Massachusetts Institute of Technology
Bayesian Nash Equilibrium → issensitiveto → Strategic Distribution Shifts
confidence 96% · Existing risk-neutral solution concepts, such as Bayesian Nash equilibrium (BNE), are sensitive to distribution shifts
PR-MRE → minimizes → worst-case regret
confidence 95% · PR-MRE minimizes worst-case regret over a high-confidence subset of the type space, providing protection against strategic redistribution of probability mass
PRMRE-PSRO → computes → PR-MRE
confidence 94% · PRMRE-PSRO, enabling population-based learning of approximate PR-MRE strategies via deep reinforcement learning best responses
PRMRE-PSRO → utilizes → Semidefinite Relaxation
confidence 93% · adapt this relaxation into a novel meta-solver within a robust double-oracle framework, PRMRE-PSRO
Graph Capture-the-Flag → validates → PR-MRE
confidence 91% · Experiments on graph-structured adversarial team games demonstrate that PR-MRE discovers strategies with substantially improved worst-case performance
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
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.
Tags
Links
- Source: https://arxiv.org/abs/2607.09993v1
- Canonical: https://arxiv.org/abs/2607.09993v1
Trouble viewing inline? Open PDF directly →
Full Text
119,124 characters extracted from source content.
Expand or collapse full text
Beyond Bayesian Nash: Learning Minimax-Regret Equilibria for Adversarial Team Games under Asymmetric Information Naman Aggarwal namanagg@mit.edu Aerospace Control Laboratory Laboratory of Information and Decision Systems Massachusetts Institute of Technology Jonathan P. How jhow@mit.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 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. 1 Introduction Computation of equilibria in large imperfect-information games has been a central driver of recent advances in artificial intelligence. A key challenge in such settings is determining how strategic agents should reason about uncertainty. Existing equilibrium concepts differ fundamentally in their treatment of risk and robustness, ranging from risk-neutral formulations that optimize expected performance to risk-averse approaches that guard against uncertainty through worst-case reasoning. These differing notions of rationality lead to markedly different behaviors and robustness guarantees. Consequently, the literature on equilibria and equilibrium refinements for imperfect-information games is extensive (see Table 1 for an overview). Figure 1: Graph-Structured Capture-the-Flag (Graph CtF) with Blue Team’s Imperfect Information about the Red Flag Location: 2v2 CtF on a graph topology with Flag Uncertainty for Blue Team seen as two potential Red Flag locations. Limited Knowledge: Graph assumed known, but limited flag visibility (orange (yellow) indicates nodes on Left (Right) Flag are visible). Asymmetric: Blue agents cannot distinguish between Red flag locations at other nodes, whereas Red agents have perfect information about Blue flag. In Bayesian games, a Nature player moves before play begins and assigns each player a type drawn from a joint type distribution. Harsanyi’s seminal framework harsanyi_1; harsanyi_2 models strategic interactions with incomplete information by introducing the Bayesian Nash Equilibrium (BNE), in which each player maximizes expected utility under the common prior distribution over types. While BNE provides a principled solution concept for games with hidden information, it relies critically on the common prior assumption: although players do not observe each other’s private types, the underlying type distribution is assumed to be common knowledge. This assumption can be restrictive in real-world strategic interactions involving asymmetric information and deception. In many settings, the type distribution itself may be uncertain, evolve over time, or even be influenced by an adversary with an information advantage. We refer to such changes as strategic distribution shifts. Unlike classical distributionally robust optimization (DRO), which models uncertainty through structured ambiguity sets such as KL-divergence, Wasserstein, or f-divergence balls around a nominal distribution, strategic distribution shifts need not admit a local divergence-based characterization. They may instead arise from regime changes, task-level shifts, or adaptive opponents that fundamentally alter the distribution of types. Figure 1 provides a concrete example of such strategic distribution shifts in an adversarial search game. The Blue team must locate and capture a hidden Red flag before a timeout, while the Red team knows the true flag location and can defend accordingly. Blue only has access to a prior belief over possible flag locations (e.g., 60% right and 40% left), making the flag location a hidden type known only to Red. Consequently, a strategy that is optimized for a nominal prior may become vulnerable when the underlying type distribution changes or when Red exploits Blue’s prior assumptions. We consider imperfect-information games with deception, specifically asymmetric-information games in which the type distribution may undergo strategic distribution shifts and the informed opponent can condition its play on the realized type. 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? Table 1: Taxonomy of robust Blue best-responses (BRs) according to the optimization objective and the amount of information trusted about Nature’s nominal. Each robust Blue BR coupled with the informed Red BR leads to a unique equilibrium concept (see Section 2.1 for details) and an associated robustness property (see Table 2) for the adversarial game with asymmetric information. High →Trust in Nature’s Nominal Distribution 64.01869pt\ Trust in Nature's Nominal Distribution\ 64.01869pt Low Objective Trust Full Local Coarse None Payoff Bayesian BR (BNE) Nominal Prior DRO-Ball Local Perturbations DRO-Structured Typicality-preserving shifts (Structured type ambiguity) Worst-Case BR Entire type-simplex (Adversarial Nature) Regret !5– !5– !40 PR-MRE Typicality-preserving shifts (Structured type ambiguity) !20 MRE Entire type-space Distributionally robust optimization (DRO) protects against uncertainty through ambiguity sets around a nominal distribution. While effective for modeling local perturbations, DRO-based equilibrium concepts provide guarantees only within the specified ambiguity set and may fail under larger regime changes. For example, in a three-flag version of the search-and-capture game, a nominal type distribution of (0.6,0.1,0.3)(0.6,0.1,0.3) may shift to (0.0,0.05,0.95)(0.0,0.05,0.95), fundamentally altering the strategic landscape. Such strategic distribution shifts are not naturally captured by local divergence-based uncertainty models. At the other extreme, a fully worst-case robust approach reasons against an adversarial type distribution over the entire type simplex, but this can be overly conservative because it effectively concentrates on the most difficult type regardless of its likelihood. To bridge this gap, we consider strategic distribution shifts that preserve type typicality: types that are rare under the nominal distribution remain rare under admissible shifts, while probability mass may be redistributed arbitrarily among typical types. We then adopt a regret-based notion of robustness. Regret, or exploitability, measures the performance loss incurred by acting under imperfect information relative to a type-conditioned optimum. A Minimax-Regret Equilibrium (MRE) minimizes worst-case regret across all types and yields a distribution-free certificate in the form of a uniform lower bound on performance under arbitrary distribution shifts. While robust, MRE can be conservative because it ignores probabilistic information about type occurrence. We therefore introduce the Probabilistically Robust Minimax-Regret Equilibrium (PR-MRE), which incorporates coarse probabilistic information through the typicality-preserving threat model. PR-MRE interpolates between risk-neutral and worst-case approaches, yielding tighter performance guarantees while retaining robustness to strategic distribution shifts. Computing MRE and PR-MRE in general adversarial team games remains an open challenge. Existing solution methods for ATGs anagnostides2026algorithms; atgs_neurips_2024; xiao2026solving; pmlr-v235-zhang24b; Celli2018-yn; pmlr-v162-carminati22a; anagnostides2023efficiently and extensive-form games (EFGs), such as Counterfactual Regret Minimization (CFR) zinkevich2007regret, are designed to compute Nash equilibria and do not naturally extend to regret-based robustness objectives under structured type uncertainty. Moreover, MRE was originally introduced in the context of finite mechanism-design settings mre; renou2010minimax; renou2011implementation, and existing formulations do not readily generalize to the large strategy spaces such as team treeplexes encountered in adversarial team games. To address this challenge, we propose PR-MRE PSRO, a robust double-oracle framework for computing approximate MRE and PR-MRE strategies via metagame approximation. We show that the resulting metagame problems can be formulated as bilinear and robust bilinear programs, respectively, and derive tractable semidefinite relaxations that serve as novel meta-solvers within a population-based learning framework. Combined with deep reinforcement learning best-response oracles, the proposed approach enables scalable computation of robust strategies in graph-structured adversarial team games. From Table 1, the optimization objective (payoff vs. regret) and the degree of trust placed in Nature’s nominal type distribution define a two-dimensional design space of robust equilibrium concepts, with PR-MRE occupying the previously unexplored regime of regret-based best-response under coarse probabilistic information from the nominal. We formally state our contributions as follows, 1. New equilibrium concept, PR-MRE: We introduce a novel robust equilibrium concept for asymmetric information games, Probabilistically-Robust Minimax-Regret equilibrium (PR-MRE) that interpolates between risk-neutral, distributionally-robust equilibria and the distribution-free Minimax-Regret equilibrium (MRE). In contrast to MRE that treats all types equally likely, PR-MRE utilizes coarse probabilistic information to minimize worst-case exploitability across subsets of the type-space weighted by known information about their probability mass under admissible distribution shifts. 2. Typicality-preserving threat model and robustness guarantees: We show that the proposed PR-MRE best-response for the information-disadvantaged team provides a robustness certificate in the form of the tightest performance lower bound under strategic distribution shifts that redistribute probability mass arbitrarily among high-confidence subsets of the type-space. 3. Scalable approximation algorithm, PRMRE-PSRO: We propose a metagame approximation to compute MRE and PR-MRE in adversarial team games under asymmetric information. We show that the metagame problems corresponding to MRE and PR-MRE can be formulated as bilinear and robust bilinear programs respectively. We provide a tractable SDP relaxation that is incorporated as a robust meta-equilibria within a double-oracle framework, PRMRE PSRO to compute robust team policies for graph-structured ATGs under asymmetric information. 4. 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. 2 Graph-Structured Adversarial Team Games under Asymmetric Information Figure 2: Graph Capture-the-Flag with two Red flag hypotheses – θ0 _0 (left) and θ1 _1 (right) (marked as the two red nodes in the top basin), the shaded pink zone represents the choke zone corresponding to the two corridors, and the purple (orange) nodes represent the information frontier or the nodes from which the left (right) flag hypothesis is visible. Red team agents initialize in the top-basin whereas the Blue team agents initialize in the bottom-basin below the choke zone. 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−MREPR-MRE meta-equilibria versus the Bayesian Nash equilibrium, BNEBNE for a nominal type distribution (μ(θ0),μ(θ1))=(0.8,0.2)(μ( _0),μ( _1))=(0.8,0.2). We study graph-structured adversarial team games under asymmetric information, instantiated as Graph Capture-the-Flag (Graph CtF). Two teams of agents move on an undirected graph over a finite horizon and optimize opposing objectives – Blue team wins if the Blue agents capture the Red flag, and Red team wins if they successfully defend their flag for the time-horizon. The key asymmetry is that the Red team observes the true flag location, while the Blue team acts under uncertainty over a finite set of flag hypotheses. Formally, the game is defined by the tuple =⟨,nr,nb,Θ,T⟩, G= <G,n_r,n_b, ,T >, where =⟨ν,ℰ⟩G= ν,E is an undirected graph with node set ν, nrn_r and nbn_b are the number of Red and Blue agents, Θ⊆ν ν is the set of possible flag locations, and T is the time horizon. The hidden type is sampled as θ∼μ∈Δ(Θ)θ μ∈ ( ). The game proceeds sequentially over T steps. At each time step, agents select actions based on their available information and move on the graph according to the transition dynamics. The Red team observes the realized type θ, whereas the Blue team does not, and must act based only on its observation history. Accordingly, we consider policy classes Πr _r and Πb _b, where Red policies may condition on θ and history, while Blue policies depend only on the Blue team’s observation history. Let V(πr,πb;θ)V( _r, _b;θ) denote the expected return of the Blue team under policies πr∈Πr _r∈ _r and πb∈Πb _b∈ _b when the underlying type is θ. The nominal type distribution μ(⋅)μ(·) induces a standard Bayesian objective. In deceptive settings, however, the true distribution over types may differ substantially from μ(⋅)μ(·), rendering policies optimized for the nominal distribution highly exploitable. This motivates the search for equilibrium concepts and associated best-response notions that remain robust under strategic distribution shifts. 2.1 Equilibrium Concepts and Robustness Properties Table 2: Robustness properties associated with the various Blue best-responses (BRs) corresponding to different optimization objectives and trust levels on Nature (see Table 1 for taxonomy on robust Blue BRs). High →Trust in Nature’s Nominal Distribution 64.01869pt\ Trust in Nature's Nominal Distribution\ 64.01869pt Low Objective Trust Full Local Coarse None Payoff No Robustness Worst-case payoff certificate Local perturbations Worst-case payoff certificate Typicality-preserving shifts (Structured type ambiguity) Worst-case payoff certificate Entire type-simplex Regret !5– !5– !40 Worst-case regret certificate ⇔ ULB (Lemma 4) Typicality-preserving shifts (Structured type ambiguity) !20 Worst-case regret certificate ⇔ ULB (Lemma 1) Entire type-space In this section, we present a unified treatment of various equilibrium concepts in the specific context of adversarial team games and analyse their robustness properties with respect to shifts in the type distribution. For the case of asymmetric information, the Red team has perfect knowledge of Nature’s hidden type (flag location) and can condition its play on the observed type. Definition 2.1. The Red team best-response operator BR(r)(πb;θ):Πb×Θ→ΠrBR^(r)( _b;θ): _b× → _r to the Blue team strategy πb∈Πb _b∈ _b and observed type θ is given as BR(r)(πb;θ)=arginfπ∈ΠrV(π(⋅),πb;θ)BR^(r)( _b;θ)= *arginf _π∈ _rV(π(·), _b;θ). Thus, for a given Blue team strategy, the Red team computes a best-response that minimizes the expected Blue team return conditioned on the observed 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.1 defines a unique equilibrium. 2.1.1 Risk-Neutral Methods Definition 2.2. (Bayesian Best-Response Operator under Asymmetric Information) The Blue team Bayesian best-response operator BR(b)(πr(⋅);p,Θ):Πr×Δ(|Θ|)→ΠbBR^(b)( _r(·);p, ): _r× ( )→ _b given Red team strategy πr(⋅) _r(·) and the nominal type distribution p∈Δ(|Θ|)p∈ ( ) is given as follows, BR(b)(πr(⋅);p,Θ)=argsupπ∈Πbθ∼p[V(πr(⋅),π;θ)]. ^(b)( _r(·);p, )= *argsup_π∈ _bE_θ 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. Definition 2.3. (Bayesian Nash Equilibrium, BNE) The ex-ante Bayesian Nash equilibrium (πb,BNE∗(p),πr∗)(π^*_b,BNE(p),π^*_r) for a nominal type distribution p is defined as the fixed point of the best-response operators defined in Definition 2.1 and Definition 2.2 as the following, πb,BNE∗(p)∈BR(b)(πr∗(⋅);p,Θ)andπr∗(⋅)∈BR(r)(πb,BNE∗(p);⋅).π^*_b,BNE(p) ^(b)(π^*_r(·);p, )\ and\ π^*_r(·) ^(r)(π^*_b,BNE(p);·). The BNE is an ex-ante equilibrium concept in which players commit to strategies before play commences and optimize expected utility under the nominal type distribution. We focus on this setting because it aligns naturally with population-based training methods in which meta-equilibria are computed over sets of competing policies. For ex-post notions that incorporate sequential rationality and belief consistency, we refer the reader to refinements such as the perfect Bayesian Nash equilibrium (PBNE) ouyang2016dynamic; konicki2026computingperfectbayesianequilibria. From Definition 2.3, the BNE can equivalently be interpreted as a solution to the following saddle-point equation, θ∼p[V(πr∗(⋅),πb;θ)]≤θ∼p[V(πr∗(⋅),πb,BNE∗(p);θ)]≤θ∼p[V(πr(⋅),πb,BNE∗(p);θ)]. _θ p [V(π^*_r(·), _b;θ) ] _θ p [V(π^*_r(·),π^*_b,BNE(p);θ) ] _θ p [V( _r(·),π^*_b,BNE(p);θ) ]. (2) At the saddle point given by the strategy-tuple (πb∗,πr∗(⋅)) (π^*_b,π^*_r(·) ) (the BNE), no team has any incentive to deviate given the opponent team strategy. An exact computation of the saddle point eq. (2) for the general formulation where strategy spaces Πr _r and Πb _b are sequence-form polytopes (or team treeplexes) is intractable. Approaches in the MARL community to find tractable approximations to the equilibria of high-dimensional games such as the graph-structured adversarial team game introduced in Section 2 broadly consists of DO-based carminati2022marriageadversarialteamgames; tme_cor_psro, CFR-based treeplexes_efg_kroer and PPO-based sokkota2026. Risk-neutral equilibria, such as BNE (2), do not take into account potential strategic shifts in the type distribution, which motivates the following class of distributionally-robust and risk-averse methods to manage risk posed by ambiguity due to deception. 2.1.2 Distributionally-Robust Methods A distributionally-robust Blue team response given opponent team strategy πr(⋅)∈Πr _r(·)∈ _r optimizes for the best worst-case performance for type distributions belonging to an ambiguity set. The distributionally-robust best-response operator corresponding to a distributional ambiguity set P is defined as BRDRO(b)(πr(⋅);,Θ)=argsupπ∈Πbinfq∈θ∼q[V(πr(⋅),π;θ)]BR^(b)_DRO( _r(·); P, )= *argsup _π∈ _b _q∈ PE_θ q[V( _r(·),π;θ)]. θ∼f[V(πr(⋅),πb,DRO(πr(⋅),);θ)]≤infq∈θ∼q[V(πr(⋅),πb,DRO(πr(⋅),);θ)]. _θ f[V( _r(·), _b,DRO( _r(·), P);θ)]≤ _q∈ PE_θ q[V( _r(·), _b,DRO( _r(·), P);θ)]. (3) The robustness guarantee of the DRO best-response is restricted to distributions contained within the ambiguity set P. Consequently, DRO does not provide performance guarantees under strategic distribution shifts that fall outside the prescribed uncertainty model. 2.1.3 Adversarial Nature and Worst-Case Robustness A rational, albeit pessimistic Blue team best-response under adversarial type selection is given by BRwc(b)(πr(⋅))=argsupπ∈Πb(infq∈Δ(|Θ|)θ∼q[V(πr(⋅),π;θ)])BR^(b)_wc( _r(·))= *argsup _π∈ _b ( _q∈ ( )E_θ q[V( _r(·),π;θ)] ). Let qwcq_wc be the adversarial type distribution corresponding to the above worst-case best-response operator on given πr(⋅) _r(·) such that for πb,wc(πr(⋅))∈BRwc(b)(πr(⋅)) _b,wc( _r(·)) ^(b)_wc( _r(·)), supπ∈Πbinfq∈Δ(|Θ|)θ∼q[V(πr(⋅),π;θ)]=θ∼qwc[V(πr(⋅),πb,wc(πr(⋅));θ)]. _π∈ _b _q∈ ( )E_θ q[V( _r(·),π;θ)]=E_θ q_wc[V( _r(·), _b,wc( _r(·));θ)]. For a given Red team strategy, the above worst-case best-response operator solves a zero-sum game between the Blue team and Nature to compute a robust Blue team best-response. This leads to the following three-player equilibrium formulation where Nature acts as an adversary and plays an adversarial type distribution such that the Red team and Nature collude (since Red can correlate play with Nature) against the Blue team, πb,wc∗∈BRwc(b)(πr∗(⋅))andπr∗(⋅)∈BR(r)(πb,wc∗;⋅).π^*_b,wc ^(b)_wc(π^*_r(·))\ and\ π^*_r(·) ^(r)(π^*_b,wc;·). Worst-case robust equilibrium provides a global performance guarantee when the Nature is adversarial such that θ∼qwc[V(πr(⋅),π′;θ)]≤θ∼qwc[V(πr(⋅),πb,wc;θ)]E_θ q_wc[V( _r(·),π^ ;θ)] _θ q_wc[V( _r(·), _b,wc;θ)]. This however can lead to overly pessimistic strategies such that, θ∼qwc[V(πr(⋅),πb,wc;θ)]≤θ∼q∈[V(πr(⋅),πb,wc;θ)]≤θ∼q∈[V(πr(⋅),πb,DRO;θ)]. _θ q_wc[V( _r(·), _b,wc;θ)] _θ q [V( _r(·), _b,wc;θ)] _θ q [V( _r(·), _b,DRO;θ)]. (4) The three-player game formulation treats all types with equal importance independent of likelihood under nominal distribution and computes a robust Blue response to an adversarial type distribution that concentrates mass potentially on the hardest type. Such an approach discards available probabilistic information about the occurrence of types and could lead to behavior with poor typical performance under non-adversarial distribution shifts. In the pursuit of global performance guarantees, we discuss a tangential approach in the following subsection that reasons about regret with respect to type-optimal best-responses. 2.1.4 Minimax-Regret Robust Best-Response and Minimax-Regret Equilibrium (MRE) Distributionally robust methods offer robustness only up to an ambiguity set centered at the nominal distribution and are suitable for settings when protection is sought against mis-specification of the nominal distribution (prior) and not strategic distribution shifts. Strategic distribution shifts refer to a smart Nature running an oracle procedure to compute a type distribution that potentially places probability mass adversarially on high-regret types. We characterize regret (or exploitability) with respect to a type as follows, @picture Definition 2.4. (Exploitability) We define the exploitability (or regret) of Blue team policy π on type θ given Red team policy πr(⋅) _r(·) as, ℰ(πr(⋅),π;θ)=supπ∗∈ΠbV(πr(⋅),π∗;θ)−V(πr(⋅),π;θ), ( _r(·),π;θ )= _π^*∈ _bV( _r(·),π^*;θ)-V( _r(·),π;θ), (5) and the worst-case exploitability of π given πr(⋅) _r(·) over the type-space as ℰ(πr(⋅),π;Θ)=supθ∈Θℰ(πr(⋅),π;θ)E ( _r(·),π; )= _θ∈ E ( _r(·),π;θ ). @picture We define the following Blue team robust best-response given opponent team strategy πr(⋅) _r(·) that minimizes worst-case regret with respect to type-optimal best-responses across the type-space. Definition 2.5. (Minimax-Regret Best-Response Operator under Asymmetric Information) BRMMR(b)(πr;Θ)=arginfπ∈Πbsupθ∈Θℰ(πr(⋅),π;θ) ^(b)_MMR( _r; )= *arginf_π∈ _b _θ∈ E ( _r(·),π;θ ) (6) In other words, the minimax-regret robust best-response penalizes deviation from the performance obtained under perfect information about the type. Such a rational attitude hedges across all types under imperfect information and prevents being overly sub-optimal on any single type. The ex-ante Minimax-Regret (MRE) equilibrium (πb∗,πr∗)(π^*_b,π^*_r) is defined as the fixed point of the best-response operator defined in Def. 2.5, πb,MRE∗∈BRMMR(b)(πr∗;Θ)andπr∗(⋅)∈BR(r)(πb,MRE∗;⋅).π^*_b,MRE ^(b)_MMR(π^*_r; )\ and\ π^*_r(·) ^(r)(π^*_b,MRE;·). The MRE best-response is distribution-free and provides global performance guarantees independent of any restrictive assumptions about the type to lie within an ambiguity set around the nominal distribution. The key consequence of minimax-regret reasoning is that it induces a performance certificate that is valid for every type distribution in the simplex. This certificate is formalized below. @picture Lemma 1 (Uniform Performance Lower Bound). For a given Red team strategy πr(⋅) _r(·), the expected payoff under Blue team strategy πb _b and a type distribution μ(⋅)μ(·) can be bounded from below as follows such that the lower bound is tight, i.e., ∃q∈Δ(|Θ|)∃\ q∈ ( ) for which equality holds, θ∼μ[V(πr(⋅),πb;θ]≥(−)(πb,μ)=∑θ∈Θμ(θ)supπ∈ΠbV(πr,π;θ)−ℰ(πr(⋅),πb,Θ)∀μ∈Δ(|Θ|). _θ μ[V( _r(·), _b;θ] ^(-)( _b,μ)= _θ∈ μ(θ) _π∈ _bV( _r,π;θ)-E( _r(·), _b, )\ ∀\ μ∈ ( ). (7) Proof. Proof in Appendix A.1. ∎ @picture From (7), the lower-bound on performance can be decoupled into a per-type component, free of the decision variable πb _b, representing optimal decision under perfect information and a second term denoting the worst-case exploitability of the decision πb _b across the type-space. Thus, the MRE best-response πb,MRE∈BRMMR(b)(πr;Θ) _b,MRE ^(b)_MMR( _r; ) from (6) can equivalently be interpreted as the decision πb,MRE _b,MRE that maximizes the performance lower-bound (−)(⋅,μ)V^(-)(·,μ) for all type distributions μ(⋅)μ(·) in the type-simplex i.e., BRMMR(b)(πr;Θ)=arginfπ∈Πbsupθ∈Θℰ(πr(⋅),π;θ)=argsupπ∈Πb(−)(π,μ)∀μ(⋅)∈Δ(|Θ|).BR^(b)_MMR( _r; )= *arginf _π∈ _b _θ∈ E ( _r(·),π;θ )= *argsup _π∈ _bV^(-)(π,μ)\ ∀\ μ(·)∈ ( ). In contrast to DRO methods that do not provide guarantees for perturbations outside the ambiguity set and worst-case robust equilibria that concentrate mass on hard types agnostic to the likelihood information contained in the nominal type distribution leading to poor typical performance under non-adversarial distribution shifts, MRE provides a uniform lower bound on performance across the type-simplex by hedging regret across all types. Limitation: MRE minimizes worst-case exploitability across the entire type-space and does not utilize useful probabilistic information from the nominal type distribution. 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. 3 Probabilistically-Robust Minimax-Regret Equilibria Motivated by the limitations of existing equilibrium concepts as discussed in Section 2.1, we introduce a novel robust best-response operator and the associated equilibrium concept – Probabilistically-Robust Minimax-Regret equilibria for ATGs under asymmetric information that minimizes exploitability across subsets of the type-space weighted by known information about their probability mass under admissible distribution shifts. Figure 3: Illustration of PR-MRE, nominal distribution μ¯(⋅)=(0.35,0.35,0.15,0.03,0.12) μ(·)=(0.35,0.35,0.15,0.03,0.12). The blue outer ellipse denotes the type space Θ=θ0,⋯,θ4 =\ _0,·s, _4\, the crosses denote specific types and the red dotted ellipses denote the set of low-probability covers Θl(μ¯,δ) _l( μ,δ) for various confidence levels δ. For (a), Θl(μ¯,0.12)=θ3,θ4 _l( μ,0.12)=\\ _3\,\ _4\\ such that under admissible shifts μ∈Δ(|Θ|)μ∈ ( ), μ(δ3)≤δ and μ(δ4)≤δμ( _3)≤δ and μ( _4)≤δ. Similarly for (b), Θl(μ¯,0.20)=θ2,θ3,θ3,θ4 _l( μ,0.20)=\\ _2, _3\,\ _3, _4\\ such that μ(θ2)+μ(θ3)≤δμ( _2)+μ( _3)≤δ and μ(δ3)+μ(δ4)≤δμ( _3)+μ( _4)≤δ, and for (c) Θl(μ¯,0.30)=θ2,θ3,θ4 _l( μ,0.30)=\ _2, _3, _4\ such that μ(θ2)+μ(θ3)+μ(θ4)≤δμ( _2)+μ( _3)+μ( _4)≤δ. Rather than minimizing worst-case exploitability uniformly across the entire type space as in MRE, PR-MRE focuses on high-confidence subsets while retaining robustness to low-probability covers defined through the confidence level δ. We first discuss the threat model. We consider distribution shifts that preserve type typicality, meaning that types that are rare under the nominal distribution remain rare under admissible shifts. 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, @picture Definition 3.1. (Probabilistic Covers of Type-Space) For a nominal type distribution μ¯(⋅) μ(·) and confidence parameter δ, a valid high-probability cover of the type-space ⊆Θ C is such that ∑θ∈μ¯(θ)≥1−δ _θ∈ C μ(θ)≥ 1-δ. The associated low-probability cover ℒ L to the high-probability cover C is defined as ℒ=c L= C^c such that ∑θ∈ℒμ¯(θ)≤δ _θ∈ L μ(θ)≤δ. @picture We characterize permissible perturbations to the nominal type distribution as given by the set of distributions that preserve all high-probability covers (or equivalently, all low-probability covers) of the type-space. For a nominal type distribution μ¯(⋅) μ(·) and confidence parameter δ, the set of all (1−δ)(1-δ)- high-probability covers Θ is defined as Θ(μ¯,δ)≔⊆Θ such that ∑θ∈μ¯(θ)≥1−δ ( μ,δ) \ C \ such that \ _θ∈ C μ(θ)≥ 1-δ\ and the set of all δ- low-probability covers is defined as Θℓ(μ¯,δ)≔c for all ∈Θ(μ¯,δ) _ ( μ,δ) \ C^c for all C∈ ( μ,δ)\. We also denote the set of all rare types under the nominal distribution and confidence level δ as Θr(μ¯,δ)=θ such that μ¯(θ)≤δ _r( μ,δ)=\θ such that μ(θ)≤δ\. We now formally characterize our threat model as follows, @picture Definition 3.2. (Threat Model) The permissible set of perturbed distributions (μ¯,δ)S( μ,δ) is given as (μ¯,δ)=μ(⋅)∈Δ(|Θ|) such that ∑θ∈ℒμ(θ)≤δ for all ℒ∈Θℓ(μ¯,δ)S( μ,δ)=\μ(·)∈ ( )\ such that \ Σ _θ∈ Lμ(θ)≤δ\ for all \ L∈ _ ( μ,δ)\. @picture In other words, the permissible perturbed distributions under our threat model allocate probability mass arbitrarily up to respecting typicality of types such that low-probability covers remain low probability. For instance, for a nominal distribution μ¯(⋅)=(0.35,0.35,0.15,0.03,0.12) μ(·)=(0.35,0.35,0.15,0.03,0.12) and δ=0.12δ=0.12, it is easy to verify that the low-probability cover is given by Θℓ(μ¯,0.12)=(θ3),(θ4) _ ( μ,0.12)=\( _3),( _4)\ (as depicted in Figure 3a) such that for any permissible perturbed distribution μ(⋅)∈(μ¯,δ)μ(·) ( μ,δ), μ(θ3)≤δμ( _3)≤δ and μ(θ4)≤δμ( _4)≤δ. Similarly for δ=0.2δ=0.2, the low probability cover is given by Θℓ(μ¯,0.20)=(θ2,θ3),(θ3,θ4) _ ( μ,0.20)=\( _2, _3),( _3, _4)\ and permissible distributions μ(⋅)μ(·) are such that μ(θ2)+μ(θ3)≤δμ( _2)+μ( _3)≤δ and μ(θ3)+μ(θ4)≤δμ( _3)+μ( _4)≤δ (Figure 3b), and for δ=0.3δ=0.3 (Figure 3c), μ(θ2)+μ(θ3)+μ(θ4)≤δμ( _2)+μ( _3)+μ( _4)≤δ. The inequality constraints arise as a direct consequence of the threat model that preserves coarse probabilistic information about type occurrence (all high-probability covers of the type-space) under distribution shift. Such a threat model makes sense for scenarios when the task hypotheses map to actual real-world configurations. For instance, for capture-the-flag, certain flag hypotheses might actually be realized with a bounded probability because of terrain traversability, other physical constraints etc. Geometry of (μ¯,δ)S( μ,δ): The threat model from Definition 3.2 admits a meaningful class of strategic perturbations not captured by ball-shaped ambiguity sets centered at a nominal type distribution (based on for example KL- or generalized f-divergence). Unlike ambiguity-set methods that constrain perturbations to remain close to the nominal distribution, our threat model permits arbitrary redistribution of probability mass within a high-confidence subset of the type space while preserving its aggregate probability mass. For the high-confidence subset Θ/Θr⊆Θ / _r , arbitrary allocations of probability mass across types within Θ/Θr / _r is allowed as long as the net mass over rare types Θr _r follows constraints posed by Definition 3.2. Consequently, the model admits highly concentrated (“peaky”) distributions that place most of their mass on a single type, while still preserving coarse probabilistic information about which regions of the type space are typical. Figure 3 illustrates the key distinction such that for μ¯=(0.35,0.35,0.15,0.03,0.12) μ=(0.35,0.35,0.15,0.03,0.12) and δ=0.12δ=0.12, (0,0,1,0,0)(0,0,1,0,0) is a permissible type distribution under the typicality-preserving threat model where μ(θ1),μ(θ2)μ( _1),μ( _2) shift from 0.35→00.35→ 0 and μ(θ3)μ( _3) shifts from 0.15→10.15→ 1. Other example distributions contained in the permissible set (μ¯,0.12)S( μ,0.12) include (0.12,0,0.76,0.06,0.06),(0.90,0,0,0.10,0)(0.12,0,0.76,0.06,0.06),(0.90,0,0,0.10,0) and (0,1,0,0,0)(0,1,0,0,0). This motivates a robust best-response operator that balances exploitability on high-probability regions of the type space against exploitability on atypical types. The resulting operator is defined as follows. @picture Probabilistically-Robust Minimax-Regret (PR-MRE) Best-Response Operator Definition 3.3. (PR-MRE Best-Response Operator under Asymmetric Information) For a given Red team strategy πr(⋅) _r(·), the probabilistically-robust MRE best-response operator for the Blue team is defined as follows, BRPRMRE(b)(πr(⋅);μ¯,δ)=arginfπ∈Πbsupμ∈(μ¯,δ)∑θ∈Θμ(θ)ℰ(πr(⋅),π;θ). ^(b)_PRMRE( _r(·); μ,δ)= *arginf_π∈ _b _μ ( μ,δ) _θ∈ μ(θ)E ( _r(·),π;θ ). (8) @picture @picture Lemma 2. For a given Red team strategy πr(⋅) _r(·), the expected payoff for Blue team strategy πb _b and any type distribution μ(⋅)∈(μ¯,δ)μ(·) ( μ,δ) permissible under the threat model can be bounded from below as follows, θ∼μ[V(πr(⋅),πb;θ]≥(−)(πb,μ)=∑θ∈Θμ(θ)supπ∗∈ΠbV(πr,π∗;θ)−supq∈(μ¯,δ)(∑θ∈Θq(θ)ℰ(πr(⋅),πb;θ)). _θ μ[V( _r(·), _b;θ] _S^(-)( _b,μ)= _θ∈ μ(θ) _π^*∈ _bV( _r,π^*;θ)- _q ( μ,δ) (Σ _θ∈ q(θ)E( _r(·), _b;θ) ). (9) @picture It is straightforward to prove the following Lemma that the PR−MREPR-MRE robust best-response from (8) is equivalent to (10) through a water-filling argument by arguing that the inner supremum for any outer π∈Πbπ∈ _b corresponds to a type distribution that places all permissible mass on the highest regret type within the high-confidence Θ/Θr / _r subset while respecting the remaining constraints posed by the low-probability covers. Lemma 3 shows that the PR−MREPR-MRE robust best-response weighs regret over rare types by a maximum of δ in contrast to the distribution-free MREMRE (6) that treats all types as equally likely and minimizes worst-case regret across the type-space. Lemma 3. For a given Red team strategy πr(⋅) _r(·), the probabilistically-robust MRE best-response operator for the Blue team is defined as follows, BRPRMRE(b)(πr(⋅);μ¯,δ)=arginfπ∈Πbsupμ(Θ/Θr)+∑θ∈Θrμ(θ)=1,∑θ∈ℒμ(θ)≤δ∀ℒ∈Θℓ(μ¯,δ)μ(Θ/Θr)⋅ℰ(πr(⋅),π;Θ/Θr)+∑θ∈Θrμ(θ)⋅ℰ(πr(⋅),π;θ), ^(b)_PRMRE( _r(·); μ,δ)= *arginf_π∈ _b _ subarraycμ( / _r)+ _θ∈ _rμ(θ)=1,\\ Σ _θ∈ Lμ(θ)≤δ\ ∀\ L∈ _ ( μ,δ) subarray\ μ( / _r)·E ( _r(·),π; / _r )+ _θ∈ _rμ(θ)·E ( _r(·),π;θ ), (10) where ℰ(πr(⋅),π;Θ/Θr)E( _r(·),π; / _r) refers to the worst-case exploitability of the Blue team strategy π over the type-space subset Θ/Θr / _r where Θr _r is the set of all rare types such that under the nominal distribution μ¯(⋅) μ(·), μ¯(θ)≤δ,∀θ∈Θr μ(θ)≤δ,\ ∀\ θ∈ _r. @picture Probabilistically-Robust Minimax-Regret Equilibrium (PR-MRE) The objective in (8) minimizes worst-case exploitability on a high-confidence subset of the type space while discounting exploitability on atypical types by the confidence parameter δ. From the novel Blue team best-response operator (8) as proposed above, we obtain the equilibrium concept – Probabilistically-Robust Minimax-Regret equilibria (PR-MRE) characterized by the following fixed-point system, πb,PRMRE∗(μ¯,δ)∈BRPRMRE(b)(πr∗(⋅);μ¯,δ)andπr∗(⋅)∈BR(r)(πb,PRMRE∗(μ¯,δ);⋅). π^*_b,PRMRE( μ,δ) ^(b)_PRMRE(π^*_r(·); μ,δ)\ and\ π^*_r(·) ^(r)(π^*_b,PRMRE( μ,δ);·). (11) @picture The key robustness guarantee of PR-MRE is given below. @picture Lemma 4. (Probabilistically-Robust Minimax-Regret Equilibria Robustness Property) For all distributions permissible under the threat model (μ¯,δ)S( μ,δ), PR−MREPR-MRE provides the tightest lower-bound on expected performance such that (−)(πb,PRMRE,μ)≥(−)(π,μ)V_S^(-)( _b,PRMRE,μ) _S^(-)(π,μ) for all μ∈(μ¯,δ)μ ( μ,δ), π∈Πbπ∈ _b. Proof. Proof in Appendix A.1. ∎ @picture A corollary of Lemma 4 is that PR−MREPR-MRE, which minimizes a weighted sum of exploitabilities over high-confidence subsets of the type-space, obtains a tighter performance lower bound on permissible distributions under the threat model as compared to MREMRE, which minimizes worst-case exploitability over the entire type-space, (−)(πb,PRMRE,μ)≥(−)(πb,MRE,μ)∀μ∈(μ¯,δ)V_S^(-)( _b,PRMRE,μ) _S^(-)( _b,MRE,μ)\ ∀\ μ ( μ,δ). This motivates PR-MREPR -MRE as an appropriate robust equilibrium concept under asymmetric information, providing a tighter lower bound on expected performance under admissible distribution shifts than distributionally robust, worst-case, and minimax-regret equilibrium concepts. In the Graph CtF setting, this corresponds to favoring strategies that remain robust across plausible flag hypotheses while avoiding excessive conservatism induced by highly atypical flag locations. The tighter lower bound does not come for free, as we establish in Section 3.1 that the computation of PR−MREPR-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 MREMRE and the well-known linear programming formulation for BNEBNE. This is due to the fact that PR−MREPR-MRE reasons about which regions of the type-space to minimize regret over as compared to MREMRE that minimizes worst-case regret over the entire type-space. Programming Formulation Unlike BNE, whose best response is a single optimization over expected utility, regret based reasoning introduces a nested optimization over type specific optima. Consequently, the optimization couples regrets across types, leading to a robust bilinear program rather than the linear programs familiar from Bayesian equilibria. We next derive this formulation and subsequently develop a tractable semidefinite relaxation for use within PSRO. @picture From (8) and Definition 3.2, the PR-MRE best-response operator can be reformulated as follows, infπ∈Πbsupμ∈Δ(|Θ|)∑θ∈ℒμ(θ)≤δ∀ℒ∈Θl(μ¯,δ)μ⊤ε(π) _π∈ _b _ subarraycμ∈ ( )\\ Σ _θ∈ Lμ(θ)≤δ\ ∀\ L∈ _l( μ,δ) subarrayμ (π) ⟺ infε~,π _ ,π ε~ supμ∈Δ(|Θ|)∑θ∈ℒμ(θ)≤δ∀ℒ∈Θl(μ¯,δ)μ⊤ _ subarraycμ∈ ( )\\ Σ _θ∈ Lμ(θ)≤δ\ ∀\ L∈ _l( μ,δ) subarray -10.00002ptμ ε(π)=ε~(π)≤ε~ (π)= (π)≤ (12) where μ⊤ε(π)=∑θ∈Θμ(θ)ℰ(πr(⋅),π;θ)μ (π)= _θ∈ μ(θ)E ( _r(·),π;θ ) is the expected regret under μ(⋅)μ(·) and Blue team policy π. @picture The robust average regret condition couples regrets across types. Moreover, optimizing over regrets is a nested optimization problem as opposed to BNE, distributionally-robust and worst-case notions of best-response since to optimize the regret, deviation from type-wise optimal solutions is minimized. For δ=0δ=0, Θl(μ¯,0)=Φ _l( μ,0)= such that robust average regret under the threat model reduces to worst-case regret corresponding to MRE best-response. The nested infimum and supremum can be reformulated as shown above. Eq. (12) is a robust formulation for expected regret under type distributions permissible under the threat model. @picture PR-MRE Best-Response Programming Formulation For Red team strategy πr(⋅) _r(·), infε~,π _ ,π ε~ (PRMRE-BR) δλ⊤|ℒ|×1 δλ 1_ L × 1 +λu≤ε~, + _u≤ , (13) −ε⊤(π)+λ⊤ℒ - (π)+λ A_ L −λp⊤+λu=0, -λ _p+ _u1=0, (14) λ∈ℝ+|ℒ|,λp∈ λ L _+, _p∈ ℝ+|Θ|;λu∈ℝ, _+;\ _u , (15) where ε(π)=[supπ∗∈ΠbV(πr(⋅),π∗;θ)−V(πr(⋅),π;θ)]θ∈Θ, (π)= [ _π^*∈ _bV( _r(·),π^*;θ)-V( _r(·),π;θ) ]_θ∈ , (16) is the regret vector corresponding to Blue team policy π. @picture From the Red team best-response operator defined in Definition 2.1 and the PR-MRE equilibrium (11) defined as the fixed-point of the Blue team and Red team best-response operators under asymmetric information, we obtain the following programming formulation for the PR-MRE equilibrium. @picture PR-MRE Equilibrium Programming Formulation infε~,πPRMRE,πr∗(⋅) _ , _PRMRE,π^*_r(·) ε~ (PRMRE-EQM) δλ⊤|ℒ|×1+ δλ 1_ L × 1+ λu≤ε~, _u≤ , (17) ε(πPRMRE) ( _PRMRE) =[supπ∗∈ΠbV(πr(⋅),π∗;θ)−V(πr(⋅),πPRMRE;θ)]θ∈Θ, = [ _π^*∈ _bV( _r(·),π^*;θ)-V( _r(·), _PRMRE;θ) ]_θ∈ , (18) −ε⊤ - (πPRMRE)+λ⊤ℒ−λp⊤+λu=0, ( _PRMRE)+λ A_ L-λ _p+ _u1=0, (19) V(πr∗(⋅),πPRMRE;θ) V(π^*_r(·), _PRMRE;θ) ≥V(πr(⋅),πPRMRE;θ) for all πr(⋅)∈Πr and θ∈Θ. ≥ V( _r(·), _PRMRE;θ) for all _r(·)∈ _r and θ∈ . (20) @picture Illustrative Example Consider an example normal-form game to illustrate the distinction between PR−MREPR-MRE and the various equilibrium concepts discussed in Section 2. Consider the 1×5×31× 5× 3 game from Table 3 with type-space Θ=θ0,θ1,θ2 =\ _0, _1, _2\, five Blue actions b0b_0 to b4b_4 on the columns, a single Red action r0r_0 as the row with three rows one for each type and a nominal prior on types μ¯=(0.25,0.70,0.05) μ=(0.25,0.70,0.05). We use a single Red action in this illustrative example so that the informed Red best-response is unique, allowing differences between equilibrium fixed-points to be attributed solely to the Blue team’s varied robust best-responses. A more complicated 2×5×3 example with the added complexity of Red’s best-response for determining the respective equilibrium fixed-points is provided in Appendix A.3 (see Table 4). From the example game shown below in Table 3, action b0b_0 is a θ0 _0-specialist such that V∗(θ0)=V(b0;θ0)V^*( _0)=V(b_0; _0), b1b_1 is a θ1 _1-specialist and b2b_2 is a θ2 _2-specialist that is rare under the nominal (μ¯(θ2)=0.05 μ( _2)=0.05). Moreover, actions b0b_0 and b1b_1 are catastrophic on the rare type θ2 _2 and action b2b_2 is catastrophic on typical types θ0 _0 and θ1 _1. Actions b3b_3 and b4b_4 are generalists such that they are not too bad for any particular type. In other words, b3b_3 and b4b_4 have markedly better worst-case regret over types as compared to the first-three specialist columns, 1.1 and 1.6 against 2.1, 2.3 and 2.0 for b0b_0, b1b_1 and b2b_2 respectively. Moreover, b3b_3 is the best generalist with lowest worst-case regret of 1.11.1 across types (see column b3b_3 in Table 3). From the taxonomy on robust Blue best-responses under asymmetric information and associated equilibria in Tables 1 and 2, each best-response corresponds to a degree of trust in Nature’s nominal type distribution and an optimization objective resulting in a unique robustness property. We now contrast PR−MREPR-MRE and the various equilibrium concepts with respect to robustness to shifts from the nominal on the example game and visualize their comparative advantage over different regions of the type-simplex (see Figure 4 and Table 3). The nominal type distribution (0.25,0.70,0.05)(0.25,0.70,0.05) represents a single point in the triangular barycentric representation of the three-dimensional simplex (Figure 4) and we evaluate the performance (Blue payoff) of the Blue decision corresponding to different robust equilibrium fixed-points as the test type distribution probes over the entire simplex. Evaluation Protocol: For our comparison and analysis (Figures 4 and 5), the performance of the Blue decision corresponding to different equilibria for any test type distribution is measured against an adaptive Red decision, specifically the Red BNEBNE corresponding to the test type distribution (Red’s decision corresponding to the BNE fixed-point for the test type distribution). Figure 4 shows the winner map and payoff difference heatmaps for PR−MREPR-MRE and the different methods against such a Red opponent that adapts as the test type distribution probes over the simplex. For the single Red action example in Table 3, the Red decision is unique everywhere by construction and the robust Blue decisions are evaluated against variations in just the Nature’s decision / type distribution (Red decision is same everywhere). For the 2×5×32× 5× 3 example in Appendix A.3, evaluation and visualization is done against an adaptive Red opponent. Table 3: Example 1×5×31×5×3 game. Columns b0⋯b4\b_0·s b_4\ are Blue actions, row r0r_0 corresponds to the Red action and there are three total rows, one per type θ∈θ0,θ1,θ2θ∈\ _0, _1, _2\ with a nominal distribution μ¯=(0.25,0.70,0.05) μ=(0.25,0.70,0.05). Each cell shows the Blue payoff V(r,b;θ)V(r,b;θ), shorthand V(b;θ)V(b;θ) for the unique Red choice r0r_0, the type-conditioned optimum values V∗(θ)V^*(θ) read left to right per θ row are marked in bold (black), and the per-type regret for any Blue action (or column) given by ε(b;θ)=V∗(θ)−V(b;θ) (b;θ)=V^*(θ)-V(b;θ) is in red subscript. Worst-case regret over types supθ∈Θε(b;θ) _θ∈ (b;θ) for any Blue action b is read top to bottom per column and marked in bold (red). b0b1b2b3b4r01.5 0.00.6 0.9−0.52.00.41.10.7 0.8θ0,0.25r00.3 0.71.0 0.0−0.8 1.80.8 0.20.8 0.2θ1,0.70r0−0.62.1−0.82.31.5 0.00.5 1.0−0.11.6θ2,0.05 array[]r |c|c|c|c|c| l @intercol @intercol& @intercol b_0 @intercol& @intercol b_1 @intercol& @intercol b_2 @intercol& @intercol b_3 @intercol& @intercol b_4 @intercol& @intercol @intercol\\[4.0pt] 2-6 r_0&1.5_\ [rgb]1,0,0 [named]pgfstrokecolorrgb1,0,00.0&0.6_\ [rgb]1,0,0 [named]pgfstrokecolorrgb1,0,00.9&-0.5_\ [rgb]1,0,0 [named]pgfstrokecolorrgb1,0,02.0&0.4_\ [rgb]1,0,0 [named]pgfstrokecolorrgb1,0,01.1&0.7_\ [rgb]1,0,0 [named]pgfstrokecolorrgb1,0,00.8& \\; _0,0.25\\ 2-6 7.0pt 2-6 r_0&0.3_\ [rgb]1,0,0 [named]pgfstrokecolorrgb1,0,00.7&1.0_\ [rgb]1,0,0 [named]pgfstrokecolorrgb1,0,00.0&-0.8_\ [rgb]1,0,0 [named]pgfstrokecolorrgb1,0,01.8&0.8_\ [rgb]1,0,0 [named]pgfstrokecolorrgb1,0,00.2&0.8_\ [rgb]1,0,0 [named]pgfstrokecolorrgb1,0,00.2& \\; _1,0.70\\ 2-6 7.0pt 2-6 r_0&-0.6_\ [rgb]1,0,0 [named]pgfstrokecolorrgb1,0,02.1&-0.8_\ [rgb]1,0,0 [named]pgfstrokecolorrgb1,0,02.3&1.5_\ [rgb]1,0,0 [named]pgfstrokecolorrgb1,0,00.0&0.5_\ [rgb]1,0,0 [named]pgfstrokecolorrgb1,0,01.0&-0.1_\ [rgb]1,0,0 [named]pgfstrokecolorrgb1,0,01.6& \\; _2,0.05\\ 2-6 array Figure 4: Comparison of PRMREPRMRE (δ=0.15δ=0.15) with BNEBNE, DRO−BallDRO-Ball, MaxMinMaxMin, DRO−MaxMinDRO-MaxMin and MREMRE for the synthetic three-type game in Table 3: winner map (first triangle) and payoff difference heatmaps (remaining triangles). Triangles represent three-dimensional simplex in barycentric coordinates with vertices corresponding to full probability mass on the respective types. Black dotted line and the trapezoidal band beneath it represent the high-confidence under nominal structured type-ambiguity set μ(θ2)≤0.15μ( _2)≤ 0.15, the star in the winner map corresponds to the nominal distribution μ¯=(0.25,0.70,0.05) μ=(0.25,0.70,0.05) and the dotted hexagon centered at the star corresponds to an L1L1-ball with radius ρ=0.5ρ=0.5 around it. For the trapezoidal band, PR−MREPR-MRE dominates all other methods which can be seen from the green volume share in the winner-map and the red volume share in the payoff difference heatmaps. BNEBNE and DRO−BallDRO-Ball perform better close to the nominal (θ1 _1-corner, mass 0.70 under nominal) but lose out on performance to PR−MREPR-MRE for a type distribution chosen at random within the trapezoidal band. PR−MREPR-MRE has the best average-case performance over the structured ambiguity set as compared to any other method (see Figure 5 for the numerical result, consistent with visual inspection of the winner-map and payoff difference heatmaps). Remark: We note that we compare PR−MREPR-MRE to two types of distributionally-robust equilibria, DRO−BallDRO-Ball based on an L1L1-ball around the nominal (local trust) and DRO−MaxMinDRO-MaxMin based on the structured type ambiguity induced by the threat model in Definition 3.2 (coarse trust) that preserves the set of all high-probability covers under admissible distribution shifts. This provides a direct comparison of our regret-based approach PR−MREPR-MRE to the payoff-based distributionally-robust approach DRO−MaxMinDRO-MaxMin over the same structured ambiguity set. BNEBNE, DRO−BallDRO-Ball, MaxMinMaxMin and DRO−MaxMinDRO-MaxMin are all computed via linear-programs whereas MREMRE and PR−MREPR-MRE (δ=0.15δ=0.15) are computed via semidefinite relaxations to the corresponding bilinear and robust bilinear programs as derived in Section 3.1 for normal form games under asymmetric information. For the example game in Table 3, the computed BNEBNE Blue decision concentrates on the specialist b1b_1 for the highest-confidence type θ1 _1 under nominal μ¯=(0.25,0.70,0.05) μ=(0.25,0.70,0.05) as (0,1,0,0,0)(0,1,0,0,0) whereas the computed DRO−BallDRO-Ball decision for an L1L1-ball of radius ρ=0.5ρ=0.5 around the nominal (dotted hexagon around the nominal star in Figure 4) hedges probability mass across generalist actions b3,b4b_3,b_4 as (0,0,0,0.89,0.11)(0,0,0,0.89,0.11). MREMRE that discards probabilistic information from the nominal and minimizes worst-case regret across all types results in a decision (0.39,0,0.39,0.22,0)(0.39,0,0.39,0.22,0) with 0.220.22 mass to the best generalist b3b_3 and a significant probability mass of 0.390.39 to the rare-type specialist b2b_2. This comes at the expense of performance over typical types θ0 _0 and θ1 _1 as the poorest worst-case and average payoffs over the high-confidence under nominal structured type ambiguity set μ(θ2)≤0.15μ( _2)≤ 0.15 (the black dotted line and the trapezoidal band beneath it in Figure 4). The MaxMinMaxMin decision that assumes an adversarial type distribution (Section 2.1.3) and optimizes for worst-case payoff across the type-simplex is the only other decision besides MREMRE that puts mass on the rare-type specialist b2b_2 as (0.18,0,0.16,0.66,0)(0.18,0,0.16,0.66,0). In contrast to distribution-free MREMRE, PR−MREPR-MRE utilizes coarse information from the nominal and optimizes for worst-case regret across a structured type ambiguity set that respects typicality of types. For δ=0.15δ=0.15, the PR−MREPR-MRE best-response discounts regret incurred on the rare-type θ2 _2 (nominal mass 0.050.05) by 0.150.15 at maximum (follows from Lemma 3) such that the PR−MREPR-MRE decision for our example game is (0.46,0,0,0,0.54)(0.46,0,0,0,0.54). Figure 5: Comparison of PRMREPRMRE (δ=0.15δ=0.15) with BNEBNE, DRO−BallDRO-Ball, MaxMinMaxMin, DRO−MaxMinDRO-MaxMin and MREMRE for the synthetic three-type game in Table 3 with respect to average and worst-case, payoff and regret over the structured ambiguity set μ(θ2)≤0.15μ( _2)≤ 0.15 and the entire type-simplex. Over μ(θ2)≤0.15μ( _2)≤ 0.15 (trapezoidal band in Figure 4), PR−MREPR-MRE has the best worst-case regret as compared to any other method. DRO−MaxMinDRO-MaxMin on the other hand beats PR−MREPR-MRE on worst-case payoff over the μ(θ2)≤0.15μ( _2)≤ 0.15 band which is consistent with its payoff-based objective (0.627 vs 0.435) but loses average-case performance for a type distribution chosen at random from the trapezoidal band such that PR−MREPR-MRE attains the highest average payoff (0.735) as compared to any other method (0.696 for DRO−MaxMinDRO-MaxMin). The regret-based objective of the PR−MREPR-MRE best-response provides the best point-wise lower bound on payoff for type distributions belonging to the structured ambiguity set (as stated in Lemma 4) which in this example game manifests as a superior average-case performance for a type-distribution chosen at random from the μ(θ2)≤0.15μ( _2)≤ 0.15 band. The PR−MREPR-MRE decision favours b4b_4 over b3b_3 despite having a higher worst-case regret over the entire type-space (1.6 vs 1.1 for MREMRE) due to higher payoff and lower worst-case regret as compared to b3b_3 when restricted to typical types θ0 _0 and θ1 _1. Blue action b3b_3 is the best overall generalist and b4b_4 is a more specialized generalist that performs better over regions which matter probabilistically. The payoff-based DRO−MaxMinDRO-MaxMin decision (0.08,0,0,0,0.92)(0.08,0,0,0,0.92) concentrates over an adversarial type distribution within the structured type ambiguity set as compared to the regret-based PR−MREPR-MRE that hedges across the μ(θ2)≤0.15μ( _2)≤ 0.15 trapezoidal band by having roughly equal mass 0.460.46 to the θ0 _0-corner that constitutes the left side of the band in Figure 4. From Figure 5, PR−MREPR-MRE has the best average-case performance over the structured ambiguity set as compared to any other method which is consistent with a visual inspection of the green share in the winner-map and the red share in the payoff difference heatmaps in Figure 4. Overall, the example game illustrates that the taxonomy in Table 1, defined by the optimization objective and degree of trust in Nature’s nominal type distribution, induces qualitatively different robust Blue best-responses and corresponding equilibria, resulting in distinct robustness properties and complementary regions of advantage across the type simplex. We refer the reader to Appendix A.3 for results on a more complicated 2×5×32× 5× 3 example game that extends the illustrative 1×5×31× 5× 3 game by restoring the informed Red player’s strategic choices when determining the corresponding robust equilibrium fixed points. 3.1 Computation of Probabilistically-Robust Minimax-Regret Equilibria via Robust Double Oracle Computing equilibria in graph-structured adversarial team games is already intractable due to the size of the extensive-form representation, necessitating approximation methods such as CFR, PPO, and double-oracle approaches. In contrast, PR-MRE introduces a regret-based robustness objective over structured type uncertainty, which does not admit standard sequence-form linear programming formulations or straightforward extensions of CFR-style regret updates. To address this challenge, we derive a tractable optimization formulation of PR-MRE together with a semidefinite relaxation that can be embedded within a population-based learning framework. For Finite Normal-Form Games @picture PR-MRE Best-Response Programming Formulation for Normal-Form Games For a finite normal-form game defined by the payoff tensor A(⋅,⋅;θ)θ∈Θ∈ℝ||×||×|Θ|\A(·,·;θ)\_θ∈ × × and the omniscient Red strategy x(⋅):Θ→Δ(||)x(·): → ( ), the Blue PR-MRE best-response yPRMRE∈Δ(||)y_PRMRE∈ ( ) denoted by yPRMRE⟵PRMRE−BRA,x(⋅)y_PRMRE -BR\A,x(·)\ can be formulated as the following program, infε~,yPRMRE _ ,y_PRMRE ε~ (PRMRE-BR-NF) δλ⊤|ℒ|×1 δλ 1_ L × 1 +λu≤ε~, + _u≤ , (21) x(θ)A(θ)ej−x(θ)A(θ)yPRMRE≤λ⊤ℒ x(θ)A(θ)e_j-x(θ)A(θ)y_PRMRE≤\λ A_ L −λp⊤+λuθ for all j∈[||] and θ∈Θ, -λ _p+ _u1\_θ for all j∈ [ ] and θ∈ , (22) λ∈ℝ+|ℒ|,λp∈ℝ+|Θ|, λ L _+, _p _+,\ λu∈ℝ,yPRMRE∈Δ(||). _u ,y_PRMRE∈ ( ). (23) @picture @picture PR-MRE Equilibrium Bilinear Program for Normal-Form Games For a finite normal-form game defined by the payoff tensor A(⋅,⋅;θ)θ∈Θ∈ℝ||×||×|Θ|\A(·,·;θ)\_θ∈ × × , the PR-MRE fixed-point σPRMRE=(x(⋅),y) _PRMRE=(x(·),y) denoted by σPRMRE⟵PRMRE−EQMA _PRMRE -EQM\A\ is given by the following bilinear program, infε~,y,x(⋅) _ ,y,x(·) ε~ (PRMRE-EQM-NF) δλ⊤|ℒ|×1 δλ 1_ L × 1 +λu≤ε~, + _u≤ , (24) x(θ)A(θ)ej−x(θ)A(θ)y≤λ⊤ℒ x(θ)A(θ)e_j-x(θ)A(θ)y≤\λ A_ L −λp⊤+λuθ for all j∈[||] and θ∈Θ, -λ _p+ _u1\_θ for all j∈ [ ] and θ∈ , (25) −x(θ)A(θ)y≥−ekA(θ) -x(θ)A(θ)y≥-e_kA(θ) y for all k∈[||] and θ∈Θ, y for all k∈[ ] and θ∈ , (26) λ∈ℝ+|ℒ|,λp∈ℝ+|Θ|;λu∈ℝ,y λ L _+, _p _+;\ _u ,y ∈Δ(||),x(θ)∈Δ(||) for all θ∈Θ. ∈ ( ),x(θ)∈ ( ) for all θ∈ . (27) @picture Rank-constrained Semidefinite Reformulation of PRMRE-EQM-NF: The details on the rank-constrained semidefinite formulation and convex relaxation are relegated to Section A.2. Robust Double Oracle for Asymmetric Information Games Double-oracle (DO) mcmahan2003planning is an algorithm for computing Nash Equilibrium (NE) in two-player zero-sum normal-form games. The algorithm proceeds by maintaining a population of strategies for each player, referred to as a metagame that abstracts away the full game, computes a NE over the metagame and iteratively adds strategies to the player populations by best-responding to the opponent meta-equilibria. The DO approach in principle recovers the NE for the full game. Policy Space Response Oracles (PSRO) psro_silver extends DO to large games by employing reinforcement-learning to compute best-responses. The metagame NE is computed on the empirical game matrix derived from the matchup between each policy in the population set against all opponent policies and tracking the average payoff in a metagame payoff matrix. As discussed in Section 2.1, NE (BNE) is risk-neutral and offers no robustness and performance guarantees under strategic distribution shifts for asymmetric information games such as Graph Capture-the-Flag where Nature’s type is hidden from the Blue team and Red can condition it’s play on the realized type and / or potentially control the type distribution. For the DO- and PSRO- policy expansion steps, best-responding to a NE (BNE) meta-equilibria over the opponent policy set might add brittle team policies to the population that suffer under distribution shift. Existing work on incorporating robustness at the metagame level and risk-aware policy expansion is limited slumbers_rae_psro and does not formally reason about exploitability of the population under hidden information and strategic shifts. Algorithm 1 PR-MRE Robust Double Oracle 1:Result: Probabilistically-Robust Minimax-Regret Equilibrium 2:Input: Θ , μ¯ μ, δ, Initial population Π0=(0,0) ^0=(X^0,Y^0), Normal-form game payoff tensor A×∈ℝ||×||×|Θ|A_X×Y × × 3:repeat 4: xk(⋅),yk←PRMRE-EQM-NFAΠkx^k(·),y^k← eq:prmre_eqm_normal_form\A_ ^k\ 5: for i∈R,Bi∈\R,B\ do 6: if i is Bi is B then 7: yk+1←PRMRE-BR-NFAk×,xk(⋅)y^k+1← eq:prmre_br_normal_form\A_X^k×Y,x^k(·)\ 8: πi←supp(yk+1)∖k _i (y^k+1) ^k 9: else 10: xk+1(θ)←BRA×k,yk for all θ∈Θx^k+1(θ) \A_X×Y^k,y^k\ for all θ∈ 11: πi←⋃θ∈Θsupp(xk+1(θ))∖k _i← \ _θ∈ supp(x^k+1(θ)) \ ^k 12: end if 13: Πik+1←Πik∪πi _i^k+1← _i^k∪\ _i\ 14: end for 15:until no novel best response exists for either player 16:return xk(⋅),ykx^k(·),y^k MREMRE and PR−MREPR-MRE are regret-based notions of equilibria that provide robustness certificates in the form of uniform performance lower bounds (see Lemmas 1 and 2). We extend the double-oracle method to compute MRE and PR-MRE for large asymmetric information normal-form games via robust double-oracle (RDO). RDORDO (see Algorithm 1) is based on PRMRE-EQM-NF as the meta-equilibria and PRMRE-BR-NF as the best-response for policy set expansion of the uninformed player. PRMRE-BR-NF provides a principled best-response that adds strategies with minimum worst-case exploitability against the omniscient opponent type-conditioned meta-equilibria. The proposed RDO expansion results in a robust population that approximates the PR−MREPR-MRE of the underlying normal-form game and is stable under distribution shifts of the hidden type. Termination of RDO is guaranteed by the fact that the meta-equilibrium PRMRE-EQM-NF is the fixed-point of the robust expansion operator based on PRMRE-BR-NF such that for the case of no new pure strategies added at an expansion iteration, the procedure terminates and the metagame approximates the PR−MREPR-MRE support of the full normal-form game with enumeration of the entire strategy space (finite) in the worst-case. 4 PRMRE-PSRO: Learning Approximate Minimax-Regret Equilibria for Adversarial Team Games under Asymmetric Information In Section 3, we proposed a novel equilibrium concept that combines the distribution-free robustness of minimax-regret reasoning with coarse probabilistic information about types from a nominal prior. The PR−MREPR-MRE best-response operator for the uninformed Blue (see Definitions 2.5 and 2.4) computes a team best-response to the omniscient Red by minimizing worst-case regret of the Blue team strategy across subsets of the type-space weighted by coarse probabilistic information about their occurrence from the prior thus providing a robustness guarantee to strategic distribution shifts in terms of the best performance lower bound. For a finite normal-form game with asymmetric information, the PR−MREPR-MRE best-response couples regrets across types resulting in a robust bilinear program for the PR−MREPR-MRE equilibrium as compared to a bilinear program for the distribution-free MREMRE equilibrium and the linear-programming formulation for Bayesian Nash equilibria (see Section 2.1 for the various equilibrium concepts and their robustness properties). PR−MREPR-MRE (and MREMRE) does not admit a known decomposition to local CFR-style regret updates for an extensive form representation of a game with hidden types. Standard variants in the CFR literature recover approximately the Bayesian Nash equilibrium of the asymmetric information game and handle hidden information as known upto a prior (or chance). To compute robust team behavior in large adversarial team games with hidden information and potential strategic distribution shifts, we propose PRMRE−PSROPRMRE-PSRO based on the robust double oracle procedure RDORDO for learning approximate PR−MREPR-MRE for ATGs via reinforcement learning based best-responses. Algorithm 2 details the pseudocode for PR−MREPR-MRE Team PSROPSRO. For the Red team (omniscient) and Blue team (uninformed) policy sets ΠRk _R^k and ΠBk _B^k at the kkth iteration of the PRMRE−PSROPRMRE-PSRO procedure, metagame payoff tensor AΠRk×ΠBk∈ℝ|ΠRk|×|ΠBk|×|Θ|A_ ^k_R× ^k_B ^k_R × ^k_B × is maintained with an explicit third dimension corresponding to the type-space. Maintaining a three-dimensional payoff tensor for the robust double oracle approach enables reasoning about the relative performance of policy sets across types as opposed to a two-dimensional empirical game matrix common in the PSRO literature psro_silver; slumbers_rae_psro; mcaleer2023teampsro. For instance for Graph Capture-the-Flag, the three-dimensional payoff tensor measures performance of the Red defense and Blue attack-and-capture team policies across all possible flag hypotheses. The 3D payoff representation enables reasoning about regret across types for meta-equilibrium computation and policy set expansion. We now detail the robust population-based approach PRMRE−PSROPRMRE-PSRO for learning approximate minimax-regret equilibria for adversarial team games under asymmetric information as follows, PRMRE PSRO (Algorithm 2): For PRMRE−PSROPRMRE-PSRO, policy set expansion proceeds by best-responding to the opponent team meta-equilibrium as computed via the robust bilinear program PRMRE-BR-NF (described in Section 3.1) on the empirical metagame payoff tensor and a uniform type distribution. Team best-responses are computed via cooperative multi-agent reinforcement learning such as multi-agent proximal policy optimization (MAPPO) mappo. The omniscient Red team uses a value-based team best-response BRValBR_Val criterion that maximizes expected Red team payoff against an opponent distribution given by the Blue PR−MREPR-MRE meta-equilibrium yk∈Δ(|ΠBk|)y^k∈ ( ^k_B ) at the latest PSROPSRO iteration. The uninformed Blue team best-responds to a uniform type distribution and the type-conditioned Red PR−MREPR-MRE meta-equilibrium xk(⋅)∈Δ(|ΠRk|)x^k(·)∈ ( ^k_R ) with a minimax-regret stopping criteria BRMMRBR_MMR until the robust average regret of the training policy πB _B (equivalent to worst-case regret over types for δ=0δ=0) falls below that of the Blue team meta-equilibrium yky^k at the latest PSROPSRO iteration. Type-wise regrets are tracked during Blue policy training as follows: ε(xk(⋅),πB;θ)≈supy∗∈Δ(|ΠBk|)xk(θ)Ak(θ)y∗−V(xk(θ),πB;θ) (x^k(·), _B;θ)≈ _y^*∈ ( ^k_B )x^k(θ)A^k(θ)y^*-V(x^k(θ), _B;θ) where V(xk(θ),πB;θ)V(x^k(θ), _B;θ) is the per-type Blue team payoff that is also tracked during training and the type-wise supremum against Red team meta-equilibrium xk(⋅)x^k(·) is approximated by restricting Blue team to the already discovered policies in the latest iteration of the metagame as supπb∗∈ΠbV(xk(⋅),πb∗;θ)≈supy∗∈Δ(|ΠBk|)xk(θ)Aky∗ _π^*_b∈ _bV(x^k(·),π^*_b;θ)≈ _y^*∈ ( ^k_B )x^k(θ)A^ky^*. In summary, PRMRE−PSROPRMRE-PSRO (i) uses a type-aware three-dimensional metagame representation (i) to compute robust mixtures via the PR−MREPR-MRE meta-equilibrium and (i) a minimax-regret based stopping criteria for training Blue team policies robust to distribution shift. BNE PSRO: BNE−PSROBNE-PSRO for a nominal prior μ¯(⋅)∈Δ(|Θ|) μ(·)∈ ( ) is defined via the risk-neutral Bayesian Nash Equilibrium (BNE) as the meta-equilibrium for a metagame ΠRk,ΠBk,AΠRk×ΠBk×Θ \ ^k_R, ^k_B,A_ ^k_R× ^k_B× \ along with risk-neutral BRVal(.,μ¯(⋅))BR_Val(., μ(·)) best-response computation for both Red and Blue teams. We now evaluate PRMRE−PSROPRMRE-PSRO and BNE−PSROBNE-PSRO on an example graph-structured ATG and compare the results. For our experiment, all Red and Blue team policies are parameterized as Graph Neural Networks (GNNs) that directly take in as input the graph-structured game state of the ATG. We note that the proposed PRMRE−PSROPRMRE-PSRO 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. 4.1 Graph-structured Capture-the-Flag: Experiment and Results Experiment 4.1. Compare Blue team policies learned via PRMRE−PSROPRMRE-PSRO and BNE−PSROBNE-PSRO on an example graph-structured adversarial team game under asymmetric information, Graph Capture-the-Flag (Figure 2), in terms of robustness to distribution shift of the hidden flag hypotheses. Algorithm 2 PR-MRE Team PSRO Result: Approximate PRMRE for the Adversarial Team Game under Asymmetric Information Input: Θ , μ¯ μ, δ, Initial population ΠR0,ΠB0 _R^0, _B^0 repeat for k=0,1,…k=0,1,… Compute metagame payoff tensor AΠRk×ΠBk∈ℝ|ΠRk|×|ΠBk|×|Θ|A_ _R^k× _B^k ^k_R × ^k_B × with a third dimension for types (xk(⋅),yk)←(x^k(·),y^k)← PRMRE-EQM-NFAΠRk×ΠBk\A_ _R^k× _B^k\ for m iterations do Update team best response πR _R toward BRVal(y,Unif(Θ))BR_Val(y,Unif( )) via cooperative MARL Update team best response πB _B toward BRMMRBR_MMR(xk(⋅),Unif(Θ))(x^k(·),Unif( )) via cooperative MARL ΠRk+1←ΠRk∪πR _R^k+1← _R^k∪\ _R\ ΠBk+1←ΠBk∪πB _B^k+1← _B^k∪\ _B\ until max k number of iterations Return: (xk(⋅),yk)(x^k(·),y^k) @picture BRMMRBR_MMR Team Best Response with Minimax-Regret Stopping Track per-type regrets while training Blue team policy πB _B as follows, ε(xk(⋅),πB;θ)≈supy∗∈Δ(|ΠBk|)xk(θ)Aky∗−V(xk(θ),πB;θ) for all θ∈Θ. (x^k(·), _B;θ)≈ _y^*∈ ( ^k_B )x^k(θ)A^ky^*-V(x^k(θ), _B;θ) for all θ∈ . (BRMMRBR_MMR) Proceed training until the robust average regret of πB _B falls below that of the Blue team PR−MREPR-MRE meta-equilibrium at the latest PSROPSRO iteration i.e. infμ∈(μ¯,δ)μ⊤ε(πB)<infμ∈(μ¯,δ)μ⊤ε(yk) _μ ( μ,δ)μ ( _B)< _μ ( μ,δ)μ (y^k). @picture For our experiment, we analyse one expansion iteration of the PSROPSRO procedure to compare the robustness and behavioral properties of learned Blue team policies induced by the PRMREPRMRE and BNEBNE meta-equilibria starting from the same seed metagame on the example Graph Capture-the-Flag instance highlighted in Figure 2. The seed metagame for the PSROPSRO runs is obtained as follows. Seed Metagame: Blue team seed policies are learned by training against a Red team curriculum of progressively harder scripted flag defenders. The curriculum stages range from passive defenders to corridor sentry agents that patrol bottleneck nodes in the graph and chase any closing Blue attackers. Blue column 0 is a FHFH-1 (flag hypothesis 1, θ1 _1) specialist trained against the Red curriculum on flag hypothesis 1. Blue column 1 warmstarts from the column 0 checkpoint and is fine-tuned against uniformly sampled FHFH-0 and FHFH-1 flag hypotheses. Columns 2 and 3 are FHFH-0 (θ0 _0) specialists with a similar fine-tuning stage against uniformly sampled hypotheses. Rows correspond to learned Red team GNN policies trained against intermediate Blue checkpoints produced while training the columns. Meta-equilibria and Expansion: Figures 7 and 7 highlight the evolution of the metagame for PR−MREPR-MRE (δ=0δ=0) and BNEBNE meta-equilibria respectively. Figure 7 describes one iteration of PRMRE−PSROPRMRE-PSRO initialized from a 2×42× 4 seed policy set for the teams as described above and the two panels correspond to the metagame states during PSROPSRO iterations 0–11. For each panel, the heatmap on the top corresponds to θ0 _0 (Red flag on the left, μ(θ0)=0.8μ( _0)=0.8) and the bottom heatmap corresponds to θ1 _1 (Red flag on the right, μ(θ1)=0.2μ( _1)=0.2). Rows represent Red team (defender) policies and columns represent Blue team (attacker) policies whereas the cells indicate the Red team numeric score (negative of the Blue team score). Red team has knowledge of the true flag location whereas Blue team has knowledge only up to the nominal distribution before reaching the information frontier as marked in Figure 2. As shown in the graphic, the meta-equilibrium distribution over the Red team policy set conditions on the flag hypothesis such that (σ(πr0|θ0),σ(πr1|θ0))=(0.19,0.81)(σ(π^0_r| _0),σ(π^1_r| _0))=(0.19,0.81) and (σ(πr0|θ1),σ(πr1|θ1))=(0.90,0.10)(σ(π^0_r| _1),σ(π^1_r| _1))=(0.90,0.10). PR−MREPR-MRE hedges the performance of the Blue team seed policy set across both flag hypothesis (types) and computes a robust mixture (minimum worst-case exploitability) over the four seed Blue team policies as (πb0,πb1,πb2,πb3)=(0.23,0,0,0.76)(π^0_b,π^1_b,π^2_b,π^3_b)=(0.23,0,0,0.76) via the SDP relaxation provided in Section A.2. Note that even though πb0π^0_b has a drastic win-rate against Red for the majority type θ0 _0 under the nominal distribution (first panel, top heatmap, first column), PR−MREPR-MRE favors πb3π^3_b over πb1π^1_b that has the best worst-case Blue win-rate across both types and lower regret. This is in contrast to BNE−PSROBNE-PSRO (Figure 7) that concentrates all mass on πb0π^0_b, the best Blue team policy on the majority type θ0 _0 (with nominal mass μ(θ0)=0.8μ( _0)=0.8) with an egregious win-rate against the minority type θ1 _1. Blue team policy trained against the robust Red team mixture results in a policy πb,MRE1π^1_b,MRE (second panel, fourth column) with better worst-case Blue team win-rate (fourth column is Blue across both top and bottom heatmaps) as opposed to the BNE-trained Blue team best-response πb,BNE1π^1_b,BNE (see Figure 7, second panel, fourth column) that loses poorly against the seed Red policy πr1π^1_r (second row) for θ1 _1. Figure 7 describes one iteration of BNE−PSROBNE-PSRO initialized from the same 2×42× 4 metagame as PRMRE−PSROPRMRE-PSRO. Policies trained via BNE−PSROBNE-PSRO are exploitable under distribution shifts as compared to the robust best-responses added in the PRMRE−PSROPRMRE-PSRO iteration (see Figure 8 for the robustness experiment). Figure 6: PRMRE-PSRO on the Graph CtF game under asymmetric information with nominal type distribution (μ(θ0),μ(θ1))=(0.8,0.2)(μ( _0),μ( _1))=(0.8,0.2). Rows correspond to Red-team policies and columns correspond to Blue-team policies. Cell values denote Red-team payoffs (negative values indicate Blue-team success). The three panels show the evolution of the metagame and PR-MRE meta-equilibrium over PSRO iterations. PR-MRE selects mixtures that hedge performance across both flag hypotheses rather than concentrating on policies that perform well only under the majority hypothesis. Consequently, the resulting Blue-team policies exhibit lower worst-case regret and improved robustness to type-distribution shifts. Figure 7: BNE-PSRO on the Graph CtF game under asymmetric information with nominal type distribution (μ(θ0),μ(θ1))=(0.8,0.2)(μ( _0),μ( _1))=(0.8,0.2). Rows, columns and cell values follow the same convention as Figure 7. The three panels show the evolution of the metagame and BNE meta-equilibrium over PSRO iterations. Unlike PRMRE-PSRO (Figure 6), the BNE meta-equilibrium concentrates probability mass on policies that perform well under the majority flag hypothesis, resulting in strategies that are more vulnerable to type-distribution shifts. Robustness to Distribution Shift: The robust Blue team best-response trained against the PR−MREPR-MRE mixture shows better robustness to type distribution shifts than the BNEBNE-mixture trained best-response (see Figure 8 for the robustness experiment). In contrast, the BNE meta-equilibrium (Figure 7) concentrates probability mass on majority-hypothesis specialists, resulting in policies that are more vulnerable to type-distribution shifts. Figure 8: Performance-Robustness Curve for PRMRE−PRMRE- and BNE−BNE-trained Blue team policies for a nominal distribution of (μ(θ0),μ(θ1))=(0.8,0.2)(μ( _0),μ( _1))=(0.8,0.2). The x-axis on the above plot shows the probability mass for the hypothesis θ0 _0 under the test distribution, and the y-axis denotes the expected Blue team win-rate against flags sampled from the test distribution and learned Red team expert opponent policies conditioned on the sampled flag. For a sampled flag under a test-distribution, the conditioned Red opponent is the BNE under test-distribution over the concatenated Red team policy pool from the PSROPSRO runs corresponding to Figures 7 and 7. From the above plot, PRMREPRMRE-trained Blue team policies overpower the BNEBNE-trained team policies for μ(θ0)≤0.6μ( _0)≤ 0.6 demonstrating superior robustness to distribution shift across the type-simplex as the PRMREPRMRE-trained team policy win-rate flattens while the BNEBNE-trained team policy win-rate deteriorates. Refer to Figure 9 for a behavioral interpretation of the learned Blue team policies. Figure 9: Behavioral comparison of BNE-PSRO (left) and PRMRE-PSRO (right) under the minority flag hypothesis. Node coloration indicates Blue-team visitation density. The BNE-trained policy is biased toward the corridor associated with the majority flag hypothesis, whereas the PRMRE-trained policy explores both corridors more symmetrically before committing to a search direction. This scouting behavior reduces exploitability across competing flag hypotheses and improves robustness to distribution shifts. Behavioral Analysis: Note the robust mixtures selected by PR-MRE in the metagame manifest behaviorally as scouting policies that avoid over-committing to the majority flag hypothesis. Figure 9 shows Blue team visitation density under learned team policies for the Graph Capture-the-Flag scenario. The PRMREPRMRE Blue team policy has a symmetric visitation behavior across the two corridors under the minority flag hypothesis unlike the BNEBNE trained team policy which is biased towards the corridor corresponding to the majority flag hypothesis θ0 _0 suggesting that policies learned via PRMREPRMRE learned scouting tactics to resolve flag ambiguity before committing to a corridor leading to lower worst-case regret across the two hypothesis. A team policy that behaviorally learns to commit to a corridor (the majority flag hypothesis in this instance) will incur performance loss when the realized type is the minority type hypothesis. The lower regret behavior with symmetric visitation will be robust to distribution shifts because of learned scouting behavior as opposed to the team policy that has learned to commit to the majority flag hypothesis that will be brittle when the distribution shifts in mass to the formerly minority hypothesis (see Figure 8 for the performance-robustness curve of PRMREPRMRE and BNEBNE under distribution shift). Moreover, in this instance of the Red opponent πr1π^1_r and minority type θ1 _1, the PRMREPRMRE trained team policy has a win-rate of +0.41 versus a win-rate of -0.24 for the BNEBNE trained team policy suggesting favorable worst-case behavior due to lower regret across types. 5 Conclusions and Future Work 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. A nominal prior distribution in such strategic multi-agent interactions is “trustable” only to a certain degree in the face of potential deception. Distributionally-robust methods provide a framework to address ambiguity in the type distribution via ambiguity sets but lack guarantees for shifts outside the ambiguity set for instance strategic distribution shifts whereby Nature could be running an oracle procedure to compute a type distribution that places probability mass on high-regret types. Moreover, a worst-case approach that assumes an adversarial nature could be too conservative as it concentrates probability mass on the hardest type and loses performance under non-adversarial distribution shifts. Motivated by the uniform lower bound interpretation of minimax reasoning, we propose probabilistically-robust minimax-regret equilibrium as a solution concept for adversarial team games under asymmetric information for robustness to strategic distribution shifts. PR-MRE best-response discounts regret over type-space subsets with coarse probabilistic information from the nominal prior distribution. This is in contrast to minimax-regret equilibrium that discards potentially useful probabilistic information about type occurrence by minimizing worst-case regret across all types. MRE is bound to lead to conservative performance on typical types when high-regret types are known to be rare for example rare flag hypothesis locations which require a remarkably different Blue team behavior for capture as compared to the typical flag hypotheses. PR-MRE is formulated as a robust bilinear program for finite normal-form games and is adapted as a meta-solver within a robust double-oracle based approach, PRMRE-PSRO to learn strategically robust team policies via reinforcement learning based best-responses. For an example graph capture-the-flag game, team strategies learned via PRMRE PSRO exhibit learned scouting behavior and enhanced robustness to distribution shift as compared to BNE PSRO. Computation of sequential refinements of minimax-regret equilibria for treeplexes in extensive-form games (EFGs) remains an open question and a subject of future research. The nested optimization structure of MRE that characterizes deviation from type-conditioned optima and the bilinear program for MRE in normal-form games as opposed to a linear program for BNE hints at non-trivial computational complexity such that a naive approach to compute the MRE would first solve an EFG corresponding to each type. It remains an open question whether regret decomposition across infosets holds for MRE in the EFG representation as it does for the computation of BNE in the established counterfactual regret minimization literature. Acknowledgments This work was supported in part by the U.S. Army Research Laboratory through the Distributed and Collaborative Intelligent Systems and Technology (DCIST) Collaborative Research Alliance under Cooperative Agreement No. W911NF-17-2-0181. The views and conclusions contained in this document are those of the authors and should not be interpreted as representing the official policies, either expressed or implied, of the U.S. Army Research Laboratory or the U.S. Government. References Appendix A Appendix A.1 Robustness Certificates for MRE and PR-MRE Best-response Operators Proof of Lemma 1. θ∼μ[V(πr(⋅),πb;θ] _θ μ[V( _r(·), _b;θ] =∑θ∈Θμ(θ)V(πr(⋅),πb;θ)=∑θ∈Θμ(θ)[supπ∗∈ΠbV(πr(⋅),π∗;θ)−ℰ(πr(⋅),πb;θ)], = _θ∈ μ(θ)V( _r(·), _b;θ)= _θ∈ μ(θ) [ _π^*∈ _bV( _r(·),π^*;θ)-E( _r(·), _b;θ) ], (28) =∑θ∈Θμ(θ)supπ∗∈ΠbV(πr(⋅),π∗;θ)−∑θ∈Θμ(θ)ℰ(πr(⋅),πb;θ), = _θ∈ μ(θ) _π^*∈ _bV( _r(·),π^*;θ)- _θ∈ μ(θ)E( _r(·), _b;θ), (29) ≥∑θ∈Θμ(θ)supπ∗∈ΠbV(πr(⋅),π∗;θ)−supq∈Δ(|Θ|)(∑θ∈Θq(θ)ℰ(πr(⋅),πb;θ))⏟ℰ¯(πb,q), ≥ _θ∈ μ(θ) _π^*∈ _bV( _r(·),π^*;θ)- _q∈ ( ) ( _θ∈ q(θ)E( _r(·), _b;θ) )_ E( _b,q), (30) =∑θ∈Θμ(θ)supπ∗∈ΠbV(πr(⋅),π∗;θ)−supθ∈Θℰ(πr(⋅),πb;θ)⏟(−)(πb,μ). = _θ∈ μ(θ) _π^*∈ _bV( _r(·),π^*;θ)- _θ∈ E( _r(·), _b;θ)_V^(-)( _b,μ). (31) Therefore, θ∼μ[V(πr(⋅),πb;θ]≥(−)(πb,μ)=∑θ∈Θμ(θ)supπ∗∈ΠbV(πr,π∗;θ)−ℰ(πr(⋅),πb,Θ)E_θ μ[V( _r(·), _b;θ] ^(-)( _b,μ)=Σ _θ∈ μ(θ) _π^*∈ _bV( _r,π^*;θ)-E( _r(·), _b, ) for all πb∈Πb _b∈ _b and μ(⋅)∈Δ(|Θ|)μ(·)∈ ( ). Moreover, the lower bound is tight such that equality holds for q=eargsupθ∈Θℰ(πr(⋅),πb;θ)q=e_argsup _θ∈ E( _r(·), _b;θ) where eke_k is the k-th canonical vector in ℝ|Θ|R . ∎ Proof of Lemma 4. We recall that, (−)(π,μ)=∑θ∈Θμ(θ)supπ∗∈ΠbV(πr,π∗;θ)−supq∈(μ¯,δ)ℰ¯(π,q), _S^(-)(π,μ)=Σ _θ∈ μ(θ) _π^*∈ _bV( _r,π^*;θ)- _q ( μ,δ) E(π,q), (32) where ℰ¯(π,q)=∑θ∈Θq(θ)ℰ(πr(⋅),π;θ) E(π,q)=Σ _θ∈ q(θ)E( _r(·),π;θ). Now, (−)(πPRMRE,μ) _S^(-)( _PRMRE,μ) =∑θ∈Θμ(θ)supπ∗∈ΠbV(πr,π∗;θ)−supq∈(μ¯,δ)ℰ¯(πPRMRE,q), =Σ _θ∈ μ(θ) _π^*∈ _bV( _r,π^*;θ)- _q ( μ,δ) E( _PRMRE,q), (33) =∑θ∈Θμ(θ)supπ∗∈ΠbV(πr,π∗;θ)−infπ′∈Πbsupq∈(μ¯,δ)ℰ¯(π′,q), =Σ _θ∈ μ(θ) _π^*∈ _bV( _r,π^*;θ)- _π ∈ _b _q ( μ,δ) E(π ,q), (34) ≥∑θ∈Θμ(θ)supπ∗∈ΠbV(πr,π∗;θ)−supq∈(μ¯,δ)ℰ¯(π′,q), ≥Σ _θ∈ μ(θ) _π^*∈ _bV( _r,π^*;θ)- _q ( μ,δ) E(π ,q), (35) =(−)(π′,μ), =V_S^(-)(π ,μ), (36) for all π′∈Πbπ ∈ _b. The same holds for πMRE∈arginfπ∈Πbsupθ∈Θℰ(πr(⋅),π;θ) _MRE∈ *arginf _π∈ _b _θ∈ E( _r(·),π;θ) such that (−)(πPRMRE,μ)≥(−)(πMRE,μ)V_S^(-)( _PRMRE,μ) _S^(-)( _MRE,μ). Hence proved that πPRMRE _PRMRE provides the tightest lower bound on expected performance for type distributions restricted to the threat model. ∎ A.2 Rank-constrained Semidefinite Reformulation and Convex Relaxation In this section, we lift the robust bilinear program PRMRE-EQM-NF to a semidefinite program (SDP) by reformulating the constraints via an introduced matrix positive semidefinite (psd) variable. Consider a symmetric psd matrix Z(θ)∈||+||+1+Z(θ) ^+_ + +1 such that, Z(θ)=[1x(θ)⊤y⊤x(θ)X(θ)W(θ)⊤yW(θ)Y]⪰0, Z(θ)= [ array[]l1&x(θ) &y \\ x(θ)&X(θ)&W(θ) \\ y&W(θ)&Y array ] 0, (40) with the first row and column equal to the concatenated x and y vectors lying in the respective probability simplices and block matrices X and Y at the diagonals and an off-diagonal block matrix W. We follow a zero-based indexing convention to refer to the rows and columns of Z(θ)Z(θ) such that Z1,1(θ)=X(θ)Z_1,1(θ)=X(θ), Z2,1(θ)=WZ_2,1(θ)=W and so on. Consider a reformulation of constraints (25)–(26) with respect to the block matrices of the psd matrix Z(θ)Z(θ), x(θ)A(θ)ej−⟨A(θ),Z2,1(θ)⟩≤λ⊤ℒ x(θ)A(θ)e_j- A(θ),Z_2,1(θ) ≤\λ A_ L −λp⊤+λuθ for all j∈[||] and θ∈Θ, -λ _p+ _u1\_θ for all j∈ [ ] and θ∈ , (41) and −⟨A(θ),Z2,1(θ)⟩≥−ekA(θ)y for all k∈[||] and θ∈Θ- A(θ),Z_2,1(θ) ≥-e_kA(θ)y for all k∈[ ] and θ∈ where ⟨⋅,⋅⟩ ·,· is the trace operator such that ⟨A,B⟩=trace(AB) A,B =trace(AB). The off-diagonal block matrix Z2,1(θ)=W(θ)Z_2,1(θ)=W(θ) has the interpretation of capturing the cross-terms between the x(θ)x(θ) and y vectors such that W(θ)≈yx(θ)⊤W(θ)≈ yx(θ) . This enables us to lift the bilinear term x(θ)⊤A(θ)yx(θ) A(θ)y and express it in terms of a block matrix of a positive semidefinite matrix variable as, x(θ)⊤A(θ)y=⟨A(θ),yx(θ)⊤⟩≈⟨A(θ),W(θ)⟩x(θ) A(θ)y= A(θ),yx(θ) ≈ A(θ),W(θ) . This is an instance of lifting a polynomial program into an SDP by the introduction of psd matrix variables (see moment_sos1; moment_sos2 for a survey on Moment-SoS hierarchy for polynomial optimization). Any rank-1 solution Z(θi)\Z( _i)\ to the lifted program recovers the exact PR−MREPR-MRE fixed-point solution (⋅),y\x(·),y\ to PRMRE-BR-NF. This follows from the eigen decomposition of a rank-1 positive semidefinite matrix and we omit a formal proof. See Proposition 2.1 in Ref. ali_zhang_bimatrix_nash_sdp for a related result on Nash equilibria in a bimatrix game with perfect information. Remark on Asymmetric Information between Red and Blue Teams: Note that Z2,0(θ)=y for all θ∈ΘZ_2,0(θ)=y for all \ θ∈ from the definition (40) of Z(θ)Z(θ). This is the robust Blue decision y under asymmetric information whereas Red can condition its play on the hidden type as reflected by x(θ)x(θ) in Z(θ)Z(θ). Therefore, psd matrices Z(θ)Z(θ) are constrained to be consistent in their y decision for all types θ∈Θθ∈ and this is added as an additional consistency constraint in the lifted program. Convex Relaxation: Rank-constrained SDPs are an important class of non-convex problems that are generally NP-hard to solve lowrank_sdp_recht_parillo. The rank constraint appears because of the cross-terms in the bilinear program that was lifted via the use of matrix PSD variables. We relax the rank constraint into a convex semidefinite program for our application using McCormick cuts. McCormick Cuts and Valid Inequalities: We begin our exposition by stating the following proposition that characterizes the desired rank-one correlations between the lifted matrix variables and the original decision variables. Proposition 1. If rank(Z(θ))=1rank(Z(θ))=1, X(θ)=x(θ)x⊤(θ)X(θ)=x(θ)x (θ), Y=yy⊤Y=y and W(θ)=yx⊤(θ)W(θ)=yx (θ). Since we relax the rank-constraint, we add valid inequalities in the form of McCormick cuts to the block matrices X(θ)X(θ), Y and W(θ)W(θ) to encode the correlation between the cross-terms as stated in Proposition 1. This is a valid approach since all feasible rankrank-11 solutions to the rank-constrained program satisfy these inequalities and is a way of pruning out high-rank solutions that do not obey the correlational structure possessed by low-rank solutions. For example, we add the following set of inequalities for Wi,j(θ)W_i,j(θ), since it is supposed to be a proxy for yixjy_ix_j such that Wi,j≈yixjW_i,j≈ y_ix_j, Wi,j(θ) W_i,j(θ) ≤xj(θ),Wi,j(θ)≤yi, ≤ x_j(θ),W_i,j(θ)≤ y_i, (42) Wi,j(θ) W_i,j(θ) ≥xj(θ)+yi−1 ≥ x_j(θ)+y_i-1 (43) for all i∈[|m|]i∈[ m ] and j∈[|n|]j∈[ n ]. We add similar cuts for the i,ji,jth terms (i≠ji≠ j) of the block-matrices X(θ)X(θ) and Y which are supposed to be proxies for xixjx_ix_j and yiyjy_iy_j respectively. For the diagonal terms of the X(θ)X(θ) and Y blocks, we enforce constraints of the form 0≤Xii(θ)≤xi(θ)0≤ X_i(θ)≤ x_i(θ) and 0≤Yii≤yi(θ)0≤ Y_i≤ y_i(θ) which follow from x(θ)x(θ) and y belonging to probability simplices. The solution Z(θi)\Z( _i)\ obtained from the relaxed program via the valid inequalities provided by McCormick cuts is not guaranteed to be rankrank-1 and the relaxation might not be lossless. Therefore, as part of our method, we project the obtained solution for Z(θ)Z(θ)’s on the manifold of rankrank-1 matrices. From the classical Eckart–Young–Mirsky theorem, the optimal rankrank-r approximant of a m×nm× n rectangular matrix M is given by the largest r singular values of M and the corresponding eigenvectors. In our method, we obtain rankrank-1 approximations for Z(θi)\Z( _i)\ via the largest eigenvector for each θi _i. Let vmax(Z(θi))∈ℝ||+||+1v_max(Z( _i)) + +1 denote the eigenvector corresponding to the largest singular value of Z(θi)Z( _i). We re-normalize vmax(θi)v_max( _i) such that the first-entry becomes unity as vmax(θi)=[1,x(θi),y]⊤v_max( _i)= [1,x( _i),y ] and obtain x(θi)x( _i) and y. Note that the x(θ)x(θ) and y obtained in this fashion might not lie in their respective probability simplices (due to negative entries for example) and will require an additional projection step. In our implementation, we clip the negative entries at 0 and re-normalize such that the sum of all entries equals 11. A.3 Additional Illustrative Example Consider the following 2×5×32× 5× 3 normal-form game such that rows corresponding to red action r0r_0 are the same as the 1×5×31× 5× 3 game from Table 3. Red action r1r_1 is an additional punisher action that punishes Blue specialists b0b_0, b1b_1 and b2b_2 on their specialized types respectively and also the generalists b3b_3, b4b_4 across all types hence modifying the regret and payoff landscape for the game. We note that b0b_0, b1b_1 and b2b_2 retain their specialist roles for θ0 _0, θ1 _1 and θ2 _2 respectively as before as can be verified from the payoff values in the game below. Unlike the main-text example, the informed Red player now has multiple strategic choices, so that both the robust Blue best-responses and the corresponding informed Red best-responses differ across equilibrium fixed-points. Table 4: Example 2×5×32×5×3 game. Columns b0⋯b4\b_0·s b_4\ are Blue actions, rows r0,r1\r_0,r_1\ correspond to Red actions and a total of three 2×52× 5 matrices stacked one on top of another along a third type-axis for θ∈θ0,θ1,θ2θ∈\ _0, _1, _2\ with a nominal distribution μ¯=(0.25,0.70,0.05) μ=(0.25,0.70,0.05) such that each cell shows the Blue payoff V(r,b;θ)V(r,b;θ) for the (r,b,θ)(r,b,θ) matchup. b0b1b2b3b4r01.50.6−0.50.40.7θ0,0.25r10.70.1−0.50.10.1r00.31.0−0.80.80.8θ1,0.70r1−0.10.3−0.80.2−0.1r0−0.6−0.81.50.5−0.1θ2,0.05r1−0.4−0.80.50.0−0.3 array[]r |c|c|c|c|c| l @intercol @intercol& @intercol b_0 @intercol& @intercol b_1 @intercol& @intercol b_2 @intercol& @intercol b_3 @intercol& @intercol b_4 @intercol& @intercol @intercol\\[4.0pt] 2-6 r_0&1.5&0.6&-0.5&0.4&0.7& $ . 0.0pt19.80551pt \ _0,0.25$\\ 2-6 r_1&0.7&0.1&-0.5&0.1&0.1&\\ 2-6 7.0pt 2-6 r_0&0.3&1.0&-0.8&0.8&0.8& $ . 0.0pt19.80551pt \ _1,0.70$\\ 2-6 r_1&-0.1&0.3&-0.8&0.2&-0.1&\\ 2-6 7.0pt 2-6 r_0&-0.6&-0.8&1.5&0.5&-0.1& $ . 0.0pt19.80551pt \ _2,0.05$\\ 2-6 r_1&-0.4&-0.8&0.5&0.0&-0.3&\\ 2-6 array BNEBNE, DRO−BallDRO-Ball, MaxMinMaxMin and DRO−MaxMinDRO-MaxMin are all computed via linear-programs as before whereas MREMRE and PR−MREPR-MRE (δ=0.15δ=0.15) are computed via semidefinite relaxations to the corresponding bilinear and robust bilinear programs as derived in Section 3.1. The evaluation protocol for the winner-map, payoff difference heatmaps and the metrics table is the same as before such that the computed Blue decisions are evaluated against the Red BNEBNE corresponding to the test type distribution that probes over the entire type-simplex. The robust Blue decisions corresponding to the above computed fixed-points are: BNE (0,1,0,0,0)(0,1,0,0,0), DRO-Ball (0,0,0,1,0)(0,0,0,1,0), MaxMin (0.05,0,0.14,0.81,0)(0.05,0,0.14,0.81,0), DRO-MaxMin (0.11,0,0,0.89,0)(0.11,0,0,0.89,0), MRE (0.42,0,0.29,0.29,0)(0.42,0,0.29,0.29,0) and PR-MRE (0.56,0,0,0.45,0)(0.56,0,0,0.45,0). We note that no Blue decision has b4b_4 in its support including PR−MREPR-MRE in contrast to the 1×5×31× 5× 3 game from before. This is due to the additional punisher row that penalizes b4b_4 more drastically than b3b_3 over typical types θ0 _0 and θ1 _1 as seen in Table 4. The computed MREMRE Blue decision allocates meaningful probability mass on the rare-type specialist b2b_2 same as before, at the expense of catastrophic performance on the typical set μ(θ2)≤0.15μ( _2)≤ 0.15 (-0.222 worst-case and -0.022 average payoff from Figure 11), as opposed to the computed PR−MREPR-MRE Blue that discounts regret incurred on the rare-type and hedges across the trapezoidal band representing the typical subset of the type-simplex under confidence-level δ=0.15δ=0.15 (see Figure 10). From the winner-map in Figure 10, PR−MREPR-MRE dominates the trapezoidal band and has the lowest worst-case regret and the highest average-case payoff (0.200) for type distributions chosen at random from the structured type ambiguity set as opposed to DRO−MaxMinDRO-MaxMin which has a higher worst-case payoff (0.135) as compared PR−MREPR-MRE (-0.005) but loses out in the average-case. The regret-based objective of PR−MREPR-MRE provides a performance guarantee in the form of a point-wise uniform lower bound (see Lemma 4) for all type distributions belonging to the structured ambiguity set that results in a favorable average-case performance over the trapezoidal band in the example game. Figure 10: Comparison of PRMREPRMRE (δ=0.15δ=0.15) with BNEBNE, DRO−BallDRO-Ball, MaxMinMaxMin, DRO−MaxMinDRO-MaxMin and MREMRE for the synthetic three-type game in Table 4: winner map (first triangle) and payoff difference heatmaps (remaining triangles). Triangles represent three-dimensional simplex in barycentric coordinates with vertices corresponding to full probability mass on the respective types. Black dotted line and the trapezoidal band beneath it represent the high-confidence under nominal structured type-ambiguity set μ(θ2)≤0.15μ( _2)≤ 0.15, the star in the winner map corresponds to the nominal distribution μ¯=(0.25,0.70,0.05) μ=(0.25,0.70,0.05) and the dotted hexagon centered at the star corresponds to an L1L1-ball with radius ρ=0.5ρ=0.5 around it. For the trapezoidal band, PR−MREPR-MRE dominates all other methods which can be seen from the green volume share in the winner-map and the red volume share in the payoff difference heatmaps. BNEBNE and DRO−BallDRO-Ball perform better close to the nominal (θ1 _1-corner, mass 0.70 under nominal) but lose out on performance to PR−MREPR-MRE for a type distribution chosen at random within the trapezoidal band. PR−MREPR-MRE has the best average Figure 11: Comparison of PRMREPRMRE (δ=0.15δ=0.15) with BNEBNE, DRO−BallDRO-Ball, MaxMinMaxMin, DRO−MaxMinDRO-MaxMin and MREMRE for the synthetic three-type game in Table 4 with respect to average and worst-case, payoff and regret over the structured ambiguity set μ(θ2)≤0.15μ( _2)≤ 0.15 and the entire type-simplex. Over μ(θ2)≤0.15μ( _2)≤ 0.15 (trapezoidal band in Figure 10), PR−MREPR-MRE has the best worst-case regret as compared to any other method. DRO−MaxMinDRO-MaxMin on the other hand beats PR−MREPR-MRE on worst-case payoff over the μ(θ2)≤0.15μ( _2)≤ 0.15 band which is consistent with its payoff-based objective (0.135 vs -0.005) but loses average-case performance for a type distribution chosen at random from the trapezoidal band such that PR−MREPR-MRE attains the highest average payoff (0.200) as compared to any other method (0.151 for DRO−MaxMinDRO-MaxMin). The regret-based objective of the PR−MREPR-MRE best-response provides the best point-wise lower bound on payoff for type distributions belonging to the structured ambiguity set (as stated in Lemma 4) which in this example game manifests as a superior average-case performance for a type-distribution chosen at random from the μ(θ2)≤0.15μ( _2)≤ 0.15 band. A.4 GNN-MAPPO PSRO Training Details A.4.1 Graph Neural Network Architecture Table 5: Node feature vector xv∈ℝ13x_v ^13 (obs_version=3). Indices 66–1010 are populated only on the acting agent’s node. # Feature # Feature 0 is_ego 7 dist. to opponent flag (ego) 1 is_frontier 8 enemy_flag_known (ego) 2 frontier resolution mass 9 min. enemy dist. to ego (ego) 3 is_regular 10 min. teammate dist. to ego (ego) 4 opponent flag present here 11 structural (graph) degree 5 hop distance to ego node 12 visibility bit 6 dist. to own flag (ego) A.4.2 PPO Configuration Table 6: Policy and PPO/MAPPO training configuration. Best responses are warm-started from a v4-hybrid checkpoint (shared MPNN transfers; per-agent heads re-initialized). Hidden width / embedding D 64 Optimizer Adam MPNN layers L 3 Learning rate 2.5×10−42.5× 10^-4 Aggregation sum (+self-loop) PPO clip range 0.20.2 Ego-subgraph radius K 6 hops GAE λ / γ 0.950.95 / 0.990.99 Node feature dim 13 Rollout length nstepsn_steps 2048† Team size 2v2 Minibatch size 128 Attention disabled PPO epochs 2† Algorithm MAPPO (CTDE) Value coef. cvc_v 0.1† Steps per best response 4×1064× 10^6 Entropy coef. 0.0