- Rating
- 3(+2)
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 1
- Soundness
- 2
Read review
Paper summary
This paper studies the problem of minimax-optimal regret minimization for linear bandits in dimension with for some constant , with finite -th moment assumption for . They provide a matching upper and lower bound, showing that the worst-case regret is of order , for .
Critical strengths
This paper apparently closes an existing gap between upper and lower bounds on linear bandits with heavily-tailed rewards.
Although I am not an expert on those topics, the literature review seems thorough.
Critical weaknesses
This paper is not clear at all. I found some sentences rather difficult to understand (e.g., lines 179, 290, 319, paragraph 353 - 358, 366-367, 381,...). Moreover, some key notations are used in the proofs and sketches of proofs and not introduced in the main text (e.g., , , , ). The full proof, while written in more detailed, is still hard to follow due to the missing notations, and to the tone being overly concise at the cost of readability.
I do believe that this paper would greatly benefit for an intensive and careful rewriting, and a resubmission.
[Edit] The authors have adequately addressed my concern, and I am happy to raise my score.
Questions for authors
My assessment rests on the fact that I find this paper much too unclear for publication. While it would not make me change my mind, I strongly encourage the authors to clarify the points mentioned above, as well as the following questions, before resubmission :
- in the proof of the lower bound, are and the same stopping time ?
- Why is the observation W_t in Section 5, while it was previously Y_t ?
I also strongly encourage the authors to ask for an external feedback on the clarity of the writing before resubmission.
5 comments
To Reviewer 5fZ6 (2/2)
W2. Key notation used in the proofs and proof sketches is not introduced in the main text (e.g., , , , ), and the full proofs are hard to follow because of missing notation and a very concise style.
R2. Thank you for listing these symbols. Each of these symbols is now defined in the main text where it first appears, and we repeat the definitions here for convenience. The symbols and denote the action selected in round when the policy interacts with the true experiment and with the auxiliary experiment , respectively. The quantity is the mutual information between the hidden index and the data collected in the auxiliary experiment. The symbol denotes the finite field with elements. The vector has coordinate if and otherwise, as in the rewritten lines 353–358 in R1.
To make the full proofs easier to follow, we have made three kinds of changes. First, we expanded the concise passages. The proof sketches of Sections 4 and 5 are now written out in more detail, as in the passages quoted in R1. In the appendices, the proof of Theorem A.1 opens with an overview of its five steps, and Appendix B opens with an outline of the proof of the upper bound. Second, we added a notation table in the new Appendix D. The table lists the main symbols of the paper, each with its meaning and the place where it is introduced, so that the proofs can be read with the table at hand. Third, we revised the wording of the appendices for readability. The appendices now use the same terms as the main text, and each symbol has a single meaning throughout the paper.
Q1. In the proof of the lower bound, are and the same stopping time?
A1. Thank you for this question. The quantities and are two different objects with different roles in the proof.
The round is drawn uniformly from , independently of everything else, and is not revealed to the policy (Section 4.3). The purpose of is to express the regret through a probability. Since is uniform and independent, the expected number of rounds in which the policy does not play the optimal action equals , so a lower bound on the probability of a mistake in round gives a lower bound on the regret.
The time appears only in Appendix A.1 and is the first round of the auxiliary run in which the diagonal gate is open and the policy plays action , with if no such round exists. The purpose of is the coupling described in R1. The true run and the auxiliary run coincide before . If , then belongs to the list . If , the two runs coincide in every round, and in particular in round . In both cases, implies , and the proof needs exactly this implication.
Appendix A.1 now explains this difference where is introduced.
Q2. Why is the observation in Section 5, while it was previously ?
A2. Thank you for this question. The symbol denotes a reward, and the symbol denotes a loss. Sections 1 to 4 are written for rewards, and Section 5 is written for losses (line 377). We use losses in Section 5 for two reasons. First, FTRL is usually analysed with losses. Second, Theorem 5.1 also covers mean losses that change from round to round, a setting more general than the model of Sections 1 to 4. In the model of Sections 1 to 4, the reward and the loss are related by (line 386). The revised Section 5 states this relation in the first paragraph, before Theorem 5.1, and the notation table lists both symbols.
Dear Reviewer 5fZ6,
Thank you again for your time and effort in reviewing our paper. As the discussion period is coming to an end, we would like to follow up on our response. We have revised the paper to address all the points raised in your review, and we have also revised other parts of the paper to improve readability. If you have any further questions or concerns, we would be glad to address them before the discussion period ends. If our response and the revision have addressed your concerns, we would greatly appreciate it if you could reconsider your rating.
To Reviewer 5fZ6 (1/2)
We sincerely thank you for providing valuable feedback. We detail our response below point by point. Please kindly let us know whether you have any further concerns. If our response addresses your concerns, we would greatly appreciate it if you could reconsider your rating.
W1. Several sentences are difficult to understand (e.g., lines 179, 290, 319, 353–358, 366–367, 381).
R1. Thank you for pointing to the exact lines. We have rewritten each of these passages, and the new text is given below so that the response can be read without the revised paper.
We also revised the other proof sketches of Sections 4 and 5 in the same way.