In reinforcement learning, with function approximation, a popular cost function is the Mean value error.

enter image description here

This involves a target value V_pi and a current value estimate V_hat. When deriving the update rule for gradient descent learning, people just ignore V_pi-s dependence on the parameters, using a semi-gradient instead of the true gradient. Why is this? Is it difficult to calculate the true gradient?


2 Answers 2


The problem does not come from the above equation but from the bootstrapping method. Sutton's reinforcement learning book (2nd) gave a pretty good explanation to the problem in Chapter 9.3.

The idea here is you cannot obtain the true value for $V_\pi$, but you want to approximate it. My understand is that when bootstrapping, like with the TD method, $V_\pi$ depends on $w$. This breaks the assumption that $V_\pi$ is independent of $w$ and thus the gradient is not the true gradient and we call it semi-gradient. However, if you are not bootstrapping, as with Monte Carlo methods, $V_\pi$ will be unbiased and the above will be guaranteed to converge to a local minimal.


Maybe this paper might be helpful: SBEED. This paper illustrate two problems, non-smoothness and double sampling.
The first problem is due to the $\max$ operator in the Bellman equation for $Q^*$ or $V^*$, i.e. $$ Q^*(s,a) = R(s,a) + \gamma \sum_{s'\in{S}} P(s'|s,a) \max_{a\in A}Q^*(s',a') $$ which can be convert to loss function $$ L(Q) = \sum_{s,a} \left( Q(s,a)-R(s,a)-\gamma \sum_{s'\in S}P(s'|s,a)\max_{a'\in A}Q(s',a ') \right)^2 $$ Assume that we are dealing with tabular case, i.e., $Q\in\mathbb{R}^{|S|\times|A|}$ is a table. Dynamic programming theory ensures the existence and uniqueness of $Q^*$ satisfying $L(Q)=0$. (By the contraction and monotonic properties of operator $T$) Note that by directly differentiating $L(Q)$ by $Q$, the $\max$ operator will be troubling.
Secondly, even if we can skip that problem by using adding entropy term as in the 'SBEED' paper, the gradient will be in form: $$ \cdots \sum_{s'\in S}P(s'|s,a) \left( \cdots -\gamma\sum_{s'\in S}P(s'|s,a)Q(s',a') \right) $$ $\textbf{Detailed derivation is omitted}$ so please try yourself. Note that the gradient composed two probability times each other. In reinforcement learning, we don't have access to reward function $R$ and transition probability $P$. Thus we usually obtain the gradient in expectation form and use sampled stochastic gradient to update $Q$ value function or $pi$ policy (Please refer to policy gradient paper for this). However, when two probability times each other, we require sample twice to obtain an unbiased estimator for this gradient, which is not convenient compared to semi-gradient, which ignore this term and thus only require one sample.
Your question seems to be about policy evaluation. Then the $\max$ operator does not exists but the double sampling problem still remains. Hopefully this can answer your question.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.