Initialize replay memory D \mathcal{D} D to capacity N N N (运行消耗 t 0 t_0 t0时间)
Initialize action-value function Q Q Q with random weights (运行消耗 t 1 t_1 t1时间)
for e p i s o d e = 1 , M episode=1,M episode=1,M do (运行一次平均消耗 t 2 t_{2} t2时间，重复运行 M M M次)
\uad Initialise sequence s 1 = x 1 s_1={x_1} s1=x1 and preprocessed sequenced ϕ 1 = ϕ ( s 1 ) \phi_1=\phi(s_1) ϕ1=ϕ(s1) (运行一次平均消耗 t 2.1 t_{2.1} t2.1时间)
\uad for t = 1 , T t=1,T t=1,T do (运行一次平均消耗 t 2.2 t_{2.2} t2.2时间，重复运行 T T T次)
\uad\uad With probability ϵ \epsilon ϵ select a random action a t a_t at (运行一次平均消耗 t 2.2.1 t_{2.2.1} t2.2.1时间)
\uad\uad otherwise select a t = max a Q ∗ ( ϕ ( s t ) , a ; θ ) a_t=\max_aQ^*(\phi(s_t),a;\theta) at=maxaQ∗(ϕ(st),a;θ) (运行一次平均消耗 t 2.2.1 t_{2.2.1} t2.2.1时间，因为是otherwise)
\uad\uad Execute action a t a_t at in emulator and observe reward r t r_t rt and image x t + 1 x_{t+1} xt+1 (运行一次平均消耗 t 2.2.2 t_{2.2.2} t2.2.2时间)
\uad\uad Set s t + 1 = s t , a t , x t + 1 s_{t+1}=s_t,a_t,x_{t+1} st+1=st,at,xt+1 and preprocess ϕ t + 1 = ϕ ( s t + 1 ) \phi_{t+1}=\phi(s_{t+1}) ϕt+1=ϕ(st+1) (运行一次平均消耗 t 2.2.3 t_{2.2.3} t2.2.3时间)
\uad\uad Store transition ( ϕ t , a t , r t , ϕ t + 1 ) (\phi_t,a_t,r_t,\phi_{t+1}) (ϕt,at,rt,ϕt+1) in D \mathcal{D} D (运行一次平均消耗 t 2.2.4 t_{2.2.4} t2.2.4时间)
\uad\uad Sample random minibatch of transitions ( ϕ j , a j , r j , ϕ j + 1 ) (\phi_j,a_j,r_j,\phi_{j+1}) (ϕj,aj,rj,ϕj+1) (运行一次平均消耗 t 2.2.5 t_{2.2.5} t2.2.5时间)
Set y j = { r j , for terminal ϕ j + 1 r j + γ max a ′ Q ( ϕ j + 1 , a ′ ; θ ) , for non-terminal ϕ j + 1 (运行一次平均消耗 t 2.2.6 时间) \text{Set}\quad y_j=\begin{cases}r_j, & \text{for terminal $\phi_{j+1}$} \\ r_j+\gamma\max_{a’}Q(\phi_{j+1},a’;\theta), & \text{for non-terminal $\phi_{j+1}$}\end{cases}\text{(运行一次平均消耗$t_{2.2.6}$时间)} Setyj={
rj,rj+γmaxa′Q(ϕj+1,a′;θ),for terminal ϕj+1for non-terminal ϕj+1(运行一次平均消耗t2.2.6时间)
\uad\uad Perform a gradient descent step on ( y j − Q ( ϕ j , a j ; θ ) ) 2 (y_j-Q(\phi_j,a_j;\theta))^2 (yj−Q(ϕj,aj;θ))2 according to equation 3 (运行一次平均消耗 t 2.2.7 t_{2.2.7} t2.2.7时间)
\uad end for
end for
根据代码上执行的平均时间假设，计算出来执行DQN算法的时间为：
T ( e p i s o d e , t ) = t 0 + t 1 + ( t 2 + t 2.1 + ( t 2.2 + t 2.2.1 + t 2.2.2 + t 2.2.3 + t 2.2.4 + t 2.2.5 + t 2.2.6 + t 2.2.7 ) ∗ T ) ∗ M (合并常数项) = t c 1 + ( t c 2 + t c 3 ∗ T ) ∗ M = t c 1 + ( t c 2 ∗ M + t c 3 ∗ T ∗ M ) = t c 1 + t c 2 ∗ M + t c 3 ∗ T ∗ M = t c 3 ∗ T ∗ M = T ∗ M \begin{aligned} T(episode,t) &=t_0 + t_1 \\ & + (t_2+t_{2.1}+(t_{2.2}+t_{2.2.1}+t_{2.2.2}+t_{2.2.3}+t_{2.2.4}+t_{2.2.5}+t_{2.2.6}+t_{2.2.7})*T)*M \\ \text{(合并常数项)} & = t_{c_1}+(t_{c_2}+t_{c_3}*T)*M \\ & = t_{c_1}+(t_{c_2}*M+t_{c_3}*T*M) \\ & = t_{c_1}+t_{c_2}*M+t_{c_3}*T*M \\ & = t_{c_3}*T*M \\ & = T*M \\ \end{aligned} T(episode,t)(合并常数项)=t0+t1+(t2+t2.1+(t2.2+t2.2.1+t2.2.2+t2.2.3+t2.2.4+t2.2.5+t2.2.6+t2.2.7)∗T)∗M=tc1+(tc2+tc3∗T)∗M=tc1+(tc2∗M+tc3∗T∗M)=tc1+tc2∗M+tc3∗T∗M=tc3∗T∗M=T∗M
当 e p i s o d e episode episode和 t t t的值非常大的时候， T ( e p i s o d e , t ) T(episode,t) T(episode,t)函数中的常数项（例如步骤4中的 t c 1 t_{c_1} tc1）以及 T T T和 M M M的系数（例如步骤5中的 t c 3 t_{c_3} tc3）对 e p i s o d e episode episode和 t t t的影响也可以忽略不计了。同时我们要注意到 T ( e p i s o d e , t ) T(episode,t) T(episode,t)函数的主体影响因素是 T ∗ M T*M T∗M而不是 M M M，因为 T ∗ M T*M T∗M的增长速度远快于 M M M。也即，这里函数 T ( e p i s o d e , t ) T(episode,t) T(episode,t)的时间复杂度可以表示为 T ( e p i s o d e , t ) = O ( n t n m ) T(episode,t)=O(n_tn_m) T(episode,t)=O(ntnm)其中， n t n_t nt是指每个episode中的时间步数量， n m n_m nm是指episode的数量。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/206595.html原文链接：https://javaforall.net
![golang 激活码 2021[在线序列号][通俗易懂]](https://javaforall.net/wp-content/uploads/2020/11/2020110817443450-480x300.jpg)
