mlsanityData to 14 Oct 2026

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

arXiv 2205.11168 ↗First posted 23 May 2022cs.LG math.OC stat.MLcited by 8

Not on the map. Why?

Abstract (arXiv)

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 rate. Our analysis builds upon upper confidence reinforcement learning, a delicate estimation of the mean holding times, and stochastic comparison of point processes.

Key facts. Cited by 8 papers in the map (data through 14 Oct 2026). Builds on 17 of its 51 references that are in the map. First posted on arXiv 23 May 2022.

Builds on

17 of 51 references.

References · 17

  1. 2019Non-Asymptotic Gap-Dependent Regret Bounds for Tabular MDPscited by 105
  2. 2021Policy Gradient and Actor-Critic Learning in Continuous Time and Space: Theory and Algorithmscited by 101
  3. 2021Policy Evaluation and Temporal-Difference Learning in Continuous Time and Space: A Martingale Approachcited by 84
  4. 2019Model-free Reinforcement Learning in Infinite-horizon Average-reward Markov Decision Processescited by 82
  5. 2018What Doubling Tricks Can and Can't Do for Multi-Armed Banditscited by 71
  6. 2018Efficient Bias-Span-Constrained Exploration-Exploitation in Reinforcement Learningcited by 66
  7. 2020Q-learning with Logarithmic Regretcited by 60
  8. 2019Making Deep Q-learning methods robust to time discretizationcited by 58
  9. 2021Fine-Grained Gap-Dependent Bounds for Tabular MDPs via Adaptive Multi-Step Bootstrapcited by 49
  10. 2020Queueing Network Controls via Deep Reinforcement Learningcited by 41
  11. 2020Logarithmic regret for episodic continuous-time linear-quadratic reinforcement learning over a finite-time horizoncited by 35
  12. 2018Exploration in Structured Reinforcement Learningcited by 34
5 more
  1. 2017Primal-Dual π Learning: Sample Complexity and Sublinear Run Time for Ergodic Markov Decision Problemscited by 33
  2. 2021Towards Tight Bounds on the Sample Complexity of Average-reward MDPscited by 33
  3. 2021Reinforcement learning for linear-convex models with jumps via stability analysis of feedback controlscited by 24
  4. 2021Exploration-exploitation trade-off for continuous-time episodic reinforcement learning with linear-convex modelscited by 21
  5. 2017Exploration--Exploitation in MDPs with Optionscited by 19

Built on by

Cited by year (2026 to 14 Oct)

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

8 papers.

  1. 2022Optimal scheduling of entropy regulariser for continuous-time linear-quadratic reinforcement learningcited by 6
  2. 2022Square-root regret bounds for continuous-time episodic Markov decision processescited by 5
  3. 2023Statistical Learning with Sublinear Regret of Propagator Modelscited by 5
  4. 2024Reinforcement Learning for Intensity Control: An Application to Choice-Based Network Revenue Managementcited by 3
  5. 2024ε-Policy Gradient for Online Pricingcited by 1
  6. 2024Reinforcement Learning and Regret Bounds for Admission Controlcited by 0
  7. 2024Two Kinds of Learning Algorithms for Continuous-Time VWAP Targeting Executioncited by 0
  8. 2026Reinforcement Learning for Continuous-Time Jump Markov Decision Processes with Applications to Network Dynamic Pricingcited by 0