Timezone: »

 
Poster
Learning on the Edge: Online Learning with Stochastic Feedback Graphs
Emmanuel Esposito · Federico Fusco · Dirk van der Hoeven · Nicolò Cesa-Bianchi

Wed Nov 30 09:00 AM -- 11:00 AM (PST) @ Hall J #828
in Poster Session 3 »
The framework of feedback graphs is a generalization of sequential decision-making with bandit or full information feedback. In this work, we study an extension where the directed feedback graph is stochastic, following a distribution similar to the classical Erdős-Rényi model. Specifically, in each round every edge in the graph is either realized or not with a distinct probability for each edge. We prove nearly optimal regret bounds of order $\min\bigl\{\min_{\varepsilon} \sqrt{(\alpha_\varepsilon/\varepsilon) T},\, \min_{\varepsilon} (\delta_\varepsilon/\varepsilon)^{1/3} T^{2/3}\bigr\}$ (ignoring logarithmic factors), where $\alpha_{\varepsilon}$ and $\delta_{\varepsilon}$ are graph-theoretic quantities measured on the support of the stochastic feedback graph $\mathcal{G}$ with edge probabilities thresholded at $\varepsilon$. Our result, which holds without any preliminary knowledge about $\mathcal{G}$, requires the learner to observe only the realized out-neighborhood of the chosen action. When the learner is allowed to observe the realization of the entire graph (but only the losses in the out-neighborhood of the chosen action), we derive a more efficient algorithm featuring a dependence on weighted versions of the independence and weak domination numbers that exhibits improved bounds for some special cases.
Keywords: Online Learning · bandits · random graphs · feedback graphs
[ Paper]  [ Slides]  [ Poster]  [ OpenReview] 

Author Information

Emmanuel Esposito (Università degli Studi di Milano)
Federico Fusco (Sapienza University of Rome)
Dirk van der Hoeven (Università degli Studi di Milano)
Nicolò Cesa-Bianchi (Università degli Studi di Milano, Italy)

More from the Same Authors