Thank you for the confirmations and suggestions.

Response to the weaknesses

1. The proposed method in this work is agnostic to any bandit algorithms. While it is true that employing more sophisticated bandit algorithms could enhance performance by leveraging pertinent prior knowledge, it's common to lack such priors. Therefore, we focus on the most general case, wherein the environment within the bandit context dynamically changes due to training neural solvers. We choose Exp3 to address potential adversarial effects under these circumstances.

2. In the revised version of Section 3.2, we have made efforts to eliminate redundant content for improved clarity.

   Assumption 1 comes from previous impactful works so we consider it to be a reasonable starting point. From this assumption, the similarity in this work is defined as: $\operatorname{Similarity}\left(T_j^i, T_j^i\right):=\cos \left(\nabla L_j^i\left(\Psi^i\left(t_1\right)\right), \sum_{t=t_1}^{t_2} \eta_t\mathbb{1}\left(a_t=T_j^i\right) \nabla L_j^i\left(\Theta^i(t)\right)\right)=1.$ This similarity holds true only when the two gradient vectors share the same direction, i.e., when:$\nabla L_j^i\left(\Psi^i\left(t_1\right)\right)= c\sum_{t=t_1}^{t_2} \eta_t\mathbb{1}\left(a_t=T_j^i\right) \nabla L_j^i\left(\Theta^i(t)\right)$ for some constant $c>0$. The reward for updating bandits is defined as the cosine similarity, and the impact of $c$ is nullified.

where $\langle\cdot,\cdot\rangle$ is the inner product for vectors. Therefore, setting $c=1$ results in Eq. (8) in the revised paper:$\nabla L_j^i\left(\Psi^i\left(t_1\right)\right)= \sum_{t=t_1}^{t_2}\eta_t \mathbb{1}\left(a_t=T_j^i\right) \nabla L_j^i\left(\Theta^i(t)\right).$

Response to the questions

1. We appreciate the reviewer's observation. $\eta_t$ represents the learning rate used in training neural networks. To enhance clarity, we have included a definition for $\eta_t$ in the revised Proposition 1.

2. The computation involves the cosine similarity between all pairs of tasks, resulting in a space complexity of $n N_{\text{share}} + N_{\text{task-specific}}$, where $n$ is the number of tasks, $N_{\text{share}}$ is the parameter count of shared modules, and $N_{\text{task-specific}}$ is the parameter count of task-specific modules. Importantly, this complexity is consistent with that of typical MTL baselines examined in our paper.

3. The comparison in Fig. 2 might be perceived as unfair due to the difference in training epochs. Our method demonstrates superiority by training a single model for 1000 epochs compared to 12 models trained under "COP-n," each for 1000 epochs (i.e., $1000$ epochs vs $12\times 1000$ epochs in total). Despite this discrepancy, our neural solver's performance on a specific COP is either better or competitive with the results from 3 models obtained by STL (trained for a total of 3000 epochs).

   The statement "...impossible for STL..." is grounded in the fact that STL exclusively focuses on one type of COP with a specific problem scale. Consequently, STL not only exhibits poor performance on different problem scales due to limited generalization ability but also fails to adapt to various COP types, given the presence of task-specific modules.

Thank you for the efforts on proposing these comments and questions.

Response to the weaknesses

1. The proposed method affords flexibility in the selection of bandit algorithms, with the primary objective of introducing the concept of employing bandits to dynamically guide training. Due to space constraints, we defer an in-depth discussion of bandit algorithms to Appendix C. And we commit to providing enhanced justifications for the chosen algorithms in the revised version.
2. (Also response for strength 1)
   • Regarding point a), while it is known and intuitively correct, our contribution lies in providing empirical justification for these observations in Fig 3. This not only validates the efficacy of our method but also highlights its potential application on tasks where task relationships are unknown.
   • For point b), while positive or negative transfers does exist among different tasks, our contribution is quantifying this phenomenon by the influence matrix. Additionally, we introduce a novel observation that different types of COPs may not significantly influence each other during training, representing a new contribution to ML4CO community.
   • Concerning point c), the understanding that easier tasks require less budget is evident. However, the challenge lies in resource allocation when no priors on the tasks are available, and our proposed method is designed to address this practical concern.
3. The analysis of budget allocation is detailed in Appendix G, supplemented with additional descriptions. In summary, Discounted Thompson Sampling, Exp3, and Exp3R, designed to handle changing and potentially adversarial environments, exhibit nearly identical budget allocations. In contrast, naive Thompson Sampling fails to adapt, leading to suboptimal performance.

Response to the questions

1. In the ML4CO community, prior RL-based works have typically trained one model for a specific type of COP with a designated problem scale. Consequently, addressing various types of COPs with different problem scales can be conceptualized as a MTL problem for two reasons: a) The existence of task-specific modules that cannot be universally shared across different COP types. b) Variations in the MDP transition steps occur for different problem scales within a COP.

   Concerning Appendix F, as acknowledged, differences among tasks cannot be effectively captured through the loss. This limitation is explicitly discusses in Section 3.1: "...such measurement is invalid in our context because there are no significant differences among tasks." Consequently, we adopt gradient-based methods to distinguish tasks. In the discussion of Fig. 3(b), we illustrate that using the inner product between gradients as reward can be misleading due to varying gradient norms among tasks. To address this, we employ cosine similarity, focusing solely on the angles between gradients.

2. The average reward serves as the basis for updating the bandit algorithm, and the exploration-exploitation procedure is entirely governed by the bandit algorithm.

3. As you rightly pointed out, the row-sum signifies the influence of all tasks on one specific task, while the column-sum represents the influence of one task on all tasks collectively, which aligns with the motivation of selecting a task that maximally benefits all tasks.

4. Our algorithm prefers tasks that provide maximal benefits to all tasks rather than solely focusing on the most challenging task. To provide further insight, we apply the proposed method on three tasks: TSP20, TSP50, and TSP100, with a clear difficulty level follows the order TSP20<TSP50<TSP100. The resulting budget allocation is distributed in the ratio of 0.326, 0.341, and 0.333, respectively, with a larger proportion of resources allocated to TSP50. This allocation strategy is justified both empirically and through the examination of the influence matrix:a) In the ML4CO community, it is well-known that training tasks of intermediate difficulty can benefit those on both sides of the difficulty spectrum. b) The influence matrix, shown below, provides support for this allocation strategy: Training TSP50 has a higher similarity contribution of 0.126 to TSP20 and 0.137 to TSP100, compared to the contribution from TSP100 to TSP20 (0.031) and from TSP20 to TSP100 (0.025). | | | | |-|-|-| | 1. | 0.126 | 0.031 | | 0.124 | 1. | 0.153 | | 0.026 | 0.137 | 1. | | | | |

5. The 1:2:3 allocation is deemed appropriate for categorizing tasks into easy-median-hard levels. We intend to convey the idea that better resource allocation yields superior results. As evidenced in Table 2, STL_bla outperforms STL_avg, highlighting the significance of proper resource allocation. While alternative allocation ratios could be explored, our focus lies in demonstrating the effects rather than determining the optimal allocation ratio. Thank you for pointing out this, we have revised the descriptions.

Thanks for your feedback.

• Using the inner product can lead to misleading updates in bandit algorithms. In Section 3.2 of our paper, we provide a clear explanation for why cosine similarity is preferable over the inner product. Specifically, we state:

  "... the inner products of gradients from different tasks can significantly differ at scale. This will mislead the bandit’s update seriously since improvements may come from large gradient values even when they are almost orthogonal."

  To further substantiate this intuition, we present Figure 5(b) in Appendix F, which visualizes the gradient norms for each task on a logarithmic scale. The figure clearly demonstrates that the gradient norms are not uniformly distributed on the same scale. Consequently, this discrepancy in scales leads to a preference for training on tasks with larger gradient magnitudes.

• Apologies for the lack of clarity in the table. Here is the revised table with labeled rows and columns:

  	TSP20	TSP50	TSP100
  TSP20	1.	0.126	0.031
  TSP50	0.124	1.	0.153
  TSP100	0.026	0.137	1.

  Regarding the reference, we can provide two influential works, namely Figure 3 in [1] and Figure 5 in [2], which provide insights supporting this claim of "In the ML4CO community, it is well-known that training tasks of intermediate difficulty can benefit those on both sides of the difficulty spectrum. Both studies demonstrate that the model trained on TSP50 exhibits the best average performance on TSP20, TSP50, and TSP100, in contrast to the models trained on TSP20 and TSP100, which perform poorly on tasks outside their training scale too far. Intuitively, this claim is supported by the fact that TSP50 lies between TSP20 and TSP100 in terms of the problem scale, making it easier to generalize performance to both sides. Conversely, the model trained on TSP20(TSP100) performs poorly on TSP100(TSP20) due to the large discrepancy in scale between TSP20 (TSP100) and TSP100 (TSP20). This observation can be verified by the above influence matrix: The rewards for training each task w.r.t. column sum are 1.151 1.264 and 1.185, where training TSP50 has the largest reward, meaning the most positive effects on all tasks.

[1]. Joshi C K, Cappart Q, Rousseau L M, et al. Learning the travelling salesperson problem requires rethinking generalization[J]. arXiv preprint arXiv:2006.07054, 2020.

[2]. Kool W, Van Hoof H, Welling M. Attention, learn to solve routing problems![J]. arXiv preprint arXiv:1803.08475, 2018.

Thanks for your endorsement.

Response to the weaknesses

1. We aim to clarify our motivation in the following manner:

   • The task relationships among COP has been observed but lacks both experimental and theoretical validation. Our approach begins by empirically substantiating these observations through the proposed MTL algorithm. Furthermore, at the implementation level, training neural solvers for COPs typically demands more time compared to tasks in classical MTL benchmarks. Traditional MTL methods, involving simultaneous training of all tasks, prove to be time-consuming and memory-intensive. As evidenced by the comparisons in Table 3, our approach, which selectively trains one task at each time slot, demonstrates efficiency and effectiveness. This is particularly notable in terms of training flexibility and cost-effectiveness, as emphasized in the discussions on page 7 (Table 3) and Appendix D.

     We extend our method to other MTL scenarios, as detailed in Appendix I. The results indicate that there is no single MTL method consistently excelling across all scenarios, and in certain cases, they may even underperform compared to a naive MTL approach (refer to Table 7). However, in scenarios where traditional MTL methods show efficacy, our approach maintains competitive performance (refer to Table 6).

   • First of all, the heuristic reward design, grounded in the cosine similarity between gradients from different tasks, aligns with widely accepted practices established in influential prior works (Wang et al., 2020; Yu et al., 2020). Secondly, this design choice is default for us and is derived from fundamental loss decomposition (Proposition 1), providing a theoretical foundation. Experimentally, the results obtained with this reward align with observations in the field of ML4CO. Consequently, our reward design stands as both theoretically sound and empirically validated.

2. • We have made significant improvements to our presentation by incorporating error bars, showing the performance on 10,000 test instances from each COP, as shown in Figure 8 in Appendix J of the revised version.
   • The work by Fifty et al. (2021) focuses on MTL centered around task grouping. This approach necessitates an offline pre-training phase for constructing task relationships, followed by training the resulting groupings for evaluation. Conversely, our work and the considered baselines are all online MTL methods, involving training the model on-the-fly and conducting evaluations immediately post-training.

Response to the questions

1. The enhanced efficiency of our proposed method stems from the changing in the training paradigm. Unlike typical MTL methods that simultaneously train all tasks at each training time slot, our method adopts a more targeted approach by selecting and training only one task per slot. This streamlining significantly reduces computational load and accelerates the training process. Regarding the computation of the influence matrix, it's noteworthy that other MTL methods typically employ specific heuristics to balance the loss from each task, and they do not compute an influence matrix.

2. The naive co-training strategy, referred to as Naive-MTL, is presented in Table 2. In addition, we include the results of random sampling in the global response.

3. Ideally, Assumption 1 consistently holds as the cosine similarity of a gradient vector with itself is always 1. In our specific context, confirming Assumption 1 requires precise computation of $\nabla L_j^i\left(\Psi^i\left(t_1\right)\right)$, a domain less explored for neural networks, to the best of our knowledge. Nonetheless, even though the exact verification of this assumption is intractable, the empirical results align with widely accepted observations in ML4CO. Thus, we assert that it holds empirically.

4. In Fig 3(a), the positive or negative signs merely signify the direction of influence on other tasks and it's reasonable to have negative transfers within the same COP types if their scales are distinct too much.

   As for the positive entries in the off-diagonals, Fig 3(b) provides a more detailed illustration, and we have discuss this comprehensively in Section 4.2: "Notably, tasks belonging to the same type of COP are highly influential towards each other due to the large variance of their influence values. Conversely, influences between different types of COPs are negligible, evident from the influence values being concentrated around 0."

5. In this work, we concentrate on the tasks at hand, and no zero-shot transfers are contemplated. The generalization ability of ML4CO methods poses a persistent challenge, often yielding unsatisfactory results when applied to unseen scenarios without additional efforts. The model derived by our method can serve as a pre-trained model for potential integration with fine-tuning techniques. This avenue holds promise for future exploration but falls outside the scope of the current paper.

Thank you for the efforts on proposing these comments and questions.

Response to the weaknesses

• This work represents a pioneering effort in addressing multiple COPs simultaneously using a unified model. It goes beyond mere amalgamation of existing methodologies within the COP context, and our distinct contributions can be elucidated as follows:
  1. About the similarity measure: a) While (Wang et al. (2020) and Yu et al.) heuristically propose a gradient-based similarity measure and discuss its rationale, our approach starts from a foundational perspective through loss decomposition (Proposition 1). This establishes a theoretical foundation for the heuristics employed by (Wang et al. and Yu et al.). b) The similarity measure serves as a pivotal assumption (Assumption 1) that facilitates the design of our proposed algorithm, circumventing the need for gradient estimation in the mean value theorem (Equation (8) in the revised paper): $\nabla^TL^i_j({\Psi}^i(t_1)) = \sum_{t=t_1}^{t_2}\eta_t\mathbb{1}(a_t=T^i_j) \nabla L^i_j(\Theta^i(t))$
  2. Concerning the application of bandit algorithms in MTL: Both theoretically and practically, our methodology and training paradigm differ from Bandit-MTL (Mao et al., 2021), which necessitates collecting loss information from all tasks and training them collectively at each time slot. In contrast, our approach involves selecting and training a single task using the bandit algorithm, resulting in superior performance (refer to Table 2) and enhanced efficiency (refer to Table 3).
• It is essential to acknowledge that bandit algorithms thrive under specific assumptions about rewards, environmental properties, and more. The theoretical guarantees sought by the reviewer can be extrapolated if our proposed gradient-based reward and the environment, as simulated by the training process of neural networks, adhere to the corresponding assumptions. Although investigating the correlation between parameter variations induced by training neural networks and the bandit setting's environmental aspects is an intriguing avenue, we believe it surpasses the scope of this work.
• For the experiments,
  1. When considering the same training budget, the primary focus should be on the overall performance across all tasks, indicated by the Avg. Gap in Table 2, where our method excels. Notably, the superior performance achieved by $\text{STL}{\text{avg.}}$ is confined to relatively straightforward tasks, such as COPs with smaller problem scales. However, this approach tends to disproportionately allocate resources to these easier tasks, resulting in inadequate training for more challenging ones. A comparison between $\text{STL}{\text{avg.}}$ and $\text{STL}_{\text{bal.}}$ reveals that the latter achieves better overall performance (Avg. Gap) through more judicious resource allocation.
  2. In the context of the same training epochs, it is crucial to emphasize that the comparison involves a single model generated by our method after 1000 epochs versus 12 models produced by the corresponding STL training scheme, each trained for 1000 epochs. Our objective is to underscore the remarkable generalization ability and efficiency of the neural solver obtained through our method, manifested in the following aspects: a) Our method yields a model capable of solving diverse COPs, a feat challenging for models trained on specific COPs due to disparate network structures and distinct state transition logic. b) Considering performance on the same kind of COPs, our method outperforms in CVRP, OP, and KP, as evidenced by the "Mean Results" in comparison with COP-small, COP-median, and COP-large. This advantage is attributed to the fact that models trained on one problem scale may perform badly on different scales. Even for TSP, considered the simplest among the four problems, our method maintains competitive performance. c) The training time for our method, averaging 0.56 minutes per epoch (Table 3), is significantly shorter than the most resource-intensive alternative (see Table 1), yet it effectively solves diverse COPs.

Response to the questions

• This observed phenomenon aligns with the considerations surrounding the generalization ability of neural solvers for COPs and has been documented in prior studies, as illustrated in Fig. 5 in (Kool et al., 2019) and Fig. 3 in [1]. Our empirical validation in Fig. 3 within this paper further substantiates this observation. Within the ML4CO community, the challenge of effectively generalizing a model trained on one problem scale to another remains an open question. This knowledge gap motivated our exploration and proposal of MTL methods, specifically designed to train neural solvers capable of handling COPs across various problem scales.
• Thanks for the advice on the ablation study, we show the results of random policy in the global response.

[1] Learning the travelling salesperson problem requires rethinking generalization