Eluder Dimension and the Sample Complexity of Optimistic Exploration
This paper considers the sample complexity of the multi-armed bandit with dependencies among the arms. Some of the most successful algorithms for this problem use the principle of optimism in the face of uncertainty to guide exploration. The clearest example of this is the class of upper confidence bound (UCB) algorithms, but recent work has shown that a simple posterior sampling algorithm, sometimes called Thompson sampling, can be analyzed in the same manner as optimistic approaches. In this paper, we develop a regret bound that holds for both classes of algorithms. This bound applies broadly and can be specialized to many model classes. It depends on a new notion we refer to as the eluder dimension, which measures the degree of dependence among action rewards. Compared to UCB algorithm regret bounds for specific model classes, our general bound matches the best available for linear models and is stronger than the best available for generalized linear models.
Summary: ******* The paper considers the 
      following general sequential learning problem: a set of actions \cal{A} 
      and a parametric set F of bounded functions mapping actions to the reals 
      are given. At each time step, a subset \cal{A}_t \subset \cal{A} is 
      provided, one has to choose one action A_t in \cal{A}_t, and then gets a 
      reward R_t. The reward is assumed to come from a sub-Gaussian 
      distribution with mean f_\theta(A_t), where f_\theta \in F is a fixed, 
      unknown, function. The authors then introduce in Section 4 the 
      notion of eluder-dimension that is designed to capture how difficult it is 
      to infer the value of one action from previously observed ones. A 
      general regret decomposition is proposed in Section 5, and a specific 
      confidence bounds around a least-squares estimate of f_\theta are 
      proposed in section 6. The main result of the paper bounds the regret 
      of a UCB-like strategy (Proposition 4) and a Thompson-like strategy 
      (Proposition 5) in terms of the eluder-dimension of the hypothesis class 
      F, in a distribution-free way. The eluder-dimension is then bounded in 
      some specific examples including the case of linear and generalized linear 
      bandits. Details: ******* Since the set of 
      available actions change over time, the initially proposed setting 
      corresponds to a sleeping bandit problem. However it is unclear to me 
      what are the assumptions you consider on the sets \cal{A}_t (Standard 
      assumptions are: deterministic, stochastic, oblivious, adaptive). It 
      also seems to me that from section 6, they are actually assumed to be just 
      the set \cal{A}, and especially in section 8 where the main result is 
      clearly stated for a "not-sleeping" bandit case ( \cal{A}_t = \cal{A} 
      for all t). This is actually confusing and it seems actually unclear 
      that the main results hold as well for the general sleeping bandit setting 
      you consider in the introduction (especially for an oblivious or adaptive 
      choice of \cal{A}_t). Thus I suggest for clarity that you align the 
      proposed setting with the main result, that is either you remove the 
      sleeping-bandit assumption entirely, or extend your results and compare 
      them to the standard sleeping-bandit literature as well. I have the 
      feeling the only purpose of this general sleeping-bandit setting is to be 
      able to handle the contextual bandit problem as a special case. 
      Question: what about distribution-dependent bounds scaling 
      with O(\log(T))? Example 2: If the noiseless binary 
      classification setting as detailed line 202-205 indeed provides 
      interesting motivation for introduction of the eluder-dimension, I 
      find on the other hand lines 205 to 212 confusing: Both the VC-dimension 
      and the eluder-dimension are quantities that depend on a set of functions, 
      not on a specific algorithm. Thus I am not sure to see the goal of those 
      lines. Please clarify. Proposition 3: It may be useful to 
      emphasize a little more the result of this proposition, since this is 
      really the key point that enables you to derive the main regret bounds. 
      Other point: In algorithm 1, you use no regularization parameter 
      (that is you use \Phi_t and not for instance \Phi_t + \lambda I). 
      However in the proof (Section D.2) you introduce such lambda, for an 
      upper bound on the max value. It may be useful to clarify if this is 
      only needed in the proof or if the algorithm also needs it. You may also 
      comment on the absence of lambda w.r.t such algorithms as OFUL. Also the 
      assumption that the bound S seems needed but is not reported. Please 
      clarify all these points. Minor comments/typos: Line 224: 
      missing "of. Line 228: mention that the label of a is defined to be 
      f_\theta(a). Line 302: I find the notation using E_t a bit awkward: 
      what is E_t? Lemma 1: It may be useful to recall that eta is the 
      constant from the sub-Gaussian assumptions. Line 518: "The implies". 
      Line 539: Missing “|” before \cal{H}_0 Line 682. Maybe add 
      something like "by definition of dim_E(F,\epsilon)", or "otherwise, it 
      would contradict the definition of d". Line 699: 1 should be 1/T. 
      Line 728: "(f_{\rho_1} - f_{\rho_1})(a_k)" change second \rho_1. 
      Line 735: idem. Line 706-707: To be able to deduce that, you 
      should replace the previous arguments with w_{i_t} \geq \epsilon (instead 
      of >) from line 698. Quality. Good, sound. Clarity. 
      Good, very well written. Originality. Good. Significance. 
      Good.