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

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.

References in corpus (14)

• Playing Atari with Deep Reinforcement Learning
• Trust Region Policy Optimization
• REGAL: A Regularization based Algorithm for Reinforcement Learning in Weakly Communicating MDPs
• Online Learning with Predictable Sequences
• On the Theory of Policy Gradient Methods: Optimality, Approximation, and Distribution Shift
• Generalization and Exploration via Randomized Value Functions
• More Adaptive Algorithms for Adversarial Bandits
• Near Optimal Exploration-Exploitation in Non-Communicating Markov Decision Processes
• Minimax Regret Bounds for Reinforcement Learning
• Learning-based Control of Unknown Linear Systems with Thompson Sampling
• Primal-Dual $\pi$ Learning: Sample Complexity and Sublinear Run Time for Ergodic Markov Decision Problems
• Q-learning with UCB Exploration is Sample Efficient for Infinite-Horizon MDP
• Exploration-Enhanced POLITEX
• Improved Path-length Regret Bounds for Bandits

Cited by in corpus (6)

• Learning Adversarial MDPs with Bandit Feedback and Unknown Transition
• Reinforcement Learning for Non-Stationary Markov Decision Processes: The Blessing of (More) Optimism
• Finite-Time Analysis of Asynchronous Stochastic Approximation and $Q$-Learning
• Average-reward model-free reinforcement learning: a systematic review and literature mapping
• Upper Confidence Primal-Dual Reinforcement Learning for CMDP with Adversarial Loss
• Optimistic Policy Optimization with Bandit Feedback