Fitted Q-Iteration via Max-Plus-Linear Approximation

• URL: http://arxiv.org/abs/2409.08422v1
• Date: Thu, 12 Sep 2024 22:51:08 GMT
• Title: Fitted Q-Iteration via Max-Plus-Linear Approximation
• Authors: Y. Liu, M. A. S. Kolarijani,
• Abstract summary: In particular, we incorporate these approximators to propose novel fitted Q-iteration (FQI) algorithms with provable convergence. We show that the max-plus-linear regression within each iteration of the proposed FQI algorithm reduces to simple max-plus matrix-vector multiplications.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this study, we consider the application of max-plus-linear approximators for Q-function in offline reinforcement learning of discounted Markov decision processes. In particular, we incorporate these approximators to propose novel fitted Q-iteration (FQI) algorithms with provable convergence. Exploiting the compatibility of the Bellman operator with max-plus operations, we show that the max-plus-linear regression within each iteration of the proposed FQI algorithm reduces to simple max-plus matrix-vector multiplications. We also consider the variational implementation of the proposed algorithm which leads to a per-iteration complexity that is independent of the number of samples.

Related papers

• Single-loop Algorithms for Stochastic Non-convex Optimization with Weakly-Convex Constraints [49.76332265680669]
  This paper examines a crucial subset of problems where both the objective and constraint functions are weakly convex. Existing methods often face limitations, including slow convergence rates or reliance on double-loop designs. We introduce a novel single-loop penalty-based algorithm to overcome these challenges.
  arXiv  Detail & Related papers  (2025-04-21T17:15:48Z)
• Q-learning for Quantile MDPs: A Decomposition, Performance, and Convergence Analysis [30.713243690224207]
  In Markov decision processes (MDPs), quantile risk measures such as Value-at-Risk are a standard metric for modeling RL agents' preferences for certain outcomes. This paper proposes a new Q-learning algorithm for quantile optimization in MDPs with strong convergence and performance guarantees.
  arXiv  Detail & Related papers  (2024-10-31T16:53:20Z)
• Regularized Q-Learning with Linear Function Approximation [2.765106384328772]
  We consider a bi-level optimization formulation of regularized Q-learning with linear functional approximation. We show that, under certain assumptions, the proposed algorithm converges to a stationary point in the presence of Markovian noise.
  arXiv  Detail & Related papers  (2024-01-26T20:45:40Z)
• Pointer Networks with Q-Learning for Combinatorial Optimization [55.2480439325792]
  We introduce the Pointer Q-Network (PQN), a hybrid neural architecture that integrates model-free Q-value policy approximation with Pointer Networks (Ptr-Nets) Our empirical results demonstrate the efficacy of this approach, also testing the model in unstable environments.
  arXiv  Detail & Related papers  (2023-11-05T12:03:58Z)
• Federated Conditional Stochastic Optimization [110.513884892319]
  Conditional optimization has found in a wide range of machine learning tasks, such as in-variant learning tasks, AUPRC, andAML. This paper proposes algorithms for distributed federated learning.
  arXiv  Detail & Related papers  (2023-10-04T01:47:37Z)
• An Efficient Algorithm for Clustered Multi-Task Compressive Sensing [60.70532293880842]
  Clustered multi-task compressive sensing is a hierarchical model that solves multiple compressive sensing tasks. The existing inference algorithm for this model is computationally expensive and does not scale well in high dimensions. We propose a new algorithm that substantially accelerates model inference by avoiding the need to explicitly compute these covariance matrices.
  arXiv  Detail & Related papers  (2023-09-30T15:57:14Z)
• Adaptive Stochastic Optimisation of Nonconvex Composite Objectives [2.1700203922407493]
  We propose and analyse a family of generalised composite mirror descent algorithms. With adaptive step sizes, the proposed algorithms converge without requiring prior knowledge of the problem. We exploit the low-dimensional structure of the decision sets for high-dimensional problems.
  arXiv  Detail & Related papers  (2022-11-21T18:31:43Z)
• On the Global Convergence of Fitted Q-Iteration with Two-layer Neural Network Parametrization [33.12181620473604]
  We study a Fitted Q-Iteration with two-layer ReLU neural network parametrization, and find the sample complexity guarantees for the algorithm. We show that this approach achieves a sample complexity of $tildemathcalO (1/epsilon2)$, which is order-optimal.
  arXiv  Detail & Related papers  (2022-11-14T19:00:24Z)
• Parallel Stochastic Mirror Descent for MDPs [72.75921150912556]
  We consider the problem of learning the optimal policy for infinite-horizon Markov decision processes (MDPs) Some variant of Mirror Descent is proposed for convex programming problems with Lipschitz-continuous functionals. We analyze this algorithm in a general case and obtain an estimate of the convergence rate that does not accumulate errors during the operation of the method.
  arXiv  Detail & Related papers  (2021-02-27T19:28:39Z)
• Geom-SPIDER-EM: Faster Variance Reduced Stochastic Expectation Maximization for Nonconvex Finite-Sum Optimization [21.81837334970773]
  We propose an extension of the Path-Integrated Differential Estima to the Expectation Maximization (EM) algorithm. We show it supports the same state art bounds as SPIDER-EM-IDER; and results provide for a rate for our findings.
  arXiv  Detail & Related papers  (2020-11-24T21:20:53Z)
• Efficient Methods for Structured Nonconvex-Nonconcave Min-Max Optimization [98.0595480384208]
  We propose a generalization extraient spaces which converges to a stationary point. The algorithm applies not only to general $p$-normed spaces, but also to general $p$-dimensional vector spaces.
  arXiv  Detail & Related papers  (2020-10-31T21:35:42Z)
• Momentum Q-learning with Finite-Sample Convergence Guarantee [49.38471009162477]
  This paper analyzes a class of momentum-based Q-learning algorithms with finite-sample guarantee. We establish the convergence guarantee for MomentumQ with linear function approximations and Markovian sampling. We demonstrate through various experiments that the proposed MomentumQ outperforms other momentum-based Q-learning algorithms.
  arXiv  Detail & Related papers  (2020-07-30T12:27:03Z)

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.