# Pseudo Random Number Generation through Reinforcement Learning and Recurrent Neural Networks
## 2 Materials and Methods
### Modeling a PRNG as a MDP  
In [6], we modeled a PRNG as a fully observable MDP in the following way. We chose a bit length for the sequence, say \(B\). The state space is given by all possible bit sequences of length \(B\):  
\[\mathcal{S}:=\{(b_{1},b_{2},\ldots,b_{B}):b_{n}\in\{0,1\}\}.\]  
Action \(1_{n}\) is the action of setting the \(n^{\text{th}}\) bit to 1, and \(0_{n}\) is the action of setting the \(n^{\text{th}}\) bit to 0. The action space is then:  
\[\mathcal{A}=\bigcup_{n=1}^{B}\{1_{n},0_{n}\}.\]  
This finite MDP formulation has \(|\mathcal{S}|=2^{B}\) and \(|\mathcal{A}|=2B\), and was called the Binary Formulation (BF) in [6]. The main problem with BF is the fact that the size \(2B\) of the action set grows linearly with the increasing length \(B\) of the sequence. Above a certain size, it is no longer possible to learn a policy with a high average score. If the size is big enough, no policy can be learned at all because it is almost impossible for an agent to explore an action space so huge within a reasonable time. Consider that for PRNGs, a sequence of 1000 bits is quite short, while for a RL problem, 2000 actions are way too much. In this paper, we overcome this limitation of BF by hiding a portion of the full pseudo-random sequence, letting the agent see and act only on the last \(N\) bits. This removes the correlation between the final length of the sequence and the number of actions, at the cost of introducing a temporal dependency among states, breaking Markovianity and making the resulting MDP partially observable. This new problem is solved by approximating the hidden portion of the state with the hidden state of a recurrent neural network with memory--see Section 2.4 for details. We call this new approach Recurrent Formulation (RF). Let \(N\in\mathbb{N}\) be the number of bits at the end of the full sequence that we want to expose, or, in other words, let the observations space be the set \(\mathcal{O}:=\{0,1\}^{N}\). We want the agent to be able to freely change the last \(N\) bits--that is, the action space \(\mathcal{A}\) coincides with \(\mathcal{O}\). We also fix a predetermined temporal horizon \(T\) for episodes. This means that the size of the action space is \(|\mathcal{A}|=2^{N}\) for a generated sequence of \(T\cdot N\) bits. Both \(|\mathcal{A}|\) and the length of \(S_{T}\) depend on \(N\), but they do not depend on each other. Increasing the length of the generated sequence can then be done by increasing the horizon \(T\), leaving the action space size constant. For example, with \(N=3\), the action and observation sets are:  
\[\mathcal{O}=\mathcal{A}=\{[000];[001];[010];[100];[011];[101];[110];[111]\}.\]  
Continuing the example, assume at \(t=0\) we start from a random initial state \(S_{0}=O_{0}=[001]\), and that \(A_{0}=[111]\). Now, the full state is \(S_{1}=[001111]\), but only the last three bits \(O_{1}=[111]\) are observed by the agent. If the agent now chooses \(A_{1}=[101]\), the full state becomes \(S_{2}=[001111101]\), and so on. If we set the episodes' length to 100, at the end of the episode the full state is a 300 bit sequence. Clearly, this formulation can work only if the policy approximator \(\pi(\cdot|\cdot;\theta)\) can preserve some information from the time series given by the past observations. Recurrent neural networks can model memory, and for this reason, are one of the possible approaches to process time series, and temporal relationships among data in general. This is very useful in RL environments where, from the point of the view of the agent, the Markov property does not hold, as it is typically the case in many partially observable environments. This approach was suggested in [12]--see [13; 14] for examples of cases far different from ours. State-of-the-art recurrent neural networks for this kind of problem are the Gated Recurrent Unit (GRU) ones, and the Long-Short Term Memory (LSTM) ones. Typically, GRU performs better than LSTM, but for this particular formulation we have experienced good performance with LSTM.