Research map / Reinforcement learning / Policy gradient and actor-critic
Reinforcement learning with combinatorial actions for coupled restless bandits
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 SEQUOIA, which embeds a DQN Q-network into a MILP to select combinatorial actions each timestep, and evaluates it on four novel coupled restless bandit (coRMAB) settings.
Problem
Restless bandit planning with strongly coupled, combinatorial action spaces where standard Whittle index / decoupling methods fail and enumeration of the joint action space is intractable.
Approach
Train a Q-network over state-action pairs with DQN and, at every step, solve for the best feasible combinatorial action by embedding the ReLU Q-network exactly into a mixed-integer program, combined with off-policy warm-starting (myopic, perturbed and infeasible actions) and MILP memoization.
Key results
- SEQUOIA outperforms existing methods by an average of 24.8% on the four coRMAB problem settings, per the abstract.
- Iterative DQN performs on average 12.1% lower than SEQUOIA even in the capacity-constrained setting where it performs best.
- The Sampling heuristic comes close to Myopic with 20 arms but falls far behind at 100 arms.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use SEQUOIA instead of existing methods | coRMAB problems · Four coRMAB settings (aggregate) | expected reward: 24.8% | Helped |
| replace MILP-based combinatorial action selection with greedy iterative construction (ablation) | SEQUOIA (Iterative DQN variant) · Capacity-constrained coRMAB | expected reward: 12.1% lower | Hurt |
| use random sampling of actions instead of sequential planning | coRMAB baselines · 20 arms | expected reward | No clear effect |
| use random sampling of actions instead of sequential planning | coRMAB baselines · 100 arms | expected reward | Hurt |
| use IPOPT continuous relaxation and sample discrete actions instead of Gurobi MILP | capacity-constrained coRMAB action selection · Capacity-constrained coRMAB | action quality | Helped |
| increase the Q-network hidden-layer size from 32 to 128 units (ablation) | SEQUOIA · Training runtime | runtime: an order of magnitude | Hurt |
Surprising findings
- Myopic policies can perform arbitrarily poorly in restless bandits, motivating sequential planning.
- Including infeasible actions in warm-start samples improves Q-network generalization to feasible actions.
Limitations
- MILP solves at every step are computationally expensive, the main bottleneck for training and inference.
- Relies on known transition dynamics and a MILP-representable constraint set.
- Path-constrained training uses a decoupled budget-only relaxation rather than the full path constraint, a heuristic approximation.
Experimental setup
Datasets: synthetic restless bandit instances (4-state MultiStateRMAB, London tube graph for routing)
Benchmarks: multiple interventions scheduling (bipartite matching) capacity-constrained path-constrained (routing)
Metrics: expected cumulative reward over 50 episodes of length 20, av
Baselines: Myopic Sampling Iterative Myopic Iterative DQN Random No Action
Builds on: DQN double DQN prioritized experience replay ReLU MILP embedding of neural networks
Closest papers by meaning
- Structured Reinforcement Learning for Combinatorial Decision-Making (NeurIPS 2025 · similarity 0.90)
- GINO-Q: Learning an Asymptotically Optimal Index Policy for Restless Multi-armed Bandits (AAAI 2026 · similarity 0.89)
- Combinatorial Optimization with Policy Adaptation using Latent Space Search (NeurIPS 2023 · similarity 0.89)
- Provably Efficient Reinforcement Learning for Adversarial Restless Multi-Armed Bandits with Unknown Transitions and Bandit Feedback (ICML 2024 · similarity 0.88)
- Preference Optimization for Combinatorial Optimization Problems (ICML 2025 · similarity 0.87)
- The Bandit Whisperer: Communication Learning for Restless Bandits (AAAI 2025 · similarity 0.87)
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.