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
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:2602. 06257v2 Announce Type: replace Abstract: Online strategic classification studies settings in which agents strategically modify their features to obtain favorable predictions.
By Chase Hutton, Adam Melrod, Han Shao
arXiv:2312. 15427v3 Announce Type: replace Abstract: Stochastic optimization is a widely used approach for optimization under uncertainty, where uncertain input parameters are modeled by random variables.
By Arpit Agarwal, Rohan Ghuge, Viswanath Nagarajan, Zhengjia Zhuo
arXiv:2606. 06043v1 Announce Type: cross Abstract: Follow-the-regularized-leader framework has shown effectiveness and flexibility in online learning problems, where the choice of learning rates are known to be crucial.
By Jongyeong Lee, Junya Honda, Shinji Ito, Chansoo Kim
arXiv:2607. 29460v1 Announce Type: new Abstract: Heavy-tailed distributions arise naturally in sequential decision-making problems such as financial investment, online advertising, and network management, where rare but extreme outcomes can dominate performance.
By Gianmarco Genalti, Alberto Maria Metelli
arXiv:2608. 08662v1 Announce Type: cross Abstract: The single-selection prophet inequality is a canonical Bayesian online selection problem in which independent nonnegative values arrive sequentially and the decision-maker must irrevocably select at most one.
By Patrick Loiseau, Mathieu Molina, Vianney Perchet, Sebastian Perez-Salazar, Victor Verdugo
arXiv:2604. 10727v2 Announce Type: replace-cross Abstract: Classical information-theoretic learning bounds typically rely on KL mutual information and moment-generating-function (MGF) arguments, which are well matched to bounded or sub-Gaussian losses but can be ineffective when losses or rewards are heavy-tailed.
By Huiming Zhang, Binghan Li, Wan Tian, Qiang Sun
arXiv:2603. 10184v2 Announce Type: replace-cross Abstract: Statistical inference with bandit data presents fundamental challenges owing to adaptive sampling, which violates the independence assumptions underlying classical asymptotic theory.
By Budhaditya Halder, Ishan Sengupta, Koustav Chowdhury, Samya Praharaj, Koulik Khamaru
arXiv:2607. 10963v1 Announce Type: cross Abstract: We study the problem of efficient online proportional sampling from a high-dimensional domain under a $\sigma$-smoothed adversary, where the sampling distribution is induced by a dynamically evolving weight function defined over a sequence of piecewise-structured partitions.
By Amirmahdi Mirfakhar, Maria-Florina Balcan, Hedyeh Beyhaghi
arXiv:2605. 14953v2 Announce Type: replace Abstract: We address the problem of conformal selection, where an agent must select a minimal subset of options to ensure that at least one ``success'' is identified with a pre-specified target probability $\phi$.
By Sreenivas Gollapudi, Kostas Kollias, Kamesh Munagala, Ali Sinop
arXiv:2603. 06957v2 Announce Type: replace-cross Abstract: We study post-training linear autoregressive models with outcome and process rewards.
By Alireza Mousavi-Hosseini, Murat A. Erdogdu