Measurability of the KL-UCB constraint supremum

Fix a horizon $n\in\mathbb N$ and a pull count $m\in\mathbb N$, and write

for the KL-UCB exploration threshold of Algorithm 8, with $c=0$ when $m=0$ under Lean's convention $x/0=0$. For a real parameter $p$ let

where $d$ is the real-valued Bernoulli relative entropy $d(p,q)=p\log(p/q)+(1-p)\log\bigl((1-p)/(1-q)\bigr)$ of Definition 10.1, and the two implications encode the book's conventions $d(p,0)=\infty$ for $p\neq 0$ and $d(p,1)=\infty$ for $p\neq 1$, which the real-valued $d$ cannot express directly.

The assertion is that the map

is Borel measurable on $\mathbb{R}$, where the supremum is the Lean $\operatorname{sSup}$, so that $\sup\emptyset=0$ and the value at parameters for which $S(p)$ is empty or unbounded is the corresponding junk value.

This is the analytic core of the measurability of the KL-UCB index. The index of arm $i$ after a history $h$ is exactly $\sup S(p)$ evaluated at $p=\widehat\mu_i(h)$ with $m=T_i(h)$, so once this parametrised supremum is known to be measurable, measurability of the index follows from measurability of the empirical mean and the pull count together with the fact that $T_i(h)\le n$, which makes the dependence on $m$ a finite measurable partition.

Note that $p$ is not assumed to lie in $[0,1]$: the empirical mean of an arbitrary real-valued reward sequence need not be a probability, so the statement is made for every real $p$ and must accommodate the junk values of $d$ outside the unit interval. Note also that $S(p)$ can degenerate to a single point, which happens for instance when $c=0$ and $p\in(0,1)$, where $S(p)=\{p\}$; consequently the supremum is not in general approximable from inside $S(p)$ by rationals, and an argument by rational exhaustion of the constraint set does not suffice.