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:2605. 09454v2 Announce Type: replace-cross Abstract: We study the $\textit{single-index bandit}$ problem, where rewards depend on an unknown one-dimensional projection of high-dimensional contexts through an unknown reward function.
By Devdan Dey, Sujoy Bhore, Avishek Ghosh
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
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
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
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
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.
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)
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
arXiv:2309. 06349v2 Announce Type: replace-cross Abstract: Thompson sampling (TS) is one of the most popular and earliest algorithms to solve stochastic multi-armed bandit problems.
By Prateek Jaiswal, Debdeep Pati, Anirban Bhattacharya, Bani K. Mallick
arXiv:2606. 19883v1 Announce Type: new Abstract: We study a multi-agent multi-armed bandit problem in the competitive setup with two-sided matching markets under a human centric decision making model.
By Ananya Kunisetty, Avishek Ghosh
arXiv:2605. 09200v2 Announce Type: replace Abstract: We study adversarial noisy bandits given a known function class $\mathcal{F}$.
By Steve Hanneke, Kun Wang