CS Paper Radar

On the Complexity of Preference-Based Bandits

Ahmed Ben Yahmed, Marc Abeille, Clément Calauzènes

cs.AI cs.LG ·submitted 2026-09-30 09:12 UTC · v1
top venue

Abstract

We study preference-based bandits with general reward function classes, where a learner sequentially selects pairs of arms and observes binary preference feedback governed by the Bradley--Terry model. This setting naturally arises in applications such as recommender systems, tournament ranking, and learning from human feedback, where relative preferences are easier to elicit than absolute rewards. The observation model inherits the logistic bandit challenge of handling the problem-dependent constant $κ$, which accounts for the non-linearity of the link function and can grow arbitrarily large. Moreover, prior work has predominantly focused on linear or kernelized reward models, precluding the use of richer function classes. To address these limitations, we consider general reward function classes and introduce the \emph{locally sensitive eluder dimension}, a novel complexity measure tailored to the logistic structure of preference feedback that yields fine-grained regret guarantees without unfavorable dependence on $κ$. Building on this notion, we propose \textbf{GINOP} (Generic INformative OPtimism), an algorithm that constructs log-loss confidence sets and jointly selects arm pairs to balance optimism and informative exploration. We establish a first-order regret bound that, in contrast with what previous results suggest, demonstrates that learning with preference feedback is as statistically efficient as learning from direct reward observation. Finally, we corroborate our theoretical findings with empirical evaluations against competitive baselines.

Journal ref
NeurIPS 2026 - Fortieth Annual Conference on Neural Information Processing Systems, Dec 2026, Sydney (AUSTRALIA), Australia

Closest papers

Nearest neighbours by meaning across the whole index.

When Greedy Sampling Explores: KL-Regularized Contextual Bandits without Eluder-Dimension Dependence

cs.LG ·2026-09-11 ·Zichen Wang, Haoyang Hong, Huazheng Wang
similarity 0.76
Abstract

We study KL-regularized contextual bandits under both reward and preference feedback. While existing regret guarantees typically depend on the eluder dimension, we show that simple greedy sampling can achieve polylogarithmic regret without explicit dependence on this complexity measure. For reward feedback, we analyze a greedy algorithm that samples directly from the Gibbs policy induced by the estimated reward. We extend the result to preference feedback under both general preference and Bradley--Terry models, while also sharpening existing dimension-dependent guarantees. Our analysis reveals a trade-off between greedy sampling and upper confidence bound-style exploration: greedy sampling enjoys stronger regret guarantees when KL regularization is sufficiently strong, whereas additional exploration yields sharper bounds as the regularization weakens.

0.31

Saturation-Insensitive Dueling Bandits with General Function Approximation

cs.LG ·2026-09-26 ·Chenggong Zhang, Xuheng Li, Qiwei Di, Weitong Zhang, Quanquan Gu
similarity 0.76
Abstract · 29 pages

We study contextual dueling bandits with general function approximation under the Bradley-Terry-Luce (BTL) preference model. A key challenge in this setting is the saturation of the preference model: when the current reward model can already distinguish two actions with high confidence, the resulting preference feedback becomes weakly informative, making it difficult to further improve reward estimation. Consequently, existing sample-complexity analyses often depend on the inverse-derivative factor $1 / σ'[Δ_{r^\ast}]$ which can be prohibitively large when the link function $σ$ saturates for large reward gaps $Δ_{r^\ast}$. To address this issue, we introduce `SI-CDB`, an algorithm that selects opponent arms using a carefully designed heuristic for arm selection. This design enables saturation-insensitive reward learning and recovers the near-optimal dependence for linear reward classes, eliminating the unfavorable $1/σ'(\cdot)$ factor. The core of our analysis is a localized Eluder dimension framework tailored to dueling bandits with general function approximation. Our theoretical results also explain why two-arm regret analysis is crucial for improving single-arm performance in dueling bandits.

0.24

High-Probability Regret Bounds for Feel-Good Thompson Sampling

cs.IT stat.MLcs.LG ·2026-10-14 ·Xuheng Li, Qingyue Zhao, Quanquan Gu
similarity 0.75
Abstract · 22 pages

Feel-good Thompson sampling (FGTS) augments the posterior of vanilla Thompson sampling with an exploration term that favors reward functions with high predicted optimal values. This modification achieves minimax-optimal regret up to logarithmic factors in linear contextual bandits, but existing analyses of its two standard variants establish regret guarantees in expectation. In this paper, we derive the first high-probability regret bounds for both cumulative and current-step FGTS in contextual bandits with general realizable function approximation. Our bounds depend on the corresponding decoupling coefficients and the prior mass near the true reward function. In the $d$-dimensional linear setting, both variants satisfy $\mathrm{Regret}(T)=O\big(d\sqrt T\log(2T)+\sqrt T\log(1/δ)\big)$ with probability at least $1-δ$, where $T$ is the time horizon. This bound matches the dimension and horizon dependence of algorithms based on the upper confidence bounds, up to logarithmic factors. Relative to the expected-regret guarantees, the cost of controlling the regret with high probability is confined to additive terms with at most linear dependence on $\log(1/δ)$. The proof ideas are partially developed by GPT-6 Astra under the authors' guidance.

0.19

Minimax Optimal Regret for Causal Logistic Bandits with Counterfactual Fairness

cs.LG ·2026-10-01 ·Junhyuk Huh, Seoungbin Bae, Dabeen Lee
similarity 0.73
Abstract

We study causal logistic bandits with counterfactual fairness constraints. The causal structure is given through known factual and counterfactual feature maps that share an unknown logistic reward parameter, but the learner observes only factual rewards. Consequently, the directions determining counterfactual feasibility need not be identifiable from the available feedback. The closest prior analyses either omit a coverage condition or impose a comparatively strong one, and do not establish matching lower bounds. We first show that some coverage condition is necessary: without a coverage-type restriction, factually indistinguishable environments with different optimal fair actions force $Ω(T)$ expected joint loss. Under a weaker full-rank condition on the factual covariance pooled across actions, we identify a target-specific information scale $V_\star$ that measures the difficulty of estimating rewards and counterfactual effects from factual feedback. We construct worst-case families satisfying this condition on which every policy incurs expected joint loss $Ω\left(\left[V_\star\min\{\log K,d\}\right]^{1/3}T^{2/3}\right)$. We also give an explore--then--exploit procedure tuned using $V_\star$ and an adaptive algorithm that does not require its value. Both algorithms achieve $\max\{R_T,V_T\}=\widetilde{O}\left(\left[V_\star\min\{\log K,d\}\right]^{1/3}T^{2/3}+κd/σ_0^2\right)$, where $R_T$ is regret relative to the best fair action and $V_T$ denotes the cumulative stage-wise positive violations. Thus the upper and lower bounds match in their leading dependence on $T$, $V_\star$, and $\min\{\log K,d\}$, up to logarithmic factors.

0.20

Risk-Sensitive Non-Parametric and Kernel Bandits

cs.LG stat.ML ·2026-11-04 ·Devdan Dey, Sujoy Bhore, Avishek Ghosh
theory similarity 0.72
Abstract · 46 pages, 6 figures

We study non-parametric bandits in which arms are evaluated using Cumulative Prospect Theory (CPT) rather than expected reward. We consider continuous action spaces with arm-dependent noise and propose Non-Parametric CPT Bandits ($\mathtt{NPCB}$), an optimistic algorithm that decouples mean estimation from CPT-based decision-making. We prove CPT regret of order $\widetilde{\mathcal O}\bigl(\sqrt{T\,\dim_E(\mathcal F,T^{-2})\,\log N(\mathcal F,T^{-2},\|\cdot\|_\infty)}\bigr)$, where $\dim_E$ is the Eluder dimension of the function class $\mathcal F$, $T$ is the time horizon, and $N$ is its covering number in the sup norm. This matches the order-wise regret of classical non-parametric bandits, showing that CPT risk sensitivity incurs no additional order-wise regret cost. We extend $\mathtt{NPCB}$ to unknown noise CDFs, retaining the known-CDF mean-learning term and adding a CDF-learning cost governed by a distributional Eluder dimension. We also study Kernel-CPT bandits and obtain information-gain-based regret bounds for a broad range of kernels, matching the corresponding risk-neutral kernel rates up to logarithmic factors.

0.20

Polylogarithmic Nash Regret in Matrix Games with Bandit Feedback

cs.LG cs.GT ·2026-09-28 ·Yuheng Zhang
similarity 0.72
Abstract

We study Nash regret minimization in unknown finite matrix games with bandit payoff feedback and observed opponent actions. We develop Optimistic Payoff Balancing (OPB), which achieves instance-dependent $\mathcal{O}(\log^2 T)$ Nash regret against arbitrary adaptive opponents, including games with nonunique equilibria. This resolves the open problem posed by Maiti et al. (2025), extending their polylogarithmic guarantee under bandit feedback from $2\times2$ games to arbitrary finite dimensions. To handle nonunique equilibria, we construct a reference strategy that leaves room for local adjustments. We order independent payoff differences by estimation accuracy and scale these adjustments by uncertainty, allowing the learner to exploit the opponent's imbalance to offset estimation costs. Our result thus shows that observing opponent actions suffices for polylogarithmic Nash regret in general finite matrix games.

0.13

Conservative Dueling Bandits: Preference Learning under Baseline Constraints

cs.LG cs.AIstat.ML ·2026-10-27 ·Rohan Deb, Mohammad Ghavamzadeh, Arindam Banerjee
similarity 0.72
Abstract

Contextual dueling bandits learn from pairwise comparisons, the same feedback used to fine-tune language models from human preferences. Standard algorithms explore aggressively and can show users two poor options. We study conservative contextual dueling bandits, which require that, at every round, the cumulative score of the better displayed item stay above a $(1-α)$ fraction of a trusted baseline's. An item's score is its probability of beating the best available item, so the constraint depends only on utility differences and needs no absolute rewards. This also changes how safety can be certified: we show that transferring the safety test of the conservative bandit algorithm CLUCB unchanged can incur linear regret, even when the baseline's utilities are known exactly. For linear utilities, we develop MaxInP-BC, which certifies scores through utility gaps and, when it must fall back, pairs the baseline with an informative partner so that fallback rounds still drive learning. It is safe with high probability at all times, with regret $\tilde{O}(d\sqrt{T}/κ)$ plus an additive cost of conservatism that does not grow with the horizon. For general utility classes, we develop BTIGW-BC, which turns the guarantee of an online logistic-regression oracle into cumulative safety certificates. It is safe at all times, makes finitely many fallbacks, and has sublinear regret whenever the oracle's logistic regret is sublinear. In experiments, both satisfy the constraint, which their unconstrained counterparts often violate, at a moderate cost in regret.

0.13

Meta-LinEXP3: Online-within-Online Learning for Adversarial Linear Contextual Bandits

cs.LG math.OC ·2026-09-09 ·Hao Li, Jie Xu, Zheng Xie
similarity 0.71
Abstract

Meta-learning has emerged as an effective paradigm for transferring knowledge across sequential bandit tasks. While substantial progress has been made for stochastic bandits and non-contextual adversarial bandits, meta-learning for adversarial linear contextual bandits (ALCBs) with random action sets remains largely unexplored. To address this problem, we propose Meta-LinEXP3, an online-within-online algorithm that constructs a predictable task-level prior from completed tasks to guide the inner LinEXP3 learner. For known context distributions, we develop a policy-centered estimator that achieves an intrinsic-dimension $\mathcal{O}(\sqrt{n})$ per-task regret bound. For unknown distributions, we introduce a past-only regularized moment estimator with an $\mathcal{O}(n^{2/3})$ leading regret term and explicit finite-sample error. We further establish a direct connection between prior accuracy and transfer regret, showing that increasingly accurate priors yield sublinear transfer-dependent regret across tasks. Experiments demonstrate the effectiveness of Meta-LinEXP3, including its application to structured hyperspectral tensor sampling.

0.11