项目
09/04/2018

2018 年 8 月

第 33 卷，第 8 期

测试运行 - 使用 C# 执行 Q-Learning 入门

James McCaffrey 强化学习 (RL) 是解决了问题的机器学习的分支，其中没有显式的定型数据已知正确输出值。问：学习是一种算法，可用于解决某些类型的 RL 问题。在本文中，我解释 Q 学习的工作原理，并提供一个示例程序。

请参阅本文所述观点的最佳方法是看看在简单的迷宫图 1和中的关联的演示程序图 2。3 x 4 迷宫有 12 个单元格，从 0 到 11 编号。目标是从单元格中 8 在左下角中，转到单元格 11 在右下角中的最少的移动。您可以向左、右、向上或向下，但不是沿对角线方向。

图 1 简单迷宫难题

问：学习演示程序
图 2 Q 学习演示程序

演示程序将设置在内存中迷宫的表示形式，然后使用 Q 学习算法查找 Q 矩阵。问：质量，代表较大的值是更好。行索引是"发件人"单元格和列索引是"收件人"单元格。如果起始单元格是 8，然后扫描该行显示的最大的 Q 值是在向单元格 9 0.44。然后从单元格中 9，行中的最大值将为 1.08 到单元格中 5。继续此过程直至程序到达单元格 11 上的目标状态。

它很可能不需要编写代码解决了迷宫，但这是因为问题是容易掌握 Hello World Q 学习。我将解释如何 Q 学习可以通用化到更高版本在这篇文章中更真实问题。

本文假定您具有中级或更高的编程技能，但并不假定您完全了解 Q 学习。演示程序使用 C# 进行编码，但您应能够将代码重构为其他语言，如 Visual Basic 或 Python 太多麻烦。演示程序的代码显示无法在本文中，还可随附的文件下载。

代码展示

对我来说，至少 Q 学习是有些奇怪，因为我认为通过检查特定的演示代码而不是通过启动与一般原则，最好理解概念。图 3 显示了演示程序的整体结构（为节省空间进行了一些较小的修改）。

图 3 Q 学习演示程序结构

using System;
using System.Collections.Generic;
namespace QLearning
{
  class QLearningProgram
  {
    static Random rnd = new Random(1);
    static void Main(string[] args)
    {
      Console.WriteLine("Begin Q-learning maze demo");
      Console.WriteLine("Setting up maze and rewards");
      int ns = 12;
      int[][] FT = CreateMaze(ns);
      double[][] R = CreateReward(ns);
      double[][] Q = CreateQuality(ns);
      Console.WriteLine("Analyzing maze using Q-learning");
      int goal = 11;
      double gamma = 0.5;
      double learnRate = 0.5;
      int maxEpochs = 1000;
      Train(FT, R, Q, goal, gamma, learnRate, maxEpochs);
      Console.WriteLine("Done. Q matrix: ");
      Print(Q);
      Console.WriteLine("Using Q to walk from cell 8 to 11");
      Walk(8, 11, Q);
      Console.WriteLine("End demo");
      Console.ReadLine();
    }
    static void Print(double[][] Q) { . . }
    static int[][] CreateMaze(int ns) { . . }
    static double[][] CreateReward(int ns) { . . }
    static double[][] CreateQuality(int ns) { . . }
    static List<int> GetPossNextStates(int s,
      int[][] FT) { . . }
    static int GetRandNextState(int s, int[][] FT) { . . }
    static void Train(int[][] FT, double[][] R, double[][] Q,
      int goal, double gamma, double lrnRate,
      int maxEpochs) { . . }
    static void Walk(int start, int goal, double[][] Q) { . . }
    static int ArgMax(double[] vector) { . . }
  } // Program
} // ns

为了创建演示程序，我启动了 Visual Studio 并创建了一个新 C# 控制台应用程序项目名为 QLearning。我使用 Visual Studio 2017，但演示程序并不重要的.NET 依赖，因此任何版本的 Visual Studio 可以正常工作。在模板代码加载到之后我删除了所有的编辑器不需要的 using 语句，只留下对引用 System 命名空间。然后我添加到 Collections.Generic 命名空间的引用，因为该演示使用列表 < int > 集合。

该演示程序类作用域的 Random 对象由于 Q 学习涉及一个随机选择组件，如稍后您将看到。变量 ns 代表的状态，数等同于在迷宫中的单元格的数目。对象 FT （可行转换）是一个数组的数组样式矩阵。矩阵 R reward 矩阵，矩阵 Q 质量矩阵。

问：学习算法需要参数 gamma （也称为折扣身份）和 learnRate。我将介绍这些更高版本。Q 学习是迭代的因此此演示程序设置了 maxEpochs 变量来控制该算法可用于查找 Q 矩阵的多长时间。

设置在迷宫和奖励

创建迷宫方法 CreateMaze，定义如下：

static int[][] CreateMaze(int ns) {
  int[][] FT = new int[ns][];
  for (int i = 0; i < ns; ++i) FT[i] = new int[ns];
  FT[0][1] = FT[0][4] = FT[1][0] = FT[1][5] = FT[2][3] = 1;
  FT[2][6] = FT[3][2] = FT[3][7] = FT[4][0] = FT[4][8] = 1;
  FT[5][1] = FT[5][6] = FT[5][9] = FT[6][2] = FT[6][5] = 1;
  FT[6][7] = FT[7][3] = FT[7][6] = FT[7][11] = FT[8][4] = 1;
  FT[8][9] = FT[9][5] = FT[9][8] = FT[9][10] = FT[10][9] = 1;
  FT[11][11] = 1;  // Goal
  return FT;
}

该方法返回一个矩阵，用于定义允许移动。例如，您可以从移动单元格 4 到单元格 8，但您不能移动从单元格中 4 到单元格 5 因为没有墙的方式。前面曾提到，C# 将初始化为 0，整数数组以便 CreateMaze 需要指定仅允许移动。请注意，您不能移动从单元格到其自身，但目标单元格 11 除外。

由定义 reward 矩阵：

static double[][] CreateReward(int ns) {
  double[][] R = new double[ns][];
  for (int i = 0; i < ns; ++i) R[i] = new double[ns];
  R[0][1] = R[0][4] = R[1][0] = R[1][5] = R[2][3] = -0.1;
  R[2][6] = R[3][2] = R[3][7] = R[4][0] = R[4][8] = -0.1;
  R[5][1] = R[5][6] = R[5][9] = R[6][2] = R[6][5] = -0.1;
  R[6][7] = R[7][3] = R[7][6] = R[7][11] = R[8][4] = -0.1;
  R[8][9] = R[9][5] = R[9][8] = R[9][10] = R[10][9] = -0.1;
  R[7][11] = 10.0;  // Goal
  return R;
}

在此示例中，将迁移到目标单元格 11 时出现的 10.0，回报，但其他移动提供-0.1 负奖励。这些值是任意的。一般情况下，在使用 RL，奖励结构是完全取决于问题。在这里，小的负 reward 将遇到每次移动一点，其效果与目标通过较长的路径优先使用较短的路径。请注意，无需设置的不能使用，因为它们将永远不会发生移动奖励。

问：学习的目标是查找 Q 矩阵的值。最初，所有的 Q 值设置为介于 0.0 和创建 Q 矩阵如下所示：

static double[][] CreateQuality(int ns) {
  double[][] Q = new double[ns][];
  for (int i = 0; i < ns; ++i)
    Q[i] = new double[ns];
  return Q;
}

定义可能的下一步状态

稍后将看到，Q 学习算法将需要知道哪些状态系统可以过渡到，根据当前状态。在此示例中，系统的状态是在迷宫中的位置相同因此仅有 12 的状态。定义方法 GetPossNextStates 如下所示：

static List<int> GetPossNextStates(int s, int[][] FT) {
  List<int> result = new List<int>();
  for (int j = 0; j < FT.Length; ++j)
    if (FT[s][j] == 1) result.Add(j);
  return result;
}

例如，如果当前状态 s，5 GetPossNextStates 返回列表 < int > 集合保存（1、 6、 9）。问：学习算法有时将进入从当前状态随机的下一个状态。该功能由 GetRandNextState 方法定义：

static int GetRandNextState(int s, int[][] FT) {
  List<int> possNextStates = GetPossNextStates(s, FT);
  int ct = possNextStates.Count;
  int idx = rnd.Next(0, ct);
  return possNextStates[idx];
}

因此，如果 s 的当前状态为 5，则 GetRandNextState 返回 1 或 6 或 9 的均匀分布 (0.33)。

问：学习算法

问：学习的密钥更新公式根据数学 Bellman 公式和底部的图 1 所示。方法 Train 中实现的算法。在高级伪代码中，Q 学习算法是：

loop maxEpochs times
  set currState = a random state
  while currState != goalState
    pick a random next-state but don't move yet
    find largest Q for all next-next-states
    update Q[currState][nextState] using Bellman
    move to nextState
  end-while
end-loop

该算法根本不是显而易见的并对我来说，它最清楚地了解检查代码。定义开始：

static void Train(int[][] FT, double[][] R, double[][] Q,
  int goal, double gamma, double lrnRate, int maxEpochs)
{
  for (int epoch = 0; epoch < maxEpochs; ++epoch) {
    int currState = rnd.Next(0, R.Length);
...

必须通过反复试验来确定培训时期数。备用设计是循环访问 Q 矩阵中的值未更改，直到或趋于稳定到少量更改每个迭代。内部循环迭代，直到当前的状态将变为目标状态，在演示迷宫的情况下的单元格 11:

while (true) {
  int nextState = GetRandNextState(currState, FT);
  List<int> possNextNextStates = GetPossNextStates(nextState, FT);
  double maxQ = double.MinValue;
  for (int j = 0; j < possNextNextStates.Count; ++j) {
    int nns = possNextNextStates[j];  // short alias
    double q = Q[nextState][nns];
    if (q > maxQ) maxQ = q;
  }
...

假设您在迷宫。您看到可以转到三个不同的房间，A、 B、 c。选取 B，但尚无移动。请求一个朋友的进入聊天室 B，友元告诉您，从房间 B 可以转到聊天室 X、 Y、 Z 和的这些聊天室 Y 具有最佳的 Q 值。换而言之，Y 是最佳的下一步的下一步状态。

执行到 Q 矩阵更新：

...
      Q[currState][nextState] =
        ((1 - lrnRate) * Q[currState][nextState]) +
        (lrnRate * (R[currState][nextState] + (gamma * maxQ)));
      currState = nextState;
      if (currState == goal) break;
    } // while
  } // for
} // Train

更新公式分为两部分。第一部分中，((1-lrnRate) * Q[currState][nextState])，称为攻击组件并将添加的旧值的一小部分。第二部分 (lrnRate * (R [currState] [nextState] + (gamma * maxQ)))，称为资源管理器组件。LrnRate 增加当前奖励和未来奖励的影响较大的值（浏览）但要牺牲过去奖励（攻击）。Gamma，折扣因子的值会影响将来的奖励的重要性。

使用问答矩阵

质量后矩阵计算所得，它可以用于查找到的目标状态的最佳路径从任意起始状态。方法遍历实现了此功能：

static void Walk(int start, int goal, double[][] Q) {
  int curr = start;  int next;
  Console.Write(curr + "->");
  while (curr != goal) {
    next = ArgMax(Q[curr]);
    Console.Write(next + "->");
    curr = next;
  }
  Console.WriteLine("done");
}

请注意，该方法假定从起始状态，目标状态是可访问。该方法使用 helper ArgMax 来查找最佳的下一个状态：

static int ArgMax(double[] vector) {
  double maxVal = vector[0];  int idx = 0;
  for (int i = 0; i < vector.Length; ++i) {
    if (vector[i] > maxVal) {
      maxVal = vector[i];  idx = i;
    }
  }
  return idx;
}

例如，如果一个向量，具有值（0.5，0.3，0.7，0.2） ArgMax 返回 2。此演示程序定义了 Print 方法，以显示 Q 矩阵。可以在随附的文件下载中获取优质打印版本。简化的版本为：

static void Print(double[][] Q) {
  int ns = Q.Length;
  Console.WriteLine("[0] [1] . . [11]");
  for (int i = 0; i < ns; ++i) {
    for (int j = 0; j < ns; ++j) {
      Console.Write(Q[i][j].ToString("F2") + " ");
    }
    Console.WriteLine();
  }
}

总结

此处介绍的问题与解答学习示例应为您充分了解所涉及的主要原则。本文中介绍的问题方案是一个具有离散状态，但问题与解答学习可以过使用连续状态。常规的挑战就是最大程度提高长期的回报，这对于迷宫示例等同于进入中移动的最小数量的目标状态。您可以安全地进行训练具有许多试用版，如培训如何来执行某项任务的工业机器人的系统时，问题与解答学习非常有用。但问题与解答学习不适用于方案，如定型无人驾驶汽车如何导航交通。问：学习和 RL 提醒我有些神经网络在 20 世纪 80 年代中 — 有相对较少的实际应用程序，但有密集的研究工作。我的同事的许多人都认为，在某些点 RL 将分解为实用性意想不到的方式。

Dr.James McCaffrey 供职于华盛顿地区雷蒙德市沃什湾的 Microsoft Research。他参与过多个 Microsoft 产品的工作，包括 Internet Explorer 和必应。Scripto可通过 jamccaff@microsoft.com 与 McCaffrey 取得联系。

衷心感谢以下 Microsoft 技术专家对本文的审阅：Asli Celikyilmaz、 Chris Lee、 Ricky Loynd、 Amr Sharaf、 Ken Tran

在 MSDN 杂志论坛讨论这篇文章