Provably Efficient Safe Exploration via Primal-Dual Policy Optimization

Abstract

We study the Safe Reinforcement Learning (SRL) problem using the Constrained Markov Decision Process (CMDP) formulation in which an agent aims to maximize the expected total reward subject to a safety constraint on the expected total value of a utility function. We focus on an episodic setting with the function approximation where the Markov transition kernels have a linear structure but do not impose any additional assumptions on the sampling model. Designing SRL algorithms with provable computational and statistical efficiency is particularly challenging under this setting because of the need to incorporate both the safety constraint and the function approximation into the fundamental exploitation/exploration tradeoff. To this end, we present an \underline{O}ptimistic \underline{P}rimal-\underline{D}ual Proximal Policy \underline{OP}timization (OPDOP) algorithm where the value function is estimated by combining the least-squares policy evaluation and an additional bonus term for safe exploration. We prove that the proposed algorithm achieves an $\tilde{O}(d{H}^{2.5}\sqrt{T})$ regret and an $\tilde{O}(d{H}^{2.5}\sqrt{T})$ constraint violation, where $d$ is the dimension of the feature mapping, $H$ is the horizon of each episode, and $T$ is the total number of steps. These bounds hold when the reward/utility functions are fixed but the feedback after each episode is bandit. Our bounds depend on the capacity of the state-action space only through the dimension of the feature mapping and thus our results hold even when the number of states goes to infinity. To the best of our knowledge, we provide the first provably efficient online policy optimization algorithm for CMDP with safe exploration in the function approximation setting.

44 pages. We have revised the linear MDP assumption and fixed a bug in our previous proofs

References in corpus (23)

• Safe Exploration in Continuous Action Spaces
• Reward Constrained Policy Optimization
• Provably Efficient Reinforcement Learning with Linear Function Approximation
• Lyapunov-based Safe Policy Optimization for Continuous Control
• Constrained Policy Optimization
• On the Theory of Policy Gradient Methods: Optimality, Approximation, and Distribution Shift
• Neural Policy Gradient Methods: Global Optimality and Rates of Convergence
• A Lyapunov-based Approach to Safe Reinforcement Learning
• Online Convex Optimization with Time-Varying Constraints
• Model-Based Reinforcement Learning with Value-Targeted Regression
• Accelerated Primal-Dual Policy Optimization for Safe Reinforcement Learning
• Optimism in Reinforcement Learning with Generalized Linear Function Approximation
• Safe Reinforcement Learning in Constrained Markov Decision Processes
• Responsive Safety in Reinforcement Learning by PID Lagrangian Methods
• Minimax Regret Bounds for Reinforcement Learning
• Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Bound
• Is a Good Representation Sufficient for Sample Efficient Reinforcement Learning?
• Online Convex Optimization with Stochastic Constraints
• Constrained Upper Confidence Reinforcement Learning
• Provably Efficient Reinforcement Learning for Discounted MDPs with Feature Mapping
• Comments on the Du-Kakade-Wang-Yang Lower Bounds
• IPO: Interior-point Policy Optimization under Constraints
• Constrained episodic reinforcement learning in concave-convex and knapsack settings

Cited by in corpus (11)

• Safe Reinforcement Learning Using Black-Box Reachability Analysis
• TRC: Trust Region Conditional Value at Risk for Safe Reinforcement Learning
• Successive Convex Approximation Based Off-Policy Optimization for Constrained Reinforcement Learning
• Risk-Sensitive Reinforcement Learning: Near-Optimal Risk-Sample Tradeoff in Regret
• Ablation Study of How Run Time Assurance Impacts the Training and Performance of Reinforcement Learning Agents
• Provably Efficient Algorithms for Multi-Objective Competitive RL
• Efficient Reinforcement Learning in Factored MDPs with Application to Constrained RL
• Safe Reinforcement Learning with Linear Function Approximation
• Assured RL: Reinforcement Learning with Almost Sure Constraints
• Price of Safety in Linear Best Arm Identification
• Scheduling and Power Control for Wireless Multicast Systems via Deep Reinforcement Learning