Provably Efficient Reinforcement Learning in Continuous-Time Episodic MDPs with Poisson Decision Epochs

Kenny Guo, Valentio Iverson, Sahan Wijetunga, William Chang
Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence, PMLR 337:1823-1856, 2026.

Abstract

Many real-world reinforcement learning ({RL}) problems evolve in continuous time, where decisions occur at irregular, event-driven intervals rather than at fixed discrete steps. We study episodic continuous-time {Markov} Decision Processes ({MDPs}) in which decision epochs are governed by a homogeneous {Poisson} process and the reward and transition dynamics vary smoothly over time. We consider both a fixed number of jumps per episode and a fixed time budget with a random number of {Poisson} decision epochs. Under a Lipschitz continuity assumption in time, we exploit local smoothness through discretization and extend both UCRL \cite{auer2006logarithmic} and Q-learning \cite{jin2018q} to this setting, proving $\tilde{\mathcal{O}}(T^{2/3})$ regret bounds for both model-based and model-free algorithms. Finally, we establish matching $\tilde{\Omega}(T^{2/3})$ minimax lower bounds, showing that the rate is optimal up to logarithmic factors. These results provide the first tight regret guarantees for Lipschitz-smooth continuous-time episodic {MDPs} with {Poisson} decision epochs.

Cite this Paper

BibTeX
@InProceedings{pmlr-v337-guo26b, title = {Provably Efficient Reinforcement Learning in Continuous-Time Episodic {MDPs} with {Poisson} Decision Epochs}, author = {Guo, Kenny and Iverson, Valentio and Wijetunga, Sahan and Chang, William}, booktitle = {Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence}, pages = {1823--1856}, year = {2026}, editor = {Perković, Emilija and Malinsky, Daniel}, volume = {337}, series = {Proceedings of Machine Learning Research}, month = {17--21 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v337/main/assets/guo26b/guo26b.pdf}, url = {https://proceedings.mlr.press/v337/guo26b.html}, abstract = {Many real-world reinforcement learning ({RL}) problems evolve in continuous time, where decisions occur at irregular, event-driven intervals rather than at fixed discrete steps. We study episodic continuous-time {Markov} Decision Processes ({MDPs}) in which decision epochs are governed by a homogeneous {Poisson} process and the reward and transition dynamics vary smoothly over time. We consider both a fixed number of jumps per episode and a fixed time budget with a random number of {Poisson} decision epochs. Under a Lipschitz continuity assumption in time, we exploit local smoothness through discretization and extend both UCRL \cite{auer2006logarithmic} and Q-learning \cite{jin2018q} to this setting, proving $\tilde{\mathcal{O}}(T^{2/3})$ regret bounds for both model-based and model-free algorithms. Finally, we establish matching $\tilde{\Omega}(T^{2/3})$ minimax lower bounds, showing that the rate is optimal up to logarithmic factors. These results provide the first tight regret guarantees for Lipschitz-smooth continuous-time episodic {MDPs} with {Poisson} decision epochs.} }
Endnote
%0 Conference Paper %T Provably Efficient Reinforcement Learning in Continuous-Time Episodic MDPs with Poisson Decision Epochs %A Kenny Guo %A Valentio Iverson %A Sahan Wijetunga %A William Chang %B Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2026 %E Emilija Perković %E Daniel Malinsky %F pmlr-v337-guo26b %I PMLR %P 1823--1856 %U https://proceedings.mlr.press/v337/guo26b.html %V 337 %X Many real-world reinforcement learning ({RL}) problems evolve in continuous time, where decisions occur at irregular, event-driven intervals rather than at fixed discrete steps. We study episodic continuous-time {Markov} Decision Processes ({MDPs}) in which decision epochs are governed by a homogeneous {Poisson} process and the reward and transition dynamics vary smoothly over time. We consider both a fixed number of jumps per episode and a fixed time budget with a random number of {Poisson} decision epochs. Under a Lipschitz continuity assumption in time, we exploit local smoothness through discretization and extend both UCRL \cite{auer2006logarithmic} and Q-learning \cite{jin2018q} to this setting, proving $\tilde{\mathcal{O}}(T^{2/3})$ regret bounds for both model-based and model-free algorithms. Finally, we establish matching $\tilde{\Omega}(T^{2/3})$ minimax lower bounds, showing that the rate is optimal up to logarithmic factors. These results provide the first tight regret guarantees for Lipschitz-smooth continuous-time episodic {MDPs} with {Poisson} decision epochs.
APA
Guo, K., Iverson, V., Wijetunga, S. & Chang, W.. (2026). Provably Efficient Reinforcement Learning in Continuous-Time Episodic MDPs with Poisson Decision Epochs. Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research 337:1823-1856 Available from https://proceedings.mlr.press/v337/guo26b.html.

Related Material