Bilinear Exponential Family of MDPs: Frequentist Regret Bound with Tractable Exploration & Planning

2022/09/01 by Reda Ouhamma, Debabrota Basu, Ouhamma, Reda +3 · 2 citations
Biochemistry, Genetics and Molecular Biology · Computer Science · Decision Sciences · #Advanced Bandit Algorithms Research #Auction Theory and Applications #Computability, Logic, AI Algorithms #FOS: Computer and information sciences #Machine Learning (cs.LG) #Optimization and Search Problems #Receptor Mechanisms and Signaling #Reinforcement Learning in Robotics

paper · pdf · doi:10.48550/arxiv.2210.02087

openalex publication_date 2022/09/01 · openalex created_date 2022/10/06 · openalex updated_date 2026/08/04

Abstract

We study the problem of episodic reinforcement learning in continuous\nstate-action spaces with unknown rewards and transitions. Specifically, we\nconsider the setting where the rewards and transitions are modeled using\nparametric bilinear exponential families. We propose an algorithm, BEF-RLSVI,\nthat a) uses penalized maximum likelihood estimators to learn the unknown\nparameters, b) injects a calibrated Gaussian noise in the parameter of rewards\nto ensure exploration, and c) leverages linearity of the exponential family\nwith respect to an underlying RKHS to perform tractable planning. We further\nprovide a frequentist regret analysis of BEF-RLSVI that yields an upper bound\nof \\O(\√(d³H³K)), where d is the dimension of the\nparameters, H is the episode length, and K is the number of episodes. Our\nanalysis improves the existing bounds for the bilinear exponential family of\nMDPs by \√(H) and removes the handcrafted clipping deployed in existing\n RLSVI-type algorithms. Our regret bound is order-optimal with respect to H\nand K.\n

Cited by

• Performative Policy Gradient: Optimality in Performative Reinforcement Learning
• Efficient Preference-Based Reinforcement Learning: Randomized Exploration Meets Experimental Design

Related

• Episodic Reinforcement Learning in Finite MDPs: Minimax Lower Bounds Revisited
• Reinforcement Learning in Linear MDPs: Constant Regret and\n Representation Selection
• Horizon-free Reinforcement Learning in Adversarial Linear Mixture MDPs
• Almost Optimal Model-Free Reinforcement Learning via Reference-Advantage Decomposition
• Achieving Constant Regret in Linear Markov Decision Processes