CS Paper Radar

When Is a Game a Markov Decision Process? Correspondences Between Game Theory and Reinforcement Learning

Eduardo C. Garrido-Merchán

cs.GT cs.LG ·submitted 2026-10-30 16:12 UTC · v2
theory

Abstract

Reinforcement learning and game theory describe the same object from two sides. Game theory says what a rational outcome of a strategic interaction is; reinforcement learning says how an agent could reach one through experience. The two literatures nevertheless keep separate vocabularies for identical structures, and the treatments that bridge them present the correspondence as analogy rather than theorem. This monograph supplies the theorems. A game is a Markov decision process in three distinct senses, and every table entry is labelled with the one that applies: a definitional identity, an exact reduction carried by a value- and solution-preserving map, or a structural analogy that fails under identifiable conditions. We take every standard class of game, from normal-form through repeated, stochastic, partially observable, extensive-form with imperfect information, Bayesian, graphical, Stackelberg, potential, coalitional, mean-field and evolutionary games, and identify for each the decision-theoretic model that reinforcement learning already studies under another name. The same treatment is applied to solution concepts: Nash equilibrium and the fixed point of the Bellman optimality operator, quantal response equilibrium and the soft Bellman operator, the Shapley value and credit assignment, Blackwell approachability and no-regret learning. We map each model class onto the training procedures sound for it and record the complexity of the associated solution problems. A final part collects the correspondences that do not hold: the non-stationarity that invalidates the independent-learner reduction, the impossibility results that forbid uncoupled convergence to Nash equilibrium, and the gap between the coarse correlated equilibria that no-regret self-play reaches and the correlated equilibria it is credited with.

Closest papers

Nearest neighbours by meaning across the whole index.

Bayesian Replicator Dynamics and the Inversion of Strict Dominance in Bimatrix Games

cs.GT cs.MA ·2026-10-26 ·Jaime Ruiz-Serra, Nihat Ay, Michael Harré
similarity 0.66
Abstract · 18 pages, 3 figures

Replicator dynamics, the central model of evolutionary game theory, describe populations evolving under selection and agents learning by trial and error. They also admit a third use: continuous-time Bayesian inference, in which an agent planning against an opponent accumulates evidence for each candidate strategy. Here we show that this use divides all two-player games into two classes. With the standard expected-utility payoff, the dynamics can be expressed as Bayesian updating only in games (with any number of actions) where no player has a dominant strategy. The logarithmic payoff of Ay and Erb (2005) admits the Bayesian representation in every game. Coordination, anti-coordination, and cyclic games share qualitative dynamics under both payoff definitions, with equilibria displaced and selection thresholds shifted. In contrast, the flows of every game with a dominant strategy are reversed between the payoff definitions, with the strictly dominant strategy eliminated under logarithmic payoffs. Cooperation therefore emerges in the Prisoner's Dilemma, and games of common interest converge to mutual defection. For two-action games the classification is complete and rests on an exact Hamiltonian structure shared by both payoff definitions. The structure gives a behavioural test: cycles in the classic Matching Pennies game have amplitude-independent period (isochronous) under logarithmic payoffs, but not under expected utility. Logarithmic evidence integration thus determines which strategic outcomes dynamical selection can reach, wherever learning approximates Bayesian updating.

0.23

Game-Theoretic Foundations for Undiscounted Bisimulation Metrics

cs.AI cs.GTcs.LGmath.OC ·2026-10-28 ·Matthew Zurek, Yudong Chen, Josiah P. Hanna
theory similarity 0.63
Abstract

Bisimulation metrics offer a principled notion of task-relevant state similarity in reinforcement learning, but existing constructions and methods are largely confined to discounted MDPs, where contraction arguments ensure well-defined fixed points and downstream guarantees. We develop a unified foundation for bisimulation metrics in undiscounted settings, that is total- and average-reward problems, by replacing the standard operator-centric view with a game-centric one: we interpret prior metric operators as Bellman-Shapley operators of zero-sum turn-based games and define metrics as the corresponding game value functions, yielding unique definitions even when $γ=1$. This game-theoretic foundation facilitates transfer of dynamic-programming theory and algorithms. We also use this game-centric perspective to characterize how metric finiteness depends on structural properties of the underlying MDP and motivate certain directed metrics that remain finite in weakly communicating MDPs. We further introduce an abstract framework for modifying the games' action spaces, allowing general transition coupling sets, that recovers many existing metrics and guides new constructions. Finally, we prove that these metrics bound total-reward and, when the optimal gain is state-independent, optimal relative value differences. We also provide error and suboptimality guarantees for aggregation-based planning in total- and average-reward settings.

0.26

A note on goal-based hierarchical RL

cs.AI ·2026-09-13 ·Kevin Murphy
similarity 0.60
Abstract

The agent-centric general value function (ACGVF) construction of \citet{tasse2026goal} lets the agent make two decisions that are normally imposed by the environment or agent designer: which goal to pursue and when to declare a goal as finished (in addition to choosing the action). This is a very general framework that subsumes almost all prior work on reinforcement learning, control and planning, as well as more general formalisms proposed in the cognitive sciences. However, it assumes the environment is fully observed, i.e., that the observation is a sufficient statistic. In \citet{murphy2025rl}, a general agent design was proposed where the policy is based on an internal belief state $z_t$ and an internal goal; however, the goals were assumed to be externally provided. In this note, we unify and extend these two approaches using the formalism of hierarchical hidden Markov models (HHMM) \citep{murphy2001hhmm}.

0.35

$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.60
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

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

An Introduction to World Models for Generalist Agents

cs.AI ·2026-10-22 ·Zhihui Zhu
survey similarity 0.59
Abstract

World models have recently emerged as a promising direction toward developing generalist agents capable of understanding, predicting, and interacting with diverse environments. However, despite growing interest, the concept of a world model remains loosely defined, encompassing approaches ranging from predictive dynamics models and learned simulators to models that jointly generate future observations and actions. This introductory paper aims to clarify the concept of world models and provide a unified perspective on their role in developing generalist agents. Starting from the partially observable Markov decision process (POMDP) framework, we connect world modeling to classical control, dynamical systems, signal processing, and reinforcement learning. We introduce different approaches to world modeling, emphasizing the knowledge they capture, their learning objectives, and how they support decision-making. We further explore the relationship between world modeling and policy learning, highlighting how these capabilities can be unified through conditional prediction without requiring separate models. Rather than offering an exhaustive survey of existing methods, this paper focuses on fundamental concepts, modeling principles, and connections, with the goal of providing an accessible and unified introduction to world models for generalist agents.

0.19

Equilibrium in Multi-Agent Reinforcement Learning

cs.GT ·2026-08-24 ·Maurizio D'Andrea, Bar Light
similarity 0.58
Abstract

Standard solution concepts for stochastic games, such as Markov perfect equilibrium and Markov coarse correlated equilibrium, are computationally difficult, and thus, standard decentralized reinforcement-learning algorithms should not generally be expected to converge to them. In this paper, we study the equilibrium generated by such algorithms. In particular, we introduce a new solution concept for stochastic games, Markov Bayes coarse correlated equilibrium (MBCCE), defined as a distribution over states and stationary policy profiles such that, after observing the state but before observing her recommended action, no player can gain by choosing a different current action, with the sampled policy profile governing play thereafter. We discuss the parallels between MBCCE and coarse correlated equilibrium (CCE) in finite normal-form games and show that MBCCE retains several of its key properties. We then introduce a corresponding regret notion, adaptive Markov coarse regret (AMCR), and show that vanishing AMCR implies that every accumulation point of the empirical distribution of realized states and policy profiles is an MBCCE. Crucially, we show that achieving AMCR reduces to two standard learning tasks: minimizing external regret at each state and accurately evaluating the current joint policy. We then prove that under mild conditions these properties hold for two natural RL algorithmic designs: a decentralized asynchronous actor--critic algorithm through a new two-timescale stochastic-approximation analysis, and a standard episodic multi-agent projected policy-gradient method. Hence, both algorithms generate approximate MBCCEs, and we establish explicit finite-time convergence rates for both.

0.08

Decentralized Multi-Player Q-Learning in Episodic Markov Decision Processes with Information Asymmetry

cs.LG ·2026-08-13 ·Larissa Xu, King Bi, William Chang
top venuebenchmark similarity 0.58
Abstract

We study decentralized multi-player reinforcement learning in episodic tabular Markov decision processes (MDPs) under three forms of information asymmetry: (A) unobserved actions with common rewards, (B) observed actions with independent rewards, and (C) unobserved actions with independent rewards. Players cannot communicate during learning but may agree on a protocol a priori. For Problems A and B we propose \texttt{mQ-learning} and \texttt{mQ-learning-intervals}, achieving $\tilde{O}(\sqrt{H^4 S A_{\text{joint}}\, T})$ regret, where $H$ is the horizon, $S$ the state count, $T = KH$ the total steps, and $A_{\text{joint}} = \prod_{i=1}^M |\mathcal{A}_i|$ the joint action space across $M$ players. For Problem C we give \texttt{mEXC} and \texttt{mEXC-Bellman}, two-phase explore-then-commit algorithms with regret $\tilde{O}(H (S A_{\text{joint}})^{1/3} T^{2/3})$. Against the centralized joint-action benchmark, decentralized learning under information asymmetry matches the single-agent Q-learning rate of \cite{jin2018q} up to logarithmic factors. Because $A_{\text{joint}}$ grows exponentially in $M$, the bounds are most meaningful for small $M$ or small per-player action sets.

0.34