Challenge: The Non-Stationarity Problem

Single-agent reinforcement learning typically operates under the assumption of a stationary environment. This means the rules governing transitions between states ($P(s'|s,a)$) and the rewards received ($R(s,a)$) remain fixed over time. An agent interacts with this stable environment, learning how its actions influence outcomes. This stationarity is a fundamental assumption underpinning the convergence guarantees of many RL algorithms like Q-learning and DQN.

However, this assumption breaks down dramatically in multi-agent settings. When multiple agents are learning simultaneously within the same environment, the environment becomes non-stationary from the perspective of any individual agent.

Consider an agent $i$ among $N$ agents. Its goal is to learn an optimal policy $\pi_i$. The environment's state $s$ transitions to $s'$ based on the joint action $a = (a_1, a_2, ..., a_N)$ taken by all agents, according to the true transition probability $P(s' | s, a)$. Agent $i$ receives a reward $r_i$, which might also depend on the joint action, $R_i(s, a)$.

Agent $i$ observes the state $s$, selects its action $a_i$ according to its current policy $\pi_i(a_i|s)$, receives reward $r_i$, and observes the next state $s'$. From agent $i$'s local viewpoint, the transition seems to depend only on its own action $a_i$. However, the actual transition probability it experiences, let's call it $P_i(s' | s, a_i)$, is determined by averaging over the actions $a_{-i} = (a_1, ..., a_{i-1}, a_{i+1}, ..., a_N)$ taken by all other agents according to their policies $\pi_{-i}$:

$$P_i(s' | s, a_i) = \sum_{a_{-i}} P(s' | s, a_i, a_{-i}) \prod_{j \neq i} \pi_j(a_j | s)$$

Similarly, the expected reward agent $i$ perceives for taking action $a_i$ in state $s$, denoted $R_i(s, a_i)$, depends on what the other agents do:

$$R_i(s, a_i) = \sum_{a_{-i}} R_i(s, a_i, a_{-i}) \prod_{j \neq i} \pi_j(a_j | s)$$

Here lies the core problem: As the other agents $j \neq i$ learn and update their policies $\pi_j$, the effective transition probabilities $P_i(s' | s, a_i)$ and expected rewards $R_i(s, a_i)$ that agent $i$ experiences change over time. The environment, from agent $i$'s perspective, is no longer stationary. The Markov property, which states that the future is independent of the past given the present state (and action), is effectively violated from the local viewpoint of agent $i$ because the underlying dynamics depend on hidden variables: the changing policies of other agents.

Agent B experiences changing environment dynamics (transition probabilities) because Agent A is simultaneously updating its policy. What worked for Agent B at time $t$ might not work at time $t+1$.

This non-stationarity poses significant challenges for learning:

Breakdown of Convergence Guarantees

Standard single-agent algorithms, like Q-Learning, rely heavily on the stationarity of the environment to guarantee convergence to optimal value functions or policies. When the target Q-values (used in the Bellman update) are constantly shifting because other agents' policies are changing, the learning process can become unstable. The algorithm might oscillate, diverge, or converge to a suboptimal solution representing a poor compromise between policies that are no longer relevant. It's like trying to hit a target that's constantly moving based on your previous attempts.

Invalidation of Experience Replay

Techniques like Experience Replay, which were essential for stabilizing DQN, store past transitions $(s, a, r, s')$ in a replay buffer and sample from it to train the Q-network. This works well in stationary environments because old experiences remain valid representations of the environment's dynamics. In MARL, however, a transition collected when other agents were following policy $\pi_{-i}^{\text{old}}$ might be drastically different from what would happen under their current policy $\pi_{-i}^{\text{new}}$. Replaying outdated experiences can introduce significant bias and hinder learning, as the agent trains on misleading information about how the multi-agent system currently behaves.

Difficult Credit Assignment

Assigning credit or blame for outcomes becomes much harder. Did agent $i$ receive a low reward because its own action $a_i$ was poor, or because another agent $j$ took an action $a_j$ that interfered or failed to coordinate effectively? Disentangling the contributions of different agents to the collective outcome is a complex problem exacerbated by the changing behavior of others.

Addressing this non-stationarity is a central theme in MARL research. Many advanced MARL algorithms, which we will explore shortly, incorporate specific mechanisms to mitigate these issues, often by allowing agents to access more information during training than they will have during execution (the Centralized Training with Decentralized Execution) or by attempting to model or anticipate the behavior of other agents.