Introduction
In safety-critical reinforcement learning (RL), ensuring that a system never violates specific safety boundaries is paramount. While standard Constrained Markov Decision Processes (CMDPs) manage average costs over time, they fail to prevent catastrophic single-event failures. This paper introduces Hard Constrained Semi-Markov Decision Processes (HCsMDPs), a framework designed for scenarios where cumulative costs must strictly remain below a threshold at every step.
The Challenge of Hard Constraints
Traditional CMDPs are suitable for long-term budgeting, such as minimizing average power consumption. However, for "hard" limits—like a drone's battery reaching zero—averages are irrelevant. Once a hard constraint is violated, the system may fail immediately.
Semi-MDPs (sMDPs) add complexity by allowing stochastic "sojourn times" (the duration spent in a state). Hard constraints in this context make the system non-Markovian: an agent's valid actions depend on the entire history of resource consumption.
Methodology: State Augmentation
To resolve the non-Markovian nature of hard constraints, the authors propose transforming the HCsMDP into an equivalent discrete-time MDP through state augmentation.
The agent's state is expanded from a simple physical state $x$ to a tuple $(x, t, \mathbf{d})$, where $t$ represents elapsed time and $\mathbf{d}$ is the vector of cumulative costs. This "bakes" the history into the current state, restoring the Markov property. The authors define two primary problem variants:
- Termination on Violation (V1): The episode ends with zero reward if a constraint is hit.
- Mandatory Avoidance (V2): The policy is restricted to actions that guarantee the constraint is never violated before a deadline.
Experimental Evaluation: The Taxi Driver
The framework was evaluated using a "Taxi Driver" simulation. In this scenario, a driver navigates between four locations to maximize profit while adhering to a strict 9-hour deadline and a 4-liter fuel limit.
The simulation demonstrates that the optimal policy is dynamic. When fuel is plentiful, the agent pursues high-profit routes. As resources dwindle, the policy automatically prioritizes refueling, even at a short-term financial loss, to ensure the hard constraint is satisfied.
Key Insights and Complexity
- NP-Hardness: The authors prove that solving HCsMDPs is NP-hard by reduction to the multi-criteria knapsack problem, highlighting the inherent computational difficulty of exact solutions.
- Policy Determinism: Unlike standard CMDPs that often require randomized policies to meet average constraints, the augmented HCsMDP allows for optimal deterministic policies.
- Action Pruning: For the "Mandatory Avoidance" case, the solution involves pruning any actions that carry a non-zero probability of leading to a constraint violation.
Conclusion
The primary contribution of this work is the formal proof that HCsMDPs can be mapped to discrete-time MDPs. This allows the application of established RL algorithms like Q-learning or Value Iteration to hard-constrained problems. However, state augmentation leads to the "curse of dimensionality." Future research will likely focus on using Deep RL and function approximation to manage the massive state spaces generated by high-precision time and cost tracking.
Summary updated