The importance sampling ratio weights samples from one distribution so sample statistics can match the target distribution.
$$\rho_t \doteq \rho_{t:t} = \frac{\pi(A_t \vert S_t)}{b(A_t \vert S_t)} \tag{11.1}$$
We can use the importance sampling ratio in the semi-gradient weight updates from before to try to implement an off-policy parameter update:
$$\mathbf{w}_{t+1} \doteq \mathbf{w}_t + \alpha \rho_t \delta_t \nabla \hat v(S_t \vert \mathbf{w}_t) \tag{11.2}$$
where $\delta_t$ is the error term depending on the target value such as the TD(0) discounted reward:
$$\delta_t \doteq R_{t+1} + \gamma \hat v (S_{t+1}, \mathbf{w}_t) - \hat v(S_t, \mathbf{w}_t) \tag{11.3}$$
or the average reward for a continuing task:
$$\delta_t \doteq R_{t+1} - \bar R_t + \hat v(S_{t+1}, \mathbf{w}_t) - \hat v (S_t, \mathbf{w}_t) \tag{11.4}$$
For action-values and expected updates, we do not need to use the importance sampling ratio (as we don't in Q-learning) since the bootstrap update does not depend on the actual action taken. However, in the tabular case each state estimation was independent so this method converged even in the off policy case. In the case of function approximation, the target value is actually the value-error which depends on the on-policy distribution. So if the samples appear according to the off-policy distriution this method may still not converge to the correct values as we will see in some later examples.
$$\mathbf{w}_{t+1} \doteq \mathbf{w}_t + \alpha \delta_t \nabla \hat q(S_t, A_t, \mathbf{w}_t) \tag{11.5}$$
$$\delta_t \doteq R_{t+1} + \gamma \sum_a \pi(a \vert S_{t + 1})\hat q(S_{t+1}, a, \mathbf{w}_t) - \hat q (S_t, A_t, \mathbf{w}_t) \tag{discounted expected sarsa}$$
$$\delta_t \doteq R_{t+1} - \bar R_t + \sum_a \pi(a \vert S_{t + 1})\hat q(S_{t+1}, a, \mathbf{w}_t) - \hat q (S_t, A_t, \mathbf{w}_t) \tag{average reward expected sarsa}$$
Using the true values, we can write down the value error objective and directly calculate the parameters which minimize it by taking the gradient:
$$\overline{\text{VE}} = \frac{1}{4} \left ( (w_A - 1)^2 + (w_A - 0)^2 + (w_B - 1)^2 + (w_C - 0)^2 \right ) = \frac{1}{4} \left ( 2(w_A^2 - w_A) + 1 + (w_B - 1)^2 + w_C^2 \right )$$
$$\begin{flalign} \frac{\partial \overline{\text{VE}}}{\partial w_A} &= \frac{1}{2} \left ( 2 w_A - 1 \right ) \\ \frac{\partial \overline{\text{VE}}}{\partial w_B} &= \frac{1}{2} \left (w_B - 1 \right )\\ \frac{\partial \overline{\text{VE}}}{\partial w_C} &= \frac{1}{2} w_C\\ \end{flalign}$$
Setting each of these to zero reveals the unique solution which minimizes the value error:
$$\begin{flalign} w_A &= \frac{1}{2} \\ w_B &= 1 \\ w_C &= 0 \\ \end{flalign}$$
which is the same solution as before, expect now the value error is not zero but rather $\frac{1}{4}(2(\frac{1}{4} - \frac{1}{2}) + 1) = \frac{1}{8}$. An exact solution is not possible since we have one too few parameters, but the whole purpose of approximation is to define what we mean by a good solution that cannot be exact. The data with respect to the parameters is the same as would be for the A-split example, and if this data did come from that problem then the value error would be 0. The fact that two distinct problems can appear the same but have different true value error might seem to be a problem, but the difference is value error is always a variance term which does not depend on the parameters but only on the stochastic nature of the problem. From that perspective, the A-split example has zero value error for these parameters because the true value from state A is always $\frac{1}{2}$ while the the A-presplit example the true value of A1 and A2 is not $\frac{1}{2}$ but that information is hidden from the approximation.
TDC Learned Policy
Total Reward: -173.0f0
Notice there is a point where the Bellman operator produces the true value function. At this point the Bellman Error equals the value error though neither of them are minimized. It is unclear if other problems have a point in general for which this occurs. The point approximation point is just something for which if the values were initialized there then one sweep of dynamic programming would produce the correct value. Note that the projected Bellman error vector also suggests a direction of change for the parameter which is used when we do semi-gradient TD(0). You could also project the value error and the point for which this is 0 is also the point of minimum VE. The problem with this objective is that we cannot observe the true value. The Bellman operator on the approximation however can always be evaluated from the environment or if not that then at least a sample of it. There is also a point for which the mean squared TD error is equal to the mean squared Bellman error. We can see the two vectors that make up the TD error together are equivalent to the Bellman Operator. With the TD error we minimize the sum of the lengths of these vectors whereas minimizing the Bellman error is minimizing the length of the sum of the vectors. When these equal, the Bellman operator points along the line of approximation functions. So at this particular w, the Bellman operator produces another value function which is in the approximation space.
Exercise 11.2
Convert the equations of $n\text{-step} \; Q(\sigma)$ (7.11 and 7.17) to semi-gradient form. Give definitions that cover both the episodic and continuing cases.
$$\begin{flalign} Q_{t+n} & \doteq Q_{t+n-1}(S_t, A_t) + \alpha \rho_{t+1:t+n}[G_{t:t+n} - Q_{t+n-1}(S_t, A_t)] \tag{7.11}\\ G_{t:h} & \doteq R_{t+1} + \gamma \left ( \sigma_{t+1}\rho_{t+1} + (1 - \sigma_{t+1} \pi(A_{t+1}|S_{t+1}) \right ) \left ( G_{t+1:h} - Q_{h-1}(S_{t+1}, A_{t+1}) \right )\\ & + \gamma \bar V_{h-1}(S_{t+1}) \tag{7.17}\\ \bar V_t(s) & \doteq \sum_a \pi(a|s)Q_t(s, a) \end{flalign}$$
To convert this to a semi-gradient method we need to provide update equations for the weight vector that defines the value function approximation.
$$\begin{flalign} \mathbf{w}_{t+n} &\doteq \mathbf{w}_{t+n-1} + \alpha \rho_{t+1} \cdots \rho_{t+n} [G_{t:t+n} - \hat q(S_{t}, A_t, \mathbf{w}_{t+n-1})]\nabla \hat q (S_t, A_t, \mathbf{w}_{t+n-1})\\ G_{t:h} &\doteq R_{t+1} + \gamma \left ( \sigma_{t+1}\rho_{t+1} + (1 - \sigma_{t+1} \pi(A_{t+1}|S_{t+1}) \right ) \left ( G_{t+1:h} - \hat q(S_{t+1}, A_{t+1}, \mathbf{w}_{h-1}) \right )\\ & + \gamma \overline{V}_{h-1}(S_{t+1}), \text{\; for } t < h \leq T \tag{episodic}\\ G_{t:h} &\doteq R_{t+1} - \bar R_{t+1} + \gamma \left ( \sigma_{t+1}\rho_{t+1} + (1 - \sigma_{t+1} \pi(A_{t+1}|S_{t+1}) \right ) \left ( G_{t+1:h} - \hat q(S_{t+1}, A_{t+1}, \mathbf{w}_{h-1}) \right )\\ & + \gamma \bar V_{h-1}(S_{t+1}), \text{\; for } t < h \leq T \tag{continuing}\\ \overline{V}_t(s) & \doteq \sum_a \pi(a|s)\hat q(s, a, \mathbf{w}_t) \end{flalign}$$
There are 7 states, 2 actions, and 8 parameters. We can analytically write down the different errors in terms of the 8 parameter values for the target policy which always takes the solid action. Also, the on-policy distribution for the target policy is $\mu(7) = 1$ so we only need to consider there error for that state.
The true values are 0 for every state, so the value error is simply:
$$\overline{\text{VE}} = (w_7 + 2w_8)^2$$
which is minimized when $w_7 = -2w_8$
$$(0 + \gamma (w_7 + 2 w_8) - w_7 - 2 w_8)^2 = ((w_7 + 2w_8)(\gamma - 1))^2$$
If we minimize this with respect to $w_7$ and $w_8$
$$0 = 2(\gamma - 1)(w_7 + 2w_8) \implies w_7 = -2w_8$$
$$0 = 4(\gamma - 1)(w_7 + 2w_8) \implies w_7 = -2w_8$$
Normally, there are fewer parameters than states, so there is a single projection point which minimizes the distance from any true state value function to the approximation function. Here we have one more parameter, so there is a whole family of projections that are equally good and reproduce the exact value function. Again, the only state value error that matters is for state 7 whose value is given as
$$\begin{flalign} v_7 &= w_7 + 2w_8 \\ \end{flalign}$$
This distance is 0 for any parameters that satisfy this equality. To calculate the mean squared projected Bellman Error, we first take state 7 and apply the Bellman operator to it:
$$B_\pi(\hat v_7) = \gamma(w_7 + 2 w_8)$$
Given this new value, which parameters satisfy the projection? We can pick any new value which satisfies $\gamma (w_7 + 2 w_8) = w_7^\prime + 2w_8^\prime$. One easy option that satisfies this relationship is just $w_7^\prime = \gamma w_7$ and $w_8^\prime = \gamma w_8$ so each parameter can just be multiplied by $\gamma$ to find the projection point. Now the projected Bellman error is the distance between these two values:
$$\overline{\text{PBE}} = ((w_7 + 2w_8) - \gamma (w_7 + 2 w_8))^2 = ((w_7 + 2 w_8)(1-\gamma))^2 = \overline{\text{VE}} (1-\gamma)^2$$
which is the same as the Bellman Error since the projection in this case can just match any value from the Bellman operator, and we already know this is minimized when $w_7 = -2w_8$ which is the same value that minimizes the value error.
Consider the value error under this approximation:
$$\begin{flalign} \overline{\text{VE}} &= \frac{1}{2} \left [ (\hat v_1 - v_1)^2 + (\hat v_2 - v_2)^2\right ] \\ &= \frac{1}{2}\left [\left ( w - \frac{\gamma}{1 - \gamma} \right )^2 + \left (cw - \frac{2-\gamma}{1-\gamma} \right )^2 \right ] \\ \end{flalign}$$
Our goal is to find the value of $w$ that minimizes the value error and we can use gradient updates to do this with the derivative:
$$\frac{\partial \overline{\text{VE}}}{\partial w} = w - \frac{\gamma}{1 - \gamma} + c^2w - c\frac{2-\gamma}{1-\gamma}$$
Setting this equal to 0 implies:
$$\begin{flalign} w(1 + c^2) &= \frac{\gamma + 2c - c \gamma}{1 - \gamma} \\ &\therefore \\ w &= \frac{\gamma + 2c - c \gamma}{(1 - \gamma)(1 + c^2)} \\ &= \frac{\gamma(1 - c) + 2c}{(1 - \gamma)(1 + c^2)} \\ \end{flalign}$$
DP Learned Policy
Total Reward: -135.0f0
mimetext/htmlrootassigneelast_run_timestampA ~Džpersist_js_state·has_pluto_hook_features§cell_id$5c87ea86-aec5-42d3-9423-4cd9d14dbc97depends_on_disabled_cells§runtime µpublished_object_keys57cd57c4c-38f6-11f0-1841-758f50f1faa4/7a8906f9f6047da9depends_on_skipped_cellsçerrored$344a94a8-58ad-4cb5-ad1c-dcf779a6ea76queued¤logsrunning¦outputbody2tdc_control_baird (generic function with 1 method)mimetext/plainrootassigneelast_run_timestampA yqpersist_js_state·has_pluto_hook_features§cell_id$344a94a8-58ad-4cb5-ad1c-dcf779a6ea76depends_on_disabled_cells§runtime صpublished_object_keysdepends_on_skipped_cellsçerrored$822bc5a4-8aa4-454f-8da0-a1d081b93c55queued¤logsrunning¦outputbody0make_baird_mdps (generic function with 1 method)mimetext/plainrootassigneelast_run_timestampA q2'persist_js_state·has_pluto_hook_features§cell_id$822bc5a4-8aa4-454f-8da0-a1d081b93c55depends_on_disabled_cells§runtime published_object_keysdepends_on_skipped_cells§errored$5960d4a9-5493-41d8-a98f-e9d91e34fa79queued¤logslinemsgNWeights for value function approxmation will diverge with dynamic programming and direct minimization since γ > 5/(6-4ϵ)): 0.9 > 0.8338892595063375 Since the weight is initialized at 0 it is already at the value for perfect approximation the updates will not diverge. Any starting value other than this will have a problem though. text/plaincell_id$5960d4a9-5493-41d8-a98f-e9d91e34fa79kwargsidPlutoRunner_d1acb81efileP/home/runner/.julia/packages/Pluto/5ete1/src/runner/PlutoRunner/src/io/stdout.jlgroupstdoutlevelLogLevel(-555)running¦outputbodyi mimetext/htmlrootassigneelast_run_timestampA w߰persist_js_state·has_pluto_hook_features§cell_id$5960d4a9-5493-41d8-a98f-e9d91e34fa79depends_on_disabled_cells§runtimepublished_object_keys57cd57c4c-38f6-11f0-1841-758f50f1faa4/ce0d48221790b111depends_on_skipped_cellsçerrored$4fd5b88f-eb4b-415b-9f8e-781dd4e194d0queued¤logsrunning¦outputbodyAThis policy takes the "dashed" action $\frac{6}{7}$ of the time in order to equalize the probability of visiting each state.
Since all of the rewards are 0, this MRP is solved exactly when both state values are 0:
$$v_1 = 0$$
$$v_2 = 0$$
The value error is just the squared error between the approximate solution and the exact solution weighted by the on-policy distribution. Since both state values are just multiples of $w$, the exact solution is trivial to find: $w = 0 \implies \hat v_1 = 0, \hat v_2 = 0$
At the TD Fixed-Point the expected TD update is 0 for both states which is given by:
State 1:
$$w_{k+1} = w_k + \alpha [ \gamma 2 w_k - w_k ] = w_k(1 + \alpha(2 \gamma - 1))$$
State 2:
$$w_{k+1} = w_k + \alpha 2[(1 - \epsilon) \gamma 2 w_k - 2 w_k] = w_k(1 + 4\alpha((1-\epsilon)\gamma - 1))$$
Since both updates involve the learning rate times a multiple of $w_k$ then this update is only 0 when $w_k = 0$ which is the correct value. Since this problem is solved exactly with $w = 0$, the solution that minimizes the value error matches the TD Fixed-Point.
Consider a MRP with just two states each of which have two equally probable transitions. The first state can transition into itself or to the second state, both with zero reward. The second state can transition to itself or to the first state, both with a reward of 2. We can define the MDP as a tabular problem as follows:
γ:
w1:
w2:
With approximation, state values affect eachother which necessitated the value error objective $\overline{\text{VE}} = \sum_{s} \mu_\pi(s) \left ( \hat v_\pi(s) - v_\pi(s) \right )^2$. Since we do not know $v_\pi$, it must be approximated somehow and the only method that generates unbiased samples is the Monte Carlo return $G_t$ since $\mathbb{E}_\pi[G_t \mid S_t = s] = v_\pi(s)$. In continuing tasks, however, this objective is not available, so we must rely on bootstrapping in which some number of rewards are observed, but then the approximation function itself is used to complete the target value. In Chapter 9, we saw that if we use the semi-gradient parameter update with this objective, it converges to the TD fixed point which may not equal the point of minimum value error. As we will see later, at the TD fixed point, the projected Bellman error is 0. All of this convergence, however, depended upon the semi-gradient updates actually using the value error objective which uses $\mu_\pi$. If we instead try to do the same updates but sample the states differently, then the convergence guarantees from before do not apply.
Since the root of the problem with function approximation is the connection between state values, we can illustrate some pathological cases by forcing a relationship between state values that causes problems. Consider a portion of an MDP with a single parameter $\mathbf{w}$ and two states whose approximations are $w$ and $2w$. Furthermore, consider that from the first state, there is only one transition deterministically into the second state with a reward of 0. If we try to estimate the state values with sampling the TD(0) error, then the target value will be $R_{t+1} + \gamma \hat v(S_{t+1}, \mathbf{w}_t) = 0 + \gamma2w_t = \gamma2w_t$ and the error term $\delta_t = \gamma2w_t - w_t = w_t(2\gamma - 1)$. So the paramter update will be:
$$w_{t+1} = w_t + \alpha \rho_t \delta_t \nabla \hat v(S_t, w_t) = w_t + \alpha w_t (2\gamma - 1) w_t = w_t(1 + \alpha(2\gamma - 1))$$
So the parameter update involves multiplying the value by some number: $w_{t+1} = cw_t$ and if $c>1$ for all updates then this process is unstable and the parameter will grow in magnitude indefinitely. In this case $c = 1 + \alpha (2\gamma - 1)$ so the process is unstable when $\alpha(2\gamma - 1) \gt 0$ where $0 \leq \gamma \lt 1$. Since $\alpha > 0$ the only condition that matters is $2\gamma - 1 \gt 0 \implies \gamma \gt 0.5$. This assumes that $w$ will never be updated from a transition out of state 2 since that transition could occur with 0 probability under the target policy so the importance sampling ratio would be 0. Later on we will construct an example where this exact scenario happens. While divergence may only occur in the off-policy case, this can still result in different value estimates depending on which objective is used.
Now let's calculate the parameters that minimize the mean square TD error. Instead of applying the parameter update rule, we can solve directly for the minimizing parameters using the definition of the objective:
$$\overline{\text{TDE}} = \mathbb{E}_b [\rho_t \delta_t^2]$$
There are four distinct TD errors as shown above. The two for state A have equal probability and $\mu_A = \frac{1}{2}$ so each TD error will occur with $\frac{1}{4}$ probability:
$$\begin{flalign} \overline{\text{TDE}} &= \mathbb{E}_b [\rho_t \delta_t^2] \\ &= \frac{1}{4}\left ( (w_B - w_A)^2 + (w_C - w_A)^2 + (1 - w_B)^2 + w_C^2 \right ) \\ &= \frac{1}{4} \left ( 2w_B^2 - 2 w_B w_A + 2w_A^2 + 2w_C^2 - 2 w_A w_C+ 1 - 2 w_B \right ) \end{flalign}$$
Next consider the gradient with respect to each parameter which will be 0 at convergence to the minimum
$$\begin{flalign} \frac{\partial \overline{\text{TDE}}}{\partial w_A} &= \frac{1}{4} \left ( -2 w_B + 4w_A - 2 w_C \right ) = \frac{1}{2}(2w_A - w_B - w_C)\\ \frac{\partial \overline{\text{TDE}}}{\partial w_B} &= \frac{1}{4} \left (4w_B - 2w_A - 2 \right ) = \frac{1}{2}(2w_B - w_A - 1)\\ \frac{\partial \overline{\text{TDE}}}{\partial w_C} &= \frac{1}{4} \left ( 4w_C - 2w_A \right ) = \frac{1}{2}(2w_C - w_A)\\ \end{flalign}$$
Setting the three components to 0 implies the following
$$\begin{flalign} 0 &= 2w_A - w_B - w_C \implies 2w_A = w_B + w_C \\ 0 &= 2w_B - w_A - 1 \implies 2w_B = 1 + w_A\\ 0 &= 2w_C - w_A \implies 2w_C = w_A\\ \end{flalign}$$
Using the last two expressions we can change the first expression into one just in terms of $w_A$: $4w_A = 1 + w_A + w_A \implies w_A = \frac{1}{2}$
Then the other weights follow: $w_B = \frac{1}{2} (1 + \frac{1}{2}) = \frac{3}{4}$ and $w_C = \frac{1}{4}$
$$\begin{flalign} w_A &= \frac{1}{2} = v_A \\ w_B &= \frac{3}{4} \ne v_B \\ w_C &= \frac{1}{4} \ne v_C \end{flalign}$$
So even though an exact solution is possible, minimizing the $\overline{\text{TDE}}$ does not find it. For Monte Carlo gradient and semi-gradient TD methods developed earlier, the tabular approximation case always reduced to the tabular methods from part 1. This simple example shows that is not the case for the mean square TD objective.
One natural choice for objective function is to take the squared sum of the Bellman error at each state weighted by the probability of visiting that state while following the target policy. We call this objective the mean square Bellman error and it is defined as:
$$\begin{flalign} \overline{\text{BE}} & \doteq \sum_s \mu_\pi(s) \overline{\delta}_\mathbf{w}(s)^2 \\ &= \sum_s \mu_\pi(s) \left ( (B_\pi \hat v)(s) - \hat v (s) \right )^2 \\ &= \sum_s \mu_\pi(s) \left [ \sum_a \pi(a\vert s)\sum_{s^\prime, r} p(s^\prime, r \vert s, a)[r + \gamma \hat v (s^\prime)] - \hat v (s) \right ]^2 \\ \end{flalign}$$
In the diagram in the previous section this error is represented by the length of a vector which points from the initial approximation point to the Bellman operator applied to that point. Since that diagram represents a two state MDP, the point's position on the graph represents both values.
$$\mathbf{v}_{t+1} \doteq \mathbf{v}_t + \beta \rho_t \left ( \delta_t - \mathbf{v}_t^\top\mathbf{x}_t \right ) \mathbf{x}_t$$
$$\begin{flalign} \mathbf{w}_{t+1} &= \mathbf{w}_t + \alpha \left ( \mathbb{E} [\rho_t \delta_t \mathbf{x}_t ] - \gamma \mathbb{E} \left [ \rho_t \mathbf{x}_{t+1} \mathbf{x}_t ^\top \right ] \mathbf{v}_t \right ) \\ &\approx \mathbf{w}_t + \alpha \rho_t \left ( \delta_t \mathbf{x}_t - \gamma \mathbf{x}_{t+1} \mathbf{x}_t ^ \top \mathbf{v}_t \right )\tag{sampling} \end{flalign}$$
Discount Rate:
Linear Constant:
Evaluation Weight:
Select discount rate for MRP evaluation
Consider a stochastic episodic environment with three states: A, B, C. Episodes always begin in state A and have an equal chance of transitioning into B or C with 0 reward. Episodes always terminate from states B and C with a reward of 1 and 0 respectively. Since this problem is an MRP, there are no policies and thus no consideration of off-policy learning or importance sampling ratios. Since the problem is episodic, we can consider the undiscounted case $\gamma = 1$. Given these constraints, the true state values are easy to determine.
$$\begin{flalign} v_B &= 1 \\ v_C &= 0 \\ v_A &= \frac{1}{2}(v_B + v_C) = \frac{1}{2} \end{flalign}$$
Consider the case of approximation but with three parameters $w_A, w_B, w_C$ so that an exact solution is possible with $w_A = \frac{1}{2}, w_B = 1, w_C = 0$ where each parameter matches the corresponding state value:
$$\begin{flalign} \hat v_A &= w_A \\ \hat v_B &= w_B \\ \hat v_C &= w_C \\ \end{flalign}$$
Approximation methods must also take into account $\mu(s)$. Episodes always begin in state A and split evenly into B and C before terminating, so $\mu_A = 2 \mu_B = 2 \mu_C$ and $\mu_B = \mu_C$. From these relationships we can solve for the state distribution:
$$\begin{flalign} \mu_A &= \frac{1}{2} \\ \mu_B &= \frac{1}{4} \\ \mu_C &= \frac{1}{4} \\ \end{flalign}$$
With three parameters this is a tabular problem, and we have already established that Monte Carlo gradient methods will converge to the exact solution in this case. The semi-gradient TD(0) method should also converge to the exact solution since the minimum value-error is 0, but we can also verify this by studying the update rule:
With a true SGD method for off-policy training, we would not have to worry about divergence even under non-linear approximation. One of the most popular proposed objectives for SGD is the Bellman error. Consider first the effect of applying the Bellman operator on a given state value function approximation $\hat v(s)$
$$(B_\pi \hat v)(s) \doteq \sum_a \pi(a\vert s)\sum_{s^\prime, r} p(s^\prime, r \vert s, a)[r + \gamma \hat v (s^\prime)$$
The Bellman error at state $s$ is the difference between the value at state s and the Bellman operator value:
$$\overline{\delta}_\mathbf{w}(s) \doteq (B_\pi \hat v)(s) - \hat v (s)$$
We know that for the true value function $v_\pi$, the effect of applying the Bellman operator is to leave the value unchanged:
$$(B_\pi v_\pi)(s) = v_\pi(s) \; \forall s$$
So for the true value function the Bellman error is 0 at every state. In the tabular methods for part 1 of the book, we sought to find this unique value function for which the Bellman error is 0 at every state and the value error is also 0 at every state. When we deal with approximation, however, it is impossible to guarantee 0 Bellman error, so we must define a different objective like we did for the value error, one that weights the errors at each state by the on-policy distribution. This distribution is irrelevant for tabular methods since the final result will have 0 error at every state.
We can use the Bellman equations to calculate the true state values for both MDPs
$$\begin{flalign} v_A &= 0 + \gamma v_B \implies v_A = \gamma v_B \\ v_B &= \frac{1}{2} \left (-1 + \gamma v_B + 1 + \gamma v_A \right ) = \frac{\gamma}{2}(v_B + v_A) \\ &\text{combining the two expressions we can get an equation just for the value of state B} \\ v_B &= \frac{\gamma}{2}(v_B + \gamma v_B) \implies v_B = \frac{\gamma v_B}{2}(1 + \gamma) \end{flalign}$$
Given that $0 \le \gamma \lt 1$, this equality is only possible when $v_B = 0 \implies v_A = 0$ and these values are independent of $\gamma$
$$\begin{flalign} v_A &= \frac{1}{2} \left ( 0 + \gamma v_B + 0 + \gamma v_{B^\prime} \right ) = \frac{\gamma}{2} \left ( v_B + v_{B^\prime} \right ) \\ v_B &= 1 + \gamma v_A \\ v_B^\prime &= \frac{1}{2} \left ( -1 + \gamma v_{B^\prime} - 1 + \gamma v_B \right ) = -1 + \frac{\gamma}{2} \left (v_{B^\prime} + v_B) \right ) = -1 + v_A \\ &\text{Using the last two expressions, we can derive an equation involving only the value of state A} \\ v_A &= \frac{\gamma}{2}(1 + \gamma v_A - 1 + v_A) = \frac{\gamma v_A}{2} (\gamma + 1) \\ \end{flalign}$$
Given that $0 \le \gamma \lt 1$, this equality is only possible when $v_A = 0$. The other two values follow immediately giving a complete value function of:
$$\begin{flalign} v_A &= 0 \\ v_B &= 1 \\ v_B^\prime &= -1 \\ \end{flalign}$$
which like the first is independent of $\gamma$.
Given two points on the approximation line defined by $w_1$ and $w_2$, the squared distance between them is just:
$$(w_1 - w_2)^2 + (c w_1 - c w_2)^2 = (w_1 - w_2)^2 (1 + c)$$
Using this formula we can also write down explicitely the projected Bellman Error:
$$\begin{flalign} B_\pi \hat v &= \left (\frac{\gamma w (1 + c)}{2}, \frac{4 + \gamma w (1+c)}{2} \right ) \\ w_{\text{min}} &= \frac{\gamma w (1+c) + c(4 + \gamma w (1+c))}{2(1+c^2)} \\ \vert \text{PBE} \vert &= \left ( w - \frac{\gamma w (1+c) + c(4 + \gamma w (1+c))}{2(1+c^2)} \right )^2 (1+c) \\ &= \left ( \frac{2w(1+c^2) - \gamma w (1+c) - c(4 + \gamma w (1+c))}{2(1+c^2)} \right )^2 (1+c) \\ &= \left ( 2w(1+c^2) - \gamma w (1+c) - c(4 + \gamma w (1+c)) \right )^2 \frac{(1+c)}{4(1+c^2)^2} \\ &= \left ( w(2(1+c^2) - \gamma (1+c) - c\gamma(1+c)) -4c \right )^2 \frac{(1+c)}{4(1+c^2)^2} \\ &\therefore \\ \frac{\partial \vert \text{PBE} \vert }{\partial w} &= \left ( w(2(1+c^2) - \gamma (1+c) - c\gamma(1+c)) -4c \right ) \frac{(1+c)(2(1+c^2) - \gamma (1+c) - c\gamma(1+c))}{2(1+c^2)^2} \\ \end{flalign}$$
Setting this equal to 0 implies the $w$ which minimies the projected Bellman Error is:
$$\begin{flalign} w_{\text{min}} = \frac{4c}{2(1+c^2) - \gamma (1+c)^2} \end{flalign}$$
$$\overline{\text{BE}} = \sum_{s} \mu_s \mathbb{E}_\pi \left [ R_{t+1} + \gamma \hat v(S_{t+1}) - \hat v(S_t) \mid S_t = s \right ] ^2$$
Since the problem is tabular, we'd expect the Bellman error to be 0 with the exact solution. We can verify the solution using the above expression for the Bellman error:
$$\begin{flalign} \overline{\text{BE}} &= \frac{1}{3}(0 + \gamma w_2 - w_1)^2 + \frac{2}{3}\left [ \frac{1}{2}(-1 + \gamma w_2 - w_2 + 1 + \gamma w_1 - w_2) \right ]^2 \\ &= \frac{1}{3}(\gamma w_2 - w_1)^2 + \frac{2}{12}\left [w_2 (\gamma - 2) + \gamma w_1 \right ]^2 \\ \end{flalign}$$
We can already see that the minimum value of 0 is achieved when $w_1 = w_2 = 0$, but we can also verify this by setting each term of the gradient to 0:
$$\begin{flalign} \frac{\partial \overline{\text{BE}}}{\partial w_1} &= \frac{2}{3}(\gamma w_2 - w_1) \times -1 + \frac{4}{12}(w_2(\gamma - 2) + \gamma w_1) \times \gamma\\ &= \frac{2}{3}(\gamma w_2 - w_1) \times -1 + \frac{4}{12}(w_2(\gamma - 2) + \gamma w_1) \times \gamma\\ &= \frac{\gamma}{3} (w_2 \left (\gamma - 4 \right ) + w_1 \left ( 2 + \gamma \right )) \\ &\therefore \\ w_1 &= w_2 \frac{\gamma - 4}{2 + \gamma} \\ \frac{\partial \overline{\text{BE}}}{\partial w_2} &= \frac{2}{3}(\gamma w_2 - w_1) \times \gamma + \frac{4}{12}(w_2(\gamma - 2) + \gamma w_1) (\gamma - 2)\\ &= \frac{1}{3} \left [ 2\gamma(\gamma w_2 - w_1) + (\gamma - 2)^2 w_2 + \gamma (\gamma - 2) w_1 \right ]\\ &= \frac{1}{3} \left [ \gamma w_1(\gamma - 4) + w_2(3\gamma^2 - 4\gamma + 4) \right ]\\ & \therefore \\ w_1 &= w_2 \frac{3\gamma^2 - 4\gamma + 4}{\gamma(\gamma - 4)} \end{flalign}$$
Since two fractions are not equal, this equality is only satisfied when $w_1 = w_2 = 0$ which is the same exact solution we had earlier with a Bellman error of 0.
Even though the problem appears the same with respect to the state representation, the Bellman error expression will differ for the second problem since we must separate the terms by state.
$$\begin{flalign} \overline{\text{BE}} &= \frac{1}{3} \left [ (0 + \gamma w_2 - w_1)^2 + (1 + \gamma w_1 - w_2)^2 + (-1 + \gamma w_2 - w_2)^2 \right ]\\ &\therefore \\ \frac{\partial \overline{\text{BE}}}{\partial w_1} &= \frac{2}{3} \left [ (\gamma w_2 - w_1)\times -1 + (1 + \gamma w_1 - w_2)\times \gamma \right ] \\ &= \frac{2}{3} \left [ w_1(1 + \gamma^2) - 2\gamma w_2 + \gamma \right ] \\ &\therefore \\ w_1 &= \frac{2\gamma w_2 - \gamma}{1 + \gamma^2} = w_2 \frac{2 \gamma}{1+\gamma^2} - \frac{\gamma}{1 + \gamma^2} \\ \frac{\partial \overline{\text{BE}}}{\partial w_2} &= \frac{2}{3} \left [ (\gamma w_2 - w_1)\times \gamma - (1 + \gamma w_1 - w_2) + (w_2(\gamma - 1) - 1)(\gamma - 1) \right ] \\ &= \frac{2}{3} \left [ -2\gamma w_1 + w_2(\gamma ^2 + 1 + (\gamma - 1)^2) - 1 - \gamma + 1\right ] \\ &= \frac{2}{3} \left [ w_2(2\gamma ^2 - 2\gamma + 2) -2\gamma w_1 - \gamma \right ] \\ &\therefore \\ w_1 &= \frac{2w_2(\gamma^2 - \gamma + 1) - \gamma}{2\gamma} = w_2 \frac{\gamma^2 - \gamma + 1}{\gamma} - \frac{1}{2}\\ &\therefore w_2 \frac{2 \gamma}{1+\gamma^2} - \frac{\gamma}{1 + \gamma^2} = w_2 \frac{\gamma^2 - \gamma + 1}{\gamma} - \frac{1}{2} \\ &w_2 \left [ \frac{2 \gamma}{1+\gamma^2} -\frac{\gamma^2 - \gamma + 1}{\gamma} \right ] = \frac{\gamma}{1 + \gamma^2} - \frac{1}{2} \\ \end{flalign}$$
Clearly this answer depends on $\gamma$ unlike the previous solutions. In the limit of $\gamma \rightarrow 1$, we can calculate the optimal weights according to the Bellman error:
$$w_2 = 0 - (1 - 1) = 0 \implies w_1 = w_2 - \frac{1}{2} = -\frac{1}{2}$$
which does not match the solution we had for the minimum value error.
The following weight updates are calculated to minimize the average estimation error for each transition weighted by the probability of experiencing that transition. (Note that vs equation (9.1) this is missing the on policy distribution over states).
$$\begin{flalign} w_{k+1} &= \text{argmin}_{w \in \mathbb{R}} \enspace \sum_{s \in \mathcal{S}} \left ( \hat v(s, w) - \mathbb{E}_\pi[R_{t+1} + \gamma \hat v(S_{t+1}, w_k) | S_t = s] \right )^2\\ &= \text{argmin}_{w \in \mathbb{R}} \enspace (w - \gamma2w_k)^2 + (2w - (1-\epsilon)\gamma2w_k)^2\\ \therefore\\ \frac{\partial{w_{k+1}}}{\partial w} &= 2(w - \gamma2w_k) + 4(2w - (1-\epsilon)\gamma2w_k) = 10w - 4\gamma w_k - 8(1-\epsilon)\gamma w_k\\ &\text{setting this equal to 0 results in }\\ 10w &= 4\gamma w_k + 8(1-\epsilon)\gamma w_k = 4 \gamma w_k (3 - 2\epsilon)\\ w &= \gamma w_k \frac{4(3 - 2\epsilon)}{10} = \gamma w_k \frac{6 - 4\epsilon}{5} \end{flalign}$$
What if $\gamma > \frac{5}{6-4\epsilon}$? In this case the factor multiplying $w_k$ on each update is greater than 1, thus the weight will diverge under any condition except where the initial value is 0.
We are still safe if the threshold exceeds 1 since for this problem $\gamma \le 1$ and we know that $0 \lt \epsilon \lt 1$ so we will never see divergence when $5 \gt 6 - 4\epsilon \implies 4\epsilon \gt 6 - 5 \implies \epsilon \gt \frac{1}{4}$
Indeed, in the plot below, when $\epsilon \ge \frac{1}{4}$ the $\gamma$ threshold is greater than 1 and we are guaranteed convergence. Note that the larger the value of $\epsilon$ the closer the expected state visit counts get to each other so we approach the on policy case again.
The values of this MRP can be solved exactly with the Bellman equation given a discount rate $\gamma$: $v(s) = \mathbb{E}[R_t + \gamma v(S_{t+1}) \mid S_t = s]$
$$\begin{flalign} v_1 &= \frac{1}{2} [(0 + \gamma v_2) + (0 + \gamma v_1)] = \frac{\gamma}{2}(v_1 + v_2) \\ v_2 &= \frac{1}{2} [(2 + \gamma v_1) + (2 + \gamma v_2)] \\ &= 2 + \frac{\gamma}{2}(v_1 + v_2) \\ &= 2 + v_1 \\ &\therefore \\ v_1 &= \frac{\gamma}{2}(v_1 + 2 + v_1) \\ &= \gamma(1 + v_1) \\ &\therefore \\ \gamma &= v_1(1 - \gamma) \implies v_1 = \frac{\gamma}{1 - \gamma}, v_2 = 2 + \frac{\gamma}{1 - \gamma} = \frac{2-\gamma}{1-\gamma} \end{flalign}$$
Discount Rate:
Initial Value 1:
Initial Value 2:
Consider the A-split example from before but converted into a deterministic problem by separating state A into two parts each of which does a deterministic transition either into state B or C. The exact solution is trivial for the four state values:
$$\begin{flalign} v_B &= 1 \\ v_C &= 0 \\ v_{A1} &= 0 + v_B = 1 \\ v_{A2} &= 0 + v_C = 0 \\ \end{flalign}$$
There are four deterministic states in this MRP, but we will consider approximate solutions in which both A states share a single parameter.
$$\begin{flalign} \hat v_{A1} = w_A \\ \hat v_{A2} = w_A \\ \hat v_B = w_B \\ \hat v_C = w_C \\ \end{flalign}$$
Equal time is spent in all four states since episodes start in either A1 or A2 with equal probability. From the perspective of the approximation parameter, $w_A$ will appear $\frac{1}{2}$ of the time while $w_B$ and $w_C$ will appear $\frac{1}{4}$ of the time, so this problem appears the same as the A-split example with respect of $\mathbf{w}$
mimetext/htmlrootassigneelast_run_timestampA fzpersist_js_state·has_pluto_hook_features§cell_id$6edbe471-361c-463a-b942-3ecbd879c427depends_on_disabled_cells§runtime _published_object_keysdepends_on_skipped_cells§errored$c8bae838-0549-48e3-b858-0c071334c0b7queued¤logslinemsg?WARNING: could not import FCANN.cuda_allocate into workspace#5 text/plaincell_id$c8bae838-0549-48e3-b858-0c071334c0b7kwargsidPlutoRunner_d1acb81efileP/home/runner/.julia/packages/Pluto/5ete1/src/runner/PlutoRunner/src/io/stdout.jlgroupstdoutlevelLogLevel(-555)running¦outputbody"# This file is machine-generated - editing it directly is not advised\n\njulia_version = \"1.11.4\"\nmanifest_format = \"2.0\"\nproject_hash = \"f96742aa2407e40995be21bd65f67a020afa7644\"\n\n[[deps.AbstractPlutoDingetjes]]\ndeps = [\"Pkg\"]\ngit-tree-sha1 = \"6e1d2a35f2f90a4bc7c2ed98079b2ba09c35b83a\"\nuuid = \"6e696" ⋯ 19342 bytes ⋯ " \"8e850b90-86db-534c-a0d3-1478176c7d93\"\nversion = \"5.11.0+0\"\n\n[[deps.nghttp2_jll]]\ndeps = [\"Artifacts\", \"Libdl\"]\nuuid = \"8e850ede-7688-5339-a07c-302acd2aaf8d\"\nversion = \"1.59.0+0\"\n\n[[deps.p7zip_jll]]\ndeps = [\"Artifacts\", \"Libdl\"]\nuuid = \"3f19e933-33d8-53b3-aaab-bd5110c3b7a0\"\nversion = \"17.4.0+2\"\n"mimetext/plainrootassigneelast_run_timestampA qQ"persist_js_state·has_pluto_hook_features§cell_id$c8bae838-0549-48e3-b858-0c071334c0b7depends_on_disabled_cells§runtimeapublished_object_keysdepends_on_skipped_cells§errored$256efb33-1b85-4fbb-be51-e43384fd149cqueued¤logsrunning¦outputbodyxNote that as $\epsilon \rightarrow 1$, the on policy distribution approaches the case of equal visit time. That explains why the convergence is no longer unstable if $\epsilon$ is larger than a certain value which is $\frac{1}{4}$ in this case.
I applied one-step semi-gradient Q-learning to Baird's counterexample extending the feature vectors by 2 elements to represent the two actions. After checking different intial weight vectors and ϵ values, both sarsa and q-learning seem to converge to show no preference for actions and value estimates of 0. While the weights may diverge momentarily, after enough time steps it converges over a range of parameter values. In the section describing the counter example it mentions that with the ϵ greedy behavior policy in Q-learning it has not been found to diverge, so I'm not sure why the weights would be expected to diverge here. Notice that the weights do diverge at first but then begin to converge to the correct values even with $\epsilon = 0.99$. The convergence shift seems to occur around the same time of the optimal policy changing to favor action 1 instead of action 2.
Select policy:
Select initial value:
* Exercise 11.4
Prove (11.24). Hint: Write the $\overline{\text{RE}}$ as an expectation over possible states $s$ of the expectation of the squared error given that $S_t = s$. Then add and subtract the true value of state $s$ from the error (before squaring), grouping the subtracted true value with the return and the added true value with the estimated value. Then if you expand the square, the most complex term will end up being zero, leaving you with (11.24).
$$\overline{\text{RE}}(\mathbf{w}) = \overline{\text{VE}}(\mathbf{w}) + \mathbb{E}_\pi \left [ \left ( G_t - v_\pi(S_t) \right )^2 \right ] \tag{11.24}$$
To start out we have the definition of the mean square return error
$$\overline{\text{RE}}(\mathbf{w}) = \mathbb{E}_\pi \left [ (G_t - \hat v(S_t, \mathbf{w}))^2 \right ]$$
Also we can note from Chapter 3 that
$$v_\pi(s) = \mathbb{E}_\pi[G_t | S_t = s] \tag{1}$$
and from Chapter 9 that
$$\overline{\text{VE}}(\mathbf{w}) \doteq \sum_{s \in \mathcal{S}} \mu(s) \left [ v_\pi(s) - \hat v(s, \mathbf{w}) \right ]^2 \tag{2}$$
Rewriting expectation results in:
$$\begin{flalign} \overline{\text{RE}}(\mathbf{w}) &= \sum_s \mu_\pi(s) \mathbb{E_\pi}\left [ (G_t - \hat v(S_t, \mathbf{w}))^2 | S_t = s \right ]\\ &= \sum_s \mu_\pi(s) \mathbb{E_\pi}\left [ (G_t - \hat v(S_t, \mathbf{w}) + v_\pi(S_t) - v_\pi(S_t))^2 | S_t = s \right ]\\ &= \sum_s \mu_\pi(s) \mathbb{E_\pi}\left [ ((G_t - v_\pi(S_t)) + (v_\pi(S_t) - \hat v(S_t, \mathbf{w})))^2 | S_t = s\right ]\\ &= \sum_s \mu_\pi(s) \mathbb{E_\pi} \left [ (G_t - v_\pi(S_t))^2 + (v_\pi(S_t) - \hat v(S_t, \mathbf{w}))^2 + 2((G_t - v_\pi(S_t))(v_\pi(S_t) - \hat v(S_t, \mathbf{w}))) | S_t = s \right ]\\ &= \mathbb{E}\left [ (G_t - v_\pi(S_t))^2 \right ] + \sum_s \mu_\pi(s) \left [v_\pi(s) - \hat v(s, \mathbf{w}) \right ]^2 + \sum_s 2\mu_\pi(s) \left [ \mathbb{E_\pi}[G_t | S_t = s] (v_\pi(s) - \hat v(s, \mathbf{w})) - v_\pi(s)^2 + v_\pi(s) \hat v(s, \mathbf{w}) \right]\\ &= \mathbb{E}\left [ ((G_t - v(S_t))^2 \right ] + \overline{\text{VE}} + \sum_s 2\mu_\pi(s) \left [ v_\pi(s)^2 - \hat v(s, \mathbf{w}) v_\pi(s) - v_\pi(s)^2 + v_\pi(s) \hat v(s, \mathbf{w}) \right] \tag{by (1) and (2)}\\ &= \mathbb{E}\left [ ((G_t - v(S_t))^2 \right ] + \overline{\text{VE}} + \sum_s 2\mu_\pi(s) \times 0\\ &\therefore\\ \overline{\text{RE}}(\mathbf{w}) &= \mathbb{E}\left [ ((G_t - v(S_t))^2 \right ] + \overline{\text{VE}} \end{flalign}$$
What if we instead try to minimize the Bellman error? We fully know the dynamics of the problem, so we can directly find a solution without resorting to gradient methods.
$$\begin{flalign} \overline{\text{BE}} &= \sum_{s \in \mathcal{S}} \mu_\pi(s)\mathbb{E}_\pi [\delta_t \mid S_t = s]^2 \\ &= \frac{1}{4} \left [(w_B - w_A)^2 + (w_C - w_A)^2 + (1 - w_B)^2 + w_C^2 \right ]\\ \end{flalign}$$
But this is the same expression we had for the $\overline{\text{TDE}}$ for example 11.2, so the previous minimizing parameters will also apply here:
$$\begin{flalign} w_A &= \frac{1}{2} \\ w_B &= \frac{3}{4} \\ w_C &= \frac{1}{4} \end{flalign}$$
Obviously this differs from the minimum value error solution. What about the TD fixed point though? We know in general that the semi-gradient algorithm does not converge to the minimum value error, but would it perform better than the Bellman error in this case? Let's consider the TD(0) update rule and when it converges.
Prior to analyzing $\overline{\text{BE}}$, consider the one-step TD error that we often use as a starting point for bootstrap approximation methods:
$$\delta_t = R_{t+1} + \gamma \hat v (S_{t+1}) - \hat v(S_t)$$
This error term is always available by sampling from the environment, so let's consider an objective that directly uses this to as a minimization objective. For example, we could square the TD error to ensure it is always positive and weight it accoring to the target policy distribution. Such an objective is called the mean square TD error:
$$\begin{flalign} \overline{\text{TDE}}(\mathbf{w}) &= \sum_{s \in \mathcal{S}} \mu(s) \mathbb{E}[\delta_t^2 \mid S_t = s, A_t \sim \pi] \\ &= \sum_{s \in \mathcal{S}} \mu(s) \mathbb{E}[\rho_t \delta_t^2 \mid S_t = s, A_t \sim b] \\ &= \mathbb{E}_b [\rho_t \delta_t^2] \tag{if μ is the distribution encountered under b} \end{flalign}$$
The importance sampling ratio is first used to adjust the values from actions taken by the behavior policy. Notice that in the last step, however, if we sample an entire trajectory by the behavior policy, we will not weight updates according to the on-policy distribution $\mu_\pi(s)$ but rather according to $\mu_b (s)$. This can be sampled from the environment but represents a different objective. Although incorrect, a true SGD method will converge to this objective which eliminates one of the problems we previously had for off-policy training. We can derive the following update rule by taking the gradient of this objective assuming that our approximation function is parametrized by some weight vector $\hat v(s, \mathbf{w})$:
$$\begin{flalign} \mathbf{w}_{t+1} &= \mathbf{w}_t - \frac{1}{2} \alpha \nabla (\rho_t \delta_t^2) \\ &= \mathbf{w}_t - \alpha \rho_t \delta_t \nabla \delta_t \\ &= \mathbf{w}_t + \alpha \rho_t \delta_t \left ( \nabla \hat v(S_t, \mathbf{w}_t) - \gamma \nabla \hat v(S_{t+1}, \mathbf{w}_t) \right ) \tag{11.23} \\ \end{flalign}$$
This update rule is a true gradient method and converges to the minimum $\overline{\text{TDE}}$ as defined above. The algorithm which uses (11.23) to update weights is known as the naive residual-gradient algorithm. It appears very similar to the semi-gradient TD update with importance sampling:
$$\mathbf{w}_{t+1} = \mathbf{w}_t + \alpha \rho_t \delta_t \nabla \hat v (S_t, \mathbf{w}_t)$$
The only difference is the final term which turns this into a true SGD method. However, this method does not converge to the TD fixed point or the point of minimum value error in general which is not surprising considering the objective is different. As seen above in the linear value function diagram, this point may be undesireable since it is further away from the point of minimum value error. The subsequent example highlights another problem with this objective even in the on-policy case where the distribution of states is no longer a problem.
Instability and divergence arise when we combine the following three elements in solving an RL problem:
Function approximation Necessary to scale up techniques to large problems where the state/action space is too large to store.
Bootstrapping Important for data efficiency. If we cannot use any bootstrapping we may need to wait and store results for very long episodes and sometimes they aren't even guaranteed to terminate.
Off-policy training Often we could use Sarsa instead of Q-learning to remedy this, so avoiding off-policy training might be the best way to guarantee stability for now. However there will be cases in the future where off-policy training might be necessary such as estimating multiple policies at once.
The steady-state distribution for this MRP is also equal for both states, so each state value error should be weighted equally. Consider now an approximate solution using only a single parameter $w$. In general, the approximation function will depend on the feature vectors for each state but in this case that reduces to a single value. Consider an approximation function of the following form:
$$\begin{flalign} \hat v_1 &= w \\ \hat v_2 &= cw \\ \end{flalign}$$
where $c$ is some constant. Depending on the value of $c$ and $w$, there is an infinite family of approximation functions we can visualize in the 2D plane.
$$\begin{flalign} w_A &\leftarrow w_A + \alpha \left ( w_B - w_A \right ) \\ w_A &\leftarrow w_A + \alpha \left ( w_C - w_A \right ) \\ w_B &\leftarrow w_B + \alpha (1 - w_B) \\ w_C &\leftarrow w_C + \alpha (0 - w_C) \end{flalign}$$
These updates each occur with equal probability and are exactly the same as the expected updates for the A-spit example. Therefore, the solution will be the same and match the exactly solution for A-split and the solution which minimizes the value error for A-presplit:
$$\begin{flalign} w_A &= \frac{1}{2} \\ w_B &= 1 \\ w_C &= 0 \\ \end{flalign}$$
We did not attempt to show any bound for the Bellman error to ensure that its solution is close to the value error, but just from this example it is clear that there are examples where semi-gradient TD methods find the same solution as the minimum value error but the Bellman error minimum solution is different.
We can use the TDC algorithm to try to do a better job of Q-learning with linear approximation. Previously, we had used some value function approximation to learn action values and then try to follow the greedy policy while updating the values. With sarsa this was an on-policy method, but in the case of Q-learning we used the parameter update that takes the maximum action value while still following the $\epsilon$-greedy policy. Usually if $\epsilon$ isn't too large, this does not cause diverging weights, but there is always a risk of that happening. We can try to use the TDC method instead learn the greedy value function while still following the $\epsilon$-greedy one. We can update the policy after one or more update steps while tracking the approximation vectors used in TDC. Unlike in TDC estimation, we will not have an explicit target policy. The behavior policy will usually just be the $\epsilon$-greedy policy and change throughout training, but this method also means we can have a static behavior policy such as one that visits all states with equal probability.
Discount Rate:
Linear Constant:
Finally, consider the mean square TD error
$$\frac{1}{4} \left [ (\gamma w - w)^2 + (\gamma c w - w)^2 + (2 + \gamma w - cw)^2 + (2 + \gamma c w - c w)^2 \right ]$$
$$\frac{1}{4} \left [ w^2((\gamma -1)^2 + (\gamma c - 1)^2) + (2 + \gamma w - cw)^2 + (2 + \gamma c w - c w)^2 \right ]$$
$$\frac{1}{4} \left [ w^2((\gamma -1)^2 + (\gamma c - 1)^2) + (2 + w (\gamma - c))^2 + (2 + w c(\gamma - 1)^2 \right ]$$
$$\frac{1}{4} \left [ w^2((\gamma -1)^2 + (\gamma c - 1)^2) + 4 + 4w(\gamma - c) + w^2 (\gamma - c)^2 + 4 + 4wc(\gamma - 1) + w^2 c^2 (\gamma - 1)^2 \right ]$$
$$\frac{1}{4} \left [ w^2((\gamma -1)^2 + (\gamma c - 1)^2 + (\gamma - c)^2 + c^2(\gamma - 1)^2) + 4w(\gamma - 2c + c\gamma)) + 8\right ]$$
The difference between this and the Bellman error is that we take the expectation of the TD squared difference rather than the square of the expected TDE
Taking the derivative of this wrt $w$ yields
$$\frac{1}{4} \left [ 2w((\gamma -1)^2 + (\gamma c - 1)^2 + (\gamma - c)^2 + c^2(\gamma - 1)^2) + 4(\gamma - 2c + c\gamma))\right ]$$
$$\frac{1}{2}w((\gamma -1)^2 + (\gamma c - 1)^2 + (\gamma - c)^2 + c^2(\gamma - 1)^2) + \gamma - 2c + c\gamma$$
setting to 0 and solving for $w$
$$w = \frac{2(2c - \gamma (1 + c))}{(\gamma -1)^2 + (\gamma c - 1)^2 + (\gamma - c)^2 + c^2(\gamma - 1)^2}$$
In the first equation we didn't correctly account for the on policy distribution over states. To calculate this we need to first get the expected value of state visits. For simplicity assume that episodes always begin in state 1. The number of visits to state 1 will always be 1 since there is only one transition that leaves the state permanently. The expected number of visits to state 2 is:
$$\begin{flalign} \mathbb{E}[\eta(2)] &= \sum_{n = 1}^\infty n \Pr \{ \eta(2) = n \} \\ &= 1\epsilon + 2\epsilon(1-\epsilon) + 3\epsilon(1-\epsilon)^2 + 4\epsilon(1-\epsilon)^3 + \cdots \\ &=\epsilon\sum_{n=1}^\infty (1-\epsilon)^{n-1}n = \epsilon \frac{1}{\epsilon^2} = \frac{1}{\epsilon} \end{flalign}$$
If $\epsilon = 1$ then we only spend 1 visit in state 2 and as $\epsilon \rightarrow 0$ the system spends increasingly more time in state 2. To get the on-policy distribution we must normalize these visit counts to get the probabilities
$$\begin{flalign} \eta(1) &= 1\\ \eta(2) &= \frac{1}{\epsilon}\\ \sum_{s}\eta(s) &= 1 + \frac{1}{\epsilon} = \frac{1+\epsilon}{\epsilon}\\ \mu(1) &= \frac{\epsilon}{1+\epsilon}\\ \mu(2) &= \frac{1}{\epsilon}\frac{\epsilon}{1+\epsilon} = \frac{1}{1+\epsilon} \end{flalign}$$
Let's now return to the mean square Bellman error and try to derive an update rule that can be achieved through sampling:
$$\begin{flalign} \overline{\text{BE}} &= \sum_s \mu_\pi(s) \left [ \sum_a \pi(a\vert s)\sum_{s^\prime, r} p(s^\prime, r \vert s, a)[r + \gamma \hat v (s^\prime)] - \hat v (s) \right ]^2 \\ &= \sum_s \mu_\pi(s) \left [ \sum_a \pi(a\vert s)\sum_{s^\prime, r} p(s^\prime, r \vert s, a)[r + \gamma \hat v (s^\prime) - \hat v (s)] \right ]^2 \\ &= \sum_s \mu_\pi(s) \mathbb{E} \left [ \delta_t \vert S_t = s, A_t \sim \pi(s) \right ]^2 \\ &= \sum_s \mu_\pi(s) \mathbb{E}_\pi \left [ \delta_t \vert S_t = s \right ]^2 \\ &= \sum_s \mu_\pi(s) \mathbb{E}_b \left [\rho_t \delta_t \vert S_t = s \right ]^2 \\ \end{flalign}$$
We can see that the mean square Bellman error is just expected value of the TD error for each state squared. The only difference between this and the $\overline{\text{TDE}}$ is that the squaring is done outside of the expected value.
We can derive an SGD parameter update rule by taking the gradient with respect to the parameters. If the visited states matches the behavior policy instead of the target policy then we are really optimizing something different again which is the mean square Bellman error weighted by the behavior policy, but it will still converge to that value as well. The example we will consider does not have an off-policy distribution, and the problems with this approach will appear ignoring that problem.
$$\begin{flalign} \mathbf{w}_{t+1} &= \mathbf{w}_t - \frac{1}{2} \alpha \nabla (\mathbb{E}_\pi [\delta_t]^2) \\ &= \mathbf{w}_t - \frac{1}{2} \alpha \nabla (\mathbb{E}_b [\rho_t \delta_t]^2) \\ &= \mathbf{w}_t - \alpha \mathbb{E}_b[\rho_t \delta_t] \nabla \mathbb{E}_b [\rho_t \delta_t] \tag{chain rule}\\ &= \mathbf{w}_t - \alpha \mathbb{E}_b [\rho_t (R_{t+1} + \gamma \hat v (S_{t+1}, \mathbf{w}) - \hat v(S_t, \mathbf{w}))] \mathbb{E}_b[\rho_t \nabla \delta_t] \tag{linearity of expected value}\\ &= \mathbf{w}_t + \alpha \left [ \mathbb{E}_b [\rho_t (R_{t+1} + \gamma \hat v (S_{t+1}, \mathbf{w}) ] - \hat v(S_t, \mathbf{w}) \right ] \left [ \nabla \hat v(S_t, \mathbb{w}) - \gamma \mathbb{E}_b[\rho_t \nabla \hat v(S_{t+1}, \mathbf{w})] \right ] \\ \end{flalign}$$
Note that the two expected values in this expression cannot in general use the same sample of the transition state since the product would reflect the correlation between the samples. Instead we need two independent samples or, if the environment is deterministic, this is unecessary. For example 11.2, this algorithm would find the correct values since it is guaranteed to minimize the Bellman error and the exact solution will always have 0 Bellman error at every state. We can however, modify the example to one in which the minimum Bellman error solution is also problematic.
The 3D space contains vectors that represent all value function of 3 states: $\{s1, s2, s3\}$ where $\overline{v} = [v1, v2, v3]$. Let's say we approximate these value functions with a parameter vector $\mathbf{w} = \{w1, w2\}$ such that $\hat v(s) = \mathbf{w} \cdot \mathbf{x}(s)$ where $\mathbf{x}(s)$ is the feature vector representation of a given state. There are three states so three feature vectors that must be defined: $\mathbf{x}_1, \mathbf{x}_2, \mathbf{x}_3$. Each feature vector has two components, one for each parameter, so three of them cannot be linearly independent. All value function approximations $\hat v(s)$ lie in a plane within the 3D space expressing the constraints placed between the 3 state values. For example let's say the feature vectors are $\{0, 1 \}, \left \{\frac{\sqrt{3}}{2}, -\frac{1}{2}\right \}, \left \{-\frac{\sqrt{3}}{2}, -\frac{1}{2}\right \}$. Then the values function approximation would be $\hat v = \left \{ w2, \frac{w1 \sqrt{3} - w2}{2}, -\frac{w1 \sqrt{3} + w2}{2} \right \}$
Another option is let's say to simplify the problem, we just group two of the states together so the feature vector is the same for two of the states. In this scenario we could have $\hat v = \left \{ x1_1 w1 + x1_2 w2, x2_1 w1 + x2_2 w2, x3_1 w1 + x3_2 w2 \right \}$
For this form of approximation we can directly compute the parameters which minimize the distance from an arbitrary value function to an approximate one. All three states have equal visit probability so we can simply sum the squared distance components and use the fact that states 2 and 3 share the same approximation:
$$\begin{flalign} d(v_1, v_2, v_3) &= (v_1 - w_1)^2 + (v_2 - w_2)^2 + (v_3 - w_2)^2 \\ &\therefore \\ \frac{\partial d}{\partial w_1} &= -2(v_1 - w_1) \implies w_1 = v_1 \\ \frac{\partial d}{\partial w_2} &= -2(v_2 - w_2) - 2(v_3 - w_2) \\ &= -2(v_2 - 2w_2 + v_3)\implies w_2 = \frac{v_2 + v_3}{2} \\ \end{flalign}$$
If we apply the Bellman operator to an approximation, we get the following three state values:
$$B_\pi(\hat v(w_1, w_2)) = \{\gamma w_2, 1 + \gamma w_1, -1 + \gamma w_2 \}$$
Applying the projection operator to these results in the following parameters:
$$\begin{flalign} w_1 &= \gamma w_2 \\ w_2 &= \frac{\gamma}{2} (w_1 + w_2) \end{flalign}$$
The Projected Bellman Error is the distance between the initial state values and the new ones implied by the updated parameters:
$$\begin{flalign} \overline{\text{PBE}} &= \frac{1}{3} \left [ (w_1 - \gamma w_2)^2 + (w_2 - \frac{\gamma}{2}(w_1 + w_2))^2 + (w_2 - \frac{\gamma}{2}(w_1 + w_2))^2 \right ] \\ &= \frac{1}{3} \left [ (\gamma w_2 - w_1)^2 + 2(\frac{\gamma}{2}(w_1 + w_2) - w_2)^2 \right ] \end{flalign}$$
Normally, we'd have to minimize this, but since we know the best solution will always have exactly 0 Projected Bellman Error, we can notice that when $w_1 = w_2 = 0$ this entire expression is 0. That is the TD fixed point which also matches the minimizing value error solution.
Exercise 11.3 (programming)
Apply one-step semi-gradient Q-learning to Baird's counterexample and show empirically that its weights diverge.
True gradient methods update the parameters of an objective function in the direction of the negative gradient of some objective function. Under the right conditions, these techniques have robust convergence properties and can find the true minimum value of the objective. Previously, the only true gradient methods developed were Monte Carlo methods, but now we seek to find true gradient methods in the off-policy case in terms of some other objective. If we forgo Monte Carlo methods, then the value error objective is no longer available to us so we must consider alternatives such as the Bellman Error. It also turns out that in the on-policy case, semi-gradient TD in the linear case does behave like a true gradient method that reaches the TD fixed point, however this point minimizes the projected Bellman Error rather than the value error. The TD fixed point is a fixed point because unlike the other error metrics, it can be reduced to 0 for any MDP and any linear approximation function. At this point, the semi-gradient update is expected to be 0.
Comparing all of the potential errors:
$$\begin{flalign} w_{ve} &= \frac{\gamma(1 - c) + 2c}{(1 - \gamma)(1 + c^2)} \\ w_{be} &= \frac{2(2c - \gamma(1+c))}{2 + \gamma(1+c)^2 (\gamma - 2) + 2c^2} \\ w_{pbe} &= \frac{4c}{2(1+c^2) - \gamma (1+c)^2} \\ w_{tde} &= \frac{2(2c - \gamma (1 + c))}{(\gamma -1)^2 + (\gamma c - 1)^2 + (\gamma - c)^2 + c^2(\gamma - 1)^2} \end{flalign}$$
This version of semi-gradient DP uses a function π! which can update the probability distribution over actions for a given policy and state. Policy evaluation is done through trajectory sampling where the policy is used to generate the distribution of states which are updated. All of the potential transition states are used in the bootstrap update, so enough samples need to be collected in order to visit those states.
Returning to the previous expression but including the on-policy distribution results in:
$$\begin{flalign} w_{k+1} &= \text{argmin}_{w \in \mathbb{R}} \enspace \sum_{s \in \mathcal{S}} \mu(s) \left ( \hat v(s, w) - \mathbb{E}_\pi[R_{t+1} + \gamma \hat v(S_{t+1}, w_k) | S_t = s] \right )^2\\ &= \text{argmin}_{w \in \mathbb{R}} \enspace \frac{\epsilon}{1+\epsilon} (w - \gamma2w_k)^2 + \frac{1}{1+\epsilon} (2w - (1-\epsilon)\gamma2w_k)^2\\ \therefore\\ \frac{\partial{w_{k+1}}}{\partial w} &= \frac{2}{1+\epsilon} \left [ \epsilon (w - \gamma2w_k) + 4(w - (1-\epsilon)\gamma w_k) \right ]\\ &=\frac{2}{1+\epsilon} \left [ w(\epsilon + 4) - 2\gamma w_k ( \epsilon + 2(1-\epsilon) \right ]\\ &=\frac{2}{1+\epsilon} \left [ w(\epsilon + 4) - 2\gamma w_k ( 2 - \epsilon ) \right ]\\ &\text{setting this equal to 0 and solving for w yields}\\ w &= 2 \gamma w_k \frac{2 - \epsilon}{\epsilon + 4}\\ &\text{therefore weight updates will diverge when}\\ 1 &\lt 2 \gamma \frac{2 - \epsilon}{\epsilon + 4} \\ \gamma &> \frac{1}{2} \frac{\epsilon + 4}{2 - \epsilon}\\ \end{flalign}$$
Since $0 \le \epsilon \le 1$ we know that $\epsilon + 4 \ge 4$ and $1 \le 2 - \epsilon \le 2$ so the fraction is greater than $\frac{4}{2} = 2$. Therefore, this expression states that $\gamma \gt 1$ is the divergence condition which is never true.
Note that for the target policy, all of the time is spent in state 7, so that is the only value that is properly updated. For the behavior policy, although the weights do not go to zero, they do find a stable solution setting all of the state values to 0. Since this algorithm uses trajectory sampling, it is an on-policy method. If instead we swept through the state space then we see the instability.
This policy always takes the "solid" action which is the second action using the convention above.
$\theta_2$ :
$\theta_3$ :
The convergence is very slow due to $\gamma$ being close to 1. Even though the value error remains high, the fact that the observed projected Bellman error is shrunk by a factor of $(1 - \gamma)^2$ makes it nearly 0 even while the value error is close to 4. If we shrink the value of $\gamma$ towards 0, then both errors converge to 0 much faster.
We can perform the same calculation for the Bellman Error:
$$\begin{flalign} \overline{\text{BE}} &= \frac{1}{2} \left [ \left (w - \frac{\gamma w}{2} (1 + c) \right )^2 + \left (cw - 2 - \frac{\gamma w}{2}(1 + c) \right )^2 \right ] \end{flalign}$$
$$\begin{flalign} \frac{\partial{\overline{\text{BE}}}}{\partial w} &= \left [ \left (w - \frac{\gamma w(1+c)}{2} \right ) \left (1 - \frac{\gamma(1+c)}{2} \right) + \left (cw - 2 - \frac{\gamma w(1+c)}{2} \right ) \left ( c - \frac{\gamma(1+c)}{2} \right ) \right ] \\ &= \left [\frac{w(2 - \gamma(1 + c))}{2} \frac{2 - \gamma(1+c)}{2} + \frac{2cw - 4 - \gamma w (1+c)}{2} \frac{2c - \gamma(1+c)}{2}\right ] \\ &= \frac{1}{2} \left [w(2 - \gamma(1 + c))^2 + (2cw - 4 - \gamma w (1+c))(2c - \gamma(1+c)) \right ] \\ &= \frac{1}{2} \left [w((2 - \gamma(1 + c))^2 + (2c - \gamma(1+c))^2) - 4(2c - \gamma(1+c)) \right ] \\ \end{flalign}$$
Setting this equal to 0 and solving for $w$ yields:
$$\begin{flalign} w &= \frac{4(2c - \gamma(1+c))}{(2 - \gamma(1 + c))^2 + (2c - \gamma(1+c))^2} \\ &= \frac{4(2c - \gamma(1+c))}{4 - 4\gamma(1+c) + \gamma^2 (1+c)^2 + 4c^2 - 4c\gamma(1+c) + \gamma^2 (1+c)^2} \\ &= \frac{4(2c - \gamma(1+c))}{4 - 4\gamma(1+c)(1 + c) + 2\gamma^2 (1+c)^2 + 4c^2} \\ &= \frac{4(2c - \gamma(1+c))}{4 + 2\gamma(1+c)^2 (\gamma - 2) + 4c^2} \\ &= \frac{2(2c - \gamma(1+c))}{2 + \gamma(1+c)^2 (\gamma - 2) + 2c^2} \\ \end{flalign}$$
The update for each state depends upon the TD error. State A has two equally likely TD errors given by:
$$\begin{flalign} \delta_A &= 0 + w_B - w_A = w_B - w_A \\ \delta_A &= 0 + w_C - w_A = w_C - w_A\\ \end{flalign}$$
States B and C both transition into terminal states deterministically, so their TD errors are given by:
$$\begin{flalign} \delta_B &= 1 - w_B \\ \delta_C &= 0 - w_C = w_C\\ \end{flalign}$$
At the TD-fixed point, the expected parameter update after visiting states according to the on-policy distribution should be 0. Let's consider all 4 updates that occur:
$$\begin{flalign} w_A &\leftarrow w_A + \alpha \left ( w_B - w_A \right ) \\ w_A &\leftarrow w_A + \alpha \left ( w_C - w_A \right ) \\ w_B &\leftarrow w_B + \alpha (1 - w_B) \\ w_C &\leftarrow w_C + \alpha w_C \end{flalign}$$
The convergence condition for $w_B$ and $w_C$ is obvious from the last two equations: $w_B = 1$ and $w_C = 0$. For state A, the two updates occur with equal probability, so the sum of the term multiplying $\alpha$ for each should be 0. We can substitude the values we already know for $w_B$ and $w_C$ to get: $1 - w_A - w_A = 0 \implies w_A = \frac{1}{2}$, confirming that the TD fixed point equals the exact solution:
$$\begin{flalign} w_A &= \frac{1}{2} = v_A \\ w_B &= 1 = v_B \\ w_C &= 0 = v_C \end{flalign}$$
Note that if we correct the dynamic programming method for the on policy distribution we recover the convergence properties of on policy TD. However because of the target policy repeatedly visiting state 7, only the parameters for that state have a chance of being updated. So we can expect an accurate value estimate for state 7 based on updates to weights 7 and 8 but not for the other states since weights 1 through 6 won't be affected by updates
In this 2D geometry with a fixed $c$, we can calculate the point on the line defining the space of possible $\hat v$ functions that is closest to any true value function vector defined by $\mathbf{v} = (v_1, v_2)$. The squared distance from this vector to the line of possible approximation functions is $((v_1 - w)^2 + (v_2 - cw)^2)$. The $w$ that minimizes this distance can be found by the usual process of setting the derivative with respect to $w$ to 0:
$$-2(v_1 - w) - 2c(v_2 - cw) = 0 \implies 2w + 2c^2 w - 2 v_1 - 2cv_2 = 0 \implies w(1 + c^2) = v_1 + c v_2 \implies w = \frac{v_1 + cv_2}{1+c^2}$$
So for any value function in the space, we can find the value $w$ that minimizes the distance to the approximation line with this formula.
Consider an approximate solution with only two parameters $w_1, w_2$. For the first problem, this is still a tabular case with an optimal solution of $w_1 = v_A$ and $w_2 = v_B$. For the second problem, we impose the following:
$$\hat v_A = w_1, \; \hat v_B = \hat v_{B^\prime} = w_2$$
Now consider the original objective for approximation for which we need access to $\mu(s)$. For the first problem $\mu(A) = \frac{1}{3}, \; \mu(B) = \frac{2}{3}$ and for the second $\mu(A) = \mu(B) = \mu(B^\prime) = \frac{1}{3}$. Note that this also implies that the observed reward sequence for each problem will look exactly the same with respect to the feature vectors.
Since the problem is tabular, the minimum value error is 0 with the following solution:
$$\begin{flalign} \overline{\text{VE}} &= 0 \\ w_1 &= w_2 = 0 \\ \hat v_A &= \hat v_B = \hat v_{B^\prime} = 0 \end{flalign}$$
This problem cannot have 0 value error due to the limited number of parameters, so we can only hope to minimize it. We can calculate this minimum explicitely using the known true values:
$$\begin{flalign} \overline{\text{VE}} &= \frac{1}{3} \left [ w_1^2 + (w_2 - 1)^2 + (w_2 + 1)^ 2 \right ] \\ &= \frac{1}{3} \left [ w_1^2 + w_2^2 - 2w_2 + 1 + w_2^2 + 2 w_2 + 1 \right ] \\ &= \frac{1}{3} \left [ w_1^2 + 2 w_2^2 + 2 \right ] \end{flalign}$$
We can minimize this by setting the gradient to 0 for each term:
$$\begin{flalign} \frac{\partial \overline{\text{VE}}}{\partial w_1} &= \frac{2 w_1 }{3}\\ \frac{\partial \overline{\text{VE}}}{\partial w_2} &= \frac{4 w_2 }{3}\\ \therefore w_1 &= w_2 = 0 \end{flalign}$$
So the final solution is the same as that for the first problem but with a different value error:
$$\begin{flalign} \overline{\text{VE}} &= \frac{2}{3} \\ w_1 &= w_2 = 0 \\ \hat v_A &= \hat v_B = \hat v_{B^\prime} = 0 \end{flalign}$$
What if we consider the weight updates using the TD0 semi-gradient on-policy learning?
$$\begin{flalign} w_{t+1} &= w_t + \alpha(R_{t+1} + \gamma \hat v(S_{t+1}, w) - \hat v(S_t, w_t)) \nabla \hat v(S_t, w_t)\\ &\text{there are 3 different possible updates depending on the transition observed}\\ &= w_t + \alpha(0 + \gamma 2w_t - w_t) = w_t(1 + \alpha (2\gamma - 1))\\ &= w_t + 2\alpha(0 + \gamma 2w_t - 2w_t) = w_t(1 + 4\alpha (\gamma - 1))\\ &= w_t + 2\alpha(0 + \gamma 0 - 2w_t) = w_t(1 - 4\alpha) \end{flalign}$$
In this case we can see that the only update in which the weight will grow is the first one for the transition from state 1 to state 2. So it seems that while for this counterexample dynamic programming and direct minimization fail, semi-gradient TD0 in fact can converge regardless of the value of γ and ϵ?
Using the dynamic programming semi-gradient update yields:
$$\begin{flalign} w_{k+1} &= w_k + \alpha \sum_s \left( \mathbb{E}[R_{t+1} + \gamma \hat v(S_{t+1}, w_k) | S_t = s] - \hat v(s, w_k) \right) \nabla \hat v(s, w_k)\\ &= w_k + \alpha \left [ \left ( \gamma 2w_k - w_k \right) + (((1-\epsilon)(\gamma 2 w_k) + \epsilon(0)) - 2w_k)2 \right ]\\ &= w_k + \alpha [w_k(2\gamma - 1) + 2((1 - \epsilon)(2 \gamma w_k) - 2w_k)]\\ &= w_k + \alpha [w_k(2\gamma - 1) + 4w_k(\gamma - \gamma\epsilon - 1)]\\ &= w_k(1 + \alpha [2\gamma - 1 + 4\gamma - 4\gamma\epsilon - 4])\\ &= w_k(1 + \alpha [6\gamma - 5 - 4\gamma\epsilon]) \end{flalign}$$
In this case we can see that if $\alpha(6\gamma - 5 - 4\gamma\epsilon)>0$ then the weights will grow indefinitely. What does this imply about the relationship between γ and ϵ?
$$\begin{flalign} 6\gamma - 5 - 4\gamma\epsilon &> 0\\ \gamma(6 - 4\epsilon) &> 5\\ \gamma &> \frac{5}{6 - 4\epsilon} \end{flalign}$$
This is the same stability condition we had before with the explicit minimization calculation.
Exercise 11.1
Convert the equation of n-step off-policy TD (7.9) to the semi-gradient form. Give accompanying definitions of the return for both the episodic and continuing cases.
$$\begin{flalign} V_{t+n}(S_t) \doteq V_{t+n-1}(S_t)+\alpha\rho_{t:t+n-1}[G_{t:t+n}-V_{t+n-1}(S_t)], \hspace{1cm} 0 \leq t < T \tag{7.9} \end{flalign}$$
where $\rho_{t:t+n-1}$, called the importance sampling ratio, is the relative probability under the two policies of taking the n actions from $A_t$ to $A_{t+n-1}$
$$\rho_{t:h} \doteq \prod_{k=t}^{\min(h, T-1)}\frac{\pi(A_k | S_k)}{b(A_k|S_k)} \tag{7.10}$$
To convert this to a semi-gradient method we need to provide update equations for the weight vector that defines the value function approximation.
$$\begin{flalign} \mathbf{w}_{t+n} &\doteq \mathbf{w}_{t+n-1} + \alpha \rho_{t} \cdots \rho_{t+n-1} [G_{t:t+n} - \hat v(S_{t}, \mathbf{w}_{t+n-1})]\nabla \hat v (S_t, \mathbf{w}_{t+n-1})\\ G_{t:t+n} &\doteq R_{t+1} + \cdots + \gamma^{n-1} R_{t+n} + \gamma^n \hat v(S_{t+n}, \mathbf{w}_{t+n-1}) \tag{episodic}\\ G_{t:t+n} &\doteq \sum_{k = 1}^{n-1} R_{t+k} - (n-1)\bar R_t + \hat v(S_{t+n}, \mathbf{w}_{t+n-1})\tag{continuing} \end{flalign}$$
The tablular value at a particular time step is replaced with the weight parameter at that time step with the gradient also being added next to the error term.
We now consider SGD methods for minimizing the $\overline{\text{PBE}}$. Remember that in the linear case, there is always an exact solution, the TD fixed point $\mathbf{w}_{\text{TD}}$, at which the $\overline{\text{PBE}}$ is zero. This could be found by least-squares methods (Section 9.8), but only by methods of quadratic $O(d^2)$ complexity in the number of parameters. We seek instead an SGD method, which should be $O(d)$ and have robust convergence properties. Gradient-TD methods come close to achieving these goals, at the cost of a rough doubling of computational complexity.
$\mathbf{D}$ is the $\vert \mathcal{S} \vert \times \vert \mathcal{S} \vert$ diagonal matrix with the $\mu(s)$ on the diagonal
$\mathbf{X}$ is the $\vert \mathcal{S} \vert \times d$ matrix whose rows are the feature vectors $\mathbf{x}(s)^\top$, one for each state $s$
To derive an SGD method for the $\overline{\text{PBE}}$ (assuming linear function approximation) we begin by expanding and rewriting the objective (11.22) in matrix terms:
$$\begin{flalign} \overline{\text{PBE}}(\mathbf{w}) &= \left \vert \left \vert \Pi \overline{\delta}_\mathbf{w} \right \vert \right \vert^2_\mu \\ &= (\Pi \overline{\delta}_{\mathbf{w}})^{\top} \mathbf{D} \Pi \overline{\delta}_\mathbf{w} \\ \end{flalign}$$
In the context of this chapter, learnability means that a quantity can be estimated from data alone. In the strictest approximation case, the only data available is the rewards observed as well as the feature vector of whatever state we are in. Sometimes we also have access to the state information in addition to the feature vector alone, and in this case there are more quantities we can calculate.
Consider the original objective we defined for approximation, the value error: $\overline{\text{VE}} = \sum_{s \in \mathcal{S}} \mu_\pi(s)(v_\pi(s) - \hat v (s))^2$. This calculation depends on knowing the true state value which is only possible if we have full information about the state. Consider an alternative error though in which we replace this unknown quantity with something that can be observed: $\overline{\text{RE}}(\mathbf{w}) = \mathbb{E}\left [ \left ( G_t - \hat v(S_t, \mathbf{w}) \right )^2 \right]$. It turns out that this objective is equal to the value error objective plus a variance term that does not depend on the paramters $\mathbf{w}$. So if we optimize $\overline{\text{RE}}$ the parameters we find will match those we would have found optimizing $\overline{\text{VE}}$. Note that we can only sample this in the case of Monte Carlo estimation and that is not possible for continuing problems. For those, we must consider the bootstrapping objectives such as the TD error.
Luckily the TD error is also always observable $\delta_t \doteq R_{t+1} + \gamma \hat v (S_{t+1}, \mathbf{w}_t) - \hat v(S_t, \mathbf{w}_t)$ since it only depends on the observed rewards and feature vectors. The semi-gradient methods we previously developed only depend on the TD error and thus are observable and in the case of linear approximation are bounded to some region around the minimum value error solution.
The Bellman error, on the other hand is $\mathbb{E}_\pi [\delta_t]$ is not observable because it requires knowledge of the state in order to correctly assign samples to the state. We can clearly sample this error on each step, but if two states appear to have the same feature vector, and that is the only information we have, then we cannot correctly separate those samples to the assigned states and apply the probability weighting to the error. If we had access to the state, then we can in theory observe the Bellman error, but we will see that minimizing it does not produce desireable results.
As we saw earlier with value function approximation, the on-policy distribution affects the results. When we do off-policy learning, it is important to alter the sampled values so they reflect the desired distribution. Previously we only used the importance sampling ratio to alter the values since we updated all values an arbitrarily large number of times. Now we may need to consider also doing a transformation on the sampled states as well as the values. However, we will also consider approaches that use true gradients with bootstrapping so we consider the effect of the parameters on the transition state value.
w1 :
w2 :