Toward Optimal Second-Order Path-Length Guarantee for Adversarial Multi-Armed Bandits

• URL: http://arxiv.org/abs/2608.15996v1
• Date: Mon, 17 Aug 2026 01:17:42 GMT
• Title: Toward Optimal Second-Order Path-Length Guarantee for Adversarial Multi-Armed Bandits
• Abstract summary: We study second-order path-length regret in adversarial $K$-armed bandits against oblivious loss sequences.<n>Our algorithm achieves $mathcalOleft(Klog(KT)+sqrtKlog(KT)bigl (1+Q_infty,2bigr)right)$ expected regret when $Q_infty,2$ is known, where $T$ is the horizon.
• Score: 13.08870048693199
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study second-order path-length regret in adversarial $K$-armed bandits against oblivious loss sequences. Bubeck et al. [2019] designed an algorithm that achieves $\widetilde{\mathcal{O}}(K+\sqrt{KQ_{\infty,1}})$ regret, where $Q_{\infty,1}$ is the first-order path length, and left open whether $\widetilde{\mathcal{O}}(\text{poly}(K)\sqrt{1+Q_{\infty,2}})$ regret is achievable under bandit feedback, where $Q_{\infty,2}$ is the second-order path length. Somewhat surprisingly, we resolve this question positively by showing that with a more involved analysis, the exact same algorithm of Bubeck et al. [2019] achieves $\mathcal{O}\left(K\log(KT)+\sqrt{K\log(KT)\bigl(1+Q_{\infty,2}\bigr)}\right)$ expected regret when $Q_{\infty,2}$ is known, where $T$ is the horizon. This matches the $Ω(\sqrt{KQ_{\infty,2}})$ lower bound up to logarithmic factors and additive terms. We further remove the knowledge of $Q_{\infty,2}$ using an adaptive restart scheme whose path-length estimator has uniformly bounded increments.

Related papers

• Nearly Minimax-Optimal Regret for Linear Contextual Bandits with Arbitrary Adaptive Action Sets [10.262827207917585]
  We study linear contextual bandits with arbitrary action menus that may depend on the fixed parameter and the interaction history.<n>We establish matching upper and lower bounds, up to logarithmic factors.
  arXiv  Detail & Related papers  (2026-09-14T07:57:45Z)
• High-Dimensional Procrustes Matching via Tree Counts [5.464035038606368]
  Procrustes matching problem asks us to recover the unknown permutation of $[n]$ that aligns the two sets.<n>We show that exact recovery is possible when $2 gtrsim maxlog n/d,sqrtlog n/n$.<n>We also carry out a low-degree advantage calculation, which suggests that condition $2 > sqrt$ is necessary for any tree-counting algorithm.
  arXiv  Detail & Related papers  (2026-07-09T14:33:47Z)
• Deterministic Hardness of Approximation of Unique-SVP and GapSVP in $\ell_p$ norms for $p>2$ [0.0]
  We establish deterministic hardness of approximation results for the Shortest Vector Problem in $ell_p$ norm ($mathsfSVP_p$) and for Unique-SVP ($mathsfuSVP_p$)<n>For every $p > 2$, we prove constant-ratio hardness: no-time algorithm approximates $mathsfSVP_p$ or $mathsfuSVP_p$ within a ratio of $sqrt2 - o(1)$.
  arXiv  Detail & Related papers  (2025-10-19T20:17:26Z)
• Batched Stochastic Bandit for Nondegenerate Functions [8.015503209312786]
  This paper studies batched bandit learning problems for nondegenerate functions.<n>We introduce an algorithm that solves the batched bandit problem for nondegenerate functions near-optimally.
  arXiv  Detail & Related papers  (2024-05-09T12:50:16Z)
• On the Minimax Regret for Online Learning with Feedback Graphs [5.721380617450645]
  We improve on the upper and lower bounds for the regret of online learning with strongly observable undirected feedback graphs. Our improved upper bound $mathcalObigl(sqrtalpha T(ln K)/(lnalpha)bigr)$ holds for any $alpha$ and matches the lower bounds for bandits and experts.
  arXiv  Detail & Related papers  (2023-05-24T17:40:57Z)
• Near-Optimal Regret Bounds for Multi-batch Reinforcement Learning [54.806166861456035]
  We study the episodic reinforcement learning (RL) problem modeled by finite-horizon Markov Decision Processes (MDPs) with constraint on the number of batches. We design a computational efficient algorithm to achieve near-optimal regret of $tildeO(sqrtSAH3Kln (1/delta))$tildeO(cdot) hides logarithmic terms of $(S,A,H,K)$ in $K$ episodes. Our technical contribution are two-fold: 1) a near-optimal design scheme to explore
  arXiv  Detail & Related papers  (2022-10-15T09:22:22Z)
• Delaytron: Efficient Learning of Multiclass Classifiers with Delayed Bandit Feedbacks [6.624726878647541]
  Adaptive Delaytron achieves a regret bound of $mathcalOleft(sqrtfrac2 Kgammaleft[fracT2+left(2+fracL2R2Vert WVert_F2right)sum_t=1Td_tright. We show that Adaptive Delaytron achieves a regret bound of $mathcalOleft(sqrtfrac2 Kgammaleft[fracT2
  arXiv  Detail & Related papers  (2022-05-17T11:12:20Z)
• Nearly Horizon-Free Offline Reinforcement Learning [97.36751930393245]
  We revisit offline reinforcement learning on episodic time-homogeneous Markov Decision Processes with $S$ states, $A$ actions and planning horizon $H$. We obtain the first set of nearly $H$-free sample complexity bounds for evaluation and planning using the empirical MDPs.
  arXiv  Detail & Related papers  (2021-03-25T18:52:17Z)
• Linear Bandits on Uniformly Convex Sets [88.3673525964507]
  Linear bandit algorithms yield $tildemathcalO(nsqrtT)$ pseudo-regret bounds on compact convex action sets. Two types of structural assumptions lead to better pseudo-regret bounds.
  arXiv  Detail & Related papers  (2021-03-10T07:33:03Z)
• Optimal Regret Algorithm for Pseudo-1d Bandit Convex Optimization [51.23789922123412]
  We study online learning with bandit feedback (i.e. learner has access to only zeroth-order oracle) where cost/reward functions admit a "pseudo-1d" structure. We show a lower bound of $min(sqrtdT, T3/4)$ for the regret of any algorithm, where $T$ is the number of rounds. We propose a new algorithm sbcalg that combines randomized online gradient descent with a kernelized exponential weights method to exploit the pseudo-1d structure effectively.
  arXiv  Detail & Related papers  (2021-02-15T08:16:51Z)
• Taking a hint: How to leverage loss predictors in contextual bandits? [63.546913998407405]
  We study learning in contextual bandits with the help of loss predictors. We show that the optimal regret is $mathcalO(minsqrtT, sqrtmathcalETfrac13)$ when $mathcalE$ is known.
  arXiv  Detail & Related papers  (2020-03-04T07:36:38Z)
• Agnostic Q-learning with Function Approximation in Deterministic Systems: Tight Bounds on Approximation Error and Sample Complexity [94.37110094442136]
  We study the problem of agnostic $Q$-learning with function approximation in deterministic systems. We show that if $delta = Oleft(rho/sqrtdim_Eright)$, then one can find the optimal policy using $Oleft(dim_Eright)$.
  arXiv  Detail & Related papers  (2020-02-17T18:41:49Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.