Nearly Minimax Optimal Regret for Learning Infinite-horizon Average-reward MDPs with Linear Function Approximation

Abstract

We study reinforcement learning in an infinite-horizon average-reward setting with linear function approximation, where the transition probability function of the underlying Markov Decision Process (MDP) admits a linear form over a feature mapping of the current state, action, and next state. We propose a new algorithm UCRL2-VTR, which can be seen as an extension of the UCRL2 algorithm with linear function approximation. We show that UCRL2-VTR with Bernstein-type bonus can achieve a regret of $\tilde{O}(d\sqrt{DT})$, where $d$ is the dimension of the feature mapping, $T$ is the horizon, and $\sqrt{D}$ is the diameter of the MDP. We also prove a matching lower bound $\tilde{\Omega }(d\sqrt{DT})$, which suggests that the proposed UCRL2-VTR is minimax optimal up to logarithmic factors. To the best of our knowledge, our algorithm is the first nearly minimax optimal RL algorithm with function approximation in the infinite-horizon average-reward setting.

31 pages, 2 figures. In AISTATS 2022

References in corpus (8)

• Contextual Decision Processes with Low Bellman Rank are PAC-Learnable
• REGAL: A Regularization based Algorithm for Reinforcement Learning in Weakly Communicating MDPs
• Model-Based Reinforcement Learning with Value-Targeted Regression
• Optimism in Reinforcement Learning with Generalized Linear Function Approximation
• Exploration-Enhanced POLITEX
• Improved Analysis of UCRL2 with Empirical Bernstein Inequality
• Sample Complexity of Reinforcement Learning using Linearly Combined Model Ensembles
• Adaptive Approximate Policy Iteration

Cited by in corpus (4)

• Understanding the Limits of Poisoning Attacks in Episodic Reinforcement Learning
• Reward-Free Model-Based Reinforcement Learning with Linear Function Approximation
• Regret Bounds for Stochastic Shortest Path Problems with Linear Function Approximation
• Near-Optimal Reward-Free Exploration for Linear Mixture MDPs with Plug-in Solver