Model-free Reinforcement Learning in Infinite-horizon Average-reward Markov Decision Processes

2019/10/15 by Chen-Yu Wei, Mehdi Jafarnia-Jahromi, Wei, Chen-Yu +7 · 2 citations
Computer Science · Decision Sciences · #Advanced Bandit Algorithms Research #Age of Information Optimization #Artificial Intelligence (cs.AI) #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Reinforcement Learning in Robotics

paper · pdf · doi:10.48550/arxiv.1910.07072

openalex publication_date 2019/10/15 · openalex created_date 2019/10/25 · openalex updated_date 2026/07/28

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 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 O(√(T)), albeit with a stronger ergodic assumption. This result significantly improves over the 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.

Citations

• Generalization and Exploration via Randomized Value Functions
• REGAL: A Regularization based Algorithm for Reinforcement Learning in Weakly Communicating MDPs
• The Nonstochastic Multiarmed Bandit Problem
• Minimax Regret Bounds for Reinforcement Learning
• Improved Path-length Regret Bounds for Bandits
• Regret Minimization for Reinforcement Learning by Evaluating the Optimal Bias Function

Cited by

• Finite-Time Bounds for Average-Reward Fitted Q-Iteration
• Learning Adversarial MDPs with Bandit Feedback and Unknown Transition

Related

• Sharper Model-free Reinforcement Learning for Average-reward Markov Decision Processes
• A Model-free Learning Algorithm for Infinite-horizon Average-reward MDPs with Near-optimal Regret
• Reinforcement Learning for Infinite-Horizon Average-Reward Linear MDPs via Approximation by Discounted-Reward MDPs
• Learning Infinite-horizon Average-reward MDPs with Linear Function Approximation
• Provably Efficient Infinite-Horizon Average-Reward Reinforcement Learning with Linear Function Approximation