Summary and Contributions: The authors provide a theoretical analysis of Double Q-learning, specifically the asymptotic MSE in the case of linear function approximation. Their analysis suggests a way to select the step size and final output to obtain faster initial convergence while maintaining the same asymptotic result, which they then verify empirically in different experiments. The asymptotic analysis relies on a stochastic approximation result, which they apply in a regime where the policy to select the next step Q evaluation is already optimal (see Eq 4-5). They can then transform the q-learning and Double Q-learning updates in a similar form (eq 10 and 12) which allows the result to apply and the asymptotic MSE to be compared between the approaches. The main concern here is that by assuming that the max action is fixed to being the optimal policy, we are already in a regime where overestimation bias isn't present in Q-learning due to the usual reasons (taking expectation after the max), and so Double Q-learning has little to offer and all to lose (since it has split updates and parameters). The asymptotic analysis doesn't seem like the right way to understand the potential benefits of Double Q-learning in this respect.

There was much discussion regarding the significance of the results and whether these will be relevant to future research. As such, the authors are encouraged to further discuss the technical implications of their result in a revised version, to clarify why it is important, in particular to the deep reinforcement learning setting. Otherwise, there was general consensus that there is something technically novel and sound here.

Overall, the paper made significant contribution to both the reinforcement learning community and optimization community. The proposed algorithm is a variant of non-convex SAGA algorithm introduced by [1]. The novelty comes from their proof for the non-convex but strongly concave case. There are several issues which should be addressed: 1, Recasting the policy evaluation as a primal-dual optimization via the Fenchel duality technique is not new. In fact, [2,3,4] have already exploit this reformulation. First, these related work should be referred appropriately.

Weaknesses: （1） The paper assumes a full-information reward feedback, which can be hardly thought as a realistic assumption. Instead, it would be much appreciated to consider the bandit feedback as what [1] does. This is undesired in practice. There are some recent efforts in removing such dependency [2,3]. The basic idea is to run another meta bandits algorithm for selecting the optimal parameter.

The justification relies on the Bayesian regret bounds to show that hierarchical decomposition can lead to statistically efficient learning by comparing the bounds for the "flat" MDP to the decomposed MDP, and thus deriving the following conditions for beneficial decomposition: either the subMDPs must all have a small state space or the original MDP is able to be decomposed into a small number of equivalent MDPs. The paper then goes on to discuss the computational complexity of planning with hierarchical structures with the Planning with Exit Profiles (PEP) algorithm. The authors derive a bound on the computational complexity of the PEP algorithm, which leads to the following properties being required for efficient learning: all subMDPs must be small, with a small number of exit profiles and total exit states. Finally, the paper also presents a bound on the performance of the PEP algorithm, and discusses the conditions for finding high-quality exit profiles, which is a requirement for the near-optimal performance of PEP.

Quoting from the reviewers: R1: The paper presents a novel framework for analyzing potential efficiencies in reinforcement learning due to hierarchical structure in MDPs. This framework formally defines several useful concepts (subMDPs, equivalent subMDPs, exit states and exit profiles) that allow for an elegant refinement of regret bounds in a well-defined regime. The identification of particular properties (subMDPs, exit state set, and equivalence of subMDPs) provides a clear and useful framework for theoretical analysis of hierarchical reinforcement learning. Overall this paper provides an elegant, concrete framework for formalizing hierarchical structure and quantifying the efficiency such structure may allow. The paper provides a theoretical analysis of hierarchical reinforcement learning, deriving results on learning and planning efficiency when the reinforcement learning problem has repeated structure.

Weaknesses: – Sec 3: You method strongly depends on the'top-terminal fraction'. I see multiple potential problems: 1) what worries me most, is that it only measures optimality. What if my model-based agent adapts very fast to the new domain but reaches just below optimal performance. Then my MBRL method can be very effective, but the LoCA regret will still be very large. Note that the regret at the bottom of P4 cannot correct for this, as it sums all timesteps and multiplies with the success fraction), 3) in more complicated tasks, it can be hard to determine the optimal behaviour, i.e., to even define the'top-terminal fraction'.

This paper proposes a method for identifying model-based behavior in RL agents (the "LoCA regret"), which can be used without knowing anything about the internal structure of the agent itself. This method is demonstrated to correctly distinguish between classical known model-free and model-based agents. It is also used to analyze MuZero, revealing that although MuZero is in principle a model-based algorithm, it does not make optimal use of its model. The reviewers agreed that the LoCA regret is a useful metric, and felt that doing careful evaluation of agents by designing metrics like this is an important area of research in RL. I agree, and found very interesting the demonstration that just because a particular algorithm makes use of a model, doesn't necessarily mean that the algorithm will have the properties that we think of as being associated with model-based algorithms. While there was some debate during the discussion period about some of the choices regarding the calculation of the LoCA regret (e.g.

This analysis provides theoretical insights explaining their empirical success. After author feedback and discussion all reviewers agree that this is a meaningful contribution to the better understanding of existing RL algorithms. This is thus a clear « Accept » decision. That being said, I would like to ask the authors to please add a discussion w.r.t.

Compact search spaces would confer computational benefits if nothing else. Overall, studying how compact representations of the state might might compare when used inside graph search seems like a nice way to evaluate just how much utility is added by the distributional RL component of the overall approach.