The Sufficiency of Memoryless Strategies

101 concepts71 papers

In sequential decision-making, it is natural to assume that the best course of action depends on everything that has happened before. To decide whether to invest today, one might look at the history of market fluctuations; to decide on a robot's next move, one might review its entire trajectory. However, a recurring discovery across reinforcement learning, game theory, and formal verification is that for a vast class of problems, history is redundant. Instead, an agent can act optimally using a memoryless strategy—a policy that maps the current state directly to an action without regard for the past.

The State as a Sufficient Statistic

The core intuition behind memoryless sufficiency is that the "state" of a system can be designed to encapsulate all information relevant to future rewards. If the current state is a sufficient statistic for the future, the history of how the agent arrived at that state provides no additional predictive power.

Shakerinava et al. and Siamak Ravanbakhsh provide an axiomatic foundation for this in Utility Theory for Sequential Decision Making. They show that if an agent’s preferences over trajectories satisfy a "memorylessness" axiom, their goals can be represented by a standard additive reward function. In such environments, a state-based policy is not just a simplification; it is mathematically sufficient for rationality.

Recursive Objectives and Positional Determinacy

Why does memorylessness hold even in complex games? The answer often lies in the recursive structure of the objective. In many infinite-horizon games, the "remaining" game from any given state looks identical regardless of when or how that state was reached.

For example, Chatterjee et al. and Thomas A. Henzinger demonstrate in Probabilistic Systems with LimSup and LimInf Objectives that optimal play for long-term limit rewards is achievable through pure, memoryless strategies. This property, often called positional determinacy, ensures that players do not need randomness or history to maximize expected outcomes. Similarly, Murhekar et al. and Eklavya Sharma show in Nash Equilibria of Two-Player Matrix Games Repeated Until Collision that stationary strategies—fixed probability distributions—are sufficient for equilibrium because the subgame remains invariant until the game terminates.

Preserving Memorylessness under Risk and Uncertainty

One might expect that adding risk-aversion or robustness requirements would force an agent to track history to "balance" past losses. Surprisingly, specific mathematical formulations of these requirements preserve the sufficiency of memoryless policies.

Scaling to Multi-Agent Systems

In large-scale systems, the sufficiency of memoryless strategies is a vital tool for overcoming the curse of dimensionality. As the number of agents grows, tracking the joint history of all interactions becomes impossible.

Saldi et al. and Naci Saldı prove in Markov-Nash Equilibria in Mean-Field Games with Discounted Cost that in the mean-field limit, strategies depending only on the current state are sufficient to achieve optimality. This reduction is also seen in leader-follower dynamics; Singh et al. show in Computing Stackelberg Equilibria in Discounted Stochastic Games that optimal leader strategies can be restricted to Markov stationary policies without losing the ability to reach equilibrium.

Computational and Practical Sufficiency

Beyond theoretical elegance, memoryless strategies are preferred because they are computationally tractable. Brázdil et al. and the authors of MultiGain demonstrate that for unichain MDPs with multiple objectives, memoryless strategies significantly reduce the complexity of controller synthesis.

In decentralized control, Abhishek Gupta shows in On the Existence of Optimal Policies for a Class of Static and Sequential Dynamic Teams that for every optimal randomized strategy, there exists a deterministic counterpart. This allows practitioners to deploy simple, rule-based behaviors—such as the threshold-based scheduling policies for IoT devices proposed by Zhou et al. in On the Age of Information in Internet of Things Systems with Correlated Devices—knowing they are not sacrificing performance for simplicity.

Key Foundational Work

Social security as Markov equilibrium in OLG models (2004) — contributed 2 concept elements to this direction.
The Complexity of Stochastic Rabin and Streett Games (2004) — contributed 1 concept elements to this direction.
History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 70 papers
  2. Version 1 · 2026-10-04 · 72 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_memoryless_strategy_sufficiency_1d9f8a65,
  title = {memoryless strategy sufficiency},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/memoryless-strategy-sufficiency/rdr_1d9f8a65e0f449599b3da735dd3fff20},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 2, frozen text):

@misc{lacuna_memoryless_strategy_sufficiency_1d9f8a65_v2,
  title = {memoryless strategy sufficiency},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/memoryless-strategy-sufficiency/rdr_1d9f8a65e0f449599b3da735dd3fff20/v/2},
  note = {Version 2, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake