Adaptive Discretization for Episodic Reinforcement Learning in Metric Spaces
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.
Code (1)
Tasks
Q-Learningreinforcement-learningReinforcement LearningReinforcement Learning (RL)Similar Papers 제목 키워드 기반
Adaptive Discretization for Model-Based Reinforcement Learning
We introduce the technique of adaptive discretization to design an efficient model-based episodic reinforcement learning algorithm in large (potentially continuous) state-action spaces. Our algorithm is based on optimist…
modelModel-based Reinforcement Learningreinforcement-learningReinforcement Learning+1Zooming for Efficient Model-Free Reinforcement Learning in Metric Spaces
Despite the wealth of research into provably efficient reinforcement learning algorithms, most works focus on tabular representation and thus struggle to handle exponentially or infinitely large state-action spaces. In t…
reinforcement-learningReinforcement LearningReinforcement Learning (RL)Deep Episodic Value Iteration for Model-based Meta-Reinforcement Learning
We present a new deep meta reinforcement learner, which we call Deep Episodic Value Iteration (DEVI). DEVI uses a deep neural network to learn a similarity metric for a non-parametric model-based reinforcement learning a…
Meta Reinforcement LearningModel-based Reinforcement LearningQ-Learningreinforcement-learning+2Discretization of continuous input spaces in the hippocampal autoencoder
The hippocampus has been associated with both spatial cognition and episodic memory formation, but integrating these functions into a unified framework remains challenging. Here, we demonstrate that forming discrete memo…
HippocampusAdaptive Discretization using Voronoi Trees for Continuous-Action POMDPs
Solving Partially Observable Markov Decision Processes (POMDPs) with continuous actions is challenging, particularly for high-dimensional action spaces. To alleviate this difficulty, we propose a new sampling-based onlin…