Importance-Weighted Regret Under Bandit Feedback

Why Partial Feedback Changes the Update

With full information, a learner can compare every action’s loss after each round and update its weights accordingly. Under bandit feedback, the learner sees only the loss of the action it actually chose. Losses of the other actions are unknown, so they cannot be inserted directly into the usual exponential-weights update. Importance weighting supplies estimates of those missing losses: the observed loss is scaled by the inverse probability of choosing its action. This makes the estimates unbiased, but can also make them variable, especially for actions assigned small probabilities.

We study a finite set of $K$ actions, also called experts. On each round, the learner forms a distribution over actions, samples one action, and observes that action’s loss. The loss vectors may be chosen adversarially, but for the main result they are fixed before the learner’s random choices. We will derive a bound for expected regret against any fixed action, and then express the bound against the best fixed action for a fixed loss sequence.

Protocol and Importance-Weighted Estimates

Definition: On round $t$, let $\ell_{t,i}\in[0,1]$ be the loss of action $i$, for $i\in\{1,\ldots,K\}$. The learner chooses a probability vector $p_t$, draws $I_t$ with $P(I_t=i\mid\text{past})=p_{t,i}$, and observes only $\ell_{t,I_t}$. If every $p_{t,i}>0$, define the importance-weighted estimate $$ \widehat{\ell}_{t,i} = \frac{\ell_{t,I_t}\mathbf{1}\{I_t=i\}}{p_{t,i}}. $$

When action $i$ is not selected, its estimate is zero; when it is selected, its observed loss is divided by its selection probability. The estimates are therefore not the unknown losses themselves. Their key property is that, conditional on the past and on the fixed loss vector for the round, each estimate has the correct mean:

E[\widehat{\ell}_{t,i}\mid\text{past}] = p_{t,i}\frac{\ell_{t,i}}{p_{t,i}} = \ell_{t,i}.

This identity assumes the loss vector is fixed before $I_t$ is drawn. If an adversary could choose $\ell_{t,I_t}$ after seeing the sampled action, the argument would not establish unbiasedness for a pre-existing loss vector.

Worked Example: Estimating Three Losses

Suppose $p_t=(0.5,0.3,0.2)$ and the fixed loss vector is $(0.2,0.8,0.5)$. If action 2 is selected, the observed loss is $0.8$. The estimates are $$ \widehat{\ell}_t=(0,\;0.8/0.3,\;0)=(0,\;8/3,\;0). $$

The estimate for action 2 is larger than its actual loss because action 2 was selected with probability only $0.3$. Across repeated draws, its estimate is $8/3$ with probability $0.3$ and zero otherwise, so its expectation is $0.3(8/3)=0.8$. For action 1, the estimate is $0.2/0.5=0.4$ with probability $0.5$, giving expectation $0.5(0.4)=0.2$. For action 3, it is $0.5/0.2=2.5$ with probability $0.2$, giving expectation $0.2(2.5)=0.5$. Each estimate is unbiased.

The probability-weighted estimate of the learner’s loss on the observed round is $p_{t,2}\widehat{\ell}_{t,2}=0.3(8/3)=0.8$, exactly the observed loss. In general, $\sum_i p_{t,i}\widehat{\ell}_{t,i}=\ell_{t,I_t}$ for every realized choice.

Variance and the Partial-Feedback Cost

Unbiasedness does not mean low variability. Conditional on the past, $\widehat{\ell}_{t,i}$ equals $\ell_{t,i}/p_{t,i}$ with probability $p_{t,i}$, and equals zero otherwise. Thus

E[\widehat{\ell}_{t,i}^{\,2}\mid\text{past}] = \frac{\ell_{t,i}^{\,2}}{p_{t,i}}, \qquad \operatorname{Var}(\widehat{\ell}_{t,i}\mid\text{past}) = \ell_{t,i}^{\,2}\left(\frac{1}{p_{t,i}}-1\right).

The variance can be large when $p_{t,i}$ is small. The regret analysis will use a probability-weighted second moment. Its conditional expectation has a particularly useful form:

E\left[\sum_{i=1}^K p_{t,i}\widehat{\ell}_{t,i}^{\,2}\,\middle|\,\text{past}\right] = \sum_{i=1}^K \ell_{t,i}^{\,2}.

Indeed, if action $j$ is selected, the sum inside the expectation is $\ell_{t,j}^2/p_{t,j}$. Averaging over the draw gives $\sum_j p_{t,j}\ell_{t,j}^2/p_{t,j}=\sum_j\ell_{t,j}^2$. For losses in $[0,1]$, this is at most $K$ per round. This dependence on the number of actions is the variance cost that distinguishes this bound from a full-information bound.

Worked Example: Computing the Second Moment

Continue with $p_t=(0.5,0.3,0.2)$ and losses $(0.2,0.8,0.5)$. If action 2 is selected, the realized weighted second moment is $$ \sum_i p_{t,i}\widehat{\ell}_{t,i}^{\,2} = 0.3(8/3)^2 = 64/30 \approx 2.1333. $$

This realized quantity can exceed the corresponding sum of squared losses because the selected action’s estimate is inflated. Its conditional expectation, however, is $$ 0.2^2+0.8^2+0.5^2 = 0.04+0.64+0.25 = 0.93. $$ For example, the contribution to this expectation from selecting action 2 is $0.3\times 2.1333\ldots=0.64=0.8^2$. The other two contributions are $0.04$ and $0.25$, respectively.

The Importance-Weighted Hedge Update

Initialize each action with weight $w_{1,i}=1$. After observing the chosen action’s loss, update using its importance-weighted estimate:

p_{t,i}=\frac{w_{t,i}}{\sum_{j=1}^K w_{t,j}}, \qquad w_{t+1,i}=w_{t,i}\exp(-\eta\widehat{\ell}_{t,i}), \qquad \eta>0.

Only the observed loss is needed: the chosen action’s weight is updated using its scaled loss, while the other estimated losses are zero and their weights do not change on that round. Starting from positive weights, this update keeps every weight, and hence every sampling probability, positive after any finite number of rounds. That positivity is essential because the estimate divides by $p_{t,i}$.

Worked Example: Updating Two Action Probabilities

There are two actions with current probabilities $p_t=(0.5,0.5)$. The learner chooses action 1 and observes loss $0.4$. Its estimate is $0.4/0.5=0.8$; action 2’s estimate is zero. Taking $\eta=0.5$, the weights, up to their common initial scale, become $$ w_{t+1}=(\exp(-0.5\times0.8),1)=(\exp(-0.4),1) \approx(0.6703200,1). $$

Normalizing gives $$ p_{t+1,1}=\frac{0.6703200}{1.6703200}\approx0.4013123, \qquad p_{t+1,2}=\frac{1}{1.6703200}\approx0.5986877. $$ The observed loss lowers the probability of action 1, but does not eliminate it. The update has used no information about action 2’s loss.

Regret Bound and Proof

Theorem: Suppose the $K$ losses on each of $T$ rounds form a fixed sequence with $\ell_{t,i}\in[0,1]$. Run the update above from uniform initial weights with learning rate $\eta>0$, and sample $I_t$ from $p_t$. For every fixed action $i$, $$ E\left[\sum_{t=1}^T\ell_{t,I_t}-\sum_{t=1}^T\ell_{t,i}\right] \le \frac{\log K}{\eta} + \frac{\eta}{2}\sum_{t=1}^T\sum_{j=1}^K\ell_{t,j}^{\,2}. $$ Consequently, expected regret against the best fixed action in this fixed sequence obeys the same bound. In particular, since $\ell_{t,j}^2\leq 1$, the second term is at most $\eta KT/2$.

The proof first bounds regret for the estimated losses on each realized sequence of draws. It then takes expectations, using the conditional identities established above. The elementary inequality needed for the potential argument is $e^{-x}\leq1-x+x^2/2$ for $x\geq0$. To verify it, let $g(x)=1-x+x^2/2-e^{-x}$. Then $g(0)=g'(0)=0$, and $g''(x)=1-e^{-x}\geq0$ for $x\geq0$. Hence $g'(x)\geq0$ and $g(x)\geq0$.

Let $W_t=\sum_j w_{t,j}$. Applying this inequality with $x=\eta\widehat{\ell}_{t,j}$, which is nonnegative, yields

\frac{W_{t+1}}{W_t} = \sum_{j=1}^K p_{t,j}\exp(-\eta\widehat{\ell}_{t,j}) \leq 1-\eta\sum_jp_{t,j}\widehat{\ell}_{t,j} +\frac{\eta^2}{2}\sum_jp_{t,j}\widehat{\ell}_{t,j}^{\,2}.

The left-hand side is positive. The right-hand side is therefore positive as well, and $\log u\leq u-1$ for $u>0$ gives an upper bound on the logarithm of this ratio. Summing over rounds gives

\log\frac{W_{T+1}}{W_1} \leq -\eta\sum_{t=1}^T\sum_jp_{t,j}\widehat{\ell}_{t,j} +\frac{\eta^2}{2}\sum_{t=1}^T\sum_jp_{t,j}\widehat{\ell}_{t,j}^{\,2}.

On the other hand, the weight of any fixed action $i$ satisfies $w_{T+1,i}=\exp(-\eta\sum_t\widehat{\ell}_{t,i})$, while $W_1=K$ and $W_{T+1}\geq w_{T+1,i}$. Thus $$ \log\frac{W_{T+1}}{W_1} \geq -\eta\sum_{t=1}^T\widehat{\ell}_{t,i}-\log K. $$ Combining the upper and lower bounds and dividing by $\eta>0$ proves the pathwise estimated-loss inequality

\sum_{t=1}^T\left(\sum_jp_{t,j}\widehat{\ell}_{t,j}-\widehat{\ell}_{t,i}\right) \leq \frac{\log K}{\eta} +\frac{\eta}{2}\sum_{t=1}^T\sum_jp_{t,j}\widehat{\ell}_{t,j}^{\,2}.

Now take expectations. For each round, $\sum_jp_{t,j}\widehat{\ell}_{t,j}=\ell_{t,I_t}$ on every draw, and $E[\widehat{\ell}_{t,i}\mid\text{past}]=\ell_{t,i}$. The weighted second moment has conditional expectation $\sum_j\ell_{t,j}^2$. Taking expectations in the pathwise inequality therefore gives the theorem’s bound for each fixed $i$. Because the loss sequence is fixed, its best action $i^\star$ is fixed too; applying the bound to $i^\star$ proves the assertion about best-action regret. $\square$

Worked Example: A Sequence-Specific Regret Bound

Suppose there are $K=3$ actions and $T=4$ rounds, and on every round the loss vector is $(1,0,0)$. The best fixed action has cumulative loss zero. Here $\sum_j\ell_{t,j}^2=1$ on each round, so with $\eta=0.5$ the theorem gives $$ E[\text{regret}] \leq \frac{\log 3}{0.5} +\frac{0.5}{2}(4) = 2\log 3+1 \approx 3.1972. $$

The more general worst-case second-moment bound would replace the sum of squared losses, which is $4$ here, by $KT=12$. It would give $2\log3+3\approx5.1972$. The sequence-specific form is sharper because most actions have zero loss on every round.

Choosing the Learning Rate and Interpreting the Bound

Using only $\ell_{t,j}^2\leq1$, the theorem gives $$ E[\text{regret}] \leq \frac{\log K}{\eta}+\frac{\eta KT}{2}. $$ Balancing the two terms yields $\eta=\sqrt{2\log K/(KT)}$, when the horizon $T$ is known, and the resulting bound is $\sqrt{2KT\log K}$. This is a guarantee on expected regret; the sampling and the estimates are random even when the loss sequence is fixed.

Importance weighting makes learning possible without revealing the full loss vector, but the estimates can be large and the bound pays for that partial feedback through a second moment. In this analysis, that cost appears as a factor of $K$ in the worst case. The sequence-specific bound can be smaller when the losses have small squared magnitudes. The result is most useful when one needs a principled update from chosen-action observations and wants to see explicitly how the estimation noise affects regret.

Common Pitfall

Using the observed loss as if it were an unbiased estimate for every action. Assigning the observed loss to all actions, or assigning zero to every unchosen action without inverse-probability scaling, does not estimate each action’s loss correctly. For example, action $i$ is observed only with probability $p_{t,i}$; the estimate $\ell_{t,i}\mathbf{1}\{I_t=i\}$ has expectation $p_{t,i}\ell_{t,i}$, not $\ell_{t,i}$. Dividing by $p_{t,i}$ restores unbiasedness. The correction has a cost: its second moment grows as selection probabilities shrink.
Allowing zero selection probability. If $p_{t,i}=0$, the loss of action $i$ cannot be estimated by this formula, and the learner can never recover by selecting it later under this update. Positive initial weights and finite updates keep probabilities positive in exact arithmetic.
Reading an expected bound as a pathwise guarantee. The theorem controls expected regret over the learner’s random choices. The proof’s estimated-loss inequality is pathwise, but replacing its estimated quantities with actual losses requires expectation; it does not yield the displayed actual-loss bound for every random outcome.

Check Your Understanding

Use the definitions and proof above to answer these questions.

If action $i$ has loss $\ell_{t,i}$ and is chosen with probability $p_{t,i}>0$, what values can its importance-weighted estimate take, and why is its conditional expectation $\ell_{t,i}$?
For a fixed loss vector and sampling distribution, derive $E[\sum_i p_{t,i}\widehat{\ell}_{t,i}^{\,2}\mid\text{past}]$.
Why must the losses on a round be fixed before the learner samples its action for the unbiasedness argument?
Which step in the potential proof uses the restriction that the estimated losses are nonnegative?
For losses in $[0,1]$, state the worst-case regret bound obtained by optimizing the learning rate when $T$ is known.