Abstract
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: fresh — where each agent's trajectory is sampled i.i.d, and 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.
Introduction
In multi-agent reinforcement learning (MARL), a fundamental objective is for a team of $m$ agents to cooperate to minimize their individual regret—the difference between their performance and that of the best fixed strategy. While it is intuitive that $m$ agents should learn faster than one, standard theoretical frameworks often assume "fresh" randomness, where each agent experiences independent noise. This paper challenges that assumption by introducing "non-fresh" randomness—shared environmental noise—and extending the cooperative model to adversarial MDPs where costs can change over time.
Problem Formulation: Fresh vs. Non-fresh Randomness
The core of this work lies in the distinction between two types of environmental noise:
- Fresh Randomness: Each agent's trajectory is sampled independently. This is the standard assumption in most existing literature.
- Non-fresh Randomness: The realization of costs and transitions is fixed at the start of each episode and shared by all agents. For example, multiple autonomous cars in the same sudden rainstorm will experience the same environmental perturbations if they take the same actions.
Under non-fresh randomness, standard "optimistic" policies fail because agents will follow identical trajectories, effectively reducing the team's exploration to that of a single agent. This necessitates new strategies for coordinated exploration.
Algorithmic Strategies
The authors propose several algorithms to handle these diverse settings:
- Centralized Aggregation (
coop-ULCVI,coop-O-REPS): For fresh randomness, agents can aggregate data to achieve a $1/\sqrt{m}$ regret reduction. - Action-Elimination (
coop-ULCAE): For stochastic MDPs with non-fresh randomness, theCOOP-ULCAEalgorithm (Algorithm 1) forces agents to "scatter" and explore different actions to ensure diverse data collection despite shared noise. - Coordinated Deviation (
coop-nf-O-REPS): For adversarial costs with non-fresh randomness, agents are assigned specific time steps to deviate from the main policy, ensuring state-space coverage.
Theoretical Results
The paper establishes a comprehensive set of upper and lower bounds for regret across various settings, summarized in Table 1.
Key findings include:
- Optimal Fresh Bounds: For stochastic MDPs with fresh randomness, the regret bound $\tilde{O}(\sqrt{H^3SAK/m})$ is shown to be optimal, improving upon previous state-of-the-art results.
- The Price of Non-freshness: Non-fresh randomness introduces a fundamental limit. The authors prove a lower bound of $\Omega(H\sqrt{SK})$ that does not vanish as $m \to \infty$, indicating that shared noise makes learning inherently harder.
- Adversarial Guarantees: The work provides the first regret bounds for cooperative learning in adversarial MDPs, showing that near-optimal performance is achievable even with unknown transitions, provided $m \geq \sqrt{K}$.
Discussion and Limitations
While this work provides a rigorous foundation for cooperative RL in complex environments, several open questions remain. The regret bounds for non-fresh settings with unknown transitions still have a small gap (a factor of $\sqrt{HS}$). Additionally, the model assumes perfect, instantaneous communication between agents, which may not hold in many real-world decentralized systems. Future research could explore communication-constrained settings and improve agent efficiency in the most challenging adversarial scenarios.
Summary updated