Linear MDPs & Linear Function Approximation Reading List

Curated by Mouhssine Rifaki | Stanford Electrical Engineering | Last updated August 2026

Linear structure makes reinforcement learning tractable without tabular assumptions. These papers develop optimistic least-squares methods, Bellman completeness, and minimax bounds that underpin provably efficient RL in large state spaces.

Linear MDPs & Linear Function Approximation: 10 key papers

1. Provably Efficient Reinforcement Learning with Linear Function Approximation
   Jin et al. arXiv 2019.
2. Learning Near Optimal Policies with Low Inherent Bellman Error
   Zanette et al. arXiv 2020.
3. Is a Good Representation Sufficient for Sample Efficient Reinforcement Learning?
   Du et al. arXiv 2019.
4. On the Optimality of Batch Policy Optimization Algorithms
   Xiao et al. arXiv 2021.
5. Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processes
   Zhou et al. arXiv 2020.
6. Optimism in Reinforcement Learning with Generalized Linear Function Approximation
   Wang et al. arXiv 2019.
7. Randomized Exploration for Reinforcement Learning with General Value Function Approximation
   Ishfaq et al. arXiv 2021.
8. Pessimistic Model-based Offline Reinforcement Learning under Partial Coverage
   Uehara and Sun. arXiv 2021.
9. Reward-Free RL is No Harder Than Reward-Aware RL in Linear Markov Decision Processes
   Wagenmaker et al. arXiv 2022.
10. Provably Efficient Exploration in Policy Optimization
    Cai et al. arXiv 2019.

Related reading lists

• Block MDPs & Latent State Discovery
• Policy Gradient Methods
• Off-Policy Evaluation & Offline Evaluation
• Sample Complexity in Reinforcement Learning
• Bayesian RL & Thompson Sampling
• Robust & Risk-Sensitive RL
• Model-Based Reinforcement Learning
• Optimal Control & LQR/LQG