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

Question

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?

Answer 1

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