mlsanityData to 7 Oct 2026

A Sample-Efficient Algorithm for Episodic Finite-Horizon MDP with Constraints

arXiv 2009.11348 ↗First posted 23 Sep 2020cs.LG cs.AI cs.SYcited by 34

Not on the map. Why?

Abstract (arXiv)

Constrained Markov Decision Processes (CMDPs) formalize sequential decision-making problems whose objective is to minimize a cost function while satisfying constraints on various cost functions. In this paper, we consider the setting of episodic fixed-horizon CMDPs. We propose an online algorithm which leverages the linear programming formulation of finite-horizon CMDP for repeated optimistic planning to provide a probably approximately correct (PAC) guarantee on the number of episodes needed to ensure an ε-optimal policy, i.e., with resulting objective value within ε of the optimal value and satisfying the constraints within ε-tolerance, with probability at least 1-δ. The number of episodes needed is shown to be of the order tildeObig(frac|S||A|C2H2ε2logfrac1δbig), where C is the upper bound on the number of possible successor states for a state-action pair. Therefore, if C ll |S|, the number of episodes needed have a linear dependence on the state and action space sizes |S| and |A|, respectively, and quadratic dependence on the time horizon H.

Key facts. Cited by 34 papers in the map (data through 7 Oct 2026). First posted on arXiv 23 Sep 2020.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 8; 2022: 5; 2023: 12; 2024: 6; 2025: 2; 2026: 1.

34 papers.

Sort:

By area:

  1. 2022A Review of Safe Reinforcement Learning: Methods, Theory and Applicationscited by 169
  2. 2021Achieving Zero Constraint Violation for Constrained Reinforcement Learning via Primal-Dual Approachcited by 46
  3. 2022Near-Optimal Sample Complexity Bounds for Constrained MDPscited by 36
  4. 2021DOPE: Doubly Optimistic and Pessimistic Exploration for Safe Reinforcement Learningcited by 34
  5. 2021Safe Reinforcement Learning with Linear Function Approximationcited by 33
  6. 2022Learning Infinite-Horizon Average-Reward Markov Decision Processes with Constraintscited by 29
  7. 2022Provably Efficient Model-Free Constrained RL with Linear Function Approximationcited by 29
  8. 2023Last-Iterate Convergent Policy Gradient Primal-Dual Methods for Constrained MDPscited by 27
  9. 2023Long-Term Fairness with Unknown Dynamicscited by 25
  10. 2021Concave Utility Reinforcement Learning with Zero-Constraint Violationscited by 18
  11. 2021A Provably-Efficient Model-Free Algorithm for Constrained Markov Decision Processescited by 17
  12. 2023A Near-Optimal Algorithm for Safe Reinforcement Learning Under Instantaneous Hard Constraintscited by 15
22 more
  1. 2023Provably Efficient Generalized Lagrangian Policy Optimization for Safe Multi-Agent Reinforcement Learningcited by 13
  2. 2023Learning to Make Adherence-Aware Advicecited by 13
  3. 2021Model-Free Reinforcement Learning for Optimal Control of MarkovDecision Processes Under Signal Temporal Logic Specificationscited by 10
  4. 2023Provably Safe Reinforcement Learning with Step-wise Violation Constraintscited by 10
  5. 2023Online Restless Multi-Armed Bandits with Long-Term Fairness Constraintscited by 10
  6. 2022Safe Exploration Incurs Nearly No Additional Sample Complexity for Reward-free RLcited by 9
  7. 2023Safe Posterior Sampling for Constrained MDPs with Bounded Constraint Violationcited by 6
  8. 2023Anytime-Constrained Reinforcement Learningcited by 5
  9. 2023Horizon-free Reinforcement Learning in Adversarial Linear Mixture MDPscited by 4
  10. 2023Near-optimal Conservative Exploration in Reinforcement Learning under Episode-wise Constraintscited by 4
  11. 2024Confident Natural Policy Gradient for Local Planning in qπ-realizable Constrained MDPscited by 4
  12. 2021Markov Decision Processes with Long-Term Average Constraintscited by 3
  13. 2023Think Before You Duel: Understanding Complexities of Preference Learning under Constrained Resourcescited by 3
  14. 2025Near-Optimal Sample Complexity Bounds for Constrained Average-Reward MDPscited by 3
  15. 2024Safe Reinforcement Learning using Finite-Horizon Gradient-based Estimationcited by 2
  16. 2026Policy Gradient Primal-Dual Method for Safe Reinforcement Learning from Human Feedbackcited by 2
  17. 2024How does Your RL Agent Explore? An Optimal Transport Analysis of Occupancy Measure Trajectoriescited by 1
  18. 2024Structured Reinforcement Learning for Media Streaming at the Wireless Edgecited by 1
  19. 2024Provably Efficient Exploration in Inverse Constrained Reinforcement Learningcited by 1
  20. 2025Addressing Finite-Horizon MDPs via Low-Rank Tensor Value Approximationcited by 1
  21. 2021Reinforcement Learning for Finite-Horizon Restless Multi-Armed Multi-Action Banditscited by 0
  22. 2024Capacity-Aware Planning and Scheduling in Budget-Constrained Multi-Agent MDPs: A Meta-RL Approachcited by 0