2020/06/10 by Qinbo Bai, Bai, Qinbo, Vaneet Aggarwal +3
Computer Science · Engineering · Mathematics · #FOS: Computer and information sciences #FOS: Electrical engineering #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Networking and Internet Architecture (cs.NI) #Optimization and Control (math.OC) #Systems and Control (eess.SY) #cs.LG #cs.NI #cs.SY #eess.SY #electronic engineering #information engineering #math.OC #stat.ML
paper · pdf · doi:10.48550/arxiv.2006.05961
The result has error
arxiv created 2021/01/30 · arxiv updated 2021/02/02
In the optimization of dynamical systems, the variables typically have constraints. Such problems can be modeled as a constrained Markov Decision Process (CMDP). This paper considers a model-free approach to the problem, where the transition probabilities are not known. In the presence of long-term (or average) constraints, the agent has to choose a policy that maximizes the long-term average reward as well as satisfy the average constraints in each episode. The key challenge with the long-term constraints is that the optimal policy is not deterministic in general, and thus standard Q-learning approaches cannot be directly used. This paper uses concepts from constrained optimization and Q-learning to propose an algorithm for CMDP with long-term constraints. For any γ∈(0,(1)/(2)), the proposed algorithm is shown to achieve O(T1/2+γ) regret bound for the obtained reward and O(T1-γ/2) regret bound for the constraint violation, where T is the total number of steps. We note that these are the first results on regret analysis for MDP with long-term constraints, where the transition probabilities are not known apriori.