This work resolves the assumption-free adaptation problem for heavy-tailed bandits and characterize the price in the regret of not knowing the tail parameters and introduces a scheduled-exploration algorithm that requires no knowledge of $u$ and matches the resulting adaptation frontier up to logarithmic factors.
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. Heavy-tailed bandits model online decision-making in these settings by assuming only that rewards $X$ satisfy $\mathbb{E}[|X|^{1+\epsilon}]\leq u$, for some tail exponent $\epsilon\in(0,1]$ and moment bound $u<+\infty$. However, most existing regret minimization algorithms require these parameters to be known. This assumption is particularly restrictive in practice: $\epsilon$ and $u$ govern the frequency and magnitude of rare events and are therefore precisely the quantities that are hardest to infer reliably from limited observations. Motivated by an open problem posed by Genalti and Metelli at COLT 2025, we resolve the assumption-free adaptation problem for heavy-tailed bandits and characterize the price in the regret of not knowing the tail parameters. We first study adaptation to the moment bound $u$ for a fixed tail exponent $\epsilon$. We prove that every algorithm unaware of $u$, or of any upper bound on it, must obey a sharp trade-off between its distribution-dependent and distribution-free regret guarantees. We then introduce a scheduled-exploration algorithm that requires no knowledge of $u$ and matches the resulting adaptation frontier up to logarithmic factors. Finally, we show that the same algorithm can be instanced without knowing $\epsilon$ by calibrating its exploration schedule to the endpoint $\epsilon=1$. It achieves sublinear regret for every fixed $\epsilon>0$, while no algorithm can guarantee sublinear regret uniformly over all $\epsilon\in(0,1]$. Altogether, our results resolve the COLT open problem without additional distributional assumptions and provide a sharp characterization of the statistical cost of adapting to unknown heavy tails.
We study online convex optimization with stochastic gradient noise whose conditional $p$-th central moment is bounded by $\sigma^p$, for an unknown $p\in(1,2]$. For losses with Lipschitz bound $G$ on a domain of diameter $D$, we obtain expected universal dynamic regret $\widetilde O(GD\sqrt{T\Lambda}+\sigma DT^{1/p}\Lambda^{(p-1)/p})$, where $\Lambda=1+P_T/D$ and $P_T$ is the path length of a fixed comparator sequence. The algorithm combines restarted AdaGrad experts with an adaptive entropy-regularized master, uses one stochastic gradient per round, and requires no knowledge of $G,\sigma,p$, or $P_T$. Its iterates are invariant under positive rescaling of the gradients. The analysis controls comparator movement within restart blocks before taking expectations, yielding the noise path exponent $(p-1)/p$ rather than the exponent $1/2$ of a direct non-restarted extension. A matching stochastic first-order oracle lower bound, combined with the deterministic dynamic-regret lower bound, identifies the minimax rate up to logarithmic factors as $\min\{GD\sqrt{T\Lambda}+\sigma DT^{1/p}\Lambda^{(p-1)/p},GDT\}$.
Bayesian optimization in a time-varying environment where the unknown reward function evolves according to a Gaussian process drift model is studied, and GP-UCB can be run with a constant exploration parameter and obtained an expected-regret bound whose coefficient depends on the drift rate.
We settle the worst-case approximability of residual-surplus maximization in general multidimensional mechanism-design environments. For $n$ agents with arbitrary nonnegative valuations over a finite outcome space, we give a universally truthful and ex-post individually rational mechanism whose expected residual surplus is at least $W(N)/H_n$, where $W(N)$ is the optimal social welfare and $H_n$ is the $n$-th harmonic number. This guarantee is worst-case optimal, including its constant, even for a single-item auction with a known i.i.d. prior and under the weaker requirement of Bayesian incentive compatibility. Our result resolves the welfare-approximation aspect of the open question of [Hartline and Roughgarden 2008] on the power of money burning beyond $k$-unit auctions, as well as an open question of [Ezra et al. 2025] concerning optimal guarantees for broader valuation classes. It also replaces the outcome-dependent $O(\log|\mathcal{O}|)$ guarantee of [Fotakis et al. 2015] by the tight agent-dependent factor $H_n$, while strengthening truthfulness in expectation to universal truthfulness. The mechanism is polynomial-time whenever welfare-maximizing VCG is polynomial-time, yielding efficient mechanisms for gross-substitutes and multi-unit valuations and for several natural single-parameter feasibility constraints.
The results resolve the open question raised in the literature concerning the sharp arm-dependent regret--instability frontier and develop a new offline top-prefix representation that removes path dependence from online decisions.
To make optimal joint pricing and inventory control decisions is a critical challenge for modern retailers. In practice, retailers face changing market conditions where demands are influenced by various contextual factors, while simultaneously dealing with the difficulty of lost sales that obscure true demand information. However, existing approaches often fail to account for both contextual information and censored demand observations. We address this gap by presenting a framework where we model demand as a linear combination of basis functions with unknown coefficients, allowing for adaptive pricing and inventory decisions that respond to changing contexts. We propose an efficient algorithm to achieve regret bound $\mathcal{O}(K\sqrt{T}\log T)$ under concave revenue conditions and $\mathcal{O}(K^{2/3}T^{2/3}(\log T)^{1/2})$ for the general case, with matching lower bounds confirming optimality. Extensive numerical experiments across diverse scenarios demonstrate our algorithm's effectiveness.
We study a variant of the Thompson Sampling (TS) algorithm, called $\alpha$-TS, for solving stochastic generalized linear bandit problems. Existing analyses of TS require inflating the posterior variance to derive near-optimal regret guarantees. We formalize the idea of variance inflation by introducing $\alpha$-TS that uses a fractional or $\alpha$-posterior instead of the standard posterior. Our main contribution is to identify general regularity conditions on the prior and reward distributions that enable a regret analysis of $\alpha$-TS without assuming any tractable approximation of the posterior distribution, unlike previous works. For a specific choice of $\alpha \propto d^{-1}$, our general regret bound yields the best known regret bound of $O(d^{3/2}\sqrt{T}\log T)$ for both the exponential and sub-Gaussian families of reward distributions. We further provide an $\alpha$-dependent lower bound showing that the regret constant depends on the product $\alpha d$, and that when $\alpha \propto d^{-1}$ the regret scales as $\Omega(d^{3/2}\sqrt{T})$, explaining the origin of the $d^{3/2}$ factor in the upper bound. Our proof technique adapts and combines recent advancements in the analysis of linear bandit problems with first- and second-order posterior concentration theory from the Bayesian statistics literature.
Prateek Jaiswal, D. Pati, A. Bhattacharya et al.· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
