Reinforcement Learning For Infinite-horizon Average-reward Linear Mdps Via Approximation By Discounted-reward Mdps

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 \(\widetilde\{O\}(\sqrt\{T\})\). In this paper, we propose the first algorithm that achieves \(\widetilde\{O\}(\sqrt\{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

Stats

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

Related papers

• Value-biased Maximum Likelihood Estimation For Model-based Reinforcement Learning In Discounted Linear Mdps (2023)0.00
• Model-free Reinforcement Learning In Infinite-horizon Average-reward Markov Decision Processes (2019)0.00
• Logarithmic Regret Bounds For Continuous-time Average-reward Markov Decision Processes (2022)5.24
• Nearly Minimax Optimal Reinforcement Learning For Linear Markov Decision Processes (2022)0.00
• Optimal Horizon-free Reward-free Exploration For Linear Mixture Mdps (2023)0.00
• Sharper Model-free Reinforcement Learning For Average-reward Markov Decision Processes (2023)0.00
• Learning General Parameterized Policies For Infinite Horizon Average Reward Constrained Mdps Via Primal-dual Policy Gradient Algorithm (2024)0.00
• A Model-free Learning Algorithm For Infinite-horizon Average-reward Mdps With Near-optimal Regret (2020)0.00