Solving CartPole with Simulated Annealing

The CartPole problem is a classic challenge in reinforcement learning, where an agent must balance a pole on a cart. In a previous post, the Cross-Entropy Method was used to solve CartPole, but it required a large number of episode evaluations. A simpler approach is to use simulated annealing, which perturbs a single set of parameters and accepts improvements. This method has been used to solve CartPole-v1 with a perfect score of 500 in just 41 iterations.

The Algorithm

The simulated annealing algorithm starts with an initial set of parameters and perturbs them at each iteration. The perturbation is scaled by a factor alpha, which is initially set to 1.0. The algorithm then evaluates the new parameters over multiple episodes and calculates the average score. If the new score is better than the previous best score, the new parameters are accepted and the alpha factor is reduced. This process continues until the maximum number of iterations is reached.

Implementation

The implementation of the simulated annealing algorithm is straightforward. The evaluate_policy function evaluates a given policy over multiple episodes and returns the average score. The simulated_annealing function implements the main loop of the algorithm, perturbing the parameters, evaluating the new policy, and accepting improvements. The alpha factor is reduced at each improvement, which helps to focus the search around the current best parameters.

Results

The results of the simulated annealing algorithm are impressive. With just 800 total episode evaluations, the algorithm is able to solve CartPole-v1 with a perfect score of 500. This is significantly fewer evaluations than the Cross-Entropy Method, which required 10,000 evaluations. The algorithm's ability to adapt the alpha factor also helps to improve the convergence rate.

Conclusion

In conclusion, simulated annealing is a powerful algorithm for solving complex optimization problems like CartPole. Its ability to adapt the perturbation factor and focus the search around the current best parameters makes it an attractive alternative to other methods. With its simplicity and effectiveness, simulated annealing is definitely worth considering for your next reinforcement learning project.