Adaptive Discretization in Online Reinforcement Learning

Abstract

Discretization based approaches to solving online reinforcement learning problems have been studied extensively in practice on applications ranging from resource allocation to cache management. Two major questions in designing discretization-based algorithms are how to create the discretization and when to refine it. While there have been several experimental results investigating heuristic solutions to these questions, there has been little theoretical treatment. In this paper we provide a unified theoretical analysis of tree-based hierarchical partitioning methods for online reinforcement learning, providing model-free and model-based algorithms. We show how our algorithms are able to take advantage of inherent structure of the problem by providing guarantees that scale with respect to the 'zooming dimension' instead of the ambient dimension, an instance-dependent quantity measuring the benignness of the optimal $Q_h^{\star }$ function. Many applications in computing systems and operations research requires algorithms that compete on three facets: low sample complexity, mild storage requirements, and low computational burden. Our algorithms are easily adapted to operating constraints, and our theory provides explicit bounds across each of the three facets. This motivates its use in practical applications as our approach automatically adapts to underlying problem structure even when very little is known a priori about the system.

77 pages, 7 figures. arXiv admin note: text overlap with arXiv:2007.00717

References in corpus (15)

• Mastering Chess and Shogi by Self-Play with a General Reinforcement Learning Algorithm
• Provably Efficient Reinforcement Learning with Linear Function Approximation
• Contextual Decision Processes with Low Bellman Rank are PAC-Learnable
• Optimism in Reinforcement Learning with Generalized Linear Function Approximation
• Model-based Reinforcement Learning and the Eluder Dimension
• Is a Good Representation Sufficient for Sample Efficient Reinforcement Learning?
• Reinforcement Learning with General Value Function Approximation: Provably Efficient Approach via Bounded Eluder Dimension
• Efficient Model-free Reinforcement Learning in Metric Spaces
• Learning to Control in Metric Space with Optimal Regret
• Explicit Explore-Exploit Algorithms in Continuous State Spaces
• Sample Efficient Reinforcement Learning via Low-Rank Matrix Estimation
• Provably adaptive reinforcement learning in metric spaces
• Single-partition adaptive Q-learning
• On Linear Convergence of Policy Gradient Methods for Finite MDPs
• Control with adaptive Q-learning