In tabular reinforcement learning (RL), the complexity of finding an optimal policy scales with the number of states $S$ and actions $A$. When dealing with real-world environments where the state space is massive or continuous, tabular methods suffer from the "curse of dimensionality." To bypass this, practitioners use function approximation to generalize across states.
Among theoretical frameworks, the Linear Markov Decision Process (Linear MDP) stands out as a foundational model. It provides a mathematically rigorous way to prove that an agent can learn efficiently in an infinite state space, reducing the sample complexity from scaling with the number of states $S$ to scaling solely with the dimensionality of a known feature space $d$.
The Core Assumption: Structural Linearity
A Linear MDP assumes that the environment's underlying physics—specifically its transition dynamics and reward functions—can be compressed into a low-dimensional linear subspace.
Formally, given a known feature map $\phi(s, a) \in \mathbb{R}^d$ that assigns a $d$-dimensional vector to any state-action pair, an MDP is linear if there exists an unknown vector $\theta \in \mathbb{R}^d$ and an unknown vector-valued measure $\mu = (\mu_1, \dots, \mu_d)$ over the state space such that for any state $s$, action $a$, and next state $s'$:
$$r(s, a) = \langle \phi(s, a), \theta \rangle$$ $$P(s' \mid s, a) = \langle \phi(s, a), \mu(s') \rangle$$
This formulation treats the transition kernel as a low-rank operator. Instead of learning transitions between every individual pair of states, the agent only needs to learn the global parameters $\theta$ and $\mu$. As shown by Chi Jin et al., this structural assumption allows an agent to navigate large environments efficiently without requiring a simulator or generative model.
Why It Works: The Bellman Closure Property
The true elegance of the Linear MDP framework lies in how linearity propagates through the Bellman equations. In general function approximation, applying the Bellman backup operator to a linear function can yield a non-linear function, causing the representation to explode in complexity. Linear MDPs completely avoid this issue due to a clean algebraic closure property.
Consider an arbitrary next-state value function $V(s')$. When we compute the expected next value from a given state-action pair $(s,a)$, we integrate over the transition distribution:
$$\mathbb{E}[V(s') \mid s, a] = \int V(s') P(s' \mid s, a) \, ds'$$
Substituting the Linear MDP transition definition into this integral yields:
$$\mathbb{E}[V(s') \mid s, a] = \int V(s') \langle \phi(s, a), \mu(s') \rangle \, ds'$$
Because the inner product is linear, we can pull the feature vector $\phi(s, a)$ out of the integral:
$$\mathbb{E}[V(s') \mid s, a] = \left\langle \phi(s, a), \int V(s') \mu(s') \, ds' \right\rangle$$
Notice that the integral on the right no longer depends on $s$ or $a$; it evaluates to a constant vector $w \in \mathbb{R}^d$. Therefore, the expected next value is simply a linear combination of our features: $\langle \phi(s, a), w \rangle$.
Because both the reward $r(s,a)$ and the expected next value are linear in $\phi(s, a)$, the action-value function $Q(s, a) = r(s, a) + \gamma \mathbb{E}[V(s') \mid s, a]$ is guaranteed to be perfectly linear in $\phi(s, a)$ for any policy. This means the Bellman operator never escapes the linear subspace, ensuring zero inherent Bellman error.
Exploration via Optimism
With the guarantee that the optimal action-value function $Q^*$ is linear (i.e., $Q^*(s,a) = \langle \phi(s,a), w^* \rangle$), the learning problem reduces to estimating the weight vector $w^*$. This can be framed as a sequence of ridge regression problems. However, to collect the right data to solve this regression, the agent must explore.
Under the framework established by Chi Jin et al., algorithms like Least-Squares Value Iteration with UCB (LSVI-UCB) maintain an empirical covariance matrix of the features visited so far:
$$\Sigma = \sum_{t=1}^T \phi(s_t, a_t) \phi(s_t, a_t)^\top + \lambda I$$
The uncertainty of a given state-action pair is directly proportional to its quadratic form under the inverse covariance matrix: $\sqrt{\phi(s, a)^\top \Sigma^{-1} \phi(s, a)}$. By adding this uncertainty as an "optimistic bonus" to the reward during value iteration, the agent is driven to visit poorly explored directions in the feature space.
Because the feature space is $d$-dimensional, the agent can only be highly uncertain in at most $O(d)$ orthogonal directions, bounding the total regret or sample complexity as a function of $d$ rather than $S$.
Key Variations and Refinements
The literature expands on this core mechanism through several distinct structural variations:
- Linear Mixture MDPs: Instead of factoring the transition kernel as $\langle \phi(s,a), \mu(s') \rangle$, a parallel line of work models the transition kernel as a linear combination of known basis transition kernels, $P(s' \mid s, a) = \sum_{i=1}^d \theta_i P_i(s' \mid s, a)$. As explored by Dongruo Zhou et al., this model allows for direct model-based parameter estimation, enabling minimax-optimal regret bounds in infinite-horizon average-reward settings.
- Linear Realizability: A weaker condition than a full Linear MDP is assuming that only the optimal action-value function $Q^*$ is linear, while the underlying transitions can be arbitrarily non-linear. While standard online learning is notoriously difficult under pure linear realizability, Gen Li et al. demonstrated that sample-efficient learning becomes achievable if the agent is allowed a "limited revisiting" mechanism to re-examine past states.
- Sample Optimality via Variance Reduction: Early algorithms suffered from loose bounds due to coarse upper-bounds on value function variance. By incorporating variance-reduction techniques directly into parametric Q-learning, Lin F. Yang et al. proved that sample-optimal bounds matching the information-theoretic limits are achievable, cementing linear feature representations as a robust foundation for provably efficient reinforcement learning.