In a multi-armed bandit problem, a decision-maker must choose from a set of alternatives, given only partial knowledge about the past costs or benefits of those alternatives and no knowledge of the future. Studied for more than 30 years, bandit problems constitute the most basic model of the "exploration versus exploitation" tradeoffs inherent in decision-making under uncertainty. A broad range of computing applications require bandit algorithms with a large but structured set of alternatives. Often this structure takes the form of a metric: a distance function expressing the decision-maker's prior knowledge that certain alternatives will have similar payoffs. This talk will focus on two such applictions, one in electronic commerce and the other in web advertising. We will show how both applications can be formulated as special cases of a general problem, the "Lipschitz multi-armed bandit problem." We will then describe an invariant of a metric space which precisely determines the performance of the best possible algorithm for this problem in a given metric, and we will describe an algorithm which meets this bound.