Technical Summary: Reward-free Pretraining for Reinforcement Learning via Occupancy Coverage Maximization

Problem Statement

Sparse rewards present a fundamental challenge in Reinforcement Learning (RL), where agents receive no informative feedback until reaching a specific goal. While intrinsic-reward methods (e.g., novelty, prediction error, skill diversity) attempt to inject supervision signals, they often rely on the ability to evaluate extrinsic rewards either online or via offline relabeling of stored transitions. This assumption fails in multi-task, meta-, and continual RL settings where interactions are strictly reward-free, and the downstream reward function is unavailable until the agent actually reaches a task-dependent goal.

Existing reward-free objectives often suffer from non-stationarity. Methods optimizing for state marginal matching, prediction error, or skill diversity may discover diverse states during pretraining but fail to maintain a policy whose discounted state occupancy is broadly distributed. Instead, the final policy often concentrates on small regions or exhibits oscillatory "expansion-collapse" behavior, failing to provide a robust initialization for downstream sparse-reward tasks.

Methodology: ROVER

The authors propose ROVER (Reward-free pretraining via Occupancy coVERage maximization), an algorithm designed to pre-train transferable exploration policies that maximize state-space coverage without requiring a target distribution or offline reward evaluation.

1. Objective: Occupancy Coverage Maximization

ROVER formulates the pretraining objective as minimizing the self-similarity of the discounted state occupancy measure $d^\pi$ within a Reproducing Kernel Hilbert Space (RKHS).

• Formulation: The objective is defined as $J(\pi) = \|\mu_{d^\pi}\|_H^2$, where $\mu_{d^\pi}$ is the kernel mean embedding of the occupancy measure.
• Theoretical Equivalence:
  • Minimizing this norm is equivalent to maximizing the metric Rényi entropy of order 2.
  • In the tabular setting with a Dirac kernel, it is equivalent to minimizing the Maximum Mean Discrepancy (MMD) distance to a uniform distribution, effectively promoting uniform coverage without explicitly defining a uniform target.
  • In learned representation spaces, it promotes diversity in the geometry induced by the representation.

2. Algorithmic Implementation

ROVER leverages the operatorial formulation of RL to make the objective computable and differentiable in closed form. The algorithm alternates between data collection and three steps:

• Representation Learning: A feature map $\phi_\theta$ is learned from transition data using a contrastive InfoNCE loss to align predicted next-state representations with actual next states. This defines the geometry for the coverage objective.
• World Model Estimation (Transition Operator): The algorithm estimates a lifted transition operator $\hat{T}_n$ using Kernel Ridge Regression (KRR) on the learned representations. This operator maps state-action features to next-state embeddings in closed form.
• Policy Mirror Descent (PMD): The policy is updated to minimize the objective $J(\pi)$ using Policy Mirror Descent. The gradient of the objective is derived in closed form using the resolvent of the transition operator, allowing for efficient updates without sampling-based gradient estimation.

3. Sink-State Augmentation

A critical component of ROVER is the introduction of a virtual "sink" state ($s_{S_\epsilon}$) to handle regions of the state space unsupported by the current data.

• Mechanism: The state space is augmented with an absorbing sink state. The transition operator is estimated using a shifted ridge problem that routes unexplained residuals (predictions for unseen state-action pairs) to this sink state rather than to a zero vector.
• Stabilization: This prevents the "expansion-collapse" behavior where a policy oscillates between discovering new regions and forgetting previously covered ones. The sink state imposes a cost on assigning occupancy to unsupported regions, balancing exploration with the retention of known coverage.
• Objective Decomposition: The total objective decomposes into the norm of the occupancy in the original space plus a penalty term proportional to the mass assigned to the sink state, controlled by a hyperparameter $\epsilon$.

Key Contributions

1. Target-Free Formulation: The paper formalizes occupancy coverage as a target-free RKHS objective for sparse-reward policy transfer, linking it to MMD matching, Rényi-2 diversity, and potential-theoretic energy minimization.
2. Operator-Based Policy Update: The authors derive a closed-form, operator-based policy update for minimizing this objective using a learned resolvent world model, avoiding the non-stationarity issues of proxy-based methods.
3. Sink-State Augmentation: The introduction of a virtual sink state stabilizes coverage under partial data, preventing cyclic expansion-collapse behavior and ensuring the policy retains coverage of previously visited regions.

Experimental Results

The authors evaluate ROVER in controlled, fully observable, sparse-navigation environments (tabular and pixel-based) designed to isolate topological bottlenecks (e.g., Middle-Room, Multi-Rooms, Maze).

• Coverage Efficiency: ROVER achieves full state-space coverage significantly faster than baselines (RND, SMM, APT, MAXENT, CIC) when trained from scratch.
• Stability and Transfer: Unlike baselines that may discover states transiently but collapse to localized occupancy, ROVER produces policies with broadly distributed discounted occupancy. This results in stronger initializations for downstream model-free RL (DDPG, SAC), requiring fewer samples to reach goals.
• Offline Transfer: In offline RL settings (CQL, DDPG), replay buffers generated by ROVER support downstream learning effectively. While the distribution differs from other methods (e.g., CIC produces more homogeneous data, while ROVER retains higher density near start states and bottlenecks), ROVER's data structure is particularly effective for conservative algorithms like CQL.
• Robustness: The method demonstrates robustness to hyperparameters, though extreme values for the sink-state norm $\epsilon$ can hinder exploration.

Significance and Claims

The paper positions ROVER as a principled step toward establishing occupancy coverage as a standard objective for reward-free behavioral transfer.

• Modest Scope: The authors explicitly state that the study is limited to discrete action spaces and simple environments to isolate the coverage objective and analyze its behavior directly, rather than presenting ROVER as a fully scalable exploration algorithm for high-dimensional domains immediately.
• Core Insight: The primary contribution is the demonstration that maximizing occupancy coverage via a stable, closed-form operator approach yields policies that are inherently better suited for downstream sparse-reward transfer than those optimized for transient novelty or skill diversity.
• Future Directions: The authors identify future work in developing scalable representations for high-dimensional domains, approximate implementations of the resolvent objective, and extensions to continuous actions and partial observability.