Sequential Stochastic Combinatorial Optimization Using Hierarchal Reinforcement Learning

Authors: Xinsong Feng, Zihan Yu, Yanhai Xiong, Haipeng Chen
Primary area: optimization
Keywords: Sequential Stochastic Combinatorial Optimization, Hierarchal Reinforcement Learning, Graph

Abstract:
Reinforcement learning (RL) has emerged as a promising tool for combinatorial optimization (CO) problems due to its ability to learn fast, effective, and generalizable solutions. 
Nonetheless, existing works mostly focus on one-shot deterministic CO, while sequential stochastic CO (SSCO) has rarely been studied despite its broad applications such as adaptive influence maximization (IM) and infectious disease intervention. 
In this paper, we study the SSCO problem where we first decide the budget (e.g., number of seed nodes in adaptive IM) allocation for all time steps, and then select a set of nodes for each time step. The few existing studies on SSCO simplify the problems by assuming a uniformly distributed budget allocation over the time horizon, yielding suboptimal solutions. We propose a generic hierarchical RL (HRL) framework called wake-sleep option (WS-option), a two-layer option-based framework that simultaneously decides adaptive budget allocation on the higher layer and node selection on the lower layer. 
WS-option starts with a coherent formulation of the two-layer Markov decision processes (MDPs), capturing the interdependencies between the two layers of decisions. Building on this, WS-option employs several innovative designs to balance the model's training stability and computational efficiency, preventing the vicious cyclic interference issue between the two layers. Empirical results show that WS-option exhibits significantly improved effectiveness and generalizability compared to traditional methods. Moreover, the learned model can be generalized to larger graphs, which significantly reduces the overhead of computational resources.

Decision: accept (poster)
Reviewer scores: 6, 6, 6

Reviews and discussion:
<thread>
creation date:
1730403146628

thread_type:
official_review

<thread_object>
creator: reviewer_r7hz

<content>
summary:
This work proposes WS-option, a hierarchical RL approach for sequential stochastic combinatorial optimisation (SSCO). The setting is formulated as a 2-layer MDP, with the higher level policy - trained using an MC approach - learning the budget allocation, while the lower level policy - trained using Q-learning - deciding on the node selection. The key idea, denoted as wake-sleep (WS), is to avoid the adversarial dynamics and instability during training, by fixing the higher level policy for the first half of the training procedure.  The approach is evaluated in two settings, adaptive influence maximisation and route planning.

strengths:
The work provides a formulation of sequential stochastic combinatorial optimisation problems as a 2-layer MDP, facilitating the application of RL methods for this setting. It also proposes a hierarchical RL framework, the WS-option, for solving such settings.

weaknesses:
While the work has some merits in terms of problem formulation under the HRL framework, I argue it lacks a sufficient algorithmic contribution, a comprehensive evaluation and remains generic in many of the implementation details and experiments. I provide below more details and raise also questions that would allow a better comprehension of the work. 

The provided details are insufficient to understand and reproduce the work. As far as I understand, Double DQN is used for both policies, but the higher level uses an MC update method, with an action-in network, trained with offline trajectory data gathered by the average budget fixed policy. Providing the complete neural architecture details, number of layers and sizes would improve this issue. Also please see Q3.

I am not sure the convergence analysis for the tabular case is complete and correct, since it does not discuss the dependency between the Q-value of the two layers in terms of how the reward is defined. Eq. 4 claims consistency between layers for the reward definition, but this is not further discussed or supported. See Q2 for further questions on the reward definition. Furthermore,  lines 316-317 state that the Q-functions of the layers are independent, but as detailed in the proof of Theorem 1, this is not the case. 

For the experiments, it is not clear in the AIM case, which settings from [1] are used and how the results compare to the ones in the referenced work. I also argue that the baseline selection is weak, only looking at fixed or heuristic based methods. Similar remark stands for the RP case, with no details or references provided for the GA approach. See Q4. 

[1] Guangmo Tong, Ruiqi Wang, Zheng Dong, and Xiang Li. Time-constrained adaptive influence maximization. IEEE Transactions on Computational Social Systems, 8(1):33–44, 2020.

Minor remarks:
- I advise to avoid using abbreviations without introduction (e.g., WS, MC, TD lines 88-96, HER line 150)
- typos: adpative (line 219), MD (line 365)

questions:
Q1. The problem formulation proposes to learn a higher level policy for the budget allocation and a lower level policy for the node selection. I failed to understand, given the simplification of the option from the actual budget to a binary value, how the option termination is taking place. Or in other words, how is the connection between the budget and sequence of selected nodes being made in the activation/propagation process, especially since in the lower level the nodes are deterministically activated.

Q2. Secondly, I was also not able to properly grasp the marginal reward calculation (Eq. 4). Could you please provide additional details on the simulation averaging and scaling procedure and its importance on the training stability. Also, how does this definition ensure consistency between the MDPs?

Q3. Could you provide more details and a reference for the action-in architecture and its role in generalisation?

Q4. Could you provide a motivation for the baseline selection and also explain how the results compare to Tong et al. [1].
</content>
</thread_object>

</thread>
<thread>
creation date:
1730641864970

thread_type:
official_review

<thread_object>
creator: reviewer_zngf

<content>
summary:
The paper introduces a novel hierarchical reinforcement learning (HRL) framework, WS-option, which addresses the sequential stochastic combinatorial optimization (SSCO) problem. This framework is innovative as it combines budget allocation and node selection in a two-layer option-based structure, which is a creative approach not commonly seen in the prior works.

strengths:
1.The authors have formulated a generic class of SSCO problems, which is an original contribution to the field. This formulation allows for a more structured approach to solving a broad range of combinatorial optimization problems with stochastic and sequential elements.
2.The paper presents a rigorous methodology, with a clear definition of the Markov decision processes (MDPs) for both layers of the HRL framework. The authors have thoughtfully designed the MDPs to capture the interdependencies between the layers, which is crucial for the model's performance.
3.The paper includes a theoretical analysis of the algorithm's convergence, which is a strong point. The theorems provided offer a solid foundation and justify the effectiveness of the proposed approach.

weaknesses:
1.The paper primarily uses synthetic datasets for experiments, which might not fully capture the complexities of real-world scenarios. Including datasets from diverse real-world applications could strengthen the validity of the results.
2.The paper primarily uses synthetic datasets for experiments, which might not fully capture the complexities of real-world scenarios. Including datasets from diverse real-world applications could strengthen the validity of the results.
3.The paper notes that each new problem may require a new graph embedding technique, which adds complexity to the framework's implementation. Further exploration into developing model-agnostic or more universally applicable graph embedding techniques could enhance the framework's usability across different domains.

questions:
1.Will the WS-option framework's performance vary significantly when applied to real-world datasets compared to synthetic ones? Could the authors share any insights or preliminary results if this framework has been tested on real-world data?
2.How does the WS-option framework scale in terms of computational resources and time when applied to extremely large problem instances, such as graphs with millions of nodes?
3.Are there any plans to explore more universal graph embedding techniques that could be applicable across different SSCO problems without the need for customization?
4.Could the authors provide more details on the computational complexity of the WS-option framework, especially when compared to existing methods in the literature?
5.Are there any plans to conduct ablation studies to isolate the impact of the wake-sleep training procedure and layer-wise learning method selection on the overall performance?
6.Will increasing the number of trials and providing confidence intervals for the experimental results further strengthen the conclusions drawn from the data?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730689642181

thread_type:
official_review

<thread_object>
creator: reviewer_e3wz

<content>
summary:
This paper proposes WS-option, a hierarchical RL (HRL) algorithm to tackle sequential stochastic combinatorial optimization (SSCO) problems. These type of problems require to allocate a fixed budget over multiple timesteps, and solve the problem over these timesteps under allocation constraint. WS-option defines a high-level policy that allocates the budget, and a low-level policy that solves the underlying problem (selecting a combination of nodes of a graph in this case). The algorithm is experimentally validated on 2 problem instances.

strengths:
There are many ways to combine RL with combinatorial optimization, but it seems particularly well-suited in this case, as RL naturally handles the stochastic and sequential nature of SSCO. I believe the RL-based approach envisioned by the authors has high potential. It also seems to adapt well to different problem-size instances, which is not necessarily the case for RL-based methods for combinatorial optimization.

weaknesses:
Nevertheless, I believe that it is insufficient in its current form for the following main reasons:

1. Design choices lack proper justification

     a. The use of HRL here introduces 2 different agents, which introduces nonstationarity due to multiple policies interacting with each other. However, it seems here that a single policy with 2 different action-spaces -- one for the budget allocation, another one for the node selection -- (or one action-space with an action-mask to select only valid actions) could mitigate this issue. The importance of HRL is unclear.

    b. The lower-level MDP includes an option that can either be 0 or 1, which defines if the lower-level policy can continue to select nodes. From my understanding, the state-space does not include the allocated budget defined by the higher-level policy.  But this information should be crucial for the lower-level policy to choose which nodes to select. Now, at each timestep, the lower-level policy does not know if it will be able to continue selecting a node at the next timestep or not. Why resort to an "intermediate" option with 0 or 1, instead of allocating the $o_t^I$ in the state?

    c. The first half of training does not use the higher level policy to stabilize the training of the low-level policy. Are there any preliminary experiments that justify the choice of 1/2 of the training time? How dependent is this on the problem?

    d. The Route Planning problem (Appendix E) updates the profits by sampling U(-0.05, 0.05). What is the reason for this choice? Also, sampling from U(-0.05, 0.05) results in 0 in expectation. Wouldn't this affect the marginal reward? What are the consequences on the sequentiality of the problem (i.e., how much does this change compared to solving everything in one shot)? 

    e. The results do not show the standard-deviation, resorting instead to two-sample t-tests. Why? There is no clear justification as to why the standard-deviation is left out.
 
2. Experimental baselines are non-adaptive

    a. I understand that, since the authors are the first to propose an adaptive budget allocation for SSCO problems, they compare it with some fixed allocation strategies (average, static, normal). But there are no RL baselines, making it hard to assess the added value of the proposed algorithm. A standard RL baseline would also help understanding the need for HRL (e.g., using 2 action spaces as mentioned in 1b).

    b. Even though the baselines are non-adaptive, they are different for AIM and for RP. I fail to understand why, and why the average/normal/static high-level policies could not be used for RP.

questions:
Additional questions:

 1. In table 1, the performance of WS-option seems to be close to the "score" baseline  (for static and average). Are there any insights for this?
 2. It is unclear to me how the simulations are performed. Is it executing the greedy policy 10 times from the current state?
 3. Why are the WS-option scores in table 3 not the same as in table 1? Shouldn't they be the same, since they use the same high-level/low-level policy combination?
</content>
</thread_object>

</thread>
<thread>
creation date:
1732181943614

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
General response

comment:
Dear reviewers,  

Thank you for your valuable feedback and recognizing the following strengths of our paper:

* A generic formulation of sequential stochastic combinatorial optimization problems (Reviewers R7Hz and zNgF).
* The RL-based or HRL framework, WS-option, to solve SSCO problems (all the reviewers).

We tried to addressed and incorporated the feedback to strengthen our work. Below are the main changes of the updated version:

* Theoretical insights of our design (Appendix A). Specifically, we answers 5 questions: 1) Why did we use HRL? 2) Why does wake-sleep option framework work? 3) Why did we simplify options in the lower layer to a binary indicator? 4) How to design lower-layer reward? 5) What does our convergence analysis matter?
* Reason for using t-test (Appendix C.5).
* Clearer description of Theorem 2 (line 401).
* A fix to notations in Algorithm 2 (lines 306 and 308).

Specifically, we also answer some questions here:

1. Why did we use HRL instead of traditional RL with 2 different action-spaces? (See Appendix A.1 for details)

   1. This SSCO problem is essentially a bi-level optimization problem. Given its hierarchical dependency, it is natural and intuitive to employ a hierarchical learning algorithm such as HRL to address such problems effectively.
   2. Single-agent RL cannot capture this interdependency between layers, as well as the interdependent objective.
2. Why did we propose this wake-sleep option framework? (See Appendix A.2 for details)

   1. The core idea for solving this bi-level optimization (SSCO) problem is to decompose it into two separate single-level optimization problems.
   2. The sleep stage aims to find the conditionally optimal solution for the lower layer given the higher layer policy.
   3. The wake stage aims to optimize both layers jointly under the observation that the conditionally optimal lower-layer policy for any higher-layer policy is similar, since the task of lower layer is just to select nodes. Then this joint training further refines both the higher-layer policy and the lower-layer policy, ensuring that the global optimal solution is achieved.
3. Why did we simplify the option in the lower layer? (See Appendix A.3 for details)

   1. What the option means for the lower layer is essentially the termination condition, as defined in the option framework. The numerical value of the budget $K_t$ does not provide additional useful information beyond determining the number of node selections. Therefore, conveying the exact budget value to the lower layer is unnecessary and does not contribute to the termination decision. By representing options as binary indicators, we clarify whether the lower layer should continue or terminate, enhancing the interpretability of the policy.
   2. Reducing the option to a binary indicator allows the lower layer to focus solely on a straightforward termination condition, without needing to interpret specific budget values. This simplification minimizes the complexity of the learning task, leading to faster convergence and more stable learning processes.
4. How did we design the lower-layer reward? (See Appendix A.4 for details)

   1. The key is the total reward of the lower layer for each time step $t$ is the same as the reward of the higher layer, which means they share the same objective and reward function $R(s^I_t, o^I_t, a_t^{II})$.
   2. When the lower-layer actions are decomposed into sequential sub-actions (e.g., selecting one node at a time), the individual rewards for each sub-action must sum up to the total reward $R(s^I_t, o^I_t, a_t^{II})$.
5. Why does our convergence analysis matter?(See Appendix A.5 and A.2 for details)

   1. We try to decouple layer dependencies during training by alternating between the two optimization processes. This iterative approach leverages the individual convergence of each layer, as proven in Theorems 1 and 2, to ensure the overall framework converges.
   2. Based on this idea, we further simplify the training process to a wake-sleep training procedure. In this case, the setting indeed is the same with a Stackelberg game setting [1], where the follower can always provide the best response.
   3. We also claimed that this convergence analysis is not a global convergence analysis. Instead, it's the convergence of each optimization process. By using this iterative training procedure, it provides a convergence of both layers implicitly.

Furthermore, we are still running some extra experiments. We will provide all the results soon (approximately within 2 days):

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

Kind regards,

Authors

References:

[1] Zhao, G., Zhu, B., Jiao, J., & Jordan, M. (2023, July). Online learning in stackelberg games with an omniscient follower. In *International Conference on Machine Learning* (pp. 42304-42316). PMLR.
</content>
</thread_object>

</thread>


Metareview:
metareview:
This paper considers using reinforcement learning (RL) techniques to solve the sequential stochastic combinatorial optimization (SSCO) problems, where one needs to first decide the budget allocation for each step and then select a set of nodes for each time step. As a sequential decision-making model under uncertainty, the authors naturally introduce an RL framework to the SSCO problems. A novel wake-sleep training procedure and a hierarchical RL framework is proposed in this paper to solve the problem. Experimental validation has been done on the propagation problem and the route planning problem. In particular, during the rebuttal period, the experimental validation has been significantly enhanced by adding RL baselines, ablation studies for 1/2 training time, real-world data experiments, and ablation studies for lower-level options, making the empirical studies more convincing. Due to these contributions, we decide to accept this paper.