We propose a new reinforcement learning algorithm for partially observable Markov decision processes (POMDP) based on spectral decomposition methods. While spectral methods have been previously employed for consistent learning of (passive) latent variable models such as hidden Markov models, POMDPs are more challenging since the learner interacts with the environment and possibly changes the future observations in the process. We devise a learning algorithm running through epochs, in each epoch we employ spectral techniques to learn the POMDP parameters from a trajectory generated by a fixed policy. At the end of the epoch, an optimization oracle returns the optimal memoryless planning policy which maximizes the expected reward based on the estimated POMDP model. We prove an order-optimal regret bound with respect to the optimal memoryless policy and efficient scaling with respect to the dimensionality of observation and action spaces.

提出了一种基于谱分解方法的新的强化学习算法，用于部分可观察马尔可夫决策过程（POMDP）。通过谱技术从由固定策略生成的轨迹中学习POMDP参数，运行多个历元后，最终通过优化预测的POMDP模型返回最佳无记忆策略，并证明了与最优无记忆策略具有相对最优的后悔界和有效的缩放性。

基于谱方法的POMDP强化学习实验结果