# DOPE: Doubly Optimistic and Pessimistic Exploration for Safe Reinforcement Learning

arXiv: https://arxiv.org/abs/2112.00885 · HTML: https://mlsanity.com/paper/2112.00885/

## Key facts

- Cited by 35 papers in the map (data through 14 Oct 2026).
- Builds on 31 of its 62 references that are in the map.
- First posted on arXiv 1 Dec 2021.

## Builds on (most cited first, 30 of 31)

- [Constrained Policy Optimization](https://mlsanity.com/paper/1705.10528/) (2017)
- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [Minimax Regret Bounds for Reinforcement Learning](https://mlsanity.com/paper/1703.05449/) (2017)
- [Reward Constrained Policy Optimization](https://mlsanity.com/paper/1805.11074/) (2018)
- [Risk-Constrained Reinforcement Learning with Percentile Risk Criteria](https://mlsanity.com/paper/1512.01629/) (2015)
- [Projection-Based Constrained Policy Optimization](https://mlsanity.com/paper/2010.03152/) (2020)
- [Unifying PAC and Regret: Uniform PAC Bounds for Episodic Reinforcement Learning](https://mlsanity.com/paper/1703.07710/) (2017)
- [Constrained Reinforcement Learning Has Zero Duality Gap](https://mlsanity.com/paper/1910.13393/) (2019)
- [Exploration-Exploitation in Constrained MDPs](https://mlsanity.com/paper/2003.02189/) (2020)
- [Provably Efficient Safe Exploration via Primal-Dual Policy Optimization](https://mlsanity.com/paper/2003.00534/) (2020)
- [Sample Complexity of Episodic Fixed-Horizon Reinforcement Learning](https://mlsanity.com/paper/1510.08906/) (2015)
- [Online Convex Optimization with Stochastic Constraints](https://mlsanity.com/paper/1708.03741/) (2017)
- [Linear Stochastic Bandits Under Safety Constraints](https://mlsanity.com/paper/1908.05814/) (2019)
- [Learning Adversarial MDPs with Bandit Feedback and Unknown Transition](https://mlsanity.com/paper/1912.01192/) (2019)
- [Learning Policies with Zero or Bounded Constraint Violation for Constrained MDPs](https://mlsanity.com/paper/2106.02684/) (2021)
- [Stochastic Bandits with Linear Constraints](https://mlsanity.com/paper/2006.10185/) (2020)
- [Online Convex Optimization with Time-Varying Constraints](https://mlsanity.com/paper/1702.04783/) (2017)
- [Online convex optimization for cumulative constraints](https://mlsanity.com/paper/1802.06472/) (2018)
- [Constrained Upper Confidence Reinforcement Learning](https://mlsanity.com/paper/2001.09377/) (2020)
- [A Sample-Efficient Algorithm for Episodic Finite-Horizon MDP with Constraints](https://mlsanity.com/paper/2009.11348/) (2020)
- [Learning with Safety Constraints: Sample Complexity of Reinforcement Learning for Constrained MDPs](https://mlsanity.com/paper/2008.00311/) (2020)
- [An Efficient Pessimistic-Optimistic Algorithm for Stochastic Linear Bandits with General Constraints](https://mlsanity.com/paper/2102.05295/) (2021)
- [Stage-wise Conservative Linear Bandits](https://mlsanity.com/paper/2010.00081/) (2020)
- [Safe Linear Stochastic Bandits](https://mlsanity.com/paper/1911.09501/) (2019)
- [Learning in Markov Decision Processes under Constraints](https://mlsanity.com/paper/2002.12435/) (2020)
- [Safe Convex Learning under Uncertain Constraints](https://mlsanity.com/paper/1903.04626/) (2019)
- [Safe Online Convex Optimization with Unknown Linear Safety Constraints](https://mlsanity.com/paper/2111.07430/) (2021)
- [Throughput Optimal Decentralized Scheduling of Multi-Hop Networks with End-to-End Deadline Constraints: Unreliable Links](https://mlsanity.com/paper/1606.01608/) (2016)
- [Trading Safety Versus Performance: Rapid Deployment of Robotic Swarms with Robust Performance Constraints](https://mlsanity.com/paper/1511.06982/) (2015)
- [Decentralized Control via Dynamic Stochastic Prices: The Independent System Operator Problem](https://mlsanity.com/paper/1605.08926/) (2016)

## Built on by (most cited first, 30 of 35)

- [A Survey of Constraint Formulations in Safe Reinforcement Learning](https://mlsanity.com/paper/2402.02025/) (2024)
- [Last-Iterate Convergent Policy Gradient Primal-Dual Methods for Constrained MDPs](https://mlsanity.com/paper/2306.11700/) (2023)
- [ReLOAD: Reinforcement Learning with Optimistic Ascent-Descent for Last-Iterate Convergence in Constrained MDPs](https://mlsanity.com/paper/2302.01275/) (2023)
- [Distributionally Robust Constrained Reinforcement Learning under Strong Duality](https://mlsanity.com/paper/2406.15788/) (2024)
- [A safe exploration approach to constrained Markov decision processes](https://mlsanity.com/paper/2312.00561/) (2023)
- [Near-Optimal Policy Identification in Robust Constrained Markov Decision Processes via Epigraph Form](https://mlsanity.com/paper/2408.16286/) (2024)
- [Directional Optimism for Safe Linear Bandits](https://mlsanity.com/paper/2308.15006/) (2023)
- [Constrained Reinforcement Learning Under Model Mismatch](https://mlsanity.com/paper/2405.01327/) (2024)
- [Cancellation-Free Regret Bounds for Lagrangian Approaches in Constrained Markov Decision Processes](https://mlsanity.com/paper/2306.07001/) (2023)
- [Provably Learning Nash Policies in Constrained Markov Potential Games](https://mlsanity.com/paper/2306.07749/) (2023)
- [Safe Posterior Sampling for Constrained MDPs with Bounded Constraint Violation](https://mlsanity.com/paper/2301.11547/) (2023)
- [A Policy Gradient Primal-Dual Algorithm for Constrained MDPs with Uniform PAC Guarantees](https://mlsanity.com/paper/2401.17780/) (2024)
- [Provably Efficient RL under Episode-Wise Safety in Constrained MDPs with Linear Function Approximation](https://mlsanity.com/paper/2502.10138/) (2025)
- [Safe Exploration via Policy Priors](https://mlsanity.com/paper/2601.19612/) (2026)
- [Near-optimal Conservative Exploration in Reinforcement Learning under Episode-wise Constraints](https://mlsanity.com/paper/2306.06265/) (2023)
- [Safe Reinforcement Learning for Constrained Markov Decision Processes with Stochastic Stopping Time](https://mlsanity.com/paper/2403.15928/) (2024)
- [A Retention-Centric Framework for Continual Learning with Guaranteed Model Developmental Safety](https://mlsanity.com/paper/2410.03955/) (2024)
- [Pure Exploration for Constrained Best Mixed Arm Identification with a Fixed Budget](https://mlsanity.com/paper/2405.15090/) (2024)
- [Near-Optimal Primal-Dual Algorithm for Learning Linear Mixture CMDPs with Adversarial Rewards](https://mlsanity.com/paper/2603.27884/) (2026)
- [Learning Weakly Communicating Average-Reward CMDPs: Strong Duality and Improved Regret](https://mlsanity.com/paper/2605.11586/) (2026)
- [Robust Shielding for Safe Reinforcement Learning](https://mlsanity.com/paper/2606.00270/) (2026)
- [Online Resource Allocation in Episodic Markov Decision Processes](https://mlsanity.com/paper/2305.10744/) (2023)
- [Structured Reinforcement Learning for Media Streaming at the Wireless Edge](https://mlsanity.com/paper/2404.07315/) (2024)
- [Constrained Meta Reinforcement Learning with Provable Test-Time Safety](https://mlsanity.com/paper/2601.21845/) (2026)
- [Near-Optimal Sample Complexity for Online Constrained MDPs](https://mlsanity.com/paper/2602.15076/) (2026)
- [Golden Handcuffs make safer AI agents](https://mlsanity.com/paper/2604.13609/) (2026)
- [A Domain-Based Taxonomy of Jailbreak Vulnerabilities in Large Language Models](https://mlsanity.com/paper/2504.04976/) (2025)
- [Provably Safe Reinforcement Learning for Stochastic Reach-Avoid Problems with Entropy Regularization](https://mlsanity.com/paper/2601.08646/) (2026)
- [Bi-Level Online Provisioning and Scheduling with Switching Costs and Cross-Level Constraints](https://mlsanity.com/paper/2601.18936/) (2026)
- [MC-CPO: Mastery-Conditioned Constrained Policy Optimization for Pedagogically Safe Intelligent Tutoring Systems](https://mlsanity.com/paper/2604.04251/) (2026)

## Abstract (arXiv)

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 tildeO(|S|√|A| K) without violating the safety constraints during learning, where |S| is the number of states, |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.