A Further Efficient Algorithm with Best-of-Both-Worlds Guarantees for $m$-Set Semi-Bandit Problem

• URL: http://arxiv.org/abs/2603.11764v1
• Date: Thu, 12 Mar 2026 10:11:50 GMT
• Title: A Further Efficient Algorithm with Best-of-Both-Worlds Guarantees for $m$-Set Semi-Bandit Problem
• Abstract summary: This paper studies the optimality and complexity of Follow-the-Perturbed-Leader (FTPL) policy in $m$-set semi-bandit problems.<n>We show that FTPL with Fréchet and distributions with certain parameters achieves the best possible regret of $O(sqrtmdT)$ in adversarial setting.<n>We also extend the conditional geometric resampling to $m$-set semi-bandits for efficient loss estimation in FTPL.
• Score: 11.27658240767421
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This paper studies the optimality and complexity of Follow-the-Perturbed-Leader (FTPL) policy in $m$-set semi-bandit problems. FTPL has been studied extensively as a promising candidate of an efficient algorithm with favorable regret for adversarial combinatorial semi-bandits. Nevertheless, the optimality of FTPL has still been unknown unlike Follow-the-Regularized-Leader (FTRL) whose optimality has been proved for various tasks of online learning. In this paper, we extend the analysis of FTPL with geometric resampling (GR) to $m$-set semi-bandits, which is a special case of combinatorial semi-bandits, showing that FTPL with Fréchet and Pareto distributions with certain parameters achieves the best possible regret of $O(\sqrt{mdT})$ in adversarial setting. We also show that FTPL with Fréchet and Pareto distributions with a certain parameter achieves a logarithmic regret for stochastic setting, meaning the Best-of-Both-Worlds optimality of FTPL for $m$-set semi-bandit problems. Furthermore, we extend the conditional geometric resampling to $m$-set semi-bandits for efficient loss estimation in FTPL, reducing the computational complexity from $O(d^2)$ of the original geometric resampling to $O(md(\log(d/m)+1))$ without sacrificing the regret performance.

Related papers

• Closing the Approximation Gap of Partial AUC Optimization: A Tale of Two Formulations [121.39938773554523]
  The Area Under the ROC Curve (AUC) is a pivotal evaluation metric in real-world scenarios with both class imbalance and decision constraints.<n>We present two simple instance-wise minimax reformulations to close the approximation gap of PAUC optimization.<n>The resulting algorithms enjoy a linear per-iteration computational complexity w.r.t. the sample size and a convergence rate of $O(-2/3)$ for typical one-way and two-way PAUCs.
  arXiv  Detail & Related papers  (2025-12-01T02:52:33Z)
• Efficient Best-of-Both-Worlds Algorithms for Contextual Combinatorial Semi-Bandits [3.448177863267093]
  We introduce the first best-of-both-worlds algorithm for contextual semi-bandits that simultaneously guarantees $widetildemathcalO(sqrtT)$ regret.<n>By leveraging the Karush-Kuhn-Tucker conditions, we transform the $K$ convex projection problem into a single-dimensional root-finding problem.<n> Empirical evaluations demonstrate that this combined strategy not only attains the attractive regret bounds of best-of-both-worlds algorithms but also delivers substantial per-round speed-ups.
  arXiv  Detail & Related papers  (2025-08-26T07:51:22Z)
• Note on Follow-the-Perturbed-Leader in Combinatorial Semi-Bandit Problems [10.435741631709403]
  We study the optimality and complexity of Follow-the-Perturbed-Leader ( FTPL) policy in size-invariant semi-bandit problems.<n>We extend the conditional geometric resampling (CGR) to size-invariant semi-bandit setting, which reduces the computational complexity from $O(d2)$ of original GR to $Oleft(mdleft(log(d/m)+1right)$ without sacrificing the regret performance of FTPL.
  arXiv  Detail & Related papers  (2025-06-14T13:06:30Z)
• Follow-the-Perturbed-Leader Approaches Best-of-Both-Worlds for the m-Set Semi-Bandit Problems [18.74680577173648]
  We consider a common case of the $m$-set semi-bandit problem, where the learner exactly selects $m$ arms from the total $d$ arms.<n>We show that FTPL with a Fr'echet perturbation also enjoys the near optimal regret bound $mathcalO(sqrtnm(sqrtdlog(d)+m5/6)$ in the adversarial setting.
  arXiv  Detail & Related papers  (2025-04-09T22:07:01Z)
• Sign Operator for Coping with Heavy-Tailed Noise in Non-Convex Optimization: High Probability Bounds Under $(L_0, L_1)$-Smoothness [74.18546828528298]
  We show that SignSGD with Majority Voting can robustly work on the whole range of complexity with $kappakappakappakappa-1right, kappakappakappa-1right, kappakappakappa-1right, kappakappakappa-1right, kappakappakappa-1right, kappakappakappa-1right, kappakappakappa-1right, kappa
  arXiv  Detail & Related papers  (2025-02-11T19:54:11Z)
• Optimism in the Face of Ambiguity Principle for Multi-Armed Bandits [6.075593833879357]
  Follow-The-Regularized-Leader (FTRL) algorithms often enjoy optimal regret for adversarial as well as bandit problems.<n>We propose a new FTPL algorithm that generates optimal policies for both adversarial and multi-armed bandits.
  arXiv  Detail & Related papers  (2024-09-30T16:00:23Z)
• Follow-the-Perturbed-Leader with Fr\'{e}chet-type Tail Distributions: Optimality in Adversarial Bandits and Best-of-Both-Worlds [43.35179630620512]
  We study the optimality of the Follow-the-Perturbed-Leader ( FTPL) policy in both adversarial and $K$-armed bandits. We establish a sufficient condition for perturbations to achieve $mathcalO(sqrtKT)$ regrets in the adversarial setting.
  arXiv  Detail & Related papers  (2024-03-08T08:07:26Z)
• Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path [80.60592344361073]
  We study the Shortest Path (SSP) problem with a linear mixture transition kernel. An agent repeatedly interacts with a environment and seeks to reach certain goal state while minimizing the cumulative cost. Existing works often assume a strictly positive lower bound of the iteration cost function or an upper bound of the expected length for the optimal policy.
  arXiv  Detail & Related papers  (2024-02-14T07:52:00Z)
• Non-stationary Delayed Online Convex Optimization: From Full-information to Bandit Setting [71.82716109461967]
  We propose an algorithm called Mild-OGD for the full-information case, where delayed gradients are available.<n>We show that the dynamic regret of Mild-OGD can be automatically bounded by $O(sqrtbardT(P_T+1))$ under the in-order assumption.<n>We also develop a bandit variant of Mild-OGD for a more challenging case with only delayed loss values.
  arXiv  Detail & Related papers  (2023-05-20T07:54:07Z)
• Matching Pursuit Based Scheduling for Over-the-Air Federated Learning [67.59503935237676]
  This paper develops a class of low-complexity device scheduling algorithms for over-the-air learning via the method of federated learning. Compared to the state-of-the-art proposed scheme, the proposed scheme poses a drastically lower efficiency system. The efficiency of the proposed scheme is confirmed via experiments on the CIFAR dataset.
  arXiv  Detail & Related papers  (2022-06-14T08:14:14Z)
• Near-Optimal No-Regret Learning for Correlated Equilibria in Multi-Player General-Sum Games [104.74734408204749]
  We show that if all agents in a multi-player general-sum normal-form game employ Optimistic Multiplicative Weights Update (OMWU), the external regret of every player is $O(textrmpolylog(T))$ after $T$ repetitions of the game. We extend their result from external regret to internal regret and swap regret, thereby establishing uncoupled learning dynamics that converge to an approximate correlated equilibrium.
  arXiv  Detail & Related papers  (2021-11-11T01:19:53Z)
• Efficient Optimistic Exploration in Linear-Quadratic Regulators via Lagrangian Relaxation [107.06364966905821]
  We study the exploration-exploitation dilemma in the linear quadratic regulator (LQR) setting. Inspired by the extended value iteration algorithm used in optimistic algorithms for finite MDPs, we propose to relax the optimistic optimization of ofulq. We show that an $epsilon$-optimistic controller can be computed efficiently by solving at most $Obig(log (1/epsilon)big)$ Riccati equations.
  arXiv  Detail & Related papers  (2020-07-13T16:30:47Z)

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.