Overview
This paper extends popular reinforcement learning (RL) algorithms—originally designed for discrete-time steps—into the realm of continuous-time Semi-Markov Decision Problems (SMDPs). By adapting TD(0), Q-learning, and Real-Time Dynamic Programming (RTDP) to handle variable transition times and continuous discounting, the authors provide a framework for training autonomous agents in "event-driven" environments like telecommunications and queueing systems.
The Challenge of Continuous Time
Most classical reinforcement learning research focuses on discrete-time Markov Decision Processes (MDPs), where the world moves in fixed ticks (e.g., turn-based games). However, many real-world engineering problems are continuous. In a computer network or a hospital waiting room, events (like a packet arriving or a patient being discharged) happen at irregular intervals.
Modeling these as discrete-time systems often requires artificially small time steps, which explodes the computational cost. The authors address this by moving to SMDPs, where the time between states is a random variable. The challenge is that standard RL update rules do not account for the "duration" of an action or the continuous decay of rewards over time.
Adapting RL for SMDPs
The authors derive continuous-time versions of three foundational RL algorithms. The key innovation across these methods is the integration of the discount factor $e^{-\beta\tau}$ and the cumulative reward over the interval $\tau$, ensuring the math remains consistent with continuous-time Bellman equations.
- TD(0) for SMDPs: Updates the value of a state based on the reward accumulated during a transition of duration $\tau$ and the discounted value of the resulting state.
- Q-learning for SMDPs: A model-free approach where the agent learns the value of state-action pairs. The update rule is modified to account for the continuous discount rate $\beta$ and the observed transition time $\tau$: $$Q(x, a) \leftarrow Q(x, a) + \alpha \left[ \frac{1 - e^{-\beta\tau}}{\beta} r + e^{-\beta\tau} \max_{a'} Q(y, a') - Q(x, a) \right]$$
- Adaptive RTDP: A model-based approach where the agent learns the transition probabilities and expected rewards on the fly, using this internal model to speed up convergence compared to model-free methods.
Experimental Setup: The Queueing System
To evaluate the algorithms, the authors use a simulated queueing system, a standard benchmark in operations research.
- The Task: Routing incoming "customers" (e.g., data packets, arriving at rate $\lambda$) to one of two queues served by different processors (heterogeneous servers with rates $\mu_1$ and $\mu_2$).
- The Goal: Minimize the infinite-horizon discounted cost, where cost is tied to the number of customers waiting in the queues.
- Function Approximation: Because the state space is technically infinite, the authors used a feedforward neural network trained via backpropagation to approximate the Q-values.
Key Results and Policy Convergence
The transition from discrete to continuous RL proves mathematically elegant. By treating the time between events ($\tau$) as a variable in the discount function, the core logic of temporal difference learning remains intact. The agent only needs to make decisions and update its knowledge when an event occurs (an arrival or a service completion), rather than at every millisecond of simulated time.
In the queueing experiment, the SMDP version of Q-learning successfully learned a policy that resembles the known optimal threshold policy (e.g., routing to the shorter queue when servers are identical).
The paper includes plots showing the evolution of the policy over thousands of updates. Initially random, the policy eventually forms a clear diagonal boundary, indicating the agent learned to balance the two queues effectively.
Limitations and Future Work
While the algorithm converged to the correct behavior, the authors noted that convergence was rather slow, highlighting the need for careful tuning of the learning rate ($\alpha$) and the exploration temperature.
- Convergence Speed: The model-free Q-learning approach requires a high number of samples to reach optimality. Model-based methods (like RTDP) or better exploration strategies are necessary for more complex systems.
- Infinite State Spaces: While the algorithms worked in practice with a neural network, formal convergence proofs for RL in infinite state spaces are significantly more difficult than in finite cases.
- Structural Knowledge: The authors suggest that RL could be made much faster if we "bake in" structural assumptions (like knowing the optimal policy is a threshold policy) into the function approximator, pointing toward future work involving more complex distributed control issues.
Summary updated