Chapter 8 Value Function Methods

In this chapter we move from previous tabular representation for state/action value to function representation. That is to say, we use a function to fit the true expression of the state/action value function. Such a function can be predifined, e.g., a linear function, or a neural network.

The reason why we move from tabular-based representation to function-based are:

1. storage, compared with tabular, we only need to store a few parameters describing the function.
2. generalization, action and state may be infinite (or continuous), we cannot store all the state/action value. We need to find a unified representation.

An illustration of the function approximation method. The x-axis and y-axis correspond to $s$ and $\hat v(s)$, respectively.

An illustration of the process for retrieving the value of s when using the function approximation method.

As shown in the figure, we update parameters $\omega$ to update the value.

Tabular TD updates an individual value entry. With function approximation, TD updates shared parameters, so an update can change predictions for many states. The usual update is a semi-gradient update: it differentiates the current prediction while treating the bootstrapped target as fixed. It should not be identified with ordinary gradient descent on the full Bellman residual.

Function-based Value representation

A simple linear function approximation:

$$\hat{v}(s, w) = as + b = \underbrace{[s, 1]}_{\phi^T(s)} \underbrace{\begin{bmatrix} a \\ b \end{bmatrix}}_{w} = \phi^T(s)w$$

here

• $w$ is the parameter vector
• $\phi(s)$ is the feature vector of $s$
• $\hat{v}(s, w)$ is linear in $w$

We can also fit the points using a second-order curve:

$$\hat{v}(s, w) = as^2 + bs + c = \underbrace{[s^2, s, 1]}_{\phi^T(s)} \underbrace{\begin{bmatrix} a \\ b \\ c \end{bmatrix}}_{w} = \phi^T(s)w.$$

In this case,The dimensions of $w$ and $\phi(s)$ increase, but the values may be fitted more accurately. Although $\hat{v}(s, w)$ is nonlinear in $s$, it is linear in $w$. The nonlinearity is contained in $\phi(s)$.

we can use even higher-order polynomial curves or other complex curves to fit the dots, which we can better approximate true value function but needs more parameter.

TD learning of state values based on function approximation

objective

As we are trying to fit the value function, our optimization objective is:

$$J(w) = \mathbb{E}[(v_{\pi}(S) - \hat{v}(S, w))^2],$$

here we invovle the random variable $S$, if the state is in uniform, we have:

$$J(w) = \frac{1}{n} \sum_{s \in \mathcal{S}} (v_{\pi}(s) - \hat{v}(s, w))^2,$$

however, we can write it into a more general form:

$$J(w) = \sum_{s \in \mathcal{S}} d_{\pi}(s)(v_{\pi}(s) - \hat{v}(s, w))^2,$$

here $d_{\pi}(s)$ is called the the stationary distribution of the Markov process under policy $\pi$. That is, the probability for the agent visiting $s$ after a long period of time is $d_\pi(s)$. By definition, $\sum_{s \in \mathcal{S}} d_\pi(s) = 1$.

It is notable that the value of $d_\pi(s)$ is nontrivial to obtain because it requires knowing the state transition probability matrix $P_\pi$. Fortunately, we do not need to calculate the specific value of $d_\pi(s)$ to minimize this objective function as shown in the next subsection. If the state space is continuous, we can replace the summations with integrals in the above equation.

Stationary distribution

Once a policy $\pi$ is given, the MDP becomes a Markov process, and its dynamics are governed by the probability transition matrix $P_\pi \in \mathbb{R}^{n \times n}$.

Let $d_0 \in \mathbb{R}^n$ be a vector representing the probability distribution of the states at the initial time step. The probability distribution vector after exactly $k$ steps, denoted as $d_k$, can be formulated in matrix-vector form as:

$$d_k^T = d_0^T P_\pi^k,$$

here, $P_{\pi}^{k}$ represents the probability matrix of the agent transitioning from state $s_{i}$ to $s_{j}$ after exactly $k$ steps under policy $\pi$.

For a finite irreducible and aperiodic Markov chain, there is a unique stationary distribution and $P_\pi^k$ converges as $k$ approaches infinity:

$$\lim_{k \to \infty} P_\pi^k = 1_n d_\pi^T$$

Here, $1_n = [1, \dots, 1]^T \in \mathbb{R}^n$, which means $1_n d_\pi^T$ is a constant matrix where all of its rows are equal to $d_\pi^T$. Substituting this limit back into the state evolution equation yields:

$$\lim_{k \to \infty} d_k^T = d_0^T \lim_{k \to \infty} P_\pi^k = d_0^T 1_n d_\pi^T = d_\pi^T$$

Under these assumptions, the initial probabilities sum to one ($d_0^T1_n=1$), so the limiting distribution is independent of $d_0$. Without such assumptions, a stationary distribution may not be unique or the time-indexed distribution may not converge to it. Stationarity should not be assumed for every trajectory from its first sample.

The analytical value of $d_\pi$ can be calculated by leveraging the recursive nature of the transition process. By taking the limit of both sides of the iterative equation $d_k^T = d_{k-1}^T P_\pi$, we obtain:

$$\lim_{k \to \infty} d_k^T = \lim_{k \to \infty} d_{k-1}^T P_\pi$$

Since both distributions converge as $k \to \infty$, this directly resolves to the stationary equation:

$$d_\pi^T = d_\pi^T P_\pi$$

In linear algebra, the left eigenvector $x$ and its corresponding eigenvalue $\lambda$ of a matrix $A$ satisfy the definition $x^{T}A = \lambda x^{T}$.

Comparing this to the steady-state equation $d_{\pi}^{T}P_{\pi} = 1 \cdot d_{\pi}^{T}$, it is clear that $d_{\pi}$ is precisely the left eigenvector of the probability transition matrix $P_{\pi}$ corresponding to the eigenvalue $\lambda=1$. when transforming the formula to $(P_{\pi}^{T} - I)d_{\pi} = 0$, we find the corresponding eigenvector with an eigenvalue of 1 by solving this homogeneous linear system of equations.

Optimization

We can adopt the gradient descent method to optimaize the objective:

$$w_{k+1} = w_k - \alpha_k \nabla_w J(w_k),$$

where

$$\begin{aligned} \nabla_w J(w_k) &= \nabla_w \mathbb{E}[(v_{\pi}(S) - \hat{v}(S, w_k))^2] \\ &= \mathbb{E}[\nabla_w (v_{\pi}(S) - \hat{v}(S, w_k))^2] \\ &= 2\mathbb{E}[(v_{\pi}(S) - \hat{v}(S, w_k))(-\nabla_w \hat{v}(S, w_k))] \\ &= -2\mathbb{E}[(v_{\pi}(S) - \hat{v}(S, w_k))\nabla_w \hat{v}(S, w_k)]. \end{aligned}$$

Therefore, the gradient descent algorithm is

$$w_{k+1} = w_k + 2\alpha_k \mathbb{E}[(v_{\pi}(S) - \hat{v}(S, w_k))\nabla_w \hat{v}(S, w_k)],$$

where the coefficient $2$ before $\alpha_k$ can be merged into $\alpha_k$ without loss of generality. The algorithm requires calculating the expectation. In the spirit of stochastic gradient descent (SGD), we can replace the true gradient with a stochastic gradient. Then, we have

$$w_{t+1} = w_t + \alpha_t (v_{\pi}(s_t) - \hat{v}(s_t, w_t))\nabla_w \hat{v}(s_t, w_t),$$

where $s_t$ is a sample of $S$ at time $t$. It requires the true state value $v_{\pi}$, which is unknown and must be estimated. We can replace $v_{\pi}(s_t)$ with an approximation to make the algorithm implementable.

The following two methods can be used to do so.

1. Monte Carlo method: Suppose that we have an episode $(s_0, r_1, s_1, r_2, \dots)$. Let $g_t$ be the discounted return starting from $s_t$. Then, $g_t$ can be used as an approximation of $v_{\pi}(s_t)$. The algorithm in (8.12) becomes:

$$w_{t+1} = w_t + \alpha_t (g_t - \hat{v}(s_t, w_t))\nabla_w \hat{v}(s_t, w_t)$$

This is the algorithm of Monte Carlo learning with function approximation.

2. Temporal-difference method: In the spirit of TD learning, $r_{t+1} + \gamma \hat{v}(s_{t+1}, w_t)$ can be used as an approximation of $v_{\pi}(s_t)$. The algorithm becomes

$$w_{t+1} = w_t + \alpha_t [r_{t+1} + \gamma \hat{v}(s_{t+1}, w_t) - \hat{v}(s_t, w_t)]\nabla_w \hat{v}(s_t, w_t).$$

This is semi-gradient TD. During the update, $y_t=r_{t+1}+\gamma\hat v(s_{t+1},w_t)$ is treated as a constant target: gradients flow through $\hat v(s_t,w)$, not through the target's dependence on $w_t$. In code, the target is detached or calculated without recording gradients. At a true terminal transition, omit the bootstrap term. Replacing $v_\pi$ with this target does not make the update an unbiased gradient of the original mean-squared value error for an arbitrary approximate critic.

We can use the function introduce in Function-based Value representation to represent which function is we use to approximate the true value function. If we use linear approximation function, the gradient is $\nabla_w \hat{v}(s, w) = \phi(s)$. We can also use neural network.

Theoretical analysis

For the convergence, see at book.

The true state-value function $v_{\pi}$ strictly satisfies the Bellman equation: $v_{\pi}=r_{\pi}+\gamma P_{\pi}v_{\pi}$. When we introduce a function approximator (e.g., a linear function or neural network with parameters $w$), we hope that the estimated value $\hat{v}(w)$ also satisfies this equation as much as possible. Therefore, the difference between the two sides of the equation is the Bellman error:

$$J_{BE}(w) = \|\hat{v}(w) - (r_\pi + \gamma P_\pi \hat{v}(w))\|^2_D \doteq \|\hat{v}(w) - T_\pi(\hat{v}(w))\|^2_D.$$

The Bellman error often cannot be optimized to 0 because the function approximators we use (such as low-dimensional linear features) have limited approximation ability, the result mapped by the Bellman operator $T_{\pi}(\hat{v}(w))=r_\pi + \gamma P_\pi \hat{v}(w)$ often "runs out" of the space that our function approximator can represent.

For linear function approximation, the TD fixed point can instead be characterized using a projection back into the feature space. The mean-squared projected Bellman error is:

$$J_{PBE}(w)=\|\hat{v}(w)-MT_{\pi}(\hat{v}(w))\|_{D}^{2}.$$

Here, $D=\operatorname{diag}(d_\pi)$ and $M$ is the orthogonal projection onto the linear feature space in the D-weighted norm. Under standard discounted, on-policy linear-TD assumptions, including suitable feature rank, state coverage, and step sizes, TD converges to the projected Bellman fixed point. At this point the projected error is zero. This conclusion requires those assumptions; merely projecting into the feature space does not establish it for arbitrary settings.

Ordinary semi-gradient TD is not generally gradient descent on $J_{PBE}$ itself. The linear on-policy result must not be extended into a blanket convergence claim for neural networks or off-policy TD. Function approximation, bootstrapping, and off-policy sampling can together lead to instability or divergence.

TD learning of action values based on function approximation

Here we use function to approximate action values.

The Sarsa algorithm with function approximation can be readily obtained by replacing the state values with action values in TD learning of state values based on function approximation section. In particular, suppose that $q_{\pi}(s, a)$ is approximated by $\hat{q}(s, a, w)$. Replacing $\hat{v}(s, w)$ by $\hat{q}(s, a, w)$ gives:

$$w_{t+1} = w_t + \alpha_t [r_{t+1} + \gamma \hat{q}(s_{t+1}, a_{t+1}, w_t) - \hat{q}(s_t, a_t, w_t)] \nabla_w \hat{q}(s_t, a_t, w_t).$$

Pseudocode: Sarsa with function approximation

Tabular Q-learning can also be extended to the case of function approximation. The update rule is

$$w_{t+1} = w_t + \alpha_t \left[ r_{t+1} + \gamma \max_{a \in \mathcal{A}(s_{t+1})} \hat{q}(s_{t+1}, a, w_t) - \hat{q}(s_t, a_t, w_t) \right] \nabla_w \hat{q}(s_t, a_t, w_t).$$

Deep Q-learning

To connect DQN with Q-learning, first consider the mean-squared sampled TD error:

$$J = \mathbb{E} \left[ \left( R + \gamma \max_{a \in \mathcal{A}(S')} \hat{q}(S', a, w) - \hat{q}(S, A, w) \right)^2 \right],$$

Here $(S,A,R,S')$ denotes a sampled transition. The Bellman optimality equation requires the conditional mean TD error to be zero at $q^*$; it does not require every sampled TD error, or its mean square, to be zero. Writing $Y=R+\gamma\max_a\hat q(S',a,w)$ gives:

$$\mathbb E[(Y-\hat q(s,a,w))^2|s,a] =(\mathbb E[Y|s,a]-\hat q(s,a,w))^2+\operatorname{Var}(Y|s,a).$$

Thus, mean-squared sampled TD error includes target variance in addition to the squared Bellman residual. For episodic tasks, all DQN targets below use $R+\gamma(1-d)\max_a\hat q(S',a,\cdot)$, where d indicates true termination; the displayed formulas omit d for brevity.

DQN treats the target as fixed during each gradient update rather than differentiating both occurrences of w in the expression above. It additionally uses a target network that changes more slowly to reduce instability from rapidly moving bootstrap targets. Stopping target gradients and maintaining a lagged target network are distinct choices. The two networks are:

1. Main Network: represent $\hat{q}(s, a, w)$, namely the approximation of action value.
2. Target network: a lagged copy $\hat q(s,a,w_T)$ of the main network used to construct bootstrap targets. It is also an approximation and does not already know the optimal action values.

The objective function in this case becomes:

$$J = \mathbb{E} \left[ \left( R + \gamma \max_{a \in \mathcal{A}(S')} \hat{q}(S', a, w_T) - \hat{q}(S, A, w) \right)^2 \right],$$

where $w_T$ is the target network's parameter. When $w_T$ is fixed, the gradient of $J$ is

$$\nabla_w J = -\mathbb{E} \left[ \left( R + \gamma \max_{a \in \mathcal{A}(S')} \hat{q}(S', a, w_T) - \hat{q}(S, A, w) \right) \nabla_w \hat{q}(S, A, w) \right],$$

where some constant coefficients are omitted without loss of generality.

The main network is updated in every iteration. By contrast, the target network is set to be the same as the main network every certain number of iterations to satisfy the assumption that $w_T$ is fixed when calculating the gradient.

DQN commonly uses experience replay to reuse transitions and reduce the temporal correlation within training batches. We store transitions, including terminal information, in a replay buffer $\mathcal B$ and sample minibatches to update the main network. This supports data reuse; using a neural network does not by itself make replay mandatory.

Uniformly sampling buffer entries is a simple choice, but it does not make the state-action distribution uniform. If 90% of stored transitions visit one state, approximately 90% of uniformly sampled entries will still visit that state. Replay neither guarantees state coverage nor requires uniform sampling. Prioritized experience replay uses nonuniform probabilities, with importance weights to address the resulting sampling bias relative to its intended replay objective. The buffer composition and sampling rule determine how states and actions are weighted in the training loss.

Pseudocode: DQN

The earlier algorithms were presented as sequential updates for clarity, not because linear models forbid replay or guarantee convergence in all cases. Suitable on-policy linear TD evaluation admits convergence analysis under Markov sampling; this does not imply convergence of arbitrary linear Q-learning or that samples collected while a policy changes already follow a single stationary distribution.

Deep on-policy methods can learn from recent rollouts without a long-term replay buffer; A2C and PPO are examples. For ordinary on-policy Sarsa, reusing a stored next action from an old policy as though it were sampled from the current policy creates a mismatch in the target $\hat q(s_{t+1},a_{t+1},w_t)$. Reusing such data requires an appropriate off-policy treatment rather than an assumption that all deep methods should share DQN's replay procedure.