Learning Infinite-Horizon Average-Reward Markov Decision Processes with Constraints
This addresses the problem of constrained reinforcement learning for researchers and practitioners, offering incremental improvements in regret bounds and extending to more general MDP classes.
The paper tackles regret minimization for infinite-horizon average-reward Markov Decision Processes with cost constraints, achieving $\widetilde{O}(\sqrt{T})$ regret and constant constraint violation for ergodic MDPs, improving over prior $\widetilde{O}(T^{2/3})$ results, and provides the first provable algorithms for weakly communicating MDPs with similar guarantees.
We study regret minimization for infinite-horizon average-reward Markov Decision Processes (MDPs) under cost constraints. We start by designing a policy optimization algorithm with carefully designed action-value estimator and bonus term, and show that for ergodic MDPs, our algorithm ensures $\widetilde{O}(\sqrt{T})$ regret and constant constraint violation, where $T$ is the total number of time steps. This strictly improves over the algorithm of (Singh et al., 2020), whose regret and constraint violation are both $\widetilde{O}(T^{2/3})$. Next, we consider the most general class of weakly communicating MDPs. Through a finite-horizon approximation, we develop another algorithm with $\widetilde{O}(T^{2/3})$ regret and constraint violation, which can be further improved to $\widetilde{O}(\sqrt{T})$ via a simple modification, albeit making the algorithm computationally inefficient. As far as we know, these are the first set of provable algorithms for weakly communicating MDPs with cost constraints.