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

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 $\tilde{\mathcal{O}}\big(T^{1 - d{\text{eff.}}^{-1}}\big)$, where $d{\text{eff.}} = d^\Phiz+2$ for model-free algorithm $\textit{PZRL-MF}$ and $d{\text{eff.}} = 2d\mathcal{S} + d^\Phiz + 3$ for model-based algorithm $\textit{PZRL-MB}$. Here, $d\mathcal{S}$ is the dimension of the state space, and $d^\Phiz$ is the zooming dimension given a set of policies $\Phi$. $d^\Phiz$ 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 $d{\text{eff.}}$ scales as the dimension of this space under mild technical conditions; and also obtain $d{\text{eff.}} = 0$, or equivalently $\tilde{\mathcal{O}}(\sqrt{T})$ regret for $\textit{PZRL-MF}$, under a curvature condition on the average reward function that is commonly used in the multi-armed bandit (MAB) literature.