## Appendix A
### Random Reinforced Forest Theorems  
**Theorem A1** (**Random Reinforced Forest Theorem 1 (Rrft 1)**). : _Let \(M\) be a total number of possible RFs (i.e., possible states), of which \(B\) are optimal. If \(B\lll M\) (i.e., considerably small), then the probability of not finding any optimal RRF with DQL is \(\approx\)1._  
Proof. : The maximum number of possible states (i.e., possible RFs) explored in DQL is \(N=n\cdot\epsilon\cdot s\), where \(\epsilon\) is the percentage of exploration, \(n\) is number of episodes, \(s\) is number of steps per episode of learning. The probability of not exploring an optimal in the first trial, \(P_{1,B}\), is  
\[P_{1,B}=\bigg{(}1-\frac{B}{M}\bigg{)}.\]  
Analogously, the probability of not exploring a optimal state in two trials, \(P_{2,B}\), is  
\[P_{2,B}=\bigg{(}1-\frac{B}{M}\bigg{)}\bigg{(}1-\frac{B}{M-1}\bigg{)}.\]  
If we consider the probability of not finding an optimal in \(N\) trials, \(P_{N,B}\), we obtain  
\[P_{N,B}=\bigg{(}1-\frac{B}{M}\bigg{)}\bigg{(}1-\frac{B}{M-1}\bigg{)}\cdots \bigg{(}1-\frac{B}{M-N+1}\bigg{)}\]  
\[=\bigg{(}\frac{M-B}{M}\bigg{)}\bigg{(}\frac{M-B-1}{M-1}\bigg{)}\cdots\bigg{(} \frac{M-B-N+1}{M-N+1}\bigg{)}\]  
\[=\bigg{(}\frac{(M-B)!}{(M-B-N)!}\bigg{)}\bigg{/}\bigg{(}\frac{M!}{(M-N)!}\bigg{)} =\frac{(\frac{M-B}{N})}{(\frac{M}{N})}.\]  
Let \(\alpha\) be a fraction of \(M\) that are optimal states. In other words,  
\[\alpha=\frac{B}{M}.\]  
As the fraction of optimal states \(B\) goes to \(0\), \(P_{N,B}\) approaches \(1\). Formally,  
\[\lim_{\alpha\to 0}P_{N,B}=\lim_{\alpha\to 0}\frac{(\frac{M-\alpha M}{N})}{(\frac{M}{N})}=1.\]  
**Theorem A2** (**Random Reinforced Forest Theorem 2 (RRFFT 2)). : _Let \(M\) be a total number of possible RFs (i.e., possible states), of which B are optimal. Let \(\left(B=\frac{M}{2}\right)\) and let \(N\) be the number of of explored states in DQL (i.e., the number of trials). Then if \(N\) and \(M\) are large, the probability of not finding any optimal state is_  
\[\frac{\binom{M-M/2}{N}}{\binom{M}{N}}\approx 2^{-N}\approx 0.\] (A1)  
Proof. : Consider the following equality  
\[\frac{\binom{M/2}{N}}{\binom{M}{N}}=\frac{(M/2)!}{M!}\cdot\frac{(M-N)!}{(M/2- N)!}.\] (A2)  
Using the [PERSON]'s approximation, we can rewrite Equation (A2) as  
\[\frac{(M/2)!}{M!}\cdot\frac{(M-N)!}{M/2-N!}\approx\frac{\sqrt{2\pi M /2}\left(\frac{M/2}{e}\right)^{M/2}}{\sqrt{2\pi M}\left(\frac{M}{e}\right)^{M} }\cdot\frac{\sqrt{2\pi(M-N)}\left(\frac{M-N}{e}\right)^{M-N}}{\sqrt{2\pi(M/2- N)}\left(\frac{M/2-N}{e}\right)^{M/2-N}}\] \[P_{2,B}=\bigg{(}1-\frac{B}{M}\bigg{)}\bigg{(}1-\frac{B}{M-1}\bigg{)}.\]0 \[P_{2,B}=\bigg{(}1-\frac{B}{M}\bigg{)}\bigg{(}1-\frac{B}{M-1}\bigg{)}.\]1 \[P_{2,B}=\bigg{(}1-\frac{B}{M}\bigg{)}\bigg{(}1-\frac{B}{M-1}\bigg{)}.\]2  
The expression \(\left(1-\frac{N}{M}\right)^{M/2}\) approximates \(e^{-N/2}\), while the \(\left(1+\frac{N}{M-2N}\right)^{(M+1)/2-N}\) approaches \(e^{N/2}\) when \(M\) is considerably big. Thus,  
\[P_{2,B}=\bigg{(}1-\frac{B}{M}\bigg{)}\bigg{(}1-\frac{B}{M-1}\bigg{)}.\]3  
**Theorem A3** (**Random Reinforced Forest Theorem 3 (RRFT 3)). : _Let \(M\) be a total number of possible RFs (i.e., possible states), of which B are optimal. Let \(N\) be the number of explored states in DQL (i.e., the number of trials) such that \(N<M/4\). There exists a threshold value \(x\) for B that makes the probability of finding at least one optimal state less than \(50\%\)._  
Proof. : Consider the inequality  
\[P_{2,B}=\bigg{(}1-\frac{B}{M}\bigg{)}\bigg{(}1-\frac{B}{M-1}\bigg{)}.\]4 (A3)  
where \(x\) denotes the threshold value we seek.