{'fraction_non_alphanumeric': 0.04095962551199532, 'fraction_numerical': 0.013537954146497154, 'mean_word_length': 4.456247279059643, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 1, 'https://': 2, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 8, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Improving Sample Efficiency in Evolutionary RL Using Off-Policy Ranking

Evolution Strategy (ES) is a powerful black-box optimization technique based on the idea of natural evolution. In each of its iterations, a key step entails ranking candidate solutions based on some fitness score. For an ES method in Reinforcement Learning (RL), this ranking step requires evaluating multiple policies. This is presently done via on-policy approaches: each policy's score is estimated by interacting several times with the environment using that policy. This leads to a lot of wasteful interactions since, once the ranking is done, only the data associated with the top-ranked policies is used for subsequent learning. To improve sample efficiency, we propose a novel off-policy alternative for ranking, based on a local approximation for the fitness function. We demonstrate our idea in the context of a state-of-the-art ES method called the Augmented Random Search (ARS). Simulations in MuJoCo tasks show that, compared to the original ARS, our off-policy variant has similar running times for reaching reward thresholds but needs only around 70% as much data. It also outperforms the recent Trust Region ES. We believe our ideas should be extendable to other ES methods as well.


Introduction
In optimization, features of the objective function such as linearity, convexity, or differentiability often are either nonexistent, unknown, or impossible to detect. An Evolution Strategy (ES), due to its derivative-free nature, is a go-to alternative in such scenarios. Salimans et al. (2017) proposed the first competitive ES method in Reinforcement Learning (RL) settings. However, its effectiveness relies heavily on several complicated ideas and the usage of neural networks for parameterizing the policies. Thankfully, the Augmented Random Search (ARS), a recent ES method by Mania, Guy, and Recht (2018), showed that such complications are not needed for a state-of-the-art RL approach. In particular, it demonstrated that it suffices to work with only deterministic linear policies. Our work proposes a novel off-policy variant of the ARS method that has running times comparable to the original one yet needs only 70% as much data.
The formal motivation for our work is as follows: explore ES algorithms in RL that minimize the number of agentenvironment interactions while keeping the control policy as simple as possible. Clearly, this would be of significance in practical RL. A vital example is robotics, where collecting samples is very expensive since the process involves active calibration, maintenance, and safety checks for every component, and overlooking these can result in unsafe behaviours. Under these constraints, any improvement in sampling efficiency would be considered significant.
We now provide an overview of the ES philosophy. As the name suggests, ES is an iterative optimization framework inspired by evolution; see (Li et al. 2020) for a recent survey. In each iteration, an ES method i.) obtains a bunch of candidate solutions from some sampling distribution, ii.) ranks them using some fitness score based on the objective function, and iii.) uses the top-ranked ones to update the sampling distribution for use in the next iteration.
In a typical ES method for RL, a candidate solution is a specific policy, while its fitness is the associated value function. Existing techniques, including ARS, use an onpolicy approach to find this fitness score: interact several times with the environment using the policy whose score needs to be estimated. Since multiple policies need to be ranked in each iteration, current ES approaches end up with significantly high interactions. Notably, most of this data is discarded in each iteration except those related to the topranked policies. Our proposed ARS variant improves sample efficiency by replacing this wasteful approach with an offpolicy alternative. We remark that this is the first ES method in RL, where an off-policy approach is used for ranking.
Our ranking technique improves sample complexity due to two novel features: i.) the fitness function choice and ii.) the use of a kernel approximation to estimate the same.
Fitness Function: Instead of using the value function η(π) of a candidate policyπ as its fitness score, our approach employs its approximation L π (π) defined in terms of a different policy π called the behavior policy (Zhang and Ross 2021, (6)). Indeed, any ranking of policies based on an approximation to the value function is going to be sub-optimal. However, it is also the key factor that enables off-policy ranking. As we shall see, the data generated by the single policy π can now be used to rank all the candidate policies! Kernel Approximation: L π (π) is estimated in (Zhang and Ross 2021) via importance sampling (see (40) in ibid). This approach works only when both π andπ are stochastic. However, the sample efficiency of ARS crucially relies on the candidate policies being deterministic. Therefore, simply using stochastic policies in ARS to incorporate the importance sampling idea isn't ideal for sample efficiency. To circumvent this issue, we propose to alternatively smooth the deterministic policies using a suitable kernel function. This approach is loosely inspired from (Kallus and Zhou 2018;Kallus and Uehara 2020), which studies extending ideas from discrete contextual bandit settings to the continuous case.
The role of L π (π) in (Zhang and Ross 2021) and our work is quite different. There it is used to approximate an intermediate objective function within a policy improvement scheme, i.e., L π (π) plays a direct role in their update rule (see (13) in ibid). Here, instead, we use it only for coarsely ranking multiple candidate policies in a sample-efficient fashion. In other words, L π (π) needs to be accurately estimated in (Zhang and Ross 2021), while a rough estimate suffices for us. Importantly, since the policies there are stochastic, a complex neural network is additionally needed for improving their sample efficiency. This complication is avoided here because ourπ's and π are all deterministic.
Key Contributions: We now summarize the main highlights of this work.
1. We propose a novel off-policy variant of ARS; see Algorithm 1. Specifically, we replace the wasteful on-policy ranking step with an efficient off-policy version. This is the first usage of an off-policy ranking in an ES. Also, while we apply it only for ARS here, the proposed method can be extended to other ES methods. 2. Our simulations on benchmark MuJoCo locomotion tasks (Section 5) show that our method reaches reward thresholds in running times comparable to the original ARS. Further, it needs only 70% as much data. This is significant when getting data about interactions with the environment is either hard or expensive, e.g., robotics. 3. We also do sensitivity to seed and hyperparameter tests similar to (Mania, Guy, and Recht 2018). Our results are similar in spirit to what was obtained in the ARS case. That is, the median trajectory crosses the reward threshold in most environments, confirming that our algorithm is robust to seed and hyperparameter choices.

Relevant Background and Research Gap
We provide here a brief overview of some of the important advances in RL relevant to our work. At the end, we also describe the current research gap that our work addresses. While RL has been around since the 1950s, it is only in the last decade-thanks to cheap computing and deeplearning advances-that we have seen any evidence of human and superhuman level performances. The pioneering work here was (Mnih et al. 2015) which proposed the Deep Q Network (DQN). This algorithm combines the popular Q-learning approach with a class of artificial neural networks. In particular, this was the first work to demonstrate that instabilities due to nonlinear function approximators can be handled effectively. A major issue with DQN though is that it can only handle discrete and low-dimensional action spaces. The seminal Deep Deterministic Policy Gradient (DDPG) algorithm in (Lillicrap et al. 2016) was proposed to overcome this issue.
In a different direction, Schulman et al. (2015) proposed a policy iteration algorithm in the discounted reward setting called Trust Region Policy Optimization (TRPO). This was recently generalized to the average reward case by Zhang and Ross (2021). Both these methods, in each iteration, repeatedly try to identify a better policy in the neighborhood of the current estimate. The difficulty, however, is that the value functions of neighbourhood policies are unknown. Schulman et al. (2015) and Zhang and Ross (2021) resolve this by instead finding a policy that is best with respect to a local approximation of the value-function such as L π (π). In the Atari domain, TRPO outperforms previous approaches on some of the games. More recently, Schulman et al. (2017) introduced the Proximal Policy Optimization (PPO) method. This is a descendant of TRPO, which is easier to implement and has a better sample complexity than previous approaches.
On the ES literature side, the first competitive RL method was the one given in (Salimans et al. 2017). It is a derivativefree optimization method with similar or better sample efficiency than TRPO in most MuJoCo tasks. However, this advantage is a consequence of several complicated algorithmic ideas; see Section 3.4 of (Mania, Guy, and Recht 2018) for the details. It is indeed true that this algorithm has scope for massive parallelization and, hence, can train policies faster than other methods. However, this benefit is realizable only if data from multiple policies can be obtained in parallel. This is often not the case in practical RL, e.g., in robotics, one typically has access only to a single robot and, hence, can obtain data only from a single policy at any given time. Mania, Guy, and Recht (2018) showed that all these complications and the usage of neural networks are often unnecessary. Instead, to obtain the state of the art time and data efficiency, it suffices to work with deterministic linear policies and a basic random search with some minor tweaks.
The LQR simulations in Section 4.4 of (Mania, Guy, and Recht 2018), however, showed that the current ARS implementation is not sample efficient in the optimal sense. Our proposed ARS variant significantly improves upon the sample efficiency of ARS without overly complicating its control policy. We also emphasize that, while this work is in the context of ARS, our off-policy ranking approach should also be useful in other ES methods.

Preliminaries
Here, we describe our RL setup and provide an overview of the original ARS algorithm.

RL Setup and Important Definitions
Let ∆(U ) denote the set of probability measures on a set U. At the heart of RL, we have an infinite-horizon Markov Decision Process (MDP) represented by (S, A, P, r, ρ 0 ). In this tuple, S denotes the state space, A represents the action space, P : S × A → ∆(S) and r : S × A × S → R are deterministic functions such that P(s |s, a) ≡ P(s, a, s ) specifies the probability of moving from state s to s after taking action a and r(s, a, s ) is the one step reward obtained in this transition, and, finally, ρ 0 is the initial state distribution.
The main goal in RL is to identify the 'best' way to interact with the MDP. We now describe this point in some detail. Any stationary interaction strategy is defined via a policy π : S → ∆(A) which gives a rule for picking an action when the environment is in a particular state. The quality of such a policy is the expected average 1 reward obtained on a single trajectory. Specifically, for a policy π, i.) a trajectory refers to a sequence τ ≡ (s 0 , a 0 , s 1 , a 1 , . . .) of states and actions, where s 0 ∼ ρ 0 , a 0 ∼ π(s 0 ), s 1 ∼ P(·|s 0 , a 0 ), a 1 ∼ π(s 1 ) and so on, and ii.) its quality is given by its value function whereη The aforementioned goal then is to find a policy that solves max π η(π). (3) Because of the MDP, the sequence of states observed under a policy π forms a Markov chain. If this chain has a stationary distribution d π and then η(π) = E s∼dπ,a∼π [r(s, a)]. Note that this expression is independent of the initial distribution ρ 0 . In our later discussions, we will also be using some terms related to the value function such as the state-bias function, action-bias function, and the advantage function. These are denoted by V π , Q π , and A π , and given by (r(s t , a t ) − η(π))|s 0 = s, a 0 = a and A π (s, a) := Q π (s, a) − V π (s), respectively.

Review of ARS
In this subsection, we shall see how ARS solves the optimization problem given in (3).
ARS belongs to a family of iterative black-box optimization methods called random search (Matyas 1965). Basic Random Search (BRS) is the simplest member of this family and is also where the origins of ARS lie. For ease of exposition, we first explain BRS's approach to solving (3). Throughout this subsection, we restrict our attention to finitehorizon MDPs where the search space is some parameterized family of policies. Note that this is often the case in practical RL and is also what we deal with in our MuJoCo simulations.
For the above setup, the optimization problem in (3) trans- In general, this objective function need not be smooth. To circumvent this issue, BRS looks at its smooth variant and then uses the idea of a stochastic gradient ascent. Specifically, the alternative objective considered is E δ E τ [η(π θ+νδ )], where ν is a suitably fixed scalar, and δ is a random perturbation made up of i.i.d. standard Gaussian entries. Further, in each iteration, the gradient of this function is estimated via a finite difference method. That is, N random directions δ 1 , . . . , δ N are first generated in the parameter space,η(π θ+νδ k ) and η(π θ−νδ k ) are then estimated by interacting with the environment using π θ+νδ k and π θ−νδ k for each k, and finally 1 N N k=1 [η(π θ+νδ k ) −η(π θ−νδ k )]δ k is used as a proxy for the gradient at θ. BRS's update rule, thus, has the form for some parameter choice α > 0. Mania, Guy, and Recht (2018) developed ARS by making the following changes to BRS. To begin with, they restricted the search space to a class of deterministic and linearly parameterized policies: a policy now is represented by a matrix M and the vector M s denotes the deterministic action to be taken at state s under that policy. Further, they made three modifications to the update rule of BRS. The first was to scale the gradient estimate by the standard deviation of theη values; this yields the ARS-V1 algorithm. The second was to normalize the states, given as input to the policies, so that all its components are given equal importance; this yields ARS-V2. The final modification was to pick some b < N and use only the b best-performing search directions for estimating the gradient in each iteration. The first and the third step yield the ARS-V1t algorithm, while the combination of all three gives ARS-V2t. The ARS-V2t variant is of most interest to us and its update rule has the form where σ R is the standard deviation of the 2bη values, δ (k) denotes the k-th largest direction, decided based on the value of max{η(π j,k,+ ),η(π j,k,− )} for different k choices, and with µ j and Σ j being the mean and covariance of the 2bHj states encountered from the start of the training.
The reason for focusing on ARS-V2t is that, in MuJoCo tasks, it typically outperforms the other V1 and V2 variants of ARS and also the previous state-of-the-art approaches such as TRPO, PPO, DDPG, the ES method from (Salimans et al. 2017), and the Natural Gradient method from (Rajeswaran et al. 2017). This demonstrates that normalization of states and then ranking and only picking the best directions for updating parameters often helps in improving the sample efficiency. Nevertheless, in each iteration, ARS uses an on-policy technique to estimateη(π j,k,+ ) andη(π j,k,− ) for each k so that the b best-performing directions can be identified. Because of this, we claim that ARS still does more interactions Algorithm 1: Off-policy ARS 1: Setup: State space R n , Action Space R p 2: Hyperparameters: step-size α, number of directions sampled per iteration N , standard deviation of the exploration noise ν, number of top-performing directions to use b, bandwidth to use for kernel approximation h, number of behaviour policy trajectories to run n b 3: Initialize: M 0 = 0 ∈ R p×n , µ 0 = 0 ∈ R n and Σ 0 = I n ∈ R n×n (identity matrix), j = 0 4: while ending condition not satisfied do 5: Sample δ 1 , δ 2 , . . . , δ N in R p×n with i.i.d. standard normal entries 6: Run n b number of trajectories using policy parameterized by M j , resulting in N d number of interactions 7: Sort the directions δ k based on f πj (δ k , h) scores (using (9)), denote by δ (k) the k-th largest direction, and by π j,(k),+ and π j,(k),− the corresponding policies 8: Collect 2b rollouts of horizon H and their corresponding return (η(·)) using the 2b policies Make the update step: where σ R is the standard deviation of 2b returns used in the update step.

10:
Set µ j+1 , Σ j+1 to be the mean and covariance of the 2bH(j + 1) states encountered from the starting of training 11: j ← j + 1 12: end while with the underlying environment than what is needed. Also, in each iteration, it discards the data that do not correspond to the top-ranked policies.

Off-policy ARS: Our proposed method
Here, we describe the details of our proposed approach which improves upon the wasteful on-policy ranking step in ARS.
Intuitively, in each iteration of our ARS variant, we plan to identify a suitable deterministic policy, interact with the environment using just this single policy, and then use the resultant data to rank the 2N deterministic policies {π j,k,+ , π j,k,− : 1 ≤ k ≤ N }. As a first step, we come up with a way to approximate the value function of a deterministic policyπ in terms of another deterministic policy π. We focus on deterministic policies here since ARS's performance crucially depends on this determinism.
If π andπ were stochastic in nature, then such an approximation has already been given in (Zhang and Ross 2021), which itself is inspired from similar estimates given in (Kakade and Langford 2002) and (Schulman et al. 2015). We now discuss the derivation of this approximation.
Consider the average reward RL setup described in Section 3.1. Suppose that, for every stationary policy π, the induced Markov chain is irreducible and aperiodic and, hence, has a stationary distribution d π satisfying (4). In this framework, (Zhang and Ross 2021, Lemma 1) showed that the value functions of the two stochastic policies π andπ satisfy η(π) = η(π) + E s∼dπ,a∼π [A π (s, a)] .
Given this relation, a natural question to ask is whether η(π) can be estimated using just the data collected by interacting with the environment using π. The answer is no, mainly because the expectation on the RHS is with respect to the states being drawn from dπ. In general, this distribution is not known a priori and is also hard to estimate unless you interact with the environment withπ itself. Inspired by (Kakade and Langford 2002) and (Schulman et al. 2015), Zhang and Ross (2021) proposed using as a proxy for the RHS in (6) to overcome the above issue. There are two main reasons why this was a brilliant idea. The first is that L π (π), since it uses d π instead of dπ, can be estimated from only environmental interactions involving π. Second, and importantly, (Zhang and Ross 2021, Lemmas 2, 3) showed that |L π (π) − η(π)| is bounded by the total variation distance between π andπ. Thus, when π andπ are sufficiently close, an estimate for L π (π) is also one for η(π). Hence, L π (π) paves the way for estimating η(π) in an off-policy fashion, i.e., using data from a different policy π. Henceforth, we refer to the policy chosen for interaction (e.g., π above) as the behavior policy and the one whose value needs to be estimated (e.g.,π above) as the target policy. We now extend the above idea to the case with deterministic policies, which we emphasize is one of our main contributions. While the idea may look simple on paper, the actual extension is not at all straightforward. The key issue is that, in the case of stochastic policies, the idea of importance sampling and, in particular, the relation E s∼dπ,a∼π [A π (s, a)] = E s∼dπ,a∼π π(a|s) π(a|s) A π (s, a) is used for estimating the second term in (7). However, for deterministic policies, the ratioπ(a|s)/π(a|s) will typically be 0, which means the estimate for the second term will also almost always be zero. Hence, this importance sampling idea for estimating L π (π) fails for deterministic policies. The alternative we propose is to modify the definition of L π (π) so that it becomes useful even for deterministic policies. Specifically, we redefine L π (π) as L π (π) = η(π) + E s∼dπ,a∼π where K h (u) = h −1 K(u/h) and K : R → R denotes a suitably chosen kernel function satisfying K(u)du = 1 and uK(u)du = 0. This approach is loosely inspired from (Kallus and Zhou 2018; Kallus and Uehara 2020) which look at extending policy evaluation and control algorithms from discrete contextual bandit settings to the continuous case.
The reason for the above choice of K is that it performs quite well in simulations and, importantly, provides a clean intuitive explanation for L π (π). That is, L π (π) assigns a higher value to a policyπ if it takes actions similar to π at all those states s where A π (s, π(s)) is large. In summary, L π (π) given above provides us with the desired expression to approximate the value function of a deterministic target policy with only the data from a deterministic behavior policy. We now discuss incorporating this expression in ARS to improve its sample efficiency. In particular, we now show how we can rank the 2N policies {π j,k,+ , π j,k,− }, generated randomly in each iteration of ARS, in an off-policy fashion (see Section 3.2 for further details on ARS).
The first thing we need to decide is the choice of the behavior policy for interacting with the environment. Recall from the discussion below (7) that |η(π) − L π (π)| is small when π andπ are sufficiently close. Now, since the policy parameterized by M j is close to each of the 2N policies specified above, it is the natural choice for the behavior policy and, indeed, this is what we use.
In summary, our ranking in each iteration works as follows: 1. Interact with the environment using the behavior policy π j ≡ π Mj on n b number of trajectories. Each trajectory here is presumed to have H many time steps (or less in case of premature termination). Suppose these interactions result in N d (s t , a t , r t , s t+1 ) transitions overall. 2. Estimate Q πj (s t , a t ), 0 ≤ t ≤ N d − 1, using the definition given in Section 3.1.

Estimate
for each 1 ≤ k ≤ N. Note that f πj (δ k , h) is a proxy for the expression in (8). In that, it ignores all the constant terms, those that depend only on the behavior policy π j . 4. Use the above estimates to rank {π j,k,+ , π j,k,− }.
Once the b best-performing directions are identified, the rest of our ARS variant more or less proceeds as the original. That is, we come up with better estimates of the valuefunctions of these top policies in an on-policy fashion and improve upon M j along the lines discussed in (5). The complete details are given in Algorithm 1. A detailed section discussing the differences in the original ARS from our offpolicy variant is given in Appendix A.
We end our discussion here by pointing out that the original ARS used 2N interaction trajectories, each of length roughly H, in each iteration. In our variant, we only need 2b + n b many trajectories. When b < N, this difference is what leads to the 30% reduction in interactions seen in our simulations.

Experiments
We compare our method with ARS (Mania, Guy, and Recht 2018) and TRES (Liu et al. 2019) on the benchmark MuJoCo (Todorov, Erez, and Tassa 2012) tasks available in OpenAI gym (Brockman et al. 2016). More details about the environment is given in Appendix B. The implementation details are given in Appendix C. In this section, we first demonstrate our algorithm's improvement in sample efficiency. Next, we thoroughly evaluate the algorithm by running it with 100 random seeds to show that it is robust. Later, we show that our algorithm is not sensitive to hyperparameters' choices. We observer that our algorithm is more sample efficient than ARS on the Linear Quadratic Regulator (LQR) problem too (see Appendix F).

Improvement in Sample efficiency
Generally, the sample complexity of benchmark MuJoCo tasks is reported by the number of interactions required to reach a certain reward threshold. There are many thresholds used in previous work, namely (Gu et al. 2017), (Rajeswaran et al. 2017), (Salimans et al. 2017) and (Mania, Guy, and Recht 2018). We continue to use the same thresholds as in ARS. Mania, Guy, and Recht (2018) use three seeds to benchmark the performance of the algorithms. We observe that the results are susceptible to the seeds. Hence, we consider eight seeds to get better estimates. We use sixteen seeds in Walker2d-v3 as the success rate in that environment is less. We compare our algorithm against ARS (Mania, Guy, and Recht 2018) and Trust Region Evolution Strategies(TRES) (Liu et al. 2019), which more efficiently uses the sample data than ES. We use the author's code of ARS and the author's code of TRES to run our experiments. We present the results as two scenarios.
We now discuss the first scenario where ARS-V2t performs better than ARS-V2. This is the case with Swimer-v3, Hopper-v3, Walker2d-v3, and Ant-v3 environments (see Appendix D). Our algorithm significantly improves the number of interactions in all the above environments except Ant-v3. Table 1 summarizes the comparison with various algorithms.
Our experiments confirm that the off-policy ARS often gets stuck at the local optima in the Ant-v3 environment. We guess the stagnation happens because, near the local maxima, the approximate off-policy ranking forces the updates in different iterations to be in opposing directions. Interleaving with on-policy estimations in such situations appears to help overcome this oscillatory behavior. If our above understanding is correct, then the reason for the stagnation is a bit of both sub-optimal ranking criteria and a poor exploration strategy. We believe additional studies will be needed to develop a robust strategy to deal with this issue.
We now discuss the second scenario where ARS-V2 is better than ARS-V2t in Humanoid-v3. This is because the sample complexity increases with increase in N . Our algorithm performs better in these situations; because we can evaluate more directions without much increase in sample complexity.  Table 1: Comparison of ARS, TRES, and our method on MuJoCo locomotion tasks. We show the median number of interactions required to achieve the prescribed reward threshold for each task. The reached column represents the fraction of the experiments that reach the threshold. The timesteps are in the order of 10 3 . The * in Ant-v3 signifies the interleaving of on-policy evaluations. (5)  Humanoid-v3 is considered the most challenging MuJoCo environment. Table 1 displays the median of the timesteps needed for the first crossover of the specified reward threshold. Specifically, the numbers in the table confirm that the first crossover in our off-policy ARS happens much earlier than in the original variant. However, the variance in results is not captured well. Figure 1 consists of box plots of the number of interactions required to reach the threshold in ARS, TRES, and our method. The number of experiments that reached the threshold is mentioned next to the algorithm's name. The variance in our approach is either less or comparable to ARS in all environments. Interestingly, our method's median is lesser in all the environments except Ant-v3.

Evaluation over 100 random seeds
As discussed in the previous sub-section, our method performs better than ARS and TRES over eight seeds. While it is well known that RL algorithms suffer high training variances, we evaluate our algorithm over 100 random seeds sampled uniquely from [0,10000]. Figure 2 consists of the plots from this experiment. We see that the median (thick blue line) crosses the threshold in all the environments except Swimmer-v3 and Walker2d-v3. This is because of comparatively lower success rates in these environments.

Sensitivity to hyper-parameters
In this subsection, we look at the sensitivity of our algorithm to the two hyperparameters we introduce: h and n b . We first, identify multiple hyperparameter choices for h and n b (see Appendix E). Next, we run our algorithm under all possible combinations of these hyperparameter choices. The performance plots of this experiment (see Figure 3) match those obtained in the 100 seed test done above, thereby demonstrating that the algorithm's performance is not sensitive to hyperparameter choices. Separately, note that we don't look at the sensitivity of our algorithm to other hyperparameters such as ν, α, N, b. Such a study in the context of ARS has already been done in (Mania, Guy, and Recht 2018). Since the role of these parameters in both ARS and our off-policy variant is similar, we expect the sensitivity test to display similar outputs.

Conclusion
This work proposes an off-policy ranking method for sample efficient evolutionary strategy. While traditional off-policy methods are not directly applicable to deterministic policies, we use kernel approximations to perform off-policy evaluations. Our experiments show that our method reached the threshold with only 70% of interactions of what ARS requires in roughly the same run time of the algorithm. We believe our approach is easy to extend to other ES or Random Search methods. A promising direction of future work would be to investigate the same theoretically.
The recent hybrid algorithms that mix ES and Deep RL methods have shown to be more sample efficient than the ES methods. For example, in CEM-RL (Pourchot and Sigaud 2018), half of the policies are trained using off-policy learning techniques like DDPG (Lillicrap et al. 2016) andTD3 (Fujimoto, Hoof, andMeger 2018), leaving the other half policies untouched; however, in the end, all the policies are evaluated by running trajectories. We believe that our off-policy ranking idea can further improve the sample efficiency of these hybrid algorithms.

A Differences in the original ARS from our off-policy variant
In this section we mention the key differences between the original ARS and our off-policy variant. Table 2 indicates the exact steps that differ between the algorithms and its implications.

B Environment details B.1 MuJoCo and OpenAI Gym
Open AI gym (Brockman et al. 2016) is an open-source python library used in benchmarking reinforcement learning Step ARS Our algorithm Implications 6 there is no corresponding step in ARS run n b trajectories the trajectories are run using policy parameterized by M j (used as behavior data for off-policy evaluation) 8 step 5 in ARS; collects 2N rollouts collects only 2b rollouts (note that b < N ) we collect data required only for update step 7 step 6 in ARS; sorts δ k based on returns from the 2N trajectories we sort δ k based on the fitness function (9) derived using offpolicy technique we generate less data as we find the approximate ranking of δs using offpolicy technique even before generating trajectories, unlike in ARS where trajectories are run for all 2N policies to find the rankings 9 step 7 in ARS; uses r(π) for the total reward received from policy π we useη(π) to denote the total reward received from policy π we useη(·) to denote the total reward because we use r(·) for one-step reward 7, 8 step 5, 6 in ARS; first collect data from 2N policies, then rank we first rank; then collect only data from 2b policies we generate less samples as mentioned earlier Table 2: Key differences between ARS and our off-policy variant. The step column refers to the step number in Algorithm 1.
algorithms. It contains many environments, for example, simple environments like pendulum and complex environments like robot locomotion tasks and Atari games. OpenAI gym abstracts the environment and provides an easy API to train RL agents. The agents can observe the current state and apply an action. The library does the simulation and provides the agent with the following observation and instantaneous reward. The robotic locomotion tasks like etc.) use the MuJoCo (Todorov, Erez, and Tassa 2012) simulator in the backend. Notably, the MuJoCo robotic locomotion tasks consist of continuous state-space and action-space. The state representation in each of these environments is the positions and velocities of the center of mass and various robot joints. The action space is the torque to be applied at each of the robot's joints. The instantaneous reward is a function of the current state, action, and next state.

B.2 Linear Quadratic Regulator(LQR)
Linear Quadratic Regulator is a linear dynamical system with quadratic cost. The goal is to devise a control strategy that minimizes the cost. Mathematically, it can be written as the following: Mania, Guy, and Recht (2018) use the LQR instance defined by (Dean et al. 2020). Here, We use the same system mentioned above for our experiments in this paper.

C Implementation details
Mania, Guy, and Recht (2018) implemented a parallel version of the ARS algorithm using the python package Ray (Moritz et al. 2018). They create a centralized noise table with standard normal entries and pass on the starting indices between workers instead of sending the entire perturbation δ. This centralized table avoids the bottleneck of communication. Similar approaches have been taken previously by Moritz et al. (2018) in implementing ES. We adopt the code from Mania, Guy, and Recht (2018) and modify it accordingly to implement our algorithm. Hopper-v3, Walker2d-v3, Ant-v3, and Humanoid-v3 tasks give a survival reward at every time step if the robot does not fall over. This survival rewards cause the ARS and TRES algorithms to learn policies that stand still for long. Hence, Mania, Guy, and Recht (2018) suggest subtracting the survival reward during the training phase. We also adopt the same. The code for ARS is borrowed from https://github.com/modestyachts/ARS and the code for LQR experiments is borrowed from https://github.com/benjamin-recht/benjaminrecht.github.io/tree/master/secret playground.

D ARS-V2 vs ARS-V2t
Mania, Guy, and Recht (2018) benchmarked the ARS algorithms against the v1 versions of MuJoCo locomotion tasks. However, this version is deprecated and no more supported in OpenAI gym. The latest version of these MuJoCo environments is v3. Hence, we now run the ARS V2 and V2t algorithms on the v3 environments. The results from our experiments show that the ARS V2t is better than ARS V2 in all environments except Humanoid-v3 and HalfCheetah-v3 (refer Table 3).

E Hyperparameters
The ARS algorithm consists of hyperparameters, namely, number of search directions N, number of top performing directions k, learning rate α, and noise standard deviation ν. Our off-policy variant has two more hyperparameters: the number of trajectories to run using behavior policy n b and the bandwidth in kernel function h. We use the same hyperparameters from (Mania, Guy, and Recht 2018), and try different values for n b and h as mentioned in Table 4. The final set of hyperparameters that gave us the best results are mentioned in Table 5.

F LQR experiments
As mentioned in Section 4.3 of (Mania, Guy, and Recht 2018), MuJoCo robotic tasks have some drawbacks. Most importantly, the optimal policies of these environments are unknown. Therefore, one is unsure how their algorithm's learned policy compares to the optimal policy. One good idea is to apply the algorithms to simple well known, and well-studied environments whose optimal policy is known. (Mania, Guy, and Recht 2018) chose Linear Quadratic Regulator (LQR) with unknown dynamics for this benchmarking. More details about the environment are given in Appendix B.2. We use the same system used by (Mania, Guy, and Recht 2018) to compare our method with model-based Nominal Control, LSPI (Lagoudakis and Parr 2001) and ARS (Mania, Guy, and Recht 2018). As shown by Mania, Guy, and Recht (2018), the Nominal method is more sample efficient than LSPI and ARS by several orders of magnitude, showing that there is a scope for improvement. Our experiments show that our method is more sample efficient than ARS as shown in Figure 4a . Figure 4c shows that our algorithm is better than ARS in terms of frequency of stability.

G Time Comparison
The hybrid algorithms like CEM-RL (Pourchot and Sigaud 2018) are more sample efficient than vanilla ES methods. However, their run time is too high. Table 6 provides a quick summary of the median wall-clock time (in seconds) taken by each algorithm to reach the threshold. ARS, TRES, and our method are run on CPU (Threadripper 3990X), while CEM-RL is run on GPU (Nvidia RTX 3080-TI). A critical point to note here is that CEM-RL could not solve the Humanoid-v3 environment, which is considered the most challenging environment.      Table 6: Comparing median wall-clock time (in seconds) of ARS, TRES, Off-policy ranked ARS(our method) and CEM-RL.