Answers.Body: <p>Your greedy policy function is wrong.</p>
  <p>It should be:</p>
  <pre><code>def greedy_policy(V, S):
     # At the edges - immediate return
     if S == 0:
        return S+1
     if S == len(V)-1:
        # Technically you should never reach here, because termination
        return S-1
     # In the middle - choose the highest estimated future return
     a = gridworld[S-1] + GAMMA * V[S-1]
     b = gridworld[S+1] + GAMMA * V[S+1]
     if a &lt; b:
        return S+1
     else:
        return S-1
  </code></pre>
  <p>This makes sense, your state value function <em>assumes</em> you will follow this rule - if the greedy policy that you were evaluating really did step backwards and forwards between states 0 and 1, then the values of both those states would be <span class="math-container">$0$</span> because a reward is never realised.</p>
  <p>In general, when working from a state value table <span class="math-container">$v(s)$</span>, the greedy policy with respect to those values is given by:</p>
  <p><span class="math-container">$$\pi(s) = \text{argmax}_a \sum_{r,s'} p(r, s'|s,a)(r + \gamma v(s'))$$</span></p>
  <p>Note this does not have to be the same policy as used to calculate <span class="math-container">$v(s)$</span>, but in the special case of optimal value function (and therefore an optimal policy) it is.</p>
  <p>If you want to avoid using the MDP model for transition and reward probabilities <span class="math-container">$p(r, s'|s,a)$</span>, then you will need to work with action value estimates and use a method like SARSA(<span class="math-container">$\lambda$</span>) or Q(<span class="math-container">$\lambda$</span>). If you use an action value table <span class="math-container">$q(s,a)$</span> then the greedy policy is much simpler:</p>
  <p><span class="math-container">$$\pi(s) = \text{argmax}_a q(s,a)$$</span></p>
  <p>In that case, you <em>can</em> select max values from your action values table.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-11-24T00:49:11.580Z
Answers.Text: That certainly results in expected behaviour. But why is it acceptable that the policy can depend on knowing the immediate reward for any state at all times? I thought the point of reinforcement learning was that that information is supposed to be learned through experience.
Answers.UserDisplayName: Multihunter
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-11-24T01:08:43.997Z
Answers.Text: And, if I understand the equation you shared correctly, it is choosing the action which maximises the expected reward (immediate + long-term), after accounting for rewards that only aren't always there? e.g. If it only rewards 50% of the time at state=2, then $p(r,s'|s,a)=0.5$ when considering moving (s=1, a=+1). Does that mean that $p(r,s'|s,a)$ is also somehow also estimated during training?
Answers.UserDisplayName: Multihunter
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-11-24T08:02:05.243Z
Answers.Text: @Multihunter: The TD($\lambda$) using state values that you have implemented is a (unnamed) baseline explanatory method that relies on knowing the MDP model (which is what $p(r,s'|s,a)$ is effectively). Usually you would learn about the approach on the way to implement SARSA($\lambda$) or Q($\lambda$), which don't have this limitation. In general, model-free approaches require learning action values $Q(S,A)$, not state values, for this reason. You could ask a separate question if you like why this is the case theoretically.
Answers.UserDisplayName: Neil Slater
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-11-25T08:22:22.077Z
Answers.Text: Thanks. Can you update your answer to include this extra information? I got this definition from Chapter 6 of Reinforcement Learning by R. Sutton and A. Barto. I think that the most salient error I made was in my assumption of what the TD($\lambda$) algorithms are for. I assumed that they were complete solutions to reinforcement learning in their own right (even if a bit slow). It seems odd to me that it wasn't just defined as using $R_t$ instead to estimate the MDP model at the same time...
Answers.UserDisplayName: Multihunter
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-11-25T09:01:34.800Z
Answers.Text: @Multihunter Sutton & Barto introduce methods in prediction then control. When performing prediction against a fixed policy, the state value function can be more useful than the action value function. I.e. you can observe the state and make an estimate of the expected return going forward. However, you don't really want to use "raw" TD($\lambda$) against the state value function as a control method
Answers.UserDisplayName: Neil Slater
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-11-24T00:32:17.610Z
Answers.LastActivityDate: 2022-11-25T09:18:19.883Z
Answers.LastEditDate: 2022-11-25T09:18:19.883Z
Answers.UserDisplayName: Neil Slater
Body: <p>Temporal difference algorithms (TD(<span class="math-container">$\lambda$</span>)) are tabular solutions to reinforcement learning problems. That is, they create a table of all the states in the problem, and estimate the expected long-term reward that can be obtained from each state.</p>
  <p>The policy used in these situations is: &quot;in your current state, choose to transition to the state that maximises the long-term reward&quot;. I observe that the &quot;long-term reward&quot; of a terminal state is precisely 0, by definition (<a href="https://ai.stackexchange.com/questions/17890/in-reinforcement-learning-is-the-value-of-terminal-goal-state-always-zero">see here</a>).</p>
  <p>So, if the greedy policy is to &quot;choose the state which maximises the long-term reward&quot;, and the &quot;long-term reward&quot; of a terminal state is 0, doesn't that mean that the policy should never choose it, even if it has an immediate reward of 1 million points?</p>
  <hr />
  <p>Minimally, practically, my query can be observed in a 3x1 gridworld. The agent starts at 0, and the goal/positive reward is in 2.</p>
  <p>The update rule for TD(0) is:</p>
  <p><span class="math-container">$$ V(S_t) \leftarrow V(S_t) + \alpha\left[R_{t+1} + \gamma V(S_{t+1}) - V(S_t) \right] $$</span></p>
  <p>Where <span class="math-container">$R_{t+1}$</span> is the immediate reward for transitioning to <span class="math-container">$S_{t+1}$</span>.</p>
  <p>Running this in python, I get something like <span class="math-container">$V=[0.784, 0.895, 0]$</span>. According to my understanding of what <span class="math-container">$V(S)$</span> should be, this is roughly the correct result. However, if I now try to apply the greedy policy (<span class="math-container">$\epsilon=0$</span>), it will result in the agent swapping between state=0 and state=1 forever, and never opt to go to state=2, because the long-term expected reward of that state is, by definition, 0.</p>
  <p>Clearly there is something very fundamental that I am not understanding or missing, but I don't know what it is, or how to find it.</p>
  <pre><code>import random
  
  def random_policy(V, S):
     # At the edges - immediate return
     if S == 0:
        return S+1
     if S == len(V)-1:
        return S-1
     # In the middle - choose randomly
     if random.random() &gt; 0.5:
        return state+1
     else:
        return state-1
  
  def greedy_policy(V, S):
     # At the edges - immediate return
     if S == 0:
        return S+1
     if S == len(V)-1:
        return S-1
     # In the middle - choose the highest estimated V(S_{t+1})
     a = V[S-1]
     b = V[S+1]
     if a &lt; b:
        return S+1
     else:
        return S-1
  
  
  gridworld = [0, 0, 1]
  V =         [0, 0, 0]
  ALPHA = 0.1
  GAMMA = 0.9
  
  for x in range(1000): # episodes
     state = 0
     while state != 2:
        next_state = random_policy(V, state)
        reward = gridworld[next_state]
        V[state] += ALPHA*(reward + GAMMA*V[next_state] - V[state])
  
        state = next_state
  
  print(V)
  
  </code></pre>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-11-28T05:53:32.633Z
Comments.Text: Value function of terminal state being 0 is also consistent with biology when it's modeled for mesolimbic dopaminergic system responsible for reward signaling which really contains reward *prediction* error magically, not reward itself (the reward is originated in some other areas of brain such as OFC). Otherwise if it only contains reward thus not 0 at terminal state of episodic/continuing task, then cerebral cortex will continue to learn that have been already mastered and lead to many bad consequences such as synaptic weights growing ever stronger and interference with other newer learning.
Comments.UserDisplayName: cinch
Tags: <reinforcement-learning><temporal-difference-methods>
Title: Using TD algorithms, if the value function of terminal states is always 0, why would a policy ever choose it?
UserDisplayName: Multihunter
ThreadText: # Using TD algorithms, if the value function of terminal states is always 0, why would a policy ever choose it?
  
  (Asked by: username_0 on 2022-11-24)
  
  Temporal difference algorithms (TD($\lambda$)) are tabular solutions to reinforcement learning problems. That is, they create a table of all the states in the problem, and estimate the expected long-term reward that can be obtained from each state.
  
  The policy used in these situations is: "in your current state, choose to transition to the state that maximises the long-term reward". I observe that the "long-term reward" of a terminal state is precisely 0, by definition ([see here](https://ai.stackexchange.com/questions/17890/in-reinforcement-learning-is-the-value-of-terminal-goal-state-always-zero)).
  
  So, if the greedy policy is to "choose the state which maximises the long-term reward", and the "long-term reward" of a terminal state is 0, doesn't that mean that the policy should never choose it, even if it has an immediate reward of 1 million points?
  
  ---
  
  Minimally, practically, my query can be observed in a 3x1 gridworld. The agent starts at 0, and the goal/positive reward is in 2.
  
  The update rule for TD(0) is:
  
  $$ V(S\_t) \leftarrow V(S\_t) + \alpha\left[R\_{t+1} + \gamma V(S\_{t+1}) - V(S\_t) \right] $$
  
  Where $R\_{t+1}$ is the immediate reward for transitioning to $S\_{t+1}$.
  
  Running this in python, I get something like $V=[0.784, 0.895, 0]$. According to my understanding of what $V(S)$ should be, this is roughly the correct result. However, if I now try to apply the greedy policy ($\epsilon=0$), it will result in the agent swapping between state=0 and state=1 forever, and never opt to go to state=2, because the long-term expected reward of that state is, by definition, 0.
  
  Clearly there is something very fundamental that I am not understanding or missing, but I don't know what it is, or how to find it.
  
  ```
  import random
  
  def random_policy(V, S):
     # At the edges - immediate return
     if S == 0:
        return S+1
     if S == len(V)-1:
        return S-1
     # In the middle - choose randomly
     if random.random() > 0.5:
        return state+1
     else:
        return state-1
  
  def greedy_policy(V, S):
     # At the edges - immediate return
     if S == 0:
        return S+1
     if S == len(V)-1:
        return S-1
     # In the middle - choose the highest estimated V(S_{t+1})
     a = V[S-1]
     b = V[S+1]
     if a < b:
        return S+1
     else:
        return S-1
  
  gridworld = [0, 0, 1]
  V =         [0, 0, 0]
  ALPHA = 0.1
  GAMMA = 0.9
  
  for x in range(1000): # episodes
     state = 0
     while state != 2:
        next_state = random_policy(V, state)
        reward = gridworld[next_state]
        V[state] += ALPHA*(reward + GAMMA*V[next_state] - V[state])
  
        state = next_state
  
  print(V)
  
  ```
  
  **Tags:** reinforcement-learning, temporal-difference-methods
  
  > **Comments:**
  > **username_1**: Value function of terminal state being 0 is also consistent with biology when it's modeled for mesolimbic dopaminergic system responsible for reward signaling which really contains reward *prediction* error magically, not reward itself (the reward is originated in some other areas of brain such as OFC). Otherwise if it only contains reward thus not 0 at terminal state of episodic/continuing task, then cerebral cortex will continue to learn that have been already mastered and lead to many bad consequences such as synaptic weights growing ever stronger and interference with other newer learning.  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_2 on 2022-11-24. Score: 2 | Accepted answer
  
  Your greedy policy function is wrong.
  
  It should be:
  
  ```
  def greedy_policy(V, S):
     # At the edges - immediate return
     if S == 0:
        return S+1
     if S == len(V)-1:
        # Technically you should never reach here, because termination
        return S-1
     # In the middle - choose the highest estimated future return
     a = gridworld[S-1] + GAMMA * V[S-1]
     b = gridworld[S+1] + GAMMA * V[S+1]
     if a < b:
        return S+1
     else:
        return S-1
  
  ```
  
  This makes sense, your state value function *assumes* you will follow this rule - if the greedy policy that you were evaluating really did step backwards and forwards between states 0 and 1, then the values of both those states would be $0$ because a reward is never realised.
  
  In general, when working from a state value table $v(s)$, the greedy policy with respect to those values is given by:
  
  $$\pi(s) = \text{argmax}\_a \sum\_{r,s'} p(r, s'|s,a)(r + \gamma v(s'))$$
  
  Note this does not have to be the same policy as used to calculate $v(s)$, but in the special case of optimal value function (and therefore an optimal policy) it is.
  
  If you want to avoid using the MDP model for transition and reward probabilities $p(r, s'|s,a)$, then you will need to work with action value estimates and use a method like SARSA($\lambda$) or Q($\lambda$). If you use an action value table $q(s,a)$ then the greedy policy is much simpler:
  
  $$\pi(s) = \text{argmax}\_a q(s,a)$$
  
  In that case, you *can* select max values from your action values table.
  
  > **Comments:**
  > **username_0**: That certainly results in expected behaviour. But why is it acceptable that the policy can depend on knowing the immediate reward for any state at all times? I thought the point of reinforcement learning was that that information is supposed to be learned through experience.  
  > **username_0**: And, if I understand the equation you shared correctly, it is choosing the action which maximises the expected reward (immediate + long-term), after accounting for rewards that only aren't always there? e.g. If it only rewards 50% of the time at state=2, then $p(r,s'|s,a)=0.5$ when considering moving (s=1, a=+1). Does that mean that $p(r,s'|s,a)$ is also somehow also estimated during training?  
  > **username_2**: @username_0: The TD($\lambda$) using state values that you have implemented is a (unnamed) baseline explanatory method that relies on knowing the MDP model (which is what $p(r,s'|s,a)$ is effectively). Usually you would learn about the approach on the way to implement SARSA($\lambda$) or Q($\lambda$), which don't have this limitation. In general, model-free approaches require learning action values $Q(S,A)$, not state values, for this reason. You could ask a separate question if you like why this is the case theoretically.  
  > **username_0**: Thanks. Can you update your answer to include this extra information? I got this definition from Chapter 6 of Reinforcement Learning by R. Sutton and A. Barto. I think that the most salient error I made was in my assumption of what the TD($\lambda$) algorithms are for. I assumed that they were complete solutions to reinforcement learning in their own right (even if a bit slow). It seems odd to me that it wasn't just defined as using $R_t$ instead to estimate the MDP model at the same time...  
  > **username_2**: @username_0 Sutton & Barto introduce methods in prediction then control. When performing prediction against a fixed policy, the state value function can be more useful than the action value function. I.e. you can observe the state and make an estimate of the expected return going forward. However, you don't really want to use "raw" TD($\lambda$) against the state value function as a control method  
  
  ---
  
  