无人机辅助移动边缘计算的计算卸载优化:一种深度确定性策略梯度方法(3)——基础知识
参考文献:
[1] Wang Y , Fang W , Ding Y , et al. Computation offloading optimization for UAV-assisted mobile edge computing: a deep deterministic policy gradient approach[J]. Wireless Networks, 2021:1-16.doi:https://doi.org/10.1007/s11276-021-02632-z
3 基于DDPG的计算卸载优化
在本节中,我们首先介绍MDP、Q-Learning、DQN和DDPG这些重要的新兴RL技术的基本知识。然后,讨论了如何利用DDPG来训练无人机辅助MEC系统的高效计算卸载策略。详细地定义了状态空间、动作空间和奖励函数,描述了数据预处理的状态归一化,并举例说明了训练算法和测试算法的过程。
3.1 RL介绍
3.1.1 MDP
MDP是描述离散时间随机控制过程的数学框架,在该过程中,结果是部分随机的,并且处于主体或决策者的控制下。它正式地描述了一个环境,它是完全可观察到的强化学习。通常,MDP可以定义为一个元组
(
S
,
A
,
p
(
.
,
.
)
,
r
)
(\mathcal{S}, \mathcal{A}, p(.,.), r)
(S,A,p(.,.),r) ,S 是状态空间, A 是动作空间,
p
(
s
i
+
1
∣
s
i
,
a
i
)
p(s_{i+1}|s_i,a_i)
p(si+1∣si,ai) 是执行动作
a
i
∈
A
a_i \in \mathcal{A}
ai∈A 从当前状态
s
i
∈
S
s_i \in \mathcal S
si∈S 到下一状态
s
i
+
1
∈
S
s_{i+1} \in \mathcal S
si+1∈S 的转移概率,同时 $r: \mathcal S \times \mathcal{A} \rightarrow \mathcal R $是即时/即时奖励功能。我们表示 $\pi : \mathcal S \rightarrow \mathcal P(\mathcal A) $ 作为一个“策略”,它是从一个状态映射到一个动作。MDP的目标是找到一个最优的政策,可以最大化预期的累积回报:
R
i
=
∑
l
=
i
∞
γ
l
−
i
r
l
R_{i}=\sum_{l=i}^{\infty} \gamma^{l-i} r_{l}
Ri=l=i∑∞γl−irl
其中,
γ
∈
[
0
,
1
]
\gamma \in [0, 1]
γ∈[0,1] 是折扣因子,
r
l
=
r
(
s
l
,
a
l
)
r_{l}=r(s_l,a_l)
rl=r(sl,al) 是第
l
l
l 个时间段的即时奖励。在策略
π
\pi
π 下,状态
s
i
s_i
si 的预期折现收益定义为状态值函数,即
V
π
(
s
i
)
=
E
π
[
R
i
∣
s
i
]
V_{\pi}\left(s_{i}\right)=\mathbb{E}_{\pi}\left[R_{i} \mid s_{i}\right]
Vπ(si)=Eπ[Ri∣si]
同样,在策略
π
\pi
π 下,
s
i
s_i
si 状态下采取行动
a
i
a_i
ai后的预期折现收益定义为一个行动值函数,即:
Q
π
(
s
i
)
=
E
π
[
R
i
∣
s
i
,
a
i
]
Q_{\pi}\left(s_{i}\right)=\mathbb{E}_{\pi}\left[R_{i} \mid s_{i}, a_{i}\right]
Qπ(si)=Eπ[Ri∣si,ai]
根据Bellman方程,状态值函数和动作值函数的递归关系分别表示为:
V
π
(
s
i
)
=
E
π
[
r
(
s
i
,
a
i
)
+
γ
V
π
(
s
i
+
1
)
]
Q
π
(
s
i
,
a
i
)
=
E
π
[
r
(
s
i
,
a
i
)
+
γ
Q
π
(
s
i
+
1
,
a
i
+
1
)
]
\begin{array}{l} V_{\pi}\left(s_{i}\right)=\mathbb{E}_{\pi}\left[r\left(s_{i}, a_{i}\right)+\gamma V_{\pi}\left(s_{i+1}\right)\right] \\ Q_{\pi}\left(s_{i}, a_{i}\right)=\mathbb{E}_{\pi}\left[r\left(s_{i}, a_{i}\right)+\gamma Q_{\pi}\left(s_{i+1}, a_{i+1}\right)\right] \end{array}
Vπ(si)=Eπ[r(si,ai)+γVπ(si+1)]Qπ(si,ai)=Eπ[r(si,ai)+γQπ(si+1,ai+1)]
既然我们的目标是找到最优的政策
π
∗
\pi*
π∗ 时,可通过最优值函数求出各状态下的最优动作。最优状态值函数可以表示为:
V
∗
(
s
i
)
=
max
a
i
∈
A
E
π
[
r
(
s
i
,
a
i
)
+
γ
V
π
(
s
i
+
1
)
]
.
V_{*}\left(s_{i}\right)=\max _{a_{i} \in \mathcal{A}} \mathbb{E}_{\pi}\left[r\left(s_{i}, a_{i}\right)+\gamma V_{\pi}\left(s_{i+1}\right)\right] .
V∗(si)=ai∈AmaxEπ[r(si,ai)+γVπ(si+1)].
最优行为值函数也遵循最优策略
π
∗
\pi*
π∗ ,我们可以写出 用
Q
∗
Q_*
Q∗ 使用
V
∗
V_*
V∗ 表示如下:
Q
∗
(
s
i
,
a
i
)
=
E
π
[
r
(
s
i
,
a
i
)
+
γ
V
∗
(
s
i
+
1
)
]
Q_{*}\left(s_{i}, a_{i}\right)=\mathbb{E}_{\pi}\left[r\left(s_{i}, a_{i}\right)+\gamma V_{*}\left(s_{i+1}\right)\right]
Q∗(si,ai)=Eπ[r(si,ai)+γV∗(si+1)]
3.1.2 Q-learning
RL是机器学习的一个重要分支,agent通过与控制环境交互,使其达到最优状态,从而获得最大的收益。虽然RL常用于解决 MDPs 的优化问题,但潜在传播概率
p
(
s
i
+
1
∣
s
i
,
a
i
)
p(s_{i+1}|s_i,a_i)
p(si+1∣si,ai) 是未知的,甚至是不稳定的。在RL中,agent试图通过与控制环境的交互,并通过之前的经验调整自己的行为来获得最大的回报。Q-learning 是 RL 中一种流行而有效的方法,它是一种 off-policy 时差(TD)控制算法。状态-行为函数即最优Q函数的Bellman最优方程可以表示为:
Q
∗
(
s
i
,
a
i
)
=
E
π
[
r
(
s
i
,
a
i
)
+
γ
max
a
i
+
1
Q
∗
(
s
i
+
1
,
a
i
+
1
)
]
Q_{*}\left(s_{i}, a_{i}\right)=\mathbb{E}_{\pi}\left[r\left(s_{i}, a_{i}\right)+\gamma \max _{a_{i+1}} Q_{*}\left(s_{i+1}, a_{i+1}\right)\right]
Q∗(si,ai)=Eπ[r(si,ai)+γai+1maxQ∗(si+1,ai+1)]
通过迭代过程可以找到Q函数的最优值。agent从经验元组
(
s
i
,
a
i
,
r
i
,
s
i
+
1
)
(s_i,a_i,r_i,s_{i+1})
(si,ai,ri,si+1) 学习,Q函数可在第 i 步时间更新如下:
Q
(
s
i
,
a
i
)
←
Q
(
s
i
,
a
i
)
+
α
[
r
(
s
i
,
a
i
)
+
γ
max
a
i
+
1
Q
(
s
i
+
1
,
a
i
+
1
)
−
Q
(
s
i
,
a
i
)
]
Q(s_{i}, a_{i}) \leftarrow Q(s_{i}, a_{i})+\alpha [ r(s_{i}, a_{i})+\gamma \max_{a_{i+1}} Q(s_{i+1}, a_{i+1})-Q(s_{i}, a_{i})]
Q(si,ai)←Q(si,ai)+α[r(si,ai)+γai+1maxQ(si+1,ai+1)−Q(si,ai)]
其中,
α
\alpha
α 为学习率,
r
(
s
i
,
a
i
)
+
γ
max
a
i
+
1
Q
(
s
i
+
1
,
a
i
+
1
)
r(s_{i}, a_{i})+\gamma \max_{a_{i+1}} Q(s_{i+1}, a_{i+1})
r(si,ai)+γmaxai+1Q(si+1,ai+1) 为预测的Q值,
Q
(
s
i
,
a
i
)
Q(s_{i}, a_{i})
Q(si,ai) 是当前Q值。预测Q值和当前Q值之间的差就是TD误差。当选择合适的学习速率时,Q学习算法收敛。
3.1.3 DQN
Q-learning算法通过维护一个查询表更新状态动作空间中各项的Q值,适用于状态动作空间较小的情况。**考虑到实际系统模型的复杂性,这些空间通常是非常大的。原因是大量状态很少被访问,对应的Q值很少更新,导致Q函数的收敛时间较长。**DQN通过将深度神经网络(DNNs)与q学习相结合,解决了Q-learning算法的不足。DQN的核心思想是利用 θ \theta θ 参数化的DNN来求得近似的Q值 Q ( s , a ) Q(s,a) Q(s,a) 代替 Q 表,即 Q ( s , a ∣ θ ) ≈ Q ∗ ( s , a ) Q(s,a \mid \theta) \approx Q_{*}(s, a) Q(s,a∣θ)≈Q∗(s,a) 。
但是使用 DNN 的 RL 算法的稳定性不能得到保证。为了解决这个问题,采用了两种机制。第一个是体验重放(experience replay)。在每个时间步 i 中,agent的交互经验元组 ( s i , a i , r i , s i + 1 ) \left(s_{i}, a_{i}, r_{i}, s_{i+1}\right) (si,ai,ri,si+1) 存储在经验重放缓冲区,即经验池 B m B_m Bm。然后,从经验池中随机选取少量样本,即小批量,对深度神经网络的参数进行训练,而不是直接使用连续样本进行训练。第二种稳定方法是使用一个目标网络,它最初包含了设定策略的网络的权值,但在固定的时间步长内保持冻结状态。目标Q网络更新缓慢,但主Q网络更新频繁。这样大大降低了目标与估计Q值之间的相关性,使得算法更加稳定。
在每次迭代中,通过最小化损失函数
L
(
θ
)
L(\theta)
L(θ),将深度 Q 函数训练到目标值。损失函数可以写成:
L
(
θ
)
=
E
[
(
y
−
Q
(
s
,
a
∣
θ
)
)
2
]
L(\theta)=\mathbb{E}\left[(y-Q(s, a \mid \theta))^{2}\right]
L(θ)=E[(y−Q(s,a∣θ))2]
其中目标值 y 表示为
y
=
r
+
γ
max
a
′
Q
(
s
′
,
a
′
∣
θ
i
−
)
y=r+\gamma \max _{a^{\prime}} Q\left(s^{\prime}, a^{\prime} \mid \theta_{i}^{-}\right)
y=r+γmaxa′Q(s′,a′∣θi−) 。在 Q-learning 中,权值
θ
i
−
=
θ
i
−
1
\theta_{i}^{-}=\theta_{i-1}
θi−=θi−1 ,而在深度 q 学习
θ
i
−
=
θ
1
−
X
\theta_{i}^{-}=\theta_{1-X}
θi−=θ1−X ,即目标网络权值每 X 个时间步更新一次。
3.1.4 DDPG
DQN算法虽然可以解决高维状态空间的问题,但仍然不能处理连续的动作空间。DDPG算法是一种基于DNN的无模型的 off-policy actor - critic算法,可以学习连续动作空间中的策略。该算法由策略函数和 q 值函数组成。策略函数扮演一个参与者来生成动作。q 值函数作为一个批评家,评价行为人的表现,并指导行为人的后续行动。
如图1所示,DDPG使用两个不同的 DNNs 来逼近actor网络
μ
(
s
∣
θ
μ
)
\mu\left(s\mid \theta^{\mu}\right)
μ(s∣θμ) (即policy function)和critic 网络
Q
(
s
,
a
∣
θ
Q
)
Q\left(s, a \mid \theta^{Q}\right)
Q(s,a∣θQ) (即Q-value funtion)。另外,行动者网络和批评网络都包含一个与它们结构相同的目标网络:使用参数
θ
μ
′
\theta^{\mu^{\prime}}
θμ′ 的行动者目标网络
μ
′
\mu^{\prime}
μ′ ,使用参数
θ
Q
′
\theta^{Q^{\prime}}
θQ′ 的批评目标网络
Q
′
Q^{\prime}
Q′。与 DQN 相似,批评家网络
Q
(
s
,
a
∣
θ
Q
)
Q\left(s, a \mid \theta^{Q}\right)
Q(s,a∣θQ) 可以更新如下:
L
(
θ
Q
)
=
E
μ
′
[
(
y
i
−
Q
(
s
i
,
a
i
∣
θ
Q
)
)
2
]
L\left(\theta^{Q}\right)=\mathbb{E}_{\mu^{\prime}}\left[\left(y_{i}-Q\left(s_{i}, a_{i} \mid \theta^{Q}\right)\right)^{2}\right]
L(θQ)=Eμ′[(yi−Q(si,ai∣θQ))2]
其中,
y
i
=
r
i
+
γ
Q
(
s
i
+
1
,
μ
(
s
i
+
1
)
∣
θ
Q
)
y_{i}=r_{i}+\gamma Q\left(s_{i+1}, \mu\left(s_{i+1}\right) \mid \theta^{Q}\right)
yi=ri+γQ(si+1,μ(si+1)∣θQ)
正如Silver等人所证明的,策略梯度可以用链式法则更新,
∇
θ
μ
J
≈
E
μ
′
[
∇
θ
μ
Q
(
s
,
a
∣
θ
Q
)
∣
s
=
s
i
,
a
=
μ
(
s
i
∣
θ
μ
)
]
=
E
μ
′
[
∇
a
Q
(
s
,
a
∣
θ
Q
)
∣
s
=
s
i
,
a
=
μ
(
s
i
∣
θ
μ
)
∇
θ
μ
μ
(
s
∣
θ
μ
)
∣
s
=
s
i
]
.
\begin{array}{r} \nabla_{\theta^{\mu}} J \approx \mathbb{E}_{\mu^{\prime}}\left[\left.\nabla_{\theta^{\mu}} Q\left(s, a \mid \theta^{Q}\right)\right|_{s=s_{i}, a=\mu\left(s_{i} \mid \theta^{\mu}\right)}\right] \\ =\mathbb{E}_{\mu^{\prime}}\left[\left.\left.\nabla_{a} Q\left(s, a \mid \theta^{Q}\right)\right|_{s=s_{i}, a=\mu\left(s_{i} \mid \theta^{\mu}\right)} \nabla_{\theta^{\mu}} \mu\left(s \mid \theta^{\mu}\right)\right|_{s=s_{i}}\right] . \end{array}
∇θμJ≈Eμ′[∇θμQ(s,a∣θQ)∣∣s=si,a=μ(si∣θμ)]=Eμ′[∇aQ(s,a∣θQ)∣∣s=si,a=μ(si∣θμ)∇θμμ(s∣θμ)∣∣∣s=si].
DDPG 算法的整个训练过程可以总结如下:首先,演员网络 μ \mu μ 在上一个训练步骤之后输出 μ ( s i ) \mu(s_i) μ(si)。**为了提供充分的状态空间探索,我们需要在探索和开发之间取得平衡。**实际上,我们可以将 DDPG 的探索与学习过程分开来看待,因为 DDPG 是一种 off-policy 算法。因此,我们通过添加行为噪声 n i n_i ni 来构造动作空间,以获得动作 a i = μ ( s i ) + n i a_i=\mu(s_i)+n_i ai=μ(si)+ni ,其中 n i n_i ni 服从高斯分布 n i ∼ N ( μ e , σ e , i 2 ) n_{i} \sim \mathbb{N}\left(\mu_{e}, \sigma_{e, i}^{2}\right) ni∼N(μe,σe,i2) , μ e \mu_e μe 为平均值, σ e , i \sigma_{e, i} σe,i 是标准差。在环境中表演 a t a_t at 后,agent 可以观察到下一个状态 s i + 1 s_{i+1} si+1 和即时奖励 r t r_t rt。然后将元组 ( s i , a i , r i , s i + 1 ) \left(s_{i}, a_{i}, r_{i}, s_{i+1}\right) (si,ai,ri,si+1) 存储在体验回放缓冲区中。之后,算法随机选择N个元组 ( s j , a j , r j , s j + 1 ) (s_j,a_j,r_j,s_{j+1}) (sj,aj,rj,sj+1) 在缓冲区中组成一个小批量,并将其输入演员网络和评论家网络。使用小批处理,演员目标网络 μ ′ \mu^{\prime} μ′ 将行为 μ ′ ( s j + 1 ) \mu^{\prime}(s_{j+1}) μ′(sj+1) 输出到评论目标网络 Q ′ Q^{\prime} Q′。利用 minibatch 和 μ ′ ( s j + 1 ) \mu^{\prime}(s_{j+1}) μ′(sj+1) ,批评家网络可以根据 y i = r i + γ Q ( s i + 1 , μ ( s i + 1 ) ∣ θ Q ) y_{i}=r_{i}+\gamma Q\left(s_{i+1}, \mu\left(s_{i+1}\right) \mid \theta^{Q}\right) yi=ri+γQ(si+1,μ(si+1)∣θQ) 计出目标值 y j y_j yj。
为了使损失函数最小化,批评家网络Q将由给定的优化器(如Adam optimizer)进行更新。然后,演员网络
μ
\mu
μ 将小批量动作
a
=
μ
(
s
j
)
a=\mu(s_j)
a=μ(sj) 发送给评论网络,以实现动作a的梯度
∇
a
Q
(
s
,
a
∣
θ
Q
)
∣
s
=
s
j
,
a
=
μ
(
s
j
)
\left.\nabla_{a} Q\left(s, a \mid \theta^{Q}\right)\right|_{s=s_{j}, a=\mu\left(s_{j}\right)}
∇aQ(s,a∣θQ)∣∣s=sj,a=μ(sj) 。参数
∇
θ
μ
μ
(
s
∣
θ
μ
)
∣
s
=
s
j
\left.\nabla_{\theta^{\mu}} \mu\left(s \mid \theta^{\mu}\right)\right|_{s=s_{j}}
∇θμμ(s∣θμ)∣s=sj 可以由它自己的优化器导出。使用这两个梯度,参与者网络可以用以下近似更新:
∇
θ
u
J
≈
1
N
∑
j
[
∇
a
Q
(
s
,
a
∣
θ
Q
)
∣
s
=
s
j
,
a
=
μ
(
s
j
∣
θ
μ
)
∇
θ
μ
μ
(
s
∣
θ
μ
)
∣
s
=
s
j
]
.
\nabla_{\theta^{u}} J \approx \frac{1}{N} \sum_{j}\left[\left.\left.\nabla_{a} Q\left(s, a \mid \theta^{Q}\right)\right|_{s=s_{j}, a=\mu\left(s_{j} \mid \theta^{\mu}\right)} \nabla_{\theta^{\mu}} \mu\left(s \mid \theta^{\mu}\right)\right|_{s=s_{j}}\right] .
∇θuJ≈N1j∑[∇aQ(s,a∣θQ)∣∣s=sj,a=μ(sj∣θμ)∇θμμ(s∣θμ)∣∣∣s=sj].
最后,DDPG agent使用小常数
τ
\tau
τ 柔化更新批评家目标网络和行动者目标网络:
θ
Q
′
←
θ
Q
+
(
1
−
τ
)
θ
Q
′
θ
μ
′
←
θ
μ
+
(
1
−
τ
)
θ
μ
′
\begin{array}{l} \theta^{Q^{\prime}} \leftarrow \theta^{Q}+(1-\tau) \theta^{Q^{\prime}} \\ \theta^{\mu^{\prime}} \leftarrow \theta^{\mu}+(1-\tau) \theta^{\mu^{\prime}} \end{array}
θQ′←θQ+(1−τ)θQ′θμ′←θμ+(1−τ)θμ′