Adaptive Discretization for Model-Based Reinforcement Learning

Abstract

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 optimistic one-step value iteration extended to maintain an adaptive discretization of the space. From a theoretical perspective we provide worst-case regret bounds for our algorithm which are competitive compared to the state-of-the-art model-based algorithms. Moreover, our bounds are obtained via a modular proof technique which can potentially extend to incorporate additional structure on the problem. From an implementation standpoint, our algorithm has much lower storage and computational requirements due to maintaining a more efficient partition of the state and action spaces. We illustrate this via experiments on several canonical control problems, which shows that our algorithm empirically performs significantly better than fixed discretization in terms of both faster convergence and lower memory usage. Interestingly, we observe empirically that while fixed-discretization model-based algorithms vastly outperform their model-free counterparts, the two achieve comparable performance with adaptive discretization.

50 pages, 7 figures

References in corpus (17)

• Playing Atari with Deep Reinforcement Learning
• Mastering Chess and Shogi by Self-Play with a General Reinforcement Learning Algorithm
• Contextual Bandits with Similarity Information
• Provably Efficient Reinforcement Learning with Linear Function Approximation
• Sample Complexity of Episodic Fixed-Horizon Reinforcement Learning
• Model-Based Reinforcement Learning with Value-Targeted Regression
• Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Bounds
• Optimism in Reinforcement Learning with Generalized Linear Function Approximation
• On Lower Bounds for Regret in Reinforcement Learning
• Model-based Reinforcement Learning and the Eluder Dimension
• Provably Efficient $Q$-learning with Function Approximation via Distribution Shift Error Checking Oracle
• Reinforcement Learning with General Value Function Approximation: Provably Efficient Approach via Bounded Eluder Dimension
• Is Long Horizon Reinforcement Learning More Difficult Than Short Horizon Reinforcement Learning?
• Efficient Model-free Reinforcement Learning in Metric Spaces
• Explicit Explore-Exploit Algorithms in Continuous State Spaces
• Learning to Control in Metric Space with Optimal Regret
• Provably adaptive reinforcement learning in metric spaces

Cited by in corpus (3)

• A Kernel-Based Approach to Non-Stationary Reinforcement Learning in Metric Spaces
• Coarse-Grained Smoothness for RL in Metric Spaces
• Effects of sampling and horizon in predictive reinforcement learning