🤖 AI

Auto-exploration for online reinforcement learning

This paper introduces a parameter-free auto-exploration framework for online reinforcement learning that achieves algorithm-independent $O(\epsilon^{-2})$ sample complexity in both tabular and linear function approximation settings by integrating exploration into policy mirror descent.

Original authors: Caleb Ju, Guanghui Lan

Published 2026-06-25

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Caleb Ju, Guanghui Lan

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Core Problem: The "Lost Tourist" Dilemma

Imagine you are a tourist dropped into a massive, unfamiliar city (the Environment) with no map. Your goal is to find the best restaurant in town (the Optimal Policy) by walking around and trying different places.

In Reinforcement Learning (RL), this is called the Exploration-Exploitation Dilemma:

Exploitation: You keep going to the restaurant you already know is good.
Exploration: You wander into new neighborhoods to see if there’s something even better.

The problem is that if you only exploit, you might miss the best restaurant because you never visited that part of the city. If you explore too much, you waste time eating bad food.

Most existing algorithms assume you have a "magic compass" that tells you exactly how long to wander in each neighborhood before moving on. This compass relies on knowing the city’s layout (the Mixing Time and Stationary Distribution) beforehand. But in real life, you don’t have that map. You’re just guessing. If you guess wrong, you either get stuck in a dead-end alley or wander aimlessly for years.

The Solution: "Auto-Exploration"

The authors propose a new method called Auto-Exploration. Instead of needing a pre-calculated map or a fixed schedule for how long to explore, the algorithm learns how to explore on the fly. It automatically figures out when it has seen enough of a specific area and when it needs to keep looking.

Think of it like this: Instead of a tourist with a rigid itinerary ("Walk for 10 minutes, then turn left"), this tourist has a smart watch. The watch tracks how long it takes to stumble upon a new landmark. If it takes a long time to find a new street, the watch knows, "Okay, this area is hard to navigate, I need to keep looking." If it finds things quickly, it knows, "I’ve seen enough here, let’s move on."

How It Works: Two Main Techniques

The paper presents this solution in two settings: one where the city is small and fully mapped (Tabular), and one where the city is huge and you only have rough sketches (Function Approximation).

1. The Small City (Tabular Setting)

In a small city with a finite number of streets, the authors use a technique called Dynamic Exploration Time.

The Old Way: Previous methods required you to know the "mixing time"—essentially, how long it takes for a random walker to visit every part of the city evenly. This number is unknown and can be huge.
The New Way: The algorithm uses a Hitting Time. It simply counts how many steps it takes to hit a specific state (street corner) for the first time.
The Analogy: Imagine you are trying to find a specific rare flower in a garden. Instead of guessing "I’ll search for 5 hours," you say, "I will keep searching until I find the flower, plus a little extra buffer time." The algorithm calculates this "buffer time" based on how hard the flower was to find. This makes the method parameter-free—you don’t need to tune knobs based on unknown city data.

2. The Huge City (Function Approximation)

In a massive city, you can’t memorize every street. You use a simplified map (a neural network or linear model) to generalize.

The Challenge: When using a simplified map, errors can creep in. If you only explore based on your current best guess, you might get stuck in a "local optimum" (a good restaurant, but not the best one) because your map is slightly wrong.
The New Way: The authors introduce a Conditional Temporal Difference (CTD) method. They create a special sampling strategy that ensures the algorithm visits states in a way that covers the whole city, even if the map is imperfect.
The Analogy: Imagine you are using a blurry map. To ensure you don’t miss the best spot, you occasionally force yourself to walk to a specific "anchor point" (like the city center) and then explore outward from there. This "anchor" ensures you don’t get lost in a blind spot of your blurry map. The algorithm automatically adjusts how often it returns to this anchor based on how uncertain it is.

Why Is This Better?

No "Magic Numbers" Needed: Previous methods required you to input parameters like "mixing rate" or "stationary distribution," which are unknown in real-world problems. If you guessed these wrong, the algorithm failed. This new method is parameter-free. It figures out the necessary exploration time automatically based on the data it collects.
Faster and More Efficient: The paper proves that this method achieves a high level of accuracy ( $\epsilon$ -accuracy) with a sample complexity of $O(\epsilon^{-2})$ . In plain English, this means it learns the optimal policy much faster than previous methods, which often required $O(\epsilon^{-4})$ samples (four times more data for the same accuracy).
Works Without a Perfect Map: It handles the "online" setting, where you can only learn from a single continuous stream of experience (like a single walk through the city), rather than having a simulator that lets you reset and start over from any point.

The Key Insight: Implicit Exploration

The paper highlights a concept called Implicit Exploration. It turns out that if the optimal policy (the best way to navigate the city) naturally visits all parts of the city, then the learning algorithm doesn’t need to force exploration artificially. It can rely on the fact that following the best path will naturally lead it to explore. The authors prove that under reasonable assumptions, the algorithm can achieve this efficient learning without needing to explicitly "force" random actions, saving time and resources.

Summary

This paper introduces a smarter way for AI agents to learn from experience. Instead of relying on pre-calculated maps or fixed schedules for exploration, the agent uses auto-exploration: it dynamically adjusts its search effort based on how hard it is to find new information. This makes the learning process faster, more efficient, and easier to implement because it doesn’t require knowing the hidden details of the environment beforehand. It’s like giving the tourist a smart watch that tells them exactly when to stop wandering and when to keep looking, ensuring they find the best restaurant without getting lost.

Technical Summary: Auto-exploration for online reinforcement learning

Problem Statement
The paper addresses the exploration-exploitation dilemma in online reinforcement learning (RL) for infinite-horizon discounted Markov decision processes (MDPs) with finite state and action spaces. In the online setting, data is generated via a single trajectory (Markovian noise), making it challenging to ensure sufficient coverage of the state-action space. Existing algorithms typically rely on assumptions of "sufficient exploration," often requiring knowledge of problem-dependent parameters such as the mixing time and stationary distribution of the Markov chains induced by intermediate policies. These parameters are generally unknown and algorithm-dependent, leading to non-implementable algorithms or sub-optimal sample complexity bounds (e.g., $O(\epsilon^{-4})$ for explicit exploration, or bounds dependent on arbitrarily large exploration constants $D_{expl}$ ). The authors identify a gap in achieving algorithm-independent $O(\epsilon^{-2})$ sample complexity for both tabular and linear function approximation settings in the online, on-policy regime.

Methodology
The authors introduce a class of methods termed "auto-exploration," integrated into Stochastic Policy Mirror Descent (SPMD). The core technical contributions are divided into two settings:

Tabular Setting:
- Dynamic Exploration Time: To avoid dependence on unknown mixing times, the authors propose a data-driven, dynamic exploration time $\tilde{m}_\pi(\pi, \varsigma)$ . This time is defined based on the hitting times of state-action pairs, specifically $\tilde{m}_\pi(\pi, \varsigma) := \max_{z \in Z_\pi(\pi)} \tau^\pi_\infty(z) + \lceil \log_\gamma((1-\gamma)\varsigma) \rceil$ , where $\tau^\pi_\infty(z)$ is the first hitting time of state-action pair $z$ .
- Implicit Exploration: The method relies on Assumption 3.2, which posits the existence of a deterministic optimal policy $\pi^*$ that induces an irreducible Markov chain with a unique stationary distribution bounded away from zero. The authors prove that if the current policy $\pi$ assigns non-zero probability to the optimal actions (implicit action exploration), it implicitly ensures sufficient state exploration. This allows the derivation of algorithm-independent bounds on the mixing properties of intermediate policies.
- Bregman Divergence: A specific Bregman divergence based on negative Tsallis entropy is used, with the entropic index $p$ adapted to the discount factor $\gamma$ to tighten convergence bounds.
Linear Function Approximation Setting:
- New Sampling Distribution: Instead of sampling from the unknown stationary distribution $\nu_\pi$ , the authors propose sampling from a distribution $w(z)$ based on the discounted visitation distribution $\kappa^\pi_{sor}(s)$ from a fixed origin state $sor$, combined with an $\epsilon$ -greedy action policy. This distribution is always well-defined and does not require estimating the mixing rate.
- Conditional Temporal Differencing (CTD): The authors develop a stochastic operator $\hat{F}(\theta)$ for solving the projected Bellman equations. The construction involves a random geometric truncation time and a dynamic exploration phase that samples until the origin state $sor$ is hit, followed by sampling under the current policy. This facilitates off-policy sampling when necessary to hedge against unknown function approximation bias.

Key Contributions

Algorithm-Independent Sample Complexity: The paper establishes the first algorithm-independent, on-policy $O(\epsilon^{-2})$ sample complexity for tabular RL under weaker exploration assumptions. The bound depends on $D_{expl}(\delta)$ , which has polylogarithmic dependence on $1/\delta$ and polynomial dependence on problem-specific parameters (like the mixing rate of the optimal policy), but no dependence on $\epsilon$ or algorithm-dependent terms.
Parameter-Free Implementation: The proposed methods are parameter-free, requiring no prior knowledge of mixing rates or stationary distributions. The dynamic exploration time is easily accessible in practice via real-time observation of hitting times.
High-Probability Last-Iterate Convergence: The authors derive new high-probability last-iterate convergence guarantees for SPMD. This improves upon prior average-iterate or expected last-iterate results. The sample complexity is improved by a factor of $O((1-\gamma)^{-2})$ compared to prior work requiring small bias and variance, and by $O(|A|^{1/2}/(1-\gamma))$ compared to implicit exploration results limited to average-iterate convergence.
Generalized Markov Chain Coverage: In the function approximation setting, the use of the discounted visitation distribution allows the method to cover a more general class of Markov chains than those requiring a stationary distribution.

Results

Theorem 3.5 (Tabular): Under Assumption 3.2, SPMD with auto-exploration achieves $\epsilon$ -accuracy with probability $1-\delta$ using $\tilde{O}(D_{expl}(\delta) \cdot |A|^{2-p} (1-\gamma)^{-5} \epsilon^{-2})$ samples. The term $D_{expl}(\delta)$ is algorithm-independent.
Function Approximation: The paper establishes similar sample complexity bounds for auto-exploratory SPMD with linear function approximation. It reveals a trade-off: implicit exploration suffices if function approximation error is known; explicit exploration is required if the error is unknown to hedge against bias.
Convergence Rates: The analysis provides high-probability bounds on the optimality gap $V^{\pi_k}(s) - V^{\pi^*}(s)$ , showing sublinear convergence rates dependent on the number of iterations $k$ .

Significance
The authors claim this work resolves the limitation of existing online RL algorithms that rely on unknown, algorithm-dependent parameters for exploration. By introducing auto-exploration, the methods are simple to implement (parameter-free) and achieve optimal $O(\epsilon^{-2})$ sample complexity without requiring explicit exploration schedules or knowledge of the environment's mixing properties. The results bridge the gap between theoretical guarantees and practical implementation in the challenging online, on-policy setting.