LemmaStatement: Literature-sourcedProof: AI-adaptedPipeline-generatedprecheck pass

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-arm regret decomposes into expected action counts

Statement

Let $T, N \geq 1$ be integers, let $(Ω, F, P)$ be a probability space, and let $A_{t} : Ω \to [N]$ be measurable arm choices and $Y_{t} : Ω \to R$ integrable rewards for $t = 1, \dots, T$ . Let $μ_{1}, \dots, μ_{N} \in R$ be finite arm means and assume the conditional-mean identity

E ⁣ [Y_{t} 1_{{A_{t} = i}}] = μ_{i} P (A_{t} = i) (t = 1, \dots, T, i \in [N]) .

Set $μ^{*} : = \max_{i \in [N]} μ_{i}$ , define the pseudo-regret ${\overset{ˉ}{R}}_{T} : = \sum_{t = 1}^{T} (μ^{*} - μ_{A_{t}})$ , the realized reward regret $R_{T}^{r e w} : = \sum_{t = 1}^{T} (μ^{*} - Y_{t})$ , and the number of pulls of arm $i$ by $N_{i} (T) : = \sum_{t = 1}^{T} 1_{{A_{t} = i}}$ . Then

E [R_{T}^{r e w}] = E [{\overset{ˉ}{R}}_{T}] = \sum_{i = 1}^{N} (μ^{*} - μ_{i}) E [N_{i} (T)] .

Statement references

Tor Lattimore and Csaba Szepesvári, Bandit Algorithms: §§4.4–4.5, PDF pp. 68–71.

Elad Hazan, Introduction to Online Convex Optimization, second edition: §1.1, PDF pp. 23–24.

Facts & Assumptions

Given: The finite stochastic-arm model in the statement, integrable rewards $Y_{t}$ , measurable choices $A_{t} \in [N]$ , and finite means satisfying the stated conditional-mean identity.

[F1]

Expectation of an integrable real random variable is its Lebesgue integral on the probability space (Expectation of a nonnegative or integrable random variable).

[F2]

Expectation is linear for finite linear combinations of integrable random variables (Linearity, monotonicity, and the modulus bound for expectation).

[F3]

For every measurable event $B$ , $E [1_{B}] = P (B)$ (The expectation of an indicator is the probability of the event).

[A1]

In the fixed-law finite-arm model, for any round $t$ , arm $i$ , and event $B$ determined by the pre-reward history and chosen arm with $B \subseteq {A_{t} = i}$ , $E [Y_{t} 1_{B}] = μ_{i} P (B)$ (Adversary and feedback models). In particular, this holds for $B = {A_{t} = i}$ .

Proof

1.1givenA1F1F2

For each fixed $t$ , the events $E_{t, i} : = {A_{t} = i}$ , $i \in [N]$ , are a measurable partition of $Ω$ , because $A_{t}$ takes exactly one value in $[N]$ . The conditional-mean hypothesis gives $E [Y_{t} 1_{E_{t, i}}] = μ_{i} P (E_{t, i})$ . Since $Y_{t} = \sum_{i = 1}^{N} Y_{t} 1_{E_{t, i}}$ pointwise and the sum is finite, linearity of expectation gives $E [Y_{t}] = \sum_{i = 1}^{N} μ_{i} P (E_{t, i})$ .

1.2givenF2F3algebra

Pointwise, $μ_{A_{t}} = \sum_{i = 1}^{N} μ_{i} 1_{E_{t, i}}$ and $μ^{*} = \sum_{i = 1}^{N} μ^{*} 1_{E_{t, i}}$ . Thus ${\overset{ˉ}{R}}_{T} = \sum_{t = 1}^{T} \sum_{i = 1}^{N} (μ^{*} - μ_{i}) 1_{E_{t, i}}$ . Linearity of expectation and $E [1_{E_{t, i}}] = P (E_{t, i})$ yield $E [{\overset{ˉ}{R}}_{T}] = \sum_{t = 1}^{T} \sum_{i = 1}^{N} (μ^{*} - μ_{i}) P (E_{t, i})$ .

2.1givenF1F2F3step 1.1step 1.2algebra

Linearity of expectation and $E [1_{Ω}] = P (Ω) = 1$ give $E [R_{T}^{r e w}] = T μ^{*} - \sum_{t = 1}^{T} E [Y_{t}]$ . Substituting step 1.1 and rearranging the finite sums gives $E [R_{T}^{r e w}] = \sum_{t = 1}^{T} \sum_{i = 1}^{N} (μ^{*} - μ_{i}) P (E_{t, i})$ , which equals the expression in step 1.2.

3.1givenF2F3step 1.2algebra∎

Since $N_{i} (T) = \sum_{t = 1}^{T} 1_{E_{t, i}}$ , linearity of expectation and the indicator expectation identity give $E [N_{i} (T)] = \sum_{t = 1}^{T} P (E_{t, i})$ . Summing these equalities over the finite set of arms with coefficients $μ^{*} - μ_{i}$ identifies the result from step 1.2 with $\sum_{i = 1}^{N} (μ^{*} - μ_{i}) E [N_{i} (T)]$ and proves the claimed identity.

Depends on

Used by

Two stochastic arms: pseudo-regret and reward regret Example
Expected regret of explore-then-commit Theorem
Gap-dependent expected regret of UCB Theorem
Gap-free expected regret of UCB Theorem

Dependency tree · two levels

18 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)
Elad Hazan, Introduction to Online Convex Optimization, second edition (standard reference, not scraped)