Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: The paper proposes a method to automatically learn the Whittle Indices for a Restless Multi-Armed Bandit (RMAB) problem. 

Contributions:

The Algorithm: The algorithm tries to learn a neural network that takes as input the state of a given arm and provides as output the whittle index of that state. It does this by showing a connection between the whittle indices for an arm and the indices of an optimal index policy for a family of MDPs (Env(𝝀)) based on that arm’s MDP (Env). It then learns a good index policy for this family of MDPs using a REINFORCE-type method.

Theoretical Justification: Towards substantiating the claim that learning a good policy for Env(𝝀) is equivalent to learning a good whittle index, the paper provides a proof about an epsilon-delta relationship between learning a good policy and a good whittle index.

Empirical Justification: The paper shows that the proposed algorithm works well on 3 previously published RMAB instances, when compared with 1 similar ‘learning a whittle index’-type baseline and 2 reinforcement learning baselines.

main_review: Positives:
1) Interesting idea: There has been a lot of recent interest in trying to automatically calculate the whittle index. However, to my knowledge, the approach outlined in this paper is different from those presented in past/contemporary work. Here, the algorithm tries to learn the whittle indices for an arm by learning a good index policy for a superset of MDPs (Env(𝝀)) in which you have to pay a cost of 𝜆 to choose the ‘active’ action. This is because the indices of such an optimal index policy are equal to the whittle indices (under indexability assumptions), and even if you can’t learn the optimal policy, the paper has a proof that suggests an almost optimal policy leads to almost correct whittle indices. There are lots of good algorithms for solving MDPs and so reducing the whittle index problem to this new one seems like a good idea.

2) Experiments on previously published RMAB instances: Rather than arbitrarily creating RMAB instances, the paper shows the effectiveness of the proposed algorithm on 3 classes of RMABs that have been previously published in the literature and, as a result, are more likely to be relevant to practice. In addition, the experimental results indicate that this method reaches a performance level equal to that of the optimal/SOTA solution.

Negatives:
1) Weak baselines and limited related work: While the experimental domains are great,  I believe that the comparison baselines are quite weak. Importantly, the paper fails to include WIBQL [1], a provably correct Q-Learning based algorithm for automatically learning whittle indices. Although the exact implementation presented in that paper is for the average reward setting and tabular case, there is a fairly straightforward extension that would allow you to learn a neural network-based function approximator for these indices. Even without this, I believe that the RL-based baselines are too weak and instead simpler baselines like decomposing the joint problem into individual problems would work better. (To do this, you’d solve the MDP to get the optimal Q-values for each arm independently, and then choose the M arms with the greatest Q(s[t], active)-Q(s[t], passive).)

2) Weak analysis of limitations:
While the paper acknowledges the fact that strong indexability is important to the performance of this method, it doesn’t test the performance of the method on RMAB instances that aren’t strongly indexable. Instead, it makes the strange claim that, because the 3 chosen instances are strongly indexable, ‘most practical bandits problems are indeed indexable’. The conclusion that I draw from this fact is that ‘people publish papers about RMABs that have nice properties’. It would be useful to see the results of the algorithm on RMAB instances that aren’t indexable.
The paper recognizes that it is important to have a simulator for this algorithm to work (because of its need for on-policy rollouts). However, in defending it, the paper argues that the algorithm still performs well on a slightly worse simulator. While this is a useful experiment in showing the algorithm’s robustness to noise, it does not address the underlying limitation. It would be more interesting if the authors commented on possible offline/off-policy extensions to their proposed algorithm.

3) Proof is nice to have, but there are issues: While it’s useful to have a proof that shows some relationship between the closeness of the indices of a good index policy for Env(𝝀) and the true whittle indices, (a) I don’t understand the statement of the proof, and (b) it’s quite weak. For (a), there are 2 sets of if-then relationships in the statement which make it hard to understand. In addition, it’s not clear how  is related to  and -- for example, for something to be 0.1-accurate, what are the conditions on  and . Also, the statement seems to be a bit different from the normal - definition; wouldn’t the statement always be trivially true for an arbitrarily large ? It would be useful if you could clarify the statement and provide a proof sketch. For (b), the proof doesn’t say anything quantitative. To begin with, it’s not clear how  and  are related, i.e., how close to the optimal whittle indices you’ll get for being within an \epsilon ball of the optimal. Even if it’s small, it’s unlikely that you will ever know what the optimal is and, as a result, how close you are to it. Finally, even if you did know the distance between your estimate of the whittle index and the true index, it’s unclear what impact that would have on the final expected return for the RMAB (across multiple arms).

Other Comments:
1) Paper organisation could be improved.
A proof sketch for Theorem 3 would be nice to have in the main text given that it’s the primary theoretical contribution.
Section 3.3 does not add much value and could be pushed to the appendix in favor of the proof sketch.
The details of the NeurWIN algorithm could be introduced earlier; they’re currently at the end of page 5 (more than half way through the paper).
2) The neural network used is very small (16, 32 dimensional layers). Do things change if you use bigger/smaller neural networks/different architectures?
3) In Figure 6, it seems like NeurWIN does better w.r.t. baselines for the Recovering Bandits and Wireless Scheduling problems when there is a noisy simulator vs. the exact simulator. It’s not clear why that should be the case.
4) There is some contemporaneous work on this problem (cited below) that the authors might find interesting.

Conclusion: The idea is interesting and the experimental results seem to show that the algorithm does its job in practice. As a result, despite a perfunctory limitations section, weak baselines and unclear theoretical contributions, I recommend a weak accept for the paper. I would increase my rating if the authors address the comments about the limitations and include stronger baselines.

Citations:
[1] Avrachenkov, Konstantin, and Vivek S. Borkar. "Whittle index based Q-learning for restless bandits with average reward." arXiv preprint arXiv:2004.14427 (2020).
[2] Biswas, Arpita, et al. "Learn to Intervene: An Adaptive Learning Policy for Restless Bandits in Application to Preventive Healthcare." arXiv preprint arXiv:2105.07965 (2021).

---
EDIT AFTER REBUTTAL: Increased score from 6 to 7 (see response to rebuttal for more details).

limitations_and_societal_impact: Limitations: While the paper does discuss possible limitations of its work, the analysis is not of high quality.

Societal Impact: The paper details an algorithm for a general class of problems. From its description, there doesn’t seem to be any obvious ethical impacts that would be associated with its usage across the broad class of problems. However, those considering employing this algorithm for a specific application should perform an application-specific analysis.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The authors develop a reinforcement learning based method for computing the Whittle Index heuristic policy for solving Restless Bandit problems. This is a novel methodological contribution in the space of restless bandits. Several experimental results are provided demonstrating the good performance and general applicability of the method.
main_review: This paper presents an original algorithm that will be of general interest to researchers in the restless bandits space. Specifically, the authors seem to be the first to use neural-network-based function approximation for learning the Whittle index policy. The paper is relatively well structured and written, though some key concepts are unclear (more comments provided below). The experimental results are comprehensive and the domains tested are strong ones, making their results fairly convincing, with a few minor comments. However, authors also missed a key competitor in related work. I think this work has potential to be a good submission, but I ask for the following clarities.

Major comments:
1. Thm 3 is reasonable in terms of motivating the use of reinforcement learning for finding the Whittle index. However, I feel like what is missing from this paper is a Thm 4 that proves that algorithm 1 is valid/will converge to the proper values of the Whittle index -- I expound on this in the next comment.
I am having some trouble determining the validity of algorithm 1. Perhaps its presentation could be improved. As far as I can tell, a key component of the validity of the algorithm is that the \lambda value is set by the network at the start of each minibatch of training, which itself sets the cost of acting in the environment. If we assume that this method converges, then eventually we would expect that that lambda value would be set to the Whittle index, i.e., the value that makes the planner expect to get exactly 0 reward for following the optimal policy -- and since you are actually charging that \lambda value in the empirical rewards, it seems that the trajectories would also go to 0 in expectation. However, an alternative controller which sets \lambda to 0 and always predicts 0 would always act randomly, but never get charged any cost of acting -- why would a neural network not find the second option preferable if it receives greater reward? This does not seem to be what happens, since the experimental results are convincing. So it would greatly help to have both an intuitive, and really a theoretical justification for why the authors' algorithm converges.

2. Line 251 - 253: "For such scenarios, we consider that there are multiple types of arms and train a separate NeurWIN for each type"
 - it would be nice to see also an experiment where every arm is sampled randomly from some distribution or set of distributions, since the assumption that many arms are exactly the same seems strong and could lead to cases where the Whittle indexes that need to be learned for different arm types have significant numerical separation that makes the precision of the authors' method less important for achieving good performance in the environment. This may increase computational demand, but seems reasonable to run so that we can see experimentally that the authors' method is learning the Whittle indices to a non-trivial precision. 

3. Authors missed an important competitor which proposes a Q-learning algorithm for learning the Whittle index which comes with convergence guarantees (bibtex below). Authors implement and compare against this baseline, as it seems to be the closest competitor to their algorithm. However, since the authors' method is based on deep Q-learning, it is more general than the below competitor that uses tabular Q-learning. However, there is likely overlap in the theory regarding the proof of convergence of the competitor method, and the algorithmic ideas behind NeurWIN that should be elucidated by the authors to properly contextualize the authors' contribution.
 
@article{avrachenkov2020whittle,
  title={Whittle index based Q-learning for restless bandits with average reward},
  author={Avrachenkov, Konstantin and Borkar, Vivek S},
  journal={arXiv preprint arXiv:2004.14427},
  year={2020}
}
 
Medium Comments:
4. Fig 3 - how well does 20-step lookahead perform on (4,1) and (10,1)? Also why does QWIC outperform the lookahead on (4,1) but not (10,1)? 

5. The authors of [17] implement UCB and Thompson-Sampling based algorithms -- it would be helpful to see how NeurWIN compares to these baselines on at least the recovering bandits environment.

6. Line 338- 340: "Fig. 5 shows the function Ds(λ) of five randomly selected states for each of the three applications. This result suggests that most practical bandit problems are indeed strongly indexable.”
"Most" is far too strong a claim based off the N=3 experimental domains given as evidence. This evidence is at best a proof of concept. A far more principled investigation of what it means to be (and not to be) strongly indexable in terms of problem structure would be necessary here to a claim about "most" bandits and more context would need to be given about what is meant by "most", e.g., most "real-world bandits?", "most bandits in literature?", "most out of all possible bandits?", etc.

7. Throughout the paper, the authors make implicit claims that most problems are indexable without giving much support for that claim. Perhaps because the authors' algorithm relies on problems being indexable in order to be asymptotically optimal. Some things that could help strengthen this paper in that regard:
  a) Adapt/reframe the numerical "strong indexability" verification step that authors' use in experiments to be a pre-processing step to their algorithm. This way, users can at least numerically verify to their desired level of precision whether or not the authors' algorithm will be optimal for their use-case.
  b) Argue for the strength of the Whittle index approach in non-indexable or non-verifiably-indexable (e.g., very large state space) cases by pointing to the  provided experimental results or pointing to papers that have analyzed/experimented with the Whittle index policy in such cases.

Minor Comments:
line 32- 33: "where the index loosely corresponds to the amount of cost that we are willing to pay to play the arm"
- Authors should consider rewording this. The Whittle index is defined as exactly this cost that the planner is willing to pay to play the arm, so I am not certain that saying "loosely corresponds" is accurate.
 
33-34: "It has been shown that the Whittle index policy is either optimal or asymptotically optimal in many settings."
- Probably makes sense to introduce indexability here? E.g., “asymptotically optimal under a technical condition known as indexability”. In general it would be helpful to frame the story of RMABs in the light of how the problem has typically been solved, i.e., by proving or providing evidence of indexability, then deriving Whittle index policies. Then making clear how your algorithm will improve on this style of approach and why it is valid.
 
35-36: "In this paper, we present Neural Whittle Index Network (NeurWIN), a principled machine learning approach that finds the Whittle indices for virtually all restless bandit problems."
- The Whittle index does not always exist, i.e., when a problem is not indexable. So this statement is somewhat misleading and should be explained more carefully. Can you be more precise by what you mean by "virtually all restless bandit problems"?
 
Line 66: "There has been a lot of studies"
 - Just suggesting something slightly more formal thant "a lot", e.g., "There have been many studies"
 
In definition 2, I was mildly confused why s was in A(\lambda)... but realized that A(\lambda) is indeed defined as a set of states. I would lightly suggest using something besides A for a set of states (perhaps \sigma?), since lower-case a is used for actions.
 
line 142: "attractable" --> attractive
 
line 142-143: "Intuitively, as the activation cost increases, it becomes less attractable to activate the arm in any given state. Hence, one would expect Ds(λ) to be strictly decreasing in λ for most practical problems."
 - While I tend to agree with this claim, I think the authors should make an effort to support this argument that "most problems are strongly indexable" with evidence (perhaps mention the experimental results) more so than intuition or by arguing further about the typical structure of problems. While it seems reasonable that increasing activation cost would not increase attractiveness, it seems perfectly plausible that increasing activation cost would leave attractiveness unchanged in some problems with specific structure.
 
Thm 1. -- this is mostly a restatement of existing concepts, i.e., indexability and the \lambda-adjusted Q-values, so I would consider reassigning this as a proposition or something similar. To this reviewer, a theorem implies a novel theoretical contribution.
 
Thm 2. -- It is unclear to me why strong indexability is important. It is not a concept I am familiar with from other restless bandit literature and unclear how it helps the authors' algorithm. Strong indexability seems to guarantee that there should be one unique \lambda that makes D(s,\lambda)=0, but again, it would help if the authors could clarify why such a concept is useful. For instance, such a concept is not required by Weber and Weiss in the proof of the optimality of the Whittle index. Understanding strong indexability is important to this reviewer, since the authors present these results as Theorems in their paper. Perhaps it is required for their neural network system to be differentiable everywhere?
 
- Recovering bandits is a strong experimental domain for the authors' algorithm, since the indexability of this space is unknown. It would help to highlight explicitly this fact in the introduction to make clear the algorithm's general applicability.
---------------------------------------------
Update:

I have read the other reviews and the author responses. I thank the authors for their response. Overall I am now convinced about the empirical results, but still unsure about the theory and the algorithm itself.

Experiments: The authors thoroughly addressed all my comments about experimental results, including implementations of WIBQL and UCB/Thompson Sampling from [17] and the results seem convincing enough, though I agree with Ha51 that WIBQL requires much hyperparameter tuning to be most effective, so it would be good to have more details there.

Theory/Algorithm: I am also still not sure how well the theory actually supports the algorithm, even with the revised theorems. I am also still somewhat lacking in my understanding of why exactly the proposed algorithm should converge, and unfortunately, the authors did not address that concern in their response (at least not clearly).

Ultimately, I am increasing my score by 1 to reflect the authors addressing my empirical concerns. However, authors should make their code publicly available upon acceptance to facilitate others building on the authors' contributions despite some lack of clarity in the algorithmic descriptions.
limitations_and_societal_impact: yes
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: 
Whittle index are used to construct a powerful heuristics for restless bandit problem.  This paper proposes to estimate Whittle Index in discounted Restless bandit problem via a deep reinforcement learning algorithm. The authors define a notion of strong indexability that they use to construct a deep RL algorithm that learns Whittle indices. The authors argue that when a problem is strongly indexability and the neural network is precise enough, the deep RL algorithm will learn Whittle index (although their theoretical result is not fully convincing to me).

The authors present extensive experimental results that show that their algorithm compute Whittle indices and provide a very good performance compared to existing work.

main_review: I liked the paper and the algorithm it proposes. While Whittle indices have been defined a long time ago, there is a recent surge of interest on restless bandits since it has potential application in many RL problems. I liked the experimental section that I find quite thorough and convincing. The comparison with related work is interesting as well as the fact that the authors show the strong indexability of various problems (either theoretically for the first, or numerically). This indicates that this notion is adapted. The algorithm performs very well in three real-life problems. Also, the limitation of the algorithm is provided: the authors test the case where simulator is noisy and the strong indexability of the three problems. All-in-all, this convinced me that the presented algorithm has potential application for many restless bandit learning algorithms.

That being said, I think that the novelty of the paper is somehow limited and I think that some part would deserve to be better explained. In particular, I did not find Theorem 3 very informative: I found the current version of the theorem rather weak and it does not convince me that a rich-enough network will indeed learn the true Whittle indices.

To me, it is not clear how others algorithms are trained (the same number of episodes and batches as NeurWIN?). And about others algorithms structures (almost the same number of parameters as NeurWIN, but how the hidden layers, input and output layers are connected?).

The NeurWIN algorithm seems to need an internal simulator. It is an off-policy algorithm. Can we say something about its regret (at least empirically?) or in general about its performance while learning? 

Also, Whittle indices are particularly useful for time-average reward and not for the discounted case. Would it still work here?

Minor remark: In the organization of the paper, I do not understand why section 3.3 is where it is. This section is interesting but completly breaks the flow of the paper. To me, this should be moved to section 5 (or merged with section 5.5 in a new section).


** Rebuttal **

The answer of the authors clarified my view of the paper. I am raising my score from 5 to 6 (not higher because I am still puzzled about the novelty of the approach, and because incorporating the new theory in a convincing manner might not be that trivial.)
limitations_and_societal_impact: Could the authors explain better what is the implication of Theorem 3? Does it guarantee anything on the convergence of the algorithm?

The pseudo-code of the algorithm is very hard to understand. Could the authors justify their design choices and the potential impact of them?

Is there an open-source implementation of the code that would make it usable by others?
review_title: null

Meta-review: The paper studies the important problem of restless bandit. While the Whittle index is known to optimally solve the problem, it remains hard to compute in many practical problems. The authors propose a solution leveraging the generalization capabilities of neural networks in a non trivial way and obtains a practically feasible and accurate method.

After the rebuttal and the discussion, the reviewers agree that the problem is significant and the contribution is interesting and it is likely to set an important baseline for future work on the topic. For this reason I recommend acceptance. Yet, there remains a number of aspects that the authors should improve in the final version:
- Add the comparison to WIBQL detailing how it is implemented and clarifying that defining a scalable version (i.e., with neural networks) is outside the scope of the paper.
- Add the improved version of the theory and possibly include an additional paragraph discussing in detail its relevance.
- Clearly acknowledge the need for a simulator and discuss how this could be possibly relaxed as a future work.
- Integrate reviewers' suggestions while improving the structure and overall clarity of the paper.


Decision: Accept (Poster)