Research map / Reinforcement learning / MDPs and planning
Sequential Stochastic Combinatorial Optimization Using Hierarchal Reinforcement Learning
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes WS-option, a two-layer option-based hierarchical RL framework that jointly learns budget allocation over time and per-step node selection for sequential stochastic combinatorial optimization, using wake-sleep training and MC/TD layer-wise learning.
Problem
Sequential stochastic combinatorial optimization (SSCO), where a total node budget must be allocated across time steps and nodes selected each step under stochastic dynamics; prior RL work assumes uniform budget allocation.
Approach
A two-layer option-based HRL where the higher layer picks per-step budgets (trained with Monte Carlo Q-learning) and the lower layer selects nodes (trained with TD Q-learning), with a wake-sleep schedule that freezes the higher layer first to avoid mutual interference, plus marginal-reward normalization to align the layers' rewards.
Key results
- On AIM with n=200, T,K=10,20, WS-option achieves 118.56 cumulative reward vs 116.10 for the best baseline (average-score).
- On RP with n=100, T,K=10,30, WS-option achieves 18.57 vs 15.70 for GA and 15.68 for greedy.
- Trained on 50-100 node graphs, WS-option reaches 221.16 on 1000-node AIM graphs vs 220.81 for normal-score, and beats all baselines at 200-700 nodes except it trails at 1000 nodes for normal policies.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use WS-option instead of the strongest listed baseline | AIM · n=200; T,K=10,10; 10,20; 10,30; 20,10 | cumulative reward: 74.36 -> 76.00; 116.10 -> 118.56; 128.29 -> 129.06; 80.31 -> 80.95 | Helped |
| Use WS-option instead of the strongest listed baseline | Route planning · n=100; T,K=10,10; 10,20; 10,30; 20,10 | cumulative reward: 6.79 -> 7.46; 12.02 -> 12.86; 15.70 -> 18.57; 6.93 -> 7.52 | Helped |
| Apply the small-graph-trained WS-option model to larger graphs without retraining | WS-option · AIM generalization, n=200, 400, 700, 1000 | cumulative reward: 119.80 -> 120.88; 171.91 -> 176.13; 199.41 -> 204.87; 220.81 -> 221.16 | Helped |
| Use the learned budget-allocation policy rather than average, normal, or static allocation, with the learned lower layer fixed | AIM budget allocation · T=10, K=10 and T=10, K=20 | cumulative reward: 71.45 -> 76.79; 126.35 -> 127.51 | Helped |
| Use WS-option node selection rather than degree- or score-based selection, with average budget allocation fixed | AIM node selection · T=10, K=10 and T=10, K=20 | cumulative reward: 69.15 -> 71.45; 125.02 -> 126.35 | Helped |
Surprising findings
- Several baselines (e.g., normal-score) outperform WS-option on the 1000-node AIM setting in the generalization table, and at larger scales the gap narrows.
- Gains over the strongest baseline are small in several AIM settings (e.g., 76.00 vs 75.05 for T,K=10,10), with some comparisons within a few percent.
Limitations
- Each new problem requires a new graph embedding technique, adding implementation complexity.
- Convergence theory is limited to the tabular case.
- Uses simple graph neural networks (S2V) and the wake-sleep schedule relies on a simple average-budget strategy during the sleep stage.
Experimental setup
Datasets: randomly generated Erdos-Renyi graphs (NetworkX, p=0.01)
Benchmarks: adaptive influence maximization (IC model, synthetic graphs) route planning (synthetic)
Metrics: cumulative reward two-sample t-test p-values
Baselines: average-degree average-score normal-degree normal-score static-degree static-score greedy GA
Builds on: option framework structure2vec double Q-learning hindsight experience replay
Closest papers by meaning
- Learning Multi-Timescale Abstractions for Hierarchical Combinatorial Planning (ICML 2026 · similarity 0.91)
- Structured Reinforcement Learning for Combinatorial Decision-Making (NeurIPS 2025 · similarity 0.87)
- Combinatorial Reinforcement Learning with Preference Feedback (ICML 2025 · similarity 0.86)
- Reinforcement learning with combinatorial actions for coupled restless bandits (ICLR 2025 · similarity 0.86)
- Preference Optimization for Combinatorial Optimization Problems (ICML 2025 · similarity 0.86)
- Randomized Exploration for Reinforcement Learning with Multinomial Logistic Function Approximation (NeurIPS 2024 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.