  A fundamental challenge for any intelligent system is prediction: given some
inputs, can you predict corresponding outcomes? Most work on supervised
learning has focused on producing accurate marginal predictions for each input.
However, we show that for a broad class of decision problems, accurate joint
predictions are required to deliver good performance. In particular, we
establish several results pertaining to combinatorial decision problems,
sequential predictions, and multi-armed bandits to elucidate the essential role
of joint predictive distributions. Our treatment of multi-armed bandits
introduces an approximate Thompson sampling algorithm and analytic techniques
that lead to a new kind of regret bound.
