Near-optimal Reinforcement Learning in Factored MDPs
Ian Osband Stanford University、Benjamin Van Roy Stanford University
Abstract
Any reinforcement learning algorithm that applies to all Markov decision processes (MDPs) will suffer $\Omega(\sqrt{SAT})$ regret on some MDP, where $T$ is the elapsed time and $S$ and $A$ are the cardinalities of the state and action spaces. This implies $T=\Omega(SA)$ time to guarantee a near-optimal policy. In many settings of practical interest, due to the curse of dimensionality, $S$ and $A$ can be so enormous that this learning time is unacceptable. We establish that, if the system is known to be a factored MDP, it is possible to achieve regret that scales polynomially in the number of parameters encoding the factored MDP, which may be exponentially smaller than $S$ or $A$ . We provide two algorithms that satisfy near-optimal regret bounds in this context: posterior sampling reinforcement learning (PSRL) and an upper confidence bound algorithm (UCRL-Factored).
中文速览
强化学习（RL）在状态空间 S 和动作空间 A 极其庞大时，理论上需要极长时间才能学到近优策略，这在实际复杂系统（如大型流水线）中根本无法接受。研究者利用"因子化马尔可夫决策过程"（Factored MDP，FMDP）这一结构——用动态贝叶斯网络描述变量间的局部依赖关系——将问题参数量从指数级压缩到多项式级。本文提出两种算法：基于后验采样的 PSRL 和基于置信上界的 UCRL-Factored，并为它们在 FMDP 设置下推导出首个近优后悔界（regret bound），其复杂度仅随 FMDP 的编码参数量多项式增长，比不利用结构的算法在指数量级上更紧。这一结果从理论上证明，只要系统具备可知的因子化结构，就能绕开维度诅咒，大幅降低高维复杂环境中的样本需求，为实用高效的强化学习奠定了坚实的理论基础。
原文 arXiv:1403.3741;中英对照 + 大白话阅读 https://aha.fim.ai/paper/1403.3741v3