Stochastic finite-armed bandits — Examples

Let $m\ge 1$ be an integer, let $n\ge 2m+1$, and fix $0<\mathrm{\Delta }<1$. In a two-arm $n$-round bandit, let every reward-stack entry of arm 1 equal $1$ and every reward-stack entry of arm 2 equal $1-\mathrm{\Delta }$. Under explore-then-commit with exploration count $m$, the algorithm commits to arm 1 and has expected reward regret exactly $m\mathrm{\Delta }$. The expected-regret theorem gives the upper bound $m\mathrm{\Delta }+(n-2m)\mathrm{\Delta }{e}^{-m{\mathrm{\Delta }}^2\mathrm{/}4}$ for this instance.

Finite stochastic bandit model, gaps, and regret: arm means, gaps, and expected reward regret.

Centered 1-sub-Gaussian reward: the mean-centred MGF condition checked for deterministic rewards.

The exponential is positive and satisfies $\exp (-x)=1\mathrm{/}\exp (x)$: the exponential factor in the regret bound is positive.

Explore-then-commit for a finite stochastic bandit: the fixed round-robin exploration and empirical-mean commitment rule.

Expected regret of explore-then-commit: the expected-regret bound compared with the exact regret.

Fix any horizon $n\ge 1$ and take two arms with deterministic reward stacks $X_{s,1}=X_{s,2}=0$ for every $s\in [n]$. Then ${\mu }_1={\mu }_2={\mu }^{\ast }=0$ and ${\mathrm{\Delta }}_1={\mathrm{\Delta }}_2=0$. Every admissible policy has identically zero pseudo-regret and realized reward regret, so both expected regrets are zero.

Finite stochastic bandit model, gaps, and regret: the finite-arm means, gaps, pseudo-regret, and realized reward regret used in the example.

For $p\in \{2,3\}$, write ${\zeta }_p={\sum }_{j=1}^{\mathrm{\infty }}{j}^{-p}$, identifying each positive integer with its canonical real image. Let $\mathrm{\Omega }=\{1,2,\dots \}$ with its full power set, put $p_j=1\mathrm{/}({\zeta }_3{j}^3)$, and define the probability measure $Q={\sum }_{j=1}^{\mathrm{\infty }}{p}_j{\delta }_j$ by its countable weighted sum of Dirac measures. Let $X:\mathrm{\Omega }\to \mathbb{R}$ be the inclusion map and let $P_X$ be its law. The reward has finite mean ${\mathbb{E}}_Q[X]={\int }_{\mathbb{R}}x{P}_X(dx)={\zeta }_2\mathrm{/}{\zeta }_3$, but ${\int }_{\mathbb{R}}\exp (\lambda x)P_X(dx)=+\mathrm{\infty }$ for every $\lambda >0$. Thus this finite-mean reward lies outside the centered 1-sub-Gaussian model.

Finite stochastic bandit model, gaps, and regret: a stochastic arm law is a probability measure on the real Borel space with finite first absolute moment.

The zeta sums at 2 and 3 are finite: the two normalizing sums ${\zeta }_2$ and ${\zeta }_3$ are finite and positive.

Expectation of a countably valued nonnegative random variable is its weighted series: a countably valued nonnegative random variable has expectation equal to its weighted series.

Centered 1-sub-Gaussian reward: a 1-sub-Gaussian reward has a finite centered MGF bounded by $\exp ({\lambda }^2\mathrm{/}2)$ for every real $\lambda$.

Probability measures and probability spaces: a probability measure has total mass one.

The Dirac set function at a point: the Dirac measure at a point assigns mass one to sets containing that point and zero otherwise.

A Dirac set function is a probability measure: each Dirac measure is a probability measure.

Nonnegative scalar multiples and countable weighted sums of measures: countable weighted sums of measures are defined pointwise by nonnegative extended sums.

Nonnegative scalar multiples and countable weighted sums of measures are measures: a countable nonnegative weighted sum of measures is a measure.

The real exponential function and the number $e$ by a power series: the real exponential is defined by its all-real-convergent power series.

The exponential function is strictly increasing: the real exponential is continuous, hence Borel measurable.

The exponential series converges absolutely for every real argument: the exponential power series converges absolutely at every real argument.

A series of nonnegative terms converges iff its partial sums are bounded, and then the sum is their supremum: partial sums of a nonnegative series are bounded above by its extended sum.

The factorial $n!$ and the falling factorial $n^{\underset{‾}{k}}$, defined by recursion in $\mathbb{N}$: the factorial is recursively defined and $4!=24$ in the natural numbers.

Integer powers $a^m$: natural powers use recursive multiplication and negative powers of positive reals are reciprocals.

The canonical natural $\iota (n)=n\cdot 1_F$ of a field: natural numbers in the real field are represented by their canonical images.

Canonical naturals are positive and strictly increasing: the canonical image of each positive natural is positive.

Every complete ordered field is Archimedean: the natural numbers are unbounded in the real field.

The exponential addition formula $\exp (x+y)=\exp (x)\exp (y)$: $\exp (x+y)=\exp (x)\exp (y)$ for all real $x,y$.

The exponential is positive and satisfies $\exp (-x)=1\mathrm{/}\exp (x)$: $\exp (x)>0$ for every real $x$.

Monotonicity and nonnegative homogeneity of the nonnegative integral: positive finite scalars factor out of nonnegative Lebesgue integrals.

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

The law of a random element is a probability measure: the law of a random element is a probability measure.

Change of variables for expectation: for nonnegative measurable $g$, $\mathbb{E}[g(X)]=\int gd{P}_X$.

Tor Lattimore and Csaba Szepesvári, Bandit Algorithms: §5.3, PDF pp. 86–88 / printed pp. 77–79; the local discrete construction and divergence proof are supplied here.