Sample Complexity of Episodic Fixed-Horizon Reinforcement Learning
Recently, there has been significant progress in understanding reinforcement learning in discounted infinite-horizon Markov decision processes (MDPs) by deriving tight sample complexity bounds. However, in many real-world applications, an interactive learning agent operates for a fixed or bounded period of time, for example tutoring students for exams or handling customer service requests. Such scenarios can often be better treated as episodic fixed-horizon MDPs, for which only looser bounds on the sample complexity exist. A natural notion of sample complexity in this setting is the number of episodes required to guarantee a certain performance with high probability (PAC guarantee). In this paper, we derive an upper PAC boundÕ( δ+c ) that match up to log-terms and an additional linear dependency on the number of states |S|. The lower bound is the first of its kind for this setting. Our upper bound leverages Bernstein's inequality to improve on previous bounds for episodic finitehorizon MDPs which have a time-horizon dependency of at least H 3 .
***************************************** SUMMARY ***************************************** Paper: Sample Complexity of Episodic Fixed-Horizon Reinforcement Learning The authors tackle the problem of minimising sample-complexity for episodic fixed-horizon (undiscounted) MDPs. The main contributions are:(a) a new algorithm, inspired by UCRL\gamma for the discounted setting(b) a theoretical analysis showing that the new algorithm enjoys sample-complexity guarantees that scale optimally with the horizon, the accuracy and the confidence. The result is sub-optimal only with respect to the size of the state/space, where it scales potentially quadratically while known lower bounds are linear in the state-space.***************************************** CLARITY *****************************************Overall I found the paper relatively well executed, but it's clear the authors struggled to include as much as possible in the main paper, and the readability suffers as a consequence. I don't know how to feel about this. On the one hand it's better to include proofs in the main body (this is a theory-only paper). On the other hand, as a standalone paper it is still relatively hopeless to verify the correctness of theresults. Anyways, I read enough of the supplementary material to be convinced that the results are correct. ***************************************** QUALITY, ORIGINALITY AND SIGNIFICANCE *****************************************Things I liked:* The setting is quite a bit cleaner than the discounted setting where there are no clear demarcation points to reset the policy* The results are relatively tight. Improving the dependence on the state-space would be nice, of course, but there are many cases where H^3 is larger than |S| and so far there are no algorithms with linear dependence on |S| in this setting (presumably it is not hard to adapt MORMAX, however).* The trick to allow C > 2 in the algorithm. (for me this is the main novelty) By the way, maybe it is worth to look at [2] and see if the Good-Turing trick can (has been?) be used to solve this problem.  Things I disliked:* The proof is following more-or-less exactly as the same cumbersome proof of Lattimore & Hutter, even using the recursive substitution of the higher-moment value estimates. I wish there was a simple proof of this result and I think more time could have been taken to look for one.* The novel contribution is on the low side. The setting is different, but intuitively there is not so much difference between the discounted and episodic settings with the latter usually being a little easier. Of course it is still a lot of work to check this, but many results go through with little modification.* The paper is a bit of a struggle to read. * The algorithm (like UCRL\gamma) is less principled than it could be. Eg., samples are not used as soon as they are obtained, and samples obtained beyond a certain point are simply discarded. I understand these tricks are useful to make the proof work, but my suspicion is that they are going to make the algorithm fairly impractical. I think many of the union bounds can be replaced with uniform bounds as used in [3] (and elsewhere). Perhaps this could be investigated in the future.    Overall I am inclined to accept. I hope the authors will try (hard) to improve the readability to a slightly less specialised audience.  Minor Comments:Line 51: Perhaps mention here (as in the abstract) that the upper and lower bounds do not match on the size of the state-space Line 99: You want to say that if the set of rewards are *not* known, then you can do this transformation Line 151: "as phase" -> "as a phase"? Often: When I see "infinite horizon" I am usually thinking of undiscounted average reward setting, but here you are mostly using it the discounted setting.Line 154: URCL-\gamma -> UCRL-\gamma? Line 223: Did Kakade really exploit the low variance for MDPs? Perhaps you mean the work by Azar [1], which should probably be cited (it is using a generative model and discounting, so different, but still very related) Line 270: "current policy" -> "the current policy" Line 304: This proof sketch is basically impossible to follow without just reading the proof in the appendix. Perhaps better to give a more intuitive sketch like the previous lemma and just refer the reader to the appendix?   [1] On the Sample Complexity of Reinforcement Learning with a Generative Mode. Azar, Munos & Kappen. 2012 [2] PAC Optimal Planning for Invasive Species Management: Improved Exploration for Reinforcement Learning from Simulator-Defined MDPs. Dietterich, Taleghan & Crowley [3] lil'UCB : An Optimal Exploration Algorithm for Multi-Armed Bandits. Jamieson, Malloy Nowak & Bubeck