PaperlayerView exact revision on arXiv

Source-linked AI summary

Reinforcement Learning for Continuous-Time Jump Markov Decision Processes with Applications to Network Dynamic Pricing

Huiling Meng, Ningyuan Chen, Xuefeng Gao

arXiv:2608.20680v1cs.LG

TL;DR

The paper addresses the lack of continuous-time RL methods for CTJMDPs with general discrete state spaces, where diffusion-based theory does not directly apply. It develops entropy-regularized, model-free q-learning with martingale-based theory and evaluates it in network dynamic pricing, where it learns near-optimal policies and scales to very large state spaces.

  • Problem

    Continuous-time RL theory largely targets Euclidean continuous-state systems, leaving CTJMDPs with general discrete state spaces and jump rewards insufficiently addressed.

  • Method

    The paper extends continuous-time q-learning to CTJMDPs using randomized entropy-regularized policies and martingale characterizations based on observable trajectories.

  • Results

    The learned pricing policy comes within 2.39% of the DP optimum in a small network, exceeds FP-BL revenue by 7.9% in a large network, and is comparable to FP without known demand functions.

  • Takeaways & Limitations

    The framework supports model-free RL for CTJMDPs and demonstrates near-optimal network pricing performance, including on an instance with approximately 5.88 × 10^13 states.

  • Takeaways & Limitations

    The theoretical analysis focuses on bounded transition rates, and direct randomized action selection at every time can create measurability problems requiring an exploratory-process construction.

Abstract

from arXiv · show

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 $\mathbb{R}^d$ and rely heavily on semimartingale theory in $\mathbb{R}^d$ 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.

1 Introduction

The paper develops continuous-time RL for CTJMDPs with general discrete state spaces, addressing limitations of discrete-time approximations and diffusion-based methods. It establishes theoretical and algorithmic foundations and evaluates them in network dynamic pricing.

  • Uniform time discretization can be sensitive to the step size and perform poorly with small steps in continuous-time decision problems.
  • Existing continuous-time RL predominantly studies continuous state spaces in R^d governed by stochastic differential equations.
  • CTJMDPs permit continuous observation and action updates, denumerable non-vector-space states, discrete or continuous actions, time-dependent rates, and running and jump rewards.
  • The paper develops model-free RL foundations and algorithms for CTJMDPs, extending continuous-time q-learning theory to discrete-state jump systems.
  • In network dynamic pricing, the learned policy achieves revenue within 2.39% of the time-discretized DP benchmark and improves on two heuristic policies in the small network.
  • Uniformization does not apply to the finite-horizon CTJMDPs studied because optimal policies are non-stationary and depend explicitly on time.

2 Classical Finite-Horizon CTJMDPs

This section formulates finite-horizon CTJMDPs with countable states, flexible actions, transition rates, and running, jump, and terminal rewards. It specifies admissible controls, state evolution, value optimization, and bounded-rate assumptions supporting the HJB characterization.

  • A finite-horizon CTJMDP uses a denumerable state space that may lack vector-space structure and an action space that can be discrete or continuous.
  • Transition rates λ(y | t, x, a) govern jumps from state x to y and are Borel measurable and stable under the model assumptions.
  • Running rewards accrue during sojourns, while jump rewards are received when the process transitions between distinct states.
  • An admissible control is a measurable function from time-state pairs to actions, and the controlled process evolves through state sojourns and jumps.
  • The objective is to choose an admissible control that maximizes the value function over the finite planning horizon.
  • The analysis assumes bounded transition rates, while allowing reward rates and terminal rewards to grow with the state through a weighting function.

3 Reinforcement Learning Formulation for CTJMDPs

The paper formulates exploration through randomized Markov policies and entropy regularization for CTJMDPs. It defines an exploratory state process, establishes value-function characterization, and identifies an optimal soft-max policy under admissibility conditions.

  • A randomized Markov policy is a stochastic kernel assigning an action distribution to each time-state pair.
  • The exploratory state process averages transition and reward dynamics over the randomized policy and is used for theoretical analysis rather than observed implementation.
  • Randomization alone may not provide sufficient exploration because finite-horizon CTJMDPs can admit optimal deterministic policies.
  • Entropy regularization introduces a temperature parameter γ that controls exploration and converges to the unregularized value as γ approaches zero.
  • Admissibility requires mutual absolute continuity with the reference measure and growth control for the entropy term, ensuring action coverage and finite regularized values.
  • Under the stated assumptions, the regularized optimal value is characterized by an HJB equation, with an admissible optimal policy taking a soft-max form.

4 q-Learning Theory and Algorithm for CTJMDPs

The paper develops model-free continuous-time q-learning for CTJMDPs with general denumerable state spaces, using martingale characterizations of the optimal value and q-functions. Its grid-independent targets and jump-aware construction support flexible implementation and reduce discretization error.

  • Model-free q-learning: The framework learns the optimal value function and q-function directly from observed CTJMDP trajectories without estimating model parameters.The learned q-function recovers the optimal policy.
  • Model-free q-learning: The continuous-time q-function captures the first-order, action-dependent advantage rate when the initial action duration vanishes.This extends continuous-time q-learning from controlled diffusions to discrete-state jump systems.
  • Martingale characterization: Theoretical results establish a Dynkin formula for the non-Markovian grid sample state process and uniquely identify the optimal value–q-function pair through a martingale condition.The identification requires terminal and normalization conditions; one policy and one fixed horizon-wide grid suffice for the sufficiency direction.
  • Martingale characterization: Unlike diffusion-based analyses, the proof handles transition-rate kernels on denumerable state spaces without Euclidean vector-space operations or semimartingale calculus.The distinction reflects the structure of general discrete-state CTJMDPs.
  • Algorithm design: The algorithm incorporates every realized state jump, grid-based action change, and observed cumulative reward without temporal quadrature.The remaining approximation error comes from time variation of integrands within each interval.
  • Algorithm design: The learning targets are continuous-time and grid-independent, allowing flexible non-uniform discretizations and incorporation of random transition times.This reduces discretization errors and can improve algorithmic efficiency relative to fixed-grid time discretization.

5 Case Study: Network Dynamic Pricing

The case study applies the CTJMDP framework to airline network dynamic pricing, where shared capacities couple itinerary prices and demand. Algorithm 1 learns pricing policies from observed transitions and revenues, achieving near-DP performance in a small network and scaling to a very large state space.

  • Problem: Airline itineraries share flight-leg capacities, so lower prices accelerate demand while consuming capacity valuable to other itineraries.Pricing decisions are therefore coupled through remaining capacities.
  • Model: The pricing CTJMDP uses remaining leg capacities as states and itinerary prices as actions, with Poisson arrivals and capacity-feasible sales.A sale of itinerary j changes the state by subtracting its leg-incidence vector and yields revenue equal to its price.
  • Method: Algorithm 1 learns from observed state transitions and revenues without knowing the demand functions.Its implementation uses separate actor and critic neural networks with normalized time-state inputs and Gamma-distributed nonnegative prices.
  • Benchmarks: The benchmarks include time-discretized dynamic programming, a deterministic upper bound, fluid pricing, and fluid pricing with booking limits.The fluid policies use deterministic price paths, with FP-BL additionally imposing itinerary-level booking limits.
  • Small-network results: Within 2.39% of the DP optimal value, the learned small-network policy outperforms FP by 8.87% and FP-BL by 18.91%.The DP reference value is 709.883; the heuristic gaps are attributed to small capacities, resource coupling, and their fixed decisions.
  • Large-network results: 58,818 revenue exceeds FP-BL by 7.9% in the large network, whose approximately 5.88 × 10^13 states make direct dynamic programming infeasible.The learned policy performs comparably to FP despite not using the known demand model required to construct FP.

6 Conclusion and Future Work

The paper establishes model-free q-learning for CTJMDPs and applies it to network dynamic pricing and queueing control. It identifies convergence analysis and broader high-dimensional applications as future research directions.

  • The paper establishes theoretical foundations for reinforcement learning in CTJMDPs with general discrete state spaces and proposes efficient q-learning algorithms.
  • Numerical experiments apply the framework to network dynamic pricing and queueing control, demonstrating strong performance.
  • Future theoretical work includes convergence analysis for the proposed q-learning algorithm and study of the underlying stochastic approximation procedures.
  • Future applied work includes extending the framework to other high-dimensional operations research applications.

A Case Study: Dynamic Server Allocation for Queue Control

The case study models dynamic server allocation as a finite-horizon CTJMDP with queue-length states and active-server actions. Model-free learning approaches the discrete-time dynamic-programming benchmark, achieving a final average reward of −31.272 versus −30.796.

  • Problem formulation: The service system has queue-length states X = {0, 1, . . . , C} and active-server actions A = {0, 1, . . . , S}, with decisions possible at any time.More active servers reduce congestion but increase operating costs, and the optimal choice depends on queue length and remaining time.
  • Problem formulation: Customer arrivals follow a nonhomogeneous Poisson process, while each busy server completes service at a time-dependent rate.Arrivals at capacity are blocked; transition rates depend on the queue length and active-server count.
  • RL setting: The model-free RL setting assumes known cost coefficients but unknown arrival and service rates, targeting a non-stationary optimal policy.The policy depends on both system state and time.
  • Experimental setup: The experiment uses a finite horizon with T = 10 and capacity and server count C = S = 10, benchmarking against a discretized dynamic-programming solution.The discretization uses a small time step ∆t′ to approximate the continuous-time control problem.
  • Training and evaluation: 10,000 independently simulated sample paths estimate the current policy value during training.The evaluation starts from x0 = 0 and reports policy values over the learning process.
  • Results: −31.272 is the final learned policy’s average reward, compared with the benchmark −30.796, leaving a performance gap of 0.476.Policy values increase and stabilize near the benchmark.

B Proofs of Statements

This section supplies the proof sequence for the paper’s theoretical results. It begins with an entropy-regularized maximization lemma and then proves Proposition 1, Theorem 1, and Theorem 2.

  • Proof organization: Lemma 1 addresses entropy-regularized maximization for a measurable q-hat function under an integrability condition.The lemma is used in the proofs of Proposition 1 and Theorem 2.
  • Proof organization: The proofs proceed in order from Proposition 1 to Theorem 1 and then Theorem 2.
  • Proof organization: The entropy-regularized maximization proof follows the argument of Jia and Zhou (2023), replacing Lebesgue measure with the reference measure µ.

B.1 Proof of Proposition 1

The proof of Proposition 1 establishes that the operator G is well-defined and contractive, yielding a unique fixed point that solves the relevant equation and represents the optimal value.

  • Operator properties: The operator G is shown to be well-defined on the weighted Banach space B_w([0, T] × X).Integrability and weighted bounds establish measurability, absolute continuity, and finite weighted norm.
  • Operator properties: The contraction factor (2L + b + c)/(2L + b + c + 1) is less than 1, so G has a unique fixed point ψ∗.
  • Solution construction: The fixed point is transformed into φ(t, x) = e^−ρtψ∗(t, x), which solves differential equation (9) and has the required regularity.The proof establishes that φ belongs to C^1,0_w([0, T] × X).
  • Optimality: For any policy π, the objective satisfies J(t, x; π) ≤ φ(t, x), while the maximizing policy π∗ attains equality.
  • Optimality: Consequently, J∗(t, x) = J(t, x; π∗) = φ(t, x), and π∗ has the form given in (10).

B.2 Proof of Theorem 1

The proof partitions intervals using the time grid and exploits that actions remain fixed between grid points. It then identifies the controlled state process with an exploratory process under a deterministic Markov policy and applies a known jump-process result.

  • Fixed actions: Actions remain fixed within each grid interval, enabling conditional analysis of the state process.For tk ≤ r1 ≤ r2 ≤ tk+1, Ak remains fixed on the relevant interval.
  • Conditional dynamics: Conditional on the sampled state and action, the exploratory state process has the same law as a deterministic Markov-policy process.The equality in law follows from matching transition rates under the deterministic policy δa.
  • Conclusion: Applying Theorem 3.1 of Guo et al. (2015) to the deterministic-policy process yields the required result.The proof concludes after applying the cited jump-process theorem and combining the resulting identities.
  • Grid construction: The time grid partitions each interval so every subinterval lies within one grid interval.Grid points strictly between u and v form the partition u = σ0 < ··· < σN = v.

B.3 Proof of Theorem 2

The proof establishes an auxiliary martingale lemma for grid-sampled processes and uses it with entropy-regularized dynamic-programming identities. It concludes that the candidate value and q-functions are optimal.

  • Auxiliary lemma: The proof first establishes an auxiliary lemma for policies, initial time-state pairs, and time grids.The lemma is proved under Assumption 1 with function w.
  • Martingale construction: Fixed grid actions and integrability make the relevant stochastic-integral processes martingales.The argument uses the martingale property of stochastic integrals with respect to compensated counting processes.
  • Almost-everywhere identity: The proof combines several martingales to derive a continuous finite-variation martingale and then obtains D(t, x, a) = 0 almost everywhere.A contradiction argument shows that failure of the zero condition would create a positive-measure set inconsistent with the earlier result.
  • Optimality identity: The resulting Hamilton–Jacobi identity and normalization condition determine the entropy-regularized optimal policy relation.The proof uses logarithms and the normalization of bq* to connect the Hamiltonian expression with the optimal policy.
  • Optimality conclusion: cJ* is the optimal value function, while bq* is the optimal q-function.This conclusion follows from the equation, terminal condition, Proposition 1, and the definition of the optimal q-function.
Loading 2608.20680v1…