mlsanityData to 7 Oct 2026

On Query-efficient Planning in MDPs under Linear Realizability of the Optimal State-value Function

arXiv 2102.02049 ↗First posted 3 Feb 2021cs.LG cs.AI stat.MLcited by 17

Not on the map. Why?

Abstract (arXiv)

We consider local planning in fixed-horizon MDPs with a generative model under the assumption that the optimal value function lies close to the span of a feature map. The generative model provides a local access to the MDP: The planner can ask for random transitions from previously returned states and arbitrary actions, and features are only accessible for states that are encountered in this process. As opposed to previous work (e.g. Lattimore et al. (2020)) where linear realizability of all policies was assumed, we consider the significantly relaxed assumption of a single linearly realizable (deterministic) policy. A recent lower bound by Weisz et al. (2020) established that the related problem when the action-value function of the optimal policy is linearly realizable requires an exponential number of queries, either in H (the horizon of the MDP) or d (the dimension of the feature mapping). Their construction crucially relies on having an exponentially large action set. In contrast, in this work, we establish that poly(H,d) planning is possible with state value function realizability whenever the action set has a constant size. In particular, we present the TensorPlan algorithm which uses poly((dH/δ)A) simulator queries to find a δ-optimal policy relative to any deterministic policy for which the value function is linearly realizable with some bounded parameter. This is the first algorithm to give a polynomial query complexity guarantee using only linear-realizability of a single competing value function. Whether the computation cost is similarly bounded remains an open question. We extend the upper bound to the near-realizable case and to the infinite-horizon discounted setup. We also present a lower bound in the infinite-horizon episodic setting: Planners that achieve constant suboptimality need exponentially many queries, either in d or the number of actions.

Key facts. Cited by 17 papers in the map (data through 7 Oct 2026). Builds on 16 of its 28 references that are in the map. First posted on arXiv 3 Feb 2021.

Builds on

16 of 28 references.

References · 16

  1. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 514
  2. 2016Contextual Decision Processes with Low Bellman Rank are PAC-Learnablecited by 290
  3. 2013Learning to Optimize Via Posterior Samplingcited by 253
  4. 2020Model-Based Reinforcement Learning with Value-Targeted Regressioncited by 233
  5. 2019Is a Good Representation Sufficient for Sample Efficient Reinforcement Learning?cited by 140
  6. 2020What are the Statistical Limits of Offline RL with Linear Function Approximation?cited by 135
  7. 2019Learning with Good Feature Representations in Bandits and in RL with a Generative Modelcited by 124
  8. 2019Optimism in Reinforcement Learning with Generalized Linear Function Approximationcited by 111
  9. 2019Sample Complexity of Reinforcement Learning using Linearly Combined Model Ensemblescited by 100
  10. 2018On Oracle-Efficient PAC RL with Rich Observationscited by 71
  11. 2020Exponential Lower Bounds for Planning in MDPs With Linearly-Realizable Optimal Action-Value Functionscited by 71
  12. 2020Exponential Lower Bounds for Batch Reinforcement Learning: Batch RL can be Exponentially Harder than Online RLcited by 55
4 more
  1. 2020Reinforcement Learning with General Value Function Approximation: Provably Efficient Approach via Bounded Eluder Dimensioncited by 36
  2. 2020Efficient Planning in Large MDPs with Weak Linear Function Approximationcited by 17
  3. 2019Comments on the Du-Kakade-Wang-Yang Lower Boundscited by 16
  4. 2017A Linearly Relaxed Approximate Linear Program for Markov Decision Processescited by 9

Built on by

Cited by year

Citing papers per year: 2021: 5; 2022: 5; 2023: 3; 2024: 4.

17 papers.

Sort:

By area:

  1. 2022Learning in Observable POMDPs, without Computationally Intractable Oraclescited by 30
  2. 2021Sample-Efficient Reinforcement Learning Is Feasible for Linearly Realizable MDPs with Limited Revisitingcited by 27
  3. 2022On the Statistical Efficiency of Reward-Free Exploration in Non-Linear RLcited by 27
  4. 2021Efficient Local Planning with Linear Function Approximationcited by 21
  5. 2024Overcoming the Sim-to-Real Gap: Leveraging Simulation to Learn to Explore for Real-World RLcited by 17
  6. 2021A Boosting Approach to Reinforcement Learningcited by 12
  7. 2023Hardness of Independent Learning and Sparse Equilibrium Computation in Markov Gamescited by 9
  8. 2021TensorPlan and the Few Actions Lower Bound for Planning in MDPs under Linear Realizability of Optimal Value Functionscited by 7
  9. 2022A Few Expert Queries Suffices for Sample-Efficient RL with Resets and Linear Value Approximationcited by 7
  10. 2021Sample Efficient Reinforcement Learning In Continuous State Spaces: A Perspective Beyond Linearitycited by 6
  11. 2024Hybrid Reinforcement Learning from Offline Observation Alonecited by 5
  12. 2023Exponential Hardness of Reinforcement Learning with Linear Function Approximationcited by 4
5 more
  1. 2024Confident Natural Policy Gradient for Local Planning in qπ-realizable Constrained MDPscited by 4
  2. 2022Computational-Statistical Gaps in Reinforcement Learningcited by 3
  3. 2023Sample-Efficiency in Multi-Batch Reinforcement Learning: The Need for Dimension-Dependent Adaptivitycited by 2
  4. 2022Linear Reinforcement Learning with Ball Structure Action Spacecited by 1
  5. 2024RL in Markov Games with Independent Function Approximation: Improved Sample Complexity Bound under the Local Access Modelcited by 0