# Near-optimal Conservative Exploration in Reinforcement Learning under Episode-wise Constraints

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 36 of its 65 references that are in the map.
- First posted on arXiv 9 Jun 2023.

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

- [Trust Region Policy Optimization](https://mlsanity.com/paper/1502.05477/) (2015)
- [Minimax Regret Bounds for Reinforcement Learning](https://mlsanity.com/paper/1703.05449/) (2017)
- [Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Bounds](https://mlsanity.com/paper/1901.00210/) (2019)
- [Unifying PAC and Regret: Uniform PAC Bounds for Episodic Reinforcement Learning](https://mlsanity.com/paper/1703.07710/) (2017)
- [Policy Finetuning: Bridging Sample-Efficient Offline and Online Reinforcement Learning](https://mlsanity.com/paper/2106.04895/) (2021)
- [Exploration-Exploitation in Constrained MDPs](https://mlsanity.com/paper/2003.02189/) (2020)
- [Safe Policy Improvement with Baseline Bootstrapping](https://mlsanity.com/paper/1712.06924/) (2017)
- [Provably Efficient Safe Exploration via Primal-Dual Policy Optimization](https://mlsanity.com/paper/2003.00534/) (2020)
- [Episodic Reinforcement Learning in Finite MDPs: Minimax Lower Bounds Revisited](https://mlsanity.com/paper/2010.03531/) (2020)
- [Fast active learning for pure exploration in reinforcement learning](https://mlsanity.com/paper/2007.13442/) (2020)
- [Linear Stochastic Bandits Under Safety Constraints](https://mlsanity.com/paper/1908.05814/) (2019)
- [Learning Policies with Zero or Bounded Constraint Violation for Constrained MDPs](https://mlsanity.com/paper/2106.02684/) (2021)
- [Optimistic Policy Optimization with Bandit Feedback](https://mlsanity.com/paper/2002.08243/) (2020)
- [Safe Reinforcement Learning via Curriculum Induction](https://mlsanity.com/paper/2006.12136/) (2020)
- [Stochastic Bandits with Linear Constraints](https://mlsanity.com/paper/2006.10185/) (2020)
- [Conservative Bandits](https://mlsanity.com/paper/1602.04282/) (2016)
- [Conservative Contextual Linear Bandits](https://mlsanity.com/paper/1611.06426/) (2016)
- [Safe Policy Improvement by Minimizing Robust Baseline Regret](https://mlsanity.com/paper/1607.03842/) (2016)
- [Policy Optimization in Adversarial MDPs: Improved Exploration via Dilated Bonuses](https://mlsanity.com/paper/2107.08346/) (2021)
- [Constrained Upper Confidence Reinforcement Learning](https://mlsanity.com/paper/2001.09377/) (2020)
- [Safe Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/2106.06239/) (2021)
- [DOPE: Doubly Optimistic and Pessimistic Exploration for Safe Reinforcement Learning](https://mlsanity.com/paper/2112.00885/) (2021)
- [Planning in Markov Decision Processes with Gap-Dependent Sample Complexity](https://mlsanity.com/paper/2006.05879/) (2020)
- [A Sample-Efficient Algorithm for Episodic Finite-Horizon MDP with Constraints](https://mlsanity.com/paper/2009.11348/) (2020)
- [Provably Efficient Model-Free Constrained RL with Linear Function Approximation](https://mlsanity.com/paper/2206.11889/) (2022)
- [Safe Linear Stochastic Bandits](https://mlsanity.com/paper/1911.09501/) (2019)
- [Kernel-Based Reinforcement Learning: A Finite-Time Analysis](https://mlsanity.com/paper/2004.05599/) (2020)
- [Conservative Exploration in Reinforcement Learning](https://mlsanity.com/paper/2002.03218/) (2020)
- [Improved Algorithms for Conservative Exploration in Bandits](https://mlsanity.com/paper/2002.03221/) (2020)
- [Optimistic Policy Optimization is Provably Efficient in Non-stationary MDPs](https://mlsanity.com/paper/2110.08984/) (2021)

## Built on by (most cited first, 5 of 5)

- [BAGEN: Are LLM Agents Budget-Aware?](https://mlsanity.com/paper/2606.00198/) (2026)
- [Offline Reinforcement Learning for Wireless Network Optimization with Mixture Datasets](https://mlsanity.com/paper/2311.11423/) (2023)
- [Advancing RAN Slicing with Offline Reinforcement Learning](https://mlsanity.com/paper/2312.10547/) (2023)
- [Off-policy Reinforcement Learning with Model-based Exploration Augmentation](https://mlsanity.com/paper/2510.25529/) (2025)
- [Instance-Dependent Regret for CMDPs with Step-Wise Constraints](https://mlsanity.com/paper/2610.02520/) (2026)

## Abstract (arXiv)

This paper investigates conservative exploration in reinforcement learning where the performance of the learning agent is guaranteed to be above a certain threshold throughout the learning process. It focuses on the tabular episodic Markov Decision Process (MDP) setting that has finite states and actions. With the knowledge of an existing safe baseline policy, an algorithm termed as StepMix is proposed to balance the exploitation and exploration while ensuring that the conservative constraint is never violated in each episode with high probability. StepMix features a unique design of a mixture policy that adaptively and smoothly interpolates between the baseline policy and the optimistic policy. Theoretical analysis shows that StepMix achieves near-optimal regret order as in the constraint-free setting, indicating that obeying the stringent episode-wise conservative constraint does not compromise the learning performance. Besides, a randomization-based EpsMix algorithm is also proposed and shown to achieve the same performance as StepMix. The algorithm design and theoretical analysis are further extended to the setting where the baseline policy is not given a priori but must be learned from an offline dataset, and it is proved that similar conservative guarantee and regret can be achieved if the offline dataset is sufficiently large. Experiment results corroborate the theoretical analysis and demonstrate the effectiveness of the proposed conservative exploration strategies.