SARSA（State-Action-Reward-State-Action）是强化学习领域经典的时序差分（Temporal Difference）在线策略控制算法。与Q-Learning的离线策略特性不同，SARSA使用实际执行的下一动作来更新Q值，使学习过程更保守、更符合在线交互场景的安全需求。本文用Java实现SARSA算法，结合ε-贪心探索策略，在网格世界环境中演示智能体的策略收敛过程。
核心原理
时序差分学习
TD学习结合了蒙特卡洛（基于完整回合）和动态规划（基于自举）的优点：
– 无需等待回合结束即可更新估计值
– 利用当前Q值估计作为部分目标，实现自举（bootstrapping）
– TD误差：δ = r + γ·Q(s’, a’) – Q(s, a)
SARSA更新规则
$$Q(s_t, a_t) \leftarrow Q(s_t, a_t) + \alpha \cdot [r_{t+1} + \gamma \cdot Q(s_{t+1}, a_{t+1}) – Q(s_t, a_t)]$$
与Q-Learning的区别在于：SARSA使用实际采取的a_{t+1}来估计回报，而Q-Learning使用max_a Q(s_{t+1}, a)。这使得SARSA：
– 属于在线策略（on-policy）：学习的是当前正在执行的策略
– 更保守：会避免学习那些依赖贪心选择但实际可能因探索而进入危险状态的策略
– 适合安全敏感场景（如悬崖行走问题）
ε-贪心探索
以ε概率随机选择动作（探索），以1-ε概率选择当前最优动作（利用）。随着学习进行，ε逐渐衰减，使策略从探索过渡到利用。
完整Java实现
import java.util.*;
/**
* SARSA算法Java实现
* 包含：Q表、ε-贪心策略、时序差分更新、网格世界环境
*/
public class SARSA {
// 学习参数
private final double alpha; // 学习率
private final double gamma; // 折扣因子
private double epsilon; // 探索率
private final double epsilonDecay; // 探索衰减
private final double epsilonMin; // 最小探索率
// Q表：状态 -> (动作 -> Q值)
private Map<String, double[]> qTable;
private List<String> actions;
private Random random;
public SARSA(List<String> actions, double alpha, double gamma,
double epsilon, double epsilonDecay, double epsilonMin) {
this.actions = actions;
this.alpha = alpha;
this.gamma = gamma;
this.epsilon = epsilon;
this.epsilonDecay = epsilonDecay;
this.epsilonMin = epsilonMin;
this.qTable = new HashMap<>();
this.random = new Random(42);
}
/**
* 选择动作：ε-贪心策略
*/
public String chooseAction(String state) {
double[] qValues = getQValues(state);
if (random.nextDouble() < epsilon) {
// 探索：随机选择
return actions.get(random.nextInt(actions.size()));
} else {
// 利用：选择Q值最大的动作
return actions.get(argmax(qValues));
}
}
/**
* SARSA核心更新：使用实际采取的下一个动作
*/
public void update(String state, String action, double reward,
String nextState, String nextAction) {
double[] qValues = getQValues(state);
double[] nextQValues = getQValues(nextState);
int actionIdx = actions.indexOf(action);
int nextActionIdx = actions.indexOf(nextAction);
// TD目标：r + γ * Q(s', a')
double tdTarget = reward + gamma * nextQValues[nextActionIdx];
double tdError = tdTarget - qValues[actionIdx];
// Q值更新
qValues[actionIdx] += alpha * tdError;
// 衰减探索率
epsilon = Math.max(epsilonMin, epsilon * epsilonDecay);
}
/**
* 获取状态的Q值数组（不存在则初始化）
*/
private double[] getQValues(String state) {
return qTable.computeIfAbsent(state, k -> new double[actions.size()]);
}
private int argmax(double[] arr) {
int maxIdx = 0;
for (int i = 1; i < arr.length; i++) {
if (arr[i] > arr[maxIdx]) maxIdx = i;
}
return maxIdx;
}
/**
* 获取当前最优策略
*/
public Map<String, String> getPolicy() {
Map<String, String> policy = new HashMap<>();
for (Map.Entry<String, double[]> entry : qTable.entrySet()) {
policy.put(entry.getKey(), actions.get(argmax(entry.getValue())));
}
return policy;
}
/**
* 获取当前epsilon值
*/
public double getEpsilon() {
return epsilon;
}
// ============ 网格世界环境 ============
/**
* 网格世界：智能体从起点导航到终点，避开陷阱
*/
static class GridWorld {
private final int rows, cols;
private final int startRow, startCol;
private final int goalRow, goalCol;
private final Set<String> cliffs; // 悬崖/陷阱位置
private final Set<String> obstacles; // 障碍物
private int agentRow, agentCol;
private int stepCount;
private double totalReward;
public GridWorld(int rows, int cols, int startRow, int startCol,
int goalRow, int goalCol, Set<String> cliffs,
Set<String> obstacles) {
this.rows = rows;
this.cols = cols;
this.startRow = startRow;
this.startCol = startCol;
this.goalRow = goalRow;
this.goalCol = goalCol;
this.cliffs = cliffs;
this.obstacles = obstacles;
reset();
}
public void reset() {
this.agentRow = startRow;
this.agentCol = startCol;
this.stepCount = 0;
this.totalReward = 0;
}
/**
* 执行动作，返回(奖励, 是否终止, 下一状态)
*/
public StepResult step(String action) {
stepCount++;
int newRow = agentRow;
int newCol = agentCol;
switch (action) {
case "UP": newRow--; break;
case "DOWN": newRow++; break;
case "LEFT": newCol--; break;
case "RIGHT": newCol++; break;
}
// 边界检查
if (newRow < 0 || newRow >= rows || newCol < 0 || newCol >= cols) {
newRow = agentRow;
newCol = agentCol;
}
// 障碍物检查
String newPos = newRow + "," + newCol;
if (obstacles.contains(newPos)) {
newRow = agentRow;
newCol = agentCol;
}
agentRow = newRow;
agentCol = newCol;
String state = getState();
// 计算奖励
double reward;
boolean done = false;
if (agentRow == goalRow && agentCol == goalCol) {
reward = 10.0; // 到达目标
done = true;
} else if (cliffs.contains(state)) {
reward = -100.0; // 掉入悬崖
done = true;
} else {
reward = -1.0; // 每步代价
}
totalReward += reward;
return new StepResult(reward, done, state);
}
public String getState() {
return agentRow + "," + agentCol;
}
public boolean isGoal() {
return agentRow == goalRow && agentCol == goalCol;
}
/**
* 渲染当前环境状态
*/
public void render() {
System.out.println("Step: " + stepCount + ", Total Reward: " + String.format("%.1f", totalReward));
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
String pos = r + "," + c;
if (r == agentRow && c == agentCol) {
System.out.print(" A ");
} else if (r == goalRow && c == goalCol) {
System.out.print(" G ");
} else if (cliffs.contains(pos)) {
System.out.print(" C ");
} else if (obstacles.contains(pos)) {
System.out.print(" # ");
} else {
System.out.print(" . ");
}
}
System.out.println();
}
System.out.println();
}
/**
* 渲染最优策略
*/
public void renderPolicy(Map<String, String> policy) {
System.out.println("Learned Policy:");
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
String pos = r + "," + c;
if (r == goalRow && c == goalCol) {
System.out.print(" G ");
} else if (cliffs.contains(pos)) {
System.out.print(" C ");
} else if (obstacles.contains(pos)) {
System.out.print(" # ");
} else {
String action = policy.getOrDefault(pos, "?");
String symbol = switch (action) {
case "UP" -> " ^ ";
case "DOWN" -> " v ";
case "LEFT" -> " < ";
case "RIGHT" -> " > ";
default -> " ? ";
};
System.out.print(symbol);
}
}
System.out.println();
}
}
}
static class StepResult {
double reward;
boolean done;
String state;
StepResult(double reward, boolean done, String state) {
this.reward = reward;
this.done = done;
this.state = state;
}
}
/**
* 训练：运行多个回合，收集经验并更新Q值
*/
public static List<Double> train(SARSA agent, GridWorld env, int episodes) {
List<Double> episodeRewards = new ArrayList<>();
List<String> actionList = agent.actions;
for (int ep = 0; ep < episodes; ep++) {
env.reset();
String state = env.getState();
String action = agent.chooseAction(state);
double episodeReward = 0;
boolean done = false;
int steps = 0;
int maxSteps = 500;
while (!done && steps < maxSteps) {
steps++;
// 执行动作
StepResult result = env.step(action);
String nextState = result.state;
double reward = result.reward;
done = result.done;
episodeReward += reward;
// 选择下一动作（SARSA关键：使用实际执行的下一动作）
String nextAction = agent.chooseAction(nextState);
// SARSA更新
agent.update(state, action, reward, nextState, nextAction);
state = nextState;
action = nextAction;
}
episodeRewards.add(episodeReward);
if ((ep + 1) % 500 == 0) {
double avgReward = episodeRewards.subList(ep - 499, ep + 1)
.stream().mapToDouble(Double::doubleValue).average().orElse(0);
System.out.printf("Episode %d: Avg Reward(last 500) = %.2f, Epsilon = %.3f%n",
ep + 1, avgReward, agent.getEpsilon());
}
}
return episodeRewards;
}
/**
* 使用学习到的策略运行一个回合（无探索）
*/
public static double runEpisode(SARSA agent, GridWorld env, boolean render) {
env.reset();
String state = env.getState();
double totalReward = 0;
boolean done = false;
int steps = 0;
int maxSteps = 100;
if (render) env.render();
while (!done && steps < maxSteps) {
steps++;
// 纯利用：选择最优动作
double[] qValues = agent.getQValues(state);
String action = agent.actions.get(argmax(qValues));
StepResult result = env.step(action);
totalReward += result.reward;
done = result.done;
state = result.state;
if (render) env.render();
}
return totalReward;
}
private static int argmax(double[] arr) {
int maxIdx = 0;
for (int i = 1; i < arr.length; i++) {
if (arr[i] > arr[maxIdx]) maxIdx = i;
}
return maxIdx;
}
/**
* 主函数：在悬崖行走环境中训练SARSA
*/
public static void main(String[] args) {
// 构建悬崖行走环境（4x12网格）
// S:起点(3,0), G:终点(3,11), C:悬崖(3,1到3,10)
int rows = 4, cols = 12;
int startRow = 3, startCol = 0;
int goalRow = 3, goalCol = 11;
Set<String> cliffs = new HashSet<>();
for (int c = 1; c <= 10; c++) {
cliffs.add("3," + c);
}
Set<String> obstacles = new HashSet<>();
GridWorld env = new GridWorld(rows, cols, startRow, startCol,
goalRow, goalCol, cliffs, obstacles);
// 动作空间
List<String> actions = Arrays.asList("UP", "DOWN", "LEFT", "RIGHT");
// 创建SARSA智能体
SARSA agent = new SARSA(actions, 0.1, 0.99, 1.0, 0.995, 0.01);
System.out.println("=== SARSA悬崖行走问题 ===");
System.out.println("环境: 4x12网格, S=起点(3,0), G=终点(3,11), C=悬崖");
System.out.println("参数: alpha=0.1, gamma=0.99, epsilon从1.0衰减到0.01");
System.out.println();
// 训练
System.out.println("--- 开始训练 ---");
int episodes = 5000;
List<Double> rewards = train(agent, env, episodes);
// 统计训练结果
System.out.println("\n--- 训练统计 ---");
double first100Avg = rewards.subList(0, 100).stream()
.mapToDouble(Double::doubleValue).average().orElse(0);
double last100Avg = rewards.subList(episodes - 100, episodes).stream()
.mapToDouble(Double::doubleValue).average().orElse(0);
System.out.printf("前100回合平均奖励: %.2f%n", first100Avg);
System.out.printf("后100回合平均奖励: %.2f%n", last100Avg);
System.out.printf("最终Epsilon: %.4f%n", agent.getEpsilon());
// 可视化学习到的策略
System.out.println("\n--- 学习到的策略 ---");
Map<String, String> policy = agent.getPolicy();
env.renderPolicy(policy);
// 使用最优策略运行演示
System.out.println("\n--- 最优策略演示 ---");
double evalReward = runEpisode(agent, env, true);
System.out.printf("演示回合总奖励: %.1f%n", evalReward);
// 对比：展示SARSA的保守特性
System.out.println("\n--- SARSA vs Q-Learning 特性对比 ---");
System.out.println("SARSA（在线策略）特点：");
System.out.println(" - 学习过程中考虑探索行为的影响");
System.out.println(" - 在悬崖问题中会学得离悬崖较远的安全路径");
System.out.println(" - 收敛到次优但安全的策略");
System.out.println("Q-Learning（离线策略）特点：");
System.out.println(" - 只考虑最优动作的回报");
System.out.println(" - 可能学到紧贴悬崖的最短路径");
System.out.println(" - 收敛到最优但可能危险的路径");
// Q值热力图展示
System.out.println("\n--- Q值热力图 (每个状态的最优Q值) ---");
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
String pos = r + "," + c;
double[] qVals = agent.qTable.getOrDefault(pos, new double[4]);
double maxQ = Arrays.stream(qVals).max().orElse(0);
System.out.printf(" %6.1f", maxQ);
}
System.out.println();
}
}
}
关键设计解析
SARSA与Q-Learning的本质差异
两者更新公式的唯一区别在于TD目标的选择：
– SARSA: r + γ·Q(s’, a’)，其中a’是实际执行的动作
– Q-Learning: r + γ·max_a Q(s’, a)，其中max不依赖实际执行
这一差异导致SARSA在ε-贪心探索下会”自我实现预言”：如果高Q值路径旁边有悬崖，SARSA会考虑到探索时可能意外掉下去的风险，从而选择绕远的安全路径。Q-Learning则无视探索风险，始终追求理论最优。
ε衰减策略
采用指数衰减ε ← max(ε_min, ε · decay)而非线性衰减。指数衰减在训练初期快速降低探索率（利用已有知识），后期缓慢趋近最小值（保持微小探索防止局部最优）。decay=0.995配合5000回合训练，使ε从1.0逐步降至约0.01。
悬崖行走问题的教育价值
这是Sutton&Barto教材中的经典对比场景。4×12网格中，起点和终点都在悬崖同一侧，最短路径紧贴悬崖（1步之遥）。SARSA学会绕远路保持安全距离，Q-Learning学会冒险走最短路径。这一对比深刻揭示了在线/离线策略的本质区别。
复杂度分析
| 组件 | 时间复杂度 | 空间复杂度 |
|---|---|---|
| 动作选择 | O(|A|) | O(1) |
| Q值更新 | O(|A|) | O(1) |
| 每回合学习 | O(T·|A|) | O(|S|·|A|) |
| 总体训练 | O(E·T·|A|) | O(|S|·|A|) |
其中E为回合数，T为每回合最大步数，|S|为状态空间大小，|A|为动作空间大小。
扩展方向
- Expected SARSA：用动作概率加权期望替代单个a’的Q值，降低方差。
- n-step SARSA：使用n步回报而非单步TD目标，平衡偏差与方差。
- SARSA(λ)：引入资格迹（eligibility traces），实现多步自举与信用分配。
- 函数逼近：用神经网络替代Q表，处理连续状态空间。
- 双重SARSA：解耦动作选择与评估，减少最大化偏差。
