Square-root regret bounds for continuous-time episodic Markov decision processes

Reinforcement learning (RL) studies the problem of sequential decision making in an unknown environment by carefully balancing between exploration (learning) and exploitation (optimizing) (Sutton and Barto 2018). While the RL study has a relatively long history, it has received considerable attention in the past decades due to the explosion of available data and rapid improvement of computing power. A hitherto default mathematical framework for RL is Markov decision process (MDP), where the agent does not know the transition probabilities and can observe a reward resulting from an action but does not know the reward function itself. There has been extensive research on RL for discrete-time MDPs (DTMDPs); see, e.g., Jaksch et al. (2010), Osband and Van Roy (2017), Azar et al. (2017), Jin et al. (2018). However, much less attention has been paid to RL for continuous-time MDPs, whereas there are many real-world applications where one needs to interact with the unknown environment and learn the optimal strategies continuously in time. Examples include autonomous driving, control of queueing systems, control of infectious diseases, preventive maintenance and robot navigation; see, e.g., Guo and Hernández-Lerma (2009), Piunovskiy and Zhang (2020), Chapter 11 of Puterman (2014) and the references therein. In this paper we study RL for tabular continuous-time Markov decision processes (CTMDPs) in the finite-horizon, episodic setting, where an agent interacts with the unknown environment in episodes of a fixed length with finite state and action spaces. The study of model-based (i.e. the underlying models are assumed to be known) finite-horizon CTMDPs has a very long history, probably dating back to Miller (1968), with vast applications including queueing optimization (Lippman 1976), dynamic pricing (Gallego and Van Ryzin 1994), and finance and insurance (Bäuerle and