Variance-Aware Regret Bounds for Stochastic Contextual Dueling Bandits
Variance-Aware Regret Bounds for Stochastic Contextual Dueling Bandits
复制标题
DOI：
10.48550/arxiv.2310.00968
复制
发表时间：
2023-10
期刊：
影响因子：
--
通讯作者：
Qiwei Di;Tao Jin;Yue Wu;Heyang Zhao;Farzad Farnoud;Quanquan Gu
中科院分区：
文献类型：
--
作者：
Qiwei Di;Tao Jin;Yue Wu;Heyang Zhao;Farzad Farnoud;Quanquan Gu
决斗强盗是一个重要的决策框架，涉及优先反馈，这是一个有价值的功能，适合各种涉及人类交互的应用，如排名，信息检索和推荐系统。虽然大量的努力，以尽量减少累积的遗憾决斗土匪，在目前的研究中的一个显着的差距是没有遗憾的界限，占决斗武器之间的成对比较的固有的不确定性。直觉上，更大的不确定性意味着问题的难度更高。为了弥补这一差距，本文研究了上下文决斗土匪的问题，决斗武器的二元比较产生的广义线性模型（GLM）。我们提出了一个新的SupLinUCB型算法，具有计算效率和方差感知的遗憾界$\tilde O\big（d\sqrt{\sum_{t=1}^T\sigma_t^2} + d\big）$，其中$\sigma_t$是轮$t$中成对比较的方差，$d$是上下文向量的维数，$T$是时间范围。我们的遗憾界自然与直观的期望一致，在比较是确定性的情况下，算法只遭受$\tilde O（d）$遗憾。我们对合成数据进行实证实验，以确认我们的方法比以前的方差不可知算法的优势。
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.