强化学习之Q-Learing基础

马尔可夫决策过程MDP

MDP 是一个离散时间随机控制过程。MDP提供了用于建模决策问题的数学框架，在该决策中，结果是部分随机的，并且受决策者或代理商的控制。MDP对于研究可以通过动态编程和强化学习技术解决的优化问题很有用。

• 通常MDP可以用这样的元组来定义:
  $(S,A,p,r)$:
  • S:state set 状态集合
  • A:action set动作集合
  • p:状态s通过动作a转化为a’的转移概率，又称状态转移概率
  • r:动作a执行后立即获得的奖励。

我们把π表示为一个“策略policy”，它是从一个状态s到一个动作a的映射。

MDP的目标就是找到一个最优的策略$π^*$，使奖励函数最大化
${\max }_{\pi } \mathbb {E} \left[{ {\sum _{t=0}^{T}} r_{t}(s_{t},\pi (s_{t})) }\right]$
最优策略$π^*$ 可以作为一个”黑匣子“，也可以比作是机器学习中训练好的模型，通过下一时刻输入的状态$s_t$就可以根据其内部映射(s->a)将应该采取的动作给求出来
$a_{t} = \pi (s_{t})$

1)部分可观察马尔可夫决策过程POMDPs

在MDPs中，我们假设系统状态完全可以被代理观察到。然而，在很多情况下，agent只能观察系统的一部分状态，因此部分可观察的马尔可夫决策过程(POMDPs)也常用于在通信中建模决策问题。

典型的POMDP模型由6-tuple定义:
$(S,A,P,R,\Omega,O,\gamma)$

• Ω 是一组观察结果集，就是代理的传感器获得的环境数据；
• O 是条件观察概率，就是代理在观察到环境数据 o 时，有多大概率确定自己处于状态s
• γ∈[0,1]是折扣因子。决定了最近的收益和未来的收益哪个对机器人影响更大
• γ=0 表示机器人只关心下一次行动中选择哪个动作可以获得最大收益，因为之后的动作收益均为0；
• γ=1 表示机器人更关心接下来所有动作的收益和。

算法工作流程：

(1) 在每个时间段 T内，代理agent的当前状态是s，根据其对当前状态s的置信度b(s)(条件观察概率)选择动作a

(2) 基于对当前状态b(s)的观察o及其置信度，代理随后更新其对新状态s′的置信度即b(s′):

• $b\left( s' \right) =\frac{\mathcal{O}\left( o|s,a,s' \right) \sum_{s\in \mathcal{S}}{p}\left( s'|s,a \right) b\left( s \right)}{\sum_{s'\in \mathcal{S}}{\mathcal{O}}\left( o|s,a,s' \right) \sum_{s\in \mathcal{S}}{p}\left( s'|s,a \right) b\left( s \right)}$

  • $\mathcal {O} (o|s,a,s')$ ： agent在状态s处执行动作a，其状态转移到了s′，然后在状态s’下的agent获得观测值o的概率

(3) 与MDP模型相似，POMDP中的agent也致力于寻找最优策略$π^*$ ，以使其期望的长期折扣报酬
${\sum _{t=0}^{\infty }} \gamma r_{t}(s_{t},\pi ^{*}(s_{t}))$
最大化.

2）Markov Games：

定义：

在博弈论中，马尔可夫博弈或随机博弈是一种动态游戏，具有多个参与者（即ML代理）进行的概率转变。典型的马尔可夫博弈模型由如下元组定义:
$(\mathcal {I}, \mathcal {S}, \{\mathcal {A}^{i}\}_{i\in \mathcal {I}}, p, \{r^{i}\}_{i\in \mathcal {I}})$

• $\mathcal {I} \triangleq \{1,\ldots,i,\ldots,I\}$是一组代理(agents set)
• $\mathcal {S} \triangleq \{ \mathcal {S}^{1}, \ldots, \mathcal {S}^{i}, \ldots, \mathcal {S}^{I} \}$是所有代理的全局状态空间 $S^i$是代理i的状态空间
• $\{\mathcal {A}^{i}\}_{i\in \mathcal {I}}$是agents的动作空间集合，$A^i$是agent_i的动作空间
• $p \triangleq \mathcal {S} \times \mathcal {A}^{1} \times \cdots \times \mathcal {A}^{I} \rightarrow [{0,1}]$是系统的转移概率函数。
• $\left\{ r^i \right\} _{i\epsilon \boldsymbol{I}}\triangleq \mathcal{S}\times \mathcal{A}^1\times \cdots \times \mathcal{A}^I\rightarrow \mathbb{R}$是agents的收益函数，即$agent_i$执行了所有动作后获得的回报

解释

在Markov博弈中，代理从初始状态$s_0∈S$开始。在观察当前状态之后，所有的代理同时选择他们的行为$a=\{a^1，…，a^I\}$，他们将获得相应的奖励和他们自己的新观察。同时，系统将以概率$p(s′|s,a)$ 跃迁到一个新的状态$s′∈S$。该过程在新状态下重复，并持续有限或无限个阶段。在这个博弈中，所有的代理都试图找到他们的最优策略来最大化他们自己期望的长期平均回报，即
${\sum _{t=0}^{\infty }} \gamma _{i} r^{i}_{t}(s_{t},\pi _{i}^{*}(s_{t}))$
这个博弈中的所有最优策略，即
$\{\pi ^{*}_{1},\ldots,\pi ^{*}_{I}\}$
的集合，已知为该博弈的均衡。如果存在有限个参与者，并且状态集和动作集是有限的，那么马尔可夫博弈在有限个阶段下总是具有纳什均衡。对于具有无限阶段的Markov博弈也是如此，但是代理的总回报是贴现和(discounted sum)。

贴现和是总回报与折扣因子$\gamma$作用的结果

总结

MDP模型是为了解决机器人轨迹规划中动作带来结果的不确定性的问题，POMDP模型是为了解决机器人轨迹规划中对环境观测的不确定性的问题。

POMDP模型就是多了一步对机器人当前所处状态的判断，因为在实际问题中，机器人对环境的观测是有局限性的，不准确的；所以根据环境观测信息来判断自己的状态也是有偏差的，这种偏差用概率来表示就是机器人有对自己目前所处状态的可信度有多大。

强化学习之Q-Learning

强化学习是机器学习的一个重要分支，是解决MDP问题的有效工具，在文献中得到了广泛的应用。在强化学习过程中，agent可以通过与环境的交互来学习其最优策略。

具体而言，如图（a）所示，代理首先观察其当前状态state，然后采取动作action，并接收其即时奖励reward以及其新状态new state。所观察到的信息，即即时奖励和新状态，被用来调整代理的策略policy，并且这个过程将被重复，直到代理的策略接近最优策略为止。在强化学习中，Q-学习是最有效的方法，在文献中得到了广泛的应用。在下面，我们将讨论Q-学习算法及其对高级MDP模型的扩展。

a）强化学习，（b）人工神经网络和（c）深度Q学习

在MDP中，我们的目标是找到一个最优策略$π^*：S→A$，使系统的长期报酬函数期望最大化。因此，我们首先定义了值函数$V^π：S→R$，它表示通过按照策略π从每个状态s∈S获得的期望值。策略π的价值函数$V^{\pi}$通过infinite horizon and discounted MDP来量化策略π的价值，可以表示如下：
$\mathcal{V}^{\pi}\left( s \right) =\mathbb{E}_{\pi}\left[ \sum_{t=0}^{\infty}{\gamma}r_t\left( s_t,a_t \right) |s_0=s \right] =\mathbb{E}_{\pi}\left[ r_t\left( s_t,a_t \right) +\gamma \mathcal{V}^{\pi}\left( s_{t+1} \right) |s_0=s \right]$
由于我们的目标是寻找最优策略π*，所以通过
$\mathcal {V}^{*}(s) = \max \limits_{a_{t}} \{ \mathbb {E}_{\pi }[r_{t}(s_{t},a_{t}) + \gamma \mathcal {V}^{\pi }(s_{t+1})] \}$
表示的最优值函数可以找到每个状态下的最优作用。

定义$\mathcal {Q}^{*}(s,a) \triangleq r_{t}(s_{t},a_{t}) + \gamma \mathbb {E}_{\pi } [\mathcal {V}^{\pi }(s_{t+1})]$ 作为所有state-action pair（状态-动作对）的最优Q-funcation，那么最优值函数就可以定义为$\mathcal {V}^{*}(s) = \max \limits_{a} \{ \mathcal {Q}^{*}(s,a) \}$ ,现在，问题被简化为寻找所有state-action pair对应的Q-function的最优值，即$Q^∗(s,a)$，这可以通过迭代过程来实现:
$\mathcal{Q}_{t+1}\left( s,a \right) =\mathcal{Q}_t\left( s,a \right) +\alpha _t\left[ r_t\left( s,a \right) +\gamma \max_{a'}\mathcal{Q}_t\left( s,a' \right) -\mathcal{Q}_t\left( s,a \right) \right]$

这个迭代过程的核心思想就是找出预测的$Q$- value即$r_{t}(s,a) + \gamma \max \limits_{a'} \mathcal {Q}_{t}(s,a')$与其当前的Q-value$\mathcal {Q}_{t}(s,a)$之间的时间差（TD)。其中$\alpha _{t}$(学习率)被用来决定新的环境信息对现有Q-value的影响程度。学习率可以选择为常数，也可以在学习过程中动态调整。然而，它必须满足假设1才能保证Q-学习算法的收敛性。

Assumption 1:

学习率(步长)$\alpha _{t}$是确定的，非负的，并且满足以下条件：
$\alpha _{t} \in [{0,1}]$
${\sum _{t=0}^{\infty }} \alpha _{t} = \infty$
${\sum _{t=0}^{\infty }} (\alpha _{t})^{2} < \infty$

步长自适应$α_t=1/t$是强化学习中最常用的例子之一。算法1给出了Q-学习算法的细节。

Algorithm 1 The Q -Learning Algorithm:

对于每个状态动作对(s,a)，初始化Q-value表条目 Q（s，a) 如为零。观察当前状态s ，为学习率$\alpha$和折扣系数 $γ$ 初始化一个值

for t:=1 to T do

从当前状态-动作对(s,a)，执行动作a 并立即获得奖励 r 和一个新的状态 s′ 。

基于状态 s′ 选择一个动作 a' 然后更新Q值表条目Q(s,a) 如下：
$\mathcal{Q}_{t+1}\left( s,a \right) \gets \mathcal{Q}_t\left( s,a \right) +\alpha _t\left[ r_t\left( s,a \right) +\gamma \max_{a'}\mathcal{Q}_t\left( s',a' \right) -\mathcal{Q}_t\left( s,a \right) \right]$
更新状态Replace s←s′

end for
$\pi ^{*}(s)=\arg \max _{a} \mathcal {Q}^{*}(s,a)$

一旦所有的Q-value收敛或达到一定的迭代次数，算法将终止。然后，该算法产生的最佳策略就可以用于指导DRL代理（机器人）在每种状态下要采取的措施，使得对于状态空间的所有状态的$\mathcal {Q}^{*}(s,a)$最大化，即 $\pi ^{*}(s)=\arg \max \limits_{a} \mathcal {Q}^{*}(s,a)$。

值得注意的是，与值函数$\mathcal {V}^{\pi }$不同,Q函数是无模型学习算法的一个示例，该算法不需要代理(agent,可以理解为机器人)预先知道系统模型参数（例如状态转换和奖励模型）即可预先估计(state-action)所对应的value。具体来说，Q函数的核心思想是通过与环境相互作用过程中获得的样本来逼近状态-动作对的值。此外，当值函数根据策略π取所有动作的期望值时，Q函数只关注特定状态下的特定动作。因此，使用Q函数的学习算法比使用值函数的学习算法复杂。然而，从抽样的角度来看，Q函数的维数高于值函数的维数，因此Q函数可能更难获得足够多的样本，即状态-动作对。因此，如果系统模型预先可用，则值函数通常更可取。

互作用过程中获得的样本来逼近状态-动作对的值。此外，当值函数根据策略π取所有动作的期望值时，Q函数只关注特定状态下的特定动作。因此，使用Q函数的学习算法比使用值函数的学习算法复杂。然而，从抽样的角度来看，Q函数的维数高于值函数的维数，因此Q函数可能更难获得足够多的样本，即状态-动作对。因此，如果系统模型预先可用，则值函数通常更可取。

还有一篇个人觉得讲的不错的博客