Value Based State Abstraction

38 concepts26 papers1 proposal

When a reinforcement learning (RL) agent faces a high-dimensional environment—such as a gridworld with millions of coordinates or a video game with raw pixel inputs—treating every distinct state as unique leads to the curse of dimensionality. To learn efficiently, the agent must compress the state space via state abstraction.

But how should we decide which states to group together?

The traditional approach relies on dynamics-preserving abstractions (such as bisimulation), which group states only if they share identical transition probabilities and immediate rewards. While mathematically elegant, this is often too restrictive: two states might have completely different transition paths but ultimately offer the exact same long-term strategic value.

Value-based state abstraction shifts the focus from what a state looks like or how it transitions to what a state is worth. If two states share the same optimal action-values (Q-values) or expected future returns, they are functionally equivalent for decision-making. By collapsing these states into a single abstract unit, we can drastically compress the environment without losing the ability to find an optimal policy.

Why Value Equivalence Works

To understand why value-based abstraction works, consider an agent navigating a maze to reach a single treasure chest. Two different positions in the maze might look completely different and lead to different adjacent squares. However, if both positions require the same optimal action (e.g., "move North") and yield the exact same expected long-term reward, distinguishing between them provides no functional benefit to the agent's policy.

As shown by Eddie J. Rafols et al. in Using Predictive Representations to Improve Generalization in Reinforcement Learning, arbitrary or random state aggregation can cause catastrophic interference, where an agent conflates states requiring opposing actions and becomes unable to learn a coherent policy. Value-based abstraction avoids this pitfall by grounding the aggregation directly in the agent's utility.

In a foundational theoretical analysis, Lihong Li et al. proved in Towards a Unified Theory of State Abstraction for MDPs that an optimal policy derived in a compressed abstract state space remains globally optimal in the original environment, provided that the abstraction groups states sharing the same optimal action and optimal action-value. This represents the most aggressive compression boundary possible that still guarantees a perfect solution. Similarly, Katharina Tluk von Toschanowitz et al. in Relevance determination in reinforcement learning (ESANN 2005) demonstrated that grouping states by value similarity rather than spatial proximity allows agents to discover these functional equivalence classes, preventing redundant learning.

Breaking the Markov Constraint

A common objection to aggressive state compression is that it often destroys the Markov property. If you merge states with different transition dynamics, the abstract environment becomes non-Markovian (history-dependent), which traditionally invalidates standard RL algorithms like Q-learning.

Remarkably, value-based abstraction bypasses this requirement. In Performance Guarantees for Homomorphisms beyond Markov Decision Processes, the authors proved that as long as an abstraction preserves the underlying optimal action-values, near-optimal performance guarantees can still be established even if the simplified model is non-Markovian.

Expanding on this, the authors in On Q-learning Convergence for Non-Markov Decision Processes showed that value-equivalent state aggregation allows standard Q-learning to converge to the true optimal action-value function, even when multiple hidden states are collapsed into a single observed state. Furthermore, Marcus Hutter demonstrated in Extreme State Aggregation Beyond MDPs that any complex, history-dependent environment can be compressed into a compact, stationary Markov Decision Process (MDP) as long as the optimal value function can be approximately represented within the reduced features. This explains why simple RL algorithms often succeed in complex, non-Markovian real-world environments: they do not need to model the full dynamics, only the underlying value structure.

From Exact to Approximate Abstractions

In real-world applications, finding states with exactly identical optimal values is rare. To make this framework practical, researchers relax the condition to approximate value abstraction, where states are merged if their values are within a specified threshold ($\epsilon$).

David Abel et al. established in Near Optimal Behavior via Approximate State Abstraction that approximate value-similarity abstractions provide a polynomial bound on policy performance loss. In his single-author work, David Abel unified various abstraction methodologies in A Theory of State Abstraction for Reinforcement Learning, showing that abstractions based on model dynamics or action preferences can be theoretically reduced to value-based abstractions.

However, compressing states also requires compressing the actions available within them. In Value Preserving State-Action Abstractions, the authors noted a crucial caveat: for an abstract representation to support a globally optimal policy, each abstract state must retain at least one high-level action or option that closely approximates the optimal action-value function. Without this representative action, the agent is fundamentally restricted from representing or reaching the optimal solution.

Value Abstraction in Practice

Value-based state abstraction is not just a theoretical tool; it underpins many practical algorithms across different domains:

By prioritizing the long-term utility of actions over raw sensory features or complex transition dynamics, value-based state abstraction provides a mathematically rigorous and highly scalable approach to simplifying the world for autonomous agents.

Key Foundational Work

Relevance determination in reinforcement learning (2005) — contributed 1 concept elements to this direction.
Exploiting Structure in Policy Construction (1995) — contributed 1 concept elements to this direction.
Solving POMDPs with Continuous or Large Discrete Observation Spaces (2005) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_value_based_state_abstraction_85520672,
  title = {value-based state abstraction},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/value-based-state-abstraction/rdr_85520672c57b4c7a81a5d43ba58468fd},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_value_based_state_abstraction_85520672_v1,
  title = {value-based state abstraction},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/value-based-state-abstraction/rdr_85520672c57b4c7a81a5d43ba58468fd/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake