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:
- Data-Driven Clustering: The SAmQ framework, introduced by Sinong Geng et al. in A Data-Driven State Aggregation Approach for Dynamic Discrete Choice Models, uses clustering on estimated Q-functions to shrink the state space, providing a theoretical bound on the error introduced during reduction.
- Contrastive Representation Learning: In deep RL, the RCRL method developed by Guoqing Liu et al. in Return-Based Contrastive Representation Learning for Reinforcement Learning uses the return distribution under a policy as a self-supervised signal to group state-action pairs, ignoring irrelevant environmental details to maximize sample efficiency.
- Visual Control Policies: The RLVC framework by Sébastien Jodogne et al. in Closed-Loop Learning of Visual Control Policies automatically aggregates high-dimensional visual inputs into discrete classes based on whether they require the same optimal action, preventing overfitting and improving generalization.
- Multiagent Planning: When modeling other agents, the space of possible behaviors grows exponentially. The authors in Approximating Value Equivalence in Interactive Dynamic Influence Diagrams Using Behavioral Coverage showed that grouping candidate models based on value equivalence (the expected utility they yield for the primary agent) achieves a much more aggressive and effective reduction than grouping them by behavioral identity alone.
- Explainable AI: Value functions can also make black-box policies interpretable. In Generation of Policy-Level Explanations for Reinforcement Learning, the authors utilized the agent's internal value function as a proxy for behavior, clustering disparate states into functionally equivalent strategic units to generate global policy visualizations.
- Factored Planning and Games: Algorithms like SPUDD, developed by Jesse Hoey et al. in SPUDD: Stochastic Planning using Decision Diagrams, perform value updates directly on Algebraic Decision Diagrams, enabling implicit state aggregation without explicitly enumerating the state space. In imperfect-information games like Poker, the authors in Don't Predict Counterfactual Values, Predict Expected Values Instead demonstrated that applying state abstraction or bucketing to expected values rather than counterfactual values reduces encoding errors because the underlying value distribution is more stable.
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.