Abstract: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 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.
| Subjects: | Machine Learning (cs.LG) |
| Cite as: | arXiv:2602.16363 [cs.LG] |
| (or arXiv:2602.16363v2 [cs.LG] for this version) | |
| https://doi.org/10.48550/arXiv.2602.16363 arXiv-issued DOI via DataCite |
From: Oran Ridel [view email]
[v1]
Wed, 18 Feb 2026 11:04:15 UTC (184 KB)
[v2]
Fri, 15 May 2026 06:33:38 UTC (331 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。