提出新算法，让智能体在无奖励环境下更高效探索，适应更高精度需求。
Improved Bounds for Reward-Agnostic and Reward-Free Exploration
- 用在线学习设计奖励，构建探索策略以收集足够数据
- 首次实现对更大精度要求ε的奖励无关探索，样本复杂度更优
- 给出奖励自由探索的紧致下界，理论闭环
我们研究了在周期性有限时域马尔可夫决策过程（MDPs）中的奖励自由与奖励无关探索问题，即智能体在不接收外部奖励的情况下探索未知环境。奖励自由探索的目标是为任何后续揭示的奖励生成ε-最优策略；而奖励无关探索则针对从一个小型有限类中抽取的奖励实现ε-最优性。已有工作在奖励无关设置下达到极小极大样本复杂度，但仅适用于极为严格的精度参数ε。本文提出一种新算法，显著放宽了对ε的要求。该方法采用精心设计的在线学习过程，生成探索奖励以构造探索策略，进而收集充足数据用于准确的动力学估计，并在奖励揭示后计算ε-最优策略。最后，我们为奖励自由探索建立了紧致下界，填补了已知上下界之间的差距。
原文摘要 · Abstract (English)
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 $ε$-optimal policies for any reward revealed after exploration, while reward-agnostic exploration targets $ε$-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 $ε$. We propose a new algorithm that significantly relaxes the requirement on $ε$. 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 $ε$-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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。