# Pseudo Random Number Generation through Reinforcement Learning and Recurrent Neural Networks
## 2 Materials and Methods
### Reinforcement Learning (RL)  
For a comprehensive, motivational, and thorough introduction to RL, we strongly suggest reading from 1.1 to 1.6 in [8]. RL is learning what to do in order to accumulate as much reinforcement as possible during the course of action. This very general description, known as _the RL problem_, can be framed as a sequential decision-making problem, as follows. Assume an _agent_ is interacting with an _environment_. When the agent is in a certain situation--a _state_--it has several options, called _actions_. After each action, the environment will take the agent to a next state, and will provide it with a numerical _reward_, where the pair \"state, reward\" may possibly be drawn from a joint probability distribution, called the _model_ or the _dynamics_ of the environment. The agent will choose actions according to a certain strategy, called _policy_ in the RL setting. The RL problem can then be stated as finding a policy maximizing the expected value of the total reward accumulated during the agent-environment interaction. To formalize the above description, see Figure 1 representing the agent-environment interaction. At each time-step \(t\), the agent receives a state \(S_{t}\in\mathcal{S}\) from the environment, and then selects an action \(A_{t}\in\mathcal{A}\). The environment answers with a numerical reward \(R_{t+1}\in\mathcal{R}\subset\mathbb{R}\) and a next state \(S_{t+1}\). This interaction gives rise to a _trajectory_ of random variables:  
\[S_{0},A_{0},R_{1},S_{1},A_{1},R_{2},\ldots\]  
In the case of interest to us, \(\mathcal{S},\mathcal{A}\), and \(\mathcal{R}\) are finite sets. Thus, the environment answers the action \(A_{t}=a\) executed in the state \(S_{t}=s\) with a pair \(R_{t+1}=r,S_{t+1}=s^{\prime}\) drawn from a discrete probability distribution \(p\) on \(\mathcal{S}\times\mathcal{R}\), the model (or dynamics) of the environment:  
\[p(s^{\prime},r|s,a):=p(s^{\prime},r,s,a):=\Pr(S_{t+1}=s^{\prime},R_{t+1}=r|S_{ t}=s,A_{t}=a).\]  
Note the visual clue of the fact that \(p(\cdot,\cdot|s,a)\) is a probability distribution for every state-action pair \(s,a\). Figure 1 implicitly assumes that the joint probability distribution of \(S_{t+1},R_{t+1}\) depends on the past only via \(S_{t}\) and \(A_{t}\). In fact, the environment is fed only with the last action, and no other data from the history. This means that, for a fixed policy, the corresponding stochastic process \(\{S_{t}\}\) is Markov. This gives the name Markov Decision Process (MDP) to the data \((\mathcal{S},\mathcal{A},\mathcal{R},p)\). Moreover, it is a _time-homogeneous_ Markov process, because \(p\) does not depend on \(t\). In certain problems, the agent can see only a portion of the full state, called _observation_. In this case, we say that the MDP is _partially observable_. Observations are usually not Markov, because the non-observed portion of the state can contain relevant information for the future. In this paper, we model a PRNG as an agent in a partially observable MDP. When the agent experiences a trajectory starting at time \(t\), it accumulates a _discounted return_\(G_{t}\):  
\[G_{t}:=R_{t+1}+\gamma R_{t+2}+\gamma^{2}R_{t+3}+\cdots=\sum_{k=0}^{\infty} \gamma^{k}R_{t+k+1},\qquad\gamma\in[0,1].\]  
The return \(G_{t}\) is a random variable, whose probability distribution depends not only on the model \(p\), but also on how the agent chooses actions in a certain state \(s\). Choices of actions are encoded by the policy, that is, a discrete probability distribution \(\pi\) on \(\mathcal{A}\):  
\[\pi(a|s):=\pi(a,s):=\Pr(A_{t}=a|S_{t}=s).\]  
A discount factor \(\gamma<1\) is used mainly when rewards far in the future are becoming increasingly less reliable or important, or in _continuing_ tasks, that is, when the trajectories do not decompose naturally into _episodes_. Since the partially observable MDP formulation we use is episodic (see Section 2.2), in this paper we use \(\gamma=1\).