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.
Introduction
Reinforcement Learning (RL) typically relies on a trial-and-error process to discover optimal policies. While effective in simulated environments like games, this approach poses significant risks in real-world applications such as autonomous driving or industrial control, where exploration errors can lead to catastrophic failures. The standard framework for addressing these concerns is the Constrained Markov Decision Process (CMDP), where an agent seeks to maximize rewards while adhering to safety constraints on expected cumulative costs.
The central challenge in safe RL is safe exploration: learning about an unknown environment without violating safety thresholds. Existing approaches often struggle with a trade-off between safety and performance. Some methods find optimal policies quickly but violate constraints during learning, while others are overly cautious, failing to explore sufficiently and resulting in "linear regret"—staying stuck on a safe but suboptimal baseline policy.
The DOPE Algorithm
We introduce DOPE (Doubly Optimistic and Pessimistic Exploration), a model-based algorithm designed to navigate the exploration-safety trade-off. DOPE manages uncertainty through three primary mechanisms:
- Model Optimism: Within a confidence set of possible environment dynamics, DOPE selects transition probabilities that are most favorable for the reward.
- Reward Optimism: It incorporates an exploration bonus for state-action pairs with high uncertainty, encouraging the agent to visit less-explored regions.
- Constraint Pessimism: To ensure safety, DOPE "hardens" safety constraints by considering the worst-case scenario for costs based on current model uncertainty.
As shown in the comparison above, DOPE is unique in its simultaneous use of model optimism, reward optimism, and constraint pessimism. This combination allows it to achieve zero constraint regret (no violations) while maintaining a competitive objective regret bound.
Theoretical Contributions and Insights
A key theoretical insight of DOPE is that reward optimism alone is insufficient to overcome the paralysis often induced by safety pessimism. By incorporating model optimism, the agent can identify potential paths to higher rewards that justify exploration within safe bounds.
Furthermore, by utilizing Bernstein-style confidence intervals—which account for the variance of the data—DOPE achieves a tighter objective regret bound. Specifically, it reduces the regret by a factor of $\sqrt{|S|}$ compared to previous state-of-the-art safe algorithms like OptPess-LP. DOPE provides a provable zero-violation guarantee, ensuring that safety constraints are satisfied throughout the entire learning process with high probability.
Empirical Evaluation
DOPE was evaluated across three simulated environments:
- Factored CMDP: A basic 3-state environment for benchmarking exploration.
- Media Streaming CMDP: A resource allocation task minimizing video stalls under service rate constraints.
- Inventory Control: A supply chain problem maximizing revenue within a strict budget.
In these simulations, DOPE consistently outperformed the previous state-of-the-art. While earlier optimism-pessimism approaches often failed to learn (exhibiting linear regret), DOPE transitioned rapidly to a square-root regret curve, indicating efficient convergence to the optimal safe policy. Crucially, DOPE maintained zero constraint violations in all tests, whereas purely optimistic algorithms frequently breached safety thresholds.
Conclusion and Future Work
DOPE represents a significant step forward in safe RL, providing a robust framework for learning in unknown environments with strict safety requirements. While currently formulated for tabular RL with discrete states and actions, the principles of "double optimism" and pessimism offer a promising path for scaling to high-dimensional spaces using function approximation. Future work will focus on extending DOPE to continuous control tasks and reducing the dependency on an initial safe baseline policy.
Summary updated