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 author studies a problem in which the reward of arms is increasing as the arms are not selected in the last rounds. At first, the author studied the problem of solving such an issue when the parameters of the problem are known. The first issue is to design an algorithm that effectively approximates the optimal solution to this problem. The author provide such an algorithm and studied its approximation properties. Finally, it provides an ETC scheme to deal with the case in which the learner is acquiring only bandit feedback. Finally, guarantees in terms of regret for this algorithm are provided.
strengths_and_weaknesses: I think that the paper is well written. However, I think that the choice of the authors to include proofs and sketches of the prooofs is not effective to communicate the message of the paper. I think that such aspects, as well as the statement of some lemmas which are not central to the paper itself might have moved to the appendix to make room for some more comments and, possibly, to some final experiments.

I think that adding a table to summarize the different results present in the literature and the ones provided in this paper would help to appreciate the value of this work.

I think that adding a more formal definition of the bandit setting is necessary.
questions: 
Why are the proof so important? Are they providing novel techniques which are of general interest?
limitations: I do not foresee limitations and potential negative societal impact of the current work.
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 studies a non-stationary bandit problem with $n$ arms, where the mean reward of an arm is a non-decreasing function of its "idle time" since last pull. It is assumed that each arm fully "recovers" after being idle for a certain number of periods, i.e., its mean reward does not change any further. An upper bound on the recovery time of all $n$ arms is also assumed known. At any time, the decision maker can play a subset of at most $k < n$ arms upon which she collects the sum of their associated payoffs. As is the norm, the goal is to maximize the cumulative expected payoffs over $T$ rounds, with $T$ possibly being unknown a priori. 
strengths_and_weaknesses: It is well-known that computing an optimal policy even for the "planning" problem (assuming perfect knowledge of the mean reward functions) is NP-hard. Notably, the authors improve upon the current best known $1/4$-approximation guarantee for $k=1$ to $1-1/e$ achievable in polynomial time. For $k>1$ also, their algorithm achieves improved numerical guarantees vis-\`a-vis extant work. Lastly, a learning version is also considered where the mean reward functions are initially unknown and decision maker only observes noisy semi-bandit feedback for the collection of arms played. For this setting, the authors propose an algorithm based on the Explore-then-Commit principle that is shown to incur sub-linear regret relative to its "full information" planning counterpart.

Overall, the analysis appears sound (though I did not delve into details contained in the supplementary sections) and I reckon this paper makes solid theoretical contributions. I would therefore vote for an accept.
questions: Just out of curiosity: If T is also known, can the approximation ratio be improved? Alternatively, if T is known but not the max recovery time, can something be claimed at least for "large" T perhaps by using some appropriate sub-linear function thereof as a proxy for the latter?
limitations: This appears to have been well-addressed.
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: Authors analyze and improved the existing results for the recharging bandits problem. They put a lot of efforts in the optimization/planning part and obtained strong improvements on that side.
strengths_and_weaknesses: The paper is well written and the contributions are clearly stated in particular thanks to paragraph 1.3. I found the literature review to be very complete.
questions: I have only few questions.

The first question I have is which technical difficulties authors have met in improving the planning stage. Specifically, I would like to understand how much the results of [PC21] and [Yan11] contribute in the obtained improvements.

Secondly, I am wondering why developing an ETC approach rather than an UCB one as done by [Kleinberg and Immorlica].
limitations: See above.
review_title: null

Meta-review: metareview: All reviewers agree on the merit of the work. 
confidence: Certain
Decision: Accept