Reinforcement learning with combinatorial actions for coupled restless bandits

Thank you for your positive review! We are glad that you see our paper is well-motivated, and that our approach of solving the exact optimization problem is better than an approximate approach.

Response to Weaknesses/Questions

1. Real data experiments: We agree that it would be preferable to use real data. However, we do not know of publicly available data sources for a restless bandit setting. We hope this changes in the near future!

2. Eq. (2): There is no $s’$ in the RHS because the equation represents the probability of transitioning to a higher-reward state — we have clarified this in the paper.

3. Transition probability formulation: Yes, the transition dynamics for these settings are specified in Appendix B.2.

4. Why 4 settings: We introduced 4 new formulations of coRMAB that we think are practical representations of many real-world settings (with multiple types actions and with path, capacity, schedule constraints).

Of course, our approach is generalizable to any deep RL setting where the actions (either continuous or binary) have constraints that can be formulated as a mixed-integer program. This of course generalizes to a very wide range of problems.

5. Iterative approach: Thank you for catching this typo! This was supposed to read “Iterative DQN” and “SEQUOIA”, not referring to Myopic. We have corrected this.

Thank you for your positive review and suggestions! We are glad you find our problem formulation interesting and realistic to the real-world, and our solution practical for addressing the computational intensity of deep RL.

We will update the paper to reflect the following response.

Response to Questions

1. Handling standard restless bandits: Indeed, our formulation of coRMAB generalizes the standard RMAB. We mention this in lines 175-178, 944, and 971-973 for our formulation of different settings.

2. Comparison to Restless UCB: Restless UCB focuses on a learning problem with unknown transition dynamics, which is a different setting. We agree they make a valuable contribution for learning in RMABs. However, their experiments only scale to $N=5$ arms and requires over $T=50,000$ timesteps to learn — clearly, that is not practical for real-world problem settings.

3. Comparison to other algorithms: Regret would be a useful metric to compare if we are considering a learning setting with unknown transition dynamics. However, here instead we focus on planning with known transition dynamics, where the challenge is overcoming computational complexity, not unknown dynamics.

4. Comparison to the optimal policy: Please see response to Question #3 for why we cannot consider regret.

5. Scalability for larger neural networks: Yes, the complexity does grow as the neural network for DQN grows; we say in lines 291-292 that the MILP requires a linear $O(DP)$ binary variables and constraints where $D$ is the number of hidden layers and $P$ is the number of neurons per layer.

6. Effect of hyperparameter tuning: Our results are shown without hyperparameter tuning. We expect that the empirical performance could improve further with more tuning.

7. Comparison to domain-specific solutions: There are not existing domain-specific solutions for the sequential, combinatorial-action problem we consider, so we cannot compare to them. We introduce the coRMAB problem in this paper.

Response to Weaknesses

1. Theoretical guarantees: Please see response to Question #3 for why we cannot evaluate regret.

For other converge bounds, note that the vast majority of deep RL approaches focus on empirical performance, not on theoretical guarantees. For example, DQN (the deep RL algorithm we use) was introduced in 2015, but the first attempt for a theoretical analysis of DQN was not done until 2020 [5] — and this paper makes extremely simplifying assumptions, such as assuming the data-gathering policy has good coverage (thus requiring minimal exploration) and that the trained neural network is sparse (i.e., mostly 0s).

Our focus is on practical restless combinatorial bandit problems. We have therefore proposed realistic problems and realistic generation schemes.

2. Experimental design: Please see response to Question #7

3. Assumption of an offline planning setting: Restless multi-armed bandits are designed as planning problems; see Whittle [1988] and Weber and Weiss [1990], and restless bandits that assume known dynamics have been applied to several real-world settings; see Raman et al. [2024] for food rescue and Mate et al. [2022] for public health in India.

References

Mate, et al. Field study in deploying restless multi-armed bandits: Assisting non-profits in improving maternal and child health. AAAI 2022

Raman, Shi, and Fang. Global rewards in restless multi-armed bandits. NeurIPS 2024

Whittle. Restless bandits: Activity allocation in a changing world. Journal of Applied Probability 1988

Weber and Weiss. On an index policy for restless bandits. Journal of Applied Probability 1990

Thank you for your review and suggestions! We are happy that you find our work to be compelling and well-presented. We will update the paper to reflect the following response.

Response to Main Questions

1. Assumption of known dynamics: We focus on RL for planning, so we do assume known dynamics and rewards. Restless multi-armed bandits are designed as planning problems; see Whittle [1988] and Weber and Weiss [1990], and restless bandits that assume known dynamics have been applied to several real-world settings; see Raman et al. [2024] for food rescue and Mate et al. [2022] for public health in India.

2. Running time Table 3: In this table we fix the number of workers to $N=10$ (the middle setting in Figure 3).

3. Tractability in combinatorial action space (step 9): Because our action spaces are combinatorial, a DQN-type network with as many outputs as the number of actions is not feasible. In other words, one cannot simply input the state vector into a network and read out Q(s,a) for all possible actions $a$ (top-left in Figure 2). To get around this, we use a network which takes as input a pair $(s,a)$ and estimates $Q(s,a)$ only for that pair. It remains to find the action $a$ which maximizes the output of this network for a fixed state s; this is what MILP solving does.

4. Size of the combinatorial action sets, and why is it prohibitive for RL: For the experiments, with the largest setting ($J=100$ arms and $N=20$ workers) the number of possible actions is $\approx 5.3 \times 10^{20}$; this is clearly prohibitive for existing RL methods.

5. Need for diverse actions: We do need to explore a number of diverse actions, but as we discuss in lines 346–350, we are able to efficiently do so in this setting.

6. Why DQN not DDPG: Given that we have to solve a MIP to evaluate our policy, we chose to use DQN as it is an effective and simple RL approach that requires only a Q-network, whereas DDPG requires both an actor and a critic.

7. Comparison to approach in l.494-498: Tkachuk et al. (2023) assume linear Q-realizability (Assumption 1 in their paper), which requires that the true $Q(s,a)$ can be approximated by a linear function in a feature vector representing the state-action pair $(s,a)$. This is a restrictive assumption which we do not make. Additionally, they assume that the actions are continuous rather than discrete, which they clarify: “​​​​Combined with the linear $Q \pi$-realizability (Assumption 1), the greedy oracle amounts to solving a linear optimization over the action set $A$.’’ This is a much simpler setting than ours that is amenable to theoretical analysis.

Response to Minor Questions

1. Need for PWL approximation of sigmoid: A mixed-integer linear program cannot directly model a continuous non-linear sigmoid function. A piecewise-linear approximation is MILP-representable.

2. Self-loops in path-constrained coRMAB (l. 196): The self-loops ensure that all paths of total length $\leq B$ are valid. If the budget is $B=10$, the reward-maximizing path might be of length $9$ — but without self-loops, a path of length $10$ might not be feasible (because we would have to go to another node and come back, requiring 2 extra edges).

Response to Weaknesses

1. Clarifications on problem formulation: (a) Indeed, this is an infinite-horizon setting; the horizon $H$ is used as the number of timesteps in evaluation. We clarified in the updated submission. (b) By “per-timestep” in l.99, we simply meant that the action space is combinatorial. We agree that SEQUOIA can handle time-varying action spaces by appropriately restricting the available actions per timestep in the MIP model.

2. Transition and rewards assumed to be known: Please see response to Question #1

3. Comparison to standard DQN and combinatorial action space: Precisely as you say, with standard DQN the output size of the NN scales with the size of the action space, which is exponentially large. That is the key contribution of our paper — to directly solve using an NN whose output size is only the dimensionality of the action space.

4. Cost of solving MILP in every timestep / scalability: Selecting an action from a constrained combinatorial set necessitates some form of combinatorial optimization. MILP solving is one generic way of doing so as it can simultaneously represent the trained ReLU Q-network as well as the combinatorial constraints. Optimizing (1) a deep network objective function with (2) binary variables and (3) combinatorial constraints is an extremely challenging problem that does not admit gradient-based methods (e.g., à la projected gradient descent for adversarial attacks) or polynomial-time algorithms. In practice, we impose a time limit to the MILP solver and modify the solver’s parameter settings to prioritize finding feasible solutions quickly over proving global optimality.

5. Q-learning for continuous action spaces: Q-learning has indeed been used for continuous action spaces, but standard Q-learning (or any existing modifications) cannot solve a policy that says: “Find me the best policy that solves an assignment problem (an NP-hard discrete optimization problem) at every timestep.” This is what our work achieves here, to integrate MIP solving into deep RL.

6. Elaboration on challenges embedding a NN into a MIP: Others have shown that neural networks can be embedded into a MIP, but our paper is the first to integrate deep RL (not just deep learning) with MIP solving to enable combinatorial action constraints. Please see our response to Weakness #4 for more detail on the technical challenges.

References

Mate, et al. Field study in deploying restless multi-armed bandits: Assisting non-profits in improving maternal and child health. AAAI 2022

Raman, Shi, and Fang. Global rewards in restless multi-armed bandits. NeurIPS 2024

Whittle. Restless bandits: Activity allocation in a changing world. Journal of Applied Probability 1988 Weber and Weiss. On an index policy for restless bandits. Journal of Applied Probability 1990

Thank you for your response which clarified some of my concerns. I would like to follow-up on the main motivation of the paper and the main challenge to be addressed which is scalability.

One of the main motivations of the paper is to address combinatorial action spaces which bring an important scalability challenge into picture. I have a few follow-up questions for clarification regarding some of the bottlenecks which are also mentioned in the paper:

1. The paper proposes to embed the Q function into an MILP and then solve it to find the maximizing action (in principle). However, embedding (by linearizing large NNs, is this done automatically?) can result in a very large MILP which can quickly become intractable to solve (these are also arguably very hard problems though as mentioned by the authors). In practice these can take days to be solved even for small instances. Moreover, the algorithm has to solve an MILP for each sampled state within each episode. Given the number of samples usually required to train RL, this is huge. I am wondering how do you meaningfully reduce the complexity of the MILPs to be solved (which have among decision variables the huge combinatorial action space). The reported running time in this work for the training is about 1 to a few hours. You mention that you 'impose a time limit to the MILP solver and modify the solver’s parameter settings to prioritize finding feasible solutions quickly over proving global optimality'. So do you still keep the same large combinatorial action space and by just reducing the running time you are able to get a feasible action to the problem, how can you guarantee that you get such an action just by reducing the running time? The paper argues that considering a Q-network with an output of the size of the combinatorial action space is intractable, but now with the proposed approach the max over the Q-network is still intractable and it has to be solved a large number of times. The experiments provide some evidence but could you elaborate more on how you manage to obtain a better result with MILP with a very limited running time that would be better than any random feasible action?

2. The exploration strategy which is also discussed in section 4.2 is based on heuristics. I find it hard to get any meaningful estimates on actions that are never encountered for instance. If all of them are sampled then you also need exponentially many sampled actions which is intractable. How would the values learned for the Q function for specific actions inform or could be extrapolated to unseen actions even intuitively? Otherwise there should be a cost to that in the approximation, does the approach in the paper involve indirectly reducing the number of actions sampled compared to the combinatorial size of the action set? Are you somehow exploiting some problem specific structure that drastically reduces the number of feasible actions in the combinatorial action space?

3. The proposed algorithm outputs a Q function. Does it mean that to find the action to be performed at a given state (i.e. the policy), you have solve an MILP (i.e. for each given state)?

4. Minor: The transition operator is valued in $[0,1]^J$ in Eq. 1. Is this a typo and it should be just [0,1]? What is the meaning of the Bellman equation you provide otherwise?

I understand that this is a hard problem to solve and any meaningful progress is important. I would like to sense better how the central scalability challenge is meaningfully addressed here, could you elaborate more on this matter?

Thank you for your response, I am increasing my score given the importance of the problem and its applications (with the settings highlighted) as well as the effort of the paper to go beyond non-combinatorial action spaces in practice. The paper builds on prior work to embed a neural network into an MILP and uses some heuristics to address the issue of scaling for combinatorial action spaces. I still believe there are a number of issues to be addressed properly in terms of scaling as this is one of the main goals of the paper: solving an MILP for each state sampled seems quite restrictive given the usual number of samples one needs in RL for instance although the method improves over the baselines presented on the instances presented, exploration is handled with some heuristic sampling that does not show the limitation of the proposed method in harder instances, I believe the justifications provided in the rebuttal need to enhance the paper since scalability is the key challenge, the Q-network used has 2 hidden layers of size 32 each which seems quite small to handle large problems with combinatorial action spaces and training a neural network with 128 neurons takes an order of magnitude longer in terms of running time as mentioned in appendix G. Given that the paper is fully practical (and no guarantees are provided), I would expect a more extensive and comprehensive experimental study to support the proposed method (on more instances, larger ones, investigating sensitivity to the parameters ...), its scalability and show its limitations.

Thank you for your review and suggestions! We're happy that you find the applications meaningful and that our method is practical and has potential for impact.

We will update the paper to reflect the following response.

Response to your question (performance during initial training):

Thank you for raising this concern about deployment in high-stakes environments. As discussed in Section 2, the coRMAB setting assumes that the environment is known, i.e., the transition probabilities and reward functions have already been derived. Offline planning is the standard assumption for restless bandits, and has been deployed for important real-world settings including public health in India [1] and clinical trial design [2]. In [1], they build the offline simulator (of the probability of a patient becoming engaged in a health program following a messaging intervention) using domain experts and historical data. As such, training the Q-network using Algorithm 1 is done in simulation, offline. Once satisfactory performance is achieved, the policy can be deployed in the real world.

This offline planning approach is discussed in Section 4.1 “Learning in the Real World” of [3], as a way of addressing online RL’s extensive data needs. Should SEQUOIA be applied to an environment with unknown dynamics, we recommend building a model of the environment dynamics first as discussed in [4], and then applying our Algorithm 1 before finally deploying the Q-network.

Response to the Weaknesses

1. The four coRMAB instantiations: We provide precise formulations of the goals and constraints of all 4 coRMAB problem settings we introduce in full mathematical detail in Appendix C. However, we disagree that these instantiations are all interdependent. For example, for the capacity-constrained setting, each worker $j$ can act on multiple arms (up to their budget $b_j$), but in the schedule-constrained setting, each worker can only act on a single arm — and based on incompatible availability, some workers may not be assigned at all. Whereas for the path-constrained setting, the “number of workers” is not a fixed number $N$, but rather corresponds to the total length of a feasible path. Separately, in the multiple interventions setting, the impact of multiple workers acting on the same arm is cumulative; that is not the case in any of the other settings (i.e., multiple workers acting on arm $j$ is no better than one worker acting on arm $j$).

2. Theoretical guarantees: The vast majority of deep RL approaches focus on empirical performance, rather than on theoretical guarantees. For example, DQN (the deep RL algorithm we use) was introduced in 2015, but the first attempt for a theoretical analysis of DQN was not done until 2020 [5] — and this paper has to make extremely simplifying assumptions to get convergence guarantees, such as assuming the data-gathering policy has good coverage (thus requiring minimal exploration) and that the trained neural network is sparse (i.e., mostly 0s). Other key deep RL algorithms, such as DDPG, PPO, or RAINBOW, do not come with theoretical guarantees.

As you highlight, our focus is on practical restless combinatorial bandit problems. We have therefore proposed realistic problems and realistic generation schemes.

3. Computational runtime: As we mentioned above, SEQUOIA is an offline planning approach. As such, a few hours of training can be seen as a reasonable upfront cost before deployment.

[1] Mate, Madaan, Taneja, et al. “Field study in deploying restless multi- armed bandits: Assisting non-profits in improving maternal and child health.” In AAAI 2022.

[2] Villar, Bowden, 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 2015.

[3] Whittlestone, Arulkumaran, and Crosby. "The societal implications of deep reinforcement learning." JAIR 2021.

[4] Moerland, et al. "Model-based reinforcement learning: A survey." Foundations and Trends in Machine Learning 2023.

[5] Fan, et al. "A theoretical analysis of deep Q-learning." Learning for dynamics and control. PMLR, 2020.

Thank you for your review! We are glad to hear you find our problem interesting, novel, and relevant for real-world applications.

Question: Why no regret bounds, unlike traditional bandit papers?

We would like to clarify the distinction between restless bandits (RMABs) and traditional multi-armed bandits. Our paper considers RMABs, which are typically a planning problem that assume known transition dynamics. The challenge for RMABs is tractably planning over this large, budgeted action space. As you point out, RMABs are a form of Markov decision processes, where each arm of the RMAB is an MDP.

On the other hand, traditional bandits are learning algorithms thus study theoretical guarantees, measured in terms of regret. Regret would be a useful metric to compare if we are considering a learning setting with unknown transition dynamics. However, we focus instead on planning with known transition dynamics, where the challenge is overcoming computational complexity, not learning unknown dynamics.

For other convergence bounds, note that the vast majority of deep RL approaches focus on empirical performance, not on theoretical guarantees. For example, DQN (the deep RL algorithm we use) was introduced in 2015, but the first attempt for a theoretical analysis of DQN was not done until 2020 [Fan et al. 2020] — and this paper makes extremely simplifying assumptions, such as assuming the data-gathering policy has good coverage (thus requiring minimal exploration) and that the trained neural network is sparse (i.e., mostly 0s).

As mentioned in line 487, Tkachuk et al. (2023) recently offered a theoretical analysis of RL with combinatorial actions under some linearity assumptions. While not applicable to our setting, it could serve as a starting point for further theory in the future.

Fan, et al. "A theoretical analysis of deep Q-learning." Learning for dynamics and control. PMLR, 2020.

Tkachuk et al. "Efficient planning in combinatorial action spaces with applications to cooperative multi-agent reinforcement learning." AISTATS 2023.

Question: Comparison to SOTA RL algorithms?

As emphasized in the paper, our action space is both combinatorial and subject to hard constraints. Naively “expanding” all possible actions results in an extremely large discrete action space. In Figure 2, we illustrate how this combinatorial explosion makes the use of existing RL methods impossible.

For example, we show how a “Standard DQN” in the top-left corner would require a Q-network with as many outputs as actions. For our largest setting in the experiments ($J=100$ arms and $N=20$ workers), the number of possible actions is $\approx 5.3 \times 10^{20}$. In addition, not all binary vectors are feasible actions, as they may violate constraints (e.g., path constraints, assignment constraints, budget constraints, etc.). This limits the applicability of SOTA RL methods. Part of our contribution is to show that using MILP within a value-based RL approach can help address both the combinatorial explosion and the presence of hard constraints.

——

Thank you again for your review of our paper; we hope our response addresses your concerns and helps to contextualize our contributions!