Variance-aware Regret Bounds for Stochastic Contextual Dueling Bandits

Thank you for your valuable feedback. We address your questions point-by-point as follows.

Q1: Comparison with SAVE in [1] and algorithms for generalized linear bandit problem.

A1: Compared with SAVE, the main difference is that we consider the problem in the generalized linear model and dueling bandit setting, which has not been studied in the literature before. Note that SAVE is for linear bandits, rather than generalized linear (dueling) bandits. The nonlinearity of the problem requires us to consider MLE instead of linear regression. Since the linear regression problem has a closed-form solution, the analysis of MLE is more difficult.

Compared with the generalized linear bandit, there is a key difference. You cannot simply regard $\mathbf{x} _ t- \mathbf y _ t$ as the feature vector to reduce dueling bandits to multi-armed bandits. Note that the regret in dueling bandits is defined as $\text{Regret}$ $(T) = \sum _ {t}$ $(\mathbf x _ t+ \mathbf y _ t)^\top \boldsymbol{\theta}^*$ $- 2 \mathbf x ^ {*\top} \boldsymbol{\theta} ^ *$. In this definition, the regret depends on $\mathbf x _ t+ \mathbf y _ t$ rather than $\mathbf x _ t- \mathbf y _ t$, i.e., it aims at minimizing the regret caused by both arms. This distinction poses a challenge for dueling bandit algorithms, necessitating a design that differs from the generalized linear bandit algorithm.

Q2: Typos and minor issues: title of subsection 4.3 (sysmmetric -> symmetric) I may overlook. What is $\kappa$ in line 20 Algorithm 1 and Eqn. (4.3)?

A2: Thanks for pointing out the typos. $\kappa$ is the same as $\kappa_\mu$. We have revised them.

Q3: Is the variance of the noise equal to under the Bernoulli setting? In that case I feel the variance would be fully dependent on the arms selected in each round.

A3: Yes, the noise equals $p_t(1-p_t)$ under the Bernoulli setting, and it depends on the arm being selected in each round. We study the problem in a general case where the arm set is time-varying and therefore the variance of arms can vary with respect to time and arms. Therefore, the variance $p_t(1-p_t)$ in each round is influenced by both the historical data and the potentially adversarial arm set $\mathcal{A}_t$ in round $t$. Our result indicates that the regret of the problem should depend on the variance of the selected arms, which aligns with our intuition that comparing high-variance dueling arms pose a greater challenge than comparing lower-variance dueling arms.

[1] Zhao et al., 2023, Variance-dependent regret bounds for linear bandits and reinforcement learning: Adaptivity and computational efficiency, COLT

Thank you for your positive feedback. We address your questions below.

Q1: Performance of the algorithm on real-world datasets.

A1: To showcase the performance of our algorithms in a real-world setting, we have added a new experiment in Appendix B. We use EventTime dataset [1]. In this dataset, $K = 100$ historical events are compared in a pairwise fashion by crowd-sourced workers. The data contains binary response indicating which one of the events the worker thinks precedes the other. There is no side information $\mathcal A = \\{ \mathbf x_i, i \in [K] \\},$ or the true parameter $\theta^*$ readily available in the dataset. Thus, we estimate them with pairwise comparison data. To achieve this, let $C_{ij}, i,j \in [K]$ be the number of times event $j$ precedes event $i$ labeled by the workers. The following MLE estimator is used:

With the estimated $\mathcal A$ and $\theta^*$, it is then possible to simulate the interactive process. We can see that after about $2500$ rounds, our algorithm starts to outperform $`MaxInP`$ in terms of cumulative regret.

Q2: The paper could benefit from a more thorough discussion on how the layered design in $`VACDB`$ specifically contributes to or differs from existing approaches.

A2: Thanks for your suggestion. We have provided a detailed discussion in Appendix A in our revision. Our approach is different in the elimination phase, where we construct our confidence set with a variance adaptive radius to determine the confidence radius (lines 10-12). Therefore, besides the layer number, our algorithm also leverages the variance information in the exploration. Moreover, we construct a carefully chosen weight dependent on the layer (line 15). It is used in the calculation of the regularized MLE estimator.

Q3: Computation of the MLE estimators grows in complexity with the number of iterations.

A3: The MLE estimator is widely used in the literature of generalized linear bandit and dueling bandits, such as [2] and [3]. Although the calculation can be expensive in some cases, there are some literally tractable solutions to that. The regularized MLE can be formulated as a finite-sum offline optimization problem. For many widely used models, such as the Bradley-Terry-Luce (BTL) model, the regularized MLE is a strongly convex and smooth optimization problem. We can solve it using accelerated gradient descent [4] and SVRG [5], both of which achieve a linear rate of convergence. This can mitigate the scalability issues caused by the increasing number of iterations. The regularized MLE estimator can also be solved by an online learning algorithm such as in [6,7].

Q4: There is a minor typo on the second line of Introduction: "arm" -> ``arm"

A4: Thanks for pointing that out. We have revised it.

[1] Zhang et al., 2016, Crowdsourced top-k algorithms: An experimental evaluation. VLDB.

[2] Li et al., 2017, Provably optimal algorithms for generalized linear contextual bandits, ICML

[3] Saha 2021, Optimal algorithms for stochastic contextual preference bandits, NeurIPS

[4] Nestorov 2003, Introductory lectures on convex optimization: A basic course,

[5] Johnson & Zhang, 2013, Accelerating Stochastic Gradient Descent using Predictive Variance Reduction, NeurIPS

[6] Jun et al., 2017, Scalable generalized linear bandits: online computation and hashing. NeurIPS

[7] Zhao et al., 2023, Optimal online generalized linear regression with stochastic noise and its application to heteroscedastic bandits, ICML

Thank you for your valuable feedback. We address your questions as follows.

Q1: The variance in the regret bound is a random variable. I think it would be much better to involve a term that indicates the variance of the instance in some sense but is not random in an expected bound. We may not know the value of the derived upper bound when knowing the exact model.

A1: Yes, the randomness of the variance is from the arm being chosen in each round, which further depends on historical data. The setting we study is quite general where the arm set is time-varying and therefore the variance of arms can vary with respect to time and arms. That’s why the regret depends on a random variable representing the variance of the chosen arms in each round. We view this as a strength rather than a weakness of our regret bound.

When we restrict our setting to a special case where the variances for all the pairwise comparisons are identical, the randomness of $\sigma_t^2$ can be removed in the regret bound. But this is similar to the worst-case regret implied by our variance-aware regret.

Q2: Is it possible to derive a lower bound for the problem?

A2: We study this problem in a general setting where the variance of instances can vary over time and across different arms. In this context, a variance-dependent lower bound is difficult and not found even in the literature on stochastic bandit settings. Deriving that lower bound stands as an open problem. The proof is challenging especially when the variance can change over time. For example, consider a scenario where initially there is no variance, but later, substantial variance emerges. In such cases, accurate early exploration could make correct policies, effectively mitigating the impact of later variance. However, the variance-dependent regret bound in the literature does not inherently possess this characteristic. In general, we are not sure if it is possible, and leave it as an interesting future work.

Although getting a lower bound in the general case is hard if not impossible, we can show our optimality in two special cases:

(1) when we consider the worst case, the variance is upper bounded by $1/4$, our result matches the $d\sqrt{T}$ lower bound proved in [1]; and (2) when the preference is deterministic, our result is $\tilde O(d)$, which is also nearly optimal.

[1] Bengs et al., 2022, Stochastic contextual dueling bandits under linear stochastic transitivity models, ICML

Thank you for your strong support. We address your question as follows.

Q1: The paper is not self contained and requires the reader to go through multiple papers for example in section 4.2.

A1: Thanks for your suggestion. In the main text, we have added Section 4.1 to give an overview of the algorithm and introduce the multi-layered structure in more detail. We have also added Appendix A to provide a detailed introduction to our algorithm and a comparison with previous works.