Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithms
Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithms
复制标题
DOI：
--
复制
发表时间：
2021-02
期刊：
影响因子：
--
通讯作者：
Chi Jin;Qinghua Liu;Sobhan Miryoosefi
中科院分区：
文献类型：
--
作者：
Chi Jin;Qinghua Liu;Sobhan Miryoosefi
寻找支持样本高效学习的最小结构假设是强化学习（RL）最重要的研究方向之一。本文通过引入一种新的复杂性度量——贝尔曼埃鲁德（BE）维度，增进了我们对这一基本问题的理解。我们表明，低 BE 维度的 RL 问题家族非常丰富，其中包含绝大多数现有的可处理的 RL 问题，包括但不限于表格 MDP、线性 MDP、反应式 POMDP、低贝尔曼秩问题以及低 Eluder 维度问题。本文进一步设计了一种新的基于优化的算法——GOLF，并重新分析了一种基于假设消除的算法——OLIVE（Jiang et al., 2017提出）。我们证明这两种算法都能在许多样本中学习低 BE 维问题的近乎最优策略，这些样本在所有相关参数中都是多项式，但与状态动作空间的大小无关。我们的遗憾和样本复杂性结果匹配或改进了低 BE 维度问题的几个众所周知的子类的最佳现有结果。
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.