When Can We Track Significant Preference Shifts in Dueling Bandits?

Summary

This paper studies the non-stationary multi-armed dueling bandit under the SST and STI conditions. The paper first shows a hardness result that SST+STI are necessary for sub-linear regret, while merely SST or STI cannot guarantee sublinear regrets. Then, the paper studies under SST+STI conditions and propose a new adaptive algorithm that achieves $\tilde{O}(\sqrt{\tilde{L}KT})$ regret. This regret upper bound improves upon the previous one $\tilde{O}(K\sqrt{\tilde{L}T})$.

Strengths

The paper is well-written and relatively easy for me to follow. The lower bound result is interesting in that it reveals that the Condorcet winner condition is not sufficient for efficient learning in the non-stationary environment. Instead, both SST and STI must hold to allow a sub-linear regret. For the upper bound, a new algorithm along with its analysis is provided to achieve an improved regret upper bound. I find the explanation and reasoning for such an algorithm framework to be quite informative. The analysis of why previous works don't have better dependence on $K$ (Section 5.1) shows the algorithm design is original.

Weaknesses

1. While the impossibility result shows that SST+STI are necessary, it is not clear what is the minimax lower bound under such conditions. Is it $\Omega(\sqrt{LKT})$ or $\Omega(\sqrt{ \tilde{L}KT})$? It is not discussed in this work what is the lower bound in terms of significant shifts. Therefore, it is not well-supported to claim the upper bound is optimal.

Questions

1. As mentioned in the section above. What is the lower bound for the setting in this paper? In the paper, it is mentioned that one lower bound is $\Omega(\sqrt{LKT})$, while your upper bound is $\Omega(\sqrt{\tilde{L}KT})$ with $\tilde{L} << L$. This is contradicting without some context. 2. There are a series of related works discussing ranking with/without SST or STI conditions. Could you also comment on these works: * On Sample Complexity Upper and Lower Bounds for Exact Ranking from Noisy Comparisons (NeurIPS'19) Ren et al. * Active Ranking without Strong Stochastic Transitivity (NeurIPS'22) Lou et al.

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, 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

4 excellent

Presentation

3 good

Contribution

3 good

Limitations

N/A due to its theoretical nature.

Summary

The paper tackles a regret minimizing problem in a dueling bandits scenario, where the underlying preference probabilities are non-stationary but instead shifting over time. In case these preference probabilities fulfill SST (strong stochastic transitivity) and STI (stochastic triangle inequality) at any time, the authors present a novel upper bound on the dynamic regret that depends on the (unknown) number of so-called significant shifts, the number of arms and the time horizon. Moreover, they provide evidence that leaving out one of the assumptions SST and STI would result in a learning scenario where suffering linear regret is in a worst case unavoidable.

Strengths

This paper presents a novel algorithm for the non-stationary dueling bandits problem, which is able to learn without knowing the number of significant shifts. It comes with an upper bound on the dynamic regret. This bound and the hardness result on the learnability in case one of SST and STI are violated (Thm 3) are highly non-trivial results. Mostly, the paper and proofs are written in a convenient way.

Weaknesses

- Unfortunately, this paper does not provide any experiments. Why not? - You say (e.g. in your conclusion and in 174ff.) that one cannot achieve a dynamic regret of order $O(\sqrt{K\tilde{L}T})$ outside of $SST \cap STI$. However, you only prove that non-linear dynamic regret can not be avoided in a worst-case sense (!) under $STI \setminus SST$ and under $SST \setminus STI$. This (a) does not formally imply any worst-case hardness result in case none of SST and STI is fulfilled, right?, and (b) does not exclude existence of a class X' outside $SST\cap STI$ where $O(\sqrt{K\tilde{L}T})$ is achievable. - 162: The constant C in (3) is required to implement and execute Algorithm 2. Do you already provide it somewhere? If so, please state it here, otherwise, provide it. - 516: $c_1$ is not given, so $\mathcal{E}_1$ is not well-defined. - Sec. 3 is called 'Hardness of significant shifts...'. However, Thm. 3 shows a negative result for a scenario with no significant shifts. How are the section title and Thm. 3 related? Minor remarks, questions and typos: - 135: Why do you write $\succeq$ instead of $\succ$? - 196: It seems as if METASWIFT has not been properly introduced yet. - 470: KL [divergence] - 477: ")" missing - 488: observations - 506: Sec. 6? - 506: a_t^\# is defined in Sec. 6, but not in the App. B - 536: Sec. 6 - In Algo 2: Refer for the definition of $B_{s,m}$ to Algo 1

Questions

- You have proven in Thm. 4 an upper regret bound. What could you say about a lower bound? How sharp is your bound? - 162: Can Thm. 3 be generalized to hold for fixed K>3?

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, 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

The authors adequately addressed the limitations of their work.

Summary

This work studies the problem of a non-stationary bandits problem. First of all, the hardness of dynamic regret minimization under significant shifts problem without SST+STI condition is discussed. Then, with such additional conditions, an algorithm is proposed with a regret of $O(\sqrt{KLT})$. An innovative arm selection strategy which maintains a set of low regret arms is used in replacement of those greedily picking the best arm so far in static environments.

Strengths

The proposed method differentiates itself with conventional arm selection strategy in stationary environments by maintaining an acceptable level of regret of order $O(\sqrt{KT})$ and simultaneously monitoring the change of the environment. This work may have significant use case compared to stationary algorithms given the fact the in real-life scenarios the environment is always changing.

Weaknesses

Simulation study on two cases might deepen the understanding of the proposed method: Although orderwise the same, a comparison between stationary method and this work under static settings can reveal the overhead, and a comparison of the existing work such as [10] with the proposed method should verify the K factor. Given this line of research usually does not carry empirical result and is of theoretical nature. This is just a nice to have suggestion.

Questions

See weakness.

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

4 excellent

Presentation

3 good

Contribution

4 excellent

Limitations

The limitations are well discussed in the paper.

Summary

This paper addresses the problem of dueling bandits with distribution shifts in preferences. The authors investigate the possibility of designing an adaptive algorithm with dynamic regret that depends on the number of significant shifts in preferences. They provide an impossibility result for well-studied preference distributions and show that it is possible to design such an algorithm under certain conditions. The paper introduces novel algorithmic approaches, including the SWIFT and METASWIFT algorithms, and contributes to the understanding of regret bounds in switching dueling bandits. The authors also discuss the difficulty of efficient exploration in non-stationary dueling bandit problems and suggest the need for smarter exploration strategies to achieve optimal regret bounds. Overall, the paper presents theoretical results, algorithmic solutions, and future research directions in the field of dueling bandits.

Strengths

This paper introduces the novel problem of dueling bandits with distribution shifts in preferences, and proposes a unique adaptive algorithm with dynamic regret that accounts for the number of significant shifts in preferences. The authors provide a thorough theoretical analysis, rigorous proofs, and well-designed algorithmic approaches, such as the SWIFT and METASWIFT algorithms. The paper is well-written, organized, and presents clear explanations and detailed pseudocode, making it easy for readers to understand and replicate the experiments. The authors’ contributions advance the state-of-the-art in dueling bandits and provide valuable insights for researchers and practitioners. Overall, this paper demonstrates originality, quality, clarity, and significance in its contributions to the field of computer science.

Weaknesses

The paper would benefit from the inclusion of empirical evaluation to complement its theoretical analysis. The authors should conduct extensive experiments on a wider range of datasets and problem instances to validate the performance of the proposed algorithms in practical scenarios. Additionally, it would be valuable for the authors to provide insights into the computational complexity and scalability of the algorithms, as these are important aspects for assessing the practical relevance of their work. Another weakness is the unclear explanation of the innovation in theoretical analysis. The authors mentioned in section 1.1 the innovation of their algorithm compared to previous work, but did not discuss how their theoretical analysis differs from existing techniques, especially in the proof analysis where some techniques from [10] and [30] were used. The authors should clearly explain the innovation in theoretical analysis and highlight the novelty and importance of their contributions in this aspect.

Questions

Please refer to weaknesses.

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, 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

The paper does not explicitly discuss the limitations of the proposed algorithms or the potential negative consequences that may arise from their application.

Thanks

Thank you for the response. My concerns are addressed.