Recoverability in General Reinforcement Learning

You are reading version 1 of this direction, frozen 2026-10-04. The latest version is version 2.

Version 1 of 28 papers19 conceptsfrozen 2026-10-04

In the standard textbook version of reinforcement learning, an agent lives in a world of clean slates. If it crashes a car or fails a task, the environment simply resets, and the agent tries again from a pristine starting state. But real-world environments—and the complex, non-Markovian mathematical models that describe them—rarely offer such easy forgiveness.

In these "general" environments, a single mistake can be permanent. This has led researchers to identify recoverability as the fundamental property that determines whether an agent can truly learn to behave optimally over time.

The Problem of Permanent Mistakes

Most theoretical guarantees in reinforcement learning, such as achieving sublinear regret (where the gap between the agent's performance and the optimal policy vanishes), rely on the assumption that the agent can eventually make up for early errors. However, as Jan Leike, Tor Lattimore, and Marcus Hutter argue in Thompson Sampling is Asymptotically Optimal in General Environments, this is only possible if the environment is "recoverable."

Imagine an agent exploring a labyrinth. In a recoverable environment, if the agent takes a wrong turn into a dead end, it can eventually turn around and find the exit. In a non-recoverable environment, that wrong turn might lead into an "inescapable trap"—a pit from which no sequence of actions can ever return the agent to a high-reward state.

If an agent falls into such a trap during its exploration phase, it might eventually learn the "optimal" way to behave inside the trap, but it can never compensate for the massive loss of reward incurred by falling in. Mathematically, this means the agent's regret will grow linearly forever, making it impossible to achieve true asymptotic optimality in the broadest sense.

Why Thompson Sampling Needs Forgiveness

Thompson Sampling is a classic algorithm that balances exploration and exploitation by sampling a hypothesis about the world and acting as if it were true. While it is highly effective, its success in complex, non-Markovian settings is tethered to the recoverability principle.

As explored in On Thompson Sampling and Asymptotic Optimality, Thompson Sampling is "objective" in that it eventually converges to the best possible policy. However, if the environment lacks recoverability, that "best possible" policy might be a consolation prize. The agent might become optimal relative to its current, compromised position (e.g., "how to survive best inside the trap"), but it cannot erase the fact that it failed the larger task. For Thompson Sampling to be truly optimal, the environment must be structured so that early exploration mistakes do not permanently bar the agent from reaching the highest-reward states.

Recoverability in Practice: The "Reset" Cheat

The challenge of recoverability isn't just a theoretical curiosity; it shows up in how we train deep RL agents today. In An Empirical Study of Deep Reinforcement Learning in Continuing Tasks, Zheqing Zhu and colleagues observe a curious behavior in "continuing" tasks—those without natural breaks or restarts.

When environments allow for resets but impose a low cost for doing so, agents often learn to "cheat." Instead of learning a robust recovery strategy to fix a mistake, the agent will intentionally trigger a failure to force a reset to a high-reward initial state. This behavior is a direct response to a lack of recoverability: if the agent doesn't know how to get back to a good state from a bad one, it simply gives up and starts over. This prevents the development of agents that can handle long-term, uninterrupted interactions.

The Imitation Gap

Recoverability also plays a crucial role in how agents learn from humans. In imitation learning, an agent tries to match the behavior of an expert. But what happens when the agent makes a small mistake and drifts off the expert's path?

Gokul Swamy and J. Andrew Bagnell show in Of Moments and Matching: A Game-Theoretic Framework for Closing the Imitation Gap that the "imitation gap"—the difference in performance between the expert and the learner—is heavily dependent on recoverability. In highly recoverable environments, an agent that makes a mistake can easily find its way back to the expert's distribution of states. In these cases, simple algorithms can achieve very tight performance bounds. Without recoverability, a single deviation can lead to a cascading failure where the agent never sees an expert example again.

Summary

Recoverability is the bridge between theoretical RL and the messy reality of the world. It is the property that allows an agent to learn from its mistakes rather than being defined by them. Whether proving the optimality of Thompson Sampling or training robots for continuing tasks, understanding how easily an agent can "get back to good" is essential for building systems that can operate outside of perfectly reset-able simulations.

Papers in this version

History & citationVersion 2 · 2026-10-04

Current · Permanent link

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

Latest version (a living page):

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

This exact version (version 1, frozen text):

@misc{lacuna_recoverability_in_general_reinforcement__5b57f827_v1,
  title = {Recoverability in General Reinforcement Learning},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/recoverability-in-general-reinforcement-learning/rdr_5b57f827251e4243ba9eb4a8ed62d986/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}