Dear Reviewer a47J,

We thank you for your comments and suggestions. These comments will greatly help improve our final manuscript. We appreciate that you find our empirical evaluation comprehensive, and find that our empirical results strengthen the validity of our policies. We are additionally glad that our real-world applications help motivate the RMAB-G problem. We provide answers to each of your questions below:

Novelties + Contributions in Approximation Bounds

We thank the reviewers for inquiring about our proof techniques and the novelties present there. Our key technical insight is a novel method to bound the performance of Linear- and Shapely-Whittle policies using similarities between the global rewards and the rewards of an induced RMAB. Such a technique provides insight into how approximation guarantees can be derived for other variants of RMABs. To quantify the similarity between the rewards of Linear- and Shapley-Whittle and the rewards of the induced RMAB, we use properties of submodular functions to upper bound the reward from Linear- and Shapley-Whittle. We plan to emphasize these contributions more in the camera-ready version of our paper.

Non-Monotonic Rewards

We thank the reviewers for bringing up this interesting question. Following the reviewer's suggestion, we empirically tested our methods with non-monotonic. In the supplemental PDF, we attach a Figure that evaluates the performance of our policies under two non-monotonic rewards. The first reward is the minimum function, where we assume that the minimum of an empty set is 0, and the second is the linear reward, but with negative rewards for some arms. We compare the performance of our policies for both 4 and 10 arms, and evaluate this across 15 seeds.

MCTS Shapley-Whittle performs best for the negative linear reward, which follows the same trend seen for monotonic rewards. Such results follow intuition, as for non-monotonic rewards, the impact of one arm upon the rewards of other arms is more complex, requiring the use of adaptive algorithms. For the minimum function, we find that MCTS-based methods perform best for N=10, while for N=4, we find that our index-based policies perform near-optimally. We believe that a more systematic investigation of non-monotonic rewards poses an interesting direction for future research, and thank the reviewer for bringing this up.

Dear Reviewer t2ns,

We thank you for your suggestions and comments on our paper, and these will greatly help improve our final manuscript. We are glad that you appreciate how RMAB-G has not been previously studied in the literature. Additionally, we are happy that you appreciate the approximation guarantees we provide for our Linear- and Shapley-Whittle policies. We provide answers to each of your questions below:

Looseness of the 1/K Guarantee

We thank the reviewers for bringing this up. While the 1/K guarantee can be loose in some situations, we demonstrate in Lemma 8 that there exist reward functions for which the 1/K guarantee is tight. To provide a tighter guarantee, in Theorems 4 and 5, we provide lower bounds for the performance of Linear- and Shapley-Whittle dependent on the value of $\beta\_{\mathrm{linear}}$ and $\beta\_{\mathrm{shapley}}$ respectively.

Iterative Linear-Whittle Guarantee

We thank you for bringing up this question, as it is an interesting and natural question. Proof techniques used to bound the performance of the Linear- and Shapley-Whittle policies cannot be directly applied to adaptive methods because adaptive methods lack an analog for the "induced linear RMAB" or "induced Shapley RMAB". To get around this limitation, we develop new performance bounds for the iterative Linear-Whittle policy and show that a) in some scenarios, the iterative Linear-Whittle policy achieves no better than $\frac{1}{1+(K-1)\gamma}$ of the optimal average reward, and b) for any choice of reward and transitions, the iterative Linear-Whittle policy achieves at least $\frac{1}{K}$ of the optimal reward. We introduce formal theorem statements and proof sketches in the global rebuttal.

Theorem 3 Significance

We thank the reviewers for bringing up the purpose of Theorem 3. We agree with the reviewer that Theorem 3 does not guarantee the long-term reward is bounded. Theorem 3 demonstrates that it is possible to achieve a 1-1/e approximation to the Q value, which serves as an initial attempt at solving the problem. However, in addition to the algorithm not guaranteeing a long-term bound on the reward, such a method is computationally intractable, as it requires exponential time to learn such a Q function. Theorem 3 motivates the need for computationally feasible algorithms with long-term reward guarantees, as initial reinforcement learning-based solutions fail to solve the problem. We plan to clarify this further in the camera-ready version of our manuscript.

Example 4.1 Approximation Ratio

In Example 4.1, we show that our Linear-Whittle policy achieves a 1/2 approximation. We demonstrate this by first computing an upper bound on the optimal reward; we do so by upper bounding the individual contribution from each arm ($p\_{i}(s\_{i})a\_{i})$), then maximizing this by summing over arms ($\sum\_{i=1}^{N} p\_{i}(s\_{i})a\_{i})$). This allows us to find that $\mathrm{OPT} \leq 6$ . We then compute the arms which are pulled by the Linear-Whittle policy, and find that the reward for this is 3. Therefore, the Linear-Whittle policy achieves at least 1/2 of the optimal reward. We plan to add more details to our analysis in Example 4.1, and include these details in the paper.

Explaining Iterative Linear-Whittle

We thank the reviewers for pointing this out, and the reviewer is correct that $X$ are the decisions from previous iterations. To improve clarity, we plan on including pseudocode in the camera-ready version of the manuscript.

Explaining MCTS with iterative algorithms

We include details on our MCTS algorithm in Algorithm 1 of the Appendix, but plan to incorporate this into the main paper and include further details. At its core, our MCTS algorithm computes a variant of the Linear-Whittle index for different actions. Each node in MCTS represents a partial selection of arms, and children nodes indicate new possible arms to be selected. During a rollout, we select additional arms to pull for the current timestep, and after this, we have a candidate set of arms to pull corresponding to an action $\mathbf{a}$. We can compute the exact global and local reward using this and use index-based approaches to estimate the future reward for the action $\mathbf{a}$. We combine these two values to assess a total reward associated with the action $\mathbf{a}$, and repeat this procedure across different combinations of arms.

Dear Reviewer oZCz,

We thank you for your suggestions and these comments will help improve our final manuscript. We appreciate that you view our work as “opening a new topic” and are glad that you recognize our theoretical bounds. Additionally, we are happy that you appreciated our empirical results and found that they supported our proposed algorithms. We provide answers to each of your questions below:

RMAB-G Model in Peer Review

We thank the authors for bringing up their questions about applying RMAB-G to the peer review setting. If peer review institutions focus exclusively on review quality, then the local reward could be 0. Such a scenario is allowed within our model and all performance guarantees still apply to such a situation. We empirically analyze situations with zero local reward in Appendix I.

Global and Local Rewards in Blood Donation and Emergency Dispatch

The volunteer emergency dispatch situation parallels the food rescue scenario for both the global and local reward. In volunteer emergency dispatch, volunteers are notified about emergencies, to have volunteers assist with an emergency (an example of this can be seen through the app PulsePoint). The global reward is the probability that any volunteer helps out with an emergency, which corresponds to the probability reward. The local reward corresponds to engagement; similar to food rescue, emergency dispatch platforms want to ensure high engagement rates from their volunteers.

In blood donation, the objective is to match blood donors to blood donation opportunities [1]. Local rewards in this situation correspond to the number of active blood donors. Global rewards could refer to the total amount of blood donated weighted by some fairness constraint proportional to the squared difference between rural and non-rural hospitals [1]. Alternatively, there could be other domain-specific considerations that play into the choice of local and global rewards.

General Model Requirements

To apply our proposed algorithms, we require two things of the reward function: a) it is submodular in the arms pulled, meaning that the marginal gain for pulling an arm is diminished as additional arms are pulled simultaneously, and b) it is monotonically increasing in the arms pulled (pulling more arms cannot decrease the reward). Submodular monotonic reward functions are common assumptions for set functions and arise naturally in many situations including explainability [2], reinforcement learning [3], and economics [4].

Global Rewards for Maximization

We thank the reviewer for this question, and plan to include further details on the maximization reward in the paper. We agree with the reviewer that for the linear global reward, naively applying the proposed solution is optimal. However, this is not true for the maximization global reward.

For example, suppose that we have three arms ($N=3$) with a budget of two ($K=2$). Suppose that the global reward is the maximization reward, while the local rewards correspond to whether arms are in state 1: $R\_{i}(s\_{i},a\_{i}) = s\_{i}$. Suppose that $m\_{1} = 5$, while $m\_{2} = 4$ and $m\_{3} = 2$. Finally, suppose that arms 1 and 2 remain in state $s\_{1}=1, s\_{2}=1$, while arm 3 is in state 1 if pulled ($P\_{3}(1,1,1) = 1$). In this scenario, naively maximizing $m\_{i} s\_{i} a\_{i} + s\_{i}$ results in pulling arms 1 and 2, while the optimal set of arms to pull is 1 and 3. Neither pulling arm 2 nor arm 3 provides any benefit to the global reward when arm 1 is already pulled. However, pulling arm 3 improves the local reward more than pulling arm 2, so pulling arms 1 and 3 is optimal. More generally, because the maximum function is non-linear and non-separable, approximating the reward purely linearly can result in poor performance due to overestimation. We demonstrate this empirically in Figure 2, where our Linear-Whittle policy, which estimates the reward in a similar manner, performs worse than our Shapley-Whittle policy, which uses Shapley values to estimate the reward function.

Time Tradeoff for MCTS

We agree with the reviewer that the time complexity of MCTS is an important consideration when deciding which algorithm to use. We agree that MCTS could run slowly due to the effect of local searching; we quantify this in Figure 3, where we plot how the time needed to run MCTS varies with the problem size. In practice, when N<=100, the MCTS-based algorithms can run in under 30 seconds, which is suitable for real-world applications such as food rescue (which require that algorithms run in under 1 minute).

Experimental details for food rescue

We thank the reviewer for this question. We provide details on the number of food rescue slots in Appendix A, and plan to bring this forward into the main paper. For all experiments, we run 50 food rescue trips, and average this across 15 seeds, and 5 trials per seed. We select T=50, because when using the discounted reward, $\gamma^50 < 0.005$, and so the rewards beyond T=50 are relatively small.

Smaller comments

We thank the reviewers for their writing suggestions, and we plan to change the typo on line 84 and correct line 103 so it specifies optimality in the asymptotic regime.

References

[1] McElfresh, Duncan C., et al. "Matching algorithms for blood donation." Proceedings of the 21st ACM Conference on Economics and Computation. 2020.

[2] Chen, Ruoyu, et al. "Less is more: Fewer interpretable region via submodular subset selection." arXiv preprint arXiv:2402.09164 (2024).

[3] Prajapat, Manish, et al. "Submodular reinforcement learning." arXiv preprint arXiv:2307.13372 (2023).

[4] Chateauneuf, Alain, and Bernard Cornet. "Submodular financial markets with frictions." Economic Theory 73.2 (2022): 721-744.

Dear Reviewer TFrk,

We thank you for your suggestions and insights, and your comments will help improve our final manuscript. We are happy that you find our study novel, and find the RMAB-G model to be a key strength of our paper. Additionally, we are glad that you find our policies intuitive and grounded in theory. Finally, we appreciate that you think our empirical results are good, both for synthetic and real-world experiments. We provide answers to each of your questions below:

Motivation for Food Rescue Scenario

We thank the reviewer for bringing up this important question. We note that the probability of any volunteer matching to a rescue trip is not simply the sum of their match probabilities. For example, if there are 2 volunteers, each with a match probability of 1/2, then the probability of any volunteer matching is 3/4, rather than 1/2+1/2 = 1. This is because we compute the probability that no volunteer successfully matches to a trip, which is a nonlinear function of the individual match probabilities.

Scalability of Method

We agree with the reviewer that the scalability of our methods is important to assess the real-world applicability of our methods. In Appendix I and Appendix J, we vary the number of arms between 25 and 1000, and compare the performance of our policies. Index-based policies run quickly because the indices can be pre-computed and Shapley values can also be computed quickly because we estimate Shapley values using a subset of arm combinations. While adaptive policies, such as MCTS, run slower than index-based policies, when N <= 50, both adaptive and index-based policies can be computed in under 15 seconds, which is fast enough for real-world use cases such as food rescue. For large N, we can use index-based methods, which run in under a second per timestep for N=1000.

Impact of Budget on Arms Selected

We thank the reviewer for bringing up an interesting question about how the budget impacts the actions chosen by our index-based policies. For the Linear-Whittle policy, all arms that are selected with a budget of $K$ are selected for a budget of $K+1$ as well (within a particular timestep), because $p\_{i}(s\_{i})$ is independent of the budget. However, for the Shapley-Whittle policy, the impact of the budget on the arms selected is more complicated because $u\_{i}(s\_{i})$ is not independent of the budget. We do not believe that the Shapley-Whittle indices should change drastically when increasing the budget because the Shapley values are computed across many combinations of arms. Intuitively, increasing the budget should change the size of each arm combination, but the average reward of the arm combinations should not change drastically.

Introducing Indexability and Whittle Index

We agree with the reviewer that indexability and the Whittle index are important concepts that can help readers better understand our work. In the camera-ready version of our work, we plan to include additional background on these concepts to make our paper more accessible.

Assumptions for Food Rescue and Blood Donation

We thank the reviewer for bringing up an interesting question about our reward functions in food rescue and blood donation. As mentioned in Section 3, we model the global reward in food rescue using the probability reward function, which is both monotonic and submodular. A similar reward function can be used for the blood donation setting, as notifying donors about donation opportunities can only result in more blood being donated. Additionally, notifying additional donors leads to diminishing returns, due to capacity restrictions on the total amount of blood donated.

Submodular g function

Theorem 3 assumes $g(\mathbf{s})$ is submodular in $\mathbf{s}$. $g(\mathbf{s})$ represents the maximum reward attainable from state $\mathbf{s}$. If $g(\mathbf{s})$ is submodular, then additional arms in the 1 state leads to diminishing marginal returns. Such an assumption holds true across each of the reward functions used in our experiments, and is commonly seen when additional present arms result in diminishing returns. We plan to include a brief discussion of the meaning of the assumptions for Theorem 3.

Better estimates from Shapley-Whittle

We thank the reviewers for pointing this out. On line 123, we state the Shapley-Whittle policy could lead to better estimates of the reward when compared to the Linear-Whittle policy. The Shapley-Whittle policy uses Shapley values to estimate the marginal contribution of each arm, while the Linear-Whittle policy overestimates marginal contributions. As a result, in many cases, the Shapley-Whittle index provides a better estimate of the reward because marginal contributions are averaged across many combinations of arms. This intuition is backed up by empirical evidence, where Shapley-based policies perform better than Linear-based policies. We plan to update our write-up to make this point clearer.

Other Questions

We thank the reviewer for pointing out our typo on Line 86, and we additionally plan to change Line 54 to Q(.,0) = Q(.,1).

On line 117, the factorial terms arise from the original definition of Shapley values; these terms account for the number of orderings of arms for a particular action combination.

For Theorem 4, $R(\mathbf{s},\mathbf{a})$ term can be computed for any given $\mathbf{s}$ and $\mathbf{a}$. $\beta\_{\mathrm{linear}}$ can then be computed by minimizing this ratio across all choices for the action and state.

When we vary the trial, the starting state, \mathbf{s}^{{0)} changes, while the transition matrices, $\mathcal{P}$, and reward parameters remain constant. However, when we change the seed, the starting state, transition matrices, and reward parameters all change.

We thank the reviewer for pointing out our misplaced citation, and we will fix this in the camera-ready.