Fitted Q-Iteration and the CartPole Simulation
Ruoqing Zhu
Last Updated: October 23, 2026
1 From Bellman Backups to Sampled Updates
In the Bellman lecture, we computed expectations using a known transition model. What changes when we only observe transitions? For one observed transition \((S_t,A_t,R_t,S_{t+1},D_t)\), where \(D_t=1\) indicates termination, we can replace the expectation by a sampled target. For policy evaluation, the one-step temporal-difference (TD) update is
\[ \begin{aligned} \delta_t &= R_t+\gamma(1-D_t)\hat V(S_{t+1})-\hat V(S_t),\\ \hat V(S_t)&\leftarrow \hat V(S_t)+\alpha_t\delta_t. \end{aligned} \]
Here the actions are generated by the policy being evaluated, and \(\alpha_t\) is a step size. We use the current value estimate for the unobserved future, which is called bootstrapping. For example, if the current value is 2, the reward is 1, the next value is 3, \(\gamma=0.9\), and the transition is nonterminal, then the sampled target is 3.7. A step size of 0.1 moves the current estimate from 2 to 2.17.
For control, Q-learning replaces the next value by the largest estimated action value:
\[ \begin{aligned} \delta_t &= R_t+\gamma(1-D_t)\max_{a'}\hat Q(S_{t+1},a')-\hat Q(S_t,A_t),\\ \hat Q(S_t,A_t)&\leftarrow \hat Q(S_t,A_t)+\alpha_t\delta_t. \end{aligned} \]
The behavior policy chooses the observed action \(A_t\), while the target uses a greedy next action. Thus Q-learning is off-policy: the behavior and target policies can differ. This does not describe when data are collected. In online learning, the agent collects new transitions while learning; in offline learning, it must reuse a fixed dataset. Q-learning can use online data while remaining off-policy. Learning from a fixed batch additionally depends on whether that batch covers the states and actions the learned policy needs.
These sampled updates explain how to learn without a transition model, but a table still cannot represent every continuous state. Fitted Q-iteration uses the same sampled target and replaces a table update by a regression fit over the batch.
2 Fitted Q-Iteration
Up to now, there are several components that we have not really dealt with:
- When the state space (and possibly the action space) is large or continuous, it is infeasible to represent the value function or Q-function exactly. We need to use function approximation to represent elements in the Bellman equation.
- In many practical scenarios, the transition dynamics are unknown, and may also be difficult to estimate. Hence, can we perform the Bellman operator without estimating the transition kernel?1
- In most medical applications (and many other human related studies), we cannot interact with the environment to collect new data. Instead, we only have a fixed batch of historical data. How can we perform policy evaluation and policy learning in this offline setting? This is also a causal inference problem: we need to estimate the value of a new target policy \(\pi\) using data collected under a behavior policy \(\mu^b(\cdot \mid s)\).
A popular approach to these challenges is Fitted Q-Iteration, studied with tree-based regression by Ernst et al. (2005). The key idea is to approximate the Q-function using a regression model (e.g., random forests, kernel methods, or neural networks), based on the Bellman optimality equation, and iteratively update this estimate. In an offline setting, this still requires sufficient coverage of the relevant state-action pairs and a state representation that controls confounding. The algorithm proceeds as follows:
- Initialize the Q-function estimate \(\hat{Q}_0(s,a)\). One may simply set it to zero or fit a regression of \(r_i\) on \((s_i,a_i)\) using the batch data.
- For each iteration \(k = 0, 1, 2, \ldots\):
- For each data point \((s_i, a_i, r_i, s'_i, d_i)\) in the dataset, where \(d_i=1\) indicates a terminal transition:
- Compute the bootstrapped target \[ y_i = r_i + \gamma (1-d_i) \max_{a'} \hat{Q}_k(s'_i, a'). \]
- Fit a regression model mapping \((s_i,a_i)\) to \(y_i\) to obtain the new estimate \(\hat{Q}_{k+1}(s,a)\).
- For each data point \((s_i, a_i, r_i, s'_i, d_i)\) in the dataset, where \(d_i=1\) indicates a terminal transition:
- Repeat for a chosen number of iterations, or until a specified stopping criterion is met. General regression approximations do not guarantee convergence.
Within iteration \(k\), compute every target using the same fixed \(\hat Q_k\), then fit \(\hat Q_{k+1}\). Updating the regression while constructing the targets would be a different algorithm. Unlike one tabular Q-learning update, one FQI regression updates predictions across the state-action space through the chosen function class.
At a terminal transition, there are no further rewards, so the target is just \(r_i\). A data-collection time limit is different: if the underlying task continues, we retain the continuation term. See the Gymnasium discussion of time limits for this distinction.
In this algorithm, the target value corresponds to the random quantity (due to the randomness of the transitioning and reward) inside the expectation of the Bellman optimality operator:
\[ \begin{aligned} \cT_Q^\ast Q(s,a) &= r(s,a) + \gamma \E \left[ (1-D)\max_{a'} Q(S', a') \mid S=s, A=a \right] \\ &= \E \left[ R + \gamma (1-D)\max_{a'} Q(S', a') \mid S=s, A=a \right]\\ &= \E \left[ Y \mid S=s, A=a \right], \end{aligned} \]
Here \(r(s,a)=\E[R\mid S=s,A=a]\), and \(D\) indicates termination. Since we only observe samples \((r_i, s'_i,d_i)\), the empirical target \(y_i\) provides a sample-based approximation to the Bellman optimality backup.
For a theoretical discussion of coverage and function approximation in fitted Q-iteration, see Chapter 4 of Agarwal et al. (2026).
3 Cartpole Example
The CartPole environment is a classic benchmark problem in reinforcement learning. It involves balancing a pole on a moving cart by applying forces to the cart. The state space is continuous, and the action space can be either discrete (e.g., left or right force) or continuous (e.g., varying force magnitude). Unlike the continuing tabular example, this task is episodic: failure ends the episode and has zero continuation value. We have created an environment simulator in R. The details of the environment dynamics and parameters can be found in our cartpole document.
For the main comparison, all three regression methods use the same 200 random-policy training episodes, actions \(\{-1,+1\}\), discount factor \(\gamma=0.9\), and 20 Bellman regression steps starting from \(\hat Q_0=0\). We use the binary safe-region reward: 1 when both the next cart position and pole angle lie within 0.1 of zero, and 0 otherwise. The first regression fits rewards, and the remaining 19 use bootstrapped targets.
# CartPole environment with actions in [-1, 1]
cartpole_step <- function(state, action,
reward.method = "discrete") {
# Unpack state
x <- state[1]
x_dot <- state[2]
theta <- state[3]
theta_dot <- state[4]
# Parameters
g <- 9.8
m_c <- 1.0
m_p <- 0.1
l <- 0.5
F_max <- 5
tau <- 0.01
x_th <- 0.2
theta_th <- 12 * (pi / 180)
total_mass <- m_c + m_p
# Action in [-1, 1]; discrete {-1, +1} is a special case
f <- action * F_max
# Compute accelerations
costheta <- cos(theta)
sintheta <- sin(theta)
temp <- (f + m_p * l * theta_dot^2 * sintheta) / total_mass
theta_acc <- (g * sintheta - costheta * temp) /
(l * (4/3 - (m_p * costheta^2) / total_mass))
x_acc <- temp - (m_p * l * theta_acc * costheta) / total_mass
# Update state using semi-implicit Euler
x_dot_new <- x_dot + tau * x_acc
x_new <- x + tau * x_dot_new
theta_dot_new <- theta_dot + tau * theta_acc
theta_new <- theta + tau * theta_dot_new
new_state <- c(x_new, x_dot_new, theta_new, theta_dot_new)
# Compute termination
done <- (abs(x_new) > x_th) ||
(abs(theta_new) > theta_th)
# Compute reward
if (reward.method == "discrete") {
reward <- ifelse(abs(theta_new) > 0.1 | abs(x_new) > 0.1, 0, 1)
} else if (reward.method == "continuous") {
reward <- - ( 0.01 * x_new^2 + # position loss
100 * theta_new^2 + # angle loss
0.01 * x_dot_new^2 + # position stability
0.1 * theta_dot_new^2) # angle stability
} else {
stop("Unknown reward.method")
}
return(list(state = new_state, reward = reward, done = done))
}
# Function to initialize the cartpole state
cartpole_initial <- function() {
state <- runif(4, min = -0.05, max = 0.05)
return(state)
}
# function to generating episodes
generate_cartpole <- function(n_episode = 1,
T_max = 200,
reward.method = "discrete",
policy = function(state) {
sample(c(-1, 1), 1)
}) {
all_rows <- list() # store rows before binding
row_id <- 1
for (ep in 1:n_episode) {
state <- cartpole_initial()
for (t in 1:T_max) {
# Generate action
A_t <- policy(state)
# check action range
if (abs(A_t) > 1) {
stop("Action out of range [-1, 1]")
}
# Step the environment
out <- cartpole_step(state, A_t, reward.method = reward.method)
S_next <- out$state
R_t <- out$reward
done <- out$done
# Record the complete transition, including the final step
all_rows[[row_id]] <- data.frame(
episode = ep,
time = t,
x = state[1],
x_dot = state[2],
theta = state[3],
theta_dot = state[4],
action = A_t,
reward = R_t,
x_next = S_next[1],
x_dot_next = S_next[2],
theta_next = S_next[3],
theta_dot_next = S_next[4],
terminated = done,
truncated = (t == T_max && !done)
)
row_id <- row_id + 1
# Move to next state
state <- S_next
if (done) break
}
}
# Combine into a dataframe
batch_data <- do.call(rbind, all_rows)
rownames(batch_data) <- NULL
return(batch_data)
}
set.seed(546)
cartpole_data = generate_cartpole(n_episode = 200, reward.method = "discrete") # plot the trajectories of the cart position and rewards
library(ggplot2)
library(patchwork)
plot_cartpole <- function(data) {
p1 <- ggplot(data, aes(x = time, y = x, color = factor(episode))) +
geom_line() +
labs(title = "Cart Position (x)", x = "Time", y = "x") +
theme_minimal() +
scale_y_continuous(limits = c(-0.2, 0.2)) +
theme(legend.position = "none")
p2 <- ggplot(data, aes(x = time, y = x_dot, color = factor(episode))) +
geom_line() +
labs(title = "Cart Velocity (x_dot)", x = "Time", y = "x_dot") +
theme_minimal() +
theme(legend.position = "none")
p3 <- ggplot(data, aes(x = time, y = theta, color = factor(episode))) +
geom_line() +
labs(title = "Pole Angle (theta)", x = "Time", y = "theta") +
theme_minimal() +
scale_y_continuous(limits = c(-12 * (pi / 180), 12 * (pi / 180))) +
theme(legend.position = "none")
p4 <- ggplot(data, aes(x = time, y = theta_dot, color = factor(episode))) +
geom_line() +
labs(title = "Pole Angular Velocity (theta_dot)", x = "Time", y = "theta_dot") +
theme_minimal() +
theme(legend.position = "none")
p5 <- ggplot(data, aes(x = time, y = reward, color = factor(episode))) +
geom_line() +
labs(title = "Reward", x = "Time", y = "reward") +
theme_minimal() +
theme(legend.position = "none")
# Four state panels with the reward panel below
(p1 | p2) /
(p3 | p4) /
p5
}
plot_cartpole(cartpole_data)
4 Fitted Q-Iteration With Linear Approximations
Fitted Q-iteration can use many regression methods. We first implement it with a linear function approximation, including state-action interactions. All examples below restrict actions to \(\{-1,+1\}\), even though the simulator also accepts continuous actions.
# Initial Q-function estimate: fit reward ~ state + action
linear_formula = y_targets ~ x + x_dot + theta + theta_dot + action +
action*x + action*x_dot + action*theta + action*theta_dot
y_targets = cartpole_data$reward
fit_qliner <- lm(linear_formula, data = cartpole_data)
# Settings
n_iter <- 20
gamma <- 0.9
# Start to iterate
for (iter in 2:n_iter) {
# Prepare data for next states with both actions
Data_Current = cartpole_data
Data_Next = data.frame(
x = cartpole_data$x_next,
x_dot = cartpole_data$x_dot_next,
theta = cartpole_data$theta_next,
theta_dot = cartpole_data$theta_dot_next
)
Data_Next_A1 = Data_Next
Data_Next_A1$action = -1
Data_Next_A2 = Data_Next
Data_Next_A2$action = 1
# Predict Q-values for next states with both actions
Q_next_A1 <- predict(fit_qliner, newdata = Data_Next_A1)
Q_next_A2 <- predict(fit_qliner, newdata = Data_Next_A2)
# Compute max Q-value for next states
Q_next_max <- pmax(Q_next_A1, Q_next_A2)
# Compute bootstrapped targets
y_targets <- Data_Current$reward + gamma * (1 - Data_Current$terminated) * Q_next_max
# Fit new regression model
fit_qliner <- lm(linear_formula, data = Data_Current)
}Based on this fitted linear Q-function, we can derive a greedy policy by selecting the action that maximizes the Q-value for each state. This is essentially plug the states into the fitted Q-function and choose the action accordingly.
# Derive greedy policy from fitted Q-function
greedy_policy <- function(state, Qfun) {
state_df <- data.frame(
x = state[1],
x_dot = state[2],
theta = state[3],
theta_dot = state[4]
)
# Action = -1
state_df$action <- -1
state_df$action_sq <- 1
Q_A1 <- predict(Qfun, newdata = state_df)
# Action = +1
state_df$action <- 1
state_df$action_sq <- 1
Q_A2 <- predict(Qfun, newdata = state_df)
if (Q_A1 > Q_A2) {
return(-1)
} else {
return(1)
}
}We can now use this function to generate new episodes under the learned policy and evaluate its performance.
# Evaluate the learned policy
new_policy <- function(state) {
greedy_policy(state, Qfun = fit_qliner)
}
# Generate new episodes using the learned policy
test_data <- generate_cartpole(n_episode = 50,
reward.method = "discrete",
policy = new_policy)
# plot the trajectories of the cart position
plot_cartpole(test_data)
A linear function approximation may be too simple for this problem. Each regression approximates a Bellman backup, so its errors can affect later targets. The trajectory plot alone does not establish improvement; below we compare held-out returns and episode lengths with a random policy. Next, we try a quadratic function approximation under the same reward.
5 Fitted Q-Iteration With Quadratic Approximations
To learn a better Q-function, we can try a more flexible function approximation. Here we use a quadratic function approximation.
# Initial Q-function estimate: fit reward ~ state + action
quad_formula = y_targets ~ I(x^2) + I(x_dot^2) + I(theta^2) + I(theta_dot^2) + action +
action*x + action*x_dot + action*theta + action*theta_dot
y_targets = cartpole_data$reward
fit_qquad <- lm(quad_formula, data = cartpole_data)
# Reuse the same n_iter and gamma as in the linear fit
# Start to iterate
for (iter in 2:n_iter) {
# Prepare data for next states with both actions
Data_Current = cartpole_data
Data_Next = data.frame(
x = cartpole_data$x_next,
x_dot = cartpole_data$x_dot_next,
theta = cartpole_data$theta_next,
theta_dot = cartpole_data$theta_dot_next
)
Data_Next_A1 = Data_Next
Data_Next_A1$action = -1
Data_Next_A2 = Data_Next
Data_Next_A2$action = 1
# Predict Q-values for next states with both actions
Q_next_A1 <- predict(fit_qquad, newdata = Data_Next_A1)
Q_next_A2 <- predict(fit_qquad, newdata = Data_Next_A2)
# Compute max Q-value for next states
Q_next_max <- pmax(Q_next_A1, Q_next_A2)
# Compute bootstrapped targets
y_targets <- Data_Current$reward + gamma * (1 - Data_Current$terminated) * Q_next_max
# Fit new regression model
fit_qquad <- lm(quad_formula, data = Data_Current)
}Same as before, we can implement the greedy policy based on the fitted quadratic Q-function.
# Evaluate the learned policy
learned_policy <- function(state) {
greedy_policy(state, Qfun = fit_qquad)
}
# Generate new episodes using the learned policy
test_data <- generate_cartpole(n_episode = 50,
reward.method = "discrete",
policy = learned_policy)
# plot the trajectories of the cart position
plot_cartpole(test_data)
6 Using Random Forests
We now use the ranger package to implement fitted Q-iteration on the same batch data. In the first step, we fit a regression model to predict the reward based on the current state and action. Function approximation still requires appropriate tuning. Here the reward, training data, action set, discount factor, and number of regression steps stay fixed, so the comparison concerns the chosen regression approximations.
# Reuse cartpole_data; set the seed for forest fitting
set.seed(546)
# Initial Q-function estimate: fit reward ~ state + action
library(ranger)
nodesize = 100
ntrees = 500
rf_q <- ranger(
formula = reward ~ x + x_dot + theta + theta_dot + action,
data = cartpole_data,
num.trees = ntrees,
min.node.size = nodesize
)To implement the fitted Q-iteration algorithm, we do the same as before, but now we use random forests as the function approximation.
# Retain every transition, including failure and time-limit steps
Data_Current = cartpole_data
Data_Next = data.frame(
x = cartpole_data$x_next,
x_dot = cartpole_data$x_dot_next,
theta = cartpole_data$theta_next,
theta_dot = cartpole_data$theta_dot_next
)
# define data frame with next states and action = -1
Data_Next_A1 = Data_Next
Data_Next_A1$action = -1
# define data frame with next states and action = +1
Data_Next_A2 = Data_Next
Data_Next_A2$action = +1
current_action = NULL
# Reuse the same n_iter and gamma as in the linear fit
# start to iterate
for (iter in 2:n_iter) {
# Predict Q-values for next states with both actions
Q_next_A1 <- predict(rf_q, data = Data_Next_A1)$predictions
Q_next_A2 <- predict(rf_q, data = Data_Next_A2)$predictions
# Compute max Q-value for next states
Q_next_max <- pmax(Q_next_A1, Q_next_A2)
# best action at next stage
action_next <- ifelse(Q_next_A1 > Q_next_A2, -1, 1)
# Compare greedy actions at the same nonterminal next states
if (!is.null(current_action)) {
cat("Iteration :", iter, "| changed actions:",
round(mean(action_next[!Data_Current$terminated] !=
current_action[!Data_Current$terminated]) * 100, 2), "%\n")
}
current_action <- action_next
# Compute bootstrapped targets
y_targets <- Data_Current$reward + gamma * (1 - Data_Current$terminated) * Q_next_max
# Fit new regression model
rf_q <- ranger(
formula = y_targets ~ x + x_dot + theta + theta_dot + action,
data = Data_Current,
num.trees = ntrees,
min.node.size = nodesize
)
}
## Iteration : 3 | changed actions: 40.28 %
## Iteration : 4 | changed actions: 9.8 %
## Iteration : 5 | changed actions: 8.8 %
## Iteration : 6 | changed actions: 5.79 %
## Iteration : 7 | changed actions: 3.54 %
## Iteration : 8 | changed actions: 3.25 %
## Iteration : 9 | changed actions: 2.48 %
## Iteration : 10 | changed actions: 3.5 %
## Iteration : 11 | changed actions: 2.82 %
## Iteration : 12 | changed actions: 2.83 %
## Iteration : 13 | changed actions: 2.05 %
## Iteration : 14 | changed actions: 2.12 %
## Iteration : 15 | changed actions: 1.99 %
## Iteration : 16 | changed actions: 2.17 %
## Iteration : 17 | changed actions: 1.72 %
## Iteration : 18 | changed actions: 1.5 %
## Iteration : 19 | changed actions: 1.38 %
## Iteration : 20 | changed actions: 1.46 %We can now implement this policy to see how well it performs
# Derive greedy policy from fitted Q-function
greedy_policy_rf <- function(state, Qfun) {
state_df <- data.frame(
x = state[1],
x_dot = state[2],
theta = state[3],
theta_dot = state[4]
)
# Action = -1
state_df$action <- -1
state_df$action_sq <- 1
Q_A1 <- predict(Qfun, data = state_df, num.threads = 1)$predictions
# Action = +1
state_df$action <- 1
state_df$action_sq <- 1
Q_A2 <- predict(Qfun, data = state_df, num.threads = 1)$predictions
if (Q_A1 > Q_A2) {
return(-1)
} else {
return(1)
}
} # Evaluate the learned policy
new_policy <- function(state) {
greedy_policy_rf(state, Qfun = rf_q)
}
# Generate new episodes using the learned policy
test_data <- generate_cartpole(n_episode = 50,
reward.method = "discrete",
policy = new_policy)
# plot the trajectories of the cart position
plot_cartpole(test_data)
The trajectory plots show how long this fitted policy balances the pole and how well it controls cart position. The percentage of changed greedy actions measures policy changes only at the observed nonterminal next states; it does not establish convergence of the Q-function or improvement in policy value. More iterations need not improve performance. If cart positions encountered by the learned policy are poorly represented in the training data, reward predictions there may be inaccurate. This is one way distributional shift and extrapolation can affect offline reinforcement learning.
7 Held-Out Policy Evaluation
Do the fitted policies improve on random actions? After fitting, we draw 50 new initial states and evaluate every policy from exactly these states, using the same binary reward and a maximum of 200 transitions. No evaluation transitions enter training. For each episode, we record its discounted return
\[ G_{200}=\sum_{t=0}^{\min(T,200)-1}\gamma^t R_t, \]
where \(T\) is the number of transitions until failure, and its length \(\min(T,200)\). A rollout that reaches 200 transitions without failure is truncated. Its return omits later rewards, whereas failure has no later rewards. The length therefore measures survival separately from time spent in the smaller rewarded safe region.
n_test <- 50
T_test <- 200
set.seed(54601)
initial_states <- t(replicate(n_test, cartpole_initial()))
policies <- list(
Random = function(state) sample(c(-1, 1), 1),
Linear = function(state) greedy_policy(state, fit_qliner),
Quadratic = function(state) greedy_policy(state, fit_qquad),
Forest = function(state) greedy_policy_rf(state, rf_q)
)
set.seed(54602)
evaluation <- list()
row_id <- 1
for (method in names(policies)) {
for (ep in 1:n_test) {
state <- initial_states[ep, ]
G <- 0
for (t in 1:T_test) {
action <- policies[[method]](state)
out <- cartpole_step(state, action, reward.method = "discrete")
G <- G + gamma^(t - 1) * out$reward
state <- out$state
if (out$done) break
}
evaluation[[row_id]] <- data.frame(
method = method, episode = ep,
discounted_return = G, steps = t,
truncated = !out$done && t == T_test
)
row_id <- row_id + 1
}
}
evaluation <- do.call(rbind, evaluation)
evaluation_summary <- aggregate(
cbind(discounted_return, steps, truncated) ~ method,
data = evaluation, FUN = mean
)
knitr::kable(evaluation_summary, digits = 3,
col.names = c("Policy", "Mean discounted return", "Mean episode length",
"Fraction truncated at 200 steps"))| Policy | Mean discounted return | Mean episode length | Fraction truncated at 200 steps |
|---|---|---|---|
| Forest | 9.998 | 128.60 | 0.06 |
| Linear | 8.791 | 55.44 | 0.00 |
| Quadratic | 9.921 | 83.70 | 0.00 |
| Random | 9.634 | 69.08 | 0.00 |
In this seeded run, the forest policy has the largest mean discounted return and mean episode length, while the linear policy does worse than random on both measures. This compares these fitted policies on one held-out set, rather than establishing that one regression method always works better. With \(\gamma=0.9\), early rewards dominate the discounted return, so also inspect episode length and the fraction truncated at the cutoff. A more flexible regression does not by itself guarantee a better policy: coverage, approximation error, and the greedy action choices all matter. The simulator supplies new interactions for evaluation. This is not an offline policy-evaluation method for historical data when no simulator or new interactions are available.
The simulator also retains a negative quadratic reward as an alternative objective. It penalizes deviations smoothly, but failure ends future penalties, so a larger return under that reward need not mean longer survival. Changing to it would require regenerating the rewards, refitting every method, and evaluating all policies under that same objective. It should not be mixed into the regression comparison above.
FQI learns a value function and then chooses a greedy action. In the policy-gradient lecture, we instead parameterize the policy and update it directly, using sampled returns or a learned value function to guide that update.
This is known as the model-free setting in reinforcement learning, where the agent learns value functions or policies from experience without explicitly modeling the environment’s dynamics. If we estimate the transition dynamics, it is known as the model-based setting.↩︎