When Simple Exploration is Sample Efficient: Identifying Sufficient Conditions for Random Exploration to Yield PAC RL Algorithms

Yao Liu, Emma BrunskillarXiv 2018 · arXiv

Introduction

In Reinforcement Learning (RL), the "exploration-exploitation" trade-off is a fundamental challenge. Formal proofs for sample efficiency (PAC-RL) typically rely on sophisticated algorithms that explicitly track uncertainty or visit counts. However, in practice, many state-of-the-art deep RL agents rely on simple $\epsilon$-greedy exploration—taking a random action with probability $\epsilon$. Despite its lack of strong general theoretical guarantees, $\epsilon$-greedy often performs remarkably well. This paper addresses the central question: When is exploration "easy"? Specifically, the authors identify conditions under which a simple random walk followed by greedy exploitation is sufficient to learn a near-optimal policy in polynomial time.

Theoretical Framework: Covering Length and Connectivity

The authors' analysis centers on the covering length ($L$), defined as the number of steps required for a random walk to visit all state-action pairs with high probability. To bound $L$, they employ two key mathematical tools:

  1. Stationary Distribution ($\phi$): This represents the long-term probability of the agent being in a specific state under a random walk. A "well-behaved" distribution (where no state has an exponentially small probability) is crucial for efficiency.
  2. Graph Laplacian Eigenvalues ($\lambda$): Specifically, the smallest non-zero eigenvalue of the MDP's transition graph. This value measures the connectivity of the environment; a high $\lambda$ indicates a well-connected graph without severe bottlenecks.

By linking these properties to the convergence of Q-learning, the authors prove that if an MDP has a balanced stationary distribution and high connectivity, random exploration is provably efficient.

Structural Properties for Efficient Exploration

Symmetry as a Shortcut

A major insight of the paper is the role of locally symmetric actions. In environments where actions can be "undone" or where movement between states exhibits symmetry, a random walk behaves similarly to a walk on an undirected graph. In such cases, the covering length is guaranteed to be polynomial relative to the number of states and actions, making simple exploration highly effective.

The Bottleneck Problem

Conversely, the presence of bottlenecks can cause random exploration to fail. The authors use the "Cheeger constant" (related to the Laplacian eigenvalue $\lambda$) to measure these bottlenecks. If an MDP contains a narrow "bridge" or a "trapdoor" structure, a random walk may remain trapped in one region for an exponential amount of time.

Figure 1: A grid world environment with a narrow opening, illustrating a structural bottleneck that can significantly increase the time required for a random walk to explore the entire state space.

Empirical Validation across Environments

The paper evaluates its theoretical findings against several classic RL benchmarks and complex tasks to see if the theoretical bounds match empirical observations:

  • Grid World & Taxi: These standard navigation tasks demonstrate "locally symmetric" properties where random walks are efficient.
  • Chain MDP: This "trapdoor" environment serves as a counterexample where random exploration requires exponential time despite having a small diameter.
  • Pong vs. Montezuma’s Revenge: In Atari games, Pong is considered "easy" because its state space is approximately symmetric and restarts distribute the agent fairly. In contrast, Montezuma’s Revenge is "hard" because falling into a pit acts as a trapdoor, creating an exponentially small stationary distribution for deeper states.
Figure 3: Comparison of different MDP structures: (a) the Chain MDP where random walks fail, (b) a standard Grid World, and (c) the Taxi environment.

Key Results and Theorem 3

The paper's core contribution is Theorem 3, which provides a formal upper bound on covering length based on $1/\phi_{min}$ and $1/\lambda$. If these values are polynomial relative to the number of states and actions, the resulting algorithm is PAC-RL. The authors also formally prove that symmetry ensures efficiency and demonstrate that a small "diameter" (shortest path length) is insufficient on its own to guarantee efficient random exploration, as evidenced by the Chain MDP.

Limitations and Future Directions

While providing a strong theoretical bridge, the work has limitations. The analysis focuses on a fixed "explore then exploit" schedule rather than the decaying $\epsilon$ schedules common in deep RL. Furthermore, applying these structural proofs to high-dimensional pixel inputs requires state abstraction assumptions. Future work may extend these findings to "reducible" MDPs with dead ends and more complex state representations.

Summary updated

Abstract

Efficient exploration is one of the key challenges for reinforcement learning (RL) algorithms. Most traditional sample efficiency bounds require strategic exploration. Recently many deep RL algorithms with simple heuristic exploration strategies that have few formal guarantees, achieve surprising success in many domains. These results pose an important question about understanding these exploration strategies such as $e$-greedy, as well as understanding what characterize the difficulty of exploration in MDPs. In this work we propose problem specific sample complexity bounds of $Q$ learning with random walk exploration that rely on several structural properties. We also link our theoretical results to some empirical benchmark domains, to illustrate if our bound gives polynomial sample complexity in these domains and how that is related with the empirical performance.
BibTeX
@misc{liu2018when,
  author = {Yao Liu and Emma Brunskill},
  title = {{When Simple Exploration is Sample Efficient: Identifying Sufficient Conditions for Random Exploration to Yield PAC RL Algorithms}},
  year = {2018},
  eprint = {1805.09045},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1805.09045},
}
Figure