# Policy Zooming: Adaptive Discretization-based Infinite-Horizon Average-Reward Reinforcement Learning

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods.
- Builds on 27 of its 53 references that are in the map.
- First posted on arXiv 29 May 2024.

## Placed in

- Deep reinforcement learning methods / [RL theory and sample complexity](https://mlsanity.com/deeprl/rl-theory-and-sample-complexity/)

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

- [R3M: A Universal Visual Representation for Robot Manipulation](https://mlsanity.com/paper/2203.12601/) (2022)
- [Provably Efficient Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/1907.05388/) (2019)
- [RMA: Rapid Motor Adaptation for Legged Robots](https://mlsanity.com/paper/2107.04034/) (2021)
- [Introduction to Multi-Armed Bandits](https://mlsanity.com/paper/1904.07272/) (2019)
- [Model-Based Reinforcement Learning with Value-Targeted Regression](https://mlsanity.com/paper/2006.01107/) (2020)
- [Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithms](https://mlsanity.com/paper/2102.00815/) (2021)
- [Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processes](https://mlsanity.com/paper/2012.08507/) (2020)
- [Model-based Reinforcement Learning and the Eluder Dimension](https://mlsanity.com/paper/1406.1853/) (2014)
- [Non-Asymptotic Gap-Dependent Regret Bounds for Tabular MDPs](https://mlsanity.com/paper/1905.03814/) (2019)
- [Information Theoretic Regret Bounds for Online Nonlinear Control](https://mlsanity.com/paper/2006.12466/) (2020)
- [Learning Unknown Markov Decision Processes: A Thompson Sampling Approach](https://mlsanity.com/paper/1709.04570/) (2017)
- [Bandits and Experts in Metric Spaces](https://mlsanity.com/paper/1312.1277/) (2013)
- [Learning Infinite-horizon Average-reward MDPs with Linear Function Approximation](https://mlsanity.com/paper/2007.11849/) (2020)
- [VOQL: Towards Optimal Regret in Model-free RL with Nonlinear Function Approximation](https://mlsanity.com/paper/2212.06069/) (2022)
- [On Online Learning in Kernelized Markov Decision Processes](https://mlsanity.com/paper/1911.01871/) (2019)
- [Kernel-Based Reinforcement Learning: A Finite-Time Analysis](https://mlsanity.com/paper/2004.05599/) (2020)
- [Efficient Model-free Reinforcement Learning in Metric Spaces](https://mlsanity.com/paper/1905.00475/) (2019)
- [Online Regret Bounds for Undiscounted Continuous Reinforcement Learning](https://mlsanity.com/paper/1302.2550/) (2013)
- [Adaptive Discretization for Episodic Reinforcement Learning in Metric Spaces](https://mlsanity.com/paper/1910.08151/) (2019)
- [Near-optimal Optimistic Reinforcement Learning using Empirical Bernstein Inequalities](https://mlsanity.com/paper/1905.12425/) (2019)
- [Optimal Sample Complexity for Average Reward Markov Decision Processes](https://mlsanity.com/paper/2310.08833/) (2023)
- [Reward Biased Maximum Likelihood Estimation for Reinforcement Learning](https://mlsanity.com/paper/2011.07738/) (2020)
- [No-Regret Reinforcement Learning in Smooth MDPs](https://mlsanity.com/paper/2402.03792/) (2024)
- [Sample-efficient Learning of Infinite-horizon Average-reward MDPs with General Function Approximation](https://mlsanity.com/paper/2404.12648/) (2024)
- [Projection by Convolution: Optimal Sample Complexity for Reinforcement Learning in Continuous-Space MDPs](https://mlsanity.com/paper/2405.06363/) (2024)
- [Provably adaptive reinforcement learning in metric spaces](https://mlsanity.com/paper/2006.10875/) (2020)
- [Optimal Scheduling Policies for Remote Estimation of Autoregressive Markov Processes over Time-Correlated Fading Channel](https://mlsanity.com/paper/2303.16285/) (2023)

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

- [Provably Adaptive Average Reward Reinforcement Learning for Metric Spaces](https://mlsanity.com/paper/2410.19919/) (2024)

## Abstract (arXiv)

We study the infinite-horizon average-reward reinforcement learning (RL) for continuous space Lipschitz MDPs in which an agent can play policies from a given set Phi. The proposed algorithms efficiently explore the policy space by ''zooming'' into the ''promising regions'' of Phi, thereby achieving adaptivity gains in the performance. We upper bound their regret as tildeObig(T^1 - deff.-1big), where deff. = d^Phiz+2 for model-free algoritahm textitPZRL-MF and deff. = 2dS + d^Phiz + 3 for model-based algorithm textitPZRL-MB. Here, dS is the dimension of the state space, and d^Phiz is the zooming dimension given a set of policies Phi. d^Phiz is an alternative measure of the complexity of the problem, and it depends on the underlying MDP as well as on Phi. Hence, the proposed algorithms exhibit low regret in case the problem instance is benign and/or the agent competes against a low-complexity Phi (that has a small d^Phiz). When specialized to the case of finite-dimensional policy space, we obtain that deff. scales as the dimension of this space under mild technical conditions; and also obtain deff. = 2, or equivalently tildeO(√T) regret for textitPZRL-MF, under a curvature condition on the average reward function that is commonly used in the multi-armed bandit (MAB) literature.