强化学习简介（一）：Q-learning

完成图像分类之类的监督学习任务，已经没有特别大的难度。我们希望AI能够帮助我们处理一些更加复杂的任务，比如：下棋、玩游戏、自动驾驶、行走等。这一类的学习任务被称为强化学习。

强化学习图示

K摇臂赌博机

我们可以考虑一个最简单的环境：一个动作可立刻获得奖励，目标是使每一个动作的奖励最大化。对这种单步强化学习任务，可以设计一个理论模型——“K-摇臂赌博机”。这个赌博机有K个摇臂，赌徒在投入一个硬币后可一选择按下一个摇臂，每个摇臂以一定概率吐出硬币，但这个概率赌徒并不知道。赌徒的目标是通过一定的策略最大化自己的奖赏，即获得最多的硬币。最终所获得的总奖励被称为累计奖励。

K摇臂赌博机

对于这个简单模型，若要知道每个摇臂的概率，我们只需要进行足够多的尝试即可，这是“仅探索”策略；若要奖励最大化，则需要执行奖赏概率最大的动作即可，这是“仅利用”策略。但在更复杂的环境中，我们不可能对每一个状态的每个动作都进行足够多的探索。比如围棋，我们后续的探索是需要依赖于之前的探索的。因此我们需要在探索和利用之间进行平衡。我们在学习的过程中，必须要保持一定的概率`epsilon`进行探索，其余时候则执行学习到的策略。

基本概念术语

为了便于分析讨论，我们定义一些术语。

机器agent处于环境`E`中。
状态空间为`S`，每个状态`s in S`是机器感知到的环境描述。
机器能够采取的可采取的动作a的集合即动作空间`A`，`a in A`。
转移函数`P`表示：当机器执行了一个动作`a`后，环境有一定概率从状态`s`改变为新的状态`s’`。即：`s’=P(s, a)`
奖赏函数`R`则表示了执行动作可能获得的奖赏`r`。即：`r=R(s,a)`。
环境可以描述为`E=<<S, A, P, R>>`。
强化学习的任务是习得一个策略（policy）`pi`，使机器在状态`s`下选择到最佳的`a`。策略有两种描述方法：
1. `a=pi(s)` 表示状态`s`下将执行动作`a`，是一种确定性的表示法。
2. `pi(s, a)` 表示状态`s`下执行动作`a`的概率。这里有 `sum_a pi(s,a)=1`
累计奖励指连续的执行一串动作之后的奖励总和。
`Q^(pi)(s, a)`表示在状态`s`下，执行动作`a`，再策略`pi`的累计奖励。为方便讨论后续直接写为`Q(s,a)`。
`V^(pi)(s)` 表示在状态`s`下，使用策略`pi`的累计奖励。为方便讨论后续直接写为`V(s)`。

强化学习往往不会立刻得到奖励，而是在很多步之后才能得到一个诸如成功/失败的奖励，这是我们的算法需要反思之前所有的动作来学习。所以强化学习可以视作一种延迟标记的监督学习。

Q-learning

对于我们要学习的`Q(s,a)`函数，我们可以使用一个Q-table来表示。Q-table是一个二维表，记录每个状态`s in S, a in A`的`Q`值。Q表被初始化为0的状态。在状态`s`执行了动作`a`之后，得到状态`s’`，奖励`r`。我们将潜在的`Q`函数记为`Q_(real)`，其值为当前奖励r与后续状态`s’`的最佳累计奖励之和。则有：

` Q_(real)(s, a) = r + gamma * argmax_aQ(s’, a) `
` err = Q_(real)(s, a) - Q(s, a) `

其中`gamma`为`Q`函数的偏差，`err`为误差，`alpha`为学习率。可得出更新公式为：

` Q(s, a) leftarrow Q(s, a) + alpha*err `
即：
` Q(s,a) leftarrow (1-alpha)Q(s,a) + alpha(r + gamma * argmax_aQ(s’, a)) `

以上公式即为Q-learning的关键

算法描述

# 初始化Q表
for s in S:
  for a in A:
    Q(s, a) = 0
# 训练过程
for i in range(N):
  if rand() < epsilon:
    a = 从 A 中随机选取一个动作
  else:
    a = 从 A 中选取使 Q(a) 最大的a
  # 从环境中获得反馈
  r = R(s, a)
  s1 = P(s, a)
  # 更新Q表
  Q(s,a) = (1-alpha)*Q(s,a) + alpha * (r + gamma * argmax Q(s1, a) - Q(s, a))
  s = s1

下图是一个Q表内存结构，在经过一定的学习后，Q表的内容将能够不断逼近每个状态的每个动作的累计收益。
Q-table

2019-12-27