每日算法 — 使用java实现Q-learning：时序差分与ε-贪心探索策略

引言

在人工智能领域，强化学习是一类让智能体通过与环境交互来学习最优决策策略的重要方法。Q-learning作为最经典的免模型强化学习算法之一，由Watkins于1989年提出，它不需要预先知道环境的转移概率，仅通过与环境的试错交互就能学习到最优策略。本文将用Java实现一个完整的Q-learning框架，以一个迷宫寻宝游戏为载体，深入讲解时序差分更新、ε-贪心探索策略以及Q表的收敛过程。

算法原理

Q-learning核心思想

Q-learning的核心是维护一张Q表（Q-table），记录在每个状态下执行每个动作的预期累积奖励。状态-动作值函数Q(s,a)表示在状态s下执行动作a后，遵循最优策略所能获得的期望 discounted reward 总和。

Q-learning的更新公式为：

$$Q(s,a) \leftarrow Q(s,a) + \alpha \cdot [r + \gamma \cdot \max_{a’} Q(s’,a’) – Q(s,a)]$$

其中：
– α（学习率）控制新信息覆盖旧信息的程度
– γ（折扣因子）衡量未来奖励的权重
– r 是即时奖励
– s’ 是执行动作a后的下一个状态
– max_{a’} Q(s’,a’) 是下一状态的最大Q值

ε-贪心探索策略

为了避免陷入局部最优，Q-learning采用ε-贪心策略：以概率ε随机选择动作（探索），以概率1-ε选择当前Q值最大的动作（利用）。随着训练进行，ε通常逐渐衰减。

Java实现

import java.util.*;

/**
 * Q-learning算法实现 - 迷宫寻宝智能体
 * 
 * 智能体在迷宫中学习找到宝藏的最短路径
 */
public class QLearningMaze {

    // 迷宫大小
    private static final int ROWS = 5;
    private static final int COLS = 5;

    // 动作定义：上、右、下、左
    private static final int[] DROW = {-1, 0, 1, 0};
    private static final int[] DCOL = {0, 1, 0, -1};
    private static final String[] ACTION_NAMES = {"上", "右", "下", "左"};

    // 超参数
    private double alpha = 0.1;      // 学习率
    private double gamma = 0.9;      // 折扣因子
    private double epsilon = 0.3;    // 探索率
    private double epsilonDecay = 0.995; // ε衰减率
    private double minEpsilon = 0.01;    // 最小探索率

    // Q表：状态 -> 各动作的Q值
    private double[][] qTable;

    // 迷宫环境
    private int[][] maze;
    private static final int EMPTY = 0;
    private static final int WALL = 1;
    private static final int START = 2;
    private static final int TREASURE = 3;
    private static final int TRAP = 4;

    // 起始位置和宝藏位置
    private int startRow, startCol;
    private int treasureRow, treasureCol;

    public QLearningMaze() {
        initMaze();
        // 状态数 = ROWS * COLS, 动作数 = 4
        qTable = new double[ROWS * COLS][4];
    }

    /**
     * 初始化迷宫环境
     * 0=空地, 1=墙, 2=起点, 3=宝藏, 4=陷阱
     */
    private void initMaze() {
        maze = new int[][] {
            {2, 0, 0, 1, 0},
            {0, 1, 0, 1, 0},
            {0, 0, 0, 0, 0},
            {1, 0, 1, 4, 0},
            {0, 0, 0, 0, 3}
        };

        // 查找起点和宝藏位置
        for (int i = 0; i < ROWS; i++) {
            for (int j = 0; j < COLS; j++) {
                if (maze[i][j] == START) {
                    startRow = i; startCol = j;
                } else if (maze[i][j] == TREASURE) {
                    treasureRow = i; treasureCol = j;
                }
            }
        }
    }

    /**
     * 将二维坐标转换为一维状态编号
     */
    private int stateOf(int row, int col) {
        return row * COLS + col;
    }

    /**
     * 执行动作，返回(新状态, 即时奖励, 是否终止)
     */
    private Result step(int state, int action) {
        int row = state / COLS;
        int col = state % COLS;

        int newRow = row + DROW[action];
        int newCol = col + DCOL[action];

        // 检查边界和墙壁
        if (newRow < 0 || newRow >= ROWS || newCol < 0 || newCol >= COLS 
                || maze[newRow][newCol] == WALL) {
            // 撞墙，保持原地，给予惩罚
            return new Result(state, -1.0, false);
        }

        int newState = stateOf(newRow, newCol);

        // 到达宝藏
        if (maze[newRow][newCol] == TREASURE) {
            return new Result(newState, 100.0, true);
        }

        // 落入陷阱
        if (maze[newRow][newCol] == TRAP) {
            return new Result(newState, -50.0, true);
        }

        // 普通移动，给予小的负奖励以鼓励快速到达目标
        return new Result(newState, -0.1, false);
    }

    /**
     * ε-贪心策略选择动作
     */
    private int chooseAction(int state) {
        Random rand = new Random();
        if (rand.nextDouble() < epsilon) {
            // 探索：随机选择
            return rand.nextInt(4);
        } else {
            // 利用：选择Q值最大的动作
            return argMax(qTable[state]);
        }
    }

    /**
     * 返回数组中最大值的索引
     */
    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;
    }

    /**
     * 单轮训练（一个episode）
     */
    private void trainEpisode() {
        int state = stateOf(startRow, startCol);
        boolean done = false;
        int steps = 0;
        double totalReward = 0;

        while (!done && steps < 100) {
            int action = chooseAction(state);
            Result result = step(state, action);

            // Q-learning更新公式
            double oldQ = qTable[state][action];
            double nextMaxQ = max(qTable[result.newState]);
            double newQ = oldQ + alpha * (result.reward + gamma * nextMaxQ - oldQ);
            qTable[state][action] = newQ;

            state = result.newState;
            done = result.done;
            totalReward += result.reward;
            steps++;
        }

        // 衰减探索率
        epsilon = Math.max(minEpsilon, epsilon * epsilonDecay);
    }

    /**
     * 训练指定轮数
     */
    public void train(int episodes) {
        System.out.println("开始训练 Q-learning 智能体...");
        for (int i = 0; i < episodes; i++) {
            trainEpisode();
            if ((i + 1) % 500 == 0) {
                System.out.printf("Episode %d, ε=%.4f%n", i + 1, epsilon);
            }
        }
        System.out.println("训练完成！");
    }

    /**
     * 使用学习到的策略执行（无探索）
     */
    public void demo() {
        System.out.println("\n=== 智能体演示 ===");
        int state = stateOf(startRow, startCol);
        boolean done = false;
        int steps = 0;

        printMazeWithAgent(state);

        while (!done && steps < 20) {
            int action = argMax(qTable[state]); // 纯利用
            Result result = step(state, action);

            int row = state / COLS;
            int col = state % COLS;
            System.out.printf("步骤 %d: 在(%d,%d)选择[%s], 奖励=%.1f%n", 
                steps + 1, row, col, ACTION_NAMES[action], result.reward);

            state = result.newState;
            done = result.done;
            steps++;

            printMazeWithAgent(state);
        }

        int finalRow = state / COLS;
        int finalCol = state % COLS;
        if (maze[finalRow][finalCol] == TREASURE) {
            System.out.println("🎉 智能体成功找到宝藏！");
        } else if (maze[finalRow][finalCol] == TRAP) {
            System.out.println("💀 智能体落入陷阱！");
        }
    }

    /**
     * 打印带智能体位置的迷宫
     */
    private void printMazeWithAgent(int agentState) {
        int agentRow = agentState / COLS;
        int agentCol = agentState % COLS;

        for (int i = 0; i < ROWS; i++) {
            for (int j = 0; j < COLS; j++) {
                if (i == agentRow && j == agentCol) {
                    System.out.print(" 🤖 ");
                } else {
                    switch (maze[i][j]) {
                        case EMPTY: System.out.print(" .  "); break;
                        case WALL: System.out.print(" ██ "); break;
                        case START: System.out.print(" S  "); break;
                        case TREASURE: System.out.print(" 💎 "); break;
                        case TRAP: System.out.print(" 💀 "); break;
                    }
                }
            }
            System.out.println();
        }
        System.out.println();
    }

    /**
     * 打印Q表
     */
    public void printQTable() {
        System.out.println("\n=== 最终Q表（部分）===");
        for (int s = 0; s < ROWS * COLS; s++) {
            int row = s / COLS;
            int col = s % COLS;
            if (maze[row][col] != WALL) {
                System.out.printf("状态(%d,%d): ", row, col);
                for (int a = 0; a < 4; a++) {
                    System.out.printf("%s=%.2f ", ACTION_NAMES[a], qTable[s][a]);
                }
                System.out.println();
            }
        }
    }

    private double max(double[] arr) {
        double max = arr[0];
        for (double v : arr) {
            if (v > max) max = v;
        }
        return max;
    }

    // 结果类
    private static class Result {
        int newState;
        double reward;
        boolean done;

        Result(int newState, double reward, boolean done) {
            this.newState = newState;
            this.reward = reward;
            this.done = done;
        }
    }

    public static void main(String[] args) {
        QLearningMaze agent = new QLearningMaze();
        agent.train(5000);  // 训练5000轮
        agent.printQTable();
        agent.demo();
    }
}

代码解析

环境建模

代码将迷宫建模为一个5×5的网格世界，每个格子代表一个状态。智能体可以执行四个基本动作（上下左右），遇到墙壁会保持原地并受到惩罚。

Q表结构

Q表是一个二维数组 qTable[状态数][动作数]，其中状态通过 row * COLS + col 编码为一维整数。这种紧凑的表示方式便于快速查找和更新。

训练循环

每个episode从起点开始，智能体根据ε-贪心策略选择动作，执行后获得奖励并更新Q值。训练过程中ε逐渐衰减，使智能体从探索转向利用。

收敛判断

Q-learning的收敛依赖于以下因素：
– 所有状态-动作对被无限次访问（通过ε-贪心保证）
– 学习率α逐渐减小
– 奖励函数设计合理

复杂度分析

对于大规模状态空间，可使用深度Q网络（DQN）替代Q表，但Q-learning作为入门算法，其简洁性和可解释性使其成为理解强化学习的最佳起点。

扩展与改进

1. SARSA：将Q-learning的off-policy改为on-policy，用实际执行的动作而非最大Q值更新
2. Double Q-learning：维护两个Q表减少过估计
3. Dueling DQN：将Q值分解为状态价值和优势函数
4. 优先级经验回放：对重要转移样本赋予更高采样概率

总结

本文通过Java实现了完整的Q-learning算法，以一个迷宫寻宝游戏展示了强化学习的核心思想。Q-learning的时序差分更新机制使智能体能够在不依赖环境模型的情况下，仅通过试错学习最优策略。ε-贪心探索策略则平衡了探索未知和利用已知之间的矛盾，是强化学习中最重要的权衡之一。