mlsanityData to 7 Oct 2026

Fitted Q-Iteration via Max-Plus-Linear Approximation

arXiv 2409.08422 ↗First posted 12 Sep 2024math.OC cs.AI cs.LGcited by 0

On the map: Offline RL and imitation learning from data → Offline RL algorithms

Abstract (arXiv)

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.

Key facts. No citing papers in the map yet (data through 7 Oct 2026). Placed in Offline RL algorithms, one of 13 directions in Offline RL and imitation learning from data. Builds on 5 of its 32 references that are in the map. First posted on arXiv 12 Sep 2024.

Builds on

5 of 32 references.

References · 5

  1. 2015End-to-End Training of Deep Visuomotor Policiescited by 847
  2. 2019Learning When-to-Treat Policiescited by 49
  3. 2018Market Making via Reinforcement Learningcited by 45
  4. 2020Fast Approximate Dynamic Programming for Input-Affine Dynamicscited by 3
  5. 2020Sparse Approximate Solutions to Max-Plus Equations with Application to Multivariate Convex Regressioncited by 1

Built on by

Not cited yet.

Similar, not cited

Close in wording, no citation either way

  1. 2025Soft Fitted Q-Iteration without Bellman Completeness: Occupancy Reweighting and Temperature Annealing
  2. 2021Approximated Multi-Agent Fitted Q Iteration
  3. 2026Finite-Sample Theory for Fitted Q-Iteration When Actions Are Functions
  4. 2020Q* Approximation Schemes for Batch Reinforcement Learning: A Theoretical Comparison
  5. 2022Offline Reinforcement Learning with Differentiable Function Approximation is Provably Efficient
  6. 2022Nearly Minimax Optimal Offline Reinforcement Learning with Linear Function Approximation: Single-Agent MDP and Markov Game
  7. 2023Pessimistic Nonlinear Least-Squares Value Iteration for Offline Reinforcement Learning
  8. 2021Fast Rates for the Regret of Offline Reinforcement Learning