This work introduces Bilinear Classes, a new structural framework, which permit generalization in reinforcement learning in a wide variety of settings through the use of function approximation. The framework incorporates nearly all existing models in which a polynomial sample complexity is achievable, and, notably, also includes new models, such as the Linear $Q^*/V^*$ model in which both the optimal $Q$-function and the optimal $V$-function are linear in some known feature space. Our main result provides an RL algorithm which has polynomial sample complexity for Bilinear Classes; notably, this sample complexity is stated in terms of a reduction to the generalization error of an underlying supervised learning sub-problem. These bounds nearly match the best known sample complexity bounds for existing models. Furthermore, this framework also extends to the infinite dimensional (RKHS) setting: for the the Linear $Q^*/V^*$ model, linear MDPs, and linear mixture MDPs, we provide sample complexities that have no explicit dependence on the explicit feature dimension (which could be infinite), but instead depends only on information theoretic quantities.
翻译：这项工作引入了双线类,这是一个新的结构框架,它允许通过使用功能近似值,在多种环境中对强化学习进行概括化,该框架包含几乎所有现有模型,其中多元样本复杂度是可以实现的,特别是还包括新的模型,例如Linear $ ⁇ /V ⁇ $$$$ /V ⁇ $$美元模型,其中最佳的美元功能和最佳的美元功能在某些已知特征空间是线性的。我们的主要结果提供了一种RL算法,该算法对双线类具有多元样本复杂度;特别是,这一抽样复杂度是用减少一个基本受监督的次级问题的一般性错误来表示的。这些模型的界限几乎与现有模型已知的最佳样本复杂度界限相匹配。此外,这一框架还延伸至无限的维度(RKHS)设置:对于Linear $ ⁇ /V ⁇ $美元模型、线性MDPs和线性混合物 MDPs,我们提供的样本复杂度并不明显依赖明确的特征层面(可能是无限的),而是仅取决于信息的理论量。