Cooperative Online Learning in Stochastic 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.
