Explicit Planning for Efficient Exploration in Reinforcement Learning

Liangpeng Zhang, Ke Tang, Xin Yao

Introduction

Most Reinforcement Learning (RL) agents explore their environment using "greedy" heuristics—simple rules of thumb that prioritize the most uncertain areas. This paper argues that such heuristics are fundamentally flawed and proposes VIEC (Value Iteration for Exploration Cost), an algorithm that treats exploration as a planning problem to find the most efficient path to gather necessary data, potentially turning exponential exploration times into linear ones.

The Flaw in Heuristic Exploration

In RL, an agent must explore its environment to collect enough data to build an accurate model. Systematic exploration strategies like R-MAX or MBIE provide theoretical guarantees that they will eventually find an optimal policy. However, these strategies are "greedy": they choose the next action based on immediate heuristic scores (like an "uncertainty bonus").

The authors identify a major flaw in this approach, categorizing the pitfalls into two primary traps:

  1. Distance Traps: An agent might prioritize a nearby state because it's easy to reach, even if visiting a distant state first would allow it to "sweep" through the nearby state on the way back, saving total steps.
  2. Reward Traps: High-reward areas can "lure" an agent into staying in well-explored regions, preventing it from venturing into unknown but necessary parts of the state space.

Because existing heuristics don't "plan" the exploration route, they often waste an excessive amount of time revisiting states they already understand perfectly.

Planned Exploration via VIEC

To overcome these traps, the authors propose shifting from heuristic exploration to planned exploration.

  • The Demand Matrix ($D$): A matrix that tracks exactly how much more data is needed for every state-action pair $(s, a)$ to reach a desired level of confidence.
  • Augmented MDP: The problem is reformulated as an "undiscounted augmented MDP." The state is no longer just where the agent is ($s$), but also what data it still needs to collect ($D$). The goal is to minimize the total number of steps (the "exploration cost") until the demand matrix is all zeros.
  • VIEC Algorithm: Value Iteration for Exploration Cost solves the Bellman equation to find the policy that satisfies all data demands in the minimum expected number of steps, rather than maximizing immediate reward.
  • Model-Based Integration: Since the environment's transitions are initially unknown, the agent uses its current best estimate of the world to plan its exploration, updates its model with new data, and re-plans in a continuous loop.

Evaluation: The Tower MDP Stress Test

The paper introduces a specific synthetic environment called Tower MDPs to serve as an exploration stress test.

Diagram of a Tower MDP showing upward and downward states

A Tower MDP consists of a chain of "upward" states and "downward" states. To explore efficiently, an agent should go all the way to the top of the tower and then collect data from "bandits" at each level as it descends. The authors use this benchmark to mathematically prove the efficiency gap between different strategies.

Heuristic agents often get stuck "lingering" at the bottom of the tower because those states are closer. This effectively results in a redundant "back-and-forth" motion that grows quadratically with the size of the environment.

Key Results

Exploration should be treated as a shortest path problem. If you need to visit 10 cities, you plan a route (like the Traveling Salesman Problem) rather than just walking to the closest one.

The paper provides a theoretical comparison of exploration costs in Tower MDPs, proving that standard heuristics fail mathematically compared to optimal planning:

Table comparing exploration costs and weaknesses of different strategies
(Note: $n$ = states, $m$ = actions, $d$ = data demand per state-action pair.)

Standard heuristics like R-MAX or Interval Estimation (IE) result in $O(n^2)$ complexity, while optimal planning (VIEC) achieves $O(n)$. The jump from $O(n^2)$ to $O(n)$ is significant. In a world with millions of states, a quadratic exploration cost makes learning impossible, whereas a linear cost remains feasible.

Limitations and Future Work

While theoretically sound, VIEC faces practical challenges:

  • Computational Complexity: The "demand space" is massive. If you need $d$ samples for each of $nm$ state-action pairs, there are $(d+1)^{nm}$ possible demand states. This makes solving the augmented MDP exactly (via VIEC) NP-hard—essentially a version of the "Rural Postman Problem."
  • Scalability: Because of the state-space explosion, VIEC in its pure form cannot be applied directly to deep RL or environments with continuous state spaces.
  • Future Directions: The authors suggest looking for approximations to VIEC, such as using Prioritized Sweeping to focus computation on the most important parts of the demand space, or designing new heuristics that better mimic the behavior of a global planner without the full computational overhead.

Summary updated

Abstract

Efficient exploration is crucial to achieving good performance in reinforcement learning. Existing systematic exploration strategies (R-MAX, MBIE, UCRL, etc.), despite being promising theoretically, are essentially greedy strategies that follow some predefined heuristics. When the heuristics do not match the dynamics of Markov decision processes (MDPs) well, an excessive amount of time can be wasted in travelling through already-explored states, lowering the overall efficiency. We argue that explicit planning for exploration can help alleviate such a problem, and propose a Value Iteration for Exploration Cost (VIEC) algorithm which computes the optimal exploration scheme by solving an augmented MDP. We then present a detailed analysis of the exploration behaviour of some popular strategies, showing how these strategies can fail and spend O(n^2 md) or O(n^2 m + nmd) steps to collect sufficient data in some tower-shaped MDPs, while the optimal exploration scheme, which can be obtained by VIEC, only needs O(nmd), where n, m are the numbers of states and actions and d is the data demand. The analysis not only points out the weakness of existing heuristic-based strategies, but also suggests a remarkable potential in explicit planning for exploration.
BibTeX
@inproceedings{zhang2019explicit,
  author = {Liangpeng Zhang and Ke Tang and Xin Yao},
  title = {{Explicit Planning for Efficient Exploration in Reinforcement Learning}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2019},
}
Figure