# Adaptive Approximate Policy Iteration

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 Feb 2020.

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

- [Near-optimal Policy Optimization Algorithms for Learning Adversarial Linear Mixture MDPs](https://mlsanity.com/paper/2102.08940/) (2021)
- [Average-reward model-free reinforcement learning: a systematic review and literature mapping](https://mlsanity.com/paper/2010.08920/) (2020)
- [Nearly Minimax Optimal Regret for Learning Infinite-horizon Average-reward MDPs with Linear Function Approximation](https://mlsanity.com/paper/2102.07301/) (2021)
- [Improved Regret Bound and Experience Replay in Regularized Policy Iteration](https://mlsanity.com/paper/2102.12611/) (2021)
- [Online Learning for Unknown Partially Observable MDPs](https://mlsanity.com/paper/2102.12661/) (2021)
- [Optimization Issues in KL-Constrained Approximate Policy Iteration](https://mlsanity.com/paper/2102.06234/) (2021)
- [Transportation-Inequalities, Lyapunov Stability and Sampling for Dynamical Systems on Continuous State Space](https://mlsanity.com/paper/2205.12448/) (2022)
- [Concentration Phenomenon for Random Dynamical Systems: An Operator Theoretic Approach](https://mlsanity.com/paper/2212.03670/) (2022)
- [Acceleration in Policy Optimization](https://mlsanity.com/paper/2306.10587/) (2023)

## Abstract (arXiv)

Model-free reinforcement learning algorithms combined with value function approximation have recently achieved impressive performance in a variety of application domains. However, the theoretical understanding of such algorithms is limited, and existing results are largely focused on episodic or discounted Markov decision processes (MDPs). In this work, we present adaptive approximate policy iteration (AAPI), a learning scheme which enjoys a tildeO(T2/3) regret bound for undiscounted, continuing learning in uniformly ergodic MDPs. This is an improvement over the best existing bound of tildeO(T3/4) for the average-reward case with function approximation. Our algorithm and analysis rely on online learning techniques, where value functions are treated as losses. The main technical novelty is the use of a data-dependent adaptive learning rate coupled with a so-called optimistic prediction of upcoming losses. In addition to theoretical guarantees, we demonstrate the advantages of our approach empirically on several environments.