A0C: Alpha Zero in Continuous Action Space

Thomas M. Moerland, Joost Broekens, Aske Plaat, Catholijn M. JonkerarXiv 2018 · arXiv

TL;DR

This paper introduces A0C, an extension of the Alpha Zero algorithm designed for continuous action spaces. By combining Monte Carlo Tree Search (MCTS) with "progressive widening" and a continuous policy prior, the authors demonstrate that the powerful "search-and-learn" loop used to master Go and Chess can be successfully adapted for robotics and control tasks.

What Problem Does This Paper Address?

Alpha Zero achieved superhuman performance in discrete games like Go and Chess by interleaving tree search with deep learning. However, its core mechanism—Monte Carlo Tree Search (MCTS)—relies on the ability to enumerate all possible actions at any given state.

In the real world, many reinforcement learning (RL) problems involve continuous action spaces. For example, a self-driving car doesn't just choose between "left" and "right"; it chooses a specific steering angle from an infinite range of possibilities. Standard MCTS breaks down here because you cannot create a branch for every possible action. This paper aims to bridge that gap, allowing the Alpha Zero paradigm to be applied to domains like robotics and navigation.

Methods

The authors propose three primary modifications to the Alpha Zero framework to handle continuity:

  1. Progressive Widening: To handle the infinite number of possible actions, the algorithm uses a technique called progressive widening. Instead of evaluating all actions, the search tree starts with a small number of actions and gradually adds new ones as the state is visited more frequently. This ensures that promising areas of the action space are explored deeply while still allowing for new discoveries.
  2. Continuous Policy Prior: In discrete Alpha Zero, the neural network provides a probability for each move to guide the search. In A0C, the network outputs the parameters of a Beta distribution (transformed to fit the action bounds). Because a continuous density is unbounded and cannot be used directly in standard selection formulas, A0C uses this distribution to sample new candidate actions for the tree.
  3. Continuous Training Targets: The authors derive a new policy loss based on the Kullback-Leibler (KL) divergence. They treat the MCTS visitation counts as an empirical, unnormalized density and train the neural network to mimic this density at the sampled support points. They also include an entropy regularization term to prevent the policy from collapsing into a single point, which would kill exploration.
Figure 1: Iterated tree search and function approximation.

As shown in Figure 1, the system maintains a closed loop: the tree search generates high-quality data for the neural network, and the neural network, in turn, provides a prior that makes the next tree search more efficient.

Datasets

The algorithm was evaluated on the Pendulum-v0 task from the OpenAI Gym. This is a classic control problem where an agent must learn to swing up and balance a pendulum by applying torque. While simpler than Go, it serves as a fundamental benchmark for continuous control.

Key Insights and Ideas

  • The "Sweet Spot" of Search: The authors found that there is a critical trade-off between the size of the tree search and the frequency of neural network updates. If the tree is too small (e.g., 1 trace), the agent generalizes too much without enough local exploration. If the tree is too large, the agent spends too much time searching and doesn't update its global "intuition" (the neural network) often enough.
  • Search as a Stabilizer: Tree search acts as a local stabilizer. While neural networks are great at generalizing across states, they can have local errors. The forward-looking nature of MCTS helps smooth out these errors by aggregating information from multiple potential future traces.
  • Density vs. Sampling: A major theoretical hurdle was how to use a continuous prior. By using the network to sample new nodes rather than just scaling a confidence interval, they effectively "prune" the infinite action space into a manageable, high-probability subset.

Key Results

The experiments on the Pendulum task confirmed that A0C can successfully learn in continuous spaces.

Figure 2: Learning curves for Pendulum domain. Compared to the OpenAI Gym implementation we rescale every reward by a factor 1/1000 (which leaves the task and optimal solution unchanged). Results averaged over 10 repetitions.

As seen in Figure 2, the performance varied significantly with the search budget ($N_{traces}$):

  • Intermediate budgets (e.g., $N=10$) performed best. These runs found the right balance between high-quality search targets and frequent network training.
  • Very small budgets ($N=1$) failed to solve the task effectively, highlighting the necessity of the search component.
  • Very large budgets ($N=100$) learned more per environment step but were much slower in terms of wall-clock time and required more total environment interactions to reach peak performance because the network was updated less frequently.

Limitations and Future Work

  • Task Complexity: The current results are limited to the 1D Pendulum task. The authors acknowledge that future work must test A0C on more complex, high-dimensional environments like those found in the MuJoCo physics engine.
  • Computational Cost: MCTS is computationally expensive. Finding ways to make the search more efficient or leveraging more advanced network architectures (like those used in the original Alpha Zero) remains an open challenge.
  • Hyperparameter Sensitivity: The balance between search and learning (governed by $c_{pw}$ and $N_{traces}$) appears sensitive and may require careful tuning for different domains.

Summary updated

Abstract

A core novelty of Alpha Zero is the interleaving of tree search and deep learning, which has proven very successful in board games like Chess, Shogi and Go. These games have a discrete action space. However, many real-world reinforcement learning domains have continuous action spaces, for example in robotic control, navigation and self-driving cars. This paper presents the necessary theoretical extensions of Alpha Zero to deal with continuous action space. We also provide some preliminary experiments on the Pendulum swing-up task, empirically showing the feasibility of our approach. Thereby, this work provides a first step towards the application of iterated search and learning in domains with a continuous action space.
BibTeX
@misc{moerland2018c,
  author = {Thomas M. Moerland and Joost Broekens and Aske Plaat and Catholijn M. Jonker},
  title = {{A0C: Alpha Zero in Continuous Action Space}},
  year = {2018},
  eprint = {1805.09613},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1805.09613},
}

Loading related content...

Figure