10 January 2019

概述

深度学习最核心的是学一个策略 $\pi$,然后这个策略$\pi$对某一个环境的状态s,可以给出一个action a,然后a会导致状态发生迁移,并且这个时候,环境会给出一个奖励r。整个过程就是不断地寻找这个$\pi$,找个最好的或者相对好的,从而让奖励的期望值最大。

核心问题就是:

马尔科夫决策过程:

E=<X,A,P,R>四元组,原型已知,其中P、R:$P^a_{x->x’}$,$R^a_{x->x’}$,但是某个状态S的时候,应该采取哪个action:a,是由$a=\pi(S)$,也就是策略决定的。

给定策略 $π(a|s)$,马尔可夫决策过程的一个轨迹(trajectory) $τ = s_0,a_0,s_1,r_1,a_1,··· ,s_{T−1},a_{T−1},s_T ,r_T$ 的概率为

$p(τ) = p(s_0, a_0, s_1, a_1, · · · ) = p(s_0) \prod_{t=0}^{T-1} \pi(a_t|s_t) p(s_{t+1}|s_t,a_t)$

这部分:$p(s_{t+1}|s_t,a_t)$,其实就是 $\color{red}{游戏本身}$ 呀,你仔细想想,对不对,就是你当前在$s_t$,然后你做了一个action:$a_t$,然后这个概率怎么跳,是你这个agent无法控制的呀。

对于一个$\tau$,也就是一个游戏从头到尾的一个回合来说,这个总的成绩回报是:

  • 对于有限回合和无限回合两种:

$\gamma是折现因子,在[0,1]之间$

最终,本质是,让这个总和回$G(\tau)$的期望最大:

为何是期望呢?因为不同的$\tau$这个值是变动的,所以,用概率来求平均,就变成了期望。

本质上,算一个$G(\tau)$是一个树搜索问题,算$V(s1)$,就是算s1的时候,最多得分是s1a1s3a1这条路。

贝尔曼方程,看上去不好理解,其实就是个递归方程,要算的$V(S)$其实是对树往下的总得分的一个期望,他没法遍历树,就把$V(S)$表示成它的下一级S’的$V(S’)$的$\Sigma$求和。

值函数的作用

即使假设状态空间 S 和动作空间 A 都是离散且有限,策略空间也为$|A|^{|S|}$,可能会很大。策略$\pi$在这种离散情况下,其实就是一个映射表,从某个s->a。所以策略空间是一个排列组合的关系。(别忘了,是离散+有限情况下)

值函数可以看作是$\color{red}{对策略π的评估}$。如果在状态s,有一个动作a使得$Q_π(s,a) > V_π(s)$,说明执行动作a比当前的策略$π(a|s)$要好,我们就可以调整参数使得策略 $π(a|s)$ 的$\color{red}{概率增加}$。

Q-learning本质是学习最优的Q表,Q表就是最终的策略$\pi$。 怎么学,靠Value Iterator。

理解一个节点的V值

定义:策略 π 优于 π′(π ⩾ π′),如果对于有限状态集里的任意一个状态 s,不等式:$v_{π(s)} ⩾ v_{π′}(s)$ 成立。 这个很重要,是$\color{red}{每个状态S}$上,好策略都比旧策略的价值函数值$\color{red}都$大!

有个结论:(据说不好证明,只要知道结论就成了)

$\forall s, \pi^* = arg max_\pi V^\pi(s) $

对于任何马尔科夫决策过程,存在一个最优策略 π∗ 优于或至少不差于所 有其它策略。一个马尔科夫决策过程可能存在不止一个最优策略,但最优策略下的状态价值函数 均等同于最优状态价值函数:$v^\pi_* (s) = v_*(s)$;最优策略下的行为价值函数均等同于最优行为价值 函数:$q^\pi_* (s,a) = q_*(s,a)$。

这话有啥用呢?就是时候,你找到的最大的$v_*$的时候,那个时刻,对应的就是$v^\pi_*$,就能找到最好的$\pi$了呀。(*表示最大) 而$\pi$实际上是对应的每一个s呀,每一个s的$V(s)$都是最大,而,每一个$V(s)$又应该是这个s下对应的所有的action:a,里面最好的那一个。 那么, 你每次只要去找每个状态s下,最好的那个action:a。每个s下都找到了最优的a,那整个最优策略$\pi$不就相当于找到么!大概就是这么一个思路。这叫啥?值迭代?

这要是找最优策略$\pi^*$,挨个枚举$\pi$,然后挨个算一下这个$\pi$下,每个s的值函数$V(s)$,那不得死人啊。

策略迭代

依据新的策略 π′ 会得到一个新的价值函数,并产生新的贪婪策略,如此重复循环迭代将最 终得到最优价值函数 v∗ 和最优策略 π∗。

从一个初始策略 π 和初始价值函数V开始,基于该策略进行完整的价值评估过程得到一个新的价值函数,随后依据新的价值函数得到新的贪策略,随后计算新的贪婪策略下的价值函数,整个过程反复进行,在这个循环过程中$\color{red}{策略和价值函数均得到迭代更新}$,并最终收敛值最有价值函数和最优策略。除初始策略外,迭代中的策略均是依据价值函数的贪婪策略。

来源:https://blog.csdn.net/trillion_power/article/details/78934608 https://blog.csdn.net/qq_30615903/article/details/80762758

给一个例子:下图是一个叫Small Gridworld的例子,左上角和右下角是终点,γ=1,移动一步reward减少1,起始的random policy是朝每个能走的方向概率相同,先单独看左边一列,它表示在第k次迭代每个state上value function的值,这一列始终采用了random policy,这里的value function就是通过Bellman Expectation Equation得到的,考虑k=2的情况,-1.7 = -1.0 + 2*(1/3.0)(-1),-2.0 = -1.0 + 4(1/4.0)*(-1)。而右边一列就是在当前的value function情况下通过greedy算法找到当前朝哪个方向走更好。

策略评估就是计算任意策略的状态值函数$V_π$,也就是对当前策略下计算出每个状态下的状态值,这就是策略预估,我们也把它称为预测问题。他的计算方式参考之前我们提到过得状态值函数。

$V_\pi(s) = E_\pi[G_t|S_t=s]$

$V_\pi(s) = E_\pi[R_{t+1}+\gamma G_{t+1}|S_t=s]$

$V_\pi(s) = E_\pi[R_{t+1}+\gamma V(S_{t+1})|S_t=s]$

$V_\pi(s) = \sum_a\pi(a|s)\sum_{s’}P(s’|s,a)(R(s,a,s′)+γV_\pi(s′))$

因为是策略迭代所以此处的π(a|s)即为在 s 状态下选取 a 动作的可能,所以策略迭代的公式应该为

$V_{k+1}(s) = \sum_a\pi(a|s)\sum_{s’,r}P(s’,r|s,a)(r+γV_k(s′))$

k2=2时刻,第一行第二列的1.7怎么来的呢?

他的下个状态分别是坐标<1,1>,<1,3>,<2,2>,三个位置:

$-1.7 = -1.0 + 2*(1/3.0)(-1)$

参考这个公式:$V_{k+1}(s) = \sum_a\pi(a|s)\sum_{s’,r}P(s’,r|s,a)(r+γV_k(s′))$

  • -1.0是k=1时刻<1,2>这个位置的rewords,注意是当前状态的,也就是<1,2>的得分
  • 1/3是<1,2>向3个方向转移的概率,即$\pi(a|s)$
  • 这个时候的$P(s’|s,a)=1$,因为,一个状态经过某个动作(往左、往右、往上、往下)跳到下一个状态是100%确定的
  • 3个位置 <1,1>,<1,3>,<2,2>,k=1时刻的,状态值函数的值为0,-1,-1。
  • 所以最终的$V_{k=2}(S_{1,2})= $

这篇的例子足够清晰,建议看一下:

https://blog.csdn.net/hold_on_me/article/details/81713173

状态迁移:

	self.v_states[state] = reward + self.gamma * self.v_states[next_state]

action的选择:

	def policy_evaluate(self):
		action = self.states_policy_action[state]

为什么会收敛,参考资料叶强的《 强化学习入门——从原理到实践》p36给出证明

价值迭代

如果一个 策略不能在当前状态下产生一个最优行为,或者这个策略在针对当前状态的后续状态时不能产生一个最优行为,那么这个策略就不是最优策略。与价值函数对应起来,可以这样描述最优化原则:一个策略能够获得某状态s的最优价值当且仅当该策略也同时获得状态s所有可能的后续状态s′的最优价值。

Q-learning和策略迭代区别?

Q-learning是

参考资料

一些概念

概念实在是太多了,列出来:

  • 策略迭代(Policy Iteration)
  • 值迭代 (Value Iteration)
  • 策略梯度(Policy Gradient)
  • 基于模型(Model based)
  • 模型无关(Model free)
  • 探索与开发(Exploreation-Exploitation)
  • 马尔可夫过程(Markov Process):具备马尔科夫性质的序列$p(s_{t+1}|s_t, … , s_0) = p(s_{t+1}|s_t)$
  • 马尔科夫决策过程(MDP - Markov Decision Process):在马尔可夫过程中 加入一个额外的变量:动作 a,$p(s_{t+1}|s_t, a_t, · · · , s_0, a_0) = p(s_{t+1}|s_t, a_t)$
  • 确定性策略(Deterministic Policy):就是张确定的s->a的确定表,当前s,做了某个a,去哪个s’
  • 随机性策略(Stochastic Policy):是个概率,s->a->s’,这个s’不是确定的,是个归一化概率
  • 轨迹(Trajectory)
  • 值函数(Value Function)
  • 状态值函数(V(s)) - V函数
  • 状态-动作值函数(Q(s,a))- Q函数
  • 动态规划算法
  • 策略评估(policy evaluation)
  • 策略改进(policy improvement)
  • 蒙特卡罗方法
  • 同策略(on policy)
  • 异策略(off policy)
  • 时序差分学习(temporal-difference learning) - TD
  • 贝尔曼方程
  • 贝尔曼最优方程
  • ε-贪心法
  • SARSA算法(State Action Reward State Action,SARSA)
  • Q学习(Q-Learning)算法
  • 深度Q网络(deep Q-networks,DQN)
  • 经验回放(experience replay)
  • 目标网络冻结(freezing target networks)
  • 策略梯度(policy gradient)
  • REINFORCE算法
  • 带基准线的 REINFORCE 算法
  • Actor-Critic 算法
  • A2C算法(Advantage Actor-Critic,A2C)
  • A3C算法(Asynchronous Advantage Actor-Critic,A3C)

书系列

视频资料

别人提供的资源

这些都是别人提供的一些DRL的各类资源汇总: