The foundational success of Reinforcement Learning (RL) relies on a elegant mathematical convenience: the Markov property. In a standard Markov Decision Process (MDP), the transition dynamics are independent across different state-action pairs. This independence allows us to break a complex, long-horizon optimization problem into localized, step-by-step decisions using the Bellman optimality equation.
However, real-world environments rarely exhibit such perfectly decoupled dynamics. When we introduce realistic forms of transition uncertainty—such as protecting against worst-case environmental shifts (Robust MDPs) or managing unobserved, evolving environments (POMDPs with rich observations)—this fundamental independence breaks down.
Recent research reveals that introducing transition uncertainty or stochasticity couples states together, creating severe computational barriers. Understanding why these barriers arise, and how modern algorithmic frameworks bypass them, is essential for designing robust, practical RL systems.
Why Transition Uncertainty Destroys Dynamic Programming
To understand why transition uncertainty introduces NP-hardness, we must look at how algorithms optimize under uncertainty.
The Non-Rectangularity Barrier in Robust MDPs
In Robust MDPs, instead of assuming a single fixed transition probability distribution, we assume the true transition dynamics belong to an adversarial uncertainty set. The goal is to find a policy that maximizes performance under the worst-case scenario within this set.
To keep this optimization tractable, traditional methods rely on a "rectangularity" assumption. An uncertainty set is rectangular if the worst-case transition distribution can be chosen independently for every single state-action pair. Under rectangularity, the robust Bellman operator remains a contraction, and standard dynamic programming works perfectly.
But rectangularity is highly unrealistic. Imagine an autonomous car driving in a storm; if the road is slippery at intersection A, it is highly likely also slippery at intersection B. The uncertainty is coupled across states. This is known as non-rectangular uncertainty.
As explained by Mengmeng Li et al. in Policy Gradient Algorithms for Robust MDP(\text{s}) with Nonrectangular Uncertainty Sets (SIAM 2026), non-rectangular uncertainty sets prevent the decomposition of uncertainty per state-action pair. Because a choice of transition at one state constrains the possible transitions at another, the robust Bellman operator becomes inherently non-convex. Navdeep Kumar et al. note in Non-rectangular Robust MDPs with Normed Uncertainty Sets (neurips 2025) that this coupling forces a harsh trade-off: optimizing over general non-rectangular sets is fundamentally NP-hard, creating an insurmountable barrier for standard optimization tools.
The Stochasticity Barrier in Rich Observations
A mathematically parallel barrier emerges when agents deal with high-dimensional, rich observations (like images) where the underlying environment state is hidden.
If the hidden state dynamics are completely deterministic, tracking the environment is computationally manageable. However, shifting from deterministic to stochastic hidden dynamics introduces a massive computational hurdle.
In On Oracle-Efficient PAC RL with Rich Observations (neurips 2018), Christoph Dann et al. demonstrated that this transition to stochasticity causes a severe computational bottleneck. When hidden transitions are stochastic, the uncertainty about where the agent is compounds over time, coupling the history of observations in a way that makes standard sample-efficient optimization algorithms NP-hard to implement.
Restoring Tractability: Three Strategies
To overcome these computational barriers, researchers have developed three distinct mathematical strategies: convexification, structural restriction, and policy-space optimization.
Transition Uncertainty / Coupling
│
┌────────┴────────┐
▼ ▼
Robust MDPs Rich Observations
(Non-convex) (Stochasticity)
│ │
├─────────────────┤
▼ ▼
Conic Programs / Normed Sets / Oracles
1. Convexification via Regularization
The primary obstacle in Robust MDPs is the non-convexity of the robust Bellman operator. In On the Convex Formulations of Robust Markov Decision Processes (Math. Oper. Res. 2025), Julien Grand-Clément et al. provide a way out.
The authors show that by introducing entropic regularization and applying a clever change of variables, the inherently non-convex robust MDP objective can be smoothed out and mapped directly into tractable conic programs. This formulation allows practitioners to bypass the broken Bellman operator entirely and leverage standard, highly efficient convex optimization solvers.
2. Restricting the Geometry of Uncertainty
If arbitrary non-rectangular uncertainty sets are NP-hard, can we find a mathematically structured subset of non-rectangular sets that are realistic yet tractable?
Navdeep Kumar et al. answered this by analyzing $L_p$-normed uncertainty sets. While general coupled sets remain intractable, the authors proved that enforcing an $L_1$-norm structure bounds the complexity of the interaction between states. This geometric restriction allowed them to develop the first polynomial-time algorithm for robust policy evaluation under non-rectangular uncertainty, breaking a long-standing theoretical bottleneck.
3. Policy-Space Optimization and Oracles
When value-based methods and dynamic programming fail due to coupled transitions, another alternative is to optimize directly in the policy space or leverage specialized optimization oracles.
- Policy Gradients: In Policy Gradient Algorithms for Robust MDP(\text{s}) with Nonrectangular Uncertainty Sets (SIAM 2026), Mengmeng Li et al. bypass value iteration entirely. They design specialized policy gradient algorithms that optimize the policy directly, proving that these methods can achieve global optimality guarantees even when operating within complex, non-rectangular uncertainty sets.
- Oracle-Efficient Algorithms: For the rich-observation setting, Christoph Dann et al. proved in On Oracle-Efficient PAC Reinforcement Learning with Rich Observations (Neural 2018) that standard sample-efficient algorithms (like OLIVE) fail computationally when dynamics become stochastic. To fix this, the authors introduced a new algorithm called VALOR. VALOR circumvents the stochasticity barrier by reducing the reinforcement learning problem to a sequence of standard supervised learning optimization problems, achieving both sample efficiency and computational tractability through an oracle model.
Summary
The frontier of modern reinforcement learning involves moving away from clean, isolated assumptions toward coupled, real-world uncertainty. Whether dealing with the non-rectangularity of robust environments or the stochasticity of hidden states, the core challenge is the same: the breakdown of independent state transitions. By shifting to convex conic formulations, restricting uncertainty to normed geometries, or optimizing directly via policy gradients and oracles, recent literature provides the mathematical toolkits necessary to make robust decision-making computationally viable.
Key Foundational Work
On the convex formulations of robust Markov decision processes (2025) — contributed 4 concept elements to this direction.
On Oracle-Efficient PAC Reinforcement Learning with Rich Observations (2018) — contributed 4 concept elements to this direction.
On Oracle-Efficient PAC RL with Rich Observations (2018) — contributed 3 concept elements to this direction.