A Model-free Learning Algorithm For Infinite-horizon Average-reward Mdps With Near-optimal Regret

Abstract

Recently, model-free reinforcement learning has attracted research attention due to its simplicity, memory and computation efficiency, and the flexibility to combine with function approximation. In this paper, we propose Exploration Enhanced Q-learning (EE-QL), a model-free algorithm for infinite-horizon average-reward Markov Decision Processes (MDPs) that achieves regret bound of \(O(\sqrt\{T\})\) for the general class of weakly communicating MDPs, where \(T\) is the number of interactions. EE-QL assumes that an online concentrating approximation of the optimal average reward is available. This is the first model-free learning algorithm that achieves \(O(\sqrt T)\) regret without the ergodic assumption, and matches the lower bound in terms of \(T\) except for logarithmic factors. Experiments show that the proposed algorithm performs as well as the best known model-based algorithms.

Stats

• citations0
• S2 citations—
• github stars0
• HF likes0
• heat score0.00
• arxiv keyjafarniajahromi2020a

Related papers

• Model-free Reinforcement Learning In Infinite-horizon Average-reward Markov Decision Processes (2019)0.00
• Sharper Model-free Reinforcement Learning For Average-reward Markov Decision Processes (2023)0.00
• Reinforcement Learning For Infinite-horizon Average-reward Linear Mdps Via Approximation By Discounted-reward Mdps (2024)0.00
• Decentralized Model-free Reinforcement Learning In Stochastic Games With Average-reward Objective (2023)0.00
• Logarithmic Regret Bounds For Continuous-time Average-reward Markov Decision Processes (2022)5.24
• Value-biased Maximum Likelihood Estimation For Model-based Reinforcement Learning In Discounted Linear Mdps (2023)0.00
• Logarithmic Regret Of Exploration In Average Reward Markov Decision Processes (2025)0.00
• A Provably-efficient Model-free Algorithm For Constrained Markov Decision Processes (2021)0.00