mlsanityData to 14 Oct 2026

Confident Approximate Policy Iteration for Efficient Local Planning in qπ-realizable MDPs

arXiv 2210.15755 ↗First posted 27 Oct 2022cs.LG cs.AI stat.MLcited by 8

Not on the map. Why?

Abstract (arXiv)

We consider approximate dynamic programming in γ-discounted Markov decision processes and apply it to approximate planning with linear value-function approximation. Our first contribution is a new variant of Approximate Policy Iteration (API), called Confident Approximate Policy Iteration (CAPI), which computes a deterministic stationary policy with an optimal error bound scaling linearly with the product of the effective horizon H and the worst-case approximation error ε of the action-value functions of stationary policies. This improvement over API (whose error scales with H2) comes at the price of an H-fold increase in memory cost. Unlike Scherrer and Lesner [2012], who recommended computing a non-stationary policy to achieve a similar improvement (with the same memory overhead), we are able to stick to stationary policies. This allows for our second contribution, the application of CAPI to planning with local access to a simulator and d-dimensional linear function approximation. As such, we design a planning algorithm that applies CAPI to obtain a sequence of policies with successively refined accuracies on a dynamically evolving set of states. The algorithm outputs an tilde O(√dHε)-optimal policy after issuing tilde O(dH4/ε2) queries to the simulator, simultaneously achieving the optimal accuracy bound and the best known query complexity bound, while earlier algorithms in the literature achieve only one of them. This query complexity is shown to be tight in all parameters except H. These improvements come at the expense of a mild (polynomial) increase in memory and computational costs of both the algorithm and its output policy.

Key facts. Cited by 8 papers in the map (data through 14 Oct 2026). Builds on 11 of its 28 references that are in the map. First posted on arXiv 27 Oct 2022.

Builds on

11 of 28 references.

References · 11

  1. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 520
  2. 2020Learning Near Optimal Policies with Low Inherent Bellman Errorcited by 181
  3. 2019Is a Good Representation Sufficient for Sample Efficient Reinforcement Learning?cited by 140
  4. 2019Learning with Good Feature Representations in Bandits and in RL with a Generative Modelcited by 127
  5. 2020Provably Efficient Reinforcement Learning for Discounted MDPs with Feature Mappingcited by 102
  6. 2020Exponential Lower Bounds for Planning in MDPs With Linearly-Realizable Optimal Action-Value Functionscited by 71
  7. 2022Reward-Free RL is No Harder Than Reward-Aware RL in Linear Markov Decision Processescited by 49
  8. 2021An Exponential Lower Bound for Linearly-Realizable MDPs with Constant Suboptimality Gapcited by 40
  9. 2014Approximate Policy Iteration Schemes: A Comparisoncited by 39
  10. 2021Efficient Local Planning with Linear Function Approximationcited by 23
  11. 2020Approximation Benefits of Policy Gradient Methods with Aggregated Statescited by 5

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2023: 3; 2024: 3; 2025: 1; 2026: 1.

8 papers.

  1. 2023Sample Efficient Deep Reinforcement Learning via Local Planningcited by 10
  2. 2024Confident Natural Policy Gradient for Local Planning in qπ-realizable Constrained MDPscited by 5
  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. 2024Offline RL via Feature-Occupancy Gradient Ascentcited by 2
  6. 2024RL in Markov Games with Independent Function Approximation: Improved Sample Complexity Bound under the Local Access Modelcited by 0
  7. 2025Computational Hardness of Reinforcement Learning with Partial qπ-Realizabilitycited by 0
  8. 2026Frozen Policy Iteration: Computationally Efficient RL under Linear Qπ Realizability for Deterministic Dynamicscited by 0