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

arXiv: https://arxiv.org/abs/2210.15755 · HTML: https://mlsanity.com/paper/2210.15755/

## 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 (most cited first, 11 of 11)

- [Provably Efficient Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/1907.05388/) (2019)
- [Learning Near Optimal Policies with Low Inherent Bellman Error](https://mlsanity.com/paper/2003.00153/) (2020)
- [Is a Good Representation Sufficient for Sample Efficient Reinforcement Learning?](https://mlsanity.com/paper/1910.03016/) (2019)
- [Learning with Good Feature Representations in Bandits and in RL with a Generative Model](https://mlsanity.com/paper/1911.07676/) (2019)
- [Provably Efficient Reinforcement Learning for Discounted MDPs with Feature Mapping](https://mlsanity.com/paper/2006.13165/) (2020)
- [Exponential Lower Bounds for Planning in MDPs With Linearly-Realizable Optimal Action-Value Functions](https://mlsanity.com/paper/2010.01374/) (2020)
- [Reward-Free RL is No Harder Than Reward-Aware RL in Linear Markov Decision Processes](https://mlsanity.com/paper/2201.11206/) (2022)
- [An Exponential Lower Bound for Linearly-Realizable MDPs with Constant Suboptimality Gap](https://mlsanity.com/paper/2103.12690/) (2021)
- [Approximate Policy Iteration Schemes: A Comparison](https://mlsanity.com/paper/1405.2878/) (2014)
- [Efficient Local Planning with Linear Function Approximation](https://mlsanity.com/paper/2108.05533/) (2021)
- [Approximation Benefits of Policy Gradient Methods with Aggregated States](https://mlsanity.com/paper/2007.11684/) (2020)

## Built on by (most cited first, 8 of 8)

- [Sample Efficient Deep Reinforcement Learning via Local Planning](https://mlsanity.com/paper/2301.12579/) (2023)
- [Confident Natural Policy Gradient for Local Planning in qπ-realizable Constrained MDPs](https://mlsanity.com/paper/2406.18529/) (2024)
- [Exponential Hardness of Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/2302.12940/) (2023)
- [Regularization and Variance-Weighted Regression Achieves Minimax Optimality in Linear MDPs: Theory and Practice](https://mlsanity.com/paper/2305.13185/) (2023)
- [Offline RL via Feature-Occupancy Gradient Ascent](https://mlsanity.com/paper/2405.13755/) (2024)
- [RL in Markov Games with Independent Function Approximation: Improved Sample Complexity Bound under the Local Access Model](https://mlsanity.com/paper/2403.11544/) (2024)
- [Computational Hardness of Reinforcement Learning with Partial qπ-Realizability](https://mlsanity.com/paper/2510.21888/) (2025)
- [Frozen Policy Iteration: Computationally Efficient RL under Linear Qπ Realizability for Deterministic Dynamics](https://mlsanity.com/paper/2603.00716/) (2026)

## 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.