  We consider the one-armed bandit problem of Woodroofe [J. Amer. Statist.
Assoc. 74 (1979) 799--806], which involves sequential sampling from two
populations: one whose characteristics are known, and one which depends on an
unknown parameter and incorporates a covariate. The goal is to maximize
cumulative expected reward. We study this problem in a minimax setting, and
develop rate-optimal polices that involve suitable modifications of the myopic
rule. It is shown that the regret, as well as the rate of sampling from the
inferior population, can be finite or grow at various rates with the time
horizon of the problem, depending on "local" properties of the covariate
distribution. Proofs rely on martingale methods and information theoretic
arguments.
