Scaling Reinforcement Learning Guarantees to Stochastic Environments

43 concepts41 papers1 proposal

Theoretical reinforcement learning (RL) and planning frameworks often rely on a powerful mathematical crutch: the deterministic transition assumption. By assuming that an agent's actions have completely certain outcomes, researchers can derive elegant proofs for sample complexity, safety boundaries, and convergence rates.

However, real-world deployments are inherently noisy. Physical systems contend with mechanical slip, sensor degradation, and unpredictable external forces. When we move from deterministic models to stochastic environments, the mathematical foundations supporting these algorithms often fracture. Understanding why this assumption is so pervasive—and exactly where it breaks down—is essential for building robust, real-world autonomous systems.


The Mathematical Allure of Determinism

To understand why theory loves determinism, consider how it simplifies the core equations of reinforcement learning. In a standard Markov Decision Process (MDP), taking an action $a$ in a state $s$ yields a probability distribution over the next states, defined by the transition function $P(s' \mid s, a)$. When calculating value functions or updating policies, an agent must compute an expectation over this distribution:

$$\mathbb{E}_{s' \sim P}[V(s')]$$

Under a deterministic transition assumption, this probability distribution collapses into a single point. The transition function becomes a simple mapping, $s' = f(s, a)$, and the expectation disappears entirely:

$$\mathbb{E}_{s' \sim P}[V(s')] = V(f(s, a))$$

This elimination of transition variance makes algorithms highly tractable. In a foundational analysis, Sven Koenig et al. demonstrated in Complexity Analysis of Real-Time Reinforcement Learning that starting from scratch in a deterministic domain allows for polynomial complexity bounds during path planning. Without this certainty, finding a goal could require an exponential number of actions.

This simplification propagates across multiple subfields of RL theory:


The Geometry of Safety and the Stochastic Fracture

The transition from deterministic paths to probabilistic distributions is particularly disruptive for safe exploration and avoidance constraints.

In a deterministic world, safety is a pathfinding problem. If an agent knows the transition function $f(s,a)$, it can project a single future trajectory and verify whether it intersects with a forbidden state. This geometric predictability underpins classical planning frameworks with avoid conditions, such as those developed by Marcel Steinmetz et al. in Classical Planning with Avoid Conditions, as well as goal-directed exploration methods like the GOOSE framework by Matteo Turchetta et al. in Safe Exploration for Interactive Machine Learning.

Deterministic Safety:
[State S] --(Action A)--> [Certain State S'] ---> (Safe)

Stochastic Safety:
                          /---> [State S'_1] ---> (Safe)
[State S] --(Action A)--> ----> [State S'_2] ---> (Safe)
                          \---> [State S'_3] ---> [CRASH] (Unsafe Tail Event)

In a stochastic environment, an action does not select a single next state; it selects a branching tree of possibilities. As Melrose Roderick et al. explain in Provably Safe PAC-MDP Exploration Using Analogies, an agent must ensure that every possible outcome within the action's probability distribution is safe.

This requirement fundamentally breaks popular safe exploration paradigms:

  1. Safe-Set Expansion: Algorithms like SAFEMDP (Felix Berkenkamp et al., Safe Exploration in Finite Markov Decision Processes with Gaussian Processes) and Lipschitz-continuity frameworks (Erdem Biyik et al., Efficient and Safe Exploration in Deterministic Markov Decision Processes with Unknown Transition Models) cautiously map out a "viability kernel"—a safe territory from which the agent can always return to a home base. In a stochastic world, a single unpredicted transition can push the agent past a point of no return.
  2. Feasibility Verification: In Solving Parameter-Robust Avoid Problems with Unknown Feasibility using Reinforcement Learning, Oswin So et al. point out that under stochastic dynamics, a single rollout is entirely insufficient to prove or disprove whether a region is safeable, requiring a shift toward probabilistic boundaries.
  3. Failure Penalties: Theoretical frameworks that penalize failures to enforce safety, such as the Safe Value Functions introduced by Pierre-François Massiani et al. in Safe Value Functions, rely on deterministic thresholds that fail to guarantee safety when environmental noise can bypass the controller's defenses.

As Akifumi Wachi et al. summarize in Long-Term Safe Reinforcement Learning with Binary Feedback, an agent operating under real-world randomness must constantly account for low-probability, catastrophic transitions, even when following a trajectory that appears safe on average.


Why Sample Complexity and Optimality Proofs Collapse

Beyond safety, removing the deterministic transition assumption causes statistical guarantees to degrade. When transitions are probabilistic, variance propagates through the Bellman updates, compounding errors at each timestep.

This issue is highly visible in offline reinforcement learning, where an agent learns from a fixed, pre-collected dataset without the ability to explore. David Meger demonstrates in Off-Policy Deep Reinforcement Learning without Exploration that batch-constrained methods rely heavily on deterministic transitions to bound extrapolation errors. When the environment is stochastic, the agent easily hallucinates high-reward transitions that are statistically unsupported by the dataset.

Similarly, Chejian Xu et al. note in COPA: Certifying Robust Policies for Offline Reinforcement Learning against Poisoning Attacks that certifying cumulative rewards against adversarial data manipulation becomes an open challenge in stochastic MDPs due to the inherent unpredictability of state trajectories.

Error Propagation over Time:

Deterministic:  [S_0] --(a)--> [S_1] --(a)--> [S_2]  (Error remains bounded)

Stochastic:     [S_0] --(a)--> Var(S_1) --(a)--> Var(S_2) ++ Var(S_1) (Errors compound exponentially)

In the online setting, near-optimal sample complexity bounds often depend on tracking value function realizability. For example, the Frozen Policy Iteration framework by Yijing Ke et al. in Frozen Policy Iteration: Computationally Efficient RL under Linear $Q^{\pi}$ Realizability for Deterministic Dynamics achieves statistical optimality by strategically "freezing" policies in well-explored states. This mechanism relies on the structural stability of deterministic transitions.

When transitions are stochastic, the agent cannot easily isolate function approximation errors from environmental noise, causing the tight bounds established by frameworks like agnostic Q-learning (Simon Shaolei Du et al., Agnostic $Q$-learning with Function Approximation in Deterministic Systems: Near-Optimal Bounds on Approximation Error and Sample Complexity) to break down.


Shifting to Probabilistic Risk Management

To bridge the gap between theory and reality, modern research is moving away from absolute, binary guarantees toward probabilistic risk management. If an algorithm cannot guarantee that a hazardous state will never be reached, it must instead prove that the likelihood of failure remains below an acceptable threshold.

One prominent approach involves modifying the optimization objective to focus on tail risks rather than expected values. In Quantile Constrained Reinforcement Learning: A Reinforcement Learning Framework Constraining Outage Probability, Whiyoung Jung et al. introduced the QCRL framework. Instead of minimizing average costs, QCRL uses the Large Deviation Principle to strictly constrain the "outage probability"—the probability that an agent experiences a catastrophic cost event in a stochastic environment.

Another strategy modifies the underlying planning operators to handle the branching complexity of noisy environments. In continuous action spaces, stochastic transitions cause traditional Monte Carlo Tree Search (MCTS) methods to fail because the search tree branches uncontrollably. To resolve this, Tuan Dam et al. developed the Stochastic-Power-HOOT algorithm in Power Mean Estimation in Stochastic Continuous Monte-Carlo Tree Search. By replacing standard backup operators with a tunable power mean, the algorithm achieves proven polynomial convergence rates despite transition noise.

By replacing the fragile assumption of absolute determinism with robust probabilistic bounds, these frameworks are establishing a new theoretical foundation—one capable of providing reliable guarantees in an inherently unpredictable world.

Key Foundational Work

Bounding the Suboptimality of Reusing Subproblem (1999) — contributed 2 concept elements to this direction.
Complexity Analysis of Real-Time Reinforcement Learning (1993) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_deterministic_transition_assumption_dete_dffd31ed,
  title = {deterministic transition assumption (deterministic environment assumption)},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/deterministic-transition-assumption-deterministic-environment-assumption/rdr_dffd31ed16284e18b964ba03050a9af7},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_deterministic_transition_assumption_dete_dffd31ed_v1,
  title = {deterministic transition assumption (deterministic environment assumption)},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/deterministic-transition-assumption-deterministic-environment-assumption/rdr_dffd31ed16284e18b964ba03050a9af7/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake