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

• URL: http://arxiv.org/abs/2409.10772v2
• Date: Tue, 24 Sep 2024 00:30:18 GMT
• Title: Provably Efficient Infinite-Horizon Average-Reward Reinforcement Learning with Linear Function Approximation
• Authors: Woojin Chae, Dabeen Lee,
• Abstract summary: We propose an algorithm for learning linear Markov decision processes (MDPs) and linear mixture MDPs under the Bellman optimality condition. Our algorithm for linear MDPs achieves the best-known regret upper bound of $widetildemathcalO(d3/2mathrmsp(v*)sqrtT)$ over $T$ time steps. For linear mixture MDPs, our algorithm attains a regret bound of $widetildemathcalO(dcdotmathrm
• Score: 1.8416014644193066
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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 guaranteeing computational efficiency, our algorithm for linear MDPs achieves the best-known regret upper bound of $\widetilde{\mathcal{O}}(d^{3/2}\mathrm{sp}(v^*)\sqrt{T})$ over $T$ time steps where $\mathrm{sp}(v^*)$ is the span of the optimal bias function $v^*$ and $d$ is the dimension of the feature mapping. For linear mixture MDPs, our algorithm attains a regret bound of $\widetilde{\mathcal{O}}(d\cdot\mathrm{sp}(v^*)\sqrt{T})$. The algorithm applies novel techniques to control the covering number of the value function class and the span of optimistic estimators of the value function, which is of independent interest.

Related papers

• Learning Infinite-Horizon Average-Reward Linear Mixture MDPs of Bounded Span [16.49229317664822]
  This paper proposes a computationally tractable algorithm for learning infinite-horizon average-reward linear mixture Markov decision processes (MDPs) Our algorithm for linear mixture MDPs achieves a nearly minimax optimal regret upper bound of $widetildemathcalO(dsqrtmathrmsp(v*)T)$ over $T$ time steps.
  arXiv  Detail & Related papers  (2024-10-19T05:45:50Z)
• Achieving Tractable Minimax Optimal Regret in Average Reward MDPs [19.663336027878408]
  We present the first tractable algorithm with minimax optimal regret of $widetildemathrmO(sqrtmathrmsp(h*) S A T)$. Remarkably, our algorithm does not require prior information on $mathrmsp(h*)$.
  arXiv  Detail & Related papers  (2024-06-03T11:53:44Z)
• Reinforcement Learning for Infinite-Horizon Average-Reward Linear MDPs via Approximation by Discounted-Reward MDPs [16.49229317664822]
  We study the infinite-horizon average-reward reinforcement learning with linear MDPs. In this paper, we propose that the regret bound of $widetildeO(sqrtT)$ achieves an algorithm that is computationally efficient.
  arXiv  Detail & Related papers  (2024-05-23T20:58:33Z)
• Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path [80.60592344361073]
  We study the Shortest Path (SSP) problem with a linear mixture transition kernel. An agent repeatedly interacts with a environment and seeks to reach certain goal state while minimizing the cumulative cost. Existing works often assume a strictly positive lower bound of the iteration cost function or an upper bound of the expected length for the optimal policy.
  arXiv  Detail & Related papers  (2024-02-14T07:52:00Z)
• Refined Regret for Adversarial MDPs with Linear Function Approximation [50.00022394876222]
  We consider learning in an adversarial Decision Process (MDP) where the loss functions can change arbitrarily over $K$ episodes. This paper provides two algorithms that improve the regret to $tildemathcal O(K2/3)$ in the same setting.
  arXiv  Detail & Related papers  (2023-01-30T14:37:21Z)
• Randomized Exploration for Reinforcement Learning with General Value Function Approximation [122.70803181751135]
  We propose a model-free reinforcement learning algorithm inspired by the popular randomized least squares value iteration (RLSVI) algorithm. Our algorithm drives exploration by simply perturbing the training data with judiciously chosen i.i.d. scalar noises. We complement the theory with an empirical evaluation across known difficult exploration tasks.
  arXiv  Detail & Related papers  (2021-06-15T02:23:07Z)
• Nearly Optimal Regret for Learning Adversarial MDPs with Linear Function Approximation [92.3161051419884]
  We study the reinforcement learning for finite-horizon episodic Markov decision processes with adversarial reward and full information feedback. We show that it can achieve $tildeO(dHsqrtT)$ regret, where $H$ is the length of the episode. We also prove a matching lower bound of $tildeOmega(dHsqrtT)$ up to logarithmic factors.
  arXiv  Detail & Related papers  (2021-02-17T18:54:08Z)
• Nearly Minimax Optimal Regret for Learning Infinite-horizon Average-reward MDPs with Linear Function Approximation [95.80683238546499]
  We propose a new algorithm UCRL2-VTR, which can be seen as an extension of the UCRL2 algorithm with linear function approximation. We show that UCRL2-VTR with Bernstein-type bonus can achieve a regret of $tildeO(dsqrtDT)$, where $d$ is the dimension of the feature mapping. We also prove a matching lower bound $tildeOmega(dsqrtDT)$, which suggests that the proposed UCRL2-VTR is minimax optimal up to logarithmic factors
  arXiv  Detail & Related papers  (2021-02-15T02:08:39Z)
• Learning Infinite-horizon Average-reward MDPs with Linear Function Approximation [44.374427255708135]
  We develop new algorithms for learning Markov Decision Processes in an infinite-horizon average-reward setting with linear function approximation. Using the optimism principle and assuming that the MDP has a linear structure, we first propose a computationally inefficient algorithm with optimal $widetildeO(sqrtT)$ regret. Next, taking inspiration from adversarial linear bandits, we develop yet another efficient algorithm with $widetildeO(sqrtT)$ regret.
  arXiv  Detail & Related papers  (2020-07-23T08:23:44Z)
• Provably Efficient Reinforcement Learning for Discounted MDPs with Feature Mapping [99.59319332864129]
  In this paper, we study reinforcement learning for discounted Decision (MDP) We propose a novel algorithm that makes use of the feature mapping and obtains a $tilde O(dsqrtT/ (1-gamma)2)$ regret. Our upper and lower bound results together suggest that the proposed reinforcement learning algorithm is near-optimal up to a $ (1-gamma)-0.5$ factor.
  arXiv  Detail & Related papers  (2020-06-23T17:08:54Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.