Unifying PAC and Regret: Uniform PAC Bounds for Episodic Reinforcement Learning
Statistical performance bounds for reinforcement learning (RL) algorithms can be critical for high-stakes applications like healthcare. This paper introduces a new framework for theoretically measuring the performance of such algorithms called Uniform-PAC, which is a strengthening of the classical Probably Approximately Correct (PAC) framework. In contrast to the PAC framework, the uniform version may be used to derive high probability regret guarantees and so forms a bridge between the two setups that has been missing in the literature. We demonstrate the benefits of the new framework for finite-state episodic MDPs with a new algorithm that is Uniform-PAC and simultaneously achieves optimal regret and PAC guarantees except for a factor of the horizon.
SUMMARY.
This paper considers the setting of finite horizon episodic learning MDPs, and studies the performance of learning algorithms in terms of PAC and regret guarantees.
The paper introduces a novel algorithm called UBEV, together with a finite time regret and PAC analysis.
DETAILED COMMENTS.
I initially thought this would be a very promising article; In the end I am quite disappointed.
A) I find Section 2 a bit spurious. The whole discussion seems to be motivated only by the fact that you make use of a refined concentration inequality based on a peeling argument instead of the crude union bound that is sometimes used in MDP analysis. Further, the UBEV algorithm is nothing but a regret minimization algorithm for undiscounted MDPs, in the spirit of UCRL, KL-UCRL and so on, with the key notable difference that it applies to the episodic setting with fixed horizon H.
I recommend removing this section 2 entirely.
B) Finite Horizon H:
The assumption of an episodic setting with a fixed, known horizon H should really be discussed. 
I find it very misleading that in page 5, several differences are mentioned with other setting but this knowledge of the horizon is not even mentioned.
This vastly simplifying assumption is actually the key element that enables to obtain a simplified analysis. In particular, it naturally gives a known upper bound on the diameter (H) of the MDP, and more importantly it enables the use of Dynamic Programming, as opposed to Value Iteration, for which it is simple to enforce constrained/regularization on the MDP. 
In stark contrast, computing an optimistic value while enforcing constrained on the output value in the context of an infinite horizon is a key challenge;
See algorithms such as UCRL, KL-UCRL or REGAL that consider infinite horizon (they do not resort to DP due to the infinite horizon), plus discussions there-in regarding the difficulty of enforcing constrains on the MDP in practice.
C) Scaling of the regret:
The leading term of the regret in Theorem 4 scales with sqrt{S} but it also scales with H^2 with the horizon. In this context where H upper bounds the diameter D of the MDP, this dependency seems to be loose compared to the regret of other algorithms that scale with D, not D^2. Thus it seems in the analysis you just improve on one factor but loose on another one. Once again, the fact this "detail" is not even discussed is misleading.
D) Concentration inequalities:
The main building block of this paper, apart from the greatly simplifying assumption of having a finite horizon H, is to resort to an improved concentration inequality for the empirical transition distribution, in order to properly handle the random stopping time (number of observations of a state-action pair).
Indeed the naive way to obtain concentration inequalities for the empirical mean reward or transition probability at time t, with N_t(s,a) observations, is to apply a crude union bound on all possible values of N_t(s,a), that is t values, thus creating a factor t in the log terms (log(t\delta)).
However, improved techniques based on a peeling argument  (where the values of N_t(s,a) are localized) leads to better scaling essentially moving from a t term to a log(t) factor, up to loosing some constant factors. Such argument has been used in several analyses of bandit: see e.g. the analysis of KL-UCB by [Cappe et al.], or tools by Aurelien Garivier relating this indeed to the LIL. One can also see a similar type of argument in the PhD of Sebastien Bubeck, or in even earlier papers by Tze Leung Lai. More generally, the peeling technique is largely used is mathematical statistics, and is not novel.
Now, it is an easy exercise to show that the same peeling argument leads to concentration inequalities valid not for a single t, but uniformly over all t (actually for possibly unbounded random stopping time, and thus in particular for the random number of pulls) as well; thus I do not see much novelty either.
Let us go a little more in depth in the statements (e.g. G.1) regarding tightness of the bounds that is provided here, one may first question the use of a peeling with a geometric factor 2, that is arguably the most naive and sub-optimal one, and could be improved (see e.g. analysis of KL-UCB in [Cappe et al.]). Second, at least for sub-Gaussian random variables, one may instead resort to the Laplace method: this method leads to a \sqrt{t} term in the logarithm instead of a \log(t) and thus might be considered sub-optimal. However, the constant factors that we are used when applying the peeling argument, even after optimization of all terms (which is not done here), is still larger than the one we loose with the Laplace method. As a result, the bound resulting from the peeling argument term becomes only tighter than the one resulting from the Laplace method asymptotically for huge values of t (this actually makes sense as the regime of the LIL is also a quite asymptotic regime).
Thus, I feel that the discussion regarding the llnp(t) term is incomplete and misses an important block of the literature, once again.
E) The only possibly interesting part of the paper is Lemma D.1; but as mentioned, being able to enforce the constraints on the MDP is made easy by the fact that a finite horizon is considered. 
F) Minor point: the appendix seems too long for a NIPS paper.
DECISION.
The paper does not enough put in perspective its results with the existing literature, especially regarding the horizon H and the concentration inequalities.
Likewise, the scaling of the regret bounds is not discussed against other results.
These missing points tend to give the feeling that the authors oversell their contribution, and hide the more debatable aspects of their results.
This is also extremely misleading for the less expert readers that may not be able to see the loose aspects of this work.
Perhaps it is just that the paper was just written in a rush, but this is anyway bad practice. 
Points B,C,D should be improved/fixed.
Reject.
FINAL DECISION
I read the authors' rebuttal.
Their answer to point C) (scaling with H) should be included in the paper, as this is an important clarification of their result.
Even though the paper is restricted to the simpler finite horizon setting, I agree that this setting is also relevant and deserves attention.
I still believe that the selling point of the paper should not be section 2 and that much more credit should be given to previous works: indeed each separate idea presented in the paper existed before, so that the paper does not introduce a novel idea; what is novel however, is the combination of these.
We should thus judge how this combination is executed, and I consider this is well done.
Overall, given that the claims and proofs look correct (even though I haven't checked everything in detail), and that the paper is globally well executed, I accept to raise my score in order to meet a consensus.