Regret Minimization in MDPs with Options without Prior Knowledge
The option framework integrates temporal abstraction into the reinforcement learning model through the introduction of macro-actions (i.e., options). Recent works leveraged the mapping of Markov decision processes (MDPs) with options to semi-MDPs (SMDPs) and introduced SMDP-versions of exploration-exploitation algorithms (e.g., RMAX-SMDP and UCRL-SMDP)  to analyze the impact of options on the learning performance. Nonetheless, the PAC-SMDP sample complexity of RMAX-SMDP can hardly be translated into equivalent PAC-MDP theoretical guarantees, while the regret analysis of UCRL-SMDP requires prior knowledge of the distributions of the cumulative reward and duration of each option, which are hardly available in practice. In this paper, we remove this limitation by combining the SMDP view together with the inner Markov structure of options into a novel algorithm whose regret performance matches UCRL-SMDP's up to an additive regret term. We show scenarios where this term is negligible and the advantage of temporal abstraction is preserved. We also report preliminary empirical results supporting the theoretical findings.
Overview:
The authors attempt to improve current regret estimation for HRL methods using options. In particular they attempt to do so in the absence of a distribution of cumulative rewards and of option durations, which is a requirement of previous methods (UCRL and SUCRL). 
After assuming that options are well defined, the authors proceed to transform the inner MDP of options, represented by a transition matrix Po, into an equivalent irreducible Markov chain with matrix P'o. This is done by merging the terminal states to the initial state. 
By doing so, and assuming that any state with a termination probability lower than one can be reached, the stationary distribution mu_o of the chain is obtainable; which in turn is utilized to estimate the optimistic reward gain. With respect to previous methods, this formulation is more robust to ill-defined estimates of the parameters, and better accounts for the correlation between cumulative reward and duration. This method is coined as FSUCRL. 
The algorithm is complemented by estimating confidence intervals for the reward r, for the SMDP transition probabilities, and for the inner Markov Chain P'o. Two versions of this same algorithm, FUSCRL Lvl1 and Lvl2, are proposed. The first version requires directly computing an approximated distribution mu_o from the estimate of P'o. The second version nests two empirical value iterations to obtain the optimal bias. 
The paper concludes with a theoretical analysis and a numerical application of FSUCLR. On a theoretical ground, FSUCRL Lvl2 is compared to SUCRL. The authors argue that the goodness of the bound on the regret predicted by FSUCRL Lvl2 compared to that of SUCRL depends various factors, including the length of the options and the accessibility of states within the option itself, and provide conditions where FSUCRL Lvl2 is likely to perform better than SUCRL. 
As an indication, 4 algorithms, UCRL, SUCRL, FSUCRL Lvl1 and FSUCRL Lvl 2 are tested on a gridworld taken from ref. 9, where the maximum duration of the options is assumed known. Result confirm the theoretical expectations previously discussed: FSUCRL Lvl2 performs better of both SUCRL and FSUCRL Lvl1, partially due to the fact that the options' actions overlap.  
Evaluation:
- Quality: The paper appears to be theoretically sound and the problem discussion is complete. The authors discuss in depth strength and weaknesses of their approach with respect to the previous SUCRL. The provided numerical simulation is not conclusive but supports the above considerations;
- Clarity: the paper could be clearer but is sufficiently clear. The authors provide an example and a theoretical discussion which help understanding the mathematical framework;
-  Originality: the work seems to be sufficiently original with respect to its predecessor (SUCRL) and with respect to other published works in NIPS;
- Significance: the motivation of the paper is clear and relevant since it addresses a significant limitation of previous methods;
Other comments:
- Line 140: here the first column of Qo is replaced by vo to form P'o, so that the first state is not reachable anymore but from a terminating state. I assume that either Ass.1 (finite length of an option) or Ass. 2 (the starting state is a terminal state) clarify this choice. In the event this is the case, the authors should mention the connection between the two;
- Line 283: "four" -> "for";
- Line 284: "where" s-> "were";