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

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods.
- Builds on 28 of its 59 references that are in the map.
- First posted on arXiv 19 Sep 2026.

## Placed in

- Deep reinforcement learning methods / [RL theory and sample complexity](https://mlsanity.com/deeprl/rl-theory-and-sample-complexity/)

## Builds on (most cited first, 28 of 28)

- [Training language models to follow instructions with human feedback](https://mlsanity.com/paper/2203.02155/) (2022)
- [Provably Efficient Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/1907.05388/) (2019)
- [Minimax Regret Bounds for Reinforcement Learning](https://mlsanity.com/paper/1703.05449/) (2017)
- [Is Q-learning Provably Efficient?](https://mlsanity.com/paper/1807.03765/) (2018)
- [(More) Efficient Reinforcement Learning via Posterior Sampling](https://mlsanity.com/paper/1306.0940/) (2013)
- [Reward-Free Exploration for Reinforcement Learning](https://mlsanity.com/paper/2002.02794/) (2020)
- [Deep Exploration via Randomized Value Functions](https://mlsanity.com/paper/1703.07608/) (2017)
- [Lipschitz Continuity in Model-based Reinforcement Learning](https://mlsanity.com/paper/1804.07193/) (2018)
- [q-Learning in Continuous Time](https://mlsanity.com/paper/2207.00713/) (2022)
- [Bandits and Experts in Metric Spaces](https://mlsanity.com/paper/1312.1277/) (2013)
- [Lipschitz Bandits: Regret Lower Bounds and Optimal Algorithms](https://mlsanity.com/paper/1405.4758/) (2014)
- [Policy Optimization in Adversarial MDPs: Improved Exploration via Dilated Bonuses](https://mlsanity.com/paper/2107.08346/) (2021)
- [Making RL with Preference-based Feedback Efficient via Randomization](https://mlsanity.com/paper/2310.14554/) (2023)
- [Delayed Feedback in Generalised Linear Bandits Revisited](https://mlsanity.com/paper/2207.10786/) (2022)
- [Near-Optimal Regret for Adversarial MDP with Delayed Bandit Feedback](https://mlsanity.com/paper/2201.13172/) (2022)
- [Efficient Exploration in Continuous-time Model-based Reinforcement Learning](https://mlsanity.com/paper/2310.19848/) (2023)
- [Lipschitz Bandits with Batched Feedback](https://mlsanity.com/paper/2110.09722/) (2021)
- [Exploration-exploitation trade-off for continuous-time episodic reinforcement learning with linear-convex models](https://mlsanity.com/paper/2112.10264/) (2021)
- [Robust Lipschitz Bandits to Adversarial Corruptions](https://mlsanity.com/paper/2305.18543/) (2023)
- [Enhancing Continuous Control of Mobile Robots for End-to-End Visual Active Tracking](https://mlsanity.com/paper/2009.13475/) (2020)
- [Near-Optimal Regret in Linear MDPs with Aggregate Bandit Feedback](https://mlsanity.com/paper/2405.07637/) (2024)
- [Continuous-Time State Estimation Methods in Robotics: A Survey](https://mlsanity.com/paper/2411.03951/) (2024)
- [When to Sense and Control? A Time-adaptive Approach for Continuous-Time RL](https://mlsanity.com/paper/2406.01163/) (2024)
- [Delay-Adapted Policy Optimization and Improved Regret for Adversarial MDP with Delayed Bandit Feedback](https://mlsanity.com/paper/2305.07911/) (2023)
- [Statistical guarantees for continuous-time policy evaluation: blessing of ellipticity and new tradeoffs](https://mlsanity.com/paper/2502.04297/) (2025)
- [Sample and Computationally Efficient Continuous-Time Reinforcement Learning with General Function Approximation](https://mlsanity.com/paper/2505.14821/) (2025)
- [Linear Dynamics meets Linear MDPs: Closed-Form Optimal Policies via Reinforcement Learning](https://mlsanity.com/paper/2508.17185/) (2025)
- [Performance Improvement Bounds for Lipschitz Configurable Markov Decision Processes](https://mlsanity.com/paper/2402.13821/) (2024)

## Abstract (arXiv)

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 (Auer and Ortner 2006) and Q-learning (Jin et al. 2018) to this setting, proving widetildeO(T2/3) regret bounds for both model-based and model-free algorithms. Finally, we establish matching widetildeOmega(T2/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.