REGAL Revisited: Regularized Reinforcement Learning for Weakly Communicating MDPs

Abstract

Markov Decision Processes (MDPs) are used extensively in artificial intelligence and reinforcement learning to describe how an agent interacts with its environment. MDPs specify what possible states an agent can be in, what its possible actions are, and what the effects of taking those actions will be. By studying MDPs, we can develop techniques and algorithms which can be applied to many real-world problems where an agent is required to act intelligently. Many such algorithms have been developed with the assumption that the conditions of the MDP is known to the agent, i.e. the agent knows all the information it needs about the environment, including the possible states, actions, and effects of taking actions. This project focuses on settings where such information is unknown to the agent: it does not know how the world will behave when it takes a certain action. This makes it necessary for the agent to take actions it is unfamiliar with in order to gradually learn what their effects may be. There have been several algorithms introduced to solve this problem, most notably UCRL2 . However, the regret bound achieved by UCRL2 is dependent on the diameter of the MDP. The diameter is the maximum average number of steps it takes to get from one state to another state. In MDPs where at least one state is unreachable from any of the other states, the diameter is infinite, making UCRL2 ineffective. In this project, I will build upon on already developed algorithm called REGAL. This algorithm has good provable theoretical performance and achieves a regret bound which does not depend on the diameter. However, it cannot be implemented into a real computer program because it requires knowledge of certain information which are unavailable. This report presents a modification to the algorithm which makes it implementable, while preserving the provable theoretical performance of the original algorithm.