Bandit importance-weighted estimator

Let $k,n\ge 1$ be integers, let $[k]=\{1,\dots ,k\}$, and let

$${\mathrm{\Delta }}_k=\{p\in [0,1{]}^k:\sum _{i=1}^k{p}_i=1\}\mathrm{.}$$

On a probability space $(\mathrm{\Omega },\mathcal{F},\mathbb{P})$, let $({\mathcal{F}}_t{)}_{t=0}^n$ be the discrete filtration generated by the complete histories through round $t$, with ${\mathcal{F}}_0$ trivial; a complete pre-action history records past reward vectors, actions, and observed rewards. A reward vector is either fixed in advance or a deterministic function of the complete pre-action history. Thus, at a finite horizon with finitely many arms, there are finitely many possible histories. Before action $A_t$ is drawn, the current reward vector $x_t=(x_{t,1},\dots ,x_{t,k})\in [0,1{]}^k$ and sampling distribution $P_t=(P_{t,1},\dots ,P_{t,k})\in {\mathrm{\Delta }}_k$ are ${\mathcal{F}}_{t-1}$-measurable, and $P_{t,i}>0$ for every $i$. The finite-valued measurable action $A_t\in [k]$ has conditional law $\mathbb{P}(A_t=i\mid {\mathcal{F}}_{t-1})=P_{t,i}$. The learner observes only $X_t=x_{t,A_t}$ and sets

$$Y_t=1-X_t,y_{t,i}=1-x_{t,i},{\widehat{Y}}_{t,i}=\frac{\mathbf{1}\{A_t=i\}{Y}_t}{P_{t,i}},{\widehat{X}}_{t,i}=1-{\widehat{Y}}_{t,i}\mathrm{.}$$

The quantity ${\widehat{Y}}_{t,i}$ is the importance-weighted loss estimate for arm $i$, and ${\widehat{X}}_{t,i}$ is its corresponding reward estimate. A fixed reward sequence is the oblivious case; allowing $x_t$ to depend on the history available before $A_t$ is drawn gives the non-anticipating past-adaptive case. In either case the current reward vector is chosen before the current action. For finite horizons and finite action histories generated by such a fixed or deterministic history-dependent sequence, all these estimates are finite and integrable.

Online decision protocol: the learner selects its round-$t$ action using prior history before round-$t$ feedback.

Adversary and feedback models: bandit feedback reveals only the played reward, and non-anticipating rewards are fixed before the current action.

Random elements and real random variables: a measurable finite-valued action is a random element of $[k]$.

Filtration and filtered probability space: the round-history sigma-algebras are increasing and record information available before each action.

Conditional expectation given a sigma algebra: conditional expectation is characterized by equality of integrals on every event in the conditioning sigma-algebra.

Expectation of a nonnegative or integrable random variable: expectations of the finite integrable estimates are Lebesgue integrals on the probability space.