- Rating
- 1
- Confidence
- 2
- Informativeness
- 1
- Presentation
- 1
- Soundness
- 1
Read review
Paper summary
This paper studies whether an online learning algorithm can achieve the optimal competitive ratio in improving multi-armed bandits without prior knowledge of problem-dependent parameters, and how the answer changes when rewards are noisy. Authors show that those priors are unnecessary up to constant factors in the noiseless setting, but bounded adversarial multiplicative noise creates a fundamental difficulty when both reward scale and curve-shape information are unknown.
Critical strengths
Frankly, I cannot verify the correctness and soundness of this paper due to poor presentation (see weakness). Suppose that all results are correct, and then the contributions are as follows:
-
Authors propose an algorithm that achieves competitive ratio without prior knowledge of the reward scale, removing term in prior work. They also establish the optimal all-horizon competitive ratio of .
-
Authors develop an algorithm that achieves the optimal competitive ratio simultaneously for all without knowing the reward scale, lower-envelope exponent, or horizon.
-
Under bounded adversarial multiplicative noise, the authors show that simultaneously adapting to an unknown reward scale and lower-envelope exponent will incur an unavoidable additional factor.
Critical weaknesses
The major weakness of this paper is its presentation. Even if I spend much time reading, it's hard for me to parse the paper. There are too many coherence and presentation issues. I just list some as examples (I do not include all issues, but I hope the authors themselves can at least go through the paper once).
- In the 1st paragraph of introduction, it is totally unclear the meaning of uniform when you refer to ``A uniform guarantee is different''
- In the 1st paragraph of introduction, there is no definition of .
- In the 2nd paragraph of introduction, there is no context for me to understand ``an absolute threshold''.
- In the 2nd paragraph of introduction, no definition for and (though there is definition for , but what is subscript for?)
- In the caption of figure 1, what's the meaning of uniform price? Uniform price appears multiple times without a clear definition.
- In contribution paragraphs, it is unclear to readers what are proposed algorithms unless they carefully check in algorithm section. First, in the first bullet, it starts with ``Probe-and-commit''
- In the third bullet of contribution paragraphs, what's the two increment-based repairs when you referring ``Random-marginal probing and two increment-based repairs fail with unbounded ratio''. What's the Nested random-permutation probing? Please at least let readers know which algorithms are proposed by this paper.
- More importantly, I try my best to read the first section, but still cannot understand the high-level idea on why the logarithm disappears.
Overall: It's extremely hard to follow this paper, and I cannot verify the soundness and correctness of this paper, even just in a high-level.
Questions for authors
I just hope that the authors can significantly improve the presentation of the paper, which make it easy to follow.