Reinforcement Learning in Rich-Observation MDPs using Spectral Methods
\nameKamyar Azizzadenesheli \addrDepartment of EECS University California, Irvine Irvine, CA 92697, USA \AND\nameAlessandro Lazaric \addrFacebook AI Research (FAIR) Paris, France \AND\nameAnimashree Anandkumar \addrCalifornia institute of technology 1200 E California Blvd, Pasadena, CA 91125
Abstract
Reinforcement learning (RL) in Markov decision processes (MDPs) with large state spaces is a challenging problem. The performance of standard RL algorithms degrades drastically with the dimensionality of state space. However, in practice, these large MDPs typically incorporate a latent or hidden low-dimensional structure. In this paper, we study the setting of rich-observation Markov decision processes (ROMDP), where there are a small number of hidden states which possess an injective mapping to the observation states. In other words, every observation state is generated through a single hidden state, and this mapping is unknown a priori. We introduce a spectral decomposition method that consistently learns this mapping, and more importantly, achieves it with low regret. The estimated mapping is integrated into an optimistic RL algorithm (UCRL), which operates on the estimated hidden space. We derive finite-time regret bounds for our algorithm with a weak dependence on the dimensionality of the observed space. In fact, our algorithm asymptotically achieves the same average regret as the oracle UCRL algorithm, which has the knowledge of the mapping from hidden to observed spaces. Th
中文速览
大规模状态空间的强化学习面临维度爆炸难题，而现实中许多高维观测背后往往隐藏着一个低维的隐状态结构，比如机器人导航中复杂的视觉输入本质上对应一张简单的二维位置图。本文研究的"富观测马尔可夫决策过程"（Rich-Observation MDP，ROMDP）正是刻画这一结构：少量隐状态通过一个未知的单射映射生成大量观测，每个观测只属于唯一一个隐状态簇。作者提出了SL-UCRL算法，将谱分解（张量分解）方法嵌入经典的乐观强化学习框架UCRL，通过对连续三步观测构造多视角张量模型，在线地把观测聚类到对应的隐状态，并在不断缩小的辅助MDP上计算最优策略。理论上，完成正确聚类所需的额外累积遗憾是有限常数，与总步数无关，因此算法的渐近平均遗憾与"已知真实映射"的oracle算法完全一致，同时计算和存储复杂度也从依赖观测空间大小降至仅依赖隐状态数量，为处理大规模观测空间的强化学习提供了一条有理论保障的高效路径。
原文 arXiv:1611.03907;中英对照 + 大白话阅读 https://aha.fim.ai/paper/1611.03907v4