More Adaptive Algorithms for Adversarial Bandits

Introduction

There are several existing works on deriving more adaptive bandit algorithms, replacing the dependence on $T$ in the regret bound by some data-dependent quantity that is $\mathcal{O}(T)$ in the worst-case but could be potentially much smaller in benign environments. Examples of such data-dependent quantities include the loss of the best arm (Allenberg et al., 2006; Foster et al., 2016) or the empirical variance of all arms (Hazan and Kale, 2011a; Bubeck et al., 2017). Extensions to more general settings such as semi-bandit, two-point bandit, and graph bandit have also been studied (Neu, 2015; Chiang et al., 2013; Lykouris et al., 2017). These adaptive algorithms not only enjoy better performance guarantees, but also have important applications for other areas such as game theory (Foster et al., 2016).

These bounds are incomparable in general. All of them have known counterparts in the full information setting (see for example (Steinhardt and Liang, 2014) and (De Rooij et al., 2014)), but are novel in the bandit setting to the best of our knowledge. Note that for the first two results that depend on some quantities of only the best arm, we require tuning a learning rate parameter in terms of these (unknown) quantities. Obtaining the same results with parameter-free algorithms remains open, even for the full information setting. However, for the other results, we indeed provide parameter-free algorithms based on a variant of the doubling trick.

Our general algorithm falls into the Online Mirror Descent (OMD) framework (see for example (Hazan et al., 2016)) with the “log-barrier” as the regularizer, originally proposed in (Foster et al., 2016). However, to obtain our results, two extra crucial ingredients are needed:

First, we adopt the ideas of optimism and adaptivity from (Steinhardt and Liang, 2014), which roughly speaking amounts to incorporating a correction term as well as an optimistic prediction into the loss vectors. In (Steinhardt and Liang, 2014), this technique was developed in the Follow-the-Regularized-Leader (FTRL) framework,Although it was confusingly referred as OMD in (Steinhardt and Liang, 2014). but it is in fact crucial here to re-derive it in the OMD framework (due to the next ingredient). The challenges here are to come up with the right correction terms and optimistic predictions.

Second, we apply an individual and increasing learning rate schedule for one of the path-length results. Such increasing learning rate schedule was originally proposed in (Bubeck et al., 2016) and also recently used in (Agarwal et al., 2017), but for different purposes.

Although most algorithmic techniques we use in this work have been studied before, combining all of them, in the general semi-bandit setting, requires novel and non-trivial analysis. The use of log-barrier in the semi-bandit setting is also new as far as we know.

There is a rich literature in deriving adaptive algorithms and regret bounds for online learning with full information feedback (see recent work (Luo and Schapire, 2015; Koolen and Van Erven, 2015; van Erven and Koolen, 2016; Orabona and Pál, 2016; Cutkosky and Boahen, 2017) and references therein), as well as the stochastic bandit setting (such as (Garivier and Cappé, 2011; Lattimore, 2015; Degenne and Perchet, 2016)). Similar results for the adversarial bandit setting, however, are relatively sparse and have been mentioned above. While obtaining regret bounds that depend on the quality of the best action is common in the full information setting, it is in fact much more challenging in the bandit setting, and the only existing result of this kind is the “small-loss” bound (Allenberg et al., 2006; Foster et al., 2016). We hope that our work opens up more possibilities in obtaining these results, despite some recent negative results discovered by Gerchinovitz and Lattimore (2016).

Chiang et al. (2013) proposed bandit algorithms with second-order path-length bounds, but their work requires stronger two-point feedback. The implication of path-length regret bounds on faster convergence rate for computing equilibriums was studied in (Syrgkanis et al., 2015). Other examples of adaptive online learning leading to faster convergence in game theory include (Rakhlin and Sridharan, 2013b; Daskalakis et al., 2015; Foster et al., 2016).

There exist several bandit algorithms that achieve almost optimal regret in both the adversarial setting ($\mathcal{O}(\sqrt{TK})$) and the i.i.d. setting ($\mathcal{O}(\sum_{i:\Delta_{i}\neq 0}\frac{\ln T}{\Delta_{i}})$ where $\Delta_{i}$ is the gap between the expected loss of arm $i$ and the one of the optimal arm) (Bubeck and Slivkins, 2012; Seldin and Slivkins, 2014; Auer and Chiang, 2016; Seldin and Lugosi, 2017). Our results in Section 4.2 have slightly weaker guarantee for the i.i.d. setting (at most $K$ times worse specifically) since it essentially replaces all $\Delta_{i}$ by $\min_{i:\Delta_{i}\neq 0}\Delta_{i}$. On the other hand, however, our results have several advantages compared to previous work. First, our guarantee for the adversarial setting is stronger since it replaces the dependence on $T$ by the loss of the best arm. Second, our logarithmic regret result applies to not just the simple i.i.d. setting, but the more general setting mentioned above where neither independence nor identical distributions is required. Our dependence on $\ln T$ is also better than previous works, resolving an open problem raised by Seldin and Lugosi (2017). Finally, our algorithm and analysis are also arguably much simpler, without performing any stationarity detection or gap estimation. Indeed, the result is in some sense algorithm-independent and solely through a new adaptive regret bound Eq. (9), similar to the results in the full-information setting such as (Gaillard et al., 2014).

Using a self-concordant barrier as regularizer was proposed in the seminal work of (Abernethy et al., 2008) for general linear bandit problems. The log-barrier is technically not a barrier for the decision set of the semi-bandit problem, but still it exhibits many similar properties as shown in our proofs. Optimistic FTRL/OMD was developed in (Chiang et al., 2012; Rakhlin and Sridharan, 2013a). As pointed out in (Steinhardt and Liang, 2014), incorporating correction terms in the loss vectors can also be viewed as using adaptive regularizers, which was studied in several previous works, mostly for the full information setting (see (McMahan, 2017) for a survey).

Problem Setup and Algorithm Overview

The learner’s goal is to minimize the regret, which is the gap between her accumulated loss and that of the best fixed action $b^{*}\in\mathcal{X}$. Formally the regret is defined as

For a convex function $\psi$ defined on a convex set $\Omega$, the Bregman divergence of two points $u,v\in\Omega$ with respect to $\psi$ is defined as $D_{\psi}(u,v)\triangleq\psi(u)-\psi(v)-\langle{\nabla\psi(v),u-v}\rangle$. The log-barrier used in this work is of the form $\psi(u)=\sum_{i=1}^{K}\frac{1}{\eta_{i}}\ln\frac{1}{u_{i}}$ for some learning rates $\eta_{1},\ldots,\eta_{K}\geq 0$ and $u\in\text{conv}(\mathcal{X})$, the convex hull of $\mathcal{X}$. With $h(y)\triangleq y-1-\ln y$, the Bregman divergence with respect to the log-barrier is: $D_{\psi}(u,v)=\sum_{i=1}^{K}\frac{1}{\eta_{i}}\left(\ln\frac{v_{i}}{u_{i}}+\frac{u_{i}-v_{i}}{v_{i}}\right)=\sum_{i=1}^{K}\frac{1}{\eta_{i}}h\left(\frac{u_{i}}{v_{i}}\right).$

The all-zero and all-one vector are denoted by $\mathbf{0}$ and $\mathbf{1}$ respectively. $\Delta_{K}$ represents the ($K-1$)-dimensional simplex. For a binary vector $b$ we write $i\in b$ if $b_{i}=1$. Denote by $K_{0}=\max_{b\in\mathcal{X}}\|b\|_{0}$ the maximum number of arms an action in $\mathcal{X}$ can pick. Note that for MAB, $K_{0}$ is simply $1$.

1 Algorithm Overview

When $a_{t}=\mathbf{0}$, this is studied in (Rakhlin and Sridharan, 2013a) under the name optimistic OMD. When $a_{t}\neq\mathbf{0}$, the closest algorithm to this variant of OMD is its FTRL version studied by Steinhardt and Liang (2014). However, while $\psi_{t}$ is fixed for all $t$ in (Steinhardt and Liang, 2014),Steinhardt and Liang (2014) also uses the notation $\psi_{t}$, but it corresponds to putting $a_{t}$ into a fixed regularizer. some of our results crucially rely on using time-varying $\psi_{t}$ (which corresponds to time-varying learning rate) and also the OMD update form instead of FTRL.

The sampling step $b_{t}\sim w_{t}$ can be done efficiently as long as $\Omega$ can be described by a polynomial number of constraints. The optimization problems in the update rules of $w_{t}$ and $w_{t}^{\prime}$ are convex and can be solved by general optimization methods. For many special cases, however, these two computational bottlenecks have simple solutions. Take MAB as an example, $w_{t}$ directly specifies the probability of picking each arm, and the optimization problems can be solved via a simple binary search (Agarwal et al., 2017).

Broad-OMD with Option I

For the update rules (1) and (2), if the following condition holds:

where $A_{t}\triangleq D_{\psi_{t}}(w_{t+1}^{\prime},w_{t})+D_{\psi_{t}}(w_{t},w_{t}^{\prime})\geq 0$.

The important part of bound (4) is the term $\langle{u,a_{t}}\rangle$, which allows us to derive regret bounds that depend on only the comparator $u$. The key is now how to configure the algorithm such that condition (3) holds, while leading to a reasonable bound (4) at the same time.

Note that with a smaller $a_{t}$, condition (3) becomes more stringent. The entropy regularizer used in (Steinhardt and Liang, 2014) no longer suffices to maintain such a condition. Instead, it turns out that the log-barrier regularizer used by Broad-OMD addresses the issue, as shown below.

The three conditions of the theorem are usually trivially satisfied as we will show. Note that $h(\cdot)$ is always non-negative. Therefore, if the sequence $\{\eta_{t,i}\}_{t=1}^{T+1}$ is non-decreasing for all $i$,One might notice that $\eta_{T+1,i}$ is not defined here. Indeed this term is artificially added only to make the analysis of Section 3.2 more concise, and $\eta_{T+1,i}$ can be any positive number. In Algorithm 2 we give it a concrete definition. the term $\sum_{t=1}^{T}\left(\frac{1}{\eta_{t+1,i}}-\frac{1}{\eta_{t,i}}\right)h\left(\frac{u_{i}}{w_{t+1,i}^{\prime}}\right)$ in bound (5) is non-positive. For some results we can simply discard this term, while for others, this term becomes critical. On the other hand, the term $\ln\frac{w^{\prime}_{1,i}}{u_{i}}$ appears to be infinity if we want to compare with the best fixed action (where $u_{i}=0$ for some $i$). However, this can be simply resolved by comparing with some close neighbor of the best action in $\Omega$ instead, similar to (Foster et al., 2016; Agarwal et al., 2017).

One can see that the expected regret in Corollary 1 only depends on the squared estimation error of $m_{t}$ for the actions that $b^{*}$ chooses! This is exactly the counterpart of results in (Steinhardt and Liang, 2014), but for the more challenging combinatorial semi-bandit problem. Note that our dependence on $K_{0}$ is also optimal (Audibert et al., 2013).

2 Path-length Bound

Therefore, the term $\sum_{t=1}^{T}\langle{u,a_{t}}\rangle$ is close to the first-order path-length but with an extra factor $\max_{t\in[T]}\frac{1}{w_{t,i}}$. To cancel this potentially large factor, we adopt the increasing learning rate schedule recently used in (Agarwal et al., 2017). The idea is that the term h\big{(}\frac{u_{i}}{w_{t+1,i}^{\prime}}\big{)} in Eq. (5) is close to $\frac{1}{w_{t+1,i}}$ if $u_{i}$ is close to $1$. If we increase the learning rate whenever we encounter a large $\frac{1}{w_{t+1,i}}$, then \Big{(}\frac{1}{\eta_{t+1,i}}-\frac{1}{\eta_{t,i}}\Big{)}h\Big{(}\frac{u_{i}}{w_{t+1,i}^{\prime}}\Big{)} becomes a large negative term in terms of $\frac{-1}{w_{t+1,i}}$, which exactly compensates the term $\sum_{t=1}^{T}\langle{u,a_{t}}\rangle$.

To avoid the learning rates increased by too much, similarly to (Agarwal et al., 2017) we use some individual threshold ($\rho_{t,i}$) to decide when to increase the learning rate and update these thresholds in some doubling manner. Also, we mix $w_{t}$ with a small amount of uniform exploration to further ensure that it cannot be too small. The final algorithm, call Broad-OMD+, is presented in Algorithm 2 (only for the MAB setting for simplicity). We prove the following theorem.

Broad-OMD with Option II

For the update rules (1) and (2) with $a_{t}=\mathbf{0}$, we have for all $u\in\Omega$,

where $A_{t}\triangleq D_{\psi_{t}}(w_{t+1}^{\prime},w_{t})+D_{\psi_{t}}(w_{t},w_{t}^{\prime})\geq 0$.

For MAB, the last term can further be lower bounded by $\sum_{t=1}^{T}A_{t}\geq\frac{1}{48\eta}\sum_{t=2}^{T}\sum_{i=1}^{K}\frac{(w_{t,i}-w_{t-1,i})^{2}}{w_{t-1,i}^{2}}$.

If conditions (ii) and (iii) in Theorem 4.2 hold, then Algorithm 3 guarantees

Unlike Eq. (6), this is bounded even without the help of negative regret, but the price is that now the regret depends on the sum of all arms’ path-length. With this calculation, we obtain the following corollary.

This new path-length bound could be $\sqrt{K}$ times better than the one in Section 3.2 in some cases, but $\sqrt{T}$ times larger in others. The extra advantage, however, is the negative term in the regret,In fact, similar negative term, coming from the term $A_{t}$ in Lemma 3.1, also exists (but is omitted) in the bound of Theorem 3.4. However, it is not clear to us how to utilize it in the same way as in Section 4.1.1 if we also want to exploit the other negative term coming from increasing learning rates. explicitly spelled out in Corollary 2, which we discuss next.

It is well-known that in a repeated two-player zero-sum game, if both players play according to some no-regret algorithms, then their average strategies converge to a Nash equilibrium (Freund and Schapire, 1999). Similar results for general multi-player games have also been discovered. The convergence rate of these results is governed by the regret bounds of the learning algorithms, and several recent works (such as those mentioned in the introduction) have developed adaptive algorithms with regret much smaller than the worst case $\mathcal{O}(\sqrt{T})$ by exploiting the special structure in this setup, which translates to convergence rates faster than $1/\sqrt{T}$ in computing equilibriums.

One way to obtain such fast rates is exactly via path-length regret bounds as shown in (Rakhlin and Sridharan, 2013b; Syrgkanis et al., 2015). In these works, the convergence rate $1/T$ is achieved when the players have full-information feedback. We generalize their results to the bandit setting, and show that convergence rate of $1/T^{\frac{3}{4}}$ can be obtained. Though faster than $1/\sqrt{T}$, it is still slower than $1/T$ compared to the full-information setting, which is due to the fact that in bandit we only have first-order instead of second-order path-length bound. We detail the proofs and the remaining open problems in Appendix I.

2 Adapting to Stochastic Bandits

Conclusions and Discussions

In this work we develop and analyze a general bandit algorithm using techniques such as optimistic mirror descent, log-barrier regularizer, increasing learning rate, and so on. We show various applications of this general framework, obtaining several more adaptive algorithms that improve previous works. Future directions include 1) improving the dependence on $K$ for the path-length results; 2) obtaining second-order path-length bounds; 3) generalizing the results to the linear bandit problem.

CYW is grateful for the support of NSF Grant #1755781. The authors would like to thank Chi-Jen Lu for posing the problem of bandit path-length, and to thank Chi-Jen Lu and Yi-Te Hong for helpful discussions in this direction.

References

Appendix A Proof of Lemma 3.1

This is by the first-order optimality condition of $w^{*}$ and direct calculations. Applying this to update rule (2) we have

while applying it to update rule (1) and picking $u=w_{t+1}^{\prime}$ we have

Now we bound the instantaneous regret as follows:

Appendix B Lemmas for Log-barrier OMD

In this section we establish some useful lemmas for update rules (1) and (2) with log-barrier regularizer, which are used in the proofs of other theorems. We start with some definitions.

$w^{\prime}\in\mathcal{E}_{t,w}(1)$ implies $\sum_{i=1}^{K}\frac{1}{\eta_{t,i}}\frac{(w^{\prime}_{i}-w_{i})^{2}}{w_{i}^{2}}\leq 1$. Thus for every $i$, we have $\frac{\lvert{w_{i}^{\prime}-w_{i}}\rvert}{w_{i}}\leq\sqrt{\eta_{t,i}}\leq\frac{1}{9}$, implying $w_{i}^{\prime}\in\left[\frac{8}{9}w_{i},\frac{10}{9}w_{i}\right]\subset\left[\frac{1}{2}w_{i},\frac{3}{2}w_{i}\right]$. Therefore, $\left\lVert h\right\rVert_{t,w^{\prime}}=\sqrt{\sum_{i=1}^{K}\frac{1}{\eta_{t,i}}\frac{h_{i}^{2}}{w^{\prime 2}_{i}}}\geq\sqrt{\sum_{i=1}^{K}\frac{1}{\eta_{t,i}}\frac{h_{i}^{2}}{\left(\frac{10}{9}w_{i}\right)^{2}}}=0.9\left\lVert h\right\rVert_{t,w}$. Similarly, we have $\left\lVert h\right\rVert_{t,w^{\prime}}\leq 1.2\left\lVert h\right\rVert_{t,w}$.

Indeed, using Taylor’s theorem, for any $u\in\partial\mathcal{E}_{t,w_{t}}(1)$, there is an $\xi$ on the line segment between $w_{t}$ and $u$ such that (let $h\triangleq u-w_{t}$)

Define $F_{t}(w)$ and $F_{t+1}^{\prime}(w)$ to be the same as in Lemma B.4. Then we have

On the other hand, for some $\xi$ on the line segment between $w_{t}$ and $w_{t+1}^{\prime}$, we have by Taylor’s theorem and the optimality of $w_{t+1}^{\prime}$,

Since the condition in Lemma B.4 holds, $w_{t+1}^{\prime}\in\mathcal{E}_{t,w_{t}}(1)$, and thus $\xi\in\mathcal{E}_{t,w_{t}}(1)$. Using again Lemma B.2, we have

If the three conditions in Theorem 3.2 hold, Broad-OMD (with either Option I or II) satisfies $\frac{1}{2}w_{t,i}\leq w^{\prime}_{t+1,i}\leq\frac{3}{2}w_{t,i}$.

This is a direct application of Lemmas B.8, B.4, and B.2.

For the MAB problem, if the three conditions in Theorem 3.2 hold, Broad-OMD (with either Option I or II) satisfies $\frac{1}{2}w_{t,i}\leq w^{\prime}_{t,i}\leq\frac{3}{2}w_{t,i}$.

It suffices to prove $w_{t}^{\prime}\in\mathcal{E}_{t,w_{t}}(1)$ by Lemma B.2. Since we assume that the three conditions in Theorem 3.2 hold and $w_{t}\in\Delta_{K}$, we have $\left\lVert m_{t}\right\rVert_{t,w_{t}}^{*}=\sqrt{\sum_{i=1}^{K}\eta_{t,i}w_{t,i}^{2}m_{t,i}^{2}}\leq\sqrt{\frac{1}{162}\sum_{i=1}^{K}w_{t,i}^{2}}\leq\sqrt{\frac{1}{162}}<\frac{1}{3}$. This implies $w_{t}^{\prime}\in\mathcal{E}_{t,w_{t}}(1)$ by a similar arguments as in the proof of Lemma B.4 (one only needs to replace $F_{t+1}^{\prime}(w)$ there by $G(w)\triangleq D_{\psi_{t}}(w,w_{t}^{\prime})$ and note that $w_{t}^{\prime}=\argmin_{w\in\Delta_{K}}G(w)$).

Appendix C Proof of Theorem 3.2 and Corollary 1

of Theorem 3.2. We first prove Eq. (3) holds: by Lemmas B.8 and B.6, we have

where the last two inequalities are by the same calculations done in the proof of Lemma B.8.

Since Eq. (3) holds, using Lemma 3.1 we have (ignoring non-positive terms $-A_{t}$’s),

In the last inequality, we add a term $D_{\psi_{T+1}}(u,w_{T+1}^{\prime})\geq 0$ artificially. As mentioned, $\psi_{T+1}$, defined in terms of $\eta_{T+1,i}$, never appears in the Broad-OMD algorithm. We can simply pick any $\eta_{T+1,i}>0$ for all $i$ here. This is just to simplify some analysis later.

The first term in (16) can be bounded by the optimality of $w_{1}^{\prime}$:

Plugging the above two terms into (16) finishes the proof.

As mentioned, if we let $u=b^{*}$, then $\ln\frac{w_{1,i}^{\prime}}{u_{i}}$ becomes infinity for those $i\notin b^{*}$. Instead, we let $u=\left(1-\frac{1}{T}\right)b^{*}+\frac{1}{T}w_{1}^{\prime}$. With this choice of $u$, we have $\frac{w_{1,i}^{\prime}}{u_{i}}\leq\frac{w_{1,i}^{\prime}}{\frac{1}{T}w_{1,i}^{\prime}}=T$. Plugging $u$ into the above inequality and rearranging, we get

Appendix D Proof of Theorem 3.3

of Theorem 3.3. As in Hazan and Kale (2011a), for the rounds we perform uniform sampling we do not update $w_{t}^{\prime}$. Let $\mathcal{S}$ be the set of rounds of uniform sampling. Then for the other rounds we can apply Corollary 1 to arrive at

The second term can be bounded as follows:

For any $i$, $\sum_{t=2}^{T}(\mu_{t,i}-\mu_{t-1,i})^{2}=\mathcal{O}(1)$.

Appendix E Proof of Theorem 3.4

Let $n_{i}$ be such that $\eta_{T+1,i}=\kappa^{n_{i}}\eta_{1,i}$, i.e., the number of times the learning rate of arm $i$ changes in Broad-OMD+. Then $n_{i}\leq\log_{2}T$, and $\eta_{t,i}\leq 5\eta_{1,i}$ for all $t,i$.

Let $t_{1},t_{2},\ldots,t_{n_{i}}\in[T]$ be the rounds the learning rate for arm $i$ changes (i.e., $\eta_{t+1,i}=\kappa\eta_{t,i}$ for $t=t_{1},\ldots,t_{n_{i}}$). By the algorithm, we have

Therefore, $n_{i}\leq\log_{2}T$. And we have $\eta_{t,i}\leq\kappa^{\log_{2}T}\eta_{1,i}=e^{\frac{\log_{2}T}{\ln T}}\eta_{1,i}\leq 5\eta_{1,i}$.

where the last inequality is by Lemma E.1 and the fact $\kappa-1\geq\frac{1}{\ln T}$. Now we bound the second and the third term in (20) separately.

For the second term, by Lemma B.10 and $T\geq 3$ we have

Noting that $h(y)$ is an increasing function when $y\geq 1$, we thus have

Combining Eq. (21) and Eq. (22) and using the fact $\frac{1+\ln\left(\frac{KT}{4}\right)}{5\ln T}\leq K\ln T$, we continue from Eq. (20) to arrive at

We are almost done here, but note that the left-hand side of (23) is not the desired regret. What we would like to bound is

Appendix F Proofs of Lemma 4.1 and Theorem 4.2

of Lemma 4.1. By the same arguments as in the proof of Lemma 3.1, we have

Therefore, by expanding the instantaneous regret, we have

of Theorem 4.2. Applying Lemma 4.1, we have

Finally we lower bound $A_{t}$ for the MAB case. Note $h(y)=y-1-\ln y\geq\frac{(y-1)^{2}}{6}$ for $y\in[\frac{1}{2},2]$. By Lemma B.10 and B.12, $\frac{w_{t+1,i}^{\prime}}{w_{t,i}}$ and $\frac{w_{t,i}}{w_{t,i}^{\prime}}$ both belong to $[\frac{1}{2},2]$. Therefore,

Appendix G Doubling Trick

We include the version of our algorithm with the doubling trick in Algorithm 3. For simplicity we still assume the time horizon $T$ is known; the extension to unknown horizon is straightforward.

of Theorem 4.3. Let $u=\left(1-\frac{1}{T}\right)b^{*}+\frac{1}{T}w_{1}^{\prime}$ so that $\ln\frac{w^{\prime}_{1,i}}{u_{i}}\leq\ln T$. At some epoch $\beta$, by Theorem 4.2, the break condition, and condition (iii) we have with $\eta_{\beta}\triangleq\frac{2^{-\beta}}{162K_{0}}$,

Suppose that at time $T$, the algorithm is at epoch $\beta=\beta^{*}$. Then we have

Appendix H Proofs of Corollary 2 and Theorem I.1

Appendix I Omitted Details in Section 4.1.1

Although the generalization to multi-player games is straightforward, for simplicity we only consider two-player zero-sum games.

We first describe the protocol of the game. The game is defined by an unknown matrix $G\in^{M\times N}$ where entry $G(i,j)$ specifies the loss (or reward) for Player 1 (or Player 2) if Player 1 picks row $i$ while Player 2 picks column $j$. The players play the game repeatedly for $T$ rounds. At round $t$, Player 1 randomly picks a row $i_{t}\sim x_{t}$ for some $x_{t}\in\Delta_{M}$ while Player 2 randomly picks a column $j_{t}\sim y_{t}$ for some $y_{t}\in\Delta_{N}$. In (Syrgkanis et al., 2015), the feedbacks they receive are the vectors $Gy_{t}$ and $x_{t}^{\top}G$ respectively. As a natural extension to the bandit setting, we consider a setting where the feedbacks are the scalar values $\mathbf{e}_{i_{t}}^{\top}Gy_{t}$ and $x_{t}^{\top}G\mathbf{e}_{j_{t}}$ respectively, that is, the expected loss/reward for the players’ own realized actions (over the opponent’s randomness).

It is clear that each player is essentially facing an MAB problem and thus can employ an MAB algorithm. Specifically, if both players apply Exp3 for example, their expected average strategies converge to a Nash equilibrium at rate $1/\sqrt{T}$. However, if instead Player 1 applies Broad-OMD configured as in Corollary 2, then her regret has a path-length term that can be bounded as follows:

which is closely related to the negative regret term in Corollary 2 for Player 2 if she also employs the same Broad-OMD. The cancellation of these terms then lead to faster convergence rate.

where $\bar{x}=\frac{1}{T}\sum_{t=1}^{T}x_{t},\bar{y}=\frac{1}{T}\sum_{t=1}^{T}y_{t}$ and $\text{\rm Val}=\min\limits_{x\in\Delta_{M}}\max\limits_{y\in\Delta_{N}}x^{\top}Gy=\max\limits_{y\in\Delta_{N}}\min\limits_{x\in\Delta_{M}}x^{\top}Gy$.

due to the assumption $|G(i,j)|\leq 1$. Therefore, by Corollary 2, Player 1’s (pseudo) regret is

Summing up the above two bounds, and using the following fact (by the inequality $a-b\leq\frac{a^{2}}{4b}$):

As shown by the theorem, we obtain convergence rate faster than $1/\sqrt{T}$, but still slower than the $1/T$ rate compared to the full-information setup of (Rakhlin and Sridharan, 2013b; Syrgkanis et al., 2015), due to the fact that we only have first-order instead of second-order path-length bound.

Note that Rakhlin and Sridharan (2013b) also studies two-player zero-sum games with bandit feedback but with an unnatural restriction that in each round the players play the same strategy for four times. Foster et al. (2016) greatly weakened the restriction, but their algorithm only converges to some approximation of Val. For further comparisons, the readers are referred to the comparisons to (Syrgkanis et al., 2015) in (Foster et al., 2016). We also point out that the question raised in (Rakhlin and Sridharan, 2013b) remains open: if the players only receive the realized loss/reward $\mathbf{e}_{i_{t}}^{\top}G\mathbf{e}_{j_{t}}$ as feedback (a more natural setup), can the convergence rate to Val be faster than $1/\sqrt{T}$?

Appendix J Proof of Theorem 4.4

Therefore, the first term on the right-hand side of (27) can be upper bounded by

which implies $H=\mathcal{O}\left(\frac{K\ln T}{\Delta^{2}}\right)$. Therefore, the expected regret is upper bounded by

For the adversarial setting, we continue from an intermediate step of (29):