强化学习简单示例——SARSA算法

【注】我也是刚刚接触强化学习的内容，对这部分理解不是很透彻，代码写的可能也会有不对或不完善的地方，还请各位批评指正。这个问题是个作业，这是我自己编的代码，老师提供的答案出来后再更。

【问题描述】

图中S为起点，G为终点，每次能前、后、左、右、左前、左后、右前、右后移动。当到达第4-9列的某一列时，会在某一状态的基础上向上被吹一格。如某一时刻到达了第4行第4列，则会被吹到第3行第4列。在第4行第7列则会被吹到第2行第7列。设每步的reward都为-1，无折扣，更新步长α为0.1，对于所有状态s和动作a，初始值函数Q(s，a)=0，ε-greedy方法的ε=0.1，求起点到终点的最优路径。

【思路】

将每个状态标号，从左到右，从上到下，为1-70。从起点S状态开始，用SARSA算法更新每个状态-动作的值函数Q，策略选择ε-greedy方法，直到到达终点G。这为一条完整的采样，再循环以上过程N次，N可以为2000、5000、10000等等，越大越接近真实值。最后得到完整的值函数Q表，从起点开始，每步选择使Q最大的动作，直到终点G，走过的路径即为最优路径。

【源代码】

1、SARSA.m

%SARSA求KING'MOVING问题
%
a=0.1;                  %更新步长
loops_num=2000;         %循环次数，自己设定，越大值函数越逼近真实值
reward=-1;              %奖赏,总为-1
global qMatrix;         %定义值函数矩阵
qMatrix=zeros(70,70);   %值函数矩阵赋值，初始全为0
routeMatrix=-1./zeros(7,10);   %定义行走路径矩阵，负无穷表示不走此路,0表示走此路
star_state=31;           %初始状态
final_state=38;          %终止状态
count=0;
epiosdes=[];
%SARSA算法更新值函数
for i=1:1:loops_num
    state=star_state;     
    action=select_action(state);     %选择当前状态下的动作
    while (1)      
        statep=action;                      %下个状态     
        actionp=select_action(statep);      %选择动作达到的状态下的动作
        qMatrix(state,action)=qMatrix(state,action)+a*(-1+qMatrix(statep,actionp)-qMatrix(state,action));      %更新值函数       
        state=statep;
        action=actionp;
        if(state==38)   break;   end     %如果到终点则退出
        count=count+1;
        epiosdes(count)=i;
    end  
%    count=count+1;
end
%找最优路径
state=star_state;
while(1)
    [val,action]=min(1./qMatrix(state,:));      %根据值函数最大，找下一个动作
    %将下个动作达到的状态设为可行走
    row=floor(action/10)+1;
    clo=action-(row-1)*10;
    routeMatrix(row,clo)=0;
    %将当前状态设为可行走
    row=floor(state/10)+1;
    clo=state-(row-1)*10;
    routeMatrix(row,clo)=0;        
    if(action==38)   break;  end          %到达终点，退出
    state=action;                         %将动作赋给状态
end
plot(1:1:count,epiosdes);   xlabel('Time steps');   ylabel('episodes');

2、selsect_action.m

%选择动作函数，用e-greedy算法
function[action_sel]=select_action(aa)
    actionMatrix=[11,10,9,1,-1,-9,-10,-11];    %定义动作，即8个方向
    max=-1000;    %要尽量小
    max_num=0;
    e=0.1;        %e-greedy算法的概率   
    global qMatrix;
    action_sel=0;
    action_maybe=[-1,-1,-1,-1,-1,-1,-1,-1];      %aa状态周围可能的状态，初始-1.-1代表没有此状态
    for i=1:1:8                                  %aa状态周围可能的状态
        action_maybe(i)=aa-actionMatrix(i);        
    %添加有风的情况
    row=floor(action_maybe(i)/10)+1;
    clo=action_maybe(i)-(row-1)*10;
    %向上吹一格的情况
    if(((clo>=4)&(clo<=6))|(clo==9))
        if(row>=2&&row<=7)     action_maybe(i)=action_maybe(i)-10; end      
    end
    %向上吹两格的情况
    if((clo==7)|(clo==8))
        if(row>=3&&row<=7)    action_maybe(i)=action_maybe(i)-20;  
        else if(row==2)     action_maybe(i)=action_maybe(i)-10;    end 
        end
    end            
    end
    %排除边角不能走的情况
    if(aa==1)    action_maybe(1:4)=-1;   action_maybe(6)=-1;   end
    if(aa==10)    action_maybe(1:3)=-1;   action_maybe(5)=-1;   action_maybe(8)=-1;  end
    if(aa==61)    action_maybe(6:8)=-1;   action_maybe(1)=-1;   action_maybe(4)=-1;  end
    if(aa==70)    action_maybe(5:8)=-1;   action_maybe(3)=-1;   end
    if(aa>=2&&aa<=9)   action_maybe(1:3)=-1;    end
    if(aa>=62&&aa<=69)   action_maybe(6:8)=-1;    end
    if(aa==11||aa==21||aa==31||aa==41||aa==51)    action_maybe(1)=-1;    action_maybe(4)=-1;   action_maybe(6)=-1;  end
    if(aa==20||aa==30||aa==40||aa==50||aa==60)    action_maybe(3)=-1;    action_maybe(5)=-1;   action_maybe(8)=-1;  end        
    r=rand();    %生成随机数
    if(r>e)       %大于e，则选择值函数最大的动作
        for i=1:1:8
            if(action_maybe(i)~=-1)
%                row=floor(action_maybe(i)/10);
%                clo=action_maybe(i)-row*10;
                if(qMatrix(aa,action_maybe(i))>=max)
                    max=qMatrix(aa,action_maybe(i));   max_num=i; end
            end           
        end
        action_sel=action_maybe(max_num);
    else          %小于e，则随机选取动作
        while(1)          
            rr=floor(rand(1)*8)+1;       %生成1-8的随机整数
            action_sel=action_maybe(rr);
            if (action_sel~=-1)   break;  end 
        end         
    end 
end

【运行结果】

循环2000次，即2000条采样路径。0表示走过的路径：

times steps和episodes的关系曲线。横轴为整个程序走过的累计步数，纵轴含义为走了那幺多步时，当前处于第几条采样路径上。