DOPE: Doubly Optimistic and Pessimistic Exploration for Safe Reinforcement Learning

Archana Bura, Aria Hasanzadezonuzy, Dileep Kalathil, Srinivas Shakkottai, Jean-Francois Chamberland

Introduction

In standard Reinforcement Learning (RL), an agent learns by trial and error, often taking risky actions to explore unknown parts of an environment. However, in many real-world applications—such as autonomous driving or medical treatment—this "move fast and break things" approach is unacceptable. The agent must ensure that it never violates safety constraints, even while it is still learning the environment's dynamics.

This paper tackles the problem of Safe Exploration within the framework of a finite-horizon Constrained Markov Decision Process (CMDP). The challenge is two-fold: the agent must explore to find the optimal policy (the exploration-exploitation trade-off), while strictly satisfying safety requirements modeled as constraints on expected cumulative costs. Previous approaches often fell into two traps: they either allowed constraint violations during the learning phase (optimistic methods) or were so fearful of violations that they failed to explore effectively, resulting in poor performance (pessimistic methods).

To resolve this, the authors introduce DOPE (Doubly Optimistic and Pessimistic Exploration), a novel model-based RL algorithm that achieves state-of-the-art regret bounds and significantly better empirical performance than previous safe RL methods.

The DOPE Approach: Balancing Optimism and Pessimism

DOPE operates in an episodic setting and relies on a carefully balanced strategy of "Double Optimism" and "Pessimism." The most significant insight of the paper is that model optimism alone isn't enough to overcome the "braking" effect of pessimistic constraints.

To encourage exploration while guaranteeing safety, DOPE utilizes three core mechanisms:

  1. Model Optimism: Similar to standard "Optimism in the Face of Uncertainty" (OFU) algorithms, DOPE maintains a confidence set of possible transition models and chooses the one that appears most favorable for maximizing rewards.
  2. Reward Optimism: In addition to model optimism, DOPE adds an exploration bonus to the reward function for state-action pairs that have not been visited frequently. This "double dose" of optimism incentivizes the agent to be brave enough to explore, even when safety constraints are acting conservatively.
  3. Constraint Pessimism: To ensure strict safety, the algorithm "hardens" the constraints. It treats the safety limits conservatively, aiming to stay well below the actual limit based on its current uncertainty. As the agent gathers more data and its uncertainty shrinks, these pessimistic bounds naturally relax.

Furthermore, the algorithm assumes access to an "inexpert" but safe baseline policy ($\pi_b$). For the initial episodes, the agent relies on this baseline until it has gathered enough data to mathematically guarantee a safe transition to its own learned exploratory policy.

Comparison of DOPE against prior safe RL algorithms.

Experimental Setup and Results

The authors evaluated DOPE on two simulated CMDP environments designed to test safe exploration: a Factored CMDP (a 3-state environment balancing safe moves against high-reward/high-risk moves) and a Media Streaming CMDP (a resource management task minimizing video outages while limiting expensive fast-service usage).

The results demonstrate DOPE's superiority in both safety and efficiency:

  • Zero Constraint Regret: In both simulations, DOPE maintained zero constraint violations throughout the entire learning process. In contrast, standard optimistic algorithms (like OptCMDP) frequently violated safety limits.
  • Faster Convergence: DOPE reached the efficient "square-root regret" phase much faster than its competitors. In the Media Streaming environment, DOPE's objective regret was significantly lower than the previous best safe algorithm, OptPessLP, which remained stuck in a linear regret phase for a long duration due to excessive pessimism.
  • Improved Theoretical Bounds: DOPE improves the objective regret bound by a factor of $\sqrt{|\mathcal{S}|}$ (where $|\mathcal{S}|$ is the number of states) compared to OptPessLP. The authors prove that DOPE achieves an objective regret of $\tilde{O}(\frac{H^3}{\bar{C}-\bar{C}_b}|\mathcal{S}|\sqrt{|\mathcal{A}|K})$ with high probability, while maintaining zero constraint violations.

Limitations and Future Work

While DOPE presents a significant step forward for safe RL, the current work is restricted to "tabular" RL, meaning it is best suited for environments with a relatively small, discrete number of states and actions. Additionally, the algorithm requires a known safe baseline policy to initialize learning. While such safe modes are often available in engineering systems, finding them in completely unknown environments remains a challenge.

For future work, the authors plan to extend the DOPE framework to incorporate function approximation (e.g., using Neural Networks). This extension would allow the algorithm to scale to much larger, continuous, and more complex real-world problems.

Summary updated

Abstract

Safe reinforcement learning is extremely challenging--not only must the agent explore an unknown environment, it must do so while ensuring no safety constraint violations. We formulate this safe reinforcement learning (RL) problem using the framework of a finite-horizon Constrained Markov Decision Process (CMDP) with an unknown transition probability function, where we model the safety requirements as constraints on the expected cumulative costs that must be satisfied during all episodes of learning. We propose a model-based safe RL algorithm that we call Doubly Optimistic and Pessimistic Exploration (DOPE), and show that it achieves an objective regret $\tilde{O}(|\mathcal{S}|\sqrt{|\mathcal{A}| K})$ without violating the safety constraints during learning, where $|\mathcal{S}|$ is the number of states, $|\mathcal{A}|$ is the number of actions, and $K$ is the number of learning episodes. Our key idea is to combine a reward bonus for exploration (optimism) with a conservative constraint (pessimism), in addition to the standard optimistic model-based exploration. DOPE is not only able to improve the objective regret bound, but also shows a significant empirical performance improvement as compared to earlier optimism-pessimism approaches.
BibTeX
@inproceedings{bura2022dope,
  author = {Archana Bura and Aria Hasanzadezonuzy and Dileep Kalathil and Srinivas Shakkottai and Jean-Francois Chamberland},
  title = {{DOPE: Doubly Optimistic and Pessimistic Exploration for Safe Reinforcement Learning}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2022},
  url = {https://openreview.net/forum?id=U4BUMoVTrB2},
}
Figure