We survey the classical multi-armed bandit problem and discuss several variations such as the problem of stochastic search in a forest and the union branching bandit problem. We will discuss structural results, algorithms for finding optimal policies, and highlight some open questions (parts of the talk are based on joint work with John Tsitsiklis (MIT) and Uri Rothblum (Technion)).