## 8 Random Reinforced Forest Theorems  
In this section, we formulate three theorems on finding optimal RRFs for various datasets. These theorems provide a theoretical basis for explaining some experimental DQL results reported in Section 7. The proofs of these theorems are given in Appendix A.3 for readers interested in technical details.  
Let \(\{T_{1}\), \(T_{2}\), \(T_{3}\),..., \(T_{k}\}\) be the set of trained DTs using \(k\) bootstrap samples from a dataset. There are \(2^{k}-1\) possible RFs. Since each RF is a possible _state_ in the DQL, the maximum number of possible states, \(M\), is \(M=2^{k}-1\). An RRF is said to be a _optimal_ random forest if and only if its performance (i.e., validation accuracy) is greater than a given threshold \(\theta\) (e.g., \(theta=0.95\)). In the theorems below, we use the terms _random forest_ and _state_ interchangeably, because in DQL, each state (i.e., a row in the Q-Table) corresponds to exactly one random forest and vice versa.  
**Theorem 1** (Random Reinforced Forest Theorem 1 (RFFT 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., \(B\) is considerably small than \(M\)), then the probability of not finding any optimal RRF with DQL is \(\approx\)1._  
An immediate corollary of this theorem is that the probability of not finding any optimal state in \(N\) trials, \(P_{N,B}\), is  
\[P_{N,B}=\frac{(\begin{subarray}{c}M-B\\ N\end{subarray})}{(\begin{subarray}{c}M\\ N\end{subarray})}. \tag{10}\]  
If we assume that there is at least one optimal state, given a set of DTs, out of which RRFs are constructed, i.e., \(B=1\), then \(P_{N,1}\) is  
\[P_{N,1}=\frac{(\begin{subarray}{c}M-1\\ N\end{subarray})}{(\begin{subarray}{c}M\\ N\end{subarray})}=\frac{M-N}{M}=\bigg{(}1-\frac{N}{M}\bigg{)}.\]  
Thus, if there are 200 DTs, out of which RRFs can be constructed, then \(M=2^{200}-1\) and \(N=10^{5}\), \(P_{N,1}=0.5\approx 1\). Is there such a value of \(B<M\) for which the probability of not finding any optimal RRF in \(N\) trials is \(\approx\)0? The next theorem gives an answer to this question.  
**Theorem 2** (Random Reinforced Forest Theorem 2 (RFFT 2)).: _Let \(B=M/2\), where \(B\) is the number of optimal states (i.e., optimal RFs) and \(N\) is the number of trials (i.e., the number of explorable states in DQL). Then, if \(N\) and \(M\) are large, the probability of not finding any optimal state is_  
\[\frac{(\begin{subarray}{c}M-M/2\\ N\end{subarray})}{(\begin{subarray}{c}M\\ N\end{subarray})}\approx 2^{-N}\approx 0. \tag{11}\]  
As a function of \(B\), \(P_{N,B}\) increases as \(B\) decreases. The third theorem answers the question, what is the threshold for \(B\) that makes the probability of finding at least one optimal RRF less than 50%.  
**Theorem 3** (Random Reinforced Forest Theorem 3 (RFFT 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 RRF less than 50%._  
If there are 200 DTs, then \(M=2^{200}-1\) and \(N=10^{5}\), then the threshold is \(\approx\)\(8\cdot 10^{54}\) (See Equation (A6)). Thus, even if we have a large number of optimal RFFs, the probability of not finding any optimal RRF is greater 50%.