建设共享经济网站的可行性/网站推广和网站优化

前言

之前在【强化学习】09——价值和策略近似逼近方法中讨论过使用参数$\theta$来近似价值函数$V$或状态价值函数$Q$$$\begin{array}{rl}{V}_{\theta }(s)& \approx V^{\pi }(s)\\ Q_{\theta }(s,a)& \approx Q^{\pi }(s,a)\end{array}$$之后，再通过价值函数推导出相应的策略（比如利用$ϵ$-贪婪策略）。

本节将主要讨论直接参数化策略的方法${\pi }_{\theta }(s,a)$。策略可以是确定性的——$a={\pi }_{\theta }(s)$，也可以是随机的——${\pi }_{\theta }(s,a)=\mathbb{P}[a\mid s,\theta ]$。通过参数化策略可以将可见的已知状态泛化到未知的状态上。在本节中我们主要讨论的是模型无关的强化学习。

强化学习算法主要可以分为基于价值函数(Value-Based)的、基于策略的(Policy-Based)以及基于Actor-Critic（后文会进行介绍）框架的。

三者区别如下表所示：

Methods	Value	Policy
Value Based	学习到的价值函数	隐式的策略，如$ϵ$-贪婪策略
Policy Based	没有价值函数	学习到的策略
Actor-Critic	学习到的价值函数	学习到的策略

策略梯度

基于策略的强化学习的优缺点

优点

• 具有更好的收敛性质
• 在高维度或连续的动作空间中更有效
  • 这是最重要的因素：基于值函数的方法，通常需要取最大值
• 能够学习出随机策略

缺点

• 通常会收敛到局部最优而非全局最优（基于值函数的方法也可能出现）
• 评估一个策略通常不够高效并具有较大的方差（variance）

Example:Aliased Gridworld

• 智能体无法区分灰色部分的格子
• 移动方向N, E, S, W

对于一个确定性的策略，可能会出现以下情况：

• 在灰色区域同时向W方向移动
• 或在灰色区域同时向E方向移动

因此，就无法抵达终点，获得奖励。基于价值函数的策略是近于确定性的策略（greedy or $ϵ$-greedy），因此会在上面的区域经过很长的时间才可能获得奖励。

对于随机性的策略，在灰色区域向W或E方向移动的概率五五开。$$\begin{array}{rl}{\pi }_{\theta }(\text{wall to N and S, move E})& =0.5\\ {\pi }_{\theta }(\text{wall to N and S, move W})& =0.5\end{array}$$随机性的策略很有可能在几步内达到目标状态。基于策略的方法可以学习到最优的随机性策略。

策略目标函数

目标：给定策略${\pi }_{\theta }(s,a)$，找到最优的$\theta$。以下为几种衡量策略${\pi }_{\theta }(s,a)$质量的方法：

• 在离散episodic的环境中使用起始价值（start value）：$$J_1(\theta )=V^{{\pi }_{\theta }}(s_1)={\mathbb{E}}_{{\pi }_{\theta }}\left[v_1\right]$$
• 在连续 continuing的环境中使用平均价值（average value）：$$J_{avV}(\theta )=\sum _s{d}^{{\pi }_{\theta }}(s)V^{{\pi }_{\theta }}(s)$$
• 或者是每步的平均奖励average reward per time-step：$$J_{avR}(\theta )=\sum _s{d}^{{\pi }_{\theta }}(s)\sum _a{\pi }_{\theta }(s,a)R_s^a$$
• ${\pi }_{\theta }$服从$d^{{\pi }_{\theta }}(s)$分布

策略优化

基于策略的强化学习本质是一个优化问题，对于目标函数$J(\theta )$，找到合适的$\theta$，使得目标函数最大化。

• 未使用梯度的方法
  • Hill climbing
  • Simplex / amoeba / Nelder Mead
  • Genetic algorithms
• 使用梯度的方法
  • Gradient descent
  • Conjugate gradient
  • Quasi-newton
    在本节中，主要讨论基于梯度下降的方法。

策略梯度

同样的，对于目标函数$J(\theta )$，策略梯度算法需要通过不断提升策略的梯度以找到$J(\theta )$的局部最大值，$\Delta \theta =\alpha {\nabla }_{\theta }J(\theta )$。其中${\nabla }_{\theta }J(\theta )$为策略梯度$${\nabla }_{\theta }J(\theta )=\left(\begin{array}{c}\frac{\partial J(\theta )}{\partial {\theta }_1}\\ ⋮\\ \frac{\partial J(\theta )}{\partial {\theta }_n}\end{array}\right)$$

利用有限差分计算策略梯度

• 对于维度$k\in [1,n]$
  • 估计滴$k$维上目标函数$J(\theta )$对$\theta$的偏微分
  • 引入偏移量$ϵu_k$，用差分近似微分。其中$u_k$是单位向量，第$k$个分量中为1，其他分量中为0.$$\frac{\partial J(\theta )}{\partial {\theta }_k}\approx \frac{J(\theta +ϵu_k)-J(\theta )}{ϵ}$$
• 简单、噪声大、效率低，但有时有效
• 适用于任意策略，即使策略不可微分

得分函数和似然比

似然比（Likelihood ratios）利用下列特性$$\begin{array}{rl}{\nabla }_{\theta }{\pi }_{\theta }(s,a)& ={\pi }_{\theta }(s,a)\frac{{\nabla }_{\theta }{\pi }_{\theta }(s,a)}{{\pi }_{\theta }(s,a)}\\ & ={\pi }_{\theta }(s,a){\nabla }_{\theta }\log {\pi }_{\theta }(s,a)\end{array}$$其中，${\nabla }_{\theta }\log {\pi }_{\theta }(s,a)$是得分函数（score function）

考虑一个简单的单步马尔可夫决策过程

• 起始状态为𝑠~𝑑(𝑠)
• 决策过程在进行一步决策后结束，获得奖励值为$r={\mathcal{R}}_{s,a}$

所以策略的价值期望可以写成$$\begin{array}{rl}J(\theta )& ={\mathbb{E}}_{{\pi }_{\theta }}\left[r\right]\\ & =\sum _{s\in \mathcal{S}}d(s)\sum _{a\in \mathcal{A}}{\pi }_{\theta }(s,a){\mathcal{R}}_{s,a}\\ {\nabla }_{\theta }J(\theta )& =\sum _{s\in \mathcal{S}}d(s)\sum _{a\in \mathcal{A}}{\nabla }_{\theta }{\pi }_{\theta }(s,a)\\ & =\sum _{s\in \mathcal{S}}d(s)\sum _{a\in \mathcal{A}}{\pi }_{\theta }(s,a){\nabla }_{\theta }\log {\pi }_{\theta }(s,a){\mathcal{R}}_{s,a}\\ & ={\mathbb{E}}_{{\pi }_{\theta }}\left[{\nabla }_{\theta }\log {\pi }_{\theta }(s,a)r\right]\end{array}$$

这一结果可以通过从$d(s)$中采样状态$s$和从${\pi }_{\theta }$中采样动作𝑎来近似估计

策略梯度定理

策略梯度定理把似然比的推导过程泛化到多步马尔可夫决策过程.用长期的价值函数 $Q^{{\pi }_{\theta }}(s,a)$代替前面的瞬时奖励 $r={\mathcal{R}}_{s,a}$。策略梯度定理涉及起始状态目标函数 $J_1$，平均奖励目标函数$J_{avR}$ ，和平均价值目标函数$J_{avV}$.
定理
对任意可微的策略${\pi }_{\theta }(s,a)$，任意策略的目标函数$J_1，J_{avR}，J_{avV}$，其策略梯度是$${\nabla }_{\theta }J(\theta )={\mathbb{E}}_{{\pi }_{\theta }}[{\nabla }_{\theta }\log {\pi }_{\theta }(s,a)Q^{{\pi }_{\theta }}(s,a)]$$这种形式也是$$\frac{\partial J(\theta )}{\partial \theta }={\mathbb{E}}_{{\pi }_{\theta }}\left[\frac{\partial \log {\pi }_{\theta }(a|s)}{\partial \theta }{Q}^{{\pi }_{\theta }}(s,a)\right]$$

详细证明过程请参考:

1. Rich Sutton’s Reinforcement Learning: An Introduction (2nd Edition)第13章
2. 动手学强化学习策略梯度的附录

蒙特卡洛策略梯度（Monte-Carlo Policy Gradient）

• 利用随机梯度上升更新参数
• 利用策略梯度定理
• 利用累计奖励值$G_t$作为 $Q^{{\pi }_{\theta }}(s,a)$的无偏采样$$\Delta {\theta }_t=\alpha \frac{\partial \log {\pi }_{\theta }(a_t|s_t)}{\partial \theta }{G}_t$$

REINFORCE算法伪代码

Puck World Example

• 连续的动作对冰球施加较小的力
• 冰球接近目标可以得到奖励
• 目标位置每30秒重置一次
• 使用蒙特卡洛策略梯度方法训练策略

Softmax随机策略

对于具体策略的设计，通常使用Softmax随机策略。Softmax策略是一种非常常用的随机策略$${\pi }_{\theta }(a|s)=\frac{e^{f_{\theta }(s,a)}}{{\sum }_{a^{\prime }}{e}^{f_{\theta }(s,a^{\prime })}}$$式中，$f_{\theta }(s,a)$是用𝜃参数化的状态-动作对得分函数，可以预先定义。其对数似然的梯度是$$\begin{array}{c}\frac{\partial \text{log}{\pi }_{\theta }(a|s)}{\partial \theta }\begin{array}{r}=\frac{\partial f_{\theta }(s,a)}{\partial \theta }-\frac{1}{{\sum }_{a^{\prime }}{e}^{f_{\theta }(s,a^{\prime })}}\sum _{a^{\prime \prime }}{e}^{f_{\theta }(s,a^{\prime \prime })}\frac{\partial f_{\theta }(s,a^{\prime \prime })}{\partial \theta }\end{array}\\ =\frac{\partial f_{\theta }(s,a)}{\partial \theta }-{\mathbb{E}}_{a^{\prime }\sim {\pi }_{\theta }(a^{\prime }|s)}\left[\frac{\partial f_{\theta }(s,a^{\prime })}{\partial \theta }\right]\end{array}$$

举线性得分函数为例，则有$$\begin{array}{rl}& f_{\theta }(s,a)={\theta }^{\mathrm{T}}x(s,a)\\ \frac{\partial \text{log}{\pi }_{\theta }(a|s)}{\partial \theta }& =\frac{\partial f_{\theta }(s,a)}{\partial \theta }-{\mathbb{E}}_{a^{\prime }\sim {\pi }_{\theta }(a^{\prime }|s)}\left[\frac{\partial f_{\theta }(s,a^{\prime })}{\partial \theta }\right]\\ & =x(s,a)-{\mathbb{E}}_{a^{\prime }\sim {\pi }_{\theta }(a^{\prime }|s)}[x(s,a^{\prime })]\end{array}$$

代码实践

class PolicyNet(torch.nn.Module):def __init__(self, state_dim, hidden_dim, action_dim):super(PolicyNet, self).__init__()self.fc1 = torch.nn.Linear(state_dim, hidden_dim)self.fc2 = torch.nn.Linear(hidden_dim, action_dim)def forward(self, x):x = F.relu(self.fc1(x))return F.softmax(self.fc2(x), dim=1)class REINFORCE:def __init__(self, state_dim, hidden_dim, action_dim, learning_rate, gamma,device, numOfEpisodes, env):self.policy_net = PolicyNet(state_dim, hidden_dim, action_dim).to(device)self.optimizer = torch.optim.Adam(self.policy_net.parameters(), lr=learning_rate)self.gamma = gammaself.device = deviceself.env = envself.numOfEpisodes = numOfEpisodes# 根据动作概率分布随机采样def takeAction(self, state):state = torch.tensor(np.array([state]), dtype=torch.float).to(self.device)action_probs = self.policy_net(state)action_dist = torch.distributions.Categorical(action_probs)action = action_dist.sample()return action.item()def update(self, transition_dict):reward_list = transition_dict['rewards']state_list = transition_dict['states']action_list = transition_dict['actions']G = 0self.optimizer.zero_grad()for i in reversed(range(len(reward_list))):reward = reward_list[i]state = torch.tensor(np.array([state_list[i]]), dtype=torch.float).to(self.device)action = torch.tensor(np.array([action_list[i]]), dtype=torch.int64).view(-1, 1).to(self.device)log_prob = torch.log(self.policy_net(state).gather(1, action))G = self.gamma * G + rewardloss = -log_prob * G  # 每一步的损失函数loss.backward()  # 反向传播计算梯度self.optimizer.step()  # 梯度下降def REINFORCERun(self):returnList = []for i in range(10):with tqdm(total=int(self.numOfEpisodes / 10), desc='Iteration %d' % i) as pbar:for episode in range(int(self.numOfEpisodes / 10)):# initialize statestate, info = self.env.reset()terminated = Falsetruncated = FalseepisodeReward = 0transition_dict = {'states': [],'actions': [],'next_states': [],'rewards': [],'terminateds': [],'truncateds':[]}# Loop for each step of episode:while (not terminated) or (not truncated):action = self.takeAction(state)next_state, reward, terminated, truncated, info = self.env.step(action)if terminated or truncated:breaktransition_dict['states'].append(state)transition_dict['actions'].append(action)transition_dict['next_states'].append(next_state)transition_dict['rewards'].append(reward)transition_dict['terminateds'].append(terminated)transition_dict['truncateds'].append(truncated)state = next_stateepisodeReward += rewardself.update(transition_dict)returnList.append(episodeReward)if (episode + 1) % 10 == 0:  # 每10条序列打印一下这10条序列的平均回报pbar.set_postfix({'episode':'%d' % (self.numOfEpisodes / 10 * i + episode + 1),'return':'%.3f' % np.mean(returnList[-10:])})pbar.update(1)return returnList

结果

可以看到，随着收集到的轨迹越来越多，REINFORCE 算法有效地学习到了最优策略。不过，相比于前面的 DQN 算法，REINFORCE 算法使用了更多的序列，这是因为 REINFORCE 算法是一个在线策略算法，之前收集到的轨迹数据不会被再次利用。此外，REINFORCE 算法的性能也有一定程度的波动，这主要是因为每条采样轨迹的回报值波动比较大，这也是 REINFORCE 算法主要的不足。

REINFORCE 算法是策略梯度乃至强化学习的典型代表，智能体根据当前策略直接和环境交互，通过采样得到的轨迹数据直接计算出策略参数的梯度，进而更新当前策略，使其向最大化策略期望回报的目标靠近。这种学习方式是典型的从交互中学习，并且其优化的目标（即策略期望回报）正是最终所使用策略的性能，这比基于价值的强化学习算法的优化目标（一般是时序差分误差的最小化）要更加直接。 REINFORCE 算法理论上是能保证局部最优的，它实际上是借助蒙特卡洛方法采样轨迹来估计动作价值，这种做法的一大优点是可以得到无偏的梯度。但是，正是因为使用了蒙特卡洛方法，REINFORCE 算法的梯度估计的方差很大，可能会造成一定程度上的不稳定，这也是后面将介绍的 Actor-Critic 算法要解决的问题。

参考

[1] 伯禹AI
[2] https://www.davidsilver.uk/teaching/
[3] 动手学强化学习
[4] Reinforcement Learning