Deriving Subgoals Autonomously to Accelerate Learning in Sparse Reward Domains

Michael Dann, Fabio Zambetta, John ThangarajahAAAI 2019 · DOI

Introduction

Reinforcement Learning (RL) agents often struggle in "sparse reward" environments, where feedback is infrequent. In games like Montezuma’s Revenge, an agent might play for extended periods without receiving a single point. This creates a "chicken-and-egg" problem: an agent cannot improve its policy without rewards, but it cannot find rewards without a purposeful policy. While Hierarchical Reinforcement Learning (HRL) addresses this by breaking tasks into subgoals, these subgoals typically require human definition. This paper introduces a method to autonomously discover subgoals using Exploration Effort (EE) and a Pellet Reward scheme.

Autonomous Subgoal Discovery via Exploration Effort

Many autonomous methods rely on visual novelty to identify subgoals. However, visual novelty is often a poor proxy for progress; for instance, in Freeway, background traffic changes constantly but is irrelevant to the agent's goal. The authors instead propose Exploration Effort (EE), a metric that measures how much an agent must deviate from its current policy to reach a new state. By focusing on the "effort" required to reach a state, the agent prioritizes states it can actually control. The system uses a Siamese network to process raw pixels and estimate EE, allowing it to function without handcrafted features.

The Pellet Reward Mechanism

To encourage exploration without falling into the "soaking" trap—where an agent stays in a novel area just to collect intrinsic rewards—the authors introduce Pellet Rewards. Inspired by Ms. Pacman, these rewards are consumable. An agent receives an intrinsic reward the first time it enters a new partition of the state space during an episode. Once visited, the reward is exhausted for that episode, compelling the agent to perform a depth-first search and move deeper into the environment to find new subgoals.

Experimental Results

The approach was tested on the Arcade Learning Environment (ALE), focusing on sparse-reward games like Venture, Freeway, and Montezuma’s Revenge.

Performance comparison on sparse-reward Atari games (Venture, Freeway, Montezuma's Revenge)

As shown in the figure above, the "With Pellets" method significantly outperforms the baseline. In Montezuma’s Revenge, the agent achieved a score of 2,500, while the baseline DQN scored 0. Notably, the method reached competitive scores in roughly 30 million frames, a massive improvement over previous autonomous subgoal methods like FeUdal Networks, which required nearly a billion frames to reach similar performance.

Robustness in Dense Reward Domains

A key strength of the pellet reward system is its robustness. Unlike other exploration methods that can distract an agent in games with already plentiful rewards, this method does not degrade performance in dense-reward environments.

Performance on Battlezone (dense reward)

In safety testing on Battlezone, the agent maintained high performance, demonstrating that the intrinsic pellet rewards do not interfere with the primary task when external rewards are sufficient. This robustness ensures that the agent remains focused on the game's actual score rather than chasing novelty for its own sake.

Conclusion

By leveraging Exploration Effort to identify controllable subgoals and using consumable pellet rewards to drive exploration, this method effectively navigates the challenges of sparse-reward domains. The result is a highly sample-efficient system capable of solving complex Atari games without human intervention. Future work may focus on incorporating uncertainty estimates to further refine the EE metric during early training phases.

Summary updated

BibTeX
@inproceedings{dann2019deriving,
  author = {Michael Dann and Fabio Zambetta and John Thangarajah},
  title = {{Deriving Subgoals Autonomously to Accelerate Learning in Sparse Reward Domains}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2019},
  doi = {10.1609/aaai.v33i01.3301881},
}
Figure