2
$\begingroup$

In section $1.5$ of the book "Reinforcement Learning: An Introduction" by Sutton and Barto they use tic-tac-toe as an example of an RL use case. They provide the following temporal difference update rule in that section: $$ V(S_{t}) \leftarrow V(S_t) + \alpha[V(S_{t+1}) - V(S_t)] \tag{1} $$ However, in the chapter on TD methods they state that the "simplest TD method makes the update": $$ V(S_{t}) \leftarrow V(S_t) + \alpha[R_{t+1} + \gamma V(S_{t+1}) - V(S_t)] \tag{2} $$

Does any one have an explanation for where $(1)$ comes from? I can't see it to be equivalent to $(2)$.

I am also wondering if anyone has a way of relating this update rule to dynamic programming. Is this supposed to be some sort of approximation of value iteration when the environments dynamics, $p(s', r | s, a)$, is unknown?

Improve this question
$\endgroup$
1
  • $\begingroup$ I wish I could answer this but I'm struggling with the notation a bit as well. If gamma is 1 and the rewards are sparse (0 for non winning moves, 100 for winning, etc) I can see the similarity between the equations. $\endgroup$
    – foreverska
    Commented Apr 11 at 3:23

1 Answer 1

Reset to default
4
$\begingroup$

The equation (1) you mentioned is a simplified form of the temporal difference TD(0) update rule, specifically for the case of episodic tasks where there's no discounting $\gamma$ and the only reward is at the episodic terminating state such as tic-tac-toe. Equation (2) is a more general form applicable to both episodic and continuing tasks, considering future rewards through discounting which is the one typically used in RL TD learning methods.

As for the connection to value iteration of dynamic programming, it seems not much since value iteration update rule is based on Bellman optimality operator of the Bellman optimality equation (BOE) whose convergence is based on contraction mapping fixed point theorem, while the convergence of TD learning is based on Dvoretzky’s convergence theorem of stochastic approximation.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks for the answer! Is there any similarity to DP at all? In Sutton&Barto they state in the section on DP that other methods try to mimic DP without the assumption of complete knowledge. Surely it must be more similarites than the common goal of finding an optimal policy, or? $\endgroup$
    – mNugget
    Commented Apr 11 at 5:58
  • 1
    $\begingroup$ Of course their goal to find optimal policy is similar while DP is usually model-base given your transition dynamics thus it's more like planning with precision and often better convergence, and TD is model-free method so you cannot use transition dynamics and thus more trial and error training needed. $\endgroup$
    – cinch
    Commented Apr 11 at 6:09

You must log in to answer this question.

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