Lecture 13: Online Mirror Descent

Can one bandit algorithm adapt to stochastic losses while remaining reliable when losses are adversarial? This lecture studies an online mirror descent formulation with a Tsallis regularizer. The original notes follow Zimmert and Seldin’s conference paper [1] and its extended treatment [2]. They present the algorithm, its regularization geometry, and the main ingredients of its regret analysis.

Editorial status. This standalone source preserves the lecture’s sections, algorithm, claimed bounds, proof outline, and references. Explicit review notes distinguish mathematical issues from prose and notation repairs. It is a revision of the credited lecture notes, not a new research contribution or a claim that every bound below has been independently verified.

1 Review of stochastic and adversarial bandit regret

Earlier lectures introduced successive elimination, UCB, Thompson sampling, and EXP3. The objective is to control expected regret after $T$ rounds. Write $k$ for the number of arms and $\Delta_i$ for the mean-loss gap of suboptimal arm $i$ in a stochastic instance, with optimal arm $i^*$.

The original notes compare the scales $$\widetilde{\Theta}(\sqrt{kT}) \qquad\text{and}\qquad \Theta\!\left(\log T\sum_{i\ne i^*}\frac{1}{\Delta_i}\right)$$ for UCB1, and the adversarial upper-bound scale $$\mathbb{E}[R(T)]\lesssim\sqrt{kT\log k}$$ for EXP3. The first stochastic expression is instance-independent; the second is instance-dependent. These labels were interchanged in the original notes. The displayed orders are retained as the lecture’s comparison, rather than a new statement of matching bounds for every instance.

An algorithm designed only for one regime need not retain its guarantee in the other. One earlier route to adapting across regimes begins with a stochastic model and changes behavior when evidence contradicts it [3]. The question here is whether a single regularization scheme can obtain useful guarantees in both regimes without such a switch.

2 Preliminaries

2.1 Convex conjugates

For an extended-real-valued function $f$, its convex conjugate is $$\begin{equation} f^*(y)=\sup_{x\in\mathbb{R}^k}\{\langle x,y\rangle-f(x)\}. \end{equation}$$ When the supremum is attained, it can be written as a maximum, as in the original notes. If $f$ is convex, the objective being maximized is concave in $x$. This identifies the optimization structure; it does not by itself establish an efficient algorithm or guarantee attainment.

2.2 The convex indicator of a set

The extended-real indicator of a set $A$ is $$\begin{equation} I_A(x)=\begin{cases}0,&x\in A,\\+\infty,&x\notin A.\end{cases} \end{equation}$$ It encodes a constraint by assigning infinite cost outside the feasible set. It differs from the probability indicator $\mathbf{1}\{B\}$, which takes values zero and one. Consequently, $$\begin{equation} (f+I_A)^*(y)=\sup_{x\in A}\{\langle x,y\rangle-f(x)\}. \end{equation}$$ Under conditions that make the maximizer unique and the conjugate differentiable, the envelope theorem, or Danskin’s theorem, gives $$\begin{equation} \nabla(f+I_A)^*(y)=\mathop{\mathrm{argmax}}_{x\in A}\{\langle x,y\rangle-f(x)\}. \end{equation}$$

Mathematical review note. The source assumes invertibility of a gradient without spelling out the conditions for the constrained identity. Existence, uniqueness, and differentiability should be checked for the selected regularizer; convexity alone does not provide all three.

3 Online mirror descent for bandits

The algorithm maintains an estimate of cumulative loss and converts it into a distribution over arms. The probability simplex is $$\begin{equation} \Delta^k=\left\{w\in\mathbb{R}^k:w_i\geq0,\ \sum_{i=1}^k w_i=1\right\}. \end{equation}$$ This set has dimension $k-1$; reference [2] uses a superscript convention reflecting that dimension.

Algorithm: regularized bandit updates. Choose a sequence of regularizers $(\Psi_t)_{t\geq1}$ and initialize $\widehat L_0=0$. At round $t$:

1. Compute $$w_t=\nabla(\Psi_t+I_{\Delta^k})^*(-\widehat L_{t-1}) =\mathop{\mathrm{argmin}}_{w\in\Delta^k} \{\langle w,\widehat L_{t-1}\rangle+\Psi_t(w)\}.$$

2. Sample $I_t\sim w_t$ and observe the loss $\ell_{t,I_t}$.

3. Form importance-weighted estimates $$\widehat\ell_{t,i}=\frac{\mathbf{1}\{I_t=i\}\ell_{t,i}}{w_{t,i}}, \qquad \widehat L_t=\widehat L_{t-1}+\widehat\ell_t.$$

For each arm with positive sampling probability, the estimate is conditionally unbiased. The linear term favors arms with small estimated loss. The regularizer counteracts premature concentration on a single arm, leaving probability for alternatives when estimates remain uncertain.

4 Tsallis regularization

For a distribution $x$ and $0<\alpha<1$, the sign convention in the notes defines $$H_\alpha(x)=\frac{1-\sum_{i=1}^k x_i^\alpha}{1-\alpha}.$$ This is the negative of a commonly used positive-entropy convention. The regularizer is written as $$\Psi_{t,\alpha}(w)=-\sum_{i=1}^k\frac{w_i^\alpha}{\alpha\eta_{t,i}}.$$ The parameter $\eta_{t,i}$ controls regularization strength and may depend only on time. For the $\alpha=1/2$ case with a common learning rate, $$\Psi_{t,1/2}(w)=-\frac{2}{\eta_t}\sum_{i=1}^k\sqrt{w_i}.$$

The relation to exponential weights can be seen through the entropy limit. Applying l’Hopital’s rule on the simplex gives $$\lim_{\alpha\to1}H_\alpha(x)=\sum_{i=1}^k x_i\log x_i\leq0,$$ with $0\log0=0$. With negative Shannon entropy and matching estimator and learning-rate conventions, the regularized update yields the exponential-weights update associated with EXP3. The original lecture assigned this derivation as an exercise.

At $\alpha=1/2$, the geometry is particularly simple: $$\max_{w\in\Delta^k}\sum_i\sqrt{w_i}=\sqrt{k}, \qquad \min_{w\in\Delta^k}\sum_i\sqrt{w_i}=1.$$ The maximum is attained at the uniform distribution and the minimum at a simplex vertex. Because the regularizer has a negative sign, minimizing the regularized objective favors spreading probability across arms when the linear loss term does not strongly distinguish them.

5 The bounds attributed to Zimmert and Seldin

The lecture chooses $\alpha=1/2$ and $\eta_{t,i}=\eta_t=1/\sqrt{t}$. The learning rate decreases without requiring a known horizon. The original notes attribute the following bounds to [2]: $$\begin{align} \mathbb{E}[R(T)]&\leq4\sqrt{kT}+1 &&\text{(adversarial setting)},\\ \mathbb{E}[R(T)]&\leq\sum_{i\ne i^*}\frac{4\log T+68}{\Delta_i}+4\sqrt{k} &&\text{(stochastic setting)}. \end{align}$$ The stochastic expression depends on the gaps; the adversarial expression does not. Their relative numerical size therefore depends on the instance and horizon. The original sentence calling the adversarial bound unconditionally “stronger” should not be used as a comparison of their values.

The lecture emphasizes $\alpha=1/2$ because its tuning can avoid unknown gaps. Its broader statement that other choices necessarily require gap-dependent learning rates should be interpreted within the family and analysis being discussed, not as an impossibility claim for all bandit algorithms.

Mathematical review note. The exact constants, loss range, regret definition, unique-optimum assumptions, estimator variant, and normalization of the regularizer need to be matched against the corresponding theorem in [2]. The original notes do not specify all of them. The inequalities above preserve the lecture’s claim; this editorial revision does not certify their constants for every version of the displayed algorithm.

6 Self-bounding analysis

The proof outline combines a stability term with a change in a potential. Write $$\Phi_t=(\Psi_t+I_{\Delta^k})^*.$$ The source attributes the following intermediate inequality to Lemma 3 of [1]: $$\begin{equation} \ell_{t,I_t}\leq \sum_{i\ne I_t}\frac{4\eta\,w_{t,i}}{w_{t,I_t}} +\Phi_t(-\widehat L_{t-1})-\Phi_t(-\widehat L_t). \end{equation}$$ Here $w_{t,i}$ normalizes the source’s alternating $w_{i,t}$ notation. The meaning of $\eta$ in this source inequality, and its relation to the later time-varying $\eta_t$, remains to be checked.

The self-bounding relation used by the notes is $$\begin{equation} \mathbb{E}[R(T)]\geq \mathbb{E}\left[\sum_{t=1}^T\sum_{i\ne i^*}w_{t,i}\Delta_i\right]. \end{equation}$$ It allows an expression involving suboptimal-arm probabilities to be related back to regret, after which a small multiple of regret can be moved to the left-hand side.

Mathematical review note. The source calls this a property of the adversarial regime. It requires additional structure. In a stochastic model with fixed mean losses, the corresponding pseudo-regret is exactly the expected gap-weighted count of suboptimal plays. More general self-bounding regimes require an explicit assumption, and may contain an additive corruption term. This is not an unrestricted adversarial lower bound.

For $\alpha=1/2$ and $\eta_t=1/\sqrt t$, the lecture states the potential estimate $$\begin{align} \mathbb{E}\!\left[\sum_{t=1}^T\{ \Phi_t(-\widehat L_{t-1})-\Phi_t(-\widehat L_t)\}\right] &\leq\mathbb{E}\!\left[\sum_{t=1}^T\sum_{i\ne i^*}\sqrt{\frac{w_{t,i}}{t}}\right] +\mathbb{E}[L_{i^*}]+\sqrt{2k}. \end{align}$$ The quantity $L_{i^*}$ is the comparator’s cumulative loss. Combining a stability estimate, a potential estimate, and a valid self-bounding relation is the intended route to the final regret bound. Lemma 4 of [1] supplies the detailed argument cited by the original notes. The lecture’s outline suppresses constants and does not by itself establish each displayed inequality.

The remaining question is precise: which assumptions and estimator normalization make this outline a complete proof of the stated pair of bounds?

References

[1]

J. Zimmert and Y. Seldin. An Optimal Algorithm for Stochastic and Adversarial Bandits. Proceedings of AISTATS, PMLR, pp. 467–475, 2019.

[2]

J. Zimmert and Y. Seldin. Tsallis-INF: An Optimal Algorithm for Stochastic and Adversarial Bandits. Journal of Machine Learning Research, 22(28):1–49, 2021.

[3]

S. Bubeck and A. Slivkins. The Best of Both Worlds: Stochastic and Adversarial Bandits. Proceedings of COLT, pp. 42.1–42.23, 2012.