异构性在联邦Q学习中的优势：线性加速及超越

摘要

本文研究联邦Q学习，其目标是通过定期聚合仅基于本地数据训练的本地Q估计来学习最优Q函数。聚焦于无限时间表格马尔可夫决策过程，为同步和异步联邦Q学习变体提供了样本复杂度保证，这些保证在代理数量上呈现线性加速，并与其他显著问题参数具有近乎最优的依赖性。

在异步设置中，现有采用本地Q估计等权平均的联邦Q学习分析要求每个代理覆盖整个状态-行动空间。相比之下，改进后的样本复杂度与所有代理平均平稳状态-行动占用分布的最小条目成反比缩放，因此仅要求代理集体覆盖整个状态-行动空间，揭示了异构性的优势。

然而，当本地轨迹高度异构时，其样本复杂度仍会受到影响。为此，提出了一种新颖的采用重要性加权的联邦Q学习算法，为更频繁访问的状态-行动对赋予更大权重，实现了稳健的线性加速，犹如所有轨迹被集中处理，无论本地行为策略的异构性如何。

关键词：联邦学习，Q学习，强化学习，样本复杂度，异构性