An algorithm EHM is proposed that extends the adaptive Huber loss method with one-pass update with one-pass update and achieves an almost optimal regret of $\widetilde{\mathcal{O}(1)$ computational complexity with respect to current round $t$ and the time horizon $T$), which simultaneously achieves an almost optimal regret.
Abstract
In this paper we first study the problem of generalized linear bandit (GLB) under heavy-tailed noise. The characteristics of heavy-tailed distributions are widely observed in real-world applications such as personalized recommendation, financial markets, and medical treatments. Based on the online mirror descent (OMD) method, we propose an algorithm EHM that extends the adaptive Huber loss method (Wang et al., 2025) with one-pass update ($\mathcal{O}(1)$ computational complexity with respect to current round $t$ and the time horizon $T$), which simultaneously achieves an almost optimal regret of $\widetilde{\mathcal{O}}(T^{\frac{1}{1+\epsilon}})$ where $T$ is the time horizon. In addition, by utilizing a special property of some link function (Sawarni et al., 2025), our algorithm eliminates the need to know a commonly used parameter. Next, we study the GLB problem under the case when contextual characteristic becomes piecewise constant, and we slightly revised former algorithm to obtain the PGLB-EHM algorithm. After theoretical analysis, we prove that the regret upper bound order stays the same. Furthermore, we look deeper into a special case of nonlinear bandit (NB) and present the NB-EHM algorithm with bisection method and special restriction. Eventually we utilize the affine lifting approach and show that the general NB problem can be applied with NB-EHM to achieve a sublinear regret bound.
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.
Gianmarco Genalti, A. Metelli· arXiv.org· 1 citation
We study generalized linear bandits with memory, an endogenous non-stationary setting in which rewards depend on past actions through a finite memory matrix. Building on prior work for linear models (Clerici et al., 2024), we show that the previously known $\tilde{O}(T^{3/4})$ regret bound stems from a loose analysis, and we provide a sharpened analysis that recovers a $\tilde{O}(\sqrt{T})$ regret rate in the linear case. We then extend this improvement to generalized linear models and propose a block-wise algorithm based on shrunken confidence bounds. Our algorithm achieves a regret bound of $\tilde{O}\left(\sqrt{mT} + d\sqrt{T} + \sqrt{\kappa}\, d^{2} m^{1/4} T^{1/4} + \kappa d^{2} \right)$, where $d$ denotes the feature dimension, $m$ the memory length, and $\kappa$ a curvature parameter of the link function. This attains a $\sqrt{T}$-type rate despite nonlinear rewards and memory effects. To the best of our knowledge, this analysis provides a unified treatment of memory-induced non-stationarity and nonlinear link functions, while ensuring that the leading regret term is independent of the curvature of the link function. We conduct numerical experiments that are consistent with our theoretical findings.
Heesang Ann, Hyunjun Choi, Taehyun Hwang et al.· 0 citations
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\}$.
We study the contextual dynamic pricing problem under non-stationarity, where a firm sells products to $T$ sequentially arriving consumers that behave according to an unknown demand model that can change over time. The demand model is assumed to be a generalized linear model (GLM), allowing for a feature vector in $\mathbb{R}^d$ that encodes products and consumer information. To achieve optimal revenue (i.e., least regret), the firm needs to learn and exploit the unknown GLMs while monitoring for potential changes. We propose a multiscale change-point detection based algorithm that achieves a regret of order $\widetilde{O}(\sqrt{s_TdT}\wedge\{V_T^{1/3}d^{1/3}T^{2/3}+\sqrt{dT}\})$, where $s_T$ is the number of piecewise stationary segments and $V_T$ is a newly defined notion of design-adjusted variation budget of model parameters. Our algorithm is adaptive and does not require knowing $s_T$ or $V_T$. Moreover, to our knowledge, this is the first dynamic pricing algorithm that is adaptive to the nature of changes and achieves the best-of-both-worlds rate, thus closing a long-standing gap in the literature. We remark that, due to the varying contexts, existing works in the adaptive non-stationary bandit literature cannot be applied to achieve optimality for contextual dynamic pricing. The regret is further accompanied with a newly constructed minimax lower bound, confirming the optimality of our algorithm (up to logarithmic factors). Extensive numerical experiments are conducted to illustrate the efficiency and robustness of the proposed algorithm in non-stationary dynamic pricing.
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.
This paper studies the policy gradient update for a multi-arm bandit problem in diffusion environment that is described by a stochastic differential equation (SDE) under the continuous-time reinforcement learning framework by Wang et al. (2020), Jia and Zhou (2022b). With the logit parameterization for the stochastic policy, we show that it converges almost surely to the optimal arm under an arbitrary constant learning rate. Furthermore, we derive the non-asymptotic regret upper bound when the constant learning rate is below a time-invariant threshold; and the regret bound has order $O(\log T)$. We improve the analysis in Lattimore (2026a) for the same SDE by constructing a novel Lyapunov function and demonstrate the transparency of analyzing policy gradient using the tools in SDEs. In addition, the same Lyapunov function is also helpful in analyzing the discrete-time policy gradient algorithm.
Yanwei Jia, Du Ouyang· arXiv.org· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
