mlsanityData to 7 Oct 2026

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

arXiv 2210.00832 ↗First posted 3 Oct 2022cs.LG math.OCcited by 3

Not on the map. Why?

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.

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

Builds on

16 of 39 references.

References · 16

  1. 2017Minimax Regret Bounds for Reinforcement Learningcited by 500
  2. 2018Is Q-learning Provably Efficient?cited by 485
  3. 2019Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Boundscited by 194
  4. 2016Why is Posterior Sampling Better than Optimism for Reinforcement Learning?cited by 116
  5. 2020Episodic Reinforcement Learning in Finite MDPs: Minimax Lower Bounds Revisitedcited by 104
  6. 2018Policy Certificates: Towards Accountable Reinforcement Learningcited by 81
  7. 2016Explore First, Exploit Next: The True Shape of Regret in Bandit Problemscited by 78
  8. 2021Policy Gradient and Actor-Critic Learning in Continuous Time and Space: Theory and Algorithmscited by 76
  9. 2022q-Learning in Continuous Timecited by 68
  10. 2021Policy Evaluation and Temporal-Difference Learning in Continuous Time and Space: A Martingale Approachcited by 62
  11. 2019Making Deep Q-learning methods robust to time discretizationcited by 51
  12. 2020Logarithmic regret for episodic continuous-time linear-quadratic reinforcement learning over a finite-time horizoncited by 31
4 more
  1. 2021Reinforcement learning for linear-convex models with jumps via stability analysis of feedback controlscited by 21
  2. 2017Exploration--Exploitation in MDPs with Optionscited by 19
  3. 2021Exploration-exploitation trade-off for continuous-time episodic reinforcement learning with linear-convex modelscited by 18
  4. 2022Logarithmic regret bounds for continuous-time average-reward Markov decision processescited by 7

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 2; 2025: 0; 2026: 1.

3 papers.

  1. 2024Reinforcement Learning for Intensity Control: An Application to Choice-Based Network Revenue Managementcited by 3
  2. 2024ε-Policy Gradient for Online Pricingcited by 1
  3. 2026Reinforcement Learning for Continuous-Time Jump Markov Decision Processes with Applications to Network Dynamic Pricingcited by 0