<p>The problem does not come from the above equation but from the bootstrapping method. <a href="http://incompleteideas.net/book/the-book-2nd.html" rel="nofollow noreferrer">Sutton's reinforcement learning book (2nd)</a> gave a pretty good explanation to the problem in Chapter 9.3.</p>
<p>The idea here is you cannot obtain the <strong>true value</strong> for <span class="math-container">$V_\pi$</span>, but you want to approximate it. My understand is that when bootstrapping, like with the TD method, <span class="math-container">$V_\pi$</span> depends on <span class="math-container">$w$</span>. This breaks the assumption that <span class="math-container">$V_\pi$</span> is independent of <span class="math-container">$w$</span> 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, <span class="math-container">$V_\pi$</span> will be unbiased and the above will be guaranteed to converge to a local minimal.</p>

CC BY-SA 4.0
2018-08-12T04:27:11.967Z
2021-03-01T11:43:56.967Z
2021-03-01T11:43:56.967Z
yeelan
<p>Maybe this paper might be helpful: <a href="https://arxiv.org/pdf/1712.10285.pdf" rel="nofollow noreferrer">SBEED</a>. This paper illustrate two problems, non-smoothness and double sampling.<br />
The first problem is due to the <span class="math-container">$\max$</span> operator in the Bellman equation for <span class="math-container">$Q^*$</span> or <span class="math-container">$V^*$</span>, i.e.
<span class="math-container">$$
Q^*(s,a) = R(s,a) + \gamma \sum_{s'\in{S}} P(s'|s,a) \max_{a\in A}Q^*(s',a')
$$</span>
which can be convert to loss function
<span class="math-container">$$
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
$$</span>
Assume that we are dealing with tabular case, i.e., <span class="math-container">$Q\in\mathbb{R}^{|S|\times|A|}$</span> is a table. Dynamic programming theory ensures the existence and uniqueness of <span class="math-container">$Q^*$</span> satisfying <span class="math-container">$L(Q)=0$</span>. (By the contraction and monotonic properties of operator <span class="math-container">$T$</span>) Note that by directly differentiating <span class="math-container">$L(Q)$</span> by <span class="math-container">$Q$</span>, the <span class="math-container">$\max$</span> operator will be troubling.<br />
Secondly, even if we can skip that problem by using adding entropy term as in the 'SBEED' paper, the gradient will be in form:
<span class="math-container">$$
\cdots \sum_{s'\in S}P(s'|s,a) \left( \cdots -\gamma\sum_{s'\in S}P(s'|s,a)Q(s',a') \right)
$$</span>
<span class="math-container">$\textbf{Detailed derivation is omitted}$</span> 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 <span class="math-container">$R$</span> and transition probability <span class="math-container">$P$</span>. Thus we usually obtain the gradient in expectation form and use sampled stochastic gradient to update <span class="math-container">$Q$</span> value function or <span class="math-container">$pi$</span> 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.<br />
Your question seems to be about policy evaluation. Then the <span class="math-container">$\max$</span> operator does not exists but the double sampling problem still remains. Hopefully this can answer your question.</p>

CC BY-SA 4.0
2023-05-31T12:30:27.697Z
2023-05-31T12:30:27.697Z
David Lee
<p>In reinforcement learning, with function approximation, a popular cost function is the Mean value error.</p>

<p><a href="https://i.sstatic.net/Tvsfh.png" rel="noreferrer"><img src="https://i.sstatic.net/Tvsfh.png" alt="enter image description here"></a></p>

<p>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?</p>

<machine-learning>
Why semi-gradient is used instead of the true gradient in Q-learning?
Adam
# Why semi-gradient is used instead of the true gradient in Q-learning?

(Asked by: username_0 on 2018-03-07)

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

[![enter image description here](https://i.sstatic.net/Tvsfh.png)](https://i.sstatic.net/Tvsfh.png)

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?

**Tags:** machine-learning

---

## 2 answers

### Answer by username_1 on 2018-08-12. Score: 3

The problem does not come from the above equation but from the bootstrapping method. [Sutton's reinforcement learning book (2nd)](http://incompleteideas.net/book/the-book-2nd.html) 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.


---

### Answer by username_2 on 2023-05-31. Score: 0

Maybe this paper might be helpful: [SBEED](https://arxiv.org/pdf/1712.10285.pdf). 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.


---

