Sequential Stochastic Combinatorial Optimization Using Hierarchal Reinforcement Learning
Authors: Xinsong Feng
Zihan Yu
Yanhai Xiong
Haipeng Chen
Venue: ICLR 2025 Poster (2025)
Keywords: Sequential Stochastic Combinatorial Optimization
Hierarchal Reinforcement Learning
Graph
Primary area: optimization

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.

Published as a conference paper at ICLR 2025
SEQUENTIAL STOCHASTIC COMBINATORIAL OPTI- MIZATION USING HIERARCHICAL REINFORCEMENT
LEARNING
Xinsong Feng', Zihan Yu², Yanhai Xiong', Haipeng Chen UCLA, 'Te University of Hong Kong, WWilliam & Mary xs xsfengeucla.edu edu,
www.ectt......e. hk, {yxicng05, hchen23) wm. edu
ABSTRACT
Reinforcement learning (RL) has emerged promising tool for combinatorial optimization (CO) problems due its ability to learn fast, effective, and generaliz- able 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 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 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-basee based framework that simultaneously decides adaptive budget al- location on the higher layer and node selection on the lower layer. WS-option starts with coherent formulation of the two-layer Markov decision processes (MDPs), capturing the interdependencies between the two layers 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 larger graphs, which significantly reduces the overhead of computational resources.
INTRODUCTION
Combinatorial optimization (CO) problems cover broad spectrum of application domains, such as social networks [45] 21. public health [17 29), transportation (7), telecommunications (8] and scheduling [4 55 Hence, much attention has been drawn from both the theory and application
communities toward solving CO problems. Recently, there have been studies using reinforcement
learning (RL) to learn generalizable heuristic policies for CO problems on graphs [4 39 14 [|
The RL policy is trained on a set previously seen training graphs and generalizes to unseen test graphs of similar structure. This policy is usually represented using graph embedding methods such as structure2vec (S2V) 12 and graph convolutional networks (GCNs) 255.. However, most existing studies focus one-shot deterministic CO, while research on another broad class of CO problems, which contain stochasticity and must be solved sequentially over multiple time steps, remains limited.
Problem Statement In this paper, study the sequential stochastic CO (SSCO) problem where we first decide the budget allocation for all the time steps, and then select a combination nodes for each time step. Given graph G (V, E), where V and E represent the set of vertices and edges the graph, respectively, the number of time steps T, and the total budget K for selecting nodes, the task is decide 1) allocation K, K2..... ..., Ky of budget over the time horizon, together with 2)

---

Published as a conference paper at ICLR 2025
sequence of node sets S2, ..,.... Sr S V, such that
maximize
E ((())
(la)
KiooKg Kr Sr..,Sr
E |=1 |St| S KG, 1I. 1 ,.... T
subject to
K₁ S K,
(lb)
(1c)
Kr E N, VI ===1 1, T,
(Id)
C,V, Vt 1, I..
(Ie)
Here, (S,) denotes the reward obtained from the nodes in set S, at the time step f. SSCO has a wide range of real-world applications such as resource allocation in wireless communication networks
32
route planning [22], and adaptive influence maximization (IM) 42 48).
As far as we know, there are not many works that address SSCO using RL; two notable examples are adaptive IM in [10] and medical resource allocation for epidemic control in [1]]. However, they assume that the budget is evenly allocated across all the time steps (i.e., Ke = K/T, Vt), which may not be optimal in stochastic environments or when additional information feedback becomes available over time. These scenarios need adaptive sequential decision-making. For example, in the adaptive IM problem, an even allocation policy cannot adapt to sudden changes and uncertainties, leading to resource shortages at critical times or redundancy at less important times. Additionally, it lacks the flexibility to adjust strategy when more important information becomes available.
Despite its criticality, solving SSCO is extremely challenging due to the following factors: I) Combinatorial complexity. The search space grows exponentially as the graph grows, which makes it difficult to find the optimal solution efficiently. 2) Stochasticity. Future states and rewards are uncertain, so the ability to adaptively update the solutions based on the real-time state and stochasticity in the future is required. 3) Sequential decision making. Decisions are interdependent and require sophisticated planning that considers both current and future consequences. 4) Scalability. The methods need to have the ability to be generalized to large-scale problems in the real world.
While traditional RL struggles with these challenges, hierarchical RL (HRL) presents viable solution by decomposing complex tasks into simpler sub-tasks improve learning efficiency. Several works have contributed to the development actions, allowing agents to learn at different levels of abstraction [47] Multi-level approaches use higher-level managers to set tasks for uub-managers [13]. Data-efficient methods leverage offline experiences for training (38). Combining HRL with intrinsic motivation 27 and hindsight experience
HRL. The option framework models temporally extended
replay (HER) I further enhances learning.
In this paper, we propose an HRL framework, WS-option, for solving SSCO by jointly considering budget allocation and node selection, with a coherent definition of MDPs for both layers. The lower layer is particularly challenging due to the need for explicit definitions of states and rewards. The MDP formulation directly affects the overall performance of the model. Maintaining model stability crucial due to the interdependence and mutual influence of the two layers. To improve model stability, especially in the higher layer, we adopt MC methods to learn budget allocation, known as the option policy. To ensure faster convergence and stable operation of the lower layer, we use TD methods to learn node selection, known as the intra-option policy [3] These methods ensure that both layers can run stably and efficiently, avoiding the issue of potential vicious mutual interference.
Our main contributions are as follows.
We are the first to formally summarize and define the generic class of SSCO problems.
We design a novel HRL algorithm, WS-opption, to solve the formulated SSCO, with major novelties in terms of the two-layer MDP formulation, and new wake-sleep training procedures to balance the training stability and efficiency and avoid the potential vicious mutual interference. Our algorithm a generic framework that applies to a wide range of SSCO problems of the same nature. For completeness, we also provide a brief theoretical analysis of the algorithm's 's convergence.
We conduct experiments on two distinct SSCO problem instances adaptive IM and route planning. The results show that compared to traditional methods, our algorithm exhibits superior performance in solving both SSCO problems. In particular, the algorithm is able to generalize to larger unseen graphs, thus significantly reducing computational overheads for larger-scale SSCO problems.
2

---

Published as a conference paper at ICLR 2025
2 RELATED WORK
RL for CO RL has been widely used to solve CO problems [35 Nazari et al. 39 propose a generic RL framework for solving the vehicle routing problem (VRP), outperforming traditional heuristic algorithms. Bello et al. [ introduce neural combinatorial optimization, combining neural networks and RL to solve the TSP problem. Kool et al. (26) develop an attention-based model using the REINFORCE algorithm, achieving superior results various CO problems like TSP, VRP, and the Orienteering Problem (OP). Khalil et al. [24] combine RL with graph embedding to construct solutions for CO problems step by step. Chen & Tian [TT present method where neural networks iteratively improve combinatorial solutions through learned local modifications. Deudon et al. 14] introduce method where policy gradient techniques are used to train neural networks to develop heuristics for solving the TSP. Emami & Ranka [15] propose Sinkhorn policy gradient methods to learn permutation matrices for CO problems. Cappart al. 9 combine decision diagrams with deep RL to enhance optimization bounds for combinatorial problems. Lu et al. [34] introduce an iterative approach that leverages REINFORCE enhance solutions for VRPs. Recent methods have further integrated search algorithms, such as active search (20), Monte Carlo tree search [16], and beam search 28 to enhance the solution qualities of RI. algorithms during inference time. While these algorithms show promising results, they typically tackle one-shot deterministic CO problems without sequential decision-making making, limiting their effectiveness for more complex scenarios.
Graph embedding Graph embedding techniques are crucial for RL-based solutions to CO prob- lems, representing graph structures in continuous vector spaces to preserve structural properties, facilitate downstream RL tasks, and generalize to unseen (potentially larger) graphs. Node2 Vee [18] uses biased random walks to explore neighborhoods efficiently, which maps nodes to www-dimensiona vector spaces while preserving the neighhor structures. Deepwalk (43, which is inspired by language models, uses truncated random walks to obtain local node information and learn potential represen- tations. Significant progress has also been made with graph neural networks (GNN) 44
58 53
such as GCN (25). Graph Attention Networks (GAT) [49] and Graph Transformer Networks [57
Xu al. [54] evaluate the expressiveness of GNNs, comparing them the Weisfeiler-Lehman test in capturing graph structures. Li et al. [31 analyze the effectiveness and mechanisms of GCNs in semi- -un-suueeeiied learning. Ying et al. (56) introduce a method interpret GNNs by identifying the crucial subgraphs and features that influence their predictions. Nonetheless, determining the most beneficial graph embedding technique for RL tasks remains an important research question.
Hierarchical reinforcement learning HRL introduces hierarchical structure to RI., decomposing complex tasks into simpler subtasks to improve learning efficiency. The option framework [47] defines HRL with options temporally extended actions, which enables agents to learn at different levels of temporal abstraction. Dayan & Hinton [3] introduce a multi-level RL approach based on subgoals, where high-level managers set tasks for sub- managern to achieve efficiently. Nachum et al. [38 propose a satta-efficient HRL method using off-line experiences to train higher-level and lover-level layers, and the results demonstrate its ability to learn complex behaviors. Bacon al. develop a method to automatically learn policy, termination function, and intra-option policy in HRL using intra-option policy gradient and termination gradient, without extra rewards or subgoals. Vezhnevets et al. [50] divide agent behavior into two levels: the Manager, which sets goals in a latent space, and the Worker, which executes these goals with primitive actions. Kulkarni al. [27] combine hierarchical structures and intrinsic motivation to improve learning in complex tasks. Andrychowicz
et al. I introduce technique called HER that enhances RL by learning from failures as if they were successes with different goals, and Levy et al. (30] integrate HER with HRL to enhance learning at multiple levels. Despite their success, these methods often do not address the specific challenges of SSCO problems, especially the need to handle sequential, combinatorial state-action spaces, and dynamic environments. Furthermore, they typically do not integrate graph- based representations, which could significantly enhance their effectiveness when dealing with graph- CO problems.
THE WS-OPTION FRAMEWORK
This section will show how to learn budget allocation and node selection using our proposed WS- option framework. We begin with brief introduction to the option framework, followed by the architecture used in our approach. Subsequently, we will formulate the MDPs for both hierarchical layers and adopt value-based methods the backbone RI approach. In particular, to balance training
3

---

Published as a conference paper at ICLR 2025
stability and computational efficiency, employ MC methods to learn the Q-function for the higher layer and TD-leaming to learn the Q-function for the lower layer. Additionally, it is important to note that model is trained on different graphs that follow certain distribution to enhance its generalization ability to unseen, similarly-structured graphs from the same distribution. The network architecture shown in Appendix C.1
3.1 PRELIMINARY: THE OPTION FRAMEWORK
The option framework, proposed by 47 is an implementation of temporal abstraction in RL. It provides a straightforward way to describe temporally extended actions, known as options, which are higher-level actions composed of several primitive actions. Formally, an option is defined by the tuple (1, n 3), where
Initiation set /: a set of states where the option can be initialized. We will assume that any state satisfies in problems.
Intra-option policy x policy that maps states to actions under given option, controlling the lower-level actions taken under that option. We use 7 as the lower-level node selection policy.
Termination function 3: a mapping 3: + [0, 1] that specifies the probability of terminating option in given state, where S is the state space.
When an agent operates within the option framework, it follows the process: 1) Option selection the agent selects an option based on option policy given a state. 2) Option execution - once the option is determined, the agent follows the intra-option policy z! until the option terminates. 3) Option termination when the termination condition met, the agent terminates the current option and proceeds to the next option selection.
In our study, we adopt slightly different approach to defining options. While at the higher layer, simplify the
the option of we select represents the budget K; allocated at the current time step information representation when passing the option to the lower layer. Specifically, we use option of to indicate that the lower layer should continue selecting nodes, and option of 0 to indicate that it should stop selecting nodes and interact with the environment. that handle cases where the budget allocated by the higher layer is 0 (i.e., of of 0), introduce null action a, for the lower layer. The null action 0, represents directly interacting with the environment and moving to the next time step. In fact, achieved very good results by introducing this null action.
important to note
3.2 HIERARCHICAL MDP FORMULATION
Here, we define the MDPs for the two layers of our hierarchical model (c.f. Figure For ease of understanding, we will take the adaptive IM problem running example. More details of both problems are shown in Appendix and respectively.
Environment
KG
High-level decision decision
st
Agent
K
+100
a
Low-level decision
n²
s!!
a!!
$t.+1
Figure Hierarchical MDPs for SSCO
4

---

Published as a conference paper at ICLR 2025
3.2.1
HIGHER LAYER MDP
State
The state s' = (X, g) E includes two types of information: node features X (e.g., inactive active in adaptive IM problem) and global information y (e.g.. the remaining time steps T, and the remaining budget K,).
Option The option of represents the budget 0 v K2 S K, allocated to the current time step t.
State transition The state transition in this layer is stochastic, which is a fundamental characteristic of SSCO problems. Given the current state of and the action of from the lower layer, the state s1+1 is updated according to the following function:
s/1 = (66),a()) + n(s),
(2)
where [(s), ! is deterministic function that updates the state of based on the current action af', while 7755 aj ) represents the stochastic component, which introduces randomness into the state transition, thereby capturing the stochastic nature of the environment. For example, in the adaptive IM problem, there is no deterministic component. Instead, the entire state transition is governed by the stochastic process n(s!, a!"), which can be interpreted as the "activation process" within this problem.
The total reward depends on the problem of interest. In adaptive IM, it is the total number of influenced nodes (e.g., active and removed nodes). Then, the immediate reward of is the increase in the total reward.
Reward
3.2.2 LOWER LAYER MDP
State
The state I! is also defined as s 9X.
The option o can be either 0 or 1, where "1" represents continuing to select nodes, and "0" represents not selecting any node and interacting with the environment.
Option
11 is the node Action Two kinds of actions are defined. Given the current time step t, the action a
selected for sub time step j (e.g.. of 1) just the null action 0r (e.g., of 0). And the a!' is all the nodes selected in the current time step or the null action 0g,0 if no nodes are selected.
State transition The state transition can occur either in a deterministic stochastic way. If option of is and the action is node v, we update the state of node deterministically (e.g.. activating node the agent interacts with the environment as described in the higher layer MDP.
v). If option
Reward The reward in the lower layer significantly affects the convergence of the model. We first define the reward r-d for the null action 0r,0, which means directly interacting with the environment at time step t. I depends on the specific problem, and the intuition is to determine the expected r1.0
reward when moving to the next day if we do not select any node in the current state. For propagation problems, we can choose -/, r! ken- where ken represents the effective number of nodes in action af' (e.g., number of inactive nodes in a that can yield actual gain. For problems without a propagation process (e.g., TSP, RP), we can simply set this reward O. Next, we define the marginal reward m4,v for node v. We denote the selected nodes in the current sub time step j as A, (Ur,m 0t,ay J.. The marginal reward obtained as follows
m = R2 (s/, A, U (ar,v)) - R2 (s)
(3)
where RS,S, A) is the immediate reward from taking action A in state S. In our experiments, this reward is estimated by averaging the results of multiple (typically 10) simulations. As a result, the reward for selecting node v is given by
11 1(
mi Encol
(rl
r(()).
(4)
My
In this manner, the total reward at each time step for the lower layer will remain consistent with the higher layer, enhancing the model's stability.
5

---

Published as a conference paper at ICLR 2025
3.3 WS-OPTION
Due to the high interdependencies between the learned Q-values across the two policy layers, along with advantages such reduced sample complexity, employ value-based RL for both layers. In our framework, the policies of both layers are e-greedy.
Algorithm WS-option: Overall training
1: Initialize experience buffer M and M2 for the higher and lower layer, respectively.
2: Initialize Q-networks for both layers.
3: for epoch i = I.,.,N .N do
4: Sample Graph G from the distribution D.
5: for episode j 1 to M do
6: if S N/2 then
7:
Set the flag ii
to true.
8:
else
9:
Set flag uss_ffixedhhigerr..es
false.
10:
end if
11:
Run an episode with the flag use fixed higher layer (see Algorithm 2
12:
Store transitions (see Algorithm
end for
14:
Sample a sequential minibatch of the most recent transitions from the replay buffer Mi.
Train the higher layer using MC methods with sampled transitions.
16:
Sample random minibatch of transitions from the replay buffer M2-
Train the lower layer using TD-learning with sampled transitions.
18:
end for
Algorithm 2 WS-option: Run episode
1: Initialize the state sf and temporary storage T for episode transitions.
2: for step = 1 to 7 do
3: if luse_fixed h giiggherrllyer is True then
4: of +- average budget allocation.
5: else
6: of + frandomly selected in the remaining budget, w.p. 61,
Barg max, q¹ (s/ o), otherwise.
7: end if
8: Initialize the set of selected nodes a!' = =
9:
for k -1 tooo of do
11 o < stale transitionss/, of abtt bt
11 frandomly select node from V af' w.p., 6 akk arg max, " (s(k a)) subject to & af otherwise.
11:
12:
of + af (afk)
end for
14: Execute action af and obtain reward rf and next state 8441
15: Store the transition (s{ of af" s(1)) in the temporary storage T.
16: Update the current state: of 8
17:
end for
Morcover, as shown from the formulation of the MDPs for both layers, we can see that the Q-functions of the two layers are highly interdependent. On one hand, the higher-layer option selection will determine feasible action spaces for the lower-layer node selection; on the other hand, the specific lower-layer node selection will affect how good the higher-layer's selected option is. Hence, we observe that, if we simply adopt the commonly used (double) Q-learning framework [5]]]]] 36 37. 19], or more essentially off- off-policy TD learning [46] for both layers, then the Q-values for both layers, especially the first layer will tend to diverge. This is because of the estimation bias derived from the deep models (see Appendix [..I) and bootstrapping of TD learning. We can see the result in Figure 2(b] To stabilize the training of both layers, while maintaining computational efficiency, propose

---

Published as a conference paper at ICLR 2025
the following two designs for training algorithm, i.e. wake-sleep training and layer- wise learning method selection. The pseudocode of the training algorithm is shown in Algorithm | During each epoch, graph is obtained from a certain distribution D (line 4). We divide all epochs into two stages (lines 6- 10), which correspond to the wake-sleep training procedure descrihed in this section. After we run algorithm and []] we can the transitions to train both layers (lines 14-16). Note that during the training of the higher layer, transistions are sampled sequentially (line 14). Although the higher-layer policy, based on MC method, is inherently on-policy and does not require stored
transitions, we maintain this to ensure consistency across both layers.
Algorithm 2 shows the process of running episodes. We first get the option (lines 3-6), then choose node one by one (lines 8-13). Subsequently, we run Algorithm 3 (see Appendix [B.1] to store transitions for training. Algorithm 3 shows how to store transitions, especially for the lower layer. Since the second layer does not interact with the environment after selecting a single node and suffers from sparse rewards, we first obtain the marginal rewards for each transition state through simulation (lines 5-10). To keep the total reward of the lower layer consistent with the higher layer, scale all the marginal rewards (lines 12-15), which does not affect the relative Q value of the actions.
3.3.1 WAKE-SLEEP TRAINING
The primary challenge in HRL lies in ensuring stable training and model convergence. Notably, training both layers together can lead to instability, as the policies of each layer are interdependent and can interfere with one another. To address this issue, we devise a wake-sleep approach to enhance training stability. As we will show in Section 3.3.3] this proposed wake-sleep training procedure well-aligned with our theoretical analysis. In Figure 2(a) we present the Q value learned by traditional HRL, where both layers are trained simultaneously from the beginning, and our proposed WS-option. Then, we will provide the details of this wake-sleep training procedure.
In the sleep stage of this training paradigm, the Q-function of the higher layer is initially frozen and an average budget allocation strategy is used instead. While more advanced strategies could be considered, we choose the simplest one to allow the lower layer to approach convergence under the current high-layer policy. The lower layer's Q-function is sufficiently trained along with the average budget allocation strategy in this stage. Mcanwhile, the high layer's Q-function will be pre-traine pre-trained offline using the trajectories of the average strategy. In the subsequent wake stage, both layers are trained online simultaneously, allowing for the fine-tuning and optimization of their interdependent policies, which ultimately lead to convergence.
3.3.2 LAYER-WISE LEARNING METHOD SELECTION
MC methods provide unbiased estimates by calculating the expected value via a complete trajectory, offering reliable and accurate results when the sample size is sufficient. In contrast, TD methods may reduce the accuracy of the Q estimation if errors occur during the intermediate process, known еттог propagation. Additionally, in practice, TD methods often result in the overestimation of Q values. Hence, using MC methods to provide more reliable Q value estimates for the higher layer can enhance the model stability. Our experimental results show that this trick, combined with wake-sleep training, is one of the key components that makes the HRL training successful. Figure ((b)) [(b) shows the Q values learned using MC and TD methods. The values from TD methods are monotonic, while those from MC methods are concave.
On the downside, MC methods usually more data-hungry because they have to wait until the end of a trajectory to get a training sample. Given that the lower-layer Q-learning (which is essentially a subtask that uses RL to solve one-shot CO problems) has been demonstrated to be reliable 124. [4] 26 6], we choose the off policy TD-lcarning (Q-Icarning) framework for the layer-layer Q-function update. TD-learning has a faster convergence speed compared to MC methods. When training in the sleep stage, the rapid feedback of the TD method can help the lower layer converge faster, so that the whole model will be better initialized with more optimized parameters. This in turn will accelerate the co-training in the wake stage.
3.3.3 CONVERGENCE ANALYSIS
For completeness of our study and to offer intuition for our framework, we present a concise theoretical analysis of the algorithm's convergence. We first discuss the convergence of the intra-
7

---

Published as a conference paper at ICLR 2025
1100
115
WS-option
TD methods
960
800
value
105
100
c600
500
120
MC methads
90
100
10 16171819
901112211411111111111
Budget
(a) WS-option vs. traditional HRL.
(b) MC methods vs. TD methods
Figure 2: Q-values learned for the AIM problem (T = 10, = 20).
option policy and give Theorem 1 Then, show the convergence the option policy and give the Theorem The proofs are provided in Appendix [ and Appendix [A.5.2] respectively.
Theorem 1. (Intra-option policy convergence). In our WS-option framework, given any Markov transition (s+, 0r, ary, Tr, 81,1, 0r+1), the Q-value function q² (St, Dr, a7) converges to the optimal 0r,07) (+) with probability assuming that the higher-layer policy is fixed. Q-value function q- (5r,0r,
0r,
Theorem 2. (Option policy convergence). In our WS-option framework, given any state-option pair (8t, oc), the Q-value function qf (st, 0₂) converges to the optimal Q-value function q (s 0g) with probability 1, assuming that for any given higher-layer policy, the lower-layer policy always provides the corresponding conditionally optimal response.
As result, the convergence of the hierarchical framework is guaranteed by the convergence of both layers. Although the interaction between layers will have some effects, we use the wake-sleep procedure instead. As illustrated in Figure 3 after the sleep stage, can get optimal policy !! conditioned on the higher layer's policy π Notably, even when the higher layer policies differ, the nature of the node selection task leads lower layer optimal policy I! being similar any conditional optimal policy r" This is analogous to the Stackelberg game setting, where the follower can always give best response. In this case, the convergence of the total framework can be achieved. Notably, our analysis is just limited to the tabular case.
Sleep
Wake
Higher Layer
Given policy
Global optimal policy xx1l)
Thearem
Theorem 2
Stackelberg game
Lower Layer
Conditianed ootimal policy x!
Close
Optimal policy
cond boned
Figure 3: Wake-sleep training procedure
EXPERIMENTAL RESULTS
4.1 SSCO PROBLEM INSTANCES
In this article, we examine two broad classes of problems: the propagation problem (high stochasticity) and the route plamning problem (low stochasticity). For the propagation problem, we use an adaptive version of the classic IM problem. For the route planning (RP) problem, consider model tailored for travel route planning. Notably, instead of showing the standard deviation of test results, we perform two-sample t-tests show the effectiveness of framework in SSCO scenarios.
8

---

Published as a conference paper at ICLR 2025
4.2 COMPARISON WITH BASELINES
Baselines To evaluate the effectiveness of our approach, we compare it against appropriate base- lines for each problem, measuring the cumulative reward obtained by various methods. Each baseline is named the form of A-B, where is the higher-layer algorithm, and B is the lower-layer algorithm. For the AIM problem, we use the baselines mentioned in Tong al. [48]: average policy, static policy, and normal policy at the high level. The static policy divides the time period I into d cycles, allocat- ing the same resources only on the first day of each cycle. The normal policy allocates all resources at the beginning. At the lower level, we use degree-based greedy strategy and well-designed score-based strategy. The score for each node v is defined as S, LmENi p(u, v), where Win (v) denotes the set of inactive nodes among the neighbors of v, and p(u, v) is the probability that u can successfully activate v. This method takes into account the characteristics of the problem and uses expected values to score each node, showing strong performance in our experiments. For the RP problem, we use genetic algorithms (GA) and greedy algorithms. We train and test on graphs of the same size here. The results are shown in T where 'T' and K are chosen according to Tong et al.
Table I: Experimental results for AIM,
200.
All cases have p p-values S 0.05.
Method
T, K 10, 10
T.K 10, 20
T.K =
10, 30
T, K = 20, 10
WS-option
76.00
118.56
129.06
80.95
average-degree
67.92
104.54
122.50
72. 18
average-score
74.36
116.10
128.29
80.31
normal-degree
69.28
101,50.34
109.39
63.47
normal-score
75.05
111.89
118.78
70.68
static-degree
70.02
105.25
122.37
70.57
static-score
74.81
118.13
128.01
71.68
Table 2: Experimental results for RP, 100. All cases have p-values S 0.05.
Method
T.K = 10
T.K = 10,20
T.K 10, 30
T, K 20, 10
WS-option
7.46
12.86
18.57
7.52
greedy
6.29
12.02
15.68
6.73
GA
6.79
11.65
15.70
6.93
As shown in Tables our method performs consistently well across various settings. As expected, our method outperforms the baseline methods the AIM problem, which emphasizes structural information about the graph as well as feedback processing of stochasticity (whether the node is successfully activated or not). our experiments, we use simple graph neural networks. In fact, employing more advanced graph neural networks could further improve the performance of our algorithm, but graph embedding is not the focus of our study. For the RP, our algorithm also shows advantages. The graph of RP is essentially fully connected graph, which does not emphasize the structural information of the graph but focuses more on the distance between nodes. Nonetheless, the primary advantage of our algorithm is its ability to be applied larger graphs without the need for retraining after single training. which significantly reduces computational overhead compared to traditional algorithms. Additionally, cumulative reward during training for AIM problem is provided in Figure 5 of Appendix D.I
4.3 ASSESSING THE LEARNED POLICIES
We now assess the learned budget allocation and node selection policies using the AIM problem. By fixing one layer's policy, compare the cumulative rewards obtained by only the other layer, enabling us to independently assess the policy of each layer.
To evaluate the higher layer, fix the lower layer using its learned policy and vary the budget allocation policy. Conversely, to evaluate the performance of the lower layer, we fix the higher layer using the average budget allocation policy and vary the node selection policy. As shown in Table

---

Published as a conference paper at ICLR 2025
Table 3:
Cumulative rewards when varying one layer's policy while the other layer remains fixed. All cases have p-values < 0.05.
lower layer fixed (using the learned policy) WS-option
Setting
average
normal
static
T. K 10, 10
76.79
71.45
75.27
74.85
T, K = 10, 20
127.51
126.35
120.26
125.46
higher layer fixed (using the average policy) WS-option
Setting
degree
score
T, K 10, 10
71.45
62.55
69.15
T.K = 10,
126.35
118.75
125.02
3 our algorithm performs well even when applied to a single layer. Both the node selection and the learned budget allocation strategies yield better results compared the baseline approach. The learned budget allocation policy showed in Appendix D.2 Figures 6 to
4.4 GENERALIZATION TO LARGER GRAPIS
Most excitingly, our algorithm generalizes well larger graphs. This means that models trained on small graphs can be effectively applied to larger ones. The reason for this generalization ability lies the framework we use, which does not include any parameters related to graph size or number of nodes. This allows us to use the same parameters for graphs of different sizes.
Table 4: AIM: Generalization to larger graphs. All cases have p-values S 0.05.
200
400
700
1000
WS-option 120.88
176.13
204.87
221.16
average-degree
110.18
144.93
155.85
167.58
average-score
119.80
158.98
165.24
176.31
normal-degree
103.22
152.46
186.01
210.57
normal-score
106.47
166.45
199.41
220.81
static-degree
109.62
155.08
178.66
198.44
static-score 118.86
171.91
188.44
204.16
We train the model on graphs with 50-100 nodes with T 10, = 20. Table 4 and Table (see Appendix D.3) present the results of our tests different graph sizes. As shown, though the model was trained on small graphs, still exhibits excellent performance on larger graphs. This result demonstrates that algorithm has good scalability and generalization ability effectively deal with large-scale graph structure problems.
5 CONCLUSION
We propose an option-based HRL framework for solving complex SSCO problems. The core of our approach use the wake-sleep training procedure and layer-wise learning method selection to make the system more stable without interfering with each other, as well as to facilitate our learning process by giving clear definition of MDPs of two layers. Through extensive experimental evaluations, we demonstrate the strong performance of our algorithm in solving the SSCO problem, its ability to learn effective budget allocation and node selection policies, and strong generalization to larger graphs. However, a notable limitation of our algorithm is that each new problem needs new graph embedding technique, which adds complexity to the framework 's implementation across different scenarios. We leave the investigation of model-agnostic graph embedding techniques for RL-based solutions to SSCO as future work, potentially borrowing ideas recent advancements on graph foundation models 33
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGEMENTS
This research was partially supported by the National Science Foundation under IIS-2348405. The authors acknowledge William & Mary Research Computing for providing computational resources and/or technical support that have contributed to the results reported within this paper.
REFERENCES
[1] Marcin Andrychowicz, Filip Wolski, Alex Ray, Jonas Schneider, Rachel Fong, Peter Welinder, Bob McGrew, Josh Tobin, OpenAl Pieter Abbeel, and Wojciech Zaremba. Hindsight experience replay. Advances in Neural Information Processing Systems, 30, 2017.
[2] Maria Chiara Angelini and Federico dicci-Tersenghi Modern graph neural networks do worse than classical greedy algorithms in solving combinatorial optimization problems like maximum independent set. Nature Machine Intelligence, 5(1):29- -1, 2023.
[3] Pierre-Luc Bacon, Jean Harb, and Doina Precup. The option-critic architecture. In Proceedings the AAAI conference on Artificial Intelligence, volume 31, 2017.
[4] Irwan Bello, Hieu Pham, Quoe Le, Mohammad Norouzi, and Samy Bengio. Neural combina- torial optimization with reinforcement learning. arXiv preprint arXiv:1611.0m 1.09400 2016.
[5] Yoshua Bengio, Andrea Lodi, and Antoine Prouvost. Machine learning for combinatorial optimization: A methodological tour d'horizon. European Journal of Operational Research, 2020.
[6] Federico Berto, Chuanbo Hua, Junyoung Park, Minsu Kim, Hyeonah Kim, Jiwoo Son, Haeyeon Kim, Joungho Kim, and Jinkyoo Park. RI4co: an extensive reinforcement learning for combina- torial optimization benchmark. arXiv preprint arXiv:2306. 17100, 2023.
[7] Valentina Cacchiani. Models and algorithms for combinatorial optimization problems arising in railway applications. 4OR, 7:109-112, 12, 2009.
[8] Buyang Cao, Minghe Sun, and Charles Macleod. Applying gis and combinatorial optimization to fiber deployment plans. Journal of Heuristics, 5:385 402, 1999.
[9] Quentin Cappart, Emmanuel Goutierre, David Bergman, and Louis- Martin Rousseau. Improving optimization bounds using machine learning: Decision diagrams meet deep reinforcement learning. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pp. 1443-1451, 2019.
[10] Haipeng Chen, Wei Qiu, Han-Ching Ou, Bo An, and Milind Tambe. Contingency- aware influence maximization: A reinforcement learning approach. In Uncertainty in Artificial Intelligence, pp. 1535-1545. PMLR, 2021.
[11] Xinyun Chen and Yuandong Tian. Learning perform local rewriting for combinatorial optimization. Advances in Neural Information Processing Systems, 32, 2019.
[12] Hanjun Dai, Bo Dai, and Le Song. Discriminative embeddings of latent variable models for structured data. In International Conference on Machine Learning, pp. 2702-2711. PMLR, 2016.
[13] Peter Dayan and Geoffrey E Hinton. Feudal reinforcement learning. Advances in Neural Information Processing Systems, 5, 1992.
[14] Michel Deudon, Pierre Cournut, Alexandre Lacoste, Yossiri Adulyasak, and Louis- Rousseau. Learning heuristics for the tsp by policy gradient. In Integration of Constraint Programming, Artificial Intelligence, and Operations Research: 15th International Conference, CPAIOR 2018, Delft, The Netherlands, June 26-29, 2018, Proceedings 15, pp. 170-181. Springer, 2018
[15] Patrick Emami and S. Ranka. Learning Permutations with Sinkhomn Policy Gradient. ArXiv, abs/180 00/11805007000 2018.
11

---

Published as a conference paper at ICLR 2025
[16] Zhang-Hua Fu, Kai-Bin Qiu, and Hongyuan Zha. Generalize small pre-trained model to arbitrarily large tsp instances. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pp. 7474-7482, 2021.
[17] Ganga Gireesan, Nisha Pillai, Michael Rothrock, Bindu Nanduri, Zhiqian Chen, and Ma- halingam Ramkumar. Deep sensitivity analysis for objective-oriented combinatorial optimiza- tion, arXiv preprin! arXiv:2403.00014 2024.
[18] Aditya Grover and Jure Leskovec. node2vec: Scalable feature learning for networks. In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 855-864, 2016.
[19] Hado Hasselt. Double q-learning. Advances in Neural Information Processing Systems, 23, 2010.
[20] André Hottung, Yeong-Dac Kwon, and Kevin Tierney. Efficient active search for combinatorial optimization problems. In International Conference on Learning Representations, 2021.
[21] Tommi Jaakkola, Michael Jordan, and Satinder Singh. Convergence stochastic iterative dynamic programming algorithms. Advances in neural information processing systems, 6, 1993.
[22] Waldy Joe and Hoong Chuin Lau. Deep reinforcement learning approach solve dynamic vehi- cle routing problem with stochastic customers. In Proceedings of the International Vonference on Automated Planning and Scheduling, volume 30, pp. 394-402, 2020.
[23] David Kempe, Jon Kleinberg, and Êva Tardos. Maximizing the spread of influence through a social network. Proceedings of the ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 137-146, 2003.
[24] Elias Khalil, Hanjun Dai, Yuyu Zhang, Bistra Dilkina, and Le Song. Learning combinatorial optimization algorithms over graphs. Advances in Neural Information Processing Systems, 30, 2017.
[25] Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In International Conference Learning Representations, 2016.
[26] Wouter Kool, Herke van Hoof, and Max Welling, Attention, learn solve routing problems! In International Conference on Learning Representations, 2018.
[27] Tejas D Kulkarni, Karthik Narasimhan, Ardavan Saeedi, and Josh Tenenbaum. Hierarchical deep reinforeement learning: Integrating temporal abstraction and intrinsic motivation. Advances in Neural Information Processing Systems, 29, 2016.
[28] Yeong-Dae Kwon, Jinho Choo, Byoungjip Kim, Iljoo Yoon, Youngjune Gwon, and Seungjai Min. Pomo: Policy optimization with multiple optima for reinforcement learning. Advances in Neural Information Processing Systems, 33:21 182-1188211 198, 2020.
[29] Changhun Lee, Soohyeok Kim, Sehwa Jeong, Chiehyeon Lim, Jayun Kim, Yeji Kim, and Minyoung Jung. Mind dataset for diet planning and dietary healthcare with machine learning: dataset creation using combinatorial optimization and controllable generation with domain experts. In fiihty-fifth Conference on Neural Information Processing Systems Datasets and Benchmarks Track (Round 2), 2021.
[30] Andrew Levy, George Konidaris, Robert Platt, and Kate Saenko. Learning multi-level hierar- chies with hindsight. In International Conference on Learning Representations, 2018.
[31] Qimai Li, Zhichao Han, and Xiao-Ming Wu. Deeper Insights Into Graph Convolutional Networks for cumi-Suuer Learning. In AAAI Conference on Artificial Intelligence (AAAI), pp. 3538-3545, 2018.
[32] Le Liang, Hao Ye, Guanding Yu, and Geoffrey Ye Li. Deep-learning based wireless resource allocation with application to vehicular networks. Proceedings of the IEEE, 108(2):341-356 2019.
12

---

Published as a conference paper at ICLR 2025
[33] Jiawei Liu, Cheng Yang. Zhiyuan Lu, Junze Chen, Yibo Li, Mengmei Zhang, Ting Bai, Yuan Fang, Lichao Sun, Philip S Yu, et al. Towards graph foundation models: A survey and beyond. arXiv preprint arXhv22310.11829 2023.
[34] Hao Lu, Xingwen Zhang, and Shuang Yang. A learning-based iterative method for solving vehicle routing problems. In International Conference on Learning Representations, 2019.
[35] Nina Mazyavkina, Sergey Sviridov, Sergei Ivanov, and Evgeny Burnaev. Reinforcement learning for combinatorial optimization: A survey. Computers & Operations Research, 134:105400 2021.
[36] Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Alex Graves, Ioannis Antonoglou, Daan Wierstra, and Martin Riedmiller. Playing atari with deep reinforcement learning. arXiv preprint arXiv: 131..502, 2013.
[37] Volodymyr Mnih, Koray Kavukeuoglu, David Silver, Andrei A Rusu, Joel Veness, Marc G Bellemare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, et al. Human-level control through deep reinforcement learning. Nature, 2015.
[38] Ofir Nachum, Shixiang Shane Gu, Honglak Lee, and Sergey Levine. Data-efficient hierarchical reinforcement learning. Advances in Neural Information Processing Systems, 31, 2018.
[39] Mohammadreza Nazari, Afshin Oroojlooy, Lawrence Snyder, and Martin Takác. Reinforcement learning for solving the vehicle routing problem. Advances in Neural Information Processing Systems, 31, 2018.
[40] Joel Oren, Chana Ross, Maksym Lefarov, Felix Richter, Ayal Taitler, Zohar Feldman, Dotan Di Castro, and Christian Daniel. Solo: search online, learn offline for combinatorial optimization problems. In Proceedings of the International Symposium on Combinatorial Search, volume 12,
pp. 97-105, 2021.
[41] Han- Han-Ching Ou, Haipeng Chen, Shahin Jabbari, and Milind Tambe. Active screening for recurrent diseases: A reinforcement learning approach. In Proceedings of the 20th International Conference on Autonomous Agents and MultiAgent Systems, pp. 992-1000, 2021.
[42] Binghui Peng and Wei Chen. Adaptive influence maximization with myopic feedback. Advances in Neural Information Processing Systems, 32, 2019.
[43] Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. Deepwalk: Online learning of social repre- sentations. In Proceedings of the 20th ACM SIGKDD International Conference Knowledge Discovery and Data Mining, pp. 701-710, 2014.
[44] Scarselli, M. Gori, Ah Chung Tsoi, M. Hagenbuchner, and G. Monfardini. The Graph Neural Network Model. IEEE Transactions Neural Networks, 20( (0(1):61-800 2009.
[45] Martin JA Schuetz, J Kyle Brubaker, and Helmut G Katzgraber. Combinatorial optimization with physics-insprred graph neural networks. Nature Machine Intelligence, 4(4):367-377, 2022.
[46] Richard S Sutton. Learning to predict by the methods of temporal differences. Machine Learning, 3:9.44, 1988.
[47] 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.
[48] 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.
[49] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In International Conference on Learning Representations, 2018.
[50] Alexander Sasha Vezhnevets, Simon Osindero, Tom Schaul, Nicolas Heess, Max Jaderberg, David Silver, and Koray Kavukcuoglu. Feudal networks for hierarchical reinforcement learning. In International Conference on Machine Learning, pp. 3540-3549. PMLR, 2017.
13

---

Published as a conference paper at ICLR 2025
[51] Christopher JCH Watkins and Peter Dayan. Q-learning. Machine Learning. 8:279-292, 1992.
[52] Zheng Wen, Doina Precup, Morteza Ibrahimi, Andre Barreto, Benjamin Van Roy, and Satinder Singh. On efficiency in hierarchical reinforcement learning. Advances in Neural Information Processing Systems, 33:6708-6718, 2020.
[53] Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and Philip Yu. Comprehensive Survey on Graph Neural Networks. IEEE Transactions on Neural Networks and Learning Systems, 32(1):4 24, 2021.
[54] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? arXiv preprint arXiv:
2018.
[55] Jiaqi Yin and Cunxi Yu. Accelerating Exact Combinatorial Optimization via RL-based Ini- tialization - A Case Study in Scheduling, In 2023 IEEE/ACM International Conference on Computer Aided Design (ICCAD). IEEE, 2023.
[56] Zhitao Ying, Dylan Bourgeois, Jiaxuan You, Marinka Zitnik, and Jure Leskovec. Gnnexplainer: Generating explanations for graph neural networks. Advances in Neural Information Processing Systems, 32, 2019.
[57] Seongjun Yun, Minbyul Jeong, Raehyun Kim, Jaewoo Kang, and Hyunwoo J Kim. Graph transformer networks. Advances in Neural Information Processing Systems, 32, 2019.
[58] Jie Zhou, Ganqu Cui, Shengding Hu, Zhengyan Zhang, Cheng Yang, Zhiyuan Liu, Lifeng Wang, Changcheng Li, and Maosong Sun. Graph neural networks: A review of methods and applications. Al Open, 1:57-81, 2020.
14

---

Published as a conference paper at ICLR 2025
CONTENTS
Introduction
2
Related work
3
The WS-option framework
3.1
Preliminary: the option framework
3.2
Hierarchical MDP formulation
3.2.1
Higher layer MDP
3.2.2
Lower layer MDP
3.3
WS-option
3.3.1
Wake-sleep training
3.3.2
Layer-wise learning method selection
3.3.3
Convergence analysis
Experimental results
4.1
SSCO problem instances
Comparison with baselines
Assessing the learned policies
4.4
Generalization to larger graphs
10
Conclusion
10
Theoretical Insights
17
Hierarchical Learning for Bi-l.evel Optimization
17
A.2
Intuition behind Wake-Sleep Option Framework
17
Simplification of Options in the Lower Layer
18
A.3.1
Why Simplify Options?
18
A.3.2
Justification of Budget Irrelevance
18
A.4
Lower-Layer Reward Design
18
A.4.I
Challenges in Lower- Lower-Layer Reward Design
18
A.4.2
Normalization of Marginal Reward
19
A.5
Convergence Analysis
19
A.5.I
Proof of Theorem
19
A.52
Proof of Theorem
20
A.5.3
Interaction and Convergence of Hierarchical Layers
20
Algorithm Details
21
B.1
Algorithm 3
21
15

---

Published as a conference paper at ICLR 2025
Implementation Details
21
Network architecture
Adaptive influence maximization (AlM)
22
Route planning (RP)
C.4 44 Experiment hyper-parameter
24
Using T-Test for Evaluation
24
D
Additional Results
24
D.I
Cumulative reward
24
D.2
Resource allocation
................................
24
D.3
Generalization to larger graphs
................................
26
D.4
Evaluation on the Real-World Data
26
D.5
Ablation Study for Sleep Stage with Different Training Time
................................
26
D.6
Ablation Study for Simplified Option in the Lower Layer
27
16

---

Published as a conference paper at ICLR 2025
A THEORETICAL INSIGHTS
A.1 HIERARCHICAL LEARNING FOR BI-LEVEL OPTIMIZATION
Based on the problem formulation in equation 1] we provide a high-level insight into the nature of this problem, which motivates the use of HRL. Specifically, the SSCO problem can be reformulated as bi-level optimization problem:
max *
J (((l(((() (x²)))
(5)
subject to
π (TT') E arg max J(T', , x²1)
(6)
where J = rs XO = (Ke), and nl {St}. Here, o' constrained by equation lb and x! satisfies the constraints in equation Ic
The formulation highlights that the SSCO problem inherently exhibits a bi-level optimizztin structure. The higher-level policy n' determines the budget allocation strategy (e.g., {K,)) while the lower- level policy x selects the corresponding subsets (e.g., {5; }) based the higher-level decisions.
Given this hierarchical dependency, it is natural and intuitive to employ a hierarchical learning algorithm such as HRL to address such problems effectively.
In contrast, traditional single-agent RL methods struggle with this bi-level optimization problem due to the following limitations:
Single-agent RL lacks the structure to handle the interdependent objective, the lower-level policy x² directly depends higher-level decisions x'.
Hierarchical Dependency:
Exploration Efficiency: HRL separates exploration across two tractable levels, improving learning effiency compared to single-agent RL's flat exploration approach, which is one of the HRL's greatest advantages (52).
Scalability and Interpretability: Optimizing the joint action space of both levels in single- agent RL is computationally intractable. HRL, by decoupling the problem into manageable subproblems, offers a scalable, interpretable, and modular framework for solving complex hierarchical tasks.
A.2 INTUITION BEHIND WAKE-SLEER OPTION FRAMEWORK
The core idea for solving this bi-level optimization problem is to decompose it into two separate single-level optimization problems.
When the lower layer provides a conditionally optimal solution, denoted as π "T=(x"), the bi-level problem reduces to single-layer problem, which corresponds to the objective defined in equation In this context, the task is just to find the optimal policy for the higher layer. Conversely, when the higher-layer policy is fixed, the problem becomes solving the sub-optimization objective in equation 6, which is to find the corresponding conditionally optimal lower-layer policy. Building on this decomposition, the framework iteratively refines the higher-layer policy by alternating between the two optimization processes. Specifically, a higher-layer policy is first provided, and the corresponding conditionally optimal layer-layer policy is determined. This iterative procedure continues until the global optimal solution is achieved.
However, in the context of the SSCO problem, the role of lower layer is to perform node selection. while the higher layer only adjusts the termination condition. Due to the nature of this task, we claim that the conditionally optimal lower-layer policy remains similar across different higher-layer policies x² Given this, the wake-sleep procedure is employed. During the sleep stage, the lower layer determines a nptr-optimal policy. Subsequently, the two layers are trained jointly during the wake stage. Since the lower layer has already converged to close-to-opting policy, the joint training further refines both the higher-laye policy and the lower-layer policy, ensuring that the global optimal solution is achieved.
17

---

Published as a conference paper at ICLR 2025
A.3 SIMPLIFICATION OF OPTIONS THE LOWER LAYER
In this section, we justify our simplification of options and provide a deeper understanding of the option framework within HRL approach. First, revisit the definition of an option in 3.1 In the traditional option framework, an option is defined as tuple (1, n 5), where:
I is the initiation set, which specify the states where the option can be initialized.
π Il is the lower-policy that the agent follows while the option is being executed.
3 is the termination condition that determines when the option should terminate.
Options allow the agent to execute temporally extended actions, thereby enabling more efficient exploration and decision-making by abstracting lower-level actions into higher-level policies.
A.3.1 WHY SIMPLIFY OPTIONS?
In our specific bi-level optimization problem, the primary role of the option in the lower layer is to determine when the lower-level policy x should terminate its node selection process. Specifically, the higher-level budget allocation K2 implicitly decides the number of nodes the lower layer should select before terminating. Given this context, we simplify options due to the following reasons.
Redundant Information and Enhanced Interpretability The numerical value of the budget K; 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, clarify whether the lower layer should continue or terminate, enhancing the interpretability of the policy.
Improved Learning Efficiency Reducing the option 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.
Therefore, we simplify the option passed to the lower layer binary indicator:
o 1: Indicates that the lower layer should continue selecting nodes.
of 0: Indicates that the lower layer should stop selecting nodes and interact with the environment.
A.3.2 JUSTIFICATION OF BUDGET IRRELEVANCE
is important to note that the specific numerical value of the budget K, does not inherently affect the termination condition beyond determining the number of node selections. The budget serves as constraint that limits the range of the lower layer's actions but does not need be explicitly taken as part of the option. By abstracting the budget into binary termination signal, we retain the essential functionality required for effective decision-makinn without introducing additional complexity.
Overall, this design choice strikes a balance between simplicity and functionality, leveraging the hierarchical structure of our problem to enhance learning efficiency and policy interpretabilityy
A.4 LOWER-LAYER REWARD DESIGN
The reward structure in the lower layer is critical component of the WS-option framework, it directly influence both the stability and convergence of the model. Proper design of the reward ensures that the hierarchical optimization aligns seamlessly across layers, mitigating potential instability caused by sparse or inconsistent feedback signals.
A.4.1 CHALLENGES IN LOWER-LAYER REWARD DESIGN
The task of the lower layer is to select nodes based on the budget allocated by the higher layer. However, if the lower layer were select all Ke nodes in single step, the size of the action
18

---

Published as a conference paper at ICLR 2025
space would grow combinatorially (k.) where N is the total number of (available) nodes. This combinatorial explosion makes the optimization process computationally infeasible for large N and K,. Therefore, we adopt a sequential selection approach where the lower layer selects one node at time and repreat this process for K, times. This strategy effectively reduces the action space size from (K,) to N per selection step, significantly enhancing the tractability of the optimization problem.
However, this sequential approach introduces new challenge: sparse rewards. Specifically, the environment only provides feedback after the final node in the sequence has been selected, resulting in delayed and aggregate reward signals. Such delayed feedback make difficult for the model to identify the contribution of individual node selections the overall reward.
A.4.2 NORMALIZATION OF MARGINAL REWARD
We normalize marginal rewards to ensure that the total reward of the lower layer for each time step t the same as the reward of the higher layer, which
Σ WEA!!
11 + J. = rt. of
At each time step, the reward R(s of a is determined jointly by both the higher-layer option of and the lower-layer action af" Since both layers share the same reward and objective, it is essential that the rewards remain aligned.
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{, of a Without normalization, the reward distribution across these sub-actions could deviate, leading to inconsistencies between the lower layer's objective and the higher layer's global reward signal. As result, by normalizing the marginal reward, ensure: 1) reward consistency. The total reward for the lower layer matches the original reward defined by the hierarchical framework, maintaining coherence between the two layers, and then objective alignment. Both the higher layer and lower layer optimize the same objective, preserving the shared purpose of achieving the overall framework's goals.
A.5 CONVERGENCE ANALYSIS
A.5.1 PROOF OF THEOREM
Theorem. (Intra-option policy convergence). In WS-option framework, given any Markov transition (ST. O,, a,, Pr, 8741, 0r+1), the Q-value Q-value (ST. Oy a,) converges to the optimal Q-value function q!d (s,,07; 07, 0,, with probability assuming that the higher-layer policy is fixed.
Proof. The update formula of intra-option Q-value in tabular form is as follows:
Ft.r + ymaxq III (61.++1;1,,,411,0)
If of > 0 and at,r # at,
aot1 (Se, Ot, Ot,5))
(8)
Ft, + h ($141, 0t+1),
otherwise.
According to Theorem from 211, we need to show the update operator is a contraction mapping. For or, 0 and at,r + 0t
14 (st.r or., at,, - g. (st,r, 0t. at,r)l
=|re,r + ymaxo! "1 ( (st, T1, ymaxgl (s1,411,0 (
(9)
=y|maxy 11 (8 (1.1+1:07-11,), maxy" (81,411, ( maxg."
a
S a ( ($,.+11 - (ss
For the other case,
1 (St,r, ot,7, (e,7) - 1x (81,7, or,7, at,7)) |rtr + 74' (8041, 0241) - r2,7 - (841,,
(10)
19

---

Published as a conference paper at ICLR 2025
Note that q' ($141, = max q" ($11,, Therefore, have Ot 0t,5) - 9. (5t,7, (t,, at,r)l =7|maxgh (5141, 0b+1, maxq.' (5+11, <ymax g (8t+1, 0++1, g. (8141,
(1I)
So we prove the convergence of the intra-option policy.
A.5.2 PROOF OF THEOREM? 2
Theorem. (Option policy convergence). our WS-option framework, given any state-option pair (st. o,), the Q-value function q (st, 01) converges to the optimal Q-value function q. (st, oi) with probability I, assuming that for any given higher-layer policy, the lower-layer policy always provides the corresponding conditionally optimal response.
Proof. The Q-value of the higher layer is updated by:
( ox) qf or) - as oz) (st, or) - -9))
(12)
where 9t is the return estimated by MC methods. Again, according to the Theorem from [21], establish the convergence, need show that TE|g! (st, a+) ge] 0. Under the assumption that for any given higher-layer policy, the lower-layer always provides the best-response policy, the lower-layer policy remains fixed and conditionally optimal each time step t.. at each time step the lower policy is fixed and the conditionally optimal. Consequently, the expected value of the observed return Ir matches the Q-value estimate of (st, (+)) Therefore, the condition Elq' (st, 0,) - 9q] is satisfied. As result, the Q-value function 9¹ converges to the optimal option Q-value 9. with probability 1.
A.5.3 INTERACTION AND CONVERGENCE HIERARCHICAL LAYERS
The theorems presented above establish the convergence of two separate single-level optimization problems, as discussed in Section A.2 However, ensuring the convergence of the entire framework for bi-level optimization remains challenging due to the inherent interdependence between the two layers.
To address this, we alternate between the two optimization processes and further use our WS option framework, which effectively decouples their dependencies during training. Specifically, the higher- layer policy provides guidance the lower-layer policy, which then adapts to the given conditions and converges to its conditionally optimal response. Once the lower layer converges, the higher-layer policy is refined based on the updated performance metrics.
This iterative approach leverages the individual convergence of each layer, as proven in Theorems in I and A.5.2 to ensure the overall framework converges. By combining the independent convergence of the two layers, the framework achieves global optimization for the bi-level problem.
20

---

Published as a conference paper at ICLR 2025
B ALGORITHM DETAILS
B. ALGORITHM 3
Algorithm 3 WS-option: Store transitions
1: for each transition (s/, of at! rt, s(41) in T
do
2: Compute the gain 9t --i=t 3
3: Store the transition (s! 02 the replay buffer M1.
4: Set sf f- sf and of + oi.
5: for each node u the af do
6: of of41 f- state transition 441 of',
7: Estimate the marginal reward m by running 10 simulations.
8: Store the intermediate transition (s of my s841 o for later scaling.
Ill
+ 11 9: Update of + S++1 of + oll
end for
11: for each stored intermediate transition (s of u, m sf off)) do
m! 12: Scale the reward r- Σ m
(rf =.0))
13: Store the transition ( of u rt sTT
s7+1 04 in the replay buffer M2.
14: end for
15:
end for
C IMPLEMENTATION DETAILS
C.I NETWORK ARCHITECTURE
Higher Layer
Lower Layer
X
X
Embedding
Embedding
Embedding
GraphLayers
Expand
GraphLayers
Concatenate
Average
Embedding
Average
Concatenate
FCs
FCs
FCs
Concatenate
q
Figure 4: Network architecture
The network architecture consists of two primary components: the higher layer network and the lower layer network, as illustrated in Figure 4 There are two inputs: the node feature X and the context We use context e to represent non-node feature information, such as global information g and the option of. which is one-dimensional vector. The basic idea is to graph network layers to get node embeddings. Then, we concatenate the node embeddings with the context embedding, which used as the input of linear layers.
Higher layer network with action-in This network is used for estimating q (s',o') It is worth noting that adopt action-in network structure, which differs from the traditional action-out
21

---

Published as a conference paper at ICLR 2025
structure in typical Q-learning frameworks like DQN 36 37 also taken as inputs. In our study, this means the option (budget) is an input. We choose the action-in in structure for two main reasons: first, it can capture the properties of particular state-action pair more accurately because of the ability to embed the action into potential features. More importantly, since the size of the budget is not used parameter of the network (i.e., the number of output nodes), this approach allows for more powerful generalization ability of the model, which is not possible with the action-out structure.
In the action-in structure, actions
For the network architecture, we use graph network layers to obtain node embeddings h. An average readout function is then applied to get the graph embedding h. After concatenating this with the context embedding, use linear layers to compute g' (s",o')
Lower layer network with action-out The lower layer network adopts a traditional "action-out" structure estimate gd (s"! of', a After obtaining the node embeddings h through graph layers, we concatenate each node embedding h; with the context embedding e (so we need to expand it first). Subsequently, we average the node embeddings to get the graph embedding, which is used to denote the null action.
Details of the network In our study, we use different architectures for two problems. For the AIM problem, we employ the S2V structure in (24) with T = 3 to obtain node embedding and graph embedding (64-dimensional) for the higher layer. Subsequently, we use a linear layer to get the embedding of the option (64-dimensional), which is also called context embedding. We then concatenate the graph embedding with the context embedding and apply three linear layers to get the Q-value. For the lower layer, we also use S2V structure but with T = 1 to get both node embedding and graph embedding (64-dimensional), And using two linear layers for node embedding and graph embedding, respectively, to estimate the Q-value of all action (n nodes and null action). To tackle the RP problem, we use attention layers due to their effectiveness in capturing the features of distances and benefits associated with nodes. For the higher layer, three attention layers with embedding size of 64 are used to get the node and graph embeddings. Additionally, for this problem, the context is the option, the current node and the starting node. We use linear layer to get the option embedding and combine it with node embeddings of the current node and starting node to get the context embedding and concatenate them with the graph embedding. The combined embedding is then passed through three linear layers to estimate the Q-value. For the lower layer, single attention layer is used to get the node embedding (64 dimensional). The context embedding is the same as the higher layer. Notably, the embedding of the current node is employed as the representation for the null action instead of the graph embedding. Finally, three linear layers are applicd to get the Q-value.
C.2 ADAPTIVE INFLUENCE MAXIMIZATION (AIM)
AIM is an extension of IM 23 which aims to progressively select seed nodes in dynamic and uncertain environments maximize the spread of information within a social network. AIM has diverse applications in fields such as viral marketing, information dissemination, and public health. In this paper, we use the Independent Cascade (IC) model as the information propagation model.
The problem is modeled on a directed graph G = EV, where V and E are nodes and edges, respectively. Each node can be either active or inactive. Once node u becomes active (either by being selected as a seed or being activated by other nodes), it will attempt to activate each of its inactive neighbors with probability p(u. v) on the next day and cannot activate nodes afterwards. The probability p(u, v) is constant and is set to र=(Ø] in our model, where d' (v) denotes the indegree of node v. Initially, all nodes are inactive, and before each day starts, we can select some seed nodes to activate. We assume a total budget K (i.e., the total number of nodes that can be selected) and study how to allocate the seed nodes maximize the influenced nodes within the time constraint of T days [48].
The MDP formulation of AIM is described in the following. The datasets used in the experiments randomly generated using the erdos redos.reyy..grapl () function from Python's 's NetworkX library, with probability of 0.01.
MDP formulation For the higher level, denote the state of nodes as X, {0, 1|111x3, The state of each node is represented as a one-hot vector, indicating that the node is in one of three possible states: inactive, active (able to activate other nodes), or removed (active but unable to activate
22

---

Published as a conference paper at ICLR 2025
other nodes). What's 's more, the global information here is the remaining budget. The option is the budget allocated to the current time step. The reward is the increase in the number of influenced nodes. For the state transition, for example, given the current state sf and action a!' (selected nodes) from the lower layer, we first change the state of selected nodes ag !!f For each node v E af".
X = 10,1,00
(13)
Now we consider the interaction with environment. Assume the set of current active nodes is Ca.t and the set of their inactive neighbors is Cina.e. Then, for each node u E Cina,t, the probability of being activated is
= = = 1- - IIEAAIO)NCC. (1 p(u, (1-p(u, r)).
(14)
where (wv) is the set of neighbors of node v. and p(u, 2) is the probability that node e is activated by node u. Then, we update the state of newly activated nodes A as in equation [3
For the lower level, the state remains consistent with the higher level but includes the option chosen by the higher level. The action is to select node. The immediate reward is defined in Equation 4 The state transition occurs by simply setting the selected node to an active state.
C.3 ROUTE PLANNING (RP)
RP includes a broad class of optimization problems that seeks to find an optimal route to satisfy specific constraints and objectives. This problem is applicable to fields such as logistics, travel planning, and vehicle routing. In this paper, we focus on a travel planning scenario with N cities. The traveler must select K cities to visit, starting from a specific city. Each city provides a profit Pe, but the combined profit for visiting multiple cities in one day is a submodular function these individual profits. The profit of each city changes dynamically over time and resets to 0 once visited. There is a maximum daily travel distance dmax, with penalties for exceeding it. The goal is to visit the selected cities within T days and return to the starting point, maximizing overall travel profits.
Specifically, the initial profit of each city follows from a uniform distribution U0055, 1) and updates as follows:
Po = Po,t + Eo,r+1, for t 2 0, where Eo,0+1 ~ U(-0.05, 0.05). For a set of cities C, the combined profit in one day is defined as
(15)
f(C)
Σ Pe - mmmax(IC - 1, 0))², cEC
(16)
where 1j is a coefficient set to 1 in our experiments. Exceeding the maximum daily travel distance dmax results in a penalty proportional to the excess distance (we choose 5). The dmax set is 1.5 max.,j dej, where de is the distance of city and j. The datasets used in this problem (coordinates of the city) are also randomly generated using the random. rand () function from Python's 'ss Numpy library with a scale of 100.
MDP formulation For the higher level, the state includes: the coordinates of each city, their profits, the current city, and the starting city. The option is the same as in the AIM problem. The reward is the combined profits of the selected cities the current time step. The state transition involves the update of profits as described in Equation T5 and the change of the current city.
For the lower level, the state remains consistent with the higher level but also includes the option chosen by the higher level. The action is to select a city. The marginal reward is simply the profit of the selected city, and the immediate reward can be obtained as described in Equation 4 Note that there is no propagation process, and the expected profit of each city does not change. Therefore, we can set !! O. The state transition only involves the change in the current node and is deterministic.
The definitions of MDPs for these two problems are also shown in Table and we will use the framework proposed in this paper to address these problems.
23

---

Published as a conference paper at ICLR 2025
Table 5: MDPs for AIM and RP problems
Problem
Layer
State
Option/Action
Reward
Higher
active and inactive
choose budget k
number of active nodes
AIM
Lower
active and inactive, option
select node
scaled marginal reward choosing node combined profit of & cities scaled profit
Higher
coordinates, profits
choose a budget k
RP
Lower
coordinates, profits. option
select city
C.4 EXPERIMENT HYPER-PARAMETER
To ensure the stability of the learning process in both problems, we employ Double Deep Q-Networks with update frequency of 10 episodes. The e-greedy strategy we is initialized with e 0.9 and decays by factor of 0.98 after each single training, with minimum threshold of 0.1. We train each model for 20 epochs and 10 episodes.
All experiments on two COPs are implemented in Python and conducted on two machines. One is NVIDIA GeForce RTX 4090 GPU and Intel 24GB 24-Core 19-13900K.. The other is NVIDIA V100 GPU and Inter 256 GB 32-Core Xeon E5-2683 v4.
Table 6: Experiment
for both problems
Parameter
AIM
RP
Discount factor (?)
0.99
0.99
Learning rate (higher-layer)
10
10
Learning rate (lower-layer)
10Th
10
Batch size
32
32
DDQN update frequency
10 episodes
10 episodes
Initial in e-greedy
0.9
0.9
Decay factor for e
0.98
0.98
Minimum threshold
0.1
0.1
Epochs
20
20
Episodes
10
NVIDIA GeForce RTX 4090, Intel 24GB 24-Core 19-13900K,
Hardware
NVIDIA V100, Intel 256GB 32-Core Xeon E5-2683 v4
C.5 USING T-TEST FOR EVALUATION
To evaluate the performance of our model, we use t-test rather than standard deviation. This approach particularly suitable given the presence of both aleatoric and epistemic uncertainties. Typically, we conduct multiple experiments to calculate the mean and standard deviation. Through this process, the epistemic uncertainty-ariiin from limited data-can mitigated according to the law of large numbers. However, aleatoric uncertainty, which stems from inherent stochasticity in the environment, irreducible and contributes to natural variability. Consequently, the standard deviation in such scenarios primarily reflects aleatoric uncertainty. In our stochastic environment, this metric alone provides limited insight into the true performance of the model.
D ADDITIONAL RESULTS
D.1 CUMULATIVE REWARD
D.2 RESOURCE ALLOCATION
Figure 6 showws the budget allocation for AIM problem. The last three days have been ignored due none resource allocation.
24

---

Published as a conference paper at ICLR 2025
Figure 5: Cumulative reward during training for AIM T 10, K = 20
Paly Pleuss
Pleved 20
Figure Budget allocation for T 10, K = 10
2 Doaer 822 timer (1a))
Figure 7: Budget allocation for T'= = =00, K
20
Table 7: RP: Generalization to larger graphs. All cases have p-values 0.05.
200
400
700
1000
WS-option
14.45
13.48
14.49
14.23
greedy
12.41
10.74
11.37
12.04
GA
12.62
10.96
11.37
11.77
25

---

Published as a conference paper at ICLR 2025
Falyy: Paurt: 12 30
Folect 2 Janas 14 30
Time
Figure Budget allocation for T 10, K 30
D.3 GENERALIZATION LARGER GRAPHS
D.4 EVALUATION ON THE REAL- WORLD DATA
Real-world datasets often exhibit certain patterns, such as clustering characteristics. These patterns easier for our RL-based algorithm to recognize, which can, in turn, achieve even better results. To demonstrate this, we evaluate our model on power2500 dataset, which has 2500 nodes.
Method
T=10, K=20
WS-option
496.37
average-degree
314.49
average-score
317.16
normal-degree
449.30
normal-score
462.54
static-degree
350.84
static-score
393.10
Table 8: Performance comparison of methods on the power2500 dataset (T=10, K=20).
The results in Table 8 show that our RL-based algorithm (WS-option) significantly outperforms baseline methods, especially under scenarios characterized by clustering patterns. This demonstrates the model's capability to exploit structural properties in real-world datasets.
D.5 ABLATION STUDY FOR SLEEP STAGE WITH DIFFERENT TRAINING TIME
Method
T=10, K-20
WS-option (sleep with 1/2 N)
118.56
WS W'Soptioo (sleep with 1/3 N)
104.84
WS-option (sleep with 2/3 N)
118.59
average-degree average-score normal-degree normal-score
104.54
116.10
101.50
111.89
static-degree
105.25
static-score
118.13
Table 9: Performance comparison under different training time for the sleep stage (T=10, K=20).
Note that we use the same random seed as in 4.2 From the results, we observe that ensuring the lower layer converges during the sleep stage is crucial. Specifically, when the model trains with N
26

---

Published as a conference paper at ICLR 2025
3 N, the performance is nearly identical, indicating sufficient convergence. In contrast, training with 3 N leads to significantly degraded performance, demonstrating that insufficient convergence in the lower layer undermines the overall results.
D.6 ABLATION STUDY FOR SIMPLIFIED OPTION IN THE LOWER LAYER
The experimental results for evaluating the effect of simplifying the option the lower layer are presented in Table I0 We observe that using simplified option achieves slightly better performance compared to the non-simplified version (118.56 vs. 116.37). This shows that while the non-simplified option can still yield good results with sufficient iterations, it requires more training for agents to accurately identify termination conditions. Specifically, termination occurs only when the budget equals O; when the budget is greater than 0, the behavior remains the same across methods.
Method
T=10, K=20
WS-option
118.56
WS-option (non-simplified option)
116.37
average-degree
104.54
average-score
116.10
normal-degree
101.50
normal-score
111.89
static-degree
105.23
static-score
118.13
Table 10: Ablation study results for simplified options in the lower layer (T=10, K=20).
27


Reviews:
[{"review_id": "BQNb2QOH4v", "reviewer": "Reviewer_E3Wz", "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.", "questions": "Additional questions:\n\n 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?\n 2. It is unclear to me how the simulations are performed. Is it executing the greedy policy 10 times from the current state?\n 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?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 1, "presentation": 3, "contribution": 2, "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:\n\n1. Design choices lack proper justification\n\n     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.\n\n    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?\n\n    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?\n\n    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)? \n\n    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.\n \n2. Experimental baselines are non-adaptive\n\n    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).\n\n    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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "D2fJPY53vf", "reviewer": "Reviewer_zNgF", "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.", "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?\n2.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?\n3.Are there any plans to explore more universal graph embedding techniques that could be applicable across different SSCO problems without the need for customization?\n4.Could the authors provide more details on the computational complexity of the WS-option framework, especially when compared to existing methods in the literature?\n5.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?\n6.Will increasing the number of trials and providing confidence intervals for the experimental results further strengthen the conclusions drawn from the data?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "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.\n2.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.\n3.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.\n2.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.\n3.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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "k7uLnfEbc4", "reviewer": "Reviewer_R7Hz", "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.", "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.\n\nQ2. 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?\n\nQ3. Could you provide more details and a reference for the action-in architecture and its role in generalisation?\n\nQ4. Could you provide a motivation for the baseline selection and also explain how the results compare to Tong et al. [1].", "limitations": "", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "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. \n\nThe 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.\n\nI 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. \n\nFor 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. \n\n[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.\n\nMinor remarks:\n- I advise to avoid using abbreviations without introduction (e.g., WS, MC, TD lines 88-96, HER line 150)\n- typos: adpative (line 219), MD (line 365)", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)