Technical Summary: Retaining Suboptimal Actions to Follow Shifting Optima in Multi-Agent Reinforcement Learning

Problem Statement

In cooperative Multi-Agent Reinforcement Learning (MARL), value decomposition methods under the Centralized Training with Decentralized Execution (CTDE) paradigm, such as QMIX, have achieved significant success. However, these methods rely on the Individual-Global-Max (IGM) condition, enforced via a monotonicity constraint, which limits the expressiveness of the joint action-value function. A critical limitation identified in this work is the inability of existing methods to adapt when the underlying value function shifts dynamically during training.

Conventional approaches typically focus on learning a single optimal joint action. When the environment or reward structure changes, causing the optimal action to shift (e.g., from action $A$ to action $C$), methods relying on a single optimal trajectory often fail to recover the new optimum. This is exacerbated by the heavy reliance on $\epsilon$-greedy policies in large joint action spaces, where the probability of jointly exploring alternative high-value actions decreases exponentially with the number of agents. Consequently, agents often converge prematurely to suboptimal policies and struggle to track moving optima.

Methodology: Successive Sub-value Q-learning (S2Q)

To address these limitations, the authors propose Successive Sub-value Q-learning (S2Q), a framework designed to retain alternative high-value actions and enable rapid adaptation to shifting optima.

Core Mechanism

S2Q departs from the single-value approach by learning a sequence of $K+1$ sub-value functions, denoted as $Q^{sub}_k$ for $k = 0, \dots, K$.

• $Q^{sub}_0$: Defined as the global joint value function $Q_{tot}$, trained to identify the true optimal action under the IGM condition.
• $Q^{sub}_k$ ($k > 0$): Designed to capture the $k$-th suboptimal joint action.

The learning process employs a successive suppression strategy. While $Q^{sub}_0$ learns the global optimum, subsequent sub-value functions are trained to maximize the joint value of actions excluding those identified by previous sub-value functions. This is achieved by modifying the Temporal-Difference (TD) learning objective with a suppression term. For a given sub-value function $Q^{sub}_k$, the target value is adjusted to suppress actions already identified as optimal or suboptimal by $Q^{sub}_0, \dots, Q^{sub}_{k-1}$.

The objective function for $Q^{sub}_k$ is defined as:
$$\mathbb{E} \left[ w_k(s_t, a_t) \left( Q^{sub}_k(s_t, \tau_t, a_t) - \left( y_t - \alpha \mathbb{I}(a_t \in A_{k-1,t}) \cdot \max(Q^*_{targ}(s_t, \tau_t, a_t), C) \right) \right)^2 \right]$$
where $A_{k-1,t}$ is the set of actions identified by previous sub-networks, $\alpha$ is a suppression factor, and $y_t$ is the target derived from an unconstrained value function $Q^*$. Theoretical analysis (Theorem 4.1) guarantees that with a sufficiently large $\alpha$, each $Q^{sub}_k$ successfully identifies the $k$-th suboptimal action.

Coordinated Execution via Communication

To effectively utilize these sub-value functions, S2Q replaces the standard $\epsilon$-greedy policy with a Softmax-based behavior policy.

1. Sampling: During training, agents sample an index $k$ from a Softmax distribution $P_t$ based on the values of the tracked suboptimal actions ($Q^*(a^*_{0,t}), \dots, Q^*(a^*_{K,t})$).
2. Execution: Once $k$ is sampled, agents execute actions according to the $\epsilon$-greedy policy of the corresponding sub-value function $Q^{sub}_k$.
3. Coordination: Since decentralized agents cannot directly observe the global distribution $P_t$, S2Q employs an Encoder-Decoder architecture during training. The encoder maps local histories to a latent representation $z_t$, and the decoder reconstructs the global state and the approximate distribution $\hat{P}_t$. Agents synchronize their choice of $k$ based on $\hat{P}_t$.
4. Decentralized Execution: Crucially, at test time, communication is not required. Since $Q^{sub}_0$ (equivalent to $Q_{tot}$) suffices to produce the greedy optimal action, evaluation remains fully decentralized and communication-free. A variant, S2Q-Comm, is also proposed for environments where communication is strictly necessary, providing the latent $z_t$ during execution.

Key Contributions

1. Identification of Dynamic Optimality Shifts: The paper highlights that existing value decomposition methods fail to track moving optima because they discard information about suboptimal actions once a single optimum is found.
2. Successive Sub-value Learning: The introduction of a framework that explicitly learns and retains multiple suboptimal actions, allowing the system to pivot quickly when the optimal action changes.
3. Softmax-Based Exploration: A novel exploration strategy that prioritizes visiting promising suboptimal actions based on their estimated values, overcoming the exponential decay of joint exploration probability in $\epsilon$-greedy policies.
4. Communication-Efficient Design: A mechanism that uses communication only during training to synchronize sub-value selection, maintaining full decentralization during execution.

Experimental Results

The authors evaluated S2Q on two major benchmarks: StarCraft Multi-Agent Challenge (SMAC) and Google Research Football (GRF).

• SMAC-Hard+ and GRF: S2Q consistently outperformed state-of-the-art baselines (including QMIX, WQMIX, DOP, FOP, PAC, RiskQ, and MARR) across various maps (e.g., 6h vs 8z, MMM2, Corridor). The performance gap was most significant in exploration-intensive scenarios where the optimal strategy shifts during training. S2Q demonstrated faster convergence and higher asymptotic win rates.
• SMAC-Comm: In tasks requiring explicit communication (e.g., 5z vs 1ul, bane vs hM), the S2Q-Comm variant showed substantial gains over communication-focused baselines like MASIA, NDQ, and CAMA, particularly in complex coordination tasks.
• Stochastic Environments: S2Q maintained superior performance in SMACv2 (randomized team compositions) and SMAC-Hard (Mixture Opponent), demonstrating robustness to stochastic dynamics.
• Generality: The method was successfully extended to other CTDE baselines like VDN and QPLEX, yielding consistent performance improvements.
• Ablation Studies: Experiments confirmed that the successive sub-value learning and Softmax-guided execution are critical components. Removing the suppression mechanism or the Softmax policy significantly degraded performance. The optimal number of sub-networks ($K$) was found to be 2, balancing diversity and stability.

Significance and Claims

The paper claims that S2Q addresses a fundamental limitation in cooperative MARL: the rigidity of methods that converge to a single optimal policy. By retaining suboptimal actions, S2Q enables agents to adapt rapidly to changing value landscapes without premature convergence.

The authors position S2Q as a practical and general framework that improves adaptability and overall performance in challenging MARL environments. They emphasize that the method achieves these gains without requiring communication during execution, making it suitable for real-world deployment where communication bandwidth may be limited. The work suggests that explicitly tracking suboptimal alternatives is a viable and effective strategy for enhancing exploration and robustness in multi-agent systems.