Near Optimal Exploration-Exploitation in Non-Communicating Markov Decision Processes

Ronan Fruit, Matteo Pirotta, Alessandro Lazaric

Reinforcement Learning (RL) theory traditionally relies on the assumption that environments are "communicating"—meaning any state can eventually be reached from any other. However, real-world environments often contain "traps" or physically impossible configurations that violate this assumption. This paper, presented at NeurIPS 2018, introduces TUCRL, the first RL algorithm to achieve sub-linear regret in finite Markov Decision Processes (MDPs) without requiring prior knowledge of the environment's reachability structure.

The Problem: The Optimism Trap

Standard RL algorithms, such as UCRL2, operate on the "Optimism in the Face of Uncertainty" (OFU) principle. They assume that unvisited states might contain high rewards and will persistently attempt to reach them. In a non-communicating MDP, where some states are unreachable, this optimism becomes a liability. The algorithm may spend an infinite amount of time trying to reach impossible states, leading to linear regret—a state of perpetual failure to learn the optimal policy.

Figure 3: Examples of unreachable states in Breakout and Mountain Car environments. In Mountain Car, certain position-velocity combinations are physically impossible to achieve.

As shown in the figure above, even simple benchmarks like Mountain Car have regions of the state space that are unreachable. Without a mechanism to recognize these boundaries, an agent's exploration remains inefficient.

Methodology: Truncated Upper-Confidence for RL (TUCRL)

To overcome the optimism trap, the authors propose TUCRL. It builds upon the standard UCRL framework but introduces a critical "truncation" mechanism to handle misspecified state spaces:

  1. Empirical Partitioning: The algorithm tracks states it has successfully visited ($S^C_k$) versus those it has not ($S^T_k$).
  2. Truncated Transitions: It estimates the maximum plausible probability of transitioning from a visited state to an unvisited one. If this probability falls below a threshold that decreases as more data is collected, the algorithm "truncates" that transition, effectively treating the unvisited state as unreachable.
  3. Periodic Re-evaluation: To avoid permanently ignoring difficult-to-reach but accessible states, TUCRL periodically resets these truncations, allowing for phases of "aggressive exploration."
  4. Truncated EVI: A modified version of Extended Value Iteration (EVI) is used to solve the optimistic planning problem over these restricted, reachable state spaces.

Key Results and Empirical Success

The authors derive a regret bound of $\widetilde{O}(D^{\texttt{C}} \sqrt{Γ^{\texttt{C}} S^{\texttt{C}} AT})$. Crucially, $D^C$ represents the diameter of only the communicating (reachable) portion of the MDP, rather than the entire (potentially infinite) space. This allows TUCRL to adapt to the actual structure of the environment.

Figure 6: Regret comparison between TUCRL, UCRL, and SCAL. In environments with unreachable states, UCRL suffers from linear regret, while TUCRL successfully achieves sub-linear regret.

Empirical evaluations in domains like the "Taxi" benchmark (modified with unreachable states) demonstrate that while standard UCRL fails to learn, TUCRL successfully identifies the reachable optimal policy. The algorithm effectively "shrinks" the state space to the relevant reachable components, making it robust to "broken" or overly broad state space definitions.

Conclusion and Future Work

TUCRL represents a significant step forward in making RL algorithms more robust to real-world complexities. It is the first computationally tractable OFU algorithm that adapts to an MDP's nature without prior structural knowledge. Future work remains to extend these proofs to continuous state-action spaces and to investigate if regret can scale with the "bias span" rather than the diameter, further improving efficiency in complex environments.

Summary updated

BibTeX
@inproceedings{fruit2018near,
  author = {Ronan Fruit and Matteo Pirotta and Alessandro Lazaric},
  title = {{Near Optimal Exploration-Exploitation in Non-Communicating Markov Decision Processes}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2018},
  url = {https://openreview.net/forum?id=Sk-7YIW_bH},
}
Figure