🤖 machine learning

Improved Bounds for Reward-Agnostic and Reward-Free Exploration

This paper proposes a novel algorithm that significantly relaxes the accuracy constraints on reward-agnostic exploration in episodic MDPs and establishes a tight lower bound for reward-free exploration, thereby closing the gap between known upper and lower bounds.

Original authors: Oran Ridel, Alon Cohen

Published 2026-05-18

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Oran Ridel, Alon Cohen

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

Imagine you are a detective sent into a massive, unknown city to learn the layout of the streets. However, there's a catch: you aren't allowed to ask for directions, and you don't know what your final mission is yet.

Maybe tomorrow you need to find the fastest route to the hospital. The day after, you might need to find the most scenic park. Or perhaps you need to locate a specific bakery. You don't know which of these tasks you'll face, but you know you'll need to be ready for any of them.

This is the core problem the paper tackles: How do you explore an environment efficiently when you don't know what the "reward" (the goal) is?

The authors, Oran Ridel and Alon Cohen, propose a new way to solve this puzzle that is much more efficient than previous methods. Here is the breakdown of their work using simple analogies.

The Two Scenarios

The paper looks at two slightly different versions of this "blind exploration" problem:

Reward-Free Exploration (The "Blank Canvas" Scenario):
You explore the city completely blind. You don't know if you'll ever need to go to a hospital, a park, or a bakery. You just need to map the city so well that whatever goal is given to you later, you can instantly figure out the best path.
- The Challenge: Since the goal could be anything, you have to be incredibly thorough.
Reward-Agnostic Exploration (The "Menu" Scenario):
You still don't know the specific goal, but you do know the list of possible goals in advance. Maybe you know the only possible destinations are "Hospital," "Park," or "Bakery."
- The Advantage: Because you know the list is short, you don't need to map every single alleyway with the same intensity. You can be slightly more strategic.

The Old Way: The "Trial and Error" Approach

Previous methods (like the one by Li et al., 2024) tried to solve this by running many separate, small experiments.

The Analogy: Imagine trying to learn the city by hiring a different guide for every single street corner. You hire Guide A to learn the north side, then fire them and hire Guide B for the south side, and so on.
The Problem: This is incredibly wasteful. You keep re-learning the same basic rules of the city over and over again. It works, but it takes a massive amount of time and data, especially if you need to be very precise.

The New Way: The "Smart Tour Guide"

The authors propose a new algorithm that acts like a single, highly intelligent tour guide who learns the city in one continuous, smart journey.

1. The "Curiosity" Strategy (Step 1)
Instead of running separate experiments, the algorithm runs one long "online learning" session. It creates a series of fake, temporary goals (rewards) designed specifically to force the agent to visit the parts of the city that are hardest to reach or least understood.

The Metaphor: Imagine the guide says, "Okay, today we are going to visit the place nobody ever goes to. Tomorrow, we go to the place that is hard to find." By constantly shifting the goal to the "hardest" spots, the agent naturally builds a complete map of the city without wasting time on places it already knows well.
The Result: This creates a single "Exploration Policy" (a master plan) that gathers enough data to understand the city's dynamics (how streets connect) with far fewer trips than before.

2. The "Map Maker" (Step 2)
Once the agent has finished its exploration, it uses all the data collected to build a precise map of the city's transitions (e.g., "If I turn left at the fountain, I end up at the square").

3. The "Mission Planner" (Step 3)
Now, the real goal is revealed (e.g., "Find the bakery"). The agent looks at its high-quality map and instantly calculates the best path to the bakery. Because the map is so accurate, the path is nearly perfect.

Why This Paper Matters

The authors made two major breakthroughs:

1. They made the "Menu" scenario much more practical.
Previous methods for the "Reward-Agnostic" (Menu) scenario only worked well if you needed to be extremely precise (a very tiny error margin). If you allowed for a slightly larger margin of error, the old methods became inefficient.

The Fix: The new algorithm relaxes this requirement. It works efficiently even when you don't need to be perfect, making it useful for a much wider range of real-world situations.

2. They proved the "Blank Canvas" scenario is as hard as we thought.
For the "Reward-Free" (Blank Canvas) scenario, there was a gap between the best-known method (how fast we can do it) and the theoretical limit (how fast we must do it).

The Fix: The authors proved a new "lower bound." They showed that no matter how clever you are, you cannot do it faster than a certain limit. This closes the gap, proving that the best existing methods are actually optimal (as good as they can possibly be).

Summary

Think of this paper as upgrading the way a robot learns a new environment.

Old Robot: "I will try to learn every street by visiting it 1,000 times separately. This will take forever."
New Robot: "I will take one smart, winding tour that forces me to visit every tricky corner exactly once, building a perfect map in the process. Then, when you tell me where to go, I'll know the way instantly."

The authors have shown that this "smart tour" approach is not only faster but also mathematically proven to be the most efficient way possible for certain types of problems.

Technical Summary: Improved Bounds for Reward-Agnostic and Reward-Free Exploration

Problem Formulation

This paper addresses the challenge of exploration in episodic finite-horizon tabular Markov Decision Processes (MDPs) where the agent operates without observing external reward signals during the data collection phase. The authors study two specific frameworks:

Reward-Free Exploration (RFE): The agent explores an unknown environment without any reward signal. The goal is to produce a policy that is $\epsilon$ -optimal for any arbitrary reward function revealed after the exploration phase.
Reward-Agnostic Exploration (RAE): Similar to RFE, but the reward function is drawn from a small, predefined finite class (size polynomial in $|S|, |A|, H$ ). The goal is to find an $\epsilon$ -optimal policy for the specific reward drawn from this class.

The core difficulty lies in gathering sufficient data to accurately estimate state-action transition dynamics without the guidance of a reward signal, ensuring that the resulting model supports the computation of near-optimal policies for downstream tasks.

Methodology

The proposed approach replaces the reliance on multiple independent no-regret subroutines found in prior work with a unified online learning procedure. The algorithm (Algorithm 1) operates in three stages:

1. Exploration Policy Creation

Instead of running multiple stochastic no-regret algorithms (as done by Jin et al., 2020b; Li et al., 2024b), the authors employ a single run of an Online Mirror Descent (OMD) algorithm over a sequence of carefully constructed auxiliary reward functions.

Mechanism: The algorithm generates a sequence of rewards $\{\lambda_t\}$ designed to steer the agent toward less-visited state-action pairs. The reward at step $t$ is inversely proportional to the visitation count of the state-action pair (plus a constant $c$ to handle low-probability visits).
Optimization Perspective: This process is framed as approximately solving a convex optimization problem over the space of valid occupancy measures. Specifically, it aims to minimize the negative log-barrier objective $f(\mu) = -\sum \log \mu_h(s,a)$ .
Significance: By using a single online MDP algorithm (adapted from Rosenberg & Mansour, 2019) rather than Frank-Wolfe style iterations, the method significantly reduces the low-order sample complexity terms. It reuses samples throughout the learning process to construct a "policy cover" that ensures near-uniform exploration of significant state-action triples.

2. Dynamics Estimation

Using the exploration policy generated in Step 1, the agent collects $N$ trajectories. To handle the temporal correlations inherent in trajectory data, the authors utilize a two-fold subsampling framework (Li et al., 2024a). This technique splits the dataset into a main set and an auxiliary set to induce statistical independence, allowing for the construction of an empirical transition kernel $\hat{P}$ with rigorous concentration guarantees.

3. Policy Estimation

Once the true reward function is revealed, the algorithm computes an $\epsilon$ -optimal policy using pessimism in the face of uncertainty.

The algorithm constructs an empirical MDP using $\hat{P}$ and the revealed reward.
It applies a penalty term $b_h(s,a)$ derived from Bernstein-style concentration inequalities to the Q-value estimates. This penalty scales with the empirical variance and visit counts, discouraging the policy from visiting poorly covered state-action pairs.
The final policy $\hat{\pi}$ is the optimal policy for this pessimistic empirical MDP.

Key Contributions and Results

1. Improved Sample Complexity for Reward-Agnostic Exploration (RAE)

The paper presents a new algorithm that achieves the optimal high-order sample complexity for RAE, matching the lower bound for Best Policy Identification (BPI).

Result: The sample complexity is $O\left(\frac{|S||A|H^3 \ell_0^3}{\epsilon^2} + \frac{|S|^2|A|H^4 \ell_0^3}{\epsilon}\right)$ .
Improvement: While previous work (Li et al., 2024b) achieved the optimal high-order term $O(|S||A|H^3/\epsilon^2)$ , their bound suffered from a high-complexity low-order term that rendered the bound optimal only for extremely small $\epsilon$ . The proposed method significantly reduces this low-order term, making the algorithm applicable to a wider range of accuracy parameters.

2. Tight Lower Bound for Reward-Free Exploration (RFE)

The authors prove a tight lower bound for the sample complexity of RFE in time-inhomogeneous MDPs.

Result: Any RFE algorithm requires $\Omega\left(\frac{|S|^2|A|H^3}{\epsilon^2}\right)$ trajectories in expectation.
Significance: This resolves a conjecture by Li et al. (2024b) that the minimax lower bound for time-inhomogeneous RFE is a factor of $H$ larger than the time-homogeneous case. This establishes that existing upper bounds (e.g., M´enard et al., 2021) are optimal up to logarithmic factors.

3. Theoretical Framework

The paper provides a novel technical perspective by linking the exploration policy creation to the minimization of a log-barrier objective over occupancy measures. It demonstrates that an online mirror descent approach can approximate this solution more efficiently than previous Frank-Wolfe-based methods, thereby reducing the dependency on problem dimensions in the lower-order terms.

Significance and Claims

The paper claims to advance the theoretical understanding of exploration without rewards by:

Disentangling Exploration and Exploitation: It clarifies the intrinsic sample complexity of exploration in finite-horizon MDPs.
Practicality of RAE: By relaxing the restrictive requirements on the accuracy parameter $\epsilon$ found in prior optimal bounds, the proposed method makes reward-agnostic exploration practical even in moderate-accuracy regimes.
Completeness of Characterization: The combination of the new upper bound for RAE and the tight lower bound for RFE provides a complete minimax characterization of the sample complexity for these problems (up to logarithmic factors).

The authors explicitly state that their focus is on the theoretical analysis of finite-horizon tabular MDPs, leaving non-tabular MDPs and empirical results as avenues for future work. They do not claim immediate application to specific real-world domains like robotics or medicine, but rather emphasize the foundational theoretical improvements that enable such applications.