Answers.Body: <p>As hinted in your reference the convergence of various TD algos lies at the extended Dvoretzky’s theorem (Theorem 1) which involves maximum norm to be applied to the entire state space with potentially numerous finite states in addition to solve the generic stochastic approximation problem as the estimation error converges to 0 w.p.1. Then you only need to transform the TD(0) iterative process to the form of Theorem 1 and also show it satisfies all 4 constraints there to rigorously prove its convergence w.p.1.</p>
  <p>For TD(0) the iterative state value update process of all states <span class="math-container">$S$</span> in the finite state space for each step <span class="math-container">$n$</span> of an episode is shown in OP as (here for generality <span class="math-container">$α$</span> may not be constant):</p>
  <p><span class="math-container">\begin{align*}
  V_{n+1}(S) &amp;= V_n(S) + α_n(S)(R_{n+1} + γV_n(S') - V_n(S)) \\
   &amp;=(1 − α_n(S))V_n(S) + α_n(S)(R_{n+1} + γV_n(S'))
  \end{align*}</span></p>
  <p>Then define the estimation error as <span class="math-container">$∆_n(S) = V_n(S) − V_π(S)$</span>, where <span class="math-container">$V_π(S)$</span> is the state value under policy <span class="math-container">$π$</span>, we can easily arrive at:
  <span class="math-container">\begin{align*}
  ∆_{n+1}(S) &amp;= (1 − α_n(S))∆_n(S) + α_n(S)(R_{n+1} + γV_n(S') - V_π(S))
  \end{align*}</span></p>
  <p>Then obviously <span class="math-container">$\beta_n(S)=α_n(S), F_n(S)=R_{n+1} + γV_n(S') - V_π(S)$</span>, and if <span class="math-container">$α$</span> is not constant and satisfies your above constraint <span class="math-container">$\sum_n \alpha_n(S) = \infty$</span> and <span class="math-container">$\sum_n \alpha_n(S)^2 &lt; \infty$</span> for every state of the finite state space, then condition 1), 2) are satisfied. And since <span class="math-container">$V_π(S)$</span> is non-random and <span class="math-container">$R_{n+1}$</span> is bounded thus condition 4) is easily satisfied. Finally since <span class="math-container">$V_n(S')=P_πV_n(S)$</span> where <span class="math-container">$P_π$</span> is the state transition probability and <span class="math-container">$V_π(S)=R_π+ γP_πV_π(S)$</span>, thus we have the conditional expectation value in condition 3) bounded from above as required. Thus we can prove TD(0) convergence.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-02-11T12:13:28.483Z
Answers.Text: Thank you for your answer! I have a couple of questions regarding conditions 3) and 4).
  
  How do you prove 4)? Is the following correct? $\mathrm{Var}(R_{n+1}+ \gamma V_n(S')+V_\pi(S)) = \mathrm{Var}(R_{n+1}+\gamma V_n(S'))$ because $V_\pi(S)$ is not random. We can then write that as $\mathrm{Var}(R_{n+1}) + \mathrm{Var}(\gamma V_n(S'))$ because $R_{n+1}$ and $V_n(S')$ are independent.
  
  Next, if $R_{n+1}$ is bounded, so is $\mathrm{Var}(R_{n+1})$. Suppose $\mathrm{Var}(R_{n+1}) \leq K$, with $K > 1$.
  
  (Character limit)
Answers.UserDisplayName: Kareit
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-02-11T12:13:49.140Z
Answers.Text: Then $\mathrm{Var}(R_{n+1}) + \mathrm{Var}(\gamma V_n(S')) \leq K+\gamma^2\mathrm{Var}(V_n(S')) = K(1+\frac{\gamma^2}{K}\mathrm{Var}(V_n(S')) \leq K(1+\mathrm{Var}(V_n(S'))$.  
  
  The last inequality is because of $K>1$. And then I don't know how to get to condition 4).  
  
  And for 3), what is $P_\pi$? The probability of transitioning from $S$ to $S'$? And is $R_\pi$ the expected next reward when starting in state S? How condition 3) follow from what you said?  
  
  Sorry for the inconvenience, maybe what I ask is easy but I am not getting how these conditions are met.
Answers.UserDisplayName: Kareit
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-02-12T23:51:08.670Z
Answers.Text: $R_{n+1}$ and $V_n(S')$ can be both conceived to be samples during above iterative update step of the two stochastic processes of immediate next reward and cumulative future rewards, respectively, albeit indexed with an offset together. Since in RL rewards are assumed to be summable with discount rate, even the two processes are dependent (actually most likely) the conditional variance of the two random variables given $P_n$ must be bounded from above (note $V_n(S')$ is a sample of future reward sampling statistic of the next $S'$) thus you can always find some constant $C$ to fit condition 4)
Answers.UserDisplayName: cinch
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-02-13T06:18:27.427Z
Answers.Text: Yes $R_π$ here is the mean next reward starting in any state S and $P_π$ is the state transition probability matrix from such state under policy π with action component summed out and is a hallmark of MDP Bellman equation with matrix form $\vec V_π=\vec R_π+γP_π\vec V_π$ for all states, thus $E[V_n(S')|P_n]=P_πV_n(S)$. Though TD(0) is model free, the maximum norm of $P_π$ of all state pairs must be bounded above by 1. Thus the conditional expectation of $F_n(S)$ reduced to $γP_π(V_n(S)−V_π(S))$ whose maximum norm is obviously $\le γ||Δ_n||_W$ which is defined to come from all possible states.
Answers.UserDisplayName: cinch
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-02-14T11:11:38.927Z
Answers.Text: I think I now understand condition 4) better. But I still don't get why condition 3) is met. Why does the equality $\mathbb{E}[V_n(S') | P_n] = P_\pi V_n(S)$ happen? The expression $\mathbb{E}[V_n(S') | P_n]$ is a vector right? With a row for each possible state of the MDP. Also, $P_\pi V_n(S)$ looks like a vector to me where each row $j$ is $\sum_i \mathbb{P}(S_j| S_i)V_n(S_i)$, which I don't know why it equals to the left-hand side of the equation.
Answers.UserDisplayName: Kareit
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-02-16T00:23:21.913Z
Answers.Text: Now it seems to me that your confusion lies in the vector interpretation while for OP's boxed algo and my above answer we'd better view them as scalar version for simplicity and clarity, then $E[V_n(S')|P_n]$ is nothing but the weighted average of all possible next states' sampled $V_n$ from the said state $S$ in OP's boxed algo at *current* iteration step $n$ with weights being their respective state transition probability from $S$ to every possible next state $S'$ simply per definition of expectation of probability theory, thus formally $E[V_n(S′)|P_n]=\sum_{S'} p_π(S'|S)V_n(S)$.
Answers.UserDisplayName: cinch
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-02-16T23:48:10.360Z
Answers.Text: If $\mathbb{E}[V_n(S')|P_n]$ is the weighted average of all possible next states, wouldn't it be $\mathbb{E}[V_n(S')|P_n] = \sum_{S'}p_\pi(S'|S)V_n(S')$? I changed the last term to $V_n(S')$ from $V_n(S)$. If I am right the $S'$ in the summation are like all the possible next states.
  
  With your equation, I think I could write $\sum_{S'}p_\pi(S'|S)V_n(S) = V_n(S)\sum_{S'}p_\pi(S'|S) = V_n(S)*1$, which doesn't make sense to me at all.
Answers.UserDisplayName: Kareit
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-02-17T00:54:45.057Z
Answers.Text: Thanks for your careful thorough checking! Yes obviously you're right and it's a typo in my last commented sentence. And since now the RHS $S'$ in your corrected $V_n(S')$ is supposed to range over all finite states it's analytically equivalent to conclude $E[F_n(S)|P_n]=γP_πV_n(S)-γP_πV_π(S)$ either in the most generic matrix-vector or above scalar form which doesn't affect final convergence result as concluded in my answer.
Answers.UserDisplayName: cinch
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-02-17T12:33:41.427Z
Answers.Text: Thank you for your answer and all the explanations! I think I now understand the proof better, although I still have to think a little about the matrix part.
Answers.UserDisplayName: Kareit
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-02-17T21:40:27.887Z
Answers.Text: Great to hear! To completely clarify your remaining matrix confusion, every variable in both the extended Dvoretzky’s theorem and your boxed algo is scalar. To understand the maximum norm in matrix form to fit condition 3) & 4), you just need to enumerate all the   conditional expectations/variances in 3) and 4), respectively, of different but finite states $S$ as a column vector $[E[F_n(S_1)|P_n], ..., E[F_n(S_i)|P_n], ...]$. And the RHS of my above commented $P_πV_n(S),P_πV_π(S)$ should be understood as scalars by summing out the all ranging $S$ as you've already pointed out and understood.
Answers.UserDisplayName: cinch
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-02-11T06:37:53.450Z
Answers.LastActivityDate: 2023-02-11T06:55:48.133Z
Answers.LastEditDate: 2023-02-11T06:55:48.133Z
Answers.UserDisplayName: cinch
Body: <p>I am looking for a proof of the following tabular TD(0) algorithm:
  <a href="https://i.sstatic.net/vPV0I.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/vPV0I.png" alt="TD0" /></a></p>
  <p>However, I can only find proofs with the more general TD(<span class="math-container">$\lambda$</span>) algorithm and I am having problems understanding them. In particular this one: <a href="https://proceedings.neurips.cc/paper/1993/file/5807a685d1a9ab3b599035bc566ce2b9-Paper.pdf" rel="nofollow noreferrer">Convergence of Stochastic Iterative
  Dynamic Programming Algorithms</a></p>
  <p>Where can I find a proof for the simpler TD(0) method? I know that <span class="math-container">$\alpha$</span> needs to satisfy <span class="math-container">$\sum_n \alpha_n = \infty$</span> and <span class="math-container">$\sum_n \alpha_n^2 &lt; \infty$</span> in order to converge with probability one, despite the fact that the image shows a constant <span class="math-container">$\alpha$</span>, so a proof using either a constant or non constant (I think in this case it only converges in expectation?) <span class="math-container">$\alpha$</span> works for me.</p>
  
Tags: <reinforcement-learning><temporal-difference-methods>
Title: Proof of convergence of TD(0) algorithm
UserDisplayName: Kareit
ThreadText: # Proof of convergence of TD(0) algorithm
  
  (Asked by: username_0 on 2023-02-10)
  
  I am looking for a proof of the following tabular TD(0) algorithm:
  [![TD0](https://i.sstatic.net/vPV0I.png)](https://i.sstatic.net/vPV0I.png)
  
  However, I can only find proofs with the more general TD($\lambda$) algorithm and I am having problems understanding them. In particular this one: [Convergence of Stochastic Iterative
  Dynamic Programming Algorithms](https://proceedings.neurips.cc/paper/1993/file/5807a685d1a9ab3b599035bc566ce2b9-Paper.pdf)
  
  Where can I find a proof for the simpler TD(0) method? I know that $\alpha$ needs to satisfy $\sum\_n \alpha\_n = \infty$ and $\sum\_n \alpha\_n^2 < \infty$ in order to converge with probability one, despite the fact that the image shows a constant $\alpha$, so a proof using either a constant or non constant (I think in this case it only converges in expectation?) $\alpha$ works for me.
  
  **Tags:** reinforcement-learning, temporal-difference-methods
  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2023-02-11. Score: 1
  
  As hinted in your reference the convergence of various TD algos lies at the extended Dvoretzky’s theorem (Theorem 1) which involves maximum norm to be applied to the entire state space with potentially numerous finite states in addition to solve the generic stochastic approximation problem as the estimation error converges to 0 w.p.1. Then you only need to transform the TD(0) iterative process to the form of Theorem 1 and also show it satisfies all 4 constraints there to rigorously prove its convergence w.p.1.
  
  For TD(0) the iterative state value update process of all states $S$ in the finite state space for each step $n$ of an episode is shown in OP as (here for generality $α$ may not be constant):
  
  \begin{align\*}
  V\_{n+1}(S) &= V\_n(S) + α\_n(S)(R\_{n+1} + γV\_n(S') - V\_n(S)) \\
  &=(1 − α\_n(S))V\_n(S) + α\_n(S)(R\_{n+1} + γV\_n(S'))
  \end{align\*}
  
  Then define the estimation error as $∆\_n(S) = V\_n(S) − V\_π(S)$, where $V\_π(S)$ is the state value under policy $π$, we can easily arrive at:
  \begin{align\*}
  ∆\_{n+1}(S) &= (1 − α\_n(S))∆\_n(S) + α\_n(S)(R\_{n+1} + γV\_n(S') - V\_π(S))
  \end{align\*}
  
  Then obviously $\beta\_n(S)=α\_n(S), F\_n(S)=R\_{n+1} + γV\_n(S') - V\_π(S)$, and if $α$ is not constant and satisfies your above constraint $\sum\_n \alpha\_n(S) = \infty$ and $\sum\_n \alpha\_n(S)^2 < \infty$ for every state of the finite state space, then condition 1), 2) are satisfied. And since $V\_π(S)$ is non-random and $R\_{n+1}$ is bounded thus condition 4) is easily satisfied. Finally since $V\_n(S')=P\_πV\_n(S)$ where $P\_π$ is the state transition probability and $V\_π(S)=R\_π+ γP\_πV\_π(S)$, thus we have the conditional expectation value in condition 3) bounded from above as required. Thus we can prove TD(0) convergence.
  
  > **Comments:**
  > **username_0**: Thank you for your answer! I have a couple of questions regarding conditions 3) and 4).  How do you prove 4)? Is the following correct? $\mathrm{Var}(R_{n+1}+ \gamma V_n(S')+V_\pi(S)) = \mathrm{Var}(R_{n+1}+\gamma V_n(S'))$ because $V_\pi(S)$ is not random. We can then write that as $\mathrm{Var}(R_{n+1}) + \mathrm{Var}(\gamma V_n(S'))$ because $R_{n+1}$ and $V_n(S')$ are independent.  Next, if $R_{n+1}$ is bounded, so is $\mathrm{Var}(R_{n+1})$. Suppose $\mathrm{Var}(R_{n+1}) \leq K$, with $K > 1$.  (Character limit)  
  > **username_0**: Then $\mathrm{Var}(R_{n+1}) + \mathrm{Var}(\gamma V_n(S')) \leq K+\gamma^2\mathrm{Var}(V_n(S')) = K(1+\frac{\gamma^2}{K}\mathrm{Var}(V_n(S')) \leq K(1+\mathrm{Var}(V_n(S'))$.    The last inequality is because of $K>1$. And then I don't know how to get to condition 4).    And for 3), what is $P_\pi$? The probability of transitioning from $S$ to $S'$? And is $R_\pi$ the expected next reward when starting in state S? How condition 3) follow from what you said?    Sorry for the inconvenience, maybe what I ask is easy but I am not getting how these conditions are met.  
  > **username_1**: $R_{n+1}$ and $V_n(S')$ can be both conceived to be samples during above iterative update step of the two stochastic processes of immediate next reward and cumulative future rewards, respectively, albeit indexed with an offset together. Since in RL rewards are assumed to be summable with discount rate, even the two processes are dependent (actually most likely) the conditional variance of the two random variables given $P_n$ must be bounded from above (note $V_n(S')$ is a sample of future reward sampling statistic of the next $S'$) thus you can always find some constant $C$ to fit condition 4)  
  > **username_1**: Yes $R_π$ here is the mean next reward starting in any state S and $P_π$ is the state transition probability matrix from such state under policy π with action component summed out and is a hallmark of MDP Bellman equation with matrix form $\vec V_π=\vec R_π+γP_π\vec V_π$ for all states, thus $E[V_n(S')|P_n]=P_πV_n(S)$. Though TD(0) is model free, the maximum norm of $P_π$ of all state pairs must be bounded above by 1. Thus the conditional expectation of $F_n(S)$ reduced to $γP_π(V_n(S)−V_π(S))$ whose maximum norm is obviously $\le γ||Δ_n||_W$ which is defined to come from all possible states.  
  > **username_0**: I think I now understand condition 4) better. But I still don't get why condition 3) is met. Why does the equality $\mathbb{E}[V_n(S') | P_n] = P_\pi V_n(S)$ happen? The expression $\mathbb{E}[V_n(S') | P_n]$ is a vector right? With a row for each possible state of the MDP. Also, $P_\pi V_n(S)$ looks like a vector to me where each row $j$ is $\sum_i \mathbb{P}(S_j| S_i)V_n(S_i)$, which I don't know why it equals to the left-hand side of the equation.  
  > **username_1**: Now it seems to me that your confusion lies in the vector interpretation while for OP's boxed algo and my above answer we'd better view them as scalar version for simplicity and clarity, then $E[V_n(S')|P_n]$ is nothing but the weighted average of all possible next states' sampled $V_n$ from the said state $S$ in OP's boxed algo at *current* iteration step $n$ with weights being their respective state transition probability from $S$ to every possible next state $S'$ simply per definition of expectation of probability theory, thus formally $E[V_n(S′)|P_n]=\sum_{S'} p_π(S'|S)V_n(S)$.  
  > **username_0**: If $\mathbb{E}[V_n(S')|P_n]$ is the weighted average of all possible next states, wouldn't it be $\mathbb{E}[V_n(S')|P_n] = \sum_{S'}p_\pi(S'|S)V_n(S')$? I changed the last term to $V_n(S')$ from $V_n(S)$. If I am right the $S'$ in the summation are like all the possible next states.  With your equation, I think I could write $\sum_{S'}p_\pi(S'|S)V_n(S) = V_n(S)\sum_{S'}p_\pi(S'|S) = V_n(S)*1$, which doesn't make sense to me at all.  
  > **username_1**: Thanks for your careful thorough checking! Yes obviously you're right and it's a typo in my last commented sentence. And since now the RHS $S'$ in your corrected $V_n(S')$ is supposed to range over all finite states it's analytically equivalent to conclude $E[F_n(S)|P_n]=γP_πV_n(S)-γP_πV_π(S)$ either in the most generic matrix-vector or above scalar form which doesn't affect final convergence result as concluded in my answer.  
  > **username_0**: Thank you for your answer and all the explanations! I think I now understand the proof better, although I still have to think a little about the matrix part.  
  > **username_1**: Great to hear! To completely clarify your remaining matrix confusion, every variable in both the extended Dvoretzky’s theorem and your boxed algo is scalar. To understand the maximum norm in matrix form to fit condition 3) & 4), you just need to enumerate all the   conditional expectations/variances in 3) and 4), respectively, of different but finite states $S$ as a column vector $[E[F_n(S_1)|P_n], ..., E[F_n(S_i)|P_n], ...]$. And the RHS of my above commented $P_πV_n(S),P_πV_π(S)$ should be understood as scalars by summing out the all ranging $S$ as you've already pointed out and understood.  
  
  ---
  
  