Sequential Transfer in Multi-armed Bandit with Finite Set of Models INRIA Lille -Nord Europe Team SequeL
Learning from prior tasks and transferring that experience to improve future performance is critical for building lifelong learning agents. Although results in supervised and reinforcement learning show that transfer may significantly improve the learning performance, most of the literature on transfer is focused on batch learning tasks. In this paper we study the problem of sequential transfer in online learning, notably in the multi-armed bandit framework, where the objective is to minimize the total regret over a sequence of tasks by transferring knowledge from prior tasks. We introduce a novel bandit algorithm based on a method-of-moments approach for estimating the possible tasks and derive regret bounds for it.
Summary: This paper studies online transfer learning 
      in multi-armed bandits (MAB), where each instance of MAB encountered 
      belongs to a finite model class. Instead of running single-task MAB 
      algorithm, the paper shows how one can do better through sequential 
      transfer across tasks. The paper first studies a variant of UCB1 (called 
      mUCB): it assumes a set of MAB models is given as input, and improves on 
      UCB1 by restricting the upper confidence bound calculation to the given 
      models. Then, this algorithm is extended to the sequential transfer case 
      (called tUCB), where the set of models is unknown, but has to be 
      discovered by the algorithm. Here, the authors build on recent advances in 
      tensor-based techniques to estimate the set of models. Under certain 
      assumptions, tUCB enjoys lower per-task regret bounds than standard UCB1. 
      Numerical experiments in synthetic problems verify the theoretical 
      findings. * Quality: The problem studied by the paper (online 
      transfer learning in MAB) is new, and the proposed methods are very 
      reasonable. While mUCB is a relatively straightforward variant, its 
      extension to tUCB, where the set of models is unknown, is definitely 
      nontrivial. The theory appears correct. * Clarify: Overall the 
      paper is written clearly, but the notation is very heavy and I wonder if 
      it can be simplified. Also, there are a few places where the presentation 
      can be improved (such as undefined quantities). Please see the detailed 
      comments below. * Originality: The problem formulation is new, to 
      the best of my knowledge. The first new algorithm, mUCB, is a simple 
      variant of UCB1, as mentioned before. But tUCB is sufficiently novel from 
      previous bandit algorithms. While the analysis techniques are mostly based 
      on existing literature (including MAB and the recent tensor-related work), 
      its use of method-of-moment methods in the context of MAB is interesting 
      and first of its kind. * Significant: While the problem is 
      interesting and important, the algorithm/analysis appear somewhat 
      preliminary, for two reasons. One is the pretty strong dependence on the 
      condition number of the second moment matrix M_2. The other is the 
      assumption that the vectors {\mu(\theta)}_\theta are linearly independent. 
      Please see the detailed comments below. Detailed comments: 
      * The finite-sample convergence rate in Thm. 2 may be too loose in 
      practice --- the strong dependence on #arms, #models, and the reciprocal 
      of the smallest eigenvalue can make the bound too loose to be useful. One 
      may wonder if these dependences are necessary, or are due to the non-tight 
      analysis in this work. * A more critical problem that limits the 
      significance of the results is assumption 1, which requires linear 
      independence of {\mu(\theta)}_\theta. Note that this is a set of m vectors 
      of dimension K. To satisfy this assumption, it must be the case that m 
      (number of all possible models) is no larger than K (number of arms). This 
      restriction is both too strong and (I think) unnecessary. * The 
      current algorithms (mUCB and tUCB) are both variants of UCB1, with changes 
      in the calculation of the confidence intervals. As acknowledged in the 
      paper, a much better approach might be to consider the amount of 
      information obtained by pulling an arm --- a suboptimal arm may result in 
      larger regret in the short term but may help identify the current model 
      more quickly. It is possible that, by considering such arms the 
      restrictive assumption 1 is not needed. * Title and in the paper: 
      'multi-arm bandit' should be 'multi-armed bandit' * The sentence 
      in line 62 (starting with 'This') does not seem to parse. * Line 
      76: should X be realization of *arms*, or *reward* of the arms? * 
      Section 2: it seems more nature to swap paragraphs 2 and 3. * Line 
      96: apparently, K is also part of the input to the learner. * Line 
      117: the notation \Theta_+ should probably be \Theta_+(\bar{\theta}) to 
      emphasize its dependence on \bar{\theta}. * Line 189: 3 samples 
      are not enough to *accurately* estimate the moments, but are enough to 
      make the estimates *well-defined*. * Line 211: 'finite sample 
      complexity bounds' -> 'sample complexity bounds'? Sample complexity 
      bounds are by definition about finite samples. * Line 222: 
      \sigma_max = max ..., instead of min...? * Line 222: 
      \lambda(\theta) seems undefined? * Line 224 (assumption 1): why 
      does one need \rho(\theta)>0? If \rho(\theta)=0 for some \theta, then 
      the model is not going to affect the algorithm anyway. * Line 269: 
      what is alpha_0? * Line 279: since \Gamma is defined as the 
      absolute difference, its estimate should probably be: \hat{\Gamma} = 
      max(0, current_definition_in_the_paper). * Line 342: again, should 
      'arms' be 'rewards', in the last sentence of Thm. 4? * Line 419: 
      'rises' -> 'raises'.