3
$\begingroup$

Exercise from the book:
7.11 Show that if the approximate action values are unchanging, then the tree-backup return (7.16) can be written as a sum of expectation-based TD errors: $$ \begin{align*} &G_{t:t+n} = Q(S_t, A_t) + \sum_{k=t}^{min(t+n-1,T-1)} \delta_k \prod_{i=t+1}^{k} \gamma \pi(A_i | S_i),\\ &G_{T-1:h} = R_T\\ &G_{h:h} = R_h + \sum_a (\pi (a|S_h) Q(A_h, S_h)) \text{, where }h < T-1\\ &\text{ where: } \delta_t = R_{t+1} + \gamma \bar{V}_t(S_{t+1} - Q(S_t, A_t) \end{align*} $$

Question: Ain't $G_{t:t+n} = Q(S_t, A_t) + \sum_{k=t}^{min(t+n-1,T-1)} \delta_k \prod_{i=t+1}^{k} \gamma \pi(A_i | S_i)$ missing return for $G_{h:h}$ in case $ h < T-1$? Here is my solution, I wonder if there is mistake or $G_{h:h}$ really should be included in sum?
my solution: $$ \begin{align*} &G_{t:t+n} = R_{t+1} + \gamma \sum_{a \neq A_{t+1}} \pi(a|S_{t+1}) Q(S_{t+1},a) + \gamma \pi (A_{t+1} | S_{t+1})G_{t+1:t+n}\\ &= R_{t+1} + \gamma \sum_{a \neq A_{t+1}} \pi(a|S_{t+1}) Q(S_{t+1},a) + \gamma \pi (A_{t+1} | S_{t+1})G_{t+1:t+n} + \gamma \pi(A_{t+1}|S_{t+1}) Q(S_{t+1},A_{t+1}) - \gamma \pi(A_{t+1}|S_{t+1}) Q(S_{t+1},A_{t+1})\\ &= R_{t+1} + \gamma \bar{V}_t(S_{t+1}) + \gamma \pi (A_{t+1} | S_{t+1})G_{t+1:t+n} - \gamma \pi(A_{t+1}|S_{t+1}) Q(S_{t+1},A_{t+1}) = R_{t+1} + \gamma \bar{V}_t(S_{t+1}) + \gamma \pi (A_{t+1} | S_{t+1}) (G_{t+1:t+n} - Q(S_{t+1},A_{t+1}))\\ &= R_{t+1} + \gamma \bar{V}_t(S_{t+1}) + \gamma \pi (A_{t+1} | S_{t+1}) (G_{t+1:t+n} - Q(S_{t+1},A_{t+1})) + Q(S_t, A_t) - Q(S_t, A_t)\\ &= Q(S_t, A_t) + \delta_t + \gamma \pi (A_{t+1} | S_{t+1}) (G_{t+1:t+n} - Q(S_{t+1},A_{t+1}))\\ &= Q(S_t, A_t) + \delta_t + \gamma \pi (A_{t+1} | S_{t+1}) (R_{t+2} + \gamma \sum_{a \neq A_{t+2}} \pi(a|S_{t+2}) Q(S_{t+2},a) + \gamma \pi (A_{t+2} | S_{t+2})G_{t+2:t+n} - Q(S_{t+1},A_{t+1}))\\ &= Q(S_t, A_t) + \delta_t + \gamma \pi (A_{t+1} | S_{t+1}) (R_{t+2} + \gamma \sum_{a \neq A_{t+2}} \pi(a|S_{t+2}) Q(S_{t+2},a) + \gamma \pi (A_{t+2} | S_{t+2})G_{t+2:t+n} - Q(S_{t+1},A_{t+1}) + \gamma \pi(A_{t+2}|S_{t+2}) Q(S_{t+2},A_{t+2}) - \gamma \pi(A_{t+2}|S_{t+2}) Q(S_{t+2},A_{t+2}))\\ &= Q(S_t, A_t) + \delta_t + \gamma \pi (A_{t+1} | S_{t+1}) (\delta_{t+1} + \gamma \pi (A_{t+2} | S_{t+2})G_{t+2:t+n} - \gamma \pi(A_{t+2}|S_{t+2}) Q(S_{t+2},A_{t+2}))\\ &= Q(S_t, A_t) + \delta_t + \gamma \pi (A_{t+1} | S_{t+1}) \delta_{t+1} + \gamma^2 \pi (A_{t+1} | S_{t+1}) \pi (A_{t+2} | S_{t+2})(G_{t+2:t+n} - Q(S_{t+2},A_{t+2}))\\ &= Q(S_t, A_t) + \delta_t + \gamma \pi (A_{t+1} | S_{t+1}) \delta_{t+1} + \gamma^2 \pi (A_{t+1} | S_{t+1}) \pi (A_{t+2} | S_{t+2}) \delta_{t+2} + ... + \gamma^{t+n-t} \pi (A_{t+1} | S_{t+1}) \pi (A_{t+2} | S_{t+2})...\pi (A_{t+n} | S_{t+n}))(R_{t+n} + \sum_a (\pi (a|S_{t+n}) Q(S_{t+n}, a)) - Q(S_{t+n},A_{t+n})) \\ &= Q(S_t, A_t) + (R_{t+n} + \sum_a (\pi (a|S_{t+n}) Q(S_{t+n}, a)) - Q(S_{t+n},A_{t+n})) \prod_{k=t+1}^{min(t+n,T-1)} \gamma \pi (A_k, S_k) + \sum_{k=t}^{min(t+n-1,T-1)} \delta_k \prod_{i=t+1}^{k} \gamma \pi(A_i | S_i) Q(S_t, A_t) \\ \end{align*} $$

$\endgroup$
1
  • 1
    $\begingroup$ +1 even only for having taken the time to write this whole thing down in latex $\endgroup$
    – Alberto
    Commented Apr 30 at 15:39

0

You must log in to answer this question.