Sequential Stochastic Combinatorial Optimization Using Hierarchal Reinforcement Learning

We generally appreciate your comments. However, we would like to emphasize that our primary contribution lies in the development of the HRL framework for SSCO problems—an area that, to the best of our knowledge, has not been explored before. To ensure stability and convergence, we have devoted significant effort to various aspects of the framework design, including (but not limited to) the introduction of null actions, lower-layer reward and option design, layer-wise learning method selection, and the wake-sleep training procedure. Furthermore, we provide a convergence analysis and briefly show its connection to Stackelberg games. Nonetheless, we acknowledge certain limitations and will do our best to address your concerns.

W1: In fact, we provided the details of the neural network we use. See Appendix C.1.

W2: See general response question 5. Lines 316-317 state that they are highly interdependent instead of "independent".

W3: Our choice of $T$ and $K$ in the AIM problem is based on [1]. Additionally, the baseline for the budget allocation policy also comes from their paper. While we evaluate our model on different graphs, we utilize their methods as baselines for comparison. Anyway, as mentioned in our general response, we will provide RL-based baselines in the near future to strengthen our evaluation.

Q1: See general response Q3. The higher-layer decision, i.e., the budget, provides a termination condition for the lower layer. This enables the lower layer to determine when to stop the node selection process. The reason the lower layer is deterministically activated is that this is the basic setting of the AIM problem: once a node is chosen as a seed, it becomes activated. After the node selection process terminates, the agents interact with the environment, receive rewards, and transition to the next state.

Q2: See general respnse 4. We do simulation for $R_t(s^I_t, A_t\cup\{a_{t,v}\})$ and $R_t(s^I_t, A_t)$. It means, after we choose the action set like $A_t$, we can peform a state transition and then get this reward. We simulate this for 10 times to get the average value.

Q3: We use an action-in architecture for the following reasons 1) For different tasks, the total budget varies. Adopting an action-out architecture would mean that the total budget becomes a network parameter, which limits the ability to generalize to tasks with different budgets. 2) After selecting a portion of the budget, subsequent decisions can be made based on the remaining budget. However, with an action-out architecture, the input would include impossible actions, even if a mask is applied, making it less efficient. 3) Finally, the action-in structure is inherently more suitable and effective for our objective of achieving generalization across tasks.

Please refer to slide 7 of Lecture 6: Value Function Approximation, from David Silver’s lecture on Reinforcement Learning.

Q4: First, these two examples, AIM and RP, denote the case with high stochasticity and low stochasticity, respectively. The baselines of AIM comes from [1]. It can be applied to RP. However, since RP is a low stochasticity problem, we use better baselines. For example, GA can usually find the global optimal solution is deterministic case. So we use it in the low-stochasticity case. However, it cannot be applied to high-stochasticity case like AIM. We evaluate our approach on different datasets (their datasets are too large); however, we did provide a comparison between the performance of our method and their methods.

If our response has addressed some of your concerns, we would highly appreciate it if you could re-evaluate our work and consider raising the score.

References: [1] Tong, G., Wang, R., Dong, Z., & Li, X. (2020). Time-constrained adaptive influence maximization. IEEE Transactions on Computational Social Systems, 8(1), 33-44.

Thank you for the insightful comments. We'll try our best to clarify your concerns.

W1-2: Thank you for pointing it out. We acknowledge this is one of our shortcomings. In fact, we do have some real-world datasets, but the large number of nodes results in significant computational overhead. Moreover, real-world datasets often exhibit certain patterns, such as clustering characteristics. These patterns are easier for our RL-based algorithm to recognize, which can, in turn, achieve even better results. Anyway, we will soon supplement the results on real-world data.

W3: The reason why different tasks require different graph embedding techniques is that, compared to traditional CO tasks, SSCO tasks generally involve more complex graph information. As a result, a mroe sophisticated structure is needed to effectively handle four types of information: (1) node information, (2) edge information, (3) topological structure information, and (4) global information. When tackling this task, we attempted to use a unified graph embedding method, but the results were unsatisfactory. For instance, we tried using GCN, which cannot effectively utilize edge information and fails to accurately represent the graph structure for both types of tasks. Developing a generic graph embedding technique might be worthy of a new paper; however, that is not the focus of this work. Nonetheless, our next work involves proposing a graph embedding method tailored for RL Q-value representation based on a graph foundation model. Building on previous works, such as [1], we provide corresponding theoretical proofs to support this approach.

Q1: See W1-2.

Q2: Our work is parallel to the effort in [2], and their techniques can certainly be applied to extend our framework to handle extremely large graphs, such as those with billions of nodes. However, scaling to this level requires significant effort and computational resources, so we are unable to provide further experiments for such large-scale instances at this time.

Q3: See W3.

Q4: Computational complexity in RL literature is indeed challenging to analyze. To the best of our knowledge, there are no existing works that provide a comprehensive complexity analysis for similar frameworks. While we acknowledge the importance of such an analysis, our current focus has been on the practical effectiveness and scalability of the WS-option framework.

Q5: We have already provided ablation stuides for the wake-sleep training procedure and the layer-wise learning method selection. See lines 378-391.

Q6: See Appendix C.5 for the reason why we use t-test instead of mean-standard deviation.

If our response does not effectively address your concerns, please feel free to ask further questions.

References: [1] Xu, K., Hu, W., Leskovec, J., & Jegelka, S. (2019). How powerful are graph neural networks?. International Conference on Learning Representations. [2] Manchanda, S., Mittal, A., Dhawan, A., Medya, S., Ranu, S., & Singh, A. (2019). Learning heuristics over large graphs via deep reinforcement learning. arXiv preprint arXiv:1903.03332.

Experiments on power2500 dataset

The result is consistent with what we said before:

Moreover, real-world datasets often exhibit certain patterns, such as clustering characteristics. These patterns are easier for our RL-based algorithm to recognize, which can, in turn, achieve even better results. Anyway, we will soon supplement the results on real-world data.

We appreciate the insightful comments and questions from the reviewer. Now we try to address concerns from the reviewer.

W1.a: See general response. The detail is provided in Appendix A.1. The biggest problem of single-agent RL is that it cannot deal with the interdependency between two actions, while HRL does.

W1.b: The state space indeed doesn't include the option, since option can be seen as another state. Note that the q-function for the lower-layer is $q^{II}(s, o, a)$, so the option can also be seen as a state. As a result, the "real state" here is $(s,o)$. See general respond for the reason of simplifying the option in the lower layer. The detail is provided in Appendix A.2.

W1.c: Since the higher-layer policy will change in the begining of the training if we don't use a sleep stage, it leads to the unstability of the second layer. See general response and Appendix A.2 for more details of our wake-sleep training procedure. In fact, the 1/2 of training doesn't matter in this case. The key idea is to make the second layer converges first (the reason is provided in Appendix A.2 and A.5), so we can just increase $N$ to achieve it. However, we will also provide an ablation study for different choices like N/3, and show what happens if the second layer doesn't coverge. This is independent of problems since our goal is to make the lower layer converge.

W1.d: This is the basic setting of RP problem, where the profit of each node changes every day. So we add this U just to model the fluctuation of the profit. We can also use like a guassian noise. The choice of the noise doesn't matter. As a result, we choose a simple one because we want a case of low stochasticity compared with AIM. This is a good point that the expectation is 0. This is also the magic of our null action, which defines the the expected reward when moving to the next day if we do not select any node in the current state. So if the reward of null action is exactly the expectation of noise here. Hence, it will affect the marginal reward according to our definition. We can consider a case where all the noise is accidentally positive, which means the profit will increase over days. Then we cannot find an optimal solution. Further, the combined profit will decrease as the number of budget increase at time step t. This also leads to a suboptimal solution. See lines 67-73 for our motivation of SSCO problems.

W1.e: See Appendix C.5.

W2.a. We will provide RL baselines soon, although it's not quite suitable for this case.

W2.b. First, these two examples, AIM and RP, denote the case with high stochasticity and low stochasticity, respectively. The methods used in AIM can be applied to RP. However, since RP is a low stochasticity problem, we use better baselines. For example, GA can usually find the global optimal solution is deterministic case. So we use it in the low-stochasticity case. However, it cannot be applied to high-stochasticity case like AIM.

Q1: We ackonwledge that finding a quite strong baseline is difficult. As a result, we design a "score" policy, which is essential a greedy policy. However, we leverage the feature of AIM problem -- the difinition of propogation probability. Based on this, we use the outdegree of one node combined with the indegree of all its inactive neighbors to get a score which is truly the expected influence of that node in two steps. Since the propagation probability is quite small, the influence of one node can just spread for 2 time steps in some cases (for some nodes). So this problem-specific design is indeed a strong baseline.

Q2: Sorry for the confusion. Note that we do simulation for $R_t(s^I_t, A_t\cup\{a_{t,v}\})$ and $R_t(s^I_t, A_t)$. It means, after we choose the action set like $A_t$, we can peform a state transition and then get this reward. We simulate this for 10 times to get the average value. The action samples are obtained when we run the episodes (see Algorithm 2), and then we use the action sample to generate corresponding transitions for the lower layer (see Algorithm 3). When we do the simulation, the choice of actions is already given.

Q3: The reason is we didn't evaluate the model on the same graph. And the score depends on the graph that we test.

Feel free to ask any questions if we haven't make them clear enough.

Thanks a lot for your comments. We now understand what's your concerns.

Am I missing something? From my understanding, the discussion provided in A.3.1 does not convince me that this information is not useful.

One point we didn't make it clear is that when we train the policies of both layers together, we have included the budget information (e.g., the specific value of budget) for both agents. Then, what the higher layer conveys to the lower layer is exactly the termination condition. The is also how the option framework works [1]. Then, we discuss the budget irrelevance in Appendix, which means in the option framework, the higher layer just conveys the termination condition to the lower layer, and the lower layer is solely aware of this termination condition and nothing more.

This question essentially is how the option framework proposed by Sutton [1] works. Although it is not the focus of our work (we just used it), we are happy to address your concern regarding this matter.

We also have the ablation studies for this:

We mentioned

we can consider a case where all the noise is accidentally positive, which means the profit will increase over days. Then we cannot find an optimal solution.

to address your concern:

What are the consequences on the sequentiality of the problem (i.e., how much does this change compared to solving everything in one shot)?

In other words, in this case, if we allocate all the budget at the first time step, we cannot get the optimal solution, as profits will increase over subsequent days.

Does this mean all the results shown in the paper are performed on a single graph for each experiment? How many seeds did you run for each algorithm?

Although we train the model on different graphs following the same distribution, we test the model on a single random graph (fixed seed, or given real-world data) for each experiment. However, we do not use the same graph for all experiments. Does this make sense? The $n$ represents the graph size.

References:

[1] Richard S Sutton, Doina Precup, and Satinder Singh. Between mdps and semi-mdps: A framework for temporal abstraction in reinforcement learning. Artificial Intelligence, 112(1-2): 181–211, 1999.

We have updated the paper with following experiments:

• Ablation studies for 1/2 training time.
• Test on real-world data
• Ablation studies for lower-level options (budget to binary indicator)

We also add the RL-baseline here.

This result serves as a baseline using single-agent RL. We do not employ a single agent with two distinct action spaces because these action spaces are interdependent. Instead, our single-agent RL framework is built upon our lower-layer agent, allowing the agent to select multiple actions (nodes) at each time step. We incorporate a null action as the termination node, indicating the end of the current time step.

We use the same number of training epochs for both approaches; however, it is evident that the performance of single-agent RL is worse than that of our HRL framework. This discrepancy highlights an inherent advantage of HRL: enhanced sample efficiency. HRL achieves this by decomposing the action space into smaller, more manageable subsets, thereby facilitating more efficient training. To improve the performance of single-agent RL, it may be necessary to utilize a more sophisticated network architecture. The SSCO problems are inherently complex. While single-agent RL can be applied, it requires extra effort to carefully design and tailor its architecture. Moreover, single-agent RL is often not generalizable across different complex tasks. In contrast, the HRL framework provides a more interpretable structure and demonstrates superior adaptability to complex tasks. As discussed in Appendix A.1, these types of problems are essentially bi-level optimization problems, making HRL a natural choice for addressing them.

Kind regards,

Authors