Provably Efficient Infinite-Horizon Average-Reward Reinforcement Learning with Linear Function Approximation

2024/09/16 by Woojin Chae, Chae, Woojin, Dabeen Lee +1
Computer Science · Engineering · #Autonomous Vehicle Technology and Safety #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Optimization and Control (math.OC) #Reinforcement Learning in Robotics #Traffic control and management

paper · pdf · doi:10.48550/arxiv.2409.10772

openalex publication_date 2024/09/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

This paper proposes a computationally tractable algorithm for learning infinite-horizon average-reward linear Markov decision processes (MDPs) and linear mixture MDPs under the Bellman optimality condition. While guaranteeing computational efficiency, our algorithm for linear MDPs achieves the best-known regret upper bound of \widetildeO(d^3/2sp(v^*)√(T)) over T time steps where sp(v^*) is the span of the optimal bias function v^* and d is the dimension of the feature mapping. For linear mixture MDPs, our algorithm attains a regret bound of \widetildeO(d\cdotsp(v^*)√(T)). The algorithm applies novel techniques to control the covering number of the value function class and the span of optimistic estimators of the value function, which is of independent interest.

Related

• Reinforcement Learning for Infinite-Horizon Average-Reward Linear MDPs via Approximation by Discounted-Reward MDPs
• Learning Infinite-Horizon Average-Reward Linear Mixture MDPs of Bounded Span
• Learning Infinite-horizon Average-reward MDPs with Linear Function Approximation
• Nearly Minimax Optimal Regret for Learning Infinite-horizon Average-reward MDPs with Linear Function Approximation
• A Computationally Efficient Algorithm for Infinite-Horizon Average-Reward Linear MDPs