Lecture 6

Learning with bandit feedback

The regret-minimization model (Definition L4.7) considered so far assumes that the learner receives enough information from the environment that she can compute her utility not only on the strategy she selected to play at each round of the interaction but also any counter-factual strategy that she could have played at that round. That is, we assume full-information feedback. This is a strong assumption, and in many cases, the decision-maker only receives partial feedback. In this lecture, we consider the case where the decision maker receives feedback only on the strategy they played. This is known as bandit feedback.

L6.1 Setup and general considerations

Like in our prior lectures, we will study linear settings, where our sequential decision-maker chooses a strategy \(\boldsymbol{x}^{(t)} \in \mathcal{X}\) in some strategy set satisfying \(\mathcal{X} \subseteq \mathbb{R}^{n}\). In the full-information setting that we have already studied, the feedback that our decision maker receives, at every round \(t\), is a utility function \(u^{(t)}: \boldsymbol{x} \mapsto \left\langle \boldsymbol{g}^{(t)},\boldsymbol{x} \right\rangle\), from which they can compute their realized utility, \(w^{(t)} \coloneqq \left\langle \boldsymbol{g}^{(t)},\boldsymbol{x}^{(t)} \right\rangle\), for the strategy they played as well as the counterfactual utility they would have received from any strategy they could have played. In the bandit setting, the decision-maker only receives as feedback their realized utility \(w^{(t)}\) as opposed to their complete utility function \(u^{(t)}\).

As a general principle, algorithms for the bandit setting are constructed from regret minimizers for the full-information setting. Indeed, the key idea is to construct an estimator \(\tilde{\boldsymbol{g}}^{(t)}\) of the (unobserved) utility gradient \(\boldsymbol{g}^{(t)}\), and feed that into a full-information regret minimizer. The estimator is constructed from the observed utility \(w^{(t)}\) and the chosen strategy \(\boldsymbol{x}^{(t)}\).

The utility function can still be picked adversarially by the environment. However, to get guarantees, it is necessary to reduce the power of the environment by letting the utility \(u^{(t)}\) only depend on \(\boldsymbol{x}^{(1)}, \dots , \boldsymbol{x}^{(t-1)}\) but not on \(\boldsymbol{x}^{(t)}\). In other words, the environment can pick the utility adaptively, but must decide the utility before the learner picks the strategy, and not after. This restriction still allows convergence to equilibria if bandit algorithms are used by players to iteratively update their strategies in games.

Typically, the construction of bandit algorithms follows the template shown in Figure L6.1.

Some loss-based algorithms obtain pseudoregret bounds without an explicit exploration mixture. High-probability guarantees require additional control of estimation errors; a uniform mixture alone does not provide that guarantee. We explain the difference next.

Stochastic regret guarantees.   Because online learning algorithms benefit from randomization, as is crucially the case in bandit settings, the regret of a bandit algorithm is a random variable. This adds a layer of complexity when approaching the analysis of bandit algorithms. As a rule of thumb, three “flavors” of guarantees are typically considered in the literature. We list them from the weakest (and easiest to obtain) to the strongest (and hardest to obtain):

• Guarantees on the pseudoregret, namely guarantees of the following form:

  \[\displaystyle \text{PseudoReg}^{\left(T\right)} \coloneqq \operatorname*{max}_{\hat{\boldsymbol{x}} \in \mathcal{X}} \mathop{\mathbb{E}}\limits\left[\sum_{t=1}^{T} \left\langle \boldsymbol{g}^{\left(t\right)},\hat{\boldsymbol{x}} \right\rangle - \sum_{t=1}^{T} \left\langle \boldsymbol{g}^{\left(t\right)},\boldsymbol{x}^{\left(t\right)} \right\rangle \right] = o\left(T\right).\]

• Guarantees on the expected regret, namely guarantees of the following form:

  \[\displaystyle \hspace{14.17pt}\mathop{\mathbb{E}}\limits\left[\text{Reg}^{\left(T\right)}\right] \coloneqq \mathop{\mathbb{E}}\limits\left[\operatorname*{max}_{\hat{\boldsymbol{x}} \in \mathcal{X}} \sum_{t=1}^{T} \left\langle \boldsymbol{g}^{\left(t\right)},\hat{\boldsymbol{x}} \right\rangle - \sum_{t=1}^{T} \left\langle \boldsymbol{g}^{\left(t\right)},\boldsymbol{x}^{\left(t\right)} \right\rangle \right] = o\left(T\right).\]

  Note the change of order between the expectation and the maximum compared with the pseudoregret introduced in the previous bullet point.

• High-probability regret guarantees, namely guarantees of the following form:

  \[\displaystyle \mathbb{P}\left[\operatorname*{max}_{\hat{\boldsymbol{x}} \in \mathcal{X}} \sum_{t=1}^{T} \left\langle \boldsymbol{g}^{\left(t\right)},\hat{\boldsymbol{x}} \right\rangle - \sum_{t=1}^{T} \left\langle \boldsymbol{g}^{\left(t\right)},\boldsymbol{x}^{\left(t\right)} \right\rangle \le o\left(T\right) \sqrt{\operatorname{log} \frac{1}{\delta}}\right] \ge 1-\delta\]

  for any \(\delta > 0\) small enough.

To make sense of the measures with respect to which the expectations and probabilities are computed in the above definitions, consider a randomized algorithm for the learner that takes as input the history, \((\boldsymbol{x}^{(τ)},w^{(τ)})_{τ<t}\), observable to the learner so far and produces a strategy \(\boldsymbol{x}^{(t)}\) and, similarly, a randomized algorithm for the adversary that takes as input the history, \((\boldsymbol{x}^{(τ)},u^{(τ)})_{τ<t}\), observable to the adversary so far and chooses a utility function \(u^{(t)}\). Pitting the two algorithms against each other defines a probability measure with respect to which the above expectations and probabilities are defined.

Finally, notice that Pseudoregret and expected regret guarantees are different, since \(\operatorname*{max} \mathop{\mathbb{E}}\limits \le \mathop{\mathbb{E}}\limits \operatorname*{max}\), but the converse is not true in general. This means that bounding expected regret automatically bounds the pseudoregret but the opposite is not necessarily the case. In fact, bounds on the pseudoregret are not strong enough to conclude convergence to the set of equilibria, in general.

L6.2 Adversarial bandit learning in normal-form games

Let’s start from the case of normal-form games, in which our decision maker faces the choice of picking an action out of a finite set \(A\). The setting in this case is also known as adversarial multi-armed bandit problem. We have \(\mathcal{X} = \Delta (A)\).

Strategy sampler.   In this settings, most algorithms use the natural strategy sampler: given a distribution \(\boldsymbol{p}^{(t)} \in \Delta (A)\), the decision maker samples an action \(a^{(t)} \in A\) according to the probabilities in \(\boldsymbol{p}^{(t)}\). The vector \(\boldsymbol{x}^{(t)}\) is then set to the deterministic distribution \(\boldsymbol{e}_{a^{(t)}}\). Clearly, \(\mathop{\mathbb{E}}\limits_{t} [\boldsymbol{x}^{(t)}] = \boldsymbol{p}^{(t)}.\)

Gradient estimator.   For this setting, the standard gradient estimator is the importance sampling estimator. Given the utility scalar \(w^{(t)} \in [0, 1]\), the importance sampling estimator is defined as

L6.2.1 The Exp3 algorithm

Exp3 (short for “exponential weights for exploration and exploitation”) adapts multiplicative weights (Section L5.1.4) to bandit feedback and was introduced by Auer, Cesa-Bianchi, Freund and Schapire [ACFS02[ACFS02] Auer, P., Cesa-Bianchi, N., Freund, Y., & Schapire, R. E. (2002). The nonstochastic multiarmed bandit problem. SIAM Journal on Computing, 32(1), 48–77.]. We use a variant that needs no explicit exploration mixture. Convert rewards \(g_{a}^{(t)} \in [0,1]\) into losses \(ℓ_{a}^{(t)}=1-g_{a}^{(t)}\). This changes neither realized regret nor pseudoregret.

Start with positive weights \(W_{1,a}=1\). At time \(t\), sample action \(a^{(t)}\) from \(p_{a}^{(t)}=\frac{W_{t,a}}{\sum_{b}} W_{t,b}\) and observe its loss. Set

Equivalently, the full-information utility learner receives \(-\hat{\boldsymbol{ℓ}}^{(t)}\).

L6.2.2 Tsallis entropy

It can be shown that, information theoretically, no bandit learning algorithm for a finite set of actions \(|A|\) can achieve better than \(\Omega (\sqrt{T |A|})\) expected regret in general. The regret guaranteed by the Exp3 algorithm is therefore optimal only up to a logarithmic factor. It remained open for a long time whether this logarithmic factor could be removed. A positive answer was given by Audibert and Bubeck [AB10[AB10] Audibert, J.-Y., & Bubeck, S. (2010). Regret bounds and minimax policies under partial monitoring. The Journal of Machine Learning Research, 11, 2785–2836.], who proposed the idea of replacing MWU (Section L5.1.4) with FTRL (Section L5.2.3) instantiated with the negative \((1/2)\)-Tsallis entropy regularizer

A simplified analysis can also be found in [ZS21[ZS21] Zimmert, J., & Seldin, Y. (2021). Tsallis-INF: An optimal algorithm for stochastic and adversarial bandits. Journal of Machine Learning Research, 22(28), 1–49.].

L6.2.3 The Exp3.P algorithm

Exp3.P uses both uniform exploration and an upper-confidence correction to reward estimates [ACFS02]. For \(K=|A|\ge 2\), let \(\boldsymbol{y}^{(t)}\) be normalized positive weights and sample from

With the reward estimator \(\tilde{\boldsymbol{g}}\) defined earlier, update the weights by

The positive bonus accounts for uncertainty; uniform exploration bounds inverse sampling probabilities. This is a different estimator/update from the loss-form Exp3 above.

The confidence parameter enters the logarithm and the bonus. Adding exploration to an unbiased estimator, without this correction or another concentration-control mechanism, is not the Exp3.P algorithm.

L6.3 Adversarial bandit learning on general convex domains

Today, we know that bandit optimization is possible well past probability simplexes. In fact, we can construct bandit algorithms for any convex and compact domain \(\mathcal{X} \subseteq \mathbb{R}^{d}\). In particular, we mention the general general result by Abernethy, Hazan and Rakhlin [AHR08[AHR08] Abernethy, J. D., Hazan, E., & Rakhlin, A. (2008). Competing in the Dark: An Efficient Algorithm for Bandit Linear Optimization. COLT, 263–274.], who showed that the a bandit algorithm can be constructed starting from a full-information regret miminizer built using the FTRL algorithm with a self-concordant distance-generating function.