Sample-Efficiency in Multi-Batch Reinforcement Learning: The Need for Dimension-Dependent Adaptivity

📄 arXiv: 2310.01616v2 📥 PDF

作者: Emmeran Johnson, Ciara Pike-Burke, Patrick Rebeschini

分类: cs.LG, cs.AI

发布日期: 2023-10-02 (更新: 2024-05-28)

备注: Accepted at ICLR 2024

💡 一句话要点

提出维度依赖适应性以提升多批次强化学习的样本效率

🎯 匹配领域: 支柱二：RL算法与架构 (RL & Architecture)

关键词: 强化学习 样本效率 适应性 多批次学习 线性函数逼近 策略评估 最佳策略识别

📋 核心要点

  1. 现有强化学习方法在样本效率和适应性之间的关系尚不明确，导致在高维问题中性能不佳。
  2. 论文提出了一种新的学习框架，允许在多个批次中发送查询，并在每个批次后处理反馈以更新查询策略。
  3. 研究结果表明，适应性并不总是能保证样本效率，且样本效率的边界依赖于适应性状态和问题维度。

📝 摘要（中文）

本文理论探讨了强化学习中样本效率与适应性之间的关系。样本效率指算法在环境中查询次数与问题维度之间的多项式关系，而适应性则涉及查询频率及反馈处理的更新策略。我们采用一种允许在K个批次中发送查询的学习框架，涵盖从非适应性到完全适应性的整个适应性谱系。针对$d$维线性函数逼近下的策略评估和最佳策略识别问题，我们建立了样本效率算法所需的批次数$K$的下界为$Ω( ext{log log } d)$，并指出仅有适应性并不一定保证样本效率。适应性与样本效率的边界并不在于离线强化学习与适应性设置之间，而是依赖于不同适应性状态和问题维度。

🔬 方法详解

问题定义：本文解决了在强化学习中样本效率与适应性之间的关系，现有方法未能明确适应性对样本效率的影响，尤其是在高维问题中。

核心思路：论文的核心思路是通过引入多批次查询的框架，研究适应性如何影响样本效率，强调适应性与样本效率之间的复杂关系。

技术框架：整体架构包括多个阶段：首先在每个批次中发送查询，接着处理反馈并更新查询策略，最后评估样本效率与适应性之间的关系。

关键创新：最重要的技术创新在于建立了样本效率算法所需的批次数的下界，揭示了适应性与样本效率之间的非线性关系。

关键设计：关键参数包括批次数$K$的选择，损失函数设计考虑了反馈处理的效率，网络结构则基于线性函数逼近的假设进行优化。

📊 实验亮点

实验结果显示，在$d$维线性函数逼近下，样本效率算法所需的批次数下界为$Ω( ext{log log } d)$，表明在高维问题中，适应性设置的选择对样本效率有显著影响，提升了算法在复杂环境中的表现。

🎯 应用场景

该研究的潜在应用领域包括机器人控制、自动驾驶、智能推荐系统等，能够在高维状态空间中提升强化学习的样本效率，具有重要的实际价值和未来影响。

📄 摘要（原文）

We theoretically explore the relationship between sample-efficiency and adaptivity in reinforcement learning. An algorithm is sample-efficient if it uses a number of queries $n$ to the environment that is polynomial in the dimension $d$ of the problem. Adaptivity refers to the frequency at which queries are sent and feedback is processed to update the querying strategy. To investigate this interplay, we employ a learning framework that allows sending queries in $K$ batches, with feedback being processed and queries updated after each batch. This model encompasses the whole adaptivity spectrum, ranging from non-adaptive 'offline' ($K=1$) to fully adaptive ($K=n$) scenarios, and regimes in between. For the problems of policy evaluation and best-policy identification under $d$-dimensional linear function approximation, we establish $Ω(\log \log d)$ lower bounds on the number of batches $K$ required for sample-efficient algorithms with $n = O(poly(d))$ queries. Our results show that just having adaptivity ($K>1$) does not necessarily guarantee sample-efficiency. Notably, the adaptivity-boundary for sample-efficiency is not between offline reinforcement learning ($K=1$), where sample-efficiency was known to not be possible, and adaptive settings. Instead, the boundary lies between different regimes of adaptivity and depends on the problem dimension.