Reinforcement learning with combinatorial actions for coupled restless bandits
Authors: Lily Xu
Bryan Wilder
Elias Boutros Khalil
Milind Tambe
Venue: ICLR 2025 Poster (2025)
Keywords: reinforcement learning
combinatorial optimization
restless bandits
mixed-integer programming
Primary area: reinforcement learning
TL;DR: We enable reinforcement learning with per-timestep combinatorial (NP-hard) constraints on actions by combining mixed-integer programming with DQN.

Abstract: 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.

Published as a conference paper at ICLR 2025
REINFORCEMENT LEARNING WITH COMBINATORIAL ACTIONS FOR COUPLED RESTLESS BANDITS
Lily Xu, 1.2* Bryan Wilder, Elias B. Khalil, 4 Milind Tambe'
Harvard University, Uniiversity of Oxford, CCarnegie Mellon University, 'University of Toronto
ABSTRACT
Reinforcement learning (RL) has increasingly been applied to solve real-world planning problems, with progress in handling large state spaces and time hori- zons. However, key bottleneck in many domains is that RL methods cannot ac- commodate 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 combinatorial action in each timestep. Here, we focus planning 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 exist- ing whichh cannot address sequential planning and combinatorial selec- tion simultaneously-by an average of 24.8% on these difficult instances.
restless
INTRODUCTION
Reinforcement learning (RI.) has made tremendous progress in recent years to solve a wide range of practical problems (Treloar al. 2020 Marot et al. 2021 Silvestro al. 2022 Degrave al.) 2022). While successful at dealing with large or infinite state spaces, RL struggles with discrete, combinatorial action spaces. This limitation is pertinent to many real-world sequential decision- making problems, where resource constraints frequently lead to combinatorial action spaces (Dulac- Arnol al.. 2020). Consider, for example, sequential resource allocation problem in which public health workers are dispatched to visit patients. The workers each have limited daily budget to maximize patient well-being. These requirements give rise to an exponentially large combinatorial action space to optimize over, even when the number of workers and patients is small.
suitable framework for modeling such problems that of restless multi-armed bandits NNiñ- Moral 2023), which have been applied to settings from clinical trial design (Villar et al. 2015) to behavioral interventions (Mate al. 2022). An "arm" the restless bandit corresponds to patient in the aforementioned public health example. At every timestep, each arm is in one of a finite number of states (e.g.. representing the health of that individual), and we aim to select actions so that arms move into the more beneficial states. Typically, restless bandit solutions have been confined to relatively simple and thus tractable problem structures. For example, the common Whittle index policy (Whittle, 1988) requires that each arm be independent, each action impacts only a single arm, and arms transition independently (Figure [[]]. Under these assumptions, the problem admits a threshold-basse top-K policy which decouples the combinatorial action selection by learning policies for each arm independently.
Real-world applications, on the other hand, often involve complicated problem structures beyond the simple budget constraint, for which action decomposition would substantially degrade performance.
"Contact: f1y. xécolumb a edu. Code available at: https//gthhaaammliiiisccmimaaaat

---

Published as a conference paper at ICLR 2025
Enables decoupling
Cannot decouple
Restless bandit
A. Multiple interventions
Bipartite matching
Capacity constrained
D. Path planning
4g
Figure 1: Restless bandits are a variant of planning over Markov decision processes, where each "arm" transitions depending on whether it is acted upon. Standard restless bandits can be solved with threshold-based policies, but these approaches are unable to address challenging settings with combinatorial constraints on the actions that cannot be decoupled, prohibiting the application of easy heuristic solutions. Our paper considers this class of strongly coupled restless bandits (CORMAB). We describe these new problem formulations (A-D) for restless bandits in detail in Section 3
Figure [ TA-D illustrate four such scenarios. For example, consider the problem of planning route for a health worker to visit patients within travel constraint (see Figure[[]> each action (path) im- pacts multiple patients and cannot be decomposed further (e.g., into separate edges) while ensuring the overall path is feasible. Another example is where actions represent heterogeneous interventions that may impact not just a single arm but several simultaneously. Individuals may be acted on by multiple actions simultancously (c.g., exposure to different messaging campaigns or nurse visits), with a potentially nonlinear cumulative effect (Figure[B).
In these more complex settings, we can no longer decompose the actions and must reason about the entire combinatorial structure at once. Coupled with combinatorial constraints, the discrete action space becomes notoriously difficult to optimize the reward function over. Thus, existing algorithms cannot accommodate this class of problems. To that end, we consider the restless bandit problem with combinatorial actions (which we call CORMAB) in four problem settings (Figure D, described in Section that highlight its broad applicability.
The existing literature at the intersection of RL and combinatorial optimization has not consid- ered sequential problems where the action space in each step is combinatorial. Rather, existing approaches solve uinglestage combinatorial optimization problems with RL by decomposing them into iterative choices from a small action set, such as iteratively choosing the next node in a traveling salesperson vehicle routing problem (Dai et al. 2017: Barrett al. 2020 Delarue al. 2020).
Here, we consider for the first time sequential combinatorial settings where the reward comes not from single-shot action but is incurred after enacting a policy over many timesteps. We leverage recent advances in integrating deep learning with mathematical programming, in which neural network with ReLU activations can be directly embedded into mixed-integer program (Fischetti & Jo 2018 Serra et al.) 2018). By integrating this technique with an RL. training procedure, we show how learn the long-term reward using a deep Q-network to approximate the value function, while tractably optimizing this Q-network over the discrete combinatorial space at each step with mixed-integer program. We call our algorithm SEQUOIA, for SEQUential cOmbInatorial Actions.
Our paper contributes: (1) four new problem formulations for restless bandits with combinatorial ac- tion constraints, (2) a general-purpose solution approach that combines deep Q-learning with math- ematical programming, and (3) empirical evaluations demonstrating the strength of this approach. Our work opens up a broad class of problem settings for restless bandits with more complex action constraints. Beyond restless bandits, our work enables general RL planning over Markov decision processes with per- timeteett combinatorial action spaces.
PROBLEM DESCRIPTION
We consider offline, stochastic planning for restless bandits with combinatorial action constraints, where the transition dynamics and reward are known priori, but the state and action space are too large to be solved directly. Specifically, we consider the setting where the arms are strongly coupled so we camnot decouple the arms of the bandit into independently controlled Markov chains using Lagrangian relaxation. We begin by describing the standard restless bandit, then present our general formulation for constrained combinatoriallaction RMABs, which we refer to CORMAB B.
2

---

Published as a conference paper at ICLR 2025
2.1 STANDARD RESTLESS BANDITS
The standard restless bandit problem is modeled by a set of Markov decision processes (MDPs). Each MDP (S, A, P, R) represents one of the restless bandit. The state 8j S of arm transitions to next state of depending on the selected action 0j E A, with known probability (5, S x A x S + [0, 1]. We use the vector $ E S* to denote the joint state of all J arms, and similarly
A for the joint action. Traditional restless bandits assume that each action acts on a single arm only, enabling an optimal policy that decouples the solution into inde- pendent, per-arm subproblems.
Each state 8j E S has an associated reward r5())) and the total reward at each timestep t is the sum of the rewards of the arms: (() Ty The traditional restless bandit problem requires
selecting binary action dj E {0, for each arm, subject to total budget constraint 2j=11 0j S B.
2.2 RESTLESS BANDITS WITH STRONGLY COUPLED ACTIONS (CORMAB)
We now introduce CORMABs a broader class of problems for restless bandits where actions may be strongly coupled due to combinatorial constraints. We consider a set of actions a, that each impact the transition probability of some subset of the arms. At each timestep, combinatorial action over the arms i.c., the action vector a must be in C S AA", a set defined by constraints. (We provide example instantiations of C in Section 3 Now, the transition probabilities may be coupled, with individual actions impacting multiple arms. We denote the joint transition probability px S' A S [0,1]"
must pick
From a given state 8, by Bellman's optimality principle we seek the combinatorial action a that maximizes the expected long-term reward, with discount factor (0, 1]:
max ((s.a) acc
(1)
s.t. Q(s a) = R(s) +y PP'
Vs E S* a
s'ES
V(s) = max Q(8,a) a) acc
V8 E Sx
This value function is difficult to implement as the max over actions a is taken over a combinatorial number of possible actions, and there are combinatorial number of constraints (for each possible state 8). Enumerative methods are therefore intractable. We address CORMAB problems this form using combination of RL to learn the Q-function and mixed- programming find an optimal constraint-feasible action a.
3 ENABLING NEW PROBLEM FORMULATIONS FOR RESTLESS BANDITS
We introduce four instantiations CORMAB problems which cannot be modeled or solved by standard restless bandit approaches. These formulations consider compounding effects from mul- tiple interventions, path planning, bipartite matching. and capacity constraints-ent of which is widely applicable challenge for resource allocation problems. To the best of our knowledge, the following problem formulations are all novel for restless bandits.
In each case, action selection requires various forms of constrained optimization. Note that planning in each instance still requires specifying the Q-function, which serves as the objective in each setting; in Section 4 we will address how to resolve estimating the Q-function. Additional details, including MILP formulations for each problem setting, are provided in Appendix C
Multiple interventions for public health In public health programs, different informational cam- paigns may impact different groups of individuals. Interventions could include, for example, radio, ads at bus stations, church events, or fliers. We model this problem as a restless bandit where one action impact fixed subset of arms. We propose the first combinatorial setting in which (a) one action impacts multiple arms, and (b) multiple actions may be applied simultancously to each arm with compounding effects. One example of this setting is visualized in Figure
3

---

Published as a conference paper at ICLR 2025
Here, each action a, {0, }} corresponds to one of N possible messaging interventions, each arm corresponds to a patient, and the state $, of a patient represents their engagement level in a health program. In this model, of engagement. More details in Appendix [8.2 The transition probability for patient j in state 8j transitioning to a higher 8) or lower 8 state is:
consider 8j E f0, 2, where each is associated with higher level
Pjls, a, 85) & (w,(s))
a( = Ps(sj,
-1-3:,)))-1 a,)))
where (,)s)) E RN is an individual and state-specific coefficient vector describing their response to different interventions, a is the action vector, and Φ IR [0, 1] is known link function. Each action has a cost e; and we are limited by a total budget B, giving rise to the optimization problem:
(s, s.t. Σ cjas
Egas B; ag {0, [je.J.
JEP
Note that this combinatorial problem formulation generalizes the standard restless bandit: we can recover the original restless bandit setting by considering N = actions, where the jth action is connected the jth arm and the edge weight W/ equals the transition probability (s ag 1, In our experiments, we consider sigmoid link function, which has been widely used in the public health literature (Levy et al., 2006). We show that using a piecewise linear approximation of this link function, which can be easily encoded into the MILP solver, solves the problem effectively.
Schedule-constrainee CORMAB (Bipartite matching) Here, actions (e.g., volunteer health workers) and arms (e.g., patients) both have limited time windows for scheduling, with K avail- able timeslots. We must assign workers to patients to form a valid schedule, where workers and patients are matched such that they have mutually agreed upon times. Each worker can only be assigned once. This problem resembles bipartite matching (Figure [B).
Capacity-constraince CORMAB Suppose we have N workers each with budget constraint b;s and the J arms each have some cost Cj for contacting them (Figure TC). This problem is an instance of the NP-hard generalized assignment problem (Özbakir et al. 2010 The goal is to assign workers to patients while respecting each worker's capacity constraint.
Path-constrainee CORMAB Now suppose that each arm of the restless bandit lies in network, represented as a graph (V, E) (see Figure [].. For example, nodes may correspond to patients' residential locations if we scheduling at-home patient interventions (Kergosien et al. 2009). We have one arm at each node j E V, with edges (J. k) E & connecting the nodes. We include self- loops, (j,j) for all V. The action is to pick a path along the edges in & with a constraint on its total length T; we act on each arm whose node we visit along the path.
4 SOLVING RMABS WITH COMBINATORIAL ACTIONS
We present novel algorithm, SEQUOIA, which builds on deep Q-learning (DQN) by integrating mixed-integer linear program (MILP) for combinatorial action selection. We start by introducing the hasic DQN+MILP framework in Section 4.T In Section 4.2 we provide a set strategies to find a good initialization for the Q-network and improve computational efficiency. We visualize our approach in Figure 2 and Algorithm| provides pseudocode for the Q-network training procedure.
While we focus on the restless bandit problem setting, SEQUOIA generalizes other sequential planning problems with per-timestep combinatorial actions, provided that the restrictions on the actions can be represented as constraints mixed-integer program.
4.1 Q-LEARNING WITH COMBINATORIAL ACTIONS
Deep Q-learning aims to estimate the long-run value of action a from state 8, denoted Q(8, a), by parameterizing the Q-function with a neural network. The DQN algorithm (Mnih) 2013) samples (action, state, reward) sequences via a mix of random actions and on-policy samples (i.e., actions that maximize the current estimate of Q). The samples are used to improve the Q-function via temporal difference (TD) updates which aim minimize the residual in the Bellman equation.
4

---

Published as a conference paper at ICLR 2025
Standard DQN
a al
SEQUOIA evaluation
Solve MILP to find best action
state chserver!
(ls. a
state
For omall, non-ccmmbneter intractatle for
abserved
estimated Q-value Q
desis varisbles from MILP inputs into NN
action a
decision voriacles
1. SEQUOIA training Learn Q-function approximator
used generate trojetiets
max
Q a)
G-value (from NNO objective
state
S.t.
a [0.1)*
estimated Q-value
action
@ a)
combinatorial constraints
hato sad samplic Faom memocy
constraints and weights to embed NN
embed trained deep G-nwworkk into MILP
Figure 2: An overview of our SEQUOIA algorithm. Standard DQN takes as input the state and outputs estimated Q-values for actions, which are assumed to be easily enumerable. In contrast, we consider cases when the actions are too large to be enumerated due their combinatorial constraint structure. PART 1. We therefore train Q-network where the action a is included as an input (Algorithm [ described in Section (41).. PART 2. We then embed that Q-network into a mixed- integer program, which also specifies the combinatorial action constraints (c.g., the formulations provided in Scction()). In evaluating the objective, the MILP solver conducts a forward pass through the neural network in order to calculate the expected Q-value. Solving the MILP thus finds an action a (the decision variables) that maximizes the predicted Q-value Q( a) (our objective).
This framework breaks down when the action space is exponentially large, as in our setting. The first challenge that typical uses of DQN output Q-values for all actions simultancously by mapping the state to one network output per action. Since our domain has an exponentially large action space, we instead use DQN to estimate the Q-value of a given state aetieeaccionn pair, where the action is represented as a binary vector a of length N (Figure Part 1).
While this allows for a concise representation of the Q-function, it leaves critical bottleneck: com- puting the temporal difference loss requires identifying the best action on policy, that is, according to the current Q-function (Algorithm [ lines and [T3). That is, it requires solving problems of the form max, Q(s,, a; 0) where 0 denotes the parameters of the Q-network. With standard DQN, this problem would be solved by evaluating all actions and picking the best one, but brute-force enumeration is infeasible for combinatorial spaces.
Instead, we leverage recent advances that enable encoding a neural network into a -ixted linear program to enable optimization over the trained network (Fischetti & Jo 2018 Serra et al. 2018). Using these methods, we embed an extra set of variables and constraints in the MILP This possible because neural networks are specified nected with a rectified linear unit (ReLU) as the activation function. Such a neural network can thus be modeled as a binary mixed-integer linear program, with continuous variable representing the output of each hidden unit and a binary variable representing the output of each ReLU. Specifically, a single hidden unit in neural network is represented as:
series of linear inequalities, commonly
x ( T b)
(3)
where the activation function a is the MIL.P-representable ReLU: (a)) = ReI.U(a) = max (0, a). Fischetti & Jo (2018) show that this hidden unit can be expressed as:
w
+ b x
220,
s s
(4)
0, == E {0.1}
8 3 0
(5)
(6)
with binary variable 2 and continuous variables x and s. The two logical constraints (eq. 5) are translated into big-M constraints. In this way, fully- collecconnected feed-forward neural network with D hidden layers and P neurons per layer can be represented exactly within a MILP with O(DP)
binary variables and linear constraints (see Section 4.2.1 Huchette et al. (202)))
5

---

Published as a conference paper at ICLR 2025
Algorithm 1 SEQUOIA for RL with combinatorial actions
Input: MDP instance (S, A, P, R) and set of constraints C _ A Parameter: Epsilon-greedy parameter e, target update frequency F
1: Initialize action-value function Q with weights 0
2: Strategically generate actions, and store state-action samples in memory D
3: Pre-train Q with myopic observed reward, using state-action samples from
4: Initialize target network Q: f= A
5: Construct MILP with current network weights f and constraints C
6: for episode I....... do
7: for 1. 1 T do
8:
With probability e, select random action a!!) E
9:
Otherwise, select a arg maxa MILP(s!); 0-)
10:
Execute action a (*)) calculate expected reward R(O, and observe next state s(++1)
11:
Store transition (s(t), aa) ((()) ((()),((++))) ((++1)) in D
Sample random minibatch of transitions (s(k), (k) a (()), R(h, s((-1)) from D
12:
13:
Set (h) = [2(a) + maxa MILP(ss (+))0)
14:
Gradient descent step on (y)**) (s((k) a (1))0))
15:
Every F steps, update Q = Q
16:
return Q-function Q
Specifically, we use the MILP represent the Q-function Q(s, a). the objective of our planning problem, as specified in the problem formulations in Section 3 We therefore embed the trained Q-network into the MILP formulations of our constraints and use its output as our objective. Thus every time we solve the MILP to determine an optimal action, we implicitly simulate forward pass of the neural network to calculate the Q-value. In every new episode, we build a new MILP instance which includes constraints that represent the current policy network Q with parameters 0, along with the original constraints on the actions. Then the inner step of arg max, (line D solves that MII. to pick combinatorial action for state that maximizes the expected long return of pair (s, a), based on estimates from the neural network Q (Figure 2 Part 2).
Typically, DQN requires executing the current policy determined by the current Q-network to get on-policy samples. However, whereas standard DQN assumes we can enumerate all actions to pick the with the highest Q-value, doing so is intractable in our setting (Figure 2) Instead, must solve the MILP, using the current network parameters 0=, in order to determine an action. To both encourage exploration and reduce the computational complexity, we select random feasible action with probability (line 8h.
Our algorithm runs this modified DQN training procedure. On top of these key changes accom- modate combinatorial actions, we incorporate standard best practices for DQN (Hessel et al. including double DQN (Van Hasselt al. 2016). prioritized experience replay (Schaul al. 2016
2018
and gradient clipping (Zhang et al. 2020).
Once the Q-network is fully trained, we use this network for planning. At inference time, we solve the MILP once at every timestep. computing the best action to take from current state s using the MILP encoding of the final Q-network (with parameters ()) and the action constraints. In other words, we solve for: max, (ILP 0), depicted in Figure Part 2.
4.2 SMART ACTION GENERATION AND OTHER COMPUTATIONAL ENHANCEMENTS
There are two independent critical computational bottlenecks with integrating neural networks into MILPs. First, solving the MILP at every timestep is necessary for both training and evaluation, but extremely expensive: for the discounted future reward estimate in line [3] we must perform that calculation for every sample in the minibatch at every timestep. For a training instance with E episodes, time horizon H, and minibatches of size M, we have EHH repeated MILP solves. Even modest problem setting of E 1,000, H 20, and M 32 requires prohibitive 640,000 solves of the MILP. Second, Q-learning requires diverse samples of the state and action spaces to learn well, but both the state and action combinatorial.

---

Published as a conference paper at ICLR 2025
Warm starting with off-policy samples We design initialization process, run before the main DQN algorithm (line 2). to help alleviate both of these computational bottlenecks. The main idea is to generate cheap but infomative samples which provide rewards observations for wide diversity of actions, allowing us to warm-start the Q-network much more effectively before training with on-poliey samples. We use three strategies for this process.
First, we initialize the Q-network to approximate the single-step (myopic) expected rewards. This leverages our access a cost-effective simulator for the state transitions and immediate rewards: we can draw a large training set of sampled state-reward pairs from the simulator and fit the Q-network to the immediate reward. Such a simulator is cheap and available, as we are focused here on planning over known MDP. Training with myopic samples provides an informative initialization when we start learning the long-run rewards.
Second, we draw sampled actions according to the implied myopic policy to seed the training process with a set of "reasonable" actions. Specifically, we use the MILP embedding of the Q-network to find the action maximizing the learned approximation of the single-step reward. This allows the method to work out-of-the-box for different settings, without having to explicitly derive a MILP formulation for the optimal myopic action and incur extra expensive computation from repeatedly solving the MILP. We then train the network using temporal difference updates on the sampled actions and rewards to learn their long-term values.
Third, we introduce diversity into the sampled actions with additional random perturbations. One source of diversity is to randomly flip entries of the myopic action (we call this "perturbed myopic"), Another is to randomly sample infeasible actions by. e.g.. starting with the all-ones or all-zeros vector for a and then randomly flipping a small number of entries (isolating the impact of including or knocking-out individual actions). This leverages the property that, in restless bandits, we can simulate valid state transitions even for infeasible actions because the state transitions are defined independently per-arm. Incorporating perturbed and even infeasible actions greatly increases the diversity of potential samples because for some combinatorial constraints may be difficult even find a single feasible solution (and otherwise may be difficult to explore parts of the action space).
Similar issues arise if the per-step feasible action space is relatively small (e.g., if the budget small with B < N). Including examples of infeasible actions provides more diverse training set for the Q-network, encouraging better generalization even to feasible actions.
Variance reduction Throughout, we incorporate two additional strategies to lower variance and improve computational efficiency. First, we directly calculate the expected one-step reward (instcad of using the observed reward after state transition), which reduces variance (line 10). Second, we memoize the solutions to MILPs seen multiple times in between updates to the Q-network. As experience replay with reasonably small buffer size (10,000) we expect to repeated samples, enabling us to store the optimal solution to avoid repeated solves. To avoid stale solves, we discard old samples at the same rate that we update the target network Q.
5 EXPERIMENTS
We evaluate the performance of SEQUOIA on the four CORMAB settings introduced in Sec- tion 3 In the appendix. we provide further details about the domains (Appendix C. basclines (Appendix D). implementation (Appendix and runtime (Appendix G
Baselines To understand the challenge of combinatorial action selection, we perform an ablation of our method and test ITERATIVE DQN, which leverages the Q-network training used by SEQUOIA to maximize future return. We do not give this method access to a MILP solver, so we instead use a greedy heuristic to overcome the combinatorial action selection problem, greedily selecting the next-best action component (that maximizes the Q-value) while there are still feasible actions. Note that this baseline would not be possible before this paper, because on-policy training of the DQN requires the techniques we developed.
To understand the importance of sequential planning in these settings, we consider three myopic baselines. These myopic solution approaches focus maximizing the expected reward from the immediate next state, based on the current state and transition probabilities (with no Q-network or any type of rollout). We implement MYOPIC policy MILP that directly encodes (as linear
7

---

Published as a conference paper at ICLR 2025
(a) Multiple interventions
(b) Scheduling
Average reward (normalized)
No ACTION
RANDOM
SAMPLNG
20
40
100
J = 20
40
100
ITER. MYOPIC
MYOPIC
(c) Capacity constraints
(d) Path constraints
ITER. DQN
3
SEQUOIA
2
J 20
40
100
J 20
40
100
Figure 3: Across all problem settings, SEQUOIA achieves consistently better performance com- pared to existing methods, which do not consider both combinatorial selection and sequential plan- ning. We evaluate with = {20, 40, 100} arms and N {5. 10, 20) workers. The y-axis depicts the average per-timestep reward, normalized to the reward achieved by the RANDOM baseline such that RRANDOM For the path-constrained problem, note that there are no ITER ATIVE MYOPIC or ITERATIVE DQN baselines, as there is no simple iterative approach for selecting valid cycle.
objective) the expected reward of the immediate next state, while using the same MILP solver as SEQUOIA. MYOPIC would be optimal in static (non-sequential) setting, but is not necessarily so the sequential contexts we consider here. We also use a SAMPLING approach, which mirrors the method proposed by He et al. (2016), that randomly samples & = 100 actions the up to (N) possible combinatorial actions and picks the action with the largest expected myopic reward. The final myopic baseline is an ITERATIVE MYOPIC solution construction algorithm that greedily selects one feasible component build up the full action, similar to ITERATIVE DQN, but using the best single-step reward instead of the predicted Q-value.
Lower bounds performance action, and No ACTION which always takes the null action a = O. We are not aware of additional RL algorithms from the literature that could be applied CORMAB: this is due the large combi- natorial action space, For instance, many algorithms in the RLlib library (Liang et al. 2018 support discrete actions, but not combinatorial ones.
benchmarked by RANDOM which randomly samples feasible
Experiment setup For each problem instance, we randomly generate transition probabilities, con- straints, and initial states. We ensure consistency by enforcing, across all algorithms, that transi- tion dynamics and initial states across every problem instance (across every episode) are consistent across all methods. We evaluate the expected reward of each algorithm across 50 episodes of length H = 20 and average results over 30 random seeds. We use Gurobi to solve the MILP, in which we embed a two-layer neural network with ReLU activations. Runtime analysis and implementation details, including hyperparameters, are in Appendix
Results SEQUOIA achieves consistently strong performance over the MYOPIC baseline, demon- strating the importance of accounting for long-run return, even in relatively simple MDP settings such restless bandits. Additionally, note that the MYOPIC approach can only be implemented in settings with simple (e.g., linear quadratic) constraints and objectives that can be handled by an integer programming solver, whereas SEQUOIA can learn arbitrary objective functions.
To better understand the challenging combinatorial structure of the problem, we look at the iter- ative baselines which achieve significantly lower performance. Even in the capacity-constrained setting where it performs best, the ITERATIVE DQN approach performs on average 12.1% lower than our non-iterative SEQUOIA an important takeaway, given that many heuristic approaches for overcoming combinatorial action structure rely iterative construction heuristics (Dai et al., 2017] Barrett et al.) 2020). The SAMPLING heuristic comes close to MYOPIC with 20 arms, but dramatically falls behind at 100 arms unsurpriin,,, as the action space jumps many orders of mag-
8

---

Published as a conference paper at ICLR 2025
nitude from roughly (a) 15,504 actions to (20) = 5.4 x 1020 (without considering feasibility constraints). This result underscores the challenge of effectively exploring combinatorially large action spaces.
To show generality and robustness of SEQUOIA, we used the same network architecture and train- ing procedure for all of the different problem settings. Our method works well even without per- domain hyperparameter tuning, which would improve performance further, especially in scaling to larger and more complex problem structures.
6 RELATED WORK
Restless multi-armed bandits RMABS generalize multi-armed bandits by introducing arm states that transition depending on whether the arm is acted on. Even when transition probabilities are fully known, computing an optimal RMAB policy is PSPACE-hard ASPAACE-aard(Paaadiiiir
(Papadimitriou & Tsitsiklis 1994) due
to the combinatorial state and action space. Heuristic approaches to solve RMABs center around the Whittle index policy (Whittle 1988, Weber & Weiss 1990) which uses Lagrangian relaxation to exploit the fact that the arms are weakly coupled (Adelman & Mersereau, 2008
Hawkins 2003).
These relaxations break down in strongly coupled action settings (Ou et al. 2022). our setting here.
Many other solution approaches for RMAB problems are variants of the Whittle index policy, in- cluding deep learning to estimate the Whittle index by training separate network for each arm (Nakhlch et al. 2021); tabular Q-learning (Avrachenkov & Borkar (0022;; and explicitly encoding the Bellman update MIP to overcome uncertainty in transition probabilities (Wang al. 2023). One recent work considers rewards that are not separable across arms, using Monte Carlo tree search to explore combinations (Raman al. 2024), but the action space is still determined by sim- ple budget constraint. Here, we introduce the first solution approach for restless bandits integrating both deep learning and mathematical programming.
RL for combinatorial optimization An iterative heuristic solve static combinatorial opti- mization problem can be represented as a Markov decision process. RL can then be used to obtain good policy for constructing a feasible solution. By "static", we mean deterministic problems that are fully specified. This iterative approach have been used by Dai et al. () Barrett et al. (2020). and Grinsztajn et al. (2023); see Mazyavkina et al. (202T) for a more complete survey and Berto et al. (2024) for benchmark problems. The action space in such approaches is not combinatorial: to construct a solution to a traveling salesperson problem, one needs to select the single next node to visit in every timestep of the decision process. Breaking with this approach, Delarue al. (2020) consider combinatorial actions in a capacitated vehicle routing problem, where at every timestep of the decision process a subset of nodes that form tour and respect the vehicle's capacity constraint must be selected. This combinatorial action selection problem is formulated as a MIP whose ob- jective function is the Q-value estimated by ReLU neural network. However, their setting is simpler, as they consider a single-shot decision that is deterministic, rather than traditional RI. prob- lems which are inherently both stochastic and sequential, such as those that can be represented as an MDP. Additionally, Tang et al. (2020) leverage deep RL for general integer programming solvers to adaptively select cuts, where the action space is the set of all possible Gomory's cutting planes; their approach for addressing the large action space is to sample from the set of feasible cuts according to a specified weighting.
RL with combinatorial actions In the RL literature, is fairly common to deal with combina- torial state spaces, but combinatorial action spaces have received far less attention. A key early example is AlphaGo (Silver et al.] 2016),, which used deep RL to estimate the probability of win- ning with each move, combined with Monte Carlo tree search (MCTS) to explore the combinatorial rollout. Feng et al. (2020) apply MCTS and deep RL to deterministic planning, solving 2D puzzles in deterministic setting.
Dulac-Arnole et al. (2015) deal with large discrete (but not combinatorial) action spaces. Their action selection strategy is sublinear in the number of actions, but this is still prohibitive when the
number of actions is exponential as in our setting. [He et al. (2016) consider simply sampling a
fixed number of actions from the (N) combinatorial action space. Tkachuk et al. (203)) provide theoretical analysis of RL with combinatorial actions when the value function approximation is

---

Published as a conference paper at ICLR 2025
linear in the nonlinear, we opt for neural network function approximations, which are beyond the scope of the aforementioned theory. Brantley et al. (2020) propose an algorithm for budget-constrainee contin- uous action spaces in a tabular RL setting. However, our state spaces are also combinatorial (in addition to discrete action space), making tabular state representation impossible. [Song al.. (2019) propose to split up combinatorial action selection into iterative con-combinatorial selections; an iterative policy must be learned for this purpose. In contrast, and similar to TKkahuuk et al. (2023), we access an optimization solver to find feasible combinatorial actions at each timestep, removing the need for any iterative decomposition of the combinatorial selection as the latter requires learning an additional policy.
pair. Because the reward functions in many practical applications may be
Embedding neural networks in optimization models There has been considerable interest in embedding trained neural networks into larger mathematical optimization models; see |Huchette et al.] (2023) for a survey. Two primary use cases are (1) adversarial machine learning problems, such as finding perturbations of an input that worsen the prediction maximally (Fischetti & Jo 2018) or verifying network robustness (Tjeng et al. (018); (2) replacing a function that is difficult to describe analytically with neural network approximation and then optimizing some decision variables over the approximation (Lombardi & Milano 2018). As feed-forward neural networks with ReLU activations are piecewise-lined functions their inputs, they can be represented using
a polynomial-sizz MILP (Fischetti & Jo. 2018 Anderson et al. 2020 Ceccon et al. 2022
7 CONCLUSION
Much recent work has focused on for combinatorial optimization, but here we address RL with combinatorial optimization in the action space. Specifically, we consider offline planning for restless multi-armed bandits where combinatorial action constraints prevent decoupling the problem.
We design our experimental settings around restless bandits because they are an increasingly com- mon planning formulation that requires optimizing for long-term reward in a sequential setting over a discrete, combinatorial action space. However, our method is a general approach for stochastic planning with per-timestep combinatorial actions, provided that the feasible set of actions can be de- scribed as an MDP. In particular, our use of model-free RL (via DQN) enables direct adaptation to a wide range of planning problems. Extending SEQUOIA to broader RL planning problems beyond restless bandits would benefit from more efficient methods to explore the large set of state vate-action transitions, as well as more structured learning methods, such as graph neural networks or other specialized architectures to capture characteristics of the problem setting.
We explored connections the literature of (stochastic) Al planning, as exemplified by the modeling framework RDDL (Sanner 2011: Taitler et al. (202)). RDDL is a powerful language for expressing sequential planning problems with known transition dynamics. Of the two direct (i.c., non-RL) solution methods there, the JAX-based gradient ascent method (Gimelfarb et al. 2024) struggles to deal with complex constraints and discrete variables, and the Gurobi-based planner cannot handle stochasticity. However, furthering the connection between the RL-based SEQUOIA and the AI planning perspective is likely to be fruitful.
Another line of exploration deals with further reducing the reliance on potentially expensive calls to MILP solver. Solving the MILP, both in training the Q-network (Algorithm [ line (3) and at inference time, is the major computational bottleneck. We use Gurobi to solve the MILP, which uses branch-and-bould
to progressively add linear constraints to a continuous relaxation of the problem, but every call to a MILP solver is relatively expensive. We therefore considered solving a continuous nonlinear relaxation of the action selection problem for a faster heuristic approach. We solve these relaxed problems using IPOPT (Wächter & Biegler 2006), state-of-the-ar nonlinear optimization algorithm that produces stationary continuous action vectors. After a solution has been found, we sample discrete, binary solutions by flipping biased coins parameterized by the IPOPT solution values. On the capacity-constrained CORMAB, this heuristic approach finds significantly better actions than Gurobi, if we allot the same amount of time to each solver. Real-time applications in which decisions must be made instantaneously or in which the number of actions is very large can benefit from this and similar ideas.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGMENTS
Xu acknowledges funding from a Google PhD fellowship and Siebel Scholars. Wilder acknowledges the AI Research Institutes Program funded by the National Science Foundation under Al Institute for Societal Decision Making (AI-SDM), Award No. 2229881. Khalil acknowledges support from the NSERC Discovery Grant program and the SCALE AI Research Chair program.
REFERENCES
Daniel Adelman and Adam J Mersereau. Relaxations weakly coupled stochastic dynamic pro- grams. Operations Research, 56(3):712-777, 2008
Ross Anderson, Joey Huchette, Will Ma, Christian Tjandraatmadja, and Juan Pablo Vielma. Strong mixed-integer programming formulations for trained neural networks. Mathematical Program- ming, 183(1-2):3-39, 2020.
Konstantin E Avrachenkov and Vivek Borkar. Whittle index based Q-learning for restless bandits with average reward. Automatica, 139:110186 2022.
Thomas Barrett, William Clements, Jakob Foerster, and Alex Lvovsky. Exploratory combinatorial optimization with reinforcement learning. In AAAI Conference on Artificial Intelligence (AAAI), pp.
2020.
Federico Berto, Chuanbo Hua, Junyoung Park, Laurin Luttmann, Yining Ma, Fanchen Bu, Jiarui Wang, Haoran Ye, Minsu Kim, Sanghyeok Choi, Nayeli Gast Zepeda, André Hottung, Jianan Zhou, Jieyi Bi, Yu Hu, Fei Liu, Hyeonah Kim, Jiwoo Son, Haeyeon Kim, Davide Angioni, Wouter Kool, Zhiguang Cao, Jie Zhang, Kijung Shin, Cathy Wu, Sungsoo Ahn, Guojie Song, Changhyun Kwon, Lin Xie, and Jinkyoo Park. RL4CO: an extensive reinforcement learning for combinatorial optimization benchmark. arXiv preprint arXiv:2:06.17100) 2024.
https: /ggttttth//uu com/
si4co/r14cm
Albert Bou, Matteo Bettini, Sebastian Dittert, Vikash Kumar, Shagun Sodhani, Xiaomeng Yang, Gianni Fabritiis, and Vincent Moens. TorchRL: data-driven decision-making library for PyTorch. In International Conference on Learning Representations (ICLR), 2024.
Kianté Brantley, Miro Dudik, Thodoris Lykouris, Sobhan Miryoosefi, Max Simchowitz, Aleksandrs Slivkins, and Wen Sun. Constrained episodic reinforcement learning concave-convex and knap- sack settings. Advances in Neural Information Processing Systems (NeurIPS), 33: 33:16315-16326, 2020.
Francesco Ceccon, Jordan Jalving, Joshua Haddad, Alexander Thebelt, Calvin Tsay, Carl D Laird, and Ruth Misener. OMLT: Optimization & machine learning toolkit. Journal of Machine Learn- ing Research (JMLR), 23(1):15829-1588 2022.
Hanjun Dai, Elias Khalil, Yuyu Zhang, Bistra Dilkina, and Le Song. Learning combinatorial opti- mization algorithms over graphs. Advances in Neural Information Processing Systems (NeurIPS), 30, 2017.
Jonas Degrave, Federico Felici, Jonas Buchli, Michael Neunert, Brendan Tracey, Francesco Carpanese, Timo Ewalds, Roland Hafner, Abbas Abdolmaleki, Diego de Las Casas, et al. Mag- netic control of tokamak plasmas through deep reinforcement learning. Nature, 602(7897):414- 419, 2022.
Arthur Delarue, Ross Anderson, and Christian Tjandraatmadja. Reinforcement learning with com- binatorial actions: An application to vehicle routing. Advances in Neural Information Processing Systems (NeurIPS), 33:609-620. 620, 2020.
Gabriel Dulac-Amold, Richard Evans, Hado Hasselt, Peter Sunehag, Timothy Lillicrap, Jonathan Hunt, Timothy Mann, Theophane Weber, Thomas Degris, and Ben Coppin. Deep rein- forcement learning in large discrete action spaces. arXiv preprint arXiv: 15/2,07679 2015.
11

---

Published as a conference paper at ICLR 2025
Gabriel Dulac-Amold, Nir Levine, Daniel J Mankowitz, Jerry Li, Cosmin Paduraru, Sven Gowal, and Todd Hester. An empirical investigation of the challenges of real-world reinforcement learn- ing. arXiv preprint arXiv:2003.11881, 2020.
Justin Dumouchelle, Rahul Patel, Elias B Khalil, and Merve Bodur. Neur2SP: Neural two-stage stochastic programming. Advances in Neural Information Processing Systems (NeurIPS), 35,
2022.
Dieqiao Feng, Carla Gomes, and Bart Selman. Solving hard Al planning instances using curriculum-drig deep reinforcement learning. In International Joint Conference on Artificial Intelligence (IJCAI), 2020.
Matteo Fischetti and Jason Jo. Deep neural networks and mixed integer linear optimization. Con- straints, 23(3):296-300 30000630002000 2018.
Michael Gimelfarb, Ayal Taitler, and Scott Sanner. JaxPlan and GurobiPlan: Optimization baselines for replanning in discrete and mixed discrete-continuous probabilistic domains. International Conference on Automated Planning and Scheduling (ICAPS), 34:230 23822880022222 2024.
Nathan Grinsztajn. Daniel Blanno, Shikha Surana, Clément Bonnet, and Tom Barrett. Win- ner takes it all: Training performant RL populations for combinatorial optimization. Advances in Neural Information Processing Systems (NeurIPS), 36:48485 48509, 2023.
Jeffrey Thomas Hawkins, A Langrangian decomposition approach to weakly coupled dynamic opti- mization problems and its applications. PhD thesis, Massachusetts Institute of Technology, 2003.
He, Mari Ostendorf, Xiaodong He, Jianshu Chen, Jianfeng Gao, Lihong Li, and Li Deng, Deep reinforcement learning with combinatorial action space for predicting popular Reddit threads. Empirical Methods Natural Language Processing (EMNLP), 2016.
Matteo Hessel, Joseph Modayil, Hado Van Hasselt, Tom Schaul, Georg Ostrovski, Will Dabney, Dan Horgan, Bilal Piot, Mohammad Azar, and David Silver. Rainbow: Combining improvements in deep reinforcement learning. In AAAI Conference Artificial Intelligence (AAAI), 2018.
Joey Huchette, Gonzalo Muñoz, Thiago Serra, and Calvin Tsay. When deep learning meets polyhe- dral theory: A survey, arXiv preprint wwXiv:2305.002441 2023.
Yannick Kergosien, Christophe Lenté, and lean-Charles Billaut. Home health care problem: extended multiple traveling salesman problem. In Multidisciplinary International Scheduling Conference: Theory and Applications (MISTA), 2009.
David T Levy, Joseph E Bauer, and Hye-ryeon Lee. Simulation modeling and tobacco control: creating more robust public health policies. American Journal of Public Health, 96(3):494-498, 2006.
Eric Liang. Richard Liaw, Robert Nishihara, Philipp Moritz, Roy Fox, Ken Goldberg, Joseph Gon- zalez, Michael Jordan, and Ion Stoica. RLlib: Abstractions for distributed reinforcement learning. In International Conference on Machine Learning (ICML), pp. 3053-3060 PMLR, 2018.
Michele Lombardi and Michela Milano. Boosting combinatorial problem modeling with machine learning. In International Joint Conference on Artificial Intelligence (IJCAI), pp. 5472-5478, 2018.
Antoine Marot, Benjamin Donnot, Gabriel Dulac-Arnold, Adrian Kelly, Aidan O'Sullivan, Jan Viebahn, Mariette Awad, Isabelle Guyon, Patrick Panciatici, and Camilo Romero. Learning to run a power network challenge: a retrospective analysis. In NeurIPS 2020 Competition and Demon- stration Track, pp. 112-132. PMLR, 2021.
Aditya Mate, Lovish Madaan, Aparna Taneja, Neha Madhiwalla, Shresth Verma, Gargi Singh, Apama Hegde, Pradeep Varakantham, and Milind Tambe. Field study in deploying restless multi- armed bandits: Assisting non non-profits in improving maternal and child health. In AAAI Conference Artificial Intelligence (AAAI), 2022.
12

---

Published as a conference paper at ICLR 2025
Nina Mazyavkina, Sergey Sviridov, Sergei Ivanov, and Evgeny Burneev. Reinforcement learning for combinatorial optimization: A survey. Computers & Operations Research, 134:105400, 2021.
Volodymyr Mnih. Playing Atari with deep reinforcement learning. NeurlPS Deep Learning Work- shop, 2013.
Khaled Nakhleh, Santosh Ganji. Ping- Chun Hsich, Hou, Srinivas Shakkottai, et al. NeurWIN: Neural Whittle index network for restless bandits via deep RL. Advances in Neural Information Processing Systems (NewrIPS), 14:828-839, 2021.
José Niña Markovian restless bandits and index policies: A review. Mathematics, 11(7):
1639, 2023.
Han- -hinnChin Ou, Christoph Siebenbrunner, Jackson Killian, Meredith B Brooks, David Kempe, Yev- geniy Vorobeychik, and Milind Tambe. Networked restless multi-armed bandits for mobile inter- ventions. In International Conference on Autonomous Agents and Multiagent Systems (AAMAS), 2022.
Lale Özbakir, Adil Baykasoğlu, and Pinar Tapkan. Bees algorithm for generalized assignment prob- lem. Applied Mathematics and Computation, 215(11):3882-3795 2010.
Christos H Papadimitriou and John N Tsitsiklis. The complexity of optimal queueing network control. In JEEE Annual Conference on Structure in Complexity Theory, pp. 318-322. IEEE, 1994.
Naveen Raman, Ryan Shi, and Fei Fang. Global rewards in restless multi-armed bandits. In Ad- vances Neural Information Processing Systems (NeurIPS), 2024.
Scott Sanner. Relational dynamic influence diagram language (RDDL): Language description. ICAPS International Probabilistic Planning Competition (IPPC), 2011.
Tom Schaul, John Quan, loannis Antonoglou, and David Silver. Prioritized experience replay. In International Conference Learning Representations (ICLR), 2016.
Grant Schoenebeck and Biaoshuai Tao. Beyond worst-case (in)approximability of nonsubmodular influence maximization. ACM Transactions on Computation Theory (TOCT), 11(3):1-56, 2019.
Thiago Serra, Christian Tjandraatmadja, and Srikumar Ramalingam. Bounding and counting linear regions of deep neural networks. International Conference on Machine Learning (ICML), pp. 4558 4566. PMLR. 2018.
David Silver, Aja Huang, Chris Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche, Julian Schrittwieser, Ioannis Antonoglou, Veda Panneershelvam, Mare Lanctot, al. Mastering the game of Go with deep neural networks and tree search. Nature, 529(7587):844488, 2016.
Danicle Silvestro, Stefano Goria, Thomas Sterner, and Alexandre Antonelli. Improving biodiversity protection through artificial intelligence. Nature Sustainability, 5(5):415-424, 2022.
Hyungseok Song, Hyeryung Jang, Hai H Tran, Se-eun Yoon, Kyunghwan Son, Donggyu Yun, Hyoju Chung, and Yung Yi. Solving continual combinatorial selection via deep reinforcement learning. In International Joint Conference on Artificial Intelligence (IJCAI), 2019.
Ayal Taitler, Michael Gimelfarb, Jihwan Jeong, Sriram Gopalakrishnan, Martin Mladenov, Xiaotian Liu, and Scott Sanner. PpyRDDLGye From RDDL to Gym environments. In ICAPS workshop on Bridging the Gap Between Al Planning and Reinforcement Learning (PRL), 2023.
Yunhao Tang, Shipra Agrawal, and Yuri Faenza. Reinforcement learning for integer programming: Learning to cut. In International Conference on Machine Learning (ICML), 2020.
Vincent Tjeng, Kai Y Xiao, and Russ Tedrake. Evaluating robustness of neural networks with mixed integer programming. In International Conference Learning Representations (ICLR), 2018.
13

---

Published as a conference paper at ICLR 2025
Volodymyr Tkachuk, Seyed Alireza Bakhtiari, Johannes Kirschner, Matej Jusup, Iljja Bogunovic, and Csaba Szepesvári. Efficient planning in combinatorial action spaces with applications to cooperative multi-agent reinforeement learning. In International Conference on Artificial Intelli- gence and Statistics (AISTATS), 2023.
Neythen Treloar, Alex JH Fedorec, Brian Ingalls, and Chris Barnes. Deep reinforcement learn- ing for the control of microbial co-cultures in bioreactors. PLoS Computational Biology. 16(4): e1007783, 2020.
Hado Van Hasselt, Arthur Guez, and David Silver. Deep reinforcement learning with double Q- learning. AAAI Conference on Artificial Intelligence (AAAI), 2016.
Soffa S Villar, Jack Bowden, and James Wason. Multi-armed bandit models for the optimal design of clinical trials: benefits and challenges. Statistical Science: A Review Journal of the Institute of Mathematical Statistics, 30(2):199, 2015.
Andreas Wächter and Lorenz T Biegler. On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming. Mathematical Programming, 106:25-57, 2006.
Kai Wang, Lily Xu, Aparna Taneja, and Milind Tambe. Optimistic Whittle index policy: Online learning for restless bandits. In AAAI Conference Artificial Intelligence (AAAI), 2023.
Richard R Weber and Gideon Weiss. On an index policy for restless bandits. Journal of Applied Probability, 2773)6637-648, 1990.
Peter Whittle. Restless bandits: Activity allocation in a changing world. Journal of Applied Proba- bility, 258A):287-298, 1988.
Jingzhao Zhang, Tianxing He, Suvrit Sra, and Ali Jadbabaie. Why gradient clipping accelerates training: A theoretical justification for adaptivity. International Conference Learning Repre- sentations (ICLR), 2020.
14

---

Published as a conference paper at ICLR 2025
A
NOTATION TABLE
List of symbols used in the paper and their description.
Table I: Symbols used in the paper.
Symbol
Description
Problem description
Sj S
state of arm E [J]
0 A
action taken on arm j
P5 84)
probability that arm j in state 5j transitions to state sf under action dj
(3(3))
reward at time for arm j in state $j reward for restless bandit instance with joint state s
(s)
B
budget
H
time horizon joint state of all arms joint action of all arms feasible action space, as determined by set of constraints joint transition probability across all arms Q-value for action a under state s value function for state s discount factor number of episodes minibatch size
S
ae A
C A*
px
Q(s a)
V(s)
E
M
Notation for SEQUOIA algorithm
ppsilon-greedy parameter
D
dataset of historical trajectories stored in replay memory
Q-network
Q-network neural network parameters
Q
target Q-network
0-
target Q-network neural network parameters
F
target Q-network update frequency
Problem-specitty symbols
E+
decision variables used in MIP (where * denotes indices)
N
action dimension (e.g., number of workers for sspacity-constraine [multi-interventiion]] link function
[multi-intervvnntion] weights of edges for probability transition function
Imulti-interventionn & capacity] cost of action [capacity] budget constraint for worker [scheduling) number of timeslots in schedule [scheduling] matrix denoting whether worker is available at slot [scheduling] matrix denoting whether arm is available at slot & [routing] set of vertices in graph [routing] set of edges in graph [routing] source node for network flow problem [routing] network flow from node j to A at step & [routing] max path length
K
Wa
Ajk
3
15

---

Published as a conference paper at ICLR 2025
B SIMULATION DETAILS
B.1 THE NEED FOR SEQUENTIAL PLANNING IN RMABS
Myopic policies can perform arbitrarily badly in restless bandits. In Figure 4 we offer a clear example through restless bandit with two arms, three states, and budget B = 1. Suppose the probability p of transitioning right one state p when the arm is acted upon and p otherwise (in which case the arm will move leftward). the arms begin state g( (0,0), 0), the myopic policy would always act on arm 1, whereas the optimal policy would be to repeatedly act on arm Thus in these experiments, we consider multi-stat settings (specifically with S states) to emphasize the sequential aspect of the problem.
Many standard restless bandit problems consider a binary state, binary action setting, The multi-state ([S) > 2) setting enables more realistic modeling of many problems, such as patient engagement or health status.
Reward
Arm1
Arm 2
P
No Random Myopic SEQUOIA
0.1
02
0.2
0.1
10
1 1-p
p
1 P
Figure 4: Even in a simple two-arm problem setting with budget to arbitrarily poor performance in restless bandits. Each arm has three states, with positive reward in each state. Suppose that the probability p of transitioning right one state is = 1 when the arm is acted on and p 0 otherwise. This problem instance leads to the rewards on the right, where the gap between myopic and SEQUOIA can be arbitrarily large depending on the rewards at the rightmost state. This poor performance results even in this simple problem setting.
1, myopic policy can lead
B.2 BASE MODEL: RESTLESS BANDIT WITH 4 STATES
To evaluate sequential planning algorithm, design simulator that is designed to ensure the myopic policy is non-optimal. Thus across all experimental settings, we consider restless bandit problems with [S] 4 states, where a fraction of the arms are long-run beneficial to act (but myopically non-optimal), and the remainder of the arms are short-run beneficial to act on but my- opically non-optimal. This base restless bandit problem is implemented the MultiStateRie class.
In these four states {0, 1,,, we model that users can only transition between consecutive states in single timestep; for example, they cannot skip from state 1 to state s' = 3. We denote moving up state as s+ and moving down as s For completeness: s max s 1} and s* m3 1}.
The bad arms have the following reward for each of the four states: [0.1, 0...0.5,.000 0.2, rhual where Thad is drawn randomly from (4, 5, 6), and the good arms have reward [0.2, 0.15, 0.1, rgond] where Tgood drawn randomly from (1, 3)..
For the bad arms, the transition probability of moving up state is drawn uniformly at random between [0.0, 0.2], and the probability moving down a state is drawn from [0.7, 0.9).
C DOMAIN DETAILS
C.1 PATH-CONSTRAINED
We encode the constraints of this path-planning problem as flow constraints graph. We allow the maximum path length T to be double the budget, that is, T = 2 B. All arms pulled must fall along the path visited; pull most B arms out of most T visited.
time-unrolled
16

---

Published as a conference paper at ICLR 2025
by Yaghh hold
Foffort notton
Fuddia Mi
CI
Tonal
Latrerr feed
hottin
Cata
Mhsptor Bodl IM!
Gri arr
Grta Rood
High Streef
Barra valtin
Waler
SQUATS
Sunry Buys
Von
Figure 5: Graph used for the path-constrained problem, based on diagram of the London under- ground. Blue represents nodes used for J = 20. Green nodes are added for J = 40, and orange nodes are added for J 100.
We introduce flow variables fa which equal 1 if take the edge from node j to ie the t-th segment of our path and 0 otherwise. Thus for every edge (j, k) in E, we have decision variables faN,t and fa.j for all & (I,...,77 T}. Node E V is the source, where we must begin and end the path. Finally, decision variable a, indicates whether we act on arm j. i.e. we pass through node j.
max () F.a
(7)
Σ
JA.11 =1
ke A KEES
Σ
SKATT= =1
k: DEE
Σ (JA)EE
SI.RA =1
M [T]
Σ kc(kW)EE
SkJJ
E
SiNttI
VjEV,LE
KGAAEE SEA,
aj S Σ
VjEV
1E(T) MiLLMjEE
Σ aj B JEV
fy (0,1} aj E (0.
Vj. k E V, [T) VjEV
Implementation The underlying graph is based real-world network of the London tube, We have that the graph is fully connected. We visualize
where one node is placed at each station T
Maa data is available the Github repo, and comes from http:::://commosswiiiieeeeeee
wi kiki
17

---

Published as a conference paper at ICLR 2025
5 where color the subset of nodes used for the three problem settings = {20, 40, 100). For simplicity, we consider the cost of each edge to be 1, but heterogeneous costs the edges could be easily implemented.
this graph in Figure
Due to the significantly increased complexity of the MILP for this path-constraine problem, due to having the encode the tine-unrolles graph with NJT nodes, take advantage of the decoupled reward structure for this problem in the training process. That is, in the training loop (lines{)an and [3 in Algorithm D we impose only the budget constraint and not the path constraint. This significantly speeds up the training time, as for the setting with J = 20, the MILP is simplified from 800 variables and 213 constraints only 20 variables and constraint. In the setting with J 100, the reduction is even greater. from 14,740 variables and 4,043 constraints to 100 variables and constraint.
Note that for all the problem instances we describe here, with the exception of the multi-action setting, the reward structure is decoupled, each action impacts the transition probability for only single arm. Thus this heuristic training process can be used for all settings which the reward structure can be decoupled.
C.2 SCHEDULING
We have N workers and J/ arms (e.g., patients). Each worker has some set of available timeslots, and each patient has their own set of available timeslots, out of K timeslots. We assign most one worker to one patient for each timeslot, and each patient must be intervened on by two compatible workers. We can intervene at most B patients.
This scheduling problem can be formulated as follows:
max Q(s, a)
(8)
S.I.
Σ ag
B
SE[J]
Σ Tisk 1
Vie [N], EE [K]
JEM
Σ
Tisk 2
Vj [J]
kE(K]
2 0j S
Σ
Tijk
Vj E [J]
NE[N]AEE[K]
2 Tisk
ViE [N]. E [J], e [K]
aj E {0,1}
[ Vi [NT,jE [K]
Tijk E {0,1]
The scheduling constraints are encoded as binary matrices, where Wi and Ajk denote whether resource i (or patient j) is available at timeslot We introduce a decision variable Tisk whenever a worker and patient j are both available at timeslot k. so Zijk exists iff Wa. = Asa 1. Then, Tijk = indicates the assignment of worker i to arm j at timeslot k; and aj indicates whether we "pull" arm j. Each worker can only be assigned once per timeslot.
This problem also generalizes the standard RMAB: each pulling action requires solving a matching problem to assign workers to each action. The standard RMAB problem would correspond to the setting where all workers and all patients are available for all timeslots (for simplicity, there can be just a single timeslot during which all workers and all patients available), and each patient must be intervened on by just one worker. this case, the number of workers simply represents the budget constraint.
Implementation We use K = 5 timeslots in all problem settings. We randomly select 2 timeslots for each arm and 3 timeslots for each worker.
18

---

Published as a conference paper at ICLR 2025
0.6
0.4
Outsue
Ingut
Figure 6: A visualization of sigmoid functions used for the Multiple Interventions setting, where values of a, b, and To are randomly generated. We consider actions with w In this setting, for the arms with reward shown in dashed blue, = 2 would have stronger effect for the first two actions deployed, but their impact would be relatively limited. contrast, for arms with transition probability shown in solid green, the first two actions applied to arm would lead to relatively low transition probability, but the third actions would lead to a significant increase, and in all cases an increase greater than three actions applied any of the blue arms.
C.3 CAPACITY-CONSTRAINNE
have a decision variable zú for all and j. indicating whether worker gets assigned to arm j.
((s,a)
(9)
s.t.
Σ
Cjtlij
S bi
vi [N]
SE[
aj
Σ
Tíj
Vj E [J]
xE[M]
Bi E {0, 1}
vi E [N], E [J]
aj Zij
Vi E [N], E [J]
0j E 10
Vj E [J]
The standard RMAB setting would correspond single worker (N 1) with budget b, B.
We generate constraints by selecting random costs for each arm (c, E i...... .}} and random capacity for each worker (c, E 72.
Implementation
C.4 MULTIPLE INTERVENTIONS
In the public health literature, these link functions have often been described S-shaped, such in a widely used model of smoking cessation (Levy et al., 2006) The S-shape implies that as individuals are impacted by more actions, they first experience increasing returns their probability of transi- tion to an improved state (the first part of the S) before plateauing as the effect saturates (the second part). While realistic, S-shaped curves are often NP-hard to approximately optimize because they violate the diminishing returns assumptions required for submodular optimization (Schoenebeck & Tao 2019). As we are motivated by public health interventions, we use these as motivating descrip- tions in the descriptions, but these problem structures exist in many other applications. Importantly for public health and other applications, these constraints could be further specified incorporate additional desiderata, such as fairness constraints. For example, if had demographic features associated with each patient, we could encode a requirement to visit at minimum some fraction of each subgroup, such the most elderly.
19

---

Published as a conference paper at ICLR 2025
The sigmoid curve use is of the form:
((x) 1 exp( b. x mZ)
(10)
where values of (0. E [1.4, 2]. and 2o {O...., 10) are randomly generated for each Instantiations of the sigmoid curves we use in the simulation is visualized in Figure
Note that the implemented class here is designed to also adapt to linear link function, which could be a useful model for some problems. The setting with a linear link function would be simpler solve; it would not require solving for combinatorial actions iterative approach would be sufficient.
Implementation We consider N 2- B actions, which only B can be pulled in each timestep. For the purposes of evaluation in this setting, we considered relatively simple setting where each action is connected to up arms. More intricate configurations could benefit from more sophisti- cated learning approaches that incorporate the structure of the problem setting, such as graph neural networks (GNNs).
D BASELINES
D.1 No ACTION BASELINE
At every timestep, the action taken is the null action (a, 0) on every arm.
Since impose the assumption that actions only have positive impact on reward, this baseline serves lower bound on the possible reward in each setting.
D.2 RANDOM BASELINE
At every timestep, we take one random valid action. Thus the action we take at every step is inde- pendent of the current state of the RMAB.
The random actions selected are:
Multiple interventions: Select a random subset (+) of the actions, according to our bud- get.
Randomize the order of workers and arms (patients). For each worker, go through the list of arms and greedily select each one, while that worker has remaining capacity. Continue until either the worker's capacity is exhausted have iterated through all arms.
Capacity constrained:
Randomize the order of workers and patients. Iterate through patient, and find the first two compatible workers that have not yet been assigned, if any exist. If such workers exists, assign those workers to the patient, then continue on the next patient.
Scheduling:
Routing: Generate all the simple random paths within the path constraint T = 2 B, using the s simple.cycles function of the networkx package. Pick one of these paths at random. Then select a random subset (2) of the nodes within that path to act on.
Note that, because are limiting ourselves to all simple paths (no repeating vertices), this approach is weaker than picking at random from among all the valid actions. A stronger approach would require significantly more complexity, finding loop of most length T is by itself an NP-hard problem.
D.3 SAMPLING BASELINE
Sample K random actions (K = 100 by default), evaluate a few rollouts with that action, and select the action that induces the great observed reward.
20

---

Published as a conference paper at ICLR 2025
D.4 MYOPIC BASELINE
Solves the MILP using expected value (based on the true transition probabilities) from the immediate next timestep, without doing any long-term planning. Otherwise, we precisely solve the MILP to get an optimal myopic action.
Multiple interventions: For the MILP myopic solver. we encode the sigmoid curve with a piecewise-lineee approximation, which can be represented as constraint, In the general case, PWLs can approximate continuous functions well and can be directly resolved in Gurob
The other settings use the same MILP as described above, using the expected value of the next immediate timestep using true transition probabilities.
D.5
ITERATIVE MYOPIC BASELINE
Multiple interventions:
Evaluate each action, and pick the action that brings the biggest
increase in reward.
Go through the workers in ascending order of their capacity. For each worker, pick from among the arms that we can afford the that yields the best ratio in terms relative increase in value. Continue until the workers' capacity is lower than the cost of any available arm.
Capacity constrained:
Organize workers by descending order of the number of available slots. For each worker, evaluate the value of adding each arm, if the worker and that arm have compatible timeslot.
Scheduling:
Routing: No computationally efficient solution that iterative; not implemented.
D.6 ITERATIVE DQN
Same as the iterative myopic baseline, but instead of using the expected value of the one-step next state, we use the Q-network estimates to estimate the long-run value.
E EXPERIMENTAL DETAILS
E. DATA GENERATION
Across all experimental settings, the base MDP used to represent each arm is the 4-state MDP described in Appendix B.2 We randomly generate transition probabilities. The constraints the actions are generated for each problem setting as described in Appendix C
F IMPLEMENTATION
Our implementation uses PyTorch and TorchRL (Bou al., 2024) libraries. We build off code from Dumouchelle et al. 2022) to embed a neural network with single-layer ReL.U activations MILP
(Fischetti Jol 2018).
For consistency in results, the random seeds are set between and 30 for the results.
To train the Q-network, we use the hyperparameters specified in Table
G RUNTIME
Experiments are run a cluster running CentOS with Intel(R) Xeon(R) CPU E5-2683 v4 @ 2.1 GHz with 8GB of RAM using Python 3.9.12. The MIP was solved using Gurobi optimizer 10.0.2.
Prancis J. Narcowich notes http:///////////////////////////
zont montimuuus201..pp
https:: /tttps://ww.... gurobi....... wttp://ro.oo.occoeettttttttoooom
html
21

---

Published as a conference paper at ICLR 2025
Table 2: Hyperparameters used in implementation train SEQUOIA
Hyperparameter
Setting
Discount factor y
0.99
Epsilon greedy
0.9 starting; final 0.05; 1000 rate of exponential decay
Learning rate
2.5 x 10
Adam
1.5 10-4
Target update rate
x 10-6
Minibatch size
Replay memory size
10,000
Number of training episodes
100
Network architecture
Two hidden layers of size 32 each
Empirically, we noticed that a major computational bottleneck was the size of the Q-network. Even with only two hidden layers, training network with 128 hidden units took an order of magnitude longer than with 32 hidden units, underlining the tradeoff between expressivity of the Q-network and runtime.
The average running time of the training procedure of SEQUOIA is listed in Table 3
Table 3: Total runtime (in minutes)
20
J 40
100
25.5
76.7
475.2
22


Reviews:
[{"review_id": "AWZXlioQ47", "reviewer": "Reviewer_1mgZ", "summary": "This paper considers the CoRMAB problem, in which there are complex combinatorial arm structures to be learned. Such complexity often arises in many real-world applications such as public health etc. The problem, as far as I can see, is kind of like an intermediate area between traditional bandits where each arm is independent, and that of the more general Markov Decision process where any transition might happen. This paper, however, focuses on the more tractable scenario where some sort of information is known beforehand about the arm dependence structure. In particular, the paper considers four specific scenarios, including multiple interventions, bipartite matching, capacity constrained, and path planning. The paper proposed SEQUOIA, which applies Q-network with mixed-integer linear programming to solve the problem. Experiments demonstrate the effectiveness and efficiency of the proposed algorithm.", "questions": "How does the algorithm in this paper compare to SOTA RL algorithms?\n\nHow to derive theoretical analysis?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "The paper studied a very novel and niche problem that is more tractable than RL but also more practically relevant in real-world bandit applications. I think it's important to have deeper investigations on such problems to directly applying SOTA RL algorithms. One novelty is that the paper combines RL with MILP to solve the problem more effectively.", "weaknesses": "Although the paper studied very interesting bandit problems, but the problem is solved via RL plus MILP. I was curious why not directly apply SOTA RL algorithms? How does that compare to the SEQUOIA proposed in this paper? I think one weakness of the paper is that it didn't compare with more advanced baselines like certain RL algorithms.\n\nAnother major weakness of the paper is that it doesn't have theoretical analysis on the algorithm performance, which is very critical for bandit papers. I would hope the authors provide regret bounds for each of the four cases studied in the paper.", "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": "aDfO34scUb", "reviewer": "Reviewer_oEWh", "summary": "This paper introduces a novel reinforcement learning framework for a challenging setting known as combinatorial restless multi-armed bandits (CoRMAB). In these problems, the vast combinatorial action space presents a key bottleneck, especially for real-world applications like public health. The authors address this by proposing SEQUOIA, a method that combines a Q-network with mixed-integer linear programming (MILP) solvers. Four distinct constraint types (such as capacity and matching constraints) are applied to CoRMAB instances to explore the method's performance. Experimental results show that SEQUOIA significantly outperforms existing baselines across these settings.", "questions": "- Since SEQUOIA’s primary application appears to be in public health, there are concerns about performance during the initial training phase. If the network’s early-stage predictions are suboptimal, this could lead to unacceptable decisions in real-world use. How do the authors envision mitigating this issue in practice, particularly in high-stakes domains like public health where early errors could have critical impacts?", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- The paper highlights meaningful applications, particularly in public health, where combinatorial decision-making is crucial. By focusing on real-world-inspired constraints, the paper emphasizes the practical utility of SEQUOIA.\n- The experimental results suggest that SEQUOIA has a strong advantage over other methods, particularly in scenarios that require both sequential planning and combinatorial action selection. This shows potential for the method to be impactful in complex decision-making tasks.", "weaknesses": "- The four specific CoRMAB instantiations appear somewhat interdependent. For instance, the first instance involving multiple interventions seems to implicitly contain elements of the second (path constraints) and third (capacity constraints). This overlap could obscure the unique contributions of each instance, and the presentation of these distinctions would benefit from clarification. Additionally, a more precise formulation of the optimization goals and constraints in each problem setting could strengthen the paper.\n- Although the SEQUOIA framework is innovative in combining Q-networks with MILP, the method lacks theoretical guarantees, which may reduce its general appeal in theoretical RL circles. The paper leans toward practical applications without rigorously addressing theoretical underpinnings. Given that the CoRMAB problems are motivated by real-world scenarios, it would be beneficial for the authors to demonstrate how SEQUOIA could operate on actual datasets or real-world instances.\n- The method's training demands significant computational resources, as evidenced by Table 3, where training times extend to hours. For online applications, this can be a prohibitive factor. The paper would benefit from a discussion on optimizing computational efficiency or alternative approaches to reduce overhead.", "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": "0DqIIl4fuh", "reviewer": "Reviewer_EMxA", "summary": "This paper addresses a RL problem setting where the action space is combinatorial and discrete, I.e. in which actions are coupled with combinatorial constraints. This work uses the formalism of restless multi-armed bandits to tackle the problem and consider the setting where arms are coupled which leads to a large action space using 4 different examples: multiple interventions, path constraints, bipartite matching and capacity constraints. The proposed approach relies on embedding a Q-network into a mixed integer program fro combinatorial action selection at each time step. The proposed RL algorithm SEQUOIA optimizes for long-term reward over the action space allows to perform sequential planning for a combinatorial action space setting. The performance of the algorithm shows empirical improvement over existing approaches.", "questions": "**Main questions:**\n- How crucial is the assumption of known dynamics and rewards for your approach?  \n- Running time: Table 3 in the appendix shows the total running time depending on the number of arms. What about the number of workers? Is it fixed in this table? \n- Why is step 9 involving an argmax over actions more tractable than given the combinatorial nature of the action space? This is an important point for scalability that is not very clear to me from the presentation. \n- What’s the size of the combinatorial action set in the experiments for each of the 4 examples? Why is it prohibitive for existing RL methods? \n- l. 345 ‘We introduce diversity into the sampled actions with additional random perturbations’. It seems that there is no way to bypass the need to see a sufficient number of diverse actions. I guess this is also an exploration requirement to solve the RL task. If you cannot explore a large number of actions, I guess there is little that can be said about the quality of the obtained policy. \n- Can you further justify the use of DQN? I understand that this is probably the most famous one but since you consider a known transition model, would DDPG make also sense to be tested? \n- Why don’t you compare to the approach you mention in l. 494-498? \n\n\n**Minor questions:**\n- Why do you need a piecewise linear approximation of the sigmoid link function (l. 181) which is known and can be computed?  \n- Any interpretation for including self-loops (l. 196)?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- The 4 example settings provided are compelling for motivating the work. I find the public healthcare example interesting and it is nicely used as a running example. I believe these sequential planning problems are important problems to solve in practice. \n- Writing is clear overall and the presentation with the figures is nice.", "weaknesses": "- The mathematical formulation of the problem is a bit confusing and could be more rigorous: \n(a) Is it an infinite horizon problem (since you seem to be using discounting)? \n(b) l. 99: you mention that your approach enables per-timestep combinatorial action spaces. Where does this flexibility show up in the problem formulation in sec. 2.2. The set C is a fixed combinatorial action vector set. I do not see any time dependence taken into account in the formulation, C also seems to be fixed in Algorithm 1. Usually in RL, action sets are fixed. In your setting, it might be useful to consider time varying ones as the actions that might be available might change because of the coupling of the actions, for instance reducing over times due to the previous actions chosen that limit the remaining possible choices. \n\n- Transition dynamics and rewards are assumed to be known a priori (l. 104). This might be quite limiting regarding the health care motivating example. \n\n- About the comparison to standard DQN (Fig. 2 + l. 243-247): in standard DQN the output size of NN scales with the size of the action space. In your approach, now the input size has to be of the size of the action space (which is exponentially large) to be able to encode any action input from the large combinatorial space you consider. Any comment about this? Why is it more tractable as for the main scaling challenge you want to overcome? \n\n- As discussed in l. 319-323: having to solve an MILP for each sample and for each time step seems extremely expensive. \n\n- Q learning has even been used for continuous actions spaces via appropriate discretization of the action space.  I believe stronger and more convincing arguments have to be made here to support the claims of the paper since this is a crucial point given the motivation of the paper. Could you please elaborate and clarify better what makes your approach scalable compared to prior existing algorithms applied to your combinatorial action space setting? See follow-up question below. \n\n- As discussed in the paper, the idea of embedding a neural network into a mixed-integer problem is not new. Could you elaborate more on the technical challenges faced when following this approach and why does it address the scalability challenge in your problem?\n\nMinor: l. 1028: seems empty for ‘Multiple interventions’, any missing description here?", "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": "lNfTIzGvVV", "reviewer": "Reviewer_ya5G", "summary": "The work introduces a new class of multi armed bandits problem, coRMAB which generalizes Restless bandits problem where the arm action cannot be decoupled because of the constraint of the problem that is common in real world scenarios. The authors also briefly go through the four scenarios with valid examples and propose an algorithm SEQUOIA based on deep RL algorithm – Q learning & mathematical optimization to optimize long-term reward. The authors also highlight the issue with very large action space and showcase the ability of SEQUOIA to perform on those scenarios with experiments comparing them with some of the other algorithms that can handle this problem.", "questions": "1.\tThe problem of coRMAB extends the problem of restless MAB to handle actions that cannot be decoupled. If we were to set the no of actions (N) equal to the no. of arms (J)  and using a simple budget constraint where \\sum j \\in [J] a_j <= B and also making each action only connect to its corres. arm, we end up in restless MAB setting. In that case, How does SEQUOIA handle the Restless bandit problem ?\n\n2.\tFor the case of standard restless bandit problem, how does SEQUOIA competes with some of the existing algorithm in the space of restless bandit problem like restless-UCB [Reference B], which tends to have a sublinear Regret bound with good empirical performance on real-world data too. ? \n\n3.\tAlso, a detailed comparison of the algorithm with other algorithms or approach could help better understand the performance of the developed algorithm. For instance, a comparison of SEQUOIA with other algorithm/ approach on the basis of either Regret/ Normalized Average reward would better help understand the performance gain of the proposed algorithm. ?\n\n4.\tThe metrics used in this paper is normalized average reward. Given that we know the transition dynamics, does comparison against the optimal best policy performance be a better metrics like Regret ? Or Other convergence guarantees like one shown in this paper [Reference A] be better fitted to potentially quantify the significance of this work ?\n\n\n5.\tAlso, solving the large action space problem is computationally hard, however how does the complexity grows if we were to increase the neural network size for a more complex system ?\n\n6.\tAlso, the SEQUOIA uses the same network architecture across all the four constraint type proposed in the paper, Is it optimal or does tunning the hyper-parameter for each constraint provide better performance ?\n\n7.\tHow does SEQUOIA’s result compare to existing domain specific solution for the four-constraint type setting discussed. This would better help SEQUOIA solidify its performance gain with better clarity ? \n\nReference:\nA.\tGuojun Xiong, Jian Li, Finite-Time Analysis of Whittle Index based Q-Learning for Restless Multi-Armed Bandits with Neural Network Function Approximation, Advances in Neural Information Processing Systems 36 (NeurIPS 2023) \nB.\tSiwei Wang, Longbo Huang, John C. S. Lui, Restless-UCB, an efficient and low-complexity algorithm for online restless bandits, Advances in Neural Information Processing Systems (NeurIPS 2020)", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1.\tThe problem setting and formulation are interesting. The formulations discussed in this paper is a natural and general extension of restless bandits. Most of the real-world scenarios often fall under one of the four scenarios highlighted by the authors in this work. \n\n2.\tDeep Q learning type algorithms are generally computationally heavy, and it only grows with the action and state space. This work addresses this issue and takes this into account in their problem formulation and algorithm.  \n\n3.\tA key challenge in using deep learning within a RL problem or any problem in general is the need for optimizing the network architecture and resource for hyper-parameter tunning and the algorithm seems to work with minimal alterations across domains.", "weaknesses": "1.\tThe work highlights the empirical results of the proposed algorithm SEQUOIA but it did not have any theoretical guarantees on measures like Regret or convergence bounds. Having them would have greatly benefitted the solidarity of the developed algorithm.\n\n2.\tThe major results shown in this work is about the experiments and how SEQUOIA, the developed algorithm performs on four scenarios of the problem formulation and competes with some of the other algorithms that can be modified to work on coRMAB, however a detailed experimental design could be carried out to further showcase the benefits and limitations of the proposed algorithm and how they perform in different regimes on different transition dynamics. \n\n3.\tThe work also assumes that it is an offline planning setting, i.e., the transition dynamics are known in advanced which can be a limiting factor on many practical settings where the transition dynamics are harder to compute. Most of the real-world setting involves an agent interacting with an environment to understand them.", "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": "ON4z7eyOVd", "reviewer": "Reviewer_9UJj", "summary": "This paper propose a more general restless bandit model---coRMAB, in which the action space for different arms could also be correlated (e.g., one action can influence multiple arms). In this model, the authors adapt the idea of DQN, and utilize the fact that solving integer programming with a feed-forward neural network programming representation is efficient. They propose the SEQUOIA algorithm, and show that it achieves good performances in experiments.", "questions": "See \"Weaknesses\" for details.\n\n\n======After rebuttal=======\n\nThanks for the reply. I do not have further questions.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- The problem setting is well-motivated.\n\n- I quite like the idea that instead of solving the exact combinatorial optimization, we choose to solve the optimization based on our estimation as an approximate approach. \n\n- From experiments, this idea seems work well.", "weaknesses": "- There are no real data experiments. For a paper that does not contain too much theories, I believe real data experiments are necessary. \n\n- There are some parts that are not very clear to me, e.g., \n\nIn Eq. (2), why there is no $s'$ in RHS?\n\nFor \"Schedule-constrained\", \"Capacity-constrained\", and \"Path-constrained\", are there any formulation about the transitions?\n\nWhy we only consider these four kinds of cdRMAB? I think your algorithm (or solving the MILP) is not restricted to these four settings, right? \n\nIn line 431-432, it is said that \"For example the ITERATIVE myopic approach performs on average 14.6% lower than optimal MYOPIC\". But I do not see that? In Figure 3(b) and 3(c), they are very close, and in Figure 3(a), it seems that ITER.MYOPIC is higher than MYOPIC?", "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)