Abstract
This paper introduces Staged Sampling + Truncated Planning (SSTP), a novel algorithm for reward-free reinforcement learning (RL). SSTP achieves nearly minimax optimal sample complexity, notably reducing the dependence on the planning horizon ($H$) from polynomial to logarithmic. This breakthrough effectively matches theoretical lower bounds and addresses the "curse of horizon" that has historically limited reward-free exploration in long-horizon tasks.
Introduction
In standard Reinforcement Learning (RL), agents typically learn by optimizing a specific reward signal. However, many practical applications—such as multi-task learning or batch RL—require agents to explore an environment without a pre-defined reward. This paradigm, known as Reward-free RL, consists of two phases: an Exploration Phase to collect a comprehensive dataset, and a Planning Phase where a near-optimal policy is derived for any given reward function.
The primary challenge in this field has been the "curse of horizon." Prior state-of-the-art algorithms exhibited sample complexities scaling polynomially with the horizon length $H$ (e.g., $H^3$ or $H^6$). This paper investigates whether such high dependence is inherent or if more efficient exploration is possible.
Methodology: Staged Sampling + Truncated Planning (SSTP)
The proposed SSTP algorithm introduces three key innovations to achieve its efficiency:
- Staged Sampling: The algorithm partitions the state-action space into $K+1$ disjoint subsets based on reachability. It employs a modified Rmax algorithm to explore these tiers sequentially, ensuring efficient coverage without redundant sampling.
- Relaxed Sufficient Condition: The authors identify that a dataset is "good enough" for planning if the truncated expected visit counts are bounded. This insight allows the algorithm to be less certain about extremely hard-to-reach states that contribute minimally to the total reward.
- Soft-Truncated Planning via Auxiliary MDPs: To implement truncation efficiently, the authors construct an auxiliary MDP featuring an "absorbing state." This state captures trajectories that exceed specific tier-based visit thresholds, enabling the use of standard dynamic programming for planning without expanding the state space.
Key Results and Comparison
The core contribution of this work is the rigorous proof of SSTP's sample complexity. The algorithm requires $O\left(\frac{SA}{\epsilon^2}(S + \log \frac{1}{\delta}) \text{poly log}(\frac{SAH}{\epsilon})\right)$ episodes, which matches the minimax lower bound $\Omega(\frac{S^2A}{\epsilon^2})$ up to logarithmic factors.
As shown in the table above, SSTP represents a significant improvement over previous methods like RF-RL-EXPLORE and RF-UCRL. By reducing the horizon dependence to $\log H$, SSTP demonstrates that long-horizon tasks are not fundamentally more difficult for reward-free exploration than short-horizon ones. Furthermore, the work operates under the "Bounded Total Reward" assumption (sum of rewards $\le 1$), which is more general than the "Uniformly Bounded Reward" assumption used in earlier literature.
Discussion and Future Work
While SSTP achieves theoretical optimality in the tabular setting, several avenues for future research remain. The current analysis assumes stationary transitions, where the environment's physics do not change within an episode. Extending these logarithmic $H$ bounds to non-stationary transitions or settings requiring function approximation (e.g., Deep RL) is a critical next step. Additionally, while the sample complexity is optimal, further optimization of the computational overhead in the planning phase could enhance the algorithm's practical applicability.
Summary updated