马尔可夫决策#

一个更学术的观点, RL 是一个马尔可夫决策过程, 由四元组 组成

• : 状态空间, 假设某个时间步对应的状态是 , 则 .
• : 动作空间, 假设某个时间步对应的状态是 , 则 .
• : 即 , 代表某个时间步在动作 影响下从 到 的概率.
• : 即 , 代表某个状态执行某个动作的奖励.

策略#

我们的目标是让智能体学会最优解, 即最大化 . 此时我们的智能体会按照某个策略 根据不同状态决定不同的动作. 此时 代表了一个映射, 其输入为状态空间与动作空间笛卡尔积, 输出则是概率, 也就是在 时刻状态为 的条件下采用动作 的概率.

奖励#

为了衡量总的奖励, 我们需要在某个时刻点 计算未来能获得多少奖励, 此时可以将未来获得的回报都加起来, 设为 .

但是这造成了一个问题, 可以立刻获得的奖励 (即时奖励) 是比未来的奖励更重要的, 所以我们引入一个折扣因子 将 改写.

价值#

为了更好地评估某个策略 在不同状态或采取动作下未来能得到多少奖励, 我们需要了解在策略 的条件下, 处于某状态 的价值 (状态价值)、处于某状态 之后采取动作 的价值 (动作价值). 策略 是一个概率分布, 因此我们应该采用期望来建模价值.

• 状态价值 , 对应在某策略下某状态的期望.
• 动作价值 , 对应在某策略下某状态采取某动作的期望.

由于 , 因此可以得到状态价值和动作价值的关系.

最优化目标#

RL 的基本目标就是尽可能得到最高的全局 Reward. 假设全局最优用 上标表示.

• 对于状态价值, 我们选择所有策略中最大的.

• 对于动作价值, 我们同样可以每次都选择最大的, 但是我们会考虑从所有动作中选择能提供最大价值的函数, 那么由于该情况下 是确定的, 所以依然能通过 与 得到 .

总时间步#

对于一场棋局, 显然当落满棋子一定结束, 所以最多有 100 个时间步, 但是对于两个对弈的智能体来说, 每个智能体相互落子, 所以时间步应该减半. 此时, 我们认为 50 个时间步就是一个完整的 eposide.

状态空间#

在该场景下, 我们可能将棋局的所有坐标建模为状态, 例如 代表第 行 列的棋子是 色的如果 的话. 假设 和 为二值的, 则状态空间应该有 这么大.

动作空间#

假设我们有两个互相博弈的智能体, 每个智能体只下黑棋或者白棋, 那么对于某个智能体来说, 我们的动作其实就是 , 表示在第 行 列落子. 总动作空间为 , 当然并非固定, 动作空间大小应该随落子数量变多而减少.

奖励#

奖励 (Reward Model) 的设计较为灵活, 我们可能会这样设计.

• 当连成 2 子时 +1; 3 子 +2; 4 子 +3; 5 子 +6;
• 当阻止对方连成 2、3、4、5 子 时 +1, +2, +3, +5;
• 当尝试落子的位置已经存在棋子时 -1;
• …

实际设计时可以尝试让 “连子” 的奖励略高于 “阻止”, 也可以反过来, 但是最好让连成 5 子的奖励较高, 或者连成 5 子的趋势奖励较高. 例如根据棋局情况可以判断当前连成的 3 子在某处落子连成 4 子后必然存在两个位置可以连成 5 子, 即考虑一些必胜情况.

策略#

通常来说我们初始化全相等 (0时刻每个落子位置都是 的概率). 此时产生的 形如 . 之后则按照不同的方式进行学习.