Adaptive Discretization for Episodic Reinforcement Learning in Metric Spaces
Adaptive Discretization for Episodic Reinforcement Learning in Metric Spaces
复制标题
DOI：
10.1145/3366703
复制
发表时间：
2019-10
期刊：
影响因子：
--
通讯作者：
Sean R. Sinclair;Siddhartha Banerjee;C. Yu
中科院分区：
文献类型：
--
作者：
Sean R. Sinclair;Siddhartha Banerjee;C. Yu
我们提出了一种在大型（可能连续的）状态动作空间上进行无模型情景强化学习的有效算法。我们的算法基于一种新颖的 Q 学习策略，具有自适应数据驱动的离散化。其中心思想是在历史轨迹中经常访问且具有较高回报估计的区域中保持对国家行动空间的更精细划分。我们演示了我们的自适应分区如何利用最佳 Q 函数和联合空间的形状，而不牺牲最坏情况的性能。特别是，我们恢复了连续状态动作空间的先前算法的遗憾保证，这还需要最佳离散化作为输入和/或访问模拟预言机。此外，实验证明了我们的算法如何自动适应问题的底层结构，与启发式算法和均匀离散化的 Q 学习相比，具有更好的性能。
We present an efficient algorithm for model-free episodic reinforcement learning on large (potentially continuous) state-action spaces. Our algorithm is based on a novel Q-learning policy with adaptive data-driven discretization. The central idea is to maintain a finer partition of the state-action space in regions which are frequently visited in historical trajectories, and have higher payoff estimates. We demonstrate how our adaptive partitions take advantage of the shape of the optimal Q-function and the joint space, without sacrificing the worst-case performance. In particular, we recover the regret guarantees of prior algorithms for continuous state-action spaces, which additionally require either an optimal discretization as input, and/or access to a simulation oracle. Moreover, experiments demonstrate how our algorithm automatically adapts to the underlying structure of the problem, resulting in much better performance compared both to heuristics and Q-learning with uniform discretization.