Upper Confidence Primal-Dual Reinforcement Learning for CMDP with Adversarial Loss

Abstract

We consider online learning for episodic stochastically constrained Markov decision processes (CMDPs), which plays a central role in ensuring the safety of reinforcement learning. Here the loss function can vary arbitrarily across the episodes, and both the loss received and the budget consumption are revealed at the end of each episode. Previous works solve this problem under the restrictive assumption that the transition model of the Markov decision processes (MDPs) is known a priori and establish regret bounds that depend polynomially on the cardinalities of the state space $\mathcal{S}$ and the action space $\mathcal{A}$. In this work, we propose a new \emph{upper confidence primal-dual} algorithm, which only requires the trajectories sampled from the transition model. In particular, we prove that the proposed algorithm achieves $\tilde{\mathcal{O}}(L|\mathcal{S}|\sqrt{|\mathcal{A}|T})$ upper bounds of both the regret and the constraint violation, where $L$ is the length of each episode. Our analysis incorporates a new high-probability drift analysis of Lagrange multiplier processes into the celebrated regret analysis of upper confidence reinforcement learning, which demonstrates the power of "optimism in the face of uncertainty" in constrained online learning.

References in corpus (11)

• The on-line shortest path problem under partial monitoring
• On the Theory of Policy Gradient Methods: Optimality, Approximation, and Distribution Shift
• Neural Policy Gradient Methods: Global Optimality and Rates of Convergence
• Learning Adversarial MDPs with Bandit Feedback and Unknown Transition
• Q-learning with UCB Exploration is Sample Efficient for Infinite-Horizon MDP
• Exploration-Exploitation in Constrained MDPs
• Constrained Upper Confidence Reinforcement Learning
• Exploration-Enhanced POLITEX
• Model-free Reinforcement Learning in Infinite-horizon Average-reward Markov Decision Processes
• Provably Efficient Exploration in Policy Optimization
• Optimistic Policy Optimization with Bandit Feedback

Cited by in corpus (6)

• Risk-Sensitive Reinforcement Learning: Near-Optimal Risk-Sample Tradeoff in Regret
• A Provably-Efficient Model-Free Algorithm for Constrained Markov Decision Processes
• A Simple Reward-free Approach to Constrained Reinforcement Learning
• Provably Efficient Algorithms for Multi-Objective Competitive RL
• Safe Reinforcement Learning with Linear Function Approximation
• Concave Utility Reinforcement Learning with Zero-Constraint Violations