贝尔曼方程和Q-Learning

贝尔曼方程(Bellman Equation)

参考视频来源

• $Q^*(s,a)$:最优动作价值函数(Optimal Action_Value Function)。表示在状态s下采取动作a，之后永远按最优策略行动能获得的期望奖励。
  这里*代表最优。
• $P(s’|s,a)$:状态转移概率(State Transition Probability)。表示在状态s下执行动作a后转移到下个状态s’的概率。因为环境是随机的，我们要考虑所有的可能性，所以我们要对所有状态的可能性进行一个加权求和。
• $R(s,a,s’)$:即时奖励(Immediate Reward)。表示在状态s执行动作a，并且转移到状态s’之后，可以立刻获得的回报。
• $\gamma$:折扣因子(Discount Factor),$\gamma \in [0,1]$。表示未来奖励相对于当前奖励的重要性，同时确保了在无限步骤的任务中总回报也是一个有限值。
• $\max_{a’}Q^(s’,a’)$:下一个状态的最大未来价值。也就是说，到达下一个状态 s’ 之后，查看所有可能的动作a’，然后选择能够使$Q^$最大的那个。这一个部分就假设了我们在未来也会一直遵循最优策略。

因为对于所有可能的下个状态$s’$对应的奖励值，用它们的条件概率作为权重进行加权平均，这个就是期望。 所以，贝尔曼方程还有如下形式：

我们可以这样理解，可以分成两个部分：左边的这个$R(s,a,s’)$就是当前能获得的及时奖励，右边的这个$\gamma\max_{a’}Q^*(s’,a’)$就是未来能获得的最大折扣奖励。

所以这个方程就相当于是你在思考这样一个问题：

Q： 如果我处在状态s，并且我选择的动作a，那么我能获得的最大未来总回报是多少？

A： 贝尔曼方程说它等于你马上能获得的奖励，再加上未来所有可能的新状态s’的最大价值，并根据它出现的概率和折扣因子进行加权。

回到原方程，既然是方程，什么是已知量？什么是未知量？

• 已知量：
  首先是环境的转移概率和即时的奖励函数，这些都是环境定义的部分。然后是$\gamma$这个因子，这是人为设定的。

• 未知量：
  这个最优的 Q 值。如果状态空间是有限的，比如说有|s|个状态、|a|个动作，那么就总共有$|s|\times|a|$个未知数$Q^*(s,a)$，每一个状态动作对一个方程。它就表达了一个递归关系：在执行动作a之后，会以概率$P(s’|s,a)$到达不同的下一个状态s，在这个过程中会得到及时奖励$R(s,a,s’)$，然后在s’里继续采取最优动作。

因此它实际上是一个大的非线性方程组，写出它就能知道最优的 Q 函数，这样就可以知道在任何状态下，每个动作的最优价值。

举个例子

假设有两个状态和两个动作${S_1,S_2}{A_1,A_2}$

则有$2\times 2=4$个未知数
$Q^(S_1,A_1)\quad Q^(S_1,A_2)\quad Q^(S_2,A_1)\quad Q^(S_2,A_2)$

最后即为关于$Q^(S_1,A_1),Q^(S_1,A_2),Q^(S_2,A_1),Q^(S_2,A_2)$的非线性方程组，解出它们，你就可以知道在每个状态下，哪一个动作最好。

怎么解？

    怎么解这个方程组呢？
    理论上，如果你知道所有可能的下一个状态 s' 和它们对应的概率 P，以及在状态s执行动作 a 转移到下一状态 s' 时的奖励 R 就可以联系起来，就像解二元一次方程一样。手工解这个方程组在规模比较大的场景下，就可以用计算机通过类似于值迭代的方式来进行迭代更新。
    但是在实际的强化学习中，直接求解它非常的困难。特别是在一些真实的场景中，我们一开始完全不知道状态转移概率 P，也不知道奖励函数 R 的完整分布，所以手工解就很难了。我们就可以使用 Q-learning 算法来迭代。

Q-Learning

求解他不需要知道概率P，也不需要知道奖励R，他会通过在环境中实际探索采样来学习。他会按照以下公式来更新Q的估计值。

$Q(s,a) \gets Q(s,a)+\alpha (r+\gamma \max_{a’}{Q(s’,a’)-Q(s,a)})$

它做了一个非常关键的简化，不计算期望，而是用实际观测到的样本来代替它。

当 Agent从状态s执行动作a，能让一个具体的奖励r和下一个状态s’之后，这个组合(s,a,r,s’) 就是对环境真实动态的一次采样。Q-learning进入这个样本计算目标值来更新 Q 值，这个目标值被称为TD目标。

$TD \quad Target=r+\gamma \max_{a’}{Q(s’,a’)}$

它和贝尔曼方程右侧方括号里面的部分长得几乎一模一样。这个r是对即时奖励R(s,a,s’) 的一次采样，$\max_{a’} Q(s’,a’)$ 是对下一个状态的最大未来价值。$\max_{a’}Q^*(s’,a’)$的当前估计。

Q_Learning的更新规则公式等价于这个公式，它不是一次性让 Q 直接等于新的目标值，而是采用了一种更平滑的增量式更新，这就是学习率 $\alpha$ 的作用。

左边的这一块是旧知识，右边的那一块是新的知识。学习率$\alpha$它控制了学习的步长。如果 $\alpha$ 很小的话，智能体学习得比较慢，会更相信过去的经验。如果 $\alpha$ 很大，智能体学习得很快，会更相信最近的这次采样。

Q-learning 算法的完整流程

1. 创建Q-table

   每一行表示的是每一个可能的状态，每一列表示的是所有的可能动作，需要对它进行初始化。常见的初始化就是所有的值都是零，表示在训练开始之前，智能体对任何动作的好坏一无所知。

2. 设置超参数

   分别是学习率 $\alpha$、折扣因子 $\gamma$、探索率和训练回合数。探索率是可选的，它是用于 $\epsilon-greedy$策略；训练回合数是指定智能体在环境中训练的总回合数。

3. 训练循环