AlgorithmAlgorithm: Literature-sourcedProof: Not applicablePipeline-generated

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

Finite-horizon upper-confidence-bound bandit algorithm

Definition

Input integers $k, n$ with $1 \leq k \leq n$ , a confidence parameter $δ \in (0, 1)$ , and access to an $n$ -round $k$ -armed stochastic bandit. Output the selected arms $A_{1}, \dots, A_{n}$ .

Initialize by choosing each arm once: set $A_{t} = t$ for $t = 1, \dots, k$ , and observe each reward.
For each round $t = k + 1, \dots, n$ , compute $T_{i} (t - 1) = \sum_{s = 1}^{t - 1} 1_{{A_{s} = i}}$ for every arm $i$ . If $T_{i} (t - 1) > 0$ , first set ${\hat{μ}}_{i} (t - 1) = (\sum_{s = 1}^{t - 1} 1_{{A_{s} = i}} Y_{s}) / T_{i} (t - 1)$ and then set $U_{i} (t - 1) = {\hat{μ}}_{i} (t - 1) + \sqrt{2 \log (1 / δ) / T_{i} (t - 1)}$ . If $T_{i} (t - 1) = 0$ , set $U_{i} (t - 1) = + \infty$ .
Choose the least index $i$ attaining $\max_{j \in [k]} U_{j} (t - 1)$ as $A_{t}$ , then observe $Y_{t}$ .

Definition references

Finite stochastic bandit model, gaps, and regret: the finite arm set, horizon, pull counts, observed rewards, and round order.

The natural logarithm as the inverse of the exponential function: $\log$ is the inverse of the real exponential on positive reals.

Order, continuity, range, and the product, quotient, and reciprocal laws for the natural logarithm: the natural logarithm is increasing and satisfies the product and quotient laws.

Tor Lattimore and Csaba Szepesvári, Bandit Algorithms: Chapter 7 §7.1, Algorithm 3, PDF p. 112 / printed p. 103.

Depends on

Used by

Dependency tree · two levels

17 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

Tor Lattimore and Csaba Szepesvári, Bandit Algorithms (standard reference, not scraped)