mlsanityData to 14 Oct 2026

Constant-Memory Strategies in Stochastic Games: Best Responses and Equilibria

arXiv 2505.07008 ↗First posted 11 May 2025cs.GT cs.MAcited by 1

On the map: Deep reinforcement learning methods → RL for games and combinatorial optimization

Abstract (arXiv)

Stochastic games have become a prevalent framework for studying long-term multi-agent interactions, especially in the context of multi-agent reinforcement learning. In this work, we comprehensively investigate the concept of constant-memory strategies in stochastic games. We first establish some results on best responses and Nash equilibria for behavioral constant-memory strategies, followed by a discussion on the computational hardness of best responding to mixed constant-memory strategies. Those theoretic insights are later verified on several sequential decision-making testbeds, including the textitIterated Prisoner's Dilemma, the textitIterated Traveler's Dilemma, and the textitPursuit domain. This work aims to enhance the understanding of theoretical issues in single-agent planning under multi-agent systems, and uncover the connection between decision models in single-agent and multi-agent contexts. The code is available at texttthttps://github.com/Fernadoo/Const-Mem.

Key facts. Cited by 1 paper in the map (data through 14 Oct 2026). Placed in RL for games and combinatorial optimization, one of 15 directions in Deep reinforcement learning methods. Builds on 27 of its 75 references that are in the map. First posted on arXiv 11 May 2025.

Builds on

27 of 75 references.

References · 27

  1. 2017Attention Is All You Needcited by 60,361
  2. 2017Proximal Policy Optimization Algorithmscited by 15,215
  3. 2014Learning Phrase Representations using RNN Encoder-Decoder for Statistical Machine Translationcited by 4,057
  4. 2013Playing Atari with Deep Reinforcement Learningcited by 3,274
  5. 2016Asynchronous Methods for Deep Reinforcement Learningcited by 2,258
  6. 2017Multi-Agent Actor-Critic for Mixed Cooperative-Competitive Environmentscited by 1,558
  7. 2020Gradient Surgery for Multi-Task Learningcited by 1,256
  8. 2019Meta-World: A Benchmark and Evaluation for Multi-Task and Meta Reinforcement Learningcited by 1,204
  9. 2021The Surprising Effectiveness of PPO in Cooperative, Multi-Agent Gamescited by 942
  10. 2017Counterfactual Multi-Agent Policy Gradientscited by 751
  11. 2020Monotonic Value Function Factorisation for Deep Multi-Agent Reinforcement Learningcited by 485
  12. 2019Leveraging Procedural Generation to Benchmark Reinforcement Learningcited by 483
15 more
  1. 2023Building Cooperative Embodied Agents Modularly with Large Language Modelscited by 237
  2. 2023Habitat 3.0: A Co-Habitat for Humans, Avatars and Robotscited by 228
  3. 2015Contextual Markov Decision Processescited by 220
  4. 2017Autonomous Agents Modelling Other Agents: A Comprehensive Survey and Open Problemscited by 131
  5. 2021Why Generalization in RL is Difficult: Epistemic POMDPs and Implicit Partial Observabilitycited by 109
  6. 2022Contextualize Me -- The Case for Context in Reinforcement Learningcited by 46
  7. 2015A Game-Theoretic Model and Best-Response Learning Method for Ad Hoc Coordination in Multiagent Systemscited by 44
  8. 2022A Survey of Ad Hoc Teamwork Researchcited by 43
  9. 2024AuctionNet: A Novel Benchmark for Decision-Making in Large-Scale Gamescited by 28
  10. 2015Belief and Truth in Hypothesised Behaviourscited by 21
  11. 2017Reinforcement Mechanism Design, with Applications to Dynamic Pricing in Sponsored Search Auctionscited by 12
  12. 2017Reinforcement Learning Produces Dominant Strategies for the Iterated Prisoner's Dilemmacited by 8
  13. 2019On Convergence and Optimality of Best-Response Learning with Policy Types in Multiagent Systemscited by 4
  14. 2025Single-Agent Planning in a Multi-Agent System: A Unified Framework for Type-Based Plannerscited by 2
  15. 2019Pure Strategy Best Responses to Mixed Strategies in Repeated Gamescited by 1

Built on by

Cited by year

Citing papers per year: 2025: 1.

1 paper.

  1. 2025A Computable Game-Theoretic Framework for Multi-Agent Theory of Mindcited by 1

Similar, not cited

Close in wording, no citation either way

  1. 2026MEMO: Memory-Augmented Model Context Optimization for Robust Multi-Turn Multi-Agent LLM Games
  2. 2024Game Theory and Multi-Agent Reinforcement Learning : From Nash Equilibria to Evolutionary Dynamics
  3. 2024Tractable Equilibrium Computation in Markov Games through Risk Aversion
  4. 2024Unraveling the Complexity of Memory in RL Agents: an Approach for Classification and Evaluation
  5. 2024widetildeO(T-1) Convergence to (Coarse) Correlated Equilibria in Full-Information General-Sum Markov Games
  6. 2026Equilibrium in Multi-Agent Reinforcement Learning ↗
  7. 2024Equilibrium Selection for Multi-agent Reinforcement Learning: A Unified Framework
  8. 2025Provable Memory Efficient Self-Play Algorithm for Model-free Reinforcement Learning