Abstract
Traditional reinforcement learning (RL) theory is built upon the Markov Decision Process (MDP) assumption, which posits that the current state contains all necessary information for future prediction. However, real-world environments are frequently non-Markovian and history-dependent. This paper introduces the Feature MDP ($\Phi$MDP) framework, proving that complex environments can be compressed into small, stationary surrogate MDPs. We demonstrate that as long as the optimal value function is approximately representable in a reduced state space, an agent can find near-optimal policies regardless of the environment's underlying complexity.
Introduction: The Markovian Dilemma
Most RL algorithms assume the environment follows a Markovian transition structure. In practice, observations are often partial, and the "true state" may depend on an extensive history of past events. To bridge this gap, researchers employ state aggregation, grouping raw histories into a smaller set of aggregated states.
Historically, state aggregation required the resulting process to maintain Markovian properties (bisimulation). This paper argues that such a requirement is overly restrictive. Instead, it asks whether we can aggregate states even when the resulting process is non-Markovian, provided we can still identify an optimal policy.
The $\Phi$MDP Framework
The paper proposes a framework centered on the representability of the value function rather than the structure of the environment. The core components include:
- Feature Map ($\phi$): A function mapping complex histories into a discrete set of states.
- Dispersion Probability ($B$): A stochastic inverse of the feature map that defines a probability distribution over histories given an aggregated state.
- Surrogate MDP ($p$): A stationary, finite-state MDP constructed using $B$-averages of the environment's actual transitions. This surrogate acts as a manageable stand-in for the complex reality.
- $\phi$-uniformity: The assumption that the optimal $Q$-value function remains approximately constant across all histories mapped to the same aggregated state.
Theoretical Foundations and Error Bounds
The technical heart of the paper lies in a series of theorems establishing that the surrogate MDP $p$ effectively captures the dynamics necessary for optimal decision-making.
Theorems 5 through 9 provide formal error bounds, showing that if the $Q$-value function is $\epsilon$-uniform, the policies derived from the surrogate MDP remain close to the true optimal values in the original environment. Furthermore, Theorem 12 proves that this surrogate MDP can be learned from experience samples using standard frequency estimation, provided the agent explores sufficiently.
Extreme Aggregation and Universal Bounds
A landmark result of this work is the "Universal Upper Bound" presented in Theorem 11 (Extreme $\phi$). It proves that for any RL problem, there exists a state-space size $|S|$ sufficient to reach an $\epsilon$-optimal policy. This size is approximately $O((1/\epsilon)^{|A|})$, where $|A|$ is the number of actions.
Crucially, this bound is independent of the environment's original complexity. While the bound scales exponentially with the number of actions, it provides a theoretical justification for why algorithms like Q-learning—designed for simple MDPs—often succeed in highly complex, non-Markovian domains like robotics. They are effectively solving the surrogate MDP defined by the features provided to them.
Limitations and Future Directions
While the theoretical results are robust, several practical challenges remain:
- Feature Discovery: The "Extreme Aggregation" proof assumes the optimal $Q$-values are known to construct $\phi$. In practice, an agent must search for a suitable feature map while simultaneously learning the values.
- Action Scalability: The exponential dependence on the number of actions limits the theory's direct application to continuous action spaces.
- Discount Sensitivity: The required state space grows significantly as the discount factor $\gamma$ approaches 1, reflecting the difficulty of long-term planning.
Future work aims to extend these results to average-reward settings and develop algorithms for "Feature Reinforcement Learning" that can autonomously learn the optimal aggregation map $\phi$.
Summary updated