Fitted Q-Iteration (FQI) Approaches

Fitted Q-Iteration (FQI) is an early and intuitive approach for learning from fixed datasets, adapting ideas from online learning. It extends the primary idea behind Q-learning and Value Iteration to the offline, batch setting. Instead of updating Q-values one transition at a time, FQI treats the problem as a sequence of supervised learning tasks, using the entire available dataset $\mathcal{D} = \{(s_i, a_i, r_i, s'_i)\}_{i=1}^N$ at each step.

The fundamental goal remains the same: estimate the optimal action-value function $Q^*(s, a)$. FQI achieves this iteratively. We start with an initial Q-function estimate, often simply $\hat{Q}_0(s, a) = 0$ for all $s, a$. Then, for each iteration $k = 1, 2, \dots, K$:

1. Generate Targets: Using the Q-function estimate from the previous iteration, $\hat{Q}_{k-1}$, we compute target values $y_i$ for each state-action pair $(s_i, a_i)$ present in our static dataset $\mathcal{D}$. The target is derived from the Bellman optimality equation, using the observed reward $r_i$ and the estimated maximum value achievable from the next state $s'_i$:

   $$y_i = r_i + \gamma \max_{a'} \hat{Q}_{k-1}(s'_i, a')$$

   This creates a target dataset $\{( (s_i, a_i), y_i )\}_{i=1}^N$. Note that the target $y_i$ uses the fixed data $(r_i, s'_i)$ but relies on the previous Q-function estimate $\hat{Q}_{k-1}$.

2. Supervised Learning: We train a function approximator (our new Q-function estimate $\hat{Q}_k$) to minimize the difference between its predictions $\hat{Q}_k(s_i, a_i)$ and the calculated targets $y_i$. This is effectively a standard regression problem over the dataset pairs generated in step 1. The objective is typically the Mean Squared Error (MSE):

   $$\hat{Q}_k = \arg \min_Q \sum_{i=1}^N \left( Q(s_i, a_i) - y_i \right)^2$$ $$\hat{Q}_k = \arg \min_Q \sum_{i=1}^N \left( Q(s_i, a_i) - \left(r_i + \gamma \max_{a'} \hat{Q}_{k-1}(s'_i, a')\right) \right)^2$$

3. Repeat: The newly trained $\hat{Q}_k$ becomes the input for generating targets in the next iteration ($k+1$). This process repeats for a predetermined number of iterations $K$, or until the changes in the Q-function estimates become sufficiently small.

Function Approximators in FQI

A significant aspect of FQI is its flexibility regarding the choice of function approximator for $Q(s, a)$. Since each iteration boils down to a supervised regression task, any suitable regressor can be employed. Historically, non-parametric methods like tree ensembles (Random Forests, Gradient Boosting Trees) were often used due to their effectiveness in capturing complex functions without extensive hyperparameter tuning. However, deep neural networks can also be used, turning FQI into "Neural Fitted Q-Iteration" (NFQ), blurring the lines somewhat with DQN but maintaining the distinct iterative batch-fitting procedure.

Strengths of FQI

• Simplicity: It directly adapts the familiar Bellman updates to a batch setting.
• Uses Supervised Learning: It allows utilizing powerful, off-the-shelf regression algorithms.
• Purely Offline: It operates entirely on the provided static dataset without needing further environment interaction.

The Achilles' Heel: Distributional Shift

Despite its appeal, FQI often struggles in practice within the offline setting precisely because of distributional shift. The core issue lies in the target calculation step: $y_i = r_i + \gamma \max_{a'} \hat{Q}_{k-1}(s'_i, a')$.

• The Maximization Operator: The $\max_{a'}$ term requires evaluating the Q-function $\hat{Q}_{k-1}$ for potentially many actions $a'$ in the next state $s'_i$.
• Out-of-Distribution Actions: The dataset $\mathcal{D}$ was generated by a specific behavior policy $\pi_b$. It's highly likely that the actions $a'$ that maximize $\hat{Q}_{k-1}(s'_i, a')$ are different from the actions typically taken by $\pi_b$ in state $s'_i$. These maximizing actions might be poorly represented or entirely absent in the training data for state $s'_i$.
• Error Propagation: Consequently, the estimate $\hat{Q}_{k-1}(s'_i, a')$ for such out-of-distribution (OOD) actions can be highly inaccurate. Standard supervised learning regressors provide no guarantees on their output for inputs far from the training distribution. These errors in the target values $y_i$ are then baked into the training objective for the next Q-function $\hat{Q}_k$. Errors can thus propagate and compound across iterations, potentially leading to divergence or significantly overestimated Q-values for OOD actions, resulting in a poor final policy.

Consider a simple visualization of this issue:

The FQI process relies on estimating the maximum Q-value in the next state ($s'_i$) using the previous Q-function ($Q_{k-1}$). However, the action $a'$ yielding this maximum might be out-of-distribution relative to the actions present in the dataset $\mathcal{D}$ for state $s'_i$. This leads to potentially unreliable estimates feeding back into the target calculation, causing error propagation.

FQI, therefore, represents an important baseline but fundamentally lacks mechanisms to explicitly combat the distributional shift problem. It operates under the implicit, often incorrect, assumption that the function approximator will generalize reasonably well even to state-action pairs unseen or rare in the data. This limitation motivates the development of methods specifically designed for the offline setting, such as the policy constraint and value regularization techniques we will discuss next, which aim to mitigate the risks associated with querying OOD actions.