{
  "id": "enwiki-001360960470",
  "slug": "explore-then-commit-algorithm",
  "title": "Explore-then-commit algorithm",
  "qid": "",
  "lead": "Explore Then Commit (ETC) is an algorithm for the multi-armed bandit problem focused on finding the best trade-off between exploration and exploitation.",
  "body": "Explore Then Commit (ETC) is an algorithm for the multi-armed bandit problem focused on finding the best trade-off between exploration and exploitation. R_T := \\sum_{a=1}^K \\Delta_a \\mathbb{E}[N_a(T)] where \\mu_a := \\mathbb{E}[\\nu_a] is the mean of arm a \\mu^* := \\max_a \\mu_a is the highest mean \\Delta_a := \\mu^* - \\mu_a N_a(t) is the number of pulls of arm a up to turn t The player has to find an algorithm that chooses at each turn t which arm to pull based on the previous actions and observations (a_s,X_s)_{s to minimize the regret R_T . This is a trade-off problem between exploration (finding the arm with the highest mean) and exploitation (playing the arm which is perceived to be the best as much as possible). R_T \\leq M \\sum_{i = 1}^K \\Delta_i + (T - M K) \\sum_{i=1}^K \\Delta_i \\exp\\left( -\\frac{M \\Delta_i^2}{4} \\right) the first term is considered the cost of the exploration M \\sum_{i = 1}^K \\Delta_i . The second term is the cost of not having explored enough, leading to a probability of not having an optimal arm as the arm with the highest empirical mean. (T - M K) \\sum_{i=1}^K \\Delta_i \\exp\\left( -\\frac{M \\Delta_i^2}{4} \\right) Increasing M increases the first term while decreasing the second term. The best possible M must depend on the (\\Delta_i)_i which is unknown by the player. For two arms with Gaussian distribution of variance 1 , it was proved that ETC cannot achieve the asymptotic optimal regret of the Equation of Lai-Robbins.",
  "categories": [
    "20165933",
    "20235111",
    "20476448",
    "23603337",
    "23617828",
    "26220375",
    "26709330",
    "27424735"
  ],
  "license": "CC BY-SA 4.0",
  "source_uri": "https://en.wikipedia.org/w/index.php?oldid=1360960470",
  "content_hash": "",
  "created_at": null,
  "updated_at": 1782321411.0,
  "claims": [],
  "contradictions": [],
  "confidence": 0.6,
  "csl": {
    "id": "enwiki-001360960470",
    "type": "webpage",
    "title": "Explore-then-commit algorithm",
    "author": [
      {
        "family": "Anticloud FZ LLE",
        "literal": "Anticloud FZ LLE"
      }
    ],
    "container-title": "encyclopegia.org",
    "publisher": "Anticloud FZ LLE",
    "publisher-place": "Dubai, United Arab Emirates",
    "URL": "https://encyclopegia.org/a/explore-then-commit-algorithm",
    "issued": {
      "date-parts": [
        [
          2026,
          11,
          18
        ]
      ]
    },
    "accessed": {
      "date-parts": [
        [
          2026,
          11,
          18
        ]
      ]
    },
    "license": "CC BY-SA 4.0",
    "DOI": "eo1:enwiki-001360960470",
    "isBasedOn": "https://en.wikipedia.org/w/index.php?oldid=1360960470",
    "note": "Immutable snapshot enwiki-001360960470"
  }
}