Model selection for contextual bandits

Code

• github.com/akshaykr/oracle_cb
  OfficialIn papernone★ 0

Abstract

We introduce the problem of model selection for contextual bandits, where a learner must adapt to the complexity of the optimal policy while balancing exploration and exploitation. Our main result is a new model selection guarantee for linear contextual bandits. We work in the stochastic realizable setting with a sequence of nested linear policy classes of dimension d_1 < d_2 < , where the m^-th class contains the optimal policy, and we design an algorithm that achieves O(T^2/3d^1/3_m^) regret with no prior knowledge of the optimal dimension d_m^. The algorithm also achieves regret O(T^3/4 + Td_m^), which is optimal for d_m^T. This is the first model selection result for contextual bandits with non-vacuous regret for all values of d_m^, and to the best of our knowledge is the first positive result of this type for any online learning setting with partial information. The core of the algorithm is a new estimator for the gap in the best loss achievable by two linear policy classes, which we show admits a convergence rate faster than the rate required to learn the parameters for either class.

Tasks

Reproductions