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

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

## 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 (most cited first, 17 of 17)

- [Non-Asymptotic Gap-Dependent Regret Bounds for Tabular MDPs](https://mlsanity.com/paper/1905.03814/) (2019)
- [Policy Gradient and Actor-Critic Learning in Continuous Time and Space: Theory and Algorithms](https://mlsanity.com/paper/2111.11232/) (2021)
- [Policy Evaluation and Temporal-Difference Learning in Continuous Time and Space: A Martingale Approach](https://mlsanity.com/paper/2108.06655/) (2021)
- [Model-free Reinforcement Learning in Infinite-horizon Average-reward Markov Decision Processes](https://mlsanity.com/paper/1910.07072/) (2019)
- [What Doubling Tricks Can and Can't Do for Multi-Armed Bandits](https://mlsanity.com/paper/1803.06971/) (2018)
- [Efficient Bias-Span-Constrained Exploration-Exploitation in Reinforcement Learning](https://mlsanity.com/paper/1802.04020/) (2018)
- [Q-learning with Logarithmic Regret](https://mlsanity.com/paper/2006.09118/) (2020)
- [Making Deep Q-learning methods robust to time discretization](https://mlsanity.com/paper/1901.09732/) (2019)
- [Fine-Grained Gap-Dependent Bounds for Tabular MDPs via Adaptive Multi-Step Bootstrap](https://mlsanity.com/paper/2102.04692/) (2021)
- [Queueing Network Controls via Deep Reinforcement Learning](https://mlsanity.com/paper/2008.01644/) (2020)
- [Logarithmic regret for episodic continuous-time linear-quadratic reinforcement learning over a finite-time horizon](https://mlsanity.com/paper/2006.15316/) (2020)
- [Exploration in Structured Reinforcement Learning](https://mlsanity.com/paper/1806.00775/) (2018)
- [Primal-Dual π Learning: Sample Complexity and Sublinear Run Time for Ergodic Markov Decision Problems](https://mlsanity.com/paper/1710.06100/) (2017)
- [Towards Tight Bounds on the Sample Complexity of Average-reward MDPs](https://mlsanity.com/paper/2106.07046/) (2021)
- [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)

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

- [Optimal scheduling of entropy regulariser for continuous-time linear-quadratic reinforcement learning](https://mlsanity.com/paper/2208.04466/) (2022)
- [Square-root regret bounds for continuous-time episodic Markov decision processes](https://mlsanity.com/paper/2210.00832/) (2022)
- [Statistical Learning with Sublinear Regret of Propagator Models](https://mlsanity.com/paper/2301.05157/) (2023)
- [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)
- [Reinforcement Learning and Regret Bounds for Admission Control](https://mlsanity.com/paper/2406.04766/) (2024)
- [Two Kinds of Learning Algorithms for Continuous-Time VWAP Targeting Execution](https://mlsanity.com/paper/2411.06645/) (2024)
- [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 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.