Answers.Body: <blockquote>
  <p>It is a very simple example with terminal states <code>s2</code> and <code>s3</code> and it is clear that the Value function should converge to:
  <code>V(s1) = 1,  V(s2) = -1,  V(s3) = 1</code>
  which my implementations of MC and DP do, so whats wrong with my TD?</p>
  </blockquote>
  <p>It is not 100% clear whether you are trying to learn optimal control, or learn policy evaluation. I don't see any control logic in your TD example code though, and you specify an equiprobable policy. So I think you are coding policy evaluation.</p>
  <p>The correct state values for this environment and the equiprobable policy are:</p>
  <p><span class="math-container">$$v(s_1) = 0, v(s_2) = 0, v(s_3) = 0$$</span></p>
  <p>None of your implementations are getting this correct.</p>
  <p>The correct state values for this environment and the optimal policy (choose <span class="math-container">$a_2$</span> in <span class="math-container">$s_1$</span>) are:</p>
  <p><span class="math-container">$$v(s_1) = 1, v(s_2) = 0, v(s_3) = 0$$</span></p>
  <p>The discount factor will have no impact for a single-step environment, it is only the immediate reward that will be taken into consideration.</p>
  <p>I suspect you have some off-by-one errors in how you are thinking about assigning reward and calculating value, in all of your agent implementations. You seem to be missing that the state value of a state is the expected <em>future</em> reward and are including the reward for arriving in the state as part of the state's value. Whilst the value of all terminal states has to be <span class="math-container">$0$</span> by definition since no reward can be received once the episode has terminated.</p>
  <p>Without seeing your DP and MC implementations, it is <em>also</em> possible that you have implemented a control method for those (Value Iteration and Policy Iteration are usually presented as control methods by default), and a prediction method (calculate value function for a provided policy) for the TD(0), and that might explain some of the difference you are seeing. In Sutton &amp; Barto's book, TD is split into prediction and control methods with prediction being explained with pseudocode first, and TD(0) is very rarely used for control because it needs access to the MDP model in order to be used that way - it is more common to implement e.g. SARSA or Q-learning for TD control.</p>
  <p>From a coding perspective, your TD(0) learning loop is poorly structured in that it mixes processing data parameters from the environment (incorrectly) with the TD learning logic. What would probably help you most is separating the environment step function from the TD loop, and having a more formally-defined environment class. To support both model-free and model-based agents, you will need both a <code>env.step(action)</code> method, returning a tuple of <code>(reward, next_state, done)</code> - for model-free methods - and a <code>env.transitions(action)</code> which returns a transitions array of tuples <code>[(probability, reward, next_state, done),...]</code> that dynamic programming and TD(0) control can work through. You could also do something similar for the policy, although it is more common to make that a simple function in the agent's code as opposed to part of a separate class.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-10-03T18:09:51.907Z
Answers.Text: So by that definition, that $V(s)$ only contains the discounted future rewards and _does not_ contain the immediate reward for $s$, it doesn't make sense at all to assign a reward to the start states, right? Because that reward will never be represented in any value (only if we have a loop and enter the start state again)
Answers.UserDisplayName: mavex857
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-10-03T18:20:47.297Z
Answers.Text: @mavex857 In your case, probably no point in having that extra `s1: 1` in the data. However, the way you are assigning rewards to state is not the only possibility for MDP definition. The most general reward function is a distribution of real numbers returned by $r(s,a,s')$. So you *could* be determining reward with some combination of start and end state if you wished. It's part of the environment definition, so you would do it if it made sense for your environment. That's why I needed to ask earlier.
Answers.UserDisplayName: Neil Slater
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-10-01T20:24:53.867Z
Answers.LastActivityDate: 2023-10-02T21:06:15.743Z
Answers.LastEditDate: 2023-10-02T21:06:15.743Z
Answers.UserDisplayName: Neil Slater
Body: <p>I am trying to implement TD(0) among other RL Policy Evaluation techniques.</p>
  <p>I have also implemented the dynamic programming approach for a given model of the world and FV Monte Carlo and EV Monte Carlo for the unknown case. It seems that my implementation for TD(0) does not converge to the right state-values for my <code>value_fuction</code>. The other approaches work, so I don't think it is a problem of data stuctures in my case. I let TD(0) also work on pre-sampled episodes, but no matter how many episodes I use and how simple the state and action spaces are, it just does not yield the same results as MC. Here is my implementation:</p>
  <pre><code>def td_0(
      episodes: list[Episode],
      states: set[State],
      reward_function: RewardFunction,
      gamma: float = 0.9,
      alpha: float = 0.1,
  ):
      value_function = ValueFunction({s: 0 for s in states})
  
      # Episodes are lists of [state, action, reward, state, action, reward, ... , state]
      for epi in episodes:
          state_index = 0
          while state_index &lt; len(epi):
              state = epi[state_index]
              if state_index == len(epi) - 1: # for terminal state value is reward
                  value_function.set_value(state, reward_function.get_reward(state))
                  break
  
              next_state = epi[state_index + 3]
              # compute new value
              new_value = value_function.get_value(state) + alpha * (
                  reward_function.get_reward(state)
                  + gamma * value_function.get_value(next_state)
                  - value_function.get_value(state)
              )
  
              value_function.set_value(state, new_value)  
   
              # set next state index
              state_index += 3
  
      return value_function
  </code></pre>
  <p>Or is it simply a question of how to set the learning rate?
  For example, I use the following model to sample the episodes:</p>
  <pre><code># define some states
  s1 = State(1)
  s2 = State(2)
  s3 = State(3)
  states = {s1, s2, s3}
  
  # define some actions
  a1 = Action(1)
  a2 = Action(2)
  actions = {a1, a2}
  
  # dynamics model syntax: (current_state, action, next_state, probability)
  dynamics_model = Dynamics(
      [
          (s1, a1, s2, 1),
          (s1, a2, s3, 1),
      ]
  )
  
  # policy syntax: (state, action, probability)
  pi = Policy(
      [
          (s1, a2, 0.5),
          (s1, a1, 0.5),
      ]
  )
  
  # reward function syntax: {state: reward}
  reward_function = RewardFunction({s1: 1, s2: -1, s3: 1})
  </code></pre>
  <p>It is a very simple example with terminal states <code>s2</code> and <code>s3</code> and it is clear that the Value function should converge to:
  <code>V(s1) = 1,  V(s2) = -1,  V(s3) = 1</code>
  which my implementations of MC and DP do, so whats wrong with my TD?</p>
  <p>Here are some outputs of some runs:</p>
  <pre><code>Nr. Episodes: 10000
  Dynamic Programming
  {State_1: 1.0, State_2: -1.0, State_3: 1.0}
  First visit Monte Carlo
  {State_1: 1.0134, State_2: -1.0, State_3: 1.0}
  Every visit Monte Carlo
  {State_1: 1.0134, State_2: -1.0, State_3: 1.0}
  Temporal Difference (0)
  {State_1: 1.5552992453591237, State_2: -1, State_3: 1}
  </code></pre>
  <pre><code>Nr. Episodes: 10000
  Dynamic Programming
  {State_1: 1.0, State_2: -1.0, State_3: 1.0}
  First visit Monte Carlo
  {State_1: 1.0114, State_2: -1.0, State_3: 1.0}
  Every visit Monte Carlo
  {State_1: 1.0114, State_2: -1.0, State_3: 1.0}
  Temporal Difference (0)
  {State_1: 0.07098345716518928, State_2: -1, State_3: 1}
  </code></pre>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2023-10-01T20:56:43.503Z
Comments.Text: I made an answer, but I'm not 100% sure of it yet. I need to understand how rewards are granted in the environment. In the TD(0) code, following the step, you assign the reward value from the state you are leaving. That would always be 1 for leaving state $s_1$. But then no action could be taken in states $s_2$ and $s_3$, so their associated rewards make no sense at all. You are using them (incorrectly) in the TD(0) code, which may be part of your problem there. But there's more than that going wrong, and I suspect *all* your value estimators are incorrect.
Comments.UserDisplayName: Neil Slater
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2023-10-01T20:58:40.347Z
Comments.Text: So could you please explain *when* the rewards associated with each state are being observed/received by the agent? Typically rewards associated with a state are granted _either_ for leaving each state, or for arriving in each state. Your code sort of assumes both, but which did you intend?
Comments.UserDisplayName: Neil Slater
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2023-10-02T08:11:56.923Z
Comments.Text: @NeilSlater Rewards are granted when you _leave_ a state and get to the next state. But for my terminal states, you get the reward when you reach them. You are right that is kinda weird, but I think it still makes sense doesn't it? The value of $s1$ for my policy should be $V(s1) = R(s1) + 1/2*V(s2) + 1/2*V(s3)$. So why can't I say that $V(s2) = R(s2)$? It should give me the correct result that $V(s1) = 1 + 1/2 * 1 + 1/2 * (-1) = 1$. Value function is defined as _immediate reward_ + dicounted sum of future rewards, but for terminal states there are no future rewards.
Comments.UserDisplayName: mavex857
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2023-10-02T09:32:18.190Z
Comments.Text: Well, it would be part of my answer. You have got the MDP model a bit muddled. But just to be clear for me, you have  only two possible trajectories in your environment, and each will grant a single reward - could you clarify what the numerical reward is in each case, and why? First trajectory is $s_1, a_1, r_a, s_2$ - what is $r_a$ and why? Second trajectory is   $s_1, a_2, r_b, s_3$ - what is $r_b$ and why?
Comments.UserDisplayName: Neil Slater
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2023-10-02T12:50:34.663Z
Comments.Text: @NeilSlater Actually, the way I implemented the sampling of episodes, $r_{a}$ and $r_{b}$ would be $-1$ and $1$ respectively, so actually you obtain the reward when you enter a state. The sampled episodes are $s_{1}$, $a_{1}$, $-1$, $s_{2}$ and $s_{1}$, $a_{2}$, $1$, $s_{3}$.  But still I don't even use the $r$ values from the episode in my TD(0) implementation. I just iterate over the states, skipping actions and rewards, and compute the rewards from my _reward_function_. So the implementation would also work with just a list of states that does not contain the rewards. You know what I mean?
Comments.UserDisplayName: mavex857
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2023-10-02T12:52:11.057Z
Comments.Text: @NeilSlater and the values of the _reward_function_ is given in the code of my original question.
Comments.UserDisplayName: mavex857
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2023-10-02T20:12:35.230Z
Comments.Text: Yes, the values are displayed, but you are using them incorrectly in the TD(0) implementation, which is probably part of your problem. Yo uhave also misunderstood how the values of the terminal states should be calculated, in such a way that *all* of your agents have incorrect values. My original answer is actually correct, so I will undeleted it now.
Comments.UserDisplayName: Neil Slater
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2023-10-02T20:12:39.267Z
Comments.Text: Let us [continue this discussion in chat](https://chat.stackexchange.com/rooms/148886/discussion-between-neil-slater-and-mavex857).
Comments.UserDisplayName: Neil Slater
Tags: <reinforcement-learning><temporal-difference-methods><policy-evaluation>
Title: Why does my implementation of TD(0) not work?
UserDisplayName: mavex857
ThreadText: # Why does my implementation of TD(0) not work?
  
  (Asked by: username_0 on 2023-10-01)
  
  I am trying to implement TD(0) among other RL Policy Evaluation techniques.
  
  I have also implemented the dynamic programming approach for a given model of the world and FV Monte Carlo and EV Monte Carlo for the unknown case. It seems that my implementation for TD(0) does not converge to the right state-values for my `value_fuction`. The other approaches work, so I don't think it is a problem of data stuctures in my case. I let TD(0) also work on pre-sampled episodes, but no matter how many episodes I use and how simple the state and action spaces are, it just does not yield the same results as MC. Here is my implementation:
  
  ```
  def td_0(
      episodes: list[Episode],
      states: set[State],
      reward_function: RewardFunction,
      gamma: float = 0.9,
      alpha: float = 0.1,
  ):
      value_function = ValueFunction({s: 0 for s in states})
  
      # Episodes are lists of [state, action, reward, state, action, reward, ... , state]
      for epi in episodes:
          state_index = 0
          while state_index < len(epi):
              state = epi[state_index]
              if state_index == len(epi) - 1: # for terminal state value is reward
                  value_function.set_value(state, reward_function.get_reward(state))
                  break
  
              next_state = epi[state_index + 3]
              # compute new value
              new_value = value_function.get_value(state) + alpha * (
                  reward_function.get_reward(state)
                  + gamma * value_function.get_value(next_state)
                  - value_function.get_value(state)
              )
  
              value_function.set_value(state, new_value)  
   
              # set next state index
              state_index += 3
  
      return value_function
  
  ```
  
  Or is it simply a question of how to set the learning rate?
  For example, I use the following model to sample the episodes:
  
  ```
  # define some states
  s1 = State(1)
  s2 = State(2)
  s3 = State(3)
  states = {s1, s2, s3}
  
  # define some actions
  a1 = Action(1)
  a2 = Action(2)
  actions = {a1, a2}
  
  # dynamics model syntax: (current_state, action, next_state, probability)
  dynamics_model = Dynamics(
      [
          (s1, a1, s2, 1),
          (s1, a2, s3, 1),
      ]
  )
  
  # policy syntax: (state, action, probability)
  pi = Policy(
      [
          (s1, a2, 0.5),
          (s1, a1, 0.5),
      ]
  )
  
  # reward function syntax: {state: reward}
  reward_function = RewardFunction({s1: 1, s2: -1, s3: 1})
  
  ```
  
  It is a very simple example with terminal states `s2` and `s3` and it is clear that the Value function should converge to:
  `V(s1) = 1, V(s2) = -1, V(s3) = 1`
  which my implementations of MC and DP do, so whats wrong with my TD?
  
  Here are some outputs of some runs:
  
  ```
  Nr. Episodes: 10000
  Dynamic Programming
  {State_1: 1.0, State_2: -1.0, State_3: 1.0}
  First visit Monte Carlo
  {State_1: 1.0134, State_2: -1.0, State_3: 1.0}
  Every visit Monte Carlo
  {State_1: 1.0134, State_2: -1.0, State_3: 1.0}
  Temporal Difference (0)
  {State_1: 1.5552992453591237, State_2: -1, State_3: 1}
  
  ```
  
  ```
  Nr. Episodes: 10000
  Dynamic Programming
  {State_1: 1.0, State_2: -1.0, State_3: 1.0}
  First visit Monte Carlo
  {State_1: 1.0114, State_2: -1.0, State_3: 1.0}
  Every visit Monte Carlo
  {State_1: 1.0114, State_2: -1.0, State_3: 1.0}
  Temporal Difference (0)
  {State_1: 0.07098345716518928, State_2: -1, State_3: 1}
  
  ```
  
  **Tags:** reinforcement-learning, temporal-difference-methods, policy-evaluation
  
  > **Comments:**
  > **username_1**: I made an answer, but I'm not 100% sure of it yet. I need to understand how rewards are granted in the environment. In the TD(0) code, following the step, you assign the reward value from the state you are leaving. That would always be 1 for leaving state $s_1$. But then no action could be taken in states $s_2$ and $s_3$, so their associated rewards make no sense at all. You are using them (incorrectly) in the TD(0) code, which may be part of your problem there. But there's more than that going wrong, and I suspect *all* your value estimators are incorrect.  
  > **username_1**: So could you please explain *when* the rewards associated with each state are being observed/received by the agent? Typically rewards associated with a state are granted _either_ for leaving each state, or for arriving in each state. Your code sort of assumes both, but which did you intend?  
  > **username_0**: @username_1 Rewards are granted when you _leave_ a state and get to the next state. But for my terminal states, you get the reward when you reach them. You are right that is kinda weird, but I think it still makes sense doesn't it? The value of $s1$ for my policy should be $V(s1) = R(s1) + 1/2*V(s2) + 1/2*V(s3)$. So why can't I say that $V(s2) = R(s2)$? It should give me the correct result that $V(s1) = 1 + 1/2 * 1 + 1/2 * (-1) = 1$. Value function is defined as _immediate reward_ + dicounted sum of future rewards, but for terminal states there are no future rewards.  
  > **username_1**: Well, it would be part of my answer. You have got the MDP model a bit muddled. But just to be clear for me, you have  only two possible trajectories in your environment, and each will grant a single reward - could you clarify what the numerical reward is in each case, and why? First trajectory is $s_1, a_1, r_a, s_2$ - what is $r_a$ and why? Second trajectory is   $s_1, a_2, r_b, s_3$ - what is $r_b$ and why?  
  > **username_0**: @username_1 Actually, the way I implemented the sampling of episodes, $r_{a}$ and $r_{b}$ would be $-1$ and $1$ respectively, so actually you obtain the reward when you enter a state. The sampled episodes are $s_{1}$, $a_{1}$, $-1$, $s_{2}$ and $s_{1}$, $a_{2}$, $1$, $s_{3}$.  But still I don't even use the $r$ values from the episode in my TD(0) implementation. I just iterate over the states, skipping actions and rewards, and compute the rewards from my _reward_function_. So the implementation would also work with just a list of states that does not contain the rewards. You know what I mean?  
  > **username_0**: @username_1 and the values of the _reward_function_ is given in the code of my original question.  
  > **username_1**: Yes, the values are displayed, but you are using them incorrectly in the TD(0) implementation, which is probably part of your problem. Yo uhave also misunderstood how the values of the terminal states should be calculated, in such a way that *all* of your agents have incorrect values. My original answer is actually correct, so I will undeleted it now.  
  > **username_1**: Let us [continue this discussion in chat](https://chat.stackexchange.com/rooms/148886/discussion-between-username_1-and-username_0).  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2023-10-01. Score: 1
  
  > It is a very simple example with terminal states `s2` and `s3` and it is clear that the Value function should converge to:
  > `V(s1) = 1, V(s2) = -1, V(s3) = 1`
  > which my implementations of MC and DP do, so whats wrong with my TD?
  
  It is not 100% clear whether you are trying to learn optimal control, or learn policy evaluation. I don't see any control logic in your TD example code though, and you specify an equiprobable policy. So I think you are coding policy evaluation.
  
  The correct state values for this environment and the equiprobable policy are:
  
  $$v(s\_1) = 0, v(s\_2) = 0, v(s\_3) = 0$$
  
  None of your implementations are getting this correct.
  
  The correct state values for this environment and the optimal policy (choose $a\_2$ in $s\_1$) are:
  
  $$v(s\_1) = 1, v(s\_2) = 0, v(s\_3) = 0$$
  
  The discount factor will have no impact for a single-step environment, it is only the immediate reward that will be taken into consideration.
  
  I suspect you have some off-by-one errors in how you are thinking about assigning reward and calculating value, in all of your agent implementations. You seem to be missing that the state value of a state is the expected *future* reward and are including the reward for arriving in the state as part of the state's value. Whilst the value of all terminal states has to be $0$ by definition since no reward can be received once the episode has terminated.
  
  Without seeing your DP and MC implementations, it is *also* possible that you have implemented a control method for those (Value Iteration and Policy Iteration are usually presented as control methods by default), and a prediction method (calculate value function for a provided policy) for the TD(0), and that might explain some of the difference you are seeing. In Sutton & Barto's book, TD is split into prediction and control methods with prediction being explained with pseudocode first, and TD(0) is very rarely used for control because it needs access to the MDP model in order to be used that way - it is more common to implement e.g. SARSA or Q-learning for TD control.
  
  From a coding perspective, your TD(0) learning loop is poorly structured in that it mixes processing data parameters from the environment (incorrectly) with the TD learning logic. What would probably help you most is separating the environment step function from the TD loop, and having a more formally-defined environment class. To support both model-free and model-based agents, you will need both a `env.step(action)` method, returning a tuple of `(reward, next_state, done)` - for model-free methods - and a `env.transitions(action)` which returns a transitions array of tuples `[(probability, reward, next_state, done),...]` that dynamic programming and TD(0) control can work through. You could also do something similar for the policy, although it is more common to make that a simple function in the agent's code as opposed to part of a separate class.
  
  > **Comments:**
  > **username_0**: So by that definition, that $V(s)$ only contains the discounted future rewards and _does not_ contain the immediate reward for $s$, it doesn't make sense at all to assign a reward to the start states, right? Because that reward will never be represented in any value (only if we have a loop and enter the start state again)  
  > **username_1**: @username_0 In your case, probably no point in having that extra `s1: 1` in the data. However, the way you are assigning rewards to state is not the only possibility for MDP definition. The most general reward function is a distribution of real numbers returned by $r(s,a,s')$. So you *could* be determining reward with some combination of start and end state if you wished. It's part of the environment definition, so you would do it if it made sense for your environment. That's why I needed to ask earlier.  
  
  ---
  
  