{'fraction_non_alphanumeric': 0.04628381880377319, 'fraction_numerical': 0.01902145744791127, 'mean_word_length': 4.065502756629036, 'pattern_counts': {'":': 0, '<': 9, '<?xml version=': 0, '>': 14, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 5, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Online Learning with Uncertain Feedback Graphs

Online learning with expert advice is widely used in various machine learning tasks. It considers the problem where a learner chooses one from a set of experts to take advice and make a decision. In many learning problems, experts may be related, henceforth the learner can observe the losses associated with a subset of experts that are related to the chosen one. In this context, the relationship among experts can be captured by a feedback graph, which can be used to assist the learner's decision making. However, in practice, the nominal feedback graph often entails uncertainties, which renders it impossible to reveal the actual relationship among experts. To cope with this challenge, the present work studies various cases of potential uncertainties, and develops novel online learning algorithms to deal with uncertainties while making use of the uncertain feedback graph. The proposed algorithms are proved to enjoy sublinear regret under mild conditions. Experiments on real datasets are presented to demonstrate the effectiveness of the novel algorithms.


Introduction
In general online learning framework, there exists a learner and a set of experts, where the learner interacts with the experts to make a decision [Cesa-Bianchi and Lugosi, 2006]. At each time instant, the learner chooses one of the experts and it takes the action advised by the chosen expert, then incurs the loss associated with the taken action. Conventional online learning literature mostly focuses on two settings, full information setting [Cesa-Bianchi et al., 1997, Hazan and Megiddo, 2007, Littlestone and Warmuth, 1994, Resler and Mansour, 2019 or bandit setting [Auer et al., 2003, Resler andMansour, 2019]. In the full information setting, at each time instant, the learner can observe the loss associated with all experts. By contrast, in the bandit setting, the learner can only observe the loss associated with the chosen expert. However, in some applications such as the web advertising problem (where a user clicks on an ad and it reveals information about other related ads), the learner can make partial observations of losses associated with a subset of experts. To cope with this scenario, online learning with feedback graphs was first developed by Mannor and Shamir [2011]. In this context, the partial observations of losses are modeled using a directed feedback graph, where each node represents an expert, and there exist an edge from node i to node j, if the learner can observe the loss associated with expert j while choosing expert i. The observations of losses associated with other experts are called learner's side observations. The full information and the bandit settings are both special cases of online learning with either a fully connected feedback graph or a feedback graph with only self loops.
Most of existing works rely on the assumption that the learner knows the feedback graph perfectly before decision making [Alon et al., 2015, 2017, Arora et al., 2019, Cortes et al., 2019, Liu et al., 2018, or after decision making [Alon et al., 2017, Cortes et al., 2020, Kocák et al., 2014, Kocák et al., 2016, Rangi and Franceschetti, 2019. However, such information may not be available in practice. In addition, due to possible uncertainty of the environment, the feedback graph may be uncertain. For instance, consider the web advertising example, where there are two possibly related ads, and the learner wants to choose and advertise one on social media. Certain group of users are interested in both ads, whereas for other users, even if they show interest in one ad, it does not indicate the same interest in the other one. However, it is not known which users will see the ad before advertisement. Therefore, the relation between the two ads is not clear and renders the resulting feedback graph uncertain. As another example, consider an online clothing store that offers discount on an item for new customers. Suppose there are two brands A and B producing similar shirts at comparable price. The store has small and medium sizes of brand A and medium and large sizes shirts of brand B in stock. Assuming that the store offers discount on brand B. If the user accepts the offer, and buys a medium size shirt of brand B, it implies the user is also interested in shirts of brand A. Moreover, if the user buys a large size of shirt B, this indicates no interest in shirts of brand A. Otherwise, if the user declines the offer of brand B, it only shows the user is not interested in shirts of brand B but no information is available about the preference of the user on the shirts of brand A. Considering the case where the exact feedback graph may not be available, Cohen et al. [2016] shows that not knowing the entire feedback graph can make the side observations useless and the learner may simply ignore them. Kocák et al. [2016] studies the case where the exact feedback graph is unknown but is known to be generated from the Erdös-Rényi model. However, such assumption may not be valid in practice. In addition, both Cohen et al. [2016] and Kocák et al. [2016] assume that the loss associated with the chosen expert is guaranteed to be observed.
The present paper extensively studies the case where the learner only has access to a feedback graph that may contain uncertainties, namely nominal feedback graph, and the learner may not be able to observe the loss associated with the chosen expert. The learner relies on this nominal feedback graph to choose among experts, and then incurs a loss associated with the chosen expert. At the same time, it observes the loss associated with a subset of experts resulting from the unknown actual feedback graph. Furthermore, different from Cohen et al. [2016] and Kocák et al. [2016], the present work does not assume it is guaranteed that the learner observes the loss associated with the chosen expert. This is true in some learning tasks, e.g., apple tasting problem [Helmbold et al., 2000], such that the learner may not be aware of how much loss it incurs. In the apple tasting problem, the learner examines apples to identify rotten ones. The learner can either discard the apple or send it to the market. An apple is tasted before it is discarded. The learner incurs an unit loss if a good apple is discarded or a rotten one is sent to the market. However, when the learner sends an apple to the market, it does not taste it. In this case, the learner is not aware of the loss of its decision after sending apples to the market. The present work studies various cases of potential uncertainties, and develops novel online learning algorithms to cope with different uncertainties in the nominal feedback graph. Regret analysis is carried out and it is proved that our novel algorithms can achieve sublinear regret under mild conditions. Experiments on a number of real datasets are presented to showcase the effectiveness of our novel algorithms.

Problem Statement
Consider the case where there exist K experts and the learner chooses to take the advice of one of the experts at each time instant t. Let G t = (V, E t ) represent the directed nominal feedback graph at time t with a set of vertices V, where the vertex v i ∈ V represents the i-th expert, and there exist an edge from v i to v j (i.e. (i, j) ∈ E t ), if the learner observes the loss associated with the j-th expert (i.e. t (v j )) with probability p ij while choosing the i-th expert. Let N in i,t and N out i,t represent in-neighborhood and out-neighborhood of v i in G t , respectively.
The present paper considers non-stochastic adversarial online learning problems. At each time instant t, the environment privately selects a loss function t (.) with t (.) : V → [0, 1], and the nominal feedback graph G t is revealed to the learner before decision making. The learner then chooses one of the experts to take its advice. Then, the learner will incur the loss associated with the chosen expert. Let I t denote the index of the chosen expert. Note that the learner observes t (v It ) with probability of p ItIt , hence the loss remains unknown with the probability of 1 − p ItIt .
The present paper discusses different potential uncertainties in the feedback graphs, and develops novel algorithms for online learning with uncertain feedback graph. Specifically, two cases are discussed: i) online learning with informative probabilistic feedback graph: where the probability p ij associated with each edge is given along with the nominal feedback graph G t ; and ii) online learning with uninformative probabilistic feedback graph: where only the nominal feedback graph G t is revealed, but not the probabilities.

Online Learning with Informative Probabilistic Feedback Graphs
First consider the case where {p ij } are given along with the G t . This can be the case in various applications. For instance, consider a network of agents in a wireless sensor network that cooperate with each other on certain tasks such as environmental monitoring. Online learning algorithms distributed over spatial locations have been employed in climate informatics field [Cesa-Bianchi et al., 2020, McQuade andMonteleoni, 2012]. Assume that each agent in the network keeps updating its local model, and there is a central unit (learner) wishes to perform a learning task based on models and data samples distributed among agents. In this case, the agents in the network can be viewed as experts.
Consider the case where the learner chooses one of the experts and sends a request for the corresponding expert advice through a wireless link. Subset of experts which receive the request, send their advice to the learner. However, due to uncertainty in the environment or power limitation, some of the agents in the network including the chosen one may not detect the request. Therefore, the learner can only observe the advice of subset of agents in the network which detect its request. In this case, the learner can model probable advice that it can receive from experts with a nominal feedback graph. If learner knows the characteristics of the environment which is true in many wireless communication applications, the probabilities associated with edges in the nominal feedback graph is revealed. At each time instant t, upon selecting an expert and observing the losses of a subset of experts, the weights {w i,t } K i=1 which indicate the reliability of experts can be updated as follows (1) where [K] := {1, . . . , K} and η is the learning rate. Functionˆ t (v i ) denotes the importance sampling loss estimate which can be obtained aŝ where S t represent the set of vertices associated with experts whose losses are observed by the learner at time instant t. The indicator function is denoted by I(.) and q i,t is the probability that the loss t (v i ) is observed. Its value depends on the algorithm, and will be specified later. Let A t denote the adjacency matrix of the nominal feedback graph G t with A t (i, j) denoting the (i, j)th entry of A t . Let X ij be a Bernoulli random process with random variables X ij (t) = 1 with probability p ij . When the learner chooses the i-th expert at time t, the learner observes t (v j ) only if v j ∈ N out i,t and X ij (t) = 1. Let F t denote the number of losses observed by the learner. Due to the stochastic nature of the observations available to the learner, F t is a random variable. Furthermore, let F i,t denote the expected number of observed losses if Algorithm 1 Exp3-IP: Online learning with informative probabilistic feedback graph Input:learning rate η > 0. Initialize: w i,1 = 1, ∀i ∈ [K]. for t = 1, . . . , T do Observe G t = (V, E t ) and choose one of the experts according to the PMF π t in (3). (1). end for the learner chooses the i-th expert at time t. Thus, we can write The learner then chooses one expert according to the probability mass function (PMF) π t := (π 1,t , . . . , π K,t ) with where W t := K i=1 w i,t . It can be observed from (3) that η controls the trade-off between exploitation and exploration. With a smaller η, more emphasis is placed on the first term which promotes exploitation, and the learner tends to choose the expert with larger w i,t . The second term allows the learner to select experts in the dominating set D t with certain probability independent of their performance in previous rounds. Based on (3), q i,t in (2) can be computed as The overall algorithm for online learning with uncertain feedback graph in the informative probabilistic setting, termed Exp3-IP, is summarized in Algorithm 1. In order to analyze the performance of Algorithm 1, as well as the ensuing algorithms, we first preset two assumptions needed: the learner can observe the loss associated with the j-th expert with probability at least > 0 when it chooses the i-th expert, and (i, i) ∈ E t , ∀i. Note that (a1) is a general assumption in online learning literature e.g., [Alon et al., 2015]. And (a2) assumes a nonzero probability of observing (but not guaranteed observation of) the loss associated with the chosen expert t (v It ). The following theorem presents the regret bound for Exp3-IP.
Theorem 1. Under (a1), the expected regret of Exp3-IP can be bounded by Proof of Theorem 1 is included in Appendix A. It can be seen from Theorem 1 that the value of π i,t /q i,t plays an important role in regret bound. Building upon Theorem 1, the ensuing Corollary further explores under which circumstances Exp3-IP can achieve sub-linear regret bound.
Lemma 2. Let the doubling trick (see e.g. Alon et al. [2017]) is employed to determine the value of η and greedy set cover algorithm (see e.g. [Chvatal, 1979]) is exploited to derive a dominating set D t for the nominal feedback graph G t . Under (a1) and (a2), the expected regret of Exp3-IP satisfies where α(G t ) denote the independence number of the nominal feedback graph G t .
Proof of Lemma 2 is included in Appendix B. If the learner does not know the time horizon T before start decision making, doubling trick can be exploited to determine η. At time instant t, as long as holds true, Exp3-IP employs learning rate η = ln K 2 r+1 , where r ≥ 0 is the smallest integer that can satisfy the inequality in (7). According to (6), Exp3-IP can achieve sub-linear regret. Furthermore, (6) shows that the regret bound of Exp3-IP depends on 1 . Larger indicates that the learner is less uncertain about the nominal feedback graph. In other words higher confidence of the nominal feedback graph leads to tighter regret bound.

Online Learning with Uninformative Probabilistic Feedback Graphs
The previous section deals with the case where probabilities associated with edges of G t are revealed. In this section, we will study the scenario where the nominal feedback graph G t is static and is revealed to the learner while the probabilities {p ij } associated with edges are not given, which is called uninformative probabilistic feedback graph. In this section the nominal feedback graph is denoted by G = (V, E). In this case, estimates of probabilities {p ij } can be updated and employed to assist the learner with future decision making. For example, consider the problem of online advertisement, where a website is trying to decide which product to be advertised via online survey with a multiple choice question. Specifically, users are asked whether they are interested in certain product along with possible reasons (cost, color, etc). Note that the answer to certain product may also indicate the participant's potential interest in other products with similar cost or color. For instance, if the participant indicates that he or she is interested in the product because of its affordable cost, this implies potential interest in other products with the same or lower price. In this case, the relationship among products can be modeled by a nominal feedback graph, where an edge exists between two nodes (products) if they share same or similar attributes (cost, color), which implies that users may be interested in both products. Such nominal feedback graph can then be used to assist the website to make a decision on which product to advertise . However, the actual relationship between the the user's interests in the products remains uncertain, which leads to uncertainty in the nominal feedback graph. Since attributes (cost, color, etc) of products do not change over time, the nominal feedback graph is static, while the probabilities associated with edges in the nominal feedback graph are unknown. Faced with this practical challenge, two approaches will be developed in this section, to estimate either the unknown probability or the importance sampling loss in (2), which will then be employed to assist the learner's decision making.

Estimation-based Approach
In the present subsection, we will further explore the general scenario where the value of p ij may vary across edges, while the nominal feedback graph G t is static. Since X ij defined under (2) is a mean ergodic random process [Papoulis and Pillai, 2002] in this scenario, the sample mean of {X ij (t)} converges to p ij , i.e., the expected value of X ij (t). Let T ij,t represent a set collecting time instants before t when the learner chooses to take the advice of the i-th expert and there is an edge between v i and v j in the nominal feedback graph G. In other word, T ij,t can be defined as Based on the above discussion, p ij can be estimated aŝ where C ij,t := |T ij,t | is the cardinality of T ij,t . Since X ij is a mean ergodic Bernoulli random process,p ij,t is an unbiased maximum likelihood (ML) estimator of p ij .
Note that a sufficient number of observations of the random process X ij is needed, in order to provide a reliable estimation in (9). To this end, the learner performs exploration in the first KM time instants to ensure that C ij,t ≥ M , ∀(i, j) ∈ E t , where the value of M is determined by the learner. Specifically, in the first KM time instants, the learner chooses all experts in V, one by one M times, i.e. the learner selects expert v k , with k = t − t K K when t ≤ KM . For t > KM , the learner draws one of the experts according to the following PMF where D denotes a dominating set for the nominal feedback graph G. In order to obtain a reliable loss estimate to assist the learner's decision making, we will approximate the importance sampling loss estimate in (2) using the estimated probabilityp ij,t . In this context, the probability of observing t (v i ) can be approximated asq where ξ ≥ 1 is a parameter selected by the learner. Consequently, the importance sampling loss estimates can be obtained as With the estimates in hand, the weights {w i,t } K i=1 can be updated as follows The procedure that the learner chooses among experts when the probabilities are unknown is presented in Algorithm 2, named Exp3-UP. The following theorem establishes the regret bound of Exp3-UP.
with probability at least Algorithm 2 Exp3-UP: Online learning with uninformative probabilistic feedback graphs Select one of the experts according to the PMF π t = (π 1,t , . . . , π K,t ) , with π i,t in (10). (13). end for See proof of Theorem 3 in Appendix C. The following Corollary states conditions under which the regret bound in (14) holds with high probability, i.e., , the proof can be found in Appendix D.
with probability at least 1 − O( 1 T ). Note that according to Algorithm 2 and Corollary 3.1, knowing the value of the time horizon T is required so that the learner can choose the values for M and ξ to achieve the sublinear regret bound in (15), which may not be feasible, and can be resolved by resorting to doubling trick. In this case, if 2 b < t ≤ 2 b+1 where b ∈ N, the learner performs the Exp3-UP with parameters When the learner realizes that the value of M needs to be increased, it then performs exploration to guarantee that at least M samples of the mean ergodic random process X ij are observed. The following lemma shows that when doubling trick is employed, Exp3-UP can achieve sub-linear regret without knowing the time horizon beforehand, the proof of which is in Appendix E.
Lemma 4. Assuming that the doubling trick is employed to determine the value of η, M and ξ at each time instant and the greedy set cover algorithm is utilized to obtain a dominating set D of the nominal feedback graph. If T > K, the regret of Exp3-UP satisfies

Geometric Resampling-based Approach
Another approach to obtain a reliable loss estimate is to employ geometric resampling. Similar to Exp3-UP, if t ≤ KM the learner chooses the k-th expert at time instant t where k = t − t/K K. In this way, it is guaranteed that at least M samples of the mean ergodic random process X ij are observed. Based on these observations, a loss estimate is obtained whose expected value is an approximation of the loss t (v i ), ∀i ∈ [K]. At t > KM , the learner draws one of the experts according to the following PMF where D represents a dominating set for G. Furthermore, at each time instant ij,M denote the last M time instants before t at which the learner observes samples of the random process ij,M ). At each time instant t, the learner draws with replacement M experts according to PMF {π i,t } in (18) in M independent trials. Let d u denote the index of the selected expert at the u-th trial, and P i,1 (t), . . . , P i,M (t) be a sequence of random variables associated for all 1 ≤ u ≤ M . An under-estimate of loss can then be obtained as Algorithm 3 Exp3-GR: Online learning with geometric resampling Select one expert according to PMF π t in (18). (13). end if end for see (116) -(119) in Appendix F for detailed derivation. Then, the weights {w i,t } K i=1 are updated as in (13) using the loss estimate˜ t (v i ) in (20). The geometric resampling based online expert learning framework (Exp3-GR) is summarized in Algorithm 3, and its regret bound is presented in the following theorem.
Theorem 5. Under (a1) and (a2), the expected regret of Exp3-GR is bounded by The proof of Theorem 5 is presented in Appendix F. Building upon Theorem 5, the following Corollary presents the conditions under which Exp3-GR can obtain sub-linear regret.
Corollary 5.1. Assume that greedy set cover algorithm is employed to find a dominating set of the nominal feedback graph G.
Proof of Corollary 5.1 is in Appendix G. Achieving the sub-linear regret in (23) requires that the learner knows the time horizon T , beforehand which may not be possible in some cases. When the learner does not know T , doubling trick can be utilized to achieve sub-linear regret. The following Lemma is proved in Appendix H, shows the regret bound for Exp3-GR when doubling trick is employed to find values of η and M without knowing the time horizon T . In this case, at time instant t, when 2 b < t ≤ 2 b+1 , for η and M the following parameters are chosen for Exp3-GR When the learner realizes that M needs to be increased, it performs exploration to guarantee that at least M samples of the mean ergodic random process X ij are observed.
Lemma 6. Employing doubling trick to select η and M at each time instant, and supposing that a dominating set for the nominal feedback graph G is obtained using greedy set cover algorithm, the expected regret of Exp3-GR satisfies Comparing Lemma 4 with Lemma 6, it can be observed that Exp3-GR achieves a tighter regret bound with probability 1 when the number of experts K is negligible in comparison with horizon T . However, note that choosing an appropriate M for Exp3-GR requires knowing or a lower bound of , which may not be feasible in general, while such information is not required for Exp3-UP in order to guarantee the regret bound in (17). Furthermore, if the number of experts K is large such that K > O(T 1 3 ), Exp3-UP can achieve tighter regret bound compared with that of Exp3-GR. For example, if K = O( √ T ), the regret of Exp3-UP is bounded from above by α(G) ln 5 (T )T 11 12 , which is tighter than the regret bound of Exp3-GR as it is α(G) ln 3 (T )T .
Comparison with Kocák et al. [2016]. Note that while Exp3-GR and Exp3-Res proposed in Kocák et al. [2016] both employ the geometric resampling technique, there exist two major differences: i) Exp3-Res assumes the actual feedback graph is generated from Erdös-Rényi model, and the probabilities of the presence of edges are equal across all edges, while Exp3-GR considers the unequally probable case; and ii) unlike Exp3-Res, Exp3-GR does not assume that the learner is guaranteed to observe the loss associated with the chosen expert. In all experiments, 9 experts are trained using 10% of each dataset. Among them, 8 are trained via kernel ridge regression, with 5 using RBF kernels with bandwidth of 10 −2 , 10 −1 , 1, 10, 100, 3 using Laplacian kernels with bandwidth 10 −2 , 1, 100, and one expert is obtained via linear regression. The nominal graph G t is fully connected. Performance of algorithms are evaluated based on mean square error (MSE) over 20 independent runs, which is defined as whereŷ τ,n and y τ are the prediction of the chosen expert at n-th run and the   Kocák et al. [2016]. Parameter M is set as 25 for both Exp3-UP and Exp3-GR and ξ = 1 for Exp3-UP. All experiments were carried out using Intel(R) Core(TM) i7-10510U CPU @ 1.80 GHz 2.30 GHz processor with a 64-bit Windows operating system.
We first tested the equally probable setting where probabilities p ij = 0.25, ∀i, j. Table 1 lists the MSE performance along with standard deviation of MSE for Air Quality and CCPP datasets. Table 2 shows the MSE performance along with its standard deviation for Twitter and Tom's Hardware datasets. It can be observed that, knowing the exact probability enables Exp3-IP to achieve the best accuracy, and our novel Exp3-UP and Exp3-GR obtain lower MSE than Exp3. Moreover, note that in this case, the actual feedback graph is indeed generated from the Erdös-Rényi model. It turns out that Exp3-Res built upon this assumption obtains larger MSE compared to Exp3-UP and Exp3-GR.
We further tested the unequally probable case, with p ij drawn from uniform distribution U[0.25, 0.5]. Tables 3 and 4 list the MSE of all algorithms along with standard deviation of MSE for Air Quality, CCPP, Twitter and Tom's Hardware datasets, respectively. It can be observed that Exp3-IP obtains the best accuracy. This shows that knowing the probabilities can indeed help obtain better performance. Furthermore, it can be observed that Exp3-UP and Exp3-GR  can achieve lower MSE in comparison with Exp3 which shows the effectiveness of using the information given by the uncertain graph. In addition, lower MSE of Exp3-UP and Exp3-GR compared to Exp3-DOM indicates that considering the uncertain graph G t as a certain graph can degrade MSE. Moreover, it can be observed Exp3-UP and Exp3-GR outperform Exp3-Res when the actual feedback graph is not generated by Erdös-Rényi model. It can be observed Exp3-IP achieves lower MSE than Exp3-GR and Exp3-UP, since the learner has access to the probabilities, while Exp3-UP and Exp3-GR do not rely on such prior information. Figure 1 illustrates the MSE performance of algorithms on Tom's Hardware dataset over time. It can be readily observed that our prposed algorithms converge faster than Exp3-DOM and Exp3-Res which do not consider the uncertainty in the feedback graph.

Conclusion
The present paper studied the problem of online learning with uncertain feedback graphs, where potential uncertainties in the feedback graphs were modeled using probabilistic models. Novel algorithms were developed to exploit information revealed by the nominal feedback graph and different scenarios were discussed. A Proof of Theorem 1 According to (3), we can write Fj,t I(v i ∈ D t ). Substituting (28) into (27) obtains Using the inequality e −x ≤ 1 − x + 1 2 x 2 , ∀x ≥ 0, the following inequality holds Taking logarithm of both sides of (30) and using the fact that 1 + x ≤ e x , we have Summing (31) over time obtains Furthermore, the left hand side of (31) can be bounded from below as where the equality holds due to the fact that W 1 = K j=1 w j,1 = K. Then, (32) and (33) lead to Multiplying both sides of (34) by (1−η) Furthermore, the expected values ofˆ t (v i ) andˆ t (v i ) 2 can be written as where the inequality in (36b) holds because of (a1) which implies t (v i ) ≤ 1.
Taking the expectation of both sides of (35), we arrive at Moreover, using the fact that q i,t ≤ 1 we have Furthermore, since based on (a1) t (v i ) ≤ 1, the second term on the RHS of (37) can be bounded by Combining (38), (39) with (37) we have By definition, the first term on the RHS of (40) equals to E t [ t (v It )]. In addition, note that (40) holds for all v i ∈ V, hence the following inequality holds which completes the proof of Theorem 1.

B Proof of Lemma 2
Based on Theorem 1, the upper bound of the expected regret of Exp3-IP is Let at each time instant t, Q t is defined as Furthermore, let τ r represent the greatest time instant such that τr t=1 Q t ≤ 2 r . According to the doubling trick at time instant τ r−1 +1 where τr−1+1 t=1 Q t > 2 r−1 , the algorithm restarts with Also, the algorithm starts with r = 0. Therefore, based on (42) and (44), it can be concluded that when 2 r−1 < τr t=1 Q t ≤ 2 r . The maximum number of restarts required in this case is log 2 T t=1 Q t . Moreover, it can be written that Therefore, based on (42) and considering the fact that the maximum possible value for incurred loss at each restart is 1, combining (45) with (46) leads to Based on (a2), we can write p ij ≥ > 0 if (i, j) ∈ E t . According to (4) and the fact that the i-th expert is chosen by the learner with probability of π i,t , based on (a2) the inequality q i,t ≥ π i,t holds. Thus, we have Combining (47) with (48) obtains In order to move forward, the following Lemma is exploited [Alon et al., 2017].
Lemma 7. Let G = (V, E) be a directed graph with a set of vertices V and a set of edges E. Let D ⊆ V be a dominating set for G and p 1 , . . . , p K be a probability distribution defined over V, such that where α(G) represents independence number for the graph G.
Based on Lemma 7 and (a2), we get Considering the fact that q i,t ≥ ∀j:j∈N in i,t π j,t which is induced by (a2), from (51), it can be inferred that Furthermore, if greedy set cover algorithm by Chvatal [1979] is employed to obtain the dominating set |D t |, it can be written that [Alon et al., 2017] Therefore, from (52) we can conclude that Combining (49) with (53) and (54), we arrive at which completes the proof of Lemma 2.

C Proof of Theorem 3
In order to prove Theorem 3, let's first consider when t ≤ KM , during which the learner chooses among experts in a deterministic fashion. The (expected) loss incurred can henceforth be written as On the other hand, for any t we have Recall (10), we have Due to the fact e −x ≤ 1 − x + 1 2 x 2 , ∀x ≥ 0, the following inequality holds Taking logarithm and using the fact that 1 + x ≤ e x , we obtain Telescoping (62) from t := KM + 1 to T achieves Moreover, note that ln W T +1 W t can be bounded by Combining (63) with (64) obtains Multiplying both sides of (65) by 1−η η arrives at In addition, the expected value of˜ t (v i ) and˜ t (v i ) 2 at time instant t can be written as Let e ij,t := |p ij,t − p ij |. According to (11), the probability thatq i,t ≥ q i,t is at least ∀j:vj ∈N in E} are independent from each other. Let ε denote ξ/ √ M and µ i,t := 1 qi,t − 1 qi,t , we have where the last inequality holds with probability ∀j:vj ∈N in Pr(e ij,t ≤ ε). Therefore, the following inequalities hold with the probability ∀j:vj ∈N in Taking expectation of both sides of (66) and combining with (69), we obtain the following inequality which holds with probability at least (i,j)∈Et Pr(e ij,t ≤ ε, . . . , e ij,T ≤ ε). Applying the chain rule for one term in the product, we have Pr(e ij,t ≤ ε, . . . , e ij,T ≤ ε) = Pr(e ij,t ≤ ε) T t=t +1 Pr(e ij,t ≤ ε | e ij,t−1 ≤ ε, . . . , e ij,t ≤ ε) Pr(e ij,t ≤ ε).
In order to obtain the lower bound of the probability Pr(e ij,t ≤ ε ij,t ), the Bernstein inequality is employed. To this end consider the following lemma [Yurinskiȋ, 1976].
Let θ ij (t) := X ij (t) − p ij , ∀(i, j) ∈ E t . Since X ij (t) follows Bernoulli distribution with the parameter p ij , it can be readily obtained that E[θ ij (t)] = 0. Furthermore, for the moment generating function of θ ij (t), we have Therefore, the expected value of θ m ij (t), m = 2, 3, . . . can be expressed as From (75), we can conclude that Thus, letting b i = 1 2 , H = 1 in Lemma 8 and combining with (76), the following inequality can be obtained which leads to Therefore, (70) holds with probability at least Since ∀j:vj ∈N in i,t π j,t ≤ 1 and ε = ξ √ M , the following inequality holds Using (80) and the fact that 1 qi,t ≥ 1, (70) can be rewritten as Combining (81) with (57) results in following inequality which holds with probability at least δ ξ and the proof of Theorem 3 is completed.

D Proof of Corollary 3.1
The proof of Corollary 3.1 will be built upon the following Lemma.
Assuming M satisfies Hence, (86) can be re-written as where the second inequality holds since C ij,t ≥ M . Let t = KM + 1. Note that the regret bound in (14) holds with probability at least δ ξ in (79). According to Lemma 9, we can obtain the following inequality Combining (87) with (88) obtains where |E| denotes the cardinality of the E. Since G does not change over time, |E| is a constant. According to (89), it can be readily obtained that when (86) holds, the regret bound in (14) holds with probability at least of order 1 − O( 1 T ). Consider the case where the learner sets η, M and ξ as follows Putting η, M and ξ in (90) into (14) and based on Lemma 7, it can be concluded that the expected regret of Exp3-UP satisfies with probability at least 1 − O( 1 T ).

E Proof of Lemma 4
In this section, doubling trick technique is employed such that Exp3-UP can achieve sub-linear regret. If 2 b < t ≤ 2 b+1 , the value of the learning rate η b , M b and ξ b are When the learner realizes that t > 2 b+1 , the algorithm restarts with η b+1 , M b+1 and ξ b+1 . The algorithm starts with b = log 2 K . Therefore, when t < 2 log 2 K , the value of η b , M b and ξ b are set with respect to b = log 2 K . Let M i denotes a set which includes the time instants when the learner chooses the i-th expert in a deterministic fashion for exploration. Specifically, when at time instant τ , the learner chooses the i-th expert for exploration without using the PMF in (10), the time instant τ is appended to M i . At each restart the learner chooses the experts one by one for the exploration until the condition is satisfied. Then, the learner chooses between experts according to PMF in (10) using the learning rate η b . Therefore, based on Theorem 3, for each b, the algorithm satisfies with probability at least δ b where it can be expressed as where T b denote the greatest time instant which satisfies 2 b < T b ≤ 2 b+1 and t b can be written as Note that M b−1 = 0 when b = log 2 K . Since for each b, M b and ξ b in (92) meet the following condition it can be concluded that the following inequality holds true and as a result according to Lemma 9 we can write Combining (97) with (98), it can be concluded that Therefore, for each b from (93), (99) and Lemma 7 it can be inferred that holds with probability at least 1 − O( 1 T b ). Summing (100) over all possible values of b, from b := log 2 K to log 2 T and taking into account that the maximum value of the loss at each restart is 1, we arrive at which holds with probability at least When b = log 2 K , we have T b ≥ 2K. Furthermore, when log 2 K < b ≤ log 2 T , it can be concluded that T b = 2T b−1 . Therefore, we can write Hence, based on (103) and under the assumption that T > K, we find Thus, ∆ meet the conditions in the Lemma 9 and it can be inferred that Therefore, in this case, Exp3-UP satisfies with probability at least 1 − O( 1 K ). This completes the proof of Lemma 4.

F Proof of Theorem 5
Since Exp3-GR chooses the experts one by one for the exploration at the first KM time instants, (56) and (57) hold true for Exp3-GR. In addition, for t > KM we have According to (18), wi,t Wt can be expressed as Therefore, (108) can be rewritten as Furthermore, using the inequality e −x ≤ 1 − x + 1 2 x 2 , ∀x ≥ 0, we have Considering the inequality 1 + x ≤ e x and taking logarithm from both sides of (110), we obtain Summing (111) over t from t = KM + 1 to T , it can be written that In addition, ln W T +1 W t can be bounded from below as Combining (113) with (112), we find Multiplying both sides of (114) by 1−η η as According to (20), expected value of loss estimate˜ t (v i ) can be expressed as Note that the expected values depend on random variable {Z i,u (t)} M u=1 in (19), where P i,u (t) and Y ij,u (t), ∀i ∈ [K], ∀(i, j) ∈ E t are independent Bernoulli random variables with parameters π i,t and p ij , respectively. Therefore, {Z i,u (t)} M u=1 are also Bernoulli random variables with expected value In other words, Z i,u (t) is a Bernoulli random variable whose value is 1 with probability q i,t . The expected value of Q i,t and Q 2 i,t can henceforth be written as 2 b < t ≤ 2 b+1 , for η b and M b the following values are chosen When t > 2 b+1 holds true, the algorithm restarts with η b+1 and M b+1 . The algorithm starts with b = 0. At each restart, the algorithm chooses the experts one by one for exploration until the condition that each expert is chosen at least M b times is met. Then, the learner uses the last M b observed samples from each expert to perform geometric resampling. In this case, for each b, Exp3-GR satisfies where T b denote the greatest time instant which satisfies 2 b < T b ≤ 2 b+1 and t b can be expressed as in (95). Note that when b = 0, we have M b−1 = 0. Taking into account that the maximum loss at each restart is 1, summing (131) over all possible values for b obtains where M is the number of samples for each expert when b = log 2 T which are used for geometric resampling during the learning task. According to (130b) and based on the fact that D is obtained using the greedy set cover algorithm, it can be written that Furthermore, for each b, the inequality q i,t > η b |D| holds. Therefore, according to (130), we can write M b q i,t > b+1 2 ln 2. Thus, it can be concluded that Using (134), we obtain In addition, based on the Lemma 7, it can be written that Therefore, combining (132) with (133), (135) and (136), it can be inferred that Exp3-GR satisfies