see Appendix.

According to (REF ), \(p_{k,t} > \frac{\xi }{|{\mathbb {D}}_t|}\) , \(\forall k \in {\mathbb {D}}_t\) . In addition, each node \(v_k \in {\mathcal {V}}\)  is in-neighbor to at least one vertex in the dominating set \({\mathbb {D}}_t\) . Therefore, based on (REF ), it can be concluded that \(q_{k,t} > \frac{\xi }{|{\mathbb {D}}_t|}\) , \(\forall k \in [K]\)  and as a result, we have \(\frac{1}{\bar{q}_{k^*,t}} < \frac{|{\mathbb {D}}_t|}{\xi }\) . If the greedy set cover algorithm (see e.g. [1]}) is employed to find a dominating set for the feedback graph \({\mathcal {G}}_t\) , EFL-FG obtains a dominating set with \(|{\mathbb {D}}_t| = {\mathcal {O}}(\alpha ({\mathcal {G}}_t)\ln K)\)  where \(\alpha ({\mathcal {G}}_t)\)  denotes the independence number of the feedback graph \({\mathcal {G}}_t\)  [2]}. In this case, if the server sets \(\eta = {\mathcal {O}}(\sqrt{\frac{\ln K}{T}})\) , \(\xi = {\mathcal {O}}(\frac{(\ln K)^{\frac{3}{4}}}{T^{\frac{1}{4}}})\)  and \(|{\mathbb {C}}_t| = {\mathcal {O}}(1)\)  from (REF ) it can be verified that EFL-FG obtains sub-linear regret of \({\mathcal {O}}(\sum _{t=1}^{T}{(\ln K)^{\frac{3}{4}}\alpha ({\mathcal {G}}_t)T^{-\frac{1}{4}}})\) . It is useful to point out that \(\alpha ({\mathcal {G}}_t)\)  depends on the budget \(B_t\) . Increase in \(B_t\)  can result in more connected feedback graph \({\mathcal {G}}_t\)  and as a result \(\alpha ({\mathcal {G}}_t)\)  decreases. Therefore, larger budget can assist EFL-FG to achieve tighter sub-linear regret bound. For example, when the budget is large enough such that at each learning round \(t\) , the feedback graph \({\mathcal {G}}_t\)  is a densely connected graph as \(\alpha ({\mathcal {G}}_t)={\mathcal {O}}(1)\) . In this case, the EFL-FG can achieve regret of \({\mathcal {O}}((\ln K)^{\frac{3}{4}}T^{\frac{3}{4}})\) . By contrast, when the feedback graph \({\mathcal {G}}_t\)  only includes self-loops, \(\alpha ({\mathcal {G}}_t)=K\)  and as a result the EFL-FG can achieve regret of \({\mathcal {O}}((\ln K)^{\frac{3}{4}}KT^{\frac{3}{4}})\) .
