Influence Diagram Bandits: Variational Thompson Sampling for Structured Bandit Problems
This work addresses the challenge of efficient decision-making in structured bandit problems for researchers and practitioners in machine learning, though it appears incremental as it builds upon and extends existing models.
The authors tackled the problem of structured bandits by proposing a novel framework called influence diagram bandits, which captures complex statistical dependencies and unifies existing models, and they developed online learning algorithms that performed as well as or better than state-of-the-art baselines in empirical evaluations.
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.