Prioritizing Starting States for Reinforcement Learning

Arash Tavakoli, Vitaly Levdik, Riashat Islam, Petar KormushevarXiv 2018 · OpenReview

Abstract

We consider the generic approach of using an experience memory to help exploration by adapting a restart distribution. That is, given the capacity to reset the state with those corresponding to the agent's past observations, we help exploration by promoting faster state-space coverage via restarting the agent from a more diverse set of initial states, as well as allowing it to restart in states associated with significant past experiences. This approach is compatible with both on-policy and off-policy methods. However, a caveat is that altering the distribution of initial states could change the optimal policies when searching within a restricted class of policies. To reduce this unsought learning bias, we evaluate our approach in deep reinforcement learning which benefits from the high representational capacity of deep neural networks. We instantiate three variants of our approach, each inspired by an idea in the context of experience replay. Using these variants, we show that performance gains can be achieved, especially in hard exploration problems.

Introduction

Reinforcement Learning (RL) agents often struggle with exploration in vast state spaces. While off-policy methods like DQN utilize Experience Replay to reuse past transitions, on-policy methods like PPO typically cannot, as they require data generated by the current policy. This often leads to agents "forgetting" rare or significant states as soon as they move past them. This paper explores whether replaying starting points, rather than transitions, can alleviate this. By "teleporting" an agent back to promising areas it has previously visited, we can facilitate deeper exploration from the frontier of its knowledge.

Methods

The proposed approach maintains a Restart Memory—a buffer of previously encountered states. During training, the agent occasionally (e.g., 10% of the time) starts an episode from a state sampled from this memory instead of the default initial state. Three sampling strategies are evaluated:

  1. Uniform Restart: Random sampling to promote general diversity in starting positions.
  2. Prioritised Restart: Sampling based on Temporal-Difference (TD) error, targeting states where the agent's value function was most "surprised."
  3. Episodic Restart: Designed for sparse-reward tasks, prioritizing states from trajectories that achieved high total returns. A nested storage mechanism maintains a diverse set of high-performing starts to prevent over-optimization.

Crucially, this method is compatible with on-policy learning because once the agent is restarted, it interacts with the environment normally using its current policy.

Key Results

The researchers evaluated their approach using the MuJoCo physics engine on both dense-reward tasks (HalfCheetah, Humanoid) and sparse-reward tasks (FetchReach, Thrower).

Dense-Reward Performance

In high-dimensional tasks like Humanoid, both Uniform and Prioritised restarts significantly outperformed the baseline PPO agent. Interestingly, Uniform Restart often performed slightly better than Prioritised in these environments, suggesting that simple diversity is a powerful tool for navigating complex state spaces.

Average score comparison for dense-reward tasks HalfCheetah and Humanoid.

Sparse-Reward Success

The most dramatic results were observed in sparse-reward environments. In the Thrower task, where rewards are only granted upon hitting a target, the baseline PPO agent failed to learn in 80% of trials. In contrast, the agent using Episodic Restarts consistently learned a successful policy across all independent runs, demonstrating that restart distributions can make learning possible in environments where rewards are extremely rare.

Average success rate for sparse-reward tasks FetchReach and Thrower.

Discussion and Limitations

By modifying the initial state distribution, the agent effectively sees a curriculum of starting points, allowing it to bypass mastered areas and spend more time at the frontier of its knowledge. While the high representational capacity of deep neural networks helps mitigate the learning bias introduced by changing the objective function, some limitations remain.

The primary constraint is the requirement for a simulator that allows resetting to specific states, which is difficult in real-world robotics. Additionally, the current work assumes access to the underlying state; extending this to raw pixel observations remains an open challenge for future research.

Summary updated

Abstract

We consider the generic approach of using an experience memory to help exploration by adapting a restart distribution. That is, given the capacity to reset the state with those corresponding to the agent's past observations, we help exploration by promoting faster state-space coverage via restarting the agent from a more diverse set of initial states, as well as allowing it to restart in states associated with significant past experiences. This approach is compatible with both on-policy and off-policy methods. However, a caveat is that altering the distribution of initial states could change the optimal policies when searching within a restricted class of policies. To reduce this unsought learning bias, we evaluate our approach in deep reinforcement learning which benefits from the high representational capacity of deep neural networks. We instantiate three variants of our approach, each inspired by an idea in the context of experience replay. Using these variants, we show that performance gains can be achieved, especially in hard exploration problems.
BibTeX
@misc{tavakoli2018prioritizing,
  author = {Arash Tavakoli and Vitaly Levdik and Riashat Islam and Petar Kormushev},
  title = {{Prioritizing Starting States for Reinforcement Learning}},
  year = {2018},
  eprint = {1811.11298},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1811.11298},
}
Figure