Evolutionary Strategies (ES) are a powerful alternative to standard Reinforcement Learning (RL) because they are "embarrassingly parallel"—you can distribute the workload across hundreds of machines with minimal communication overhead. However, ES is notoriously "sample-inefficient," often requiring millions of trials to learn simple tasks.
In their paper, "Shaped Policy Search for Evolutionary Strategies using Waypoints," Kiran Lekkala and Laurent Itti propose a clever way to fix this. By leveraging intermediate waypoints (subgoals) that are often already available in robotics and navigation tasks, they "shape" the search process, guiding the algorithm toward the optimal solution much faster than traditional methods.
TL;DR
The authors improve the efficiency of Evolutionary Strategies by using intermediate waypoints to learn an "inverse dynamics model" during training. This model generates "surrogate gradients" that bias the search for new policy parameters toward promising regions, allowing the agent to reach global optima faster than standard ES or PPO.
What Problem Does This Paper Address?
Reinforcement Learning agents typically learn by trial and error, receiving a reward only when they succeed (or fail). In complex tasks with "sparse rewards"—like driving a car to a distant destination—an agent might wander aimlessly for a long time before receiving any useful feedback.
Evolutionary Strategies (ES) tackle this by sampling a "population" of different policy parameters and seeing which ones perform best. While ES scales beautifully across computer clusters, it usually ignores the rich information hidden within the trajectories of a failed rollout. It only cares about the final score. The authors argue that if we have access to waypoints (intermediate points the agent should pass through), we can use the data from every single rollout to understand the physics of the environment and guide the "evolution" of the policy more effectively.
Methods
The core of the paper is a technique called Shaped Policy Search. Here is the breakdown of how it works:
- Learning Inverse Dynamics: During rollouts, the agent records its state and the local waypoints it is trying to reach. It uses this data to train an Inverse Dynamics Model ($M_\phi$). This model essentially learns to answer the question: "If I am at state A and want to get to waypoint B, what action should I take?"
- Generating Surrogate Gradients: Using the inverse dynamics model, the system can estimate what the "ideal" actions should have been during a rollout. By comparing the agent's actual actions to these "ideal" actions (using a technique called DAgger), the authors calculate a surrogate gradient.
- Biasing the Search: In standard ES, you sample new policy parameters randomly (usually from a Gaussian distribution). In this "Shaped" version, the authors use the surrogate gradients to warp that distribution. Instead of searching in every direction equally, the algorithm prioritizes searching in directions that align with the "ideal" actions suggested by the dynamics model.
- Distributed Architecture: The system is designed for a Beowulf cluster (a group of identical computers). A "Master" node generates parameters, while "Worker" nodes run the simulations in parallel and send back rewards and surrogate gradients.
Datasets and Simulators
The authors evaluated their method on two distinct, high-fidelity simulators:
- CARLA Driving Simulator: A point-goal navigation task where a car must navigate a complex environment (Town07) from a random start to a random destination using LIDAR and odometry data.
- UR5 Robotic Arm (Gazebo): A task where a 5-degree-of-freedom robotic arm must move its end-effector along a trajectory defined by a quadratic Bezier curve.
Key Insights and Ideas
- Dynamics are "Free" Information: Most RL algorithms throw away the state-transition data from rollouts. By learning an inverse dynamics model, the authors turn "failed" explorations into a teaching tool.
- Waypoints as Heuristics: The paper assumes waypoints are available (which is true for most navigation and industrial robotics tasks). By conditioning the dynamics model on these waypoints, the agent learns a local "compass" that helps it even before it reaches the final goal.
- Covariance Shaping: Unlike "Vanilla-ES," which only updates the mean of the search distribution, this method updates the covariance matrix. This allows the search to become "elongated" toward the goal, effectively narrowing the search space to the most promising regions.
Key Results
The "Shaped" ES method was compared against CMA-ES, Vanilla-ES, and PPO (a state-of-the-art policy gradient method).
- Superior Performance: In both CARLA and the UR5 arm tasks, the proposed method reached higher cumulative rewards faster than all baselines.
- Faster Convergence: In the CARLA simulator, the shaped policy search reached the global optimum significantly earlier in terms of "Wall Time" (actual hours spent training) compared to standard ES methods.
- Accuracy Gains: The authors showed that the accuracy of the inverse dynamics model improves over generations, which in turn makes the surrogate gradients more reliable as training progresses.
Limitations and Future Work
- Waypoint Dependency: The method relies on having access to local waypoints. While the authors suggest using A* search or global planners to generate these in real-world scenarios, the performance of the policy is inherently tied to the quality of these waypoints.
- Covariate Shift: There is a risk that the waypoints generated by a planner might not match the distribution of states the agent actually visits, which could confuse the inverse dynamics model.
- Sim2Real: The authors mention that this method is ideal for training in a simulator where data is abundant before transferring to a real robot, but they did not demonstrate a physical "Sim2Real" transfer in this specific paper.
Overall, this research provides a compelling blueprint for making Evolutionary Strategies more competitive in the RL landscape by simply being smarter about how we use the data we're already collecting.
Summary updated