PAC Reinforcement Learning with Rich Observations
Akshay Krishnamurthy Alekh Agarwal Microsoft Research New York, NY 10011 John Langford Microsoft Research New York, NY 10011
Abstract
We propose and study a new model for reinforcement learning with rich observations, generalizing contextual bandits to sequential decision making. These models require an agent to take actions based on observations (features) with the goal of achieving long-term performance competitive with a large set of policies. To avoid barriers to sample-efficient learning associated with large observation spaces and general POMDPs, we focus on problems that can be summarized by a small number of hidden states and have long-term rewards that are predictable by a reactive function class. In this setting, we design and analyze a new reinforcement learning algorithm, Least Squares Value Elimination by Exploration. We prove that the algorithm learns near optimal behavior after a number of episodes that is polynomial in all relevant parameters, logarithmic in the number of policies, and independent of the size of the observation space. Our result provides theoretical justification for reinforcement learning with function approximation.
中文速览
强化学习在面对高维感知输入（如游戏画面）时，如果要做到高效探索，通常要么依赖观测空间的大小、要么样本复杂度随时间步指数级爆炸，两者都让算法无法实用。这篇论文提出了一类新的决策模型——情境决策过程（Contextual Decision Process，CDP），它把情境赌博机（contextual bandit）推广到序列决策，核心思想是：虽然观测空间可以无限大，但环境本质上只有少量隐藏状态，且最优动作价值函数 Q* 可以被一个只看当前观测的函数类捕捉到。在这个框架下，作者设计了新算法 LSVEE（最小二乘值消除探索），通过结合情境赌博机技术、状态等价性检验和全局探索策略，证明了算法的样本复杂度关于隐藏状态数 M、动作数 K、时间步 H 和策略类复杂度 log|Π| 均为多项式，且完全不依赖观测空间的大小。这一结果首次为带函数近似的强化学习（即当前深度 RL 的主流范式）提供了严格的理论保证，说明只要函数类能逼近 Q*，高效学习在数学上是可行的。
原文 arXiv:1602.02722;中英对照 + 大白话阅读 https://aha.fim.ai/paper/1602.02722v4