Cooperative Online Learning in Stochastic and Adversarial MDPs
This addresses the problem of multi-agent reinforcement learning in dynamic environments for researchers and practitioners, introducing new models like non-fresh randomness and adversarial MDPs, which is incremental as it extends existing cooperative RL frameworks.
The paper tackles cooperative online learning in Markov decision processes (MDPs) with stochastic and adversarial randomness, where multiple agents share information to minimize individual regret, and it proves nearly-matching regret bounds for settings including non-fresh randomness and adversarial MDPs.
We study cooperative online learning in stochastic and adversarial Markov decision process (MDP). That is, in each episode, $m$ agents interact with an MDP simultaneously and share information in order to minimize their individual regret. We consider environments with two types of randomness: \emph{fresh} -- where each agent's trajectory is sampled i.i.d, and \emph{non-fresh} -- where the realization is shared by all agents (but each agent's trajectory is also affected by its own actions). More precisely, with non-fresh randomness the realization of every cost and transition is fixed at the start of each episode, and agents that take the same action in the same state at the same time observe the same cost and next state. We thoroughly analyze all relevant settings, highlight the challenges and differences between the models, and prove nearly-matching regret lower and upper bounds. To our knowledge, we are the first to consider cooperative reinforcement learning (RL) with either non-fresh randomness or in adversarial MDPs.