Exp3 expected regret under bandit feedback

First fix any positive finite real learning rate $\eta$ and any reward sequence admitted by the algorithm. Initially ${\widehat{S}}_{0,i}=0$ is finite for every $i$ by [F18]. Suppose all ${\widehat{S}}_{t-1,i}$ are finite. Then each $\exp (\eta {\widehat{S}}_{t-1,i})$ is a positive finite real by [F7] and the real-valued exponential definition [F17]. Its finite sum over $[k]$ is positive and finite, so [F1] gives $P_{t,i}>0$ and ${\sum }_i{P}_{t,i}=1$. The assumed measurable action draw exists by [F21]; its observed reward is in $[0,1]$. Thus each ${\widehat{Y}}_{t,i}=\mathbf{1}\{A_t=i\}(1-X_t)\mathrm{/}{P}_{t,i}$ and ${\widehat{X}}_{t,i}=1-{\widehat{Y}}_{t,i}$ is finite, and [F19] makes every ${\widehat{S}}_{t,i}$ finite. Induction proves these facts through round $n$. The prescribed loop has the finite index set $\{1,\dots ,n\}$ and each round consists of the finite operations just checked together with an assumed draw, so it completes exactly $n$ rounds. This argument uses only $\eta >0$ and the algorithm's reward range, for either fixed or deterministic past-adaptive rewards. For the rate in the regret clauses, $k>1$, [F10] and [F20] give $\log k>\log 1=0$, and [F9] makes $\log k$ real; hence that tuned $\eta$ is also a positive finite real and the same argument applies to it.

For $t=0$, the claimed identity ${\widehat{S}}_{t,i}=t-{\sum }_{s=1}^t{\widehat{Y}}_{s,i}$ holds by [F18] and the empty-sum convention. If it holds at $t-1$, then [F19] and ${\widehat{X}}_{t,i}=1-{\widehat{Y}}_{t,i}$ give

Substituting this identity into [F1] and using [F6] factors out the common positive term $\exp (\eta (t-1))$ from numerator and denominator, giving the stated loss-weight formula for $P_{t,i}$.

For each $t$, set $W_t={\sum }_{j=1}^k\exp (\eta {\widehat{S}}_{t,j})$ and $V_t={\sum }_{j=1}^k{P}_{t,j}{\widehat{Y}}_{t,j}^2$. By [F1], [F7], and step 1.1, $W_t$ is positive and finite, and $P_t$ is a probability vector.

By [A1] and [F11], each reward vector is fixed at the pre-action history. At each such history, [F3] and ${\widehat{X}}_{t,i}=1-{\widehat{Y}}_{t,i}$ give the conditional mean $\mathbb{E}[{\widehat{X}}_{t,i}\mid {\mathcal{F}}_{t-1}]=x_{t,i}$ by the finite conditional sum. Averaging these sums over histories and using [F14] and [F19] gives $\mathbb{E}[{\widehat{S}}_{n,i}]=\mathbb{E}[{\sum }_t{x}_{t,i}]$.

On every round and every action outcome, ${\sum }_j{P}_{t,j}{\widehat{X}}_{t,j}=1-{\sum }_j{P}_{t,j}{\widehat{Y}}_{t,j}=1-Y_t=X_t$, because only the sampled arm contributes to the middle sum.

Fix a pre-action history at round $t$. If $A_t=a$, only coordinate $a$ contributes to $V_t$, with value $y_{t,a}^2\mathrm{/}{P}_{t,a}$. Its conditional expectation is therefore ${\sum }_{a=1}^k{P}_{t,a}(y_{t,a}^2\mathrm{/}{P}_{t,a})={\sum }_{a=1}^k{y}_{t,a}^2\le k$, since $0\le y_{t,a}\le 1$. Averaging over the finite histories and summing the $n$ rounds gives $\mathbb{E}[{\sum }_t{V}_t]\le nk$.

By [F1]–[F2], $W_t\mathrm{/}{W}_{t-1}={\sum }_{j=1}^k{P}_{t,j}\exp (\eta {\widehat{X}}_{t,j})=\exp (\eta ){\sum }_{j=1}^k{P}_{t,j}\exp (-\eta {\widehat{Y}}_{t,j})$. Each ${\widehat{Y}}_{t,j}\ge 0$, so [F4] with $z=-\eta {\widehat{Y}}_{t,j}$ gives $W_t\mathrm{/}{W}_{t-1}\le \exp (\eta )(1-\eta {\sum }_j{P}_{t,j}{\widehat{Y}}_{t,j}+{\eta }^2{V}_t\mathrm{/}2)$. Put $u_t=-\eta {\sum }_j{P}_{t,j}{\widehat{Y}}_{t,j}+{\eta }^2{V}_t\mathrm{/}2$. By [F5] and ${\sum }_j{P}_{t,j}{\widehat{X}}_{t,j}=1-{\sum }_j{P}_{t,j}{\widehat{Y}}_{t,j}$, this is at most $\exp (\eta +u_t)=\exp (\eta {\sum }_j{P}_{t,j}{\widehat{X}}_{t,j}+{\eta }^2{V}_t\mathrm{/}2)$.

Multiplying step 3.2 over $t=1,\dots ,n$ and using [F6] gives $W_n\mathrm{/}{W}_0\le \exp (\eta {\sum }_{t=1}^n{\sum }_j{P}_{t,j}{\widehat{X}}_{t,j}+{\eta }^2{\sum }_{t=1}^n{V}_t\mathrm{/}2)$. Here $W_0=k$ by [F17]–[F18], and $W_n\ge \exp (\eta {\widehat{S}}_{n,i})$ for every $i$ by [F19]. Since $k=\exp (\log k)$ by [F9], strict increase [F8] and $\eta >0$ yield ${\widehat{S}}_{n,i}-{\sum }_{t=1}^n{\sum }_j{P}_{t,j}{\widehat{X}}_{t,j}\le \log k\mathrm{/}\eta +(\eta \mathrm{/}2){\sum }_{t=1}^n{V}_t$ for every arm $i$.

For the oblivious case set $R_{n,i}={\sum }_t{x}_{t,i}-\mathbb{E}[{\sum }_t{X}_t]$; for the past-adaptive case set $R_{n,i}=\mathbb{E}[{\sum }_t(x_{t,i}-X_t)]$. By steps 2.2–2.3, both equal $\mathbb{E}[{\widehat{S}}_{n,i}-{\sum }_t{\sum }_j{P}_{t,j}{\widehat{X}}_{t,j}]$. Taking expectations in step 4.1, using [F14]–[F16], and applying step 3.1 gives $R_{n,i}\le \log k\mathrm{/}\eta +\eta nk\mathrm{/}2$ for every $i$.

Using $\eta >0$ from step 1.1, substitution gives $\log k\mathrm{/}\eta =\eta nk\mathrm{/}2=\sqrt{nk\log k\mathrm{/}2}$. The per-arm bound in step 5.1 therefore equals $\sqrt{2nk\log k}$; taking the finite maximum over $i$ proves both regret bounds in the Statement.