Tracking Most Significant Shifts in Nonparametric Contextual Bandits

Summary

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.

Strengths

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.

Weaknesses

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.

Questions

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.

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

3 good

Contribution

4 excellent

Limitations

N/A

Summary

This paper studies the contextual bandits problem with changing Lipschitz reward function and proves a *minimax optimal* regret bounds for this problem, which includes both upper and lower bounds. For the upper bound, this paper comes up with an algorithm that achieves it. The algorithm is based on carefully maintaining a hierarchical partition tree that discretizes the context space.

Strengths

1. This paper achieves minimax optimality for the problem, which closes the existing gap and solves the problem. 2. The novel idea of significant shifts and the algorithm design of maintaining the partition tree, could be of independent interest. 3. This paper provides excellent plain word explanation to highlight the key ideas and steps in their proof.

Weaknesses

1. The algorithm is recursive and complicated, so it makes the audience hard to understand the algorithm, even with the algorithm explanation in Sec. 4. Maybe it is better to replace Line 9 in Algorithm 2 with some while-loop to improve readability.

Questions

Typos: 1. Line 178, "Miminimax". 2. Below Line 259, Algorithm 1, "tree $T$" -> tree $\mathcal T$. 3. Line 305, "ut". 4. Line 306, "(i.e., the bin at level $r_{s_2-s_1}$ containing $X_t$)" duplicates. 4. Line 13 in Algorithm 2, trailing ; after : The authors may spend some time to polish the paper before finalizing.

Rating

8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

4 excellent

Contribution

4 excellent

Limitations

N/A

Summary

This paper studies nonstationary contextual bandits. In particular, a new notion of "significant shift" is introduced (Definition 6) which accounts for shifts in the distribution localized at the possible actions and with significant magnitude. First, the authors derive a lower bound for existing definitions of shifts (Theorem 1) and provide an oracle algorithm to achieve it. Then, after introducing the new notion of shifts, they derive an algorithm which adapts to it (i.e., which does not require the time indexes of the shifts), see Theorem 3.

Strengths

- The topic is of interest to the NeurIPS community - The paper is globally clear and well written - The intuition and analysis are sound - Authors constantly compares their results with existing ones to position their contribution

Weaknesses

- The paper lacks experiments. Since the authors provided a detailed algorithm, I find it disappointing that no experiment is carried out. It would be of particular interest to study the behavior of the different algorithm depending on the types of switches - I feel previous paper on significant switches could be discussed a bit more, to highlight the changes and challenges raised by the contextual setting - No lower bound for the proposed definition of switches is provided Minor: - Abstract: MAB is not defined yet - Section 1.1: linebreaks do not seem necessary to me and make the reading less fluid - When citing several works, the chronological order is preferable - Equation ($\star$): what is $r(B)$? - Lines 242, 252: are the log factors omitted? - l. 305: ut - l. 316: $\approx$ could be avoided

Questions

- In this paper, the available actions are the same at every time steps. Could the authors think about a generalization when the action set changes over time? In particular, would it be possible to restrict the significant changes only to the playable arms? - Could the Lipschitz assumption be removed? - In Definition 7: does $\cal{G}_t$ always exist? - Do authors have in mind simple examples of $f_a^t$ where both switches characterization drastically differ? - If I'm not missing anything, it seems to me that no definition of switch implies the other. Then, I find it a bit misleading to compare results all along. It should be made clear that the two are two different parameterizations incomparable in general (I agree on the identity $\tilde{L} \le L$) - Assume that changes have small magnitude (e.g., small drift at each time step) or do not apply to every arms (but only to the best let say), is the regret of CMETA not impacted by those switches?

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

N/A

Summary

This paper studies nonparametric contextual bandits where the mean reward functions can change over time. A key assumption is that the rewards are Lipchitz in context. The authors then adopt a typical approach to discretize the context space into bins. The notions “significant regret”, “unsafe at context”, and “experienced significant shift,”; in particular, an experienced significant shift implies a change in the optimal arm in a particular bin. The authors then propose an algorithm Contextual Meta-Elimination while Tracking (CMETA) and establish regret bounds in terms of the total number of “experienced significant shifts.”

Strengths

This paper is well-organized and introduces both a notion of “experienced significant shift” and an algorithm, CMETA, accompanied with theoretical guarantees.

Weaknesses

My major concerns centers around the comparison of CMETA and its analysis to the algorithm and regret analysis introduced by Suk and Kpotufe (2022), and the presentation of the theoretical results. 1. Besides discretization of the context space into bins, how does CMETA and its analysis differ from that introduced by Suk and Kpotufe (2022)? 2. As for the presentation of the results, we take Theorem 3 as an example. First, the notation is inconsistent: the notation $\tilde{L}$ is introduced in line 214, and in Theorem 3 it is appeared as $\tilde{L}$ in line 248 but $\tilde{L}(\mathbb{X}_T)$ in line 250. In addition, $\tilde{L}$ is dependent on the discretization of context space into bins, which is determined by level $r$ in Algorithm 1, yet $r$ does not appear in Theorem 3.1? Moreover, could the authors elaborate on “choice of level” in Section 4 on how the level is adaptively chosen?

Questions

My main concerns were raised in the “Weakness” section. To reiterate: 1. Besides discretization of the context space into bins, how does CMETA and its analysis differ from that introduced by Suk and Kpotufe (2022)? 2. It would be very helpful if the authors could elaborate on the “choice of level” in Algorithm 1 (CMETA) and how the regret bound established in Theorem 3.1 depends on the level. A remaining question is: - In Corollary 4, it seems that if $\tilde{L}$ grows linearly in $T$, the bound on cumulative regret becomes linear in $\log^3(T) T$, in bandits where rewards are bounded in $[0, 1]$ (and cumulative regret is at most $T$)?

Rating

4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

2 fair

Contribution

3 good

Limitations

N/A