mlsanityData to 14 Oct 2026

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

arXiv 2609.23127 ↗First posted 19 Sep 2026cs.LGcited by 0

On the map: Deep reinforcement learning methods → RL theory and sample complexity

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.

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.

Builds on

28 of 59 references.

Closest ancestors · 4

Same direction, newest first

  1. 2025Linear Dynamics meets Linear MDPs: Closed-Form Optimal Policies via Reinforcement Learning24 Aug
  2. 2025Sample and Computationally Efficient Continuous-Time Reinforcement Learning with General Function Approximation20 May
  3. 2024When to Sense and Control? A Time-adaptive Approach for Continuous-Time RL3 Jun
  4. 2024Near-Optimal Regret in Linear MDPs with Aggregate Bandit Feedback13 May

Other references · 24

  1. 2022Training language models to follow instructions with human feedbackcited by 15,971
  2. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 520
  3. 2017Minimax Regret Bounds for Reinforcement Learningcited by 503
  4. 2018Is Q-learning Provably Efficient?cited by 487
  5. 2013(More) Efficient Reinforcement Learning via Posterior Samplingcited by 233
  6. 2020Reward-Free Exploration for Reinforcement Learningcited by 177
  7. 2017Deep Exploration via Randomized Value Functionscited by 156
  8. 2018Lipschitz Continuity in Model-based Reinforcement Learningcited by 91
  9. 2022q-Learning in Continuous Timecited by 91
  10. 2013Bandits and Experts in Metric Spacescited by 63
  11. 2014Lipschitz Bandits: Regret Lower Bounds and Optimal Algorithmscited by 60
  12. 2021Policy Optimization in Adversarial MDPs: Improved Exploration via Dilated Bonusescited by 52
12 more
  1. 2023Making RL with Preference-based Feedback Efficient via Randomizationcited by 46
  2. 2022Delayed Feedback in Generalised Linear Bandits Revisitedcited by 23
  3. 2022Near-Optimal Regret for Adversarial MDP with Delayed Bandit Feedbackcited by 22
  4. 2023Efficient Exploration in Continuous-time Model-based Reinforcement Learningcited by 22
  5. 2021Lipschitz Bandits with Batched Feedbackcited by 21
  6. 2021Exploration-exploitation trade-off for continuous-time episodic reinforcement learning with linear-convex modelscited by 21
  7. 2023Robust Lipschitz Bandits to Adversarial Corruptionscited by 15
  8. 2020Enhancing Continuous Control of Mobile Robots for End-to-End Visual Active Trackingcited by 11
  9. 2024Continuous-Time State Estimation Methods in Robotics: A Surveycited by 10
  10. 2023Delay-Adapted Policy Optimization and Improved Regret for Adversarial MDP with Delayed Bandit Feedbackcited by 6
  11. 2025Statistical guarantees for continuous-time policy evaluation: blessing of ellipticity and new tradeoffscited by 4
  12. 2024Performance Improvement Bounds for Lipschitz Configurable Markov Decision Processescited by 1

Built on by

Not cited yet.

Similar, not cited

Close in wording, no citation either way

  1. 2026Learning Markov Decision Processes under Fully Bandit Feedback
  2. 2026Optimal Variance-Dependent Regret Bounds for Infinite-Horizon MDPs
  3. 2026Model-Based Reinforcement Learning with Double Oracle Efficiency in Policy Optimization and Offline Estimation
  4. 2026Learning in Markov Decision Processes with Exogenous Dynamics
  5. 2026DARLING: Detection Augmented Reinforcement Learning with Non-Stationary Guarantees
  6. 2024Local Linearity: the Key for No-regret Reinforcement Learning in Continuous MDPs
  7. 2026Online Markov Decision Processes with Terminal Law Constraints
  8. 2022Near-Optimal Regret Bounds for Multi-batch Reinforcement Learning