特征空间中的强化学习|希尔伯特|神经网络|算法

特征空间中的强化学习：矩阵老虎机、核方法与遗憾界

Reinforcement Learning in Feature Space: Matrix Bandit, Kernels,and Regret Bound

https://arxiv.org/pdf/1905.10389

摘要

1 引言

为了应对维度问题，一种常见的做法是使用特征以紧凑的形式对高维价值函数和策略函数进行参数化，希望这些特征能够捕捉 MDP 的主要结构。事实上，使用显式特征和/或神经网络作为隐式特征的强化学习取得了巨大的经验成功（参见，例如，Mnih et al., 2015）。然而，目前缺乏关于在 RL 中使用特征进行探索及其学习复杂性的理论理解。在本文中，我们关注以下理论问题：

如何在强化学习中使用特征进行可证明的高效探索？

此外，我们考虑再生核空间（reproducing kernel space）中的在线 RL。核方法在许多机器学习任务中因其捕捉非线性和高维性的强大能力而闻名（Shawe-Taylor et al., 2004）。我们感兴趣的是使用核方法来捕捉 MDP 状态转移动态中的非线性。核空间可能包含无限多个隐式特征函数。我们研究以下问题：如何在在线强化学习中使用核？即使核空间是无限维的，能否实现低遗憾？本文的目标是肯定地回答上述问题。特别是，我们要设计能够利用给定特征和核来实现高效探索的算法。

1.1 我们的方法与主要结果

1.2 相关文献

我们的结果也与线性老虎机（linear bandits）的文献相关。老虎机问题可以被视为马尔可夫决策问题的一个特例。有一系列关于线性老虎机问题及其遗憾分析的工作 (Dani et al., 2008; Rusmevichientong and Tsitsiklis, 2010; Li et al., 2010; Abbasi-Yadkori et al., 2011; Chu et al., 2011)。有关更详细的综述，请参阅 (Bubeck et al., 2012)。我们的部分结果受线性老虎机问题的核化（kernelization）启发，例如 (Valko et al., 2013; Chowdhury and Gopalan, 2017)，他们研究了当每个臂（arm）的特征位于某个再生核希尔伯特空间时的遗憾界。

2 问题定义

3 特征空间中的 RL 探索

在本节中，我们研究使用给定特征集在 RL 中平衡探索与利用的接近最优的方法。我们的目标是开发一种在线 RL 算法，其遗憾仅依赖于特征大小 d d，而不依赖于状态-动作空间的大小。我们的算法受 LinUCB 算法（Chu et al., 2011）及其变体（Dani et al., 2008）的启发，可以被视为一种“矩阵老虎机”（matrix bandit）方法。

3.1 MatrixRL 算法