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

arXiv: https://arxiv.org/abs/2210.00832 · HTML: https://mlsanity.com/paper/2210.00832/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 39 references that are in the map.
- First posted on arXiv 3 Oct 2022.

## Builds on (most cited first, 16 of 16)

- [Minimax Regret Bounds for Reinforcement Learning](https://mlsanity.com/paper/1703.05449/) (2017)
- [Is Q-learning Provably Efficient?](https://mlsanity.com/paper/1807.03765/) (2018)
- [Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Bounds](https://mlsanity.com/paper/1901.00210/) (2019)
- [Why is Posterior Sampling Better than Optimism for Reinforcement Learning?](https://mlsanity.com/paper/1607.00215/) (2016)
- [Episodic Reinforcement Learning in Finite MDPs: Minimax Lower Bounds Revisited](https://mlsanity.com/paper/2010.03531/) (2020)
- [Policy Gradient and Actor-Critic Learning in Continuous Time and Space: Theory and Algorithms](https://mlsanity.com/paper/2111.11232/) (2021)
- [q-Learning in Continuous Time](https://mlsanity.com/paper/2207.00713/) (2022)
- [Policy Evaluation and Temporal-Difference Learning in Continuous Time and Space: A Martingale Approach](https://mlsanity.com/paper/2108.06655/) (2021)
- [Policy Certificates: Towards Accountable Reinforcement Learning](https://mlsanity.com/paper/1811.03056/) (2018)
- [Explore First, Exploit Next: The True Shape of Regret in Bandit Problems](https://mlsanity.com/paper/1602.07182/) (2016)
- [Making Deep Q-learning methods robust to time discretization](https://mlsanity.com/paper/1901.09732/) (2019)
- [Logarithmic regret for episodic continuous-time linear-quadratic reinforcement learning over a finite-time horizon](https://mlsanity.com/paper/2006.15316/) (2020)
- [Reinforcement learning for linear-convex models with jumps via stability analysis of feedback controls](https://mlsanity.com/paper/2104.09311/) (2021)
- [Exploration-exploitation trade-off for continuous-time episodic reinforcement learning with linear-convex models](https://mlsanity.com/paper/2112.10264/) (2021)
- [Exploration--Exploitation in MDPs with Options](https://mlsanity.com/paper/1703.08667/) (2017)
- [Logarithmic regret bounds for continuous-time average-reward Markov decision processes](https://mlsanity.com/paper/2205.11168/) (2022)

## Built on by (most cited first, 5 of 5)

- [Reinforcement Learning for Intensity Control: An Application to Choice-Based Network Revenue Management](https://mlsanity.com/paper/2406.05358/) (2024)
- [ε-Policy Gradient for Online Pricing](https://mlsanity.com/paper/2405.03624/) (2024)
- [Two Kinds of Learning Algorithms for Continuous-Time VWAP Targeting Execution](https://mlsanity.com/paper/2411.06645/) (2024)
- [Continuous-Time Reinforcement Learning for N-Player Stochastic Differential Games with Exploratory Policies](https://mlsanity.com/paper/2607.19928/) (2026)
- [Reinforcement Learning for Continuous-Time Jump Markov Decision Processes with Applications to Network Dynamic Pricing](https://mlsanity.com/paper/2608.20680/) (2026)

## Abstract (arXiv)

We study reinforcement learning for continuous-time Markov decision processes (MDPs) in the finite-horizon episodic setting. In contrast to discrete-time MDPs, the inter-transition times of a continuous-time MDP are exponentially distributed with rate parameters depending on the state--action pair at each transition. We present a learning algorithm based on the methods of value iteration and upper confidence bound. We derive an upper bound on the worst-case expected regret for the proposed algorithm, and establish a worst-case lower bound, both bounds are of the order of square-root on the number of episodes. Finally, we conduct simulation experiments to illustrate the performance of our algorithm.