Sequential Multi-Agent Dynamic Algorithm Configuration

AI summary

Overview

Research area: Automated machine learning / dynamic algorithm configuration (DAC), cooperative multi-agent reinforcement learning (MARL), and multi-objective evolutionary optimization.

Technical level: Advanced. The paper assumes familiarity with Markov decision processes, multi-agent MDPs, value/advantage decomposition, the IGM principle, and evolutionary algorithms such as MOEA/D.

Scope: The paper proposes a framework (Seq-MADAC) and a decomposition network (SADN) for dynamically configuring multiple interdependent algorithm hyperparameters, and evaluates them on synthetic sequential benchmarks and on the configuration of the multi-objective optimizer MOEA/D (arXiv:2510.23535v1, cs.LG, 27 Oct 2025).

What This Paper Is About

Dynamic algorithm configuration (DAC) tunes an algorithm's hyperparameters while the algorithm runs, but the complex algorithms used in practice have several heterogeneous hyperparameters whose settings depend on one another — for example, you choose a reproduction operator type before you can choose that operator's own parameters. Prior multi-agent DAC formulations treat the tuning agents as making decisions simultaneously or independently, so they ignore these built-in dependencies and explore illegal or nonsensical parameter combinations. The authors' goal is to model hyperparameter tuning as a sequential multi-agent decision process and to design a learning method that exploits the resulting action order.

Key Contributions

1. A sequential decision-making framework for DAC. The paper formulates the multi-hyperparameter DAC task with inherent inter-dependencies as a contextual sequential multi-agent MDP (contextual sequential MMDP), where each agent (one per hyperparameter) observes the actions already chosen by earlier agents before acting.
2. The Sequential Advantage Decomposition Network (SADN). SADN decomposes the global advantage function into per-agent advantage functions that are summed in sequence, using the multi-agent advantage decomposition lemma, and updates the global advantage via Generalized Advantage Estimation with λ = 0 (one-step temporal difference).
3. A theoretical guarantee. The authors prove a theorem (Theorem 1) stating that maximizing the global action-value function is equivalent to sequentially maximizing each agent's advantage function, i.e., the decomposition satisfies the Individual Global Max (IGM) principle in the sequential setting.
4. Extensive empirical validation. Experiments span controllable synthetic tasks (Sigmoid, Seq-Sigmoid, Seq-Sigmoid-Mask, Seq-Sigmoid-Robust) and configuration of MOEA/D on multi-objective optimization problems, comparing SADN against sequential methods (ACE, SAQL) and general MARL algorithms (VDN, QMIX, MAPPO, MAPPOar, HAPPO, HASAC).

Main Findings

• Sequential information helps. On Seq-Sigmoid and Seq-Sigmoid-Mask with 5 and 10 dimensions (results averaged over 6 runs), the methods that exploit sequential structure — SADN, ACE, and SAQL — captured the hyperparameter inter-dependencies to some degree and performed better than conventional MARL baselines, which the paper reports fail to cope with the inter-dependencies and randomness on Seq-Sigmoid-Mask.
• SADN converges faster and more stably. The authors report that SADN outperformed the compared methods on every benchmark, with faster convergence, less variance, and better final performance.
• ACE degrades with diverse instances. ACE showed a clear performance decay on Seq-Sigmoid; the authors attribute this to its long-chain action-value function update scheme being disrupted when problem instances vary.
• Order matters. Reversing the action order underperformed the correct order and produced larger variance, which the authors present as evidence that modelling the inherent inter-dependencies correctly is important. The exception was HAPPO, because it only reorders the update of agents, not the order in which actions are taken.
• SADN is more robust to failing agents. On Seq-Sigmoid-Robust (5 and 10 dimensions, with 1 or 2 random agents, averaged over 6 runs), SADN outperformed ACE and SAQL. ACE's long-chain update was destabilized by the random agents, and SAQL remained stuck at poor performance due to interference from them.
• SADN leads on multi-objective configuration, with exceptions. On the MOEA/D configuration task (IGD metric, mean of 10 runs, Wilcoxon rank-sum test at significance level 0.05, dimensions 6, 9 and 12 over DTLZ2, DTLZ4, WFG4, WFG5, WFG6, WFG7, WFG8 and WFG9), the training-side summary row reports 0 significantly superior / 9 significantly inferior / 0 approximately equal problems for ACE, VDN, QMIX and HAPPO; 0/8/1 for SAQL and HASAC; 1/8/0 for MAPPO. SADN is not itself scored in that row.
• Notable individual losses. SADN was worse than ACE on DTLZ4 at dimension 9 (7.319e-02 vs 4.492e-02) and dimension 12 (7.852e-02 vs 4.650e-02), and worse than the untuned MOEA/D column on WFG8 at dimension 6 (1.018e-01 vs 7.875e-02). The testing-side significance counts are not present in the available content.
• SADN also improves credit assignment. The paper contrasts SADN with SAQL, arguing that SAQL (which extends independent Q-learning by feeding prior agents' actions into later agents' states) applies the team reward directly to individual agents and therefore cannot reveal inter-agent interactions or provide proper credit assignment.

Methodology in Plain English

The authors start from the observation that tuning several hyperparameters is like several agents each controlling one knob. Earlier multi-agent versions let every agent decide at once. This paper instead lets the agents decide one after another within each timestep: the first agent picks its parameter without extra information, the second sees what the first chose, the third sees the first two, and so on. That ordering encodes real dependencies (choose the operator type, then choose the operator's parameters) and avoids wasting effort on illegal combinations.

To learn this, they keep one small network per agent that scores that agent's own choices, and one shared "value" network that estimates how good the overall situation is. Crucially, they do not have each agent learn from the raw team reward alone. Instead, they split the team's advantage — the extra value gained by acting — into a sum of per-agent advantages, following the multi-agent advantage decomposition lemma. Each agent then trains to maximize its own piece, and gradients flow back from the shared value network to all of them. The authors prove that greedily maximizing each agent's advantage in sequence yields the same joint choice as maximizing the overall value, so decentralized execution remains optimal.

For evaluation they build staged benchmarks. Sigmoid is an approximation task where hyperparameters drift over time. Seq-Sigmoid modifies it so that each parameter's value determines a scaling factor controlling the next parameter's slope, creating a true dependency chain. Seq-Sigmoid-Mask hides the instance parameters and sets the slope to 1, producing a single-instance task with heavy randomness, intended to mimic stochastic evolutionary execution. Seq-Sigmoid-Robust(n) forces n agents to take completely random configuration actions, simulating agents that fail to learn, to see whether the rest of the system copes. Finally, MOEA/D is the real target: configuring the weights, neighborhood size, reproduction operator type, and operator parameters of a well-known multi-objective evolutionary algorithm, scored by the IGD indicator on standard multi-objective problem suites across three dimensions.

Why This Matters

Impact on research. The paper shifts DAC from "tune several parameters in parallel" to "tune them in a dependency-aware order," and supplies a decomposition theorem (an IGM-style result for sequential advantage decomposition) rather than only an empirical fix. It also positions itself against two families of prior work: parallel MARL approaches such as MADAC, which ignore inter-dependencies, and sequential Q-learning approaches such as SAQL and ACE, which the authors argue suffer from weak credit assignment or fragile long-chain updates. The code is released at https://github.com/lamda-bbo/seq-madac.

Potential applications (the paper itself evaluates synthetic functions and MOEA/D configuration; the following are general settings the DAC paradigm targets rather than settings tested here):

• Automatic tuning of learning rates, optimizers, and other training hyperparameters in deep learning pipelines.
• Step-size and operator control in evolutionary and swarm-based optimizers used in engineering design and simulation-based optimization.
• Selecting heuristics and search strategies in automated planning and combinatorial solvers.
• Configuring parameters of database query optimizers or compilers, where settings are typically chosen in a fixed order with dependencies.

Industry relevance. The work is co-authored with Huawei's Advanced Computing and Storage Lab, which signals interest in automating the configuration of optimization and machine-learning pipelines that are otherwise tuned by hand. Because the method learns a policy over a distribution of problem instances rather than a single instance, it targets reusable tuning policies — the property that makes automated configuration economically attractive at scale.

Future Directions

• Handling problems where SADN lagged. SADN was worse than ACE on DTLZ4 at dimensions 9 and 12, and worse than the untuned baseline on WFG8 at dimension 6. Understanding what makes these problems different is an open question the results raise but the available content does not answer.
• Learning the dependency order rather than assuming it. The authors use a known correct order and show reverse order hurts (except for HAPPO); inferring the correct action order automatically when dependencies are unknown is a natural extension, and the paper does not report such experiments.
• Scaling to more agents and longer chains. SAQL's and ACE's weaknesses grow with chain length and with failing agents; whether SADN's independent advantage updates remove that scaling barrier at larger numbers of hyperparameters is not established in the reported experiments (the synthetic studies use 5 and 10 dimensions).
• Validation beyond synthetic benchmarks and MOEA/D. The paper's real target is MOEA/D; whether the framework transfers to other complex algorithms with heterogeneous hyperparameters is not reported.

Target Audience

Researchers and practitioners in automated machine learning and reinforcement learning who work on algorithm configuration, hyperparameter optimization, and multi-agent credit assignment; readers interested in applying RL to the tuning of evolutionary and multi-objective optimization algorithms; and engineers responsible for hand-tuning complex optimization pipelines who want to understand what a dependency-aware, learning-based tuner can and cannot yet deliver.

Authors’ abstract

Dynamic algorithm configuration (DAC) is a recent trend in automated machine learning, which can dynamically adjust the algorithm's configuration during the execution process and relieve users from tedious trial-and-error tuning tasks. Recently, multi-agent reinforcement learning (MARL) approaches have improved the configuration of multiple heterogeneous hyperparameters, making various parameter configurations for complex algorithms possible. However, many complex algorithms have inherent inter-dependencies among multiple parameters (e.g., determining the operator type first and then the operator's parameter), which are, however, not considered in previous approaches, thus leading to sub-optimal results. In this paper, we propose the sequential multi-agent DAC (Seq-MADAC) framework to address this issue by considering the inherent inter-dependencies of multiple parameters. Specifically, we propose a sequential advantage decomposition network, which can leverage action-order information through sequential advantage decomposition. Experiments from synthetic functions to the configuration of multi-objective optimization algorithms demonstrate Seq-MADAC's superior performance over state-of-the-art MARL methods and show strong generalization across problem classes. Seq-MADAC establishes a new paradigm for the widespread dependency-aware automated algorithm configuration. Our code is available at https://github.com/lamda-bbo/seq-madac.