# Approximation Benefits of Policy Gradient Methods with Aggregated States

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 22 Jul 2020.

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

- [On the Sample Complexity and Metastability of Heavy-tailed Policy Search in Continuous Control](https://mlsanity.com/paper/2106.08414/) (2021)
- [Confident Approximate Policy Iteration for Efficient Local Planning in qπ-realizable MDPs](https://mlsanity.com/paper/2210.15755/) (2022)
- [Optimizing Audio Recommendations for the Long-Term: A Reinforcement Learning Perspective](https://mlsanity.com/paper/2302.03561/) (2023)
- [Multi-Timescale Ensemble Q-learning for Markov Decision Process Policy Optimization](https://mlsanity.com/paper/2402.05476/) (2024)
- [Functional Acceleration for Policy Mirror Descent](https://mlsanity.com/paper/2407.16602/) (2024)

## Abstract (arXiv)

Folklore suggests that policy gradient can be more robust to misspecification than its relative, approximate policy iteration. This paper studies the case of state-aggregated representations, where the state space is partitioned and either the policy or value function approximation is held constant over partitions. This paper shows a policy gradient method converges to a policy whose regret per-period is bounded by ε, the largest difference between two elements of the state-action value function belonging to a common partition. With the same representation, both approximate policy iteration and approximate value iteration can produce policies whose per-period regret scales as ε/(1-γ), where γ is a discount factor. Faced with inherent approximation error, methods that locally optimize the true decision-objective can be far more robust.