%Random walk solver, Monte-Carlo %V[k](s) = V[k](s) + alpha*(R[k] - V[k-1](s)) %len: length of the walk %it: number of iterations %A: initial V %a: alpha value %s0: starting step function [V,RMSE]=rwMC(len,it,A,a,s0) l = int32(len + 2); if (mod(l,2) == 0) disp('length must be odd') return end %V: expected reward if (nargin >= 3) [m,n]=size(A); if (m ~= 1 || n ~= len) disp('initial vector dimension mismatch') return end V = [0 A 1]; else V = ones(1,l) * 0.5; end RMSE = zeros(1,it); %S: final result (to count RMS) S = (1:len)/(len+1); %iterations for i=1:it %generate walk (starting from the middle) if (nargin > 4) t = s0; else t = idivide(l,2); end T = zeros(1,l); while (t ~= 1 && t ~= l) if (rand < 0.5) t = t - 1; else t = t + 1; end T(t) = 1; %points stepped on end %if the end reached set the reward for all the points stepped on R = zeros(1,l); if (t == l) R = T; end %iterative averaging if (nargin < 4) a = 1/i; end V = V + T .* (R - V) * a; Vr = V(1,2:l-1); RMSE(i) = sqrt(sum((Vr-S).*(Vr-S))/len); end %remove the two ends V=V(1,2:l-1);

%Random walk solver - Temporal-Difference %V[k](s) = V[k-1](s) + alpha*(r + V[k-1](s) - V[k-1](s)) %len: length of the walk %it: number of iterations %A: initial V %a: alpha value %s0: starting step function [V,RMSE]=rwTD(len,it,A,a,s0) l = int32(len + 2); if (mod(l,2) == 0) disp('length must be even') return end if (nargin < 4) a = 0.1; end if (nargin >= 3) [m,n]=size(A); if (m ~= 1 || n ~= len) disp('initial vector dimension mismatch') return end V = [0 A 0]; else V = ones(1,l) * 0.5; V(1) = 0; V(l) = 0; end R = zeros(1,l); R(l) = 1; RMSE = zeros(1,it); S = (1:len)/(len+1); %iterations for i=1:it if (nargin > 4) s = s0; else s = idivide(l,2); end %Vp = V; while (s ~= 1 && s~= l) %store previous step sp = s; %generate step if (rand < 0.5) s = s - 1; else s = s + 1; end V(sp) = V(sp) + a*(R(s) + V(s) - V(sp)); end Vr = V(1,2:l-1); RMSE(i) = sqrt(sum((Vr-S).*(Vr-S))/len); end %remove the two ends V=V(1,2:l-1);

%plot Random walk results %Random walk: In a sequence one can step forward or backward one step. The %V function (expected reward) will show what is the probability of reaching %the rigth end of the path if starting from a given point. %This function will compare and plot the result of a Monte-Carlo method and %a Temporal-difference method for the problem. function [M,T,Md,Td]=rwPlot(len,it,A,a,s0) if (mod(int32(len),2) == 0) disp('length must be odd') return end switch nargin case 2 [Em,Dm]=rwMC(len, it); [Et,Dt]=rwTD(len, it); sLm = sprintf('MC'); sLt = sprintf('TD (alpha= 0.1)'); case 3 [m,n]=size(A); if (m ~= 1 || n ~= len) disp('initial vector dimension mismatch') return end [Em,Dm]=rwMC(len, it,A); [Et,Dt]=rwTD(len, it,A); sLm = sprintf('MC'); sLt = sprintf('TD (alpha= 0.1)'); case 4 [m,n]=size(A); if (m ~= 1 || n ~= len) disp('initial vector dimension mismatch') return end [Em,Dm]=rwMC(len, it,A,a); [Et,Dt]=rwTD(len, it,A,a); sLm = sprintf('MC (alpha= %f)',a); sLt = sprintf('TD (alpha= %f)',a); case 5 [m,n]=size(A); if (m ~= 1 || n ~= len) disp('initial vector dimension mismatch') return end [Em,Dm]=rwMC(len, it,A,a,s0); [Et,Dt]=rwTD(len, it,A,a,s0); sLm = sprintf('MC (alpha= %f)',a); sLt = sprintf('TD (alpha= %f)',a); end sTitle = sprintf('MC & TD method comparison on Random walk (%d)',len); figure(1); plot(1:it, Dm,'b',1:it, Dt,'r'); xlabel('iteration'); ylabel('RMS'); legend(sLm,sLt); title(sTitle); figure(2); plot(1:len, Em, '+b', 1:len, Et, '+r', 1:len, (1:len)/(len+1), 'k', ... 'LineWidth',2); xlabel('state'); ylabel('value'); legend(sLm,sLt,'real values','Location','NorthWest'); title(sTitle); M=Em; T=Et; Md = Dm(it); Td = Dt(it);