In this talk, we consider finite-horizon (Bayesian)
  multi-armed bandit problems with useful side constraints. We present
  general techniques that yield constant factor polynomial time approximations
  for several bandit problems where no solution with provable performance
  guarantees was known to exist with sub-exponential running time.
  We demonstrate the generality of our techniques by significantly simplifying 
and improving previous results for variants for which such approximations were known.