Improved Bounds for Reward-Agnostic and Reward-Free Exploration

We study *reward-free* and *reward-agnostic* exploration in episodic finite-horizon Markov decision processes (MDPs), where an agent explores an unknown environment without observing external rewards. Reward-free exploration aims to enable $\epsilon$-optimal policies for *any* reward revealed after exploration, while reward-agnostic exploration targets $\epsilon$-optimality for rewards drawn from a small finite class. In the *reward-agnostic setting*, Li, Yan, Chen, and Fan (2024) achieve minimax sample complexity, but only for restrictively small accuracy parameter $\epsilon$. We propose a new algorithm that significantly relaxes the requirement on $\epsilon$. Our approach is novel and of technical interest by itself. Our algorithm employs an online learning procedure with carefully designed rewards to construct an exploration policy, which is used to gather data sufficient for accurate dynamics estimation and subsequent computation of an $\epsilon$-optimal policy once the reward is revealed. Finally, we establish a tight lower bound for *reward-free exploration*, closing the gap between known upper and lower bounds.

In standard reinforcement learning, an agent learns by trying to maximize a stream of rewards. But in many practical applications, like scientific experiments or robotics, it is hard to define, or impossible to know, what the reward should be while the agent is first collecting data. This paper looks at how an agent can effectively explore an unknown environment completely blind to what its ultimate goal will be. We want the agent to learn how the environment operates to the point that once a goal is introduced, it can choose the best actions without further exploration of the environment. While older methods needed restrictively small margins of error to work optimally , we introduce a new approach that uses a sequence of carefully designed internal rewards to guide the agent. This significantly reduces the amount of data required to learn. Additionally, we provide a lower bound to the problem, that is closing the gap between theoretical and achievable performance for that setting.