《机器学习》笔记（第六部分：规则学习、强化学习）

15 规则学习

15.1 基本概念

  规则学习 (rule learning) 是基于数理逻辑的学习. 一条规则 (rule) 形如

$$\oplus \gets \mathrm f_1 \land \cdots \land \mathrm f_L$$

蕴含号右侧部分称为规则体 (body), 它是逻辑文字 (literal) 的合取式 (conjunction), $L$ 称为规则的长度; 左侧部分的规则头 (head) $\oplus$ 是该规则的结果, 一般用来表示判定目标. 这样的规则也被称为 if-then 规则. 假定从数据集学得规则集合 $\mathcal R$:

$$\mathcal R = \left\{ \oplus ^{(k)} \gets \bigwedge _{i=1}^{n^{(k)}} \mathrm f_i^{(k)} \right\}_{k=1}^n$$

规则 $k$ 的长度为 $n^{(k)}$. 符合改规则的样本称为被该规则覆盖 (cover). 有时规则覆盖不满全样本空间, 此时可以添加一条默认规则 (default rule), 例如无覆盖样本判定为 $\oplus _0$.

命题规则和一阶规则 规则分为命题规则和一阶规则

• 命题规则 (propositional rule) 由原子命题 (propositional atom) 和逻辑连接词 $\land$、$\lor$、$\lnot$、$\gets$ 构成的简单陈述句;
• 一阶规则 (first-order rule) 由原子公式 (atomic formula) 包括形如 $\forall x$、$\exists x$ 的量词 (quantifier) 和形如 $f(x)$ 谓词 (predicate) 构成的规则.

冲突消解与元规则 有时样本空间局部被规则头不同的多条规则覆盖, 会发生冲突 (conflict), 要考虑冲突消解 (conflict resolution). 常用的冲突消解策略包括

• 投票法 使用规则头的众数;
• 排序法 规则集合中定义一个顺序, 称为带序规则 (ordered rule) 或优先级规则 (priority rule);
• 元规则法 设置一些元规则 (meta-rule), 例如发生冲突时使用长度最小的规则.

15.2 序贯覆盖

  与决策树相似, 规则学习的原子命题 $\mathrm f$ 经常有“属性是否为某个取值”即 $x_1 = a$ 的形式. 序贯覆盖 (sequential covering) 即逐条归纳, 是一种分治 (separate-and-conquer) 策略. 以二分类问题的命题规则为例:

• 基于样本集 $D$ 生成一条规则 $(+1) \gets \mathrm f_1 \land \cdots \land \mathrm f_L$, 使得符合该规则的子集 $D'$ 全为正例. 该规则可以枚举属性取值产生 (但是计算开销极大), 也可以:
  • 自顶而下 (top-down) 从空规则开始, 每次添加正例率最高的新规则, 直到全为正例为止. 亦称生成-测试 (generate-then-test) 法, 是规则逐渐特化 (specialization) 的过程;
  • 自底而上 (bottom-up) 从任取一个正例样本所有属性取值的规则开始, 逐渐删除新规则但保证仍全为正例. 亦称数据驱动 (data-driven) 法, 是规则逐渐泛化 (generalization) 的过程.
• 将已归类为正例的子集从样本集剔除, 即 $D \gets D \setminus D'$.

集束搜索 在添加新规则时, 同时考虑正例率最高的 $b$ 条 $\mathrm f_1$, 下一步筛选正确率最高的 $b$ 条合取规则 $\mathrm f_1 \land \mathrm f_2$ 并以此类推. 这样可以缓解局部最优的问题. 该方法称为集束搜索 (beam search).

15.3 剪枝优化

  规划生成非常容易过拟合, 所以要考虑剪枝 (pruning).

预剪枝 即下一个规则生成后, 若反而降低预测精度, 则停止搜索. CN2 算法考虑了一个似然比统计量

$$\varLambda = 2m \left( \hat p_+ \mathop{\mathrm{lb}} \frac{\hat p_+}{p_+} + \hat p_- \mathop{\mathrm{lb}} \frac{\hat p_-}{p_-} \right)$$

其中 $m$ 是样本量, $p_+, p_-$ 是样本正反例率, $\hat p_+, \hat p_-$ 是预测正反例率. $\varLambda$ 刻画了规则学习模型比朴素模型 (即胡乱猜测) 好多少, 通常设置在 $\varLambda$ 很大 (例如 $0.99$) 时停止规则集生长.

后剪枝 即生成完整个规则集后再依据预测误差删除一些叶节点. 减错剪枝 (REP, Reduced Error Pruning) 删除叶结点时每一轮穷举可能的剪枝操作, 包括删除规则中某个文字、删除结尾若干文字、删除整条规则等, 它的算法复杂度是 $\mathcal O(m^4)$. IREP (Incremental REP) 尝试在每条规则生成前都进行一次 REP, 它的算法复杂度是 $\mathcal O(m \log ^2 m)$. IREP* 是一种改良的 IREP, 它以 $\hat p_+ + p_- - \hat p_-$ 取代准确率作为性能度量指标.

  RIPPER 算法是一种良好的规则学习算法, 它将预剪枝与后剪枝结合. 考虑指定深度 $k$ 的规则树时, RIPPER 算法在生成时对每一层做以下后剪枝:

• 基于当前规则 $\mathrm r$ 覆盖的样例用 IREP* 生成一条替换规则 (replacement rule) $\mathrm r'$;
• 对当前规则 $\mathrm r$ 增加文字进行特化, 再用 IREP* 剪枝生成一条修订规则 (revised rule).

然后将 $\mathcal R$、$\mathcal R' = \mathcal R \setminus \mathrm r \cup \mathrm r'$ 以及 $\mathcal R'' = \mathcal R \setminus \mathrm r \cup \mathrm r''$ 比较, 选择性能最好的规则集保留. RIPPER 算法进一步缓解了贪心策略陷入局部最优的情况, 所以是良好的规则学习算法.

15.4 一阶规则学习

  一阶规则学习希望学习出类似这样的规则: 对于两个样本 $\boldsymbol x', \boldsymbol x''$, 若 $x'_1 > x''_1$ 且 $x'_2 > x''_2$, 则 $\boldsymbol x'$ 优于 $\boldsymbol x''$. 考虑谓词逻辑的语言, 令 $f_0(\boldsymbol x', \boldsymbol x'')$ 表示“$\boldsymbol x'$ 优于 $\boldsymbol x''$”, $f_1(\boldsymbol x', \boldsymbol x'')$ 表示“$x'_1 > x''_1$”, $f_2$ 同理, 则希望学习到的规则为

$$(\forall \boldsymbol x')(\forall \boldsymbol x''), \ f_0(\boldsymbol x', \boldsymbol x'') \gets f_1(\boldsymbol x', \boldsymbol x'') \land f_2(\boldsymbol x', \boldsymbol x'')$$

  FOIL (First-Order Inductive Learner) 是著名的一阶规则学习算法, 它的学习过程与序贯覆盖自顶而下相同, 但是每条规则的搜索空间取遍所有可能的原子公式, 例如

$$x'_1 > x''_1, \qquad x'_1 < x''_1, \qquad x'_1 \neq x''_1, \qquad x'_1 > x''_2, \qquad \dots$$

FOIL 使用 FOIL 增益 (FOIL gain) 来选择文字

$$\mathrm{FOILGain} = m \hat p_+ \mathop{\mathrm{lb}} \frac{\hat p_+}{\hat p_-}$$

FOIL 增益只考虑正例的信息量, 这是因为一阶规则中通常正例数远少于反例数.

15.5 归纳逻辑程序设计 ILP

  归纳逻辑程序设计 (ILP, Inductive Logic Programming) 在一阶规则学习中引入了函数 $f(\boldsymbol x)$ 和类似 $f_1(f_2(\boldsymbol x))$ 逻辑表达式嵌套.

15.5.1 最小一般泛化 LGG

  ILP 使用自底而上的规则生成策略. ILP 直接将具体事实 (grounded fact) 作为初始规则, 例如

$$\boldsymbol x^{(1)} = (1, 0, 1)^T, \quad \boldsymbol x^{(2)} = (0, 1, 0)^T, \quad \boldsymbol x^{(3)} = (1, 1, 0)^T$$

若已知 $\boldsymbol x^{(1)}$ 优于 $\boldsymbol x^{(2)}$ 优于 $\boldsymbol x^{(3)}$, 利用相同的 $f_0, f_1, f_2$ 定义, 定义 $f_3$ 同理, 则初始规则可以是

$$f_0(\boldsymbol x^{(1)}, \boldsymbol x^{(2)}) \gets f_1(\boldsymbol x^{(1)}, \boldsymbol x^{(2)}) \land f_2(\boldsymbol x^{(2)}, \boldsymbol x^{(1)}) \land f_3(\boldsymbol x^{(1)}, \boldsymbol x^{(2)})$$

以及

$$f_0(\boldsymbol x^{(1)}, \boldsymbol x^{(3)}) \gets f_2(\boldsymbol x^{(3)}, \boldsymbol x^{(1)}) \land f_3(\boldsymbol x^{(1)}, \boldsymbol x^{(3)})$$

这两条规则只对应单对样本, 难以泛化. 为解决这个问题, 考虑最小一般泛化 (LGG, Least General Generalization). 举例来说, LGG 一次性将两条关于三个变元的规则取交集后合并为一条. 例如上面两条规则都包含 $\boldsymbol x^{(1)}$, 所以将 $\boldsymbol x^{(2)}$ 和 $\boldsymbol x^{(3)}$ 换成任意变元 $\boldsymbol x$ 然后取交集, 合并为

$$f_0(\boldsymbol x^{(1)}, \boldsymbol x) \gets f_2(\boldsymbol x, \boldsymbol x^{(1)}) \land f_3(\boldsymbol x^{(1)}, \boldsymbol x)$$

但是它还包含一个常量 $\boldsymbol x^{(1)}$. 假若我们又有一条规则

$$f_0(\boldsymbol x^{(2)}, \boldsymbol x^{(4)}) \gets f_1(\boldsymbol x^{(4)}, \boldsymbol x^{(2)}) \land f_2(\boldsymbol x^{(4)}, \boldsymbol x^{(2)}) \land f_3(\boldsymbol x^{(2)}, \boldsymbol x^{(4)})$$

上面两条规则, 一个包含任意变元 $\boldsymbol x$, 一个包含常量 $\boldsymbol x^{(4)}$. 所以将 $\boldsymbol x^{(4)}$ 换成一致的任意变元 $\boldsymbol x$, 将 $\boldsymbol x^{(1)}$ 和 $\boldsymbol x^{(2)}$ 换成另一个任意变元 $\boldsymbol x'$ 然后取交集, 合并为

$$f_0(\boldsymbol x', \boldsymbol x) \gets f_2(\boldsymbol x, \boldsymbol x') \land f_3(\boldsymbol x', \boldsymbol x)$$

这样就将三条初始规则合并为了一条不含常量的规则. 两条公式的 LGG 是它们仅泛化一步的结果, 所以 LGG 是最小泛化.

15.5.2 命题逻辑的逆归结

  在逻辑学中, 演绎 (deduction) 是从一般规律探讨具体事物, 归纳 (induction) 是从具体事物总结一般规律.

归结 假定有原子命题 $A, B, L$, 与他们相关的表达式

$$C_1 = A \lor L = \top, \qquad C_2 = B \lor \lnot L = \top$$

析取可以得到

$$C := C_1 \lor C_2 = A \lor B \lor (L \lor \lnot L) = A \lor B = \top$$

即 $C = A \lor B$. 该过程可以表述为

$$C = (C_1 - \{L\}) \lor (X_2 - \{\not L\})$$

逆归结 相反, 已知 $C$ 和 $C_1$ 可以还原出 $C_2$

$$C_2 = (C - (C_1 - \{L\})) \lor \{\lnot L\}$$

  逆归结尝试分拆析取式 $A \lor B$ 或合取式 $A \land B$. 令 $A, B, C$ 表示合取式, $p, q, r$ 表示原子公式, 逆归结有四种基本操作:

• 吸收 (absorption)

$$(p \gets A \land B, \ q \gets A) \implies (p \gets q \land B, \ q \gets A)$$

• 辨识 (identification)

$$(p \gets A \land B, \ p \gets A \land q) \implies (q \gets B, \ p \gets A \land q)$$

• 内构 (intra-construction)

$$(p \gets A \land B, \ p \gets A \land C) \implies (q \gets B, \ p \gets A \land q, \ q \gets C)$$

• 外构 (inter-construction)

$$(p \gets A \land B, \ q \gets A \land C) \implies (p \gets r \land B, \ r \gets A, \ q \gets r \land C)$$

15.5.3 一阶逻辑的逆归结

  一阶逻辑的归结和逆归结需要引入合一置换操作. 为简化表述, 在本节中使用 $X, Y$ 等代替变量 $\boldsymbol x, \boldsymbol x''$ 等, 用 $1, 2$ 等代替常量 $\boldsymbol x^{(1)}, \boldsymbol x^{(2)}$ 等.

置换 可以用置换 (substitution) 操作将常数代入表达式中的变量. 例如有一个逻辑表达式 $C$ 和一个置换 $\theta$, 则可以进行置换操作

$$C = \mathrm f_1(X, Y) \land \mathrm f_2(X, Y), \quad \theta = \{1/X, 2/Y\} \quad \implies \quad C \theta = \mathrm f_1(1, 2) \land \mathrm f_2(1, 2)$$

置换操作可以定义复合, 例如 $\{Y/X\} \circ \{Y/1\} = \{1/X\}$ 表示将 $X$ 替换为 $Y$, 然后将 $Y$ 替换为 $1$, 注意这里复合符号 $\circ$ 需要从左到右理解; 也可以定义逆, 例如 $\{X/Y\}^{-1} = \{Y/X\}$.

合一 可以用合一 (unification) 操作将两个逻辑表达式整合为同一个. 例如

$$A = \mathrm f(1, X), \quad B = \mathrm f(Y, 2), \quad \theta = \{2/X, 1/Y\} \implies A \theta = B \theta = \mathrm f(1, 2)$$

此时称 $A, B$ 是可合一的 (unifiable), $\theta$ 是 $A, B$ 的合一化子 (unifier). 一组逻辑表达式集中最小的那一个合一化子称为它们的最一般合一化子 (MGU, most general unifier).

  利用 MGU 可以逆归结出给定一阶规则集的泛化版本. 与命题规则不同, 一阶规则的 MGU 可能还可以发明出规则集以外的新规则. 一阶规则学习可以通过归结商 (resolution quotient) 定义, 此处省略.

16 强化学习

16.1 任务与奖赏

  强化学习任务由一个 Markov 决策过程 (MDP, Markov Decision Process) 描述. 设状态集为 $X$, 行动集为 $A$. 设位于状态 $x$ 时, 若使用行动 $a$, 则有概率 $P(x, a, x')$ 会移动到状态 $x'$, 且移动的奖励是 $R(x, a, x')$. 强化学习希望习得一个策略 $\boldsymbol \pi(x, a) \in [0, 1]$, 表示在状态 $x$ 下选择行动 $a$ 的概率.

累积奖赏 假设在该策略下, 第 $t$ 步取得的奖赏是随机变量 $r_t$, 则定义 $T$-步累积奖赏为 $\sum _{t=1}^T \mathrm E r_t / T$ 和 $\gamma$-折扣累积奖赏 $\mathrm E \sum _{t=0}^\infty \gamma ^t r_{t+1}$. 它们可以作为强化学习的优化目标.

16.2 $k$-老虎机

  考虑单步强化学习任务. 考虑一台 $k$-老虎机, 它有 $k$ 个摇臂, 第 $k$ 个摇臂突出的奖金服从分布 $X_k$. 赌徒允许尝试 $n$ 次老虎机. 赌徒的策略有两种:

• 仅探索 (exploration-only), 每一次以均等概率尝试每个摇臂. 如此可以估计出所有摇臂的奖金分布.
• 仅利用 (exploitation-only), 每一次按下目前为止的平均奖励最高的摇臂. 这样可以尝试最大化总奖励.

赌徒必须在这两种策略之间达成某种折中, 例如前 $n/2$ 次采用仅探索、后 $n/2$ 次采用仅利用. 这是因为探索和利用是一对矛盾, 称为探索-利用窘境 (Exploration-Exploitation dilemma).

$\varepsilon$-贪心法 指定一个概率 $\varepsilon \in [0, 1]$, 每次尝试时以 $\varepsilon$ 概率探索、以 $1 - \varepsilon$ 概率利用. 通常令 $\varepsilon$ 取一个很小的数, 例如 $1/10$ 或 $1/100$. 也可以令 $\varepsilon (t)$ 随着尝试次数减小, 例如 $\varepsilon (t) = 1 / \sqrt t$.

Softmax 算法 设当前第 $k$ 个摇臂的平均奖赏是 $\bar r_k$, 则 Softmax 算法令本次选择第 $k$ 个摇臂的概率服从 Boltzmann 分布

$$P(k) \propto \exp \frac{\bar r_k}{\tau}$$

其中温度超参数 $\tau > 0$. $\tau \to 0$ 时等价于仅利用, $\tau \to +\infty$ 时等价于仅探索.

16.3 有模型学习

  考虑多步强化学习任务. 假设整个 Markov 决策过程的所有参数 $X, A, P, R$ 已知. 考虑优化目标是最大化 $T$-步累积奖赏或 $\gamma$-折扣累积奖赏

$$V_T = \frac 1T \sum _{t=1}^T \mathrm E r_t = \max \qquad \text{or} \qquad V_\gamma = \sum _{t=0}^\infty \mathrm E \gamma ^t r_{t+1} = \max$$

  整个强化学习围绕两个函数. 对于已知的策略 $\pi(x, a) \in [0, 1]$, 假设依照该策略生成的路径是

$$\{(x_0, a_0), (r_1, x_1, a_1), (r_2, x_2, a_2), \dots\}$$

定义:

• 状态值函数 (state value function) $V(\pi, x)$ 表示从初状态 $x_0 = x$ 开始依照策略 $\pi$ 获得的累积奖赏.
• 状态-动作值函数 (state-action value function) $Q(\pi, x, a)$ 表示从初状态 $x$ 执行动作 $a$ 后再依照策略 $\pi$ 带来的累积奖赏.

即

$$V(\pi, x) = \mathrm E(V \mid x_0 = x), \qquad Q(\pi, x, a) = \mathrm E(V \mid (x_0, a_0) = (x, a))$$

自然地, 它们的联系是

$$V(\pi, x) = \sum _{a \in A} Q(\pi, x, a)$$

  由于 Markov 决策过程具备 Markov 性, 所以状态值函数有全概率展开

$$\left \{ \begin{aligned} V_T(\pi, x) & = \frac 1T \sum _{t=1}^T \mathrm E_\pi (r_t \mid x_0 = x)\\ & = \frac 1T \sum _{a \in A} \sum _{x' \in X} \pi(x, a) P(x, a, x') \Big( R(x, a, x') + (T - 1) V_{T-1}(\pi, x') \Big)\\ V_\gamma(\pi, x) & = \sum _{t=0}^T \mathrm E_\pi (\gamma ^t r_{t+1} \mid x_0 = x)\\ & = \sum _{a \in A} \sum _{x' \in X} \pi(x, a) P(x, a, x') \Big( R(x, a, x') + \gamma V_\gamma(\pi, x') \Big) \end{aligned} \right.$$

前者是一个递归式, 可以令所有初值 $V_0 = 0$ 然后迭代求解. 后者是一个线性方程组, 但也可以通过设置初值迭代求解. 它们对应的状态-动作值函数是

$$\left \{ \begin{aligned} Q_T(\pi, x, a) & = \frac 1T \sum _{x' \in X} \pi(x, a) P(x, a, x') \Big( R(x, a, x') + (T - 1) V_{T-1}(\pi, x') \Big)\\ Q_\gamma(\pi, x, a) & = \sum _{x' \in X} \pi(x, a) P(x, a, x') \Big( R(x, a, x') + \gamma V_\gamma(\pi, x') \Big) \end{aligned} \right.$$

  以下重写策略为 $\pi(x) = a$ 形式, 即给定当前状态 $x$ 后固定选择行为 $a$ 而不是以一个概率选择. 此时问题的搜索空间是 $|A|^{|X|}$. 若对于每一个状态 $x$, 都能找到最佳行为 $a$, 使其奖励最大. 即最佳策略 $\pi^*: X \to A$ 满足

$$\pi ^*(x) = \argmax _{a \in A} Q(\pi ^*, x, a), \quad \forall x$$

该问题也可以迭代求解. 只需给策略 $\pi(x)$ 赋一个随机初值, 然后重复迭代即可.

16.4 无模型学习

  实际情况下有时 $P$ 和 $R$ 未知, 甚至 $A$ 也不定. 此时需要考虑无模型学习 (model-free learning).

Monte Carlo 强化学习 模型完全未知的情况下, 从起点 $x_0$ 开始尝试以某种策略 $\pi$ 探测 $T$ 步, 可以获得轨迹

$$\{(x_0, a_0), (r_1, x_1, a_1), (r_2, x_2, a_2), \dots, (r_{T-1}, x_{T-1}, a_{T-1}), (r_T, x_T)\}$$

考虑估计状态--动作值函数 $Q(\pi, x, a)$. 记录一个状态--动作对 $(x, a)$ 在轨迹中出现的位置, 然后统计其后的奖赏之和作为状态--动作值函数的估计值.

  现在考虑迭代估计最优策略 $\pi ^*$. 初次估计先任取策略 $\pi$ 并估计出最优策略 $\pi(x) \gets \argmax _a Q(x, a)$. 每一次采样决定策略时, 依照 $\varepsilon$-贪心法选定 $\pi$ 以概率 $1 - \varepsilon$ 为上一轮的最优策略, 概率 $\varepsilon$ 为从 $A$ 中任选一个策略.

时序差分 (TD, Temporal Difference) 学习 Monte Carlo 强化学习没有利用 Markov 性. 所以实际上无需每次重复采样生成新的轨迹, 而是只需在轨迹中的每一步实时更新状态-行动值函数并实时更新最优策略即可. 以 $\gamma$-折扣累积奖赏为例, 时序差分法对状态-动作值函数估计的迭代式是

$$Q(\pi, x, a) \gets (1 - \alpha) Q(\pi, x, a) + \alpha \Big( R(x, a, x') + \gamma Q(\pi, x', \pi(x')) \Big)$$

其中 $x$ 是前一个状态, $x'$ 是 $x$ 执行动作 $a$ 后转移到的状态. $\alpha$ 是学习率. $\pi(\cdot)$ 是与 Monte Carlo 强化学习中相同的 $\varepsilon$-贪心法选择的策略.

值函数近似 有时状态集是连续的, 例如 $X = \mathrm R^n$. 此时有无穷多个值函数要估计. 设真实值函数是 $V(\pi, \boldsymbol x)$. 与线性回归相似, 我们假设值函数是一个线性函数, 即

$$\hat V(\boldsymbol \theta, \boldsymbol x) = \boldsymbol \theta ^T \boldsymbol x$$

其中 $\boldsymbol \theta$ 是待估系数. 考虑最小二乘误差

$$(V(\pi, \boldsymbol x) - \hat V(\boldsymbol \theta, \boldsymbol x))^2 = \min$$

可以使用梯度下降法获得迭代式

$$\boldsymbol \theta \gets \boldsymbol \theta + \alpha ( V(\pi, \boldsymbol x) - \hat V(\boldsymbol \theta, \boldsymbol x)) \boldsymbol x$$

16.6 模仿学习

  利用人类专家决策过程范例的学习任务称为模仿学习 (imitation learning).

直接模仿学习 直接模仿学习尝试学习到一个状态到动作的映射. 假定已经有一批人类专家的决策轨迹数据 $\{\tau ^{(i)}\}_{i=1}^m$, 每条轨迹包含若干状态-动作对

$$\tau ^{(i)} = \{ (s^{(i)}_1, a^{(i)}_1), (s^{(i)}_2, a^{(i)}_2), \dots, (s^{(i)}_{n_i}, a^{(i)}_{n_i}), s^{(i)}_{n_i+1} \}$$

考虑到 Markov 性, 直接将这些数据合并为一个大数据集

$$D = \bigcup _i \tau ^{(i)}$$

然后对其进行分类 (对于离散动作) 或回归 (对于连续动作) 即可学得策略模型.

逆强化学习 逆强化学习 (inverse reinforcement learning) 尝试从人类专家范例数据学习到一个奖赏函数. 即估计一个奖励函数 $R$, 在该奖励函数下范例数据 $\{\tau ^{(i)}\}_{i=1}^m$ 是最优的. 假设奖励函数是线性函数 $R(\boldsymbol x) = \boldsymbol w^T \boldsymbol x$ 且仅与当前所处状态有关. 考虑策略 $\pi$ 对应的 $\gamma$-折扣累积奖赏

$$\rho(\pi) = \sum _{t=0}^\infty \mathrm E \gamma ^t \boldsymbol w^T \boldsymbol x_t = \boldsymbol w^T \underbrace{ \left( \sum _{t=0}^\infty \mathrm E \gamma ^t \boldsymbol x_t \right) }_{\bar{\boldsymbol x}} =: \boldsymbol w^T \bar{\boldsymbol x}$$

假设人类专家数据对应的策略是 $\pi^*$, 则我们希望学得的奖赏函数 $\rho(\pi)$ 可以使得

$$\rho(\pi^*) - \rho(\pi) = \min, \qquad \forall \pi \neq \pi^*$$

假设 $\sum \mathrm E \gamma ^t \boldsymbol x^* _t =: \bar{\boldsymbol x}^*$, 则奖赏函数的优化目标可以写成

$$\boldsymbol w^* = \argmax _{\boldsymbol w} \min _\pi \boldsymbol w^T (\bar{\boldsymbol x}^* - \bar{\boldsymbol x})$$

其中 $\bar{\boldsymbol x}$ 由策略 $\pi$ 生成, 而 $\pi$ 取遍所有可能的策略. 所有策略难以取遍, 在计算时可以考虑从随机策略开始迭代地取更好的策略.