Year: 2018

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.

heading: 1 INTRODUCTION
text: 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).

heading: 2 RELATED WORK
text: 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 & Ferná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.

heading: 3 PROBLEM FORMULATION
text: 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 γ krk ∣∣s0, π] where γ < 1 is a discount factor, k is a time index and s0 is an initial state.
We assume that all policies belong to the Markovian randomized set ΠMR s.t. π ∈ ΠMR 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 π(ai|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) δ(π, π′) = 12 ∑ ai |πi − π′i| and the second is the KL divergence DKL(π||π′) = − ∑ ai πi log π′i πi .
1Note that humans’ policies can generally be considered as part of the history randomized set ΠHR where π ∈ ΠHR is a probability function overA given the states and actions history. In the appendix we explain how we circumvented this hurdle in the Atari dataset.
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 γ krk ∣∣s, π]. Similarly, theQ-value functionQπ(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 (s0 k−→ s|π) the probability of switching from state s0 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 pi, i = 1, ..., N , and their corresponding policies are βi, with value and Q-value functions V i, Qi respectively. D is indexed as {xj}|D|j=0, where the cardinality of the dataset is denoted by |D| and each record is the tuple xj = (sj , aj , rj , tj , ij) s.t. tj is a termination signal and ij is the player’s index. D may also be partitioned to D = {Di|i = 1, .., N}, representing the different players’ records.
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).

heading: 4 AVERAGE BEHAVIOR POLICY AND ITS VALUE FUNCTION
text: 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
β (a|s) = ∑ j∈D 1s,a(j)∑ j∈D 1s(j) = ∑ pi ∑ j∈Di 1s,a(j)∑ j∈Di 1s(j) ∑ j∈Di 1s(j)∑ j∈D 1s(j) , (1)
where 1s,a(j) = 1 if (sj , aj) = (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
β (a|s) = ∑ pi βi(a|s)P ( pi|s ) . (2)
Here P ( pi|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 learningQβ 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 Es∼U(D) [ |V β(s)− r(s, a)− γV β(s′)|2 ] where s, a, s′ are tuples of state-action and next state sampled fromD. 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
Qβ = arg min Qβ
Es,a,s′∼U(D) [ |Qβ(s, a)− r(s, a)− γV β(s′)|2 ] . (3)
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 QD(s, a) = ∑ pi Qi(s, a)P ( pi|s, a ) (4)
which we term the Q-value of the dataset. QD may be interpreted as the weighted average over the players’Q-values, where the weights P ( pi|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 L1-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 Qi 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 Q̂D and a loss LL1(Q̂D) = 1|D| ∑ j∈D|QD(sj , aj) − Q̂D(sj , aj)|, an upper bound for the loss when |D|→ ∞ is LL1(Q̂D) ≤ LMC(Q̂D) = Exj∼U(D)
[∣∣∣Q̂D(sj , aj)−Rj∣∣∣] , (5) where Rj = ∑ k≥0 γ krj+k is the sampled Monte-Carlo return (Proof in the appendix).
The attractive implication of Proposition 4.1 is that we can learnQD 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 QD. Proposition 4.2. Given a state-action pair s̃, ã, then QD(s̃, ã) is the Q-value of a time dependent policy βDs̃,ã(a|s, k), where k is a time index and s̃, ã is a fixed initial state-action pair,
βDs̃,ã(a|s, k) = ∑ pi βi(a|s)P (pi|s̃, ã k−→ s). (6)
Here the conditional probability is over a uniform sample x ∼ U(Ds̃,ã,k) where Ds̃,ã,k is a subset ofD that contains all the entries in the dataset with distance k from an entry with a state-action pair s̃, ã (Proof in the appendix).
Proposition 4.2 indicates that when P (pi|s̃, ã k−→ s) can be approximated as P ( pi|s )
at least for a finite horizon k ∝ 11−γ , then Q
D ' Qβ . This happens when the distribution of players in states near s̃, ã 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, ai)}ai∈A (see next section). This, as we show hereafter, significantly increases the effective similarity between QD and Qβ .
We demonstrates the action ranking similarity between Qβ and QD 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 βDs̃,ã, as a function of the time-step forN = 2. Generally it is low, but it may be questionable whether relying on the true value of QD 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 QD (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 QD, evaluating the Pearson’s rank correlation confirms our statement that in practice the action ranking of QD is an acceptable surrogate for the action ranking of Qβ .

heading: 5 SAFE POLICY IMPROVEMENT
text: Our next step, is to harness the approximatedQ-functionQD ' Qβ (which here will be termedQβ), 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 ci =
π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.

heading: 5.1 SOFT POLICY IMPROVEMENT
text: Before analyzing the error’s statistics, we begin by considering a subset of policies in ΠMR 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 highestQ-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 π ∈ ΠMR 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.2
Essentially, 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 (Ai) |A| i=1 be an ordered list of the β advantages in a state s, s.t. Ai+1 ≥ Ai, and let ci = πi/βi. If for all states (ci)|A|i=1 is a monotonic non-decreasing sequence s.t. ci+1 ≥ ci, then π improves β (Proof in the appendix).

heading: 5.2 STANDARD ERROR OF THE VALUE ESTIMATION
text: To provide a statistical argument for the expected error of theQ-function, consider learningQβ with a tabular representation. The Q-function is the expected value of the random variable zπ(s, a) =∑ k≥0 γ
krk|s, a, π. Therefore, the Standard Error (SE) of an approximation Q̂β(s, a) for the Qvalue with N MC trajectories is
σε(s,a) = σz(s,a)√ Nsβ(a|s) , (7)
where Ns = ∑ j∈D 1s(j) is the number of visitations in state s, s.t. N = β(a|s)Ns. Therefore, σε(s,a) ∝ 1√ β(a|s) and specifically for low frequency actions such estimation may suffer large SE.3

heading: 5.3 POLICY IMPROVEMENT IN THE PRESENCE OF VALUE ESTIMATION ERRORS
text: 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̂ β + Âβ 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 Âβ . Then the following holds
V π(s)− V β(s) ≥ − ∑ s′∈S ∑ k≥0 γkP (s k−→ s′|π) ∑ a∈A ε(s′, a) (β(a|s′)− π(a|s′)) , (8)
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 σ2E(s) ≥ ∑ s′,a (ρπ(s′|s))2σ2ε(s′,a)(β(a|s ′)−π(a|s′))2 = ∑ s′,a (ρπ(s′|s))2σ2z(s′,a) Ns′ (β(a|s′)− π(a|s′))2 β(a|s′) .
2We post a proof in the appendix for completeness, though it may have been proven elsewhere. 3Note that even for deterministic environments, a stochastic policy inevitably provides σz(s,a) > 0.
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.

heading: 5.4 THE REROUTE CONSTRAINT
text: In order to regulate the ratio |β−π| 2
β , we suggest limiting the improvement step to a subset of Π MR
based on the following constraint.
Definition 5.1 (Reroute Constraint). Given a policy β, a policy π is a reroute(cmin, cmax) of β, if π(a|s) = c(s, a)β(a|s) where c(s, a) ∈ [cmin, cmax]. Further, note that reroute is a subset of the TV constraint with δ = min(1− cmin,max( cmax−12 , 1−cmin 2 )) (proof in the appendix).
Now, it is evident that with the reroute constraint, each element in the sum of (8) is regulated and proportional to √ β(a|s)|1 − c(s, a)| where c(s, a) ∈ [cmin, cmax]. Analyzing other well-known
trust regions such as the TV constraint δ ≥ 12 ∑ a|β(a|s) − π(a|s)|, the average KL-divergence
constraint D̄KL(β||π) = −Es∼β [ ∑ a β(a|s) log π(a|s) β(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).

heading: 5.5 MAXIMIZING THE IMPROVEMENT STEP UNDER THE REROUTE CONSTRAINT
text: 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 JOP (π) = Es∼β [ ∑ 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 JOP one may ad hoc compute the policy that maximizes the improvement step ∑ a π(a|s)Aβ(s, a) (which is the argument of the JOP objective) for each different state. Such an approach maximizes also the JOP 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π

heading: Subject to: cminβ ≤ π ≤ cmaxβ
text: And: ∑
πi = 1.
(9)
Where π, β and Aπ̂ are vector representations of (π(ai|s))|A|i=1, (β(ai|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 Data: s, β, Aβ , (cmin, cmax) Result: {π(a|s), a ∈ A} begin Ã ←− A ∆←− 1− cmin π(a|s)←− cminβ(a|s) ∀a ∈ A while ∆ > 0 do
a = arg maxa∈ÃA β(s, a) ∆a = min{∆, (cmax − cmin)β(a|s)} Ã ←− Ã/a ∆←− ∆−∆a π(a|s)←− π(a|s) + ∆a
Let us now return to our Taxi example and examine different types of improvement steps with respect to a behavioral cloning baseline:: (1) a greedy step4 (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 103 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 QD and TD to Qβ , we cannot link any performance degradation to the evaluation of QD instead of Qβ . On the other hand, we can still hypothesize that the slow improve-
ment 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.

heading: 6 LEARNING TO PLAY ATARI BY OBSERVING INEXPERT HUMAN PLAYERS
text: 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
4An unconstrained step, equivalent to reroute parameters (cmin, cmax.) = (0,∞)
(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 (cmin, cmax); 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 QD 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 cmin > 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
JPPO(π) = Es∼β [∑ 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 PPO(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 PPO(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 cmin 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, OffPolicy 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

heading: 7 CONCLUSIONS
text: 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.

heading: A OPERATOR NOTATION
text: 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‖= maxs,a|x|. Let us define two 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̃: ( P̃vπ ) (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, ⇒ P̃x ≥ P̃y
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 ) kx](s) = Esk∼π|s [x(sk)]

heading: B AVERAGE BEHAVIOR PROOFS

heading: B.1 UPPER BOUND FOR MONTE-CARLO EVALUATION OF QD WITH L1 LOSS
text: Proof. We denote by LL1(Q̂D) the true L1 least absolute error loss of the value function estimator, and we show that LMC(Q̂D) ≥ LL1(Q̂D) for |D|→ ∞ such that minimization of LMC leads to a bounded error of LL1 . Remember that the dataset D is a concatenation of the sets Di = {(s1, a1), (s2, a2), ...}, i = 1, .., N .
LL1(Q̂D) = 1 |D| ∑ j∈D ∣∣∣QD(sj , aj)− Q̂D(sj , aj)∣∣∣ = 1
|D| ∑
j∈D∩Ω< ∑ pi Qi(sj , aj)P ( pi|sj , aj ) − Q̂D(sj , aj) + + 1 |D| ∑
j∈D∩Ω> Q̂D(sj , aj)−∑ pi Qi(sj , aj)P ( pi|sj , aj )
where Ω< and Ω> denote the complementary subspaces of S × A where Q̂D underestimates and overestimates the target (respectively).
1 |D| ∑
j∈D∩Ω< ∑ pi Qi(sj , aj)P ( pi|sj , aj ) − Q̂D(sj , aj)  = 1
|D| ∑
j∈D∩Ω< ∑ pi P ( pi|sj , aj ) [ Qi(sj , aj)− Q̂D(sj , aj) ] ≤
1 |D| ∑
j∈D∩Ω< ∑ pi P ( pi|sj , aj ) ∣∣∣Qi(sj , aj)− Q̂D(sj , aj)∣∣∣ . Joining the equivalent term for the Ω> region, we obtain the inequality
LL1(Q̂D) ≤ 1 |D| ∑ j∈D ∑ pi P ( pi|sj , aj ) ∣∣∣Qi(sj , aj)− Q̂D(sj , aj)∣∣∣ = 1
|D| ∑
unique(s,a)∈D ∑ j∈D 1s,a(j) ∑ pi ∑ j∈Di 1s,a(j)∑ j∈D 1s,a(j) ∣∣∣Qi(sj , aj)− Q̂D(sj , aj)∣∣∣ = 1
|D| ∑
unique(s,a)∈D ∑ pi ∑ j∈Di 1s,a(j) ∣∣∣Qi(sj , aj)− Q̂D(sj , aj)∣∣∣ = 1
|D| ∑ j∈D ∣∣∣Qij (sj , aj)− Q̂D(sj , aj)∣∣∣ = 1|D|∑ j∈D ∣∣∣E [Rj |sj , aj , pij ]− Q̂D(sj , aj)∣∣∣ Plugging in the Jensen inequality for all sj , aj , pij∣∣∣E [Rj |sj , aj , pij ]− Q̂D(sj , aj)∣∣∣ ≤ E [|Rj − Q̂D(sj , aj)|∣∣∣sj , aj , pij] we obtain
LL1(Q̂D) ≤ 1 |D| ∑ j∈D E [ |Rj − Q̂D(sj , aj)| ∣∣∣sj , aj , pij] . In the limit when |D|→ ∞ the sample average converges to the expectation, i.e. 1|D| ∑ j∈D [·] → E [·], therefore
LL1(Q̂D) ≤ 1 |D| ∑ j∈D E [ |Rj − Q̂D(sj , aj)| ∣∣∣sj , aj , pij] = E [ E [ |Rj − Q̂D(sj , aj)|
∣∣∣sj , aj , pij]] = E [ |Rj − Q̂D(sj , aj)|
] = 1
|D| ∑ j∈D |Rj − Q̂D(sj , aj)|= LMC(Q̂D).
B.2 QD IS A VALUE OF A TIME DEPENDENT POLICY βDs̃,ã
Given a state-action pair s̃, ã, then QD(s̃, ã) is the Q-value of a time dependent policy βDs̃,ã(a|s, k), where k is a time index and s̃, ã is a fixed initial state-action pair,
βDs̃,ã(a|s, k) = ∑ pi βi(a|s)P (pi|s̃, ã k−→ s). (10)
Here the conditional probability is over a uniform sample x ∼ U(Ds̃,ã,k) where Ds̃,ã,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̃, ã.
Proof. For the proof, let us construct an extended MDP, with an additional initial state, termed s0 with N different actions. Following an action selection in state s0, an action ã 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 rule:
1. In state s0, select an action i with probability P (pi|s̃, ã).
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 s0 state with the law of total probability s.t. V β h (s0) = ∑ π Q
i(s̃, ã)P (pi|s̃, ã) = QD(s̃, ã). 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 βDs̃,ã. The Markovian policy satisfies
βDs̃,ã(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
βDs̃,ã(a|s, k) = ∑ i βi(a|s)P (a(s0) = i|s0 k−→ s),
where a(s0) is the chosen action in state s0. Notice that s̃, ã deterministically follow state s0 so by applying Bayes’ theorem, we get that
P (a(s0) = i|s0 k−→ s) = P (a(s0) = i)P (s̃, ã
k−→ s|a(s0) = i)
P (s̃, ã k−→ s)
= P (pi|s̃, ã)P (s̃, ã k−→ s|βi)∑ pj P (p j |s̃, ã)P (s̃, ã k−→ s|βj) .
Let us define by 1s̃,ã,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̃, ã. We may represent the above expression with the indicator summation notation
P (pi|s̃, ã)P (s̃, ã k−→ s|βi)∑ pj P (p j |s̃, ã)P (s̃, ã k−→ s|βj) =
∑ j∈Di 1s̃,ã∑ j∈D 1s̃,ã ∑ j∈Di 1s̃,ã,k,s∑ j∈Di 1s̃,ã∑
pi′ (∑ j∈Di′ 1s̃,ã∑ j∈D 1s̃,ã ∑ j∈Di′ 1s̃,ã,k,s∑ j∈Di′ 1s̃,ã
) = ∑j∈Di 1s̃,ã,k,s∑ j∈D 1s̃,ã,k,s .
Finally, the last expression can be transformed back to conditional probability notation of the form∑ j∈Di 1s̃,ã,k,s∑ j∈D 1s̃,ã,k,s = P (pi|s̃, ã k−→ s)

heading: C SAFE POLICY IMPROVEMENT

heading: C.1 REROUTE IS A SUBSET OF TV
text: The set of reroute policies with [cmin, cmax] is a subset of the set of δ-TV policies, where δ = min(1− cmin,max( cmax−12 , 1−cmin 2 )). Proof. For a reroute policy, the TV distance is 12 ∑ a β(ai|s)|1 − ci|≤ ∑ a β(ai|s)δ = δ. For the second upper bound 1−cmin, notice that a rerouted policy {πi}may be written as πi = cminβi+δi, where δi ≥ 0. Therefore, the TV distance is
TV = 1
2 ∑ i |πi − βi|= 1 2 ∑ i |cminβi + δi − βi|≤ 1 2 ∑ i ((1− cmin)βi + δi) ,
but 1 = ∑ i πi = ∑ i(cminβi + δi) = cmin + ∑ i δi. Thus, ∑ i δi = 1− cmin and we may write
TV ≤ 1 2 ((1− cmin) + (1− cmin)) = 1− cmin.
To show that the TV region is not in reroute, take any policy with a zero probability action and another action with a probability of β(ai|s) ≤ δ. The policy which switches probabilities between these two actions is in TV (δ) but it is not in reroute for any finite cmax.

heading: C.2 SOFT POLICY IMPROVEMENT
text: 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
Ππaβ ≥ 0
Proof. Plugging in aβ = qβ − vβ and using vβ = Ππvβ , we get that
vβ ≤ Ππqβ = Ππ(r + γP̃vβ) = rπ + γPπv vβ . (11)
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 )2vβ ≤ rπ+
γPπv r π + γ2(Pπv ) 2rπ + γ3(Pπv ) 3vβ ≤ ... ≤ ∑ k≥0 γk(Pπv ) krπ = (I − γPπv )−1rπ = vπ.
(Schulman et al., 2015) have shown that
J(π)− J(β) = ET∼π ∑ k≥0 γkAβ(sk, ak)  . This equation can also be written as
J(π)− J(β) = ∑ k≥0 γkEsk∼π|s0 [∑ a∈A π(a|sk)Aβ(sk, ak) ] =
= ∑ k≥0 γk ∑ s∈S P (s0 k−→ s|π) ∑ a∈A π(a|s)Aβ(s, a) =
∑ s∈S ∑ k≥0 γkP (s0 k−→ s|π) ∑ a∈A π(a|s)Aβ(sk, a).
Recall the definition of the discounted distribution of states ρπ(s) = ∑ k≥0 γkP (s0 k−→ s|π),
we conclude that J(π)− J(β) = ∑ s∈S ρπ(s) ∑ a∈A π(a|s)Aβ(s, a)

heading: C.3 RANK-BASED POLICY IMPROVEMENT
text: Proof. Denote by i the index of the advantage ordered list {Ai}. Since ∑ ai βiA β i = 0, we can write it as an equation of the positive and negative advantage components
N∑ a=ip βiA β i = in∑ a=0 βi(−Aβi ),
where ip is the minimal index of positive advantages and in is the maximal index of negative advantages. Since all probability ratios are non-negative, it is sufficient to show that
N∑ a=ip ciβiA β i ≥ in∑ a=0 ciβi(−Aβi ).
But clearly
N∑ a=ip ciβiA β i ≥ cip N∑ a=ip βiA β i ≥ cin in∑ a=0 βi(−Aβi ) ≥ in∑ a=0 ciβi(−Aβi ).

heading: C.4 POLICY IMPROVEMENT PENALTY
text: 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:
V π(s)− V β(s) ≥ − ∑ s′∈S ∑ k≥0 γkP (s k−→ s′|π) ∑ a∈A ε(s′, a) (β(a|s′)− π(a|s′)) . (12)
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 P̃v ≥ P̃u. 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 ) nq̂β ≥ q̂β + n∑ k=0 γk(Pπq ) ky.
We showed it for n = 1, assume it holds for n, then for n+ 1 we obtain
(Tπq ) n+1q̂β = Tπq (T π q ) nq̂β ≥ Tπq
( q̂β +
n∑ k=0 γk(Pπq ) ky
) =
= Tπq q̂ β + n∑ k=0 γk+1(Pπq ) k+1y ≥ q̂β + y + n∑ k=0 γk+1(Pπq ) k+1 = q̂β + n+1∑ k=0 γk(Pπq ) ky.
Using the contraction properties of Tπq , s.t. limk→∞(T π q ) kx = 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 )ε
= 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 ) kPπq = Π π(P̃Ππ)kP̃Ππ = (ΠπP̃)k+1Ππ = (Pπv )k+1Ππ , and in the same manner, Ππ(Pπq ) kP βq = (P π v ) k+1Πβ . Therefore, we can write
vπ ≥ vβ − ∑ k≥0 γk(Pπv ) k(Πβ −Ππ)ε,
which may also be written as (12).

heading: C.5 UNBOUNDED PROBABILITY RATIOS IN THE TV AND KL CONSTRAINTS
text: To verify that TV and KL do not regulate the probability ratios, let’s consider a tiny example of maximizing the objective function JPPO for a single state MDP with two actions {a0, a1}. 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, 12 (1 − (1 − α) + α) = α ≤ δ. The improvement step in this case is∑ ai Aβi πi = α. Hence the solution is α = δ and the probability ratio π(a1)/β(a1) 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.

heading: C.6 MAX-TV
text: Algorithm 2: Max-TV Data: s, β, AD, δ Result: {π(a|s), a ∈ A} begin
π(a|s)←− β(a|s), ∀a ∈ A a = arg maxa∈ÃA
D(s, a) ∆ = min{δ, 1− β(a|s)} π(a|s)←− π(a|s) + ∆ Ã ←− A while ∆ > 0 do
a = arg mina∈ÃA D(s, a) ∆a = min{∆, β(a|s)} Ã ←− Ã/a ∆←− ∆−∆a π(a|s)←− π(a|s)−∆a

heading: C.7 THE PPO OBJECTIVE FUNCTION
text: 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:
JPPO(π) = Es∼β [∑ 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, JPPO 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 ci = π(ai|s)β(ai|s) and βi = β(ai|s). Then, we can write the PPO objective of state s as
JPPO(π, s) = ∑ ai∈A+ βiA β i min (ci, 1 + ε)− ∑ ai∈A− βi(−Aβi ) max (ci, 1− ε) .
Clearly maximization is possible (yet, still not unique) when setting all ci = 0 for ai ∈ A−, namely, discarding negative advantage actions. This translates into a reroute maximization with parameters (cmin, cmax) = (0, 1 + ε)
arg max ci [JPPO(π, s)] = arg max ci  ∑ ai∈A+ βiA β i min (ci, 1 + ε)  = arg max ci  ∑ ai∈A+ ciβiA β i  for ci ≤ 1 + ε. The only difference is that the sum ∑ i ciβ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̃ = {Ã+, Ã−} Ã ←− A+ ∆←− 1 π(a|s)←− 0 ∀a ∈ A while ∆ > 0 and |Ã|> 0 do
a = arg maxa∈ÃA β(s, a) ∆a = min{∆, (1 + ε)β(a|s)} Ã ←− Ã/a ∆←− ∆−∆a π(a|s)←− π(a|s) + ∆a
a = arg maxa∈AA β(s, a) π(a|s)←− π(a|s) + ∆

heading: D TAXI EXPERIMENT: TECHNICAL DETAILS
text: 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 {sj}500j=1. For N players, the definitions for our the selection types are Row Selection: {
sj ∈ S∗i ∣∣∣∣(j − i500N ) (mod500) < 250 } Column Selection: {
sj ∈ S∗i ∣∣∣∣(j + i) (modN) < N2 } 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,aNs (see the first item in Definition 4.1). For Monte-Carlo learning, we applies the following update rule
Qβ(s, a)←− Qβ(s, a) + α ( R−Qβ(s, a) ) , (13)
where α = 0.1 is a learning rate and Rs,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
Qβ(s, a)←− Qβ(s, a) + α ( r + γ
∑ a′ β(a′|s′)Qβ(s′, a′)−Qβ(s, a)
) , (14)
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,aNs .

heading: E ATARI EXPERIMENT: TECHNICAL DETAILS

heading: E.1 DATASET PREPROCESSING
text: 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 mod4 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.

heading: E.2 LEARNING FROM HUMAN PLAYERS
text: 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 NonMarkovian 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.

heading: E.3 NETWORK ARCHITECTURE
text: 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 {Ãi}i and the Q-function outputs are therefore expressed as
Qβi = V β + Ãi − ∑ j Ãjβj , (15)
where {βj}j are the outputs of the policy network. Note that ∑ iQ β i = V
β . The normalized advantage is therefore Aβi = Ãi − ∑ j Ã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 CrossEntropy Loss. For the value network, though the theoretical bound in the paper is calculated for the L1 loss, we found that slightly better results are obtained with the MSE loss. This may be due to better regression of outliers. All results reported in the paper used the MSE loss for value.

heading: E.4 LEARNING PROCESS
text: A single iteration of our learning process is depicted with the following PyTorch style pseudo-code. Value and Behavioral networks are trained simultaneously on the same sample. The state is passed through the beta net once in training mode (with dropout) and once in evaluation mode (without dropout) for the advantage calculation.

heading: E.5 EVALUATION
text: The execution of a RBI policy at evaluation time is depicted with the following pseudo-code.
b e t a n e t . e v a l ( ) v a l u e n e t . e v a l ( )
t = 0 s c o r e = 0 s = env . r e s e t ( )
whi le not t :
b e t a = b e t a n e t ( s ) q , adv , v = v a l u e n e t ( s , b e t a ) p i = m a x r e r o u t e ( be t a , adv , c min , c max ) a = c h o i c e ( p i )
s , r , t = env . s t e p ( a )
s c o r e += r

heading: F FINAL POLICY PERFORMANCE TABLE

heading: E.6 HYPERPARAMETERS TABLES

Review summaries:
The paper looks at learning a policy from multiple demonstrators which should also be safely improved by an reinforcement learning signal. They define the policy as a mixture of policies from the single demonstrators. The paper gives a new way to estimate the value function of each policy where the overall policy is defined as mixture of the single policies. The paper subsequently looks at the standard error of the value function estimation and then define the policy improvement step in the presence of value estimation error. The resulting reroute constraint for the policy improvement step is evaluated on the taxi toy task as well as on 4 different atari domains. 

In this paper, the authors study the problem if learning for observation, a reinforcement learning setting where an agent is given a data set of experiences from a potentially arbitrary number of demonstrators. The authors propose a method which deploys these experience to initialize a place. Then estimate the value of this policy in order to improve it.