Influence Diagram Bandits: Variational Thompson Sampling for Structured Bandit Problems

Abstract

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.

References in corpus (9)

• Weight Uncertainty in Neural Networks
• Reinforcement Learning with Deep Energy-Based Policies
• Tight Regret Bounds for Stochastic Combinatorial Semi-Bandits
• Cascading Bandits: Learning to Rank in the Cascade Model
• Efficient Learning in Large-Scale Combinatorial Semi-Bandits
• TopRank: A practical algorithm for online stochastic ranking
• Customized Nonlinear Bandits for Online Response Selection in Neural Conversation Models
• Thompson Sampling with Approximate Inference
• Scalable Thompson Sampling via Optimal Transport