用范畴论统一建模强化学习,实现异步并行求解价值函数。
Universal Reinforcement Learning in Coalgebras: Asynchronous Stochastic Computation via Conduction
- 基于余代数框架,将RL算法统一为函子范畴中的模型。
- 异步分布式计算下,通过度量余归纳保证收敛性。
- 适合对数学形式化和理论深度感兴趣的算法研究者。
本文提出一种基于范畴论的通用强化学习(URL)框架,利用非良基集上的余归纳、通用余代数、拓扑理论及异步并行计算的范畴模型,对强化学习进行数学抽象。首先回顾标准强化学习框架,展示范畴与函子在其中的洞察力,并关联Bertsekas和Tsitsiklis提出的异步分布式最小化模型与度量余归纳之间的关系。马尔可夫决策过程(MDPs)、部分可观测马尔可夫决策过程(POMDPs)、预测状态表示(PSRs)和线性动态系统(LDSs)均可视为特定类型的余代数。在此基础上,扩展出一类广义通用余代数,涵盖此前多种动态系统模型。在该框架下,求解价值函数固定点的问题被泛化为异步并行地确定最终余代数。
原文摘要 · Abstract (English)
In this paper, we introduce a categorial generalization of RL, termed universal reinforcement learning (URL), building on powerful mathematical abstractions from the study of coinduction on non-well-founded sets and universal coalgebras, topos theory, and categorial models of asynchronous parallel distributed computation. In the first half of the paper, we review the basic RL framework, illustrate the use of categories and functors in RL, showing how they lead to interesting insights. In particular, we also introduce a standard model of asynchronous distributed minimization proposed by Bertsekas and Tsitsiklis, and describe the relationship between metric coinduction and their proof of the Asynchronous Convergence Theorem. The space of algorithms for MDPs or PSRs can be modeled as a functor category, where the co-domain category forms a topos, which admits all (co)limits, possesses a subobject classifier, and has exponential objects. In the second half of the paper, we move on to universal coalgebras. Dynamical system models, such as Markov decision processes (MDPs), partially observed MDPs (POMDPs), a predictive state representation (PSRs), and linear dynamical systems (LDSs) are all special types of coalgebras. We describe a broad family of universal coalgebras, extending the dynamic system models studied previously in RL. The core problem in finding fixed points in RL to determine the exact or approximate (action) value function is generalized in URL to determining the final coalgebra asynchronously in a parallel distributed manner.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。