2
$\begingroup$

In Deep Q Learning the parametrized Q-functions $Q_i$ are optimised by performing gradient descent on the series of loss functions

$L_i(\theta_i)= E_{(s,a)\sim p}[(y_i-Q(s,a;\theta_i))^2]$ , where

$y_i = E_{s' \sim \mathcal{E}}[r+\gamma \max_{a'}Q(s',a';\theta_{i+1})\mid s,a]$.

In the actual algorithm, however, the expected value is never computed. Also, I think it cannot be computed since the transition probabilities of the underlying MDP remain hidden from the agent. Instead of the expected value, we compute $y_i = r_i + \gamma \max_a Q(\phi_{i+1},a;\theta)$. I assume some sort of stochastic approximation is taking place here. Can someone explain the details?

$\endgroup$
2
$\begingroup$

Just as the paper says

$$L_i(\theta_i)= E_{(s,a)\sim p}[(y_i-Q(s,a;\theta_i))^2]$$

where

$$y_i = E_{s' \sim \mathcal{E}}[r+\gamma \max_{a'}Q(s',a';\theta_{i+1})\mid s,a]$$

Then in the Background section of the paper, it says

Differentiating the loss function with respect to the weights we arrive at the following gradient:

$$\nabla_{\theta_i} L_i(\theta_i)\\= E_{(s,a)\sim p,s'\sim\mathcal{E}}\left[\left(r+\gamma \max_{a'}Q(s',a';\theta_{i+1})-Q(s,a;\theta_i)\right)\nabla_{\theta_i}Q(s,a;\theta_i)\right]\tag{1}$$

Rather than computing the full expectations in the above gradient, it is often computationally expedient to optimize the loss function by stochastic gradient descent.

...

and the expectations are replaced by single samples from the behavior distribution $ρ$ and the emulator $\mathcal{E}$ respectively.

If you're familiar with SGD and Stochastic Optimization then you know what happens here:

The expression inside the expectation of (1), i.e. $\left(r+\gamma \max_{a'}Q(s',a';\theta_{i+1})-Q(s,a;\theta_i)\right)\nabla_{\theta_i}Q(s,a;\theta_i)$ , is an unbiased estimation of the real gradient $\nabla_{\theta_i}L_i(\theta_i)$ - its expectation is the real gradient. In other words,

$$\widehat{\nabla L}=\left(r+\gamma \max_{a'}Q(s',a';\theta_{i+1})-Q(s,a;\theta_i)\right)\nabla_{\theta_i}Q(s,a;\theta_i).$$

Then by theory of Stochastic Optimization we can optimize $L$ by $\theta\leftarrow \theta - \alpha\widehat{\nabla L}$ , which is how SGD works.

The unbiased estimation $\left(r+\gamma \max_{a'}Q(s',a';\theta_{i+1})-Q(s,a;\theta_i)\right)\nabla_{\theta_i}Q(s,a;\theta_i)$ can be sampled and calculated directly - you can run the emulator $\mathcal{E}$ and current behavior policy to collect $r, s', a'$ and calculate the gradient of your Q network $\nabla Q$ using TensorFlow. So the gradient to $L$ can be approximated.

The $y_j$ in the pseudocode of the paper is also an estimation. It'll be more proper to denote it as $\hat{y_j}$.

(I'm not an native English speaker so forgive my poor expression.)

| improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Welcome to AI SE! Thanks for contributing! This answer seems consistent with knowledge. Maybe you could spend more words on why that is an "unbiased estimator of the gradient" (maybe just link to a paper that shows that this an unbiased estimator of the gradient) and how this estimator is actually called. Furthermore, what do you mean by "which can be sampled and calculated directly", i.e. how can an estimator be sampled? Also, which pseudocode are you talking about where $\hat{y_j}$ is present? $\endgroup$ – nbro Feb 28 at 2:12
  • $\begingroup$ Thank you for your feedback. I have tried to edit my post to make it more clear. My English writing skill is not so good. $\endgroup$ – Guo Shuai Feb 28 at 3:58
  • 1
    $\begingroup$ Thanks for addressing my questions. Now your answer is clearer! And thanks again for contributing! I've already upvoted your answer. Feel free to stick around and contribute more :) $\endgroup$ – nbro Feb 28 at 4:02
  • $\begingroup$ Thanks for your contribution. I must admit that I haven't watched enough into stochastic gradient. As I understand it we try to find a zero of the gradient via the Robbins-Monro-Algorithm. In general, does that mean you have to check the prerequisites of Robbins-Monro before using stochastic gradient ? I think here they are satisfied. $\endgroup$ – Leroy Od Feb 28 at 9:17
  • $\begingroup$ I don't understand how it is an unbiased estimator, can someone elucidate? $\endgroup$ – PyWalker27 Apr 23 at 1:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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