Reinforcement learning with combinatorial actions for coupled restless bandits
This addresses a key bottleneck in applying RL to real-world planning problems with combinatorial actions, such as restless bandits, though it is incremental in combining existing techniques for a specific domain.
The paper tackled the problem of reinforcement learning with large, combinatorial action spaces by proposing SEQUOIA, an algorithm that embeds a Q-network into a mixed-integer program to optimize long-term reward, and it outperformed existing methods by an average of 24.8% on novel restless bandit problems with combinatorial constraints.
Reinforcement learning (RL) has increasingly been applied to solve real-world planning problems, with progress in handling large state spaces and time horizons. However, a key bottleneck in many domains is that RL methods cannot accommodate large, combinatorially structured action spaces. In such settings, even representing the set of feasible actions at a single step may require a complex discrete optimization formulation. We leverage recent advances in embedding trained neural networks into optimization problems to propose SEQUOIA, an RL algorithm that directly optimizes for long-term reward over the feasible action space. Our approach embeds a Q-network into a mixed-integer program to select a combinatorial action in each timestep. Here, we focus on planning over restless bandits, a class of planning problems which capture many real-world examples of sequential decision making. We introduce coRMAB, a broader class of restless bandits with combinatorial actions that cannot be decoupled across the arms of the restless bandit, requiring direct solving over the joint, exponentially large action space. We empirically validate SEQUOIA on four novel restless bandit problems with combinatorial constraints: multiple interventions, path constraints, bipartite matching, and capacity constraints. Our approach significantly outperforms existing methods -- which cannot address sequential planning and combinatorial selection simultaneously -- by an average of 24.8\% on these difficult instances.