前言
看到比赛的第一个想法是可以用强化学习的方式来学一个智能体出来。于是在找到了这个Github项目，花了两天时间恶补了一下强化学习的知识，但是读代码还是花费了不少时间，网上对于DQN训练俄罗斯方块智能体的解释都不大详细，所以就写一篇比较详细的。
什么是强化学习
它其实是和监督学习、无监督学习并列的一种机器学习的方法。
在强化学习当中，有几个元素：
- 智能体 agent（很多时候因为翻译的原因agent会被机翻成代理，是不对的。）
- 环境 environment
- 状态 state
- 行为 action
- 奖励 reward
他们之间的关系可以借助俄罗斯方块这个例子来理解，
智能体就是我们训练出来玩游戏的机器人；
环境就是俄罗斯方块的规则、积分等等的整个游戏环境；
状态就是某个时刻下，游戏的进行的状态，比如有多少分，之前的方块如何放置，目前正在下落的方块是什么等等；
行动是对状态采取的行为，例如把当前正在下落的方块旋转、移动等等；
奖励是指每个行为后环境给智能体的反馈，例如消除了方块记分，有空洞需要扣分，游戏结束了需要扣分等等。
那么强化学习的目标，实际上是训练智能体，让他学习出一个策略，根据这个策略可以做出相应的行动，让行动的奖励最大化。
这个策略也就是一个由状态集合到行为集合的映射，换句话说，给智能体一个当前的状态，它能给出一个合适的行为。
马尔可夫决策过程
智能体的每一次决策应当是一个马尔科夫决策过程。
它的步骤应该是这样的：
- 准备好策略，也就是一个由状态集合到行为集合的映射。
- 在t时刻，智能体观察环境的状态，根绝策略选择行动。
- 环境根据智能体的行动给奖励，同时更新到下一个状态。
- 重复上述过程，直到结束。
这个过程应该满足马尔可夫假设：
也就是，在设计时，应当尽量保证：
- 状态的转移只依赖于前一时刻的状态和动作
- 奖励只依赖于前一时刻的状态和动作
价值函数
那么我们怎么来衡量决策的好坏呢，这就需要引入价值函数。
假设我们已经有了一个策略，那么定义状态s的价值函数：V^{pi}(s)=Eleft[sum_{t=0}^{infty} gamma^{t} r_{t}right] 。
其中：
- 上标{pi}表示策略，策略不同，价值函数的值也不同。
- s表示状态，同一策略下，不同的状态有不同的价值。（例如，一般情况下，越接近成功的状态价值越高）
- E表示期望，使用期望是因为可能状态的转移不是确定的，而是按照概率分布的。（例如，可能同一个状态下，做同一个动作，有0.3的概率转移到状态1，有0.7的概率转移到状态2，这时候价值应该加权计算。
- gamma表示奖励的折扣率，随着时间t的增加，折扣越大。因为离当前状态越近的奖励应该是越重要的，而离当前状态越远的奖励应该打折扣。
- 价值函数就表示，当前状态下，根据已经有的策略，执行对应的动作无穷次（到终点）后，所有的奖励根据折扣的累加。以此来衡量当前状态的价值。
价值函数的值显然和后续每一步的行为和状态都有关，因此它也常被写成递推定义的形式：V^{}(s)=Eleft[rleft(s, pi^{}(s)right)right] gamma E_{left(s^{prime} mid s, pi^{}(s)right)}left[V^{}left(s^{prime}right)right]，这里的s^{prime}就表示下一个状态，而pi^{}(s)表示根据策略pi选出的动作，也就是a。
（好像看到有的面试题会要手动算，那其实应该倒着算，比如说定义最后一个状态的价值为0，往前算递推式比较好。）
在递推式当中，当前状态的价值就等于当前状态下根据所选择的动作带来的奖励期望加上下一个状态的价值乘以折扣率gamma。
这样一来，就可以衡量状态的价值了，那么最好的策略pi^{*}应该是：
也就是说，在最好的策略pi^{*}下，对于任意的状态s，状态s的价值都是大于其他策略的。
Q函数
通过不断迭代更新价值函数，就一定可以收敛到最优的V^{*}(s)（数学上可以证明），但是很多情况下，我们没法计算价值函数，因为：Pleft(S_{t 1} mid S_{t}, Aright)未知。
Pleft(S_{t 1} mid S_{t}, Aright)位置的意思就是说，给定状态和行为，下一个状态是未知的。
这里的未知，并不是不确定，如果是按照某种我们知道的概率分布的话，它应该是已知的。
俄罗斯方块就是这么个情况，相同的状态下我们放置了相同的方块（执行了相同的动作），但是下一个出现的方块和旋转情况仍是未知的，因此我们没法计算当前状态的价值，因为当前状态的价值是依赖于下一个状态的。
回顾一下上面的价值函数的递归定义：
V^{}(s)=Eleft[rleft(s, pi^{}(s)right)right] gamma E_{left(s^{prime} mid s, pi^{}(s)right)}left[V^{}left(s^{prime}right)right]
Q函数的定义是：
Q(s, a)=E[r(s, a)] gamma E_{left(s^{prime} mid s, aright)}left[Vleft(s^{prime}right)right]
Q函数和V函数的差别就在于，Q函数的行为是作为参数传入的，因此不需要给定策略，也不需要知道状态转移Pleft(S_{t 1} mid S_{t}, Aright)。
二者的联系在于，V^{*}(mathrm{~s})=max _{a} Q(s, a)，也就是，s状态的价值应该是s状态下选择价值最大的行为的Q函数的值。
在决策的时候，最佳策略pi^{*}(s)=arg max _{mathrm{a}} Q(s, a)，智能体对某个状态只要选择使Q函数最大的行为a即可。
总的来说，价值函数是用来衡量某个状态的价值的，Q函数是用来衡量某个状态下选择了某个行为的价值的，而选择了最佳行为的Q函数的值就等于当前状态的价值。但是使用Ｑ函数可以在状态转移未知的情况下学习到策略，因为智能体可以通过试错的方式，经验状态s下的每一个行为a。
学习Q函数
前面说到，学习策略的问题现在变成了学习Q函数的问题。
可以通过这个式子来不断更新Q函数：令Q(s, a) = left(1-beta_{n}right) Q(s, a) beta_{n}left[r gamma max _{a^{prime}} Qleft(s^{prime}, a^{prime}right)right]，其中，beta_{n}=frac{1}{1 text { 遍历 }(s, a) text { 的次数 }}
具体的步骤如下：
- 随机初始化所有Q(s,a)。
- 在状态s下执行行动a。
- 得到奖励$r$和新的状态s^{prime}。
- 令Q(s, a) = left(1-beta_{n}right) Q(s, a) beta_{n}left[r gamma max _{a^{prime}} Qleft(s^{prime}, a^{prime}right)right]
- 状态更新为s^{prime}，重复2。
最开始的时候，因为(s,a)遍历次数少，beta_{n}较大，因此更新的权重较高，随着次数增加，1-beta_{n}增大，更新的权重下降。
神经网络
上述迭代学习Q函数的过程是可证一定收敛的，但是在俄罗斯方块中，还是有问题。
因为俄罗斯方块的状态是很多很多的，很难列举出所有的状态做迭代。
因此DQN(Deep Q Learning)的思想就是，不通过迭代来学习Q函数，而是直接使用神经网络来近似学习Q函数。
神经网络当然完全可能不收敛，但是达到一定的水平也可以使用。
还是一样的学习思路：令Q(s, a) = left(1-beta_{n}right) Q(s, a) beta_{n}left[r gamma max _{a^{prime}} Qleft(s^{prime}, a^{prime}right)right]。
DQN下，学习的过程是：
- 随机初始化神经网络N内部的权值。
- 在状态s下执行行动a。
- 得到奖励$r$和新的状态s^{prime}。
- 使用神经网络N计算r gamma max _{a^{prime}} Qleft(s^{prime}, a^{prime}right)
- 使用神经网络N计算Q(s,a)
- 因为Q学习的过程就是要缩小r gamma max _{a^{prime}} Qleft(s^{prime}, a^{prime}right)和Q(s,a)的差距，因此损失函数L=frac{1}{2}left[r gamma max _{a prime} Qleft(s^{prime}, a^{prime}right)-Q(s, a)right]^2
- 回传优化L。
- 重复2。
值得一提的，如果4和5使用的两个相同设计的神经网络，就成为DDQN(Double Deep Q Learning)。
核心代码详解
如果知道DQN的话，代码就挺好懂的了！
一起看看核心的代码（会跳过一部分不是很重要的），其中还有几个有意思的小trick。
首先是初始化代码和模型，神经网络的结构并不复杂，是几个全连接层和relu激活函数，就不细说：
代码语言：txt复制env = Tetris(width=opt.width, height=opt.height, block_size=opt.block_size)
model = DeepQNetwork()每次训练时会计算epsilon
代码语言：txt复制epsilon = opt.final_epsilon (max(opt.num_decay_epochs - epoch, 0) * (
opt.initial_epsilon - opt.final_epsilon) / opt.num_decay_epochs)
u = random()
random_action = u <= epsilon这是我们在训练神经网络的时候常用的一个小trick，叫做Exploration-Exploitation，在训练时，epsilon会从大变小。
而epsilon代表的是使用随机动作的概率，因此训练过程中采用随机动作而不采用学习到策略推算出的动作的概率会从小到大。
因为最开始时网络的权值是随机初始化的，输出的本身也是随机的。
而随着网络的收敛，输出的动作开始倾向稳定，但这样反而可能不利于智能体学习到另一个更优的动作，因此此时可以采样一些随机动作。
然后获取下一个状态和下一个状态可以进行的动作。
代码语言：txt复制next_steps = env.get_next_states()
next_actions, next_states = zip(*next_steps.items())使用模型来选择一个行动，得到奖励，判断游戏是否结束，未结束的继续下一个状态和行动：
代码语言：txt复制model.eval()
with torch.no_grad():
predictions = model(next_states)[:, 0]
model.train()
reward, done = env.step(action, render=True)这里除了predictions = model(next_states)[:, 0]之外，
其他代码的作用是关闭pytorch的自动求导功能，
也就是这一步是没有前向传播的过程的。
因为这里是在玩游戏，是采样的过程，不需要被优化，整个优化的过程放在后面。
一轮游戏结束后，就有另一个比较有意思的小trick：
代码语言：txt复制replay_memory = deque(maxlen=opt.replay_memory_size)
state_batch, reward_batch, next_state_batch, done_batch = zip(*batch)
state_batch = torch.stack(tuple(state for state in state_batch))
reward_batch = torch.from_numpy(np.array(reward_batch, dtype=np.float32)[:, None])
next_state_batch = torch.stack(tuple(state for state in next_state_batch))这个叫 Experience Replay ，在每次训练的时候不是使用最近一局游戏的状态和行为集合来训练，而是每次都将数据放入一个缓存中，训练时从缓存中拿出几组数据来训练。
这样可以防止陷入局部的最优解，也更有利于GPU的并行计算。
（其实更有趣的是这样就可以把人类玩家游戏的数据也放进去一起训练）
具体的优化代码是：
代码语言：txt复制q_values = model(state_batch)
model.eval()
with torch.no_grad():
next_prediction_batch = model(next_state_batch)
model.train()
y_batch = torch.cat(
tuple(reward if done else reward opt.gamma * prediction for reward, done, prediction in
zip(reward_batch, done_batch, next_prediction_batch)))[:, None]
optimizer.zero_grad()
loss = criterion(q_values, y_batch)
loss.backward()
optimizer.step()先计算状态s下每个行为的Q值，也就是前文提到的Q(s,a)。
（这其实也是个小trick，一般这样会比每个行为都过一遍网络更快）
然后计算下一行为的Q值。（这里是不需要前向传播的，因为这个Q值后面会被用来计算r gamma max _{a^{prime}} Qleft(s^{prime}, a^{prime}right)，也就相当于我们做回归时候的真实值，后面的代码也将其命名为y。
随后就是优化Q值和Y值的过程了，应该通过优化使二者不断接近。
就到这啦。
结语
其实这个代码是训练一个玩正常的俄罗斯方块的智能体。
但是挑战赛中，方块出现的顺序、种类、旋转都是固定的，我们可以通过修改环境，将比赛的规则加入，然后再比赛的环境下训练出解出比赛的机器人。
但是：
Q Learning可能有点不太合适，因为这其实是一个确定的环境。
我觉得更好的方法可能是值函数近似（解决状态太多的问题） 价值迭代 or 某种基于价值函数的解法。
更更好的方法也许会是 Policy Gradients ，整体理解起来会更简单（和概率预测的回归对比起来理解），并且DQN的作者本人之前有篇arxiv的文章上也承认调试的好的话 Policy Gradients 效果会更好呢。
