Contextual bandit protocol with finite expert advice

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

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

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

$$R_n=\mathbb{E}[\underset{m\in [M]}{\max }\sum _{t=1}^n⟨E(t{)}_m,x_t⟩-\sum _{t=1}^n{X}_t],$$

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.