DQN算法及进阶

DQN 算法

核心思想

DQN核心思想

在Q学习基础上

引入深度Q网络来近似Q函数：可处理连续状态空间，输出仍为离散动作。

Q_{ϕ} (s, a) \approx Q (s, a)

新增经验回放和目标网络两个技巧

核心思想

仍是维护Q函数进行决策，仍是基于价值的学习方法

Q_{θ} (s_{t}, a_{t}) \leftarrow Q_{θ} (s_{t}, a_{t}) + α (\underset{目 标 值, 目 标 网 络}{\underset{⏟}{r_{t} + γ max_{a^{'}} Q_{\hat{θ}} (s_{t + 1}, a^{'})}} - \underset{当 前 预 测 值}{\underset{⏟}{Q_{θ} (s_{t}, a_{t})}})

直接优化Q值，目标是使得预测值和目标值接近

{\hat{Q}}_{目 标} \leftrightarrow r_{t} + Q_{π} (s_{t + 1}, π (s_{t + 1}))

y_{i} = {\begin{cases} r_{i} & s_{i} = 终 态 \\ r_{i} + γ max_{a^{'}} Q_{\hat{θ}} (s_{i + 1}, a^{'}; θ) & s_{i} \neq 终 态 \end{cases}

Loss函数及参数更新，MSE均分误差

\begin{array}{l} L (θ) = (y_{i} - Q_{θ} (s_{i}, a_{i}; θ))^{2} \\ θ_{i} \leftarrow θ_{i} - α \cdot \nabla_{θ_{i}} L_{i} (θ_{i}) \end{array}

DL：训练样本提前准备好；RL：训练样本和环境实时交互获得

Q表格 vs Q网络

Q表格

只能处理离散状态空间，需要定义状态。输出为离散动作。

神经网络

近似Q表格，可处理连续状态空间，输出仍为离散动作。
- 如 仅用2个维度(x,y)，即可表示无穷个状态
新引入参数为 $θ$ ，梯度下降法进行优化

评论员V、Q函数

评论员

在基于价值的算法中，我们学习的不是策略，而是评论员。
评论员无法凭空评价一个状态的好坏
评论员评价的是给定某状态时，如果后面actor按照策略 $π$ 交互，会得到多少奖励。
评论员输出取决于状态和演员。实际评价的是演员的好坏。

评论员V函数

蒙特卡洛方法

核心思想

让演员和环境交互，采样轨迹，计算出状态的回报 (累计奖励)

s_{a} \to G_{a} \to V_{π} (s_{a}), s_{b} \to G_{b} \to V_{π} (s_{b})

再用回归问题训练网络，使得网络预测结果接近采样值

缺点

采样方差很大： $G_{a}$ 是多步累计奖励结果，其实是一个随机变量
- 每次到 $s_{a}$ ，最后得到的回报不一定是一样的
- $G_{a}$ 的方差，比某一个状态的奖励方差大

Var [k X] = k^{2} Var [X]

花费时间高：需等到回合结束时，才能计算出累积奖励，这时才能更新网络

时序差分方法

核心思想

时序差分计算V函数

V_{π} (s_{t}) = r_{t} + V_{π} (s_{t + 1})

时间步差值来训练网络

l o s s = V_{π} (s_{t}) - V_{π} (s_{t + 1}) \leftrightarrow r_{t}

单步奖励 $r$ 的方差会比累计回报 $G_{t}$ 的奖励小很多

蒙特卡洛方法 vs 时序差分方法 Case

Case

8条轨迹， $s_{b}$ 出现8次， $s_{a}$ 仅出现1次，最重要是第1条轨迹引起争议

$V (s_{b})$ 计算

蒙特卡洛方法

V (s_{b}) = \frac{6 \times 1 + 2 \times 0}{8} = \frac{3}{4}

时序差分方法

V (s_{b}) = \frac{3}{4}

$V (s_{a})$ 计算

蒙特卡洛方法
- 可能 $s_{a}$ 影响了 $s_{b}$ ，导致奖励为0，MC方法考虑了这件事，因此 $s_{a}$ 回报为0

V (s_{a}) = \frac{1 \times 0}{1} = 0

TD 方法
- 可能看到 $s_{a}$ 以后， $s_{b}$ 奖励为0，仅是巧合，并非 $s_{a}$ 造成的
- $s_{a}$ 一定进入 $s_{b}$ ，所以TD奖励期望值是 $\frac{3}{4}$

V (s_{a}) = r + V (s_{b}) = 0 + \frac{3}{4} = \frac{3}{4}

MC 和 TD 方法的值都有可能

评论员Q函数

Q函数及学习过程

Q函数定义

$Q_{π} (s, a)$ ：在状态s，强制采取动作a，让策略 $π$ 继续执行下去，得到的期望回报就是
- 注意：策略 $π$ 在状态s时，不一定选择 $a$
有了Q函数，就可以做强化学习，决定采取更好的动作，来改进策略。
- 学习Q函数、策略改进，不断迭代

学习过程

初始策略 $π$ 、Q函数
根据策略 $π$ 学出策略 $π$ 的Q函数 (策略评估)，根据新Q找到新策略 $π^{'}$ (策略改进)

Q_{π} (s_{t}, a_{t}) = r_{t} + Q_{π} (s_{t + 1}, π (s_{t + 1}))

π^{'} (s) = \arg max_{a} Q_{π} (s, a)

用 $π \leftarrow π^{'}$ ，如此迭代下去
证明可知： $V_{π^{'}} (s) \geq V_{π} (s)$

经验回放/经验池

经验回放是所有异策略算法都会用到的技巧。

经验回放

背景问题

Q学习每交互一个样本，就立即用于更新策略。单样本迭代参数会导致训练不稳定。
梯度下降法假设训练样本独立同分布，但每次迭代样本是有关联的。

经验回放

构建一个回放缓冲区replay buffer
- 把采样到的经验存放在缓冲区内，经验可能来自不同的策略。
- 如果缓冲区已满，则丢弃旧的经验。早期的经验可能不适合后期训练。
- 缓冲区不能太大，也不能太小。
每次迭代，从缓冲区里随机挑一个batch经验，去更新Q函数。

优点

提高了采样效率
- RL中环境交互非常费时间，使用回放缓冲区，可以减少交互次数
- 一些过去的经验，可以重复利用
增加了样本多样性
- 回放缓冲区里的数据来自不同策略，多样性比较好，性能好

目标网络

问题背景

要拟合的TD目标值一直在变化，会导致训练不稳定，不好训。

{\hat{Q}}_{目 标} \leftrightarrow r_{t} + Q_{π} (s_{t + 1}, π (s_{t + 1}))

核心思想

采用一个目标网络，固定住一段时间；在当前网络 更新n步后，才拷贝权重去更新目标网络。

类比例子

猫抓老鼠，猫和老鼠都在动，其实不太好训；可以让老鼠不要动的那么频繁，猫就好抓了。
目标网络是皇帝，当前网络是大臣；皇帝做决策时，不着急下定论；先让大臣集思广益收集情报后，皇帝再做决策。

伪代码

经验回放：存样本、取样本。

python

class ReplayBuffer:
    def __init__(self, capacity):
        self.capacity = capacity # 经验回放的容量
        self.buffer = [] # 用列表存放样本
        self.position = 0 # 样本下标，便于覆盖旧样本
    
    def push(self, state, action, reward, next_state, done):
        ''' 缓存样本
        '''
        if len(self.buffer) < self.capacity: # 如果样本数小于容量
            self.buffer.append(None)
        self.buffer[self.position] = (state, action, reward, next_state, done)
        self.position = (self.position + 1) % self.capacity 
    
    def sample(self, batch_size):
        ''' 取出样本，即采样
        '''
        batch = random.sample(self.buffer, batch_size) # 随机采出小批量转移
        state, action, reward, next_state, done =  zip(*batch) # 解压成状态，动作等
        return state, action, reward, next_state, done
    
    def __len__(self):
        ''' 返回当前样本数
        '''
        return len(self.buffer)

Agent：采样动作、预测动作、更新策略。

python

class Agent:
    def __init__(self):
        # 定义当前网络
        self.policy_net = MLP(state_dim,action_dim).to(device) 
        # 定义目标网络
        self.target_net = MLP(state_dim,action_dim).to(device)
        # 将当前网络参数复制到目标网络中
        self.target_net.load_state_dict(self.policy_net.state_dict())
        # 定义优化器
        self.optimizer = optim.Adam(self.policy_net.parameters(), lr=learning_rate) 
        # 经验回放
        self.memory = ReplayBuffer(buffer_size)
        self.sample_count = 0  # 记录采样步数
 
	def sample_action(self,state):
        ''' 采样动作，主要用于训练
        '''
        self.sample_count += 1
        # epsilon 随着采样步数衰减
        self.epsilon = self.epsilon_end + (self.epsilon_start - self.epsilon_end) * math.exp(-1. * self.sample_count / self.epsilon_decay) 
        if random.random() > self.epsilon:
            with torch.no_grad(): # 不使用梯度
                state = torch.tensor(np.array(state), device=self.device, dtype=torch.float32).unsqueeze(dim=0)
                q_values = self.policy_net(state)
                action = q_values.max(1)[1].item() # choose action corresponding to the maximum q value
        else:
            action = random.randrange(self.action_dim)
    
    def predict_action(self,state):
        ''' 预测动作，主要用于测试
        '''
        with torch.no_grad():
            state = torch.tensor(np.array(state), device=self.device, dtype=torch.float32).unsqueeze(dim=0)
            q_values = self.policy_net(state)
            action = q_values.max(1)[1].item() # choose action corresponding to the maximum q value
        return action
    
    def update(self, share_agent=None):
      	''' 更新策略
      	'''
        # 当经验回放中样本数小于更新的批大小时，不更新算法
        if len(self.memory) < self.batch_size: # when transitions in memory donot meet a batch, not update
            return
        # 1. 从经验回放中采样
        state_batch, action_batch, reward_batch, next_state_batch, done_batch = self.memory.sample(
            self.batch_size)
        # 转换成张量（便于GPU计算）
        state_batch = torch.tensor(np.array(state_batch), device=self.device, dtype=torch.float) 
        action_batch = torch.tensor(action_batch, device=self.device).unsqueeze(1) 
        reward_batch = torch.tensor(reward_batch, device=self.device, dtype=torch.float).unsqueeze(1) 
        next_state_batch = torch.tensor(np.array(next_state_batch), device=self.device, dtype=torch.float) 
        done_batch = torch.tensor(np.float32(done_batch), device=self.device).unsqueeze(1) 
        
        # 2. 计算Q的当前值和目标值，计算loss
        # 计算 Q 的当前值  z
        q_value_batch = self.policy_net(state_batch).gather(dim=1, index=action_batch) # shape(batchsize,1),requires_grad=True
        # 计算 Q 的目标值，即 r + \gamma * Q_max
        next_max_q_value_batch = self.target_net(next_state_batch).max(1)[0].detach().unsqueeze(1) 
        expected_q_value_batch = reward_batch + self.gamma * next_max_q_value_batch* (1-done_batch)
        # 计算损失
        loss = nn.MSELoss()(q_value_batch, expected_q_value_batch)  
        
        # 3. 反向传播
        # 梯度清零，避免在下一次反向传播时重复累加梯度而出现错误。
        self.optimizer.zero_grad()  
        # 反向传播
        loss.backward()
        # clip避免梯度爆炸
        for param in self.policy_net.parameters():  
            param.grad.data.clamp_(-1, 1)
        # 更新优化器
        self.optimizer.step() 
        
        # 每C(target_update)步更新目标网络
        if self.sample_count % self.target_update == 0: 
            self.target_net.load_state_dict(self.policy_net.state_dict())

不足点

Q值过估计

Q值过估计问题

问题定义

由于采样数据不充分或算法本身等问题，导致学习到的V或Q函数，估计值大于真实值。
过估计会影响算法性能和稳定性

为何Q值被高估

由于网络估算误差，智能体总是选择Q值被高估的动作，一直叠加，导致目标值总是太大，最终导致Q过估计。

Q (s_{t}, a_{t}) \leftrightarrow r_{t} + γ max_{a} Q (s_{t + 1}, a)

被高估的Q值：

四个动作，绿色是被高估部分，算法总是选择被高估的动作，作为目标值，导致Q过估计。

其他不足点

DQN 算法缺点

无法表示连续动作

只能解决离散动作空间问题

高方差

通过采样方法来估计价值函数，会导致方差高，影响算法收敛
尽管通过经验回放、目标网络等方法，但不能完全解决

探索和利用平衡问题

DQN通常选择 $ϵ$ 贪心策略，导致效果不是很理想。
- 很多问题的最优策略是随机性策略，即需要以不同概率选择不同动作。

DQN 进阶技巧

Double DQN (双)

Double DQN

背景

为解决 DQN 存在Q值过估计问题

核心方法

提出2个 $Q 、 Q^{'}$ 两个Q网络。
$Q$ ：选择动作 $a$ 。选择了高估动作，没关系。
$Q^{'}$ ：对 $a$ 做价值评估。只要 $Q^{'}$ 步不高估 $a$ 的值就行。

Q (s_{t}, a_{t}) \leftrightarrow r_{t} + Q^{'} (s_{t + 1}, \arg max_{a} Q (s_{t + 1}, a))

$Q$ 和 $Q^{'}$ 交替着来，轮着选动作和价值评估。

注意

效果和单纯C步复制目标网络，差不多，但后者更简单，一般仍选用目标网络，不用DDQN。

Dueling DQN (竞争)

核心思想

Dueling DQN

核心思想

优化网络结构，增加价值层和优势层，二者结合起来，再作为输出层。
优势层 $A_{θ, α} (s, a)$ ：估计每个动作带来的优势，输出维度是动作数。
- 类似Actor-Critic里的Actor
价值层 $V_{θ, β} (s)$ ：估计每个状态的价值，输出维度为1。
- 类似Actor-Critic里的Critic

Q_{θ, α, β} (s, a) = A_{θ, α} (s, a) + V_{θ, β} (s)

优势层增加约束，和为0；即减均值，做零中心化处理。

Q_{θ, α, β} (s, a) = \underset{A c t o r, 中 心 化 处 理}{\underset{⏟}{(A_{θ, α} (s, a) - \frac{1}{A} \sum_{a \in A} A_{θ, α} (s, a))}} + \underset{C r i t i c}{\underset{⏟}{V_{θ, β} (s)}}

让网络竞争更新，尽量更新V

思考

为何要设计成A(s,a)和V(s)竞争型网络？

如果要同时更新所有动作的 $Q (s, a)$ (如都加一)，不用更新每个 $A (s, a)$ ，只需更新 $V (s)$ 即可
如果有3个动作，但只采样到2个，更新 $V (s)$ ，也能更改第3个动作的Q值，数据高效方法

优势层为何要减均值增加约束和为0？

如果学到 $V (s) = 0$ ，则 $A (s, a) = Q (s, a)$ ；那么就没有A+V的优势了。
所以要让 $A$ 更新起来麻烦，给 $A$ 增加约束，让网络尽量去更新 $V$ ，竞争更新
这个约束就是对 $s$ 的所有动作优势求和为0， $\sum_{a \in A} A (s, a) = 0$ ，优势有正有负

竞争更新V(s)的好处：

对优势层做约束，减均值做0中心化处理：

实现伪代码

python

class DuelingQNetwork(nn.Module):
    def __init__(self, state_dim, action_dim,hidden_dim=128):
        super(DuelingQNetwork, self).__init__()
        # 隐藏层
        self.hidden_layer = nn.Sequential(
            nn.Linear(state_dim, hidden_dim),
            nn.ReLU()
        )
        #  优势层
        self.advantage_layer = nn.Sequential(
            nn.Linear(hidden_dim, hidden_dim),
            nn.ReLU(),
            nn.Linear(hidden_dim, action_dim)
        )
        # 价值层
        self.value_layer = nn.Sequential(
            nn.Linear(hidden_dim, hidden_dim),
            nn.ReLU(),
            nn.Linear(hidden_dim, 1)
        )
        
    def forward(self, state):
        x = self.hidden_layer(state)
        advantage = self.advantage_layer(x)
        value     = self.value_layer(x)
        # Q(s,a) = V(s) + A(s,a) - mean(A(s,a))
        return value + advantage - advantage.mean()

Noisy DQN (噪声)

Noisy DQN

问题背景

改进探索策略，探索和状态应该是有关系的。
$ϵ$ 贪心法，在动作空间上加噪声。其实有问题，探索和状态无关
- 给定状态s，一会儿随机选、一会儿按Q输出，其实是不正常的。
- 真实世界，给定同样的状态，应该有同样的回应。

核心思想

在参数空间上加噪声。 在Q网络上，加高斯噪声，变成噪声 $\tilde{Q}$ 网络。

a = \arg max_{a} \tilde{Q} (s, a)

每个回合开始时，采样噪声并固定下来，直到回合结束。在一个回合中噪声保持不变。
- 这是和 $ϵ$ 贪心法最本质的区别，这是依赖状态的探索，是更合理的。
业界做法
- OpenAI(2018)：每一个参数都加高斯噪声
- DeepMind(2018)：噪声由一组参数控制，网络可以自己决定噪声加多大

PER DQN (优先级经验回放)

PER 核心思想

优先级经验回放

问题背景

普通经验回放均匀地从缓冲区采样，不一定是最好的。
- 有些数据比较重要，比如TD误差较大的样本，应该给与高权重。

核心思想

针对TD误差较大(重要,难训练)的样本，给更高优先级、更大概率采样到
- TD误差越大，loss越大，对反向传播的作用也就越大
- TD误差越大的样本被采样到，算法更容易收敛
基于SumTree来实现。

SumTree实现思路

SumTree 实现优先级回放思路

基础SumTree思路

叶子节点为各样本的TD误差，依次向上回溯到根节点
叶子节点按误差大小，从左到右依次排序；TD误差越大，区间越大
在[0-root值] 之间均匀采样，TD误差大的节点，采样到的几率更高

TD误差优先级问题及重定义重要性采样权重

直接使用TD误差做优先级的问题及改进方法

算法效率

考虑到效率，每次更新，不会为经验池中的所有经验都计算TD误差并更新优先级
经验池中的TD误差、优先级是针对之前的网络

直接使用TD误差作为优先级的问题

如果某批样本TD误差较小，只能说明对之前网络来说信息量不大，但不能说明对当前网络信息量不大。因此，可能会错过对当前网络信息量更大的样本。
如果被选中样本的TD误差在当前更新后减小，下次这些样本就不会被选到；可能导致来来回回参与计算的就那几个样本，旱的旱死、涝的涝死，容易导致过拟合。

解法1：定义采样概率

不直接使用TD误差，定义以下样本采样概率，每个样本有一个优先级， $α$ 是超参数。

样 本 采 样 概 率 ： P (i) = \frac{p_{i}^{α}}{\sum_{k} p_{k}^{α}} ， 样 本 优 先 级 ： p_{i} = | δ_{i} | + ϵ

解法2：定义重要性采样权重

TD误差样本对应之前的网络 $q (x)$ ，而非当前待更新的网络 $p (x)$ 。重要性权重 $w = \frac{p (x)}{q (x)}$ ，其中 $q (x)$ 已知
利用重要性采样 可以估计当前网络的性质，重新定义重要性权重

\begin{array}{l} 重 要 性 权 重 : & w_{i} = (\frac{1}{N} \frac{1}{P (i)})^{β} = (N \cdot P (i))^{- β} \\ 权 重 归 一 化 ： & w_{i} = \frac{w_{i}}{max_{j} w_{j}} \end{array}

超参数 $β$
- $β = 0$ ，重要性权重为1，即不考虑重要性采样
- $β = 1$ ，重要性权重为 $w_{i}$ ，即完全考虑重要性采样
$β$ 希望从0开始，随训练逐渐增大，更好利用重要性采样，热偏置思想
- 训练开始：随机优先级采样，快速收敛。
- 训练后期：使用重要性采样，更好利用经验回放中的样本。

β = min (1, β + β_{s t e p}) 一 般 β_{s t e p} = 0.0001

在MC和TD中取得平衡

MC-TD平衡

核心思想

采取多步方法，同时采样N步，保存N步的经验。
目标 $\hat{Q}$ 网络，计算的不再是 $s_{t + 1}$ 的奖励，而是 $s_{t + N + 1}$ 的奖励

Q (s_{t}, a_{t}) \leftrightarrow \sum_{t^{'} = t}^{t + N} r_{t^{'}} + \hat{Q} (s_{t + N + 1}, a_{t + N + 1})

优点

单步方法：只采样1步，后面的奖励都是Q值估计出来的，误差影响比较大。
目前多步：采样N步才进行估测，采样多，Q估测带来的误差影响就比较小。
但多步方差会比较大，可以在方差和不精确的Q值之间取一个平衡。

分布式Q函数

分布Q函数

核心思想

Q函数，输出的价值不是一个数字，而是一个分布，通过该分布去计算均值，最终得到Q值

特点

因为会有限制，极大极小值会被丢掉。
导致不会高估奖励，反而会低估奖励。比如[-10,10]，会丢掉超过10以上的奖励。

3个动作，奖励共有5个选择，所以Q一共输出3*5=15个值，最后再去为每个动作计算奖励期望，得到Q值。

彩虹🌈

彩虹

核心思想

每个方法都有一个自己的颜色，组合起来就变成彩虹。

一些结论

Noise DQN 比 DQN好
PER DQN、Dueling DQN、分布式DQN 性能也还挺好。

DQN 算法 ​

核心思想 ​

Q表格 vs Q网络 ​

评论员V、Q函数 ​

评论员 ​

评论员V函数 ​

评论员Q函数 ​

经验回放/经验池 ​

目标网络 ​

伪代码 ​

不足点 ​

Q值过估计 ​

其他不足点 ​

DQN 进阶技巧 ​

Double DQN (双) ​

Dueling DQN (竞争) ​

核心思想 ​

思考 ​

实现伪代码 ​

Noisy DQN (噪声) ​

PER DQN (优先级经验回放) ​

PER 核心思想 ​

SumTree实现思路 ​

TD误差优先级问题及重定义重要性采样权重 ​

在MC和TD中取得平衡 ​

分布式Q函数 ​

彩虹🌈 ​

DQN 算法

核心思想

Q表格 vs Q网络

评论员V、Q函数

评论员

评论员V函数

评论员Q函数

经验回放/经验池

目标网络

伪代码

不足点

Q值过估计

其他不足点

DQN 进阶技巧

Double DQN (双)

Dueling DQN (竞争)

核心思想

思考

实现伪代码

Noisy DQN (噪声)

PER DQN (优先级经验回放)

PER 核心思想

SumTree实现思路

TD误差优先级问题及重定义重要性采样权重

在MC和TD中取得平衡

分布式Q函数

彩虹🌈