CS Paper Radar

Risk-Sensitive Non-Parametric and Kernel Bandits

Devdan Dey, Sujoy Bhore, Avishek Ghosh

cs.LG stat.ML ·submitted 2026-11-04 13:27 UTC · v1
theory

Abstract

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.

Comment
46 pages, 6 figures

Closest papers

Nearest neighbours by meaning across the whole index.

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.74
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

A General $\widetildeΩ(\sqrt{T γ_T})$ Lower Bound for Kernel Bandits

cs.IT stat.MLcs.LG ·2026-10-08 ·Chenkai Ma, Jonathan Scarlett
theory similarity 0.74
Abstract

The kernel bandit problem consists of sequentially optimizing an unknown function with noisy feedback, where the function has bounded norm in a given Reproducing Kernel Hilbert Space (RKHS). A central quantity in the regret analysis of kernel bandits is the maximum information gain $γ_T$. In particular, the best existing upper bounds scale as $\sqrt{Tγ_T}$ up to log factors, and nearly-matching lower bounds have been derived for specific kernels such as squared exponential and Matérn. However, lower bounds for general kernels are lacking, thus making it unclear in what generality the upper bounds are near-optimal. In this paper, we establish a general $Ω(\sqrt{Tγ_T/\log T})$ minimax regret lower bound for non-constant continuous kernels on compact domains, establishing near-optimality (within log factors) in a very general sense. We show that the log factor appearing in this bound is unavoidable in general, but that it can be removed under certain conditions. Among other things, our findings imply that the minimax-optimal scaling is exactly $Θ(\sqrt{Tγ_T})$ (i.e., within constant factors) for the Matérn-$ν$ kernel with $ν\in (0,2)$, $γ$-exponential kernel with $γ\in (0,2)$, and certain piecewise-polynomial kernels.

0.21

Reliable Scale-Free Bandits via Empirical Likelihood

cs.LG stat.ML ·2026-10-13 ·Pratham Gupta, Alhad Sethi, Shubhada Agrawal
theory similarity 0.73
Abstract

We study stochastic bandits without knowledge of reward scales or tail parameters. Almost-sure regret guarantees describe eventual learning but do not quantify expected performance or the risk of large regret in a finite run. We introduce $\texttt{EL-F}$, an anytime empirical-likelihood (EL) extension of the $g$-Forcing policy of Cowan and Katehakis (2020), and characterize its performance at three levels. First, for integrable rewards and non-decreasing, diverging exploration schedules $g$ with vanishing increments, $\texttt{EL-F}$ preserves the $g$-Forcing asymptotics for pseudo-regret $R(T)$: $R(T)/g(T)\to\sum_{i:Δ_i>0}Δ_i$ almost surely as $T\to\infty$, where $Δ_i$ is the suboptimality gap of arm $i$. Second, on every sub-exponential instance, for non-decreasing $g(t)=ω(\log t)$ satisfying a mild feasibility condition, expected pseudo-regret is at most $g(T)\sum_{i:Δ_i>0}Δ_i+C_{\underline{P}}$, where $C_{\underline{P}}$ is an instance-dependent constant independent of $T$. Moreover, we also establish finite-time tail bounds with super-polynomial decay in regret beyond the forced-exploration budget. For slowly varying $g$, we determine the exact exponent of linear regret deviations on two-armed Gaussian instances with common variance and establish a matching lower bound among policies satisfying the same expected-regret budget on every such Gaussian instance. These quantitative guarantees also cover the greedy variant obtained at zero EL radius. A fixed positive radius introduces local optimism while preserving the leading asymptotic regret. We establish coupled pathwise dominance over the greedy variant in two-armed bandits with a deterministic suboptimal arm. Experiments demonstrate reductions in prolonged suboptimal allocation compared with $g$-Forcing on challenging instances.

0.36

On the Complexity of Preference-Based Bandits

cs.AI cs.LG ·2026-09-30 ·Ahmed Ben Yahmed, Marc Abeille, Clément Calauzènes
top venue similarity 0.72
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.

0.39

Nearly Minimax-Optimal Regret for Linear Contextual Bandits with Arbitrary Adaptive Action Sets

cs.LG cs.GT ·2026-09-14 ·Tianyuan Jin
theory similarity 0.71
Abstract

We study stochastic linear contextual bandits with arbitrary action menus that may depend on the fixed parameter and the interaction history. We establish matching upper and lower bounds, up to logarithmic factors. Let $d$ be the dimension, $K$ be the menu size, and $T$ the time horizon. For $2\le K\le d$, we prove an upper bound $\widetilde O(K^{1/4}\sqrt{dT})$. When $T\ge d^2$, we further prove a lower bound $Ω(K^{1/4}\sqrt{dT})$. Thus, for $T\ge d^2$ and $2\le K\le d$, the upper and lower bounds match up to logarithmic factors, and the polynomial dependence on $K$ is optimal. Compared with the previous $\widetilde O(\sqrt{dKT})$ bound, our upper bound improves the dependence on $K$ by a factor of $K^{1/4}$. For $K\ge d$, we prove an upper bound $\widetilde O_{d,T}\left(\sqrt{dT}\min\{\sqrt d,(d\log K)^{1/4}\}\right)$ and a lower bound $Ω\left(\sqrt{dT}\min\left\{\sqrt d,\left(\frac{d\log K}{\log(2d)}\right)^{1/4}\right\}\right)$. Here, $\widetilde O_{d,T}$ omits logarithmic factors only in $d$ and $T$. In particular, for polynomially large $K\ge d$, the upper and lower bounds both scale as $d^{3/4}\sqrt T$ up to logarithmic factors, improving the standard $\widetilde O(d\sqrt T)$ rate by a factor of $d^{1/4}$. As $K$ grows further, the regret smoothly recovers the $d\sqrt T$ scale once $\log K$ reaches order $d$.

0.21

Accelerating Linear Bandits with Persistent Candidate Sets

cs.LG ·2026-10-09 ·Bingkui Tong, Daria Korovaitceva, Marina Sheshukova, Sergey Samsonov, Junpei Komiyama
theory similarity 0.71
Abstract

Exhaustive optimistic scoring can make action selection costly in linear bandits with a large fixed set of $K$ actions, requiring $\mathcal{O}(K)$ score evaluations per round. We introduce Persistent Candidate LinUCB (\textsc{PC-LinUCB}), which maintains $k$ active actions and samples $q$ challengers uniformly from the remaining $K-k$ actions at each round. By scoring only these $k+q$ candidates, \textsc{PC-LinUCB} reduces the number of score evaluations per round to $\mathcal{O}(k+q)$. We establish problem-independent and problem-dependent high-probability regret bounds consisting of a standard linear-bandit learning term and an additive discovery cost of order $\mathcal{O}\left((K-k)\log(K-k)/q\right)$ at fixed confidence. Notably, this additional cost does not grow with the horizon. For fixed gaps and sufficiently long horizons, we establish an $Ω\left((K-k)/q\right)$ regret lower bound under uniform challenger sampling, showing that partial candidate access itself imposes an unavoidable regret cost. Experiments show that \textsc{PC-LinUCB} substantially accelerates LinUCB while maintaining comparable regret, and that the persistent candidate mechanism can extend beyond LinUCB.

0.20

On the Computational Tractability of Robust Bandits

cs.LG ·2026-10-06 ·Vanessa Kosoy, Vinayak Pathak
similarity 0.71
Abstract

Learning when the environment does not belong to the learner's hypothesis class is typically handled using agnostic learning guarantees. However, for anything beyond supervised learning, agnostic guarantees are difficult to come by. Recently, imprecise bandits (Kosoy, 2025) (later renamed to robust bandits in Appel and Kosoy, 2025) were introduced as another approach to unrealizable learning in the bandits setting and a $Θ(\sqrt{T})$ regret learner was shown for a large class. However, no computational guarantees were provided. In this paper we identify a special case that admits a polynomial-time learner with $\tilde{O}(\sqrt{T})$ regret. We also show that several small generalizations of this special case are NP-hard thus indicating that the special case is at the boundary of what is tractable. It has been recently suggested (Kosoy, 2018) that computationally efficient learners for unrealizable learning problems are crucial for solving the AI alignment problem. This work is a small step in that direction.

0.20

Vanilla Policy Optimization Is Both Optimal and Differentially Private for Stochastic Contextual Bandits

cs.LG ·2026-09-27 ·Idan Attias, Orin Levy, Alexander Ryabchenko, Yishay Mansour, Uri Stemmer
similarity 0.70
Abstract

Can vanilla policy optimization explore enough to achieve near-optimal regret in stochastic contextual bandits? We show that standard exponential policy updates driven by offline regression do so under realizability, without exploration bonuses or importance weighting. For $A$ actions, $T$ rounds, and a finite prediction class $F$, vanilla PO achieves $\widetilde O(\sqrt{AT\log(|F|)})$ regret with high probability. Our analysis reveals an implicit exploration mechanism of independent interest: gradual policy updates prevent actions from losing probability too quickly, allowing the regression oracle to learn their expected losses. We further develop a batched version using only $O(\log T)$ regression calls and policy switches, and show how private regression oracles yield differentially private contextual bandit algorithms without composition across batches. For a finite class, this gives pure $\varepsilon_{\rm priv}$-DP and regret $\widetilde O\left( \sqrt{AT \log(|F|/δ)}(1+\varepsilon_{\rm priv}^{-1/2}) \right)$. Finally, experiments across oracle-based contextual bandit algorithms, with and without privacy, demonstrate the practical effectiveness of policy optimization and the value of explicit exploration under stronger privacy constraints.

0.14