Efficient and Optimal Algorithms for Contextual Dueling Bandits under Realizability
By Aadirupa Saha, Akshay Krishnamurthy. 2021
49 citations recorded by the source corpus.
We study the $K$-armed contextual dueling bandit problem, a sequential decision making setting in which the learner uses contextual information to make two decisions, but only observes \emph{preference-based feedback} suggesting that one decision was better than the other. We focus on the regret minimization problem under realizability, where the feedback is generated by a pairwise preference matrix that is well-specified by a given function class $\mathcal F$. We provide a new algorithm that achieves the optimal regret rate for a new notion of best response regret, which is a strictly stronger performance measure than those considered in prior works. The algorithm is also computationally efficient, running in polynomial time assuming access to an online oracle for square loss regression over $\mathcal F$. This resolves an open problem of Dud\'ik et al. [2015] on oracle efficient, regret-optimal algorithms for contextual dueling bandits.
Subfields: Reinforcement Learning
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Reinforcement Learning
- Aldo Pacchiano
- Jonathan Lee
- Banghua Zhu
- Jiantao Jiao
- Aadirupa Saha
- Michael I. Jordan
- Sergey Levine
- Pieter Abbeel
Citations in the corpus
- Dueling RL: Reinforcement Learning with Trajectory Preferences (2021, background): “Yue and Joachims (2009, 2011); Saha and Krishnamurthy (2022); Ghoshal and Saha (2022); Saha and Gopalan (2018a) The setting is relevant in various realworld systems which aim to collect information from user preferences, including recommender systems, retail management, search engine optimization,…”
- Principled Reinforcement Learning with Human Feedback from Pairwise or K-wise Comparisons (2023, background): “In the literature of dueling bandit, one compares two actions and aims to minimize regret based on pairwise comparisons (Yue et al., 2012; Zoghi et al., 2014b; Yue and Joachims, 2009; 2011; Saha and Krishnamurthy, 2022; Ghoshal and Saha, 2022; Saha and Gopalan, 2018a; Ailon et al., 2014; Zoghi et al”