多智能体并发学习中，随机化值迭代提升探索效率。
Concurrent Learning with Aggregated States via Randomized Least Squares Value Iteration
- 用随机化最小二乘值迭代实现多智能体并发学习。
- 每智能体最坏情况下的后悔率降至 Θ(1/√N)，达到最优。
- 空间复杂度降低 K 倍，适合大规模多智能体系统。
设计能在复杂环境中高效探索的学习智能体，是强化学习中的核心挑战。尽管已有研究证明随机值函数在单智能体场景下有效，但理论上仍不清楚随机化是否能帮助一群智能体同时探索环境。本文通过将并发学习框架适配至随机化最小二乘值迭代（RLSVI）与聚合状态表示，建立了有限与无限时域环境下的多项式最坏情况后悔界。在两种设定下，每智能体的后悔率均以最优速率 Θ(1/√N) 下降，凸显了并发学习的优势。相比 Russo et al. (2019) 与 Agrawal et al. (2021)，本算法空间复杂度降低 K 倍，仅导致最坏后悔界增加 √K。数值实验验证了理论结果。
原文摘要 · Abstract (English)
Designing learning agents that explore efficiently in a complex environment has been widely recognized as a fundamental challenge in reinforcement learning. While a number of works have demonstrated the effectiveness of techniques based on randomized value functions on a single agent, it remains unclear, from a theoretical point of view, whether injecting randomization can help a society of agents {\it concurently} explore an environment. The theoretical results %that we established in this work tender an affirmative answer to this question. We adapt the concurrent learning framework to \textit{randomized least-squares value iteration} (RLSVI) with \textit{aggregated state representation}. We demonstrate polynomial worst-case regret bounds in both finite- and infinite-horizon environments. In both setups the per-agent regret decreases at an optimal rate of $Θ\left(\frac{1}{\sqrt{N}}\right)$, highlighting the advantage of concurent learning. Our algorithm exhibits significantly lower space complexity compared to \cite{russo2019worst} and \cite{agrawal2021improved}. We reduce the space complexity by a factor of $K$ while incurring only a $\sqrt{K}$ increase in the worst-case regret bound, compared to \citep{agrawal2021improved,russo2019worst}. Additionally, we conduct numerical experiments to demonstrate our theoretical findings.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。