Beyond Rectangularity in Robust Reinforcement Learning

106 concepts73 papers1 proposal

When training reinforcement learning (RL) agents for real-world deployment, simulators are indispensable. However, a well-known challenge arises: the "sim-to-real gap." Minor discrepancies in friction, mass, or actuator noise between the simulator and the physical world can cause an agent's performance to collapse.

To bridge this gap, Robust Markov Decision Processes (RMDPs) optimize for the worst-case scenario within a predefined uncertainty set of possible transition dynamics. While this framework provides strong safety guarantees, standard implementations suffer from a severe limitation known as the rectangularity assumption.

The Intuition of Rectangularity

To understand rectangularity, imagine an adversarial game. The agent tries to maximize its long-term reward, while an imaginary adversary manipulates the environment's transition probabilities to make things as difficult as possible.

In a standard state-action $(s,a)$-rectangular setup, the adversary is granted total freedom: it can choose the worst possible transition distribution for every single state-action pair completely independently of all others. As Yue Wang et al. note, this structural choice decouples the environment's uncertainty across the state space.

Standard (s,a)-Rectangular Uncertainty:
[ State 1, Action A ] ---> Adversary picks worst-case transition independently
[ State 1, Action B ] ---> Adversary picks worst-case transition independently
[ State 2, Action A ] ---> Adversary picks worst-case transition independently

Why do we make this assumption? The answer is purely computational. By treating each state-action pair as an independent silo, the complex global minimax optimization problem decomposes into local, independent sub-problems. As Kishan Panaganti et al. highlight, this decomposition allows researchers to compute robust Bellman updates efficiently, making robust RL computationally tractable even when scaling to large state spaces with function approximation.

The Price of Independence: Compounding Pessimism

While mathematically convenient, rectangularity introduces a major flaw: it assumes an unrealistic, omnipotent adversary.

In the real world, environmental uncertainties are highly correlated. If a robot's joint suffers from physical degradation, that degradation systematically alters the transitions across all states and actions. Under a rectangular assumption, however, the adversary can choose a worst-case scenario where the joint behaves as if it is loose in state $A$, but suddenly behaves as if it is jammed in state $B$.

As Esther Derman et al. argue, this independence allows the adversary to manipulate the environment in ways that violate basic physical or logical constraints. By forcing the agent to prepare for statistically improbable, physically impossible joint-failure combinations, rectangular models suffer from excessive conservatism or compounding pessimism (Cheng Tang et al.; Navdeep Kumar et al.).

Early work by Olivier Buffet et al. and Mohammad Ghavamzadeh et al. demonstrated that this localized view of uncertainty prevents the agent from identifying highly beneficial policy changes because it is effectively "paralyzed" by an overly hostile model. Furthermore, Andrea Tirinzoni et al. point out that treating transitions independently prevents an agent from generalizing learned transition dynamics from visited states to similar, unvisited regions of the environment.

The Rectangularity Spectrum

To mitigate this pessimism without completely sacrificing tractability, researchers developed a hierarchy of uncertainty structures.

   (s,a)-Rectangular             s-Rectangular               Non-Rectangular
=======================     =======================     =======================
 Uncertainty completely      Uncertainty coupled         Uncertainty globally
 independent for every      across actions within       coupled across all
 state-action pair.          each individual state.      states and actions.

A common intermediate step is state ($s$)-rectangularity. Instead of decoupling every single action, $s$-rectangularity forces the adversary's perturbations to be consistent across all actions within a given state.

Pierre Clavier et al. and Zhenghao Li et al. explain that this approach provides a much more realistic model for physical or economic systems where external environmental factors—such as weather or market demand—remain constant regardless of the specific action the agent chooses to execute. However, this tighter coupling comes with a theoretical catch: Pierre Clavier et al. demonstrate that maintaining robustness under state-rectangular sets necessitates handling stochastic optimal policies rather than deterministic ones, increasing the underlying mathematical complexity.

Embracing Coupled and Non-Rectangular Uncertainty

The frontier of robust RL focuses on breaking the rectangularity barrier entirely by modeling coupled uncertainty. If the true environment varies based on a few global parameters (like wind speed or surface friction), the uncertainty set should constrain those parameters globally, linking transitions across the entire state space.

The authors of Multi-Environment POMDPs: Discrete Model Uncertainty Under Partial Observability show that modeling uncertainty across a finite set of discrete environments naturally captures these global correlations, preventing the physically unrealistic models produced by independent state assumptions.

To implement this in continuous or large-scale settings, researchers use structured representations:

  • Latent Factor Constraints: Cheng Tang et al. propose applying robustness constraints to latent transition factors rather than independent state-action pairs. This allows the agent to recognize structural correlations across the environment, eliminating compounding pessimism.
  • Linear Mixtures: Zhishuai Liu et al. model the environment as a linear mixture of known base components, placing the uncertainty set directly on the mixture weights. This forces the adversary to choose a valid, globally consistent environment.
  • Geometric and Normed Sets: Rather than treating sets as boxes (rectangles), researchers use ellipsoids or $L_p$ norms to bind uncertainties together. Qiuhao Wang et al. demonstrate that capturing these dependencies through non-rectangular ambiguity sets yields superior real-world performance in complex tasks like inventory management.

Overcoming the Computational Bottleneck

If non-rectangular uncertainty sets are more realistic and less conservative, why did the field anchor to rectangularity for so long?

The reason is that non-rectangular constraints break the local nature of dynamic programming. When uncertainty is coupled globally, an action taken in state $A$ consumes part of the "uncertainty budget," which directly alters the worst-case transitions available to the adversary in state $B$. This coupling destroys the standard robust Bellman equation, often rendering the optimization problem NP-hard.

Recent algorithmic breakthroughs are overcoming this bottleneck through clever mathematical reformulations:

  1. Frequency Regularization: Uri Gadot et al. proved a surprising mathematical equivalence: coupling reward uncertainty across the entire state-action space is dual to regularizing the policy's state visitation frequency. This insight allows designers to solve non-rectangular problems using a provably convergent policy gradient algorithm without explicitly tracking the global adversary.
  2. Tractable Subclasses: Navdeep Kumar et al. bypassed the traditional NP-hardness barrier by identifying a specific, tractable class of $L_p$-normed uncertainty sets. They provided the first polynomial-time algorithm for robust policy evaluation in $L_1$-normed non-rectangular scenarios, proving that global coupling does not always require prohibitive computational overhead.

By moving beyond rectangularity, modern robust RL shifts the focus from preparing for an impossible, omnipotent adversary to planning against realistic, structurally bound environmental shifts.

Key Foundational Work

Robust Planning with (L)RTDP (2005) — contributed 2 concept elements to this direction.
History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 75 papers
  2. Version 1 · 2026-10-04 · 97 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_state_action_rectangularity_a9c621bb,
  title = {state-action rectangularity},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/state-action-rectangularity/rdr_a9c621bbb4974431a2ebde4b822bbf73},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 2, frozen text):

@misc{lacuna_state_action_rectangularity_a9c621bb_v2,
  title = {state-action rectangularity},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/state-action-rectangularity/rdr_a9c621bbb4974431a2ebde4b822bbf73/v/2},
  note = {Version 2, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake