Logarithmic Regret Bounds For Continuous-time Average-reward Markov Decision Processes

Abstract

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.

Stats

• citations4
• S2 citations—
• github stars0
• HF likes0
• heat score5.24
• arxiv keygao2022logarithmic

Related papers

• Square-root Regret Bounds For Continuous-time Episodic Markov Decision Processes (2022)2.26
• Reinforcement Learning For Infinite-horizon Average-reward Linear Mdps Via Approximation By Discounted-reward Mdps (2024)0.00
• Regret Analysis In Deterministic Reinforcement Learning (2021)0.00
• Logarithmic Regret Of Exploration In Average Reward Markov Decision Processes (2025)0.00
• Model-free Reinforcement Learning In Infinite-horizon Average-reward Markov Decision Processes (2019)0.00
• Variance-aware Regret Bounds For Undiscounted Reinforcement Learning In Mdps (2018)0.00
• Logarithmic Regret For Episodic Continuous-time Linear-quadratic Reinforcement Learning Over A Finite-time Horizon (2020)7.81
• Value-biased Maximum Likelihood Estimation For Model-based Reinforcement Learning In Discounted Linear Mdps (2023)0.00