## 4 Random Reinforced Forests
### Hidden and Dynamic Q-Learning  
Q-Learning is an RL algorithm used in many ML applications. This algorithm starts with the initialization of the so called Q-Table (aka the Q-Matrix) with 0's. The Q-Table rows are the states of the environment and the columns are the actions that the agent can execute. Each cell in the Q-Table specifies the cumulative reward (aka q-value) the agent receives if it executes the corresponding action in the corresponding state. The agent chooses an action by means of (1) _exploitation_ (i.e., the maximum value in the current row is chosen and the action specified by the corresponding column is executed) or (2) _exploration_ (i.e., a random action is chosen). The extent of exploration and exploitation is controlled by the \(\epsilon\) parameter (aka the \(\epsilon\)-value). The greater the \(\epsilon\)-value, the higher the degree of exploration. A best practice is to aggressively explore early on and gradually switch to exploiting the acquired knowledge later (i.e., gradually decay \(\epsilon\) from 1 to 0). After the agent takes an action \(a\) in a state \(s\) and receives a reward \(r\), the entry for \(s\) and \(a\) in the Q-Table (i.e., \(Q(s,a)\)) is updated according to Equation (1), where \(\alpha\) is the learning rate, \(\gamma\) is the discount factor, and \(max\{Q(s^{\prime},a^{\prime})\}\) is the maximum Q-value over all possible actions \(a^{\prime}\) available to the agent in the next state \(s^{\prime}\) to which the environment transitions after \(a\) is executed in \(s\). \[Q(s,a)=(1-\alpha)Q(s,a)+\alpha(r+\gamma\cdot max\{Q(s^{\prime},a^{\prime})\}) \tag{1}\]  
We designed two Q-Learning methods (_hidden_ Q-Learning (HQL) and _dynamic_ Q-Learning (DQL)) for our RRF construction algorithm. Both methods take as input a list of DTs trained on bootstrap samples from a given dataset. Specifically, both methods are given a list of 200 DTs trained on 200 bootstrap samples from a given dataset. The trained DTs are enumerated from 1 to 200. In HQL, the agent has 200 actions (i.e., \(a_{1}\), \(a_{2}\),..., \(a_{200}\)), where \(a_{k}\), \(1\leq k\leq 200\), denotes adding the \(k\)-th trained DT \(T_{\text{S}_{i},\text{D}_{i}}\) to a given RRF. There are 200 states (i.e., \(s_{1}\), \(s_{2}\),..., \(s_{200}\)), each of which specifies the DT last added to the RRF. Thus, \(s_{1}\) signals that DT 1 is last added to the RRF; \(s_{2}\) signals that DT 2 is last added to the RRF, etc. Equivalently, we can interpret \(s_{k}\) to mean that the RRF contains at least one instance of \(k\)-th DT. The initial state  
Figure 2: RRF construction with hidden Q-learning (HQL) and dynamic Q-learning (DQL) described in Section 4.2. \(s_{k}\) is chosen by randomly selecting integer \(k\) from [1, 200] and adding the \(k\)-th DT to the initially empty RRF. We called this method HQL, because the RRF itself is not explicitly specified in the Q-Table (i.e., it is a hidden variable); the RRF is used by the algorithm to compute action rewards every time a DT is added to it. HQL runs for 1000 episodes with 100 steps each. These numbers are arbitrary and can be increased or decreased as required. At each step of an episode, after a DT is added to the RRF, the RRF's validation accuracy is evaluated and the reward is computed as the difference of the current validation accuracy and the previous validation accuracy. The initial validation accuracy is set to the validation accuracy of the initial RRF (i.e., the accuracy of its only randomly selected DT) and becomes the previous validation accuracy. The current validation accuracy is recomputed after the addition of each new DT to the RRF. If at some step of an episode, the RRF's validation accuracy is \(\geq\)90%, RL stops and the RRF is constructed from the Q-Table and persisted. Appendix A.1 gives a step-by-step example of how HQL method works to construct an RRF out of four DTs. In DQL, the states are represented as 200-bit vectors. If bit \(k\) is toggled, the \(k\)-th DT is in the RRF; if bit \(k\) is untogled, the \(k\)-th DT is not in the RRF.