CS Paper Radar

Truncated Noisy Best-Response Algorithms: Toward Game Theoretic Learning with Safety Guarantees

Vartika Singh, Philip N. Brown

cs.GT cs.MAeess.SY ·submitted 2026-09-10 17:41 UTC · v1

Abstract

We consider a game theoretic approach to solve multi-agent coordination problems with submodular maximization objectives. It is known for such problems that the Nash equilibria for the corresponding game are always within 50% of the optimal, but that the equilibria which achieve this worst-case bound are not stable. To exploit this instability, we propose a family of algorithms which we call Truncated Noisy Best-Response (TNBR) Algorithms. These algorithms are flexibly characterized by agents asynchronously and stochastically selecting actions from a neighbourhood of their best response payoffs. We compute bounds on the recurrent classes of TNBR algorithms' associated Markov chains. Our bounds fall into two categories: first, "Performance" bounds ensure that TNBR algorithms always have a high-value recurrent state; second, "Safety" bounds ensure that TNBR algorithms never have arbitrarily-bad recurrent states. Furthermore, these two types of bounds are linked by a waterbed-like effect: every game with a poor Safety guarantee necessarily has a favorable Performance guarantee.

Closest papers

Nearest neighbours by meaning across the whole index.

ABRA: An algorithm which cannot converge to low-quality Nash equilibria

cs.GT ·2026-09-10 ·Vartika Singh, Philip N. Brown
publishedhot direction similarity 0.75
Abstract

We consider a game theoretic approach to solve multi-agent coordination problems with submodular objectives. It is known for such problems that the Nash equilibria for the corresponding game are always within 50% of the optimal. A recent work further shows that the equilibria which achieve this worst-case bound are not stable. Leveraging this, we design an Approximate Best Response Algorithm (ABRA) governed by a noise parameter and a rationality parameter. The noise allows ABRA to escape the bad equilibria and the rationality parameter balances any degradation in the objective function caused by the noise. We show for any two-player game that if ABRA converges to a Nash equilibrium, its system objective value is strictly more than 50% of optimal plus a term controlled by the noise parameter. Otherwise, ABRA converges to some recurrent class: if a recurrent class contains any action profile yielding system objective less than 50% of the optimal, the class must also contain either the optimal action profile or an action profile yielding system objective strictly more than 50\% of the optimal by the same amount in addition to a factor controlled by noise parameter. The time that ABRA spends in such action profiles can be controlled using the rationality parameter. Using numerical simulations, we show that the minimum expected objective function is typically well above half of the optimal.

0.71

How Learning Selects Equilibria and When It Leads to Collusion

cs.GT ·2026-10-26 ·Hanzhang Wang, Manxi Wu
benchmark similarity 0.66
Abstract

We study how learning algorithm design shapes equilibrium selection in infinite-horizon discounted Markov games with finite states and actions. Each episode, players choose smooth best responses to beliefs about opponents' policies, test them using noisy observations, and resample rejected beliefs or explore at rates determined by increasing transformations of their discounted values. We show that stochastically stable states induce approximate stationary Nash equilibria maximizing the minimum transformed discounted value across players, with transformations governing which players selection favors. In repeated games with bounded recall of noisy public signals, longer recall weakly increases the selected minimum transformed value. In repeated Cournot games, every stochastically stable state induces an approximate public perfect equilibrium whose minimum discounted profit across firms exceeds the Cournot-Nash benchmark. Collusion is therefore inevitable under these conditions and learning dynamics. For symmetric firms, selected profits can approach the monopoly benchmark arbitrarily closely. These results offer a novel equilibrium-selection perspective on algorithmic collusion.

0.17

Robust PAC Learning of Concurrent Stochastic Games

cs.LG cs.GTcs.LOcs.MA ·2026-09-03 ·Angel Y. He, David Parker
top venuebenchmark similarity 0.65
Abstract · Camera-ready version of a paper accepted to NeurIPS 2026. Main text: 10 pages, 1 figure, 2 tables; Appendix: 22 pages, 2 figures, 1 table. M…

We introduce the first Probably Approximately Correct (PAC) learning framework for general-sum concurrent stochastic games (CSGs) with transition uncertainty, while addressing the challenge of Nash equilibrium (NE) existence. Our algorithm maintains data-driven $L^1$ confidence sets over transition kernels and solves a robust CSG to compute a social-welfare optimal $\varepsilon$-NE, using a robust MDP-based exploration mechanism to drive joint state-action coverage. Crucially, we introduce a Nash margin characterisation that enables principled reasoning about equilibrium existence: the framework either returns an $\varepsilon$-approximate NE whose social-welfare value is $\varepsilon$-close to optimal, or provides a sound certificate that no exact NE exists. Under a minimum reachability condition $p_{\mathrm{reach}}>0$ over relevant state-action pairs, the algorithm terminates after a polynomial number of trajectory samples, with sample complexity $\widetilde{O}\left( {R_{\max}^2 H^4 |S|^2 |A| / (p_{\mathrm{reach}} \varepsilon^2)} \right)$. Empirical results on benchmark CSGs demonstrate near-optimal performance, correct handling of equilibrium (non-)existence, and sample complexity consistent with theory.

0.33

Learning Rational Strategies for Temporal Objectives in Multi-Agent Systems

cs.LG cs.LOcs.MA ·2026-10-15 ·Omar Adalat, Edwin Hamel-De le Court, Francesco Belardinelli
similarity 0.65
Abstract

We study rational synthesis for stochastic multi-agent systems with unknown dynamics, where each agent is equipped with its own probabilistic temporal objective specified using Probabilistic Linear Temporal Logic on Finite Traces ($\mathsf{PLTL}_f}$). We impose solution concepts (e.g., Nash equilibrium, subgame-perfect equilibrium) as constraints on the joint strategy profile, using payoffs derived from each agent's probability of satisfying its temporal objective. In particular, we formulate per-agent rational synthesis as finding a strategy profile -- if one exists -- such that (i) the designated agent's probabilistic temporal constraint is satisfied, and (ii) the profile represents a stable solution under a chosen solution concept. We give conditional convergence guarantees for tabular Nash-Q learning, certify satisfaction with simultaneous finite-sample confidence bounds, and assess strategic stability with approximate best-response checking. Our approach operates in a stochastic \emph{Multi-Agent Reinforcement Learning} (MARL) environment, where model-free learning algorithms attempt to attain extremal satisfaction probabilities for temporal objectives automatically compiled into reward automata. Our approach is empirically validated using 8 general-sum concurrent stochastic games.

0.15

$Q$ Can Play That Game: Online Fitted $Q$-Iteration for Continuous-Action Zero-Sum Markov Games with Convex-Concave Function Approximation

cs.GT cs.MA ·2026-10-02 ·Kushagra Gupta, Jingqi Li, Cade Armstrong, Lasse Peters, Ross E. Allen +2 more
code/data similarity 0.65
Abstract

Zero-sum Markov games arise in a wide variety of sequential decision-making problems such as adversarial learning and planning against modeled uncertainties. However, prior work on finite-sample guarantees on the learned state-action value function ($Q$-function) for zero-sum Markov games is largely restricted to finite-action settings, or to continuous-action games in which agents have linear dynamics and quadratic rewards (i.e. linear-quadratic, or LQ, games). A central challenge in extending such guarantees to more general continuous-action zero-sum Markov games is that the associated Bellman operator involves a minimax problem that need not admit a tractable saddle-point solution. To this end, we first introduce a class of neural network function approximators for the $Q$-function that is convex-concave in the players' actions, which guarantees that this minimax problem admits a pure-strategy saddle point. We then study an online variant of fitted $Q$-iteration employing this function class and establish, to the best of our knowledge, the first finite-sample guarantees for non-LQ zero-sum Markov games with continuous states and actions. Our code can be found at https://github.com/CLeARoboticsLab/QCanPlayThatGame.

0.33

High-Probability Nash Regret for Decentralized Learning in Markov $α$-Potential Games: Episodic and Fully Online Asynchronous Algorithms with Applications to Markov Congestion Games

cs.LG cs.GTcs.MAeess.SY+1 ·2026-09-14 ·S. Rasoul Etesami
similarity 0.64
Abstract

We study decentralized learning of Nash equilibria (NE) in infinite-horizon discounted Markov games under bandit feedback, focusing on Markov $α$-potential games. We develop KL-projected natural policy gradient (NPG) algorithms in two settings: an episodic setting with frozen policies during sampling and a fully online setting in which players receive a single realized cost sample per time step and update their policies asynchronously along a continuing trajectory. We establish finite-time high-probability NE regret bounds of order $\widetilde O(T^{-1/4})$ and $\widetilde O(T^{-2/15})$ for the episodic and fully online settings, respectively, up to fixed approximation terms. Crucially, our bounds eliminate the distribution-mismatch coefficient, which can scale prohibitively with the size of the state space, while accommodating potential approximation, estimation-oracle bias, and transition sensitivity. We further identify a state-wise potential structure that yields sharper guarantees with additive dependence on the potential approximation error $α$. We specialize the framework to independent-resource Markov congestion games (IMCGs), establish their approximate-potential and transition-sensitivity properties, and construct decentralized estimation oracles from realized costs. As an application, we introduce strategic online job scheduling on stochastic machines and obtain a scalable decentralized algorithm for learning stable dispatching policies. Overall, our results provide the first finite-time high-probability NE regret guarantees for fully online asynchronous decentralized learning in Markov $α$-potential games, remove distribution-mismatch coefficients from the regret bounds, accommodate fixed estimation-oracle bias, and provide scalable decentralized learning with finite-time guarantees for IMCGs.

0.42

NashDreamer: Model-Based Reinforcement Learning for Zero-Sum Imperfect-Information Games

cs.LG ·2026-09-01 ·Tomáš Holeček, Viliam Lisý
top venuebenchmarkposition similarity 0.64
Abstract · Accepted to NeurIPS 2026

Model-based reinforcement learning (MBRL) has achieved remarkable results in single-agent domains, yet its extension to competitive imperfect information games (IIGs) remains underexplored. In multi-agent settings, opponent-induced non-stationarity complicates the learning process, and decentralized model learning faces severe identifiability barriers, which we argue make centralized model learning a mathematical necessity. Building on this analysis, we propose NashDreamer, a principled MBRL framework for two-player zero-sum IIGs. It introduces a centralized Multi-Agent Recurrent State-Space Model (MARSSM) that decouples environment dynamics from the effect of players' strategies on their individual observations. NashDreamer is designed to use arbitrary policy gradient algorithms and inherits their convergence guarantees towards Nash equilibria under an idealized model. Empirical evaluations across five benchmark games demonstrate that NashDreamer substantially improves sample efficiency over model-free baselines early in the training. Finally, we theoretically analyze the architecture's optimization landscape, identifying the vulnerability of the Dreamer family of algorithms to posterior collapse in stochastic environments. We leave it as an open challenge.

0.34

Exploiting Aggregate Feedback for Decentralized Equilibrium Learning in Markov Games: A Smart Grid Application

cs.GT ·2026-11-17 ·Siying Huang, Yifen Mu, Ge Chen, Qingshan Jia
similarity 0.64
Abstract

In many multi-agent systems, an agent's payoff depends on its own action and an aggregate of other agents' actions, rather than their individual decisions. This paper investigates decentralized equilibrium learning in Markov games (MGs) with such aggregative reward structures. However, existing decentralized learning algorithms for general MGs typically rely on bandit feedback, without exploiting the additional information available from aggregate observations. To exploit this information, we develop an aggregation-predictive stage-based V-learning algorithm with hybrid-feedback Exp3-IX. Using known local reward functions and observed aggregate quantities, each agent evaluates the immediate rewards of all candidate actions and predicts their immediate losses from historical aggregate feedback, while continuation values are learned from selected-action state transitions. The algorithm requires neither opponents' individual information nor knowledge of the transition kernel. We establish a high-probability regret bound that explicitly depends on aggregate prediction errors and retains the standard worst-case order. Under a regularity condition on adaptive stage lengths, the algorithm learns an $ε$-approximate coarse correlated equilibrium (CCE) within $\widetilde O(SA_{\max}T^5/ε^2)$ episodes and extends to correlated equilibrium (CE) learning. We further apply the algorithm to a renewable-rich microgrid with strategic prosumers and shared energy storage. Numerical results show smaller deviation gaps and lower gap-AUC than three learning baselines. Compared with representative demand-response rules, the learned policies exhibit weaker incentives for unilateral deviations while maintaining favorable user rewards, high renewable utilization, and relatively stable electricity prices.

0.11