Exp3 with importance-weighted loss feedback

Let $k>1$ and $n\ge 1$ be integers, and let $\eta >0$. Use the finite-arm bandit protocol with rewards in $[0,1]$ and conditional sampling as specified in the bandit importance-weighted estimator definition. Initialize ${\widehat{S}}_{0,i}=0$ for each $i\in [k]$. For rounds $t=1,\dots ,n$, perform the following operations:

1. Set $$P_{t,i}=\frac{\exp (\eta {\widehat{S}}_{t-1,i})}{\sum _{j=1}^k\exp (\eta {\widehat{S}}_{t-1,j})},i\in [k]\mathrm{.}$$
2. Draw a measurable finite-valued action $A_t$ with conditional probabilities $\mathbb{P}(A_t=i\mid {\mathcal{F}}_{t-1})=P_{t,i}$, and observe only $X_t=x_{t,A_t}$.
3. Form the loss estimates ${\widehat{Y}}_{t,i}=\mathbf{1}\{A_t=i\}(1-X_t)\mathrm{/}{P}_{t,i}$ and reward estimates ${\widehat{X}}_{t,i}=1-{\widehat{Y}}_{t,i}$ for every $i\in [k]$.
4. Update ${\widehat{S}}_{t,i}={\widehat{S}}_{t-1,i}+{\widehat{X}}_{t,i}$ for every $i\in [k]$.

The output is $(P_t,A_t,X_t,{\widehat{X}}_t,{\widehat{Y}}_t{)}_{t=1}^n$ and ${\widehat{S}}_n$. These operations use exact real arithmetic. The procedure assumes a probability space carrying the stated measurable draws; it makes no probability-space construction claim. Normalizing the weights $\exp (\eta {\widehat{S}}_{t-1,i})$ is the exponential-weights step used by Hedge.

Bandit importance-weighted estimator: the finite-arm reward protocol and loss/reward estimate definitions used at each round.

Hedge: initialize equal weights, normalize exponentials, draw an action, and update after feedback.

The real exponential function and the number $e$ by a power series: the real exponential used in the unnormalized weights.

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

Random elements and real random variables: each sampled arm is a measurable finite-valued random element.