{
  "id": "1904.11131",
  "version": "v1",
  "published": "2019-04-25T02:38:33.000Z",
  "updated": "2019-04-25T02:38:33.000Z",
  "title": "Lipschitz Bandit Optimization with Improved Efficiency",
  "authors": [
    "Xu Zhu",
    "David B. Dunson"
  ],
  "comment": "12 pages, 0 figure",
  "categories": [
    "cs.LG",
    "cs.AI",
    "math.OC",
    "stat.ML"
  ],
  "abstract": "We consider the Lipschitz bandit optimization problem with an emphasis on practical efficiency. Although there is rich literature on regret analysis of this type of problem, e.g., [Kleinberg et al. 2008, Bubeck et al. 2011, Slivkins 2014], their proposed algorithms suffer from serious practical problems including extreme time complexity and dependence on oracle implementations. With this motivation, we propose a novel algorithm with an Upper Confidence Bound (UCB) exploration, namely Tree UCB-Hoeffding, using adaptive partitions. Our partitioning scheme is easy to implement and does not require any oracle settings. With a tree-based search strategy, the total computational cost can be improved to $\\mathcal{O}(T\\log T)$ for the first $T$ iterations. In addition, our algorithm achieves the regret lower bound up to a logarithmic factor.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2019-04-25T02:38:33.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "efficiency",
      "lipschitz bandit optimization problem",
      "regret lower bound",
      "total computational cost",
      "upper confidence bound"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 12,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}