Constrained episodic reinforcement learning in concave-convex and knapsack settings

Abstract

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.

The NeurIPS 2020 version of this paper includes a small bug, leading to an incorrect dependence on H in Theorem 3.4. This version fixes it by adjusting Eq. (9), Theorem 3.4 and the relevant proofs. Changes in the main text are noted in red. Changes in the appendix are limited to Appendices B.1, B.5, and B.6 and the statement of Lemma F.3

References in corpus (10)

• Reward Constrained Policy Optimization
• Provably Efficient Reinforcement Learning with Linear Function Approximation
• AI Safety Gridworlds
• Reinforcement Learning with Convex Constraints
• Online Convex Optimization in Adversarial Markov Decision Processes
• Exploration-Exploitation in Constrained MDPs
• Constrained Upper Confidence Reinforcement Learning
• Active Exploration in Markov Decision Processes
• Provably Efficient Imitation Learning from Observation Alone
• Efficient Model-free Reinforcement Learning in Metric Spaces

Cited by in corpus (6)

• Provably Efficient Safe Exploration via Primal-Dual Policy Optimization
• A Provably-Efficient Model-Free Algorithm for Constrained Markov Decision Processes
• Accommodating Picky Customers: Regret Bound and Exploration Complexity for Multi-Objective Reinforcement Learning
• Provably Efficient Algorithms for Multi-Objective Competitive RL
• Efficient Reinforcement Learning in Factored MDPs with Application to Constrained RL
• Concave Utility Reinforcement Learning with Zero-Constraint Violations