Contextual expert bandits

Fix integers $n\ge 1$, $k>1$, and $M>1$. Write $[r]=\{1,\dots ,r\}$ for a positive integer $r$, and let

An oblivious contextual bandit instance consists of reward vectors $x_t\in [0,1{]}^k$ and advice matrices $E(t)\in \mathcal{E}$, for $t\in [n]$, all fixed before the learner's private randomization. The matrix $E(t)$ is revealed before the round-$t$ action; its row $E(t{)}_m=(E(t{)}_{m,1},\dots ,E(t{)}_{m,k})$ is expert $m$'s probability distribution over the $k$ actions. The expected reward of expert $m$ on round $t$ is $⟨E(t{)}_m,x_t⟩={\sum }_{i=1}^{k}E(t{)}_{m,i}{x}_{t,i}$.

At round $t$, the learner's pre-action history consists of its earlier actions and observed rewards. Given that history and the revealed advice, it selects a distribution $P_t\in {\mathrm{\Delta }}_k$, draws a measurable finite-valued action $A_t\in [k]$ with conditional probabilities $\mathbb{P}(A_t=i\mid {\mathcal{F}}_{t-1})=P_{t,i}$, and observes only $X_t=x_{t,A_t}$. Here ${\mathcal{F}}_{t-1}$ is the sigma-algebra generated by the pre-action history. For every fixed expert sequence and reward sequence, the expected regret against the best fixed expert is

where expectation is over the learner's action draws. The regret random variable is bounded, so this expectation is finite. This protocol makes no stochastic generalization claim and imposes no shared-structure condition on the experts; it does not cover advice or rewards selected in response to the learner's current action.

Online decision timing: the learner chooses each action from its pre-action history before observing current-round feedback.

Oblivious adversary and bandit feedback: an oblivious sequence is fixed before learner randomization, and bandit feedback reveals only the played reward.

Expected-regret convention: expected regret is the expectation of the specified measurable, integrable regret random variable.

Measurable random actions: a finite action draw is a measurable random element of the discrete action set.

Pre-action filtration: the sigma-algebras generated by successive histories form a filtration.

Expectation: the expectation of an integrable real random variable is its Lebesgue integral on the underlying probability space.

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

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

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

and update the expert distribution by

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.

For the exact-real Exp4 procedure, take any integers $n\ge 1$, $k>1$, $M>1$, any finite real learning rate $\eta >0$, and every oblivious reward/advice instance and supplied measurable draws in its input scope. At every round $t\in [n]$, the expert vector $Q_t$ is a probability vector with strictly positive entries, the action mixture $P_t$ belongs to ${\mathrm{\Delta }}_k$, and $P_{t,i}=0$ implies $E(t{)}_{m,i}=0$ for every expert $m$. Every action and expert reward estimate is finite; the corresponding estimated losses $1-{\widehat{X}}_{t,i}$ and $1-{\tilde{X}}_{t,m}$ are nonnegative. The normalizing denominator is finite and strictly positive, so $Q_{t+1}$ again has strictly positive entries summing to one. The procedure completes its $n$ prescribed rounds and returns all specified outputs.

The zero-quotient convention is retained exactly. These conclusions do not require positive sampling probability for every action, a uniform exploration mixture, a bound on the magnitude of an importance-weighted estimate, or a restriction on the learning rate beyond $\eta >0$.

Exp4 with unbiased estimated rewards

Contextual bandit protocol with finite expert advice

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

Lattimore and Szepesvári, Bandit Algorithms, §18.3 Algorithm 11

In Exp4, at every round $t\in [n]$ and for every expert $m\in [M]$, the expert's estimated reward satisfies

The assertion includes rounds where some actions have zero sampling probability; no componentwise unbiasedness claim is made for an unsupported action.

Exp4 estimates and zero-probability convention: the estimated action rewards and expert rewards are defined in the algorithm.

At every round $t$ in Exp4, define the estimated action loss by ${\widehat{L}}_{t,i}=1-{\widehat{X}}_{t,i}$ and the estimated loss of expert $m$ by ${\tilde{L}}_{t,m}=1-{\tilde{X}}_{t,m}$. Then

This bound includes actions with zero sampling probability under the zero-quotient convention.

Exp4 expert weights and estimated losses: the action distribution, arm reward estimates, and expert weights define the random variables in the statement.

For any Exp4 run with learning rate $\eta >0$ and any fixed expert $m^{\ast }\in [M]$, define ${\tilde{L}}_{t,m}=1-{\tilde{X}}_{t,m}$. The following pathwise inequality holds for every realized action sequence:

Exp4 update: the expert weights are updated by normalized exponentials of the estimated rewards.

Nonpositive-axis exponential inequality: the potential proof applies this inequality to the negative estimated losses.

Let $n\ge 1$, $k>1$, and $M>1$ be integers. For each $t\in [n]$, let $x_t\in [0,1{]}^k$ and let $E(t)$ be an $M\times k$ matrix with nonnegative entries whose every row sums to one. Assume the reward vectors and advice matrices are deterministic and fixed before learner randomization, each advice matrix is revealed before its action, and the learner observes only the reward of its sampled action. Run Exp4 with

where $\log$ is the natural logarithm and the square root is the nonnegative real root. Define expected regret against the best fixed expert by

Then

Oblivious contextual bandit protocol and expected regret: the fixed reward/advice scope, action feedback, and reward-regret convention are defined there.

Exp4 algorithm: the action mixture, importance-weighted estimates, and expert update used in the theorem are defined there.

Conditional unbiasedness of expert reward estimates: supported action estimates recover each fixed expert's expected reward, including the zero-support boundary.

Weighted estimated-loss second moment: the expected quadratic term in the potential bound is at most $k$ per round.

Exp4 potential inequality: every fixed expert's estimated-reward advantage is bounded by the log-prior term and estimated-loss second moments.