上海浦东注册公司湖南企业竞价优化
强化学习算法总结 2
4.动态规划
待解决问题分解成若干个子问题，先求解子问题，然后得到目标问题的解
需要知道整个状态转移函数和价值函数，状态空间离散且有限
- 策略迭代：
- 策略评估:贝尔曼期望方程来得到一个策略的 V ( s ) V(s) V(s)
- 策略提升:
- 价值迭代
4.1 策略迭代算法
- 策略评估
V ( S ) = ∑ a π ( a ∣ s ) Q ( s , a ) = ∑ a π ( a ∣ s ) ( r ( a , s ) + γ ∑ s P ( s ′ ∣ s , a ) V π ( S ′ ) ) V(S) = \sum_a \pi(a|s)Q(s,a) = \sum_a \pi(a|s)(r(a,s)+ \gamma\sum_s P(s'|s,a)V^\pi(S')) V(S)=a∑π(a∣s)Q(s,a)=a∑π(a∣s)(r(a,s)+γs∑P(s′∣s,a)Vπ(S′))
知道状态转移函数和未来状态价值就可以估计当前的状态：我们只需要求解 V ( s ) V(s) V(s)
这里就是利用贝尔曼方程，来不断地更新 V ( s ) V(s) V(s),
V ( S ) k + 1 = ∑ a π ( a ∣ s ) Q ( s , a ) = ∑ a π ( a ∣ s ) ( r ( a , s ) + γ ∑ s P ( s ′ ∣ s , a ) V k ( S ′ ) ) V(S)^{k+1} = \sum_a \pi(a|s)Q(s,a) = \sum_a \pi(a|s)(r(a,s)+ \gamma\sum_s P(s'|s,a)V^k(S')) V(S)k+1=a∑π(a∣s)Q(s,a)=a∑π(a∣s)(r(a,s)+γs∑P(s′∣s,a)Vk(S′))
-
策略提升
只要当前状态下的策略的得到的状态动作函数比 V ( S ) V(S) V(S)高一些
π ′ ( s ) = a r g m a x a Q π ( s , a ) \pi'(s) = argmax_aQ^\pi(s,a) π′(s)=argmaxaQπ(s,a) -
策略迭代
π 0 策略评估 V π 0 （ S ）策略提升 π 1 \pi^0 策略评估 V\pi_0（S）策略提升 \pi^1 π0策略评估Vπ0（S）策略提升π1
- 代码
- 策略评估
w h i l e max > θ d o : m a x = 0 f o r s i n r a n g e ( S ) : v = V ( s ) （所有 Q ( s , a ）求和 ) V ( S ) = ( b e l l m a n f u c t i o n ) m a x = m a x ( m a x , V ( s ) − v ) while \ \max \ >\theta \ do: \\ \ max = 0 \\ \ for \ s \ in \ range(S):\\ \ v = V(s)（所有Q(s,a）求和)\\ \ V(S) = (bellman fuction)\\ \ max = max(max,V(s) - v) while max >θ do: max=0 for s in range(S): v=V(s)（所有Q(s,a）求和) V(S)=(bellmanfuction) max=max(max,V(s)−v)
* 策略提升
f o r s i n S ： π ( s ) = a r g m a x ( Q ( s , a ) ) for\ s\ in\ S：\\ \pi (s) = argmax(Q(s,a)) for s in S：π(s)=argmax(Q(s,a))
4.2 价值迭代算法
V k + 1 ( s ) = m a x a { r ( s , a ) + γ ∑ s P V k } V^{k+1}(s) = max_a\{ r(s,a)+\gamma\sum_sPV^k\} Vk+1(s)=maxa{r(s,a)+γs∑PVk}
可以理解为只执行一轮的策略迭代算法
5 时序差分算法
在数据分布未知的情况下来对模型进行更新，通过智能体与环境的交互进行学习。无模型的强化学习。
- 在线强化学习：使用当前策略下采样得到的数据进行学习
- 离线强化学习：使用经验回访池
5.1 时序差分
V ( S t ) = V ( s t ) + α [ G t − V ( s t ) ] V(S_t) = V(s_t) +\alpha[G_t - V(s_t)] V(St)=V(st)+α[Gt−V(st)]
G t G_t Gt表示整个序列采集结束之后，得到的回报。而很多时候我们是没有办法
V ( s t ) + = α [ r t + γ V ( s t + 1 ) − V ( s t ) ] V(s_t) += \alpha[r_t + \gamma V(s_{t+1}) -V(s_t) ] V(st)+=α[rt+γV(st+1)−V(st)]
用时序差分法估计到了状态价值函数 V ( s ) V(s) V(s)
5.2 SARSA
Q ( s , a ) + = α [ r ( s , a ) + γ Q ( s , a ) − Q ( s , a ) ] Q(s,a) += \alpha[r(s,a) + \gamma Q(s,a) - Q(s,a)] Q(s,a)+=α[r(s,a)+γQ(s,a)−Q(s,a)]
$$
\begin{equation}
\pi(a|s)=\left{
\begin{aligned}
argmax(Q(s,a))& \ & if \ prob < \ 1- \epsilon \
random & \ & \
\end{aligned}
\right.
\end{equation}
$$
5.3 多步Sarsa
MC方法是无偏估计但是方差比较大
TD 是有偏估计，因为每一个对下一个状态的价值都是估计的
Q ( s t , a t ) + = α [ r t + γ Q ( s t + 1 ) + γ 2 Q ( s t + 2 ) + γ 3 Q ( s t + 3 ) . . . − Q ( s , a ) ] Q(s_t,a_t)+= \alpha[ r_t + \gamma Q(s_{t+1}) + \gamma^2 Q(s_{t+2})+ \gamma^3 Q(s_{t+3})... -Q(s,a) ] Q(st,at)+=α[rt+γQ(st+1)+γ2Q(st+2)+γ3Q(st+3)...−Q(s,a)]
代码实现上，是前几次不执行只是进行数据的收集，第n次开始进行多步Sarsa
5.4 Q-learning
Q ( s , a ) + = α [ r ( s , a ) + γ m a x a Q ( s , a ) − Q ( s , a ) ] Q(s,a) += \alpha[r(s,a) + \gamma max_aQ(s,a) - Q(s,a)] Q(s,a)+=α[r(s,a)+γmaxaQ(s,a)−Q(s,a)]
Q-learning的时序差分算法在算下一个状态的Q的时候会取最大的那个
Sarsa会先 ϵ − g r e e d y \epsilon -greedy ϵ−greedy 选择s，a然后计算TD_error,然后估计Q(s’,a’)(比如放在环境中跑一下）
Q-learning next_s和a之后，会找到最大的Q(s’,a’),不依赖于 ϵ − g r e e d y \epsilon -greedy ϵ−greedy 的a
-
在线策略算法和离线策略算法
在线策略算法：行为策略（采样数据的策略）和 目标策略（用于更新的策略）是同一个策略
离线策略算法：行为策略和目标策略并不是同一个策略
7 DQN算法
Q网络的损失函数
w ∗ = a r g m i n w 1 2 N ∑ i = 1 N [ r i + γ m a x i Q w ( s i ′ , a ′ ) − Q w ( s i , a i ) ] w^* = argmin_w \frac{1}{2N}\sum_{i=1}^N[r_i+\gamma max_i Q_w(s'_i,a') - Q_w(s_i,a_i)] w∗=argminw2N1i=1∑N[ri+γmaxiQw(si′,a′)−Qw(si,ai)]
-
经验回放
制作一个数据回放缓冲区，每次环境中得到的<s,a,r,s’>都进行存放
-
目标网络
采用TD_error作为我们的误差，但是包含着网络的输出，所以在更新网络参数的时候，目标也在不断地更新
因为优化目标是让
Q → r + γ m a x Q ( s ′ + a ′ ) Q \rightarrow r+\gamma max Q(s'+a') Q→r+γmaxQ(s′+a′)