Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper presents an extension of the options framework to the average-reward formulation in RL. To this end, the key contributions of this paper are: 1) it extends an off-policy control algorithm by Wan, Naik, Sutton’s differential q learning to inter-option differential q learning, 2) presents an incremental sample-based inter-option differential q learning planning algorithm. For 1) they guarantee convergence without requiring a special state, and prove convergence for 2) as well. 3) Next, the work presents intra-option learning and planning algorithms for the average reward formulation including their convergence guarantees. 4) Finally, this work also extends the interruption algorithm from Sutton 1999 to the average reward case. The empirical results support the theoretical claims but could be extended further. 
main_review: **Originality and Significance**:
The work builds upon the foundations laid in Wan, Naik, Sutton (2021) such as Assumption 1, concept of reward rate and the differential value function, etc. Despite that, there are a lot of interesting and important challenges that the work addresses by extending the options framework to the average reward formulation. For instance, the instability incurred due to the large option length and consequently the dependence of the step size on the option length is a key challenge.  
 
The ideas presented in the paper are presented with clarity and technically sound. I appreciate the inclusion of extended discussion in the appendix on the attempts for this which did not work. This gives further insight on the merits of the work.  

Re option models: Can you comment on the comparison to the option multi-time-models both theoretically and empirically? Any insights would be helpful. While the duration component is an explicit additional component as presented here, the MTM captures the full distribution of all possible lengths of the options. What do we gain by explicitly modelling the length of the options? Is the key impact in the scaling component in the TD error (Alg 6, L21-23)? It would be good to expand on this impact in the main paper. 
 

**Empirical Analysis**:  The empirical analysis provided more confidence and understanding of the ideas presented in the work and its impact on the robustness for example. The inter-option differential q learning in Fig 2 and 3 helps in establishing the improvements in robustness of the algorithm proposed towards the hyper-parameters including a comparison to the baseline. However, I have the following concerns and questions:  

* The empirical analysis as it stands seems rather weak. For instance, in Fig 1 we conclude that the results indeed match theorem 1, but potentially a lot more analysis can be done to show the utility of the proposed algorithms.
* Why do we not see the Gosavi’s (2004) algorithm compared in Fig 1 left? 
* I wonder if it would be valuable to compare with the primitive actions differential q learning (Wan, Naik and Sutton, 2021) as a baseline. Especially since the work derives a lot from the aforementioned paper? This could potentially highlight the trade-offs between actions and options in the average reward case.
* As also pointed out by the authors, it would be helpful to provide a stronger empirical analysis in other domains with closely related baselines. For instance, an interesting comparison can be made between the original options framework and the one present in this paper to understand and analyse the trade-off. This analysis might highlight the 
* Additionally, would a baseline such as the average cost TD learning be a suitable candidate to compare with? If not, could you please shed some light on why?
 

**Writing and Presentation**:  
I suggest expanding the introduction specifically to address the motivation for average-reward setting. It is clear that the existing literature has the discounted formulation already, but it is hard for the reader to gauge why the average-setting is important. This is easy to address by rewriting parts of the introduction and the paper.
 
**Miscellaneous**:
 * I was a bit confused in the figures because only the proposed algorithm is shown with little to no comparisons. The sensitivity analysis could be placed side by side perhaps to show the robustness difference.
* It took a while to understand that Fig 3 is the baseline method. Perhaps you might want to make it more explicit. 

limitations_and_societal_impact: Yes, limitations of the work have been discussed in Sec 7. 
I do not see a broader impact statement, I encourage you to write one and add that to the paper.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper extends options framework to average-reward Markov Decision Processes. This paper presents inter-option learning and planning algorithms, and intra-option learning and planning algorithms, as well as provide theoretical analyses that support these algorithms. It also uses an idea of allowing interruption during the option, which allows behaviors with a potentially higher than without interruption - and combine it in its framework. 
main_review: Detailed summary
- The introduction part explains the concept of RL, options framework, SMDP, inter-/intra-option algorithms, etc. I think the intro part was well written, but it would've been a bit better if it contained a brief background explanation about average-reward MDP either in section 1 or in section 2.  
- Inter-option: Q_{n+1}(S_n, O_n) = Q_n(S_n, O_n) + \alpha_n \delta_n / L_n(S_n, O_n), where L approximates the expected length of s-o pairs. L_n is also updated by using another step-size \beta_n. The L_n(s_n, o_n) is different from the sampled option length. 
- I've checked the convergence proofs for inter-options, and didn't find any flaws
- Intra-option: q(s,o) = \sum_{a} \pi(a|s,o) \sum_{s',r} p(s',r|s,a) (r-R + u^q(s',o)). The intra-option differential q-learning and q-evaluation algorithms are suggested. Again, the proof for theorem3 checked. 
- intra-option model learning/planning: should predict the duration of execution of the option. 
- Interruption improves the performance of intra-option models. 

I think this paper is a well-written paper with a combinations of novel, original ideas (average-reward MDP and option framework) and mathematical approach. Although the level of experiments are not extensive, the main idea in this paper has a potential to be extended to more general cases including function approximation. 

I have two questions. 

Q1. General question: I get the idea of combining average-reward MDP and option framework; but other than achieving high reward empirically, is there any motivation or necessity to use average-reward MDP in the setting of option framework?  

Q2. Empirical results in Appendix: the algorithm's sensitivity to hyperparameter \alpha, \beta, \eta varies; in the case of inter-option differential q-learning, the algorithm is not very sensitive to any parameter \alpha, \beta, \eta. In the case of inter-option learning with options O=A, the algorithm was more sensitive to the choice of \alpha; in the case of intra-option algorithms; the choice of \alpha and \eta didn't make much difference. Can you give us an intuition of why this difference happens in different cases?
limitations_and_societal_impact: None
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: This paper extends the Options framework from the discounted MDP setting to the average-reward setting. The authors introduce 4 main contributions: (1) an off-policy inter-option learning algorithm with convergence guarantees; (2) intra-option techniques for learning value functions and models; (3) a method that allows for these ideas to be deployed under sample-based planning algorithms; and (4) an extended definition of interrupting options, adapting its original definition (as proposed for the discounted case) to the average-reward formulation.

main_review: This is a well-written paper that makes an important set of contributions to the area. Average-reward RL has been (comparatively) less studied than the discounted setting, but it is equally important. Being able to extend important key concepts in Hierarchical RL to the average reward formulation is certainly relevant to the community.

Besides being significant, I found the paper to be clear and technically sound. I have a few questions and suggestions:

1) when defining the reward rate of a policy, r^C(mu), what does the "C" superscript stand for? I do  understand the difference between r^C(mu) and r(mu), but was confused about the terminology.

2) regarding Assumption 1: why are all stationary policies in the proposed MDP recurrent? Is this a well-known result? If so, a citation would be helpful. If not: is this statement a claim (that can be proved) or part of the assumption itself?

3) in Equations 1 and 2, \bar{r} was never defined, I believe.

4) in Equation 2, shouldn't it be q*(s,o) instead of q(s,o)?

5) regarding the technique presented in Section 3: my understanding is that the main contribution, here, is the idea of scaling the step-size not by the observed option length, but by an estimate (model) of the option's length. Is that the case? If so, what is the theoretical justification for doing this? Is this meaningful because the option length model \hat{L} encodes the expected length, and using that (the expectation, instead of individual length realizations) decreases the variance of the update rule? A discussion motivating this idea would be helpful.

6) even though the discussion of Equations 6-9 is clear, it was not immediately clear to me how all of these ideas could be combined to construct a planning algorithm. I suggest including high-level pseudo-code, or at least a discussion (in English) about the overall steps involved.

7) regarding the results presented in Figure 2: is the setting of O=A+H faster than the alternatives because options allowed the agent to explore more efficiently, during the early stages of its life? If so, were the options helpful *only* during the initial exploratory phase? One simple way of checking whether options were helpful mostly with exploration, or if they were used by the agent to express optimal policies, is to check whether the final learned policy made use of options or, alternatively, whether it used mostly primitives. A discussion about this would be helpful.

8) still regarding Figure 2, the authors claim the the algorithm's rate of learning varied little over a broad range of parameters. However, it seems like the reward rate can vary from approximately 0.03 up to 0.06. This is twice the reward rate, which is not a little change. I suggest either revisiting this claim or better supporting it.

9) Figure 3 shows the parameter-sensitivity of Gosavi's algorithm. Why did you not include an analysis of its reward rate, like you did in Fig2a when analyzing your proposed algorithm?

10) in Equation 17, where is s' coming from? Perhaps the second summation should be sum_{s', r'} instead of sum_r?

11) in Theorem 6, what is v_mu(s)? This was never defined, I believe

limitations_and_societal_impact: My understanding is that this paper's main contributions are theoretical. The paper does show a few simple experiments, but additional experimental analysis (even for these simple domains) could be made; see, for instance, my comment #9, above. In terms of technical limitations, I believe that the main one is that the paper tackles only the tabular setting, which is usually not of particular interest for real-world applications. The authors, however, do acknowledge this, and propose extending these ideas to the case of linear function approximation as future work.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper extended the learning and planning algorithms and their theoretical properties for options framework in discounted settings MDP settings to average-reward MDPs. The main contributions include three algorithms their convergence property. These algorithms include off-policy inter-option learning and planning, intra-option value learning and planning, intra-option model learning and planning. The convergence property is justified based on the resulted developed for differential Q-learning, an off-policy control algorithm. The paper also extended the notion of option-interrupting behavior from the discounted case to the average-reward formulation and showed it’s efficacy on a continuing version of the 4room domain. Importantly, the intra-option differential Q-learning introduced in this paper can be sued with options having stochastic policies (by using the importance sampling ratio), whereas the original discounted intra-option learning methods were restricted to options with deterministic policies.
main_review: In all the paper is well written and provides some didactic results for options learning and planning in average-reward MDP settings which are complementary to the existing literature on the same topic but mostly for discounted MDP settings.

One issue I have is that many theoretical results seem are directly and trivially extend from some existing work, e.g. Wan et al.’s differential Q learning and Wan et al.’s differential learning and planning algorithms for average-reward MDPs. The paper would be stronger if the difficulties of the theoretical results that are unique to the average-reward settings for options can be highlighted. Another issue is the sufficiency of empirical study. Admittedly the paper is mostly for didactic purpose and the algorithms are developed based on tabular representations. It would be better if more baselines can be compared. i.e,  in figure 4, maybe the authors can include some method from discounted case, but set the discount factor to be large.  Also there is only one domain used for empirical study, it might be stronger if results based on a problem different from 4rooms and described by average reward MDP can be provided.  

limitations_and_societal_impact: The limitations of this work has been discussed in the last section of the paper.
review_title: null

Meta-review: The paper advances the state of the art for average reward hierarchical RL.  The reviewers unanimously recommended acceptance.  The work is theoretically solid and novel.  Well done!
Decision: Accept (Poster)