Title: SAFE POLICY LEARNING FROM OBSERVATIONS

Abstract: In this paper, we consider the problem of learning a policy by observing numerous non-expert agents. Our goal is to extract a policy that, with high-confidence, acts better than the agents' average performance. Such a setting is important for real-world problems where expert data is scarce but non-expert data can easily be obtained, e.g. by crowdsourcing. Our approach is to pose this problem as safe policy improvement in reinforcement learning. First, we evaluate an average behavior policy and approximate its value function. Then, we develop a stochastic policy improvement algorithm that safely improves the average behavior. The primary advantages of our approach, termed Rerouted Behavior Improvement (RBI), over other safe learning methods are its stability in the presence of value estimation errors and the elimination of a policy search process. We demonstrate these advantages in the Taxi grid-world domain and in four games from the Atari learning environment.

1. INTRODUCTION:

Recent progress in Reinforcement Learning (RL) has shown a remarkable success in learning to play games such as Atari from raw sensory input (Mnih et al., 2015; Hessel et al., 2017) . Still, tabula rasa, RL typically requires a significant amount of interaction with the environment in order to learn. In real-world environments, particularly when a risk factor is involved, an inept policy might be hazardous (Shalev-Shwartz et al., 2016) . Thus, an appealing approach is to record a dataset of other agents in order to learn a safe initial policy which may later be improved via RL techniques (Taylor et al., 2011) .

Learning from a dataset of experts has been extensively researched in the literature. These learning methods and algorithms are commonly referred to as Learning from Demonstrations (LfD) (Argall et al., 2009) . In this paper, we consider a sibling, less explored problem of learning form a dataset of observations (LfO). We define LfO as a relaxation of LfD, where: (1) we do no assume a single policy generating the data and; (2) the policies are not assumed to be optimal, nor do they cover the entire state space. Practically, LfO is of interest since it is often easier to collect observations than expert demonstrations, for example, using crowdsourcing (Kurin et al., 2017) . Technically, LfO is fundamentally different from LfD, where the typical task is to clone a single expert policy. The data under the LfO setting is expected to be more diverse than LfD data, which in general can be beneficial for learning. However, it also brings in the challenge of learning from multiple, possibly contradicting, policy trajectories.

In this work, we propose to solve the LfO problem with a three phases approach: (1) imitation (2) annotation and; (3) safe improvement. The imitation phase seeks to learn the average behavior in the dataset. In the annotation part we approximate the value function of the average behavior and in the final safe improvement step (section 5), we craft a novel algorithm that takes the learned average behavior and its approximated value function and yields an improved policy without generating new trajectories. The improvement step is designed to increase the policy performance with a high confidence in the presence of the value estimation errors that exists in a LfO setup.

Our three phases approach which we term Rerouted Behavior Improvement (RBI), provides a robust policy (without any interaction with the environment), that both eliminates the risks in random policy initialization and in addition, can boost the performance of a succeeding RL process. We demonstrate our algorithm both in a Taxi grid-world (Dietterich, 2000) as well as in the Atari domain (section 6). In the latter, we tackle the challenge of learning from non-experts human players (Kurin et al., 2017) . We show that our algorithm provides a robust policy, on par with deep RL policies, using only the demonstrations and without any additional interaction with the environment. As a baseline, we compare our approach to two state-of-the-art algorithms: (1) learning from demonstrations, DQfD (Hester et al., 2018)  and ; (2) robust policy improvement, PPO (Schulman et al., 2017) .

2. RELATED WORK:

Learning from demonstrations in the context of deep RL in the Atari environment have been studied in Cruz Jr et al. (2017) , DQfD (Hester et al., 2018) and recently in Pohlen et al. (2018) . However, all these methods focus on expert demonstrations and they benchmark their scores after additional trajectory collection with an iterative RL process. Therefore, essentially these methods can be categorized as a RL augmented with expert's supervised data. In contrast, we take a deeper look into the first part of best utilizing the observed data to provide the highest initial performance.

Previously, LfO has often been solved solely with the imitation step, e.g. in AlphaGo (Silver et al., 2016) , where the system learned a policy which mimics the average behavior in a multiple policies dataset. While this provides sound empirical results, we found that one can do better by applying a safe improvement step to boost the policy performance. A greedy improvement method with respect to multiple policies has already been suggested in Barreto et al. ( 2017), yet we found that practically, estimating the value function of each different policy in the dataset is both computationally prohibitive and may also produce large errors since the generated data by each different policy is typically small. In section 4 we suggest a feasible alternative. Instead of learning the value of each different policy, estimate the value of the average behavior. While such estimation is not exact, we show both theoretically and experimentally that it provides a surrogate value function that may be used for policy improvement purposes.

There is also a significant research in the field of safe RL (Garcıa & Fernández, 2015) , yet, here there may be multiple accepted definitions of this term ranging from worst-case criterion (Tamar et al., 2013) to baseline benchmark approach (Ghavamzadeh et al., 2016) . We continue the line of research of safe RL investigated by Kakade & Langford (2002) ; Pirotta et al. (2013) ; Thomas et al. (2015) but we focus on a dataset composed of unknown policies. Finally, there are two recent well-known works in the context of non-decreasing policy improvement (also can be categorized as safe improvement) TRPO and PPO (Schulman et al., 2015; 2017) . We compare our work to these algorithms and show two important advantages: First, our approach can be applied without an additional Neural Network (NN) policy optimization step and second we provide theoretical and experimental arguments why both approaches may be deemed unsafe when applied in the context of a LfO setup.

3. PROBLEM FORMULATION:

We are dealing with a Markov Decision Process (MDP) (Puterman, 2014) where an agent interacts with an environment and tries to maximize a reward. A MDP is defined by the tuple (S, A, P, R), where S is a set of states and A is a set of actions. P : S × A → S is the set of probabilities of switching from a state s to s when executing action a, i.e. P (s |s, a) and R is a reward function S × A → R which defines the reward r that the agent gets when applying action a in state s. An agent acts according to a policy π, and its goal is to find a policy that maximizes the expected cumulative discounted reward, also known as the objective function J(π) = E ∞ k=0 γ k r k s 0 , π where γ < 1 is a discount factor, k is a time index and s 0 is an initial state.

We assume that all policies belong to the Markovian randomized set Π M R s.t. π ∈ Π M R is a probability distribution over A given a state s, i.e. π (a|s).1 For convenient and when appropriate, we may simply write π i to denote π(a i |s) (omitting the state's dependency). In the paper we will discuss two important distance measures between policies. The first is the Total Variation (TV)

δ(π, π ) = 1 2 ai |π i -π i | and the second is the KL divergence D KL (π||π ) = -ai π i log π i πi .

These measures are often used to constrain the updates of a learned policy in an iterative policy improvement RL algorithm (Schulman et al., 2015; 2017) .

For a given policy, the state's value is the expected cumulative reward starting at this state,

V π (s) = E ∞ k=0 γ k r k s, π . Similarly, the Q-value function Q π (s, a)

is the value of taking action a in state s and then immediately following with policy π. The advantage A π (s, a) = Q π (s, a) -V π (s) is the gain of taking action a in state s over the average value (note that a∈A π(a|s)A π (s, a) = 0).

We denote by P (s 0 k -→ s|π) the probability of switching from state s 0 to state s in k steps with a policy π.

We define the LfO problem as learning a policy π solely by observing a finite set of trajectories of other behavior policies without interacting with the environment. Formally, we are given a dataset D of trajectories executed by N different players each with a presumably different policy. Players are denoted by p i , i = 1, ..., N , and their corresponding policies are β i , with value and Q-value

functions V i , Q i respectively. D is indexed as {x j } |D| j=0

, where the cardinality of the dataset is denoted by |D| and each record is the tuple x j = (s j , a j , r j , t j , i j ) s.t. t j is a termination signal and i j is the player's index. D may also be partitioned to D = {D i |i = 1, .., N }, representing the different players' records.

R G Y B:

Figure 1 : Taxi world

The paper is accompanied with a running example, based on the Taxi grid-world domain (Dietterich, 2000) , In the Taxi world, the driver's task is to pickup and drop a passenger in predefined locations with minimal number of steps (See figure 1 ). For this example, we synthetically generated policies of the form

β i = α i (s)π rand + (1 -α i (s))π *

, where π * is the optimal policy and α i (s) is a different mixing parameter for each different policy. Generally we divide the state space into two complementary and equal-size sets

S * i ∪ S * i = S, |S * i |= | S * i |.

Where α i (s) = 0 for s ∈ S * i and α i (s) = 0.75 for s ∈ S * i . In the next sections, we will use different selections of S * i to generate different types of datasets. For example, randomly pick half of the states to form S * i is termed in the paper as a random selection (see also appendix).

4. AVERAGE BEHAVIOR POLICY AND ITS VALUE FUNCTION:

We begin with the first phase of the RBI approach which is learning a behavior policy from the dataset. Learning a behavior policy is a sensible approach both for generating a sound initial performance, as well as to avoid unknown states and actions. Yet, contrary to LfD where a single expert policy is observed, in multiple policies dataset the definition of a behavioral policy is ambiguous. To that end, we define the average behavior of the dataset as a natural generalization of the single policy imitation problem. Definition 4.1 (Average Behavior). The average behavior of a dataset D is

EQUATION

where 1 s,a (j) = 1 if (s j , a j ) = (s, a), and 0 otherwise. The first form in Eq. equation 4.1 is simply the fraction of each action taken in each state in D, which for a single policy dataset is identical to behavioral cloning. Typically, when β is expressed with a NN (as in section 6) we apply a standard classification learning process with a Cross Entropy loss. Otherwise, for a tabular representation (as in the Taxi example) we directly enumerate to calculate this expression. The second form in Eq. equation 4.1 is a weighted sum over all players in the dataset, which may also be expressed with conditional probability terminology as

EQUATION

Here P p i |s is the probability of visiting an ith player's record given that a uniform sample x ∼ U (D) picked s. While other definitions of average behavior are possible, the ease of learning such formulation with a NN makes it a natural candidate for RBI. Yet, for the second phase of RBI, one must evaluate its Q-value function, i.e. Q β . To that end, we study two alternatives: (1) Temporal Difference (TD) learning and (2) Monte-Carlo (MC) approximation.

4.1 LEARNING Q β WITH TD METHODS A natural approach to evaluate Q β , would be with off-policy TD learning (Sutton & Barto, 2017) . However, directly learning Q β requires the knowledge of β which can only be approximated in LfO.

To skirt this requirement, we can first evaluate V β over the distribution of states in D with one-step TD. This is attained by minimizing the loss E s∼U (D) |V β (s) -r(s, a) -γV β (s )| 2 where s, a, s are tuples of state-action and next state sampled from D. Notice that since the distribution of actions in each state in the dataset equals to β, there is no requirement for Importance Sampling (IS) factor.

With V β at hand, Q β can be learn by minimizing the loss

EQUATION

)

While this TD method avoids IS calculation and doe not require any β knowledge, it may still be problematic in LfO due to the bootstrapping operation. Bootstrapping is the practice of estimating the value of s from the estimations of the next state s . If our evaluation of s is incorrect, this error also propagates to s. Unlike, iterative RL this cannot be compensated by visiting again in s and updating the s value. In this sense, deep NN parametric forms are much more susceptible to bootstrapping since the evaluation error is larger comparing to a tabular representation (see also Sutton's Deadly Triad discussion in (Sutton & Barto, 2017) ).

4.2. APPROXIMATING:

Q β WITH MC LEARNING

As an alternative, to avoid bootstrapping we suggest to evaluate a surrogate function

EQUATION

which we term the Q-value of the dataset. Q D may be interpreted as the weighted average over the players' Q-values, where the weights P p i |s, a are the probability of visiting an ith player's record given that a uniform sample x ∼ U (D), picked s, a. In the following two propositions, we show that such a function has two appealing characteristics. First, it may be evaluated with a L 1 -norm loss and Monte-Carlo (MC) learning (Sutton & Barto, 2017) from the dataset trajectories, without off-policy corrections and without the burden of evaluating each Q i independently. Secondly, it is a Q-value function of a time dependent policy with a very similar structure to the average behavior. Taken together, they provide an efficient alternative to approximate the value function of β.

Proposition 4.1 (Consistency of MC upper bound). For an approximation QD and a loss

EQUATION

where R j = k≥0 γ k r j+k is the sampled Monte-Carlo return (Proof in the appendix).

The attractive implication of Proposition 4.1 is that we can learn Q D without any policy information and specifically without plugging Importance Sampling (IS) corrections such as β β i which are known as a source of high variance (Munos et al., 2016) . In addition, as suggested, this method does not use bootstrapping. The next proposition defines a policy with a Q-value equal to Q D . Proposition 4.2. Given a state-action pair s, ã, then Q D (s, ã) is the Q-value of a time dependent policy β D s,ã (a|s, k), where k is a time index and s, ã is a fixed initial state-action pair,

EQUATION

Here the conditional probability is over a uniform sample x ∼ U (D s,ã,k ) where D s,ã,k is a subset of D that contains all the entries in the dataset with distance k from an entry with a state-action pair s, ã (Proof in the appendix).

Proposition 4.2 indicates that when P (p i |s, ã k -→ s) can be approximated as P p i |s at least for a finite horizon k ∝ 1 1-γ , then Q D Q β . This happens when the distribution of players in states near s, ã equals to the distribution of players in those states in the entire dataset. Practically, while both policies are not equal, they have a relatively low TV distance and therefore their Q-values are close. To further increase the robustness of our method we add an interesting consideration: our improvement step will rely only on the action ranking of the Q-value in each state, i.e. the order of {Q β (s, a i )} ai∈A (see next section). This, as we show hereafter, significantly increases the effective similarity between Q D and Q β .

We demonstrates the action ranking similarity between Q β and Q D in the Taxi grid-world example.

To that end, we generated trajectories with N players according to three selection types of S * i : (1) row selection (2) column selection and; (3) random selection. Each selection type provides a different class of policies and therefore form a different dataset (see exact definitions in the appendix). In the first experiment (Figure 2a ), we plot the average TV distance (for various initial states s), between β and β D s,ã , as a function of the time-step for N = 2. Generally it is low, but it may be questionable whether relying on the true value of Q D for the improvement step will provide adequate results. However, when we consider only the action ranking similarity (evaluated with the Pearson's rank correlation), we find even more favorable pattern.

First, in Figure 2b we plot the average rank correlation between Q β and Q D (for γ = 0.9) as a function of the number of different policies used to generate the dataset. It is evident that the rank correlation is very high and stable for any number of policies. In the second experiment, we generated N = 2 (Figure 2c ) and N = 10 (Figure 2d ) policies and examined the impact of different discount factors. Also here, for the majority of practical scenarios we observe sufficiently high rank correlation. Only for a very large discount factor (close to 1) the rank correlation reduces. This happens since the long horizon accumulates more error from the difference (in high k steps) in the TV distance. In conclusion, while Proposition 4.2 state bounds on the similarity between Q β and Q D , evaluating the Pearson's rank correlation confirms our statement that in practice the action ranking of Q D is an acceptable surrogate for the action ranking of Q β . 

5. SAFE POLICY IMPROVEMENT:

Our next step, is to harness the approximated Q-function Q D Q β (which here will be termed Q β ), in order to improve the average behavior β, i.e. generate a policy π such that J(π) -J(β) ≥ 0. However, one must recall that Q β is learned from a fixed, sometimes even small dataset. Therefore, in order to guarantee improvement, we analyze the statistics of the value function's error. This leads to an interesting observation: the Q-value has a higher error for actions that were taken less frequently, thus, to avoid improvement penalty, we must restrict the ratio of the change in probability c i = πi βi . We will use this observation to craft our third phase of RBI, i.e. the safe improvement step, and show that other well-known monotonic improvement methods (such as PPO (Schulman et al., 2017) and TRPO (Schulman et al., 2015) ) overlooked this consideration and therefore their improvement method may be unsafe for a LfO setup.

5.1. SOFT POLICY IMPROVEMENT:

Before analyzing the error's statistics, we begin by considering a subset of policies in Π M R which are proven to improve β if our estimation of Q β is exact. Out of this subset we will later pick our improved policy. Recall that the most naive and also common improvement method is taking a greedy step, i.e. deterministically acting with the highest Q-value action in each state. This is known by the policy improvement theorem (Sutton & Barto, 2017) , to improve the policy performance. The policy improvement theorem may be generalized to include a larger family of soft steps. Lemma 5.1 (Soft Policy Improvement). Given a policy β, with value and advantage V β , A β , a policy π ∈ Π M R improves β, i.e. V π ≥ V β ∀s, if it satisfies a π(a|s)A β (s, a) ≥ 0 ∀s with at least one state with strict inequality. The term a π(a|s)A β (s, a) is called the improvement step. 2Essentially, every policy that increases the probability of taking positive advantage actions over the probability of taking negative advantage actions achieves improvement. We will use the next Corollary to prove that our specific improvement step guarantees a positive improvement step.

Corollary 5.1.1 (Rank-Based Policy Improvement). Let (A i ) |A| i=1 be an ordered list of the β advan- tages in a state s, s.t. A i+1 ≥ A i , and let c i = π i /β i . If for all states (c i ) |A| i=1 is a monotonic non-decreasing sequence s.t. c i+1 ≥ c i , then π improves β (Proof in the appendix).

5.2. STANDARD ERROR OF THE VALUE ESTIMATION:

To provide a statistical argument for the expected error of the Q-function, consider learning Q β with a tabular representation. The Q-function is the expected value of the random variable z π (s, a) = k≥0 γ k r k |s, a, π. Therefore, the Standard Error (SE) of an approximation Qβ (s, a) for the Qvalue with N MC trajectories is

EQUATION

where N s = j∈D 1 s (j) is the number of visitations in state s, s.t. N = β(a|s)N s . Therefore,

σ ε(s,a) ∝ 1 √ β(a|s)

and specifically for low frequency actions such estimation may suffer large SE.3 

5.3. POLICY IMPROVEMENT IN THE PRESENCE OF VALUE ESTIMATION ERRORS:

We now turn to the crucial question of what happens when one applies an improvement step with respect to an inaccurate estimation of the Q-function, i.e. Qβ .

Lemma 5.2 (Improvement Penalty). Let Qβ = V β + Âβ be an estimator of Q β with an error ε(s, a) = (Q β -Qβ )(s, a) and let π be a policy that satisfies lemma 5.1 with respect to Âβ . Then the following holds

EQUATION

where the difference, denoted E(s), is called the improvement penalty (proof in the appendix).

For simplicity we may write E(s) =s ,a ρ π (s |s)ε(s , a)(β(a|s ) -π(a|s )), where ρ π (s |s) is sometimes referred to as the undiscounted state distribution of policy π given an initial state s. Since ε(s , a) is a random variable, it is worth to consider the variance of E(s). Assuming that the errors ε(s, a) are positively correlated (since neighboring state-action pairs share trajectories of rewards) and under the error model introduced above, it follows that

σ 2 E(s) ≥ s ,a (ρ π (s |s)) 2 σ 2 ε(s ,a) (β(a|s )-π(a|s )) 2 = s ,a (ρ π (s |s)) 2 σ 2 z(s ,a) N s (β(a|s ) -π(a|s )) 2 β(a|s ) .

Hence, it is evident that the improvement penalty can be extremely large when the term |β-π| 2 β is unregulated. Moreover, a single mistake along the trajectory, caused by an unregulated element, might wreck the performance of the entire policy. Therefore, it is essential to regulate each one of these elements to minimize the potential improvement penalty.

5.4. THE REROUTE CONSTRAINT:

In order to regulate the ratio |β-π| 2 β , we suggest limiting the improvement step to a subset of Π M R based on the following constraint. )) (proof in the appendix). Now, it is evident that with the reroute constraint, each element in the sum of ( 8 β(a|s) ], used in the TRPO algorithm, and the PPO objective function (Schulman et al., 2017) , surprisingly reveals that non of them properly controls the improvement penalty (see an example and an analysis of the PPO objective in the appendix, we also show in the appendix that the solution of the PPO objective is not unique).

5.5. MAXIMIZING THE IMPROVEMENT STEP UNDER THE REROUTE CONSTRAINT:

We now consider the last part of our improvement approach, i.e. maximizing the objective function under the reroute constraint and whether such maximization provides a positive improvement step. It is well-known that maximizing the objective function without generating new trajectories of π is a hard task since the distribution of states induced by the policy π is unknown. Previous works have suggested to maximize a surrogate off-policy objective function J OP (π) = E s∼β [ a π(a|s)A β (s, a)]. These works have also suggested to solve the constrained maximization with a NN policy representation and a gradient ascent approach (Schulman et al., 2015) . Here we suggest a refreshing alternative, instead of precalculating the policy π that maximizes J OP one may ad hoc compute the policy that maximizes the improvement step a π(a|s)A β (s, a) (which is the argument of the J OP objective) for each different state. Such an approach maximizes also the J OP objective since the improvement step is independent between states. For the reroute constraint, this essentially sums up to solving the following simple linear program for each state Maximize:

(A β ) T π Subject to: c min β ≤ π ≤ c max β

And:

EQUATION

Where π, β and A π are vector representations of (π(a i |s))

|A| i=1 , (β(a i |s)) |A| i=1 and (A β (s, a)) |A| i=1

respectively. We term the algorithm that solves this maximization problem as Max-Reroute (see Algorithm 1). In the appendix we also provide an analogous algorithm that maximizes the improvement step under the TV constraint (termed Max-TV). We will use Max-TV as a baseline for the performance of the reroute constraint. With an ad hoc maximization approach, we avoid the hassle of additional learning task after the policy imitation step, and in addition, our solution guarantees maximization without the common caveats in NN learning such as converging to local minima or overfitting etc.

Further analyzing Max-Reroute and Max-TV quickly reveals that they both rely only on the action ranking at each state (as stated in the previous section). This is also in contrast with the aforementioned methods (TRPO and PPO) where by their definition as policy gradient methods (Sutton et al., 2000) , they optimize the policy according to the magnitude of the advantage function. Finally, notice that both Max-Reroute and Max-TV satisfy the conditions of Corollary 5.1.1, therefore they always provide a positive improvement step and hence for a perfect approximation of the value function they are guaranteed to improve the performance.

Algorithm 1: Max-Reroute Let us now return to our Taxi example and examine different types of improvement steps with respect to a behavioral cloning baseline::

Data: s, β, A β , (cmin, cmax) Result: {π(a|s), a ∈ A} begin Ã ←-A ∆ ←-1 -cmin π(a|s) ←-cminβ(a|s) ∀a ∈ A while ∆ > 0 do a = arg max a∈ Ã A β (s, a) ∆a = min{∆, (cmax -cmin)β(a|s)} Ã ←-Ã/a ∆ ←-∆ -∆a π(a|s) ←-π(a|s) + ∆a

(1) a greedy step 4 (2) a TV constrained and;

(3) a reroute constrained steps. The dataset is generated by two policies with a discount factor γ = 0.9. We consider two types of policies: row selection (3a) and random selection (3b). The behavior policy was calculated by enumerating actions in each state. We examine the two alternatives of evaluating Q β : MC (without off-policy corrections) and TD learning (as described in section 4).

First, it is clear that taking a greedy step is a precarious approach. In these experiments, the generated greedy policy contained recurrent states (which is a repetitive series of states). This prevented the completion of the task. Comparing the TV step to the average behavior baseline, reveals that only in relatively large datasets (more than 10 3 episodes in this example) TV step is better than behavioral cloning. This demonstrates the problematic approach of taking actions that were insufficiently evaluated. In real-world MDP with larger number of states, it is extremely difficult to sufficiently sample the entire state-space, hence, we project that TV should be poorer than behavioral cloning even for large datasets. In the next section, this premise is verified in the Atari domain.

Contrary to TV, reroute provided almost always better performance than the average behavior. This pattern repeats both with TD and MC learning. An important observation is that MC outperform TD for larger datasets. Since MC should converge to Q D and TD to Q β , we cannot link any performance degradation to the evaluation of Q D instead of Q β . On the other hand, we can still hypothesize that the slow improvement in TD (in large datasets) is due to bootstrapping. In the next section in the Atari example, we show that when we utilize a NN parametric form where bootstrapping errors are larger, this pattern intensifies.

6. LEARNING TO PLAY ATARI BY OBSERVING INEXPERT HUMAN PLAYERS:

In the previous section, we analyzed the expected error which motivated the reroute constraint for a tabular representation. In this section, we experimentally show that the same ideas holds for Deep NN parametric form. We conducted an experiment with a crowdsourced data of 4 Atari games (Spaceinvaders, MsPacman, Qbert and Montezuma's Revenge) (Kurin et al., 2017) . Each game had roughly 1000 recorded episodes. We employed two networks, one for policy cloning β and one for Q-value estimation with architecture inspired by the Dueling DQN (Mnih et al., 2015; Wang et al., 2015) and a few modifications (see appendix). We evaluated two types of local maximization steps: Max-Reroute, with different parameters (c min , c max ); and Max-TV. We implemented two baselines: (1) DQfD algorithm with hyperparameters as in Hester et al. (2018) and (2) a single PPO policy search step based on the learned behavior policy and the estimated advantage. The following discussion refers to the results presented in Figure 4 . Average behavior performance: When comparing the average behavior performance to the average human score, we get very similar performance in 2 out of 4 games. However, in Qbert, we obtained substantially better performance than the average human score. Generally, we expect that in games where longer trajectories lead to significantly more reward, the average policy obtains above average reward, since the effect of good players in the data has a heavier weight on the results. On the other hand, we assume that the lower score in MsPacman is due to the more complex and less clear frame in this game with respect to the other games. We take the average behavior performance as a baseline for comparing the safety level of the subsequent improvement steps.

MC and TD estimators of the Q-value function: We evaluated the performance of reroute(0.5, 1.5) during the training process with two different estimators, both concurrently learned from the same batches. MC-reroute(0.5, 1.5) learned the surrogate Q D with full trajec-tories and provided better score than the behavioral cloning baseline in 3 out of 4 games and tied in one. On the other hand TD-reroute(0.5, 1.5) learned the true Q β with 1-step TD learning but did not show a significant improvement in any game. We hypothesize that larger evaluation errors due to bootstrapping may be the reason for the low performance of the TD estimator. The rest of the discussion focuses on the MC evaluation.

Local maximization steps: We chose to evaluate Max-TV with δ = 0.25 since it encapsulates the reroute(0.5, 1.5) region. It is clear that Max-TV is always dominated by Max-Reroute and it did not secure safe improvement in any of the games. A comparison of different reroute parameters reveals that there is an fundamental trade-off between safety and improvement. Smaller steps like reroute(0.5, 1.5) support higher safety at the expense of improvement potential. In all games reroute(0.5, 1.5) provided safe improvement, but in Qbert its results were inferior to reroute(0, 2).

On the other hand, reroute(0, 2) reduced the Revenge score which indicates a too greedy step. Our results indicates that it is important to set c min > 0 since avoiding so may discard some important actions altogether due to errors in the value evaluation, resulting in a poor performance.

Comparison with PPO: For the PPO baseline, we executed a policy search with the learned advantage A β according to the PPO objective

J P P O (π) = E s∼β a∈A β(a|s) min A β (s, a) π(a|s) β(a|s) , A β (s, a) clip π(a|s) β(a|s) , 1 -ε, 1 + ε .

We chose ε = 0.5, motivated by the similarity to the reroute(0.5, 1.5) region (see appendix). Contrary to the PPO paper, we plugged our advantage estimator and did not use the Generalized Advantage Estimation (GAE). While P P O(0.5) scored (see box plot in Figure 4a ) better than reroute(0.5, 1.5) in Qbert, in all other games it reduced the behavioral cloning score. The overall results indicate the similarity between P P O(0.5) and reroute(0, 2), probably since negative advantages actions tend to settle at zero-probability to avoid negative penalty. This emphasizes the importance of the c min parameter of reroute which is missing from PPO.

Comparison with DQfD: DQfD scored below the average behavior in all games. The significantly low scores in MsPacman and Qbert raise the question whether DQfD and more generally, Off-Policy greedy RL can effectively learn from multiple non-exploratory fixed policies. The most conspicuous issue is the greedy policy improvement approach taken by DQfD: we have shown that an unconstrained greedy improvement step leads to a poor performance (recall the Taxi example).

In addition, as discussed in section 4, Off-Policy RL with TD learning also suffers from the second RL ingredient, i.e. policy evaluation . As our results show, our proposed safe policy improvement scheme with MC learning mitigates these issues, leading to significantly better results

7. CONCLUSIONS:

In this paper, we studied both theoretically and experimentally the problem of LfO. We analyzed factors that impede classical methods, such as TRPO/PPO and Off-Policy greedy RL, and proposed a novel alternative, Rerouted Behavior Improvement (RBI), that incorporates behavioral cloning and a safe policy improvement step. RBI is designed to learn from multiple agents and to mitigate value evaluation errors. It does not use importance sampling corrections or bootstrapping to estimate values, hence it is less sensitive to deep network function approximation errors. In addition, it does not require a policy search process. Our experimental results in the Atari domain demonstrate the strength of RBI compared to current state-of-the-art algorithms. We project that these attributes of RBI would also benefit an iterative RL process. Therefore, in the future, we plan to study RBI as an online RL policy improvement method.

A OPERATOR NOTATION:

In part of the appendix, we use vector and operator notation, where v π and q π represent the value and Q-value functions as vectors in V ≡ R |S| and Q ≡ R |S×A| . We denote the partial order x ≥ y ⇐⇒ x(s, a) ≥ y(s, a) ∀s, a ∈ S × A, and the norm x = max s,a |x|. Let us define mappings between V and Q:

1. Q → V mapping Π π : (Π π q π ) (s) = a∈A π(a|s)q π (s, a) = v π (s).

This mapping is used to backup state-action-values to state value.

2. V → Q mapping P: Pv π (s, a) = s ∈S P (s |s, a)v π (s ). This mapping is used to backup state-action-values based on future values. Note that this mapping is not dependent on a specific policy.

Let us further define two probability operators:

1. V → V state to state transition probability P π v :

(P π v v π ) (s) = a∈A π(a|s) s ∈S P (s |s, a)v π (s ). 2. Q → Q state-

action to state-action transition probability P π q : P π q q π (s, a) = s ∈S P (s |s, a) a ∈A π(a |s )q π (s , a ).

Note that the probability operators are bounded linear transformations with spectral radios σ(P π v ) ≤ 1 and σ(P π q ) ≤ 1 (Puterman, 2014). Prominent operators in the MDP theory are the recursive value operator T π v v = Π π r + γP π v v and recursive Q-value operator T π q q = r + γP π q q. Both have a unique solution for the singular value equations v = T π v v and q = T π q q. These solutions are v π and q π respectively (Sutton & Barto, 2017; Puterman, 2014) . In addition, in the proofs we will use the following easy to prove properties:

1. P π q = PΠ π 2. P π v = Π π P 3. x ≥ y, x, y ∈ V, ⇒ Px ≥ Py 4. The probability of transforming from s to s in k steps is P (s k -→ s |π) = (P π v ) k (s, s ). 5. [(P π v ) k x](s) = E s k ∼π|s [x(s k )] B AVERAGE BEHAVIOR PROOFS B.1 UPPER BOUND FOR MONTE-CARLO EVALUATION OF Q D WITH L 1 LOSS

Proof. We denote by L L1 ( QD ) the true L 1 least absolute error loss of the value function estimator, and we show that L M C ( QD ) ≥ L L1 ( QD ) for |D|→ ∞ such that minimization of L M C leads to a bounded error of L L1 . Remember that the dataset D is a concatenation of the sets

D i = {(s 1 , a 1 ), (s 2 , a 2 ), ...}, i = 1, .., N . L L1 ( QD ) = 1 |D| j∈D Q D (s j , a j ) -QD (s j , a j ) = 1 |D| j∈D∩Ω <   p i Q i (s j , a j )P p i |s j , a j -QD (s j , a j )   + + 1 |D| j∈D∩Ω >   QD (s j , a j ) - p i Q i (s j , a j )P p i |s j , a j  

where Ω < and Ω > denote the complementary subspaces of S × A where QD underestimates and overestimates the target (respectively).

1 |D| j∈D∩Ω <   p i Q i (s j , a j )P p i |s j , a j -QD (s j , a j )   = 1 |D| j∈D∩Ω < p i P p |s j , a j Q i (s j , a j ) -QD (s j , a j ) ≤ 1 |D| j∈D∩Ω < p i P p i |s j , a j Q i (s j , a j ) -QD (s j , a j ) .

Joining the equivalent term for the Ω > region, we obtain the inequality

L L1 ( QD ) ≤ 1 |D| j∈D p i P p i |s j , a j Q i (s j , a j ) -QD (s j , a j ) = 1 |D| unique(s,a)∈D   j∈D 1 s,a (j)   p i j∈Di 1 s,a (j) j∈D 1 s,a (j) Q i (s j , a j ) -QD (s j , a j ) = 1 |D| unique(s,a)∈D p i   j∈Di 1 s,a (j)   Q i (s j , a j ) -QD (s j , a j ) = 1 |D| j∈D Q ij (s j , a j ) -QD (s j , a j ) = 1 |D| j∈D E R j |s j , a j , p ij -QD (s j , a j )

Plugging in the Jensen inequality for all s j , a j , p ij E R j |s j , a j , p ij -QD (s j , a j ) ≤ E |R j -QD (s j , a j )| s j , a j , p ij we obtain

L L1 ( QD ) ≤ 1 |D| j∈D E |R j -QD (s j , a j )| s j , a j , p ij .

In the limit when |D|→ ∞ the sample average converges to the expectation, i.e.

1 |D| j∈D [•] → E [•], therefore L L1 ( QD ) ≤ 1 |D| j∈D E |R j -QD (s j , a j )| s j , a j , p ij = E E |R j -QD (s j , a j )| s j , a j , p ij = E |R j -QD (s j , a j )| = 1 |D| j∈D |R j -QD (s j , a j )|= L M C ( QD ). B.2 Q D IS A VALUE OF A TIME DEPENDENT POLICY β D s,ã

Given a state-action pair s, ã, then Q D (s, ã) is the Q-value of a time dependent policy β D s,ã (a|s, k), where k is a time index and s, ã is a fixed initial state-action pair,

EQUATION

)

Here the conditional probability is over a uniform sample x ∼ U (D s,ã,k ) where D s,ã,k is a subset of D that contains all the entries in the dataset with distance k from an entry with a state-action pair s, ã.

Proof. For the proof, let us construct an extended MDP, with an additional initial state, termed s 0 with N different actions. Following an action selection in state s 0 , an action ã is executed in state s (in the original MDP) and then the original MDP continues as usual.

Let us define a History Randomized (HR) policy β h ∈ Π HR according to the following 1. In state s 0 , select an action i with probability P (p i |s, ã).

2. In all consecutive states act with the Markovian policy β i .

Notice that it is clearly a HR policy since the second step is determined by the history (that is the first step). It is straightforward to calculate the value of the s 0 state with the law of total probability s.t.

V β h (s 0 ) = π Q i (s, ã)P (p i |s, ã) = Q D (s, ã).

Puterman ( 2014) proved (Theorems 5.5.1-3) that for every HR policy, there exists a time dependent Markovian policy with the same value, let it be denoted as β D s,ã . The Markovian policy satisfies

β D s,ã (a|s, k) = P (a|s, k, β h ),

that is the probability of executing action a in state s and time step k when following β h . Again, with the law of total probability this may be written as

β D s,ã (a|s, k) = i β i (a|s)P (a(s 0 ) = i|s 0 k -→ s),

where a(s 0 ) is the chosen action in state s 0 . Notice that s, ã deterministically follow state s 0 so by applying Bayes' theorem, we get that

P (a(s 0 ) = i|s 0 k -→ s) = P (a(s 0 ) = i)P (s, ã k -→ s|a(s 0 ) = i) P (s, ã k -→ s) = P (p i |s, ã)P (s, ã k -→ s|β i ) p j P (p j |s, ã)P (s, ã k -→ s|β j )

.

Let us define by 1 s,ã,k,s an indicator function which equals 1 for the entries in the dataset which are in state s in a distance k from an entry with state-action pair s, ã. We may represent the above expression with the indicator summation notation

P (p i |s, ã)P (s, ã k -→ s|β i ) p j P (p j |s, ã)P (s, ã k -→ s|β j ) = j∈D i 1s,ã j∈D 1s,ã j∈D i 1 s,ã,k,s j∈D i 1s,ã p i j∈D i 1s,ã j∈D 1s,ã j∈D i 1 s,ã,k,s j∈D i 1s,ã = j∈D i 1 s,ã,k,s j∈D 1 s,ã,k,s

.

Finally, the last expression can be transformed back to conditional probability notation of the form

j∈D i 1 s,ã,k,s j∈D 1 s,ã,k,s = P (p i |s, ã k -→ s) C SAFE POLICY IMPROVEMENT C.1 REROUTE IS A SUBSET OF TV

The set of reroute policies with [c min , c max ] is a subset of the set of δ-TV policies, where

δ = min(1 -c min , max( cmax-1 2 , 1-cmin 2 )).

Proof. For a reroute policy, the TV distance is

1 2 a β(a i |s)|1 -c i |≤ a β(a i |s)δ = δ.

For the second upper bound 1 -c min , notice that a rerouted policy {π i } may be written as π i = c min β i + δ i , where δ i ≥ 0. Therefore, the TV distance is

T V = 1 2 i |π i -β i |= 1 2 i |c min β i + δ i -β i |≤ 1 2 i ((1 -c min )β i + δ i ) , but 1 = i π i = i (c min β i + δ i ) = c min + i δ i .

Thus, i δ i = 1 -c min and we may write

T V ≤ 1 2 ((1 -c min ) + (1 -c min )) = 1 -c min .

To show that the TV is not in reroute, take any policy with a zero probability action and another action with a probability of β(a i |s) ≤ δ. The policy which switches probabilities between these two actions is in T V (δ) but it is not in reroute for any finite c max .

C.2 SOFT POLICY IMPROVEMENT:

The soft policy improvement rule states that every policy π that satisfies a π(a|s)A β (s, a) ≥ 0 ∀s ∈ S improves the policy β s.t. V π ≥ V β ∀s. To avoid stagnation we demand that the inequality be strict for at least a single state. In operator notation, the last equation can be written as

EQUATION

Then, by applying (11) recursively we get

v β ≤ r π + γP π v v β = r π + γP π v (r π + γP π v v β ) ≤ r π + γP π v r π + γ 2 (P π v ) 2 v β ≤ r π + γP π v r π + γ 2 (P π v ) 2 r π + γ 3 (P π v ) 3 v β ≤ ... ≤ k≥0 γ k (P π v ) k r π = (I -γP π v ) -1 r π = v π .

( Schulman et al., 2015) have shown that

J(π) -J(β) = E T ∼π   k≥0 γ k A β (s k , a k )   .

This equation can also be written as

J(π) -J(β) = k≥0 γ k E s k ∼π|s0 a∈A π(a|s k )A β (s k , a k ) = = k≥0 γ k s∈S P (s 0 k -→ s|π) a∈A π(a|s)A β (s, a) = s∈S   k≥0 γ k P (s 0 k -→ s|π)   a∈A π(a|s)A β (s k , a).

Recall the definition of the discounted distribution of states

ρ π (s) = k≥0 γ k P (s 0 k -→ s|π), we conclude that J(π) -J(β) = s∈S ρ π (s) a∈A π(a|s)A β (s, a) C.3 RANK-BASED POLICY IMPROVEMENT

Proof. Denote by i the index of the advantage ordered list {A i }. Since ai β i A β i = 0, we can write it as an equation of the positive and negative advantage components

N a=ip β i A β i = in a=0 β i (-A β i ),

where i p is the minimal of positive advantages and i n is the maximal index of negative advantages. Since all probability ratios are non-negative, it is sufficient to show that

N a=ip c i β i A β i ≥ in a=0 c i β i (-A β i ). But clearly N a=ip c i β i A β i ≥ c ip N a=ip β i A β i ≥ c in in a=0 β i (-A β i ) ≥ in a=0 c i β i (-A β i ).

C.4 POLICY IMPROVEMENT PENALTY:

Let Qβ be an approximation of Q β with an error ε(s, a) = (Q β -Qβ )(s, a) and let π be a policy that satisfies the soft policy improvement theorem with respect to Qβ . Then the following holds:

EQUATION

The proof resembles the Generalized Policy improvement theorem (Barreto et al., 2017) .

Proof. We will use the equivalent operator notation. Define the vector ε = q β -qβ

T π q qβ = r + γ PΠ π qβ ≥ r + γ PΠ β qβ = r + γ PΠ β q β -γ PΠ β ε = T β q q β -γP β q ε = q β -γP β q ε = qβ + (1 -γP β q )ε .

Note that the inequality is valid, since Π π qβ ≥ Π β qβ (by the theorem assumptions), and if v ≥ u then Pv ≥ Pu. Set y = (1 -γP β q )ε and notice that T π q (q β + y) = T π q qβ + γP π q y. By induction, we show that

(T π q ) n qβ ≥ qβ + n k=0 γ k (P π q ) k y.

We showed it for n = 1, assume it holds for n, then for n + 1 we obtain

(T π q ) n+1 qβ = T π q (T π q ) n qβ ≥ T π q qβ + n k=0 γ k (P π q ) k y = = T π q qβ + n k=0 γ k+1 (P π q ) k+1 y ≥ qβ + y + n k=0 γ k+1 (P π q ) k+1 = qβ + n+1 k=0 γ k (P π q ) k y.

Using the contraction properties of T π q , s.t. lim k→∞ (T π q ) k x = q π , ∀x ∈ Q and plugging back (1 -γP β q )ε = y, we obtain

q π = lim n→∞ (T π q ) n (q β ) ≥ qβ + k≥0 γ k (P π q ) k (1 -γP β q )ε = + ε + k≥0 γ k+1 (P π q ) k (P π q -P β q )ε.

Applying Π π we transform back into V space

v π ≥ Π π qβ + Π π ε + k≥0 γ k+1 Π π (P π q ) k (P π q -P β q )ε ≥ Π β qβ + Π π ε + k≥0 γ k+1 Π π (P π q ) k (P π q -P β q )ε = v β + (Π π -Π β )ε + k≥0 γ k+1 Π π (P π q ) k (P π q -P β q )ε

.

Notice that Π π (P π q ) k P π q = Π π ( PΠ π ) k PΠ π = (Π π P) k+1 Π π = (P π v ) k+1 Π π , and in the same manner, Π π (P π q ) k P β q = (P π v ) k+1 Π β . Therefore, we can write

v π ≥ v β - k≥0 γ k (P π v ) k (Π β -Π π )ε,

which may also be written as (12).

C.5 UNBOUNDED PROBABILITY RATIOS IN THE TV AND KL CONSTRAINTS:

To verify that TV and KL do not regulate the probability ratios, let's consider a tiny example of maximizing the objective function J P P O for a single state MDP with two actions {a 0 , a 1 }. Assume a behavior policy β = {1, 0} and an estimated advantage A β = {0, 1}. We search for a policy π = {1 -α, α} that Maximize improvement step under the TV or KL constraints.

For a δ-TV constraint, 1 2 (1 -(1 -α) + α) = α ≤ δ. The improvement step in this case is ai A β i π i = α. Hence the solution is α = δ and the probability ratio π(a 1 )/β(a 1 ) is unconstrained (and undefined). Similarly for a δ-KL constraint we get -log α ≤ δ and the improvement step is identical. Hence α = e -δ and again, no constraint is posed on the probability ratio. Recently, (Schulman et al., 2017) have suggested a new surrogate objective function, termed Proximal Policy Optimization (PPO), that heuristically should provide a reliable performance as in TRPO without the complexity of a TRPO implementation:

J P P O (π) = E s∼β a∈A β(a|s) min A β (s, a) π(a|s) β(a|s) , A β (s, a) clip π(a|s) β(a|s) , 1 -ε, 1 + ε ,

where ε is a hyperparameter. PPO tries to ground the probability ratio by penalizing negative advantage actions with probability ratios above 1-ε. In addition, it clips the objective for probability ratios above 1 + ε so there is no incentive to move the probability ratio outside the interval [1 -ε, 1 + ε].

However, we show in the following that the solution of PPO is not unique and is dependent on the initial conditions, parametric form and the specific optimization implementation. This was also experimentally found in (Henderson et al., 2017) . The effect of all of these factors on the search result is hard to design or predict. Moreover, some solutions may have unbounded probability ratios, in this sense, J P P O is not safe.

First, notice that PPO maximization can be achieved by ad hoc maximizing each state since for each state the objective argument is independent and there are no additional constraints. Now, for state s, let's divide A into two sets: the set of positive advantage actions, denoted A + , and the set of negative advantage actions, A -. For convenience, denote c i = π(ai|s) β(ai|s) and β i = β(a i |s). Then, we can write the PPO objective of state s as

J P P O (π, s) = ai∈A + β i A β i min (c i , 1 + ε) - ai∈A - β i (-A β i ) max (c i , 1 -ε) .

Clearly maximization is possible (yet, still not unique) when setting all c i = 0 for a i ∈ A -, namely, discarding negative advantage actions. This translates into a reroute maximization with parameters (c min , c max ) = (0, 1 + ε)

arg max ci [J P P O (π, s)] = arg max ci   ai∈A + β i A β i min (c i , 1 + ε)   = arg max ci   ai∈A + c i β i A β i   for c i ≤ 1 + ε.

The only difference is that the sum i c i β i = 1 -∆ may be less then 1. In this case, let us take the unsafe approach and dispense ∆ to the highest ranked advantage. It is clear that partition of ∆ is not unique, and even negative advantage actions may receive part of it as long as their total probability is less than (1-ε)β i . We summarize this procedure in the following algorithm.

Algorithm 3: Ad hoc PPO Maximization

Data: s, β, A β , ε Result: {π(a|s), a ∈ A} begin Ã = { Ã+ , Ã-} Ã ←-A + ∆ ←-1 π(a|s) ←-0 ∀a ∈ A while ∆ > 0 and | Ã|> 0 do a = arg max a∈ Ã A β (s, a) ∆ a = min{∆, (1 + ε)β(a|s)} Ã ←-Ã/a ∆ ←-∆ -∆ a π(a|s) ←-π(a|s) + ∆ a a = arg max a∈A A β (s, a) π(a|s) ←-π(a|s) + ∆

D TAXI EXPERIMENT: TECHNICAL DETAILS:

In the paper, we presented three selection types of the subset of the optimal policy, i.e. S * i : (1) row selection (2) column selection and; (3) random selection. In the Taxi environment the states are enumerated {s j } 500 j=1 . For N players, the definitions for our the selection types are Row Selection:

s j ∈ S * i j -i 500 N (mod500) < 250

Column Selection:

EQUATION

Random Selection: Randomly (and uniformly) choose 250 states out of the 500 state for each different S * i . For the improvement step experiment, we evaluated the behavior policy β with a tabular representation, i.e., β(a|s) = Ns,a Ns (see the first item in Definition 4.1). For Monte-Carlo learning, we applies the following update rule

EQUATION

where α = 0.1 is a learning rate and R s,a (j) is a single instance of the total discounted return from a state-action pair s, a, up to the terminal state. For Temporal Difference learning, we applied

EQUATION

with the same learning rate. Notice that in this experiment we did not evaluated Q β from a V β evaluation since for the tabular case, β is perfectly calculated with β(a|s) =

Ns,a

Ns .

E ATARI EXPERIMENT: TECHNICAL DETAILS E.1 DATASET PREPROCESSING:

The dataset (Kurin et al., 2017) (Version 2) does not contain an end-of-life signal. Therefore, we tracked the changes of the life icons in order to reconstruct the end-of-life signal. The only problem with this approach was in Qbert where the last life period has no apparent icon but we could not match a blank screen since, during the episode, life icons are flashed on and off. Thus, the last endof-life signal in Qbert is missing. Further, the dataset contained some defective episodes in which the screen frames did not match the trajectories. We found them by comparing the last score in the trajectory file to the score that appears in the last or near last frame.

We also found some discrepancies between the Javatari simulator used to collect the dataset and the Stella simulator used by the OpenAI gym package where we evaluated the agents' scores:

• The Javatari reward signal has an offset of -2 frames. We corrected this shift in the preprocessing phase.

• The Javatari actions signal has an offset of ∼ -2 frames (depending on the action type), where it is sometimes recorded non-deterministically s.t. the character executed an action in a frame before the action appeared in the trajectory file. We corrected this shift in the preprocessing phase.

• The Javatari simulator is not deterministic, while Stella can be defined as deterministic. This has the effect that icons and characters move in different mod 4 order, which is crucial when learning with frame skipping of 4. Thus, we evaluated the best offset (in terms of score) for each game and sampled frames according to this offset.

• There is a minor difference in colors/hues and objects location between the two simulators.

E.2 LEARNING FROM HUMAN PLAYERS:

The Atari dataset introduced a further challenge of learning from human players. Contrary to RL agents, while much of the developed theory in previous sections assumes observation of Markovian policies, humans do not play with MR policies. We found that two significant sources of Non-Markovian behavior are: (1) delayed response and (2) action repetition. The first happens due to an unavoidable delay between eye and hand movement. In simple words, humans respond to a past state. The second implies that actions depend on action history, which violates the Markovian assumption. Practically, when using a NN classifier, such Non-Markovian behavior hurts the classification since the network learns to predict past actions. We found that training the network to predict an action in the near future (6 frames away, i.e. 0.1 seconds) can mitigate such a non-Markovian nature. This way there is less correlation between the present state and the executed action, and the human delayed response is mitigated.

E.3 NETWORK ARCHITECTURE:

A finite dataset introduces overfitting issues. To avoid overfitting, DQN constantly updates a replay buffer with new samples. In a finite dataset this is not possible, but, contrary to many Deep Learning tasks, partitioning into training and validation sets is also problematic: random partitions introduce a high correlation between training and testing, and blocking partitioning (Racine, 2000) might miss capturing parts of the action-states space. Moreover, the ultimate learning goal, i.e. the playing score, is not necessarily captured via the loss function score. In LfO, evaluating the agent's score to avoid overfitting violates the assumption of learning only from the dataset. Fortunately, we found that Dropout (Srivastava et al., 2014) , as a source of regularization, improves the network's resiliency to overfitting. In addition, it has the benefit of better generalization to new unseen states since the network learns to classify based on a partial set of features. We added two sources of dropout: (1) in the input layer (25%) and (2) on the latent features i.e. before the last layer (50%).

We also found that for a finite dataset with a constant statistics, Batch Normalization (BN) can increase the learning rate. Therefore, we used BN layer before the ReLu nonlinearities. Note that for an online RL algorithm, BN may sometimes impede learning because the statistics may change during the learning process.

To estimate the advantage for the PPO objective, we used a trick inspired by the Duelling DQN architecture (Wang et al., 2015) . We added a single additional output to the last layer of the Q network which represents the value V β . The other |A| outputs represents the unnormalized advantages { Ãi } i and the Q-function outputs are therefore expressed as

EQUATION

where {β j } j are the outputs of the policy network. Note that i Q β i = V β . The normalized advantage is therefore A β i = Ãij Ãj β j . Finally, we also shaped a reward for an end-of-life signal (for all our experiments including DQfD). Usually, DQN variants set an end-of-life signal only as a termination signal so that the agent learns that near end-of-life states have a 0 value and, as a consequence, states that dodge termination are preferred. Since RBI policy is stochastic and does not just choose the best one, it is helpful to differentiate between near zero reward and termination. Thus, we added a negative reward (-1) for a terminal state.

To summarize, we used two DQN style networks: one for β and the second for Q β . We used the same network architecture as in (Mnih et al., 2015) except for the following add-ons:

• A batch normalization layer before nonlinearities.

• A 25% Dropout in the input layer.

• A 50% Dropout in the latent features layer. To compensate for the dropped features we expanded the latent layer size to 1024, instead of 512 as in the original DQN architecture.

• An additional output that represents the state's value.

The overall architecture is depicted in figure 5 . For the behavioral cloning, we used the Cross-Entropy Loss. For the value network, though the theoretical bound in the paper is calculated for the L 1 loss, we found that slightly better results are obtained with the M SE loss. This may be due to better regression of outliers. All results reported in the paper used the MSE loss for value.

E.4 LEARNING PROCESS:

A single iteration of our learning process is depicted with the following PyTorch style pseudo-code. 

:

Note that humans' policies can generally be considered as part of the history randomized set Π HR where π ∈ Π HR is a probability function over A given the states and actions history. In the appendix we explain how we circumvented this hurdle in the Atari dataset.

We post a proof in the appendix for completeness, though it may have been proven elsewhere.

Note that even for deterministic environments, a stochastic policy inevitably provides σ z(s,a) > 0.

An unconstrained step, equivalent to reroute parameters (cmin, cmax.) = (0, ∞)

Figures and Tables:

Figure 2: Taxi: comparison between Q β and Q D

Definition 5.1 (Reroute Constraint). Given a policy β, a policy π is a reroute(c min , c max ) of β, if π(a|s) = c(s, a)β(a|s) where c(s, a) ∈ [c min , c max ]. Further, note that reroute is a subset of the TV constraint with δ = min(1 -c min , max( cmax-1 2 , 1-cmin 2

) is regulated and proportional to β(a|s)|1 -c(s, a)| where c(s, a) ∈ [c min , c max ]. Analyzing other well-known trust regions such as the TV constraint δ ≥ 1 2 a |β(a|s) -π(a|s)|, the average KL-divergence constraint DKL (β||π) = -E s∼β [ a β(a|s) log π(a|s)

Figure 3: Taxi: Improvement steps comparison

Figure 4: Atari experiment results

MAX-TVAlgorithm 2: Max-TVData: s, β, A D , δ Result: {π(a|s), a ∈ A} begin π(a|s) ←-β(a|s), ∀a ∈ A a = arg max a∈ Ã A D (s, a) ∆ = min{δ, 1 -β(a|s)} π(a|s) ←-π(a|s) + ∆ Ã ←-A while ∆ > 0 do a = arg min a∈ Ã A D (s, a) ∆ a = min{∆, β(a|s)} Ã ←-Ã/a ∆ ←-∆ -∆ a π(a|s) ←-π(a|s) -∆ a C.7 THE PPO OBJECTIVE FUNCTION

Figure 5: Network architecture

Policy and Q-value networks Hyperparameters

Table content: <table><tr><td>Name</td><td>Value</td></tr><tr><td>Last linear layer size</td><td>1024</td></tr><tr><td>Optimizer</td><td>Adam</td></tr><tr><td>Learning Rate</td><td>0.00025</td></tr><tr><td>Dropout [first layer]</td><td>0.25</td></tr><tr><td>Dropout [last layer]</td><td>0.5</td></tr><tr><td>Minibatch</td><td>32</td></tr><tr><td>Iterations</td><td>1562500</td></tr><tr><td>Frame skip</td><td>4</td></tr><tr><td>Reward clip</td><td>-1,1</td></tr><tr><td colspan="2">Table 2: DQfD Hyperparameters</td></tr><tr><td>Name</td><td>Value</td></tr><tr><td>Optimizer</td><td>Adam</td></tr><tr><td>Learning Rate</td><td>0.0000625</td></tr><tr><td>n-steps</td><td>10</td></tr><tr><td>Target update period</td><td>16384</td></tr><tr><td>l a E</td><td>0.8</td></tr><tr><td>Priority Replay exponent</td><td>0.4</td></tr><tr><td>Priority Replay IS exponent</td><td>0.6</td></tr><tr><td>Priority Replay constant</td><td>0.001</td></tr><tr><td>Other parameters</td><td>As in policy/value networks</td></tr><tr><td/><td>(except Dropout)</td></tr><tr><td>F FINAL POLICY PERFORMANCE</td><td/></tr></table>



Table content: <table/>

Final scores table

Table content: <table><tr><td>Method</td><td colspan="4">MsPacman Qbert Revenge SpaceInvaders</td></tr><tr><td>Humans</td><td>3024</td><td>3401</td><td>1436</td><td>634</td></tr><tr><td>Behavioral cloning</td><td>1519</td><td>8562</td><td>1761</td><td>678</td></tr><tr><td>Reroute-(0.5, 1.5)</td><td colspan="2">1550 12123</td><td>2379</td><td>709</td></tr><tr><td>Reroute-(0.25, 1.75)</td><td colspan="2">1638 13254</td><td>2431</td><td>682</td></tr><tr><td>Reroute-(0, 2)</td><td colspan="2">1565 14494</td><td>473</td><td>675</td></tr><tr><td>TV(0.25)</td><td>1352</td><td>5089</td><td>390</td><td>573</td></tr><tr><td>PPO(0.5)</td><td colspan="2">1528 14089</td><td>388</td><td>547</td></tr><tr><td>DQfD</td><td>83</td><td>1404</td><td>1315</td><td>402</td></tr></table>

Peer review (iclr2019):
 The paper plugs the ideas of TRPO/PPO into the value based RL. Though there is no big surprise in terms of the tools used, this is interesting to know that safe policy improvement is possible in this setting. Nevertheless for a conference as ICLR which is interested in the performance of ML tools, I have two concerns: - The scores obtained on all tests tasks on Atari game are quite far from the state of the art. As an example OpenAI announced to be able to score 74k at Montezuma*s revenge with a single demonstration using PPO and a carefull selection of the initializations states (see blog post https://blog.openai.com/learning-montezumas-revenge-from-a-single-demonstration/). I understand that the setting is not directly comparable but the goal of RL is to learn good policies. This remark would vanish is the authors could come with a real use case where for some reason their approach is the best performer. - The proposed approach is benchmarked wrt few algorithms while there exist a lot in the safe RL literature. The setting is often slightly different but adaptation is often possible. In particular I*d like more positioning wrt what is proposed by the work of Petrik&all (https://papers.nips.cc/paper/6294-safe-policy-improvement-by-minimizing-robust-baseline-regret.pdf the paper is cited but the first author is incorrect). What are the deep differences that make this paper setting more interesting (in terms of what can be done from an applied perspective) or more challenging in terms of mathematical tools. Here I feel the core difference is a comparison against an average of policies which becomes the new baseline to beat. Also not that at EWRL*18 an alternative approach for value based safe RL was presented https://arxiv.org/pdf/1712.06924.pdf