- Rating
- 2
- Confidence
- 2
- Informativeness
- 3
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This paper works on the Restless Multi-armed bandit with (possibly biased) offline data. They aim to achieve a best-of-both algorithm, which guarantees (1) if the offline data illustrates the environmental stochasticity correctly, the algorithm is able to achieve smaller regret compared to the fully online learning setting (2) if the offline data is biased, the algorithm still recovers the upper bound of pure online learning algorithm. They design algorithm ODR-IOB to handle the problem setting, achieving these two targets with intuition of algorithm design and performance guarantee. Numeric records validate the efficiency of their algorithm.
Critical strengths
- I appreciate the paper is willing to spend enough space to present the intuition of the algorithm design, which is helpful and easy to follow.
- The derived upper bound of the regret is meaningful and consistent with the intuition of the algorithm. The instance-independent upper bound of regret should be tight, by comparing it with the K-armed bandit
- The paper follows the research standard and covers the required analysis of a theoretical paper.
Critical weaknesses
I am unfamiliar with the topic and I didn't check the proof carefully. Please rectify me if my understanding is wrong.
- I think the paper still needs to clarify some notations and improve the presentation, for the rigorousness. See the subsection "Questions For Authors".
- Instance-dependent analysis is unclear. But I think it is OK. To my knowledge, that the paper has provided new ideas on the algorithm design and the problem settings. I will check the comments from other reviewers.
Small typo:
- line 305, Equation equation
Questions for authors
Please forgive my stupidity if some of them are naive.
-
I want to confirm whether this paper generalizes the problem setting in "Leveraging (Biased) Information: Multi-armed Bandits with Offline Data, by Cheung Wang Chi and Lyu Lixing", which consider K-armed bandits with offline (possibly biased) data. If not, could you explain the difference?
-
I would like to confirm the dynamic of the interaction between the agent and the environment. Line 38 suggests "At each time stept , a policy selects a subset of arms to activate, where ". While the notation table at the page 15 mentions that is Episode horizon, which also occurs in the Theorem 5.7. Do you mean there are H horizons in each time step ? And at each time step , the agent needs to first choose K arms, and then takes actions in episodes. Then the time step moves to the . In addition, Line 135 suggests that . Does it mean we should take in the Theorem 5.7?
-
I would like to confirm the intuition of the Wasserstein distance. There could be other definition of gap between two distribution. Could you explain why we choose the Wasserstein-1 distance in the definition 3.2, can we replace it with others? For example, 1-norm gap , or kl-divergence.
-
I notice that Figure 3 doesn't take the generic metric as the input, which is required in the step 1, calculation of (8). How to specify ?
-
Regarding the presentation appendix C.2, I doubt whether the following presentation is better. We can first present the full formulation of the ELP equation, and then step into constraints. I will expect a lemma, or theorem to conclude that, for example, must be a feasible solution to the optimization formulation.
It will be easier for me to follow the meaning of solving an optimization problem.
-
Question 1 regarding (24), if , then (24) becomes . In this case, it can be worse than the bound in (23), contradicting with the conclusion in line 421.
-
Question 2 ragarding (24). The definition of is . That means for two pairs , such that , they contribute the same to the regret upper bound. I wonder whether it is possible to quantify the impact , , in the case that is much larger than . In other words, are we able to derive partially instance-dependent result? From my intuition, there should be some difference between and if is much larger than .
I think the answer to the questions 1, 2, 4, 6, 7 are required to support the acceptance, which concerns about a sufficient literature review or rigorous theorem presentation. I will increase my score if the authors are able to clarify these 5 questions. And it will be even better if the authors are able to answer question 3 and 5, which are about the scaffold of designing the algorithm and conducting the analysis.