Regret Analysis for RL using Renewal Bandit Feedback

Learning in a Markov Decision Process (MDP) framework is a fundamental challenge for sequential decision making under uncertainty. In this paper, we present a new perspective on model-based learning in MDPs using ideas from renewal theory. In particular, we reformulate the problem of controlling a Markov chain to one of controlling a renewal reward process with bandit feedback. For this reformulated problem, we provide a regret decomposition that informs novel algorithm design for MDPs. We further provide a naive algorithm based¨ on this reformulation along with the regret analysis. A simple greedy variant of the proposed algorithm is shown to empirically outperform popular value-based methods for finite MDPs.