April | 2017 | ZHANG RONG

Lectures

Note that there will be two lectures about AlphaGo on March 24. We will talk about AlphaGo in the context of the whole course at the normal place and time (9:15am in Roberts 412), and in addition David Silver will give a seminar that afternoon. Neither of these will be required for the exam.

Introduction to reinforcement learning updated January 14 (Lecture: January 14)

Exploration and Exploitation updated January 21 (Lecture: January 21)

Markov decision processes updated January 27 (Lecture: January 28)

Dynamic programming updated February 3 (Lecture: February 4)

Learning to predict updated February 10 (Lecture: February 11)

Learning to control updated March 16 (Lecture: February 25)

Value function approximation updated March 2 (Lecture: March 3)

Policy-gradient algorithms updated March 9 (Lecture:…

随着 DeepMind 成功地使用卷积神经网络（CNN）和强化学习来玩 Atari 游戏，AlphaGo 击败围棋职业选手李世石，强化学习已经成为了机器学习的一个重要研究方向。除此之外，随着人工智能的兴起，自然语言处理在聊天机器人和智能问答客服上也有着广泛的应用。之前在一篇博客里面曾经介绍了强化学习的基本概念，今天要介绍的是强化学习在文本领域的应用，也就是如何使用强化学习来玩文本游戏。要分享的 Paper 是 Deep Reinforcement Learning with a Natural Language Action Space，作者是 Microsoft 的 Ji He 与他的合作者们。

对于强化学习而言，那就不得不提到 Markov 决策过程（Markov Decision Process）。它是由状态（State），动作（Action），状态转移概率（State Transition Probability），折扣因子（Discount Factor），奖励函数（Reward Function）五个部分构成。强化学习做的事情就是该 agent 在某一个时刻处于某个状态 s，然后执行了某个动作 a，从整个环境中获得了奖励 r，根据状态 s 和奖励 r 来继续选择下一个动作 a，目标是让获得的奖励值最大。整个过程其实是一个不断地从环境中执行动作和获得奖励的过程，通过引入动作值函数 Q(s,a) 的概念，介绍了 Q-learning 这个基本算法。通过 Q-learning 来让 agent 获得最大的奖励。

在实际的生产环境中，状态空间 S 很可能是十分巨大的，如果对于 Atari 游戏的话，动作空间 A 是有限的（例如上下左右移动，攻击，躲避等）。因此 DeepMind 在处理这个问题的时候，创新性地使用了卷积神经网络（CNN）和强化学习（RL）两者结合的解决方案。通过 CNN 来读取游戏图像，然后神经网络输出的是动作值函数 Q(s,a)，其中 a 就是游戏手柄上的几个动作按钮。然后使用周围环境的反馈和强化学习方法来获得相应的样本，从而训练整个 CNN 神经网络。

下面来介绍本文的正式内容。首先文本游戏和视觉游戏有一定的差别，视觉游戏的状态就是当前的屏幕图像，文本游戏的状态是一段文本描述，然后玩家来给出一个合适的动作进入下一个状态。例如：白色的文字描述就是当前的状态，蓝色的文字就是玩家要选择的动作。

Description of Text Games

当玩家选择了其中一个状态（例如选择了第一个 A Lister sandwich）之后，就会进入下一个状态，如图所示。

Description of Text Games2

注：关于文本游戏 Machine of Death 的代码和基本信息，可以参见 https://github.com/jvking/text-games.

为了做一个 agent 使其能够自主地玩文本游戏，基于当前的文本游戏背景，就要考虑到两种文本情况，分别是状态文本（state-text）和动作文本（action-text）。agent 需要同时理解这两部分的文本，然后争取在玩游戏的过程中获得最大的收益，最终才能够学会玩游戏。对于每一个时刻 t，状态是 $s_{t}$ ，动作是 $a_{t}$ 。该 agent 的策略定义为在状态 $s_{t}$ 执行动作 $a_{t}$ 的概率 $\pi(a_{t}|s_{t})$ 。如果折扣因子是 $\gamma$ ，那么基于策略 $\pi$ 的动作值函数就定义为：

$Q^{\pi}(s,a)=E[\sum_{i=0}^{\infty}\gamma^{i}r_{t+i}|s_{t}=s, a_{t}=a]$ .

在该paper中，作者使用 softmax 策略来进行必要的探索活动，也就是说在状态 $s_{t}$ 选择 $a_{t}$ 的概率是

$\pi(a_{t}=a_{t}^{i}|s_{t}) = \exp(\alpha\cdot Q(s_{t},a_{t}^{i}))/\sum_{j=1}^{|A_{t}|}\ \exp(\alpha\cdot Q(s_{t},a_{t}^{j})),$

在这里 $A_{t}$ 是在状态 $s_{t}$ 可以执行的所有动作的集合， $a_{t}^{i}$ 是 $A_{t}$ 的第 i 个动作， $\alpha>0$ 是某个常数。

因为状态文本（state-text）通常来说是长文本，动作文本（action-text）是短文本，两者有着本质的区别，因此作者在构建神经网络的时候分别对状态文本和动作文本搭建了相应的神经网络。在本文中，作者对比了三种神经网络结构，分别是 Max-action DQN，Pre-action DQN 和 DRRN。如下图所示：

DRRN

对于 Max-action DQN，该模型适用于对每一个状态 $s_{t}$ 中动作空间的数量都是已知的情况，因为它是把状态和动作拼成一个向量作为神经网络的输入的，然后计算出每一个动作的 Q 值。

对于 Pre-action DQN，该模型把每一对状态文本和动作文本当作输入，也就是（状态文本，动作文本）这种形式，通过神经网络计算出这一对状态文本和动作文本的 Q 值。

对于 DRRN，该模型把每一对状态文本和动作文本当作输入，依旧是（状态文本，动作文本）这种形式。然后对状态文本和动作文本分别构建一个神经网络，然后对输出的两个向量进行内积的操作，从而获得 Q 值。用数学语言来描述就是，给定一个状态文本和动作文本的对，也就是 $(s_{t},a_{t}^{i})$ ，使用相应的神经网络同时把 $s_{t}$ 和 $a_{t}^{i}$ 映射成向量 $h_{\ell,s}$ 和 $h_{\ell,a_{t}^{i}}$ ，然后计算这两个向量的内积 $h_{\ell,s}\cdot h_{\ell,a_{t}^{i}}$ ，最后选择 $a_{t} = argmax_{a_{t}^{i}}Q(s_{t},a_{t}^{i})$ 作为当前状态的动作。其中， $h_{\ell,s}$ 和 $h_{\ell, a}$ 分别指的是状态网络和动作网络的第 $\ell$ 个隐藏层神经网络的输出。 $W_{\ell,s}$ , $W_{\ell,a}$ 和 $b_{\ell,s}$ , $b_{\ell,a}$ 是在第 $(\ell-1)$ 层和第 $\ell$ 层的权重矩阵和偏移量。也就是说，DRRN 拥有 L 个隐藏层，并且

$h_{1,s} = f(W_{1,s}s_{t}+b_{1,s}),$

$h_{1,a}^{i} = f(W_{1,a}a_{t}^{i}+b_{1,a}),$

$h_{\ell,s} = f(W_{\ell,s}h_{\ell-1,s}+b_{\ell,s}),$

$h_{\ell,a}^{i} = f(W_{\ell,a}h_{\ell-1,a}^{i}+b_{\ell,a}),$

其中 f 是激活函数， $1\leq \ell \leq L$ 。Q 值函数定义为 $Q(s,a^{i};\Theta) = g(h_{L,s},h_{L,a}^{i})$ ，其中 g 可以定义为两个向量的内积。

综上所述，DRRN 的伪代码如下：

DRRN Code

DRRN 相比另外两个模型其创新点在于分别使用了两个网络来映射状态文本和动作文本，因为如果将长文本和短文本直接拼接输入单个神经网络结构的时候，可能会降低 Q 值的质量，所以把 state-text 和 action-text 分别放入不同的网络结构进行学习，最后使用内积合并的方式获得 Q 值的方法会更加优秀。

参考文献：

Deep Reinforcement Learning with a Natural Language Action Space

ZHANG RONG

Monthly Archives: April 2017

UCL course – 2016

Lectures

用强化学习玩文本游戏

zr9558's Blog