Reinforcement Learning for Infinite-Horizon Average-Reward Linear MDPs via Approximation by Discounted-Reward MDPs

2024-05-23 · Kihyuk Hong, Woojin Chae, Yufan Zhang, Dabeen Lee, Ambuj Tewari

We study the infinite-horizon average-reward reinforcement learning with linear MDPs. 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 an algorithm that achieves the regret bound of $\widetilde{O}(\sqrt{T})$ and is computationally efficient in the sense that the time complexity is polynomial in problem parameters. Our algorithm runs an optimistic value iteration on a discounted-reward MDP that approximates the average-reward setting. With an appropriately tuned discounting factor $\gamma$, the algorithm attains the desired $\widetilde{O}(\sqrt{T})$ regret. The challenge in our approximation approach is to get a regret bound with a sharp dependency on the effective horizon $1 / (1 - \gamma)$. We address this challenge by clipping the value function obtained at each value iteration step to limit the span of the value function.

📄 PDF Abstract BibTeX arXiv:2405.15050

Code (0)

등록된 구현이 없습니다.

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 …

A Computationally Efficient Algorithm for Infinite-Horizon Average-Reward Linear MDPs

2025-04-16 · Kihyuk Hong, Ambuj Tewari

We study reinforcement learning in infinite-horizon average-reward settings with linear MDPs. Previous work addresses this problem by approximating the average-reward setting by discounted setting and employing a value i…

Provably Efficient Infinite-Horizon Average-Reward Reinforcement Learning with Linear Function Approximation

2024-09-16 · Woojin Chae, Dabeen Lee

This paper proposes a computationally tractable algorithm for learning infinite-horizon average-reward linear Markov decision processes (MDPs) and linear mixture MDPs under the Bellman optimality condition. While guarant…

Computational Efficiency

Offline Primal-Dual Reinforcement Learning for Linear MDPs

2023-05-22 · Germano Gabbianelli, Gergely Neu, Nneka Okolo, Matteo Papini

Offline Reinforcement Learning (RL) aims to learn a near-optimal policy from a fixed dataset of transitions collected by another policy. This problem has attracted a lot of attention recently, but most existing methods w…

Offline RL reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)+1

Infinite-Horizon Reinforcement Learning with Multinomial Logistic Function Approximation

2024-06-19 · JaeHyun Park, Junyeop Kwon, Dabeen Lee

We study model-based reinforcement learning with non-linear function approximation where the transition function of the underlying Markov decision process (MDP) is given by a multinomial logistic (MNL) model. We develop …

Model-based Reinforcement Learning reinforcement-learning Reinforcement Learning