We study a multi-armed bandit problem in a setting with covariates available. We take a nonparametric approach to estimate the functional relationship between the response (reward) and the covariates. The estimated relationships and an appropriate randomization are used to select a good arm to play for a greater expected reward. The randomization helps to balance the tendency to trust the currently most promising arm with further exploration of other arms. It is shown that with some familiar nonparametric methods (e.g., histogram), the proposed strategy is strongly consistent in the sense that the accumulated reward is asymptotically equivalent to that based on the best arm (which depends on the covariates) almost surely.