强化学习之Q-Learning

算法步骤

完整的算法步骤：

简单实例

假设一栋建筑里有5个房间，房间之间通过门相连，将房间从0至4进行编号，且建筑外围可以认为是一个很大的房间，编号为5，如下图所示。下面的房间可以通过一个图来表示，房间作为图的节点，两个房间若有门相连，则相应节点对应一条边。

首先将Agent置于建筑中的任意一个房间，然后从那个房间开始，让其走到建筑外。将编号为5的房间设置为目标，我们为每一扇门关联一个reward值，直接连到目标房间的门的reward值为100，其他门的reward值为0。注意，编号为5的房间有一个指向自己的箭头，其reward值为100，其他直接连接目标房间reward值也是100。Q-Learning的目标是达到reward值最大的state，因此，当Agent到达目标房间后，将永远停留在那里。

以状态为行，动作为列构建一个reward值的矩阵R，其中-1表示空值。
$$R=\left[\begin{array}{cccccc}-1& -1& -1& -1& 0& -1\\ -1& -1& -1& 0& -1& 100\\ -1& -1& -1& 0& -1& -1\\ -1& 0& 0& -1& 0& -1\\ 0& -1& -1& 0& -1& 100\\ -1& 0& -1& -1& 0& 100\end{array}\right]$$
构建一个矩阵Q，用来表示Agent已经从经验中学到的知识，矩阵Q与R同阶，其行表示状态，列表示动作。由于刚开始时，Agent对外界环境一无所知，因此矩阵Q应初始化零矩阵。在本例中状态数量是已知的，对于状态未知的情形，我们可以让Q从一个元素出发，每次发现一个新的状态时，就可以在Q中增加相应的行列。

算法转移规则： $Q(s,a)=R(s,a)+\gamma ma{x}_{a^{\prime }}Q(s^{\prime },a^{\prime })$

其中s，a表示当前的状态和动作，s’，a’表示下一个状态及行为，折扣系数 $0\leq\gamma \leq 1 $。

Q-Learning算法具体执行步骤：

首先令折扣系数 $\gamma=0.8 $，初始状态为房间2，并将Q初始化为全零矩阵。
$$Q=\left[\begin{array}{cccccc}0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0\end{array}\right]$$
观察矩阵R的第三行（对应房间2或状态2），它包含一个非负值，即当前状态1的下一步行为只有一个可能：转至状态3。更新Q(2,3). Q ( 2 , 3 ) = R ( 2 , 3 ) + 0.8 ∗ m a x { Q ( 3 , 1 ) , Q ( 3 , 2 ) , Q ( 3 , 4 ) } = 0 + 0.8 ∗ 0 = 0 Q(2,3)=R(2,3)+0.8*max\{Q(3,1),Q(3,2),Q(3,4)\}=0+0.8*0=0 Q(2,3)=R(2,3)+0.8∗max{Q(3,1),Q(3,2),Q(3,4)}=0+0.8∗0=0,更新Q，接着将从状态3继续开始，观察矩阵R的第四行（对应房间3或状态3），它包含三个非负值，即当前状态3的下一步行为有三个可能：随机转至状态4。更新Q(3,4)， Q ( 3 , 4 ) = R ( 3 , 4 ) + 0.8 ∗ m a x { Q ( 4 , 0 ) , Q ( 4 , 3 ) , Q ( 4 , 5 ) } = 0 + 0.8 ∗ 0 = 0 Q(3,4)=R(3,4)+0.8*max\{Q(4,0),Q(4,3),Q(4,5)\}=0+0.8*0=0 Q(3,4)=R(3,4)+0.8∗max{Q(4,0),Q(4,3),Q(4,5)}=0+0.8∗0=0,更新Q，接着将从状态4继续开始，观察矩阵R的第五行（对应房间4或状态4），它包含三个非负值，即当前状态3的下一步行为有三个可能：随机转至状态5。更新(4,5), Q ( 4 , 5 ) = R ( 4 , 5 ) + 0.8 ∗ m a x { Q ( 5 , 1 ) , Q ( 5 , 4 ) , Q ( 5 , 5 ) } = 100 + 0.8 ∗ 0 = 100 Q(4,5)=R(4,5)+0.8*max\{Q(5,1),Q(5,4),Q(5,5)\}=100+0.8*0=100 Q(4,5)=R(4,5)+0.8∗max{Q(5,1),Q(5,4),Q(5,5)}=100+0.8∗0=100，到达目标状态，一次episode完成，更新Q。
$$一次episode更新后的Q=\left[\begin{array}{cccccc}0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 100\\ 0& 0& 0& 0& 0& 0\end{array}\right]$$
执行更多次episode，矩阵Q最终收敛成
$$Q=\left[\begin{array}{cccccc}0& 0& 0& 0& 400& 0\\ 0& 0& 0& 320& 0& 500\\ 0& 0& 0& 320& 0& 0\\ 0& 400& 256& 0& 400& 0\\ 320& 0& 0& 320& 0& 500\\ 0& 400& 0& 0& 400& 500\end{array}\right]$$
对其进行规范化，每个非零元素都除以矩阵Q的最大元素
$$Q=\left[\begin{array}{cccccc}0& 0& 0& 0& 80& 0\\ 0& 0& 0& 64& 0& 100\\ 0& 0& 0& 64& 0& 0\\ 0& 80& 51& 0& 80& 0\\ 64& 0& 0& 64& 0& 100\\ 0& 80& 0& 0& 80& 100\end{array}\right]$$
一旦矩阵足够接近收敛状态，Agent便学习到了转移至目标状态的最佳路径。

代码实例

悬崖行走问题，S，G分别代表起始点和目标，图有48个格子，因而有48个状态。相应的对应每个状态有四种行为：上下左右。普通的行为会产生相应的上下左右移动。每次移动都获得-1的回报。但如果进入图中标记为悬崖的区域，会获得-100的回报，同时将状态重置为起始点S。现通过Q-Learning算法学习到一个从S到G的最优策略，也就是最佳路径。

MATLAB代码：

% 这个script将展示如何利用Q-Learning算法求解悬崖行走问题
% 初始化参数，通用参数
close all
clear
alpha = 1e-1  %学习步长
row = 4; col = 12   %网格大小
CF = ones(row, col); CF(row, 2:(col-1)) = 0 %网格中为0的地方表示悬崖
s_start = [4, 1]; %初始状态
s_end = [4, 12];    %目标
max_epoch = 500;  %最多学习多少轮，一个episode是一轮

% qlearn中的参数
gamma = 1;  %折扣系数
epsilon = .1;   %epsilon-greedy策略的概率阈值
nStates = row*col;  %所有的状态数
nActions = 4;   %每个状态的行为

Q = zeros(nStates, nActions);   %行为值函数矩阵，qlearn的更新目标
ret_epi = zeros(1, max_epoch);  %存储每一个episode的累积回报R
n_qlearn = zeros(nStates, nActions); %存储每个（s,a）访问的次数
steps_epi = zeros(1, max_epoch);    %存储每个episode中经历的步数，越小说明学习越快

% 进行每一轮循环
for ei = 1:max_epoch
    q_finish = 0; %标志一轮episode是否结束
    st = s_start;

    % 初始化状态，开始算法的step2
    % sub2ind函数把一个的索引转换成一个一维的索引值，这样每个网格坐标被映射成一个唯一的整数值
    st_index = sub2ind([row, col], s_start(1), s_start(2));

    % 选择一个行为，对应算法step2后半句
    [value, action] = max(Q(st_index, :))   %这里分别用1,2,3,4代表上下左右4个行为

    % 以epsilon的概率选择一个随机策略
    if( rand<epsilon )       
        tmp=randperm(nActions); action=tmp(1); %产生一个随机策略
    end
    
    % 开始一个episode，对应算法step3
    R = 0;
    while(1)
        %根据当前状态和行为，返回下一个(s',a')和回报， 算法s3-1
        [reward, next_state]  = transition(st, action, CF, s_start,s_end);
        R = R + reward;
        next_ind = sub2ind( [row, col], next_state(1), next_state(2));
        % 如果下一个状态不是终止态，则执行
        if (~q_finish)
            steps_epi(1, ei) = steps_epi(1, ei) +1;
            % 选择下一个状态的行为，算法s3-2
            [value, next_action] = max(Q(next_ind, :));
            if( rand<epsilon )         
                tmp=randperm(nActions); next_action=tmp(1); 
            end
            n_qlearn(st_index,action) = n_qlearn(st_index,action)+1; %状态的出现次数
            if( ~( (next_state(1)==s_end(1)) && (next_state(2)==s_end(2)) ) ) % 下一个状态不是终止态
                Q(st_index,action) = Q(st_index,action) + alpha*( reward + gamma*max(Q(next_ind,:)) - Q(st_index,action) ); %值函数更新
            else                                                  % 下一个状态是终止态
                Q(st_index,action) = Q(st_index,action) + alpha*( reward - Q(st_index,action) );
                q_finish=1;
            end
            % 更新状态，对应算法s3-4
            st = next_state; action = next_action; st_index = next_ind;
        end
        if (q_finish)
            break;
        end
    end     %结束一个episode的循环
    
    ret_epi(1,ei) = R;
          
end

% 获得策略
sideII=4; sideJJ=12;
% 初始化pol_pi_qlearn表示策略，V_sarsa是值函数，n_g_sarsa 是当前状态采取最优策略的次数
pol_pi_qlearn  = zeros(sideII,sideJJ); V_sarsa  = zeros(sideII,sideJJ); n_g_sarsa  = zeros(sideII,sideJJ); 
for ii=1:sideII
  for jj=1:sideJJ
    sti = sub2ind( [sideII,sideJJ], ii, jj ); 
    [V_sarsa(ii,jj),pol_pi_qlearn(ii,jj)] = max( Q(sti,:) ); 
    n_g_sarsa(ii,jj) = n_qlearn(sti,pol_pi_qlearn(ii,jj));
  end
end

% 绘图
plot_cw_policy(pol_pi_qlearn,CF,s_start,s_end);
title( 'Q学习算法策略' ); 
% fn = sprintf('cw_sarsa_policy_nE_%d',MAX_N_EPISODES); if( save_figs ) saveas( gcf, fn, 'png' ); end 

figure('Position', [100 100 400 200]); 
imagesc( V_sarsa ); colormap(flipud(jet)); colorbar; 
title( 'Q学习算法状态行为值' ); 
set(gca, 'Ytick', [1 2 3 4 ], 'Xtick', [1:12], 'FontSize', 9);
% fn = sprintf('cw_sarsa_state_value_fn_nE_%d',MAX_N_EPISODES); if( save_figs ) saveas( gcf, fn, 'png' ); end

figure('Position', [100 100 400 200]); 
imagesc( n_g_sarsa ); colorbar; 
title( 'Q学习:最优策略的步数' ); 
set(gca, 'Ytick', [1 2 3 4 ], 'Xtick', [1:12], 'FontSize', 9);

% 观察学习过程
figure('Position', [100 100 600 250]); 
subplot(121)
plot(1:max_epoch, ret_epi, 'b', 'LineWidth', 1);
title('每个episode的累积回报(Q学习)');
xlabel('episode');
ylabel('回报值');
set(gca, 'FontSize', 9);
axis( [-50 600 -2500 100]);
subplot(122)
plot(1:max_epoch, steps_epi, '-b', 'LineWidth', 1, 'Marker', 'o', 'MarkerSize', 2);
title('平均每个episode用的步数(Q学习)');
xlabel('episode');
ylabel('步数');
set(gca, 'FontSize', 9);
axis( [-50 600 -100 1000]);

transition.m

function [reward, next_state] = transition(st, act, CF, s_start, s_end)
% 函数用于计算当前转移到下一个状态，返回（s',a')和r
[row, col] = size(CF);
ii = st(1); jj = st(2);

switch act
    case 1
        %
        % action = UP
        %
        next_state = [ii-1,jj];
    case 2
        %
        % action = DOWN
        %
        next_state = [ii+1,jj];
    case 3
        %
        % action = RIGHT
        %
        next_state = [ii,jj+1];
    case 4
        %
        % action = LEFT
        %
        next_state = [ii,jj-1];
    otherwise
        error(sprintf('未定义的行为 = %d',act));
end

% 边界处理
if( next_state(1)<1      ) next_state(1)=1;      end
if( next_state(1)>row ) next_state(1)=row; end
if( next_state(2)<1      ) next_state(2)=1;      end
if( next_state(2)>col ) next_state(2)=col; end

% 回报计算

if( (ii==s_end(1)) && (jj==s_end(2)) )  % 结束
  reward = 0;
elseif( CF(next_state(1),next_state(2))==0 )        % 在悬崖区域
  reward  = -100;
  next_state = s_start;
else                                   
  reward = -1;
end
end

plot_cw_policy.m(画图函数)

function plot_cw_policy(pol_pi,CF,s_start,s_end)
[sideII,sideJJ]=size(pol_pi); 
IIdelims = 0:sideII; IIcents = 1:sideII;
JJdelims = 0:sideJJ; JJcents = 1:sideJJ;
% 画悬崖
figure('Position', [100 100 400 200]); 
imagesc( JJcents, IIcents, CF ); colorbar; hold on; 
set(gca, 'Ytick', [1 2 3 4 ], 'Xtick', [1:12], 'FontSize', 9);
% 画开始和结束点:
plot( s_start(2), s_start(1), '^', 'MarkerSize', 10, 'MarkerFaceColor', 'k' ); 
plot( s_end(2), s_end(1), 'o', 'MarkerSize', 10, 'MarkerFaceColor', 'k' ); 
axis normal

% fill the vectors:
px = zeros(size(pol_pi)); py = zeros(size(pol_pi)); 
for ii=1:sideII,
  for jj=1:sideJJ,
    switch pol_pi(ii,jj)
     case 1
      %
      % action = UP 
      %
      px(ii,jj) = 0;
      py(ii,jj) = 0.5; 
     case 2
      %
      % action = DOWN
      %
      px(ii,jj) = 0;
      py(ii,jj) = -0.5; 
     case 3
      %
      % action = RIGHT
      %
      px(ii,jj) = 0.5;
      py(ii,jj) = 0; 
     case 4
      %
      % action = LEFT 
      %
      px(ii,jj) = -0.5; 
      py(ii,jj) = 0; 
     case 5
      px(ii,jj) = -0.5; 
      py(ii,jj) = +0.5; 
     case 6
      px(ii,jj) = +0.5; 
      py(ii,jj) = +0.5; 
     case 7
      px(ii,jj) = +0.5; 
      py(ii,jj) = -0.5; 
     case 8
      px(ii,jj) = -0.5; 
      py(ii,jj) = -0.5; 
     otherwise
      error('unknown value of pol_pi(ii,jj)'); 
    end
  end
end

ind0 = find(CF(:)==0); px(ind0)=0; py(ind0)=0; px(sideII,sideJJ)=0; py(sideII,sideJJ)=0; 

%[jjM,iiM]=meshgrid(1:sideJJ,1:sideII);
[jjM,iiM]=meshgrid(JJcents,IIcents);

%quiver(iiM,jjM,px,py,0); 
quiver(jjM,iiM,px,-py,0, 'Color','r', 'LineWidth', 1.5);