{
  "id": "2006.08850",
  "version": "v1",
  "published": "2020-06-16T00:58:40.000Z",
  "updated": "2020-06-16T00:58:40.000Z",
  "title": "Finding All ε-Good Arms in Stochastic Bandits",
  "authors": [
    "Blake Mason",
    "Lalit Jain",
    "Ardhendu Tripathy",
    "Robert Nowak"
  ],
  "comment": "93 total pages (8 main pages + appendices), 12 figures, submitted to NeurIPS 2020",
  "categories": [
    "stat.ML",
    "cs.LG"
  ],
  "abstract": "The pure-exploration problem in stochastic multi-armed bandits aims to find one or more arms with the largest (or near largest) means. Examples include finding an {\\epsilon}-good arm, best-arm identification, top-k arm identification, and finding all arms with means above a specified threshold. However, the problem of finding all {\\epsilon}-good arms has been overlooked in past work, although arguably this may be the most natural objective in many applications. For example, a virologist may conduct preliminary laboratory experiments on a large candidate set of treatments and move all {\\epsilon}-good treatments into more expensive clinical trials. Since the ultimate clinical efficacy is uncertain, it is important to identify all {\\epsilon}-good candidates. Mathematically, the all-{\\epsilon}-good arm identification problem presents significant new challenges and surprises that do not arise in the pure-exploration objectives studied in the past. We introduce two algorithms to overcome these and demonstrate their great empirical performance on a large-scale crowd-sourced dataset of 2.2M ratings collected by the New Yorker Caption Contest as well as a dataset testing hundreds of possible cancer drugs.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2020-06-16T00:58:40.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "stochastic bandits",
      "conduct preliminary laboratory experiments",
      "yorker caption contest",
      "stochastic multi-armed bandits aims",
      "large candidate set"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}