arXiv Machine Learning

Risk-Sensitive Non-Parametric and Kernel Bandits

The paper introduces Non-Parametric CPT Bandits (NPCB), an optimistic algorithm for bandit problems where arm rewards are evaluated using Cumulative Prospect Theory instead of expected value. It provides regret bounds that match classical non‑parametric bandits, showing that incorporating risk sensitivity does not increase order‑wise regret. Extensions to unknown noise distributions and kernel‑based CPT bandits are also presented, with regret guarantees that align with risk‑neutral kernel rates up to logarithmic factors.

arXiv Machine Learning
Oct 9

A General $\widetilde{\Omega}(\sqrt{T \gamma_T})$ Lower Bound for Kernel Bandits

The paper establishes a general minimax regret lower bound of Ω(√{Tγ_T/ log T}) for kernel bandits with non‑constant continuous kernels on compact domains, matching existing upper bounds up to logarithmic factors. It shows that this log factor is unavoidable in general but can be removed under specific conditions. Consequently, the optimal scaling is exactly Θ(√{Tγ_T}) for several common kernels, including Matérn‑ν (ν∈(0,2)), γ‑exponential (γ∈(0,2)), and certain piecewise‑polynomial kernels.

By Chenkai Ma, Jonathan Scarlett
arXiv Machine Learning
Jun 9

Asymptotic Optimality of Thompson Sampling for Risk-Averse Bandits with Sub-Gaussian Rewards

arXiv:2606. 09191v1 Announce Type: new Abstract: We prove that $\rho\text{-}\mathrm{NPTS}_{\mathrm{SG}}$, an anchor-free nonparametric Thompson Sampling algorithm for risk-averse bandits, achieves regret matching the instance-dependent lower bound to leading order in $\log n$, establishing it as asymptotically optimal for any continuous risk functional $\rho$ (CVaR, mean-variance, Sharpe ratio, distortion risk measures, and more) on the class of distributions with bounded density and sub-Gaussian tails, including Gaussian arms.

By Joel Q. L. Chang
arXiv Machine Learning
Oct 16

Follow the Perturbed Leader for Linear Bandits: $\sqrt{T}$ Regret over General Convex Sets

The paper presents the first adversarial linear bandit algorithm based on Follow-the-Perturbed-Leader (FTPL) that achieves √T regret over general convex action sets. It achieves a regret of ≥O(d^{5/4}√T) using only linear optimization oracles, and a near‑optimal ≥O(d√T) regret when an optimal‑design exploration distribution is available. The work improves on previous FTPL algorithms and generalizes earlier results for special action sets, offering a simpler and more computationally efficient approach that relies on adaptive perturbation distributions and a new analysis framework based on Fisher information.

By Chen-Yu Wei
arXiv Machine Learning
Oct 15

High-Probability Regret Bounds for Feel-Good Thompson Sampling

The paper presents the first high‑probability regret bounds for both cumulative and current‑step variants of Feel‑Good Thompson Sampling (FGTS) in contextual bandits with general realizable function approximation. The bounds rely on decoupling coefficients and prior mass near the true reward function, and in the linear setting they achieve ≠d√T log(2T)+√T log(1/δ) regret with probability at least 1‑δ. This matches the dimension and horizon dependence of upper‑confidence‑bound algorithms up to logarithmic factors, while the high‑probability cost adds only linear dependence on log(1/δ).

By Xuheng Li, Qingyue Zhao, Quanquan Gu
arXiv Machine Learning
Oct 19

Follow the Perturbed Leader for Linear Bandits: $\sqrt{T}$ Regret over General Action Sets

The paper presents the first adversarial linear bandit algorithm based on Follow-the-Perturbed-Leader (FTPL) that achieves √T regret over general action sets. It attains a ≥O(d^{5/4}√T) regret using only linear optimization oracles, and a near‑optimal ≥O(d√T) regret when an optimal‑design exploration distribution is available. The authors introduce adaptive perturbation distributions—including Gaussian, random‑weighting, and elliptical perturbations—and develop a systematic analysis of the FTPL stability term via Fisher information, extending the FTPL framework beyond previous approaches.

By Chen-Yu Wei
Hugging Face Trending Papers
Jun 8

Asymptotic Optimality of Thompson Sampling for Risk-Averse Bandits with Sub-Gaussian Rewards

We prove that $ρ\text{-}\mathrm{NPTS}_{\mathrm{SG}}$, an anchor-free nonparametric Thompson Sampling algorithm for risk-averse bandits, achieves regret matching the instance-dependent lower bound to leading order in $\log n$, establishing it as asymptotically optimal for any continuous risk functional $ρ$ (CVaR, mean-variance, Sharpe ratio, distortion risk measures, and more) on the class of distributions with bounded density and sub-Gaussian tails, including Gaussian arms. Both this result and its bounded-support counterpart require only continuity of $ρ$: strictly weaker than the dominance condition of prior parametric Thompson Sampling results, and strictly weaker than the Lipschitz condition of UCB-type algorithms, yielding the first instance-optimal guarantees for non-Lipschitz functionals such as the Sharpe ratio without parametric reward assumptions.

arXiv AI
Oct 1

On the Complexity of Preference-Based Bandits

The paper investigates preference-based bandits where a learner selects pairs of arms and receives binary preference feedback modeled by Bradley–Terry. It introduces the locally sensitive eluder dimension, a new complexity measure for logistic preference feedback, and proposes the GINOP algorithm that uses log-loss confidence sets to balance optimism and exploration. The authors prove a first-order regret bound showing that learning with preference feedback can be as statistically efficient as learning from direct rewards, and they validate their theory with empirical experiments.

By Ahmed Ben Yahmed (CREST, ENSAE Paris, FAIRPLAY), Marc Abeille (FAIRPLAY), Cl\'ement Calauz\`enes (FAIRPLAY)
arXiv Machine Learning
Oct 22

The Price of Current-Effect Inference in Nonstationary Multi-Armed Bandits

The paper studies the trade‑off between maximizing rewards and accurately estimating current treatment effects in nonstationary multi‑armed bandits. For $K$‑armed bandits with H"older‑smooth mean rewards, the authors derive minimax bounds on expected dynamic regret under a high‑probability simultaneous coverage requirement for all current effects. They propose the TRACE algorithm, which achieves a regret–precision trade‑off that separates reward‑learning regret from the unavoidable cost of refreshing current‑effect estimates, and extend the method with an empirical‑Bernstein e‑process to adapt exploration while preserving worst‑case guarantees.

By Sharan Sahu, Martin T. Wells