Applying Online Search Techniques to Continuous-State Reinforcement Learning

AAAI 1998

TL;DR

This paper introduces online search techniques to improve reinforcement learning (RL) in continuous state spaces. By combining approximate value functions with search algorithms, they achieve better control policies and faster learning, especially in complex, high-dimensional problems where traditional methods struggle.

What Problem Does This Paper Address?

Reinforcement learning agents learn to make decisions by interacting with an environment and receiving rewards. A common approach is to learn a "value function" that estimates the expected future reward from any given state. The agent then acts greedily with respect to this value function. However, in continuous state spaces (where states can take on an infinite number of values, like position and velocity), learning an accurate value function is computationally very expensive, even with a perfect model of the environment. This often leads to suboptimal policies. The paper addresses this by proposing methods that use online search to find better trajectories from the current state, rather than relying solely on a pre-computed, potentially inaccurate, global value function.

Methods

The paper presents a progression of search techniques, building upon existing RL and search methods:

  • Local Search (LS): This involves performing a limited-depth lookahead search from the current state using an approximate value function. It's like a "what if I do this for a few steps?" analysis.
  • Constrained Local Search (CLS): This optimizes LS by restricting the search to trajectories where actions are changed infrequently. This significantly speeds up the search, allowing for deeper exploration.
  • Uninformed Global Search (UGS): For "least-cost-to-goal" problems, this method plans a path from the current state all the way to the goal. It uses a sparse grid representation of the state space and prunes redundant trajectories, making large state spaces tractable.
  • Informed Global Search (IGS): This is a key contribution. It enhances UGS by using an approximate value function to guide the search, similar to the A* algorithm. This drastically reduces the search space explored and often leads to better solutions.
  • Learning Local Search (LLS) & Learning Global Search (LGS): These extensions incorporate learning the environment's dynamics model online, which is then used to generate approximate value functions for the LS and CLS approaches.

The approximate value functions are primarily obtained using k-dimensional simplex interpolation combined with value iteration.

Datasets

The paper evaluates its methods on four benchmark domains:

  • MOUNTAIN-PARKING (2D): A simplified car-on-a-hill problem requiring parking with near-zero velocity.
  • ACROBOT (4D): A two-link robot arm task.
  • MOVE-CART-POLE (4D): A cart-and-pole balancing task with a goal to move the cart.
  • SLIDER (4D): A "slider" navigating a 2D terrain to a goal region.

These are described as undiscounted tasks, with MOVE-CART-POLE and SLIDER having specific cost structures. The MOUNTAIN-PARKING domain is highlighted as a good illustration due to its visualizability.

Key Insights and Ideas

  • Search as a Complement to Value Functions: The core idea is that even a rough value function can be immensely useful when combined with online search. Search helps overcome the limitations of approximate value functions by finding accurate trajectories from the current state.
  • The Power of Informed Search: IGS significantly outperforms UGS by using the value function to intelligently prune the search space. This is a crucial insight for tackling high-dimensional problems where exhaustive search is impossible.
  • Constraining Actions for Efficiency: CLS demonstrates that by exploiting domain knowledge (e.g., actions are often held for periods), search efficiency can be dramatically improved without sacrificing solution quality.
  • Global Search for Tractability: UGS and IGS provide a framework for planning long trajectories in continuous spaces by discretizing the state space and using local search to connect these discrete regions.
  • Model Learning Integration: LLS and LGS show that these search techniques can be effectively integrated with online model learning, a critical step for real-world robotics.

Key Results

  • Improved Solution Quality: Across various domains, the proposed search techniques (especially IGS) consistently yielded better solutions (lower costs) compared to no search or basic greedy policies. For instance, in SLIDER, IGS achieved a factor of 4 improvement in cost.
  • Faster Learning with Model Learning: LLS and LGS significantly accelerated learning in the MOUNTAIN-PARKING domain with model learning, reaching good policies in far fewer trials than without search.
  • Computational Trade-offs: While search increases computation time per step, it often leads to much shorter trajectories, resulting in comparable or even better overall trial times for improved solutions. For example, IGS often achieved similar trial times to "no search" but with vastly superior results.
  • UGS vs. IGS: IGS generally outperforms UGS, especially when the value function is reasonably accurate, by exploring a much smaller portion of the state space. However, in cases with very large search grids, UGS can sometimes find better solutions if the value function's inaccuracies lead IGS astray.

Limitations and Future Work

  • Curse of Dimensionality: The authors acknowledge that their experiments are low-dimensional. While IGS handles larger grids, they conclude that more sophisticated value function approximators and variable-resolution state-space partitioning methods will be needed for truly high-dimensional problems.
  • Value Function Accuracy: The performance of IGS is sensitive to the accuracy of the value function. Inaccurate heuristics can lead to suboptimal solutions, a known issue in A*-like searches.
  • Non-deterministic Systems: The paper focuses on deterministic domains. Extending these techniques to non-deterministic systems will require more advanced state transition function approximators, especially when learning models online.
  • Open-Loop Control: The planned trajectories are executed in an open-loop fashion. Adaptive closed-loop controllers could further improve performance, especially when dealing with model inaccuracies.
  • Local Trajectory Optimization: For domains with continuous action spaces, incorporating local trajectory optimization routines could fine-tune discovered trajectories.
  • Optimistic Value Functions: Developing algorithms that learn consistently "optimistic" value functions could further enhance the performance of Informed Global Search.

Summary updated

BibTeX
@inproceedings{1998applying,
  title = {{Applying Online Search Techniques to Continuous-State Reinforcement Learning}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1998},
}
Figure