Multi-Task Learning for Contextual Bandits
Contextual bandits are a form of multi-armed bandit in which the agent has access to predictive side information (known as the context) for each arm at each time step, and have been used to model personalized news recommendation, ad placement, and other applications. In this work, we propose a multi-task learning framework for contextual bandit problems. Like multi-task learning in the batch setting, the goal is to leverage similarities in contexts for different arms so as to improve the agent's ability to predict rewards from contexts. We propose an upper confidence bound-based multi-task learning algorithm for contextual bandits, establish a corresponding regret bound, and interpret this bound to quantify the advantages of learning in the presence of high task (arm) similarity. We also describe an effective scheme for estimating task similarity from data, and demonstrate our algorithm's performance on several data sets.
Summary.
The paper is about contextual bandits with N arms. In each round the learner observes a context x_{ti} for each arm, chooses
an arm to pull and receives reward r_{ti}.
The question is what structure to impose on the rewards. The authors note that
E[r_{ti}] = < x_{ti}, theta > is a common choice, as is 
E[r_{ti}] = < x_{ti}, theta_i >
The former allows for faster learning, but has less capacity while the latter has more capacity and slower learning. The natural question
addressed in this paper concerns the middle ground, which is simultaneously generalized by kernelization.
The main idea is to augment the context space so the learner observes (z_{ti}, x_{ti}) where z_{ti} lies in some other space Z.
Then a kernel can be defined on this augmented space that measures similarity between contexts and determines the degree of sharing
between the arms.
Contribution.
The main contribution as far as I can tell is the idea to augment the context space in this way. The regret analysis
employs the usual techniques.
Novelty. 
There is something new here, but not much. Unless I am somehow mistaken the analysis of Valko et al. should apply directly to the augmented
contexts with more-or-less the same guarantees. So the new idea is really the augmentation.  
Impact.
It's hard to tell what will be the impact of this paper. From a theoretical perspective there is not much new. The practical experiments
are definitely appreciated, but not overwhelming. Eg., what about linear Thompson sampling?   
Correctness. 
I only skimmed the proofs in the supplementary material, but the bound passes plausibility tests.
Overall.
This seems like a borderline paper to me. I would increase my score if the authors can argue convincingly that the theoretical results are really doing
more than the analysis in the cited paper of Valko et al.
Other comments.
- On L186 you remark that under "further assumption that after time t, n_{a,t} = t/N". But this assumption is completely unjustified, so how meaningful
  are conclusions drawn from it?
- It's a pity that the analysis was not possible for Algorithm 1. I presume the sup-"blah blah" algorithms don't really work? It could be useful to 
  show their regret relative to Algorithm 1 in one of the figures. Someone needs to address these issues at some point (but I know this is a tricky problem).
Minors.
- I would capitalize A_t and other random variables.
- L49: "one estimate" -> "one estimates".
- L98: "z_a" -> "z_a \in \mathcal Z".
- L110: The notation t_a as a set that depends on t and a is just odd.
- L114: Why all the primes?
- There must be some noise assumption on the rewards (or bounded, or whatever). Did I miss it?
- L135: augmented context here is also (a, x_a).