1
$\begingroup$

Here is the batch TD(0) algorithm:

enter image description here

Here is the AB example I want to solve using batch TD(0):

enter image description here

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?

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

1 Answer 1

0
$\begingroup$

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
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .