linear MDP theory

In a tabular MDP the sample cost grows with the raw number of states, which is hopeless when states number in the billions. Linear MDP theory rescues tractability by assuming hidden structure: the transition dynamics and rewards can be written as a low-dimensional linear function of known feature vectors over state-action pairs. If that holds, learning lives in a d-dimensional feature space rather than the giant state space.

Under the linear-MDP assumption both the transition kernel and reward are linear in a feature map φ(s,a), and crucially the action-value of every policy becomes linear in those same features. Algorithms like LSVI-UCB add an optimism bonus computed from a feature-covariance matrix and earn regret that scales with the feature dimension d and the horizon, with no dependence on the number of states at all. That is the payoff: structure converts an intractable count into a polynomial in d.

The model is restrictive — real features rarely make dynamics exactly linear — and the analysis is delicate because the bonus must control error across all states simultaneously. Linear MDPs are best read as the simplest setting where function approximation provably works, a stepping stone toward general theory.