# Hierarchical Episodic Control
## 3 Hierarchical Episodic Control
### Theoretical Analysis
#### 3.3.2 Convergence Analysis
## Appendix B Proof

\(\Delta_{t}=M_{t}^{(1)}-M^{*}\) when \(\beta_{t}=0\),\(F_{t}(s_{t},\omega_{t},a_{t})=R_{t}^{(1)}-M^{*}(s_{t},\omega_{t},a_{t})\); when \(\beta_{t}=1\), \(F_{t}(s_{t},\omega_{t},a_{t})=R_{t}^{(1)}-M_{\Omega}^{*}(s_{t},\omega_{t})\), so,

\[\Delta\[ \begin{split}\tilde{R}_{t}^{(1)}-M^{*}(s_{t},\omega_{t},a_{t})& \geq r_{t}+\gamma\sum_{s_{t+1}}\text{P}(s_{t+1}\mid s_{t},\tilde{a}^{*})\tilde{M _{\Omega}}^{(1)}(\omega,s_{t+1})-M^{*}(s_{t},\omega_{t},a_{t})\\ &=r_{t}+\gamma\sum_{s_{t+1}}\text{P}(s_{t+1}\mid s_{t},\tilde{a}^ {*})\tilde{M_{\Omega}}^{(1)}(\omega,s_{t+1})-r_{t}-\gamma\sum_{s_{t+1}}\text{P} (s_{t+1}\mid s_{t},a^{*})M_{\Omega}^{*}(\omega,s_{t+1})\\ &=\gamma\Bigg{(}\sum_{s_{t+1}}\text{P}(s_{t+1}\mid s_{t},a_{t}) \tilde{M_{\Omega}}^{(1)}(\omega,s_{t+1})-\sum_{s_{t+1}}\text{P}(s_{t+1}\mid s_ {t},a_{t})M_{\Omega}^{*}(\omega,s_{t+1})\Bigg{)}\\ &=\gamma\sum_{s_{t+1}}\text{P}(s_{t+1}\mid s_{t},a_{t})\Big{(} \tilde{M}_{\Omega}^{(1)}(\omega,s_{t+1})-M_{\Omega}^{*}(\omega,s_{t+1})\Big{)} \\ &\geq-\gamma\|\Delta_{t}\|\\ \end{split}  \tag{12}\]

\[ \begin{split}\tilde{R}_{t}^{(1)}-M^{*}(s_{t},\omega_{t},a_{t})& =\sum_{i=0}^{h_{(1)}^{*}}\gamma^{i}r_{t+i}+\gamma^{h_{(1)}^{*}+1} \tilde{M}^{(1)}\Big{(}s_{t+h_{(1)}^{*}+1},\omega_{t+h_{(1)}^{*}+1},\tilde{a}^ {*}\Big{)}-M^{*}(s_{t},\omega_{t},a_{t})\\ &\leq\sum_{i=0}^{h_{(1)}^{*}}\gamma^{i}r_{t+i}+\gamma^{h_{(1)}^{ *}+1}\tilde{M}_{\pi}^{(1)}\Big{(}s_{t+h_{(1)}^{*}+1}\Big{)}\\ &-\left(\sum_{i=0}^{h_{(1)}^{*}}\gamma^{i}r_{t+i}+\gamma^{h_{(1)} ^{*}+1}M^{*}\Big{(}s_{t+h_{(1)}^{*}+1},\omega_{t+h_{(1)}^{*}+1},a^{*}\Big{)} \right)\\ &=\gamma^{h_{(1)}^{*}+1}\Big{(}\tilde{M}^{(1)}\Big{(}s_{t+h_{(1) }^{*}+1},\omega_{t+h_{(1)}^{*}+1},\tilde{a}^{*}\Big{)}-M^{*}\Big{(}s_{t+h_{(1) }^{*}+1},\omega_{t+h_{(1)}^{*}+1},a^{*}\Big{)}\Big{)}\\ &\leq\gamma\Big{(}\tilde{M}^{(1)}\Big{(}s_{t+h_{(1)}^{*}+1}, \omega_{t+h_{(1)}^{*}+1},\tilde{a}^{*}\Big{)}-M^{*}\Big{(}s_{t+h_{(1)}^{*}+1}, \omega_{t+h_{(1)}^{*}+1},a^{*}\Big{)}\Big{)}\\ &\leq\gamma\|\Delta_{t}\|\end{split}  \tag{13}\]

The proof of Theorem 2 is an extension of the work by [PERSON] et al. (2016). This theorem is applicable only to deterministic scenarios, which is a common assumption in episodic memory-based algorithms ([PERSON] et al., 2013). To establish a more precise characterization, we consider a broader class of MDPs, known as approximately deterministic MDPs. ## Appendix C

This appendix provides the proof for Theorem 3. Proof. : \[ \begin{array}{l}M_{\Omega}^{*}(\omega,s^{\prime})-M_{\Omega}^{\pi}(\omega, s^{\prime})\\ =M_{\Omega}^{*}(s,\omega^{*})-M_{\Omega}^{\pi}(s,\omega)\\ =U^{*}(s,\omega^{*})-M_{\Omega}^{\pi}(s,\omega^{*})+M_{\Omega}(s,\omega^{*})- M_{\Omega}^{\pi}(s,\tilde{a})\\ \leq\varepsilon+M_{\Omega}(s,\tilde{a})-M_{\Omega}^{\pi}(s,\omega)\\ =\varepsilon+\big{(}\tilde{M}_{\Omega}(s,\omega)-M_{\Omega}^{\pi}(s,\omega) \big{)}+\big{(}M_{\Omega}^{*}(s,\omega)-M_{\Omega}^{\pi}(s,\omega)\big{)}\\ \leq 2\varepsilon+\gamma\big{(}M_{\Omega}^{*}(\omega,s^{\prime})-M_{\Omega}^{ \pi}(\omega,s^{\prime})\big{)}\\ \end{array} \] (14)

\[ \begin{array}{l}V^{*}(s)-V^{\pi}(s)\\ =M^{*}(s,\omega,a^{*})-M^{\pi}(s,\omega,\tilde{a})\\ =M^{*}(s,\omega,a^{*})-\tilde{M}(s,\omega,a^{*})+\tilde{M}(s,\omega,a^{*})-M^{ \pi}(s,\tilde{a})\\ \leq\varepsilon+\tilde{M}(s,\tilde{a})-M^{\pi}(s,\tilde{a})\\ =\varepsilon+\big{(}\tilde{M}(s,\omega,\tilde{a})-M^{*}(s,\omega,\tilde{a})\big{)} +\big{(}M^{*}(s,\omega,\tilde{a})-M^{\pi}(s,\omega,\tilde{a})\big{)}\\ \leq 2\varepsilon+\gamma\big{(}V^{*}(s)-V^{\pi}(s)\big{)}\end{array}  \tag{15}\]

The above proof ensures the applicability of the OptionEM method in nearly deterministic environments, which closely resemble real-world scenarios. ## References

* [PERSON] et al. (2019) [PERSON]; [PERSON]; [PERSON]; [PERSON]; [PERSON] [PERSON]; [PERSON] [PERSON] Reinforcement learning, fast and slow. _Trends Cogn. Sci._**2019**, _23_, 408-422. [CrossRef] [PubMed]
* [PERSON] et al.