课程主页: https://www.davidsilver.uk/teaching/

这里回顾David silver 强化学习 Lecture 10的课程内容,这一讲简单介绍了经典游戏。

Game Theory

Optimality in Games

  • 第$i$个玩家的最佳策略$\pi^i$是什么,如果其他的玩家固定他们的策略$\pi^{-i}$?

  • 最优响应$\pi_{*}^{i}\left(\pi^{-i}\right)$为对抗这些策略的最优策略

  • 纳什均衡是所有玩家的共同策略,其中

    使得每个玩家的策略都是最佳响应

  • 即没有玩家会选择偏离纳什

Single-Agent and Self-Play Reinforcement Learning

  • 最优响应是解决单智能体RL问题

    • 其他参与者成为环境的一部分
    • 游戏简化为MDP
    • 最佳响应是此MDP的最佳策略
  • 纳什均衡是self-play RL的不动点

    • 经验是通过在智能之间玩游戏而产生的

    • 每个智能体都学会了对其他玩家的最佳反应

    • 一个玩家的策略决定了另一个玩家的环境

    • 所有玩家都在互相适应

Two-Player Zero-Sum Games

我们将专注于特殊类别的游戏:

  • 一个两人游戏包含两个(交替)玩家

    • 我们将玩家1命名为白方,将玩家2命名为黑方
  • 零和博弈对黑白双方的奖励相等且相反

我们考虑在这些游戏中找出纳什均衡的方法

  • 游戏树搜索(即规划)
  • self-paly强化学习

Perfect and Imperfect Information Games

  • 完全信息或马尔可夫游戏是完全可观测的
    • 跳棋
    • 黑白棋
    • 西洋双陆棋
    • 围棋
  • 不完全信息游戏是部分可观测的
    • 拼字游戏
    • 扑克
  • 我们首先专注于完全信息游戏

Minimax

  • 价值函数定义了联合策略$\pi=\left\langle\pi^{1}, \pi^{2}\right\rangle$下的预期总回报

  • minimax价值函数最大化白方的期望回报,同时最小化黑方的期望回报

  • minimax策略是一种联合策略$\pi=\left\langle\pi^{1}, \pi^{2}\right\rangle$,该策略达到minimax价值

  • 存在唯一的minimax价值函数

  • minimax策略是纳什均衡

来看一个具体例子:

  • 搜索树呈指数增长
  • 搜索到游戏结束不切实际
  • 而是使用值函数逼近器$v(s, \mathbf{w}) \approx v_{*}(s)$
    • 例如评估函数,启发式函数
  • 使用价值函数来估计叶节点的minimax值

Binary-Linear Value Function

  • 二进制特征向量$\mathrm x(s)$:例如每个格子一个值
  • 权重向量$\mathrm w$:例如每个格子的价值
  • 通过对特征的权重求和来评估位置

例如

Self-Play Reinforcement Learning

Self-Play Temporal-Difference Learning

  • 将基于价值的RL算法应用于self-play游戏

  • $\text{MC}$:利用回报$G_t$更新价值函数

  • $\text{TD}(0)$:利用$v(S_{t+1})$更新价值函数

  • $\text{TD}(\lambda)$:利用$\lambda$回报$G_t^\lambda$更新价值函数

Policy Improvement with Afterstates

  • 对于确定性游戏,可以估计$v_{*}(s)$

  • 这是因为我们可以有效地评估后继状态

  • 游戏规则定义了后继状态$\operatorname{succ}(s, a)$

  • 选择动作,通过最小/最大化后继状态值

  • 这改善了双方的共同策略

Simple TD

  • 通过TD学习价值函数

  • 然后在minimax搜索中使用价值函数(无学习)

TD Root

  • TD根:利用后续搜索结果更新价值

  • 搜索值是从根节点在$S_t$处计算

  • 利用下一个状态的搜索值更新价值函数

  • 其中$l_{+}(s)$是从$s$处获得minimax值的叶节点

TD Leaf

  • TD叶子:根据后继搜索值更新搜索值

  • 计算当前和下一步的搜索值

  • 利用$t+1$的搜索值更新$t$的搜索值

TreeStrap

  • TreeStrap:将搜索值更新为更深的搜索值

  • 在所有节点$s \in \text { nodes }\left(S_{t}\right)$处计算出的Minimax搜索值

  • 根据搜索值更新全部节点

  • Self-play强化学习可以代替搜索
  • 从根状态$S_t $模拟Self-play游戏
  • 将RL应用于模拟经验
    • 蒙特卡洛控制$\Longrightarrow$蒙特卡洛树搜索
    • 最有效的变体是UCT算法
      • 使用UCB平衡每个节点中的探索/开发
    • Self-play UCT收敛于minimax值
    • 完全信息,零和,2人游戏
    • 不完全信息:请参阅下一部分

Reinforcement Learning in Imperfect-Information Games

Game-Tree Search in Imperfect Information Games

  • 玩家的信息状态不同,因此搜索树不同

  • 每个信息状态有一个节点

    • 总结玩家所知道的
    • 例如他们看过的卡片
  • 许多真实状态可能共享相同的信息状态

  • 也可能汇总状态,例如具有相似的价值

Solution Methods for Imperfect Information Games

信息状态博弈树可以通过以下方式解决:

  • 迭代前向搜索方法
  • Self-play强化学习
  • 平滑的UCT
  • 将MCTS应用于信息状态游戏树

  • UCT的变体,受博弈理论Fictitious Play的启发

    • 智能体学习对手的平均行为并做出回应
  • 从节点的动作计数中提取平均策略,$\pi_{a v g}(a | s)=\frac{N(s, a)}{N(s)}$

  • 在每个节点上,根据如下方式选择动作

  • 根据经验,在扑克的变体中:

    • 普通的MCTS发散
    • 平滑UCT收敛到Nash均衡

Conclusions