AlphaGo

围棋可以类比为一个分类任务，输入为棋盘状况，输出为每个点的行棋概率。

SL Policy Network

• CNN
• 目标：模仿人类棋手的下法
• 损失函数：$L(w)=-\sum t_a\log (p_{\sigma })$
  • $t_a$：棋手落子处为 1，否则为 0
  • $p_{\sigma }$：网络输出

RL Policy Network

• 初始化为 SL Policy Network
• 让当前网络与先前随机选择的一个版本的网络进行对弈
• 直观上讲，若结果为胜，则提高对弈过程中每一步的选择概率，否则相反

形式化说明

目标是最大化所有可能轨迹的期望总回报

$$J(\theta )={\mathbb{E}}_{\tau \sim {\pi }_{\theta }}[R(r)]=\sum _{\tau }P(\tau |\theta )R(\tau )$$

• $\tau$ 为轨迹，即棋局-走法-棋局-…-终局，$\tau =(s_0,a_0,s_1,a_1,\dots ,s_T)$
• $R(\tau )$ 为总回报 求导得 ${\nabla }_{\theta }J(\theta )={\sum }_{\tau }{\nabla }_{\theta }P(\tau |\theta )R(\tau )$ 由于 $\nabla x=x\nabla \ln x$， ${\nabla }_{\theta }J(\theta )={\sum }_{\tau }P(\tau |\theta ){\nabla }_{\theta }\ln P(\tau |\theta )R(\tau )={\mathbb{E}}_{\tau \sim {\pi }_{\theta }}[{\nabla }_{\theta }\ln P(\tau |\theta )R(\tau )]$ $P(\tau |\theta )=P(s_0){\prod }_{t=0}^T{\pi }_{\theta }(a_t|s_t)P(s_{t+1}|s_t,a_t)$ 其中 $P(s_0)$ 和环境状态转移概率 $P(s_{t+1}|s_t,a_t)$ 均为常数，对两侧取对数求导后有 ${\nabla }_{\theta }J(\theta )={\mathbb{E}}_{\tau \sim {\pi }_{\theta }}\left[{\sum }_{t=0}^T{\nabla }_{\theta }\ln {\pi }_{\theta }(a_t|s_t)R(\tau )\right]$ 由于工程实现中无法穷举所有轨迹，只能通过蒙特卡洛采样来近似这个期望，经典的实现是 REINFORCE 算法

• 问题：可能整盘棋中大多数棋都很好，只有某几步很坏，导致最后输棋，但是该方法会直接对全部走子一视同仁

Value Network

• 结构类似策略网络，但输出是一个 $[-1,1]$ 的标量代表预估胜率
• 训练样本是训练 RL Policy Network 时 self play 产生的对局数据
  • 为了避免前后盘面高度相关导致网络过拟合，每局只随机抽取一个盘面

Rollout Policy Network

• 结构与 SL Policy Network 类似但规模更小，速度快
• 用于与 MCTS 进行结合，在 rollout 时使用

与 MCTS 结合

• 节点第 $i$ 次 rollout 的收益为 $v_i(s)=\lambda \cdot value(s)+(1-\lambda )rollout(s)$
• 平均收益为 $Q(s_a)={\sum }_{i=1}^n{v}_i(s_a)/n$
• 探索项改为

$$u(s_a)=c\cdot \frac{p_{\sigma }(s,a)}{N(s,a)+1}$$

- 注意此处用的是 SL 策略网络而不是 RL 策略网络
- $N$ 为模拟次数

• 用 $Q(s_a)+u(s_a)$ 代替信心上限进行选择

Actor-Critic

在计算策略梯度时，不直接乘以回报 $G_t$ ，而是乘以增量 $A(s_a)=G_t-V(s_a)$

• 如果走的比平均预期好，概率增加，否则降低