Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The paper considers the online RMAB problem, with multiple available actions and when the MDP on each arm is unknown. The paper derives an index policy for the online RMAB problem, different from the WHittle index policy and then proposes two index-aware RL algorithms. The paper shows that both algorithms achieve sublinear regret.
strengths_and_weaknesses: **Strengths**




- The approach seems principled and theoretically solid. The paper proves that their proposed index based approach is asymptotically optimal. 
 - Empirical analysis: The experiments seem to be comprehensive; they cover a wider range of settings and test against most of the relevant baselines, including fairly recent baselines. 
- The context is well set up: explaining where the sota is and what gap needs to be filled.

**Weaknesses**

- The writing/exposition is not clear at some places: For instance, the abstract says each arm evolves according to a Markov chain. However, later in section 2, each arm is said to evolve according to an MDP. 

- Minor issues: grammatical issues/typos involving usage of plural/singular quantity at few places

questions: - Line 114 says w.l.o.g r(s,0)=0. However, how is this general given that r() could potentially depend on s, i.e. r(s,0) =s? 
- Lines (70-74) say that the paper takes a more general approach, hence is more efficient. However, this seems a bit counterintuitive; shouldn’t there be a trade-off? Is there something else that is being given up?

limitations: Yes
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: Authors provide two learning algorithms for the multi-action restless bandit problem (R2MAB), with new regret bounds that advance state of the art. Their algorithm and bounds rely on a new index policy which is asymptotically optimal under a global attractor condition. Authors provide numerical experiments on three domains that support their claims.
strengths_and_weaknesses: Strengths:
 - The draft is mostly well-written, making the contributions clear.
 - Authors provide experimental results on three domains showing wins on each (though modest compared to MAIQL on scheduling and TB)
 - The authors provide attractive regret bounds or the average reward, R2MAB case, advancing current state of the art.
 - Authors introduce a new index policy class for R2MAB, ERC, which seems to have good performance and will be of general interest to the RMAB community, though it seems to rely on a numerically verifiable global attractor condition.
 - Authors provide two learning algorithms, GM-R2MAB and UC-R2MAB, where the former is "offline" in that it takes time to collect enough samples to build a confident world model, and the latter is "online" in that it follows more closely to an upper confidence bound approach, exploring and exploiting in tandem. UC-R2MAB seems to perform better than all baselines in experiments.

Weaknesses:
 - My understanding is that the global attractor property of a policy class is data dependent, and thus needs to be verified for each new dataset to which a policy class is applied. All of the authors' core results seem to depend on the global attractor condition, i.e., optimality of the ERC index policy they propose, and thus also the regret bounds (which rely on the ERC being asymptotically optimal). So, unless I am missing something, all of the results here depend on the users' ability to numerically verify the global attractor policy for the data to which they hope to apply the authors' algorithms. This may be ok, but the authors need to make it much more clear throughout the draft if this is the case. For instance, in Remark 1, authors claim that "ERC does not require the indexability condition, which is often hard to establish especially when the transition kernel of the underlying MDP is convoluted" -- while true, one seems to have to verify a global attractor condition instead to use the authors' policy, which is ultimately very similar since the indexability condition is a necessary condition for the global attractor property of the Whittle index policy, and itself is often verified numerically for new MDP classes. So authors should clearly state the tradeoff.
 - The authors mark N/A in their checklist for both limitations and social impacts -- this is not acceptable in the current iteration of NeurIPS. Authors need to engage in some amount of discussion in the limitation of their methodology. Also, since the authors present experimental results on a tuberculosis care domain, it is reasonable to ask that they discuss how their algorithm might have adverse social impact, and so they should engage in this part of the discussion as well.
 - More evaluation would be helpful. Specifically, authors vary the number of actions, but not the number of arms, which is they key scaling parameter in RMAB. Authors should provide some experiments to show both regret and runtime scaling as N increases for at least one domain. Additionally, the authors compare against MAIQL from Killian et al. 2021, but not LPQL, which seems to be the preferred R2MAB learning algorithm from that paper. Presumably they did not compare against LPQL because it handles the discounted reward case, rather than average. However, in the appendix, authors compare against NeurWIN which handles the discounted reward case. So authors should also compare against LQPL for completeness.

questions:  - Please respond to the weaknesses above.


Note: the paper potentially has enough merit to be considered for acceptance in my view, but the points listed in "weaknesses" need to be clarified.

-------
I have read the other reviews and author responses and am satisfied with their answers to my questions, and have increased my score. Authors should add more clarifying language about the global attractor property's reliance on data distributions as is done in Verloop 2016 section 6.
limitations:  - Please see weaknesses, second comment
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: The authors address infinite horizon average reward restless multi-action bandits. They propose a new type of index, and two algorithms that calculate this index when the transitions and rewards are unknown - one offline and one online. The authors provide regret bounds for their algorithms and compare them empirically to other methods.
strengths_and_weaknesses: Originality
The paper is novel to the best of my knowledge. The authors emphasize that their regret bounds are highly novel, I have no knowledge to contradict that fact.

Quality
The paper is of very high quality - the presentation of the problem is clear and well written, the regret bounds are impressive and strong,  and the experiments form a convincing argument. 

Clarity
Despite the results being mostly theoretical, I found the paper to be very clear and very well written. 

Significance
Restless multi-action bandits is a a bit of a niche so the significance of the paper is somewhat limited. The proposed algorithms and simulations correspond to discrete MDPs whose model is learned, which further hampers the significance of the work for applications. Inside this niche, the results do seem convincing, interesting and filling in missing knowledge.


questions: The paper is very clear and I have no questions or suggestions.
limitations: Not relevant for this paper.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: The paper proposes two reinforcement learning algorithms for the multi-action multi-armed restless bandits' framework: GM-R2MAB (offline learning) and UC-R2MAB (online learning). An index-based policy is advocated for to avoid the dimensionality issue with increasing arms' count. A linear program (LP) is described to find a value upper bound for the R2MAB, and to characterize the asymptotic optimality of the ERC index-based approach. When the transition kernel and reward function are unknown, regret bounds were proven for both RL algorithms, and a comparison against other RMAB learning algorithms is provided on two experiment cases. The online learning algorithm (UC-R2MAB) was shown to give the lowest empirical regret in all cases.
strengths_and_weaknesses: ### Strengths:

The paper contributes well in the finite-time analysis of R2MABs in the average reward case, and offers detailed theoretical regret analysis for both the offline (GM-R2MAB) and online (UC-R2MAB) algorithms. The introduction also explains in detail the lack of understanding of R2MABs' regret performance. The experiments include results from recent RMAB learning algorithms, and the experiment cases cover both the two-actions and multiple actions' cases. The necessary regret proofs (for theorems 2 and 3) provided in the appendices form the bulk of the paper's contribution and are well articulated.


### Weaknesses:

I find lemma 1 statement to be vague and the proof a bit general. The lemma statement depends on the value definition $V$ that is only mentioned in the appendix with the scaling parameter $\rho$ (for theorem 1). I find having an explicit definition of the average reward value necessary before going into the proofs. For lemma 1 proof, the wording should be modified to indicate that the original problem's feasible region $\Gamma$ is reachable for all points of the relaxed problem's region $\Gamma^/$.

In the experiments' section, I understand that the page limit prevents a longer description of the results. In the revised manuscript, the author(s) should dedicate more explanation as to why the two algorithms perform better than the baselines. Currently the discussion rightly mentions that the two algorithms solve an ELP, but it would help if the author(s) discuss UC-R2MAB and GM-R2MAB limitations compared to the baselines. In addition, it would be nice to aggregate all algorithms' results into one plot rather than splitting them between two plots (one in the main text and the other in the appendix). I currently need to look at two graphs that consider a single case study to understand how the two algorithms perform.

While the paper's technical analysis and sections are well-written, the paper's organization\spelling accuracy can be significantly improved as I highlight below:

Starting in line 19 and throughout the paper: *Restless multi-armed bandits (RMAB)...*
should be RMABs throughout the paper when the plural bandits is used.

Line 29 *"This is restrictive since the decision maker in many applications often has access to multiple actions for each arm."*
The author(s) should provide examples or cite work for this claim in the introduction.

Line 31 *"which we call the restless multi-action bandits, dubbed as R2MAB"*
the full name would be better here: multi-action multi-armed bandits. 

Line 46 *Second, existing RL algorithms with theoretical guarantee of  a sub-linear...*
algorithms with **a** theoretical guarantee.

Line 58 *[57] achieved low-complexity... and not easy to be directly generalized*
**a** low-complexity policy... and **is** not easy.

Line 123 *In the remaining of the paper,*
In the remainder of the paper.

Both remarks 3 (line 237) and 4 (line 298) can be written as normal non-italicized paragraphs for easier reading. 

Line 288 at the end of equation 12 (theorem 3), it should be a period and not a comma.

Line 301 *and the regret is exponentially in the number of arms and states*
and the regret is **exponential** in the number...

Line 320 *as a specific birth-and-death process*
better to call it **birth-death** process for consistency.

Line 324 *For multi-action setting*
For **the** multi-action setting

Line 337 *between this award difference and the number of arms as optimality gap.*
between this *reward* difference and  the number of arms as **the** optimality gap.

Line 351 *It is clear that our GM-R2MAB and UC-R2MAB is more efficient in running time.*
It is clear that our ... **are** more efficient...

Line 372 *Each action has varying cost and effective*
should be *effectiveness*.

As a minor note, the author(s) should also cite the paper in the introduction section:
Francisco Robledo, Vivek Borkar, Urtzi Ayesta, and Konstantin Avrachenkov. 2022. QWI: Q-learning with Whittle Index. SIGMETRICS Perform. Eval. Rev. 49, 2 (September 2021), 47–50. https://doi.org/10.1145/3512798.3512816



---------------------------------------------
### After rebuttal:

I thank the author(s) for responding to all of my comments. I read their responses and I find it to answer my concerns. In the updated paper, the author(s) should include the revised description of lemma 1 and the TB care dataset usage. 

I have updated the soundness score from 3 to 4 to reflect the updates the author(s) provided. I will keep my overall score at 7.

 
questions: 
1. Both GM-R2MAB and UC-R2MAB are able to learn index policies without the indexability condition (needed for the Whittle index). However, if the considered RMAB is indexable, how would that affect the two algorithms' regret bound? would indexability give a tighter regret bound?

2. Assuming the RMAB is indexable, is there a characterization of the two algorithms' learned indices and the Whittle index if it exists? How would the learned index relate to the Whittle index? 

3. In the checklist under 4.d, I couldn't locate in the main text or the appendix where consent was obtained for the used data, which should be explicitly mentioned in the revised manuscript.  
limitations: **Limitations:** While the proposed approach is direct at multi-action RMABs and not the binary action case, the paper does not discuss the two algorithms' performance when the restless arms are indexable. A brief discussion of how indexability affects regret upper bounds would be interesting. 

**Societal impact:** The paper presents two algorithms for RMABs in the average rewards' setting, including one medical trial case in India. Hence, an application-specific analysis should be performed by those wishing to use either algorithm (especially in medical trials' cases).
review_title: null

Meta-review: metareview: The paper tackles the challenging problem of online learning restless multi armed bandit (RMAB) policies. Among its contributions are the introduction of a new tractable class of RMAP policies to learn over, and tractable learning algorithms, with regret guarantees, along the lines of statistical upper confidence bounds. These could serve as useful building blocks for theoreticians and practitioners in the area alike.

The contributions of the paper are unanimously acknowledged to be positive by the reviewers, after their initial reviews were responded to in detail by the paper's author(s) leading to helpful clarifications. In view of this, I recommend acceptance of the paper. 
confidence: Certain
Decision: Accept