Lecture 6

Bandit feedback

The mathematical abstraction of a sequential decision-maker we considered in previous lectures 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 \(x^{(t)} \in X\) in some strategy set satisfying \(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)}: x \mapsto \left\langle g^{(t)},x \right\rangle\), from which they can compute their realized utility, \(w^{(t)} \coloneqq \left\langle g^{(t)},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{g}^{(t)}\) of the (unobserved) utility gradient \(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 \(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 \(x^{(1)}, \dots , x^{(t-1)}\) but not on \(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 1.

The exploration term can be ignored if regret bounds in expectation are sought. Its role becomes important when high-probability guarantees are sought instead. 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{x} \in X} \mathop{\mathbb{E}}\limits\left[\sum_{t=1}^{T} \left\langle g^{\left(t\right)},\hat{x} \right\rangle - \sum_{t=1}^{T} \left\langle g^{\left(t\right)},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{x} \in X} \sum_{t=1}^{T} \left\langle g^{\left(t\right)},\hat{x} \right\rangle - \sum_{t=1}^{T} \left\langle g^{\left(t\right)},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{x} \in X} \sum_{t=1}^{T} \left\langle g^{\left(t\right)},\hat{x} \right\rangle - \sum_{t=1}^{T} \left\langle g^{\left(t\right)},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, \((x^{(τ)},w^{(τ)})_{τ<t}\), observable to the learner so far and produces a strategy \(x^{(t)}\) and, similarly, a randomized algorithm for the adversary that takes as input the history, \((x^{(τ)},u^{(τ)})_{τ<t-1}\), observable to the adversary so far and chooses a loss 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 \(X = \Delta (A)\).

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

The Exp3 (short for “exponential weights for exploration and exploitation”) algorithm, 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.], applies the multiplicative weights update (MWU) algorithm on the importance sampling estimator. No exploration term is added, so that the deterministic strategy \(x^{(t)}\) is sampled from the \(y^{(t)}\) output by MWU directly (see also Figure 1).

It is important to note that the analysis of MWU we did in Lecture 5 does not apply well to analyze the regret incurred by the full-information regret minimizer. The issue is that the estimated utilities potentially have a large range due to the division by the probabilities \(p_{a}^{(t)}\). However, a better analysis of MWU in this case is possible.

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 recently 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 the MWU algorithm with the FTRL algorithm 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

The Exp3.P algorithm, introduced by Auer, Cesa-Bianchi, Freund and Schapire [ACFS02], is a variant of the Exp3 algorithm to achieve high-probability regret guarantees. Intuitively, the difficulty with getting high-probabilty bounds for the regret in Exp3 is due to the importance sampling: the gradient estimator has entries of magnitude inversely proportional to the probabilities output by MWU. This makes the variance of the estimator large, and the concentration of the regret around its expectation difficult. To sidestep the issue, the Exp3.P algorithm uses the idea of superimposing a uniform exploration term to the output \(y^{(t)}\) of MWU. More specifically, the input to the strategy sampler is set to

where \(\gamma \in [0, 1]\) is a parameter.

The exploration term increases the exploration of the algorithm, reducing the variance of the estimator. However, it is important to observe that this correction incurs a regret penalty due to the fact that MWU recommended \(y^{(t)}\), and yet the decision maker sampled from \(p^{(t)}\). The effect of such misalignment grows with the exploration parameter \(\gamma\). Nonetheless, the following can be shown.

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 \(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.