{
  "id": "1903.08600",
  "version": "v1",
  "published": "2019-03-20T16:34:11.000Z",
  "updated": "2019-03-20T16:34:11.000Z",
  "title": "Contextual Bandits with Random Projection",
  "authors": [
    "Xiaotian Yu"
  ],
  "categories": [
    "cs.LG",
    "stat.ML"
  ],
  "abstract": "Contextual bandits with linear payoffs, which are also known as linear bandits, provide a powerful alternative for solving practical problems of sequential decisions, e.g., online advertisements. In the era of big data, contextual data usually tend to be high-dimensional, which leads to new challenges for traditional linear bandits mostly designed for the setting of low-dimensional contextual data. Due to the curse of dimensionality, there are two challenges in most of the current bandit algorithms: the first is high time-complexity; and the second is extreme large upper regret bounds with high-dimensional data. In this paper, in order to attack the above two challenges effectively, we develop an algorithm of Contextual Bandits via RAndom Projection (\\texttt{CBRAP}) in the setting of linear payoffs, which works especially for high-dimensional contextual data. The proposed \\texttt{CBRAP} algorithm is time-efficient and flexible, because it enables players to choose an arm in a low-dimensional space, and relaxes the sparsity assumption of constant number of non-zero components in previous work. Besides, we provide a linear upper regret bound for the proposed algorithm, which is associated with reduced dimensions.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2019-03-20T16:34:11.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "contextual bandits",
      "random projection",
      "extreme large upper regret bounds",
      "linear upper regret bound",
      "linear bandits"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}