Finite stochastic bandit model, gaps, and regret

Fix positive integers $n$ and $k$, write $[k]=\{1,\dots ,k\}$, and let $(\mathrm{\Omega },\mathcal{F},\mathbb{P})$ be a probability space. A finite-horizon $k$-armed stochastic bandit in reward-stack form consists of probability measures $P_i$ on $(\mathbb{R},\mathcal{B}(\mathbb{R}))$ with finite first absolute moments, and an independent table of integrable real random variables $(X_{s,i}{)}_{1\le s\le n,i\in [k]}$ such that the table entries are mutually independent and each $X_{s,i}$ has law $P_i$. Its mean for arm $i$ is ${\mu }_i={\int }_{\mathbb{R}}x{P}_i(dx)=\mathbb{E}[X_{s,i}]$, which does not depend on $s$. The learner may also use a random element $U$ for private randomization, provided $\sigma (U)$ is independent of the sigma-algebra generated by the entire table; a deterministic learner uses a constant $U$.

A non-anticipating policy chooses a measurable arm $A_t\in [k]$ at each round $t\in [n]$ using only $U$ and the previously observed history $(A_1,Y_1,\dots ,A_{t-1},Y_{t-1})$. Write ${\mathcal{H}}_{t-1}=\sigma (U,A_1,Y_1,\dots ,A_{t-1},Y_{t-1})$ for that history sigma-algebra. Define the pull count $T_i(0)=0$ and

$$T_i(t)=\sum _{r=1}^t{\mathbf{1}}_{\{A_r=i\}},Y_t=X_{T_{A_t}(t),A_t}\mathrm{.}$$

Thus each time arm $i$ is selected the learner receives the next unused entry in arm $i$'s reward stack. Set

$${\mu }^{\ast }=\underset{i\in [k]}{\max }{\mu }_i,{\mathrm{\Delta }}_i={\mu }^{\ast }-{\mu }_i\ge 0,$$

define the pseudo-regret ${\bar{R}}_n={\sum }_{t=1}^n({\mu }^{\ast }-{\mu }_{A_t})$, and define the realized reward regret $R_n^{\mathrm{r}\mathrm{e}\mathrm{w}}=n{\mu }^{\ast }-{\sum }_{t=1}^n{Y}_t$ and expected reward regret $R_n=\mathbb{E}[R_n^{\mathrm{r}\mathrm{e}\mathrm{w}}]$.

Each $Y_t$ is integrable because it selects one entry of the finite table, so $\mathrm{\mid }{Y}_t\mathrm{\mid }\le {\sum }_{s=1}^n{\sum }_{i=1}^k\mathrm{\mid }{X}_{s,i}\mathrm{\mid }$ and the right-hand side is integrable. Hence $R_n^{\mathrm{r}\mathrm{e}\mathrm{w}}$ is integrable as well.

Online decision protocol: the learner chooses before the current round's feedback and uses only earlier revealed history.

Adversary and feedback models: a stochastic finite-arm environment has a fixed probability law for each arm, finite first moments, and the stated conditional reward-law convention.

Static, dynamic, interval, and strongly adaptive regret: pseudo-regret is the sum of mean gaps along the action sequence; realized reward regret subtracts the observed rewards; expected regret integrates realized regret.

Random elements and real random variables: table entries and learner randomization are measurable random elements, with the table entries real-valued.

Law or distribution of a random element: the law of a random element is the pushforward probability measure on its measurable target space.

Change of variables for expectation: expectation of an integrable measurable function of a random element equals its integral against the law, in particular for the identity function on the real line.

Expectation of a nonnegative or integrable random variable: expectation of an integrable real random variable is its Lebesgue integral.

Linearity, monotonicity, and the modulus bound for expectation: finite linear combinations of integrable random variables are integrable and expectation is linear.

Independent random elements: the table entries are mutually independent as random elements, and learner randomization is independent of the table.

Tor Lattimore and Csaba Szepesvári, Bandit Algorithms: §4.1, PDF p. 65 / printed p. 56; §§4.4–4.6, PDF pp. 69–74 / printed pp. 60–65.

Sébastien Bubeck and Nicolò Cesa-Bianchi, Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems: Chapter 2, PDF pp. 11–12 / printed pp. 8–9.