Fitted Q-Iteration via Max-Plus-Linear Approximation

Y. Liu, Mohamad Amin Sharifi KolarijaniIEEE Control. Syst. Lett 2024

TL;DR

This paper introduces novel Fitted Q-Iteration (FQI) algorithms for offline reinforcement learning that leverage max-plus-linear approximations. These new methods offer provable convergence guarantees, a significant improvement over standard FQI, and introduce a variational approach that achieves per-iteration computational complexity independent of the number of samples.

What Problem Does This Paper Address?

Reinforcement learning (RL) aims to train agents to make sequential decisions that maximize cumulative rewards. Offline RL, a crucial sub-field, focuses on learning policies from pre-collected datasets, which is vital when online interaction is costly or risky. A standard algorithm for offline RL is Fitted Q-Iteration (FQI), which approximates the Q-function (state-action value function) and iteratively updates it. However, a major drawback of FQI is its lack of guaranteed convergence, even for simple problems with linear function approximators. This paper addresses this convergence issue by proposing a new class of FQI algorithms that utilize max-plus-linear approximators, a framework known for its compatibility with Bellman operators.

Methods

The core innovation lies in applying max-plus-linear (MP-linear) approximation to the Q-function within the FQI framework. MP-linear functions are characterized by replacing standard addition and multiplication with maximum and addition operations, respectively. This choice is motivated by the fact that the Bellman operator exhibits desirable properties in the max-plus algebra.

The paper proposes two main algorithms:

  • MP-FQI (Algorithm 1): This algorithm directly uses MP-linear approximation for the Q-function. The key insight is that the MP-linear regression problem in each iteration simplifies to a max-plus matrix-vector multiplication. This algorithm is shown to converge linearly with a per-iteration complexity of O(np), where 'n' is the number of samples and 'p' is the number of parameters.
  • Variational MP-FQI (v-MP-FQI) (Algorithm 2): Inspired by variational formulations of optimal control problems, this algorithm reformulates the problem using a set of test functions. This leads to a per-iteration complexity of O(pq), where 'q' is the number of test functions, which is independent of the sample size 'n'. This is a significant advantage for large datasets.

Both algorithms are built upon MP-linear regression techniques, which are adapted to solve the empirical Bellman equation. The convergence analysis relies on showing that the operators involved are contractions in the max-plus algebra.

Datasets

The paper uses a standard DC motor stabilization problem dataset, adapted from a previous work [7]. The dataset consists of 5000 state-action pairs generated uniformly at random. This dataset is used for evaluating the performance of the proposed algorithms against a standard FQI.

Key Insights and Ideas

  • Max-Plus Algebra for RL: The paper demonstrates the effectiveness of applying max-plus algebra to reinforcement learning, specifically for Q-function approximation in FQI. This is a novel application that leverages the inherent structure of the Bellman operator.
  • Provable Convergence: By using MP-linear approximators, the authors achieve provable convergence guarantees for FQI, overcoming a major limitation of existing methods.
  • Computational Efficiency: The variational approach (v-MP-FQI) offers a significant computational advantage by making the per-iteration complexity independent of the sample size, which is crucial for large-scale problems.
  • Simplified Regression: The MP-linear nature of the approximation simplifies the regression step in FQI to efficient max-plus matrix-vector operations.

Key Results

  • Convergence: Both MP-FQI and v-MP-FQI algorithms are shown to converge linearly with a rate less than the discount factor γ.
  • Performance: Numerical experiments on the DC motor stabilization problem show that the proposed MP-FQI and v-MP-FQI algorithms consistently outperform the standard FQI in terms of the quality of the greedy policy.
  • Complexity:
    • MP-FQI has a per-iteration complexity of O(np).
  • v-MP-FQI has a per-iteration complexity of O(pq), independent of the sample size 'n'.
  • Compilation time for MP-FQI is O(np), and for v-MP-FQI is O(npq).
  • Comparison: The paper highlights that while standard FQI with linear approximation is not guaranteed to converge, the proposed MP-based methods offer this crucial guarantee.

Limitations and Future Work

  • Lack of Error Analysis: The authors acknowledge that a theoretical bound on the distance between the output of their algorithms and the optimal Q-function is missing. They suggest that this could be addressed by bounding the error introduced in solving the MP-linear regression problem.
  • Problem Class Identification: Further work is needed to identify the specific classes of problems (e.g., MDPs with certain transition kernels and reward functions) for which optimal value functions can be well-represented by MP-linear function spaces.
  • Numerical Efficiency Extensions: The paper suggests exploring combinations with fast numerical algorithms for discrete conjugate or distance transforms to further reduce computation costs, especially for factorized samples or features.
  • Sparse Solutions: Applying sparse approximate solutions to MP-linear equations is proposed as an extension to control approximation size and reduce memory/time complexity.

Summary updated

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.
BibTeX
@article{liu2024fitted,
  author = {Y. Liu and Mohamad Amin Sharifi Kolarijani},
  title = {{Fitted Q-Iteration via Max-Plus-Linear Approximation}},
  journal = {IEEE Control. Syst. Lett.},
  year = {2024},
}
Figure