Adversarial bandits and importance-weighted feedback

For every real $z\le 0$,

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

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

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.

In the bandit importance-weighted estimator definition, fix a round $t$ and arm $i$, and write $p=P_{t,i}>0$ and $y=y_{t,i}$. Then

With conditional variance defined by $\mathrm{Var}(Z\mid {\mathcal{F}}_{t-1})=\mathbb{E}[(Z-\mathbb{E}[Z\mid {\mathcal{F}}_{t-1}]{)}^2\mid {\mathcal{F}}_{t-1}]$, one also has

Bandit importance-weighted estimator: the arm probabilities, observed loss, and importance-weighted loss estimate used here.

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.

Let $n\ge 1$ and $k>1$ be integers. Let $x_1,\dots ,x_n\in [0,1{]}^k$ be a reward sequence fixed before the learner's random choices, and run Exp3 with learning rate

Here $\log$ is the natural logarithm. For the well-definedness, finite-horizon completion, and two weight identities below, one may instead take any learning rate $\eta >0$ and any reward sequence admitted by the algorithm: rewards in $[0,1{]}^k$ fixed in advance or deterministic functions of the complete pre-action history. These procedure properties do not require the tuned learning rate. Assume the run is on a probability space carrying the measurable, finite-valued actions with the conditional probabilities specified by Exp3; no probability-space construction is asserted. Every normalizing denominator is finite and positive, all estimates and cumulative estimates are finite, and the procedure completes its $n$ rounds. For every $t\in \{0,\dots ,n\}$ and $i\in [k]$,

where the sum is empty when $t=0$. Consequently, for every $t\in \{1,\dots ,n\}$,

For the following regret guarantees, use the tuned learning rate displayed above. Write $X_t=x_{t,A_t}$ and define expected regret against the best fixed arm by

Then

The same bound holds when each $x_t$ is a deterministic function of the complete history available before $A_t$ is drawn, provided $x_t\in [0,1{]}^k$. In that past-adaptive case define

with the maximum outside the expectation; then $R_n^{\mathrm{p}\mathrm{a}\mathrm{s}\mathrm{t}}\le \sqrt{2nk\log k}$. This is an expected fixed-arm regret bound, not a high-probability bound, an expected in-hindsight maximum bound for random reward vectors, or a policy-regret bound for a reward rule that responds to the current action.

Exp3 with importance-weighted loss feedback: the sampling distribution, loss estimate, reward estimate, and cumulative update.

Bandit importance-weighted estimator: the bandit feedback and importance-weighted estimate conventions.

Adversary and feedback models: oblivious and non-anticipating timing, distinguished from current-action-reactive timing.

Static, dynamic, interval, and strongly adaptive regret: fixed-comparator and expected-regret conventions.

The natural logarithm as the inverse of the exponential function: the natural logarithm is the inverse of the exponential on positive reals.