We formulate and study a novel multi-armed bandit problem called the qualitative dueling bandit (QDB) problem, where an agent observes not numeric but qualitative feedback by pulling each arm. We employ the same regret as the dueling bandit (DB) problem where the duel is carried out by comparing the qualitative feedbac…
On-device research index
arXiv research
A locally-built, LLM-digested index of recent arXiv papers in quant finance, geometry/topology, and statistical ML — keyword search served straight from SQLite on this machine.
168,742 papers · 148 categories
Trend · papers per month
48 results for “dueling feedback”
Algorithm identifies Copeland winners in dueling bandits with ternary feedback.
problem Identifying Copeland winners in dueling bandits with indifferences.
method Proposed POCOWISTA algorithm with a sample complexity close to lower bound.
result Algorithm shows excellent performance, even for conventional dueling bandits.
Multi-armed bandit(MAB) problem is a reinforcement learning framework where an agent tries to maximise her profit by proper selection of actions through absolute feedback for each action. The dueling bandits problem is a variation of MAB problem in which an agent chooses a pair of actions and receives relative feedback…
Paper tackles dueling bandits with delayed feedback, revealing preference bias.
problem Real-world dueling bandit applications often face delays in feedback.
method Introduces biased dueling bandit problem with stochastic delayed feedback, presents two algorithms.
result Two algorithms achieve optimal regret bounds for dueling bandit problems with delay.
The paper tackles learning from imperfect human feedback, especially in dueling bandit problems.
problem Learning from human feedback that can be irrational or imperfect.
method Developed a Robustified Stochastic Mirror Descent for Imperfect Dueling (RoSMID) algorithm.
result Achieved nearly optimal regret for dueling bandit problems under imperfect human feedback.
Develops a new model for RLHF accounting for partially observed states and intermediate feedback.
problem Lack of models for partially observed states and intermediate feedback in RLHF.
method PORRL model with cardinal and dueling feedback methods.
result Demonstrates improved learning and alignment with new model-based and model-free methods.
Efficiently identifies good policies by choosing contexts for human feedback.
problem Efficiently identifying good policies in applications with high feedback costs.
method Introduces offline contextual dueling bandit setting and an upper-confidence-bound style algorithm.
result Proves a regret bound and shows superior performance over uniformly sampled contexts.
A new algorithm for conversational recommendation systems using dueling bandits in GLMs.
problem Limited user feedback in existing conversational bandit methods.
method Integrates dueling bandits with relative feedback in generalized linear models.
result Theoretical and empirical validation of ConDuel's efficacy.
New algorithm for identifying Condorcet team in noisy comparisons.
problem Online learning with noisy comparisons of teams.
method Formalized dueling teams problem, developed algorithms for stochastic and deterministic settings.
result Identifies Condorcet winning team with reduced number of duels.
Neural algorithms optimize arm selection with human preference feedback for complex reward functions.
problem Optimizing arm selection with noisy human preference feedback for complex, non-linear reward functions.
method Neural network to estimate reward function using preference feedback, upper confidence bound and Thompson sampling algorithms.
result Sub-linear regret guarantees for efficient arm selection in contextual dueling bandits.
New algorithm for minimizing regret in adversarial dueling bandits.
problem Minimizing regret in dueling bandits with adversarial feedback.
method Introduced an algorithm with -round regret of .
result Algorithm achieves regret lower bound.
Algorithm minimizes regret in dueling bandits with contextualized utilities.
problem Minimizing regret in dueling bandits with context-dependent utilities.
method Proposes CoLSTIM algorithm based on perturbed utility estimates.
result Achieves regret of order .
Think Before You Duel: Understanding Complexities of Preference Learning under Constrained Resourcescs.LG
A dueling bandit problem with resource constraints is solved using EXP3.
problem Maximizing rewards in dueling bandits with resource constraints.
method EXP3 algorithm considering resource consumptions.
result Achieves $ ilde{\mathcal{O}}\left({\frac{OPT^{(b)}}{B}}K^{1/3}T^{2/3}
ight)$ regret.
A Finite Time Analysis of Thompson Sampling for Bayesian Optimization with Preferential Feedbackstat.ML
Proposes a TS approach for Bayesian optimization with preferential feedback.
problem Optimizing with preference feedback in complex applications.
method Uses Thompson Sampling with a dueling kernel and anchor invariance.
result Performance matches standard TS for scalar feedback in finite time.
The dueling bandit is a learning framework wherein the feedback information in the learning process is restricted to a noisy comparison between a pair of actions. In this research, we address a dueling bandit problem based on a cost function over a continuous space. We propose a stochastic mirror descent algorithm and …
New algorithms improve dueling bandit performance in multiplayer settings.
problem Challenges in collaborative exploration of non-informative arm pairs in multiplayer dueling bandits.
method Demonstrated Follow Your Leader approach and message-passing fully distributed protocol.
result Multiplayer algorithms outperform single-player benchmarks.
New ranking algorithms are continually being developed and refined, necessitating the development of efficient methods for evaluating these rankers. Online ranker evaluation focuses on the challenge of efficiently determining, from implicit user feedback, which ranker out of a finite set of rankers is the best. Online …
In this paper, we present simple algorithms for Dueling Bandits. We prove that the algorithms have regret bounds for time horizon T of order O(T^rho ) with 1/2 <= rho <= 3/4, which importantly do not depend on any preference gap between actions, Delta. Dueling Bandits is an important extension of the Multi-Armed Bandit…
PDO optimizes LLM prompts without labels, improving performance.
problem Optimizing prompts for LLMs without access to labeled data.
method Pairwise preference feedback, dueling bandits, Thompson Sampling, mutation.
result PDO identifies stronger prompts than label-free methods.
New algorithm for contextual dueling bandits achieves nearly optimal regret.
problem Contextual dueling bandits with feedback on preferred options.
method Proposes FGTS.CDB, a Thompson sampling algorithm for linear contextual dueling bandits.
result Achieves nearly minimax-optimal regret of .
We study the -armed dueling bandit problem, a variation of the standard stochastic bandit problem where the feedback is limited to relative comparisons of a pair of arms. We introduce a tight asymptotic regret lower bound that is based on the information divergence. An algorithm that is inspired by the Deterministic…
New algorithms for batched dueling bandits with improved regret bounds.
problem Batched dueling bandits with noisy pairwise comparisons.
method Developed algorithms for two settings: Condorcet winner and strong stochastic transitivity.
result Regret bounds match sequential bounds using only a logarithmic number of batches.
This paper addresses dueling bandits with contextual information, improving regret bounds by accounting for variance.
problem Minimizing cumulative regret in dueling bandits with contextual information.
method Proposes a new SupLinUCB-type algorithm for contextual dueling bandits with variance-aware regret bound.
result Achieves a variance-aware regret bound of .
Efficiently identifies good policies by choosing contexts for human feedback.
problem Efficiently acquiring human feedback for preference alignment in large language models.
method Formalizes active exploration as a dueling bandit problem and proposes an active exploration algorithm with a polynomial worst-case regret bound.
result Proposed method outperforms baselines with limited human preferences on various language models and datasets.
Algorithm minimizes regret in non-stationary dueling bandits with unknown parameters.
problem Minimizing regret in dueling bandits with time-varying preferences.
method Proposes Beat the Winner Reset algorithm and meta-algorithms DETECT and Monitored Dueling Bandits.
result Proves bounds on expected weak and strong regret for non-stationary dueling bandits.
New algorithm achieves near-optimal performance in dueling bandit problem.
problem Optimizing decision-making in dueling bandit problems with limited adaptive rounds.
method Developed a batched algorithm that matches the asymptotic regret bounds of sequential algorithms under the Condorcet condition.
result Asymptotic regret of in rounds.
We study the K-armed dueling bandit problem, a variation of the standard stochastic bandit problem where the feedback is limited to relative comparisons of a pair of arms. The hardness of recommending Copeland winners, the arms that beat the greatest number of other arms, is characterized by deriving an asymptotic regr…
Study on tracking preference shifts in dueling bandits problems.
problem Tracking significant preference shifts in dueling bandits problems.
method Analysis of dueling bandits with distribution shifts, focusing on significant shifts (Suk and Kpotufe, 2022).
result Design of adaptive algorithms with dynamic regret for certain preference distribution classes.
The paper minimizes Borda regret in dueling bandits models.
problem Minimizing Borda regret in dueling bandits models.
method Proposes explore-then-commit and EXP3-type algorithms for stochastic and adversarial settings respectively.
result Achieves nearly matching regret upper bounds of for both settings.
In preference-based reinforcement learning (RL), an agent interacts with the environment while receiving preferences instead of absolute feedback. While there is increasing research activity in preference-based RL, the design of formal frameworks that admit tractable theoretical analysis remains an open challenge. Buil…
Optimizes decision-making in dueling bandits with contextual features.
problem Identifying the best arm in dueling bandits with contextual features.
method Develops algorithms for minimizing regret in stochastic contextual dueling bandits.
result Proves optimal regret bounds for contextual dueling bandits.
In machine learning, the notion of multi-armed bandits refers to a class of online learning problems, in which an agent is supposed to simultaneously explore and exploit a given set of choice alternatives in the course of a sequential decision process. In the standard setting, the agent learns from stochastic feedback …
Formulates a Dueling Bandits problem for eliciting Kemeny rankings.
problem Eliciting preferences to find a Kemeny ranking.
method Formulates the problem as a Dueling Bandits problem, considering sampling with and without replacement.
result Approximation bounds and algorithms for finding PAC solutions with sample complexity.
We introduce the probably approximately correct (PAC) \emph{Battling-Bandit} problem with the Plackett-Luce (PL) subset choice model--an online learning framework where at each trial the learner chooses a subset of arms from a fixed set of arms, and subsequently observes a stochastic feedback indicating prefere…
New RLHF algorithm identifies optimal policies from human feedback without explicit reward inference.
problem Training large language models with human feedback without reward inference.
method Model-free RLHF algorithm that identifies optimal policies directly from human preference.
result Provable, instance-dependent sample complexity .
New algorithm reduces dynamic regret in non-stationary dueling bandits using a weighted Borda score.
problem Designing algorithms with low dynamic regret in non-stationary dueling bandits.
method Introducing a novel weighted Borda score framework to analyze the Condorcet problem and establish improved bounds.
result First optimal and adaptive dynamic regret upper bound of .
New algorithm optimizes dueling bandits for both stochastic and adversarial preferences.
problem Optimizing decision-making in environments where only relative preferences are observed.
method Proposed a reduction from dueling bandits to multi-armed bandits, achieving optimal regret bounds.
result First best-of-both-world result for dueling bandits, optimal regret bound for Condorcet-winner benchmark.
In this paper, we propose a Double Thompson Sampling (D-TS) algorithm for dueling bandit problems. As indicated by its name, D-TS selects both the first and the second candidates according to Thompson Sampling. Specifically, D-TS maintains a posterior distribution for the preference matrix, and chooses the pair of arms…
Bayesian optimization improved for biased data.
problem Adversarial bias in observations, especially hidden confounders.
method Reduction to dueling bandits, information-directed sampling (IDS).
result First efficient kernelized algorithm with regret guarantees.
The Thresholding Bandit Problem (TBP) aims to find the set of arms with mean rewards greater than a given threshold. We consider a new setting of TBP, where in addition to pulling arms, one can also \emph{duel} two arms and get the arm with a greater mean. In our motivating application from crowdsourcing, dueling two a…
This paper tackles combinatorial pure exploration for dueling bandits, aiming to find the best candidate-position match.
problem Finding the best candidate-position match in a dueling bandit setting.
method The paper adapts combinatorial pure exploration for multi-armed bandits to dueling bandits, considering both Borda winner and Condorcet winner cases. It designs PAC and exact algorithms for Borda winner and a fully polynomial time approximation scheme (FPTAS) for Condorcet winner.
result The paper introduces the first algorithm with polynomial running time per round for identifying the Condorcet winner in CPE-DB.
Linear Partial Monitoring for Sequential Decision-Making: Algorithms, Regret Bounds and Applicationscs.LG
IDS algorithm optimizes sequential decisions in various monitoring settings.
problem Optimizing sequential decisions in complex monitoring scenarios.
method Information-directed sampling (IDS) algorithm for linear partial monitoring.
result IDS achieves nearly worst-case rate optimality in finite-action games.
Paper proposes efficient RLHF methods for LLMs using active queries.
problem Efficiently aligning LLMs with human preferences using RLHF.
method Formalizes RLHF as a dueling bandit problem, introduces APPO and ADPO algorithms.
result ADPO achieves similar performance to state-of-the-art methods with fewer queries.
Factored Banditscs.LG
We introduce the factored bandits model, which is a framework for learning with limited (bandit) feedback, where actions can be decomposed into a Cartesian product of atomic actions. Factored bandits incorporate rank-1 bandits as a special case, but significantly relax the assumptions on the form of the reward function…
New method identifies Condorcet winner in dueling bandits with improved sample complexity.
problem Identifying Condorcet winner in noisy pairwise comparisons.
method Exploits full gap matrix Δ to improve sample complexity.
result Improves sample complexity guarantees by leveraging informative comparisons.
Unified framework for best arm identification and dueling bandits regret minimization.
problem Best arm identification and dueling bandits regret minimization.
method Tree-Guided Identify-Then-Exploit (TG-ITE) framework.
result Unified approach achieving optimal sample complexity and regret guarantees.
Improved algorithm for adaptive dueling bandits with near-optimal regret bound.
problem Non-stationary dueling bandits with unknown number of preference changes.
method Elimination-based rescheduling algorithm for adaptive dynamic regret.
result Near-optimal dynamic regret bound.
A new algorithm finds minimizers in dueling optimization with a monotone adversary.
problem Finding minimizers in dueling optimization with a monotone adversary.
method Introduces and studies dueling optimization with a monotone adversary, designs an efficient randomized algorithm.
result Efficient algorithm incurs cost and iteration complexity , asymptotically optimal.