Reinforcement Learning with a Terminator
Authors: Guy Tennenholtz
Nadav Merlis
Lior Shani
Shie Mannor
Uri Shalit
Gal Chechik
Assaf Hallak
Gal Dalal
Venue: NeurIPS 2022 Accept (2022)
Keywords: reinforcement learning
termination

Abstract: We present the problem of reinforcement learning with exogenous termination. We define the Termination Markov Decision Process (TerMDP), an extension of the MDP framework, in which episodes may be interrupted by an external non-Markovian observer. This formulation accounts for numerous real-world situations, such as a human interrupting an autonomous driving agent for reasons of discomfort. We learn the parameters of the TerMDP and leverage the structure of the estimation problem to provide state-wise confidence bounds. We use these to construct a provably-efficient algorithm, which accounts for termination, and bound its regret. Motivated by our theoretical analysis, we design and implement a scalable approach, which combines optimism (w.r.t. termination) and a dynamic discount factor, incorporating the termination probability. We deploy our method on high-dimensional driving and MinAtar benchmarks. Additionally, we test our approach on human data in a driving setting. Our results demonstrate fast convergence and significant improvement over various baseline approaches.

Reinforcement Learning with a Terminator
Guy Tennenholtz "F guytenn@gmail.cmm com
Nadav Merlis
Lior Shani
Shie Mannor
Uri Shalit
Gal Chechik 1-
Assaf Hallak
Gal Dalal
Abstract
We present the problem of reinforcement learning with exogenous termination. We define Termination Markov Decision Process (TerMDP), an extension of the MDP framework, in which episodes may be interrupted by external non-Markovian observer. This formulation accounts for numerous real-world situations, such as a human interrupting autonomous driving agent for reasons of discomfort. We learn the parameters of the TerMDP and leverage the structure of the estimation problem provide state-wise confidence bounds. We use these to construct a provably-effciiet algorithm, which accounts for termination, and bound its regret. Motivated by our theoretical analysis, we design and implement a scalable approach, which combines optimism (w.r.t. termination) and a dynamic discount factor, incorporating the termination probability. We deploy our method on high-dimensional driving and MinAtar benchmarks. Additionally, we test our approach on human data driving setting. Our results demonstrate fast convergence and significant improvement over various baseline approaches.
Introduction
The field reinforcement learning (RL) involves an agent interacting with environment, max- imizing a cumulative reward [Puterman 2014]. As RL becomes more instrumental in real-world applications [Lazic al., 2018 Kiran al. [021]] Mandhane al. [022]. exogenous inputs beyond the prespecified reward pose new challenge. Particularly, an external authority (e.g., human operator) may decide to terminate the agent's operation when detects undesirable behavior. this work, we generalize the basic RL framework to accommodate such external feedback.
We propose generalization of the standard Markov Decision Process (MDP), in which external termination can occur due to a non-Markovian observer. When terminated, the agent stops interacting with the environment and cannot collect additional rewards. This setup describes various real- world scenarios, including: passengers in autonomous vehicles (Le Vine et al. 2015 Zhu et al., 2020). users in recommender systems [Wang al. 2009 employees terminating their contracts (churn management) (Sisodia et al. [2017]. and operators in factories; particularly, datacenter cooling systems, or other safety-critical systems, which require constant monitoring and rare, though critical, human takeovers [Modares et al. 2015). In these tasks, human preferences, incentives, and constraints play a central role, and designing reward function to capture them may highly complex. Instead, we propose to let the agent itself learn these latent human utilities by leveraging the termination events.
We introduce the Termination Markov Decision Process (TerMDP), depicted in Figure [ We consider a terminator, observing the agent, which aggregates penalties w.r.t. predetermined, state-action- dependent, yet unknown,
function. As the agent progresses, unfavorable states accumulate costs
"Technion, Israel institute of technology
I Nvidia Research, Isracl
Baar llnn University, Israel
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

8%; 4
Terminator
Environment
(du; 0o), ($1, ai), (sk-1, a3-1)
no
yes
Agent
continue learning
termination decision
agent
Figure 1: A block diagram of the TerMDP framework. An agent interacts with an environment while an exogenous observer (i.e., terminator) can choose terminate the agent based on previous interactions. If the agent terminated, it transitions sink state where reward of 0 given until the end of the episode.
that gradually increase the terminator's inclination to stop the agent and end the current episode. Receiving merely the sparse termination signals, the agent must learn to behave in the environment, adhering to the terminator's 's preferences while maximizing reward.
Our contributions
follows. (1) We introduce novel history diseene-de termination model, natural extension the MDP framework which incorporates non- con-trivial termination (Section 2 (2)
We learn the unknown costs from the implicit termination feedback (Section B), and provide local guarantees w.r.t. every visited state. We leverage our results to construct tractable algorithm and provide regret guarantees. (3) Building upon theoretical results, devise a practical approach that combines optimism with a cost-dependent discount factor, which we test on MinAtar (Young (4) We demonstrate the efficiency of method on these benchmarks as well as on human-collected termination data (Section 5). Our results show significant improvement over other candidate solutions, which involve direct termination penalties and bistory-dependent approaches. We also introduce a new task for RL - a driving simulation game which can be easily deployed on mobile phones, consoles, and PC
and Tian 2019] and new driving benchmark.
2 Termination Markov Decision Process
We begin by presenting the termination framework and the notation used throughout the paper. Informally, we model the termination problem using logistic model of past "bad behaviors" We an unobserved nate-action-deeendde cost function to capture these external preferences. As the overall cost increases throughout time, so does the probability termination.
For positive integer we denote [n] fl..... n.. We define the Termination Markov Decision Process (TerMDP) by the tuple My (S. A. P. R, H, c), where S and A are state and action spaces with cardinality S and A, respectively, and И E N is the maximal horizon. We consider the following protocol, which proceeds in discrete episodes i 1,2, ..... K. At the beginning of each episode an agent is initialized at state xt S. At every time step h of episode kt, the agent is at state s E S, takes an action af, A and receives a random reward F.J. j0, 1] generated from fixed distribution with mean r (s ). A terminator overseeing the agent utilizes a cost function e [H] x S x A + R that is unobserved and unknown the agent. time step h, the episode terminates with probability
(c) = Σ ci(s), )
where p(x:) (1 exp(-2))-1 the logistic function and R is a bias term which determines the termination probability when no costs are aggregated. Upon termination, the agent transitions terminal state Stem which yields no reward, i.c., Th (Stemm a) for all [M] A. If no termination occurs, the agent transitions
next state sh+1 with probability Pr |s af)) Let be the time step when the 1tth episode was terminated. Notice that
t min h st = Stemm the termination probability is non-Markovian, as it depends on the entire trajectory history. We also
'Code for Backseat Driver and method, TermPG, be found htthgp//gghhub..cmmmeeye///eaaaa

---

note that, when c O, the TeMMD reduces to finite horizon MDP with discount factor y = p(-b). Finally, we note that our model allows for negative costs. Indeed, these may capture satisfactory behavior, diminishing the effect of previous mistakes, and decreasing the probability of termination.
We define stochastic, history dependent policy TA (Sh; Ti:h) which maps trajectories Tish ($1, (81,a1,.... ,i....,,,,h. 9 44-1) up to time step (excluding) and the 1tth states to probability distributions
over A. Its value is defined by (s) = E>'>> T oz) Sh = S, T1sh = T, ag ~ Te( (1.))
With slight abuse of notation, we denote the value at the initial time step by Vi (s). An optimal policy x² maximizes the value for all states and histories simultaneously we denote its value function by V*. We measure the performance of an agent by its regret; namely, the difference between the cumulative value it achieves and the value of optimal policy,
Reg(K) Σ (s V/ (s7).
Notations. We denote the Euclidean norm by Il-lla and the Mahalanobis norm induced by the positive definite matrix A 0 by ||=|| vx Ax. We denote by n (s. a) the number of times that a state action pair (s. was visited at the hthh time step before the 1thh episode. Similarly, we denote by (s, a) the empirical average a random variable X (c.g., reward and transition kernel) (s, a) in the 1thh time step, based on all samples before the hhth episode.
We assume there exists a known constant L that bounds the norm of the costs; namely, VI., E' (3( S L, and denote the set of possible costs by C. We also denote the maximal reciprocal derivative of the logistic function by K [ax max ((rra)))) (p(E"= ((=t,c((s;; - -b) This factor will be evident in our theoretical analysis in the next section, as estimating the costs in regions of saturation of the sigmoid more difficult when the derivative nears zero. Finally, we use (xx) to refer to a quantity that depends on x up poly-log expression in S, A, K, H, L, K and log( (
3 An Optimistic Approach to Overcoming Termination
Unlike the standard MDP setup, in the TerMDP model, the agent can potentially be terminated at any time step. Consider the TerMDP model for which the costs known. We can define a Markov policy na mapping augmented states S x R to a probability distribution over actions, where here, the state space is augmented by the accumulated costs Σ'=1 (e($t,at). There exists a policy, which does not use historical information, besides the accumulated costs, and achieves the value of the optimal history-dependent policy (see Appendix [ Therefore, when solving for an optimal policy (e.g., by planning), one can use the current accumulated cost instead the full trajectory history.
This suggests plausible approach for solving the TerMDP - first learn the cost function, and then solve the state-augmented MDP for which the costs are known. This, in turn, leads to the following question: can we learn the costs from the termination signals? In what follows, we answer this question affirmatively. We show that by using the termination structure, one can efficiently converge to the true cost function locally- for every state and action. We provide uncertainty estimates for the state-wise costs, which allow us to construct an efficient optimistic algorithm for solving the problem.
Learning the Costs. To learn the costs, we show that the agent can effectively gain information about costs even in time steps where termination occurs. Recall that at any time step h [H 1], the agent acquires a sample from a Bernoulli random variable with parameter
P (c) ( a - b). Notably, a lack of termination, which occurs with probability 1 - 1 (c). also an informative signal of the unknown costs. We propose leverage this information by recognizing the costs e as parameters of a probabilistic model, maximizing their likelihood. We use
SSuch policy always exists; we can always augment the state space with the history, which would make the environment Markovian and imply the existence of an optimal deeendet policy [Puterman 2014).
3

---

Algorithm TermCRL: Termination Confidence Reinforcement Learning
1: require: À 0
2: for k= l.......
K do
3: for (h, s,a) E [H] x S A do
4:
(s, (s, a) + (h, 8,0) (h,
5: (s, (5 a) - (h,
// Appendix
6: end for
7: n² TerMDP [ (S,(S,, AS H. H pk 24)
// Appendix
8: Rollout trajectory by acting n
9: ck+1 arg max.ec (c)
// Equation
10: Update pk+ a), (8, a), n ( a) over rollout trajectory
11: end for
the regularized cross-entropy, defined for some À >> 0 by
Σ H-1
Cx(c)
[1 < the log ph(( = = log(P(())))) -
(1)
By maximizing the cost likelihood in Equation (T. global guarantees of the similar to previous work on logistic bandits (Zhang et al. 2016 Abeille et al. 2021] Particularly, denoting by a² e arg max (c) the maximum likelihood estimates of the costs, can shown that for any history, global upper bound on 1 cllE, can be obtained, where the history-dependent design matrix E. captures the empirical correlations of visitation frequencies (see Appendix for details). Unfortunately, using || - <llx m. amounts to intractable algorithm CChatterji et al. 2021 and thus to an undesirable result.
be achieved,
Instead, as terminations are sampled on every time step (i.e., non-termmnntions are informative signals as well), we show we can obtain local bound on the cost function c. Specifically, we show that the error (s, a) - Cs (s, a) diminishes with n (s, a). The following result a main contribution of our work, and the crux of our regret guarantees later on (see Appendix for proof).
Theorem 1 (Local Cost Estimation Confidence Bound). Let ek E aig max.ec (c) be the maximum likelihood estimate of the costs. Then, for any 8 > O, with probability of least I for all episodes 1 E [K] timesteps h E [H 1] and state-actions (8, a) E S x A, it holds that
(s, as so c <0((((ss.))
0..
VESAHL3 log
(1
kL
A2
We note the presence of k in our upper bound, common factor [Chatterji et al. 2021), which is fundamental to our analysis, capturing the complexity estimating the costs. Trajectories that saturate the logistic function lead to more difficult credit assignment. Specifically, when the accumulated costs are high, any additional penalty would only marginally change the termination probability, making its estimation harder. A similar argument can be made when the termination probability is low.
We emphasize that in contrast to previous work global reward feedback in RL (Chattejii al. 2021 Efroni et al. 2020b), which focused specifically on settings in which information is provided only the end of episode, the TerMDP framework provides us with additional information whenever no termination occurs, allowing us to achieve strong, local bounds of the unknown costs. This observation is crucial for the design computationally tractable algorithm, as will see both in theory as well in our experiments later on.
3.1 Termination Confidence Reinforcement Learning
are now ready to present our method for solving TerMDPs with unknown costs. Our pro- posed approach, which we call Termination Confidence Reinforcement Learning (TermCRL), is shown in Algorithm I Leveraging the local convergence guarantees of Theorem I we estimate the costs by maximizing the likelihood in Equation [ We compensate for uncertainty in the

---

Algorithm 2 TermPG
1: require: window w, number of ensembles M, number of rollouts N, number of iterations K,
policy gradient algorithm ALG-PG
2: initialize: Bpss f- 0, Bueg <- 0, mg t random initialization
3: for k ,...., K do
N 4: Rollout N trajectories using To. R = aj Sig Ggp 1 i=1
5: for .,..., N do
1'
6: Add 1 negative examples (51max(1,1- (1,1-xx
a1
to Bueg.
7: Add one positive example (-== a,
St- 0c
8:
end for
9:
Train bootstrap ensemble {ce... } M
m=1 using binary cross entropy over data Bneg. Bpos.
10: Augment states in R. by of <- of و D minm Co... (st-g: aر-z)
Update policy कe t (LG-PG(R) with dynamic discount (see Section 4.2
12:
end for
reward, transitions, and costs by incorporating optimism. We define bonuses for the reward, tran- sition, and cost function by bi(h, s, = (v log(1/6)
(s,aav (h, o
SHe log[1/6] and (s,ajV
(g, s, s. - -0 RSAHL (s,a]i log())) for some > 0 (see Appendix I.1 for explicit definitions).
We add the reward and transition bonuses to the estimated reward (line 4), while the optimistic cost bonus is applied directly to the estimated costs (line 5). Then, planner (line 7) solves the optimistic MDP for which the costs are known and are given by their optimistic counterparts. We refer the reader to Appendix H for further discussion on planning in TerMDPs. The following theorem provides regret guarantees for Algorithm T Its proof is given in Appendix J analysis of UCRL [Auer et al., 2008, Efroni et al. [2119].
and relies on Theorem and the
Theorem 2. [Regret of TermCRL] With probability at least 1 - 6. the regret of Algoritim
Reg(K)= S s0
1 KS2ASHSSL log
SAHH 5
Compared the standard regret of UCRL [Auer et al. 2008 J an additional VK multiplicative factor is evident in our result, which is due to the convergence rates of the costs in Theorem [ Motivated by our theoretical results, in what follows we propose practical approach, inspired by Algorithm which utilizes local cost confidence intervals in a deep RL framework.
4 Termination Policy Gradient
Following the theoretical analysis in the previous section, we propose a practical approach for solving TerMDPs. Particularly, in this section, devise policy gradient method that accounts for the unknown costs leading to termination. We assume a stationary setup for which the transitions, rewards, costs, and policy are time-homogeneous. Our approach consists of three key elements: learning the costs, leveraging uncertainty estimates over costs, and constructing efficient value estimates through dynamic cost-dependent discount factor.
Algorithm 2 describes the Termination Policy Gradient (TermPG) method, which trains an ensemble of cost networks (to estimate the costs and uncertainty) over rollouts in policy gradient framework.
We represent our policy and cost networks using neural networks with parameters 0, {6m J.M J==1- At every iteration, the agent rolls out N trajectories in the environment using a parametric policy, ma- The rollouts are split into subtrajectories which are labeled w.r.t. the termination signal, where positive labels are used for examples that end with termination. Particularly, we split the rollouts into "windows" (i.e., subtrajectories of length w), where rollout of length t", which ends with
termination, is split into t" negative examples (5max(1./-w+| Gmax (1,- 1-w+1........................... a)) =-1
5

---

{ mm)
; (a)mm) m-1
Model Eraunile
Coc (sf am(mm) M
m=1
(m) mmmm) de
(oom (s2mi) agg ) M
Cross Entropy Loss
h 1 2
Model Ersemble
mm1
:
h =
{ ag m=1
(m)
(m)
M
Model
( Coi (s/m)) al(mm) )
M
Figure 2: Block diagram of the cost training procedure. Rollouts are split into subtrajectories, labeled according whether they end lermination. Given the dataset labeled subtrajectories, ensemble of M cost networks trained end-to-end using cross-entropy with bootstrap samples (all time steps share same ensemble).
and one positive example (1axx(1,1-=+111) -max(1" -w+1:: ................................ 8 ar-) Similarly, a rollout
of length H which does not end with termination contains negative examples. We note that by taking finite windows, we assume the terminator "forgets" accumulated costs that are not recent
a generalization of the theoretical TerMDP model in Section [ for which w = И. In Section 5 provide experiments of misspecification of the true underlying window width, where this model assumption does not hold.
4.1 Learning the Costs
Having collected dataset of positive and negative examples, we train a logistic regression model consisting of ensemble of M cost networks {ca... 1 m= shared across timesteps, depicted in
Figure Specifically, for an example (smax(1,1- 1) mmax (./-a++]] 1}. ..l........))........ .t, (t,a)) ai) we estimate the
.M (bm) are learnable bias parameters. The parameters are then learned end-to-end using the cross entropy loss. We use the bootstrap method [ickel and Freedman 1981 Chua et al. 2018) over the ensemble of cost networks. This ensemble is later used in Algorithm
termination probability by / Ej=1 Imiu(w.!) con.. (81-++1, (-++1) bm where (bm
produce optimistic estimates of the costs. Particularly, the agent policy To uses the current state augmented by the optimistic cummulative predicted cost, i.e., 5, .un (st, Captimistic), where Capriistic = -mminwd] milm Cé.. (8t-j+1, Q1-j+11) 1). Finally, the agent is trained with the augmented states using policy gradient algorithm ALG-PG (e.g.. PPO (Schulman et al. 2017), IMPALA [Espehoot et al. 2018).
4.2 Optimistic Dynamic Discount Factor
While augmenting the state with the optimistic accumulated costs is sufficient for obtaining optimality. we propose to further leverage these estimates more explicitly noticing that finite horizon objective we are solving can be cast to discounted problem. Particularly, it is well known that the discount factor y E (0, 1) can equivalently formulated as probability of "staying alive" (see the discounted MDP framework, [Puterman] (2014)). Similarly, by augmenting the state with the
accumulated cost C₁ Σh. c(st, ar), we view the probability - -O(O)) as a state-dependent discount factor, capturing the probability of an agent in a TerMDP to not be terminated.
We define dynamic, cost-dependent discount factor for value estimation. We use the state-action value function (s, a, C.) over the augmented states, defined for any s, a, C' by
(" (s, ET
II Th r(82, at) =8 =8 0, =a, =

---

Backseat Driver (Coin Avoidance)
Backseat Driver (Human)
10
10
8
Legend
8
reward
reward
PG
Recurrent PG
PG+RS
TerPPG
TermPGRRS
2
2
TermPG+Pennaly
0
1
2
4
5
6
0
2
3 step
4
5
6
Step
Figure 3: Mcan reward with std. over five seeds of "Backscat Driver", Left: coin avoidance; right: human termination. Variants with reward shaping (RS, orange and brown) penalize the agent with constant value upon termination. The recurrent PG variant (green) history-dependent policy without learning The TermPG+Penalty variant (purple) penalizes the reward every time step using the estimated costs.
where ?h = 1- 11- - c(s,, -b).
b). This yields the Termination Bellman Equations (sce
Appendix D for derivation)
(" r(s, + (1- ol
To incorporate uncertainty in the estimated costs, we use the optimistic accumulated costs 1j=1 [min(w.)) min, Co... ( @t-j+1). Then, the discount factor becomes y (Coptimitti) 1 p( optiiistic b). Assuming that, w.h.p., optimistic costs are smaller than the true costs, the discount factor decreases as the agent exploits previously visited states.
Coptiiisicc
The dynamic discount factor allows to obtain more accurate value estimator. In particular, leverage the optimistic cost-dependent discount factor 7 (Cupiimisti))) in our value estimation procedure, using Generalized Advantage Estimation (GAE, [Schulman et al. (2013)). As will show in the next section, using the optimistic discount factor significantly improves overall performance.
Experiments
In this section we evaluate the strength of our approach, comparing it to several baselines, including: (1) PG (naive): The standard policy gradient without additional assumptions, which ignores termi- nation. (2) Recurrent PG: The standard policy gradient with a history-dependent recurrent policy (without cost estimation dynamic discount factor). As the history is sufficient statistic of the costs, optimal policy realizable. (3) PG with Reward Shaping (RS): penalize the reward upon termination by constant value, i.c., r(s, a) p1 Stemm for some p O. This approach can be applied to any variant of Algorithm 2 or the methods listed above. (4) TermPG: Described in Algorithm 2 We additionally implemented two variants of TermPG, including: (5) TermPG with Reward Shaping: We penalize the reward with constant value upon termination. (6) TermPG with Cost Penalty: We penalize the reward every time step by the optimistic cost estimator, i.e., - aCotimistic for some a > O. All TermPG variants used an ensemble three cost networks, and a dynamic cost-dependent discount factor, described in Section 4.2) We report mean and std. of the total reward (without penalties) for all our experiments.
Backseat Driver (BDr). We simulated driving application, using MLAgeets (Juliani et al. 2018
by developing a new driving benchmark, "Backseat Driver" (depicted in Figure 4 where we tested both synthetic and human terminations. The game consists of five lane never-ending road, with randomly instantiating vehicles and coins. The agent can switch lanes and is rewarded for overtaking vehicles. In experiments, states were represented as top view images containing the position of the agent, nearby cars, and coins with four stacked frames. We used finite window length 120 for termination (30 agent decision steps), mimicking passenger forgetting mistakes of the past.
BDr Experiment 1: Coin Avoidance. In the first experiment Backseat Driver, coins are considered as objects the driver must avoid. The coins signify unknown preferences of the passenger, which are not explicitly provided to the agent. As the agent collects coins, penalty accumulated, and the agent is terminated probabilistically according the logistic cost model in Section 2 We emphasize

---

Space Invaders
Seaquest
12
RG
Recurrent PG
3.0
10
reward
8
TermPG
2.0
TermPG Penaity
6
1.0
4
0.5
2
0.0
0.0
0.2
0.4
0.6
0.8
0.0
0.2
0.4
0.6
0.8
step
1e7
step
1e7
Breakout
Asterix
1.8
1.6
reward
1.2
1.0
0.6
0.4
0.0
0.2
0.4
0.6
0.8
0.0
0.2
0.4
0.6
0.8
step
1e7
step
1e7
Figure 5: Results for MinAtar benchmarks. All runs were averaged over five seeds. Comparison best performing TermPG variant to best performing PG variant (relative improvement percentage): 80% in Space Invaders, 150% in Seaquest, 410% in Breakout, and 90% in Asterix.
that, while the coins are visible to the agent (i.e., part of the agent's state), the agent only receives feedback from collecting coins through implicit terminations.
Results for Backseat Driver with coin-avoidance termination are depicted in Figure 3 We compared TermPG (pink) and its two variants (brown, purple) the PG (bluc), recurrent PG (green), and reward shaping (orange) methods described above. Our results demonstrate that TermPG significantly outperforms the history- based and penalty- based baselines. We found TermPG (pink) perform significantly better, doubling the reward of the best PG variant. All TermPG variants converged quickly to a good solution, suggesting fast convergence of the costs (see Appendix
BDr Experiment 2: Human Termination. To comple- our results, we evaluated human termination on Back- seat Driver. For this, we generated data of termination sequences from agents of varying quality (ranging from random to expert performance). We asked five human supervisors label subsequences of this data by termi- nating the agent in situations of "continual discomfort". This guideline was kept ambiguous allow for diverse termination signals. The final dataset consisted of 512 termination examples. We then trained model to pre- dict human termination and implemented it into Backseat Driver to simulate termination. We refer the reader to Appendix for specific implementation details. Figure 3 shows results for human termination in Backscat Driver. As before, a significant performance increase was evident in our experiments. Additionally, found that using cost penalty (purple) termination penalty (brown) for TermPG did not greatly affect performance.
Figure Backseat Driver
MinAtar. We further compared our method to the PG, recurrent PG, and reward shaping methods, on MinAtar (Young and Tian 2019). For each environment, we defined cost functions that do not necessarily align with the pre-specified reward, to mimic uncanny behavior that humans are expected to dislike. For example, in Breakout, the agent was penalized whenever the paddle remained in specific regions (e.g., sides of the screen), whereas in Space Invaders, the agent was penalized for

---

Table 1: Summary of results (top) and ablations for TermPG (bottom). Standard deviation optimism did not have significant impact on performance. Removing optimism or the dynamie discount factor had negative impact on performance. TermPG was found to be robust to model misspecifecations of the accumulated cost window.
Backseat Driver
MinAtar
Experiment
Coin Avoid.
Human
Space Inv.
Seaquest
Breakout
Asterix
PG
5.3 0.8
19=13
5.2
0.6
14=25
0.8 0.3
Recurrent PG
0.22
6418
2.8 0.05
0.1 0.3
0.7
0.7 0.2
PG RS
5.9.1.44
7.4 1 1.7
7.6 1 2.3
0.4 1 0.2
0.5 1 0.03
0.9 1 0.2
TermPG (ours)
8.741.4 1.4
8.3 = 1.3
9.7 = 1.1
1.4 0.8
8.2 = 0.3
1 + 0.2
TermPG + (ours)
8.4
7.7
0.8
0.3
5.1
0.8 1 0.1
TormPG + Ponaliy (ours)
6 0.8
11.8 1.5
7.7 = 1.4
24=1
2.3 = 2.3
1.7 0.1
Ablation Test
Coin Avoid.
Human
Space Inv.
Seaquest
Breakout 10.9
Asterix
Optimism with Ensemble Std.
7.6 2.1
7.5
2.8 0.02
0.9 0.6
1.1.1
No Optamism
7.8 4 1.3
8.8 10:1122 1.2
5.2 = 1.6
0.7 4 0.3
1.3 = 0.7
1.0.1
No Dynamic Discount
6.9 0.6
5.9
14 1.8
0.1
0.00
0.8 0.80011
x0.5 Window Mispecification
7.2 1.1
7.2 0.5
9.7 331
2.4
7.9
0.8 + 0.1
x2 Window Mispecifheation
0.1
8.4
11.13
2.2
10.3 = 0.8
0.1.1
"near misses" of enemy bullets. We refer the reader Appendix E for specific details of the different termination cost functions.
Figure [ depicts results on MinAtar. As with Backseat Driver, TermPG lead to significant improve- ment, often achieving a magnitude order as much reward as Recurrent PG. We found that adding a termination penalty and cost penalty produced mixed results, with them being sometimes useful (e.g.. Space Invaders, Sequest, Asterix), yet other times harmful to performance (e.g., Breakout). Therefore, we propose fine-tune these penalties in Algorithm [ Finally, we note that training TermPG was, on average, 67% slower than PG, on the same machine. Nevertheless, though TermPG was somewhat more computationally expensive, it showed a significant increase in overall performance. A summary of all of our results is presented in Table [ (top).
Ablation Studies. We present various ablations for TermPG in Table I (bottom). First, we tested the effect replacing the type of cost optimism in TermPG. In Section [, cost optimism was defined using the minimum of the cost ensemble, i.e., min }. Instead, we replaced the cost optimism to Captimistic = mean (Co... } (std((o..,) ). testing different values of a. Surprisingly, this change mostly decreased performance, except for Breakout, where it performed significantly better. Other ablations included removing optimism altogether (i.e., only using the mean of the ensemble). and removing the dynamic discount factor. In both cases we found significant decrease in performance, suggesting that both elements are essential for TermPG to work properly and utilize the estimator of the unknown costs. Finally, we tested misspecifications of our model by learning with windows that were different from the environment' 's real cost accumulation window. In both cases, TermPG was suprisingly robust to window misspecification, as performance remained almost unaffected by it.
Related Work
Our setup can be linked to various fields, as listed below.
Constrained MDPs. Perhaps the most straightforward motivations for external termination stems from constraint violation [Chow et al., 2018 Efroni al.) 2020al [HasanzadeZonuzy al., 2020]] where strict or soft constraints are introduced to the agent, who must learn to satisfy them. In these setups, which often motivated by safety [Garcıa and Fernández 2015), the constraints are usually known. In contrast, in this work, the costs are unknown and only implicit termination is provided.
Reward Design. Engineering good reward function is hard task, for which frequent design choices may drastically affect performance [Oh et al., 2021). Moreover, for tasks where humans are involved, it is rarely clear how to engineer reward, as human preferences are not necessarily known, and humans are non-Markovian by nature [Clarke et al. 2013 Christiano et al. [017]] Termination thus be viewed an efficient mechanism to elicit human input, allowing to implicitly interpret human preferences and utility more robustly than trying to specify a reward.
Global Feedback in RL, Recent work considered once-per-trajectory reward feedback in RL, observing either the cumulative rewards at the end of an episode [Efroni et al., (2020)] Cohen et al.)
2021 or logistic function of trajectory-bast based features Chatterji et al. [021] While these works are

---

based on similar solution mechanism, our work concentrates new framework, which accounts for non- Mon-Markovian termination. Additionally. we provide ptr-state concentration guarantees of the unknown cost function, compared to global concentration bounds in previous work [Abbasi- Yadkori jtt al. 2011 Zhang et al. 2016 Qi et al, [018 Abeille et al. 202T]. Using our local guarantees, we are able to construct a scalable policy gradient solution, with significant improvement over recurrent and reward shaping based approaches.
Preference-based RL. In contrast to traditional reinforcement learning, preférence-based rein- forcement learning (PbRL) relies on subjective opinions rather than numerical rewards. In PbRL preferences are captured through probabilistic rankings of trajectories (Wirth et al. 2016 2017 Xu al.) 2020). Similar our work, CCristtaano al. [2017] use a regression model to learn a reward function that could account for the preference feedback. Our work considers different setting in which human feedback provided through termination, where termination and reward may not align.
Discussion
This paper formulated reinforeement learning. We defined the TeMMDP framework and proposed a theoretically gararaaalyyg solution, well as practical policy-gradient approach. Our results showed significant improvement of our approach over various baselines. We stress that while may seem as if the agent has two potentially conflicting goals-avoiding termination and maximizing reward they are, in fact, aligned. The long-term consequences actions need to account for longer survival which, in turn, allows for more reward collection. In what follows, discuss K, as factored in our regret bounds, well possible limitations of our work.
model to account for distory-dependent exogenous termination in
The Role of As shown in Theorem 2 plays a significant role in the regret bound of Algorithm [ This linear dependence is induced from the confidence bounds of Theorem [ Informally, k is
negligible whenever the costs and bias b are "well behaved". Suppose Eí ce(s at) ) - > 0. In this case, x would be large and termination would mostly occur after the first step. such, estimation of the costs would be hard (see Chatterji et al. [2021). Alternatively, suppose Σi= ce(st, - < O. In this case, would also be large. Here, credit assignment would make the cost estimation problem harder, as trajectories would span longer horizons. It is unclear, as to the writing of this work, if other solutions to TerMDPs could bring about stronger regret guarantees that significantly reduce their dependence on k. We note that lower bounds, which include have previously been established for the estimation problem (see gcefAbeille
al. [202]), Faury et al. [2020]. Jun et al. (202T)) Nevertheless, when searching for policy which maximizes reward, it is unclear if estimation of the costs is indeed necessary for every state. We leave this direction for future work.
Limitations and Negative Societal Impact A primary limitation of our work involves the linear dependence of the logistic termination model. some settings, might be hard to capture true human preferences and behaviors using linear model. Nevertheless, when measured across the full trajectory, our empirical findings show that this model highly expressive, as we demonstrated on real human termination data (Section 5). Additionally, we note that work in inverse RI. (Arora and Doshi 2021 also assumes such linear dependence of human decisions w.r.t. reward. Future work can consider more involved hypothesis classes, building upon our work to identify the optimal tradeoff between expressivity and convergence rate.
Finally, we note a possible negative societal impact of our work. Termination is strongly motivated by humans interacting with the agent. This may be harmful if not carefully controlled, learning incorrect or biased preferences may, in turn, result in unfavorable consequences, or if humans engage in adversarial behavior in order to mislead an agent. Our work discusses initial research in this domain. We encourage caution in real-world applications, carefully considering the possible effects of model errors, particularly in applications that affect humans.
10

---

References
Yasin Abhasi-Yadkori, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. Advances in neural information processing systems, 24, 2011.
Marc Abeille, Louis Faury, and Clément Calauzènes. Instance-wise manimax--ptiimal algorithms for logistic bandits. In International Conference on Artificial Intelligence and Statistics, pages 3691-3699, PMLR, 2021.
Saurabh Arora and Prashant Doshi. A survey of inverse reinforcement learning: Challenges, methods and progress. Artificial Intelligence, 297:103500, 2021.
Peter Auer, Thomas Jaksch, and Ronald Ortner.
Near-optimal regret bounds for reinforcement learning, Advances neural information processing systems, 21, 2008.
KV Bhagwat and R Subramanian. Inequalities between means of positive operators. In Mathematical Proceedings of the Cambridge Philosophical Society, volume 83, pages 393-401 Cambridge University Press, 1978.
Peter J Bickel and David A Freedman. Some asymptotic theory for the bootstrap. The annals of statistics, 9(6): 19111177 1981.
Niladri Chatterji, Aldo Pacchiano, Peter Bartlett, and Michael Jordan. On the theory of reinforcement learning with once-per-episode feedback. Advances in Neural Information Processing Systems, 34, 2021.
Yinlam Chow, Ofir Nachum, Edgar Duenez-Guzman and Mohammad Ghavamzadeh. A Lyapunov- based approach to safe reinforcement learning. Advances in neural information processing systems, 31, 2018.
Paul F Christiano, Jan Leike, Tom Brown, Miljan Martic, Shane Legg, and Dario Amodei. Deep reinforcement learning from human preferences. Advances in neural information processing systems, 30, 2017.
Kurtland Chua, Roberto Calandra, Rowan McAllister, and Sergey Levine Deep reinforcement learning in a handful of trials using probabilistic dynamics models. Advances in neural information processing systems, 31, 2018.
AM Clarke, Johannes Friedrich, Walter Senn, EM Tartaglia, Silvia Marchesotti, and Michael H Herzog. Human learning in non-markovian decision making, 2013.
Alon Cohen, Haim Kaplan, Tomer Koren, and Yishay Mansour. Online markov decision processes with aggregate bandit feedback. In Conference on Learning Theory, pages 1301-1329. PMLR, 2021.
Christoph Dann, Tor Lattimore, and Emma Brunskill. Unifying pac and regret: Uniform pac bounds for episodic reinforcement learning. Advances Neural Information Processing Systems, pages 5713-5723, 2017.
Yonathan Efroni, Nadav Merlis, Mohammad Ghavamzadeh, and Shie Mannor. Tight regret bounds for model-based reinforcement learning with greedy policies. Advances in Neural Information Processing Systems, 32, 2019.
Yonathan Efroni, Shie Mannor, and Matteo Pirotta. Exploration-exxploitatooo in constrained mdps. arXiv preprint /8X2 2020a.
Yonathan Efroni, Nadav Merlis, and Shie Mannor. Reinforcement learning with trajectory feedback. arXiv preprint arXhv:2008.06036. 2020b.
Lasse Espeholt, Hubert Soyer, Remi Munos, Karen Simonyan, Vlad Mnih, Tom Ward, Yotam Doron, Vlad Firoiu, Tim Harley, lain Dunning, et al. Impala: Scalable distributed deep-rl with importance weighted actor-learner architectures. International Conference on Machine Learning, pages 1407-1416. PMLR, 2018

---

Louis Faury, Mare Abeille, Clément Calauzènes, and Olivier Fercoq. Improved optimistic algorithms for logistic bandits. In International Conference on Machine Learning, pages 3052-3060. PMLR, 2020.
Javier Garcia and Fernando Fernández. A comprehensive survey on safe reinforcement learning. Journal of Machine Learning Research, 16(1):1437-1400, 2015.
Aria HasanzadeZonmuzy, Dileep M. Kalathil, and Srinivas Shakkottai. Learning with safety con- straints: Sample complexity of reinforcement learning for constrained mdps. arXiv preprint arXiv:2008.003// 00311, 2020.
Arthur Juliani, Vincent-Pierr Berges, Ervin Teng, Andrew Cohen, Jonathan Harper, Chris Elion, Chris Goy, Yuan Gao, Hunter Henry. Marwan Mattar, et al. Unity: A general platform for intelligent agents. arXiv preprint arXiv:1809.02627 026279 2018.
Kwang-Sung Jun, Lalit Jain, Blake Mason, and Houssam Nassif. Improved confidence bounds for the linear logistic model and applications to bandits. In International Conference Machine Learning, pages 5148-5157. PMLR, 2021.
B Ravi Kiran, Ibrahim Sobh, Victor Talpaert, Patrick Mannion, Ahmad A Al Sallab, Senthil Yogamani, and Patrick Pérez. Deep reinforcement learning for autonomous driving: A survey. IEEE Transactions Intelligent Transporiution Systems, 2021.
Nevena Lazic, Craig Boutilier, Tyler Lu, Eehern Wong, Binz Roy, MK Ryu, and Greg Imwalle. Data center cooling using model-predictte control. Advances in Neural Information Processing Systems, 31, 2018
Scott Le Vine, Alireza Zolfaghari, and John Polak. Autonomous cars: The tension between occupant experience and intersection capacity. Transportation Research Part C: Emerging Technologies, 52: 1-14, 2015.
Eric Liang, Richard Liaw, Robert Nishihara, Philipp Moritz, Roy Fox, Ken Goldberg, Joseph Gonzalez, Michael Jordan, and lon Stoica. Rllib: Abstractions for distributed reinforcement learning. In International Conference Machine Learning, pages 3053-3062. PMLR, 2018
Amol Mandhane, Anton Zhernov, Maribeth Rauh, Chenjie Gu, Miaosen Wang, Flora Xue, Wendy Shang, Derek Pang, Rene Claus, Ching-Han Chiang, et al. Muzero with self-competition for rate control in vp9 video compression. arXiv preprint arXiv:2202.066: 066266 2022.
Hamidreza Modares, Isura Ranatunga, Frank L Lewis, and Dan O Popa. Optimized assistive human- robot interaction using reinforcement learning. IEEE transactions cybernetics, 46(3):655-66) 667,
2015.
Inseok Oh, Seungeun Rho, Sangbin Moon, Seongho Son, Hyoil Lee, and Jinyun Chung. Creating pro-level ai for real-time fighting game using deep reinforcement learning. IEEE Transactions Games, 2021.
Martin L Puterman. Markov decision processes: discrete stochastic dynamic programming. John Wiley & Sons, 2014.
Yi Qi. Qingyun Wu, Hongning Wang, Jie Tang. and Maosong Sun. Bandit learning with implicit feedback. Advances in Neural Information Processing Systems, 31, 2018.
John Schulman, Philipp Moritz, Sergey Levine, Michael Jordan, and Pieter Abbecl. High-dimensional continuous control using generalized advantage estimation. arXiv preprint 15X6:15566002338 2015.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint arXiv: 1707.06377 2017.
Dilip Singh Sisodia, Somdutta Vishwakarma, and Abinash Pujahari. Evaluation of machine learning models for employee churn prediction. In 20/7 international conference on inventive computing and informatics (icici), pages 1016-1020. IEEE, 2017.
12

---

Yi-Fan Wang, Ding-An Chiang, Mei-Hua Hsu, Cheng-Jung Lin, and I-Long Lin. A recommender system avoid customer churn: case study. Expert Systems with Applications, 36(4):8071-8075. 2009.
Tsachy Weissman, Erik Ordentlich, Gadiel Seroussi, Sergio Verdu, and Marcelo J Weinberger. Inequalities for the deviation of the empirical distribution. Newleet-Packan Labs, Tech. Rep, 2003.
Christian Wirth, Johannes Fürnkranz, and Gerhard Neumann. Model-free preference- weeerence-based reinforce- ment learning. In Thirtieth AAAI Conference on Artificial Intelligence, 2016.
Christian Wirth, Riad Akrour, Gerhard Neumann, Johannes Fürnkranz, et al. A survey of preference- based reinforcement learning methods. Journal of Machine Learning Research, 18(136):1-46, 2017.
Yichong Xu, Ruosong Wang, Lin Yang, Aarti Singh, and Artur Dubrawski. Preference-hased reinforcement learning with finite-time guarantees. Advances in Neural Information Processing Systems, 33:18784-18794, 2020.
Kenny Young and Tian Tian. Minatar: An atari-inspired testbed for thorough and reproducible reinforcement learning experiments. arXiv preprint arXiv:1903.03176. 2019.
Lijun Zhang, Tianbao Yang. Rong Jin, Yichi Xiao, and Zhi-Hua Zhou Online stochastic linear optimization under one-bit feedback. In International Conference Machine Learning, pages 392-401. PMLR, 2016.
Meixin Zhu, Yinhai Wang, Ziyuan Pu, Jingyun Hu, Xuesong Wang, and Ruimin Ke. Safe, effi- cient, and comfortable velocity control based on reinforcement learning for autonomous driving. Transportation Research Part C: Emerging Technologies, 117:102662, 2020.
13

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [Yes]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either the supplemental material or as URL)? [Yes]
(b) Did you specify all the training details (e.g., data splits. hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e.g.. with respect the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (c.g., type of GPUs, internal cluster, or cloud provider)? [Yes]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [Yes]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
14


Reviews:
[{"review_id": "d1D-syiasit", "reviewer": "Reviewer_tpfd", "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.  ", "questions": "-\tWhat 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.\n-\tHow 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?\n-\tWhat 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.\n", "limitations": "-\tThe paper provides a reasonable discussion of technical limitations.\n-\tThe paper provides some discussion of societal impact in the final discussion, at a level that is adequate for the potential risks.\n", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "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.\n(+) The paper is clearly written, and the reader can understand the methodology and contributions.\n(+) Several experimental domains are considered, and ablations are performed to clarify impact of different aspects of the model.\n\n(-) 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.\n(-) 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.\n(-) 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.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "_MfTwYZxSUh", "reviewer": "Reviewer_gYNG", "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. \n", "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?\n\n2. 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?\n\n3. 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?\n\n4. 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?\n", "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. ", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "## Clarity\n\nThe paper is generally clear and well-written. \n\n\n## Soundness\n\nThe 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. \n\n\n## Novelty and Significance\n\nThe 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.\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "3FGwXNnlrv5", "reviewer": "Reviewer_nYZQ", "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. ", "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.\n\n1. 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?   \n\n2. 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.\n\n3. 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? \n\n4. 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?\n\n5. 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? \n\nMinor typo: Line 158: rollouts -> rolls out\n\n[1] Arjona-Medina, Jose A., et al. \"Rudder: Return decomposition for delayed rewards.\" Advances in Neural Information Processing Systems 32 (2019).\n[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. \n\n[3] Orseau, Laurent, and Stuart Armstrong. \"Safely interruptible agents.\" Proceedings of the Thirty-Second Conference on Uncertainty in Artificial Intelligence. 2016. ", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "\n\\+ 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.\n\n\\+ 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. \n\n\\+ On the whole, the paper was extremely well-written (but see below) and well laid out \n\n\\+ At various points, the paper points out limitations or shortcomings, which I appreciated\n\n\\- 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). \n\n\\- 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. \n\n\\- 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. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept