用等周不等式设计出可实现亚线性后悔的强化学习算法
Isoperimetry is All We Need: Langevin Posterior Sampling for RL with Sublinear Regret
- 基于对偶等周条件设计后验采样算法，突破传统高斯假设限制
- 提出LaPSRL算法，在非对称和非凹分布下仍保持亚线性后悔
- 适合处理复杂分布的强化学习场景，尤其适用于带噪声或非凸问题
常见假设如线性模型、RKHS空间及高斯或对数凹后验，并不能解释强化学习在更广泛分布和模型下的实际成功。为此，本文研究如何设计针对满足对偶等周不等式（LSI）分布的强化学习算法，以实现亚线性后悔。我们证明：在数据分布满足LSI且具备若干弱附加条件下，基于后验采样的强化学习（PSRL）算法可实现亚线性后悔。当无法精确计算或采样后验时，提出一种基于朗之万采样的算法设计——LaPSRL。我们证明，该算法达到最优阶次的后悔率，且每轮复杂度为次二次。最后，将LaPSRL与朗之万采样器SARAH-LD结合，在多种老虎机和马尔可夫决策过程环境中进行测试。实验结果验证了LaPSRL在不同环境下的通用性及其相对于基线方法的竞争力。
原文摘要 · Abstract (English)
Common assumptions, like linear or RKHS models, and Gaussian or log-concave posteriors over the models, do not explain practical success of RL across a wider range of distributions and models. Thus, we study how to design RL algorithms with sublinear regret for isoperimetric distributions, specifically the ones satisfying the Log-Sobolev Inequality (LSI). LSI distributions include the standard setups of RL theory, and others, such as many non-log-concave and perturbed distributions. First, we show that the Posterior Sampling-based RL (PSRL) algorithm yields sublinear regret if the data distributions satisfy LSI and some mild additional assumptions. Also, when we cannot compute or sample from an exact posterior, we propose a Langevin sampling-based algorithm design: LaPSRL. We show that LaPSRL achieves order-optimal regret and subquadratic complexity per episode. Finally, we deploy LaPSRL with a Langevin sampler -- SARAH-LD, and test it for different bandit and MDP environments. Experimental results validate the generality of LaPSRL across environments and its competitive performance with respect to the baselines.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。