ora-0144

11.5 Entropic realization and the classical rate

Take uniform initial weights and update

\[ p_t(a)=\frac{w_t(a)}{\sum _b w_t(b)}, \qquad w_{t+1}(a)=w_t(a)e^{-\eta \widehat\ell _t(a)}. \]

Proposition 11.7 Entropic surrogate comparison

For every arm \(a\) and every nonnegative surrogate sequence,

\[ \sum _{t=1}^T\langle p_t,\widehat\ell _t\rangle -\sum _{t=1}^T\widehat\ell _t(a) \leq \frac{\log K}{\eta } +\frac{\eta }{2}\sum _{t=1}^T \langle p_t,\widehat\ell _t^2\rangle . \]

Proof ▼

Apply \(e^{-x}\leq 1-x+x^2/2\) for \(x\geq 0\) to the exponential-weights potential, telescope the logarithms of total weight, and compare the final total weight with the contribution of arm \(a\).

Corollary 11.8 Adversarial finite-arm bandit rate

Under the assumptions of 11.6, the entropic realization satisfies

\[ \mathbb E\! \left[\sum _{t=1}^T\ell _t(A_t)\right] -\min _{a\in A}\sum _{t=1}^T\ell _t(a) \leq \frac{\log K}{\eta }+\frac{\eta KT}{2}. \]

With \(\eta =\sqrt{2\log K/(KT)}\), the bound is \(\sqrt{2TK\log K}\).

Proof ▼

Conditionally on the past,

\[ \mathbb E\langle p_t,\widehat\ell _t^2\rangle =\sum _{a\in A}\ell _t(a)^2\leq K. \]

Take expectations in 11.7, use the displayed second-moment identity and barycentric reconstruction for the fixed comparison arm, and then minimize over arms. Optimizing \(\eta \) gives the stated choice.

The inverse probabilities disappear from this expected second moment, but they do not disappear from the pathwise tangent bound in 11.4. Sublinear expected regret and robust infinitesimal evidence transport are therefore genuinely different properties, witnessed by different observers.