Sequential Multi-Agent Dynamic Algorithm Configuration¶

🕒 Published (v1): 2025-01-01 · Source: NeurIPS · Venue: NeurIPS 2025 · link

Ask a follow-up

Open an assistant pre-loaded with this paper's context.

TL;DR¶

Seq-MADAC introduces a cooperative multi-agent reinforcement learning framework for dynamic algorithm configuration (DAC) that explicitly models inter-dependencies among hyperparameters via sequential decision-making. The core contribution is the Sequential Advantage Decomposition Network (SADN), which decomposes the global advantage function into ordered per-agent advantage functions satisfying the IGM principle. On both synthetic benchmarks and real multi-objective evolutionary algorithm tuning (MOEA/D), SADN outperforms prior MARL and sequential-action baselines.

Problem¶

Multi-hyperparameter DAC faces two compounding challenges: (1) the combinatorial explosion of joint action spaces when configuring multiple heterogeneous parameters simultaneously, and (2) inherent inter-dependencies among parameters (e.g., the reproduction operator type must be fixed before its associated parameters can be meaningfully set). Existing cooperative MARL approaches (VDN, QMIX, MAPPO, HAPPO, HASAC) treat agents as fully decentralized and ignore these dependencies. The only prior sequential approach, CANDID/SAQL, uses IQL-style credit assignment that causes non-convergence; ACE's long Q-value update chain introduces compounding errors under diverse instances.

Method¶

The problem is formulated as a contextual sequential multi-agent MDP (sequential MMDP): at each timestep, agents act one-by-one in a predefined dependency order, with each agent $i$ observing the state $s$ plus all prior actions $a_{1:i-1}$.

SADN decomposes the global advantage function $A(s, a)$ into a sum of per-agent conditional advantage functions via the Multi-Agent Advantage Decomposition Lemma: $$A^\pi(s, a) = \sum_{i=1}^n A^\pi_i(s, a_{1:i-1}, a_i)$$

Each agent $i$ maintains a network estimating $A_i(s, a_{1:i-1}, a_i)$ and selects the action maximizing it. A shared global value network $V(s)$ is maintained; the global advantage target is computed by one-step TD (GAE with $\lambda=0$): $$A(s,a) \leftarrow A(s,a) + \alpha[r + \gamma V(s') - V(s) - A(s,a)]$$

Gradients backpropagate through the summed global advantage to all individual networks simultaneously, so individual nets update in parallel rather than sequentially, avoiding the chain-error problem of ACE. The decomposition is proven to satisfy the IGM principle in the sequential setting (Theorem 1), guaranteeing that per-agent greedy action selection recovers the joint optimum.

The required hyperparameter ordering is set by the natural execution order in the target algorithm's code (e.g., for MOEA/D: neighborhood size → operator type → operator parameters → weight update).

Key Contributions¶

Formalizes multi-hyperparameter DAC with inter-dependencies as a contextual sequential MMDP, enabling principled sequential action ordering.
Proposes SADN with sequential advantage decomposition, satisfying IGM in the sequential setting—proven theoretically—allowing decentralized greedy execution with guaranteed joint optimality.
Introduces Seq-Sigmoid and its variants (Seq-Sigmoid-Mask, Seq-Sigmoid-Robust) as synthetic benchmarks with explicit hyperparameter inter-dependencies.
Demonstrates robustness to "broken" agents (Seq-Sigmoid-Robust) that emit random configurations, where ACE and SAQL degrade sharply.

Results¶

Seq-Sigmoid (5D/10D): SADN converges faster, lower variance, and higher final return than ACE, SAQL, VDN, QMIX, MAPPO, HAPPO, HASAC across all variants; ACE degrades on diverse-instance Seq-Sigmoid due to chain-update fragility.
Seq-Sigmoid-Robust (5D/10D, 1–2 random agents): SADN maintains robust performance; ACE shows apparent decay; SAQL stagnates.
MOEA/D (3 training problems, 5 test problems, dims 6/9/12): SADN achieves the best average rank across all dimensions (ranks: 1.75/2.5/2.5 for dims 6/9/12) versus next-best MAPPO (2.0/3.125/3.625). On training problems SADN is significantly superior in 0 cases and inferior in only 8/27 comparisons vs. baselines; comparable pattern holds on test problems.
Correct parameter ordering consistently outperforms reverse ordering within sequential methods, validating the dependency-modeling hypothesis.

Limitations¶

Ordering must be provided a priori; no automatic order discovery—though the paper suggests using the execution order in algorithm code as a practical heuristic.
Cross-dimensional generalization (training on one dimension, testing on another) remains a significant open challenge noted by the authors.
The MOEA/D environment is still one specific algorithm family; applicability to other complex algorithm classes (e.g., neural architecture search, black-box optimizers beyond MOEA/D) is not demonstrated.
Sequential ordering assumes a DAG of dependencies that must be specified by domain knowledge or LLMs (suggested as future work).

Relevance to Agentic AI / LLM Agents¶

Seq-MADAC directly addresses how cooperative agents can coordinate sequential, dependency-ordered decisions—a fundamental pattern in agentic pipelines where sub-tasks have causal ordering constraints (e.g., tool-use chains, plan decomposition). The SADN decomposition shows how to assign credit across agents acting in sequence without the chain-error pathologies that plague naive sequential Q-learning, a problem structurally analogous to multi-step tool-use or subagent credit assignment in LLM agent frameworks. The contextual sequential MMDP formulation may inform future designs of multi-agent LLM systems where action order encodes dependency structure. The paper also connects to offline sequential RL architectures (Q-Transformer, Q-Mamba), pointing toward potential integration with transformer-based agent policies.