Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: The work presents a multi-agent extension to the Dynamic Algorithm Configuration (DAC) framework. As such, the paper discusses how to extend the formulation of a contextual MDP to a contextual (cooperative) multi-agent MDP. Further, the work provides a benchmark in the form of MOEA/D which allows to study 1) dynamic algorithm configuration in the case of various heterogeneous hyperparameters, and 2) MARL algorithms. 
strengths_and_weaknesses: # Taking Author Feedback into account (during rebuttal)
I am very happy how the authors addressed my and other reviwers concerns. Thus **I already increased my score to strong accept**

-----
-----

# Original Review
Overall I'm very excited about this paper. I believe that dynamic configuration is an important problem that is not yet studied broadly enough. I am particularly excited about the extension to multiple hyperparameters of different types. In the following I will list the strengths and weaknesses.

-----
-----

## Strengths
The work combines two interesting and important fields of research (Multi-agent RL and DAC). This combination enables interesting research opportunities in both fields. For example, to the best of my knowledge, MARL methods have not had a particular focus on learning general policies. By following the DAC framework and using contextual MDPs (or rather contextual (cooperative) multi-agent MDPs) MARL algorithms can be evaluated with regards to their generalization capability. In particular, the notion of context allows to study generalization of policies in a principled manner (see e.g. [Kirk et al. 2021](https://arxiv.org/abs/2111.09794)), as was also discussed in the original work on DAC (referenced as [2] in the paper).
On the DAC side for example, as most methods employ some form of RL, the use of (cooperative) multi-agent methods allows to deal with very different types of hyperparameters (as shown in the paper). Thus I believe the combination of MARL and DAC is of importance to the NeurIPS community. 

-----
-----

## Weaknesses
### Differentiation with DAC
The work calls the proposed multi-agent approach to DAC a novel framework, however I do not see large enough differences to talk about a novel framework. In particular, the original DAC work considers also tuning of multiple hyperparameters. As the go-to solution methods for DAC are vanilla deep RL approaches (e.g. DQN) the so far considered DAC scenarios are limited by the capabilities of vanilla RL, which typically does not deal with "heterogeneous" action spaces. Thus, from my point of view, the work proposes a novel *solution approach* to the DAC problem based on multi-agent RL, which might be superior as it allows to make efficient use of human knowledge (e.g. certain hyperparameters are distinct from each other).

To me, this weakness is particularly apparent in section 3.
For example in Section 3.1 (line 103-104) it is said that the work "... explicitly take[s] the instance distribution [...] as context into account to facilitate generalization." This same motivation was stated by Biedenkapp et al. 2020 (cited as [2] in the paper) when formulating the DAC problem as cMDP. The work presented here does not make this connection explicit.
Further, in Section 3.2 the work details the components of the cMMDP. In the paragraph about the state, desiderata are listed that are not unique to the multi-agent setting. For example, [Lindauer and Biedenkapp 2020](https://www.automl.org/wp-content/uploads/2020/08/AC_Tutorial_2020.pdf) presented a similar set of 3 desiderata for the state.

In Section 4.2 when the different hyperparameters are discussed, selection of different operators for differential evolution are mentioned. I believe in the main paper there should be a reference to Sharma et al. 2019 (cited as [10] in the appendix) as their work proposed to adapt DE operators via DQN.

Finally, although a benchmark collection for DAC problems, DACBench, is cited (as [9] in the paper), none of the existing benchmarks were used for evaluation. This seems strange to me as I believe there are benchmarks in the collection that allow for configuration of multiple hyperparameters as well as multiple hyperparameters of different types. At least the former seems to be covered as the artificial benchmarks from the ECAI paper by Biedenkapp et al. 2020 are contained. It would have given a good experiment that could have shown if a multi-agent approach can outperform  the DQN results by Biedenkapp et al.

Thus, overall I believe the work would benefit if from a closer alignment with DAC.

-----

### Notation
The work is somewhat inconsistent with the notation. In Section 2.1 contextual MDPs are discussed, though context is not formally introduced. Later in Section 3.1 context is denoted as $i\in\mathcal{I}$, however the connection to problem instances is not given. Later on when the transition function is discussed the connection between context $i$ and problem instances $f\in\mathcal{F}$ is not obvious. Thus for readers not familiar with DAC it might make it difficult to follow what context is and how it is used in this work. Further, the index variable $i$ is overloaded. On line 82 it is first introduced as the agent index and later reused to denote context. Thus in line 126 it was at first confusing as it seemed that the actions were context dependent rather than $a^{(i)}$ giving the agent index.

The way the reward function in equation 2 is written up is rather confusing. I would suggest to expand the $p^2_t$ variables and then to rearrange similar to
$$r_t = -0.5\cdot \frac{
 (f_{t}^{\star} - f_{t-1}^{\star}) \cdot ( f_{0}^{\star} - f_{t}^{\star} + f_{0}^{\star} -  f_{t-1}^{\star})
}{
(f_0^{\star})^{2}
}$$
where $f_{t}^{\star}$ denotes the best observed function value up til time-step $t$ (thus, $f_{0}^{\star} = f(s_0)$).
I think this highlights better that the reward function only reflects changes in the incumbent values. Also, to me, it better highlights how improvements over the default function value are rewarded (and how the reward is scaled).
In regards to that, I do not understand how Figure 1 should be interpreted. Since the reward is solely based on changes in incumbent, the reward is more sparse than Fiugre 1 suggests. While in the beginning it is reasonable to expect rapid improvements in incumbents, I believe in later stages improvements will be more infrequent, thus often leading to rewards of 0. Thus, overall I would expect more plateaus in Figure 1.

-----

### Claim about instance sets
It is stated that "[...] instances should have similar properties, otherwise the good generalization ability is hardly achievable [9]" (lines 156&157). That claim is false and the citation (to DACBench) does not seem correct. Biedenkapp et al. 2020 (cited as [2] in the paper) proposed artificial benchmarks on which one can control the heterogeneity of the problem instances. They showed that by using context information it is possible to learn policies even across very heterogeneous problem instances. Further, Shala et al. 2020 (cited as [29] in the paper) showed that DAC policies for step-size adaptation of CMA-ES are capable of generalization to even dissimilar functions. This is possible as context information enables RL agents to learn to distinguish between problem instances and learn about how they relate to each other.
Thus I believe the claim is wrong.

-----

### Experiments
I believe the experiments would be strengthened by showing results on the artificial benchmarks of Biedenkapp et al. 2020 as they used a DQN to control multiple hyperapameters (of the same type) the same way the DQN baseline in this work was used. This could highlight the importance of a multi-agent approach over a single-agent approach already for larger (but homogeneous) action spaces. I believe this would be a particularly informative experiment as the benchmarks allow to arbitrarily scale the number of parameters and number of choices per parameter. This could neatly highlight the advantage of a multi-agent approach.

On the evaluated benchmarks, the DQN baseline actually does not make too much sense to me. On the real benchmark, the action space is 128. Biedenkapp et al. showed that DQN does not scale well with the number of parameters, even on the artificial benchmarks. In a more recent work by [Biedenkapp et al. 2022](https://arxiv.org/abs/2202.03259) showed that on more stochastic DAC problems, DQN already struggled to scale with the number of hyperparameter value choices of a single hyperparameter. In their experiments, the DQN already struggled to perform well with only 10 values for the single hyperparameter.
I would suggest to change this baseline to a DQN that only changes the most important parameter (according to the ablation analysis from the paper). This would give the DQN at most an action space of size 4, which is much easier to learn. I think that would better highlight the importance of tuning all hyperparameters and provide a likely more competitive baseline.

Some of the experimental setup is not immediately clear without the appendix. It would be beneficial for the reader to move parts of the appendix, that describe the experimental setup in more detail, to the main paper. To make room for this I would suggest to move some of the details of Tables 3 or 4 to the appendix instead and only report average ranks and the "$+$/$-$/$\approx$" row. 

-----
-----

## Overall
I am very enthusiastic about the presented work. I believe it provides an interesting extension to the DAC framework which will be interesting to researchers of AutoML/DAC but also for researchers of multi-agent RL. I believe the weaknesses I listed above should be addressed. (I think they can be addressed without too much effort). For now I vote for weak acceptance but I am willing to change my score based on the discussion with the authors and other reviewers.

-----
-----


## References
* [Kirk et al. 2021](https://arxiv.org/abs/2111.09794);  "A Survey of Generalisation in Deep Reinforcement Learning"; https://arxiv.org/abs/2111.09794
* [Lindauer and Biedenkapp 2020](https://www.automl.org/wp-content/uploads/2020/08/AC_Tutorial_2020.pdf); "Algorithm Configuration
Challenges, Methods and Perspectives"; Tutorial at PPSN 2020 and IJCAI 2020, https://www.automl.org/wp-content/uploads/2020/08/AC_Tutorial_2020.pdf
* [Biedenkapp et al. 2022](https://arxiv.org/abs/2202.03259); Theory-inspired Parameter Control Benchmarks for Dynamic Algorithm Configuration; https://arxiv.org/abs/2202.03259
questions: The questions are not ordered in any particular order.
* Why did you not consider any benchmarks from DACBench?
* As you target handling of different parameter types, how would you handle ordinal or categorical hyperparameters, as well as hyperparameters that are using some form of transformation (i.e. log-scaled learning-rates).
* Do you believe your approach is also helpful in the multi-hyperparameter case with hyperparameters of the same type?
* To me it seems that the proposed reward might give higher weight to crossing from positive function values to negative ones. Is my interpretation of that correct? If so, is there any particular benefit from that?
* How did you discretize the neighborhood size?
* How did you normalize the state features?
* How did you limit the frequency for adjusting the weights?
* Are all hyperparameters adjusted at the same frequency?
* How did you select the instances? What exactly are MOPs with similar properties?
* When testing, it is stated that "[...] all the functions are considered in the testing[...]" (line 266). Does that mean that you test on the training set?
* Why do you differentiate between three types of features in the state? Aren't indicators such as hypervolume and other statistics part of the optimization process?
* Why is the reward scaled by $\frac{1}{2}$?
limitations: The limitations are not particularly addressed. For example, a limitation of the work is that it only considers the multi-agent configuration on a single benchmark. Further, from the text it seems that the test set includes the training set which will result in inaccurate assessments on the generalization performance.

----

**During the rebuttal the authors remedied these shortcomings.**
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This work introduces the multi-agent dynamic algorithm configuration problem which models the hyperparameter search of an arbitrary iterative algorithm as a contextual multi-agent MDP. Each agent in the environment is tasked to determine the value of a specific hyperparameter with its actions corresponding to hyperparameter values, states indicating information about the tuned algorithm and rewards indicating performance. An instantiation of this problem is presented based on the MOEA/D evolutionary algorithm as the MaMo environment and an algorithm based on value decomposition networks (VDN) is trained and evaluated in this problem, and compared to using evolutionary and alternative (MA)RL algorithms.
strengths_and_weaknesses: ### Strengths
The primary contribution of this work is the formulation of the MA-DAC problem which models a hyperparameter search over multiple, heterogeneous hyperparameters as a multi-agent decision making problem. While the idea of dynamic algorithm configuration (DAC) is not novel, the framing as a multi-agent problem to the best of my knowledge is novel, interesting and significant.

### Weaknesses
However, the proposed framework lacks generality, the multi-agent algorithm presented alongside does not appear to contain novelty (outside of the modelled problem), and the evaluation is insufficient.

**Major:**
1. Lack of generality of MA-DAC problem modelling: The modelling of the hyperparameter search as a multi-agent decision making problem requires several properties from the underlying to-be-tuned algorithm which appear quite restrictive and are not sufficiently discussed.

    1.1. In particular, the tuned algorithm needs to be iterative with some metric that for each iteration gives a reasonable indication of its future performance. This is not true for e.g. most (MA)RL algorithms where future performance often only becomes visible after thousands if not millions of steps. One could model the entire training of the underlying algorithm as a single transition but in that case each transition would be too costly for this to be computationally feasible.

    1.2. Also, the modelling appears to assume that the tuned hyperparameters can be changed at each iteration of the algorithm. For some hyperparameters and algorithms, this is not possible (e.g. model size in DL).

2. The set of baselines in the experiments seems insufficient. The proposed approach based on the VDN MARL algorithm is only compared to a multi-agent version of UCB, a single-agent centralised controller trained with DQN and the evolutionary approach of MOEA/D. Given its similarity to other MARL algorithms, comparisons to independent learning algorithms such as IDQN, IPPO, and other CTDE learning algorithms like MAPPO, MADDPG and QMIX would be essential to understand the relevance and challenge of the proposed algorithm.

**Minor:**

3. The MA-DAC (M) algorithm is compared to in Table 4 but not included as a column - I strongly suggest to include this as a baseline in the table.
4. The authors suggest that “the importance of (tuned) hyperparameters varies” (l. 315f) because the setting of specific hyperparameters to “reasonable” default settings (l. 310) impacts performance differently. However, it is not clear whether these performances are obtained as a result of the relevance of the hyperparameters or the quality of the choice of the default setting for the different hyperparameters.

questions: 1. For experiments towards RQ2, it is unclear in which exact problems the policy was trained. L. 293 “... the policy is trained on the problems with 3, 5, and 7 objectives.” - does this include all problems with the respective number of objectives?
2. In line 302 it is stated that “Among all the policies, MA-DAC always takes the first or second place ...” - do you refer to MA-DAC (M) for this experiment?

limitations: The proposed problem of MA-DAC appears to have underlying assumptions which limit its applicability to new algorithms (outside of MOEA/D and similar iterative, evolutionary algorithms) and are insufficiently discussed.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: This paper proposes to apply MARL to the dynamic algorithm conﬁguration (DAC) problem and instantiates it on a multi-objective optimization task. The method is mostly well presented and the experiments are illustrated clearly.
strengths_and_weaknesses: Strengths:
1. The researched question, i.e. applying MARL to DAC problems is interesting;
2. The experiments are well conducted;

Weaknesses:
1. The theoretical motivation to use MARL rather than single RL is not clearly analyzed;
2. The theoretical analysis for the different performance of the experiments is lacked;
questions: 1. Line 135-138: “higher rewards do not always imply better performance…”, I don’t understand what it means. How and why does your proposed reward function (equation 2) work?

2. Figure 1 and its corresponding texts are also very confusing. What do you mean by “repeated rewards”? Why switching from good to bad states can still get good rewards?

3. I cannot see any theoretical reason for using MARL on this problem. Specifically, I don’t know why DQN cannot work better than or at least as good as VDN?

4. How do you set the episode length? 

limitations: 1. The theoretical motivation of applying MARL on DAC problems is not convincing, even though the authors argue it by the heterogeneity of configuration hyperparameters. However, that is just a dimension problem, which doesn't mean single-agent RL cannot handle it.
review_title: null

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper addresses the problem of adjusting multiple heterogeneous hyper-parameters of a complex algorithm dynamically, and proposes a general framework, Multi-Agent Dynamic Algorithm Configuration (MA-DAC). The authors gave a concrete application of tuning the hyper-parameters of a popular evolutionary algorithm MOEA/D for solving multi-objective optimisation problems, and the experimental results on benchmark multi-objective problems show the effectiveness of MA-DAC.
strengths_and_weaknesses: DAC (Biedenkapp et al., ECAI’20) has been an effective framework for dynamically adjusting a single type of hyper-parameters of algorithms, while this paper tries to address the more challenging problem, that is adjusting multiple heterogeneous hyper-parameters simultaneously. The authors modeled this problem as a contextual multi-agent MDP where one agent corresponds to one type of hyper-parameter, and applied multi-agent RL algorithms to solve it. 

As far as I can tell, this is the first work to address the dynamic tuning of multiple heterogeneous types of hyper-parameters. The idea of multi-agent MDP modeling is natural, and also reasonable. The framework named MA-DAC is general. I like the authors gave guidance on the setting of elements of multi-agent MDP, which makes the MA-DAC framework easier to be applied. The triangle-shaped reward function encouraging long-term rewards is novel, the effectiveness of which the authors have also empirically validated. Very interesting work!

To show the effectiveness of MA-DAC, the authors considered the MOEA/D (Zhang & Li, TEvC’07), which is a popular evolutionary algorithm for solving multi-objective optimisation problems. They applied MA-DAC to dynamically adjust the hyper-parameters of MOEA/D, including weights, neighborhood size, types and parameters of crossover operator. This is a meaningful and practical application, and also constitutes a difficult benchmark (named MaMo in the paper) for MARL algorithms, which can be independent of interest for the MARL community.

In the experiments, the authors selected the DTLZ and WFG benchmark problems with various number of objectives, three of which are used for training and the others are for testing. They compared MA-DAC with DAC (using one agent to adjust the combination of the four heterogeneous hyper-parameters together), MA-UCB (using four UCB agents to adjust the four heterogeneous hyper-parameters, respectively) and two SOTA adaptive MOEA/D algorithms. Their experimental results clearly show the superiority of MA-DAC (MA-DAC is significantly better in most cases). Especially, the generalization ability of MA-DAC is impressive to me. MA-DAC trained using problems with a single number of objectives can even be better than the compared algorithms trained using problems with various number of objectives.

I have read the appendix as well. The experiments are described in details, and I believe they are reproducible. The codes are also provided.

In my opinion, this is a very good work. The authors studied the challenging problem of dynamically tuning multiple heterogeneous types of hyper-parameters for the first time, proposed a simple, yet novel and general multi-agent RL solution, gave a practical application of tuning the hyper-parameters of MOEA/D, and showed the excellent performance by comprehensive experiments.

I believe MA-DAC would be a supplementary for DAC, as well as a good resource to the AutoML community, and will bring some influence.

The paper is also well written and easy to follow. Minor issues:

- line 17, “problems classes” -> “problem classes”
- line 31, “the tuning learning rate” -> “the learning rate tuning”
- line 72, “the the” -> “the”
- Tables 3, 4, S3, S4, S5, S6, caption, “The best mean value of each problem” -> “The best mean value on each problem”
- Table 4, caption, it would be better to clearly say “MA-DAC (M) in Table 3”, which is easier to be understood.
- line 401, “nature” -> “Nature”
- line 40 in the appendix, “lines 4-9” -> “lines 4-10”
- line 43 in the appendix, “reproduction” -> “crossover”
- line 136 in the appendix, “at step $t$” -> “by step $t$”?
- Table S3, caption, “the MA-DAC” -> “MA-DAC”

For my major concerns, please see the questions.

questions: - I did not see any discussion on the scalability of MA-DAC. The application of MaMo involves four heterogeneous hyper-parameters. If there are more hyper-parameters, how about the runtime complexity of MA-DAC?

- For RQ2 in the experiments, “MA-DAC (M) … trained on the problems with all 3, 5, and 7 objectives” What are the training problems? Still DTLZ2, WFG4 and WFG6?

- If I have not misunderstood, MA-DAC (M) in Table 3 is just MA-DAC in Table 2. If so, why are the results slightly different?

- The states in Table S1 defined for MOEA/D seem to be reasonable and comprehensive. Can they be directly applied when tuning the hyper-parameters of other MOEAs (e.g., NSGA-II and SPEA)? I’d like to see some discussion. 

- lines 109-110 in the appendix, what does $x$ mean in OP3 and OP4?

- In the experiments, you used the popular benchmark multi-objective problems, DTLZ and WFG. I understand these are standard test problems. But if you can add some real-world problems, the contribution will be more significant.

limitations: YES
review_title: null

Meta-review: metareview: After reading the reviews, feedbacks and discussions, I lean towards acceptance. Reviewers are all in favour of acceptance with different levels of enthusiasm. Some reviewers found particularly interesting that MARL methods could be applied to DAC problems but other reviewers were not entirely convinced why MARL is more suited that single RL or even classical optimization techniques for this particular problem. However, this could generate an interesting discussion between the DAC and MARL communities and this is the main reason why I vote for acceptance. The authors should consider adding a discussion section explaining why MARL could be fundamentally more advantageous/general than single RL methods in addition to their exhaustive experimental section.   
confidence: Certain
Decision: Accept