Adaptive Discretization for Episodic Reinforcement Learning in Metric Spaces
This work addresses the challenge of scaling reinforcement learning to complex environments for researchers and practitioners, offering a novel approach that improves performance over heuristics and uniform discretization, though it is incremental in its method development.
The paper tackles the problem of model-free episodic reinforcement learning in large or continuous state-action spaces by introducing an efficient Q-learning algorithm with adaptive data-driven discretization, which automatically refines partitions based on visitation frequency and payoff estimates, achieving regret guarantees comparable to prior methods without requiring optimal discretization input or simulation oracles.
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.