2022/09/30 by Zixiang Chen, Chen, Zixiang, Chris Junchi Li +8 · 3 citations
Computer Science · Mathematics · Psychology · #Artificial Intelligence (cs.AI) #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Mental Health Research Topics #Reinforcement Learning in Robotics #cs.AI #cs.LG #stat.ML
paper · pdf · doi:10.48550/arxiv.2209.15634
arxiv created 2022/09/30 · openalex publication_date 2022/09/30 · arxiv updated 2022/10/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
With the increasing need for handling large state and action spaces, general function approximation has become a key technique in reinforcement learning (RL). In this paper, we propose a general framework that unifies model-based and model-free RL, and an Admissible Bellman Characterization (ABC) class that subsumes nearly all Markov Decision Process (MDP) models in the literature for tractable RL. We propose a novel estimation function with decomposable structural properties for optimization-based exploration and the functional eluder dimension as a complexity measure of the ABC class. Under our framework, a new sample-efficient algorithm namely OPtimization-based ExploRation with Approximation (OPERA) is proposed, achieving regret bounds that match or improve over the best-known results for a variety of MDP models. In particular, for MDPs with low Witness rank, under a slightly stronger assumption, OPERA improves the state-of-the-art sample complexity results by a factor of dH. Our framework provides a generic interface to design and analyze new RL models and algorithms.