# Optimization Issues in KL-Constrained Approximate Policy Iteration

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 26 references that are in the map.
- First posted on arXiv 11 Feb 2021.

## Builds on (most cited first, 18 of 18)

- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [Trust Region Policy Optimization](https://mlsanity.com/paper/1502.05477/) (2015)
- [Constrained Policy Optimization](https://mlsanity.com/paper/1705.10528/) (2017)
- [DeepMind Control Suite](https://mlsanity.com/paper/1801.00690/) (2018)
- [Maximum a Posteriori Policy Optimisation](https://mlsanity.com/paper/1806.06920/) (2018)
- [On the Global Convergence Rates of Softmax Policy Gradient Methods](https://mlsanity.com/paper/2005.06392/) (2020)
- [Provably Efficient Exploration in Policy Optimization](https://mlsanity.com/paper/1912.05830/) (2019)
- [A unified view of entropy-regularized Markov decision processes](https://mlsanity.com/paper/1705.07798/) (2017)
- [On the Theory of Policy Gradient Methods: Optimality, Approximation, and Distribution Shift](https://mlsanity.com/paper/1908.00261/) (2019)
- [Understanding the impact of entropy on policy optimization](https://mlsanity.com/paper/1811.11214/) (2018)
- [Adaptive Trust Region Policy Optimization: Global Convergence and Faster Rates for Regularized MDPs](https://mlsanity.com/paper/1909.02769/) (2019)
- [Mirror Descent Policy Optimization](https://mlsanity.com/paper/2005.09814/) (2020)
- [V-MPO: On-Policy Maximum a Posteriori Policy Optimization for Discrete and Continuous Control](https://mlsanity.com/paper/1909.12238/) (2019)
- [Reward Augmented Maximum Likelihood for Neural Structured Prediction](https://mlsanity.com/paper/1609.00150/) (2016)
- [Optimistic Policy Optimization with Bandit Feedback](https://mlsanity.com/paper/2002.08243/) (2020)
- [Leverage the Average: an Analysis of KL Regularization in RL](https://mlsanity.com/paper/2003.14089/) (2020)
- [Momentum in Reinforcement Learning](https://mlsanity.com/paper/1910.09322/) (2019)
- [Adaptive Approximate Policy Iteration](https://mlsanity.com/paper/2002.03069/) (2020)

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

- [A general class of surrogate functions for stable and efficient reinforcement learning](https://mlsanity.com/paper/2108.05828/) (2021)
- [Understanding the Effect of Stochasticity in Policy Optimization](https://mlsanity.com/paper/2110.15572/) (2021)
- [Learning to Constrain Policy Optimization with Virtual Trust Region](https://mlsanity.com/paper/2204.09315/) (2022)
- [Examining Policy Entropy of Reinforcement Learning Agents for Personalization Tasks](https://mlsanity.com/paper/2211.11869/) (2022)
- [Fast Convergence of Softmax Policy Mirror Ascent](https://mlsanity.com/paper/2411.12042/) (2024)
- [Simulated Contextual Bandits for Personalization Tasks from Recommendation Datasets](https://mlsanity.com/paper/2210.10631/) (2022)
- [Revisiting Estimation Bias in Policy Gradients for Deep Reinforcement Learning](https://mlsanity.com/paper/2301.08442/) (2023)
- [Aligning Frozen LLMs by Reinforcement Learning: An Iterative Reweight-then-Optimize Approach](https://mlsanity.com/paper/2506.17828/) (2025)
- [Beyond I-Con: Exploring New Dimension of Distance Measures in Representation Learning](https://mlsanity.com/paper/2509.04734/) (2025)
- [Non-Stationarity Breaks Permutation Surrogates in Multi-Agent Reinforcement Learning: Diagnosis and Remedies](https://mlsanity.com/paper/2604.23716/) (2026)

## Abstract (arXiv)

Many reinforcement learning algorithms can be seen as versions of approximate policy iteration (API). While standard API often performs poorly, it has been shown that learning can be stabilized by regularizing each policy update by the KL-divergence to the previous policy. Popular practical algorithms such as TRPO, MPO, and VMPO replace regularization by a constraint on KL-divergence of consecutive policies, arguing that this is easier to implement and tune. In this work, we study this implementation choice in more detail. We compare the use of KL divergence as a constraint vs. as a regularizer, and point out several optimization issues with the widely-used constrained approach. We show that the constrained algorithm is not guaranteed to converge even on simple problem instances where the constrained problem can be solved exactly, and in fact incurs linear expected regret. With approximate implementation using softmax policies, we show that regularization can improve the optimization landscape of the original objective. We demonstrate these issues empirically on several bandit and RL environments.