Efficient Planning in Large MDPs with Weak Linear Function Approximation

Abstract

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.

arXiv comment12 pages and appendix (10 pages). Submitted to the 34th Conference on Neural Information Processing Systems (NeurIPS 2020), Vancouver, Canada

References in corpus (10)

• Provably Efficient Reinforcement Learning with Linear Function Approximation
• Contextual Decision Processes with Low Bellman Rank are PAC-Learnable
• Stochastic Primal-Dual Methods and Sample Complexity of Reinforcement Learning
• Provably Efficient $Q$-learning with Function Approximation via Distribution Shift Error Checking Oracle
• Linear Programming for Large-Scale Markov Decision Problems
• Is a Good Representation Sufficient for Sample Efficient Reinforcement Learning?
• Scalable Bilinear $\pi$ Learning Using State and Action Features
• Comments on the Du-Kakade-Wang-Yang Lower Bounds
• Large-Scale Markov Decision Problems via the Linear Programming Dual
• Faster saddle-point optimization for solving large-scale Markov decision processes

Cited by in corpus (6)

• Exponential Lower Bounds for Planning in MDPs With Linearly-Realizable Optimal Action-Value Functions
• An Exponential Lower Bound for Linearly-Realizable MDPs with Constant Suboptimality Gap
• Provable Model-based Nonlinear Bandit and Reinforcement Learning: Shelve Optimism, Embrace Virtual Curvature
• On Query-efficient Planning in MDPs under Linear Realizability of the Optimal State-value Function
• Efficient Local Planning with Linear Function Approximation
• Improved Variance-Aware Confidence Sets for Linear Bandits and Linear Mixture MDP