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.
our problem of estimating E m,i clearly falls into this general setup if we uniformly explore the actions for n rounds, then set {x s } n s=1 to be the features obtained through the feature map i and {y s } n s=1 to be the observed losses.