# Fitted Q-Iteration via Max-Plus-Linear Approximation

arXiv: https://arxiv.org/abs/2409.08422 · HTML: https://mlsanity.com/paper/2409.08422/

## Key facts

- Cited by 1 papers in the map (data through 14 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.

## Placed in

- Offline RL and imitation learning from data / [Offline RL algorithms](https://mlsanity.com/offlinerl/offline-rl-algorithms/)

## Builds on (most cited first, 5 of 5)

- [End-to-End Training of Deep Visuomotor Policies](https://mlsanity.com/paper/1504.00702/) (2015)
- [Learning When-to-Treat Policies](https://mlsanity.com/paper/1905.09751/) (2019)
- [Market Making via Reinforcement Learning](https://mlsanity.com/paper/1804.04216/) (2018)
- [Fast Approximate Dynamic Programming for Input-Affine Dynamics](https://mlsanity.com/paper/2008.10362/) (2020)
- [Sparse Approximate Solutions to Max-Plus Equations with Application to Multivariate Convex Regression](https://mlsanity.com/paper/2011.04468/) (2020)

## Built on by (most cited first, 1 of 1)

- [Control and Reinforcement Learning through the Lens of Optimization: An Algorithmic Perspective](https://mlsanity.com/paper/2512.07377/) (2025)

## 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.