Variance-aware Regret Bounds for Stochastic Contextual Dueling Bandits
Authors: Qiwei Di
Tao Jin
Yue Wu
Heyang Zhao
Farzad Farnoud
Quanquan Gu
Venue: ICLR 2024 poster (2024)
Keywords: Dueling Bandit
Variance-aware
contextual bandit
Primary area: reinforcement learning
TL;DR: We study the problem of dueling bandit and prove a variance-aware regret bound.

Abstract: Dueling bandits is a prominent framework for decision-making involving preferential feedback, a valuable feature that fits various applications involving human interaction, such as ranking, information retrieval, and recommendation systems. While substantial efforts have been made to minimize the cumulative regret in dueling bandits, a notable gap in the current research is the absence of regret bounds that account for the inherent uncertainty in pairwise comparisons between the dueling arms. Intuitively, greater uncertainty suggests a higher level of difficulty in the problem.  To bridge this gap, this paper studies the problem of contextual dueling bandits, where the binary comparison of dueling arms is generated from a generalized linear model (GLM). We propose a new SupLinUCB-type algorithm that enjoys computational efficiency and a variance-aware regret bound $\tilde O\big(d\sqrt{\sum_{t=1}^T\sigma_t^2} + d\big)$, where $\sigma_t$ is the variance of the pairwise comparison at round $t$, $d$ is the dimension of the context vectors, and $T$ is the time horizon. Our regret bound naturally aligns with the intuitive expectation — in scenarios where the comparison is deterministic, the algorithm only suffers from an $\tilde O(d)$ regret. We perform empirical experiments on synthetic data to confirm the advantage of our method over previous variance-agnostic algorithms.

Published as a conference paper at ICLR 2024
VARIANCE-AWARE REGRET BOUNDS FOR STOCHASTIC CONTEXTUAL DUELING BANDITS
Qiwei Di Tao Jin Yue Wu', Heyang Zhao', Farzad Farnoud 2 Quanquan Gulf 'Department of Computer Science. University of California, Los Angeles
*Department of Computer Science, University of Virginia
qiwei2000@cs, ucla. edu, tao taoj@virgini... edu, ywuêcs uula.ellaaa. hyzhao@cs wela edu, farzadevirgin edu, qquêes ucla.edu
ABSTRACT
Dueling bandits is a prominent framework for decision-making involving prefer- ential feedback, valuable feature that fits various applications involving human interaction, such as ranking, information retrieval, and recommendation systems. While substantial efforts have been made to minimize the cumulative regret in du- eling bandits, a notable gap in the current research is the absence of regret bounds that account for the inherent uncertainty dueling arms. Intuitively, greater uncertainty suggests higher level of difficulty in the problem. To bridge this gap, this paper studies the problem of contex- tual ducling bandits, where the binary comparison of ducling arms is generated from a generalized linear model (GLM). We propose a new SupLinUCB Linteee algorithm that enjoys computational efficiency and variance-aware regret bound
pairwise comparisons between the
Ö(d E of +d), where o, is the variance of the pairwise comparison round t, d is the dimension of the context vectors, and the time horizon. Our regret bound naturally aligns with the intuitive expectation in scenarios where the comparison is deterministie, the algorithm only suffers from an Ö(d) regret. We perform empirical experiments on synthetic data to confirm the advantage of our method over previous variance-agnostic algorithms.
INTRODUCTION
The multi-armed bandit (MAB) model has undergone comprehensive examination as framework for decision-making with uncertainty. Within this framework, an agent has to select one specific "arm" " pull in each round, and receives stochastic reward feedback. The objective is maximize the cumulative reward accumulated over all rounds. While the MAB model provides a robust foundation for various applications. the reality that many real-world tasks present an intractably large action space coupled with intricate contextual information. Consequently, this challenge has led to the proposal of the (linear) contextual bandit model, where the reward intricately linked both the context associated with the selected arm and the underlying reward function. A series of work into the linear contextual bandits has led to efficient algorithms such as LinUCB (Li al. 2010 Chu
et al. 2011) and OFUL (Abbasi- Yadkori et al. (2011).
In scenarios where feedback is based on subjective human experiences phenomenon evident in fields such as information retrieval (Yue & Joachims 2009), ranking (Minka et al., 2018). crowd- sourcing (Chen et al. 2013), and Reinforcement Learning from Human Feedback (RLHF) (uyang et al.) 2022) preferential choices emerge as a more natural and intuitive form of feedback compared with numerical evaluations. The rationale behind preference feedback lies in the fact that numerical scores can exhibit significant variability among individuals, resulting in noisy and poorly calibrated rewards. On the contrary, binary signal from preferential feedback remains independent of scale and is thus more reliable. This distinction gives rise to a specialized variant of the MAB problem known as dueling bandits (uue et al. 2012). In this setting, the agent simultancously pulls two arms and receives binary preferential feedback, which essentially indicates the outcome of a comparison between the chosen arms. A line of works proposed efficient and practical algorithms for multi-armed dueling bandits based on upper confidence bound (UCB) (Zoghi et al.) 2014 2015) or Thompson
"quual Contribution Co-corresponding Authors

---

Published as a conference paper at ICLR 2024
sampling (Wu & Liu 2016). Similar to linear contextual bandits, considerable effort has been invested in developing efficient algorithms that minimize the cumulative regret for the contextual dueling bandits (Saha 2021 Bengs et al.. 2022).
Intuitively, the variance of the noise in the feedback signal determines the difficulty of the problem. To illustrate, consider an extreme case, where the feedback of a linear contextual bandit is noiseless (i.e., the variance is zero). A learner can recover the underlying reward function precisely by exploring each dimension only once, and suffer a O(d) regret total, where is the dimension of the context vector. This motivates a series of works establishing variance- regret bounds for multi-armed bandits, c.g. (Audibert et al. 2009, Mukherjee et al. 2017) and contextual bandits, c.g. (Zhou et al. 2021 Zhang et al. 202 lb| Kim et al. 2022 Zhao al. 2023b a). This observation also remains valid when applied to the dueling bandit scenario. In particular, the binary preferential feedback is typically Bernoulli distribution, with the mean value denoted by p. The variance reaches its maximum when p is close to 1/2, a situation that undesirable in human feedback applications, it indicates high level of disagreement or indecision. Therefore, maintaining a low variance in comparisons is usually preferred, and variance variance-dependent dueling algorithms are desirable because they can potentially perform better than those algorithms that only have worst-case regret guarantees. This leads to the following research question:
assumed to adhere
Can we design dueling bandit algorithm with a variance-awan regret bound?
We give an affirmative answer to this question by studying the dueling bandit problem with contextualized generalized linear model, which is in the same setting as Saha (2021); Bengs et al. (2022). We summarize our contributions as follows:
We propose a new algorithm, named VACDB, to obtain a variance-aware regret guarantee. This algorithm is built upon several innovative designs, including (1) adaptation of multi-layered estimators to generalized linear models where the mean and variance are coupled (i.e., Bermoulli distribution). (2) symmetric arm selection that naturally aligns with the actual reward maximization objective in dueling bandits.
We prove that our algorithm enjoys a variance-aware regret bound Öd Σi= of + d)) where or is the variance of the comparison in round t. Our algorithm is computationally efficient and does not require any prior knowledge of the variance level, which is available in the dueling bandit scenario. In the deterministic case, our regret bound becomes (dd), showcasing a remarkable improvement over previous works. When the variances of the pairwise comparison are the same across different pairs of arms, our regret reduces to the worst-case regret of OdvTT), which matches the lower bound (dVV)) proved in Bengs al. (202))
We compare our algorithm with many strong basclines on synthetic data. Our experiments demon- strate the empirical advantage of the proposed algorithm in terms of regret and adaptiveness when faced with environments with varying variances.
As an additional outcome of our research, identified an unrigorous argument in the existing analysis of MLE for generalized linear bandits. To rectify this issue, we provide a rigorous proof based on Brouwer's invariance of domain property (Brouwer 1911). which discussed further in Appendix D
Notation In this paper, we use plain letters such as J to denote scalars, lowercase bold letters such as x to denote vectors and uppercase bold letters such as X to denote matrices. For a vector x, ||x||2 denotes its fo-norm. The weighted -oom associated with a positive-defintte matrix is defined as ||x||A = vx Ax. For two symmetric matrices A and B, we use A > B to denote A - B is positive semidefinite. We use to denote the indicator function and 0 to denote the zero vector. For a postive integer N, we use [N] to denote (1, 1.,.....,0 N). We use X1a to denote the set (x (xs). We use standard asymptotic notations including O()), (()), and ((), Õ(-) will hide logarithmic factors.
2 RELATED WORK
Multi--Armd Bandits and Contextual Bandits. The multi-armed bandit problem involves an agent making sequential decisions among multiple arms based on the observation of stochastic reward, with the goal of maximizing the cumulative rewards over time. has been widely studied, including
works such as Lai et al. (1985): Lai (1987); Auer 2002): Auer al. 2002); Kalyanakrishnan et al.
2

---

Published as a conference paper at ICLR 2024
(2012); Lattimore & Szepesvári (2020); Agrawal & Goyal 2012). To deal with large decision spaces with potentially infinitely many actions or to utilize contextual information, extensive studies have been conducted in contextual bandits. Some work focused on contextual linear bandits, where the mean reward of an arm is a linear function of some feature vectors, including algorithms such as LinUCB/Supp UCBB (Chu al., ( OFUL (Abbasi-Yadkori et al. [20TT). Other works, such as Filiippi et al. 2010 Li et al.) 2017 Jun et al., 2017). studied the generalized linear bandits where the mean reward is from generalized linear model (GLM).
bandits, where the stochastic reward is replaced by a pairwise preference. This model was first proposed in Yue et al. (2012). Many works (Zoghi et al. 2014, Komiyama et al., 2013) studied this problem, assuming the existence of a Condorcet winner, which is one arm that beats all the other arms. There are also works on other types of winners such as Copeland winner (Zoghi et al., 2015 Wu & Liu 2016 Komiyamal ct al. 2016), Borda winner (Jamieson et al. 2015 Falahatgar et al., 2017 Heckel et al., 2018 (ahaa
Dueling Bandits. The problem of dueling bandits a variant of the
ct al., 2021; Wu et al. 2023) and von Neumann winner (Ramamohan et al. 2 et al.) 2015]]
Balsubramani et al. 2016). Similar to the idea of contextual bandits, some works considered regret
minimization for dueling bandits with context information. Kumagai (2017) studied the contextual dueling bandit problem where the feedback is based on cost function. They proposed a stochastic mirror descent algorithm and proved the regret upper bound under strong convexity and smoothness assumptions. Saha (202I) proposed algorithms and lower bounds for contextual preference bandits with logistic link function, considering pairwise and subsetwise preferences, respectively. [engg) et al. 2022) further extended to the contextual linear stochastic transitivity model, allowing arbitrary comparison function, and provided efficient algorithms along with matching lower bound for the weak regret. For recent comprehensive survey of dueling bandits, please refer to |Bengs et al. (202T). Our work studies the same model as Saha (202T); [Bengs et al. (202T).
Variance-Aware Bandits. It has been shown empirically that leveraging variance information in multi-armed bandit algorithms can enjoy performance benefits (Auer et al. 2002). In light of this. Audibert et al. (009) proposed an algorithm, named UCBV, which is based on Bernstein's ' inequality equipped with empirical variance. It provided the first analysis of variance-aware al- gorithms, demonstrating an improved regret bound. EUCBV Mukkerree et al.] (2017) is another variance-aware algorithm that employs an elimination strategy. It incorporates variance estimates to determine the confidence bounds of the arms. For linear bandits, (Zhou al. (2021) proposed Bernstein-tyre type concentration inequality for self-normalizz named We i iightttee ed OFUL. This approach used a weighted ridge regression scheme, using variance to discount each sample's 's contribution to the estimator. In particular, they proved a variance-dependent regret upper bound, which was later improved by Zhou & Gul 2002). These two works assumed the knowledge of variance information. Without knowing the variances, Zhang et al. (2021a) and Kim ct al. (2022) obtained the variance-dependent regret bound by constructing variance-aware confidence sets. (Zhao et al. 2023b) proposed an algorithm named MOR- UCB with the idea of partitioning the observed data into several layers and grouping samples with similar variance into the same layer. A similar idea was used in Zhao et al. (2023a) to design SupLin-type algorithm SAVE. It assigns collected samples to T. layers according to their estimated variances, where each layer has twice the variance upper bound as the one at one level lower. In this way, for each layer, the estimated variance of one sample is at most twice as the others. Their algorithm is computationally tractable with a variance-dependent regret bound based on a Freedman-type concentration inequality and adaptive variance-aware exploration.
martingales and designed an algorithm
3 PROBLEM SETUP
In this work, we consider a preferential feedback model with contextual information. In this model, an agent learns through sequential interactions with its environment over series of rounds indexed by I, where L E [7'] and T is the total number of rounds. In each round 4, the agent is presented with a finite set of alternatives, with each alternative being characterized by its associated feature in the contextual set A, C Rd. Following the convention in bandit theory, we refer to these alternatives as arms. Both the number of alternatives and the contextual set A, can vary with the round index 1. Afterward, the agent selects pair of arms, with features (x,, y:) respectively. The environment then compares the two selected arms and returns a stochastic feedback o,, which takes a value from the set {0, 1). This feedback informs the agent which arm is preferred: When o 1 (resp. o, 0), the arm with feature x, (resp. y:) wins.
We assume that stochastic feedback o, follows a Bermoulli distribution, where the expected value Pt is determined by a generalized linear model (GLM). To be more specific, let nu-)) be fixed link
3

---

Published as a conference paper at ICLR 2024
function that is increasing monotonically and satisfies ju(z) + (x)=)) = 1. We assume the existence of an unknown parameter 0 E IRd' which generates the preference probability when two contextual vectors given, i.c.
P(o: 1) Parm with x is preferred over arm with y+) - Pt - pl((x, yo) O0)).
This model is the same the linear stochastic transitivity (LST) model in Bengs et al. (2022), which includes the Bradley-Tenee Teey-Terry-Lue (BTL) model (Hunter 2003 Luce 1959). Thurstone- Mostellle model (Thurstone) 1994) and the exponential noise model as special examples. Please refer to Bengs et al. (022) for details. The preference model studied in Saha 2021 can be treated as a special case where the link function is logistic.
We make the assumption on the boundness of the true parameter 0* and the feature vector.
Assumption 3.1. ||0*||2 < 1. There exists constant A > 0 such that for all / E [T] and all x E A.. ||x|| S A.
Additionally, we make the following assumption on the link function μ., which is common in the study of generalized linear contextual bandits (Filippi et al. 2010 Li et al. 2017).
Assumption 3.2. The link function μs is differentiable. Furthermore, the first derivative ji satisfies Ri S (()) < Ty for some constants Tugs Rig > 0.
We define the random noise e, O₁ Ps. Since the stochastic feedback o, adheres to the Bernoulli
distribution with expected value Pt, E, E {-Pt, - -P... From the definition of eg, we can see that
|ea] $ 1. Furthermore, we make the following assumptions:
E|cg|x1aa3 V1... 11--1 0, ((c/) Vu:e: (1=-1] o/.
Intuitively, reflects the difficulty associated with comparing the two arms:
When pt is around 1/2, it suggests that the arms are quite similar, making the comparison challeng- ing. Under this circumstance, the variance tends toward a constant, reaching a maximum value of 1/4.
On the contrary, pt approaches 0 or signals that arm is distinctly preferable over the other, thus simplifying the comparison. In such scenarios, the variance a, decreases significantly toward 0.
The learning objective is to minimize the cumulative average regret defined as
1 T 2
Regret (T)
2x 0" - (x, + T.) 0*),
(3.1)
where x; arg A x 0" is the contextual/feature vector of the optimal arm in round t. This definition is the same the average regret studied in (Saha, 2021 Bengs et al., 2022). Note that in Bengs et al. (2022), besides the average regret, they also studied another type of regret, called weak regret. Since the weak regret is smaller than the average regret, the regret bound proved in paper can immediately imply a regret bound defined by the weak regret.
4
ALGORITHM
4.1
OVERVIEW OF THE ALGORITHM
In this section, present algorithm named VACDB in Algorithm Our algorithm shares a similar structure with Sta' D in Saha (2021) and SuPCoLSTIM in [engs et al. (2022). The core of our algorithm involves a sequential algorithm conducts arm selection with a layered elimination procedure. Arms are progressively eliminated across layers, with increased exploration precision in the subsequent layers. Starting at layer = 1. our algorithm incorporates loop comprising three primary conditional phases: Exploitation (Lines 9.. Flimination (Lines TO 12 and Exploration (Lines 14 16). When all arm pairs within particular layer have low uncertainty, the elimination procedure begins, dropping the arms with suboptimal estimated values. This elimination process applies an adaptive bonus radius based on variance information. A more comprehensive discussion can be found in Section 4.3 Subsequently, it advances to a higher layer, where exploration is conducted over the eliminated set. Upon encountering layer with arm pairs of higher uncertainty than desired, them and receives the feedback. Once comprehensive exploration has been achieved across layers and the uncertainty for all remaining arm pairs is small enough, our algorithm leverages the estimated
elimination process: from Line to Line 18] our
algorithm explores
4

---

Published as a conference paper at ICLR 2024
Algorithm 1 Variance-Aware Contextual Dueling Bandit (VACDB)
1: Require: 0. L (log(1/oo) Mis Lu-
2: Initialize: For L E [4], Σ1, +- 2 I,, 01. t 0, Vi + 0. 2 1/kj))
3: for 1,..., do
4: Observe Ar
5: Let Ar,1 Ar. +
6: while Xt. are not specified do
7:
if X yell -xy--
S a for all Xt, E Ar, then
8:
Choose Xx, Yr = argmax
(x+ To, - Br y
and observe or 1(x; > ye)
//Exploitation Keep the same index sets at all layers: 1,1,0 + v for all ll E'E [L]
(Lines
9:
10:
else if X vells S -- for all Xr, E Ar, then
e
A Ar,+1 + X Ar,e xx 1x= 2 ma x' TT 2-
11:
12:
f=1+1
//Elimination (Lines
10
13:
else
14:
Choose Xt, Vr such that |x - -ells > 2
and observe o (x > yr)
/ //Exploration (Lines
14 1 6
Compute the weight we 2 1 yells,
16:
Update the index sets 11+1, ve, U {1} and V411, Ver for all l' (4) end if end while
17:
19:
For l E [4] such that MitII # Lr,, update E.t1.e + Eee + +ff wf(x: - yx)( - y.)
20:
Calculate the MLE θ.+1, by solving the equation:
2-2 R +
w ()
- -))) - -0s -x))(x
- yys)
Compute 3. according
443
22: For l E [4] such that Vi+1. = r,e, let Eet1. = Er,e. O 4.1 + Br,,, + Br.e
end for
parameters in the last layer to select the best arm from the remaining arms. For a detailed discussion of the selection policy, please refer Section 4.4 After arm selection in the exploration phase, the
estimator of the current layer is updated (Lines 19 22) using the regularized MLE, which will be discussed in more details in Section 4.2 Note that our algorithm maintains index V/ V,, for each layer, comprising all rounds before round t when the algorithm conducts exploration in layer l. As result, for each exploration step, only of the estimators Or.e needs to be updated. Furthermore, our algorithm updates the covariance matrix Σ,,e used estimate uncertainty (Line 19 4.2 REGULARIZED MLE
Most of the previous work adopted standard MLE techniques to maintain estimator of 0* in the generalized linear bandit model (Filippi et al. 2010 Li et al. 2017). which requires an initial exploration phase ensure balanced input dataset across F. for the MLE. In the ducling bandits setting, where the feedback in each round can be seen as generalized linear reward, [ahha (2021): Bengs et al. (202) also applied similar MLE in their algorithms. As result, a random initial exploration phase is also inherited to ensure that the MLE equation has a unique solution. However, in our setting, where the decision set varies among rounds and is even arbitrarily decided by the envi- ronment, this initial exploration phase cannot be directly applied to control the minimum eigenvalue of the covariance matrix.
To resolve this issue, we introduce a regularized MLE for contextual dueling bandits, which is more well-behaved in the face of extreme input data and does not require an additional exploration phase at the starting rounds. Specifically, the regularized MLE the solution of the following equation:
X0 Σ w (p((x, To) 0.) 2x) -ya)
(4.1)
5

---

Published as a conference paper at ICLR 2024
where add the additional regularization term X0 to make sure that the estimator will change mildly, From the theoretical viewpoint, our proposed regularization term leads to non-singulari -innuuull guarantee for the covariance matrix. Additionally, inequality. Concretely, with a suitable choice of the parameters in each layer and a Freedman-type inequality first introduced in Zhao et al. (2023)), we can prove concentration inequality for the estimator in the é-th layer:
add some weights here obtain a tighter concentration
Kpp 2 16 Eoev, w6o log(4{116)) + 6log(4(21/6) + +2
0- - 0.0
(4.2)
S.,
This upper bound scales with 2- which arises from our choice of the weights.
The regularized MLE can be formulated as finite-sum offline optimization problem. For many widely used models, such as the Bradley-Terry- Luce (BTL) model (Hunter) 2003 Luce 1959), the regularized MLE is a strongly convex and smooth optimization problem. We can solve if using accelerated gradient descent (Nesterov) 2003) and SVRG (Johnson & Zhang 2013), both of which achieve linear rate of convergence. This can mitigate the scalability issues caused by the increasing number of iterations. The regularized MLE can also be solved by online learning algorithm such as in Jun et al. (2017) and /Zaa et al. 2023b). where additional effort is required for the analysis. 4.3
MULTI-LAYER STRUCTURE WITH VARIANCE-AWARE CONFIDENCE RADIUS
Due to the multi layei- structure our algorithm, the construction of the confidence paramount importance. Our algorithm distinguishes itself from prior multi-layered algorithms (Saha 2021 Bengs et al. 2022) primarily through a variance-aware adaptive selection of the confidence radius, which helps to achieve variance-aware regret bound. Intuitively, we should choose the confidence radius Be, based the concentration inequality (42)). However, it depends on the true variance os, of which we do not have prior knowledge. To address this issue, we estimate it using the estimator Oz.E. We choose
of
,
16 26.2-
V (sVarr, + 18 log((4 1))(((((+)))LL)))) log(4f2L/8)
Kyp
6 2
log( log(4t"L/8) + 2
(4.3)
Kp
where
-p((x, (x)x,,)))TOr.))) 2' (l /lg(() 1)2L/8),
Varg,
otherwise.
The varied selections of Var,, arise from the fact that variance estimator becomes more accurate at higher layers. For those low layers, we employ the natural upper bound a; 1. Note that this situation arises only (log log(T/o)) times, which is small portion of the total layers L = (log T). In our proof, we deal with two cases separately. Due to the limited space available here, the full proof can be found in Appendix E
4.4 SYMMETRIC ARM SELECTION
In this subsection, we focus on the arm selection policy described in Line 9 To our knowledge, this policy new and has never been studied prior work for the (generalized) linear dueling bandit problem. In detail, suppose that we have an estimator 0, in round t that lies in a high probability confidence set:
(0: 0 11 S 3
where E, = AI Ef (x)(x: - T. Our choice of arms can be written as
Xt.Yt argmax X.EEA.
(x y) TTTT, 0, 3,1lxx vl1s,*]
(4.4)
Intuitively, we utilize (x + TO as the estimated score and incorporate an exploration bonus dependent on ||x - yl|s,11. Our symmetric selection of arms aligns with the nature of dueling bandits
where the order of arms does not matter. Here we compare with several alternative arm selection criteria that have appeared in previous works.

---

Published as a conference paper at ICLR 2024
The MaxInP algorithm in Saha (0021) builds the so-called "promising" set that includes the optimal arm:
C.
{x x A. (x y) B,|1x -yl
V, 0, E.
It chooses the symmetric arm pair from the set C, that has the highest pairwise score variance (maximum informative pair), i.e.,
Xt
argmax ||-->|xx,"* x.yEC,
yllx,"
The Sta' D algorithm in Saha 1021 first arm with the highest estimated score, i.c.,
asymmetric arm selection criterion, which selects the
argmax Oz.
X
Following this, selects the second arm as the toughest competitor to the arm x,, with bonus term related to |x yllx,1, 1 i.c.,
Y1 argmaxy TØ + 2Bel - YlE,," yEA.
(4.5)
Similar arm selection criterion has also been used in the CoLSTIM algorithm (Bengs et al. 2022 We can show that these two alternative arm selection policies result in comparable regret decomposition and can establish similar regret upper bound. A more detailed analysis can be found in Appendix
5
MAIN RESULTS
5.1
VARIANCE-AWARE REGRET BOUND
In this section, we summarize our main results in the following theorem.
Theorem 5.1. If we set a 1/(13/2), then with probability least 28, the regret of Algorithm ! is bounded as
Regret(T) = d Ky
T Σ o + d
12
ky 2
This regret can be divided into two parts, corresponding to the regret incurred from the exploration steps (Line 14 and the exploitation steps (Line 8). The exploitation-indueed regret is always O(1) shown in (5.1), and thus omitted by the big-O notation. The total regret is dominated by the exploration-induced regret, which mainly depends on the total variance T of. Note that the comparisons during the exploration steps only happen between non-identical arms (x, y:).
Remark 5.2. To show the advantage of variance awareness, consider the extreme case where comparisons are deterministic. More specifically, for any two arms with contextual vectors x and y, the comparison between arm x and item y is determined by o, = {x, 0- y: 0 }. and thus has zero variance. Our algorithm account for the zero variance, and the regret becomes (dd). which is optimal since recovering the parameter 0* e Rd requires exploring each dimension.
Remark 5.3. The setting study is quite general, where the arm set is time-vary -arryinn and therefore, the variance of arms can vary with respect to time and arms. When we restrict our setting to a special case with uniform variances for all pairwise comparisons, i.e., of o² for all I, our upper bound becomes ((od/T). This results in a regret bound that does not depend on the random variable o? Remark 5.4. In the worst-case scenario, the variance of the arm comparison is upper bounded by 1/4, our regret upper bound becomes Ö(dVT), which matches the regret lower bound ((dvT) for dueling bandits with exponentially many arms proved in Bengs et al. (2022) ) up to logarithmic factors. This regret bound also recovers the regret bounds of MaxInP Saha 2021 and CoLST IM (Bengs et al. 2022). Compared with St (Sahal 2021) and SupCoLST TM (Bengs et al. 2022). regret bound is par with their regret bounds provided the number of arms K is large. More specifically, their regret upper bounds are Ö( O(vaT log K). When is exponential in d, their regret bound becomes Ö(dvT), which of the same order as our regret bound.
Remark 5.5. Notably, in Bengs et al. (2022), they made assumption that the context vectors span the total d-dimensional Euclidean space, which is essential in their initial exploration phase. In work, replace the initial exploration phase with regularizer, thus relaxing their assumption.
7

---

Published as a conference paper at ICLR 2024
5.2 PROOF SKETCH OF THEOREM 5.1
As we describe Section the arm selection specified two places, the exploration part (Lines) 14 T6) and the exploitation part (Lines 8 19. Given the update rule of the index set, each step within the exploration part will be included by the final index set VT+I,E of singular layer Conversely, steps within the exploitation part get into T/ UEE[2] MT+1,6 Using this division, we can decompose the regret i
1
Regret(T) 2
Σ / 1xxT (x] 0- + +y, 0-)
exploitation
DeEL -x, 0))
exploration
We bound the incurred regret of each part separately.
For any round 8 E T/ Ure[1]] Wr+1,6 the given condition for exploitation indicates the existence of a layer le such that ||x, Yells, S a for all x. A.... Using the Cauchy inequality and ,,
the MLE described in Section 4.2
show that the regret incurred in round is smaller than 3,3.,,, a. Considering the simple upper bound Ba.e, I Ö(VT) and T-3/2, the regret for one exploitation round does not exceed Ó(1/T). Consequently, the cumulative regret is
ExETT//UVe Vr 1.) 2x T 0 - (x, 0 +yTor) s Ō().,
(5.1)
which is a low-order term total regret.
the exploration part, the regret the cumulative regret encountered within each layer. We analyze the low layers and high layers distinctly. For et logz (64(Ln./kp) (r.)) 1)2L00))))))))))
the incurred regret can be upper bounded by the number of rounds in this layer
Eeevra.. (2x; To 0- (x] 0 +y]0*) S 4frr..
Moreover, [T4+, can be upper bounded by
L2 dlog (1 2 AT/d) log (4(T (4(T+1)2
TT+ll S dd (1 2 AT/d) S 0
(5.2)
Thus the total regret for layers < E" is bounded by (d). For l e", we can bound the cumulative regret incurred in each layer with
Lemma 5.6. With high probability, for all E [4] \ {1}, the regret incurred by the index set M bounded by
ExEYriA -xx;T0--xx" +y++) 5(d 2' 2....
By summing up the regret of all the layers, we can upper bound the total regret for layers l Et as
EeE(L E.EVre.e [2x; 0" (x]0 +yIon) < o d V'
We can complete the proof of Theorem 5.] by combining the regret in different parts together. For the detailed proof, please refer to Appendix
EXPERIMENTS
Experiment Setup. We study the proposed algorithm in simulation to compare with those that are also designed for contextual dueling bandits. Each experiment instance is simulated for 7 = 4000 rounds. The unknown parameter 0" to be estimated generated at random and normalized to be a unit vector. The feature dimension is set to d = 5. A total of |Asel 2d distinct contextual vectors generated from {-1, 1]dd In each round, given the arm pair selected by the algorithm, a response is generated according the random process defined in Section 3 For each experiment, total of 128
8

---

Published as a conference paper at ICLR 2024
repeated runs carried out. We tume the confidence radius of each algorithm to showcase the best performance. The average cumulative regret is reported in Figure I along with the standard deviation in the shaded region. The link function p(() is set be the logistic function. Our implementation is publicly available
Algorithms. We list the algorithms studied in this section as follows:
MaxInP: Maximum Informative Pair by Saha (202I). maintains an active set of possible optimal arms each round. The pairs are chosen on the basis of the maximum uncertainty in the difference between the two arms. Instead of using warm-up period To in their definition, we initialize Do AI as regularization. When À = 0.001 this approach empirically has no significant impact on regret performance compared to the warm-up method.
MaxPairUCB: In this algorithm, we keep the MLE the same as MaxInP. However, we eliminate the need for an active set of arms, and the pair of arms that is picked is according to the term defined in
COLSTIM: This method is from Bengs et al. (0022) First, they add randomly disturbed utilitics each arm and pick the arm that has the best estimation. They claim this step achieves better empirical performance. The second arm is chosen according to criteria as defined in (4.5)
VACDB: The proposed variance-ave according to Theorem 5.1 However, we note that for this specific experiment, L = 4 is enough to eliminate all suboptimal arms. The estimated @ in one layer below is used to initialize the MLE of the upper layer when it first reached provide a rough estimate since the data is not shared among layers.
Algorithm I in this paper. is set this theoretical value
Regret Comparison. In Figure la we first notice that the proposed method VACDB has a better regret over other methods on aver- age, demonstrating its efficiency. Second, the EexpPairUCB and COLSTIM algorithm have slight edge over the MaxInP algorithm em- pirically, which can be partially explained by
1.0
Regento
0.0
VICOB
MacharKe
0.2
1000
2001
3000
4900
0
5000
23001
3000
-900
the discussion in Section 4.4 The contributing factor for this could be that in Max InP the cho- sen pair is solely based on uncertainty, while the other two methods choose at least one arm that maximizes the reward.
(a) Compare proposed ab-(b) Variance- Swraence-awareness of gorithm with basclines. the proposed algorithm. Figure 1: Experiments showing regret performance in various settings.
Figure 16 we show the variance awareness of our algorithm by scaling the unknown parameter 0" Note that the variance of the Bernoulli distribution with parameter p is x² = p(1 p). To generate high- and low-variance instances, we scale the parameter 0* by a ratio of a E (0.5, 1,2, 43. If a 1 then p will be closer to 0 or which results in lower variance instance, and vice versa. In this plot, we show the result under four cases where the scale set in an increasing manner, which corresponds to reducing the variance of each arm. With decreasing variance, our algorithm suffers less regret, which corresponds the decrease the oe term in our main theorem.
Variance-Awareness.
CONCLUSION
We introduced variance-awan method for contextual dueling bandits. An adaptive algorithm called VACDB is proposed. Theoretical analysis shows regret upper bound depending on the observed variances in each round. The worst-case regret bound matches lower bound. Additionally, we conduct some simulated studies to show that the proposed algorithm reacts to instances with changing variance implied by the regret analysis. the future, one of the possible directions is to consider a subset-wise comparison: In each round, a subset of size K arms can be chosen from all arms, and the agent can only observe the best arm of the chosen subset. The ducling bandits model in this work can be treated special case of K 2. Moreover, the preference probability is characterized by generalized linear model, which may be a strong assumption for some real-world applications. We aim generalize results to broader nonlinear function classes, such the function class with bounded Eluder dimension (Russo & Van Roy 2013).
https://gi cot.:c/acmcccccccccooc /VACCH

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGEMENTS
We thank the anonymous reviewers and area chair for their helpful comments. QD, YW and QG are supported in part by the NSF grants CIF-1911168 and CPS-2312094, YW is also supported by UCLA Dissertation Year Fellowship. TJ and FF are supported in part by the NSF grant CIF-1908544. The views and conclusions contained in this paper are those of the authors and should not be interpreted as representing any funding agencies.
REFERENCES
Yasin Yadkori, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. Advances in neural information processing systems, 24, 2011.
Shipra Agrawal and Navin Goyal. Analysis of thompson sampling for the multi-armed bandit problem.
In Conference on learning theory, pp. 39-1. JMLR Workshop and Conference Proceedings, 2012. Jean-Y Yves Audibert, Rémi Munos, and Csaba Szepesvari. palloration-xploittaainn
tradeoff using variance estimates in multi-armed bandits. Theor. Comput. Sci., 410; 1876-1902, 2009,
Peter Auer. Using confidence bounds for exploitation-exploaaiio trade-offs. Journal of Machine Learning Research, (.NNov):397-422 2002.
Peter Auer, Nicolò Cesa-Bianchi, and Paul Fischer. Finite-time analysis of the multiarmed bandit problem. Machine Learning, 47:235-256, 200).
Akshay Balsubramani, Zohar Karnin, Robert E. Schapire, and Masrour Zoghi. instance-dependee regret bounds for ducling bandits. In Conference on Learning Theory, pp. 336-360. PMLR, 2016. Viktor Bengs, Róbert Busa-Fekete, Adil El Mesaoudi-Paule and Eyke Hüllerreeir.. Preference-based online learning with dueling bandits: A survey, Journal of Machine Learning Research, 22:7-1, 2021.
Viktor Bengs, Aadirupa Saha, and Eyke Hüllermeier. Stochastic contextual dueling bandits under linear stochastic transitivity models. In International Conference on Machine Learning, pp. 1764-1786. PMLR, 2022.
Luitzen EJ Brouwer. Beweis der invarianz des n-dimensionalen gebiets. Mathematische Annalen, 71:
305-313, 1911.
Xi Chen, Paul N Bennett, Kevyn Collins-Thomper and Eric Horvitz. Pairwise ranking aggregation in a crowdsourced setting. In Proceedings of the sixth ACM international conference on Web search and data mining. pp. 193-202, 2013.
Wei Chu, Lihong Li, L. Reyzin, and Robert E. Schapire. Contextual bandits with linear payoff functions. In International Conference on Artificial Intelligence and Statistics, 2011.
Miroslav Dudík, Katja Hofmann, Robert E. Schapire, Aleksandrs Slivkins, and Masrour Zoghi. Contextual dueling bandits. ArXiv, abs/1502.00662 2015.
Moein Falahatgar, Hao, Alon Orlitsky, Venkatadheerai Pichapati, and Vaishakh Ravindrakumar. Maxing and ranking with few assumptions. Advances in Neural Information Processing Systems,
30, 2017.
Sarah Filippi, Olivier Cappe, Aurélien Garivier, and Csaba Szepesvári. Parametric bandits: The generalized linear case. Advances in Neural Information Processing Systems, 23, 2010. David A Freedman. On tail probabilities for martingales. the Annals of Probability, pp. 100-118. 1975.
Reinhard Heckel, Max Simchowitz, Kannan Ramchandran, and Martin Wainwright. Approximate ranking from pairwise comparisons. In International Conference on Artificial Intelligence and Statistics, pp. 1057-1066. PMLR, 2018.
David R. Hunter. Mm algorithms for generalized bradley-terry models. Annals of Statistics, 32: 384-406, 2003.
Kevin Jamieson, Sumeet Katariya, Atul Deshpande, and Robert Nowak. Sparse dueling bandits. In Artificial Intelligence and Statistics. pp. 416-424. PMLR, 2015.
Rie Johnson and Tong Zhang. Accelerating stochastic gradient descent using predictive variance
reduction. Advances in neurul information processing systems, 26, 2013.
Kwang-Sung Jun, Aniruddha Bhargava, Robert Nowak, and Rebecca Willett. Scalable generalized
linear bandits: Online computation and hashing. Advances in Neural Information Processing
Systems, 30, 2017.
Shivaram Kalyanakrishnan, Ambuj Tewari, Peter Auer, and Peter Stone. Pac subset selection in
stochastic multi-armed bandits. In ICML, volume 12, pp. 655-662, 2012.
Yeoneung Kim, Insoon Yang, and K Kwang-Sung Jun. Improved regret analysis for variance-adaptive
linear bandits and horizon-free linear mixture mdps Advances in Neural Information Processing Systems, 15:1060-1077 2022.
10

---

Published as a conference paper at ICLR 2024
Junpei Komiyama, Junya Honda, Hisashi Kashima, and Hiroshi Nakagawa. Regret lower bound and optimal algorithm in dueling bandit problem. In Conference on learning theory. pp. 1141-1154.
PMLR. 2015.
Junpei Komiyama, Junya Honda, and Hiroshi Nakagawa. Copeland dueling bandit problem: Re- gret lower bound, optimal algorithm, and computationally efficient algorithm. In International Conference on Machine Learning, pp. 1235-1244. PMLR, 2016.
Wataru Kumagai. Regret analysis for continuous dueling bandit. Advances in Neural Information Processing Systems, 30, 2017.
Tze Leung Lai. Adaptive treatment allocation and the multi-armen bandit problem. The annals of statistics, pp. 1091-1114, 1987.
Tze Leung Lai, Herbert Robbins, et al. Asymptotically efficient adaptive allocation rules. Advances in applied mathematics, 6(1):4-22, 1985.
Tor Lattimore and Csaba Szepesvári. Bandit Algorithms. Cambridge University Press, 2020, doi:
10.1017/9781 108571401.
Lihong Li, Wei Chu, John Langford, and Robert Schapire. A contextual-bandit approach to personalized news article recommendation. In Proceedings the 19th international conference on World wide web, pp. 661-670, 2010.
Lihong Li, Yu Lu, and Dengyong Zhou. Provably optimal algorithms for generalized linear contextual bandits. In International Conference on Machine Learning, pp. 2071-2080. PMLR, 2017.
R. Duncan Luce. Individual choice behavior. In 1959.
Thomas P. Minka, Ryan Cleven, and Yordan Zaykov. Trueskill 2: An improved bayesian skill rating system. In Microsoft Research, 2018.
Subhojyoti Mukherjee, Kolar Purushothama Naveen, Nandan Sudarsanam, and Balaraman Ravindran. Efficient-ucbv: An almost optimal algorithm using variance estimates. In AAAI Conference on Artificial Intelligence, 2017.
Yurii Nesterov. Introductory lectures on convex optimization: A basic course, volume 87. Springer Science & Business Media, 2003.
Long Ouyang. Jeffrey Wu, Xu Jiang. Diogo Almeida, Carroll Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Ray, et al. Training language models to follow instructions with human feedback. Advances in Neural Information Processing Systems, 35: 27730-27744, 2022.
S. Ramamohan, A. Rajkumar, and Shivani Agarwal. Ducling bandits: Beyond condorcet winners to general tournament solutions. In NIPS, 2016.
Daniel Russo and Benjamin Van Roy. Eluder dimension and the sample complexity of optimistic exploration. Advances in Neurul Information Processing Systems, 26, 2013.
Aadirupa Saha. Optimal algorithms for stochastic contextual preference bandits. In Neural Informa- fion Processing Systems, 2021.
Aadirupa Saha, Tomer Koren, and Y. Mansour. Adversarial dueling bandits. ArXiv, 1055/2000.14633.
2021.
Louis Leon Thurstone. A law of comparative judgment. Psychological Review, 34:273-286, 1994. Huasen Wu and Xin Liu. Double thompson sampling for dueling bandits. Advances in neural information processing systems, 29, 2016.
Yue Wu, Tao Jin, Hao Lou, Farzad Farnoud, and Quanquan Gu. Borda regret minimization for generalized linear dueling bandits. arXiv preprint arXiv:2303.0m 008.08866, 2023.
Yisong Yue and Thorsten Joachims. Interactively optimizing information retrieval systems dueling bandits problem. In Proceedings of the 26th Annual International Conference on Machine Learning, pp. 1201-1208, 2009.
Yisong Yue, Josef Broder, Robert Kleinberg, and Thorsten Joachims. The k-armed dueling bandits problem. Journal of Computer and System Sciences, 78(5):1538-1555 2012.
Xiaohang Zhang, Guoliang Li, and Jianhua Feng. Crowdsourced top-k algorithms: An experimental evaluation. Proc. VLDB Endow., 9:612 623, 2016.
Zihan Zhang. Jiaqi Yang, Xiangyang Ji, and Simon S Du. Improved variance-aware confidence sets for linear bandits and linear mixture mdp. Advances in Neural Information Processing Systems,
34:4342-4355, 2021a.
Zihan Zhang, Jiaqi Yang, Xiangyang Ji, and Simon Shaolei Du. Improved variance-aware confidence sets for linear bandits and linear mixture mdp. In Neural Information Processing Systems, 202 b. Heyang Zhao, Jiafan He, Dongruo Zhou, Tong Zhang, and Quanquan Gu. Variance-dependent regret bounds for linear bandits and reinforcement learning: Adaptivity and computational efficiency. arXiv preprint ArXiv:2302. 2023a.
11

---

Published as a conference paper at ICLR 2024
Heyang Zhao, Dongruo Zhou, Jiafan He, and Quanquan Gu. Optimal online generalized linear regression with stochastic noise and its application to heteroscedastic bandits. In International PMLR, 2023b.
Conference Machine Learning, pp.
Dongruo Zhou and Quanquan Gu. Computationally efficient horizon-free reinforcement learning for linear mixture mdps. Advances in neural information processing systems, 35:36337-36344 2022. Dongruo Zhou, Quanquan Gu, and Csaba Szepesvari. Nearly minimax optimal reinforcement learning for linear mixture markov decision processes. In Conference on Learning Theory, pp. 4532-4576.
PMLR, 2021.
Masrour Zoghi, Shimon Whiteson, Rémi Munos, and M. de Rijke. Relative upper confidence bound
for the k-armed dueling bandit problem. ArXiv, abs/1312.3399 2014.
Masrour Zoghi, Zohar S. Karnin, Shimon Whiteson, and M. de Rijke. Copeland dueling bandits. In
NIPS, 2015.
12

---

Published as a conference paper at ICLR 2024
A COMPARISON WITH PRIOR WORKS
In this section, we provide a detailed discussion of the layered design, drawing a comparison with Sta'D D in Saha (2021) and SupCoLSTIN in Bengs et al. (2022). The general idea follows Auer 22002). which locuses on maintaining a set of "high confidence promising arms". The algorithm operates differently in two distinct scenarios. there are some pairs (x, in the current layer & with high uncertainty, represented by ||x+ Vells, we will explore those arm pairs. Conversely,
when achieving the desired accuracy, we eliminate suboptimal arms using our confidence set and proceed to subsequent layer demanding greater accuracy. This process continues until reach a sufficiently accurate high layer, at which we make decisions based on the remaining arms in the
confidence set and the estimated parameters d,,--
In the final stage, Sta'D D picks the first arm x; as the one with the maximum estimated score, followed by choosing its strongest challenger Yı, which has the highest optimistic opportunity to beat X SupCoLST IM adopts a similar policy and distinguishes itself with a randomized learning strategy by generating additive noise terms from an underlying perturbation distribution. Our arm selection is based on the symmetric arm selection policy described in Section
Sta' D and SupCoLSTIM choose the confidence set radius 3r. to be 2- in the (-th layer. In comparison, our choice Be, is defined in 4.. As mention in Section 4.3 apart from the 2- dependency the layer it also relies on the estimated variance. Such variance-adaptive confidence set radius helps to achieve the variance-aware regret bound.
B ADDITIONAL EXPERIMEN EXPERIMENT ON REAL-WORLDD DATA
To showcase the performance of our algorithms in a real-world setting, use EventTime dataset (Zhagg et al. 2016). In this dataset, = 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
x10
2.5
Regret(t)
1.0
= [x,, i E [K]]
0.5
MaxinP
or the true parameter 0' readily available in the dataset. Thus, we estimate them with pairwise comparison data. To achieve this, let Cij, i, [K] be the number of times event j precedes event labeled by the workers. The following MILE is used:
VACDB
0.0
0
1000
2000
3000
4000
Figure 2: Regret comparison be- tween VACDB and MaxIns on real-worke dataset.
argmnax [x,].0
ΣD Σ JE|K]
Ciy (o((x;-x,) -T,XK TO).
With the estimated A and 0", it is then possible to simulate the interactive process. We compared our algorithm VACDB with MaxInP in Figure(2 We can see that after about 2500 rounds, our algorithm starts to outperform MaxInP in terms of cumulative regret.
C DISCUSSION ON ARM SELECTION POLICIES
In this section, we present detailed discussion for Section 4.4 We assume that in round t, we have an estimator 0r, a covariance matrix Σ, = AI + Σ (x, yx)(x, - - and a concentration inequality with confidence radius S,,
0 0 < B,.
(C.1)
The three arm selection methods can be described as follows: Method 1: Following Saha (202)), let C, be
C. {x A (x (k-y) TO, 8, -y 20, Ar).
Then x E C. because for any y Ar
(x] - y) TO, + [x|12 y 51l
1 (xi - -y) T(, 0*) + (x] - y) 0t + + v1z,,'
2 Bellx - y11s, ||x - y1 10. 0'
0,
13

---

Published as a conference paper at ICLR 2024
where the first inequality holds due to Cauchy-Schward inequality and x is the optimal arm in round t. The second inequality holds due to (C.I)
The arms selected in round i are xx, Ye = aragaaxx x,EC, ||x - -yl,, Then the regret in round can be decomposed as
2r:- 2x; 0- (xe + v1) 0t
(x]- xx) 0" (x] y1) 0
= (x; x1) T T(O" 0.) + (x: xx) T 0, + (x: - y1) (0 - -0,) + +x; -y)) 0:
$ (x: xx) T "0" 0.) + B xx Xx "اا (x T 0.) :,llx; vellx,
$ ||x] xx xx =100 0: Ex, + +B xx1lxx
+ ||x - yrl - 110 - 011|., + Bel|x/ - -vellx,
- 2/ |x] - X >>>"" + 23: |x, - -yele "o11z,"
$ 4,3,|xx -YelI,,
where the first inequality holds because the choice xx, Yr E C.. The second inequality holds due to Sehuwaz inequality. The third inequality holds due to CC.I The last inequality holds due to x E Ct2 Yt = argmaxx.yec, x yll,,*
Method 2: Following Bengs et al. (2022). we choose the first arm as
X, argmaxx O..
XEAr
Then choose the second arm as
-, + 23, - y11
argmax
YEA,
The regret in round / can be decomposed as
2r: 2x; T 0- (xx + y:) 0-
2(x; x)) 0²
T + (x: yy) TT)T 0"
2(x; - x)) T( - 0.) + 2(x - x,) x,)
0, + (xi -
(x)- -T)T((r -0) + (x, -x) T.)
s 2||x; x x111x,11 -10 0,112, + (xt - -x,) T
+ |x - yt -1:ll,-1110 1 01112, + (x: - -x)) T
S 28, - x 1. + (x; - TO + B/||x/ yellz, x
S y. 0, + 23 Xt -ell x; x; 0, + (xi - T
- - Bellxx - vvlls,
3/ - yy y
where the first inequality holds due to the Cauchy-Schware inequality and x x 2 x; x; The second inequality holds due to the Cauchy-Schward inequality. The third inequality holds due to
y, argmaxyeaA y 0, 2,,,|x, yl
Method 3: In this method, we choose two arms
X Yt argmax x,YEA,
yx+ T. + Bellx -11s,-]
(C.2)
Then the regret can be decomposed as
2r:- 2x;" 0 (x, + yr)Te 6
[x] x,) T + (x- - y.)) T
[x] x,) (0" 0.) + (x) - vt) T (0) - θ.) + (2x; - X2, -V.)
S ||x; xill xi||اا1 ||0 0il1., + ||x; - yell 00 0.11z, + (2x; x, 13-y,) y.) TO 0,
s [x][x; - xx x1|1z;1 + x/|xx -Vlll,,' + (2x; - -x - y.) TO,
14

---

Published as a conference paper at ICLR 2024
where the first incquality holds due to the Sruuchy-Schwazznnnee inequalitt. The second inequality holds due to (C.I). Using
C.2p. we have
(x) x O2 Bellx; Xells, (x; + ye) (0)0))=)))))
0, + 3e11x, vells,
(xi + y:) Ou. - Bellxi - Vells, S (x: y.) 0, + Be||x, vells,
Adding the above two inequalities, we have
Bx|x; - X x + 8x|1x; Vellz, S (x4 + Yt 2x;) 10 + +3, - yells."
Therefore, we prove that the regret can be upper bounded by
2r. S 23 X - Yells,"
In conclusion, we can prove similar inequalities for the above three arm selection policies. To get an upper bound of regret, we can sum up the instantaneous regret in each round and use Lemma G. to obtain the final result.
D A RIGOROUS PROOF FOR THE MLE D.1 DISCUSSION ON THE WEAKNESS
In the proof of Lemma E. for completeness, we need to prove that (4.1) has a unique solution.
Following Li et al. (011 7), we define auxiliary function G. ; R2d - R
G( 00
2 W
[ (xx, 00) ((x, v.) To) -x.
Using the condition that the minimum eigenvalue of the covariance matrix is strictly positive, we can prove that G is injective and @ is the solution of 44.1) 1) is equivalent G(θ) Z, where Z is quantity dependent on the stochastic noise. In Li et al. (2017), there is a minor weakness in asserting the existence and uniqueness of the solution with O = G G-1(Z), without confirming whether Z lies in the range of G. We solve this problem with the classical Brouwer invariance of domain theorem in algebraic topology:
Theorem D.1 (Brouwer 1911). Let U be an open subset of Rd, and let f U - IRd be a continuous injective map. Then f(O) is also open.
We complete the proof by proving G(Rd) is both open and closed and therefore 4.1 has a unique solution.
D.2 A DETAILED PROOF
We will prove that the function is a bijection from Id to Rd. We first show it's injective. The proof idea is similar to Theorem 1 in et al. 2017). With the mean value theorem, for any 02, 02 E Rdd there exists m E [0, 1] and 0 = m0,
m 02, such that the following equation holds,
G - G(
A(0 - 02) + Σ w [H ((x. - yy) T.) - 11 ((xs - -ys) (x))(2)) (x. yo)
AI+ Σ 2 ((x, - yo) v 0) (x, - yx)(xx - yo) (0, O2).
We define F(0) as
- y
F(0)
AI Σ w ((x, T0) (x, -x)) -
Using ji(:) 2 Ka > 0 and inf, 3 > 0, we have F(O) is positive definite. Therefore, we prove that when 0, # 02. Go,) + (02) That is to say, G., is an injection from Id to Rdd Next, we prove G is surjective. The classical Brouwer invariance of domain theorem (Theorem G.4 in algebraic topology indicates that G is open map, and thus G(Rd) is open set. On the other
15

---

Published as a conference paper at ICLR 2024
hand, the minimum eigenvalue of F(0) is strictly positive. Therefore, F(0) is invertible, and have
01 -2 = ([t Gr)e(O2))
(D.1)
Let be a Cauchy sequence in G(RR). Using (D.1) and the fact that Amin (F(O)) 2 A we have for any m > n,
0 - 0nl12 S [[((0m)) -[G(()))((0.))) G(0,)]l2-
1
This inequality shows that [0,] also Cauchy sequence. With the completeness of the space Rd the limit lim; 0: = exists. By the continuity of the function G, we have
lim G(O.) G(0) G(RR).
Therefore, (TR))) also closed. We have proved that G(R)) is both open and closed. Using IRd is connected, we have proved that G(RR) = E i.c. Gt,e is subjective. In conclusion, the function G' is invertible, and (4.1) has a unique solution.
E PROOF OF THEOREM 5.1
In this section, we assume 4.1 has unique solution d.41, which is essential in our analysis. A detailed discussion is in Section first need the concentration inequality for the MLE.
Lemma E.1. With probability at least 1 5, the following concentration inequality holds for all
round 2 2 and layer & E [L] simultaneously:
| 0r Si
2
16
Σ sEW.
woo? log (/() Llog(44
+2-
Ky
With this lemma, we have the following event holds with high probability:
2
3
o.. 0-
16
Σ
w3o? log((1 +
( 6log(412 + + for all t,
D
Kgp
Lemma
E.1
shows that PIE)
2 1
8. For our choice of Br, defined 4.3 we define the following
event:
2
ebonus
Bi
16
woo? log( L/8) + 6 log
+ +2- for all t,
SEVI
The following two lemmas show that the event Ehomas holds with high probability.
Lemma E.2. With probability at least - 6, for all 2 2, E [L]. the following two inequalties hold simultaneously.
Σ sEW
2
Σ
whe +
14 log 4t2 L/8).
3
Σ SEW.
<
3
Σ
w + log 4t L/8).
2
SEW.
Lemma E.3. Suppose that the inequalities in Lemma l E [L] such that 2 64(Ln//nu) /log/ (oT((((TT))))) 1)2
E.2 and the event & hold. For all 222 2 and 8), the following inequalities hold
Σ w <8 Σ w (o.- - ((x=
(xx--xa) y.) T..)) 18 +18log(((++
SEW
SEV..
Σ 3
11 (xx-- - yz)
-y)-
<4 Σ
wpo 8log(4(t 1)28.
SEW.
16

---

Published as a conference paper at ICLR 2024
Recall that with our choice of Be in 4.3). the inequality in hhomss holds naturally when 2 64(Ln/Ku) /lgp://///////////// + L/). Combining Lemma E.2 Lemma E.3 and P( 1 8, after taking a union bound, we have proved PP n0 2 26.
Lemma E.4. Suppose the high probability events hoons and holds. Then for all 2 1 and / [4] such that the set A is defined, the contextual vector of the optimal arm xj lies in Ar.e-
Then bound the regret incurred in each layer separately.
Lemma E.5. Suppose the the high probability events & Ebonus and & holds. Then for all é E [4]/1, the regret incurred by the index set 1,+ e. is bounded by
Σ
2x, 0- - -x, 0- + +. s (d..2'Br..))))
With all these lemmas, we can prove Theorem 5.1
Proof of Theorem
5.7
Conditioned on Eboms n let
E* loga (64(2 (ogga
Using the high probability event Chomus
Lemma
E.4 and Lemma
E.5 for any > Et, we have
Σ
[x T 0- - (x] +yI
d. 2 2²BT.o-1)
d
w? (os (o.- pl(xs - ys) 0r) +1+1
0
Kp
SEVT
T
<
Σ
o
+1
(E. 1)
Kpp
Ki
where the first incquality holds due to Lemma
E.5 The second inequality holds due to the definition
4.3 The last inequality holds due to Lemma E.3 and w, 1.
For E [E*], we have
Σ WT4LE
(2x; 0- - (x. 0- +yI
S 4/
2
Σ
||,,(X, -
vo)1
SEVTHLE
=
(E.2)
where the first equality holds due to our choice w, such that [Iw,((; 1l) E... The second inequality holds due Lemma G.I The last equality holds due For any (Ut)(Ure)r)) (T+,,e) we set l, the value of layer such that ||x, - -ells, S a for all
E"
x. Va As,t and then the while loop ends. By the choice of x. and x; A.e. (Lemma E.4 we have
2x;
T Oatt S x x,,0..e + +Y + Bae.lIxo -olls
x 0 0,. + +y θzee e, Bae,a
+yT0.p
(E.3)
17

---

Published as a conference paper at ICLR 2024
where the last inequality holds because ||x, -Yllss, I for all X, As,t- Then we have
Σ
(2x; 0 - (x, 0- +y,0")
Σ
T Os.e, 2x; 0" -
[x] Os,e, x x))
sE(T)/(WEE[4) (TIL.)
y2 v²00)) (2x; (2xx,T0,.. (x, Os y v=Oaa. 0sle))
E
(1x3 Xx. x1l1sttt $5,, + +|x volls, 110" O2et llsu.e. +Bee
NE[T (e VT+Ld
Σ
3,3,,,
sE(T)/(UL(()) VT+1.)
<T (1/7) = Ö(1)
(E.4)
where the first inequality holds due to the Cauchy-Schwaad inequality and E.. The third inequality holds due to ||x y. Σيك S for all X,, E Au.,, x2 E As,t, (Lemma E.4) and Lemma E.1
The third inequality holds due to our choice of Ba,e, I Õ(VT) and a = 1/ 3/7 Combining E E.4 together, obtain
Regret(T) =Ō
d
Σ
T
o
+
d
# k
kp )
Kp
PROOF OF LEMMAS IN SECTION
F.1 PROOF OF LEMMA
E.1
Proof of Lemmal
E.
For fixed é E [L], let E VT+ 1 12 2, we define some auxiliary quantities:
Gr 2 2- +
02
Σ
wa [e (x)) - ((x, y..) v0)) (x. -y.)
f - 11 ((x: - T
Ze, = Σ w.Ea(t (X: - ys).
SEW
Recall 4.1 Oi, is the solution to
2 2 0
Σ
wi (oo) 0, (x. yy) 0.
(F.1)
simple transformation shows that
F.I is equivalent to following equation,
Ge,t (Br.) 2 22 --22kxp Ou.e
Σ w² P (xs yo) T=)T - a ((x, v.)
sEW.e
Σ w Jo. ((x, yx) TT))) (x, -y))
sEW.
Zz,e-
We has proved G.,e invertible in Section D and thus θ., G7.
18

---

Published as a conference paper at ICLR 2024
Moreover, we that Gr,e(0") 2 =2-2kx00 Recall Σ,,e 22:==2220 -2-2kxp++ Eoev., wg(X; (x) - ya) We have
(0., -0000000- (())=(0)) 0*)
2 kyt ( 6") Σ (0..0 0")
= x 00. 0- E
where the first inequality holds because ji(-) 2 Ri inequality, we have
> 0 and thus F(0) = Rig Ei Using the triangle
00. 0-
52 2/ 10 S +
1 - -11Z,eelss
E.e
Ki
1
$ 2
0 12
+
Zz, sel. s
Fig
To bound the || term, we use Lemma G.3 By the choice of w.s for any E Vr+1, we have
[x: y:) s 2- and we I 1.
We also have
E fewe 5
Fil S
Fi] S o and |arel S leel S 1. wf
Therefore, Lemma inequality holds
G.3 shows that with probability least 5/L, for all Vr+1, the following
11 16
Σ
L/) + -- 2 log( (t((4t2))) L/8).
SEV
Finally, we get
2-E
|0.c 0-
16
Σ
w6o2 log(4t2L/8)
L/0) +2
Nu
Take union bound on all & E [L], and then we finish the proof of Lemma E.1
F.2 PROOF OF LEMMA E.2
Proof of Lemma F.2 The proof of this lemma is similar to the proof of Lemma B.4 in Zhao et al. (003a)). For a fixed layer / [4]. using the definition of e, and σ. we have
Vs E, 02'x11s |1::: y Ylss 01:--1 0.
Therefore, we have
Σ SEV
Elwi(e) 22:s N1.s 010011 5 Σ
Blw X Nis. 01:01
sEVi,
w w0.?
SEWLE
where the last inequality holds due to the definition of a, and 6 S 1. Then using Lemma G.2 and taking union bound on all E [T.), for all > 2, have
Σ SEVIE
3 o3)
2 Σ
w lotgo((((LL)))
2 + 2 log( Mog((t2L) L/8)
SEV,e
Σ
w 0² +
log log(4t2L/6),
(F22
2
3
19

---

Published as a conference paper at ICLR 2024
where the Young's inequality ab - 2a² + 22b². Finally, finish the proof of Lemma E.2 by
Σ u2o0
Σ
W
Σ
" (
0²))
SEW
Σ
w
Σ
(c o.2)
SEV
SEV
Σ
" 0 2
7
log (444
(F.3
3
SEV
where the first inequality holds due to the triangle inequality. The second inequality holds due to We also have
Σ
Σ
Σ
-,²)
BE EE
Σ
w.
Σ
w (c 0:²
SE
7
log(4t (t L/8).
3
SEVLE
s.V.
The proof of this incquality is almost the same
F3
F.3 PROOF OF LEMMA E.3
Proof of Lemma E.3 For fixed é [L], Lemma E.2 indicates that
Σ
o
2 2
Σ e +
14
log( (4t 1og(4t21 L/8)
3
SE 12
SEVi,
<
14
log 4t
(1/42//00 L/8) +4 Σ
u² 0, (Ix, yy)) (x)) -O.)) )²
3
SEVie
4
Σ
w² 6x
(0s 1 (xx, yo) yo) TO.e)
(F.4)
sEV
where the second inequality holds due the basic inequality (a 6)2 < 2a² 21 for all a, e IR.
Using our definition of Es. O, = a ((x+ yo) T 00) + e.. Thus, we have
Σ w c, (o. 1 (xx,-x)) TT.)))))
(1)
SEVIE
= Σ /²
(u((xx -y.) Tθ..) ((x, - v..) -x))
(u(xx.-y.))
sEVIE
< L2 p
Σ
w (1x, - -x) (0.,- - -07)²
TT)T(Or,
(F.5)
sEVir
20

---

Published as a conference paper at ICLR 2024
where the last inequality holds because the first order derivative of function j is upper bounded by L (Assumption 3.2). Moreover, by expanding the square, we have
(1) < L
Σ
3² (xx - y.)) (0r. y.))
07))
L Σ
(ol - -00) T "x,sx, yx)(xx yy) vo)) -*)
LE
= (0 07)²
Σ
y,)(x, wx(x, [r)xxxx)((x, vo) (0e. -0)
sEViL
$ 0n - 0 12
(F.6
Ex.e"
where the last inequality holds due to
E, = 2- I+
Σ
" - (x, - yy,) = Σ
" y.)(x, -y.)
SEWL
Combining F.5
F.6
and the event & (Lemma E. we have
2 28 L
(1) 5
16
Σ
wLo [o ( (log(4((+1)2///))) K
Ri
2 T
512 log (4(t 1))
Σ
o + (6log 1)2 + km))
SEVLE
where the last inequality holds due to the basic inequality (a b)2 < 2a + 26 for all a, b R.
When 2 2 =4(LL./rm) / Tog ((tt L/)), we can further bound the above inequality by
(T) S
Σ
wāo + log(4(t++1) 1))
(F.7)
sEW
Subitituting
F.7
into
F.4
we have
Σ
w <4 Σ
w² 0s p ((xx -v)) -B.) Tr.e)
sEV,e 1.2
SEVi,
+ + (t + 1))
Σ o
2 SE VE.
Therefore, we prove the first inequality in Lemma E.3 as follows
Σ wL
Σ w (o. l ((xs v.)
SEW
.EV.
18 4(t + 11)).
For the second inequality, we have
Σ w² (0s - 1 (ox) T.)T
SEV
2 Σ
2 2 + Σ
w²² (cx - 00. (oa-14 ((xx -y)) T
0r.) )),)
W
SEV.
21

---

Published as a conference paper at ICLR 2024
We complete the proof of Lemma
E.3
Σ
/² (o, 1 (xx; -y.) 0r.))
1 Σ
221 Σ
W +
w¹o + 2 log(4(t + L/8)
sEW
3 Σ 0 + 7
1 Σ
2
log log(41(1/0)
who 2lgg(4((+ 1)81/8)
2
3
4 s.W.
I 4
o + 8 log(((( + L/8)
LE
where the first inequality holds due to
F.7 The second inequality holds due to Lemma E.2
F.4 PROOF OF LEMMA
E.4
Proof of Lemmal E.4 We prove it by induction. For 1, we initialze the set Ar,1 be A,, thus trivially x E A Now we suppose Ar, is defined and x; E AA, By the way Ar,411 is constructed, Ar,+I is defined only when ||x y I 2- for all x, y E Ar,e-
Let Xma = argmaxxxA, x Or.e. Then we have
x; 0r. x Xmax 0,,= (x;; (x;T 0" TT 0²) + (x, xmax) T(Or. X - 0*)
2 -1xx; - xmux 875 ||0,e 0- 0"
where the inequality holds due the Cauchy- inequality and the fact x argmaxxEA: x 0" With the inductive hypothesis, we know x E A Thus we have |xc] Xmaxl ب, 2- Finally, with the inequality in Lemma E.1 have
x 0..
max TT 00. 2 xEArt
Therefore, we have x; E Ar,++ and we complete the proof of Lemma E.4 by induction.
F.5 PROOF OF LEMMA E.5
Proof of Lemma E.5 For any E VT+L. due to the definition of V and our choice of x,, (Algorithm LLnne 16). we have x,,y, E As,e- Additionally, because the set Ag,e is defined,
||x yl1 vlls I
+I for all x, E Ag,e-1 From Lemma E,4 we can see that x E Aa,t-
Combining these results, we have
||x - xells,11 52 8+1 ||x;; - volls < 2--41
(F.8)
where we the inclusion property As,E C A.s-1. Moreover, Xs, X2 E As,e shows that
x -_001-1>
x -- 2- - 13,e-1
max xEAr1-1
2 x - 2 11.1388111
(F.9
where we use x, E A..g-1. Similarly, we have
y. 2 0..-1 0-.-1122 2 B- 1
(F.10)
22

---

Published as a conference paper at ICLR 2024
Now compute the regret incurred in round
2x; 0- (x. 0- + +y 0²) (x, - xx) 0³ + (x, - yo) 0r
(x3 x,) T 0 + (x; xx,) (T)] (0.0-11 - 07)
+ (x: ya) T 0, 02 + [xx; -va) (0ac-1- - 07)
S 2 B B + ||x; x.1l 000-1- 0r -en-1
+2 ++ B 1 | volls, |- 00,0-1
0
(F.11) where the first inequality holds due to the basic inequality S |x|| for all x E R. The second inequality holds due (.. (E.0)) and the Cauchy-Schware inequality. The last inequality holds due return to the summation of regret on the index set 1
28.2-"3,.-11
to (F.8) and Lemma E.1 Now
Σ
(2x;] 0- (x. 0" + +YI0
Σ
8 3.2-BB..
BE BE
+EWT+I,
< 8 2 BT VT++1e
<8 2 BT,E-1
Σ SEVT+I
|ww : (x2- - y=) -%a--))li
<8 2 BT 2d + 22+22+21/dd
where the first inequality holds due to (F.II). The second inequality holds due to our choice of w, such that ||w, (X, ys) 5 2-c The last inequality holds due to Lemma G.1 Therefore, we
complete the proof of Lemma E.5
G AUXILIARY LEMMAS
Lemma G.1 (Lemma 11. Abbasi Yadkori et al. 2011). For any À > 0 and sequence [x=]k= S Rd x Then, provided that ||xx|b || S L holds for all k [K].
for & E [K], define Z + we have
K min ||x 122 S 2d log(1 + KL2 (dx/)
Lemma G.2 (Freedmam 1975). . Let M, v > 0 be fixed constants. Let {x; [ be a stochastic process, [Grheem be filtration so that for all i [n]. x, is G--measurable, while almost surely
E[r:/9-1]] = 0, |ar|| < M, Σ B[b? S v.
Then for any 5 > 0, with probability least 1 8, we have
a
I S V log(110)) + 2/3 M log(1/8).
Lemma G.3 (haoo et al. 2023ah. Let {G+) be a filtration, and (xx, mh he21 be stochastic process such that X E Rd is meamaauuable and m E IR is mmer-uaarralle. Let L, o, X, > 0. 4² E Rd. For & 2 1, let y = (1",, xx) + Tkk where Tik X2 satisfy
E [mp
[x] = 0, Inxl S R.
E 1
9i] S Uk. for Vk 2
For l: 2 1, let Z = AI Σi X, b = Σi vi pb = Z by and
Bx = 16 un log(
4k2 4k2 Rp 1og(4K: 15),
23

---

Published as a conference paper at ICLR 2024
where p 2 supp>1 | Then, for any 0 < 8 < 1, we have with probability at least 6,
4k 2 1, Σ xmillz..' 5 ps 1 uzl S 3k + vAll 1/2
Theorem G.4 (Brouwer invariance of domain theorem Brouwer 1911). ). Let U be an open subset of R., and let f: U + IR be continuous injective map. Then f(U) also open.
24


Reviews:
[{"review_id": "Eo4o0R2juV", "reviewer": "Reviewer_2YSg", "summary": "The paper studies contextual dueling bandits, where binary comparison is generated from a generalized linear model. The work proposes a new framework to obtain variance aware regret guarantees. This work further provides empirical results comparing the algorithm against baseline.", "questions": "No questions.", "limitations": "", "rating": 8, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The problem setup is well laid out and easy to follow with the precisely required assumptions.", "weaknesses": "The paper is not self contained and requires reader to go through multiple papers for example in section 4.2.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "YgF4BafE9J", "reviewer": "Reviewer_W8bc", "summary": "This work studied the stochastic contextual dueling bandits. It proposed the VACDB algorithm, which is a new SupLinUCB-type algorithm. It provided a variance-aware bound on the regret of the proposed algorithm. This work presented a detailed review on existing literature and clarified the novelty of the proposed algorithm. It also evaluated the performance of the algorithm with numerical experiments.\n\n\n\n==============\n\nI appreciate the response from the author(s). I may increase the score if they further resolve my concern.", "questions": "Please refer to the **Weaknesses** section.", "limitations": "", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. This paper is in general well organized and easy to follow.\n1. The variance is considered in the dueling bandit setting.\n1. I appreciate the detailed review on existing literature, and the clarification on the novelty of the proposed algorithm and the differences from existing algorithms (especially SupLinUCB-type ones).", "weaknesses": "1. The variance $\\sum_{t=1}^T \\sigma_t$ 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.\n    1. The appearance of $\\sum_{t=1}^T \\sigma_t$ indicates that even if we know $X_t$ for all arms and $\\theta^*$, we may not know the value of the derived upper bound.\n1. I wonder if it is possible to derive a lower bound for the problem. If not, may the author(s) clarify the analytical challenge?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "u5irDELm9y", "reviewer": "Reviewer_Kvxm", "summary": "The paper addresses the problem of contextual dueling bandits, where the feedback is based on pairwise comparisons between arms. The authors focus on scenarios where the binary comparisons are generated from a GLM. The authors proposed VACDB algorithm that adapts to the variance of the pairwise comparisons, leading to potentially better performance in scenarios with varying levels of uncertainty. The variance-aware regret bound of order $O\\left(\\sqrt{d\\sum_{t=1}^{T} \\sigma_t^2} + d\\right)$, which also aligns with intuitive expectations, reducing to $O(d)$ in deterministic scenarios. The authors validate their approach through experiments on synthetic data, demonstrating the advantages of VACDB over previous variance-agnostic algorithms.", "questions": "- There is a minor typo on the second line of Introduction: \"arm\" -> ``arm\"\n\n\n================================================\n\n**After Rebuttal:**\n\nI appreciate the response from the authors, and I am going to keep my original rating.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The primary contribution of the paper is the introduction of a new algorithm VACDB (Variance-Aware Contextual Dueling Bandits), which incorporates a SupLinUCB-type approach to handle the contextual information and provide a variance-aware regret bound. \n- The regret bound $O\\left(\\sqrt{d\\sum_{t=1}^{T} \\sigma_t^2} + d\\right)$ proposed by the authors provides a more nuanced performance measure that reflects the difficulty of the decision-making problem.\n- Beyond the specific algorithm and regret bound, the paper also contributes to the theoretical understanding of generalized linear bandits, correcting an issue in the existing analysis of the MLE estimator.\n\nOverall, I think the paper enhances our understanding of decision-making in dueling bandits scenarios by explicitly accounting for the uncertainty in pairwise comparisons, providing both theoretical insights and practical algorithms to address the challenge on variance-awareness algorithms.", "weaknesses": "- The paper primarily conducts experiments on synthetic data to validate the proposed algorithm. While this is a common practice, the performance of the algorithm in real-world scenarios might differ. To strengthen the paper, the authors could include experiments on real-world datasets, particularly those related to the applications mentioned like ranking, recommendation systems, or any human-interactive system, ensuring the practicality and robustness of the algorithm in diverse settings.\n- The concept of a layered design for bandit algorithms, which the authors adopt in the VACDB algorithm, has been previously explored in the literature. Layered or epoch-based approaches are widely used in bandit algorithms to balance exploration and exploitation in stochastic settings. The paper could benefit from a more thorough discussion on how the layered design in VACDB specifically contributes to or differs from existing approaches.\n- The VACDB algorithm relies on the computation of regularized MLE for parameter estimation. The computation of these estimators is known to grow in complexity with the number of iterations, potentially leading to scalability issues, especially in settings with a large number of arms, contexts, or iterations.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "GGOQHDsoFw", "reviewer": "Reviewer_83pH", "summary": "The paper addresses the problem of dueling bandits with a variance-aware regret bound. It introduces an algorithm for contextual dueling bandits, which accounts for uncertainty in pairwise comparisons between arms and provides a variance-aware regret bound. The paper highlights the importance of considering uncertainty in decision-making scenarios and proposes an efficient algorithm with a regret bound that depends on the variance of comparisons, dimensionality of context vectors, and the time horizon. The authors demonstrate the effectiveness of their method through empirical experiments.", "questions": "In addition to my concerns in the above Weaknesses section,\n\n1. Is the variance of the noise $\\epsilon_t$ equal to $p_t(1-p_t)$ under the Bernoulli setting? In that case I feel the variance would be fully dependent on the arms selected in each round.", "limitations": "", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The paper is well written and easy to follow.\n\nThe proposed algorithm is the first algorithm with a variance-aware regret bound. It has some novelty, and the symmetric arm selection is new.\n\nThe authors also support their theoretical claims with empirical experiments on synthetic data.", "weaknesses": "I feel this paper is an extension to [1], with similar algorithm proposed and regret analysis. The main algorithm has identical structure with the SAVE proposed in [1] based on the SupLin methodology, and it is not new and novel for the variance-aware contextual bandit problem. Under the generalized linear contextual dueling bandit setting used in the paper, we can regard $x_t - y_t$ as the contextual information, which would then be degeneralized to the ordinary generalized linear contextual bandit problem. I think the high similarity with the existing literature is the major weakness of this work.\n\nTypos and minor issues: \n1. title of subsection 4.3 (sysmmetric -> symmetric)\n2. I may overlook. What is $\\kappa$ in line 20 Algorithm 1 and Eqn. (4.3)?\n\n[1] Variance-dependent regret bounds for linear bandits and reinforcement learning: adaptivity and computational efficiency. Zhao et al., COLT.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)