Abstract:
We consider the reinforcement learning problem for the constrained Markov decision process (CMDP), which plays a central role in satisfying safety or resource constraints in sequential learning and decision-making. In this problem, we are given finite resources and a MDP with unknown transition probabilities. At each stage, we take an action, collecting a reward and consuming some resources, all assumed to be unknown and need to be learned over time. In this work, we take the first step towards deriving optimal problem-dependent guarantees for the CMDP problems. We derive a logarithmic regret bound, which translates into a O(κϵ⋅log^2(1/ϵ)) sample complexity bound, with κ being a problem-dependent parameter, yet independent of ϵ. Our sample complexity bound improves upon the state-of-art O(1/ϵ^2) sample complexity for CMDP problems established in the previous literature, in terms of the dependency on ϵ. To achieve this advance, we develop a new framework for analyzing CMDP problems. To be specific, our algorithm operates in the primal space and we resolve the primal LP for the CMDP problem at each period in an online manner, with adaptive remaining resource capacities. The key elements of our algorithm are: i). an eliminating procedure that characterizes one optimal basis of the primal LP, and; ii) a resolving procedure that is adaptive to the remaining resources and sticks to the characterized optimal basis.
About the speaker:
Jiashuo Jiang is an assistant professor at Industrial Engineering and Decision Analytics at HKUST. He got his PhD degree in Operations from NYU Stern School of Business in 2022 and obtained his bachelor's degree in Mathematics from Peking University in 2017. His research focuses on dynamic decision making and data driven decision making under uncertainty, with applications in supply chain management, revenue management, inventory management, online advertising, and so on. His work has been recognized as finalists for Informs RMP and Nicholson student paper competitions, under the supervision of Prof. Jiawei Zhang and Prof. Will Ma.