mlsanityData to 7 Oct 2026

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

arXiv 2210.02087 ↗First posted 5 Oct 2022cs.LGcited by 12

Not on the map. Why?

Abstract (arXiv)

We study the problem of episodic reinforcement learning in continuous state-action spaces with unknown rewards and transitions. Specifically, we consider the setting where the rewards and transitions are modeled using parametric bilinear exponential families. We propose an algorithm, BEF-RLSVI, that a) uses penalized maximum likelihood estimators to learn the unknown parameters, b) injects a calibrated Gaussian noise in the parameter of rewards to ensure exploration, and c) leverages linearity of the exponential family with respect to an underlying RKHS to perform tractable planning. We further provide a frequentist regret analysis of BEF-RLSVI that yields an upper bound of tildeO(√d3H3K), where d is the dimension of the parameters, H is the episode length, and K is the number of episodes. Our analysis improves the existing bounds for the bilinear exponential family of MDPs by √H and removes the handcrafted clipping deployed in existing RLSVI-type algorithms. Our regret bound is order-optimal with respect to H and K.

Key facts. Cited by 12 papers in the map (data through 7 Oct 2026). Builds on 30 of its 48 references that are in the map. First posted on arXiv 5 Oct 2022.

Builds on

30 of 48 references.

References · 30

  1. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 514
  2. 2017Minimax Regret Bounds for Reinforcement Learningcited by 500
  3. 2016Contextual Decision Processes with Low Bellman Rank are PAC-Learnablecited by 290
  4. 2013(More) Efficient Reinforcement Learning via Posterior Samplingcited by 233
  5. 2020Model-Based Reinforcement Learning with Value-Targeted Regressioncited by 233
  6. 2021The Statistical Complexity of Interactive Decision Makingcited by 208
  7. 2019Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Boundcited by 199
  8. 2021Bilinear Classes: A Structural Framework for Provable Generalization in RLcited by 176
  9. 2017Unifying PAC and Regret: Uniform PAC Bounds for Episodic Reinforcement Learningcited by 175
  10. 2019Is a Good Representation Sufficient for Sample Efficient Reinforcement Learning?cited by 140
  11. 2019Learning with Good Feature Representations in Bandits and in RL with a Generative Modelcited by 124
  12. 2014Model-based Reinforcement Learning and the Eluder Dimensioncited by 116
18 more
  1. 2014Generalization and Exploration via Randomized Value Functionscited by 112
  2. 2020Episodic Reinforcement Learning in Finite MDPs: Minimax Lower Bounds Revisitedcited by 104
  3. 2019Frequentist Regret Bounds for Randomized Least-Squares Value Iterationcited by 100
  4. 2017Scalable Generalized Linear Bandits: Online Computation and Hashingcited by 63
  5. 2013Relative Loss Bounds for On-line Density Estimation with the Exponential Family of Distributionscited by 59
  6. 2021Randomized Exploration for Reinforcement Learning with General Value Function Approximationcited by 49
  7. 2020Low-Rank Generalized Linear Bandit Problemscited by 48
  8. 2013Thompson Sampling for 1-Dimensional Exponential Family Banditscited by 41
  9. 2021Provable Representation Learning for Imitation with Contrastive Fourier Featurescited by 34
  10. 2019On Online Learning in Kernelized Markov Decision Processescited by 32
  11. 2021A Free Lunch from the Noise: Provable and Practical Exploration for Representation Learningcited by 24
  12. 2020Efficient Planning in Large MDPs with Weak Linear Function Approximationcited by 17
  13. 2018Kernel Exponential Family Estimation via Doubly Dual Embeddingcited by 16
  14. 2019Comments on the Du-Kakade-Wang-Yang Lower Boundscited by 16
  15. 2021A Computationally Efficient Method for Learning Exponential Family Distributionscited by 10
  16. 2021Stochastic Online Linear Regression: the Forward Algorithm to Replace Ridgecited by 10
  17. 2021A Short Note on the Relationship of Information Gain and Eluder Dimensioncited by 7
  18. 2021Exponential Family Model-Based Reinforcement Learning via Score Matchingcited by 5

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 4; 2024: 5; 2025: 2; 2026: 1.

12 papers.

  1. 2023Provable and Practical: Efficient Exploration in Reinforcement Learning via Langevin Monte Carlocited by 29
  2. 2024Diffusion Spectral Representation for Reinforcement Learningcited by 15
  3. 2024Provably Efficient Reinforcement Learning with Multinomial Logit Function Approximationcited by 10
  4. 2023Optimistic Planning by Regularized Dynamic Programmingcited by 8
  5. 2023Stochastic Online Instrumental Variable Regression: Regrets for Endogeneity and Bandit Feedbackcited by 7
  6. 2025Performative Policy Gradient: Optimality in Performative Reinforcement Learningcited by 4
  7. 2025Efficient Preference-Based Reinforcement Learning: Randomized Exploration Meets Experimental Designcited by 3
  8. 2024How does Your RL Agent Explore? An Optimal Transport Analysis of Occupancy Measure Trajectoriescited by 1
  9. 2024SaVeR: Optimal Data Collection Strategy for Safe Policy Evaluation in Tabular MDPcited by 1
  10. 2024Isoperimetry is All We Need: Langevin Posterior Sampling for RL with Sublinear Regretcited by 1
  11. 2023Reinforcement Learning in the Wild with Maximum Likelihood-based Model Transfercited by 0
  12. 2026Asymptotically Optimal Sequential Testing with Markovian Datacited by 0