Reinforcement Learning for Infinite-Horizon Average-Reward Linear MDPs via Approximation by Discounted-Reward MDPs

2024/05/23 by Hong, Kihyuk, Chae, Woojin, Zhang, Yufan +2
#FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML)

paper · doi:10.48550/arxiv.2405.15050

Abstract

We study the problem of infinite-horizon average-reward reinforcement learning with linear Markov decision processes (MDPs). The associated Bellman operator of the problem not being a contraction makes the algorithm design challenging. Previous approaches either suffer from computational inefficiency or require strong assumptions on dynamics, such as ergodicity, for achieving a regret bound of \widetildeO(√(T)). In this paper, we propose the first algorithm that achieves \widetildeO(√(T)) regret with computational complexity polynomial in the problem parameters, without making strong assumptions on dynamics. Our approach approximates the average-reward setting by a discounted MDP with a carefully chosen discounting factor, and then applies an optimistic value iteration. We propose an algorithmic structure that plans for a nonstationary policy through optimistic value iteration and follows that policy until a specified information metric in the collected data doubles. Additionally, we introduce a value function clipping procedure for limiting the span of the value function for sample efficiency.

Related

• Provably Efficient Infinite-Horizon Average-Reward Reinforcement Learning with Linear Function Approximation
• A Computationally Efficient Algorithm for Infinite-Horizon Average-Reward Linear MDPs
• Learning Infinite-horizon Average-reward MDPs with Linear Function Approximation
• Model-free Reinforcement Learning in Infinite-horizon Average-reward Markov Decision Processes
• Nearly Minimax Optimal Regret for Learning Infinite-horizon Average-reward MDPs with Linear Function Approximation