# Hierarchical Episodic Control
## 3 Hierarchical Episodic Control
### Theoretical Analysis
#### 3.3.2 Convergence Analysis  
In addition to analyzing the statistical properties of value estimation, the convergence of the algorithm is also examined. Consistent with the environmental assumptions of [PERSON] et al. (2016) and [PERSON] et al. (2011) in their respective studies, we first derive convergence guarantees for the algorithm under deterministic scenarios. **Theorem 2**. : _In a finite Markov Decision Process with a discount factor less than 1, the parameterized memory of Algorithm 1 converges to \(Q^{*}\) under the following conditions:_  
_(1) \(\sum_{t}\alpha_{t}(s,\omega,a)=\infty,\sum_{t}\alpha_{t}^{2}(s,\omega,a)<\infty\);_  
_(2) Given that the environment's state transition function is completely deterministic._  
_while \(\alpha_{t}\in(0,1)\) is the learning rate._  
The proof of Theorem 2 is an extension of the work by [PERSON] et al. [16] and can be seen in Appendix B. This theorem is applicable only to deterministic scenarios, which is a common assumption in episodic memory-based algorithms [2]. To establish a more precise characterization, we consider a broader class of MDPs, known as approximately deterministic MDPs. ```
Initializes the episodic memory network and option network  Initializes the target network parameters \(\theta^{\prime}_{(1)}\leftarrow\theta_{(1)},\theta^{\prime}_{(2)}\leftarrow \theta_{(2)},\alpha^{\prime}_{(1)}\leftarrow\alpha_{(1)},\alpha^{\prime}_{(2) }\leftarrow\alpha_{(2)},\phi^{\prime}\leftarrow\phi,\zeta^{\prime}\leftarrow \zeta,\eta^{\prime}\leftarrow\eta\)  Initializes the episodic memory \(\mathbb{M}\) for\(t=1,\ldots,T\)do  Choose Option \(\omega\),execute action \(a\)  receive reward \(r\) and next state \(s^{\prime}\)  store tuple \((s,\omega,a,r,s^{\prime},\omega^{\prime},\beta)\) in memory \(\mathbb{M}\) for\(i\in\{1,2\}\)do  sample N tuples \((s,a,r,s^{\prime},\beta,R_{i}^{i})\) from memory \(\mathbb{M}\) if\(\beta=0\)then  update \(\theta_{(i)}\leftarrow\min_{\theta_{(i)}}\sum\left(R_{t}^{(i)}-M_{\theta}^{i}( s,\omega,a)\right)^{2}\) else  update \(\alpha_{(i)}\leftarrow\min_{\alpha_{(i)}}\sum\left(R_{t}^{(i)}-M_{\alpha}^{i}( s,\omega)\right)^{2}\) endif endfor if\(\mathit{mod}\)\(u=0\)then \(\theta^{\prime}_{(i)}\leftarrow\tau\theta_{(i)}+(1-\tau)\theta^{\prime}_{(i)}\) \(\alpha^{\prime}_{(i)}\leftarrow\tau\alpha_{(i)}+(1-\tau)\alpha^{\prime}_{(i)}\) \(\eta^{\prime}_{(i)}\leftarrow\tau\eta_{(i)}+(1-\tau)\eta^{\prime}_{(i)}\) \(\phi^{\prime}_{(i)}\leftarrow\tau\phi_{(i)}+(1-\tau)\phi^{\prime}_{(i)}\)  update Episodic Memory according Algorithm 2 endif if\(\mathit{t}\)\(\mathit{mod}\)\(p=0\)then  update \(\phi\),\(\
abla_{\phi}f(\phi)=\left.\
abla_{a}M_{\theta_{1}}(s,\omega,a)\right|_{\omega= \pi_{\omega},\omega=\pi_{\theta}(s)}\
abla_{\phi}\pi_{\phi(s)}\) according policy gradient update \(\zeta\),\(\
abla_{\zeta}f(\zeta)=\left.\
abla_{\omega}M_{\alpha_{1}}(s,\omega)\right|_{



**Definition 1**. : _Define \(M_{max}(s_{0},\omega_{0},a_{0})\) as the maximum value obtained from the trajectory, which starts from the point \((s_{0},\omega_{0},a_{0})\):_

\[M_{\max}(s_{0},\omega_{0},a_{0}):=\max_{ \begin{subarray}{c}(s_{1},\cdots,s_{T}), (\omega_{1},\cdots,\omega_{T}),(a_{1},\cdots,\Delta_{T})\\ s_{i_{1}}\in\operatorname{supp}(P(\cdot|s_{i},\omega_{i},a_{i}))\end{subarray} } \sum_{t=0}^{T}\gamma^{t}r(s_{t},\omega_{t},a_{t}) \tag{12}\]

\(\mu_{1},\mu_{2}\) _are parameters of this nearly deterministic Markov Decision Process (MDP)_

\[M_{\max}(s,\omega,a)\leq M^{*}(s,\omega,a)+\mu_{1} \tag{13}\]

\[M_{\Omega,\max}(s,\omega)\leq M^{*}_{\Omega}(s,\omega)+\mu_{2} \tag{14}\]

_where \(\mu\) is a threshold that depends on the constraint of environmental randomness._

Based on the definition of nearly deterministic MDPs, the performance guarantee of the method is formulated as follows:

**Lemma 1**.