Reinforcement Learning for Continuous-Time Jump Markov Decision Processes with Applications to Network Dynamic Pricing
Authors: Huiling Meng, Ningyuan Chen, Xuefeng Gao
Organizations: Department of Systems Engineering and Engineering Management, The Chinese University of Hong Kong, Hong Kong, China. · Rotman School of Management, University of Toronto, Toronto, Canada
We study reinforcement learning (RL) in Continuous-Time Jump Markov Decision Processes (CTJMDPs) featuring general discrete state spaces (which need not possess a vector space structure) and continuous/discrete action spaces. The setup covers many well-known applications in operations such as multi-product dynamic pricing with capacitated resources (Gallego and van Ryzin 1997). To model the exploration-exploitation tradeoff, we formulate an entropy-regularized continuous-time control problem with stochastic policies. Recent continuous-time RL techniques such as q-learning for controlled diffusions in (Jia and Zhou 2023) focus on continuous state spaces Rd and rely heavily on semimartingale theory in Rd for their theoretical analysis. Consequently, their methods cannot be directly applied to CTJMDPs with general discrete state spaces, which may lack the algebraic addition and subtraction structures inherent to Euclidean spaces. To bridge this gap, we establish the theoretical foundations of q-learning for CTJMDPs and develop model-free q-learning algorithms. Compared to naïve time discretization and approximating CTJMDPs using discrete-time MDPs, our approach has several conceptual and empirical benefits. Numerical experiments in network dynamic pricing (Gallego and van Ryzin 1997) show that our proposed RL algorithm reliably learns near-optimal policies and consistently outperforms standard benchmark methods, demonstrating superior solution quality and effective scalability to large-scale network instances.
Figures & tables
S∪TJ={0=s0<s1<⋯<sM=T},
Algorithm 1 Episodic q -Learning Algorithm
Itinerary j
λj0
ϵj0
pj0
1
30
4.0
20
2
15
4.0
30
3
50
4.0
45
Table 1: Itinerary and demand parameters for the example in Section 5.1
Figure 1: Average revenue of Algorithm 1 over episodes for the example in Section 5.1
Method
Average revenue
99%-CI ( ± )
Gap from DP
DP
709.883
–
0.00%
Algorithm 1
692.951
0.811
2.39%
FP
636.519
2.599
10.33%
FP-BL
582.763
2.392
17.90%
Table 2: Numerical results for the example in Section 5.1
Figure 2: Airline network for the example in Section 5.2
Itinerary j
O–D pair
Path
ϵj0
pj0
1
1 – 2
1 – 2
1.0
220
2
1 – 3
1 – 3
1.2
220
3
1 – 4
1 – 2 – 4
2.0
400
4
1 – 5
1 – 3 – 5
1.0
250
5
1 – 6
1 – 6
0.8
200
6
2 – 3
2 – 3
1.0
230
Table 3: Itinerary and demand parameters for example in Section 5.2
Figure 3: Average revenue of Algorithm 1 over episodes for the example in Section 5.2
Appendix figures & tables1 asset
Supplementary material from the paper’s appendix.
Appendix
Figure 4: Average reward of Algorithm 1 over episodes for queue control
Markov decision processes model sequential choices under uncertainty, linking actions, state transitions, and rewards to planning and reinforcement learning.
The framework of robust Markov decision processes (RMDPs) allows the design of reinforcement learning agents that satisfy performance guarantees under worst-case transition dynamics. Traditional RMDPs consider discrete-time dynamics and recently, sample-efficient policy gradient algorithms have been considered in this context. This paper investigates policy gradient algorithms within a continuous-time RMDP framework. Policy gradients and adversarial gradients are derived using pathwise and adjoint-based formulas for stochastic and ordinary differential equations. We propose double-loop optimisers to obtain linear convergence in the oracle-based setting and an O~(ε21) sample complexity in the sample-based setting in an analysis which also derives novel tools for the framework of undiscounted total cost MDPs. Additionally, we propose mean-field optimisers as distributional optimisers with an O~(K1) oracle-based convergence rate and an O~(εN2) sample complexity under N-particle approximation. The effectiveness of continuous-time policy gradient algorithms is confirmed for both optimisers on continuous-time RMDPs with neural ordinary differential equation dynamics.
Tanya Veeravalli, David M. Bossens, Atsushi Nitanda
Centre for Frontier AI Research, Agency for Science, Technology and Research (A*STAR) · Institute of High Performance Computing, Agency for Science, Technology and Research (A*STAR) · College of Computing and Data Science, Nanyang Technological University
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 O(T2/3) regret bounds for both model-based and model-free algorithms. Finally, we establish matching Ω(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.
Kenny Guo, Valentio Iverson, Sahan Wijetunga +1
Department of Economics, Yale University, New Haven, Connecticut, USA · Department of Computer Science, Massachusetts Institute of Technology, Cambridge, Massachusetts, USA · Department of Mathematics, University of California, Los Angeles, Los Angeles, California, USA
We study reinforcement learning in infinite-horizon discounted Markov decision processes with continuous state spaces, where data are generated online from a single trajectory under a Markovian behavior policy. To avoid maintaining an infinite-dimensional, function-valued estimate, we propose the novel Q-Measure-Learning, which learns a signed empirical measure supported on visited state-action pairs and reconstructs an action-value estimate via kernel integration. The method jointly estimates the stationary distribution of the behavior chain and the Q-measure through coupled stochastic approximation, leading to an efficient weight-based implementation with O(n) memory and O(n) computation cost per iteration. Under uniform ergodicity of the behavior chain, we prove almost sure sup-norm convergence of the induced Q-function to the fixed point of a kernel-smoothed Bellman operator. We also bound the approximation error between this limit and the optimal Q∗ as a function of the kernel bandwidth. To assess the performance of our proposed algorithm, we conduct RL experiments in a two-item inventory control setting.
Shengbo Wang
Daniel J. Epstein Department of Industrial and Systems Engineering, University of Southern California