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

arXiv: https://arxiv.org/abs/2505.07008 · HTML: https://mlsanity.com/paper/2505.07008/

## Key facts

- Cited by 1 papers 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.

## Placed in

- Deep reinforcement learning methods / [RL for games and combinatorial optimization](https://mlsanity.com/deeprl/rl-for-games-and-combinatorial-optimization/)

## Builds on (most cited first, 27 of 27)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [Learning Phrase Representations using RNN Encoder-Decoder for Statistical Machine Translation](https://mlsanity.com/paper/1406.1078/) (2014)
- [Playing Atari with Deep Reinforcement Learning](https://mlsanity.com/paper/1312.5602/) (2013)
- [Asynchronous Methods for Deep Reinforcement Learning](https://mlsanity.com/paper/1602.01783/) (2016)
- [Multi-Agent Actor-Critic for Mixed Cooperative-Competitive Environments](https://mlsanity.com/paper/1706.02275/) (2017)
- [Gradient Surgery for Multi-Task Learning](https://mlsanity.com/paper/2001.06782/) (2020)
- [Meta-World: A Benchmark and Evaluation for Multi-Task and Meta Reinforcement Learning](https://mlsanity.com/paper/1910.10897/) (2019)
- [The Surprising Effectiveness of PPO in Cooperative, Multi-Agent Games](https://mlsanity.com/paper/2103.01955/) (2021)
- [Counterfactual Multi-Agent Policy Gradients](https://mlsanity.com/paper/1705.08926/) (2017)
- [Monotonic Value Function Factorisation for Deep Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2003.08839/) (2020)
- [Leveraging Procedural Generation to Benchmark Reinforcement Learning](https://mlsanity.com/paper/1912.01588/) (2019)
- [Building Cooperative Embodied Agents Modularly with Large Language Models](https://mlsanity.com/paper/2307.02485/) (2023)
- [Habitat 3.0: A Co-Habitat for Humans, Avatars and Robots](https://mlsanity.com/paper/2310.13724/) (2023)
- [Contextual Markov Decision Processes](https://mlsanity.com/paper/1502.02259/) (2015)
- [Autonomous Agents Modelling Other Agents: A Comprehensive Survey and Open Problems](https://mlsanity.com/paper/1709.08071/) (2017)
- [Why Generalization in RL is Difficult: Epistemic POMDPs and Implicit Partial Observability](https://mlsanity.com/paper/2107.06277/) (2021)
- [Contextualize Me -- The Case for Context in Reinforcement Learning](https://mlsanity.com/paper/2202.04500/) (2022)
- [A Game-Theoretic Model and Best-Response Learning Method for Ad Hoc Coordination in Multiagent Systems](https://mlsanity.com/paper/1506.01170/) (2015)
- [A Survey of Ad Hoc Teamwork Research](https://mlsanity.com/paper/2202.10450/) (2022)
- [AuctionNet: A Novel Benchmark for Decision-Making in Large-Scale Games](https://mlsanity.com/paper/2412.10798/) (2024)
- [Belief and Truth in Hypothesised Behaviours](https://mlsanity.com/paper/1507.07688/) (2015)
- [Reinforcement Mechanism Design, with Applications to Dynamic Pricing in Sponsored Search Auctions](https://mlsanity.com/paper/1711.10279/) (2017)
- [Reinforcement Learning Produces Dominant Strategies for the Iterated Prisoner's Dilemma](https://mlsanity.com/paper/1707.06307/) (2017)
- [On Convergence and Optimality of Best-Response Learning with Policy Types in Multiagent Systems](https://mlsanity.com/paper/1907.06995/) (2019)
- [Single-Agent Planning in a Multi-Agent System: A Unified Framework for Type-Based Planners](https://mlsanity.com/paper/2502.08950/) (2025)
- [Pure Strategy Best Responses to Mixed Strategies in Repeated Games](https://mlsanity.com/paper/1902.09066/) (2019)

## Built on by (most cited first, 1 of 1)

- [A Computable Game-Theoretic Framework for Multi-Agent Theory of Mind](https://mlsanity.com/paper/2511.22536/) (2025)

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