2022/04/11 by Arushi Jain, Jain, Arushi, Sharan Vaswani +8
Computer Science · Decision Sciences · #Advanced Bandit Algorithms Research #Artificial Intelligence (cs.AI) #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning and Algorithms #Reinforcement Learning in Robotics #cs.AI #cs.LG
paper · pdf · doi:10.48550/arxiv.2204.05176
Paper under submission. 27 pages, 12 figures
arxiv created 2022/04/11 · openalex publication_date 2022/04/11 · arxiv updated 2022/04/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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)) + (εb√(d))/((1 - γ)2) ) reward sub-optimality and an O((1)/((1 - γ)2 √(T)) + (εb √(d))/(1 - γ) ) 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.