Efficient reinforcement learning for irregular continuous time decisions
Provably Efficient Reinforcement Learning in Continuous-Time Episodic MDPs with Poisson Decision Epochs
Machine Learning
Summary
Many learning systems make decisions at set times, but some real-world problems need decisions happening at unpredictable moments. This paper studies how to learn well in situations where decision opportunities come randomly over time, following a pattern called a Poisson process. The authors develop and analyze methods that adapt classic learning techniques to this setup and prove these methods learn efficiently with certainty about their performance. Their results also show the learning speed they achieve is the best possible for these kinds of problems.
What this means in practice
- •For automated control engineers: Design controllers that learn optimal actions in systems where events happen at unpredictable times, improving control efficiency under time-varying conditions.
- •For financial algorithm developers: Develop trading algorithms that adapt to irregular market events with provably efficient learning guarantees over continuous time.
A theory result. No direct application yet.
Authors
Kenny Guo, Valentio Iverson, Sahan Wijetunga, William Chang
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 (Auer and Ortner 2006) and Q-learning (Jin et al. 2018) to this setting, proving $\widetilde{O}(T^{2/3})$ regret bounds for both model-based and model-free algorithms. Finally, we establish matching $\widetildeΩ(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.