Title: AVOIDING CATASTROPHIC STATES WITH INTRINSIC FEAR

Abstract: Many practical reinforcement learning problems contain catastrophic states that the optimal policy visits infrequently or never. Even on toy problems, deep reinforcement learners periodically revisit these states, once they are forgotten under a new policy. In this paper, we introduce intrinsic fear, a learned reward shaping that accelerates deep reinforcement learning and guards oscillating policies against periodic catastrophes. Our approach incorporates a second model trained via supervised learning to predict the probability of imminent catastrophe. This score acts as a penalty on the Q-learning objective. Our theoretical analysis demonstrates that the perturbed objective yields the same average return under strong assumptions and an -close average return under weaker assumptions. Our analysis also shows robustness to classification errors. Equipped with intrinsic fear, our DQNs solve the toy environments and improve on the Atari games Seaquest, Asteroids, and Freeway.

1. INTRODUCTION:

Following success on Atari games (Mnih et al., 2015) and the board game Go (Silver et al., 2016) , many researchers have begun exploring practical applications of deep reinforcement learning (DRL). Some investigated applications include robotics (Levine et al., 2016) , dialogue systems (Fatemi et al., 2016; Lipton et al., 2016) , energy management (Night, 2016) , and self-driving cars (Shalev-Shwartz et al., 2016) . Amid this push to apply DRL, we might ask, can we trust these agents in the wild? Agents acting in real-world environments might possess the ability to cause catastrophic outcomes. Consider a self-driving car that might hit pedestrians or a domestic robot that might injure a child. We might hope to prevent DRL agents from ever making catastrophic mistakes. But doing so requires extensive prior knowledge of the environment in order to constrain the exploration of policy space (Garcıa and Fernández, 2015) .

Many conflicting definitions of safety and catastrophe exist, a problem that invites further philosophical consideration. In this paper, we introduce a specific but plausible notion of avoidable catastrophes. These are states that prior knowledge dictates an optimal policy should never visit. For example, we might believe that an optimal self-driving algorithm would never hit a pedestrian. Moreover, we assume that an optimal policy never even comes near an avoidable catastrophe state. We define proximity in trajectory space, and not by the geometry of feature space. We denote states proximal to avoidable catastrophes as danger states. While we don't assume prior knowledge of which states are dangerous, we do assume the existence of a catastrophe detector. After encountering a catastrophic state, an agent can realize this and take action to avoid dangerous states in the future.

Given this definition, we address two challenges: First, can we expect DRL agents, after experiencing some number of catastrophic failures, to avoid perpetually making the same mistakes? Second, can we use our prior knowledge that catastrophes should be kept at a distance to accelerate learning of a DRL agent? Our experiments show that even on toy problems, the deep Q-network (DQN), a basic algorithm behind many of today's state-of-the-art DRL systems, struggles on both counts. Even in toy environments, DQNs may encounter thousands of catastrophes before learning to avoid them and are susceptible to repeating old errors. We call this latter problem the Sisyphean curse.

This poses a formidable obstacle to using DQNs in the real world. How can we hand over responsibility for consequential actions (control of a car, say) to a DRL agent if it may be doomed to periodically remake every kind of mistake, however grave, so long as it continues to learn? Imagine a self-driving car that had to periodically hit a few pedestrians in order to remember that is undesirable. In the tabular setting, an RL agent never forgets the learned dynamics of its environment, even as its policy evolves. Moreover, if the Markovian assumption holds, eventual convergence to a globally optimal policy is guaranteed. Unfortunately, the tabular approach becomes infeasible in high-dimensional, continuous state spaces.

The trouble for DQNs owes to the use of function approximation (Murata and Ozawa, 2005) . When training a DQN, we successively update a neural network based on experiences. These experiences might be sampled in an online fashion, from a trailing window (experience replay buffer), or uniformly from all past experiences. Regardless of which mode we use to train the network, eventually, states that a learned policy never encounters will come to form an infinitesimally small region of the training distribution. At such times, our networks are subject to the classic problem of catastrophic interference (McCloskey and Cohen, 1989; McClelland et al., 1995) . Nothing prevents the DQN's policy from drifting back towards a policy that revisits long-forgotten catastrophic mistakes.

More formally, we characterize the problem as unfolding in the following steps: (i) Training under distribution D, our agent produces a safe policy π s that avoids catastrophes (ii) Collecting data generated under π s yields a new distribution of transitions D (iii) Training under D , the agent produces π d , a policy that once again experiences avoidable catastrophes. To illustrate the brittleness of modern DRL algorithms, we introduce a simple pathological problem called Adventure Seeker. This problem consists of a one-dimensional continuous state, two actions, simple dynamics, and a clear analytic solution. Nevertheless, the DQN fails. We then show that similar dynamics exist in the classic RL environment Cart-Pole.

In this paper, to combat these problems, we propose intrinsic fear. In this approach, we train a supervised fear model that predicts which states are likely to lead to a catastrophe within k r steps. The output of the fear model (a probability), scaled by a fear factor penalizes the Q-learning target. Our approach draws inspiration from intrinsic motivation (Chentanez et al., 2004) . However, instead of perturbing the reward function to encourage the discovery of novel states, we perturb it to discourage revisiting catastrophic states.

We validate the approach both empirically and theoretically. Our experiments address both our Adventure Seeker problem and Cartpole as well as the Atari games Seaquest and Asteroids, and Freeway. For these environments, we label each loss of a life as a catastrophic state. On the toy environments, the intrinsic fear agent learns to avoid death indefinitely, achieving unbounded reward per episode. On Seaquest and Asteroids, the intrinsic fear agent improves markedly and on Freeway the improvement is dramatic. Theoretically, we demonstrate the following: First, we prove that when the reward is bounded and the optimal policy rarely visits the catastrophic states, the policy learned on the altered value function has return similar to the optimal policy on the original value function. Second we prove that the method is robust to noise in the danger model.

2. INTRINSIC FEAR:

Over a series of turns, an agent interacts with its environment via a Markov decision process, or MDP, (S, A, T , R, γ). At each step t, an agent observes a state s ∈ S. The agent then chooses an action a ∈ A according to some policy π. In turn, the environment transitions to a new state s t+1 ∈ S according to transition dynamics T (s t+1 |s t , a t ) and generates a reward r t with expectation R(s, a). This cycle continues until each episode terminates.

The goal of an agent is to maximize the cumulative discounted return T t=0 γ t r t . Temporaldifferences (TD) methods (Sutton, 1988) such as Q-learning (Watkins and Dayan, 1992) model the Q-function, which gives the optimal discounted total reward of a state-action pair; the greedy policy w.r.t. the Q-function is optimal (Sutton and Barto, 1998) . Problems of practical interest tend to have large state spaces, thus the Q-function is typically approximated by parametric models such as neural networks.

In Q-learning with function approximation, an agent alternately collects experiences by acting greedily with respect to Q(s, a; θ Q ) and updates its parameters θ Q . Updates proceed as follows. For a given experiences (s t , a t , r t , s t+1 ), we minimize the squared Bellman error:

L = (Q(s t , a t ; θ Q ) -y t ) 2

(1)

for y t = r t + γ • max a Q(s t+1 , a ; θ Q ).

Traditionally, the parameterised Q(s, a; θ) is trained by stochastic approximation, estimating the loss on each experience as it is encountered, yielding the update:

EQUATION

Q-learning methods also require an exploration strategy for action selection. For simplicity, we consider only the -greedy heuristic.

A few tricks help to stabilize Q-learning with function approximation. Of particular relevance to this work is experience replay (Lin, 1992) : the RL agent maintains a buffer of past experiences, applying TD-learning on randomly selected mini-batches of experience to update the Q-function.

In this paper, we propose a new formulation of the safety problem. We suppose there exists a subset C ⊂ S of states that an optimal policy encounters them very rarely or never and denote them catastrophic states. Moreover, we assume that for some environments, optimal policies are rarely within a short distance of a catastrophic state. As a measure of distance, we consider steps in trajectory space. We define the distance d(s i , s j ) to be length N of the smallest sequence of transitions {(s t , a t , r t , s t+1 )} N t=1 that traverses state space from s i to s j .1 Definition 2.1. Suppose that we are given a priori knowledge that acting according to the optimal policy π * , an agent never encounters states s ∈ S for which lie within distance d(s, c) < k τ for any catastrophe state c ∈ C. Then each state s for which ∃c ∈ C s.t. d(s, c) < k τ is a danger state.

We also suppose that the agent can recognize the catastrophe states as they are encountered. Definition 2.2. A catastrophe detector is a function f : S → {0, 1} that returns 1 if and only if a state is a catastrophe state.

We propose Intrinsic Fear (IF) (Algorithm 1), a novel algorithm for avoiding catastrophes when learning online with function approximation. In our approach, we maintain both a DQN and a separate, supervised fear model F : S → [0, 1]. Our fear model F provides an auxiliary source of reward, penalizing the Q-learner for entering possibly dangerous states.

The goal in modeling danger states is twofold. First, by shaping rewards away from suboptimal states, we encode prior knowledge about the environment and can thus accelerates learning. Second, when catastrophic states correspond to especially undesirable outcomes, the learned reward shaping can protect DQNs, which are susceptible to catastrophic forgetting, from drifting close to catastrophic states. Owing to this self-assigned reward, once the fear model is trained, a Q-learner might update to avoid catastrophes without having to actually repeat them, so long as the fear model is not itself susceptible to catastrophic forgetting. We draw some inspiration from the idea of a parent scolding a child for running around with a knife. The child can learn to adjust its behavior without actually having to stab someone. We also draw inspiration from the way humans appear to process traumatic experience, remembering especially bad events vividly even as most other memories from the same time period fade. Perhaps this selective memorization of bad events confers a benefit for avoiding similar outcomes in the future.

Our instantiation of intrinsic fear works as follows: In addition to the DQN, we maintain a binary classifier that we term a fear model. In our case, we use a neural network of the same architecture as the DQN (but for the output layer). The fear model's purpose is to predict the probability that any state will lead to catastrophe within k moves. Over the course of training, our agent adds each experience (s, a, r, s ) to its experience replay buffer. As each catastrophe is reached at the n th turn of an episode, we add the k r (fear radius) states leading up to the catastrophe to a list of danger states. We add the preceding n -k r states to a list of safe states. When n < k r , all states for that episode are added to the list of danger states. Then after each turn, in addition to making one update to the Q-network, we make one mini-batch update to the fear model. To make this update, we sample 50% of samples in the batch from the danger states, assigning them label 1 and the remaining 50% from the safe states, assigning them label 0.

For each update to the DQN, we perturb the TD target y t . Instead of updating Q(s t , a t ; θ Q ) towards r t + max a Q(s t+1 , a ; θ Q ), we introduce the intrinsic fear to the model via the target: 

EQUATION

λ τ ← min(λ, λ•t k λ ) 17: y τ ← r τ -λ τ , for terminal s τ +1 r τ + max a Q(s τ +1 , a ; θ Q ) -λ • F (s τ +1 ; θ F ) for non-terminal s τ +1 18: θ Q ← θ Q -η • ∇ θ Q (y τ -Q(s τ , a τ ; θ Q )) 2 19:

Sample random mini-batch s j with 50% of examples from D D and 50% from D S 20:

y j ← 1, for s j ∈ D D 0, for s j ∈ D S 21: θ F ← θ F -η • ∇ θ F loss F (y j , F (s j ; θ F ))

where F (s; θ F ) is the fear model and λ is a fear factor determining the scale of the impact of intrinsic fear on the Q-function update.

Note that IF perturbs the objective function. Thus, one might be concerned that the perturbed reward might indicate a different optimal policy. Fortunately, if the labeled catastrophe states and danger zone do not violate our assumptions, and if the fear model reaches arbitrarily high accuracy, then this will not happen.

For an MDP, M = S, A, T , R, γ , with 0 ≤ γ ≤ 1, the average reward return is as follows:

η M (π) :=      lim T →∞ 1 T E M T t r t |π if γ = 1 (1 -γ)E M ∞ t γ t r t |π if 0 ≤ γ < 1 (4)

The optimal policy π * of the model M is the policy which maximizes the average reward return, π * = max π∈P η(π) where P is a set of stationary polices.

Theorem 1. For a given MDP, M , with γ ∈ [0, 1] and a catastrophe detector f , let π * denote an optimal policy of M , and π denote an optimal policy of M equipped with fear model F and λ. If the probability π * visits the states in the danger zone is at most , and

EQUATION

Proof. Appendix A.

It is worth noting that when at least one of the optimal policies of M , does not visit the fear zone ( = 0), then η * M = η M,F (π) and the fear signal can boost up the process of learning the optimal policy.

Since we learn the catastrophe detector f and fear model F empirically using the collected data, our RL agent has access to an imperfect detector f and imperfect fear model F , and therefore assumes the fear model is F . In this case, the RL agent trains with intrinsic fear generated by f , learning a different value function than the RL agent with perfect f . To show robustness against modeling errors, we are interested in the average deviation in the value functions of the two agents.

In general, in practical RL problems, we use discount factors γ < 1 (Kocsis and Szepesvári, 2006) in order to reduce the planing horizon, and computation cost. Moreover, (Jiang et al., 2015) suggests that when we have estimation (up to the confidence intervals) of our MDP model, it is better to use smaller discount factors in order to prevent over-fitting to the estimated model. We show that under modeling errors, if the actual objective function to optimize for Eq. 4 has with discount factor γ eval , it's better to use some γ ≤ γ eval because it reduces the average deviation in the value functions.

For a given environment, with fear model F 1 and discount factor γ 1 , let

V π * F 2 ,γ 2

F1,γ1 (s), s ∈ S, denote the state value function under the optimal policy of a environment with fear model F 2 and the discount factor γ 2 . On the same environment, let ω

π * F 2 ,γ 2 F1

(s) denote the stationary distribution over states. Therefore we are interested in the average deviation on value functions caused by imperfect classifier:

L(F, F , γ eval , γ) := (1 -γ eval ) s∈S ω π * F ,γ F (s) V π * F,γ eval F,γ eval (s) -V π * F ,γ F,γ eval (s) ds

Theorem 2. For a given MDP model, the average deviation on the value functions, L(F, F , γ eval , γ), F, F ∈ F, vanishes as the number of samples N increases

EQUATION

with probability at least 1 -δ. VC(F) is the VC dimension of the hypothesis class F.

Proof. Appendix B Thm. 2, holds for both tabular MDPs and continuous state-action MDPs. In addition to proofs of these results, we provide a deeper theoretical analysis on deterministic and stochastic fear models in the tabular setting in Appendix B.

Over the course of our experiments, we discovered the following pattern: Intrinsic fear models are more effective when the fear radius k r is large enough that the model can experience danger states at a safe distance and correct the policy, without experiencing many catastrophes. When the fear radius is too small, the danger probability is only nonzero at states from which catastrophes are inevitable anyway and intrinsic fear seems not to help. We also found that wider fear factors train more stably when phased in over the course of many episodes. So, in all of our experiments we gradually phase in the fear factor λ from 0 to λ reaching full strength at predetermined time step k λ . In our Cart-Pole experiments, we phase λ in over 1M steps.

3. ENVIRONMENTS:

We demonstrate our algorithms on three environments. These include Adventure Seeker, a toy pathological environments which we designed to demonstrate the Sisyphean curse; Cartpole, a classic reinforcement learning environment; and three Atari games, Seaquest, Asteroids, and Freeway, simulated in the Arcade Learning Environment (Bellemare et al., 2013) .

Adventure Seeker We imagine a player placed on a hill, sloping upward to the right (Figure 1a ). At each turn, the player can move to the right (up the hill) or left (down the hill). The environment adjusts the player's position accordingly, adding some random noise. Between the left and right edges of the hill, the player gets more reward for spending time higher on the hill. But if the player goes too far to the right, he/she will fall off (a catrastrophic state), terminating the episode and receiving a return of 0. This game admits an obvious analytic solution; There exists some threshold above which the agent should always choose to go left, and below which it should always go right. And yet a state-of-the-art DQN model learning online or with experience replay successively plunges to its death. To be clear, the DQN does learn a near-optimal thresholding policy quickly. But over the course of continued training, the agent oscillates between a reasonable thresholding policy and one which always moves right, regardless of the state. The pace of this oscillation evens out and all networks (over multiple runs) quickly reach a constant catastrophe per turn rate that does not attenuate with continued training. How could we trust a system that can't solve Adventure Seeker to make consequential decisions?

Cart-Pole In this classic RL environment, an agent balances a pole atop a cart (Figure 1b ). Qualitatively, the game exhibits four distinct catastrophe modes. The pole could fall down to the right or fall down to the left. Additionally, the cart could run off the right boundary of the screen or run off the left. Formally, at each time, the agent observes a four-dimensional state vector (x, v, θ, ω) consisting respectively of the cart position, cart velocity, pole angle, and the pole's angular velocity. At each time step, the agent chooses an action, applying a force of either -1 or +1. For every time step that the pole remains upright and the cart remains on the screen, the agent receives a reward of 1. If the pole falls, the episode terminates, giving a return of 0 from the penultimate state. In experiments, we use the implementation CartPole-v0 contained in the openAI gym (Brockman et al., 2016) . Like Adventure Seeker, this problem admits an analytic solution. A perfect policy should never drop the pole. But, as with Adventure Seeker, a DQN converges to a constant rate of catastrophes per turn.

Atari games In addition to these pathological cases, we address Freeway, Asteroids, and Seaquest, games from the Atari Learning Environment. In Freeway, the agent controls a chicken with a goal of crossing the road while dodging traffic. The chicken loses a life and starts from the original location if hit by a car. Points are only rewarded for successfully crossing the road. In Asteroids, the agent pilots a ship and gains points from shooting the asteroids. She must avoid colliding with asteroids which cost it lives. In Seaquest, a player swims under water. Periodically, as the oxygen gets low, she must rise to the surface for oxygen. Additionally, fishes swim across the screen. The player gains points each time she shoots a fish. Colliding with a fish or running out of oxygen result in death. In all three games, the agent has 3 lives, and the final death is a terminal state. We label each loss of a life as a catastrophe state.

4. EXPERIMENTS:

To assess the effectiveness of the intrinsic fear model, we evaluate both a standard DQN (DQN-NoFear) and one enhanced by intrinsic fear (DQN-Fear). In both cases, we use multilayer perceptrons (MLPs) with a single hidden layer and 128 hidden nodes. We train all MLPs by stochastic gradient descent using the Adam optimizer Kingma and Ba (2015) to adaptively tune the learning rate. Figure 2 : Catastrophes and reward/episode for DQNs and Intrinsic Fear. On Adventure Seeker, all Intrinsic Fear models cease to "die" within 14 runs, giving unbounded (unplottable) reward thereafter.

On Seaquest, the IF model achieves a similar catastrophe rate but significantly higher total reward. On Asteroids, the IF model outperforms DQN. For Freeway, a randomly exploring DQN (under our time limit) never gets reward but IF model learns successfully.

Because, for the Adventure Seeker problem, an agent can escape from danger with only a few time steps of notice, we set the fear radius k r to 5. We phase in the fear factor quickly, reaching full strength in just 1000 moves. On this problem we set the fear factor λ to 40.

For Cart-Pole, we set a wider fear radius of k r = 20. We initially tried training this model with a shorter fear radius but made the following observation. Some models would learn surviving for millions of experiences, with just a few hundred catastrophes. This compared to a DQN (Figure 2 ) which would typically suffer 4000-5000 catastrophes. When examining the output from the fear models on successful vs unsuccessful runs, we noticed that the unsuccessful models would output danger of probability greater than .5 for precisely the 5 moves before a catastrophe. But by that time it would be too late for an agent to correct course. In contrast, on the more successful runs, the fear model typically outputs predictions in the range .1 -.5. We suspect that the gradation between mildly dangerous states and those with imminent danger provides a richer reward signal to the DQN.

On both the Adventure Seeker and Cart-Pole environments, the DQNs augmented by intrinsic fear far outperform their otherwise identical counterparts (Figure 2 ). We cannot plot the reward per episode for the intrinsic fear models on these environments because after the first several deaths, the episodes never terminate. In contrast, both the DQN and related approaches like expected SARSA continue to visit the catastrophic states regularly. We compared our approach against some traditional approaches for mitigating catastrophic forgetting. For example, we tried a memory-based method in which we preferentially sample the catastrophic states for updating the model, but they did not improve over the DQN. It seems that the notion of a danger zone is necessary here.

For Seaquest, Asteroids, and Freeway, we use a fear radius of 5 and a fear factor of .5. For all Atari games, the IF models outperform their DQN counterparts. Interestingly while for all games, the IF models achieve higher reward, on Seaquest, models trained with Intrinsic Fear have similar catastrophe rates. More precisely, they appear to have fewer catastrophes early on but eventually enter a different reward regime, exchanging more catastrophes for higher reward. This result suggests an interplay between the various reward signals that warrants further exploration. For Asteroids and Freeway, the improvements are more dramatic. Over just a few thousand episodes of Freeway, a randomly exploring DQN achieves zero reward. However, the reward shaping of intrinsic fear leads to rapid improvement.

5. RELATED WORK:

The paper addresses safety in RL, intrinsically motivated RL, and the stability of Q-learning with function approximation under distributional shift. Our work also has some connection to reward shaping. We attempt to highlight the most relevant papers here. Several papers address safety in RL. (Garcıa and Fernández, 2015) provide a thorough review on the topic, identifying two main classes of methods: those that perturb the objective function and those that use external knowledge to improve the safety of exploration.

While a typical reinforcement learner optimizes expected return, some papers suggest that a safely acting agent should also minimize risk. (Hans et al., 2008) defines a fatality as any return below some threshold τ . They propose a solution comprised of a safety function, which identifies unsafe states, and a backup model, which navigates away from those states. Their work, which only addresses the tabular setting, suggests that an agent should minimize the probability of fatality instead of maximizing the expected return. Heger (1994) suggests an alternative Q-learning objective concerned with the minimum (vs expected) return.Other papers suggest modifying the objective to penalize policies with high-variance returns (Garcıa and Fernández, 2015) . Maximizing expected returns while minimizing their variance is a classic problem in finance, where a common objective is the ratio of expected return to its standard deviation (Sharpe, 1966) . (Moldovan and Abbeel, 2012) gives a definition of safety based on ergodicity. They consider a fatality to be a state from which one cannot return to the start state. Shalev-Shwartz et al. ( 2016) theoretically analyzes how strong a penalty should be to discourage accidents. They also consider hard constraints to ensure safety. None of the above works address the case where distributional shift dooms an agent to perpetually revisit known catastrophic failure modes. Other papers incorporate external knowledge into the exploration process.

Typically, this requires access to an oracle or extensive prior knowledge of the environment. In the extreme case, some papers suggest confining the policy search to the subset of policies known to be safe. For reasonably complex environments or classes of policies this seems infeasible.

The potential oscillatory or divergent behavior of Q-learners with function approximation has been previously identified (Boyan and Moore, 1995; Baird et al., 1995; Gordon, 1996) . Outside of RL, the problem of covariate shift has been extensively studied (Sugiyama and Kawanabe, 2012) . Murata and Ozawa (2005) addresses the problem of catastrophic forgetting owing to distributional shift in RL with function approximation, proposing a memory-based solution. Many papers address intrinsic rewards, which are internally assigned, vs the standard (extrinsic) reward. Typically, intrinsic rewards are used to encourage exploration (Schmidhuber, 1991; Bellemare et al., 2016) and to acquire a modular set of skills (Chentanez et al., 2004) . Some papers refer to the intrinsic reward for discovery as curiosity. Like classic work on intrinsic motivation, our methods perturb the reward function.

But instead of assigning bonuses to encourage discovery of novel transitions, we assign penalties to discourage catastrophic transitions.

Key differences:

In this paper, we undertake a novel treatment of safe reinforcement learning, While the literature offers several notions of safety in reinforcement learning, we see the following problem: Existing safety research that perturbs the reward function requires little foreknowledge, but fundamentally changes the objective globally. On the other hand, processes relying on expert knowledge may presume an unreasonable level of foreknowledge. Moreover, little of the prior work on safe reinforcement learning, to our knowledge, specifically addresses the problem of catastrophic forgetting. This paper proposes a new class of algorithms for avoiding catastrophic states and a theoretical analysis supporting its robustness.

6. CONCLUSIONS:

Our experiments demonstrate that DQNs are susceptible to periodically repeating mistakes, however bad, raising questions about their real-world utility when harm can come of actions. While it's easy to visualize these problems on toy examples, similar dynamics are embedded in more complex domains. Consider a domestic robot acting as a barber. The robot might receive positive feedback for giving a closer shave. This reward encourages closer contact at a steeper angle. Of course, the shape of this reward function belies the catastrophe lurking just past the optimal shave. Similar dynamics might be imagines in a vehicle that is rewarded for traveling faster but could risk an accident with excessive speed. Our results with the intrinsic fear model suggest that with only a small amount of prior knowledge (the ability to recognize catastrophe states after the fact), we can simultaneously accelerate learning and avoid catastrophic states. This work represents a first step towards combating some issues relating to safety in RL stemming from catastrophic forgetting.

A LOSS IN OPTIMAL VALUE (PROOF OF THEOREM 1)

The average return of the reward under a policy π is as follows:

EQUATION

Let us assume that any stationary policy π induces a stationary distribution ω π (s), s ∈ S. Therefore we can rewrite Eq. 7 in terms of stationary distribution (Puterman, 2014) .

η M (π) = lim T →∞ 1 T E t r t |π = s∈S a∈A ω π (s)π(a|s)R(s, a) .

In RL, we are interested in a policy π * that maximizes the expected average reward:

π * := arg max π η M (π) . Denote η * M = η M (π * ).

In a first place, the optimization in Eq. 7 looks linear in π but actually the policy π derives the stationary distribution ω π (•), which makes the optimization problem harder.

Given the policy π, let's define the joint distribution in (s, a) as follows: µ π (s, a) := P(s, a|π) = ω π (s)π(a|s), ∀s ∈ S, a ∈ A .

Then we can rewrite the optimization problem in terms of the joint probability distribution µ π .

EQUATION

We can see that this new formalization, turns our optimization objective into a linear function of µ π . Since µ π is a join distribution of (s, a) under the model dynamics T , it can not take any arbitrary value. Let ∆ denote the set of feasible value for µ π , then This change of variable allows us to analyze the introduction of intrinsic fear in different situations. Among all the optimal policies of Eq. 7, consider the one which minimizes := s∈C,a µ π * (s, a).

∆ := {µ : µ ≥ 0,

let's assume that the negative reward assigned to the states in the danger zone is λ(R max -R min ) and the optimal policy π of the environment with the intrinsic fear has return of η M,F (π).

Applying policy π * on the environment with intrinsic fear gives a return of η * M -λ (R max -R min ). Therefore, the return of π on the environment with intrinsic fear, η M,F , is lower bounded by η * M -λ (R max -R min ). Therefore, applying π on the environment without intrinsic fear gives a return of η M (π) which is lower bounded by η

EQUATION

A.1 DISCOUNTED CUMULATIVE REWARD For the γ-discounted setting, we are interested in

EQUATION

The above mentioned equations hold in this setting as well, i.e., η

* M ≥ η M (π) ≥ η M,F (π) ≥ η * M -λ (R max -R min ).

B IMPERFECT CLASSIFIER (PROOF OF THEOREM 2):

In the previous section, we assumed that we have access to the perfect classifier F which can exactly label the danger zone. This assumption does not hold in real world where we train the classifier. In this section we derive an analysis in order to show that imperfect classifier F can not change the overall performance by much.

In general, in practical RL problems, we use discount factors γ eval < 1 (Kocsis and Szepesvári, 2006) in order to reduce the planing horizon, and computation cost. Moreover, (Jiang et al., 2015) suggest that when we have an estimation (up to the confidence intervals) of our MDP model, it is better to use γ ≤ γ eval . They show that since larger discount factor enriches the class of optimal policies for a given set of plausible models, large discount factors enrich models and end up over fitting to the noisy estimate of the environment.

In this section, we show how to choose the discount factor γ ≤ γ eval such that the learned Value function stays close to the Value function under the perfect classifier

EQUATION

s), s ∈ S, denote the state value under the optimal policy of model with classifier F 1 under the discount factor γ 1 on the environment equipped with classifier F and discount factor γ 2 . On the same environment, ω π * F 1 ,γ 1 F2 (s) denotes the stationary distribution over states. We are interested in the average deviation on value functions caused by the imperfect classifier:

L := (1 -γ eval ) s∈S ω π * F ,γ F (s) V π * F,γ eval F,γ eval (s) -V π * F ,γ F,γ eval (s)

This quantity can be upper bounded by

L ≤ (1 -γ eval ) V π * F,γ eval F,γ eval -V π * F ,γ F,γ eval ∞ (12)

The goal is to find an γ * which minimizes this loss, i.e. γ * = argmin γ≤γ eval L with high probability. For simplicity and without loss of generality, let's assume that all the rewards, including the intrinsic fears, are in [0, 1] and call λ , the transformed version of λ2 . One can decompose the upper bound in Eq. 12 as follows:

EQUATION

The first term is the deviation on value function when applying same policy on the same environment but with different discount factors. Since γ ≤ γ eval we have

EQUATION

The second part of Eq. 13 is the deviation in value function under different policies and different classifiers. Again, since γ ≤ γ eval , we have

EQUATION

where the last inequality is due to the optimality of π * F,γ on the environment of F, γ. To bound this part we exploit the proof trick used in (Jiang et al., 2015) .

V π * F,γ F,γ (s) -V π * F ,γ F,γ (s) = V π * F,γ F,γ (s) -V π * F,γ F ,γ (s) + V π * F,γ F ,γ (s) -V π * F ,γ F ,γ (s) + V π * F ,γ F ,γ (s) -V π * F ,γ F,γ (s) (17)

since the middle term is negative we have

EQUATION

This quantity V π F ,γ (s) -V π F,γ (s) is the difference between the performance of the same policy on two different environments. These two values functions should satisfy the following bellman equations: As i tends to infinity, these two dynamics updates converge to V π F,γ (s), and V π F ,γ (s) respectively. To bound the right hand side of Eq. 18 we have

EQUATION

EQUATION

As i tends to infinity, we have 

V π * F,γ F,γ (s) -V π * F ,γ F,γ (s) = max π lim i→∞ V π i (s) -V π i (s) ≤ λ i i =0 γ i max

with probability δ where N (s) is the number visits to a state s at time step N . The trajectory produced by algorithm does not produce i.i.d. samples of state. Therefore, for Eq. 20 we use Hoeffding's inequality accompanied with union bound over time N . In order to have this bound to hold for all the states at once, we need another union bounds over states and all possibly optimal policies Π γ under noisy classifier , which requires to replace δ → δ/SAΠ γ . Let's assume a minimum number of visit N to each state,

EQUATION

Finally, adding Eq. 14 and Eq. 21, the upper bound on L is as follows: 

L ≤ λ 1 -γ eval 1 -γ log N SAΠγ 1-δ N + γ eval -γ 1 -γ B.

F:

. Given a policy π, the MDP transition process reduces to a Markov chain with transition probability T π . Now we rewrite the Eq. 19 in a matrix format where V π i , F ∈ R S are vectors of concatenation of V π i (s) and F (s), ∀s ∈ S respectively.

EQUATION

as i goes to infinity we have

V π * F,γ F,γ -V π * F ,γ F,γ ≤ λ (1 -γT π ) -1 F -F

Using PAC analysis of binary classification in (Hanneke, 2016) a follow up to (Vapnik, 2013) , we have

F -F ω π * F ,γ

≤ 3200 VC(F) + log 1 δ N with probability at least 1 -δ where VC(F) is the VC dimension of the hypothesis class and | • | is entry-wise absolute value. Since γ < 1, then α max , the maximum eigenvalue of (1 -γT π )

-1 , is bounded above and we have The same analysis, up to a slight modification3 , holds for the continuous state and action spaces.

:

In the stochastic dynamics setting, the distance is the minimum mean passing time between the states.

Shifting and then rescaling the reward is equivalent to shifting and rescaling the Q and Value function, and does not change the optimal policy. Moreover the mentioned transformation is r → (r -(Rmin -λ(Rmax -Rmin)))/((Rmax -Rmin)(1 + λ)), therefore, λ = λ/(1 + λ)

Instead of having V as a vector of state values indexed by states, it is a continuous function of states. Furthermore, the Transition kernel is over continuous distribution therefore the same bellman update in Eq. 22 holds.

Figures and Tables:

Figure 1: In experiments, we consider two toy environments (a,b) and the Atari games Seaquest (c), Asteroids (d), and Freeway (e)state s t , T (s t+1 |s t , a t ) gives successor state s t+1 ← s t + .01 • a t + η where η ∼ N (0, .01 2 ). The reward at each turn is equal to s t (proportional to height). The player falls off the hill, entering the catastrophic terminating state, whenever s t+1 > 1.0 or s t+1 < 0.0.

(s |s, a)µ(s, a), ∀s ∈ S} . (9)Clearly, ∆ is a polytope on the simplex in R S×A . Now, we can rewrite the optimization problem Eq. 7 as a constrained linear program on µ π :

s) = R(s, π(s)) + λ F (s) + γ s ∈S T (s |s, π(s))V π F,γ (s ) V π F ,γ (s) = R(s, π(s)) + λ F (s) + γ s ∈S T (s |s, π(s))V π F ,γ (s )To compute the solution two this equation, we use dynamic programing. Let initialize V 0 , V = V (an arbitrary value) and construct the following updates.for i ∈ {1, . . . ∞} V π i (s) = R(s, π(s)) + λ F (s) + γ s ∈S T (s |s, π(s))V π i-1 (s) V π i (s) = R(s, π(s)) + λ F (s) + γ s ∈ST (s |s, π(s)) V π i-1 (s )

The remaining part is to solve γ * = argmin γ≤γ eval L to find the optimal γ.

Two models: Q (DQN) and F (fear model), fear factor λ, fear phase-in length k λ , fear radius k r 2: Output: Learned parameters θ Q and θ F 3: Initialize parameters θ Q and θ F randomly 4: Initialize replay buffer D, danger state buffer D D , and safe state buffer D S 5: Start per-episode turn counter n e 6: for t in 1:T do Otherwise, select action a t = argmax a Q(s t , a ; θ Q ) Execute action a t in environment, observing reward r t and successor state s t+1 10: Store transition (s t , a t , r t , s t+1 ) in D Add states s t-kr through s t to D D Add states s t-ne through s t-kr-1 to D S 15:Sample random minibatch of transitions (s τ , a τ , r τ , s τ +1 ) from D

Table content: <table><tr><td>7:</td><td>With probability select random action a t</td></tr><tr><td>8:</td><td/></tr><tr><td>9:</td><td/></tr><tr><td>11:</td><td>if s t+1 is a catastrophe state then</td></tr><tr><td>12:</td><td/></tr><tr><td>13:</td><td>else</td></tr><tr><td>14:</td><td/></tr><tr><td>16:</td><td/></tr></table>

TABLE CLASSIFIER If we consider the fear model as a lookup table, and deterministic, then observing each state once is enough to exactly recover the classifier.

Table content: <table/>

2 CLASSIFIER FROM A SET OF FUNCTIONSLet F denote a set of given binary classifiers and F ∈ F. In this case, let's assume that we are given a set of N i.i.d samples from the stationary distribution ω

Table content: <table><tr><td>π  *  F ,γ</td></tr></table>

Peer review (iclr2018):
 The paper addresses the problem of learners forgetting rare states and revisiting catastrophic danger states. The authors propose to train a predictive ‘fear model’ that penalizes states that lead to catastrophes. The proposed technique is validated both empirically and theoretically. Experiments show a clear advantage during learning when compared with a vanilla DQN. Nonetheless, there are some criticisms than can be made of both the method and the evaluations: The fear radius threshold k_r seems to add yet another hyperparameter that needs tuning. Judging from the description of the experiments this parameter is important to the performance of the method and needs to be set experimentally. There seems to be no way of a priori determine a good distance as there is no way to know in advance when a catastrophe becomes unavoidable. No empirical results on the effect of the parameter are given. The experimental results support the claim that this technique helps to avoid catastrophic states during initial learning.The paper however, also claims to address the longer term problem of revisiting these states once the learner forgets about them, since they are no longer part of the data generated by (close to) optimal policies. This problem does not seem to be really solved by this method. Danger and safe state replay memories are kept, but are only used to train the catastrophe classifier. While the catastrophe classifier can be seen as an additional external memory, it seems that the learner will still drift away from the optimal policy and then need to be reminded by the classifier through penalties. As such the method wouldn’t prevent catastrophic forgetting, it would just prevent the worst consequences by penalizing the agent before it reaches a danger state. It would therefore be interesting to see some long running experiments and analyse how often catastrophic states (or those close to them) are visited. Overall, the current evaluations focus on performance and give little insight into the behaviour of the method. The paper also does not compare to any other techniques that attempt to deal with catastrophic forgetting and/or the changing state distribution ([1,2]). In general the explanations in the paper often often use confusing and imprecise language, even in formal derivations, e.g. ‘if the fear model reaches arbitrarily high accuracy’ or ‘if the probability is negligible’. It is wasn’t clear to me that the properties described in Theorem 1 actually hold. The motivation in the appendix is very informal and no clear derivation is provided. The authors seem to indicate that a minimal return can be guaranteed because the optimal policy spends a maximum of epsilon amount of time in the catastrophic states and the alternative policy simply avoids these states. However, as the alternative policy is learnt on a different reward, it can have a very different state distribution, even for the non-catastrophics states. It might attach all its weight to a very poor reward state in an effort to avoid the catastrophe penalty. It is therefore not clear to me that any claims can be made about its performance without additional assumptions. It seems that one could construct a counterexample using a 3-state chain problem (no_reward,danger, goal) where the only way to get to the single goal state is to incur a small risk of visiting the danger state. Any optimal policy would therefore need to spend some time e in the danger state, on average. A policy that learns to avoid the danger state would then also be unable to reach the goal state and receive rewards. E.g pi* has stationary distribution (0,e,1-e) and return 0*0+e*Rmin + (1-e)*Rmax. By adding a sufficiently high penalty, policy pi~ can learn to avoid the catastrophic state with distribution (1,0,0) and then gets return 1*0+ 0*Rmin+0*Rmax= 0 < n*_M - e (Rmax - Rmin) = e*Rmin + (1-e)*Rmax - e (Rmax - Rmin). This seems to contradict the theorem. It wasn’t clear what assumptions the authors make to exclude situations like this. [1] T. de Bruin, J. Kober, K. Tuyls and R. Babuška, "Improved deep reinforcement learning for robotics through distribution-based experience retention," 2016 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), Daejeon, 2016, pp. 3947-3952. [2] Kirkpatrick, J., Pascanu, R., Rabinowitz, N., Veness, J., Desjardins, G., Rusu, A. A., ... & Hassabis, D. (2017). Overcoming catastrophic forgetting in neural networks. Proceedings of the National Academy of Sciences, 201611835.