论文标题
通过球结构动作空间进行线性增强学习
Linear Reinforcement Learning with Ball Structure Action Space
论文作者
论文摘要
我们研究了具有线性函数近似的增强学习问题（RL），即假设最佳的动作值函数是在已知的$ d $维度映射中线性的。但是，不幸的是，仅基于此假设，即使在生成模型下，最坏情况的样本复杂性也被证明是指数的。我们没有对MDP或值函数做出进一步的假设，而是假设我们的动作空间使得始终存在可玩的动作来探索特征空间的任何方向。我们将此假设形式化为``球结构''的动作空间，并表明能够自由探索特征空间允许有效的RL。特别是，我们提出了一种样本效率的RL算法（BALLRL），该算法（BallRl）仅使用$ \ tilde {o} {o} \ left（\ frac {h^5d^3} {h^5d^3} {ε^3} {ε^3} \ right）$。
We study the problem of Reinforcement Learning (RL) with linear function approximation, i.e. assuming the optimal action-value function is linear in a known $d$-dimensional feature mapping. Unfortunately, however, based on only this assumption, the worst case sample complexity has been shown to be exponential, even under a generative model. Instead of making further assumptions on the MDP or value functions, we assume that our action space is such that there always exist playable actions to explore any direction of the feature space. We formalize this assumption as a ``ball structure'' action space, and show that being able to freely explore the feature space allows for efficient RL. In particular, we propose a sample-efficient RL algorithm (BallRL) that learns an $ε$-optimal policy using only $\tilde{O}\left(\frac{H^5d^3}{ε^3}\right)$ number of trajectories.
