mlsanityData to 7 Oct 2026

Constrained episodic reinforcement learning in concave-convex and knapsack settings

arXiv 2006.05051 ↗First posted 9 Jun 2020cs.LG cs.AI cs.DScited by 33

Not on the map. Why?

Abstract (arXiv)

We propose an algorithm for tabular episodic reinforcement learning with constraints. We provide a modular analysis with strong theoretical guarantees for settings with concave rewards and convex constraints, and for settings with hard constraints (knapsacks). Most of the previous work in constrained reinforcement learning is limited to linear constraints, and the remaining work focuses on either the feasibility question or settings with a single episode. Our experiments demonstrate that the proposed algorithm significantly outperforms these approaches in existing constrained episodic environments.

Key facts. Cited by 33 papers in the map (data through 7 Oct 2026). First posted on arXiv 9 Jun 2020.

Builds on

No reference list yet.

Built on by

Cited by year

Citing papers per year: 2021: 5; 2022: 7; 2023: 10; 2024: 5; 2025: 6.

33 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. 2022Trustworthy Reinforcement Learning Against Intrinsic Vulnerabilities: Robustness, Safety, and Generalizabilitycited by 32
  5. 2022Challenging Common Assumptions in Convex Reinforcement Learningcited by 29
  6. 2022Provably Efficient Model-Free Constrained RL with Linear Function Approximationcited by 29
  7. 2021A Simple Reward-free Approach to Constrained Reinforcement Learningcited by 28
  8. 2023Last-Iterate Convergent Policy Gradient Primal-Dual Methods for Constrained MDPscited by 27
  9. 2023Long-Term Fairness with Unknown Dynamicscited by 25
  10. 2023Provably Efficient Model-Free Algorithms for Non-stationary CMDPscited by 21
  11. 2025Knapsack RL: Unlocking Exploration of LLMs via Optimizing Budget Allocationcited by 21
  12. 2021Provably Efficient Algorithms for Multi-Objective Competitive RLcited by 20
21 more
  1. 2021Concave Utility Reinforcement Learning with Zero-Constraint Violationscited by 18
  2. 2021A Provably-Efficient Model-Free Algorithm for Constrained Markov Decision Processescited by 17
  3. 2023A Near-Optimal Algorithm for Safe Reinforcement Learning Under Instantaneous Hard Constraintscited by 15
  4. 2024Global Reinforcement Learning: Beyond Linear and Convex Rewards via Submodular Semi-gradient Methodscited by 15
  5. 2023Provably Efficient Generalized Lagrangian Policy Optimization for Safe Multi-Agent Reinforcement Learningcited by 13
  6. 2022Reinforcement Learning with Stepwise Fairness Constraintscited by 9
  7. 2023Safe Posterior Sampling for Constrained MDPs with Bounded Constraint Violationcited by 6
  8. 2023Pseudonorm Approachability and Applications to Regret Minimizationcited by 5
  9. 2023Anytime-Constrained Reinforcement Learningcited by 5
  10. 2024Deterministic Policies for Constrained Reinforcement Learning in Polynomial Timecited by 5
  11. 2025Reinforcement learning with combinatorial actions for coupled restless banditscited by 5
  12. 2025No-Regret Learning Under Adversarial Resource Constraints: A Spending Plan Is All You Need!cited by 5
  13. 2025Near-Optimal Sample Complexity Bounds for Constrained Average-Reward MDPscited by 3
  14. 2024Double Duality: Variational Primal-Dual Policy Optimization for Constrained Reinforcement Learningcited by 2
  15. 2024Efficient Exploration in Average-Reward Constrained Reinforcement Learning: Achieving Near-Optimal Regret With Posterior Samplingcited by 2
  16. 2025Primal-Dual Sample Complexity Bounds for Constrained Markov Decision Processes with Multiple Constraintscited by 2
  17. 2022An Empirical Evaluation of Posterior Sampling for Constrained Reinforcement Learningcited by 1
  18. 2024Anytime-Constrained Equilibria in Polynomial Timecited by 1
  19. 2025Polynomial-Time Approximability of Constrained Reinforcement Learningcited by 1
  20. 2023Model-Free, Regret-Optimal Best Policy Identification in Online CMDPscited by 0
  21. 2023Provably Efficient Exploration in Constrained Reinforcement Learning:Posterior Sampling Is All You Needcited by 0