{
  "id": "1209.2693",
  "version": "v1",
  "published": "2012-09-12T19:14:21.000Z",
  "updated": "2012-09-12T19:14:21.000Z",
  "title": "Regret Bounds for Restless Markov Bandits",
  "authors": [
    "Ronald Ortner",
    "Daniil Ryabko",
    "Peter Auer",
    "Rémi Munos"
  ],
  "comment": "In proceedings of The 23rd International Conference on Algorithmic Learning Theory (ALT 2012)",
  "journal": "Proceedings of ALT, Lyon, France, LNCS 7568, pp.214-228, 2012",
  "categories": [
    "cs.LG",
    "math.OC",
    "stat.ML"
  ],
  "abstract": "We consider the restless Markov bandit problem, in which the state of each arm evolves according to a Markov process independently of the learner's actions. We suggest an algorithm that after $T$ steps achieves $\\tilde{O}(\\sqrt{T})$ regret with respect to the best policy that knows the distributions of all arms. No assumptions on the Markov chains are made except that they are irreducible. In addition, we show that index-based policies are necessarily suboptimal for the considered problem.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2012-09-12T19:14:21.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "regret bounds",
      "restless markov bandit problem",
      "arm evolves",
      "markov process",
      "markov chains"
    ],
    "tags": [
      "conference paper",
      "journal article"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2012arXiv1209.2693O"
    }
  }
}