Model-Free Algorithm and Regret Analysis for MDPs with Long-Term Constraints

Autor:	Bai, Qinbo, Aggarwal, Vaneet, Gattami, Ather
Rok vydání:	2020
Předmět:	Computer Science - Machine Learning Computer Science - Networking and Internet Architecture Electrical Engineering and Systems Science - Systems and Control Mathematics - Optimization and Control Statistics - Machine Learning
Druh dokumentu:	Working Paper
Popis:	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 $\gamma\in(0,\frac{1}{2})$, the proposed algorithm is shown to achieve $O(T^{1/2+\gamma})$ regret bound for the obtained reward and $O(T^{1-\gamma/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. Comment: The result has error
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/2006.05961 Zobrazit plný text záznamu View this record from Arxiv