We will review the multi-armed bandit problem and its application to optimizing click-through for Web site banners. We will present multi-variate extensions to the basic bandit technology including the use of Gaussian Processes to model relations between different arms. This leads to the consideration of infinitely many arms as well as applications to grammar learning and optimization.