A Model-free Learning Algorithm for Infinite-horizon Average-reward MDPs with Near-optimal Regret

2020-06-08 · Mehdi Jafarnia-Jahromi, Chen-Yu Wei, Rahul Jain, Haipeng Luo

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.

📄 PDF Abstract BibTeX arXiv:2006.04354

Code (0)

등록된 구현이 없습니다.

Tasks

Q-Learningreinforcement-learning Reinforcement Learning (RL)

Methods 이 논문이 사용한 방법론

Q-Learning Q-Learning is an off-policy temporal difference control algorithm: $$Q\left(S\_{t}, A\_{t}\right) \leftarrow Q\left(S\_{t}, A\_{t}\right) + \alpha\left[R_{t+1} +…

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

2019-10-15 · ICML 2020 1 · Chen-Yu Wei, Mehdi Jafarnia-Jahromi, Haipeng Luo, Hiteshi Sharma 외

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-…

Multi-Armed Bandits reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)

A Harmonic Mean Formulation of Average Reward Reinforcement Learning in SMDPs

2026-05-06 · Erel Shtossel, Alicia Vidler, Uri Shaham, Gal A. Kaminka arxiv

Recent research has revived and amplified interest in algorithms for undiscounted average reward reinforcement learning in infinite-horizon, non-episodic (continuing) tasks. Semi-Markov decision processes (SMDPs) are of …

Reinforcement Learning

Nearly Minimax Optimal Regret for Learning Infinite-horizon Average-reward MDPs with Linear Function Approximation

2021-02-15 · Yue Wu, Dongruo Zhou, Quanquan Gu

We study reinforcement learning in an infinite-horizon average-reward setting with linear function approximation, where the transition probability function of the underlying Markov Decision Process (MDP) admits a linear …

Policy Zooming: Adaptive Discretization-based Infinite-Horizon Average-Reward Reinforcement Learning

2024-05-29 · Avik Kar, Rahul Singh

We study Lipschitz MDPs in the infinite-horizon average-reward reinforcement learning (RL) setup in which an agent can play policies from a given set $\Phi$. The proposed algorithms ``zoom'' into ``promising'' regions of…

reinforcement-learning Reinforcement Learning (RL)

Regret Analysis of Policy Gradient Algorithm for Infinite Horizon Average Reward Markov Decision Processes

2023-09-05 · Qinbo Bai, Washim Uddin Mondal, Vaneet Aggarwal

In this paper, we consider an infinite horizon average reward Markov Decision Process (MDP). Distinguishing itself from existing works within this context, our approach harnesses the power of the general policy gradient-…