# Hierarchical Episodic Control
## 3 Hierarchical Episodic Control
### Theoretical Analysis
#### 3.3.2 Convergence Analysis
It demonstrates significant improvements in both low-dimensional and high-dimensional environments, as well as performing well in sparse environments. Additionally, a summary of the average training times for episodic memory models and hierarchical episodic control models is provided across 57 Atari games and the UE4 tracking game. This summary underscores how the proposed algorithms in this paper can effectively improve training efficiency and reduce the required training time across diverse games and practical applications. Conceptualization, methodology, software, validation, writing, R.Z. ; resources, data curation, project administration, Y.W. ; supervision, Z.Z. and Y.W. All authors have read and agreed to the published version of the manuscript. This work was supported in part by the Natural Science Foundation of Shaanxi Province under Grant 2022 JQ-584. **Data Availability Statement:** The source code of environments is contained within the article. \begin{table}
\begin{tabular}{c c c} \hline \hline
**Baseline** & **GPU** & **Time Consumption** \\ \hline A3C & NVIDIA GeForce RTX 2080 & 2 Days \\ \hline GEM & NVIDIA GeForce RTX 2080 & 2 Days \\ \hline BootstrapEM [26] & NVIDIA GeForce RTX 2080 & 2 Days \\ \hline OptionEM & NVIDIA GeForce RTX 2080 & **28 h** \\ \hline \hline \end{tabular}
\end{table} 
Table 5: Training time consumption for UE4-based active tracking. Figure 7: Option samples in UE4 tracking. **Conflicts of Interest:** The authors declare no conflicts of interest. The funders had no role in the design of the study; in the collection, analyses, or interpretation of data; in the writing of the manuscript; or in the decision to publish the results. ## Appendix A Proof

Consider independent unbiased estimate

\[M_{\theta}^{(1,2)}(s_{t+h},\omega_{t+h},a_{t+h})=M^{\pi}(s_{t+h},\omega_{t+h},a _{t+h})+e_{h}^{(1,2)} \tag{11}\]

The equation satisfies the following:

\[\mathbb{E}_{\tau,\varepsilon}\Big{[}R_{t}^{(1,2)}(s_{t},\omega_{t})\Big{]} \leq\mathbb{E}_{\tau}\bigg{[}\max_{0\leq h\leq T-t-1}M_{t,h}^{\pi}(s_{t}, \omega_{t})\bigg{]} \tag{12}\]

while

\[M_{t,h}^{\pi}(s,\omega,a)=\left\{ \begin{array}{ll}\sum_{i=0}^{h}\gamma^{i}r_ {t+i}+\gamma^{h+1}M^{\pi}(s_{t+h+1},\omega_{t+h+1},a_{t+h+1})&\text{if }h<T-t,\beta_{t+h+1}=0\\ \gamma^{h+1}M_{\Omega}^{\pi}(s_{t+h+1},\omega_{t+h+1}),&\text{if }h<T-t,\beta_{t+h+1}=1\\ \sum_{h=0}^{h}\gamma^{i}r_{t+i}&\text{if }h=T-t\end{array} \right. \tag{13}\]

\[R_{t}^{(1,2)}=V_{t,h^{*}}=\left\{ \begin{array}{ll}\sum_{i=0}^{h^{*}}\gamma^ {i}r_{t+i}+\gamma^{h+1}M_{\theta}^{(2,1)}(s_{t+h^{*}+1},\omega_{t+h^{*}+1},a_ {t+h^{*}+1}),&\text{if }\beta_{t+h+1}=1\\ \sum_{i=0}^{h^{*}}\gamma^{i}r_{t+i}+\gamma^{h+1}M_{\Omega,\alpha}^{\pi}(s_{t+h ^{*}+1},\omega_{t+h^{*}+1})&\text{if }\beta_{t+h+1}=0\end{array} \right. \tag{14}\]

\[\mathbb{E}_{\varepsilon}\bigg{[}R_{t}^{(1,2)}-M_{t,h_{(1,2)}}^{\pi}(s_{t}, \omega_{t})\bigg{]} =\mathbb{E}\bigg{[}V_{t,h_{(1,2)}^{*}}-M_{t,h_{(1,2)}^{*}}^{\pi}( s_{t},\omega_{t})\bigg{]} \tag{15}\] \[=\mathbb{E}\bigg{[}\gamma^{h^{*}+1}\Big{(}M_{\Omega,\theta}^{(2,1 )}(s_{t+h^{*}+1},\omega_{t+h^{*}+1})-M_{\Omega}^{\pi}(s_{t+h^{*}+1},\omega_{t+ h^{*}+1})\Big{)}\bigg{]}\] \[=0\]

so,

\[\mathbb{E}_{\tau,\varepsilon}\Big{[}R_{t}^{(1,2)}\Big{]}=\left\{ \begin{array}[ ]{ll}\mathbb{E}_{\tau}\bigg{[}M_{t,h_{(1,2)}^{*}}^{\pi}(s_{t},\omega_{t},a_{t })\bigg{]}\leq\mathbb{E}_{\tau}\Big{[}\max_{0\leq h\leq T-t}M_{t,h}^{\pi}(s_{t},\omega_{t},a_{t})\Big{]},&\text{if }\beta_{t+h+1}=0\\ \mathbb{E}_{\tau}\bigg{[}U_{t,h_{(1,2)}^{*}}^{\pi}(s_{t},\omega_{t})\bigg{]} \leq\mathbb{E}_{\tau}\Big{[}\max_{0\leq t\leq T-t}U_{t,h}^{\pi}(s_{t},\omega_ {t})\Big{]},&\text{if }\beta_{t+h+1}=1\end{array} \right. \tag{16}\]

This concludes the proof of Theorem 1. The subsequent analysis further demonstrates the convergence property of the OptionEM algorithm.