  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.
