🤖 machine learning

Stochastic Decision Horizons for Constrained Reinforcement Learning

This paper introduces Stochastic Decision Horizons (SDH), a theoretically grounded framework that ensures every-step constraint satisfaction in constrained reinforcement learning by modeling violations as effective horizon shortenings, leading to novel off-policy algorithms like VT-MPO that achieve superior reward-violation trade-offs and training stability compared to state-of-the-art methods.

Original authors: Nikola Milosevic, Leonard Franz, Daniel Haeufle, Georg Martius, Nico Scherf, Pavel Kolev

Published 2026-05-27

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Nikola Milosevic, Leonard Franz, Daniel Haeufle, Georg Martius, Nico Scherf, Pavel Kolev

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are teaching a robot to walk. In the old way of doing this (called Constrained MDPs or CMDPs), you give the robot a "budget" of mistakes it can make. Think of it like a credit card: "You can step on the grass 10 times before you get in trouble." The robot might walk carefully for a while, then take a huge risk, step on the grass 9 times in a row, and still be "safe" because it hasn't hit the limit yet. This works for things like fuel consumption, but it's dangerous for things like a robot falling over or a patient's heart rate spiking, where one bad step causes immediate disaster.

This paper proposes a new way to teach robots called Stochastic Decision Horizons (SDH). Instead of a credit card budget, SDH treats every step as a "survival check."

The Core Idea: The "Fragile Glass" Analogy

Imagine the robot is walking on a floor made of fragile glass.

The Old Way (Budget): The floor has a counter. If the robot steps too hard, the counter goes up. As long as the counter is below 10, the robot is fine. It might learn to jump around wildly, hoping not to hit the limit.
The New Way (SDH): Every time the robot takes a step, there is a chance the glass cracks. If the step is safe, the glass stays strong. If the step is dangerous (a "violation"), the glass becomes slightly more fragile. If the robot takes a really bad step, the glass might shatter completely, and the robot's "life" in that specific training run ends immediately.

In SDH, a violation doesn't just add a point to a score; it shortens the robot's future. If the robot knows that a bad step might end its "life" right now, it learns to be careful every single time, not just when it's close to its budget limit.

Two Ways to Handle a "Cracked Glass"

The paper explores two different philosophies on what happens after the glass cracks (a violation occurs):

The "Absorbing State" (AS-SAC): Imagine the glass shatters, and the robot falls into a black hole. It stops making decisions entirely. It's game over for that specific attempt. The robot learns that if it messes up, it loses all future rewards. This is like a "hard stop."
The "Virtual Termination" (VT-MPO): Imagine the glass cracks, and the robot is still standing, but it is now "ghostly." It can still move its legs and make decisions, but it can no longer earn any points (rewards) for its actions. It's like playing a video game where you are still alive, but your score is frozen at zero. The robot keeps moving, but it learns that bad moves make its future worthless.

The paper finds that the second method (VT-MPO) is often more stable and easier to train, especially for complex tasks.

The Big Breakthrough: Realistic Walking

The authors tested this on a very complex, realistic human-like robot with 90 muscles (called H2190). Teaching this robot to walk naturally without falling or hurting itself is a huge challenge.

The Problem: Previous methods tried to balance "walking fast" vs. "using less energy" by constantly changing the rules (like a teacher yelling, "Walk faster!" then "Slow down!"). This made the robot's training unstable and took a long time.
The Result: Using SDH (specifically the VT-MPO method), the robot learned to walk just as realistically as the best previous methods, but it did it 4 times faster and with much more stable training. It didn't need constant rule changes; it just learned that bad steps shorten its future, so it naturally found a safe, efficient way to walk.

When Does This Work? (The "Single Scale" Rule)

The paper also explains when this method works best.

It works great when the dangers are consistent. For example, if every time the robot steps too hard, it's a "medium" risk that shortens its life a little bit. This is like walking on a floor where every loose tile is equally dangerous.
It struggles when the dangers are mixed. Imagine a floor where 99% of the time, stepping on a tile does nothing, but 1% of the time, stepping on a tile blows up the whole building. The "survival" method might not catch this rare, massive explosion because it's used to small, frequent cracks. In these cases, the old "budget" method might still be needed.

Summary

This paper introduces a smarter way to teach robots safety. Instead of giving them a "budget" for mistakes, it teaches them that every mistake reduces their future. This forces them to be safe at every single step, leading to faster, more stable learning for complex tasks like realistic human walking.

Technical Summary: Stochastic Decision Horizons for Constrained Reinforcement Learning

Problem Statement

Reinforcement learning (RL) for real-world control systems (e.g., robotics, biomechanics, medical processes) often requires satisfying instantaneous constraints at every time step. A single deep violation can cause hardware damage, patient harm, or controller instability. The standard framework for constrained RL, the Constrained Markov Decision Process (CMDP), optimizes for a cumulative cost budget. While effective for global budgets (e.g., total fuel consumption), CMDPs struggle with instantaneous feasibility. Encoding a per-step limit into a cumulative budget forces the budget to be extremely small, a regime where existing CMDP algorithms often fail to converge or learn effectively.

The paper proposes Stochastic Decision Horizons (SDH) as a theoretically grounded alternative. Instead of spending a budget upon violation, SDH treats a constraint violation as an instantaneous (in)feasibility signal that probabilistically shortens the effective planning horizon.

Methodology

1. Stochastic Decision Horizons (SDH)

SDH reframes the constrained problem as a survival-chance problem.

Mechanism: A state-action continuation probability $\alpha(s, a) \in [0, 1]$ is introduced. If a constraint is violated, $\alpha$ drops, reducing the probability that the trajectory continues.
Objective: The agent maximizes the expected reward at a random geometric termination time $T_\gamma$ , conditioned on the trajectory surviving up to that point.
Bellman Formulation: This leads to a modified Bellman equation with shaped rewards and state-action-dependent discounts:
- $\tilde{r}(s, a) = \alpha(s, a) r(s, a)$
- $\tilde{\gamma}(s, a) = \gamma \alpha(s, a)$
Dual Variable: The Lagrangian dual variable $\eta$ acts as a survival bonus added to the reward ( $r + \eta$ ) rather than a cost penalty. This encourages policies that maintain a high probability of survival.

2. Control as Inference (CaI) and Regularization

To derive off-policy, regularized algorithms, the authors use Control as Inference. They identify two distinct semantic interpretations of what happens after a constraint violation, leading to two different regularizers:

Absorbing-State (AS) Semantics: The decision process terminates immediately upon violation. Only surviving decisions contribute to the information cost (KL divergence/entropy).
- Algorithm: AS-SAC (Absorbing-State Soft Actor-Critic).
- Regularizer: Maximum entropy, but weighted only by the surviving decision mass. This yields a variable-discount soft Bellman recursion.
Virtual-Termination (VT) Semantics: The decision process continues, but reward credit stops. The agent continues to act on the underlying MDP, but future rewards are gated by survival.
- Algorithm: VT-MPO (Virtual-Termination Maximum a Posteriori Policy Optimization).
- Regularizer: KL-regularized policy improvement on the ordinary discounted horizon, paired with a survival-shaped critic.

3. Theoretical Link to CMDPs

The paper introduces violation-depth profiles to characterize the relationship between SDH and additive-budget CMDPs.

Single-Scale Regime: If violations occur at a single characteristic scale (e.g., frequent shallow violations or rare deep ones following a specific distribution), SDH effectively solves the matching additive-budget CMDP.
Multi-Scale Regime: If the violation profile mixes scales (e.g., frequent shallow violations alongside rare deep ones), SDH and CMDP objectives diverge. SDH cannot reproduce exact budget-aware feasibility rules without augmenting the state space with history.

Key Contributions

Formalization of SDH: The authors formalize general continuation models $\alpha(s, a)$ as Bellman-consistent survival occupancies. They prove SDH is the fixed-dual Lagrangian form of a stochastic survival-chance problem.
Regularized Off-Policy Algorithms: They derive the first off-policy, regularized algorithms for instantaneous constraints: AS-SAC (max-entropy) and VT-MPO (KL-regularized). Both are compatible with experience replay.
Theoretical Scope Analysis: Through violation-depth profiles, they precisely delineate when SDH solves an additive-budget CMDP (single-scale violations) and when it does not (multi-scale violations).
State-of-the-Art Biomechanical Control: They apply VT-MPO to high-fidelity musculoskeletal models, solving the long-standing effort-velocity gait trade-off as a fixed instantaneous constraint problem.

Experimental Results

1. Hyfydy (Musculoskeletal Control)

Setup: Training on three humanoid models (H0918, H1622, H2190) with up to 90 muscles.
Comparison: Compared against Effort Weight Adaptation (EWA), the state-of-the-art domain-specific method that uses adaptive reward reweighting.
Results:
- Stability: VT-MPO converges to stable walking with significantly fewer oscillations than EWA, which suffers from non-stationary reward signals.
- Sample Efficiency: VT-MPO achieves state-of-the-art gait realism with 4 $\times$ fewer environment steps (e.g., reaching peak performance on H2190 in 21M steps vs. 90M for EWA).
- Realism: Both methods achieve similar gait match percentages (approx. 63-76%), but VT-MPO reaches these peaks much faster and with tighter constraint satisfaction (velocity, Ground Reaction Forces, joint torques).

2. Safety Gymnasium (Scope Test)

Setup: Evaluated on locomotion and navigation tasks with standardized cost signals.
Findings:
- Single-Scale Tasks (e.g., AntVelocity): SDH (VT-MPO and AS-SAC) achieves strong reward-cost trade-offs, outperforming unconstrained baselines and matching constrained baselines with higher sample efficiency.
- Multi-Scale Tasks (e.g., PointGoal, CarButton): The theory correctly predicts failure modes. In tasks requiring the agent to sacrifice some constraint satisfaction to achieve a goal (multi-scale violation profiles), SDH either fails to satisfy constraints or suffers catastrophic reward degradation. This confirms the theoretical limitation that SDH is not a general solver for arbitrary additive-budget CMDPs.

Significance and Claims

The paper claims that Stochastic Decision Horizons offer a complementary design axis for constrained RL: shape the horizon rather than tune a budget.

Practical Impact: SDH provides a principled way to handle instantaneous constraints where a single violation is catastrophic, avoiding the instability of adaptive reward reweighting (like EWA) and the difficulty of setting tiny budgets in CMDPs.
Theoretical Insight: The work clarifies that instantaneous constraints and cumulative budgets are distinct objectives that only coincide under specific geometric conditions (single-scale violation profiles).
Algorithmic Advancement: It provides the first regularized off-policy algorithms (AS-SAC, VT-MPO) specifically designed for instantaneous constraints, enabling stable training on high-dimensional, complex systems like 90-muscle humanoids.

The authors emphasize that while SDH is not a universal replacement for CMDPs, it is the exact solution for survival-chance problems and offers superior stability and sample efficiency in regimes where per-step feasibility is the primary concern.