Exp4 with unbiased estimated rewards

Given integers $n\ge 1$, $k>1$, $M>1$, a learning rate $\eta >0$, and an instance from the contextual bandit protocol with finite expert advice, initialize $Q_{1,m}=1\mathrm{/}M$ for $m\in [M]$. For rounds $t=1,\dots ,n$, perform the following operations:

1. Receive the advice matrix $E(t)$, whose $m$th row is $E(t{)}_m\in {\mathrm{\Delta }}_k$.

2. Form the action distribution

$$P_{t,i}=\sum _{m=1}^M{Q}_{t,m}E(t{)}_{m,i},i\in [k]\mathrm{.}$$

3. Draw a measurable action $A_t\in [k]$ 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}$.

4. For each $i\in [k]$, form

$${\widehat{X}}_{t,i}=1-\frac{\mathbf{1}\{A_t=i\}(1-X_t)}{P_{t,i}}\mathrm{.}$$

When $P_{t,i}=0$, the action $A_t=i$ is impossible; in this case the quotient term is defined to be zero on every possible outcome.

5. For each expert $m\in [M]$, form its estimated reward

$${\tilde{X}}_{t,m}=\sum _{i=1}^{k}E(t{)}_{m,i}{\widehat{X}}_{t,i}$$

and update the expert distribution by

$$Q_{t+1,m}=\frac{Q_{t,m}\exp (\eta {\tilde{X}}_{t,m})}{\sum _{r=1}^M{Q}_{t,r}\exp (\eta {\tilde{X}}_{t,r})}\mathrm{.}$$

The output is $(Q_t,P_t,A_t,X_t,{\widehat{X}}_t,{\tilde{X}}_t{)}_{t=1}^n$ and $Q_{n+1}$. All arithmetic is over exact real numbers, and the procedure assumes a probability space carrying the stated finite-valued measurable draws. This is the $\gamma =0$ Exp4 update; no regret guarantee for bounded-loss Hedge is part of the algorithm.

Contextual bandit protocol: the fixed oblivious reward/advice instance, action set, observed reward, and pre-action history used here.

Normalized exponential weights: the full-information algorithm uses normalized exponential weights; this is notation only, not a regret result for the present unbounded estimates.

Importance-weighted loss estimate: on coordinates with positive sampling probability, the quotient term is the standard estimate of loss $1-X_t$; the zero-probability convention is handled locally here.

Measurable finite actions: each action draw is a measurable finite-valued random element.

Real exponential: the update uses the real exponential function.

Exponential positivity: exponential weights are positive for every finite real input.

Exp4 well-definedness ↗: the separate result proves finite estimates, simplex mixtures, positive expert weights and finite-horizon completion, including zero-probability actions.