Online exploration in least-squares policy iteration

Lihong Li, Michael L. Littman, Christopher R. Mansley

TL;DR

This paper tackles the challenge of efficient exploration in large-scale reinforcement learning problems where function approximation is necessary. The authors propose LSPI-RMAX, a novel algorithm that integrates the RMAX exploration strategy with Least-Squares Policy Iteration (LSPI), demonstrating superior performance on benchmark tasks compared to standard exploration methods.

What Problem Does This Paper Address?

Reinforcement learning (RL) agents face a fundamental dilemma: exploration vs. exploitation. To maximize cumulative rewards, an agent must balance using its current knowledge (exploitation) with gathering new information about the environment (exploration). This is particularly challenging in large or continuous state spaces, where traditional tabular methods are infeasible, necessitating function approximation. While algorithms like Least-Squares Policy Iteration (LSPI) are effective for learning in such environments, they often rely on simple exploration strategies like epsilon-greedy, which can be inefficient. This paper aims to bridge this gap by developing a more intelligent exploration strategy for LSPI in large-scale, continuous Markov Decision Processes (MDPs).

Methods

The core contribution of this paper is the LSPI-RMAX algorithm. It combines the strengths of two existing approaches:

  • Least-Squares Policy Iteration (LSPI): A state-of-the-art model-free RL algorithm known for its efficiency and stability in large environments, particularly when using linear function approximation. LSPI iteratively improves a policy by evaluating its value function and then updating the policy to be greedy with respect to the new value function.
  • RMAX: An exploration strategy for finite MDPs that embodies the "optimism in the face of uncertainty" heuristic. RMAX maintains a model of the environment and treats unknown state-action pairs as maximally rewarding, encouraging exploration.

LSPI-RMAX adapts the RMAX concept of "known" vs. "unknown" state-action pairs to continuous state spaces. Instead of exact state-action pairs, it uses a distance function and a threshold ($\epsilon_d$) to define "$\epsilon_d$-close" samples. A state-action pair is considered ($\epsilon_d$, m)-known if at least m samples within $\epsilon_d$ distance have been observed. This allows LSPI-RMAX to generalize the RMAX heuristic to continuous domains. The algorithm uses a modified Least-Squares Temporal Difference (LSTD) method, called LSTD-RMAX, as a subroutine within LSPI to evaluate value functions. LSTD-RMAX assigns a maximum possible reward to unknown state-action pairs, effectively guiding LSPI towards exploring uncertain regions of the state space.

Datasets

The paper evaluates LSPI-RMAX on four continuous, episodic benchmark domains:

  • MOUNTAINCAR: A classic RL problem where an agent must drive a car to a hilltop.
  • BICYCLE: A deterministic version of a bicycle balancing problem.
  • EXPRESSWORLD: An adaptation of PUDDLEWORLD, featuring an "express lane" to incentivize exploration.
  • CONTCOMBLOCK: A continuous version of a combination lock problem designed to require smart exploration.

No new datasets were introduced.

Key Insights and Ideas

  • Generalizing Optimism to Continuous Spaces: The paper successfully extends the "optimism in the face of uncertainty" principle from finite MDPs (RMAX) to continuous state spaces by introducing the concept of ($\epsilon_d$, m)-known state-action pairs. This is a crucial step for applying powerful exploration strategies to more realistic problems.
  • Synergy of LSPI and RMAX: The combination of LSPI's efficient learning and planning capabilities with RMAX's intelligent exploration proves to be highly effective. LSPI-RMAX can discover better policies than LSPI with simpler exploration methods.
  • Exploration Cost vs. Reward: The experiments, particularly on EXPRESSWORLD, highlight that initial exploration can lead to lower immediate rewards but ultimately results in a superior long-term policy. This demonstrates the value of strategic exploration.
  • Parameter Sensitivity: The study of the parameter m (the threshold for known state-action pairs) reveals a trade-off. Small m leads to faster exploitation but potentially suboptimal policies and higher variance, while large m leads to more robust learning but delayed exploitation. Medium values of m appear to offer the best balance.

Key Results

  • LSPI-RMAX demonstrated superior performance on MOUNTAINCAR and BICYCLE, converging to much better policies than LSPI with epsilon-greedy or counter-based exploration.
  • In CONTCOMBLOCK, LSPI-RMAX was the only algorithm that succeeded in finding a good policy.
  • The learning curves for EXPRESSWORLD showed that LSPI-RMAX initially performed worse due to exploration but eventually surpassed other methods, illustrating the cost and benefit of exploration.
  • The paper provides a theoretical bound on the sample complexity of LSPI-RMAX, suggesting its efficiency.

Limitations and Future Work

  • Formal Analysis Complexity: The authors acknowledge that a thorough formal analysis of LSPI-RMAX is difficult, and a key assumption (Assumption 1) regarding the cover number of the MDP is hard to verify. Extending the formal analysis without this assumption is a significant future research direction.
  • Feature Engineering: The paper notes that feature engineering is an orthogonal problem to exploration and was not optimized. Future work could explore how better features might interact with the proposed exploration strategy.
  • Model-Based Approaches: The paper focuses on model-free methods. Investigating model-based approaches for exploration in continuous environments is suggested as a future research avenue.
  • Realistic Control Problems: The authors plan to test LSPI-RMAX on more realistic control problems beyond the benchmark domains used in the paper.
  • Gaussian Processes: The paper suggests exploring Gaussian processes as function approximators, which naturally provide confidence intervals useful for exploration.

Summary updated

Abstract

One of the key problems in reinforcement learning is balancing exploration and exploitation. Another is learning and acting in large or even continuous Markov decision processes (MDPs), where compact function approximation has to be used. In this paper, we provide a practical solution to exploring large MDPs by integrating a powerful exploration technique, Rmax, into a state-of-the-art learning algorithm, least-squares policy iteration (LSPI). This approach combines the strengths of both methods, and has shown its effectiveness and superiority over LSPI with two other popular exploration rules in several benchmark problems.
BibTeX
@inproceedings{li2009online,
  author = {Lihong Li and Michael L. Littman and Christopher R. Mansley},
  title = {{Online exploration in least-squares policy iteration}},
  booktitle = {AAMAS},
  year = {2009},
}
Figure