A Best-of-Both-Worlds Algorithm for Constrained MDPs with Long-Term Constraints

Understand

We study online learning in episodic constrained Markov decision processes (CMDPs), where the learner aims at collecting as much reward as possible over the episodes, while satisfying some long-term constraints during the learning process.

• Rewards and constraints can be selected either stochastically or adversarially, and the transition function is not known to the learner.
• While online learning in classical (unconstrained) MDPs has received considerable attention over the last years, the setting of CMDPs is still largely unexplored.
• This is surprising, since in real-world applications, such as, e.g., autonomous driving, automated bidding, and recommender systems, there are usually additional constraints and specifications that an agent has to obey during the learning process.