{
  "id": "2103.13059",
  "version": "v1",
  "published": "2021-03-24T10:14:16.000Z",
  "updated": "2021-03-24T10:14:16.000Z",
  "title": "Towards Optimal Algorithms for Multi-Player Bandits without Collision Sensing Information",
  "authors": [
    "Wei Huang",
    "Richard Combes",
    "Cindy Trinh"
  ],
  "comment": "23 pages",
  "categories": [
    "stat.ML",
    "cs.LG"
  ],
  "abstract": "We propose a novel algorithm for multi-player multi-armed bandits without collision sensing information. Our algorithm circumvents two problems shared by all state-of-the-art algorithms: it does not need as an input a lower bound on the minimal expected reward of an arm, and its performance does not scale inversely proportionally to the minimal expected reward. We prove a theoretical regret upper bound to justify these claims. We complement our theoretical results with numerical experiments, showing that the proposed algorithm outperforms state-of-the-art in practice as well.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2021-03-24T10:14:16.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "collision sensing information",
      "multi-player bandits",
      "optimal algorithms",
      "algorithm outperforms state-of-the-art",
      "minimal expected reward"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 23,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}