@inproceedings{
zhou2023modelfree,
title={Model-Free, Regret-Optimal Best Policy Identification in Online {CMDP}s},
author={Zihan Zhou and Honghao Wei and Lei Ying},
booktitle={OPT 2023: Optimization for Machine Learning},
year={2023},
url={https://openreview.net/forum?id=tfEKwVEmGT}
}
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 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 we discover, called 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 a near-optimal policy with a high probability at the end of learning; and (iii) in the tabular setting, PRI guarantees $\tilde{\mathcal{O}}(\sqrt{K})$ regret and constraint violation, which significantly improves the best existing regret bound $\tilde{\mathcal{O}}(K^{\frac{4}{5}})$  under a  model-free algorithm, where $K$ is the total number of episodes.
Model-Free, Regret-Optimal Best Policy Identification in Online CMDPs
Zihan Zhou Honghao Wei Lei Ying