1
$\begingroup$

I am looking for a proof of the following tabular TD(0) algorithm: TD0

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

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.

$\endgroup$

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
10
  • $\begingroup$ 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) $\endgroup$
    – Kareit
    Feb 11 at 12:13
  • $\begingroup$ 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. $\endgroup$
    – Kareit
    Feb 11 at 12:13
  • $\begingroup$ $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) $\endgroup$ Feb 12 at 23:51
  • $\begingroup$ 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. $\endgroup$ Feb 13 at 6:18
  • $\begingroup$ 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. $\endgroup$
    – Kareit
    Feb 14 at 11:11

You must log in to answer this question.

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