User activity data on the Internet tends to be very large, with
hundreds of millions of users performing billions of actions
every day. At the same time, this data is also very sparse, since
each user only performs a very small share of possible actions on
the Internet (eg. searches for a small fraction of possible
keywords, reviews or purchases a small fraction of all products,
etc.). Consequently, if we are doing Bayesian optimization, the number of
experiments allowed is typically far less than the number of
alternatives. We will sketch index-based approximation algorithms
for the budgeted learning problem, which attempts to choose the
best from a set of alternatives given a fixed experimentation
budget. We will then extend this to the discount
oblivious multi-armed bandit problem.