Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper studies the RL setting with external / forced termination and defines a new type of MDP, the Termination MDP or TerMDP. The authors propose a theoretically-grounded method which is well suited to this setting and derive regret bounds. They also introduce a scalable approach, TermPG, which combines optimism and a dynamic discount factor incorporating. The method is evaluated on two different domains, including an autonomous driving scenario with human termination data. TermPG is significantly better than vanilla PG and other variants. 

strengths_and_weaknesses: ## Clarity

The paper is generally clear and well-written. 


## Soundness

The introduced setting and method are well-motivated with practical examples, analyzed through a theoretical lens, and thoroughly evaluated on a number of challenging tasks. The authors compare with a number of ablations, demonstrating the importance of each design choice. The proposed approach seems significantly better than naive algorithms in this setting, across many environments. 


## Novelty and Significance

The paper introduces a new type of MDP, the TerMDP, together with a method suited for this setting TermPG, which is novel as far as I know. I particularly liked the optimistic discounting factor part of the algorithm. The paper also introduces a new benchmark and evaluation protocol in a realistic domain for evaluating methods for TerMDP. I also appreciated the fact that the authors ran experiments with human data, rather than merely synthetic data or human proxies (which are typically quite disconnected from reality). It is promising that the results are strong in those cases. While this setting is quite niche / specific and I wouldn't expect a large part of the community to build on this work, I believe it is still important for certain real-world applications and for building systems that won't act in isolation but rather interact with humans, so I hope it will inspire more research in this area. The open sourcing of the code for environments and methods could help advance research in this area, so I encourage authors to make these publicly available.


questions: 1. In the introduction, you mention that the cost function is state-dependant, but in the first equation for the termination probability, it looks like it is a function of state-action pairs. Could you write it as a state-only function? Would this change the formulation, analysis, algorithm, or results?

2. Why did you choose this particular probability as a function of the termination? Could this be modelled in a different way or what are the advantages / disadvantages of this choice?

3. The TerMDP formulation seems to share some similarities with the IRL (inverse RL) paradigm where the agent receives some reward but it is not the full reward (there is uncertainty, some unknown part of the reward which needs to be inferred from the environment -- in this case the termination actions). Could you comment on this?

4. In the related work you mention several relevant areas such as contrained MDPs, reward design, global feedback, or preference-based RL. However, you don't compare your methods with any of those (or some variants adapted to this setting). Could you add such baselines or at least explain why those aren't being considered?

limitations: The paper addresses limitations and potential negative social impacts in the last section. I found this section to have a reasonable amount of detail and nuance. However, it would still be good if the authors can further expand (perhaps in the appendix) on how this approach compares with others, particularly different types of reward shaping, inverse RL methods.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: The paper introduces an extension of the MDP paradigm, to the case where episodes can be interrupted by an external non-Markovian signal.  This has several practical applications for cases with human supervision. The paper includes the formalization of this setting, theoretical properties on provably-efficient learning, and practical algorithm that is evaluated on driving and MinAtar benchmarks.  
strengths_and_weaknesses: (+) The proposed setting is interesting, and I can indeed see many useful applications of this.  As such, this is a significant novel contribution.
(+) The paper is clearly written, and the reader can understand the methodology and contributions.
(+) Several experimental domains are considered, and ablations are performed to clarify impact of different aspects of the model.

(-) The paper makes a very specific assumption about the conditions under which termination happens (based on sum of costs), which seems more out of mathematical convenience than out of real-world motivation. This limitation is clearly stated upfront, and acknowledged in the discussion.
(-) More experiments would be helpful to draw stronger conclusions. Only 5 seeds are used (Fig.5 caption), yet there has been many reports that this is insufficient for high-confidence conclusions in RL (e.g. Henderson et al., AAAI 2018). Why not run 10 seeds? This should be feasible.
(-) The number of terminations needed to learn seem very high.  Can you report how many terminations are observed for each result?  The figures should # steps, so it’s not obvious to know how many terminations were observed.  But #steps is in the 10^6-10^7, which suggestions #terminations would be much higher than is practical for humans to give.  The fact that you had to train a termination for BDr Expt 2 highlights this limitation; it would have been preferable to show results with direct human termination, to be verify whether the proposed work meets the problem as stated.

questions: -	What is “L” in Sec.3, e.g. Thm 1 (l.123)?  This seems an important (cubic) factor in the bound, yet I could not see it defined.
-	How much is the ensemble needed?  This seemed somewhat of a distraction on the proposed method.  Its effect is investigated in the Ablation, and it seems to help. But would it be possible to achieve similar effect without the extra cost of an Ensemble?
-	What metric do you report specifically?  “We report mean and std” (l.214). Is this the std dev or the std error?  I suspect std dev, based on caption of Table 1. I would recommend std error to draw conclusions on significance, and verify whether you ran enough seeds.

limitations: -	The paper provides a reasonable discussion of technical limitations.
-	The paper provides some discussion of societal impact in the final discussion, at a level that is adequate for the potential risks.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: The paper introduces a variant of an episodic MDP where exogenous termination occurs - the episode is terminated by an observer based on some accumulated cost function that is not observed by the agent. Under this new formulation (and some additional assumptions) the paper proposes a solution to the problem, which amounts to estimating these unknown costs from the sparse termination signal, and then incorporating the cost estimation into an RL algorithm optimistically. Theoretical guarantees are provided with respect to the cost estimation, bounds on the regret and the existence of optimal policies in this setting. Results on several domains (requiring deep RL methods) demonstrate that the proposed algorithm outperforms policy gradient baselines when both algorithmic and human termination is applied exogenously. 
strengths_and_weaknesses: 
\+ The paper introduces a useful variant of the standard MDP formalism. I found this well-motivated with several real-world use cases, and I was surprised to see that no one has considered such an extension previously.

\+ The paper provides theoretical guarantees for the algorithm and then extends it to implement a practical policy gradient method that can be used on larger MDPs with all the latest deep RL algorithms. 

\+ On the whole, the paper was extremely well-written (but see below) and well laid out 

\+ At various points, the paper points out limitations or shortcomings, which I appreciated

\- The only section I found difficult to read was Section 3. In particular, the various symbols (such as $\kappa$) encapsulate an awful lot, and it makes it hard to get a sense of how tight the bounds are and how they behave under various conditions (I have some questions in the next section). 

\- Much of the theoretical analysis relies on the particular form of termination assumed. There are also certain other assumptions made where it is not clear if they are done for simplicity or because of some fundamental reason. 

\- A lesser issue, but the experiments, while requiring a neural network for function approximation, are on "smaller" domains - it is thus unclear how the method scales (or whether it can, given the computational overhead) to larger ones. 
questions: While reading the paper, parts of it put me in mind of other formalisms or approaches. While it is not necessary to include these in the paper, I would be curious to hear the authors' thoughts on how their paper links to those and whether there is any connection. I also have a couple of clarifying questions below.

1. The approach to learning the cost function relies on the termination condition being of a specific form. This paper introduces this MDP extension and so it is reasonable for the paper to make any claim about how termination occurs, but I am curious about other forms of termination. For example, if there was just a hard threshold at which point termination occurs, could we use something like RUDDER [1] to do credit assignment on the termination signal (1/0) to estimate the costs in practice?   

2. The MDP formulation here puts me in mind of the average reward SMDP formulation of [2], where the aim is to learn a policy that maximises the infinite-horizon ratio between expected reward and expected cost. Of course, this assumes that the cost function is known, but does cater for the infinite horizon MDP case, which seems more in line with the autonomous driving example. I would be interested if the authors think there is any link here or under what conditions it would be appropriate to use the TerMDP vs AR SMDP formulation.

3. On line 59, the rewards received by the agent are in the range $[0, 1]$, but I could not see why this would be the case. Certainly, I understand that the rewards must be non-negative since termination is "bad", but why should the rewards be bounded? 

4. On the topic of the theoretical bounds, I struggle to get some intuition about the various terms. The constant $L$ bounds the norm of the costs, but there is no bound on the costs themselves. So let's say that, for example, the costs were in the millions (and so was the bias). What would that mean for the bounds? Would things change if everything was scaled accordingly (e.g. costs/bias are 1 vs 1e6). A similar question about $\kappa$ - if the derivative is near 0, then $\kappa$ would be massive. Presumably, this equates to the case where termination happens extremely infrequently (or all the time)? One concern here for me would be what this means in practice - how useful are these bounds for practical purposes if termination happens every so often (ranging from all the time to never)? And how likely is termination to occur in the domains tested?

5. In the results, I notice that a window size twice as large as necessary improves performance. Is this a statistically significant result? If so, why should this be? 

Minor typo: Line 158: rollouts -> rolls out

[1] Arjona-Medina, Jose A., et al. "Rudder: Return decomposition for delayed rewards." Advances in Neural Information Processing Systems 32 (2019).
[2] Ross, Sheldon M. "Average cost semi-Markov decision processes." Journal of Applied Probability 7.3 (1970): 649-656.
limitations: One big positive of the paper was that it was honest about where problematic areas arise (both in the theoretical analysis as well as potential practical deployment). One additional aspect that bears discussing, though, is [3] and related work. In particular, if termination is done from outside the system, then there is no problem. However, you could imagine a case of a real robot being operated by a real human. Since termination is bad, the robot could learn either positive behaviours that mean the human does not wish to terminate it, or it could learn to prevent the human from terminating it (e.g. by preventing the human from pressing a kill-switch), which of course would be a terrible outcome. 

[3] Orseau, Laurent, and Stuart Armstrong. "Safely interruptible agents." Proceedings of the Thirty-Second Conference on Uncertainty in Artificial Intelligence. 2016.
review_title: null

Meta-review: metareview: All reviewers are in agreement that this paper should be accepted. It combines clear writing, a well-motivated setting (external termination due to unobserved accumulation of costs), and sound theoretical analysis with a novel algorithmic contribution (TermPG) that performs well on an interesting domain that aligns well with the stated setting. Furthermore, the additional leveraging of the cost estimation for dynamic discounting may itself be of fairly broad interest to research in RL. Clear Accept, really solid paper.
confidence: Certain
Decision: Accept