Global Rewards in Restless Multi-Armed Bandits

Summary

The authors study restless multi-arm bandits where we do not observe separate reward for individual arms and instead observe a global reward which is the sum of reward across arms. They propose Linear and Shapley-Whittle indices, which extend classical Whittle indices (designed for settings where separate reward for individual arms are observed) into the global reward setting and establish approximation bounds. The proposed linear-Whittle policy computes marginal reward for each arm, and the proposed Shapley-Whittle policy computes Shapley values for each arm. To address nonlinear reward functions, the authors propose adaptive policies that takes into account inter-arm interactions. They combine MCTS with Whittle indices to look beyond greedy selection.

Strengths

The authors prove the difficulty of finding solutions to RMABs with global reward through reduction from RAMB and reduction from submodular optimization. They establish performance bounds for index-based policies and include discussions on the takeaways of the bounds. A comprehensive set of policies and baselines are compared in experimental evaluations. Results on both synthetic and real-world data showcase the strength of proposed approaches. The real-world setting nicely motivates the global reward RMAB problem.

Weaknesses

For approximation bounds in section 4.2, the authors briefly describe proof techniques and implications of the results. It would strengthen the paper to elaborate more on technical novelties / contributions in the proofs. The adaptive policies are stronger than pre-computed index-based policies, which have exhibit poor performance due to their inability to consider inter-arm interactions. However, the theoretical results focus on linear and Shapley-Whittle indices.

Questions

Could the theoretical results be modified and applied to adaptive approaches, or have implications in adaptive approaches? If so, it would be nice to have a discussion in the paper. The authors focus on scenarios where the global reward is monotonic and submodular in actions. Such rewards have diminishing returns as extra arms are pulled. Could the authors discuss potential ways to apply/modify proposed approaches to settings where the global reward is not monotonic and submodular in actions? This is mentioned in limitations section, but it could improve the paper to at least point out potential ways to apply proposed methods in more general settings.

Rating

7

Confidence

4

Soundness

4

Presentation

4

Contribution

4

Limitations

The authors discussed the limitations and impact of the work.

Summary

This paper studies RMAB (restless multi-armed bandits) with global rewards. Standard RMAB assumes that the total reward is a sum of the rewards across arms. Even though this type of RMAB incurs curse-of-dimensionality, the linear reward structure allows Whittle index to be defined. In contrast, in this paper the total reward has an additional term that is submodular but non-linear. The authors first propose two linear approximations of the global reward, through which the Whittle policy can then to used. The approximation bounds of the resulting linear-Whittle policy and Shapley-Whittle policy are provided. Since these approximation bounds can be poor, the authors further provide an iterative linear approximation (iterative linear-Whittle policy), although the latter does not have performance guarantees.

Strengths

1. RMAB with global reward has not been studied in the literature. 2. Some approximation guarantees are provided for the Linear-Whittle and Shapley-Linear Whittle policies.

Weaknesses

1. The provable approximation guarantees can be loose (as low as $1/K$, where $K$ is the number of arms), unless the non-linear term is insignificant. 2. The iterative linear-Whittle policy, which is meant to achieve better performance, does not have performance guarantees. 3. The presentation of the iterative linear-Whittle policy could be improved.

Questions

1. What is the significance of Theorem 3? The reviewer is confused because only ensuring that $\hat{a}$ attains a certain fraction of the optimal $Q$-function does not seem to imply that the long-term reward is guaranteed to be lower bounded. Also, it seems that in this theorem the argument of $P_i$ for the state is either 0 or 1. Why are there only two states? 2. In Example 4.1, how do you know that the approximation ratio is 1/2 by only examining one $a$ and $s$. Shouldn't you take the minimum over all $a$ and $s$? 3. The Definition 4 (Iterative Linear-Whittle) is a bit confusing. The iterations were never introduced. It seems that $X$ is the decision from the previous iteration, is that right? It would be better to state the algorithm in a pseudo code with iterations. 4. Similarly, Section 5.3 is difficult to follow. It is unclear to the reader where/how/why Monte Carlo Tree Search is combined with the iterative algorithm in Definition 4.

Rating

6

Confidence

3

Soundness

3

Presentation

2

Contribution

3

Limitations

Limitations are discussed in Section 8.

Summary

Conventional RMAB problems model the rewards with respect to individual arms. Authors claim that for some instances (such as food rescue), a global non-separable reward function exists, because of which solutions to RMAB cannot be applied to such problem. To address this NP-hard problem, authors modify Whittle index policy for linear cases, and propose two adaptive policies for nonlinear cases. Theoretical results (competitive ratio) are provided for modified index policy, and experiments show the performance of proposed algorithms.

Strengths

This work opens a new topic that hasn’t been explored in RMAB, where there is a global utility function. The authors provide theoretical bounds for linear and shapley whittle index policies. The experiment part explores different combinations of policies and reward functions. Both synthetic and real traces are simulated to support the superior of proposed algorithms.

Weaknesses

1. The major weakness I’m thinking of is the model itself. I might need more input from the authors to clarify why RMAB-G is required as a general model, instead of some specific scenario. The authors start with food rescue problems, that the platform wants to maximize the probability of one rescue task completion, while maintaining high engaging levels. This model makes sense to me, but when I’m trying to understand other examples, such as peer review, I cannot find a good explanation for the local arm reward. The state of arm(reviewer) here is if they are available, so what will be the local arm reward? Maximize the availability of the reviewers? The authors have mentioned several other applications for RMAB-G such as blood donation, emergency dispatch, could you clarify how these applications model global and local rewards? Can the authors provide a general requirement for the models that need RMAB-G? 2. I’m also having a hard time understanding some of the global reward settings in section 6.1. More specifically the necessity of global reward function. For example, for linear reward function, if we set the individual reward for each arm as a very naïve m_i s_i a_i + s_i, the solution for maximizing this reward for each arm seems to generate the largest global reward function? The same holds for max global reward, that we can just set the local reward as m_i s_i a_i. 3. Another question that I have is, it seems that MCTS requires local searching, which is a relatively complicated algorithm. Given known transition probabilities, Whittle index can be computed (or approximated), then rest of the algorithm is just looking up the index tables. I understand that proposed algorithms have better reward performance, but what is the time/ complexity sacrifice?

Questions

Please refer to weakness for my major concerns. Some minor questions: 1. Line 84, Shouldn’t it be R(s,a) = R_glob plus \sum R_i instead of times? 2. Line 103, To clarify, Whittle index policy is optimal in asymptotic regime. 3. For experiments, how many time slots (food rescue tasks) are deployed to measure the average reward? Also have you duplicated arms for the experiments, or the proposed algorithms can achieve very close to optimal reward even for 4 different arms? I’m having this question because based on my previous experience with RMABs, Whittle index may perform a bit far from optimal if there is only 1 duplicate for each type of arm. This question also corresponds to previous question that index policies are optimal in asymptotic regime.

Rating

4

Confidence

4

Soundness

3

Presentation

2

Contribution

2

Limitations

My scores are based on the concern of model itself, as well as the necessity of global reward function in some circumstances. If my statement is wrong or inaccurate, I’m willing to adjust the scores accordingly.

Summary

This paper studies the popular Restless Multi-Armed Bandit (RMAB) problem and aims to tackle a key limitation – which is that, in RMABs, the rewards are assumed to be separable across arms. This is a limitation because in many scenarios, the overall reward may not simply be a sum over individual rewards of arms, but these rewards may be tied inextricably with each other. To tackle this issue, the paper proposed the RMAB-G framework with non-separable global rewards. The paper shows hardness results on the RMAB-G problem. Further, the paper proposes index-based policies, similar to the original “whittle index” policy for regular RMABs – the two indexes proposed are the “linear whittle” and the “shapely whittle” indexes. The paper also proves approximation bounds on the performance of these indexes and carries out empirical studies based on synthetic and real-world data to demonstrate the good performance.

Strengths

1. I believe a key strength of the paper is proposing the RMAB-G model with a notion of non-separable global rewards. While RMABs have been extensively studied before, this formulation (and its solution) is novel to the best of my knowledge. 2. THe proposed linear and shapely whittle indexes intuitively make sense. I quite like the concept and augmentations made to the original whittle index to solve the RMAB-G problem. 3. The results presented in the paper are grounded in theory – the paper provides approximation bounds for the proposed solutions. It also proves other minor theoretical results such as hardness of the RMAB-G. 4. Empirical results look good: there are experimental results on both synthetic as well as real-world data.

Weaknesses

1. Motivation: While the new RMAB-G framework and the provided analysis is interesting from a technical pov, the motivation for this setup / application to food rescue seems a little tortured. For instance, in line 66-67, the paper says that global rewards are needed because we cannot split the reward into per-volunteer functions. However, I’m not sure why — isn’t the total reward simply the sum of probabilities of individuals carrying our their assigned rescue tasks? 2. Scalability: My worry is that the proposed solutions may not scale well. The experiments are all run on a small number of arms. Technically, the bottleneck might come from computing the shapely index itself. It seems like an expensive step with a min over exponential number of state vectors. 3. Both the proposed index policies seem to depend on the budget K. Contrary to the regular whittle index, which is budget-agnostic, this seems a little less clean (and also perhaps a hurdle?). Is it possible that if the budget changes from K to K+1, the selected arms may change drastically because all the index values of all arms changed? 4. Some concepts are not introduced in the paper. For instance, indexability, whittle index, etc. are assumed to be common knowledge, potentially making the paper difficult to access for someone not familiar with these concepts.

Questions

1. In line 54, why is whittle index defined as the min w where Q(., 0) > Q(., 1)? As far as I know whittle index is defined as the point where the two Q values become equal? 2. Are the assumptions on the reward functions (monotonic, submodular, etc.) true for the food rescue setting or the blood donation example? 3. Line 86: Is the RHS missing a +? 4. In Theorem 3, what does it mean for the function g(s) to be submodular in s? Why is this a reasonable assumption? 5. In the expression for u(s_i) in line 117, what do factorial terms stand for? 6. In computing the shapely index, how stable is the index wrt K? For example if K were to increase by 1, is it possible that the top-K arms are significantly different from the top-(K+1) arms because all the indices changed? 7. In line 123: why is it true that “this approach could lead to more accurate estimates”? 8. In Theorem 4, in the expression for \beta_{linear}, how is the R(s,a) term determined? 9. In line 230, what is the difference between a trial and a seed? 10. In first paragraph the paper cites maternal health [6] but this paper seems to have nothing to do with maternal health. Perhaps the authors wanted to cite the following: Aditya Mate, Lovish Madaan, Aparna Taneja, Neha Madhiwalla, Shresth Verma, Gargi Singh, Aparna Hegde, Pradeep Varakantham and Milind Tambe. “Field Study in Deploying Restless Multi-Armed Bandits: Assisting Non-Profits in Improving Maternal and Child Health”

Rating

7

Confidence

4

Soundness

4

Presentation

3

Contribution

4

Limitations

yes

Thank you for your response

Thank you for your comment! To answer your question, for brevity, we displayed the minimizing pair of a and s (which are a=[1,1,0,0] and s=[1,1,1,1]), but you are correct in that all pairs a and s should be considered to compute $\beta$. We plan to update our manuscript to further specify and clarify this.