ML：SARSA 的基本原理与实现

在强化学习中智能体Agent并不是一次性从已有标签中学习答案而是在环境Environment中不断尝试动作、观察结果、获得奖励并根据经验逐步调整行为策略。在 Q 学习中智能体可以通过不断更新动作价值函数 Q(s, a)学习“在某个状态下采取某个动作到底有多好”。不过Q 学习有一个重要特点它在更新时假设下一步会选择最优动作因此更偏向“理想最优策略”的学习。SARSA 则采用另一种思路它不仅观察当前状态和动作也把智能体下一步实际选择的动作纳入更新过程。因此SARSA 是一种典型的同策略On-Policy时序差分控制方法。简单地说SARSA 学习的是在当前策略实际执行的行为方式下各状态—动作对具有怎样的长期价值。一、从强化学习最小闭环理解 SARSA强化学习Reinforcement Learning的基本问题可以概括为智能体在环境中不断选择动作并根据环境反馈改进自己的行为方式。一个最小交互闭环通常包括• 状态State智能体当前看到的环境情况• 动作Action智能体可以执行的行为• 奖励Reward环境对动作结果给出的反馈• 策略Policy智能体选择动作的规则• 价值Value对长期收益的估计图 1强化学习中的智能体—环境交互闭环在每一步交互中智能体通常经历如下过程• 观察当前状态 s• 根据策略选择动作 a• 执行动作后环境返回奖励 r• 环境转移到下一个状态 s′• 智能体继续选择下一步动作 a′• 根据这次经验更新 Q(s, a)图 2SARSA 的五元更新链条SARSA 的名字正来自这个更新过程中的五个元素其中• S 表示当前状态 s• A 表示当前动作 a• R 表示执行动作后得到的奖励 r• S′ 表示下一个状态 s′• A′ 表示在 s′ 下实际选择的下一个动作 a′因此SARSA 不是只看“下一状态中理论上最好的动作”而是看“下一状态中当前策略实际会选的动作”。二、SARSA 的基本思想SARSA 的核心思想是用当前经验逐步更新动作价值函数 Q(s, a)使智能体越来越清楚在不同状态下采取不同动作的长期价值。Q(s, a) 的含义是在状态 s 下采取动作 a并在之后继续按照当前策略行动最终能够获得的长期累计奖励估计。与监督学习不同SARSA 没有现成的标准答案。它依靠的是智能体在环境中的真实交互经验。一次 SARSA 更新包含以下过程• 当前处于状态 s• 根据当前策略选择动作 a• 执行动作 a得到奖励 r• 到达下一个状态 s′• 在 s′ 下继续根据当前策略选择动作 a′• 用 r 和 Q(s′, a′) 更新 Q(s, a)也就是说SARSA 的学习不是脱离策略单独估计最优动作而是在当前策略的实际行为轨迹上进行学习。这也是 SARSA 被称为同策略On-Policy方法的原因。三、动作价值函数 Q(s, a)在 SARSA 中最重要的对象是动作价值函数 Q(s, a)。它回答的问题是如果智能体在状态 s 下采取动作 a并且之后继续按照当前策略行动那么从现在开始大约能得到多少长期回报图 3动作价值函数 Q(s, a) 的含义例如在一个网格世界中• s 可以表示智能体当前所在格子• a 可以表示向上、向下、向左、向右• Q(s, a) 表示在该格子采取某个方向行动的长期价值如果某个动作经常带来较高奖励或者能更快到达目标那么它的 Q 值通常会逐渐升高。如果某个动作经常导致惩罚或者让智能体走入危险区域那么它的 Q 值通常会逐渐降低。因此SARSA 的训练过程本质上就是不断修正 Q 表使它越来越接近当前策略下的真实长期收益。四、SARSA 的更新公式图 4SARSA 的更新公式与时序差分误差SARSA 的核心更新公式为其中• Q(s, a) 表示当前状态 s 下采取动作 a 的旧价值估计• Q(s′, a′) 表示下一个状态 s′ 下实际选择动作 a′ 的价值估计• r 表示当前动作得到的即时奖励• α 表示学习率控制新经验对旧估计的影响程度• γ 表示折扣因子控制未来奖励的重要程度• r γQ(s′, a′) 表示这次经验给出的目标估计• r γQ(s′, a′) − Q(s, a) 表示时序差分误差其中时序差分误差Temporal Difference ErrorTD Error可以单独写成其中• δ 表示当前估计与新目标之间的差距• δ 0说明当前 Q(s, a) 估计偏低需要调大• δ 0说明当前 Q(s, a) 估计偏高需要调小• δ 0说明当前估计与新经验基本一致因此SARSA 更新可以理解为新估计 旧估计 学习率 × 估计误差这与很多机器学习算法中的“沿误差方向逐步修正参数”的思想是一致的。五、SARSA 为什么是同策略方法SARSA 最关键的特点是它更新 Q(s, a) 时使用的是下一步实际选择的动作 a′。也就是说a′ 不是单纯从 Q(s′, ·) 中选出的最大值动作而是由当前策略实际产生的动作。图 5SARSA 为什么是同策略方法如果当前策略是 ε-greedy 策略那么在 s′ 下• 大多数时候选择当前 Q 值最大的动作• 少数时候随机探索其他动作因此a′ 可能是当前最优动作也可能是探索动作。SARSA 会把这种真实探索行为也考虑进价值更新中。换句话说SARSA 学到的是“在当前带有探索行为的策略下动作的实际长期价值”。这就是同策略On-Policy的含义• 行为策略智能体实际用来选择动作的策略• 评估策略算法正在学习和评估的策略• 在 SARSA 中二者是同一个策略因此SARSA 更关注“智能体实际怎么走”而不是“理论上下一步最好怎么走”。六、SARSA 与 Q 学习的区别SARSA 和 Q 学习都属于基于动作价值函数的时序差分控制方法但二者在更新目标上有关键差异。SARSA 的更新目标是其中a′ 是下一状态 s′ 下按照当前策略实际选择的动作。Q 学习的更新目标是其中max 表示直接选取下一状态 s′ 下最大的动作价值。二者的区别可以这样理解• SARSA下一步实际会怎么走就按这个动作更新• Q 学习下一步理论上最优怎么走就按最优动作更新因此SARSA 是同策略方法Q 学习是离策略Off-Policy方法。这种差异会影响学习行为。在存在风险区域的任务中SARSA 往往会更加谨慎。因为它会把探索动作可能带来的风险也纳入价值估计。Q 学习则更倾向于学习一条最优路径即使实际探索时可能因为偶然动作而掉入危险区域。图 6SARSA 与 Q 学习的更新差异可以概括为• SARSA 更贴近当前策略的真实表现• Q 学习更接近理想贪心策略下的最优估计• SARSA 在带探索的任务中可能更保守• Q 学习在理想收敛条件下更直接逼近最优动作价值七、ε-greedy 策略探索与利用的平衡SARSA 通常需要配合 ε-greedy 策略使用。因为在强化学习中智能体不能一开始就只选择当前看起来最好的动作否则可能错过更好的选择。图 7ε-greedy 策略与探索-利用平衡ε-greedy 策略的思想是• 以 1 − ε 的概率选择当前 Q 值最大的动作• 以 ε 的概率随机选择一个动作可以写成随机动作以概率以概率其中• ε 表示探索概率• ε 越大智能体越倾向于随机探索• ε 越小智能体越倾向于利用当前已知的较优动作• argmax 表示选择使 Q(s, a) 最大的动作在训练初期较大的 ε 有助于探索更多可能路径在训练后期较小的 ε 有助于稳定利用已经学到的经验。因此ε-greedy 策略体现的是强化学习中的一个基本矛盾探索Exploration与利用Exploitation的平衡。八、SARSA 的算法流程SARSA 的训练流程可以概括如下。图 8SARSA 的训练流程1、初始化 Q 表对于每个状态 s 和动作 a初始化 Q(s, a)。常见做法是全部初始化为 0。2、开始一个 episode将智能体放入初始状态 s。3、根据策略选择动作 a使用 ε-greedy 策略从当前状态 s 中选择动作 a。4、执行动作并观察反馈执行动作 a得到奖励 r 和下一个状态 s′。5、在下一个状态继续选择动作 a′在 s′ 下继续使用 ε-greedy 策略选择下一步动作 a′。6、更新 Q(s, a)使用 SARSA 更新公式修正 Q(s, a)。7、推进状态与动作令 s ← s′a ← a′继续下一步。8、直到 episode 结束如果到达终止状态则结束本轮训练并开始下一轮 episode。可以用伪代码表示为初始化 Q(s, a) 对每一轮 episode 初始化状态 s 根据当前策略从 s 选择动作 a 当 s 不是终止状态 执行动作 a得到 r 和 s 根据当前策略从 s 选择动作 a Q(s, a) ← Q(s, a) α [r γQ(s,a) - Q(s, a)] s ← s a ← a这个流程中最关键的一点是每一步更新之前SARSA 都要先在 s′ 下选出实际的下一动作 a′。九、Python 实现用简单网格世界演示 SARSA下面用一个不依赖复杂强化学习库的简化网格世界演示 SARSA 的基本实现。任务设定如下• 网格大小为 4 × 4• 起点为左上角 (0, 0)• 终点为右下角 (3, 3)• 每走一步奖励为 -1• 到达终点奖励为 10并结束 episode• 动作包括上、下、左、右图 94x4 网格世界示意图这个任务的目标是让智能体尽量用更少步数到达终点。import randomimport numpy as np # # 1. 环境设置# grid_size 4start_state (0, 0)goal_state (3, 3) actions [up, down, left, right]n_actions len(actions) # Q 表键是状态值是该状态下每个动作的 Q 值Q {} for row in range(grid_size): for col in range(grid_size): Q[(row, col)] np.zeros(n_actions) def step(state, action): 执行动作返回下一状态、奖励、是否结束 row, col state if action up: row max(row - 1, 0) elif action down: row min(row 1, grid_size - 1) elif action left: col max(col - 1, 0) elif action right: col min(col 1, grid_size - 1) next_state (row, col) if next_state goal_state: return next_state, 10, True return next_state, -1, False # # 2. ε-greedy 策略# def choose_action(state, epsilon): 根据 ε-greedy 策略选择动作 if random.random() epsilon: return random.randrange(n_actions) return int(np.argmax(Q[state])) # # 3. SARSA 训练# alpha 0.1 # 学习率gamma 0.9 # 折扣因子epsilon 0.1 # 探索概率episodes 500 for episode in range(episodes): state start_state action choose_action(state, epsilon) done False while not done: action_name actions[action] next_state, reward, done step(state, action_name) next_action choose_action(next_state, epsilon) # SARSA 更新 Q[state][action] Q[state][action] alpha * ( reward gamma * Q[next_state][next_action] - Q[state][action] ) state next_state action next_action # # 4. 查看学习到的策略# arrow { up: ↑, down: ↓, left: ←, right: →} print(学习到的策略) for row in range(grid_size): line [] for col in range(grid_size): state (row, col) if state goal_state: line.append(G) else: best_action np.argmax(Q[state]) line.append(arrow[actions[best_action]]) print( .join(line))这段代码体现了 SARSA 的基本流程• 使用 Q 表保存每个状态—动作对的价值• 使用 ε-greedy 策略选择动作• 每执行一步后观察 r 和 s′• 在 s′ 下继续选择实际动作 a′• 使用 Q(s′, a′) 更新 Q(s, a)• 反复训练后得到一个趋向目标的策略其中最关键的代码是Q[state][action] Q[state][action] alpha * ( reward gamma * Q[next_state][next_action] - Q[state][action])它正对应 SARSA 的更新公式其中• state 对应 s• action 对应 a• reward 对应 r• next_state 对应 s′• next_action 对应 a′• Q[next_state][next_action] 对应 Q(s′, a′)这也说明SARSA 的更新确实依赖下一步实际选择的动作而不是直接取下一状态中的最大 Q 值。十、Python 实现对比 SARSA 与 Q 学习的更新差异为了更清楚地看出 SARSA 与 Q 学习的区别可以只比较二者的核心更新语句。SARSA 更新Q[state][action] Q[state][action] alpha * ( reward gamma * Q[next_state][next_action] - Q[state][action])Q 学习更新Q[state][action] Q[state][action] alpha * ( reward gamma * np.max(Q[next_state]) - Q[state][action])二者差异只在目标值部分。SARSA 使用其中a′ 是当前策略在 s′ 下实际选出的动作。Q 学习使用其中max 表示直接选择 s′ 下价值最大的动作。因此• SARSA 的更新受实际探索行为影响• Q 学习的更新更偏向下一状态的最优动作• SARSA 学到的是当前策略下的动作价值• Q 学习更接近学习最优贪心策略下的动作价值在包含危险区域、探索代价或路径风险的环境中这种差异会非常明显。十一、SARSA 的适用场景与主要局限图 10SARSA 的适用场景、优势与主要局限1、适用场景SARSA 较适合以下情况• 环境可以通过状态、动作、奖励来描述• 智能体需要通过交互逐步学习策略• 探索动作本身可能带来风险• 希望学习的是当前行为策略下的实际表现• 任务规模较小可以用 Q 表表示状态—动作价值典型示例包括• 网格世界路径学习• 简单游戏智能体• 有风险区域的导航任务• 教学用强化学习实验• 小规模离散状态控制问题2、主要优势SARSA 的主要优势包括• 原理清晰便于理解时序差分学习• 不需要环境转移概率模型• 可以边交互边学习• 能把探索行为带来的风险纳入估计• 更适合解释同策略学习思想与蒙特卡洛方法相比SARSA 不需要等到一整轮 episode 结束后再更新而是可以每走一步就更新一次。与 Q 学习相比SARSA 更贴近智能体实际执行的策略。3、主要局限SARSA 也有明显局限• 需要大量交互经验• 对 α、γ、ε 等超参数比较敏感• 在状态空间很大时Q 表会变得难以维护• 只能直接处理离散状态和离散动作问题• 收敛速度可能较慢• 学到的结果受当前探索策略影响较大如果状态空间很大或者状态是连续变量就不能简单使用表格形式保存 Q(s, a)。这时通常需要使用函数近似方法例如用神经网络近似动作价值函数。4、与其他强化学习方法的关系SARSA 可以放在强化学习方法谱系中理解• 蒙特卡洛方法等一整轮结束后根据完整回报更新价值• SARSA每走一步就用实际下一动作更新 Q(s, a)• Q 学习每走一步就用下一状态的最大 Q 值更新 Q(s, a)• Deep SARSA用神经网络近似 Q(s, a)• DQN用深度神经网络近似 Q 学习中的动作价值函数因此SARSA 是连接基础时序差分学习与更复杂强化学习算法的重要方法。它既能帮助理解时序差分 TD 更新也能帮助理解同策略与离策略之间的核心区别。 小结SARSA 是一种同策略时序差分控制方法。它通过 S → A → R → S′ → A′ 的交互序列更新 Q(s, a)学习当前策略下各状态—动作对的长期价值。与 Q 学习相比SARSA 使用下一步实际选择的动作进行更新因此更能反映探索策略下的真实行为表现是理解强化学习控制方法的重要入口。“点赞有美意赞赏是鼓励”