# Synthetic Experiences for Accelerating DQN Performance in Discrete Non-Deterministic Environments +
## 4 Interpolated Experience Replay
### Averaging Rewards  
The intention of our solution is to reduce the amount of training by the creation of synthetic experiences that are as similar as possible to \(e_{t}^{\text{exp}}\). As a current limitation, we focus on estimating \(r_{t}^{\text{exp}}\) and use real observed follow-up states \(s_{t+1}\). That approach is possible because the environment is discrete (this represents a mandatory precondition of our algorithm). Discrete environments provide a limited amount of states and more important corresponding follow-up states, and it is possible to observe and remember them. In continuous environments, we would also need to predict the follow-up state next to the reward, and for this first investigation of the concept of interpolated experiences, we  
Figure 1: The FrozenLake8x8-v0 environment from OpenAI Gym [7].  
decided to keep it simple. To compute an accurate estimation of \(e_{t}^{\text{exp}}\), we need to estimate \(r_{t}^{\text{exp}}\) first.  
The set of all rewards that belong to the experiences that start in the same state \(s_{t}\) and execute the same action \(a_{t}\) can be defined as:  
\[R_{t}:=\big{\{}r_{n}\in\{r|(s,a,r,s^{\prime})\in D_{t}\wedge a=a_{t}\wedge s=s_ {t}\}\big{\}}. \tag{6}\]  
We use the rewards in \(R_{t}\) to calculate the average and denote it as \(r_{t}^{\text{avg}}\). This value holds as a good estimation of \(r_{t}^{\text{exp}}\).  
\[r_{t}^{\text{avg}}=\frac{\sum_{r\in R_{t}}r}{|R_{t}|}, \tag{7}\]  
following this, we can then define \(e_{t}^{\text{avg}}\) as our estimation of \(e_{t}^{\text{exp}}\) as:  
\[e_{t}^{\text{avg}}=(s_{t},a_{t},r_{t}^{\text{avg}},s_{t+1}), \tag{8}\]  
with  
\[e_{t}^{\text{avg}}\approx e_{t}^{\text{exp}}. \tag{9}\]  
The accuracy of this interpolation correlates with the amount of transitions stored in the ER, which start in \(s_{t}\) and execute \(a_{t}\). This comes from the fact that the effect of outliers can be mitigated from enough normal distributed samples. To achieve this, we defined an algorithm that triggers an interpolation after every step the agent takes. A query point \(x_{q}\) is drawn via a sampling method from the state space, and all matching experiences:  
\[D_{\text{match}}:=\{e_{t}\in D_{t}|s_{t}=x_{q}\}, \tag{10}\]  
where their starting point \(s_{t}\) is equal to the query point \(x_{q}\), are collected from the ER. Then for every action \(a\in A\), all experiences that satisfy \(a_{t}=a\) are selected from \(D_{\text{match}}\) in:  
\[D_{\text{match}}^{a}:=\{e_{t}|e_{t}\in D_{\text{match}}\wedge a_{t}=a\}. \tag{11}\]  
The resulting transitions are used to compute an average reward value \(r_{t}^{\text{avg}}\). Utilizing this estimation, a synthetic experience \(e_{t}^{\text{avg}}\) for every distinct next state:  
\[s_{t+1}\in\{s^{\prime}|(s_{t},a_{t},r_{t},s^{\prime})\in D_{\text{match}}^{a }\}, \tag{12}\]  
is created. This results in a minimum of 0 and a maximum of 3 synthetic experiences per action and sums up to a maximum of 12 synthetic transitions per interpolation depending on the amount of stored transitions in the ER. As with the amount of stored real transitions, which can be seen as the combined knowledge of the model, the quality of the interpolated experiences may get better. A parameter \(c_{\text{start\_inter}}\) is introduced that determines the minimum amount of stored experiences before the first interpolation is executed. The associated pseudocode is depicted in Algorithm 1.