7
$\begingroup$

Projected Bellman error has shown to be stable with linear function approximation. The technique is not at all new. I can only wonder why this technique is not adopted to use with non-linear function approximation (e.g. DQN)? Instead, a less theoretical justified target network is used.

I could come up with two possible explanations:

  1. It doesn't readily apply to non-linear function approximation case (some work needed)
  2. It doesn't yield a good solution. This is the case for true Bellman error but I'm not sure about the projected one.
$\endgroup$
4
  • $\begingroup$ Can you define the "projected Bellman error"? $\endgroup$
    – nbro
    May 10, 2019 at 14:47
  • $\begingroup$ @nbro It literally means what it says. Projecting a Bellman error onto a representable space of a function approximation. I think Sutton's Gradient TD minimize this. But it is proposed for a linear approximation case. $\endgroup$
    – Phizaz
    May 11, 2019 at 14:06
  • $\begingroup$ It might be clear to you, but what does it mean to project something onto a representable space of a function approximation model? Moreover, what is the Bellman error? Do you have a specific source that talks about this topic more in detail? $\endgroup$
    – nbro
    May 11, 2019 at 16:48
  • $\begingroup$ @nbro I refer to chapter 11.7 in Sutton's 2018 book which he describes Gradient TD methods. The projection you're talking about refers to p. 268 in the same book. Honestly, I don't really understand it that much. $\endgroup$
    – Phizaz
    May 13, 2019 at 9:41

2 Answers 2

3
$\begingroup$

I have found some clues in Maei's thesis (2011): “Gradient Temporal-Difference Learning Algorithms.”

According to the thesis:

  1. GTD2 is a method that minimizes the projected Bellman error (MSPBE).
  2. GTD2 is convergent in non-linear function approximation case (and off-policy).
  3. GTD2 converges to a TD-fixed point (same point as semi-gradient TD).
  4. GTD2 is slower to converge than usual semi-gradient TD.

It doesn't readily apply to non-linear function approximation.

No, it does.

It doesn't yield a good solution.

No, it does. TD-fixed point is the same point for the solution of semi-gradient TD (which is generally used). There is no edge on that.

The only explanation seems to be practical convergence rate.

To quote his words:

Some of our empirical results suggest that gradient-TD method maybe slower than conventional TD methods on problems on which conventional TD methods are sound (that is, on-policy learning problems).

$\endgroup$
0
$\begingroup$

As I understand it above-mentioned projection operator project into linear feature subspace produced from set of feature vectors (or feature functions), that is space of linear combinations of features. Vanilla DQN don't have any feature space, projection into linear subspace doesn't make sense in DQN context. If you attempt to produce feature space for values/Q with some NN it wouldn't be DQN (because Q wouldn't be produced) and it wouldn't work anyway on anything but toy problems because amount of degrees of freedom of output would be too high.

$\endgroup$
2
  • $\begingroup$ The proof in Maei's thesis on the convergence of GTD2 on non-linear case is based on a "tangent" plane. He argued that there exists a differentiable manifold which is locally linear (given that a learning rate is arbitrarily small). This extends the proof of linear case onto the non-linear case. $\endgroup$
    – Phizaz
    Oct 11, 2019 at 4:41
  • $\begingroup$ Output space of DNN is not even a manifold strictly speaking because input (and in some treatments even weights) are random variables. Manifold of random variables is hard math problem (unlike random variable on manifold). Tangent hyperplane could be approximated sometimes but it's hard anyway. $\endgroup$ Oct 12, 2019 at 7:13

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .