mlsanityData to 14 Oct 2026

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

arXiv 2309.15395 ↗First posted 27 Sep 2023cs.LGcited by 0

Not on the map. Why?

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.

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

19 of 34 references.

References · 19

  1. 2018Is Q-learning Provably Efficient?cited by 487
  2. 2020FLAMBE: Structural Complexity and Representation Learning of Low Rank MDPscited by 233
  3. 2020Exploration-Exploitation in Constrained MDPscited by 149
  4. 2020Provably Efficient Safe Exploration via Primal-Dual Policy Optimizationcited by 134
  5. 2020Episodic Reinforcement Learning in Finite MDPs: Minimax Lower Bounds Revisitedcited by 106
  6. 2021Learning Policies with Zero or Bounded Constraint Violation for Constrained MDPscited by 80
  7. 2020Constrained Upper Confidence Reinforcement Learningcited by 46
  8. 2020Nearly Minimax Optimal Reinforcement Learning for Discounted MDPscited by 42
  9. 2020Constrained episodic reinforcement learning in concave-convex and knapsack settingscited by 34
  10. 2022i-Sim2Real: Reinforcement Learning of Robotic Policies in Tight Human-Robot Interaction Loopscited by 32
  11. 2022Provably Efficient Model-Free Constrained RL with Linear Function Approximationcited by 31
  12. 2022Learning Infinite-Horizon Average-Reward Markov Decision Processes with Constraintscited by 29
7 more
  1. 2023Provably Efficient Model-Free Algorithms for Non-stationary CMDPscited by 21
  2. 2023ReLOAD: Reinforcement Learning with Optimistic Ascent-Descent for Last-Iterate Convergence in Constrained MDPscited by 20
  3. 2021A Provably-Efficient Model-Free Algorithm for Constrained Markov Decision Processescited by 17
  4. 2022Safe Linear Bandits over Unknown Polytopescited by 14
  5. 2022Best Policy Identification in Linear MDPscited by 4
  6. 2021Markov Decision Processes with Long-Term Average Constraintscited by 3
  7. 2023Intrinsic Rewards from Self-Organizing Feature Maps for Exploration in Reinforcement Learningcited by 1

Built on by

Not cited yet.