Nonparametric Estimation in a Bandit Problem with Covariates

• Activity Number: 685
• Type: Contributed
• Date/Time: Thursday, August 8, 2013 : 10:30 AM to 12:20 PM
• Sponsor: Section on Nonparametric Statistics
• Author(s): Wei Qian*+ and Yuhong Yang
• Companies: University of Minnesota and University of Minnesota
• Keywords: regret bound ; nonparametric bandit ; MABC ; exploration-exploitation tradeoff ; contextual bandit problem

Abstract

Bandit problem is an optimization game that requires the balance between exploration and exploitation to maximize the total reward. Motivated by important applications in web-based services and clinical research, we consider a problem setting where the mean reward of each arm can be dependent on some covariates. Based on a sequential randomized allocation strategy, we perform the finite-time regret analysis and provide the cumulative regret upper bound for nonparametric reward estimation methods. Simulations and a real data evaluation are conducted to illustrate the performance of the proposed allocation strategy.