Body: <p>In <em><a href="http://www.incompleteideas.net/book/RLbook2020.pdf" rel="nofollow noreferrer">Reinforcement Learning: An Introduction</a></em> 2nd edition  section 9.4 (p. 206), it says that when we use TD(0) as target and use semi-gradient method to update :</p>
  <blockquote>
  <p>In general, <span class="math-container">$w_t$</span> will be reduced toward zero whenever A is positive definite, meaning &gt;<span class="math-container">$y^TAy &gt; 0$</span> for any real vector y <span class="math-container">$\neq$</span> 0. Positive definiteness also ensures that the inverse A exists</p>
  </blockquote>
  <p>How to prove this statement? I tried to prove it in the following way, but I can only get  <span class="math-container">$\lambda &lt;1$</span> rather than <span class="math-container">$|\lambda|&lt;1$</span>.</p>
  <p><span class="math-container">$$
  w_{t+1} = (I-\alpha A)w_t + \alpha b \\
  \because\delta_{w+1} = (I-\alpha A)\delta_{w}\therefore|\lambda_{max}(I-\alpha A)|\lt 1\Rightarrow\lim_{t\rightarrow\infty}\delta_{w_t}= 0 \\
  (I-\alpha A)y= \lambda y\Rightarrow y^T(I-\alpha A)y= y^Ty-\alpha y^TAy = \lambda y^Ty \\
  \Rightarrow 1-\lambda = \alpha\frac{y^TAy}{y^Ty}\gt 0\Rightarrow\lambda\lt 1
  $$</span></p>
  <p><a href="https://i.sstatic.net/GAmQl.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/GAmQl.png" alt="statement in the book" /></a></p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-01-21T20:51:55.767Z
Comments.Text: Are you sure it is in section 9.4 (pages 241-247)? I cannot seem to find the statement there.
Comments.UserDisplayName: desertnaut
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-01-22T01:55:19.910Z
Comments.Text: The link you post seems to be the first edition of the book. The statement I mentioned can be found in second edition,  p206, 9.4 linear method
Comments.UserDisplayName: 陳文澤
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-01-22T11:01:48.470Z
Comments.Text: You are right, my previous link was to the "Second edition in progress". I have updated the link to the final 2nd version - could you please accept the edit?
Comments.UserDisplayName: desertnaut
Tags: <reinforcement-learning><math><proofs>
Title: How to prove that "w will converge to TD fixed point once A is positive definite"
UserDisplayName: 陳文澤
ThreadText: # How to prove that "w will converge to TD fixed point once A is positive definite"
  
  (Asked by: username_0 on 2022-01-21)
  
  In *[Reinforcement Learning: An Introduction](http://www.incompleteideas.net/book/RLbook2020.pdf)* 2nd edition section 9.4 (p. 206), it says that when we use TD(0) as target and use semi-gradient method to update :
  
  > In general, $w\_t$ will be reduced toward zero whenever A is positive definite, meaning >$y^TAy > 0$ for any real vector y $\neq$ 0. Positive definiteness also ensures that the inverse A exists
  
  How to prove this statement? I tried to prove it in the following way, but I can only get $\lambda <1$ rather than $|\lambda|<1$.
  
  $$
  w\_{t+1} = (I-\alpha A)w\_t + \alpha b \\
  \because\delta\_{w+1} = (I-\alpha A)\delta\_{w}\therefore|\lambda\_{max}(I-\alpha A)|\lt 1\Rightarrow\lim\_{t\rightarrow\infty}\delta\_{w\_t}= 0 \\
  (I-\alpha A)y= \lambda y\Rightarrow y^T(I-\alpha A)y= y^Ty-\alpha y^TAy = \lambda y^Ty \\
  \Rightarrow 1-\lambda = \alpha\frac{y^TAy}{y^Ty}\gt 0\Rightarrow\lambda\lt 1
  $$
  
  [![statement in the book](https://i.sstatic.net/GAmQl.png)](https://i.sstatic.net/GAmQl.png)
  
  **Tags:** reinforcement-learning, math, proofs
  
  > **Comments:**
  > **username_1**: Are you sure it is in section 9.4 (pages 241-247)? I cannot seem to find the statement there.  
  > **username_0**: The link you post seems to be the first edition of the book. The statement I mentioned can be found in second edition,  p206, 9.4 linear method  
  > **username_1**: You are right, my previous link was to the "Second edition in progress". I have updated the link to the final 2nd version - could you please accept the edit?  
  
  ---
  
  ## 0 answers
  
  