# Sequential Stochastic Combinatorial Optimization Using Hierarchal Reinforcement Learning

arXiv: https://arxiv.org/abs/2502.05537 · HTML: https://mlsanity.com/paper/2502.05537/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Placed in RL for games and combinatorial optimization, one of 15 directions in Deep reinforcement learning methods.
- First posted on arXiv 8 Feb 2025.

## Placed in

- Deep reinforcement learning methods / [RL for games and combinatorial optimization](https://mlsanity.com/deeprl/rl-for-games-and-combinatorial-optimization/)

## Built on by (most cited first, 4 of 4)

- [Demonstrating Real Advantage of Machine-Learning-Enhanced Monte Carlo for Combinatorial Optimization](https://mlsanity.com/paper/2510.19544/) (2025)
- [HyCO: A Hybrid Neural Solver for Combinatorial Optimization](https://mlsanity.com/paper/2609.07990/) (2026)
- [Representative Action Selection for Large Action Space Bandit Families](https://mlsanity.com/paper/2505.18269/) (2025)
- [Learning Multi-Timescale Abstractions for Hierarchical Combinatorial Planning](https://mlsanity.com/paper/2605.17058/) (2026)

## Abstract (arXiv)

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.