Towards Painless Policy Optimization for Constrained MDPs

Code

• github.com/arushijain94/coinbettingpolitex
  OfficialIn papernone★ 3

Abstract

We study policy optimization in an infinite horizon, -discounted constrained Markov decision process (CMDP). Our objective is to return a policy that achieves large expected reward with a small constraint violation. We consider the online setting with linear function approximation and assume global access to the corresponding features. We propose a generic primal-dual framework that allows us to bound the reward sub-optimality and constraint violation for arbitrary algorithms in terms of their primal and dual regret on online linear optimization problems. We instantiate this framework to use coin-betting algorithms and propose the Coin Betting Politex (CBP) algorithm. Assuming that the action-value functions are _b-close to the span of the d-dimensional state-action features and no sampling errors, we prove that T iterations of CBP result in an O(1(1 - )^3 T + _bd(1 - )^2 ) reward sub-optimality and an O(1(1 - )^2 T + _b d1 - ) constraint violation. Importantly, unlike gradient descent-ascent and other recent methods, CBP does not require extensive hyperparameter tuning. Via experiments on synthetic and Cartpole environments, we demonstrate the effectiveness and robustness of CBP.

Reproductions