Neuroevolutionary reinforcement learning for generalized control of simulated helicopters

The sequential decision problems addressed in RL are often formalized as MDPs [9], which can be described as 5-tuples \(\langle \mathcal{S}, \mathcal{A}, \mathcal{T}, \mathcal{R}, \gamma \rangle\) where

The process evolves over a series of discrete timesteps. In each timestep t, the agent observes its current state \(s_t \in \mathcal{S}\) (e.g., via sensors on a robot) and selects an action \(a_t \in \mathcal{A}\) (e.g., by activating motors on a robot). Following \(\mathcal{T}\) and \(\mathcal{R}, \) the agent receives an immediate reward r _t and transitions to a new state s _t + 1.

A policy π(s, a) = P(a|s) indicates the probability of selecting each action in each state. An optimal policy π^*(s, a) is one that maximizes the expected discounted return:For every MDP there exists at least one deterministic optimal policy π^*(s) which directly maps states to actions [82]. In this article, we consider only deterministic policies.

When \(\mathcal{T}\) and \(\mathcal{R}\) are known to the agent, the result is a planning problem, which can be solved using dynamic programming methods [8]. When \(\mathcal{T}\) and \(\mathcal{R}\) are initially unknown, the agent faces a reinforcement learning problem. Such a problem can be solved using temporal-difference methods [80], which extend principles of dynamic programming to the learning setting. However, in many tasks, better performance can be obtained using a policy search approach [28, 41, 94], in which optimization methods such as evolutionary computation are used to directly search the space of policies for high performing solutions. This article focuses on neuroevolutionary policy search approaches.

In the helicopter hovering task, an RL agent seeks a policy for controlling a 3-dimensional simulated helicopter. The dynamics of the task are based on data collected during actual flights of an XCell Tempest helicopter. The goal is to make the helicopter hover as close as possible to a fixed position for the duration of an episode. Helicopter hovering is challenging for several reasons. First, the transition dynamics are complex. Second, both the state and action spaces are continuous and high dimensional. Third, the task involves high risk, as bad policies can crash the helicopter, incurring catastrophic negative reward. Here we give a brief description of the helicopter hovering problem; more details can be found in [6, 57].

A helicopter episode lasts 10 min. During this time, the helicopter simulator operates at 100 Hz, i.e., the helicopter state is updated 100 times per second, yielding 60,000 simulator timesteps per episode. However, helicopter control occurs at only 10 Hz, yielding 6,000 control timesteps per episode. Throughout this article, we refer to the current simulator timestep as ts and the current control timestep as tc.

At each control timestep, the agent receives a 9-dimensional state vector⁴ (see Table 1) and responds by specifying a 4-dimensional action (see Table 2). Although the transition function is stochastic (i.e., the agent does not know to what state it will transition before its action is complete), there is no noise in the agent’s state signal (i.e., the state is fully observable and thus the Markov property holds). While this assumption would not strictly hold in a real helicopter, it is a reasonable approximation for a simulator, as modern systems often have access to sophisticated hardware and software for highly accurate state estimation. For example, several examples of control for real helicopters have relied on the well-known VICON motion-capture technology [19, 34, 60].

Together with the state vector, the agent also receives a negative immediate reward equal to the sum, over all state features, of the squared difference between that state feature and the fixed target position in which the helicopter wishes to hover. Since the target position is the origin, this is simply:where s _i is the current value of the ith state feature. Reward is not discounted, i.e., γ = 1.

The helicopter begins each episode at the origin, i.e., s _i  = 0 for all i. An episode ends prematurely if the helicopter crashes, which occurs if the velocity along any of the main axes exceeds 5 m/s, the position is off by more than 20 m, the angular velocity around any of the main axes exceeds 4 π rad/s, or the orientation is more than π/6 rad from the target orientation. Crashing results in a large reward penalty equal to the most negative reward achievable for the remaining time.

To discourage participants from overfitting to a single MDP and to encourage them to develop methods capable of robust, on-line learning, many events in the RL Competitions are formulated as generalized tasks [91, 92]. A generalized task \(\mathcal{G}: \Uptheta\, \mapsto\, [0, 1]\) is simply a probability distribution over a set of tasks \(\Uptheta.\) In the RL Competitions, \(\mathcal{G}\) is not known to the participants. Instead, only a few MDPs sampled from this distribution are released for training. The competition is then decided by averaging the performance of each participant’s agent across multiple test runs, with each run i conducted using a single task θ _i sampled independently from \(\mathcal{G}, \) where \(\theta_{i} \in \Uptheta\) is an MDP.

At the beginning of each test run, the agent does not know which task has been sampled from \(\mathcal{G}.\) Except in degenerate cases, no fixed policy will perform well across \(\Uptheta.\) Consequently, the agent must learn on-line during each test run in order to perform well in expectation across the test runs.

Before addressing the challenges of generalized helicopter hovering, we first consider how to evolve policies for a single helicopter MDP with fixed wind parameters. This process is a central component in each of the methods presented in Sects. 3.3 and 3.4 for tackling the full, generalized problem.

We use a neuroevolutionary approach, i.e., we evolve policies represented as neural networks. Given its numerous successes in difficult RL tasks [28, 29, 43, 55, 76, 88, 89, 94], especially those that are large, noisy, and continuous, neurevolution is well suited to this task. Other optimization methods, such as cross-entropy [17] or covariance matrix adaptation evolutionary strategies (CMA-ES) [30], could also be used. We do not include empirical comparisons against such alternatives in this article because our purpose is not to identify the best algorithm for optimizing helicopter policies. Instead, our goal is to investigate how to construct complete methods for generalized helicopter hovering. To this end, we employ neuroevolution as a representative optimization method for the subproblem of evolving policies.

In the helicopter problem, each neural network generated by evolution represents a different policy mapping states to actions. To find a good policy, we employ a simple steady-state neuroevolutionary method that builds its initial population off a given prototype network. The details of this algorithm, as well as the parameter settings used for all our experiments on GHH-08 and GHH-09 (i.e., those presented throughout Sects. 3 and 4), are specified in Appendix A.

The fitness function consists of the reward that the agent accrues during a single episode when using the policy specified by the network. Because of stochasticity in the transition function, the resulting fitness function is noisy. Therefore, we also tried using longer fitness evaluations in which reward is averaged over multiple episodes but found no performance improvement.

In the second approach, we evolve SLPs but starting from a prototype network whose weights correspond to a baseline policy provided with the competition software. This baseline policy is robust in that it never causes the helicopter to crash. However, its performance is weak, as it is unable to consistently hover near the target point. This approach can be viewed as a simple form of population seeding, which has proven advantageous in numerous applications of evolutionary methods, e.g., [33, 38, 62].

In the third approach, we evolve multi-layer perceptrons (MLPs) using a topology manually constructed by human experts [57]. The topology, shown in Fig. 1, employs both sigmoid and linear activation functions.

In the fourth approach, we evolve MLPs but seed the initial weights such that it is equivalent to the baseline policy. To implement the linear baseline policy in this nonlinear topology, all links from the hidden nodes to the outputs are set either to 1.0, to propagate the input signal without modification, or to 0.0, so that they have no influence on the network’s output.

All networks have nine inputs, corresponding to the state features described in Table 1, and four outputs, one for each action feature. In all four approaches, evolution optimizes only the weights of fixed-topology networks. However, we also tested two neuroevolutionary methods, NeuroEvolution of Augmenting Topologies (NEAT) [76] and Alternating Extension and Optimization of Neural Networks (AEONN) [46], that can simultaneously optimize network topologies and weights. Unfortunately, neither of these methods discovered topologies that outperformed the manually designed topology. We suspect this result is due to both the quality of the topology, which was highly engineered, and the size of the topology space, which makes it difficult for evolution to search.

To compare these four approaches, we conducted 10 independent runs of each approach in each of the 10 training MDPs, i.e., 100 runs per approach and 400 runs total. The results, averaged over all 100 runs for each method, are shown in the left side of Fig. 2. Student’s t tests confirmed that the differences in final performance between all approaches (except between the two SLP approaches, which converge to nearly identical scores) are statistically significant (p < 0.0026).

The results demonstrate that seeding the population with the baseline policy enables evolution to begin in a relatively fit region of the search space and therefore can significantly speed evolution. This is consistent with many earlier results confirming the efficacy of population seeding, e.g., [33, 38, 62]. The results also show that, when the baseline policy is used, the manually designed MLP performs substantially better than the SLP. This is not surprising since the topology was carefully engineered for helicopter control. More surprising is the poor performance of the MLP when beginning from scratch, without population seeding. This strategy appears to perform the worst. However, a closer examination of the individual runs revealed that the vast majority achieve performance similar to the MLP using the baseline policy, albeit more slowly (as in the best runs shown in the right side of Fig. 2). The remaining few runs converge prematurely, performing badly enough to greatly skew the average.

All the approaches described in this section evolve policies only for a single training MDP, with no attempt to generalize across MDPs with different wind settings. To determine the robustness of the resulting policies, we compared their average performance across all 10 training MDPs to their performance on the particular MDP for which they were trained. Specifically, we selected the best single-layer and multi-layer policy evolved for each MDP from the baseline policy and tested it for 10 episodes in every training MDP. The results are shown in Table 3.

This comparison demonstrates that the MLP policies are far more robust, achieving much better average performance and lower variance across the training MDPs. In fact, no specialized multi-layer policy crashes the helicopter on any of the 10 MDPs. By contrast, the single-layer policies frequently crash on MDPs other than those they trained on, with catastrophic effects on average reward. Nonetheless, even the MLPs see an order of magnitude performance drop when tested across all training MDPs. This result underscores the challenges of achieving high performance in the generalized version of the task, which we address in Sects. 3.3 and 3.4.

The results presented above demonstrate that neuroevolution can discover effective policies for helicopter hovering. However, doing so incurs high sample costs because it requires evaluating tens of thousands of policies through interactions with the environment. Many of these policies yield poor reward or even crash the helicopter. Consequently, directly using evolution to find policies on-line is infeasible for the competition because participants are evaluated on the cumulative reward their agents accrue during learning. Even if methods for improving the on-line performance of neuroevolution [14, 89, 90] were used, such an approach would not be practical.

One way to reduce sample costs is to use a model-based approach. If the agent can learn a model of the environment from flight data for each testing MDP early in the run, that model can simulate the fitness function required by neuroevolution. Thus, once a model has been learned, evolution can proceed off-line without increasing sample costs. Doing so allows the agent to employ a good policy much earlier in the run, thus increasing its cumulative reward.

Learning such a model can be viewed as a form of surrogate modeling, also known as fitness modeling [36], in which a surrogate for the fitness function is learned and used for fitness evaluations. Surrogate modeling is useful for smoothing fitness landscapes [67, 98] or when there is no explicit fitness function, e.g., in interactive evolution [61, 69]. However, it is most commonly used to reduce computation costs [37, 59, 67, 68, 70] by finding a model that is faster than the original fitness function. The use of surrogate modeling in our setting is similar but the goal is to reduce sample costs, not computational costs.

Recall that, as described in Sect. 2.2, helicopter state is updated at 100 Hz while the agent observes this state and adjusts its action only at 10 Hz. Consequently, any learned model is necessarily an approximation, as it can only predict the next control timestep tc + 1 given the current control timestep tc and action, without explicitly modeling the simulator timesteps ts that occur in between. In practice, however, it is still possible to learn models that correctly predict how a given policy will perform in GHH-08.

During the competition, the details of the helicopter environment were hidden. However, helicopter dynamics have been well studied. In particular, Abbeel et al. [3] developed a representation of the transition function of a hovering helicopter that uses a set of linear equations to predict accelerations given a state and action at time ts.The accelerations depend on the values of the g vector, which represent gravity (9.81 m/s) expressed in the helicopter frame. The values of w are zero-mean Gaussian random variables that represent perturbations in acceleration due to noise.

Integrating the accelerations produces an estimate of the velocities at time ts + 1. These velocities describe half the state at time ts + 1. The remaining half, which describes the helicopter’s position, is estimated by adding the velocities at time ts to the position at time ts. As described in Sect. 2.2, reward is a simple function of the helicopter’s current state, which can be approximated using the state estimated with these equations.

Because this model representation was not designed for the generalized version of the problem, it does not explicitly consider the presence of wind. Nonetheless, it can still produce accurate models if the amount of wind in the helicopter frame remains approximately constant, i.e., when the helicopter position and orientation remain fixed. Since helicopters in the hovering problem aim to keep the helicopter as close to the target position as possible, this assumption holds in practice. Therefore, wind can be treated as a constant and learning a complete model requires only estimating values for the weights C, D, and w.

We consider three different approaches to learning these weights. In the first approach, we use evolutionary computation to search for weights that minimize the error in the reward that the model predicts a given policy will accrue during one episode. This approach directly optimizes the model for its true purpose: to serve as an accurate fitness function when evolving helicopter policies. To do so, we apply the same steady-state evolutionary method used to evolve policies (see Appendix A). Fitness is based on the error in total estimated reward per episode using a single policy trained on an MDP with no wind, which we call the generic policy.

In the second approach, we use evolutionary computation to search for weights that minimize error in the model’s one-step predictions. In other words, fitness is based on the average accuracy, across all timesteps tc in an episode, of the state predicted at time tc + 1. Again we use the same steady-state evolutionary method and compute fitness using the generic policy.

In the third approach, we still try to minimize error in one-step predictions but use linear regression in place of evolutionary computation. Linear regression computes the weight settings that minimize the least squared error given one episode of data gathered with the generic policy.

For both the second and third approaches, the flight data must first be preprocessed by dividing it into pairs of consecutive states and subtracting gravity g from the state at tc + 1. After preprocessing, evolution or linear regression is used to estimate C and D. The noise parameters w are approximated using the average of the squared prediction errors of the learned model on the flight data.

We evaluated each of these approaches by using them to learn models for each of the 100 test MDPs that were released after the competition ended. Then we used the learned model to evolve policies in the manner described in Sect. 3.1 Finally, we took the best policy discovered in each evolutionary run and averaged its performance over 5 episodes in the MDP on which the corresponding model was trained.

The results, shown in Table 4, demonstrate that minimizing error in one-step predictions yields much more useful models. They also demonstrate that, when minimizing one-step error, linear regression is more effective than evolution. Furthermore, linear regression requires vastly less computation time than evolution. This difference is not surprising since evolution requires on average approximately 2000 evaluations to evolve a model. By contrast, linear regression requires only one sweep through the flight data to estimate model weights.

In this section, we describe the simple model-free approach for tackling GHH-08 that won first place in the 2008 RL Competition.

The robustness analysis presented in Sect. 3.1 shows that, while it is possible to evolve a policy that will not crash on an arbitrary MDP, such a policy will not perform as well as one optimized for that MDP. Thus, excelling in the competition requires learning on-line in order to adapt to each test MDP. At the same time, a good agent must avoid crashing the helicopter and must minimize the time spent evaluating suboptimal policies during learning.

Therefore, a naïve strategy of evolving a new policy on-line for each test MDP is impractical. Each competition test run lasts only 1,000 episodes but, as shown in Fig. 2, tens of thousands of episodes are required to evolve a strong policy. Even if evolution could find a good policy in 1,000 episodes, it would accrue large negative reward along the way. As mentioned in Sect. 3.2, models of the environment learned from flight data can be used to reduce the sample complexity of on-line learning. However, at the time of the competition, we were unable to learn models accurate enough to serve as reliable fitness functions for evolution.

Instead, we devised a simple, sample-efficient model-free approach. In advance of the competition, specialized policies for each of the 10 training MDPs were evolved using the procedure described in Sect. 3.1 Then, for each test MDP of the competition, the first 10 episodes were spent evaluating each of these specialized policies in that test MDP. Finally, whichever specialized policy performed the best was used for the remaining 990 episodes of that test MDP. This strategy, depicted in Fig. 3, allows the agent to adapt on-line to each test MDP in a sample-efficient way, without needing an accurate model.

Figure 4 (left) shows the results of the generalized helicopter hovering event at the 2008 RL Competition, in which this model-free approach won first place. Of the six entries that successfully completed test runs, only one other entry managed to avoid ever crashing the helicopter, though it still incurred substantially more negative reward. In fact, all the competitors accrued at least two orders of magnitude more negative reward than our model-free approach. Due to these large differences, the results are shown in a log scale. Since this scale obscures details about the performance of the model-free method, the same results are also reproduced in a linear scale in Fig. 4 (right), showing how the slope rises or falls suddenly as the test MDP changes every 1000 episodes.

However, one entry matched the performance of the model-free approach for approximately the first third of testing. This entry, submitted by a team from the Complutense University of Madrid, also uses neuroevolution [51]. However, only single-layer feed-forward perceptrons are evolved. Furthermore, all evolution occurs on-line, using the actual test episodes as fitness evaluations. To minimize the chance of evaluating unsafe policies, their approach begins with the baseline policy and restricts the crossover and mutation operators to allow only very small changes to the policy. While their strategy makes on-line neuroevolution more feasible, three crashes still occurred during testing, relegating it to a fourth-place finish.

After the competition, we successfully implemented the model-learning algorithms described in Sect. 3.2 and tested a model-based approach to generalized helicopter hovering, depicted in Fig. 5. Given some test MDP, one episode of flight data is gathered using the generic policy, which avoids crashing but may not achieve excellent reward on that MDP. Next, a complete model of the test MDP is learned from the flight data via linear regression, the best performing method. Then, neuroevolution is used to evolve a policy optimized for this MDP, using the model to compute the fitness function. Finally, the evolved policy controls the helicopter for all remaining episodes on that MDP.

We also tested an incremental model-based approach, depicted in Fig. 6, which works the same way but continues to evolve new policies using updated models as more flight data is gathered. Specifically, the incremental approach learns a new model at the end of each episode using all the flight data gathered on that MDP. Then, evolution is repeated using the latest model to find a new policy for the next episode. Once the performance of the policy in the MDP is at least as good as that predicted by the model, learning is halted and that policy is employed for the remaining episodes. The incremental approach is similar to traditional methods for model-based RL (e.g., [54, 81]), but evolution, rather than dynamic programming [8], is used to find a policy given the model. It is also similar to apprenticeship learning [1‐5], though the initial flight data is gathered by the generic policy instead of a human expert.

To test these methods, we applied them to each of the 100 test MDPs and measured the average cumulative reward they accrued over 1,000 episodes. Figure 7 shows the results. Student’s t tests confirmed that the differences in final performance between the incremental model-based approach and the other approaches are statistically significant (p < 0.0002).

The model-free approach used in the competition gathers a lot of negative reward in the first 10 episodes as it evaluates each of the policies optimized for the training MDPs. Thereafter, its cumulative negative reward grows more slowly, as it uses only the best of these policies.

Surprisingly, the model-based approach performs worse than the model-free approach. Due to noise in the flight data, linear regression cannot always learn an accurate model given only one episode of flight data. Thus, the policies evolved using that model sometimes perform poorly in the corresponding test MDP. However, the incremental model-based approach performs better than the model-free approach. By continually gathering flight data for learning, it reliably finds an accurate model within a few episodes.

Due to the more complex wind dynamics, neither the model-free nor the model-based methods that excel in GHH-08 perform well in GHH-09. The model-free approach relies on the assumption that each specialized policy evolved off-line is robust enough to test on-line. In other words, while potentially suboptimal, these policies will not incur catastrophic negative reward. This assumption, which holds in GHH-08, does not hold in GHH-09.

To illustrate this effect, we conducted 80 runs testing the performance of the model-free method in GHH-09. Since no test MDPs were available before the competition, the training MDPs are used both for training and testing. First, a specialized policy was evolved for each of the 10 training MDPs. Then, 8 test runs were conducted with each of these MDPs. Since the agent does not know which MDP is used in each run, it tries out each specialized policy (except the one specifically trained for this MDP) during the initial episodes of each test run, as per the model-free method described in Sect. 3.3

The solid red line in Fig. 8 shows the resulting average cumulative performance. Though this method performs well on most runs, approximately 10% of the time the more complex wind dynamics lead to crashes when specialized policies evolved on one training MDP are tested on a different training MDP. Since even a single crash results in so much negative reward, the overall performance of the model-free method is poor.

Different problems arise for the incremental model-based approach. As described in Sect. 3.2, the model representation does not explicitly account for wind. This does not pose a problem for GHH-08, since wind velocities are approximately fixed in the helicopter frame. In GHH-09, however, wind velocity changes substantially over time. As a result, the incremental model-based approach cannot learn accurate models and thus cannot evolve high-performing policies off-line.

The dashed line in Fig. 8 illustrates this effect, showing the average cumulative performance of the incremental model-based method. As before, 80 runs were conducted, 8 on each training MDP. No crashes occurred during these runs, leading to better overall performance than the model-free method. A Student’s t test confirmed that the final performance difference was statistically significant (p = 5.8 × 10⁻¹²). However, the policies produced by the incremental model-based method perform worse on average (−448.07 per episode) than the model-free method when it avoids crashing (−215.83 per episode).

An obvious solution would be to improve the model representation such that it explicitly accounts for wind velocity that changes over time. However, since the wind dynamics were not known during the competition, no prior knowledge was available that would guide the selection of a better model representation. We made several guesses, e.g., that stationary wind had been added to the z-axis, but were unable to find a representation that outperformed the one used for GHH-08.

Therefore, we designed a hybrid approach to try to minimize the weaknesses of both the model-free and incremental model-based approaches in GHH-09. We selected the two most reliable training MDPs⁶ and evolved specialized policies for them. These MDPs are reliable in the sense that, in the experiments shown in Fig. 8, the specialized policies evolved for them never crashed on the other training MDPs. At the beginning of each test run, the hybrid method tests each of the two specialized policies by using it to control the agent for one episode on-line, as in the model-free approach.

Next, the flight data gathered during these two episodes is used to learn a model with linear regression, as in Sect. 3.4 Since evolution does not always produce good policies with such a model, the hybrid method conducts three independent evolutionary runs using this model and tests the resulting policies on-line for one episode each. Finally, the policy that performs best during these five initial episodes (two for policies generated by the model-free method and three for the incremental model-based method) is selected and used for the remainder of the test run.

While this hybrid approach tries to minimize the weaknesses of the model-free and incremental model-based approaches, it still allows some chance of a helicopter crash. In particular, thanks to model inaccuracies, it is possible that one of the three policies evolved from the model will crash when tested. It is also possible that one of these policies will perform well during its initial test but then crash on one or more episodes later in the run. While no crashes occurred during the evaluation of the incremental model-based method shown in Fig. 8, our informal experiments conducted leading up the 2009 competition showed that such crashes do occur approximately 0.5% of the time.

Since even one crash can devastate the overall performance of a helicopter agent, we augmented the hybrid method with safeguards designed to further reduce the chance of a helicopter crash. In particular, the agent tries to detect, within a single episode, whether the helicopter is headed towards a crash. If so, it replaces the current policy with the generic policy. As with GHH-08, the generic policy is evolved in the absence of wind and, while its performance is suboptimal, it never crashes the helicopter.

At the end of any episode in which a dangerous state occurs, the policy that induced that state is discarded. A new evolutionary run using the model is conducted to produce a replacement policy, which is used for the remainder of the test run or until it also induces a dangerous state. The hybrid approach is depicted in Fig. 9.

The blue dotted line in Fig. 8 shows the average cumulative performance of the hybrid method, including this safeguard. As before, 80 runs were conducted, 8 on each training MDP. Integrating the model-free and incremental model-based methods seems to improve performance over using either method alone. A Student’s t test confirmed that the difference in final performance between the hybrid and model-free approaches is statistically significant (p = 1.4 × 10⁻¹⁴). However, due to high variance resulting from infrequent crashes by the incremental model-based method, the performance difference between it and the hybrid method was significant only at a 90% confidence level (p = 0.07585).

By testing only the safest specialized policies, the hybrid method strives to minimize the chance of a catastrophic crash. By testing the results of several independent runs of evolution using the learned model, the hybrid method strives to maximize the chance that a high-performing policy will be selected for the remainder of each run. The safeguard also proved useful: on one run, the helicopter was headed towards a crash while using a policy evolved with the model. The safeguard switched to the generic policy, preventing a crash that would otherwise have erased the hybrid method’s performance advantage.

While these results showed the safeguard’s potential to improve performance, the results of the 2009 competition revealed limitations in its ability prevent crashes. Further experiments conducted after the competition showed that the success rate of the safeguard in preventing crashes depends critically on the choice of the fallback policy. In the following section, we present and discuss these additional results.

Based on its superior performance on the training MDPs, we submitted the hybrid method to the 2009 competition, the results of which are shown in Fig. 10. Three entries successfully completed the test runs but one incurred several orders of magnitude more negative reward than our entry (note the log scale in the figure). The other entry, an updated neuroevolutionary agent submitted by the team from the Complutense University of Madrid, was much more competitive but still accrued 85% more negative reward during the first 19 test runs. However, on the twentieth test run, our entry crashed the helicopter during the third episode, while testing one of the policies evolved from the model. During this episode, the agent detected that the helicopter entered a dangerous state and switched to the generic policy. However, the helicopter was already too close to crashing and the generic policy was unable to stabilize it. The negative reward incurred for this crash was great enough to relegate our entry to a second-place finish.

The crash that prevented the hybrid approach from winning was exactly the sort of event that the safeguards described above were designed to avert. Therefore, after the competition, we conducted additional experiments to analyze the cause of its failure and determine whether the competition was representative of the method’s performance or merely bad luck.

To do so, we tested both the model-free and hybrid methods on the 20 MDPs used in the competition testing runs. For each MDP, we tested each method for 3 independent runs, for a total of 60 runs per method.

We hoped to conduct similar additional runs for the winning agent from the Madrid team. However, we were not able to reproduce the exact agent they submitted. Though they shared with us the source code they used for training, the behavior of their agent depends not only on this code but on the neural-network weights that resulted from an ad-hoc training regimen conducted before the competition. Unfortunately, they were not able to provide us with these weights or sufficient details of the training regimen to enable reliable reproduction of their agent (José Antonio Martin H., personal communication). However, we can still use the winning agent’s performance during the competition as an unbiased estimator of its expected performance.

Figure 11 shows the average cumulative performance of the model-free and hybrid methods during these post-competiton runs, plotted against the average cumulative performance of the winning agent during the competition. As expected, the hybrid method reduces the chance of a crash: it crashed only 1% of the time, compared to 2.67% for the model-free method. As a result, it appears to modestly outperform the model-free method early on, though the difference is significant only at a 90% confidence level (p = 0.08675). However, because it falls back on the generic policy more often, it tends to accrue more negative reward per timestep when it does not crash, such that its final cumulative performance is only as good as that of the model-free method.

Furthermore, the hybrid method’s cumulative performance is not as good as that of the winning agent, suggesting the outcome of the competition was not a fluke. However, the hybrid method was moderately unlucky in the competition: if crashes occur on 1% of runs, the probability of one or more crashes on 20 runs is only 18.21%. It is also possible that the winning agent was lucky and would occasionally crash if tested on all 100 MDPs. However, this seems unlikely, since the winning agent did not crash even on the difficult MDP that proved problematic for the hybrid method in the competition.

In any case, the results make clear that the safeguards built into the hybrid method to minimize crashes are inadequate. From analyzing the runs that resulted in crashes, we concluded that the mechanism for determining that the helicopter is headed towards a crash works reliably, detecting a dangerous state well in advance of the crash. Therefore, we hypothesized that the problem lies in the generic policy to which the agent switches when such states occur. Though not designed to exploit a particular wind setting, the generic policy is still optimized to maximize performance (in the absence of wind). As a result, it may not be robust enough to save the helicopter when it is already in a dangerous state.

To test this hypothesis, we altered the hybrid method to fall back on the baseline policy rather than the generic policy. Recall from Sect. 3.1 that the baseline policy, provided with the competition software, is designed purely for robustness: it is not optimized for any MDP but merely tries to minimize the chance of crashing. We tested this method for 300 runs on the 100 test MDPs, the results of which are also shown in Fig. 11. Using the baseline policy improves the hybrid method’s performance such that it approximately matches that of the winning agent. The improvement is a result of avoiding crashes; in fact, this method never crashed on any of the 300 test runs. However, due to high variance resulting from crashes by the original hybrid method, the performance difference between the two hybrid methods was significant only at a 90% confidence level (p = 0.0849).

Of course, avoiding crashes comes at a price, as the baseline policy performs worse than the greedy policy when the latter does not crash. We chose the generic policy as a fallback because, in training, it seemed to achieve this superior performance without increasing the chance of crashing (see Fig. 8). However, the post-competition analysis reveals that the training MDPs were misleadingly easy and the generic policy is not safe enough to use as a fallback. This design decision proved critical in the competition.

Given a suitably large value of σ, the generalization in FGHH ensures that no single policy will avoid crashing on any MDP drawn from \(\mathcal{G}. \) As a result, finding a suitable generic policy with which to gather flight data for model learning becomes more challenging. In GHH-08 and GHH-09, it was sufficient to evolve a generic policy in the absence of wind and simply assume it was reliable enough to safely gather flight data across all wind settings. As we show below, this approach fails in FGHH because a generic policy evolved on the default settings shown in Table 5 will often crash on other MDPs drawn from \(\mathcal{G}. \)

To address this difficulty, we augment the incremental model-based approach to more rigorously select a generic policy that minimizes the chance of crashing during flight data collection. In particular, a generic policy is evolved, not with a single MDP for the fitness evaluation, but rather with a new MDP sampled from \(\mathcal{G}\) each time. When this evolutionary run completes, the best performing policy is used as a generic policy for the incremental model-based approach shown in Fig. 6. That is, in each test run, the generic policy is used to gather flight data, which is used to evolve a policy specialized to that MDP.

Sampling MDPs from \(\mathcal{G}\) obviously introduces an enormous amount of noise into the fitness function. There are many possible ways to address this, e.g., by enlarging the population according to population-sizing equations that consider the variance of the fitness function [16, 25, 26, 31]. In this article, we focus on the well-known technique of resampling, i.e., averaging performance across multiple episodes. In this section, we consider a simple fixed resampling approach, in which each generic policy is evaluated for k episodes. In Sect. 5.2, we propose a more sophisticated resampling technique.

The fixed resampling approach evolves generic policies using a slightly different neuroevolutionary approach than that used for GHH-08 and GHH-09. In particular, it uses a generational algorithm rather than a steady-state one. This change was made to create consistency with the selection races approach (introduced below in Sect. 5.2), which requires a generational approach. The details of the generational algorithms and parameter settings are specified in Appendix B.

To fully specify FGHH, we must select a value for σ. Choosing σ properly is critical to creating a suitable task. If σ is too low, the task will not be sufficiently generalized and may not be any more difficult than GHH-08 or GHH-09. If σ is too high, the task will be too difficult, as even a resampling approach will not be able to find a generic policy stable enough to gather the flight data needed for model learning.

To ensure an appropriate choice, we tested the fixed resampling approach at different values of σ and k to find a value of σ where the best performing value of k is greater than 1, indicating a need for resampling. We found that when σ < 0.2, no resampling is required. Fig. 12 shows the performance of the generation champion, averaged over 24 independent runs, for different values of k with σ = 0.2. Not surprisingly, there is a trade-off between the speed and quality of learning. Lower values of k make faster progress at the beginning because they can evaluate policies more quickly; higher values of k plateau higher because they can more accurately make fine distinctions between policies. While values of k > 1 perform best in the long run, good performance is still possible with k = 1. In contrast, Fig. 13 shows results when σ = 0.3. In this case, k = 1 performs poorly, as a single fitness evaluation is not enough to guide evolution. When k = 2, evolution makes significant progress but plateaus early. To achieve good performance, k ≥ 5 is required.

The results in the previous section make clear that a significant amount of resampling is required to evolve a good generic policy for FGHH. Consequently, the computational costs of the fixed resampling approach are much higher than those of the model-based approaches used for GHH-08 and GHH-09, since computing each fitness estimate requires simulating multiple episodes of evaluation. The increased computational costs make the fixed resampling approach less practical for a real-world setting. For example, when computational resources are limited, it will be necessary to terminate evolution early, before performance plateaus. As a result, flight data for model learning will be gathered using an inferior generic policy that accrues more negative reward and has a higher chance of crashing the helicopter.

To address this problem, we developed a second method for FGHH that we call the selection races approach. Like the fixed resampling approach, this method evolves a generic policy that minimizes the probability of crashing during flight data collection. As before, it evaluates each candidate policy on multiple MDPs sampled from \(\mathcal{G}. \) However, the number of episodes spent evaluating each policy is not fixed. Instead, episodes are allocated to policies dynamically, in an attempt to most efficiently determine which policies in the current generation should be selected as parents for the next generation.

Many strategies for making resampling more efficient have been developed, e.g., [7, 11, 12, 42, 56, 74]. For this work, we adapt a strategy recently proposed by Heidrich-Meisner and Igel [32] that uses selection races, a technique originally developed by Maron and Moore [50], to determine how many episodes to spend evaluating each policy. The main idea is to maintain confidence intervals around the fitness estimates of each candidate policy. These intervals are used to determine when, with probability δ, the best μ of the λ candidate policies in each generation have been selected for reproduction.⁸

In particular, policies are sorted into three pools: selected, discarded, and undecided. In each iteration, all the undecided policies are evaluated for one additional episode. If, as a result of these evaluations, the lower confidence bound of an undecided policy becomes larger than the upper confidence bound of at least λ − μ other policies, it is moved to the selected pool. Conversely, if the upper confidence bound of an undecided policy is lower than the lower confidence bound of at least μ other policies, it is moved to the discarded pool. This process repeats until the selected pool contains μ policies or every undecided policy has already been evaluated for t _limit episodes. In either case, the μ policies with the highest estimated fitness at the end of the generation are selected for reproduction.

In principle, this method could be directly applied to the problem of selecting generic policies in FGHH. However, in practice, we had to substantially modify the method to produce an algorithm suitable to our setting. The first change concerns the way confidence bounds are computed. Both Heidrich-Meisner and Igel and Maron and Moore propose using the Hoeffding bound, which states that with probability δ the expected fitness of policy i isafter t episodes of evaluation. Here \(\hat{X}_i = \frac{1}{t} \sum_{j=1}^t X_{i,j}, \) where X _i,j is the fitness estimate from the jth evaluation of policy i. Furthermore,where \(X_{i,j} \in [a,b]. \)

The Hoeffding bound is problematic in the helicopter task because of the range of possible fitness estimates a policy can accrue on a given episode. A perfect policy will never accrue negative reward so a = 0. However, the worst possible policy crashes immediately and accrues the maximal possible negative reward on each timestep, yielding b ≃ −1 × 10⁷. Consequently, the confidence bounds are enormous. This would not be a problem if the typical difference in fitness between two policies was in a similar range. However, once evolution discovers policies that rarely crash, differences in fitness are typically many orders of magnitude less than a − b. As a result, using the Hoeffding bound is infeasible, as the conditions required to select or discard policies are never met.

Instead, we use Bayesian confidence bounds, as also proposed by Maron and Moore. This approach typically produces tighter bounds but assumes that the distribution over fitness values for each policy is normal. While this is not necessarily true in FGHH, the Bayesian confidence bounds still perform well in practice. As with the Hoeffding bound, these bounds state that with probability δ the expected fitness of policy i is \(X_i = \hat{X}_i \pm c_{i,t}. \) However, in our implementation, c _i,t is now defined as:where Z _δ is the number of standard deviations from the mean of a standard normal distribution required to contain area of size δ and \(\hat{\sigma}\) is the estimated standard error. This estimate is calculated using the Bayesian method, which employs the Jeffreys prior and assumes that each of the sampled fitness values have the same mean and variance.⁹

The second change concerns the way the confidence bounds are updated. The algorithm described by Heidrich-Meisner and Igel keeps running estimates of these bounds and updates them only when new data makes them tighter. That is,where LB _i and UB _i are the lower and upper confidence bounds of policy i, respectively. This approach works well in their experiments but leads to difficulties in the helicopter task, again because of the large range of possible cumulative rewards. The left side of Fig. 14 illustrates how a sequence of episodes evaluating a given policy can lead to a problematic scenario. In the first two episodes, the policy performs similarly but in the third episode it performs significantly worse. Since the new lower bound would be lower than the old one, it is not updated. As a result \(\hat{X}_i < LB_i. \) In other words, the mean is below the lower bound! This can lead to undesirable behavior in selection races. For example, the policy may be selected even if its expected fitness is low, because its lower bound will stay high no matter how far the mean drops.

To address this problem, we alter the update of the confidence bounds to incorporate new data regardless of whether the new resulting bounds are tighter:The right side of Fig. 14 shows the bounds updates that occur on the same example using this new scheme. Since the bounds are always updated after each episode, the mean stays within the lower and upper bounds and the weaker performance in the third episode produces a corresponding drop in the lower bound.

Algorithm 1 contains pseudocode of our modified selection races algorithms for picking μ policies in a given generation. First, each policy is given an initial evaluation and bounds are initialized (lines 5–8). In each iteration, each undecided policy receives another evaluation and the corresponding bounds are updated (lines 12–17). Then, policies are selected or discarded if appropriate (lines 18–25). Finally, if the selected pool is still too small once t _limit is reached, the highest ranked undecided policies are added to it (lines 34–39).

To evaluate this method, we conducted 24 independent runs in FGHH with σ = 0.3 at each of several values of δ. The other parameters were set as follows: \(\lambda=50, \mu=20, t_{limit} = t_{min} = t_{max} = 10, \alpha=0.1. \) Since FGHH is so noisy, we found that setting t _limit  < t _max was pointless, since t _limit always quickly grew to reach t _max . Hence, we set t _limit  = t _max , which effectively renders t _min and α irrelevant. The other neuroevolutionary parameters were set the same as with fixed resampling, as shown in Appendix B.

Figure 15 shows the resulting performance at each value of δ, compared to the fixed-resampling method at k = 5, the best-performing setting. At every setting, the selection races approach outperforms fixed resampling. Student’s t tests confirmed that these performance differences are statistically significant (p < 1 × 10⁻⁴). By more efficiently allocating episodes of evaluation to candidate policies, the selection races approach is able to find better policies substantially more quickly.

Both these results and those presented in Sect. 5.1 measure only the performance of evolution while searching for generic policies. We also evaluated the performance of the incremental model-based approach in FGHH when using the best policies produced by evolution to gather flight data for learning models. In other words, we tested the strategy shown in Fig. 6 with either the fixed resampling or selection races method used to evolve the generic policy.

Figure 16 shows the results of 100 runs conducted for each method. In each run, the incremental model-based method used the generic policy produced from a different run of either fixed resampling or selection races, at the best-performing settings. As a baseline, the graph also shows the performance of the incremental model-based method using a generic policy discovered as was done for GHH-08 and GHH-09: by evolving it for a fixed MDP, without explicitly selecting for robustness across many MDPs. We used an MDP we call the zero setting, which corresponds to the mean of \(\mathcal{G}\) for FGHH, i.e., using the default parameter values shown in Table 5.

The results verify the importance of evolving a generic policy that is sufficiently robust. Since FGHH is more aggressively generalized, generic policies evolved only for the zero-setting are not reliable, resulting in poor performance for the incremental model-based method. The results also underscore the importance of efficient resampling. Though fixed resampling explicitly searches for robust generic policies, wasteful evaluations slow it down. Consequently, the best generic policy found after 500,000 evaluations leads to performance for the incremental model-based method that is only marginally better than with a generic policy evolved just for the zero setting (the difference is not statistically significant). While fixed resampling could in principle discover better generic policies if run longer, the computational expense of doing so quickly becomes prohibitive. In contrast, thanks to smarter resampling, selection races are able to discover stronger generic policies in the same number of evaluations, yielding much better performance for the incremental model-based method. Student’s t tests confirmed that the differences in final performance between the selection-races and zero-setting methods is statistically significant (p = 0.0402). Due to high variance resulting from infrequent crashes by the fixed-resampling method, the performance difference between it and selection races was significant only at a 90% confidence level (p = 0.0706).