Feel-Good Thompson Sampling for Contextual Dueling Bandits

2024/04/09 by Xuheng Li, Heyang Zhao, Li, Xuheng +3 · 7 citations
Decision Sciences · Computer Science · #Advanced Bandit Algorithms Research #Mobile Crowdsensing and Crowdsourcing #Distributed Sensor Networks and Detection Algorithms

paper · pdf · doi:10.48550/arxiv.2404.06013

Abstract

Contextual dueling bandits, where a learner compares two options based on context and receives feedback indicating which was preferred, extends classic dueling bandits by incorporating contextual information for decision-making and preference learning. Several algorithms based on the upper confidence bound (UCB) have been proposed for linear contextual dueling bandits. However, no algorithm based on posterior sampling has been developed in this setting, despite the empirical success observed in traditional contextual bandits. In this paper, we propose a Thompson sampling algorithm, named FGTS.CDB, for linear contextual dueling bandits. At the core of our algorithm is a new Feel-Good exploration term specifically tailored for dueling bandits. This term leverages the independence of the two selected arms, thereby avoiding a cross term in the analysis. We show that our algorithm achieves nearly minimax-optimal regret, i.e., O(d√ T), where d is the model dimension and T is the time horizon. Finally, we evaluate our algorithm on synthetic data and observe that FGTS.CDB outperforms existing algorithms by a large margin.

Cited by

• DT-PBO: an Interpretable Tree-based Surrogate Model for Preferential Bayesian Optimization
• Variance-Aware Feel-Good Thompson Sampling for Contextual Bandits
• LLM Routing with Dueling Feedback
• Neural Variance-aware Dueling Bandits with Deep Representation and Shallow Exploration
• Bayesian Optimization from Human Feedback: Near-Optimal Regret Bounds
• Accelerating RL for LLM Reasoning with Optimal Advantage Regression
• ActiveDPO: Active Direct Preference Optimization for Sample-Efficient Alignment

Related

• Regret Minimization in Stochastic Contextual Dueling Bandits
• Efficient and Optimal Algorithms for Contextual Dueling Bandits under\n Realizability
• Variance-Aware Regret Bounds for Stochastic Contextual Dueling Bandits
• Neural Dueling Bandits: Preference-Based Optimization with Human Feedback
• Versatile Dueling Bandits: Best-of-both-World Analyses for Online Learning from Preferences