mlsanityData to 7 Oct 2026

Efficient Local Planning with Linear Function Approximation

arXiv 2108.05533 ↗First posted 12 Aug 2021cs.LG math.OC stat.MLcited by 21

Not on the map. Why?

Abstract (arXiv)

We study query and computationally efficient planning algorithms with linear function approximation and a simulator. We assume that the agent only has local access to the simulator, meaning that the agent can only query the simulator at states that have been visited before. This setting is more practical than many prior works on reinforcement learning with a generative model. We propose two algorithms, named confident Monte Carlo least square policy iteration (Confident MC-LSPI) and confident Monte Carlo Politex (Confident MC-Politex) for this setting. Under the assumption that the Q-functions of all policies are linear in known features of the state-action pairs, we show that our algorithms have polynomial query and computational costs in the dimension of the features, the effective planning horizon, and the targeted sub-optimality, while these costs are independent of the size of the state space. One technical contribution of our work is the introduction of a novel proof technique that makes use of a virtual policy iteration algorithm. We use this method to leverage existing results on ℓ_∞-bounded approximate policy iteration to show that our algorithm can learn the optimal policy for the given initial state even only with local access to the simulator. We believe that this technique can be extended to broader settings beyond this work.

Key facts. Cited by 21 papers in the map (data through 7 Oct 2026). Builds on 26 of its 53 references that are in the map. First posted on arXiv 12 Aug 2021.

Builds on

26 of 53 references.

References · 26

  1. 2016Contextual Decision Processes with Low Bellman Rank are PAC-Learnablecited by 290
  2. 2020Model-Based Reinforcement Learning with Value-Targeted Regressioncited by 233
  3. 2021Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithmscited by 222
  4. 2019Go-Explore: a New Approach for Hard-Exploration Problemscited by 207
  5. 2019Provably Efficient Exploration in Policy Optimizationcited by 203
  6. 2019Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Boundcited by 199
  7. 2020Learning Near Optimal Policies with Low Inherent Bellman Errorcited by 180
  8. 2021Bilinear Classes: A Structural Framework for Provable Generalization in RLcited by 176
  9. 2019Is a Good Representation Sufficient for Sample Efficient Reinforcement Learning?cited by 140
  10. 2019Model-Based Reinforcement Learning with a Generative Model is Minimax Optimalcited by 124
  11. 2019Learning with Good Feature Representations in Bandits and in RL with a Generative Modelcited by 124
  12. 2021Provably Efficient Reinforcement Learning with Linear Function Approximation Under Adaptivity Constraintscited by 124
14 more
  1. 2019Optimism in Reinforcement Learning with Generalized Linear Function Approximationcited by 111
  2. 2020Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Modelcited by 108
  3. 2020Provably Efficient Reinforcement Learning for Discounted MDPs with Feature Mappingcited by 102
  4. 2020PC-PG: Policy Cover Directed Exploration for Provable Policy Gradient Learningcited by 91
  5. 2020Exponential Lower Bounds for Planning in MDPs With Linearly-Realizable Optimal Action-Value Functionscited by 71
  6. 2021Cautiously Optimistic Policy Optimization and Exploration with Linear Function Approximationcited by 53
  7. 2020Learning Infinite-horizon Average-reward MDPs with Linear Function Approximationcited by 48
  8. 2021An Exponential Lower Bound for Linearly-Realizable MDPs with Constant Suboptimality Gapcited by 40
  9. 2021Sample-Efficient Reinforcement Learning Is Feasible for Linearly Realizable MDPs with Limited Revisitingcited by 27
  10. 2020Agnostic Q-learning with Function Approximation in Deterministic Systems: Tight Bounds on Approximation Error and Sample Complexitycited by 19
  11. 2021Improved Regret Bound and Experience Replay in Regularized Policy Iterationcited by 18
  12. 2020Efficient Planning in Large MDPs with Weak Linear Function Approximationcited by 17
  13. 2021On Query-efficient Planning in MDPs under Linear Realizability of the Optimal State-value Functioncited by 17
  14. 2019Comments on the Du-Kakade-Wang-Yang Lower Boundscited by 16

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 1; 2022: 5; 2023: 7; 2024: 3; 2025: 2; 2026: 3.

21 papers.

Sort:

By area:

  1. 2024Dataset Reset Policy Optimization for RLHFcited by 41
  2. 2023Distributionally Robust Model-based Reinforcement Learning with Large State Spacescited by 17
  3. 2024Overcoming the Sim-to-Real Gap: Leveraging Simulation to Learn to Explore for Real-World RLcited by 17
  4. 2026Reuse your FLOPs: Scaling RL on Hard Problems by Conditioning on Very Off-Policy Prefixescited by 16
  5. 2022Minimax-Optimal Multi-Agent RL in Markov Games With a Generative Modelcited by 15
  6. 2022Provably Efficient Causal Model-Based Reinforcement Learning for Systematic Generalizationcited by 12
  7. 2023Sample Efficient Deep Reinforcement Learning via Local Planningcited by 9
  8. 2023Hardness of Independent Learning and Sparse Equilibrium Computation in Markov Gamescited by 9
  9. 2023Can Agents Run Relay Race with Strangers? Generalization of RL to Out-of-Distribution Trajectoriescited by 9
  10. 2022Efficient Global Planning in Large MDPs via Stochastic Primal-Dual Optimizationcited by 8
  11. 2022Confident Approximate Policy Iteration for Efficient Local Planning in qπ-realizable MDPscited by 8
  12. 2022Near-optimal Policy Identification in Active Reinforcement Learningcited by 7
9 more
  1. 2021Improved Algorithms for Misspecified Linear Markov Decision Processescited by 6
  2. 2023Efficient Planning in Combinatorial Action Spaces with Applications to Cooperative Multi-Agent Reinforcement Learningcited by 6
  3. 2023Exponential Hardness of Reinforcement Learning with Linear Function Approximationcited by 4
  4. 2023Regularization and Variance-Weighted Regression Achieves Minimax Optimality in Linear MDPs: Theory and Practicecited by 4
  5. 2024Confident Natural Policy Gradient for Local Planning in qπ-realizable Constrained MDPscited by 4
  6. 2026Near-Optimal Sample Complexity for Online Constrained MDPscited by 1
  7. 2025In-Context Compositional Q-Learning for Offline Reinforcement Learningcited by 0
  8. 2025Computational Hardness of Reinforcement Learning with Partial qπ-Realizabilitycited by 0
  9. 2026Frozen Policy Iteration: Computationally Efficient RL under Linear Qπ Realizability for Deterministic Dynamicscited by 0