Binary action search for learning continuous-action control policies

Jason Pazis, Michail G. LagoudakisICML 2009 · DOI

TL;DR

This paper introduces Binary Action Search (BAS), a novel method for enabling reinforcement learning agents to learn effective control policies in domains with continuous action spaces. BAS cleverly transforms the problem of selecting a continuous action into a series of binary decisions, making it compatible with existing discrete-action RL algorithms and significantly improving learning efficiency and performance.

What Problem Does This Paper Address?

Many real-world applications, from robotics to autonomous systems, require agents to make decisions in continuous action spaces. Think of controlling the precise torque of a robot's joint or the exact speed of a vehicle. However, most reinforcement learning (RL) algorithms are designed for discrete action spaces (e.g., "turn left," "turn right," "accelerate"). To handle continuous actions, researchers often resort to coarse discretization, which can lead to inefficiency and suboptimal performance, especially when the number of discrete actions becomes large. This paper tackles the challenge of efficiently learning control policies in continuous action spaces without the limitations of discretization, particularly in scenarios where actions don't exhibit strong temporal locality (meaning consecutive optimal actions can be quite different).

Methods

The core innovation is the Binary Action Search (BAS) algorithm. Instead of directly outputting a continuous action, BAS relies on a learned binary policy. This binary policy answers a simple question for each continuous action variable: "Should I increase or decrease the current action value?"

Here's how it works:

  1. Augmented State Space: The binary policy operates on an augmented state space that includes the original state of the environment and the current candidate action value being considered.
  2. Binary Search: BAS uses this binary policy to perform a binary search over the entire continuous action range. Starting with a candidate action at the midpoint of the range, the binary policy guides the search by repeatedly halving the remaining action space.
  3. Resolution: The number of binary decisions (queries to the binary policy) determines the resolution of the final continuous action. For example, 8 bits of resolution allow for 256 distinct action choices, achievable with just 8 binary decisions.
  4. Compatibility: Crucially, BAS can be combined with any existing RL algorithm that can learn a binary policy over continuous states. The paper demonstrates this by integrating BAS with Least-Squares Policy Iteration (LSPI) and Fitted Q-Iteration (FQI).

This approach contrasts with prior methods like Adaptive Action Modification (AAM), which relied on adaptive step sizes and temporal action locality, and could struggle when these assumptions didn't hold. BAS, by contrast, is more general and doesn't require temporal action locality.

Datasets

The paper evaluates BAS on three standard continuous-action control benchmark domains:

  • Inverted Pendulum: Balancing a pendulum at the upright position.
  • Double Integrator: Controlling a car on a flat terrain to reach a target position and velocity.
  • Car on the Hill: Driving an underpowered car up a hill.

These are not new datasets but rather established environments used to demonstrate the effectiveness of RL algorithms in continuous control.

Key Insights and Ideas

  • Transforming Continuous to Discrete: The most significant insight is reframing the continuous action selection problem as a series of binary decisions. This elegantly leverages the strengths of existing discrete RL algorithms.
  • Arbitrary Resolution: BAS allows for achieving arbitrary resolution in the action space by simply increasing the number of binary search steps (resolution bits), offering a flexible and powerful way to explore continuous actions.
  • No Temporal Locality Assumption: Unlike some prior methods, BAS does not assume that consecutive optimal actions will be close to each other. This makes it applicable to a wider range of real-world problems.
  • Efficiency: By using a binary search, BAS can find a highly precise action with a logarithmic number of queries to the learned policy, making it computationally efficient.
  • Anytime Algorithm: BAS can be viewed as an "anytime" algorithm, meaning it can provide a reasonable action even if interrupted, and can refine its decision as more time becomes available.

Key Results

The paper demonstrates BAS's effectiveness across the tested domains:

  • Inverted Pendulum: BAS controllers learned by LSPI and FQI achieved significantly better cumulative rewards and required fewer training episodes compared to discrete action controllers. They also exhibited much smaller mean force magnitudes, indicating more efficient control. Crucially, BAS controllers maintained balance even under significantly increased noise levels where discrete controllers failed.
  • Double Integrator: BAS controllers again learned much faster and achieved better rewards than discrete counterparts. While a combined state-action approximator also performed well, BAS offered a better trade-off between performance and computational cost.
  • Car on the Hill: This domain was chosen to test BAS in a scenario where discrete "bang-bang" controllers are known to be optimal. While BAS required more steps initially due to the challenge of sampling extreme actions in a continuous space, its performance improved significantly with more training data. The paper notes that in an online learning setting, BAS performance would likely be comparable to discrete controllers.

Limitations and Future Work

  • State Space Complexity: The BAS approach requires augmenting the state space with the current candidate action value. While the overhead is manageable, it does increase the complexity for the underlying learning algorithm.
  • Sample Efficiency (Car on the Hill): In domains like "Car on the Hill," where optimal actions are extreme, BAS can initially be less sample-efficient because random sampling in a continuous space has a lower probability of hitting these extreme values. The authors suggest that online learning, where the agent can focus sampling on promising regions, would mitigate this.
  • Multidimensional Actions: The paper mentions that extending BAS to handle simultaneous decisions for multiple continuous action variables is an area of ongoing research. This would involve learning a binary policy for each action variable, which could become computationally expensive if not managed carefully.
  • Skewing Functions: The authors propose using non-linear "skewing functions" to distort the action space, allowing for finer resolution in important areas while reducing it elsewhere. This could further improve efficiency and is a promising avenue for future work.

Summary updated

BibTeX
@inproceedings{pazis2009binary,
  author = {Jason Pazis and Michail G. Lagoudakis},
  title = {{Binary action search for learning continuous-action control policies}},
  booktitle = {International Conference on Machine Learning},
  year = {2009},
  doi = {10.1145/1553374.1553476},
}
Figure