# Where is the problem: in batch TD(0) algorithm or in the code to solve AB problem in Sutton-Barto RL book?

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?

• I did not understand what you mean. initial values can be arbitrary and I considered all data in the given episodes. Feb 21, 2023 at 9:33
• even if you use the initial condition v(1)=v(2)=1, it does not converge to the right value. Feb 21, 2023 at 22:37
• 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. Feb 22, 2023 at 3:52
• please see the slides 17-19 from this link: groups.uni-paderborn.de/lea/share/lehre/reinforcementlearning/…. They obtained the results analytically. Feb 22, 2023 at 6:43
• 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. Feb 22, 2023 at 6:52

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