Offline Reinforcement Learning: Role of State Aggregation and Trajectory Data
作者: Zeyu Jia, Alexander Rakhlin, Ayush Sekhari, Chen-Yu Wei
分类: cs.LG, cs.AI, stat.ML
发布日期: 2024-03-25
💡 一句话要点
提出离线强化学习新方法以解决样本复杂性问题
🎯 匹配领域: 支柱二：RL算法与架构 (RL & Architecture)
关键词: 离线强化学习 样本复杂性 聚合马尔可夫模型 价值函数可实现性 集中性系数 轨迹数据 策略评估
📋 核心要点
- 现有研究未能明确在有限集中性系数和轨迹数据下，离线策略评估的样本复杂性是否为多项式。
- 提出的解决方案表明，样本复杂性由聚合马尔可夫转移模型中的集中性系数决定，而非原始MDP。
- 研究结果显示，轨迹数据并未提供额外的优势，且聚合模型中的集中性系数可能随时间步长指数增长。
📝 摘要（中文）
本文重新审视了离线强化学习中的价值函数可实现性问题，但不考虑贝尔曼完备性。以往的研究未能解答在有限的集中性系数和基于轨迹的离线数据下，样本复杂性是否为多项式。我们对此问题给出了否定答案，并提供了关于仅有价值函数可实现性的离线策略评估的完整视图。主要发现包括：样本复杂性由聚合马尔可夫转移模型中的集中性系数决定，而非原始MDP；聚合模型中的集中性系数可能随时间步长呈指数增长；在价值函数可实现性下，任何具有可接受数据的困难实例都可以转化为具有轨迹数据的困难实例，表明轨迹数据并未提供额外的优势。这三项发现共同解决了开放问题，且各自具有独立的研究价值。
🔬 方法详解
问题定义：本文解决的是离线强化学习中样本复杂性的问题，尤其是在有限集中性系数和轨迹数据的情况下，现有方法未能给出清晰的答案。
核心思路：论文的核心思路是通过聚合马尔可夫转移模型来分析样本复杂性，强调集中性系数在此模型中的重要性，而非原始MDP的集中性系数。
技术框架：整体架构包括对离线策略评估的分析，首先定义聚合马尔可夫转移模型，然后研究集中性系数的影响，最后探讨轨迹数据与可接受数据的关系。
关键创新：最重要的技术创新在于明确了聚合模型中的集中性系数可能随时间步长呈指数增长，且在价值函数可实现性下，轨迹数据并未提供额外优势。
关键设计：在设计中，重点关注聚合马尔可夫转移模型的构建，集中性系数的计算方法，以及如何将可接受数据转化为轨迹数据的过程。具体的参数设置和损失函数设计在论文中进行了详细讨论。
📊 实验亮点
实验结果表明，在聚合马尔可夫转移模型下，样本复杂性显著受到集中性系数的影响，且在某些情况下，聚合模型的集中性系数随时间步长呈指数增长。这一发现与以往研究形成鲜明对比，提供了新的视角。
🎯 应用场景
该研究的潜在应用领域包括机器人控制、自动驾驶、游戏智能体等需要高效学习策略的场景。通过优化离线策略评估的样本复杂性，可以在数据稀缺的环境中提升学习效率，具有重要的实际价值和未来影响。
📄 摘要（原文）
We revisit the problem of offline reinforcement learning with value function realizability but without Bellman completeness. Previous work by Xie and Jiang (2021) and Foster et al. (2022) left open the question whether a bounded concentrability coefficient along with trajectory-based offline data admits a polynomial sample complexity. In this work, we provide a negative answer to this question for the task of offline policy evaluation. In addition to addressing this question, we provide a rather complete picture for offline policy evaluation with only value function realizability. Our primary findings are threefold: 1) The sample complexity of offline policy evaluation is governed by the concentrability coefficient in an aggregated Markov Transition Model jointly determined by the function class and the offline data distribution, rather than that in the original MDP. This unifies and generalizes the ideas of Xie and Jiang (2021) and Foster et al. (2022), 2) The concentrability coefficient in the aggregated Markov Transition Model may grow exponentially with the horizon length, even when the concentrability coefficient in the original MDP is small and the offline data is admissible (i.e., the data distribution equals the occupancy measure of some policy), 3) Under value function realizability, there is a generic reduction that can convert any hard instance with admissible data to a hard instance with trajectory data, implying that trajectory data offers no extra benefits over admissible data. These three pieces jointly resolve the open problem, though each of them could be of independent interest.