提出首个高效可复现强化学习算法，仅需约S²A样本即可学习最优策略。
From Generative to Episodic: Sample-Efficient Replicable Reinforcement Learning
- 设计新算法，通过近似生成模型实现低样本可复现探索
- 理论证明只需 Õ(S²A) 样本，比之前方法减少数个数量级
- 适用于状态空间较小的实时控制场景，如机器人决策
强化学习中的可复现性问题近年来受到广泛关注。在固定独立同分布数据源的批量设置中，数据高效的可复现学习已基本解决。然而在需与动态环境交互的控制场景中仍存在显著知识空白。已有研究表明，在拥有生成模型（$S$状态、$A$动作）的批量设置下，学习近优策略仅需 Õ($S^2A^2$) 样本；而在无生成模型的情况下，最坏情况需 Õ($S^7A^7$) 样本。本文针对低时域表格型马尔可夫决策过程（tabular MDPs），提出一种可复现强化学习算法，仅需 Õ($S^2A$) 样本，几乎弥合了生成模型与单次探索（episodic）设置间的差距。我们进一步证明，在并行采样假设下，生成模型设置下的下界为 Õ($S^2A$)，而无条件的单次探索下界为 Õ($S^2$)，表明该算法对状态空间 $S$ 接近最优。
原文摘要 · Abstract (English)
The epidemic failure of replicability across empirical science and machine learning has recently motivated the formal study of replicable learning algorithms [Impagliazzo et al. (2022)]. In batch settings where data comes from a fixed i.i.d. source (e.g., hypothesis testing, supervised learning), the design of data-efficient replicable algorithms is now more or less understood. In contrast, there remain significant gaps in our knowledge for control settings like reinforcement learning where an agent must interact directly with a shifting environment. Karbasi et. al show that with access to a generative model of an environment with $S$ states and $A$ actions (the RL 'batch setting'), replicably learning a near-optimal policy costs only $\tilde{O}(S^2A^2)$ samples. On the other hand, the best upper bound without a generative model jumps to $\tilde{O}(S^7 A^7)$ [Eaton et al. (2024)] due to the substantial difficulty of environment exploration. This gap raises a key question in the broader theory of replicability: Is replicable exploration inherently more expensive than batch learning? Is sample-efficient replicable RL even possible? In this work, we (nearly) resolve this problem (for low-horizon tabular MDPs): exploration is not a significant barrier to replicable learning! Our main result is a replicable RL algorithm on $\tilde{O}(S^2A)$ samples, bridging the gap between the generative and episodic settings. We complement this with a matching $\tildeΩ(S^2A)$ lower bound in the generative setting (under the common parallel sampling assumption) and an unconditional lower bound in the episodic setting of $\tildeΩ(S^2)$ showcasing the near-optimality of our algorithm with respect to the state space $S$.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。