Official Review · NEURIPS 2023

This paper studies nonparametric contextual bandit problems with distributional shifts. This paper proposes a new notion of distributional changes called the experienced significant shifts. Based on this notion, the authors develop new algorithms that achieve the minimax rates without knowing some problem-dependent parameters. ====After rebuttal==== I have read the rebuttal. I'd like to keep my scores. I also encourage the authors to add more discussions regarding the adaptivity issue. The authors developed a new notion called the experience significant shifts that better capture the distribution shifts in contextual bandits. Based on this new notion, the authors show that the minimax optimal regret in contextual bandits with distributional shifts can be achieved, even without knowing problem-dependent parameters. In my opinion, this result is significant to the community. Also, along the way, the authors develop several new techniques to achieve this result (e.g., those have been highlighted in Section 5), which can be of independent interest. In the paper, the authors mention several generalizations of the existing setting, e.g., (i) generalization to H\"older continuity, and (ii) the one mentioned in Remark 1. However, no formal results are provided for these generalizations. It will be great if the authors can provide some formal statements. Also, for the oracle procedure described in Definition 7, it's better formally state the power of the oracle, e.g., what is known to the oracle and what is unknown. In bandit learning, when the goal is to minimize the cumulative regret, researchers have previously shown that adaptivity to the usual minimax rate is usually impossible and the best one can hope for is the Pareto optimality, e.g., for the model selection problem [1, 2]. However, in this paper, the authors show the opposite in this paper for learning with distributional shifts. Can authors elaborate more on this? Is this because of the common assumptions made in this setting, e.g., Assumption 2? Citations: [1] Teodor Marinov and Julian Zimmert. The Pareto frontier of model selection for general contextual bandits. [2] Yinglun Zhu and Robert Nowak. Pareto optimal model selection in linear bandits.