Achieving $\tilde{O}(1/\epsilon)$ Sample Complexity for Constrained Markov Decision Process

arXiv:2402.16324v1 Announce Type: new
Abstract: We consider the reinforcement learning problem for the constrained Markov decision process (CMDP), which plays a central role in satisfying safety or resource constraints in sequential learning and decision-making. In this problem, we are given finite resources and a MDP with unknown transition probabilities. At each stage, we take an action, collecting a reward and consuming some resources, all assumed to be unknown and need to be learned over time. In this work, we take …

abstract arxiv complexity constraints cs.lg decision epsilon making markov math.oc process reinforcement reinforcement learning resources role safety sample transition type