Answers.Body: <p>Based upon your reference background of the given sample episodes in one batch, you need to average v_pr(2) since there're 8 cases then update your vector v with vector v_pr before next batch before expected convergence is achieved. Below is sample Python code based upon your matlab code, which arrives at your desired result from its output print.</p>
  <pre><code>v1=0
  v2=0
  v_ter=0
  thrs=1e-5
  delta=1e5
  alpha=0.01
  v_pr1=0
  v_pr2=0
  
  # we have 9 (s, a, r, s') cases
  while (delta &gt; thrs):
      v1 = v_pr1
      v2 = v_pr2
      v_pr1 = 0
      v_pr2 = 0
      for i in range(1, 10):
          if(i==1):
              v_pr1 += v1 + alpha * (0 + 1 * v2 - v1)
          elif(i==2):
              v_pr2 += v2 + alpha * (0 + 1 * v_ter - v2)
          elif(i&gt;=3 and i&lt;=8):
              v_pr2 += v2 + alpha * (1 + 1 * v_ter - v2)
          else:
              v_pr2 += v2 + alpha * (0 + 1 * v_ter - v2)
      v_pr2 = v_pr2/8
      Delta1 = abs(v_pr1 - v1)
      Delta2 = abs(v_pr2 - v2)
      delta = max(Delta1, Delta2)
  
  print('v1=' + str(v1) + ', v2=' + str(v2) + ', delta=' + str(delta))
  
  --------
  result:
  v1=0.7488911797417349, v2=0.7498874120968516, delta=9.962323551215846e-06
  </code></pre>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-02-23T06:36:05.000Z
Answers.LastActivityDate: 2023-02-23T06:36:05.000Z
Answers.UserDisplayName: cinch
Body: <p>Here is the batch TD(0) algorithm:</p>
  <p><a href="https://i.sstatic.net/l2VKg.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/l2VKg.png" alt="enter image description here" /></a></p>
  <p>Here is the AB example I want to solve using batch TD(0):</p>
  <p><a href="https://i.sstatic.net/Vjb8C.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/Vjb8C.png" alt="enter image description here" /></a></p>
  <p>And finally here is my Matlab code:</p>
  <p>% eps1: A 0 B 0<br />
  % eps2: B 1<br />
  % eps3: B 1<br />
  % eps4: B 1<br />
  % eps5: B 1<br />
  % eps6: B 1<br />
  % eps7: B 1<br />
  % eps8: B 0</p>
  <p>% (s, r, s') cases:<br />
  % (A,0,B)<br />
  % (B,0,Ter)<br />
  % (B,1,Ter)<br />
  % (B,1,Ter)<br />
  % (B,1,Ter)<br />
  % (B,1,Ter)<br />
  % (B,1,Ter)<br />
  % (B,1,Ter)<br />
  % (B,0,Ter)</p>
  <pre><code>n_s=2; % number of states
  
  v(1)=0;
  v(2)=0;
  v_ter=0;
  thrs=1e-3;
  
  delta=1e6;
  alpha=0.1;
  
  while (delta &gt; thrs)
  
      for i=1:9 % we have 9 (s, r, s') cases
          if i==1
              v_pr(1)=v(1)+alpha*[0+1*v(2)-v(1)];
              Delta(1)=abs(v_pr(1)-v(1));
          elseif i==2
              v_pr(2)=v(2)+alpha*[0+1*v_ter-v(2)];
              Delta(2)=abs(v_pr(2)-v(2));
          elseif (i&gt;=3) &amp;&amp; (i&lt;=8)
              v_pr(2)=v(2)+alpha*[1+1*v_ter-v(2)];
              Delta(2)=abs(v_pr(2)-v(2));
          else
              v_pr(2)=v(2)+alpha*[0+1*v_ter-v(2)];
              Delta(2)=abs(v_pr(2)-v(2));
          end
      end
      v=v_pr;
      delta=max(Delta);
      delta
  
  end
  </code></pre>
  <p>However, my code fails to find the correct result <span class="math-container">$v_{TD}(A)=v_{TD}(B)=3/4$</span>.
  Where is the problem: in the batch TD(0) algorithm, in my code or in both?</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2023-02-21T09:33:29.480Z
Comments.Text: I did not understand what you mean. initial values can be arbitrary and I considered all data in the given episodes.
Comments.UserDisplayName: DSPinfinity
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2023-02-21T22:37:07.190Z
Comments.Text: even if you use the initial condition v(1)=v(2)=1, it does not converge to the right value.
Comments.UserDisplayName: DSPinfinity
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2023-02-22T03:52:55.977Z
Comments.Text: For this specific MDP reward shape and extremely short episode and your code structure, v(1)=v(2)=1 would induce same bad behavior as v(1)=v(2)=0. Once you try some different big random numbers it would behave better. Also the experience D in your referenced algo most likely occurs within a single episode. Not sure where your 9 cases come from? It doesn't follow 75%/25% action policy at state B. you can simulate 100 cases where 75 of which follow the rewarded action and remaining cases follow the 0 reward action then to get average expected cumulative rewards for both states, respectively.
Comments.UserDisplayName: cinch
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2023-02-22T06:43:00.457Z
Comments.Text: please see the slides 17-19 from this link:  https://groups.uni-paderborn.de/lea/share/lehre/reinforcementlearning/lecture_slides/built/Lecture05.pdf.  They obtained the results analytically.
Comments.UserDisplayName: DSPinfinity
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2023-02-22T06:52:02.393Z
Comments.Text: we have 8 cases  at which 2 go to 0, 6 go to 1 and hence 25%/755 policy is followed. moreover, batch td  is for cases where you have limited number of episodes.
Comments.UserDisplayName: DSPinfinity
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2023-02-25T22:48:48.467Z
Comments.Text: My algo is called the batch TD(0) learning not MC since $\alpha$ is less than 1. If you reset $\alpha=1$ it'll give you exact result since your samples exactly follow your policy for both states. You can of course use pure TD(0) to incrementally update each state value after each atomic experience as your experience replay code but it would converge much slower and not accurate compared to my batch TD(0) which is more unbiased. To correct your code you *only* need your v_pr (which is really a temporary vector needed for delta) defined as v at the start of your while-loop *besides* Delta def.
Comments.UserDisplayName: cinch
Tags: <reinforcement-learning><sutton-barto><temporal-difference-methods>
Title: Where is the problem: in batch TD(0) algorithm or in the code to solve AB problem in Sutton-Barto RL book?
UserDisplayName: DSPinfinity
ThreadText: # Where is the problem: in batch TD(0) algorithm or in the code to solve AB problem in Sutton-Barto RL book?
  
  (Asked by: username_0 on 2023-02-20)
  
  Here is the batch TD(0) algorithm:
  
  Here is the AB example I want to solve using batch TD(0):
  
  And finally here is my Matlab code:
  % eps1: A 0 B 0
  % eps2: B 1
  % eps3: B 1
  % eps4: B 1
  % eps5: B 1
  % eps6: B 1
  % eps7: B 1
  % eps8: B 0
  % (s, r, s') cases:
  % (A,0,B)
  % (B,0,Ter)
  % (B,1,Ter)
  % (B,1,Ter)
  % (B,1,Ter)
  % (B,1,Ter)
  % (B,1,Ter)
  % (B,1,Ter)
  % (B,0,Ter)
  n_s=2; % number of states
  
  v(1)=0;
  v(2)=0;
  v_ter=0;
  thrs=1e-3;
  
  delta=1e6;
  alpha=0.1;
  
  while (delta > thrs)
  
      for i=1:9 % we have 9 (s, r, s') cases
          if i==1
              v_pr(1)=v(1)+alpha*[0+1*v(2)-v(1)];
              Delta(1)=abs(v_pr(1)-v(1));
          elseif i==2
              v_pr(2)=v(2)+alpha*[0+1*v_ter-v(2)];
              Delta(2)=abs(v_pr(2)-v(2));
          elseif (i>=3) && (i<=8)
              v_pr(2)=v(2)+alpha*[1+1*v_ter-v(2)];
              Delta(2)=abs(v_pr(2)-v(2));
          else
              v_pr(2)=v(2)+alpha*[0+1*v_ter-v(2)];
              Delta(2)=abs(v_pr(2)-v(2));
          end
      end
      v=v_pr;
      delta=max(Delta);
      delta
  
  end
  
  However, my code fails to find the correct result $v_{TD}(A)=v_{TD}(B)=3/4$.
  Where is the problem: in the batch TD(0) algorithm, in my code or in both?
  
  **Tags:** reinforcement-learning, sutton-barto, temporal-difference-methods
  > **Comments:**
  > **username_0**: I did not understand what you mean. initial values can be arbitrary and I considered all data in the given episodes.  
  > **username_0**: even if you use the initial condition v(1)=v(2)=1, it does not converge to the right value.  
  > **username_1**: For this specific MDP reward shape and extremely short episode and your code structure, v(1)=v(2)=1 would induce same bad behavior as v(1)=v(2)=0. Once you try some different big random numbers it would behave better. Also the experience D in your referenced algo most likely occurs within a single episode. Not sure where your 9 cases come from? It doesn't follow 75%/25% action policy at state B. you can simulate 100 cases where 75 of which follow the rewarded action and remaining cases follow the 0 reward action then to get average expected cumulative rewards for both states, respectively.  
  > **username_0**: please see the slides 17-19 from this link:  https://groups.uni-paderborn.de/lea/share/lehre/reinforcementlearning/lecture_slides/built/Lecture05.pdf.  They obtained the results analytically.  
  > **username_0**: we have 8 cases  at which 2 go to 0, 6 go to 1 and hence 25%/755 policy is followed. moreover, batch td  is for cases where you have limited number of episodes.  
  > **username_1**: My algo is called the batch TD(0) learning not MC since $\alpha$ is less than 1. If you reset $\alpha=1$ it'll give you exact result since your samples exactly follow your policy for both states. You can of course use pure TD(0) to incrementally update each state value after each atomic experience as your experience replay code but it would converge much slower and not accurate compared to my batch TD(0) which is more unbiased. To correct your code you *only* need your v_pr (which is really a temporary vector needed for delta) defined as v at the start of your while-loop *besides* Delta def.  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2023-02-23. Score: 0
  
  Based upon your reference background of the given sample episodes in one batch, you need to average v_pr(2) since there're 8 cases then update your vector v with vector v_pr before next batch before expected convergence is achieved. Below is sample Python code based upon your matlab code, which arrives at your desired result from its output print.
  v1=0
  v2=0
  v_ter=0
  thrs=1e-5
  delta=1e5
  alpha=0.01
  v_pr1=0
  v_pr2=0
  
  # we have 9 (s, a, r, s') cases
  while (delta > thrs):
      v1 = v_pr1
      v2 = v_pr2
      v_pr1 = 0
      v_pr2 = 0
      for i in range(1, 10):
          if(i==1):
              v_pr1 += v1 + alpha * (0 + 1 * v2 - v1)
          elif(i==2):
              v_pr2 += v2 + alpha * (0 + 1 * v_ter - v2)
          elif(i>=3 and i<=8):
              v_pr2 += v2 + alpha * (1 + 1 * v_ter - v2)
          else:
              v_pr2 += v2 + alpha * (0 + 1 * v_ter - v2)
      v_pr2 = v_pr2/8
      Delta1 = abs(v_pr1 - v1)
      Delta2 = abs(v_pr2 - v2)
      delta = max(Delta1, Delta2)
  
  print('v1=' + str(v1) + ', v2=' + str(v2) + ', delta=' + str(delta))
  
  --------
  result:
  v1=0.7488911797417349, v2=0.7498874120968516, delta=9.962323551215846e-06
  
  
  ---
  
  