Logarithmic regret bounds for continuous-time average-reward Markov decision processes

Reinforcement learning (RL) is the problem of an agent learning how to map states to actions in order to maximize the reward over time in an unknown environment. It has received significant attention in the past decades, and the key challenge is in balancing the trade-off between exploration and exploitation (Sutton and Barto 2018). The common model for RL is a Markov Decision Process (MDP), which provides a mathematical framework for modeling sequential decision making problems under uncertainty. Most of the current studies on RL focus on developing algorithms and analysis for discrete-time MDPs. In contrast, less attention has been paid to continuous-time MDPs. However, there are many real-world applications where one needs to consider continuous-time MDPs. Examples include control of queueing systems, control of infectious diseases, preventive maintenance and high frequency trading; see, e.g., Guo and Hernández-Lerma (2009), Piunovskiy and Zhang (2020), Chapter 11 of Puterman (2014) and the references therein. One may propose discretizing time upfront to turn a continuous-time MDP into a discrete-time one and then apply the existing results and algorithms. However, it is well known in the RL community that this approach is very sensitive to time discretization and may perform poorly with small time steps; see e.g.