Regret Analysis of Sleeping Competing Bandits

• URL: http://arxiv.org/abs/2603.19700v1
• Date: Fri, 20 Mar 2026 07:11:28 GMT
• Title: Regret Analysis of Sleeping Competing Bandits
• Abstract summary: We present an algorithm that simultaneously achieves an regret bound of $mathrmOleft(NKlog T_i/2right)$ under reasonable assumptions.<n>We also provide a regret lower bound of $mathrmleft( N(K-N+1)log T_i/2 right)$ under the same assumptions.
• Score: 0.2291770711277359
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The Competing Bandits framework is a recently emerging area that integrates multi-armed bandits in online learning with stable matching in game theory. While conventional models assume that all players and arms are constantly available, in real-world problems, their availability can vary arbitrarily over time. In this paper, we formulate this setting as Sleeping Competing Bandits. To analyze this problem, we naturally extend the regret definition used in existing competing bandits and derive regret bounds for the proposed model. We propose an algorithm that simultaneously achieves an asymptotic regret bound of $\mathrm{O}\left(NK\log T_{i}/Δ^2\right)$ under reasonable assumptions, where $N$ is the number of players, $K$ is the number of arms, $T_{i}$ is the number of rounds of each player $p_i$, and $Δ$ is the minimum reward gap. We also provide a regret lower bound of $\mathrmΩ\left( N(K-N+1)\log T_{i}/Δ^2 \right)$ under the same assumptions. This implies that our algorithm is asymptotically optimal in the regime where the number of arms $K$ is relatively larger than the number of players $N$.

Related papers

• Corrupted Learning Dynamics in Games [62.73758165845971]
  An equilibrium can be computed at a fast rate of $O(log T)$ when all players follow the optimistic follow-the-regularized-leader (OFTRL)<n>We present corrupted learning dynamics that adaptively find an equilibrium at a rate that depends on the extent to which each player deviates from the strategy suggested by the prescribed algorithm.
  arXiv  Detail & Related papers  (2024-12-10T02:23:44Z)
• An Asymptotically Optimal Batched Algorithm for the Dueling Bandit Problem [13.69077222007053]
  We study the $K$-armed dueling bandit problem, a variation of the traditional multi-armed bandit problem in which feedback is obtained in the form of pairwise comparisons. We obtain regret of $O(K2log(K)) + O(Klog(T))$ in $O(log(T))$ rounds, where $T$ is the time horizon. In computational experiments over a variety of real-world datasets, we observe that our algorithm using $O(log(T))$ rounds achieves almost the same performance as fully
  arXiv  Detail & Related papers  (2022-09-25T00:23:55Z)
• Corralling a Larger Band of Bandits: A Case Study on Switching Regret for Linear Bandits [99.86860277006318]
  We consider the problem of combining and learning over a set of adversarial algorithms with the goal of adaptively tracking the best one on the fly. The CORRAL of Agarwal et al. achieves this goal with a regret overhead of order $widetildeO(sqrtd S T)$ where $M$ is the number of base algorithms and $T$ is the time horizon. Motivated by this issue, we propose a new recipe to corral a larger band of bandit algorithms whose regret overhead has only emphlogarithmic dependence on $M$ as long
  arXiv  Detail & Related papers  (2022-02-12T21:55:44Z)
• Differentially Private Multi-Armed Bandits in the Shuffle Model [58.22098764071924]
  We give an $(varepsilon,delta)$-differentially private algorithm for the multi-armed bandit (MAB) problem in the shuffle model. Our upper bound almost matches the regret of the best known algorithms for the centralized model, and significantly outperforms the best known algorithm in the local model.
  arXiv  Detail & Related papers  (2021-06-05T14:11:01Z)
• Bandits with many optimal arms [68.17472536610859]
  We write $p*$ for the proportion of optimal arms and $Delta$ for the minimal mean-gap between optimal and sub-optimal arms. We characterize the optimal learning rates both in the cumulative regret setting, and in the best-arm identification setting.
  arXiv  Detail & Related papers  (2021-03-23T11:02:31Z)
• No Discounted-Regret Learning in Adversarial Bandits with Delays [40.670563413892154]
  We show that the expected discounted ergodic distribution of play converges to the set of coarse correlated equilibrium (CCE) if the algorithms have "no discounted-regret" For a zero-sum game, we show that no discounted-regret is sufficient for the discounted ergodic average of play to converge to the set of Nash equilibria.
  arXiv  Detail & Related papers  (2021-03-08T05:15:31Z)
• Combinatorial Bandits without Total Order for Arms [52.93972547896022]
  We present a reward model that captures set-dependent reward distribution and assumes no total order for arms. We develop a novel regret analysis and show an $Oleft(frack2 n log Tepsilonright)$ gap-dependent regret bound as well as an $Oleft(k2sqrtn T log Tright)$ gap-independent regret bound.
  arXiv  Detail & Related papers  (2021-03-03T23:08:59Z)
• Near-Optimal Regret Bounds for Contextual Combinatorial Semi-Bandits with Linear Payoff Functions [53.77572276969548]
  We show that the C$2$UCB algorithm has the optimal regret bound $tildeO(dsqrtkT + dk)$ for the partition matroid constraints. For general constraints, we propose an algorithm that modifies the reward estimates of arms in the C$2$UCB algorithm.
  arXiv  Detail & Related papers  (2021-01-20T04:29:18Z)
• Impact of Representation Learning in Linear Bandits [83.17684841392754]
  We study how representation learning can improve the efficiency of bandit problems. We present a new algorithm which achieves $widetildeO(TsqrtkN + sqrtdkNT)$ regret, where $N$ is the number of rounds we play for each bandit.
  arXiv  Detail & Related papers  (2020-10-13T16:35:30Z)
• Blocking Bandits [33.14975454724348]
  We consider a novel multi-armed bandit setting, where playing an arm makes it unavailable for a fixed number of time slots thereafter. We show that with prior knowledge of the rewards and delays of all the arms, the problem of optimizing cumulative reward does not admit any pseudo-polynomial time algorithm. We design a UCB based algorithm which is shown to have $c log T + o(log T)$ cumulative regret against the greedy algorithm.
  arXiv  Detail & Related papers  (2019-07-27T20:42:01Z)

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.