Timezone: »

 
Poster
Influence Diagram Bandits: Variational Thompson Sampling for Structured Bandit Problems
Tong Yu · Branislav Kveton · Zheng Wen · Ruiyi Zhang · Ole J. Mengshoel

Tue Jul 14 10:00 AM -- 10:45 AM & Tue Jul 14 10:00 PM -- 10:45 PM (PDT) @
in Poster Session 4 »

We propose a novel framework for structured bandits, which we call an influence diagram bandit. Our framework captures complex statistical dependencies between actions, latent variables, and observations; and thus unifies and extends many existing models, such as combinatorial semi-bandits, cascading bandits, and low-rank bandits. We develop novel online learning algorithms that learn to act efficiently in our models. The key idea is to track a structured posterior distribution of model parameters, either exactly or approximately. To act, we sample model parameters from their posterior and then use the structure of the influence diagram to find the most optimistic action under the sampled parameters. We empirically evaluate our algorithms in three structured bandit problems, and show that they perform as well as or better than problem-specific state-of-the-art baselines.

Keywords: Graphical Models · Online Learning / Bandits · Online Learning, Active Learning, and Bandits

Author Information

Tong Yu (Carnegie Mellon University)
Branislav Kveton (Google Research)
Zheng Wen (DeepMind)
Ruiyi Zhang (Duke University)
Ole J. Mengshoel (Carnegie Mellon University)

More from the Same Authors