Horizon-Free Reinforcement Learning in Polynomial Time: The Power of Stationary Policies
Abstract
This paper gives the first polynomial-time algorithm for tabular Markov Decision Processes (MDP) that enjoys a regret bound \emph{independent on the planning horizon}. Specifically, we consider tabular MDP with $S$ states, $A$ actions, a planning horizon $H$, total reward bounded by $1$, and the agent plays for $K$ episodes. We design an algorithm that achieves an $O\left(\mathrm{poly}(S,A,\log K)\sqrt{K}\right)$ regret in contrast to existing bounds which either has an additional $\mathrm{polylog}(H)$ dependency \citep{zhang2020reinforcement} or has an exponential dependency on $S$ \citep{li2021settling}. Our result relies on a sequence of new structural lemmas establishing the approximation power, stability, and concentration property of stationary policies, which can have applications in other problems related to Markov chains.
Cite
Text
Zhang et al. "Horizon-Free Reinforcement Learning in Polynomial Time: The Power of Stationary Policies." Conference on Learning Theory, 2022.Markdown
[Zhang et al. "Horizon-Free Reinforcement Learning in Polynomial Time: The Power of Stationary Policies." Conference on Learning Theory, 2022.](https://mlanthology.org/colt/2022/zhang2022colt-horizonfree/)BibTeX
@inproceedings{zhang2022colt-horizonfree,
title = {{Horizon-Free Reinforcement Learning in Polynomial Time: The Power of Stationary Policies}},
author = {Zhang, Zihan and Ji, Xiangyang and Du, Simon},
booktitle = {Conference on Learning Theory},
year = {2022},
pages = {3858-3904},
volume = {178},
url = {https://mlanthology.org/colt/2022/zhang2022colt-horizonfree/}
}