Standard reinforcement learning models the world as a sequence of rapid, uniform ticks of a clock. At every tick, an agent observes a state, takes an action, and immediately transitions to the next state. However, as Craig Boutilier and Martin L. Puterman pointed out in Process-Oriented Planning and Average-Reward Optimality, real-world ongoing processes rarely conform to uniform time steps. A robot navigating between distant rooms (Rishi Shah et al. in Deep R-Learning for Continual Area Sweeping), a ride-sharing vehicle completing a trip (Xiaocheng Tang et al. in A Deep Value-network Based Approach for Multi-Driver Order Dispatching), or a transit bus navigating urban traffic (Jose Paolo Talusan et al. in An Online Approach to Solving Public Transit Stationing and Dispatch Problem) all execute actions with variable, stochastic durations.
Forcing these durative actions into a standard Markov Decision Process (MDP) creates a severe dilemma. We can either discretize time finely—which exponentially explodes the state space and the search tree's history (Zhan Wei Lim et al. in Monte Carlo Value Iteration with Macro-Actions)—or we treat actions as instantaneous, ignoring the temporal costs and risks inherent to the task (Majid Khonji and Duoaa Khalifa in Heuristic Search in Dual Space for Constrained Fixed-Horizon POMDPs with Durative Actions).
To resolve this, researchers rely on the Semi-Markov Decision Process (SMDP) framework. By decoupling decision points from a rigid clock, SMDPs allow actions to span variable, uncertain intervals of time, providing a mathematically rigorous way to smooth rewards and discount future states over the actual duration of an event.
The Mechanics of Temporal Discounting and Reward Smoothing
In a standard MDP, the value of a state under a policy is updated by discounting the next state's value by a fixed factor $\gamma$. In an SMDP, because the duration $\tau$ between decisions is a random variable, the discount factor must adapt dynamically to the time elapsed. The core mechanism relies on a modified Bellman equation where the discount factor becomes $\gamma^\tau$, effectively penalizing actions that take longer to reach a goal.
As Xiaocheng Tang et al. demonstrate, this formulation ensures that long-term value estimations remain stable by smoothing accumulated immediate rewards over the actual duration of the task rather than assuming fixed-interval transitions. This temporal amortization is crucial across diverse domains:
- Resource Allocation: In IoT networks, Chao Xu et al. use this framework in Optimal Status Update for Caching Enabled IoT Networks: A Dueling Deep R-Network Approach to ensure metrics like information staleness are accurately amortized over non-uniform operational phases.
- Adaptive Computation: Adrian Orenstein et al. leverage multi-step temporal difference updates in Toward Agents That Reason About Their Computation to ensure that rewards accumulated during skipped decision steps are correctly attributed to the initial choice of action duration, allowing agents to "coast" through predictable states and "think" during critical ones.
Hierarchical Abstraction and the Options Framework
One of the most powerful applications of variable-duration action modeling is Hierarchical Reinforcement Learning (HRL). Instead of forcing an agent to plan using low-level primitive actions, the environment is modeled as an SMDP where actions represent "macro-actions" or "options" (e.g., "drive to the next intersection").
Natalia Hernandez-Gardiol and Sridhar Mahadevan show in Hierarchical Memory-Based Reinforcement Learning that this framework allows rewards to propagate across actions taking varying amounts of time, which is essential when a single high-level command encompasses a long sequence of low-level operations.
The theoretical benefits of this approach are profound:
- Accelerated Convergence: The authors of Scaling Up Approximate Value Iteration with Options: Better Policies with Fewer Iterations prove that integrating temporally extended actions into value iteration allows reward information to propagate across multiple timesteps within a single update, accelerating the convergence of the value function.
- Reduced Regret: Gianluca Drappo et al. establish in An Option-Dependent Analysis of Regret Minimization Algorithms in Finite-Horizon Semi-MDP that options reduce the effective planning horizon, leading to lower regret than flat RL approaches.
- Forward Projection: Because standard backward induction cannot handle stochastic durations in finite-horizon settings, Alberto Maria Metelli et al. introduce a value iteration mechanism in A Provably Efficient Option-Based Algorithm for both High-Level and Low-Level Learning that projects values forward to all possible future state-time pairs reachable by an option.
This hierarchical SMDP structure is not just computationally efficient; it also mirrors biological decision-making. Christoph Gebhardt demonstrates in Hierarchical Reinforcement Learning Explains Task Interleaving Behavior that a two-level supervisory SMDP framework accurately predicts how humans adapt to task-switching costs and variable temporal lengths during complex activities.
Continuous-Time Dynamics and Asynchronous Events
In many real-world systems, decisions are triggered by asynchronous events rather than a fixed schedule. SMDPs naturally extend to continuous-time settings (CT-SMDPs) to capture these irregular dynamics. For instance, Wenjuan Cheng et al. utilize a CT-SMDP framework in Continuous-time MAXQ Algorithm for Web Service Composition to accurately model processing times and network latencies.
When the timing of events is itself stochastic and history-dependent, standard models fail. Chao Qu addresses this in Bellman Meets Hawkes: Model-Based Reinforcement Learning via Temporal Point Processes by integrating Neural Hawkes Processes into the SMDP Bellman equation. This allows agents to perform accurate reward discounting across highly irregular, non-deterministic intervals where the timing of an event carries as much information as the event itself.
To ensure these continuous-time control systems are reliable, Ngo Anh Vien et al. establish rigorous mathematical bounds on approximation and estimation errors in Policy Gradient Based Semi-Markov Decision Problems: Approximation and Estimation Errors, proving that policy gradient methods remain stable even when decisions occur at irregular, random intervals.
Applications in Complex and Constrained Environments
By decoupling decisions from a rigid clock, agents can focus computation and coordination only when it matters. For example, Zhenyu Shi et al. show in Learning Expensive Coordination: An Event-Based Deep RL Approach that an event-based semi-MDP allows a leader agent to act only at significant events (like task completion), stabilizing multi-agent coordination.
In navigation and routing, Matthias Schubert and Sebastian Schmoll use SMDPs for high-level goal transitions in Semi-Markov Reinforcement Learning for Stochastic Resource Collection, discounting rewards based on the actual travel times between distant locations. This flexibility extends to high-level autonomous planning under physical constraints, such as space robots filming humans (David Kent and Sonia Chernova in Human-Centric Active Perception for Autonomous Observation), dynamic radar scanning (Victoria Manfredi and Jim Kurose in Scan Strategies for Meteorological Radars), and proactive network defense (Yingbo Li et al. in Rlaph: a lightweight and dynamic proactive defense method in cloud-edge collaboration).
Ultimately, modeling variable-duration actions allows agents to balance the high cost of deliberation with the necessity of reacting to sudden environmental changes, as demonstrated by Kevin Lloyd and Peter Dayan in Interrupting behaviour: Minimizing decision costs via temporal commitment and low-level interrupts. By formalizing time as an inherent dimension of an action rather than a rigid constraint of the environment, SMDPs provide the mathematical foundation necessary for efficient, long-term planning in the real world.
Key Foundational Work
Process-Oriented Planning and Average-Reward Optimality (1995) — contributed 1 concept elements to this direction.
Reinforcement Learning Methods for Continuous-Time Markov Decision Problems (1994) — contributed 1 concept elements to this direction.