Efficient Exploration and Value Function Generalization in Deterministic Systems
We consider the problem of reinforcement learning over episodes of a finitehorizon deterministic system and as a solution propose optimistic constraint propagation (OCP), an algorithm designed to synthesize efficient exploration and value function generalization. We establish that when the true value function Q ⇤ lies within the hypothesis class Q, OCP selects optimal actions over all but at most dim E [Q] episodes, where dim E denotes the eluder dimension. We establish further efficiency and asymptotic performance guarantees that apply even if Q ⇤ does not lie in Q, for the special case where Q is the span of pre-specified indicator functions over disjoint sets.
*Summary* This paper proposes an algorithm for 
      episodic reinforcement learning (RL) in deterministic environments when 
      the learner has a set of possible Q-functions at his disposal. Sample 
      complexity and regret bounds are given that depend on the so-called 
      "eluder dimension" of the function set and are independent of other 
      parameters. The agnostic case is considered as well. *Evaluation* 
      There is a lot to like about this paper. It is original, well-written, 
      and has some nice-looking results. On the other hand, the setting the 
      paper considers is very simple (episodic learning, deterministic 
      environment), and it is questionable whether the results can be 
      generalized to more interesting settings. Further, there are also a few 
      things that I found improvable: - With the exception of the 
      mentioned linear systems with quadratic cost, I found it not very natural 
      to have a set of possible Q-functions at the disposal of the learner. 
      Thus, the results for the "tabula rasa" case and agnostic learning seem to 
      be the more important ones. However, for the tabula rasa case, it seems 
      one does not get anything better than when doing pure exploration until 
      all states have been visited. (I think this deserves to be mentioned.) 
      Concerning agnostic learning, in Theorem 4 there is an unresolved 
      dependence between K and rho, so that it is not clear what can be really 
      accomplished in this case. - It would be good to include at least 
      some proof sketch for the main theorem to give a more detailed idea why 
      the algorithm works. There is enough space for this, even more when the 
      special hypothesis classes are dealt with more concisely. In particular, 
      the lines 282-295 are simply redundant. - Finally, some related 
      work should be mentioned w.r.t. * RL with a set of possible models: 
      See recent work of Marcus Hutter and co-authors, and the paper of Maillard 
      et al at NIPS 2011 and two subsequent papers by the same author and 
      various co-authors at ICML and AISTATS this year. * Deterministic RL: 
      Bernstein & Shimkin, COLT 2008. *Minor comments* - In 
      l.47, I found it not clear what is precisely meant by "model-based 
      algorithms". - In l.82, according to the results near-optimality is 
      not so clear, cf. the remark on the dependence of K and rho in Theorem 4 
      above. The sentence as stated gives the wrong impression that one gets 
      better results with fewer basis functions. - In l.124, I did not see 
      why R^(j) is strictly smaller than V*_0(x_j,0). It seems, it should be 
      \leq instead. - In lines 125 and 139 L is used with different meaning. 
      It would be better to use two different letters instead. - In l.144 
      "more recent experience" assumes that there is some temporal order in the 
      constraints. This should be made clear before. - In l.168 in Algorithm 
      2, it should be made clear that the set C comes from Algorithm 1. - In 
      l.177, \cap should be used for set intersection. - In l.209, 
      "transition" is used as a verb, which I think is not correct. - In 
      l.229, "Q to denote" should be "Q denote". - In l.339, it was not 
      clear to me why the condition in Proposition 1 means that the constraints 
      are "redundant" (and not just consistent). --- Remarks to 
      author's response: - Pure exploration: What I meant is that since 
      the system is deterministic, one could first explore till the whole system 
      is known and then exploit. - Payoff between K and rho: If one 
      chooses a finer discretization (higher K) then the error rho will usually 
      be smaller. Hence there seems to be a payoff between K and rho in Theorem 
      4, and it is not clear what one can expect for an optimal 
      discretization.