Addressing Sparse Reward Problems in Model-Free Reinforcement Learning

This summary article originates from the author Feng Chao of Didi, based on a presentation at the PRICAI2018 Reinforcement Learning Workshop.

Model‑free reinforcement learning has achieved remarkable success, but it follows two main steps: (1) collecting interaction data <state s, action a, reward r> by executing the current policy in the environment, and (2) training a model on this data so that it can predict long‑term discounted returns, similar to supervised learning. Despite its achievements, model‑free methods face three key problems: the need for large amounts of data that scales with problem size, the risk of merely memorizing data without true generalization, and difficulty handling sparse‑reward environments.

Sparse Reward Problem

A classic example of a sparse‑reward task is the game Montezuma’s Revenge, where the agent receives rewards only for rare events such as obtaining a key or opening a door, while most actions yield no feedback, causing learning to stall.

One straightforward remedy is to redesign the reward function to be denser, but this requires expert knowledge and conflicts with the goal of building autonomous agents that learn without handcrafted rewards.

Typical Solutions

Expert Demonstrations

Curriculum Learning

Self‑Play

Hierarchical Reinforcement Learning

Count‑Based Exploration

Below are brief introductions to each method.

Expert Demonstrations

Instead of manually shaping a reward function, experts can provide demonstration trajectories. In off‑policy algorithms, a replay buffer can store both agent‑generated experiences and expert demonstrations, allowing the model to learn from both sources.

Curriculum Learning

Curriculum learning lets the agent progress from easy to hard tasks, similar to teaching a child basic arithmetic before calculus. Reverse curriculum learning starts from a state close to the goal and works backward, selecting appropriate intermediate “starting points” based on the agent’s estimated return.

Self‑Play

Inspired by AlphaZero, self‑play creates a competitive environment where two agents of comparable strength train against each other, encouraging the development of robust strategies. To avoid overfitting to a single opponent, a pool of diverse opponents is maintained.

Hierarchical Reinforcement Learning

Hierarchical RL decomposes a task into two levels: a Meta‑Controller that proposes sub‑goals and a Controller that executes actions to achieve those sub‑goals, effectively breaking a long trajectory into manageable segments.

Count‑Based Exploration

In environments with a finite state space, visitation counts can be used to augment the reward, encouraging the agent to explore less‑visited states. For large or continuous spaces, a mapping function (e.g., using hashing or learned embeddings) approximates counts for similar states.

The article concludes with author information: Feng Chao, Didi Chuxing, contributor to the "Pain‑Free Machine Learning" column, and references to his books on reinforcement learning and deep learning.