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

• URL: http://arxiv.org/abs/2504.11997v1
• Date: Wed, 16 Apr 2025 11:47:41 GMT
• Title: A Computationally Efficient Algorithm for Infinite-Horizon Average-Reward Linear MDPs
• Abstract summary: We study reinforcement learning in infinite-horizon average-reward settings with linear MDPs.<n>Previous work addresses this problem by approximating the average-reward setting by discounted setting and employing a value-based algorithm that uses clipping to constrain the span of the value iteration function for improved statistical efficiency.<n>In this paper, we introduce a value iteration method with efficient clipping operation that only requires computing the minimum of value functions over the set of states visited by the algorithm.
• Score: 18.449996575976993
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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 iteration-based algorithm that uses clipping to constrain the span of the value function for improved statistical efficiency. However, the clipping procedure requires computing the minimum of the value function over the entire state space, which is prohibitive since the state space in linear MDP setting can be large or even infinite. In this paper, we introduce a value iteration method with efficient clipping operation that only requires computing the minimum of value functions over the set of states visited by the algorithm. Our algorithm enjoys the same regret bound as the previous work while being computationally efficient, with computational complexity that is independent of the size of the state space.

Related papers

• End-to-End Efficient RL for Linear Bellman Complete MDPs with Deterministic Transitions [66.17960480460185]
  We study reinforcement learning with linear function approximation in Decision Processes (MDPs)<n>We provide a computationally efficient algorithm for linear Bellman complete oracles with emphdeterministic transitions, initial states, and rewards.
  arXiv  Detail & Related papers  (2026-03-24T17:32:29Z)
• 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)
• Provably Efficient Infinite-Horizon Average-Reward Reinforcement Learning with Linear Function Approximation [1.8416014644193066]
  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
  arXiv  Detail & Related papers  (2024-09-16T23:13:42Z)
• Computationally Efficient RL under Linear Bellman Completeness for Deterministic Dynamics [39.07258580928359]
  We study computationally and statistically efficient Reinforcement Learning algorithms for the linear Bellman Complete setting.<n>This setting uses linear function approximation to capture value functions and unifies existing models like linear Markov Decision Processes (MDP) and Linear Quadratic Regulators (LQR)<n>Our work provides a computationally efficient algorithm for the linear Bellman complete setting that works for MDPs with large action spaces, random initial states, and random rewards but relies on the underlying dynamics to be deterministic.
  arXiv  Detail & Related papers  (2024-06-17T17:52:38Z)
• Reinforcement Learning for Infinite-Horizon Average-Reward Linear MDPs via Approximation by Discounted-Reward MDPs [16.49229317664822]
  We study the problem of infinite-horizon average-reward reinforcement learning with linear decision processes (MDPs) Our approach approximates the average-reward setting by a discounted discounting factor, then applies an optimistic value iteration.
  arXiv  Detail & Related papers  (2024-05-23T20:58:33Z)
• Provably Efficient Reinforcement Learning via Surprise Bound [66.15308700413814]
  We propose a provably efficient reinforcement learning algorithm (both computationally and statistically) with general value function approximations. Our algorithm achieves reasonable regret bounds when applied to both the linear setting and the sparse high-dimensional linear setting.
  arXiv  Detail & Related papers  (2023-02-22T20:21:25Z)
• Linearized Wasserstein dimensionality reduction with approximation guarantees [65.16758672591365]
  LOT Wassmap is a computationally feasible algorithm to uncover low-dimensional structures in the Wasserstein space. We show that LOT Wassmap attains correct embeddings and that the quality improves with increased sample size. We also show how LOT Wassmap significantly reduces the computational cost when compared to algorithms that depend on pairwise distance computations.
  arXiv  Detail & Related papers  (2023-02-14T22:12:16Z)
• Nearly Minimax Optimal Reinforcement Learning for Linear Markov Decision Processes [80.89852729380425]
  We propose the first computationally efficient algorithm that achieves the nearly minimax optimal regret $tilde O(dsqrtH3K)$. Our work provides a complete answer to optimal RL with linear MDPs, and the developed algorithm and theoretical tools may be of independent interest.
  arXiv  Detail & Related papers  (2022-12-12T18:58:59Z)
• Efficient Dataset Distillation Using Random Feature Approximation [109.07737733329019]
  We propose a novel algorithm that uses a random feature approximation (RFA) of the Neural Network Gaussian Process (NNGP) kernel. Our algorithm provides at least a 100-fold speedup over KIP and can run on a single GPU. Our new method, termed an RFA Distillation (RFAD), performs competitively with KIP and other dataset condensation algorithms in accuracy over a range of large-scale datasets.
  arXiv  Detail & Related papers  (2022-10-21T15:56:13Z)
• Computational-Statistical Gaps in Reinforcement Learning [23.517741855454044]
  We show a reduction from Unique-Sat, where we convert a CNF formula into an MDP Hypothesis with deterministic transitions, constant number of actions and low dimensional linear optimal value functions. This result also exhibits the first computational-statistical gap in reinforcement learning with linear function approximation.
  arXiv  Detail & Related papers  (2022-02-11T04:48:35Z)
• Average-Reward Off-Policy Policy Evaluation with Function Approximation [66.67075551933438]
  We consider off-policy policy evaluation with function approximation in average-reward MDPs. bootstrapping is necessary and, along with off-policy learning and FA, results in the deadly triad. We propose two novel algorithms, reproducing the celebrated success of Gradient TD algorithms in the average-reward setting.
  arXiv  Detail & Related papers  (2021-01-08T00:43:04Z)
• Aligning Partially Overlapping Point Sets: an Inner Approximation Algorithm [80.15123031136564]
  We propose a robust method to align point sets where there is no prior information about the value of the transformation. Our algorithm does not need regularization on transformation, and thus can handle the situation where there is no prior information about the values of the transformations. Experimental results demonstrate the better robustness of the proposed method over state-of-the-art algorithms.
  arXiv  Detail & Related papers  (2020-07-05T15:23:33Z)

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.