Computationally Efficient PAC RL in POMDPs with Latent Determinism and Conditional Embeddings
Computationally Efficient PAC RL in POMDPs with Latent Determinism and Conditional Embeddings
复制标题
DOI：
10.48550/arxiv.2206.12081
复制
发表时间：
2022-06
期刊：
影响因子：
--
通讯作者：
Masatoshi Uehara;Ayush Sekhari;Jason D. Lee;Nathan Kallus;Wen Sun
中科院分区：
文献类型：
--
作者：
Masatoshi Uehara;Ayush Sekhari;Jason D. Lee;Nathan Kallus;Wen Sun
我们研究了大规模部分可观测马尔可夫决策过程（POMDPs）的函数逼近强化学习，其中状态空间和观测空间是大的甚至是连续的。特别地，我们考虑POMDP的Hilbert空间嵌入，其中潜在状态的特征和观测的特征允许观测发射过程的条件Hilbert空间嵌入，并且潜在状态转移是确定性的。在最优潜在状态-动作$Q$-函数在状态特征上是线性的，并且最优$Q$-函数在动作上有间隙的函数近似设置下，我们提供了一个计算和统计上有效的算法来寻找最优策略.我们展示了我们的算法的计算和统计复杂性尺度多项式的地平线和内在维度的观察空间上的功能。此外，我们证明了确定性的潜在转移和间隙假设是必要的，以避免统计复杂性指数的水平或维度。由于我们的保证没有明确的依赖于状态和观测空间的大小，我们的算法可证明规模大规模POMDPs。
We study reinforcement learning with function approximation for large-scale Partially Observable Markov Decision Processes (POMDPs) where the state space and observation space are large or even continuous. Particularly, we consider Hilbert space embeddings of POMDP where the feature of latent states and the feature of observations admit a conditional Hilbert space embedding of the observation emission process, and the latent state transition is deterministic. Under the function approximation setup where the optimal latent state-action $Q$-function is linear in the state feature, and the optimal $Q$-function has a gap in actions, we provide a \emph{computationally and statistically efficient} algorithm for finding the \emph{exact optimal} policy. We show our algorithm's computational and statistical complexities scale polynomially with respect to the horizon and the intrinsic dimension of the feature on the observation space. Furthermore, we show both the deterministic latent transitions and gap assumptions are necessary to avoid statistical complexity exponential in horizon or dimension. Since our guarantee does not have an explicit dependence on the size of the state and observation spaces, our algorithm provably scales to large-scale POMDPs.