1 Introduction↩︎

Online learning is a general framework for studying sequential decision-making in unknown environments (see, for example, [1]–[3]). We consider a setting where, at each round, the player chooses an action (a.k.a.arm) from a fixed set of \(K\) actions and incurs the loss associated with the chosen action. The performance of the learner is quantified in terms of regret, which is the difference between the total loss incurred by the learner over the duration of the game, and the smallest cumulative loss obtained by a player that would only ever play the same action throughout the game.

The smallest achievable regret is determined by a number of parameters. One of these parameters is the amount of feedback that the learner receives at each round. There is a whole spectrum of problems, characterized by the amount of feedback received by the learner. At the one extreme of this spectrum is the bandit setting, where the learner only observes the loss of the action taken. At the other extreme is the full information setting, where the learner observes the full loss vector at the end of each round, irrespective of the action played.

There are two common ways to interpolate between full information and bandit feedback. One is to allow the learner to make a limited number of additional observations without restricting how the additional observations are selected. Then no additional observations correspond to the bandit setting and \(K-1\) additional observations correspond to the full information setting. This way of interpolation was proposed by [4] in two variants, "prediction with limited advice" and "multiarmed bandits with paid observations". It was also studied by [5].

The second way of interpolation, which we focus on in this paper, is via feedback graphs [6]. In this setting observations of the learner are governed by a feedback graph on the actions. When an action is played, the learner observes the losses of all of its neighbors in the feedback graph. A complete graph corresponds to the full information setting, whereas a graph containing only self-loops corresponds to the bandit setting. This setting has multiple variants, depending on whether the graph is directed or undirected, observed or unobserved, static or dynamic.

Another important parameter characterizing online learning problems is the type of environment. The two primary types that we focus on are stochastic and adversarial environments. In stochastic environments each action is associated with a fixed, but unknown distribution, and in each round the loss of each action is sampled independently from the corresponding distribution. In adversarial environments the loss sequence is chosen arbitrarily. We consider oblivious adversarial environments, where the loss sequences are chosen independently of the actions taken by the learner.

For a long time stochastic and adversarial environments where studied separately, but in practice the exact nature of environment is rarely known. In recent years this has led to a growing interest in “best-of-both-worlds” algorithms that are robust against adversarial loss sequences and, at the same time, provide tighter regret guarantees in the stochastic regime. Most work has focused on the bandit setting [7]–[11], where the Tsallis-INF algorithm proposed by [12], [13] was shown to achieve the optimal regret rates in both stochastic and adversarial regimes, as well as a number of intermediate regimes. The analysis was further improved by [14] and [15]. In the full information setting [16] have shown that the well-known Hedge algorithm originally designed for the adversarial setting [17] also achieves the optimal stochastic regret. Best-of-both-world results also spilled over to other domains, including additional approaches to full information games and online convex optimization [18]–[20], decoupled exploration and exploitation [21], combinatorial bandits [22], bandits with switching costs [23], MDPs [24], [25], and linear bandits [26].

In the context of online learning with feedback graphs the only best-of-both-worlds result known to us is by [27] for undirected graphs. They present an intricate FTRL-based algorithm with a regularization function that is a product of the Tsallis and Shannon entropies. The algorithm simultaneously enjoys an \(O\big(\sqrt{\chi T} \big(\ln(KT)\big)^2\big)\) pseudo-regret bound in the adversarial regime and an \(O\big(\big(\ln(KT)\big)^4 \sum_{k}\frac{\ln T}{\Delta_k})\) pseudo-regret bound in the stochastic regime, where \(T\) is the number of prediction rounds, \(\chi\) is the clique covering number of the undirected feedback graph, and the summation in the second bound is on the smallest non-zero gap within each clique.

It is tempting to apply an FTRL-based algorithm with Tsallis entropy regularization to online learning with feedback graphs, since Tsallis entropy with power \(a = 1/2\) leads to the optimal Tsallis-INF algorithm for the bandit setting [13] and Tsallis entropy with power \(a=1\) leads to the Hedge algorithm, which is optimal in the full information setting. However, as also noted by [27], extension of the analysis to online learning with feedback graphs when the power \(a \in (1/2, 1)\) is not straightforward and, so far, there was no success in this direction. Furthermore, at the moment it is unclear whether it is possible to derive bounds that take further advantage of the graph structure and depend on the independence number of the graph when \(a < 1\).

Our contribution. We significantly extend and improve on the bounds of [27]. Our results hold for directed graphs (with self-loops), depend on the independence number of the graph, have a better dependence on \(T\) in the stochastic regime, and extend to time-varying feedback graphs. Our approach takes advantage of the common structure shared by two exponential weights algorithms: EXP3.G [28] and EXP3++ [8], [10], to obtain near-optimal best-of-both worlds guarantees. By using similar ideas as in the proof of the regret bound of EXP3.G, the proposed algorithm adapts to the independence number of the graph. We derive an \(O(\sqrt{\tilde{\alpha} T \ln K})\) pseudo-regret bound against adversarial sequences of losses, where \(\tilde{\alpha}\) is the strong independence number, which is a graph dependent quantity smaller than the clique covering number. For undirected graphs, independence number and strong independence number are equal and the result matches the best known lower bound \(\Omega(\sqrt{\alpha T})\) within logarithmic factors [6]. In the stochastic setting we use the idea of injected exploration from EXP3++ to estimate the suboptimality gaps of each arm. By introducing a novel dynamic exploration set and an appropriate exploration rate, we derive an almost optimal regret bound in the stochastic setting. Along the way, we also improve the regret bound of EXP3++ in the stochastic bandit setting. Our exploration set is constructed by sorting the arms by ascending gap estimates, and then adding a new arm to the exploration set if the arm cannot be observed by playing another arm previously added to the set. If we play each arm \(i\) in the exploration set at a rate \(1/\hat{\Delta}_{i}^2\), where \(\hat{\Delta}_i\) is the gap estimate, then all arms \(j\) in the graph are observed with probability at least \(1/\hat{\Delta}_{j}^2\).

To present our main result we introduce some notations. Let \(G = (V, E)\) be a directed feedback graph with independence number \(\alpha\) (where the independence number is computed on \(G\) ignoring edge directions). We define a strongly independent set on \(G\) as an independent set on the subgraph \(G' = (V,E')\), where \((i,j) \in E'\) if and only if \((i,j) \in E\) and \((j,i) \in E\). We use \(\tilde{\alpha}\) to denote the strong independence number of \(G\), and \(\mathcal{I}(G)\) to denote the collection of all the strongly independent sets in \(G\). We note that \(\alpha = \tilde{\alpha}\) for undirected graphs and \(\alpha \le \tilde{\alpha}\) for directed graphs. Now we can present an informal statement of our main result.

We emphasize that Algorithm 1 requires neither prior knowledge of the type of the environment (adversarial or stochastic), nor the time horizon.

1.1 Additional Related Work↩︎

The study of bandits with feedback graphs was initiated by [29] in the adversarial regime and by [30] in the stochastic regime. In the adversarial regime, the optimal regret rates for arbitrary directed graphs were characterized (up to log factors) by [28]. They showed an \(\Omega(T)\) lower bound for graphs that have non-observable nodes (i.e., with an empty in-neighborhood). For graphs with observable nodes, they derived pseudo-regret bounds of order \(O\big(\sqrt{\alpha T} \log(KT)\big)\) when all nodes are strongly observable (i.e., they have a self-loop or their in-neighborhood contains all of the other nodes) and of order \(O\big((\delta \ln K)^{1/3}T^{2/3}\big)\) for weakly observable graphs (where each non-strongly observable node is in the out-neighborhood of some observable node). Here \(\alpha\) is the independence number of the graph and \(\delta\) is the dominating number of the weakly observable portion of the graph. [31] derived results for the multiclass classification with feedback graphs setting. The setting where the graph can adversarially change over time has been studied by [6] in the case of directed graphs with self-loops. For learners that are allowed to observe the feedback graph at the beginning of each round, they achieved a bound of \(O\big(\ln K \sqrt{\ln (KT) \sum_{t = 1}^T \alpha_t}\big)\), where \(\alpha_t\) is the independence number of the graph at time \(t\). For the case of undirected graphs, they proved a refined bound \(O\big(\sqrt{\ln K \sum_{t = 1}^T \alpha_t}\big)\) that holds even when the learner can only observe the graph at the end of each round. Note that, as shown by [32], in order to take advantage of the graph structure in the adversarial regime, it not sufficient to observe the neighborhood of the played action at the end of each round.

In the stochastic regime, [33], [34] considered a fixed, possibly directed, feedback graph. They derived an asymptotic lower bound showing that the regret scales as \(\Omega(c^*\ln T)\), where \(c^*\)—which is related to the domination number of the graph—is the solution to a linear program expressing the trade-off between the loss incurred from playing an action and the observations that can be gathered from playing that action. They proposed an algorithm that can achieve a matching \(O\big(c^*\ln T + K d\big)\) pseudo-regret bound, where \(d\) is the maximum degree in the feedback graph. In the case of graphs that change over time, [32] derived an \(O(\sum_{i \in S} (\ln T) / \Delta_i)\) bound, where \(S\) is a set containing an order of \(\alpha\) arms (up to log factors), and \(\alpha\) is an upper bound on the independence number of the graphs in the sequence. They achieved this result without requiring to observe the graphs fully, and having only access to the neighbourhood of the arm played at the end of the round. Both of these approaches are based on arm elimination algorithms, which—by construction—are not suitable for best-of-both worlds guarantees. The proof strategy of [32] was adapted by [35] to provide refined bounds for both UCB-N and Thompson Sampling-N, which are variants of UCB1 [36] and Thompson Sampling [37]. In both cases, [35] considered undirected feedback graphs and obtained pseudo-regret bounds that scale as \(O\big(\max_{\mathrm{Ind} \in \mathcal{I}(G)}\sum_{i \in \mathrm{Ind}} \ln (KT) (\ln T) / \Delta_i\big)\), where \(\mathcal{I}(G)\) is the collection of all the independence sets of the graph.

2 Problem Setting and Definitions↩︎

2.0.0.1 Problem Setting

We consider a sequential decision-making game, where in each round \(t=1,2,\ldots\), the learner repeatedly plays an action \(I_t \in V\), where \(|V| = K\), receives a feedback based on a feedback graph \(G = (V, E)\), and suffers a loss \(\ell_{t, I_t}\). We consider directed feedback graphs with self-loops, meaning that \((i, i) \in E\) for each vertex \(i \in V\). The feedback received by the learner at the end of round \(t\) is \(\big\{ (i,\ell_{t,i}) \,:\, i \in N^{\mathrm{out}}(I_t) \big\}\), where \(N^{\mathrm{out}}(i) = \{j \in V: (i, j) \in E\}\) is the out-neighbourhood of \(i\). Similarly, we define \(N^{\mathrm{in}}(i) = \{j \in V: (j, i) \in E\}\) to be the in-neighborhood of \(i\). For each arm \(i \in V\), \(\ell_{t, i} \in [0,1]\) for \(t \ge 1\). In the adversarial regime the losses are generated arbitrarily by an oblivious adversary. In the stochastic regime they are independently drawn from a fixed but unknown distribution with expectation \(\mathbb{E}[\ell_{1, i}]\). The performance of the learner is measured in terms of the pseudo-regret: \[\mathcal{R}_T = \ifthenelse{\isempty{\sum_{t = 1}^T \ell_{t, I_t}}{}}{\mathbb{E}}{\mathbb{E} \left[\sum_{t = 1}^T \ell_{t, I_t}\right]} - \min_{i \in V}\ifthenelse{\isempty{ \sum_{t = 1}^T\ell_{t, i}}{}}{\mathbb{E}}{\mathbb{E} \left[ \sum_{t = 1}^T\ell_{t, i}\right]}.\] In the stochastic regime, we define the best arm \(i^*\) as the arm with the smallest expected loss, i.e. \(i^*=\text{argmin}_{i \in V} \mathbb{E}[\ell_{1, i}]\). The pseudo-regret can then be expressed in terms of the suboptimality gaps \(\Delta_i = \mathbb{E}[\ell_{1, i}- \ell_{1, i^*}]\), \[\mathcal{R}_T = \sum_{t = 1}^T \sum_{i\in V} \ifthenelse{\isempty{p_{t, i}}{}}{\mathbb{E}}{\mathbb{E} \left[p_{t, i}\right]}\Delta_i,\] where \(p_{t, i}\) is the probability that the learner plays action \(i\) at round \(t\). We define the smallest suboptimality gap \(\Delta_{\text{min}}= \min_{i : \Delta_i > 0} \left\{\Delta_i\right\}\), and for all \(i\), we define \(\bar\Delta_i = \max \left\{\Delta_{\text{min}}, \Delta_i\right\}\), so that \(\bar \Delta_{i^*}=\Delta_{\text{min}}\). We use \(\ifthenelse{\isempty{}{}}{\mathbb{E}}{\mathbb{E} \left[\right]}_t\) to express expectation conditioned on all randomness up to round \(t\).

2.0.0.2 Properties of Graphs

Recall that a dominating set in \(G\) is a subset \(D \subseteq V\), such that for all \(i \in V\) there exists \(j \in D\), such that \((j, i) \in E\). An independent set in \(G\) is a subset \(S \subseteq V\), such that for all \(i, j \in S\), \((i, j) \not\in E\) and \((j, i) \not\in E\). We define the independence number \(\alpha(G)\) as the size of the largest independent set in the graph \(G\). For clarity, we restate below here the definition of the strong independence number which was already mentioned in the introduction.

We use \(\mathcal{I}(G)\) to denote a collection of all the strongly independent sets in \(G\). We note that \(\alpha = \tilde{\alpha}\) for undirected graphs and \(\alpha \le \tilde{\alpha}\) for directed graphs.

3 Algorithm↩︎

We present the EXP3.G++ algorithm (Algorithm 1), which is a combination of the EXP3.G algorithm of [28] and the EXP3++ algorithm of [10] with a novel exploration scheme described in Algorithm 2. This scheme ensures that the additional feedback the learner obtains (relative to the bandit setting) is used nearly optimally.

To understand the motivation behind the novel exploration scheme, note that in the stochastic setting EXP3.G++ needs to ensure that the loss of each arm is observed sufficiently often. However, if we would play each arm too often, the regret would scale with the number of arms, rather than with the independence number or some other graph-theoretic quantity. To avoid that, we exploit the central property of feedback graphs: since we can gather information on certain arms by playing adjacent arms in the graph, we can restrict exploration to a subset of nodes and yet obtain sufficient information on all the arms. We exploit this observation, to design a strategy for selecting an exploration set \(S_t\) at each round \(t\). \(S_t\) is defined in terms of estimated suboptimality gaps \(\hat{\Delta}_{t, i}\), which are maintained by EXP3.G++. Crucially, the exploration set ensures that, with high probability, the empirical gaps are reliable estimates of the true suboptimality gaps \(\Delta_i\). In turn, this ensures that we observe the loss of each arm sufficiently often.

The construction of the exploration set \(S_t\) is detailed in Algorithm 2, which is used by EXP3.G++ to update the exploration rates \(\varepsilon_{t, i}\) according to 1 . Algorithm 2 starts by sorting the arms according to their gap estimates in ascending order. The exploration set is then greedily constructed by sequentially selecting the next arm with the smallest \(\hat{\Delta}_{t, i}\), and discarding all the arms in the out-neighborhood of that arm. The exploration set can be constructed in \(O(K^3)\) time, but note that we only need to recompute it only when the order of the estimated suboptimality gaps changes. The exploration set \(S_t\) has several useful properties, as shown in Proposition 1 below.

We define the exploration rates at round \(t\) in terms of the exploration set \(S_t\), which is constructed using the aforementioned procedure. For all arms \(i\) in \(V\), \[\varepsilon_{t, i} = \min \left\{\frac{1}{2K}, \frac{1}{2} \sqrt{\frac{\lambda \ln K}{tK^2}}, \xi_{t, i}\right\}, \label{eq:def95eti}\tag{1}\] for some constant \(\lambda \in [1, K]\) and where \(\xi_{t, i}\) depends on whether \(i \in S_t\) or not: \[\xi_{t, i} = \begin{cases} ({\beta \ln t})/({t \hat{\Delta}_{t, i}^2}), &\qquad \text{if}\, i \in S_t,\\ {4}/{t^2}, &\qquad \text{otherwise}, \end{cases} \label{eq:def95xiti}\tag{2}\] where \(\beta > 0\) is a constant. The role of \(\xi_{t,i}\) changes depending on whether we are in an adversarial or stochastic environment. In an adversarial environment, we use \(4/t^2 \leq \xi_{t,i}\) to ensure that we sample each arm with a small positive probability, which is essential to bound the second-order term in the regret bound in terms of the independence number. Note that \(\varepsilon_{t, i} \leq \frac{1}{2} \sqrt{\frac{\lambda \ln K}{tK^2}}\), so choosing \(\lambda = \tilde{\alpha}\) ensures that the cost of exploration is bounded by \(\tilde{O}(\sqrt{\tilde{\alpha} T})\). In the stochastic environment, the construction of the exploration set and the choice of \(\xi_{t, i}\) ensure that, at each round \(t\), each \(i \in V\) is observed with probability at least \(({\beta \ln t})/({t \hat{\Delta}_{t, i}^2})\), independently of whether \(i\) is in the exploration set at round \(t\).

Formally, our procedure ensures that we can lower bound the probability with which any arm is observed. In the algorithm we use \(P_{t, i} = \ifthenelse{\isempty{i \in N^{\mathrm{out}}(I_t)}{}}{\mathbb{P}}{\mathbb{P} \left[i \in N^{\mathrm{out}}(I_t)\right]}\) to denote the probability that arm \(i\) is observed at round \(t\). We can lower bound this quantity by only considering the minimum rate at which each arm is observed according to the exploration rate \(\varepsilon_{t, i}\) and our construction of the exploration sets. We use \(o_{t, i}\) to denote that quantity, and we have for all \(t\) and \(i\), \[P_{t, i} \geq o_{t, i} = \min \left\{\frac{1}{2K}, \frac{1}{2} \sqrt{\frac{\lambda \ln K}{tK^2}}, \frac{\beta \ln t}{t \hat{\Delta}_{t, i}^2}\right\}. \label{eq:oti95lb}\tag{3}\] The definition of \(o_{t, i}\) uses that \(S_t\) is a dominating set. The difference between \(\varepsilon_{t, i}\) and \(o_{t, i}\) is key to take advantage of the graph structure. First, we need to lower bound \(o_{t, i}\) to ensure that enough observations (counted by \(O_{t, i}\) in Algorithm 1) are made for each arm, such that our gap estimates are reliable. Simultaneously, we upper bound \(\varepsilon_{t, i}\) to ensure that the extra exploration is not too costly. Here we benefit from the fact that \(S_t\) is a strongly independent set on \(G\).

We ensure that all arms get sufficiently many observations and derive the following concentration bounds on the gap estimates \(\hat{\Delta}_{t, i}\) computed by Algorithm 1. Concentration of the gap estimates around the true gaps is crucial for bounding the regret in the stochastic setting.

A proof of the lemma is provided in 10.

We run the algorithm with \(\gamma = 4\) and \(\beta = 64 (\gamma + 1) = 320\) which is a different parameterization from the EXP3++ algorithm [10], which uses \(\gamma = 3\) and \(\beta = 256\). Picking a larger value of \(\gamma\) means that the confidence intervals are slightly larger, which allows us to obtain a better dependency on the suboptimality gaps. Indeed, under the same assumptions as in 1, if \(\gamma = 4\) and \(t \geq t_{\mathrm{min}}(i)\), we have that \[\frac{(\ln t)^2}{t} \leq \frac{\lambda \Delta_i^4 \ln K}{4K^2 \beta^2} \;\text{, implying}\; \left(\frac{\ln t}{t\Delta_i^2}\right)^{2} = \frac{\left(\ln t\right)^2}{t^2\Delta_i^4} = \frac{\left(\ln t\right)^2}{t} \frac{1}{t\Delta_i^4} \leq \frac{\lambda \Delta_i^4 \ln K }{4K^2 \beta^2} \frac{1}{t\Delta_i^4} = \frac{1}{t} \frac{\lambda \ln K}{4K^2\beta^2}.\]

4 Adversarial Analysis↩︎

Our result for the adversarial regime is given in the following theorem.

On undirected graphs, this bound matches the one of [6] which implies that in the adversarial regime we are not paying a price for the extra guarantees that we derive in the stochastic regime. On directed graphs, if the difference between \(\alpha\) and \(\tilde{\alpha}\) is large, it may be advantageous to express the bound in terms of the independence number of the graph rather than its strong independence number at the cost of a logarithmic factor. See Section 6 for additional results in this direction.

We give a sketch of the proof here and defer the detailed proof to Appendix 9.

4.0.0.1 Proof sketch.

We separate the first \(K\) rounds, in which the algorithm plays deterministically, from the remaining rounds, where we bound separately the contributions to the regret from the exponential weights and from the extra exploration. To bound the contribution of the extra exploration, we use that \(\varepsilon_{t, i} \leq \frac{1}{2} \sqrt{\frac{\tilde{\alpha} \ln K}{t K^2}}\) for all \(t\) and \(i\), meaning that the extra exploration contributes at most \(O(\sqrt{\tilde{\alpha} T \ln K})\) to the regret. For bounding the contribution of the exponential weights to the regret, we follow the standard analysis of EXP3 with time varying learning rate [2]. We bound the second order term by exploiting the fact that \(p_{t, i}\) and \(q_{t, i}\) are close to each other because \(\varepsilon_{t, i} \leq \frac{1}{2K}\) for all \(t\) and \(i\). This allows us to bound the second order term in terms of \(\sum_{i \in V} \frac{p_{t, i}}{P_{t, i}}\), which is the sum on the ratios between the probability of playing an arm and the probability of observing it. This quantity can be bounded by the strong independence number of the graph (Lemma 10 [6]).

5 Stochastic Analysis↩︎

Our result for the stochastic regime is given in the following theorem.

We remark that the last two terms do not depend on \(T\). Moreover, the leading coefficient of the term scaling with \((\ln T)^2\) sums over an independence set (as opposed to summing over the entire action set). The lower bound for this problem scales as \(\Omega (c^* \ln T)\), where \(c^*\) is a graph dependent quantity which takes the size of the suboptimality gaps into account [33]. Compared to that, our result is suboptimal by a logarithmic factor and our dependency on the strong independence number of \(G\) is weaker. The algorithms of [33], [34] and [32] almost match the lower bound, but their elimination based structure prevents them from being applicable in best-of-both-worlds settings. In the undirected case, we obtain the same dependence on \(T\) and on the set of arms as the UCB-N algorithm analysed by [35].

We provide a sketch of the proof here. The detailed version can be found in Appendix 11.

5.0.0.1 Proof sketch.

Let \(t_{\mathrm{min}}= \max_{i: \Delta_{i} > 0} \left\{t_{\mathrm{min}}(i)\right\} = \max \left\{ {t\ge 0} : \frac{1}{2}\sqrt{\frac{\tilde{\alpha} \ln K}{t K^2}} \leq \frac{ \beta \ln t}{t\Delta_{\text{min}}^2}\right\}\). The pseudo-regret can be decomposed by treating the first \(t_{\mathrm{min}}\) rounds like in the adversarial case, and by using a refined bound for the stochastic regime in the remaining rounds. \[\begin{align} R_T = R_{t_{\mathrm{min}}} + \sum_{t = t_{\mathrm{min}}}^T \sum_{i \,:\, \Delta_i > 0} \Delta_i \ifthenelse{\isempty{p_{t, i}}{}}{\mathbb{E}}{\mathbb{E} \left[p_{t, i}\right]} \leq R_{t_{\mathrm{min}}} + \sum_{t = t_{\mathrm{min}}}^T \sum_{i \,:\, \Delta_i > 0} \Delta_i \big(\ifthenelse{\isempty{q_{t, i}}{}}{\mathbb{E}}{\mathbb{E} \left[q_{t, i}\right]} + \ifthenelse{\isempty{\varepsilon_{t, i}}{}}{\mathbb{E}}{\mathbb{E} \left[\varepsilon_{t, i}\right]}\big). \addtocounter{equation}{1}{} \label{decomp95stoch95reg2} \end{align}\tag{4}\] Note that \(t_{\mathrm{min}}\) is time independent: \(t_{\mathrm{min}}= \frac{c}{\Delta_{\text{min}}^4} \left(\ln \left(\frac{c}{\Delta_{\text{min}}^4}\right)\right)^2\) for a positive constant \(c\), therefore, \[R_{t_{\mathrm{min}}} = C_0 \sqrt{\tilde{\alpha} \;t_{\mathrm{min}}} = C_1 \frac{K}{\Delta_{\text{min}}^2} \left(\ln\left(\frac{K}{\Delta_{\text{min}}}\right)\right),\] where the first equality follows from Theorem 2 and \(C_0, C_1\) are universal constants. After the initial \(t_{\mathrm{min}}\) rounds, enough observations on all arms have been gathered to ensure with high probability that the gap estimates of all arms are close to their true gaps, as stated in Lemma 1. These concentration inequalities allow us to show that the two following propositions hold.

Formal statements and proofs of the above propositions are in Appendix 11. These propositions ensure that after \(t_{\mathrm{min}}\) steps the exponential weights of all suboptimal arms \(i\) are small, the extra exploration \(\varepsilon_{t,i}\) achieves the correct rate, and that the sum of the probabilities that the suboptimality gap estimates fail in any of the rounds is of order \(O( \tilde{\alpha} \ln T)\). Applying these propositions to 4 finishes the proof.

Our approach to bound the pseudo-regret in the initial rounds differs from the one of [10] as we take advantage of the adversarial bound in these rounds. ([16] used a similar approach to derive best-of-both worlds guarantees for the Hedge algorithm.) This refinement improves upon the result of [10] by replacing \(\sum_{i: \Delta_i > 0} \frac{1}{\Delta_i^3}\) with \(\frac{1}{\Delta_{\text{min}}^2}\) (numerical constants ignored) in the time-independent part of the bound.

6 Extension to Time Varying Feedback Graphs↩︎

A natural extension of our results is to the setting where the feedback graphs are allowed to change over time. We consider a setting, where an oblivious adversary chooses a feedback graph at each round and the algorithm observes the graph at the beginning of the round. In the stochastic regime, the knowledge of the full feedback graph is required at the beginning of the round in order to construct the exploration set. Since computation of the independence number is an NP-hard problem, it is vital that we tune our algorithm so that it can adapt to the independence number of the graphs without needing to actually compute it. In order to do so, we define the quantity: \[\theta_t := \sum_{i \in V} \frac{p_{t, i}}{P_{t, i}}, \label{eq:def95theta}\tag{5}\] which is the sum of the ratios of the probability of playing an arm to the probability of observing its loss. By adapting the learning rate we show that in the adversarial setting our regret bound is of order \(\sqrt{\sum_{t=1}^T \theta_t}\), for which we can use Lemma 5 of [28] to upper bound \(\theta_t\) in terms of \(\alpha_t\) to obtain the desired result. As we do not know the independence numbers ahead of time, we tune the exploration rates defined in equation 1 with \(\lambda = 1\) to ensure that the exploration is never too large. This exploration rate allows us to apply Lemma 1 with \(\lambda = 1\), and derive the following result.

A proof of this theorem is provided in Appendix 12. In the adversarial regime, adapting to graphs that change over time replaces the dependence on the strong independence number by the average on the independence numbers of the sequence of graphs, but comes at the cost of a multiplicative logarithmic factor. In the stochastic regime, the first term of the bound is a sum over the \(\tilde{\alpha}_n\) arms that have the smallest non-zero suboptimality gaps. In the case of undirected graphs, if we upper bound the infimum by taking \(n = 0\), we have \(\tilde{\alpha}_0 = \max_{t > 1} \left\{\alpha(G_t)\right\}\), which matches the dependency on gaps achieved by [32], who got an \(O \left( \max_{S \subset V\backslash \left\{i^*\right\}: |S| = O\left(\alpha\right)} \sum_{i \in S} \frac{\ln T}{\Delta_i}\right)\) bound.

7 Conclusion↩︎

[27] left open the following questions: is it possible to achieve best-of-both-worlds regret bounds in terms of the independence number, and can the dependence on \(T\) in their regret bounds be improved? We partially answered these questions with the EXP3.G++ algorithm and derived near-optimal best-of-both-worlds guarantees for directed feedback graphs. Our regret bounds depend on the independence number of the feedback graphs and improve upon the results of [27] by poly-logarithmic factors in both the adversarial and stochastic regimes. Furthermore, we extended our results to time-varying feedback graphs with a computationally efficient algorithm.

8 Tools to Bound Series↩︎

We use the following lemmas to bound series.

We also require a variation of this bound to handle the case where the denominator of the sum only sums up to index \(t - 1\). The proof of this Lemma follows from [38] that we generalized to adapt to sequences of \(a_t\) that are not restricted to the \([0, 1]\) interval.

9 Proof of Theorem 2↩︎

We follow the proof structure of Theorem 2 from [28], and use Lemma 7 from [8] where \(X_{t, i} = \tilde{\ell}_{t, i}\) for all \(t, i\) as a base for the analysis of EXP3.

We also require Lemma 10 from [6] to take advantage of the structure of the feedback graph. That Lemma depends on a graph dependent quantity: the maximum acyclic subgraph of a feedback graph \(G\), which is defined by [6] as follows. For undirected graphs, using this approach leads to tighter bounds compared to using the bound from [28].

A key property of the maximum acyclic subgraph is that for any graph \(G\), \(\alpha (G) \leq \mathrm{mas}(G)\) and for undirected graphs, \(\alpha(G) = \mathrm{mas}(G)\) [6]. We now show that for any directed graph \(G\), the maximum acyclic subset of \(G\) can be upper bounded by its strong independence number.

This characterization allows us to use the following lemma and derive bounds that scale with the strong independence number.

With those results, we can move on to the proof of Theorem 2.

10 Properties of the Gaps Estimates↩︎

In this section, we provide upper and lower high probability bounds for the estimates of the suboptimality gaps. We decompose the proof of Lemma 1 in two parts.

10.1 Upper bound↩︎

We start by deriving a high probability upper bound. For this bound, we have to be careful with the fact that the gap estimates are clipped in the \([0, 1]\) interval. We first upper derive bounds on UCB and LCB.

Using this result, we can move on to bound the gap estimates.

10.2 Lower bound↩︎

To derive a lower bound on the gap estimates and prove the second part of Lemma 1, we start by proving some intermediate results. recall that we use \(o_{t, i}\) to lower bound the probability of observing the loss of arm \(i\) at round \(t\), and that by construction we have for all \(t\), \(i\): \[o_{t, i} =\min \left\{\frac{1}{2K}, \frac{1}{2}\sqrt{\frac{\lambda \ln K}{t K^2}}, \frac{\beta \ln t}{t \hat{\Delta}_{t, i}^2}\right\}.\] We also recall that for all \(i\) such that \(\Delta_i > 0\), we defined \(t_{\mathrm{min}}(i)\) as: \[t_{\mathrm{min}}(i) = \max \left\{t \ge 0: \;\frac{1}{2}\sqrt{\frac{\lambda \ln K}{t K^2}} \leq \frac{ \beta \ln t}{t\Delta_i^2}\right\}.\]

10.2.0.1 A lower bound for \(o_{t, i}\).

As \(\hat{\Delta}_{t, i}\) is a random variable, we derive a high probability lower bounds on \(o_{t, i}\).

Note that the second event lower bounds the rate at which observations on optimal arm \(i^*\) are gathered in terms of the gap with the suboptimal arm \(i\).

10.2.0.2 A lower bound for \(O_{t, i}\)

We now want to lower bound the number of observations of an arm up to round \(t\). We rely on the following concentration inequality.

We recall that the first \(K\) rounds of the algorithm are deterministic, and that each arm is observed at least once. We use \(O_{[K+1:t], i}\) to refer to the number of observations from rounds \(K+1\) to \(t\), and we note that \(O_{t, i} \geq O_{[K+1:t], i} + 1\). We have: \[\begin{align} \ifthenelse{\isempty{O_{t, i} \leq \frac{\beta \ln t}{2 \Delta_i^2}}{}}{\mathbb{P}}{\mathbb{P} \left[O_{t, i} \leq \frac{\beta \ln t}{2 \Delta_i^2}\right]} & \leq \ifthenelse{\isempty{O_{[K+1:t], i} \leq \frac{\beta \ln t}{2 \Delta_i^2} - 1}{}}{\mathbb{P}}{\mathbb{P} \left[O_{[K+1:t], i} \leq \frac{\beta \ln t}{2 \Delta_i^2} - 1\right]} \\ & \leq \ifthenelse{\isempty{O_{[K+1:t], i} \leq \frac{\beta \ln t}{2 \Delta_i^2} \frac{t-K}{t}}{}}{\mathbb{P}}{\mathbb{P} \left[O_{[K+1:t], i} \leq \frac{\beta \ln t}{2 \Delta_i^2} \frac{t-K}{t}\right]}, \end{align}\] where the second step follows from, \(\frac{\beta \ln t}{2 \Delta_i^2} - 1 \leq \frac{\beta \ln t}{2 \Delta_i^2} \frac{t-K}{t} \Leftrightarrow \frac{K \beta \ln t}{2t \Delta_i^2} \leq 1\), which is true for \(t \geq t_{\mathrm{min}}(i)\) as \[\frac{K \beta \ln t}{2t \Delta_i^2} \leq \frac{K \beta \ln t}{2 \Delta_i^2} \frac{\Delta_i^4 \lambda \ln K}{4 K^2 \beta^2 \ln^2 t} \leq \frac{\Delta_i^2 \ln K}{8 \ln t} \leq \frac{\Delta_i^2}{8} \leq 1.\] We can apply 5 on the \(t-K\) random variables \(\ifthenelse{\isempty{i \in N^{\mathrm{out}}(I_s)}{}}{\mathbb{1}}{\mathbb{1} \left[i \in N^{\mathrm{out}}(I_s)\right]}\) for \(s \in \left[K+1, t\right]\) and we get: \[\begin{align} \ifthenelse{\isempty{O_{t, i} \leq \frac{\beta \ln t}{2 \Delta_i^2}}{}}{\mathbb{P}}{\mathbb{P} \left[O_{t, i} \leq \frac{\beta \ln t}{2 \Delta_i^2}\right]} & \leq \ifthenelse{\isempty{\left(O_{[K+1:t], i} \leq \frac{\beta \ln t}{2 \Delta_i^2} \frac{t-K}{t} \right) \land \mathcal{E}_{t, i}}{}}{\mathbb{P}}{\mathbb{P} \left[\left(O_{[K+1:t], i} \leq \frac{\beta \ln t}{2 \Delta_i^2} \frac{t-K}{t} \right) \land \mathcal{E}_{t, i}\right]} + \ifthenelse{\isempty{\overline{\mathcal{E}_{t, i}}}{}}{\mathbb{P}}{\mathbb{P} \left[\overline{\mathcal{E}_{t, i}}\right]} \\ & \leq e^{-\frac{t-K}{t}\frac{\beta \ln t}{8 \Delta_i^2}} + \frac{1}{2} \left(\frac{\ln t}{t \Delta_i^2}\right)^{\gamma -2}\\ & \leq e^{-\frac{3}{4}\frac{\beta \ln t}{8 \Delta_i^2}} + \frac{1}{2} \left(\frac{\ln t}{t \Delta_i^2}\right)^{\gamma -2}\\ & \leq \left(\frac{1}{t}\right)^{\beta/10} + \frac{1}{2} \left(\frac{\ln t}{t \Delta_i^2}\right)^{\gamma -2}, \end{align}\] where we use that \(t \geq t_{\mathrm{min}}(i) \geq 4K\), so \(\frac{t - K}{t} \geq \frac{3}{4}\).

10.2.0.3 A lower bound for \(\hat{\Delta}_{t, i}\)

Using Lemma 8, we know that the upper and lower confidence bounds satisfy: \(\ifthenelse{\isempty{\text{UCB}_{t, i^*} \leq \mu_{i^*} \lor \text{LCB}_{t, i} \geq \mu_{i}}{}}{\mathbb{P}}{\mathbb{P} \left[\text{UCB}_{t, i^*} \leq \mu_{i^*} \lor \text{LCB}_{t, i} \geq \mu_{i}\right]} \leq \frac{2}{Kt^{\gamma -1}}\). Then assuming that \(\text{UCB}_{t, i^*} \geq \mu_{i^*}\) and \(\text{LCB}_{t, i} \leq \mu_{i}\), we have: \[\begin{align} \hat{\Delta}_{t, i} \geq & \text{LCB}_{t, i} - \min_{j \neq i} \text{UCB}_{t, i} \\ \geq & \text{LCB}_{t, i} - \text{UCB}_{t, i^*} \\ \geq & \frac{\hat{L}_{t-1, i}}{O_{t-1, i}} - \sqrt{\frac{\gamma \ln\left(tK^{1/\gamma}\right)}{2O_{t-1, i}}} - \frac{\hat{L}_{t-1, i^*}}{O_{t-1, i^*}} - \sqrt{\frac{\gamma \ln\left(tK^{1/\gamma}\right)}{2O_{t-1, i^*}}} \\ = & \frac{\hat{L}_{t-1, i}}{O_{t-1, i}} + \sqrt{\frac{\gamma \ln\left(tK^{1/\gamma}\right)}{2O_{t-1, i}}} - 2 \sqrt{\frac{\gamma \ln\left(tK^{1/\gamma}\right)}{2O_{t-1, i}}} \\ & - \left( \frac{\hat{L}_{t-1, i^*}}{O_{t-1, i^*}} - \sqrt{\frac{\gamma \ln\left(tK^{1/\gamma}\right)}{2O_{t-1, i^*}}}\right) - 2\sqrt{\frac{\gamma \ln\left(tK^{1/\gamma}\right)}{2O_{t-1, i^*}}} \\ = & \text{UCB}_{t, i} - \text{LCB}_{t, i^*} - 2 \sqrt{\frac{\gamma \ln\left(tK^{1/\gamma}\right)}{2O_{t-1, i}}} - 2\sqrt{\frac{\gamma \ln\left(tK^{1/\gamma}\right)}{2O_{t-1, i^*}}} \\ \geq & \Delta_i - 2 \sqrt{\frac{\gamma \ln\left(tK^{1/\gamma}\right)}{2O_{t-1, i}}} - 2\sqrt{\frac{\gamma \ln\left(tK^{1/\gamma}\right)}{2O_{t-1, i^*}}}. \end{align}\] Using the previously derived high probability bounds, assuming that \(O_{t, i} \geq \frac{\beta \ln t}{2 \Delta_i^2}\) and \(O_{t, i^*} \geq \frac{\beta \ln t}{2 \Delta_i^2}\), and using that \(t \geq t_{\mathrm{min}}(i) \geq K\), we have: \[\begin{align} \hat{\Delta}_{t, i} \geq & \Delta_i - 2 \sqrt{\frac{\gamma \ln\left(tK^{1/\gamma}\right)}{2O_{t-1, i}}} - 2\sqrt{\frac{\gamma \ln\left(tK^{1/\gamma}\right)}{2O_{t-1, i^*}}} \\ \geq & \Delta_i - 4 \sqrt{\frac{2 \Delta_i^2 \gamma \ln\left(tK^{1/\gamma}\right)}{2\beta \ln t}} \\ \geq & \Delta_i - 4 \sqrt{\frac{\Delta_i^2 (\gamma + 1) \ln\left(tK^{1/\gamma}\right)}{\beta \ln t}} \addtocounter{equation}{1}{} \label{proof95lb95eq1}\\ = & \Delta_i \left(1 - 4\sqrt{\frac{\gamma + 1}{\beta}}\right), \end{align}\tag{9}\] where equation 9 follows from \(t \geq K\), so \(\gamma \ln\left(tK^{1/\gamma}\right) = \gamma \ln\left(t^\gamma K\right) \leq \ln\left(t^\gamma t\right) = \left(\gamma + 1\right) \ln t\). Using that \(\beta \geq 64\left(\gamma + 1\right)\), we have:

\[\ifthenelse{\isempty{\hat{\Delta}_{t, i} \leq \frac{1}{2}\Delta_i}{}}{\mathbb{P}}{\mathbb{P} \left[\hat{\Delta}_{t, i} \leq \frac{1}{2}\Delta_i\right]} \leq \left(\frac{\ln t}{t \Delta_i^2}\right)^{\gamma -2} + \frac{2}{Kt^{\gamma - 1}} + 2\left(\frac{1}{t}\right)^{\beta/10} .\]

11 Proof of Theorem 3↩︎

In the stochastic regime, we decompose the regret bound into three terms that we bound separately. First, during the initial \(t_{\mathrm{min}}= \max_{i: \Delta_i > 0} \left\{t_{\mathrm{min}}(i)\right\}\) rounds we use the adversarial bound. Then, in the remaining rounds we bound the contribution of the exponential weights and of the exploration separately.

11.1 Control over the Initial Rounds↩︎

We start by deriving a time independent upper bound on \(t_{\mathrm{min}}(i)\) for all vertices \(i\) such that \(\Delta_i > 0\).

11.2 Control over the Exponential Weights↩︎

Proposition 2 introduced in the proof sketch of Theorem 3 is based on the following result.

To prove this result, we can follow the same derivation as in [10]. We want to bound the \(q_{t, i}\) for all \(i\) such that \(\Delta_i > 0\) and \(t \geq t_{\mathrm{min}}(i)\). First, we note that \[\begin{align} q_{t, i}& = \frac{\exp(-\eta_t \tilde{L}_{t, i})}{\sum_{j \in V}\exp(-\eta_t \tilde{L}_{t, j})} \\ & = \frac{\exp(-\eta_t (\tilde{L}_{t, i} - \tilde{L}_{t, i^*})) }{\sum_{j \in V}\exp(-\eta_t (\tilde{L}_{t, j}- \tilde{L}_{t, i^*})))} \\ & \leq \exp(-\eta_t (\tilde{L}_{t, i} - \tilde{L}_{t, i^*})) \\ & := \exp(-\eta_t \tilde{\Delta}_{t, i}), \end{align}\] where \(i^*\) is the best arm, and where the inequality holds because one term of the sum is \(\exp(-\eta_t (\tilde{L}_{t, i^*} - \tilde{L}_{t, i^*})) = 1\) and the other terms are positive, so the denominator is greater than \(1\). We now want to want to ensure that \(\tilde{\Delta}_{t, i}:= \tilde{L}_{t, i} - \tilde{L}_{t, i^*}\) is close to \(t \Delta_i\). To do so, we want to apply a variant of Bernstein’s inequality on the martingale sequence difference \(t\Delta_i - \tilde{\Delta}_{t, i} = \sum_{s = 1}^t X_s\), where each single term of the sequence is defined as \(X_s = \Delta_i - (\tilde{\ell}_{s, i} - \tilde{\ell}_{s, i^*})\).

In order to apply the this theorem, we need to bound \(\max_{1\leq s \leq n} \left\{X_s\right\}\) and \(\sum_{s=1}^n \ifthenelse{\isempty{(X_s)^2| \mathcal{F}_{s-1}}{}}{\mathbb{E}}{\mathbb{E} \left[(X_s)^2| \mathcal{F}_{s-1}\right]}\).

11.2.0.1 Control of \(\max_{1\leq s \leq t} \left\{X_s\right\}\)

For each \(s\) we have: \[\begin{align} X_s & = \Delta_i - (\tilde{\ell}_{s, i} - \tilde{\ell}_{s, i^*}) \\ & \leq 1 + \ell_{s, i^*} \\ & \leq 1 + \frac{1}{P_{t, i^*}} \\ & \leq 1 + \max\left\{2K, 2\sqrt{\frac{sK^2}{\lambda \ln K}}, \frac{s \hat{\Delta}_{s, i^*}^2}{\beta \ln s}\right\} \addtocounter{equation}{1}{} \label{proof95cn951}\\ & \leq 1.25 \max\left\{2K, 2\sqrt{\frac{sK^2}{\lambda \ln K}}, \frac{s \hat{\Delta}_{s, i^*}^2}{\beta \ln s}\right\} \\ \end{align}\tag{10}\] where equation 10 holds by definition of \(o_{t, i^*}\). Using the same argument as in the proof of 1, we know that \(t \geq t_{\mathrm{min}}(i)\), and if \(s \leq \frac{t \Delta_i^2}{ \ln t}\) then \(\frac{s \hat{\Delta}_i^2}{\ln s} \leq \frac{s}{\beta} \leq \frac{ t \Delta_i^2}{ \beta \ln t}\) then:

\[\begin{align} \ifthenelse{\isempty{ \exists s \leq t: \max\left\{2K, 2\sqrt{\frac{sK^2}{\lambda \ln K}}, \frac{s \hat{\Delta}_{s, i^*}^2}{\beta \ln s}\right\} \geq \frac{ t \Delta_i^2}{ \beta \ln t}}{}}{\mathbb{P}}{\mathbb{P} \left[ \exists s \leq t: \max\left\{2K, 2\sqrt{\frac{sK^2}{\lambda \ln K}}, \frac{s \hat{\Delta}_{s, i^*}^2}{\beta \ln s}\right\} \geq \frac{ t \Delta_i^2}{ \beta \ln t}\right]} & = \ifthenelse{\isempty{ \exists s \in \left[\frac{t \Delta_i^2}{ \ln t}, t\right]: \Delta_{s, i^*} \geq \Delta_i}{}}{\mathbb{P}}{\mathbb{P} \left[ \exists s \in \left[\frac{t \Delta_i^2}{ \ln t}, t\right]: \Delta_{s, i^*} \geq \Delta_i\right]} \\ & \leq \ifthenelse{\isempty{ \exists s \in \left[\frac{t \Delta_i^2}{ \ln t}, t\right]: \Delta_{s, i^*} \geq \overline{\Delta_{i^*}}}{}}{\mathbb{P}}{\mathbb{P} \left[ \exists s \in \left[\frac{t \Delta_i^2}{ \ln t}, t\right]: \Delta_{s, i^*} \geq \overline{\Delta_{i^*}}\right]}, \end{align}\] because \(\Delta_i \geq \Delta_{\text{min}}= \bar \Delta_{i^*}\). Let \(\kappa_t = \max_{1\leq s \leq t} \left\{X_s\right\}\), and we deduce: \[\ifthenelse{\isempty{ \kappa_t \geq \frac{1.25 t \Delta_i^2}{\beta \ln t}}{}}{\mathbb{P}}{\mathbb{P} \left[ \kappa_t \geq \frac{1.25 t \Delta_i^2}{\beta \ln t}\right]} \leq \ifthenelse{\isempty{ \exists s \in \left[\frac{t \Delta_i^2}{ \ln t}, t\right]: \Delta_{s, i^*} \geq \overline{\Delta_{i^*}}}{}}{\mathbb{P}}{\mathbb{P} \left[ \exists s \in \left[\frac{t \Delta_i^2}{ \ln t}, t\right]: \Delta_{s, i^*} \geq \overline{\Delta_{i^*}}\right]}.\]

11.2.0.2 Control of \(\nu_t = \sum_{s = 1}^t \ifthenelse{\isempty{(X_s)^2 | \mathcal{F}_{s-1}}{}}{\mathbb{E}}{\mathbb{E} \left[(X_s)^2 | \mathcal{F}_{s-1}\right]}\)

We start by looking at each individual element of the sum. \[\begin{align} \ifthenelse{\isempty{(X_s)^2 | \mathcal{F}_{s-1}}{}}{\mathbb{E}}{\mathbb{E} \left[(X_s)^2 | \mathcal{F}_{s-1}\right]} & = \ifthenelse{\isempty{(\Delta_i - (\tilde{\ell}_{s, i} - \tilde{\ell}_{s, i^*}))^2 | \mathcal{F}_{s-1}}{}}{\mathbb{E}}{\mathbb{E} \left[(\Delta_i - (\tilde{\ell}_{s, i} - \tilde{\ell}_{s, i^*}))^2 | \mathcal{F}_{s-1}\right]} \\ & \leq \ifthenelse{\isempty{(\tilde{\ell}_{s, i} - \tilde{\ell}_{s, i^*})^2 | \mathcal{F}_{s-1}}{}}{\mathbb{E}}{\mathbb{E} \left[(\tilde{\ell}_{s, i} - \tilde{\ell}_{s, i^*})^2 | \mathcal{F}_{s-1}\right]} \\ & \leq \ifthenelse{\isempty{\tilde{\ell}_{s, i}^2 | \mathcal{F}_{s-1}}{}}{\mathbb{E}}{\mathbb{E} \left[\tilde{\ell}_{s, i}^2 | \mathcal{F}_{s-1}\right]} + \ifthenelse{\isempty{\tilde{\ell}_{s, i^*}^2 | \mathcal{F}_{s-1}}{}}{\mathbb{E}}{\mathbb{E} \left[\tilde{\ell}_{s, i^*}^2 | \mathcal{F}_{s-1}\right]}, \end{align}\] where the last equation holds, because for all non-negative \(a\) and \(b\), we have: \((a - b)^2 \leq a^2 + b^2\).

Then, note that: \[\begin{align} E[\tilde{\ell}_{s, i}^2 | \mathcal{F}_{s-1}] \leq \frac{1}{P_{t, i}}, \end{align}\] so \[\begin{align} \ifthenelse{\isempty{(X_s)^2 | \mathcal{F}_{s-1}}{}}{\mathbb{E}}{\mathbb{E} \left[(X_s)^2 | \mathcal{F}_{s-1}\right]} & \leq \frac{1}{P_{s, i}} + \frac{1}{P_{s, i^*}}. \end{align}\] Using the same argument as before to bound \(\frac{1}{P_{s, i^*}}\) and \(\frac{1}{P_{s, i}}\), we have: \[\begin{align} \ifthenelse{\isempty{ \sum_{s = 1}^t \ifthenelse{\isempty{}{}}{\mathbb{E}}{\mathbb{E} \left[\right]}\left[(X_s)^2 | \mathcal{F}_{s-1}\right] \geq \frac{2 t^2 \Delta_i^2}{ \beta \ln t}}{}}{\mathbb{P}}{\mathbb{P} \left[ \sum_{s = 1}^t \ifthenelse{\isempty{}{}}{\mathbb{E}}{\mathbb{E} \left[\right]}\left[(X_s)^2 | \mathcal{F}_{s-1}\right] \geq \frac{2 t^2 \Delta_i^2}{ \beta \ln t}\right]} \leq \;& \ifthenelse{\isempty{ \exists s \in \left[\frac{t \Delta_i^2}{ \ln t}, t\right]: \Delta_{s, i^*} \geq \overline{\Delta_{i^*}}}{}}{\mathbb{P}}{\mathbb{P} \left[ \exists s \in \left[\frac{t \Delta_i^2}{ \ln t}, t\right]: \Delta_{s, i^*} \geq \overline{\Delta_{i^*}}\right]} \\ & + \ifthenelse{\isempty{ \exists s \in \left[\frac{t \Delta_i^2}{ \ln t}, t\right]: \Delta_{s, i^*} \geq \overline{\Delta_{i^*}}}{}}{\mathbb{P}}{\mathbb{P} \left[ \exists s \in \left[\frac{t \Delta_i^2}{ \ln t}, t\right]: \Delta_{s, i^*} \geq \overline{\Delta_{i^*}}\right]}. \end{align}\]

Noting that the bounds on \(\kappa_t\) and \(\nu_t\) depend on the same events, we deduce that:

\[\begin{align} \ifthenelse{\isempty{ \left(\kappa_t \geq \frac{1.25 t \Delta_i^2}{\beta \ln t}\right) \lor \left(\nu_t \geq \frac{2 t^2 \Delta_i^2}{ \beta \ln t}\right) }{}}{\mathbb{P}}{\mathbb{P} \left[ \left(\kappa_t \geq \frac{1.25 t \Delta_i^2}{\beta \ln t}\right) \lor \left(\nu_t \geq \frac{2 t^2 \Delta_i^2}{ \beta \ln t}\right) \right]} \leq \;& \ifthenelse{\isempty{ \exists s \in \left[\frac{t \Delta_i^2}{ \ln t}, t\right]: \Delta_{s, i} \geq \overline{\Delta_{i}}}{}}{\mathbb{P}}{\mathbb{P} \left[ \exists s \in \left[\frac{t \Delta_i^2}{ \ln t}, t\right]: \Delta_{s, i} \geq \overline{\Delta_{i}}\right]} \\ & + \ifthenelse{\isempty{ \exists s \in \left[\frac{t \Delta_i^2}{ \ln t}, t\right]: \Delta_{s, i^*} \geq \overline{\Delta_{i^*}}}{}}{\mathbb{P}}{\mathbb{P} \left[ \exists s \in \left[\frac{t \Delta_i^2}{ \ln t}, t\right]: \Delta_{s, i^*} \geq \overline{\Delta_{i^*}}\right]} \\ \leq & \frac{1}{t} \frac{\lambda \ln K}{4K^2\beta^2}, \end{align}\] where for the last step we use that for all \(j, k \in V\) and \(\gamma = 4\), \[\begin{align} \ifthenelse{\isempty{ \exists s \in \left[\frac{t \Delta_k^2}{ \ln t}, t\right]: \Delta_{s, j} \geq \overline{\Delta_{j}}}{}}{\mathbb{P}}{\mathbb{P} \left[ \exists s \in \left[\frac{t \Delta_k^2}{ \ln t}, t\right]: \Delta_{s, j} \geq \overline{\Delta_{j}}\right]} & \leq \sum_{s = \frac{t \Delta_k^2}{ \ln t}}^t \ifthenelse{\isempty{ \Delta_{s, j} \geq \overline{\Delta_{j}}}{}}{\mathbb{P}}{\mathbb{P} \left[ \Delta_{s, j} \geq \overline{\Delta_{j}}\right]} \\ & \leq \sum_{s = \frac{t \Delta_k^2}{ \ln t}}^t \frac{1}{s^{3}} \\ & \leq \frac{1}{2} \left(\frac{\ln t}{t\Delta_k^2}\right)^{2} \\ &\leq \frac{1}{t} \frac{\lambda \ln K}{8K^2\beta^2}, \end{align}\] and the last step follows by definition of \(t_{\mathrm{min}}\).

11.2.0.3 Control of \(\tilde{\Delta}_{t, i}\)

We have that: \[\begin{align} \ifthenelse{\isempty{\tilde{\Delta}_{t, i} \leq \frac{1}{2}t\Delta_i}{}}{\mathbb{P}}{\mathbb{P} \left[\tilde{\Delta}_{t, i} \leq \frac{1}{2}t\Delta_i\right]} = \;& \ifthenelse{\isempty{t\Delta_i - \tilde{\Delta}_{t, i} \geq \frac{1}{2}t\Delta_i}{}}{\mathbb{P}}{\mathbb{P} \left[t\Delta_i - \tilde{\Delta}_{t, i} \geq \frac{1}{2}t\Delta_i\right]} \\ \leq \;& \ifthenelse{\isempty{\left(t\Delta_i - \tilde{\Delta}_{t, i} \geq \frac{1}{2}t\Delta_i\right)\land \left(\kappa_t \leq \frac{1.25 t \Delta_i^2}{\beta \ln t}\right) \land \left(\nu_t \leq \frac{4 t^2 \Delta_i^2}{ \beta \ln t}\right)}{}}{\mathbb{P}}{\mathbb{P} \left[\left(t\Delta_i - \tilde{\Delta}_{t, i} \geq \frac{1}{2}t\Delta_i\right)\land \left(\kappa_t \leq \frac{1.25 t \Delta_i^2}{\beta \ln t}\right) \land \left(\nu_t \leq \frac{4 t^2 \Delta_i^2}{ \beta \ln t}\right)\right]} \\ &+ \ifthenelse{\isempty{ \left(\kappa_t \geq \frac{1.25 t \Delta_i^2}{\beta \ln t}\right) \lor \left(\nu_t \geq \frac{2 t^2 \Delta_i^2}{ \beta \ln t}\right) }{}}{\mathbb{P}}{\mathbb{P} \left[ \left(\kappa_t \geq \frac{1.25 t \Delta_i^2}{\beta \ln t}\right) \lor \left(\nu_t \geq \frac{2 t^2 \Delta_i^2}{ \beta \ln t}\right) \right]} \end{align}\]

We set \(\nu = \frac{2 t^2 \Delta_i^2}{ \beta \ln t}\), \(\kappa = \frac{1.25 t \Delta_i^2}{\beta \ln t}\), \(\delta = \frac{1}{Kt}\), and we recall that \(\beta = 320\). Then:

\[\begin{align} \sqrt{2\nu \ln\left(\frac{1}{\delta}\right)} + \frac{\kappa \ln \left(\frac{1}{\delta}\right)}{3} & = \sqrt{2 \frac{2 t^2 \Delta_i^2}{ \beta \ln t}\ln \left(Kt\right)} + \frac{ \frac{1.25 t \Delta_i^2}{\beta \ln t}\ln \left(Kt\right)}{3} \\ & \leq \sqrt{8 \frac{t^2 \Delta_i^2}{ \beta \ln t}\ln \left(t\right)} + \frac{ \frac{1.25 t \Delta_i^2}{\beta \ln {t}}\ln t}{3} \addtocounter{equation}{1}{} \label{proof95bern95KT}\\ & \leq t \Delta_i \left(\frac{2\sqrt{2}}{\sqrt{\beta}} + \frac{2.5}{3 \beta}\right) \\ &\leq \frac{1}{2}t\Delta_i, \end{align}\tag{11}\] where equation 11 is due to \(t \geq t_{\mathrm{min}}(i) \geq K\), so \(\ln \left(Kt\right) \leq 2 \ln t\). We can then use 6 and get: \[\begin{align} \ifthenelse{\isempty{\tilde{\Delta}_{t, i} \leq \frac{1}{2}t\Delta_i}{}}{\mathbb{P}}{\mathbb{P} \left[\tilde{\Delta}_{t, i} \leq \frac{1}{2}t\Delta_i\right]} \leq \frac{1}{t} \frac{\lambda \ln K}{4K^2\beta^2} + \frac{1}{Kt} = \frac{1}{t} \left(\frac{\lambda \ln K}{4K^2\beta^2} + \frac{1}{K}\right). \end{align}\]

Using this bound, summing on \(t\) gives \[\begin{align} \sum_{t = t_{\mathrm{min}}(i)}^T \ifthenelse{\isempty{q_{t, i}}{}}{\mathbb{E}}{\mathbb{E} \left[q_{t, i}\right]} & \leq \sum_{t = t_{\mathrm{min}}(i)}^T \ifthenelse{\isempty{}{}}{\mathbb{E}}{\mathbb{E} \left[\right]}\left[e^{-\frac{1}{2}t\eta_t\Delta_i} \ifthenelse{\isempty{\tilde{\Delta}_{t, i} \geq \frac{1}{2}t\Delta_i}{}}{\mathbb{1}}{\mathbb{1} \left[\tilde{\Delta}_{t, i} \geq \frac{1}{2}t\Delta_i\right]} + \ifthenelse{\isempty{\tilde{\Delta}_{t, i} \leq \frac{1}{2}t\Delta_i}{}}{\mathbb{1}}{\mathbb{1} \left[\tilde{\Delta}_{t, i} \leq \frac{1}{2}t\Delta_i\right]}\right] \\ & \leq \sum_{t = t_{\mathrm{min}}(i)}^T \left(e^{-\frac{1}{2}t\eta_t\Delta_i} + \frac{1}{t} \left(\frac{\lambda \ln K}{4K^2\beta^2} + \frac{1}{K}\right)\right), \end{align}\] which finishes the proof.

11.3 Control over the Exploration↩︎

We now provide a more general version of Proposition 3.

11.4 Proof of Theorem 3↩︎

The proof of Theorem 3 follows from the propositions in this section.

12 Extension to Graphs that Change over Time↩︎

We recall that for this version of the problem, we use \(\varepsilon_t\) given by: \[\varepsilon_{t, i} = \min \left\{\frac{1}{2K}, \frac{1}{2} \sqrt{\frac{\ln K}{tK^2}}, \xi_{t, i}\right\} \qquad \text{ where } \qquad \xi_{t, i} = \begin{cases} ({\beta \ln t})/({t \hat{\Delta}_{t, i}^2}) &\qquad \text{if} \qquad i \in S_t,\\ {4}/{t^2} &\qquad \text{otherwise.} \end{cases}\] and that the learning rate is defined from index \(t \geq K + 1\) by: \[\begin{align} \eta_t = \sqrt{\frac{\ln K}{2\sum_{s = K}^{t-1}\theta_s}}, \quad \text{ where } \theta_t = \sum_{i \in V} \frac{p_{t, i}}{P_{t, i}}. \end{align}\] As the quantities \(p_{t, i}\) are not defined for \(t \geq K\), we set \(\theta_K := K\). This ensures that the learning rate is well defined and non-increasing at all the rounds where we use exponential weights.

To take advantage of the structure of the feedback graph and depend on the independence number of the graphs rather than their strong independence number, we rely on Lemma 5 from[28].

References↩︎