SARSA算法严格上来说，是TD(0)关于状态动作函数估计的on-policy形式，所以其基本架构与TD的$v_{\pi}$估计算法（on-policy）并无太大区别，所以这里就不再单独阐述之。

强化学习中的统计方法（包括Monte Carlo，TD）在实现episode task时，无不例外存在着两层最基本的循环结构。如果我们将每一个episode task看作是一局游戏，那么这个游戏有开始也有结束，统计方法是就是一局接着一局不停的在玩，然后从中总结出最优策略。Monte Carlo与TD的区别在于，Monte Carlo是玩完一局，总结一次，而TD算法是边玩边总结。所以这两层基本结构的外层是以游戏次数为循环，内层则是以游戏过程为循环。

SARSA作为TD算法下的on-policy control算法，只需边进行游戏边更新动作值函数和Policy即可，所以SARSA算法的内层可以由TD算法细化为如下结构：

Windy Grid World

在Markov方法里，曾介绍过Grid World问题，以及使用DP方法求解的过程，具体可以参考：Dynamic programming in Python ，然而如果面对更为复杂的Windy Grid World环境，则Markov方法就很难适用了。在Windy Grid World里，Agent的每一步移动都会受到风的影响，比如正常移动情况下，坐标(1, 1)向右动作会移动到坐标(1, 2)，但如若受到由下向上的风影响，则可能移动到坐标(2, 3)。在Windy Grid World中，风速场虽然可以是固定不变的，但却是未知的，对于存在影响状态转换的未知因素的模型是很难构建的，所以这里我们使用统计方法中的SARSA算法在求解最优策略。

先给出环境设定（四周都是围墙，也就是说不可能被风吹出环境之外，实际程序设计中可以使用“异常检测”与设定可能跳出地图之外的格子风速场为0来实现围墙）：

给出解决该问题的SRASA算法的代码结构（Matlab）

NumOfGames = 500
while(index < NumOfGames)
    [Q, Policy] = PlayGame(Q, Policy);
end                            

function [Q, Policy] = PlayGame(Q, Policy)
while(1)
    % Begin Game
    while(1)
        Action = ChooseAction(Policy(State));
        NextState = State + Action + windy(State);
        try
            Grid(NextState) % Check for exception
        catch
            break;
        end     
        NextAction = ChooseAction(Policy(NextState));
        Q(State, Action) = Q(State, Action) + alpha*(R + gamma*Q(NextState, NextAction)...
            - Q(State, Action));
        Policy = UpdatePolicy(Policy);
        State = NextState;
        if(State == Target)
            return;
        end    
    end
end

给出Windy Grid World的最优Policy（箭头指向为处于每个格子中的最优选择，格子(4, 1)为Start，(4, 8)为Goal，红线表示最优路线15步）；