Hypothesis Driven Coordinate Ascent for Reinforcement Learning
Authors: John Kenton Moore
Junier Oliva
Venue: ICLR 2022 Submitted (2022)
Keywords: Reinforcement Learning
Black-Box Optimization
Hypothesis Testing
Coordinate Ascent
Block Coordinate Ascent
Random Search
MDP

Abstract: This work develops a novel black box optimization technique for learning robust policies for stochastic environments. Through combining coordinate ascent with hypothesis testing, Hypothesis Driven Coordinate Ascent (HDCA) optimizes without computing or estimating gradients. The simplicity of this approach allows it to excel in a distributed setting; its implementation provides an interesting alternative to many state-of-the-art methods for common reinforcement learning environments. HDCA was evaluated on various problems from the MuJoCo physics simulator and OpenAI Gym framework, achieving equivalent or superior results to standard RL benchmarks.

Under review as a conference paper at ICLR 2022
SMPOTHESIS-TEST DRIVEN COORDINATE ASCENT FOR REINFORCEMENT LEARNING
Anonymous authors Paper under double-blind review
ABSTRACT
This work develops novel black box optimization technique for learning policies for stochastic environments. Through combining coordinate ascent with hypothe- sis testing, Hypothesis-test Driven Coordinate Ascent (HDCA) optimizes without computing or estimating gradients. The simplicity of this approach allows it to ex- cel in distributed setting; its implementation provides an interesting alternative many state-of-the the-art art methods for common reinforcement learning environments. HDCA was evaluated on various problems from the MuJoCo physics simulator and OpenAl Gym framework, achieving equivalent or superior results to standard RL benchmarks.
INTRODUCTION
In recent years, Reinforcement Learning (RL) techniques have contributed to striking advancements in artificial intelligence. From mastering complicated games like Go (Silver et al.) (017) to au- tonomous helicopter flight (Ng al., 2006). RI. agents continue to make impressive strides. RI is primarily concerned with discovering a policy that encodes a mapping from states to actions that optimizes rewards within a given environment. This work proposes a method for learning policies in stochastic environments where agent performance is evaluated via a black box function.
Much of RL focuses on Markov Decision Processes (MDPs), where agent's actions are chosen to maximize the expected value of reward function over time (Russell & Norvig 2019). Due to the inherent variability within real-world problem domains, the outcome of these actions depends on the action taken and noise within the environment. MDPs treat time as discrete quantity, where actions are chosen at each time step based on learned policy that leads the agent to a new state. Different states correspond to specific rewards, which are used to refine the policy parameters. Typically, parameter updates are taken in the direction that maximizes the expected reward and often involve calculating (or approximating) gradients.
The function of interest opaque for black box optimization (BBO); only point-wise evaluations possible and the true gradient is inaccessible. As result, gradient-basse based techniques must ap- proximate the true gradient through function sampling and calculating mean and variance estimates. Calculating reliable estimates can be difficult in practice and is made especially challenging by the stochastic nature of MDPs. While various gradient- based BBO methods have found success (Mania) al.) 2018 Salimans et al. 2017 Bibi et al., 2020), they may converge local optima and can be slow to converge for complex domains. As an alternative to gradient approximations, we pro- pose Hypothesis-test Driven Coordinate Ascent (HDCA), which leverages the use of derivative-free optimization (DFO) techniques operating on a black box function.
Our first major insight is to leverage coordinate ascent to decompose the large search space of the original policy optimization problem into sequence of sub-problems with smaller search spaces (Wright 2015). By considering simple enough sub-problems, we are able to optimize each iterate using a basic random search with uniform sampling from a defined search range. This process in- volves generating batches of candidate solutions at each iteration and updating the policy to the best performing candidate. While there are numerous methods to explore the high-dimensional policy space, other more informed search policies, such as Importance Sampling (Bibi et al. 2020), in- volve significant computational overhead as well as additional reliance approximated gradients. Uniform sampling avoids these complications and allows us to take full advantage of modern ad- vances in parallel and distributed computing. While sufficiently exploring the perturbation space

---

Under review as a conference paper at ICLR 2022
may require generating several candidate solutions, each model evaluation may be done entirely in parallel the other candidates. Therefore, with appropriate computational resources, our method can converge in fewer iterations than other current methods.
Our second major insight is to account for the stochastic nature of our optimization problem. That is, the cumulative reward is stochastic quantity whose distribution depends on the stochastic policy and environment. Thus, one must estimate the expected cumulative reward with finite samples of rollouts. This leads variance and uncertainty about true expectations of cumulative rewards for candidate solutions. The stochastic nature (and finite sample estimation) of the cumulative reward criterion has been largely ignored by previous BBO approaches, where the mean over rollouts is (incorrectly) taken as the ground truth criterion. In practice this may result in updates that happen to perform better by chance, rather than due policy improvement. Here, we develop a principled approach that accounts for stochasticity with one-sided, two-sample hypothesis tests to update policy parameters based on statistical significance.
Lastly, we perform several experiments and ablations to empirically study HDCA. When evaluated on sample of RL control problems, we found HDCA to consistently converge to solution in fewer iterations than other comparable methods. Given HDCA's highly scalable nature, the reduced number of iterations required to find a solution translates to quicker training time given adequate computational resources.
METHODS
2.1 MARKOV DECISION PROCESS
An MDP describes an environment where an agent acts within fully observable, stochastic domain to maximize its expected cumulative discounted reward (Russell & Norvig 2019). The environment can be described as set of states, S, along with set of actions, A. that can be taken to transition between states. The transition function ((s||s, a) describes the probability that taking action a in state 8 leads to state 8', and the reward function R(s, a) describes the reward received for taking action in state
solution to an MDP represented as a policy ne, encoded by parameters 0, that maps states to distribution over actions in a way that maximizes accumulated rewards. This paper focuses on environments where the reward function acts as a black box.
2.2 COORDINATE ASCENT
Our first insight is to use coordinate ascent to decompose the problem of optimizing the large policy parameter space into a sequence of smaller, more feasible, sub-problems. Coordinate ascent max- imizes function f() by successively maximizing sub-problems with respect to varying a single coordinate at a time. Similarly, block coordinate ascent iterates through blocks of coordinates and updates a subset of multiple coordinates sequentially (Tseng 2001) (see Algorithm I
Choose 80 E I:d;
Set i <- 0; repeat
Given 0², choose block of coordinates b in the (I...., d} and compute new iterate 0++1 that satisfies;
05+1 arg max f(0pp 0b) 0.
gi+1 = 00 Vp b
(2)
i i-i+1:
until termination test satisfied;
Algorithm 1: Block Coordinate Ascent
We approximate coordinate ascent optimization to maximize policy parameters without gradients.
To do so, numerically optimize the sub-problem for block of coordinates, rather than analyt-
2

---

Under review as a conference paper at ICLR 2022
ically solving it. If the dimension of the block of coordinates being updated is small, simple numerical optimization techniques yield good estimates of optimal updates. We propose approxi- mate block coordinate ascent (ABCA), which simply performs random search over the coordinates of the block that is being maximized (see Algorithm 2)
The primary benefit of utilizing ABCA is that optimization occurs without the use of gradient ap- proximation, which can be challenging even for deterministic functions. When applied to rein- forcement learning, the difficulties are exacerbated by the stochastic dynamics of many real-world RL problems, which lead to noisy function evaluations and rough approximations of the gradient. When combined with a potentially non-convex reward function, following an inaccurate gradient can lead to sub-op sub-optimal solutions and slow convergence. ABCA permits us to avoid gradient estimation altogether and instead make updates using simple global numerical techniques that are feasible for the smaller sub-problems.
We can see from Algorithm / that the update rule simply takes the policy corresponding to the highest empirical average cumulative reward within each batch of perturbed 0 values for block of coordinates. This differs from typical gradient estimation, where the update rule implemented as weighted sum across the batch of perturbed coordinates. For example, in the popular Evolu- tionary Strategies approach discussed in Sec. 3 updates are computed via an average (Eq. [2] perturbations. Due to the concentration of empirical means, this results in diminishing returns as one increases the number of perturbations per update (iteration). In contrast, ABCA considers maximum perturbations, and thus is able see greater returns of perturbations considered per update. As one may compute trajectories, +()) and cumulative re- wards, R (+h)), ), in parallel, the better utility of perturbations implies that ABCA is able to take better advantage the benefits of distributed computing compared gradient estimation techniques.
increase the number
Input:
Initial policy parameters 8 Rdd
Hyperparameters: Search range number of noise samples n, Number of coordinates per block c, number of rollouts in mean calculation M:
Set i < 0;
repeat
Let coordinate block b consist of c randomly selected coordinates from the set {l,..., d);
Sample Cj ~U(s) for j I,.., n, and & E b;
Let (() be the jth candidate optimizer (perturbation) over block b with values:
Vy E (I,.... \ b, 09: + 0% vk E b, 0() < 0g + ej,k
(3)
Using the policy samples ~ Taan (8:) and environment samples 8:4 ~ p(8441
88, az)
generate M rollouts +() and compute respective cumulative rewards R(t Vm E {I,...,M, M):
9 ( { (00))) (s :.......
R(
Σ
R(s,a)
(4)
(s,a)
Update 0 based on the empirical average cumulative rewards R(((1)) + M
1 ΣM R(tb)))
j + arg max R R(0()), gi+l < (()
(5)
i ++i+1;
until termination test satisfied;
Algorithm 2: Approximate Block Coordinate Ascent (ABCA)
2.3 HYPOTHESIS TESTING
Our second insight is to note that, unlike deterministic optimization, the stochastic nature of our optimization problem (through the environment dynamics and stochastic policy) requires a careful consideration of variance over expected rewards when comparing different perturbations in ABCA
3

---

Under review as a conference paper at ICLR 2022
iterates. That is, an improvement in parameters, that the average reward for candidate optimizer perturbation is greater. Below we propose to account for the stochasticity of expected reward approximations using hypothesis testing.
enumerating random policies, it may be due chance, rather than
Given the variance in the sequence of states encountered during policy rollouts, the cumulative reward can be highly variable, and thus selecting the policy corresponding to the empirical maximum reward may lead improved overall performance. To generate a more accurate assessment of given model's expected reward, we make multiple function evaluations for each perturbed ((3) (see Eq. and compute corresponding mean and variance estimates from the set of policy rollouts:
R(OG)
Σ R M
1
R(
1 M
Σ
(R(t R(
(6)
We are ultimately interested in determining if there is a perturbed model that is statistically demon- strated to yield a higher expected reward than our current model, thus one-sided, two-sample t-test best suited for this task (NIST/SEMATECH 2003). Since our policy perturbations at any given iteration are selected from uniform distribution, it is likely that some of the perturbed models will lead to worse overall performance. Additionally, since function evaluations represent independent environment rollouts, the data in our two-sample t-test is umpaired. Operating under the likelihood that the variances of the two samples are not equivalent, the test statistic, T, for the two-sample t-test is calculated as: T = (#1 / / + o /22 where μ4; 0,, and N; correspond to the tth sample's mean, standard deviation, and sample size, respectively (Cressie & Whitford 1986).
In our method, we seek to compare the rewards of candidate policy parameters (1:) to the rewards of the current iterate 0'; thus, test statisties are derived from the respective means and variances for reward:
Te R(OO)) - R((0')
V R(OSS) /M + R( /M
The null hypothesis Ho for this test is that the expected performance of the current policy is greater than equal to the perturbed policy that is being compared. Since are only interested in models with higher expected rewards, we reject the null hypothesis
T3 h h.a9,
(8)
where / corresponds to the critical value of the distribution with significance threshold a and degrees freedom, calculated as
O /M + o² R R(oOn ( /MP//(M - ( (o (M
Vij
(22
Finally, the update step concludes by updating the model to the perturbed Ô with the highest degree of statistical evidence outperform the previous iteration's model, if such model is found (or passes through the previous iterate, otherwise). Thus, HDCA considers a test-based update, which replaces the update in ABCA (Eq. (5) with:
- arg max T L 11-a,ey 0C+1 f- ( if Tj - 11 11-0,33 > 0, else 0².
(10)
That is, HDCA implements ABCA with an update that is based on statistical significance for better policy updates (see appendix for full statement of HDCA algorithm). It is important to note that the two-sample t-test has a parameter for the significance level a that is likely to be problem specific. In the realm of hypothesis testing. this parameter controls whether or not the null hypothesis gets rejected. When applied to our optimization scheme, this parameter determines a policy demon- strates enough statistical evidence to be considered more optimal policy than the previous iteration. Therefore, this parameter can be used to control the degree of policy exploration, with a larger a indicating higher affinity update the policy to perturbed value.
4

---

Under review as a conference paper at ICLR 2022
3 RELATED WORK
BLACK BOX OPTIMIZATION
This work uses the term "black box" as qualifier for objective functions in which only point-wise evaluations are possible, producing a single scalar output for each input. To maximize this objective function, the problem can be written as m- F()), where 0 represents the d-dimensional input parameters (Choromanski et al. 2020). Since the internal mechanisms governing the objective are hidden, this form of optimization is derivative-fres Therefore, typical solutions are iterative in nature, where perturbations to 0 occur at the beginning of each round of training. Such solutions methods (Stulp & Sigaud, 2012). Within RI., these parameters encode a policy that maps states to actions. The function evaluation corresponds to the total reward for a policy rollout, or trajectory, so information about the specific states encountered during the rollout is not available to the agent.
are known as parameter-perturban
BBO algorithms have demonstrated success common RL benchmarks, such as the gradient- estimation techniques ES (Salimans et al. 2017) and Augmented Random Search (ARS) (Mania et al. 2018) as well as gradient-free techniques like GradientLess Descent (GLD) (Golovin et al, 2019 HDCA separates itself from these comparable techniques by sampling multiple trajectories per perturbed policy, and thus is able to integrate the variance in the estimated expected cumulative reward when making policy updates to optimize in gradient-free manner.
Evolutionary Strategies. the ES approach proposed by [Saliaans et al. (2017). an objective function F acts candidate solutions defined by parameters O. where 0 is distributed according to some distribution py- ES, then, is concerned with maximizing Ea-p, F(0). Letting Pe be a multivariate Gaussian distribution with mean & and variance I²1, this optimization problem can be written as Eg-p., F()) = Ee-N(o,T) F(O + ac). In order to optimize this expected value, ES implements stochastic gradient ascent, with gradient steps taken based on the estimation:
1
VEE=NNO,, + = -E F( oe)e.
(11)
For each candidate solution within given iteration t, Fn F(0' + oc,)) is evaluated and the parameter update step defined as:
1 N
g++1 8³ +a No n=1
Σ Frens
(12)
where a is the learning rate and is the population size.
VARIANCE OPTIMIZATION
Several proposed RL methods incorporate mean-variance estimates to train risk-sensitive agents. Xie et al. (2018) explore this concept in their Mean- Variance Policy Gradient (MVP) implementa- tion. Rather than simply maximizing the expected cumulative reward, MVP aims learn the best performing policy that keeps the variance in the estimated cumulative reward below some threshold value. MVP reformulates the mean-variance trade-off function as its Legendre-Fencher dual, and subsequently uses cyclic block coordinate ascent to maximize this objective. While MVP shares similar inspiration with HDCA, MVP is a black-box optimization technique, nor is it gradient- free. Further, despite both methods incorporating the variance in the expected return to guide policy updates, MVP uses this variance as an upper-bound, while HDCA uses the variance in its hypothesis testing framework for performance comparison across policy perturbations.
Alternatively, Thomas et al. (215)) propose High Confidence Policy Improvement as framework for generating new policies with probabilistic guarantees. This approach asks the user to supply a performance floor p_ and confidence level ö, and the algorithm will return policy that has a lower expected cumulative return than p_ with probability at most 6. The interpretation of á is closely related to a used in HDCA's hypothesis tests, with both being dependent on how much risk is reasonable for the given task. High Confidence Policy Improvement, however, is designed framework for ensuring policy safety and not concerned with how proposed policies are trained and generated. It is therefore black-box optimization technique, unlike HDCA.
5

---

Under review as a conference paper at ICLR 2022
4 EVALUATION
Experiments were conducted on multiple RL environments to analyze the training performance of HDCA as compared to other blackbox optimization methods: ARS (Mania et al.) (018). ES (Sali-) mans et al. 2017), and GLD (Golovin al., (019). We compare performance based on the number of parameter updates (iterations), which are the bottleneck when training with simulated environ- ments and parallel computing. Sec. 4. analyzes performance on the environment, where HDCA and ES train a neural network and ARS trains a linear model. Sec. [4.2] explores the performance of HDCA, ARS, and GLD various MuJoCo locomotion tasks, where every approach trains identically structured linear policies.
Implementation details. Our implementation HDCA is provided in the supplemental mate- rial. We use the Pathos multiprocessing Python framework (MeKems et al. 2012) to implement a parallel version of Algorithm [] Since the majority of HDCA's computational overhead derives from evaluating the reward function, we created a pool of workers to compute episode rollouts in parallel. We evaluated HDCA on various MuJoCo locomotion tasks (Todorov et al. (2012) and the LunarrLnddrronntnnuuuss.
environment simulated through the OpenAl Gym (Brockman al., 2016). The OpenAl Gym provides benchmark reward functions for all simulated environments. For each environment, experiments were run until threshold performance level was reached averaged over 100 trials.
4.1 LUW.RAANDERCNNINNOOO
In this section, compare the training performance of HDCA, ES, and ARS for the Lumartanderrontinouss control task from the Box2d simulator within OpenAI Gym. The pri- mary goal of this task is navigate lander to its landing pad, with the environment being consid- ered solved at a total reward of 200. For this environment, HDCA and ES trained identical policies represented by neural network with a hidden layer consisting of 100 neurons, using tanh activation, with 1,000 total parameters. ARS trained a linear policy to stay consistent with the work produced by Mania al. (2018), requiring 16 parameters be optimized.
Effeet of sub-problem dimensionality. This section aims to explore how HDCA's training per- formance varies with respect to the block size b of perturbed coordinates. Figure I shows the total expected reward as a function of the training iteration across five independent trials. In each trial, 5,000 directions were sampled per iteration, corresponding to 5,000 perturbed policies to evaluate. The generated plots demonstrate the maximum, minimum, and average expected reward for all three methods. The subfigures of Figure Daaureerrrrreer represent training results for varying coordinate block sizes for HDCA. For example, Figure shoss the training performance HDCA when a block of 50 coor- dinates is chosen to be perturbed at each iteration. Since ES and ARS perturb all policy parameters when sampling new directions, the number of coordinates perturbed in each subplot of Figure I only applies to HDCA.
Table 1: Average number of training iterations before solving LumarLanderrComiimouu-y
Method
Average Training Iterations
HDCA-3
14.8 10.5
HDCA-10
4.4 + 0.80
HDCA-50
4.6 2.33
HDCA-100
5.2 - 2.99
HDCA (Average)
7.25 + 4.37
The results from Figure I for HDCA are summarized in Table I and demonstrate how HDCA can quickly converge to solution. On average, it took ES 18.4 iterations, ARS 20.8 iterations, and HDCA 7.25 iterations to converge. The number of training iterations was chosen as a primary metric for analysis due to HDCA's scalability with the number of cores. Depending how HDCA implemented and the total number of available processors, all function evaluations for given iteration can be performed in parallel. Thus, looking how these methods perform relative to the

---

Under review as a conference paper at ICLR 2022
Perturbed Coordinates
10 Perturbed Coordinates
Estmate Eppprttddd Camuilctvvs Rowardd
203
203
100
103
Falmsin dfEapttted
-100
-100
-300
.000
Thsiring
Thaiting Ilenation
(a) 3 Coordinates
(h) 10 Coordinates
Coordinates
Perturbed
300
303
Expeected mutattteee Rocorrd
Expeedeed mutaaa
103
103
.200
420A
1200
H3GA
ARS
ARS
12
18
20
12
18
18
20
Thiining lie llaiaioon
Thiining Blenstion
(c) 50 Coordinates
(d) 100 Coordinates
Figure 1: Training performance for HDCA compared ARS and ES for the Lunarl 2.n.anrrroniiuuuuss22222 environment. The estimated expected cumulative reward plot- ted against the training iteration, where training continued until the expected reward minus its standard deviation exceeded the threshold of 200. HDCA and ES were trained on neural network with one hidden layer consisting of 100 neurons, while ARS trained linear policy. 5,000 directions were evaluated at each training iteration for all three methods, and the number of coordinates perturbed in each subplot refers the block size for HDCA.
number of training episodes gives insight into HDCA's viability optimization technique as large-scale computing clusters become more accessible.
Following (Salimans al. 2017), examining the number of training iterations is meaningful for BBO techniques than sampling efficiency since better parallelization in policy optimizers shall lead to faster training. Furthermore, given that BBO techniques are primarily applied simulated environments, policy rollouts are much less expensive than in real-world experiments. The primary bottleneck to training is therefore the wall-clock training time. Since every rollout can be executed in parallel for HDCA, this is directly proportional to the number of training iterations assuming adequate resources are available.
All variants of HDCA outperformed ARS and ES in terms of the expected number of iterations until solved besides HDCA-3, which performed consistently with the other methods. The decreased per- formance of HDCA-3 is likely due to the small overall percentage of network parameters that are perturbed at each iteration. Perturbing just .3% of the total parameters at each iteration, HDCA-3 required more training iterations than the other variants to optimize enough of the model to converge to solution. Conversely, HDCA-100 required the second most training iterations out the HDCA variants evaluated. This method perturbed 100 coordinates each iteration, corresponding of the total model parameters. However, searching in this high-dimensiona. space is much harder task than sub-problems of lower dimensionality, thus performance observed to be less consis-
10%

---

Under review as a conference paper at ICLR 2022
tent. To improve training the sub- peoblooobem complexity increases, more samples must be taken each iteration. Hence, we see a trade-off when increasing block size and find that 'middle- -oouuld configurations work best. Overall, HDCA proves robust to the choice of block size and demonstrates flexibility and efficient convergence for this task.
Effeet of perturbations per iteration. Figure 2 demonstrates the relationship between the num- ber of perturbations sampled per iteration and the expected number of iterations until solution is found. HDCA-10 was chosen for demonstration purposes based on the findings in Table [ For HDCA, the number of perturbations per iteration represents how extensively the parameter space explored. a break from the common paradigm, HDCA does not use its perturbations weighted sum but performs maximum- much better updates as we increase the number of perturbations. In contrast, ARS and ES base their policy updates on averages across perturbed policy performance, thus the contribution from each perturbation decreases as the sample size increases, and we get diminishing returns due to the concentration of empirical means. This the primary explanation for why HDCA greatly reduces the number of training iterations with larger perturbation sample size, while ARS and ES see more similar performance. These results show that HDCA makes better use of increased computational resources.
a update from perturbations, which potentially yields
LumarLandieCorrrrooau-2222
Lunartanddrrorrtnnccsza
2010
2013
Fstretta Expected Cummuittvv Roward
Cummusttve Roward
200
203
109
103
-100
.200
1200
1724-110
E5
10 10
10
Training Ite ltration
Traning Ileration
(a) 250 Perturbed Policies per Iteration
(b) 5000 Perturbed Policies per Iteration
Figure 2: Training performance for HDCA-10 compared to ARS and ES for the environment. The estimated expected cumulative reward is plotted against the training iteration, where training continued until the expected reward minus its stan- dard deviation exceeded the threshold of 200. The left figure shows the expected number of training iterations when 250 samples taken each iteration, and the right shows the same relationship for 5000 samples.
4.2 MuJoCo
Next, HDCA was evaluated against a subset of the MuJoCo locomotion tasks, where its training performance was compared to ARS and GLD. All three methods trained identical linear policies. The documented success of linear models (Mania et al. (0188) in the MuloCo control tasks is compelling indication that deep neural networks with many parameters may not necessary for complex RL problems.
The results presented in Table reflect similar trends as those discussed Sec. 4.1 regarded as the simplest of the three evaluated MuJoCo environments, and HDCA is rapidly able to converge to an optimal solution. GLD demonstrates similar performance, while ARS is slower to converge. This difference in behavior is likely due to HDCA and GLD's independence of gradient estimates their policy update steps.
Swimmer-v2
Despite demonstrating similar performance in the Swimmer-v2 environment, HDCA was able to converge to an optimal solution much more quickly than GLD for Hopper-v2. A likely explanation to this divergence is in how the methods handle stochasticity within the environment. By esti-
8

---

Under review as a conference paper at ICLR 2022
mating the numerical mean and variance of policy rewards, HDCA can leverage hypothesis testing to effectively guide its policy updates. Taking a simple maximum of policy rewards ignores how cumulative rewards are stochastic quantity, which may lead to the slower convergence observed in GLD in more complex domains.
The results for HalfCheetah-v2 highlight the importance of the number of perturbations per iteration. Here we see that HDCA remains competitive with ARS. While HDCA and ARS were able train policies for HalfCheetah-v2 using 500 perturbed policies per iteration, GLD was unable to converge to an optimal solution unless approximately 10x more policy perturbations were generated.
Table 2: Average number of training iterations before solving various MuJoCo locomotion tasks
Task (Threshold)
Method Average Training Iterations
Swimmer-v2 (325)
HDCA
2.2 + 0.75 25.6 + 2.65
ARS
GLD
2.2 .4
Hopper-v2 (3120)
HDCA
80.8 + 30,9
ARS
121 = 34.9
GLD
393 + 245
HalfCheetah-v2 (3430)
HDCA
116 + 72.8
ARS
93.6 + 11.3
GLD
5 CONCLUSION
This work develops gradient-free, black box optimization technique that can match or outperform similar state-of-the-ar methods. Its independence from gradients makes highly scalable and com- petitive in parallel architectures. Furthermore, its intuitive hyperparameters and simple structure lead to a straightforward implementation that can be easily adapted to other RL environments.
We develop HDCA off of two major insights. Our first insight is to frame policy optimization via coordinate ascent. Coordinate ascent naturally decomposes the problem of optimizing the large policy parameter space into sequence of smaller, more feasible sub- cob-problems.. Although do not have access to analytical solutions the sub-problems (as is typical in coordinate ascent), we note that if sub-problems are of low enough dimension, then any simple numerical optimization strategy shall approximate solutions well. Our second insight is to note that the cumulative rewards, the expectation of which is our optimization criterion, is stochastic quantity. Thus, the expecta- tion is estimated with finite samples of rollouts, which leads to variance and uncertainty about true expectations of cumulative rewards for candidate perturbations. The stochastic nature (and finite sample estimation) of the cumulative reward criterion has been largely ignored by previous BBO approaches. Here, we develop a principled approach that accounts for this with one-sided, two- sample hypothesis tests to update policy parameters based on statistical significance. The resulting algorithm is easy to implement, easy to parallelize, and highly effective.
Future work shall explore extensions to HDCA for applications in large network- policies. Although recent work (Mania et al. 2018) has shown that simple policies are competitive even for complicated tasks, it would be beneficial to leverage larger capacity networks when necessary. (Salimans et al. 2017) showed that using virtual batch normalization (Salimans et al. 2016) allowed for better optimization of larger networks. Thus, we shall explore similar strategies well as network pre-training schemes for better leveraging of the coordinate ascent block updates when parameters are large.
9

---

Under review as a conference paper at ICLR 2022
ETHICS STATEMENT
While all experiments conducted in this work were simulated through software for demonstration purposes, there are many physical problems that can lead to significant consequences if proper safety measures are not considered, such as when developing autonomous vehicles. Therefore, it is imper- ative to properly define reward functions for environments that could have societal impact. It is equally important verify that deployed policies accurately reflect this definition. To mitigate the risk of adverse consequences, trained policies should undergo significant testing before deployment.
REPRODUCIBILITY STATEMENT
Our implementation of HDCA is provided in the supplementary material within the "HDCA" direc- tory. Please refer the README file for execution instructions.
10

---

Under review as a conference paper at ICLR 2022
REFERENCES
Adel Bibi, EI Houcine Bergou, Ozan Sener, Bernard Ghanem, and Peter Richtarik. stochastic derivative-free optimization method with importance sampling: Theory and learning to control. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pp. 3275-3282, 2020.
Greg Brockman, Vicki Cheung, Ludwig Pettersson, Jonas Schneider, John Schulman, Jie Tang, and Wojciech Zaremba. Openai gym. arXiv preprint 1eX.v::666.01355 2016.
Krzysztof Choromanski, Aldo Pacchiano, Jack Harker-Holded Yunhao Tang, Deepali Jain, Yuxiang Yang, Atil Iscen, Jasmine Hsu, and Vikas Sindhwani. Provably robust blackbox optimization for reinforcement learning. In Conference on Robot Learning, pp. 683-696, PMLR, 2020.
NAC Cressie and Whitford. How to use the two sample t-test. Biometrical Journal, 28(2): 131-148, 1986.
Daniel Golovin, John Karro, Greg Kochanski, Chansoo Lee, Xingyou Song, and Qiuyi Zhang. Gra- dientless descent: High-dimensional zeroth-order optimization. arXiv preprint arXiv: /9/ 1.06317, 2019.
Horia Mania, Aurelia Guy, and Benjamin Recht. Simple random search of static linear policies is competitive for reinforcement learning. In Proceedings of the 32nd International Conference on Neural Information Processing Systems, pp. 1805-1814, 2018
Michael M McKerns, Leif Strand, Tim Sullivan, Alta Fang, and Michael AG Aivazis. Building framework for predictive science. arXiv preprint /202.. 1056, 2012.
Andrew Y Ng, Adam Coates, Mark Diel, Varun Ganapathi, Jamie Schulte, Ben Tse, Eric Berger, and Erie Liang. Autonomous inverted helicopter flight via reinforcement learning. In Experimental robotics IX, pp. 363-372. Springer, 2006.
NIST/SEMATECH. Two-sample t-test for equal means, 2003. URL https:tt////// /www. itl mis... gow//ivv98//aaddaaaeooo http://aaaaaaoooeaaaaaaaa////aaa .tmm
Stuart Russell and Peter Norvig. Artificial intelligence: modern approach. Pearson Education, 2019.
Tim Salimans, Ian Goodfellow, Wojeiech Zaremba, Vicki Cheung, Alec Radford, and Xi Chen. Improved techniques for training gans. Advances in neural information processing systems, 29: 2234-2242, 2016.
Tim Salimans, Jonathan Ho, Xi Chen, Szymon Sidor, and Ilya Sutskever. Evolution strategies as a scalable alternative reinforcement learning. arXiv preprint arXiv: 033643 2017.
David Silver, Julian Schrittwieser, Karen Simonyan, Ioannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton, et al. Mastering the game of go without human knowledge. nature, 550(7676):354 359, 2017.
Freek Stulp and Olivier Sigaud. Policy improvement methods: Between black-box optimization and episodic reinforcement learning. 2012.
Philip Thomas, Georgios Theocharous, and Mohammad Ghavamzadeh. High confidence policy improvement. In International Conference on Machine Learning, pp. 2380-2388. PMLR, 2015.
Emanuel Todorov, Tom Erez, and Yuval Tassa. Mujoco: A physics engine for model-based control. In 2012 IEEE/RSJ International Conference on Intelligent Robots and Systems, pp. 5026-5033. IEEE, 2012.
Paul Tseng. Convergence of block coordinate descent method for nondifferentiable minimization.
Journal of optimization theory and applications, 109(3):475-494, 2001.
Stephen J Wright. Coordinate descent algorithms. Mathematical Programming, 151(1):3-34, 2015.
Tengyang Xie, Bo Liu, Yangyang Xu, Mohammad Ghavamzadeh, Yinlam Chow, Daoming Lyu, and Daesub Yoon. A block coordinate ascent algorithm for mean-variance optimization. Advances in Neural Information Processing Systems, 31, 2018.

---

Under review as a conference paper at ICLR 2022
A APPENDIX
Hypothesis-test Driven Coordinate Ascent (HDCA) combines the insights from sections 2.2 and 2.3 and is presented in Algorithm
Input:
Initial policy parameters d Rd
Hyperparameters: Search range 8, number noise samples n, Number of coordinates per block c, number of rollouts in mean calculation M, hypothesis test parameters (a, N); Set < 0;
repeat
Let (( be the empirical average, standard deviation of the current policy cumulative reward;
Let coordinate block consist of e randomly selected coordinates from the set {1.... d]:
Sample j, ~s() for 1,... n, k E b;
Let g() be the jth candidate optimizer over block b with values:
Vq bb ((1) Og. vk b, 0 0j + Ejj
Using the policy samples a, ~ Too (5:) and environment samples 8i41 ~ p(s++1 |s,,a)) sample M rollouts 1h6 and compute respective cumulative rewards R R(1))). )
vm E {I....,MH M]:
{lmm mm)), (s m.......
R(t = Σ R(s,a)
(13)
(s,a)Eth
Estimate empirical average cumulative rewards R(OG)) and corresponding standard deviation (((0))) as:
M
M
R( - M Σ R(
R((OG)) +
Σ (R R(())))2
(14)
M
m=1
m=1
Compute test-statistics T, for two-sample t-Test to compare each cumulative reward with the previous empirical average;
T₁ R(05)) R(((1)
(15)
( /M + o R
Determine critical value for two-sample t-Test ((.1aaw)) where is caleulated in Eq. Determine which policy corresponds to the most statistically significant cumulative reward:
j + arg max T, - ((--),))) diff + T; - t( (1-a.)))
(16)
if diff then g++1 (()
else
01+1 +-
end
i it++l:
until termination test satisfied;
Algorithm 3: Hypothesis-test Driven Coordinate Ascent
12


Reviews:
[{"review_id": "zvEoJ_ecBEm", "reviewer": "Reviewer_ADBA", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "As the paper notes, there are several conceptual advantages to an approach like HDCA: it is gradient-free, and well suited to parallelism. I believe, however, that aspects of the paper's exposition could be improved: For instance, in the plots that convey the central results, I do not have clarity on what the y-axis is conveying. The y-axis label differs from the caption, which differs further from what I believe the y-axis is actually stating (the average estimate of the expected return). Similarly, core statements are made that I found a bit hard to follow: \"the noise in the reward incurred during an RL policy rollout\"; what noise is present in the reward? It seems we have assumed that reward functions are deterministic. Is it the noise in the sequence of random variables associated with future rewards along a random trajectory? If so, it would be helpful to be a bit more precise in some of this language.\n\nAdditionally, I have two major questions regarding closely related work.\n1. I believe block coordinate ascent has been used for policy optimization previously: See \"A block coordinate ascent algorithm for mean-variance optimization\" by Xie et al. (NeurIPS 2018). Unless I have missed something critical, it seems important that the authors read this paper and understand what HDCA does beyond their proposed algorithm (\"Mean-Variance Policy Gradient\" or MVP).\n2. The methods of this paper bear a resemblance to _high-confidence policy improvement_ methods, too, in which hypothesis tests are conducted on the value of a proposed new policy to ensure that a better policy is found, based on a set of data. For instance, see \"High Confidence Policy Improvement\" by Thomas, Theocharous, and Ghavamzadeh (2015), who xamine a variety of methods for attaining probabilistic guarantees about improving policy $\\pi_i$ to $\\pi_{i+1}$. This work and its successors (Chandak et al 2020, for example) seem conceptually quite similar to the method proposed here. I suspect the present paper would be sharpened with a related work section contrasting the proposed approach with that of policy improvement methods.\n\nFor these reasons, I presently lean toward rejection. I am willing to increase my score (pending the perspectives of other reviewers) if the paper's exposition can be sharpened and the relation to the above two bodies of work can be made more clear.\n\n**Minor Questions/Comments**\n- \"with a potentially non-convex reward function\": Are reward functions typically non-convex?\n- \"... that ABCA is able to take better advantage of the benefits...\": Take better advantage than what, gradient estimation? If so, it might be useful to state that more explicitly.\n- \"Given the noise in the reward incurred during an RL policy rollout\": I am not sure I follow. What exactly is the source of the noise? I see that the reward function is defined as a deterministic function, $R : \\mathcal{S} \\times \\mathcal{A} \\rightarrow \\mathbb{R}$.\n- To me, the title does not capture the spirit of the paper. I believe \"Hypothesis-Test Driven...\" would be more suitable. The phrase \"hypothesis driven\", to me, evokes the idea that a given learning algorithm is incentivized by falsifying candidate hypotheses in some way.\n- I believe I do not understand what is being plotted in Figure 1. The y-axis label says \"reward\", but the caption says \"average expected reward\", but I believe these are estimates of the average expected cumulative reward. Can you clarify?\n\n**Writing Suggestions**\n-  I believe this sentence could be cleaned up by removing \"the expectation of which is our optimization criterion\": \"That is, the cumulative rewards, the expectation of which is our optimization criterion, is a stochastic quantity whose distribution depends on the stochastic policy and environment.\"\n- \"the development of an environment\" --> \"an environment\"\n- \"its expected discounted reward over time\" --> \"the expected discounted cumulative reward\"\n- You can delete the following, as it is contained in the definition of $p$: \"A fundamental property of MDPs is that the resulting state is only dependent on the current state and is therefore unaffected by the agent’s prior history\"\n- \"In stochastic environments, a solution to an MDP is represented as a policy $\\pi_\\theta$, encoded by parameters $\\theta$, that maps states to a distribution over actions in a way that maximizes accumulated rewards.\" This could be true of both deterministic and stochastic environments, but the sentence seems to emphasize stochastic environments. Perhaps just remove the initial phrase?", "summary_of_the_paper": "This paper introduces a new policy optimization method based on coordinate ascent. As the paper notes early on, the core of the proposed method is based on two central insights. The first is that coordinate ascent is a suitable approach for policy optimization as it decomposes the large search space (the policy space) into \"a sequence of sub-problems with smaller search spaces\". The second notes that the objective is in fact stochastic: The return can be thought of as a random variable distributed according to the mixture of a possibly stochastic control policy and the possibly stochastic transition dynamics of the environment. In contrast, prior black box approaches to optimization have tended to ignore this stochasticity in favor of optimizing for the expected return (the value). To account for this, the paper proposes a one-sided hypothesis test that can inform whether to update the policy based on the significance of a given rollout. Experiments are conducted on a continuous variant of the LunarLander-v2 domain and MuJoCo, contrasting estimates of the average return achieved by policies vs. iterations for the proposed method (HDCA), an evolutionary approach (ES), and Augmented Random Search (ARS). Results support the improvement of the approach over ES and ARS on this domain.", "summary_of_the_review": "There are aspects of the proposed approach that seem desirable, but I am reluctant about its novelty due to two closely related pieces of work: (1) A Block Coordinate Ascent Algorithm for Mean-Variance Optimization, and (2) High-Confidence Policy Improvement. Additionally, I believe the paper's overall clarity could be improved.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "LgZz39kEr4V", "reviewer": "Reviewer_pTGV", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "I found the paper to be clearly presented and reasonably well written.\n\nThe authors present a simple idea for a new approach for a 'black box optimization' method for learning RL policies. In so doing they contribute to a growing literature noting the extent to which simple optimization methods and linear policies are able to achieve comparable results to current SOTA methods on many RL benchmarks. This work is critical to the RL community.\n\nThe new method presented contains a number of magic numbers however (the number of alternate policies-permutations to be considered at each step, the number of steps each policy must be rolled forward, the number of times each policy is to be rolled forward, and the 'significance level' /alpha). To my mind there is simply insufficient experimental evidence to assert the claims made in the paper. Certainly the results look promising on the domains present, but they are few in number. Additionally I do not believe the authors provide for how practitioners might assign these in practice. The authors themselves note, for example, that /alpha is like a \"problem specific parameter\" but do not make mention of the sensitivity to that parameter in the experiments.\n\nOverall I think the authors have presented an interesting idea - one that finds itself in good company in the literature. But ultimate do not present sufficient evidence to support their more general claims.\n\nnit: if the experimentation presented for a new optimization approach is only to be run against linear policies or single-layer networks that ought to be called out early, perhaps even in the title. ", "summary_of_the_paper": "The authors propose a new 'black box optimization' method for learning RL policies in stochastic environments. The simple new method, called Hypothesis Driven Coordinate Ascent (HDCA), does not explicitly require a gradient estimation, and proceeds instead by rolling forward multiple candidate policies in parallel and taking as best performing policy parameters as the iterate update.", "summary_of_the_review": "The authors propose a simple new 'black box optimization' method for learning RL policies in stochastic environments. The method is simple and clearly explained. The paper is clearly written and reasonably presented.\n\nThis method contributes to a growing literature noting the effectiveness of simple optimization method and linear policies on many current RL benchmarks. However, unlikely notable previous working in this space (in particular, \"Horia Mania, et al. Simple random search of static linear policies is competitive for reinforcement learning\" who's work this paper references a few times), this paper presents only a limited experimental and sensitivity analysis.\n\nI think the paper would benefit strongly from a more robust experimental treatment of the idea. Specifically, the authors might explicitly restrict themselves to linear policies and do a like-for-like experimental comparison against previous work.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "JKzEwqt4J3C", "reviewer": "Reviewer_Je5f", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "While the algorithm designed in this paper sounds interesting, it does not appear to be sufficiently novel. In fact, random search methods for black-box optimization have been studied for many years. Especially, in the evolutionary computation community, various approaches to improve the search performance, including block-based search and statistical testing techniques, have been explored extensively in the past to solve various numerical optimization problems. In comparison to existing EC and local search algorithms, it is not clear which part of the new algorithm is truly novel.\n\nThe authors claim in the paper that reinforcement learning problems are black-box optimization problems. On such problems, critical gradient information is hard to obtain. However, the prominent success of many state-of-the-art deep reinforcement learning algorithms, such as TD3 and SAC, have already demonstrated the effectiveness of calculating and using gradients to train policies. In comparison to these deep reinforcement learning algorithms, it is not clear what key advantages the new algorithm has. Furthermore, any possible advantages of the new algorithm should be verified both experimentally and theoretically. In particular, the theoretical strength of adopting a gradient-free approach for reinforcement learning is not clearly justified in the paper.\n\nThe experimental analysis in the paper has some limitations. First, the number of benchmark problems utilized in the experimental study seems to be quite limited. It is not easy to draw any solid conclusion based on the results obtained from these benchmark problems. Second, the authors argued that the number of training iterations is more meaningful as a performance metric because the algorithms are only applied to simulated environments. Does that mean that the new algorithm cannot be applied to any real-world problems? If so, what is the practical value of the new algorithm? Even when the environment is simulated, it is still important to determine the final learning performance achievable by the new algorithm. For the Mujoco benchmarks, I cannot find any performance results in the main body of the paper. In fact, the authors claimed that the new algorithm can converge to the optimal solution on Swimmer-v2. However, it is not clear what the optimal solution is and how the optimal solution is obtained. Third, the hyper-parameter settings used to solve different problems appear to be different. For example, on the lunar lander problem, 5000 directions were sampled per iteration. Different from that, on half cheetah, the number of sampled policies is reduced to 500 per iteration. It is not clear how the change of hyper-parameters is determined and whether the hyper-parameter settings used present a fair comparison among all the competing algorithms.\n\nFinally, it is claimed in the abstract that this paper has the aim to learn robust policies for stochastic environments. However, to my understanding, most of the benchmark problems utilized in the paper are not highly stochastic in nature. Furthermore, the actual robustness of the learned policies is not evaluated in the paper.", "summary_of_the_paper": "This paper proposed a new random search algorithm for reinforcement learning. This algorithm features a block-based parameter search technique and the use of statistical testing techniques to determine reliably the next-step search direction.", "summary_of_the_review": "This paper introduced some interesting ideas for gradient-free policy training for reinforcement learning. However, the novelty of the new algorithm design should be clearly highlighted and strongly justified. The theoretical strength of adopting a gradient-free approach for reinforcement learning also requires better justifications. Meanwhile, the empirical evaluation has some limitations.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "3dUcvlkv2nL", "reviewer": "Reviewer_gfVu", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is well-written and clear. I like that the algorithm is relatively simple and benefits from scaling up. The authors have done a good job of justifying the design choices. However, the algorithm is not very novel, essentially consisting of a combination of existing techniques.\n\nMy main concern about the algorithm is how well it would scale to more difficult environments. In particular, the paper which made the case for evolution strategies (ES) in RL had experiments on the Humanoid task and Atari games, which raises the question of why HDCA does not compare on these tasks. The experiments in this paper only demonstrate HDCA’s operation in scenarios where a relatively small number of parameters (1000 or less) need to be optimized, and the reward is dense.\n\nThere are a few things that could make the paper stronger:\n* Experiments on a domain with sparse rewards, or using high-dimensional parameter spaces, as these seem like challenging cases for HDCA. The Atari tasks with CNNs are a common testbed with these characteristics.\n* Experiments on non-RL tasks. The HDCA algorithm is in principle applicable to any stochastic black-box optimization problem, but the paper limits itself to RL problems. It would be cool to see that the proposed improvements are effective across domains.\n* Plotting a scalar measure of the performance (e.g. how many iterations required to reach a particular performance threshold) as a function of the number of perturbations, so that we can see the diminishing returns more clearly.\n\nI also had a small/unimportant question which could be interesting: why does the block (i.e. indices telling which variables are being optimized) have to be fixed within each iteration? I see no reason why you couldn’t re-sample the block along with the perturbation. This could speed convergence if some parameters are unimportant or harder to optimize.", "summary_of_the_paper": "The paper proposes a derivative-free optimization algorithm which is applicable to stochastic black-box functions. (The target application area is reinforcement learning, but the algorithm is more broadly applicable.) The core elements of the algorithm are\n1. Block coordinate ascent: Only a few parameters are optimized at each step, while the others are held fixed. The maximization is performed by random search over the parameters being optimized, so the function evaluations can be performed in parallel.\n2. Hypothesis testing: Because of the high variability of Monte Carlo policy evaluation, a one-sided two-sample hypothesis test is performed to determine whether or not the candidate policy is in fact better than the current policy, and the policy is only updated if this is the case.\n\nThe proposed algorithm, hypothesis-driven coordinate ascent (HDCA), is compared to previous derivative-free optimizers proposed in the RL literature, where it is shown to require fewer iterations to converge on most tasks.", "summary_of_the_review": "The proposed algorithm makes intuitive sense and performs well on the tasks presented by the authors, but it is not particularly novel, and I have doubts about whether it can solve more difficult tasks. Further experiments could change my evaluation.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The manuscript proposes a black box optimization algorithm based on statistical hypothesis testing and proposes to use it to solve control problems posed in stochastic environments. While "Reinforcement Learning" appears in the title, this appears to have nothing to do with RL other than that it purports to solve problems that are typically used to benchmark RL algorithms, i.e. sequential decision making for reward maximization with stochastic dynamics. Baselines compared against also don't involve the reinforcement learning formalism. A key claim appears to be that the application of other gradient-free methods to such problems incorrectly ignores stochasticity of the objective function owing to the stochastic sequential dynamics.

Reviewers found the paper both clear and well-written, but questioned the novelty of the approach, its situation in the wider world of gradient-free black box optimization methods, and the limited scope of the empirical results. Reviewer pTGV criticized apparent "magic numbers" in the algorithm description, to which the authors responded rather dismissively.

In their general reply statement, the authors seem to misinterpret reviewer Je5f's comment that “critical gradient information is hard to obtain”: my own interpretation is that Je5f is characterizing _black box optimization problems_ in general, and noting that the special structure of MDPs admits gradient estimation via the policy gradient theorem, etc. In response to Je5f directly, the authors state "[TD3 & SAC] are not BBO techniques, thus we did not feel as though it would be fair to compare HDCA to problems solved by these methods". ADBA raises some concerns about links to the existing literature, which appear to have been addressed to their satisfaction, though was unwilling to champion the paper for acceptance in light of the concerns of other reviewers.

The AC concurs with the reviewers' assessments regarding the limited nature of the experiments  The paper makes the claim that the newly proposed method is a compelling choice for the solution of stochastic MDPs, but fails to adequately defend this claim, and fails to benchmark against either policy or value-based RL methods. When challenged on this, they assert that such comparisons would be unfair; this may be true in a limited sense, but if an RL algorithm can outperform the novel BBO method on all problems considered, it's unclear why this would be of significant interest to the ICLR community. A recurring theme in the discussion is that BBO methods are more scalable than RL, though batched A2C methods (e.g. Espeholt et al, 2018) or distributed Q-learning (e.g. Kapturowski et al, 2019) would at least merit mention, and would appear to at least challenge this claim.

Finally, the AC would like to note that work on Evolution Strategies predates the work of Salimans et al, 2017, including for control problems (e.g. Cardamone et al, 2009) and in particular Wierstra et al (2014) propose many sophisticated techniques for more effectively utilizing function evaluations (including methods based on hypothesis testing) which are a natural point of comparison for this work. Similarly, CMA-ES is a widely used and well-regarded technique for gradient-free optimization, and would be a reasonable baseline. In short, the empirical investigation is inadequate even if restricted to gradient-free methods, and the fact that these methods may not explicitly account for stochastic dynamics does not obviate the need for comparison.

The method presented is interesting, and I encourage the authors to continue studying it, with a more diverse set of environments, strong baselines and careful ablations.
Decision: Reject