Variance-Aware Regret Bounds for Stochastic Contextual Dueling Bandits
Qiwei Di Tao Jin Yue Wu Heyang Zhao Farzad Farnoud Quanquan Gu
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 in 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.