Model-free Reinforcement Learning In Infinite-horizon Average-reward Markov Decision Processes
2019 · Chen-Yu Wei, Mehdi Jafarnia-Jahromi, Haipeng Luo, et al.
Abstract
Model-free reinforcement learning is known to be memory and computation efficient and more amendable to large scale problems. In this paper, two model-free algorithms are introduced for learning infinite-horizon average-reward Markov Decision Processes (MDPs). The first algorithm reduces the problem to the discounted-reward version and achieves \(\mathcal\{O\}(T^\{2/3\})\) regret after \(T\) steps, under the minimal assumption of weakly communicating MDPs. To our knowledge, this is the first model-free algorithm for general MDPs in this setting. The second algorithm makes use of recent advances in adaptive algorithms for adversarial multi-armed bandits and improves the regret to \(\mathcal\{O\}(\sqrt\{T\})\), albeit with a stronger ergodic assumption. This result significantly improves over the \(\mathcal\{O\}(T^\{3/4\})\) regret achieved by the only existing model-free algorithm by Abbasi-Yadkori et al. (2019a) for ergodic MDPs in the infinite-horizon average-reward setting.
Authors
(none)
Tags
Stats
Related papers
- Sharper Model-free Reinforcement Learning For Average-reward Markov Decision Processes (2023)0.00
- A Model-free Learning Algorithm For Infinite-horizon Average-reward Mdps With Near-optimal Regret (2020)0.00
- Reinforcement Learning For Infinite-horizon Average-reward Linear Mdps Via Approximation By Discounted-reward Mdps (2024)0.00
- Regret-optimal Model-free Reinforcement Learning For Discounted Mdps With Short Burn-in Time (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
- Learning And Planning In Average-reward Markov Decision Processes (2020)0.00
- Model-free Reinforcement Learning: From Clipped Pseudo-regret To Sample Complexity (2020)0.00