A High Performance, Low Complexity Algorithm for Multi-Player Bandits Without Collision Sensing Information

• URL: http://arxiv.org/abs/2102.10200v1
• Date: Fri, 19 Feb 2021 23:10:48 GMT
• Title: A High Performance, Low Complexity Algorithm for Multi-Player Bandits Without Collision Sensing Information
• Abstract summary: We propose Randomized Selfish KL-UCB, an algorithm with very low computational complexity, inspired by the Selfish KL-UCB algorithm. We show that it far outperforms state-of-the-art algorithms in almost all environments, sometimes by several orders of magnitude, and without the additional knowledge required by state-of-the-art algorithms.
• Score: 7.198362232890585
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Motivated by applications in cognitive radio networks, we consider the decentralized multi-player multi-armed bandit problem, without collision nor sensing information. We propose Randomized Selfish KL-UCB, an algorithm with very low computational complexity, inspired by the Selfish KL-UCB algorithm, which has been abandoned as it provably performs sub-optimally in some cases. We subject Randomized Selfish KL-UCB to extensive numerical experiments showing that it far outperforms state-of-the-art algorithms in almost all environments, sometimes by several orders of magnitude, and without the additional knowledge required by state-of-the-art algorithms. We also emphasize the potential of this algorithm for the more realistic dynamic setting, and support our claims with further experiments. We believe that the low complexity and high performance of Randomized Selfish KL-UCB makes it the most suitable for implementation in practical systems amongst known algorithms.

Related papers

• Optimal Centered Active Excitation in Linear System Identification [48.09783075634403]
  We propose an active learning algorithm for linear system identification with optimal centered noise excitation.<n>We first establish lower bounds of the sample complexity for any active learning algorithm to attain the prescribed accuracy and confidence levels.
  arXiv  Detail & Related papers  (2026-04-07T07:16:16Z)
• Fast Stochastic Greedy Algorithm for $k$-Submodular Cover Problem [2.8348950186890467]
  Existing algorithms for $k$SC often provide weak approximation guarantees or prohibitively high query complexity.<n>Our approach reduces the number of function evaluations, making it highly scalable and practical for large-scale real-world applications.
  arXiv  Detail & Related papers  (2025-11-02T09:39:06Z)
• A Multiagent Path Search Algorithm for Large-Scale Coalition Structure Generation [61.08720171136229]
  Coalition structure generation is a fundamental computational problem in multiagent systems. We develop SALDAE, a multiagent path finding algorithm for CSG that operates on a graph of coalition structures.
  arXiv  Detail & Related papers  (2025-02-14T15:21:27Z)
• Indexed Minimum Empirical Divergence-Based Algorithms for Linear Bandits [55.938644481736446]
  Indexed Minimum Empirical Divergence (IMED) is a highly effective approach to the multi-armed bandit problem. It has been observed to empirically outperform UCB-based algorithms and Thompson Sampling. We present novel linear versions of the IMED algorithm, which we call the family of LinIMED algorithms.
  arXiv  Detail & Related papers  (2024-05-24T04:11:58Z)
• An Optimal Algorithm for the Real-Valued Combinatorial Pure Exploration of Multi-Armed Bandit [65.268245109828]
  We study the real-valued pure exploration problem in the multi-armed bandit (R-CPE-MAB) Existing methods in the R-CPE-MAB can be seen as a special case of the so-called transductive linear bandits. We propose an algorithm named the gap-based exploration (CombGapE) algorithm, whose sample complexity matches the lower bound.
  arXiv  Detail & Related papers  (2023-06-15T15:37:31Z)
• Sparsity May Cry: Let Us Fail (Current) Sparse Neural Networks Together! [100.19080749267316]
  "Sparsity May Cry" Benchmark (SMC-Bench) is a collection of carefully-curated 4 diverse tasks with 10 datasets. SMC-Bench is designed to favor and encourage the development of more scalable and generalizable sparse algorithms.
  arXiv  Detail & Related papers  (2023-03-03T18:47:21Z)
• Genetic multi-armed bandits: a reinforcement learning approach for discrete optimization via simulation [0.0]
  This paper proposes a new algorithm, that combines the reinforcement learning domain of multi-armed bandits and random search strategies to solve discrete optimization problems via simulation. Our aim is to combine the property of multi-armed bandits with the ability of genetic algorithms to handle high-dimensional solution spaces.
  arXiv  Detail & Related papers  (2023-02-15T14:46:19Z)
• A Fast Algorithm for PAC Combinatorial Pure Exploration [21.376800678915558]
  We consider the problem of Combinatorial Pure Exploration (CPE), which deals with finding a set or arms with a high reward. Previous algorithms for this problem are highly computationally intensive, making them impractical even for mildly large problems. We propose a new CPE algorithm in the PAC setting, which is computationally light weight and can easily be applied to problems with tens of thousands of arms.
  arXiv  Detail & Related papers  (2021-12-08T09:52:56Z)
• Deep Upper Confidence Bound Algorithm for Contextual Bandit Ranking of Information Selection [0.0]
  Contextual multi-armed bandits (CMAB) have been widely used for learning to filter and prioritize information according to a user's interest. In this work, we analyze top-K ranking under the CMAB framework where the top-K arms are chosen iteratively to maximize a reward. We introduce a novel algorithm called the Deep Upper Confidence Bound (UCB) algorithm.
  arXiv  Detail & Related papers  (2021-10-08T13:32:14Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  This paper investigates the classical integer least-squares problem which estimates signals integer from linear models. The problem is NP-hard and often arises in diverse applications such as signal processing, bioinformatics, communications and machine learning. We propose a general hyper-accelerated tree search (HATS) algorithm by employing a deep neural network to estimate the optimal estimation for the underlying simplified memory-bounded A* algorithm.
  arXiv  Detail & Related papers  (2021-01-07T08:00:02Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  We investigate the problem of best-policy identification in discounted Markov Decision (MDPs) when the learner has access to a generative model. The advantages of state-of-the-art algorithms are discussed and illustrated.
  arXiv  Detail & Related papers  (2020-09-28T15:22:24Z)
• A black-box adversarial attack for poisoning clustering [78.19784577498031]
  We propose a black-box adversarial attack for crafting adversarial samples to test the robustness of clustering algorithms. We show that our attacks are transferable even against supervised algorithms such as SVMs, random forests, and neural networks.
  arXiv  Detail & Related papers  (2020-09-09T18:19:31Z)

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.