{
  "id": "1906.06594",
  "version": "v1",
  "published": "2019-06-15T17:39:18.000Z",
  "updated": "2019-06-15T17:39:18.000Z",
  "title": "The True Sample Complexity of Identifying Good Arms",
  "authors": [
    "Julian Katz-Samuels",
    "Kevin Jamieson"
  ],
  "categories": [
    "stat.ML",
    "cs.LG"
  ],
  "abstract": "We consider two multi-armed bandit problems with $n$ arms: (i) given an $\\epsilon > 0$, identify an arm with mean that is within $\\epsilon$ of the largest mean and (ii) given a threshold $\\mu_0$ and integer $k$, identify $k$ arms with means larger than $\\mu_0$. Existing lower bounds and algorithms for the PAC framework suggest that both of these problems require $\\Omega(n)$ samples. However, we argue that these definitions not only conflict with how these algorithms are used in practice, but also that these results disagree with intuition that says (i) requires only $\\Theta(\\frac{n}{m})$ samples where $m = |\\{ i : \\mu_i > \\max_{i \\in [n]} \\mu_i - \\epsilon\\}|$ and (ii) requires $\\Theta(\\frac{n}{m}k)$ samples where $m = |\\{ i : \\mu_i > \\mu_0 \\}|$. We provide definitions that formalize these intuitions, obtain lower bounds that match the above sample complexities, and develop explicit, practical algorithms that achieve nearly matching upper bounds.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2019-06-15T17:39:18.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "true sample complexity",
      "algorithms",
      "pac framework",
      "largest mean",
      "results disagree"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}