Instance-Dependent Near-Optimal Policy Identification in Linear MDPs via Online Experiment Design
Instance-Dependent Near-Optimal Policy Identification in Linear MDPs via Online Experiment Design
复制标题
DOI：
10.48550/arxiv.2207.02575
复制
发表时间：
2022-07
期刊：
影响因子：
--
通讯作者：
Andrew J. Wagenmaker;Kevin G. Jamieson
中科院分区：
文献类型：
--
作者：
Andrew J. Wagenmaker;Kevin G. Jamieson
虽然在理解强化学习(RL)的极小最大样本复杂性——“最坏情况”实例上学习的复杂性——方面已经取得了很大进展，但这种复杂性度量通常不能捕捉学习的真正难度。实际上，在“简单”的情况下，我们可能希望实现比最坏情况情况下可实现的复杂性好得多的复杂性。在这项工作中，我们试图理解在线性函数逼近的 RL 设置中学习近最优策略 (PAC RL) 的“实例相关”复杂性。我们提出了一种算法 \textsc{Pedel}，它实现了细粒度的依赖于实例的复杂性测量，这是 RL 中第一个具有函数逼近设置的算法，从而捕获了每个特定问题实例的学习难度。通过一个明确的例子，我们表明 \textsc{Pedel} 比低遗憾、极小极大最优算法产生了可证明的收益，并且此类算法无法达到实例最优率。我们的方法依赖于一种新颖的基于在线实验设计的程序，该程序将探索预算集中在与学习接近最优策略最相关的“方向”上，并且可能具有独立的兴趣。
While much progress has been made in understanding the minimax sample complexity of reinforcement learning (RL) -- the complexity of learning on the"worst-case"instance -- such measures of complexity often do not capture the true difficulty of learning. In practice, on an"easy"instance, we might hope to achieve a complexity far better than that achievable on the worst-case instance. In this work we seek to understand the"instance-dependent"complexity of learning near-optimal policies (PAC RL) in the setting of RL with linear function approximation. We propose an algorithm, \textsc{Pedel}, which achieves a fine-grained instance-dependent measure of complexity, the first of its kind in the RL with function approximation setting, thereby capturing the difficulty of learning on each particular problem instance. Through an explicit example, we show that \textsc{Pedel} yields provable gains over low-regret, minimax-optimal algorithms and that such algorithms are unable to hit the instance-optimal rate. Our approach relies on a novel online experiment design-based procedure which focuses the exploration budget on the"directions"most relevant to learning a near-optimal policy, and may be of independent interest.