Timezone: »

 
Poster
Online Learning with Dependent Stochastic Feedback Graphs
Corinna Cortes · Giulia DeSalvo · Claudio Gentile · Mehryar Mohri · Ningshan Zhang

Thu Jul 16 06:00 AM -- 06:45 AM & Thu Jul 16 05:00 PM -- 05:45 PM (PDT) @
in Poster Session 41 »

A general framework for online learning with partial information is one where feedback graphs specify which losses can be observed by the learner. We study a challenging scenario where feedback graphs vary stochastically with time and, more importantly, where graphs and losses are dependent. This scenario appears in several real-world applications that we describe where the outcome of actions are correlated. We devise a new algorithm for this setting that exploits the stochastic properties of the graphs and that benefits from favorable regret guarantees. We present a detailed theoretical analysis of this algorithm, and also report the result of a series of experiments on real-world datasets, which show that our algorithm outperforms standard baselines for online learning with feedback graphs.

Keywords: Online Learning / Bandits · Other · Online Learning, Active Learning, and Bandits

Author Information

Corinna Cortes (Google Research)
Giulia DeSalvo (Google Research)
Claudio Gentile (Google Research)
Mehryar Mohri (Google Research and Courant Institute of Mathematical Sciences)
Ningshan Zhang (Hudson River Trading)

More from the Same Authors