Logarithmic regret bounds for continuous-time average-reward Markov decision processes. (arXiv:2205.11168v2 [cs.LG] UPDATED)

We consider reinforcement learning for continuous-time Markov decision
processes (MDPs) in the infinite-horizon, average-reward setting. In contrast
to discrete-time MDPs, a continuous-time process moves to a state and stays
there for a random holding time after an action is taken. With unknown
transition probabilities and rates of exponential holding times, we derive
instance-dependent regret lower bounds that are logarithmic in the time
horizon. Moreover, we design a learning algorithm and establish a finite-time
regret bound that achieves the logarithmic growth …

arxiv continuous decision markov processes time