REGAL: A Regularization based Algorithm for Reinforcement Learning in Weakly Communicating MDPs

Understand

We provide an algorithm that achieves the optimal regret rate in an unknown weakly communicating Markov Decision Process (MDP).

• The algorithm proceeds in episodes where, in each episode, it picks a policy using regularization based on the span of the optimal bias vector.
• For an MDP with S states and A actions whose optimal bias vector has span bounded by H, we show a regret bound of ~O(HSpAT).
• We also relate the span to various diameter-like quantities associated with the MDP, demonstrating how our results improve on previous regret bounds.