Chapter 9: On-policy Prediction with Approximation
From this chapter, we move from tabular methods to approximate methods to tackle the curse of dimension in the state space. Instead of storing a lookup table for state values in tabular methods, approximate methods learn state values with function approximation, i.e., %20%5Capprox%20v_%5Cpi(s))
.
However, approximate methods are not simple combination of RL and supervised learning. Compared to tabular RL methods, approximate methods introduce the challenge of generalization, i.e., the change of 
based on one state will also change the value of all other states, while the values of different states are decoupled in tabular case. In other words, with function approximation, we have lost the policy improvement theorem under the tabular case. Compared to standard supervised learning on a static distribution, function approximation in RL raises new issues such as nonstationarity (the training samples are collected online from a time-variant policy), bootstrapping (the learning target itself is dependent on the parameters), and delayed targets.
This chapter starts from the simplest case, i.e., on-policy prediction (value estimation) with approximation given a fixed policy.
The Prediction Objective
The prediction problem can be seen as a supervised learning problem, where the data distribution is the on-policy distribution )
generated by the policy 
. The on-policy distribution is the normalized fraction of time spent in 
.
Under the on-policy distribution, the learning objective is defined as ![\overline{VE}(w) = \sum_{s \in \mathcal{S}} \mu(s) \big[ v_\pi(s) - \hat{v}(s, w) \big]^2.](https://math.jianshu.com/math?formula=%5Coverline%7BVE%7D(w)%20%3D%20%5Csum_%7Bs%20%5Cin%20%5Cmathcal%7BS%7D%7D%20%5Cmu(s)%20%5Cbig%5B%20v_%5Cpi(s)%20-%20%5Chat%7Bv%7D(s%2C%20w)%20%5Cbig%5D%5E2.)
However, we need to note that
Remember that our ultimate purpose--the reason we are learning a value function--is to find a better policy. The best value function for this purpose is not necessarily the best for minimizing 
. Nevertheless, it is not yet clear what a more useful alternative goal for value prediction might be.
Stochastic-gradient and Semi-gradient Methods
If we know the true state values, then we can learn with standard SGD as follows: ![w_{t+1} = w_t - \frac{1}{2} \alpha \nabla \big[ v_\pi(S_t) - \hat{v}(S_t, w_t) \big]^2 = w_t + \alpha \big[ v_\pi(S_t) - \hat{v}(S_t, w_t) \big] \nabla \hat{v}(S_t, w_t).](https://math.jianshu.com/math?formula=w_%7Bt%2B1%7D%20%3D%20w_t%20-%20%5Cfrac%7B1%7D%7B2%7D%20%5Calpha%20%5Cnabla%20%5Cbig%5B%20v_%5Cpi(S_t)%20-%20%5Chat%7Bv%7D(S_t%2C%20w_t)%20%5Cbig%5D%5E2%20%3D%20w_t%20%2B%20%5Calpha%20%5Cbig%5B%20v_%5Cpi(S_t)%20-%20%5Chat%7Bv%7D(S_t%2C%20w_t)%20%5Cbig%5D%20%5Cnabla%20%5Chat%7Bv%7D(S_t%2C%20w_t).)
However, the challenge in RL is that we don't have a ground-true )
as in supervised learning. Instead, we need to use a backup estimation 
as the target.
If is an unbiased estimate, like in MC (
), then 
is guaranteed to converge to a local minimum under the usual stochastic approximation conditions for decreasing 
.
However, for TD, our alternative target )
is not independent of . Consequently, we can not apply standard SGD, but use semi-gradient methods for update, i.e., only take into account the gradient of w.r.t. the current estimate, while ignore its gradient w.r.t. the target part. Altough semi-gradient methods converge less robustly, they do converge reliably in the linear case, and more importantly, they typically enable significantly faster and fully continual and online learning.
Linear Methods and Least-Squares TD
When the approximation function is linear, we can write the semi-gradient update explicitly as:
![\begin{aligned} w_{t+1} &= w_t + \alpha (R_{t+1} + \gamma w_t^T x_{t+1} - w_t^T x_t) x_t \\ &= w_t + \alpha \big[ R_{t+1} x_t - x_t(x_t - \gamma x_{t+1})^T w_t \big] \end{aligned}](https://math.jianshu.com/math?formula=%5Cbegin%7Baligned%7D%20w_%7Bt%2B1%7D%20%26%3D%20w_t%20%2B%20%5Calpha%20(R_%7Bt%2B1%7D%20%2B%20%5Cgamma%20w_t%5ET%20x_%7Bt%2B1%7D%20-%20w_t%5ET%20x_t)%20x_t%20%5C%5C%20%26%3D%20w_t%20%2B%20%5Calpha%20%5Cbig%5B%20R_%7Bt%2B1%7D%20x_t%20-%20x_t(x_t%20-%20%5Cgamma%20x_%7Bt%2B1%7D)%5ET%20w_t%20%5Cbig%5D%20%5Cend%7Baligned%7D)
In expectation, we have ![\mathbb{E}[w_{t+1}|w_t] = w_t + \alpha (b - Aw_t),](https://math.jianshu.com/math?formula=%5Cmathbb%7BE%7D%5Bw_%7Bt%2B1%7D%7Cw_t%5D%20%3D%20w_t%20%2B%20%5Calpha%20(b%20-%20Aw_t)%2C)
where ![b = \mathbb{E} [R_{t+1} x_t]](https://math.jianshu.com/math?formula=b%20%3D%20%5Cmathbb%7BE%7D%20%5BR_%7Bt%2B1%7D%20x_t%5D)
, and ![A = \mathbb{E}[x_t (x_t - \gamma x_{t+1})^T]](https://math.jianshu.com/math?formula=A%20%3D%20%5Cmathbb%7BE%7D%5Bx_t%20(x_t%20-%20%5Cgamma%20x_%7Bt%2B1%7D)%5ET%5D)
. Thus the converged solution, i.e., the TD fixed point, satisfies 
. Consequently, instead of using iterative algorithm like SGD, we can directly compute the closed-form solution for linear methods. This is known as the least-squared TD algorithm, and its complexity is )
, where 
is the state space dimension. Matrix inverse typically requires a complexity of )
. However, the matrix 
is the sum of vector outer product, thus its inverse can be computed more efficiently using the Sherman-Morrison formula.
