Variance-Aware Regret Bounds for Stochastic Contextual Dueling Bandits

Quanquan Gu, Yue Wu, Heyang Zhao, Qiwei Di, Tao Jin, Farzad Farnoud

arXiv · PDF · Open in the Atlas

Code that ran

We lifted 5 functions out of this paper's own repositories and ran 0 of them in a sandbox. "Ran" means the function executed on a synthesized input and returned a value. It is not a reproduction of the paper's results.

Repositories linked to this paper

• uclaml/vacdb — marked official in Papers with Code; named in the paper

Some links come from the archived Papers with Code dataset (CC BY-SA 4.0): attribution and licence.

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 , where σ 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 O(d) regret. We perform empirical experiments on synthetic data to confirm the advantage of our method over previous variance-agnostic algorithms.

For agents

The same record, over MCP at https://syntology.ai/mcp:

get_harvested_code_for_paper("2310.00968")
get_code_for_paper("2310.00968")
have("2310.00968")

Connect an agent — have() is free.