Adaptive Discretization in Online Reinforcement Learning

Sean R. Sinclair (), Siddhartha Banerjee () and Christina Lee Yu ()
Additional contact information
Sean R. Sinclair: Operations Research and Information Engineering, Cornell University, Ithaca, New York 14853
Siddhartha Banerjee: Operations Research and Information Engineering, Cornell University, Ithaca, New York 14853
Christina Lee Yu: Operations Research and Information Engineering, Cornell University, Ithaca, New York 14853

Operations Research, 2023, vol. 71, issue 5, 1636-1652

Abstract: Discretization-based approaches to solving online reinforcement learning problems are studied extensively on applications such as resource allocation and cache management. The two major questions in designing discretization-based algorithms are how to create the discretization and when to refine it. There are several experimental results investigating heuristic approaches to these questions but little theoretical treatment. In this paper, we provide a unified theoretical analysis of model-free and model-based, tree-based adaptive hierarchical partitioning methods for online reinforcement learning. We show how our algorithms take advantage of inherent problem structure by providing guarantees that scale with respect to the “zooming” instead of the ambient dimension, an instance-dependent quantity measuring the benignness of the optimal Q h ⋆ function. Many applications in computing systems and operations research require algorithms that compete on three facets: low sample complexity, mild storage requirements, and low computational burden for policy evaluation and training. Our algorithms are easily adapted to operating constraints, and our theory provides explicit bounds across each of the three facets.

Keywords: Machine Learning and Data Science; reinforcement learning; metric spaces; adaptive discretization; online learning (search for similar items in EconPapers)
Date: 2023
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/opre.2022.2396 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:71:y:2023:i:5:p:1636-1652

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().