# Model-Free, Regret-Optimal Best Policy Identification in Online CMDPs

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 19 of its 34 references that are in the map.
- First posted on arXiv 27 Sep 2023.

## Builds on (most cited first, 19 of 19)

- [Is Q-learning Provably Efficient?](https://mlsanity.com/paper/1807.03765/) (2018)
- [FLAMBE: Structural Complexity and Representation Learning of Low Rank MDPs](https://mlsanity.com/paper/2006.10814/) (2020)
- [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)
- [Episodic Reinforcement Learning in Finite MDPs: Minimax Lower Bounds Revisited](https://mlsanity.com/paper/2010.03531/) (2020)
- [Learning Policies with Zero or Bounded Constraint Violation for Constrained MDPs](https://mlsanity.com/paper/2106.02684/) (2021)
- [Constrained Upper Confidence Reinforcement Learning](https://mlsanity.com/paper/2001.09377/) (2020)
- [Nearly Minimax Optimal Reinforcement Learning for Discounted MDPs](https://mlsanity.com/paper/2010.00587/) (2020)
- [Constrained episodic reinforcement learning in concave-convex and knapsack settings](https://mlsanity.com/paper/2006.05051/) (2020)
- [i-Sim2Real: Reinforcement Learning of Robotic Policies in Tight Human-Robot Interaction Loops](https://mlsanity.com/paper/2207.06572/) (2022)
- [Provably Efficient Model-Free Constrained RL with Linear Function Approximation](https://mlsanity.com/paper/2206.11889/) (2022)
- [Learning Infinite-Horizon Average-Reward Markov Decision Processes with Constraints](https://mlsanity.com/paper/2202.00150/) (2022)
- [Provably Efficient Model-Free Algorithms for Non-stationary CMDPs](https://mlsanity.com/paper/2303.05733/) (2023)
- [ReLOAD: Reinforcement Learning with Optimistic Ascent-Descent for Last-Iterate Convergence in Constrained MDPs](https://mlsanity.com/paper/2302.01275/) (2023)
- [A Provably-Efficient Model-Free Algorithm for Constrained Markov Decision Processes](https://mlsanity.com/paper/2106.01577/) (2021)
- [Safe Linear Bandits over Unknown Polytopes](https://mlsanity.com/paper/2209.13694/) (2022)
- [Best Policy Identification in Linear MDPs](https://mlsanity.com/paper/2208.05633/) (2022)
- [Markov Decision Processes with Long-Term Average Constraints](https://mlsanity.com/paper/2106.06680/) (2021)
- [Intrinsic Rewards from Self-Organizing Feature Maps for Exploration in Reinforcement Learning](https://mlsanity.com/paper/2302.04125/) (2023)

## Abstract (arXiv)

This paper considers the best policy identification (BPI) problem in online Constrained Markov Decision Processes (CMDPs). We are interested in algorithms that are model-free, have low regret, and identify an approximately optimal policy with a high probability. Existing model-free algorithms for online CMDPs with sublinear regret and constraint violation do not provide any convergence guarantee to an optimal policy and provide only average performance guarantees when a policy is uniformly sampled at random from all previously used policies. In this paper, we develop a new algorithm, named Pruning-Refinement-Identification (PRI), based on a fundamental structural property of CMDPs proved before, which we call limited stochasticity. The property says for a CMDP with N constraints, there exists an optimal policy with at most N stochastic decisions. The proposed algorithm first identifies at which step and in which state a stochastic decision has to be taken and then fine-tunes the distributions of these stochastic decisions. PRI achieves trio objectives: (i) PRI is a model-free algorithm; and (ii) it outputs an approximately optimal policy with a high probability at the end of learning; and (iii) PRI guarantees tildeO(H√K) regret and constraint violation, which significantly improves the best existing regret bound tildeO(H4 √SAK^frac45) under a model-free algorithm, where H is the length of each episode, S is the number of states, A is the number of actions, and the total number of episodes during learning is 2K+tildecal O(K0.25). We further present a matching lower via an example that shows under any online learning algorithm, there exists a well-separated CMDP instance such that either the regret or violation has to be Omega(H√K), which matches the upper bound by a polylogarithmic factor.