Bellman Eluder 尺寸:新富的RL问题类别和抽样有效算法 (Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithms)

from arxiv, We propose a new complexity measure and an optimization-based sample-efficient algorithm for reinforcement learning with function approximation

Finding the minimal structural assumptions that empower sample-efficient learning is one of the most important research directions in Reinforcement Learning (RL). This paper advances our understanding of this fundamental question by introducing a new complexity measure -- Bellman Eluder (BE) dimension. We show that the family of RL problems of low BE dimension is remarkably rich, which subsumes a vast majority of existing tractable RL problems including but not limited to tabular MDPs, linear MDPs, reactive POMDPs, low Bellman rank problems as well as low Eluder dimension problems. This paper further designs a new optimization-based algorithm -- GOLF, and reanalyzes a hypothesis elimination-based algorithm -- OLIVE (proposed in Jiang et al. (2017)). We prove that both algorithms learn the near-optimal policies of low BE dimension problems in a number of samples that is polynomial in all relevant parameters, but independent of the size of state-action space. Our regret and sample complexity results match or improve the best existing results for several well-known subclasses of low BE dimension problems.

翻译：找到增强抽样效率学习的最低限度结构假设是加强学习(RL)最重要的研究方向之一。本文件通过引入新的复杂度 -- -- Bellman Eluder(BE) 维度 -- -- 增进了我们对这个根本问题的了解。我们表明,低BE维度RL问题的家庭非常丰富,它囊括了绝大多数现有的可移植RL问题,包括但不限于表格式MDP、线性MDP、反应式POMDP、低贝尔曼等级问题以及低Eluder维度问题。本文还设计了一种新的基于优化的算法 -- -- GOLF,并重新分析基于假设的消除算法 -- -- OLIVE(在江等人(2017年)提出)。我们证明,两种算法都学习了在所有相关参数中都具有多元性但独立于国家行动空间大小的若干样本中低BE维度问题的近最佳政策。我们的遗憾和抽样复杂性结果或改进了几个众所周知的低BE维度子类现有最佳结果。