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

• URL: http://arxiv.org/abs/2607.09993v1
• Date: Fri, 10 Jul 2026 21:36:07 GMT
• Title: Beyond Bayesian Nash: Learning Minimax-Regret Equilibria for Adversarial Team Games under Asymmetric Information
• Abstract summary: Adversarial team games (ATGs) with asymmetric information require strategies that are robust to hidden opponent types.<n>We introduce Probabilistically Robust Minimax-Regret Equilibrium (PR-MRE)<n>PR-MRE minimizes worst-case regret over a high-confidence subset of the type space.<n>We show that PR-MRE can be formulated as a robust bilinear program and derive a tractable semidefinite relaxation.
• Score: 16.899830979282815
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• Uncertainty-Aware Jamming Mitigation with Active RIS: A Robust Stackelberg Game Approach [65.06640919319413]
  This paper investigates the jamming mitigation by leveraging an active reconfigurable intelligent surface (ARIS)<n>We adopt the Stackelberg game formulation to model the strategic interaction between the legitimate side and the adversary.<n>We first derive the optimal jamming policy as the follower's best response, which is then incorporated into the legitimate-side optimization for robust anti-jamming design.
  arXiv  Detail & Related papers  (2026-02-20T12:02:01Z)
• Provably Convergent Actor-Critic in Risk-averse MARL [15.77454427706097]
  We study Risk-averse Quantal response Equilibria (RQE), a solution concept rooted in behavioral game theory that incorporates risk aversion and bounded rationality.<n>We propose a novel two-timescale Actor-Critic algorithm characterized by a fast-timescale actor and a slow-timescale critic.
  arXiv  Detail & Related papers  (2026-02-12T20:29:41Z)
• Likelihood Reward Redistribution [0.0]
  We propose a emphLikelihood Reward Redistribution (LRR) framework for reward redistribution.<n>When integrated with an off-policy algorithm such as Soft Actor-Critic, LRR yields dense and informative reward signals.
  arXiv  Detail & Related papers  (2025-03-20T20:50:49Z)
• Robust Optimization with Diffusion Models for Green Security [49.68562792424776]
  In green security, defenders must forecast adversarial behavior, such as poaching, illegal logging, and illegal fishing, to plan effective patrols.<n>We propose a conditional diffusion model for adversary behavior modeling, leveraging its strong distribution-fitting capabilities.<n>We introduce a mixed strategy of mixed strategies and employ a twisted Sequential Monte Carlo (SMC) sampler for accurate sampling.
  arXiv  Detail & Related papers  (2025-02-19T05:30:46Z)
• $k$-Submodular Interdiction Problems under Distributional Risk-Receptiveness and Robustness: Application to Machine Learning [0.8233493213841317]
  We study submodular optimization in adversarial context, applicable to machine learning problems such as feature selection.<n>We focus on Stackelberg games between an attacker (or interdictor) and a defender where the attacker aims to minimize the defender's objective of maximizing a $k$-submodular function.<n>We introduce Distributionally Robust $k$-SIP and Distributionally Risk-Receptive $k$-SIP along with finitely convergent exact algorithms for solving them.
  arXiv  Detail & Related papers  (2024-06-18T19:30:46Z)
• Sample-Efficient Robust Multi-Agent Reinforcement Learning in the Face of Environmental Uncertainty [40.55653383218379]
  This work focuses on learning in distributionally robust Markov games (RMGs) We propose a sample-efficient model-based algorithm (DRNVI) with finite-sample complexity guarantees for learning robust variants of various notions of game-theoretic equilibria.
  arXiv  Detail & Related papers  (2024-04-29T17:51:47Z)
• A Minimaximalist Approach to Reinforcement Learning from Human Feedback [49.45285664482369]
  We present Self-Play Preference Optimization (SPO), an algorithm for reinforcement learning from human feedback. Our approach is minimalist in that it does not require training a reward model nor unstable adversarial training. We demonstrate that on a suite of continuous control tasks, we are able to learn significantly more efficiently than reward-model based approaches.
  arXiv  Detail & Related papers  (2024-01-08T17:55:02Z)
• Regret Minimization and Convergence to Equilibria in General-sum Markov Games [61.6869963435955]
  We present the first algorithm for learning in general-sum Markov games that provides sublinear regret guarantees when executed by all agents.<n>Our algorithm is decentralized, computationally efficient, and does not require any communication between agents.
  arXiv  Detail & Related papers  (2022-07-28T16:27:59Z)
• Decentralized Optimistic Hyperpolicy Mirror Descent: Provably No-Regret Learning in Markov Games [95.10091348976779]
  We study decentralized policy learning in Markov games where we control a single agent to play with nonstationary and possibly adversarial opponents. We propose a new algorithm, underlineDecentralized underlineOptimistic hypeunderlineRpolicy munderlineIrror deunderlineScent (DORIS) DORIS achieves $sqrtK$-regret in the context of general function approximation, where $K$ is the number of episodes.
  arXiv  Detail & Related papers  (2022-06-03T14:18:05Z)
• Learning Risk-Averse Equilibria in Multi-Agent Systems [13.25454171233235]
  In multi-agent systems, intelligent agents are tasked with making decisions that have optimal outcomes when the actions of the other agents are as expected. We introduce a new risk-averse solution concept that allows the learner to accommodate unexpected actions. We show that our population of agents that approximate a risk-averse equilibrium is particularly effective in the presence of unseen opposing populations.
  arXiv  Detail & Related papers  (2022-05-30T21:20:30Z)
• Robust Reinforcement Learning using Adversarial Populations [118.73193330231163]
  Reinforcement Learning (RL) is an effective tool for controller design but can struggle with issues of robustness. We show that using a single adversary does not consistently yield robustness to dynamics variations under standard parametrizations of the adversary. We propose a population-based augmentation to the Robust RL formulation in which we randomly initialize a population of adversaries and sample from the population uniformly during training.
  arXiv  Detail & Related papers  (2020-08-04T20:57:32Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.