改进线性MDP强化学习算法，降低内存和时间开销。
Efficient, Low-Regret, Online Reinforcement Learning for Linear MDPs
- 通过学习与不学习周期交替减少存储与计算
- 实测在合成数据和真实基准上保持低后悔值
- 适合资源受限的在线强化学习场景
强化学习算法通常缺乏性能的理论保证。Jin 等人（COLT 2020）提出了一种针对线性马尔可夫决策过程的多项式时间算法（即 LSVI-UCB），并提供了运行时间和后悔率的理论保障。然而，在实际场景中，该算法因使用线性回归步骤而导致空间占用过高。本文提出并分析了 LSVI-UCB 的两种修改版本，通过交替进行学习与非学习阶段，显著降低空间和时间开销，同时保持亚线性后悔。实验表明，所提算法在合成数据和真实世界基准上均实现了低空间占用与运行时间，且后悔值无明显下降。
原文摘要 · Abstract (English)
Reinforcement learning algorithms are usually stated without theoretical guarantees regarding their performance. Recently, Jin, Yang, Wang, and Jordan (COLT 2020) showed a polynomial-time reinforcement learning algorithm (namely, LSVI-UCB) for the setting of linear Markov decision processes, and provided theoretical guarantees regarding its running time and regret. In real-world scenarios, however, the space usage of this algorithm can be prohibitive due to a utilized linear regression step. We propose and analyze two modifications of LSVI-UCB, which alternate periods of learning and not-learning, to reduce space and time usage while maintaining sublinear regret. We show experimentally, on synthetic data and real-world benchmarks, that our algorithms achieve low space usage and running time, while not significantly sacrificing regret.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。