1. The paper appears to be limited to a combination of existing techniques: adaptation to an unknown level of corruption (Lykouris et al., 2018); varying variances treated with a weighted version of OFUL (Zhou et al., 2021); variable decision sets (standard in contextual linear bandits). The fact that these results can be combined together is not surprising, and thus the contribution could be considered incremental. 2. The regret bounds seem sub-optimal in the level of corruption (they are of order C^2 when existing bounds seem to be of order C). The authors should discuss more this sub-optimality, is it due to the unknown corruption level? Why should we incur it?
Other comments:
The authors state that if C is known and the variances are fixed then one could directly apply OFUL with a modified variance (to add the corruption). This yields several questions: a. The regret bound would then be of order O((R+C)d\sqrt{T}), right? It would be informative to write it, so that we can compare it with the bound of Thm. 5.1. b. It is then claimed that one of the problems is the varying variances. But this problem was already solved by Weighed OFUL (Thm. 4.2 of Zhou et al 2021) for OFUL without corruption. Isn't it possible to apply the same reasoning with this algorithm? c. For the adaptation to the unknown value of C, I am wondering whether it is not possible to just apply the Corral algorithm (see Cor. 6 of [1]) to (Weighed)-OFUL with an exponential grid of possible values for C (from 1 to T). Wouldn't this imply a bound of order C \sqrt{T} log T?
The assumption that the variance is revealed by the adversary (l. 135) is not clear and should be better motivated. We understand that it was already done by Kirschner and Krause (2018) and Zhou et al (2021) but examples of practical applications would be enjoyable to make the paper more self-contained. Similarly, the assumption of varying decision sets is standard in linear bandits but a few lines to recall why this allows dealing with contexts could be helpful for a reader new to the area.
About the experiments: a.The results seem significantly different when C = 0 and 300. What is the intermediate regime? For what level of corruption does Multi-level OFUL outperform algorithms that do not consider corruption? b. I regret that the algorithm is only compared to baselines that are not designed to deal with corruption and suffer linear regrets. It would be interesting to compare Multi-level OFUL with algorithms for linear bandits with corruptions. This could be done by considering fixed variance and fixed decision sets for instance to apply existing algorithms, so that we can see the actual cost of having a more general algorithm. The algorithm could also be compared with the version of OFUL which knows C and takes into account the corruption.
Minor remarks:
How a \min in (6.3) is obtained using lemma 6.5 is not clear and should be clarified. Same for the \min in (6.8) using lemma 6.6?
How substituting (6.5) and (6.6) into (6.3) gives (6.7) should also be more detailed.
[1] Agarwal et al. Corralling a Band of Bandit Algorithms, 2017.
The authors did not mention the limitations and potential negative societal impact of their work.
1. The paper appears to be limited to a combination of existing techniques: adaptation to an unknown level of corruption (Lykouris et al., 2018); varying variances treated with a weighted version of OFUL (Zhou et al., 2021); variable decision sets (standard in contextual linear bandits). The fact that these results can be combined together is not surprising, and thus the contribution could be considered incremental.