When Is a Game a Markov Decision Process? Correspondences Between Game Theory and Reinforcement Learning
arXiv:2610.41962 · cs.GT, cs.LG · Submitted 2026-10-30 · Read on arXiv
cs.GT, cs.LG
Submitted: 2026-10-30
Updated: 2026-11-08
Terminology
- Reinforcement Learning — 227× in this paper · explained in 5 episodes
- Regret — 108× in this paper · explained in 5 episodes
- Fixed Point — 48× in this paper · explained in 2 episodes
- Coordination — 39× in this paper · explained in 2 episodes
- Core — 37× in this paper · explained in 2 episodes
- POMDP — 36× in this paper · explained in 3 episodes
- Planner — 27× in this paper · explained in 4 episodes
- Cooperation — 26× in this paper · explained in 2 episodes
- Dec-POMDP — 19× in this paper · explained in 4 episodes
- Q-learning — 16× in this paper · explained in 3 episodes
- Continuation — 14× in this paper · explained in 2 episodes
- Reward Structure — 14× in this paper · explained in 3 episodes
- Benchmark — 13× in this paper · explained in 2 episodes
- Degeneracy — 13× in this paper · explained in 5 episodes
- Multi-Agent System — 12× in this paper · explained in 8 episodes
- Reward Function — 10× in this paper · explained in 5 episodes
- Monotonicity — 8× in this paper · explained in 3 episodes
- Robustness — 8× in this paper · explained in 7 episodes
- Sample Complexity — 8× in this paper · explained in 22 episodes
- Compatibility — 7× in this paper · explained in 2 episodes
- Consistency — 7× in this paper · explained in 3 episodes
- Papers — 7× in this paper · explained in 3 episodes
- Actor — 6× in this paper · explained in 3 episodes
- Axioms — 6× in this paper · explained in 2 episodes
- Composition — 6× in this paper · explained in 2 episodes
- Deep Reinforcement Learning — 6× in this paper · explained in 3 episodes
- Mean-Field Limit — 6× in this paper · explained in 3 episodes
- Reward Hacking — 6× in this paper · explained in 11 episodes
- Adam — 5× in this paper · explained in 3 episodes
- Credit assignment — 5× in this paper · explained in 3 episodes
- Pareto Frontier — 5× in this paper · explained in 5 episodes
- Asymmetry — 4× in this paper · explained in 3 episodes
- Bootstrapping — 4× in this paper · explained in 3 episodes
- Fairness — 4× in this paper · explained in 2 episodes
- Adversarial Training — 3× in this paper · explained in 2 episodes
- Contextual Bandit — 3× in this paper · explained in 2 episodes
- Convexity — 3× in this paper · explained in 3 episodes
- Decoder — 3× in this paper · explained in 2 episodes
- Degeneracies — 3× in this paper · explained in 2 episodes
- Exchangeability — 3× in this paper · explained in 2 episodes
- Information Structure — 3× in this paper · explained in 2 episodes
- Lyapunov Function — 3× in this paper · explained in 5 episodes
- Non-stationarity — 3× in this paper · explained in 4 episodes
- Augmentation — 2× in this paper · explained in 2 episodes
- Continuum Limit — 2× in this paper · explained in 3 episodes
- Convergence Rate — 2× in this paper · explained in 4 episodes
- Convex Hull — 2× in this paper · explained in 2 episodes
- Decoupling — 2× in this paper · explained in 2 episodes
- Failure Modes — 2× in this paper · explained in 5 episodes
- Hyperparameters — 2× in this paper · explained in 2 episodes
- Hysteresis — 2× in this paper · explained in 6 episodes
- Pruning — 2× in this paper · explained in 4 episodes
- Regret Bound — 2× in this paper · explained in 3 episodes
- Treewidth — 2× in this paper · explained in 5 episodes
- Anonymity — 1× in this paper · explained in 2 episodes
- Bifurcation — 1× in this paper · explained in 2 episodes
- Bradley-Terry Model — 1× in this paper · explained in 3 episodes
- Computational Complexity — 1× in this paper · explained in 2 episodes
- Convergence Rates — 1× in this paper · explained in 2 episodes
- Counterexamples — 1× in this paper · explained in 2 episodes
- Elias — 1× in this paper · explained in 2 episodes
- Fine-Tuning — 1× in this paper · explained in 7 episodes
- Formal Methods — 1× in this paper · explained in 3 episodes
- Generator — 1× in this paper · explained in 3 episodes
- Harness — 1× in this paper · explained in 2 episodes
- Information Gain — 1× in this paper · explained in 2 episodes
- Intermediate Regime — 1× in this paper · explained in 2 episodes
- Limit Cycles — 1× in this paper · explained in 3 episodes
- Meta-learning — 1× in this paper · explained in 4 episodes
- Mutual Information — 1× in this paper · explained in 4 episodes
- NP-hardness — 1× in this paper · explained in 4 episodes
- Regularization — 1× in this paper · explained in 3 episodes
- Sample Complexity Bounds — 1× in this paper · explained in 4 episodes
- Self-Consistency — 1× in this paper · explained in 3 episodes
- Trace — 1× in this paper · explained in 3 episodes
- Training Objective — 1× in this paper · explained in 3 episodes
- Transformer — 1× in this paper · explained in 4 episodes
- Zero-Shot Transfer — 1× in this paper · explained in 7 episodes
Sources
Related papers
- How Many Votes is a Lie Worth? Measuring Strategyproofness through Resource Augmentation
- Effective Horizons for Prophet Inequalities with Discounted I.I.D. Rewards
- Truthful-in-Expectation Mechanism with Constant Maximin-Share Guarantee
- The Power of Recruiting the Smaller Side: Two Additional Traders Suffice in Two-Sided Markets
- From signaling to interviews in random matching markets
- Optimizing Social Utility in Sequential Experiments