mlsanityData to 7 Oct 2026

Efficient Planning in Large MDPs with Weak Linear Function Approximation

arXiv 2007.06184 ↗First posted 13 Jul 2020cs.LG stat.MLcited by 17

Not on the map. Why?

Abstract (arXiv)

Large-scale Markov decision processes (MDPs) require planning algorithms with runtime independent of the number of states of the MDP. We consider the planning problem in MDPs using linear value function approximation with only weak requirements: low approximation error for the optimal value function, and a small set of "core" states whose features span those of other states. In particular, we make no assumptions about the representability of policies or value functions of non-optimal policies. Our algorithm produces almost-optimal actions for any state using a generative oracle (simulator) for the MDP, while its computation time scales polynomially with the number of features, core states, and actions and the effective horizon.

Key facts. Cited by 17 papers in the map (data through 7 Oct 2026). First posted on arXiv 13 Jul 2020.

Builds on

No reference list yet.

Built on by

Cited by year

Citing papers per year: 2021: 10; 2022: 6; 2023: 1.

17 papers.

Sort:

By area:

  1. 2021Improved Variance-Aware Confidence Sets for Linear Bandits and Linear Mixture MDPcited by 45
  2. 2021An Exponential Lower Bound for Linearly-Realizable MDPs with Constant Suboptimality Gapcited by 40
  3. 2021Provable Model-based Nonlinear Bandit and Reinforcement Learning: Shelve Optimism, Embrace Virtual Curvaturecited by 32
  4. 2021Sample-Efficient Reinforcement Learning Is Feasible for Linearly Realizable MDPs with Limited Revisitingcited by 27
  5. 2022Proximal Point Imitation Learningcited by 25
  6. 2021Efficient Local Planning with Linear Function Approximationcited by 21
  7. 2021Sample-Efficient Reinforcement Learning for Linearly-Parameterized MDPs with a Generative Modelcited by 18
  8. 2021On Query-efficient Planning in MDPs under Linear Realizability of the Optimal State-value Functioncited by 17
  9. 2023Distributionally Robust Model-based Reinforcement Learning with Large State Spacescited by 17
  10. 2022Bilinear Exponential Family of MDPs: Frequentist Regret Bound with Tractable Exploration and Planningcited by 12
  11. 2021Efficient Performance Bounds for Primal-Dual Reinforcement Learning from Demonstrationscited by 9
  12. 2022Efficient Global Planning in Large MDPs via Stochastic Primal-Dual Optimizationcited by 8
5 more
  1. 2022A Few Expert Queries Suffices for Sample-Efficient RL with Resets and Linear Value Approximationcited by 7
  2. 2022Near-optimal Policy Identification in Active Reinforcement Learningcited by 7
  3. 2021Exploiting Action Impact Regularity and Exogenous State Variables for Offline Reinforcement Learningcited by 2
  4. 2022Linear Reinforcement Learning with Ball Structure Action Spacecited by 1
  5. 2021Planning with Expectation Models for Controlcited by 0