analiza aiqbench
This monograph maps standard game classes and solution concepts onto reinforcement-learning models, and it labels each correspondence as a definitional identity, an exact reduction, or a structural analogy. Its most useful part for practitioners is the final section on where the mapping breaks: non-stationarity in independent learners, impossibility results for uncoupled convergence to Nash equilibrium, and the gap between coarse correlated equilibria and correlated equilibria. Readers building multi-agent RL systems should treat the correspondence tables as conditional tools, not blanket guarantees.
When Is a Game a Markov Decision Process? Correspondences Between Game Theory and Reinforcement Learning
arXiv:2610.41962v1 Announce Type: cross 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.
Title:When Is a Game a Markov Decision Process? Correspondences Between Game Theory and Reinforcement Learning
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.
Computer Science and Game Theory (cs.GT); Machine Learning (cs.LG)
arXiv:2610.41962 [cs.GT]
(or arXiv:2610.41962v1 [cs.GT] for this version)
https://doi.org/10.48550/arXiv.2610.41962 Focus to learn more arXiv-issued DOI via DataCite (pending registration)
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.
Text integral sub licența deschisă a publicației · 371 cuvinte
Subiecte conexe
Exploiting Intrinsic Duality for Multi-Hop Question Generation
arXiv · 4 aug. 2026
LexReward: A Taxonomy-Driven Reward Framework for Legal Language Models
arXiv · 1 oct. 2026
Sample complexity of variance-reduced policy gradient: weaker assumptions and lower bounds
arXiv · 5 oct. 2026
SMOPD: Multi-Reward Reinforcement Learning via Specialize-and-Merge Online Policy Distillation
arXiv · 6 aug. 2026