# Synthetic Experiences for Accelerating DQN Performance in Discrete Non-Deterministic Environments +
## 4 Interpolated Experience Replay
### Problem Description  
\"FrozenLake\" is one example of a non-deterministic world in which an action \(a_{t}\in A\) realised in a state \(s_{t}\in S\) may not consistently lead to the same follow-up state \(s_{t+1}\in S\). FrozenLake is basically a grid world consisting of an initial state \(I\), a final state \(G\) and frozen, as well as unfrozen tiles. The unfrozen tiles equal holes \(H\) in the lake and if the agent falls into one of such, he has to start from the initial state again. If the agent reaches \(G\), he receives a reward of \(1\). The set of possible actions \(A\) consists of the four cardinal directions \(A=\{N,E,S,W\}\). Executing a concrete action (e.g., \(N\)) only results with a probability of \(\frac{1}{3}\) in the corresponding field, but it is also possible that the agent instead performs one of the orthogonal actions (in our example: \(W\) or \(E\)) with the same probability of \(\frac{1}{3}\) for each case. This behaviour makes the environment non-deterministic. Because there is a discrete number of states the agent can reach, we can denote the problem as discrete as well. The environment used for evaluation is the \"FrozenLake8x8-v0\" environment from OpenAI Gym [7], as depicted in Figure 1.  
In addition to the described version, we changed the reward function to return a reward of \(-1\) in the case of falling into a hole and \(5\) for reaching the goal. As the first adaption is crucial for our approach, the second change helps the learner to solve the environment. Both changes intensify the received rewards and therefore the experienced transitions. Assigning a negative reward to the end of an episode (hole) makes it possible to calculate an average reward containing an additional value (see below). By testing different final rewards (goal), we could observe that the agent performed best with a reward of \(5\). The decision to focus on the presented environment was taken because: (1) it is a relatively well-known problem in the RL community (OpenAI Gym); (2) our presented approach is designed for discrete and non-deterministic environments. To add more variability, we used three different state encodings (see Section 5.1). The non-deterministic character of the problem comes with difficulties that are described in the following paragraph: If an action is chosen that leads the agent in the direction of the goal, but because of the slippery factor, it is falling into a hole, it additionally receives a negative reward and creates the following experience: \(e_{t}=(s_{t},a_{t},-1,s_{t+1})\)If this experience is used for a \(Q\) update, it misleadingly shifts the state-action value away from a positive value. We denote the slippery factor for executing a neighbouring action as \(c_{\text{slip}}\), the resulting rewards for executing the two neighbouring actions as \(r_{t}^{\text{right}}\) and \(r_{t}^{\text{left}}\) and the reward for executing the intended action as \(r_{t}^{\text{int}}\) and can then define the true expected reward for executing \(a_{t}\) in \(s_{t}\) as follows:  
\[r_{t}^{\text{exp}}=\frac{c_{\text{slip}}}{2}\cdot r_{t}^{\text{right}}+\frac{c _{\text{slip}}}{2}\cdot r_{t}^{\text{left}}+(1-c_{\text{slip}})\cdot r_{t}^{ \text{int}}. \tag{3}\]  
Following Equation (3), we define the experience that takes the state-transition function into account and that does not confuse the learner as the expected experience \(e_{t}^{\text{exp}}\):  
\[e_{t}^{\text{exp}}=(s_{t},a_{t},r_{t}^{\text{exp}},s_{t+1}). \tag{4}\]  
The learner will converge its state-action value \(Q_{\pi}(s_{t},a_{t})\) after seeing enough experiences to:  
\[Q_{\pi}(s_{t},a_{t})=Q^{*}(s_{t},a_{t})=r_{t}^{\text{exp}}+\gamma\max_{a^{ \prime}}Q^{*}(s_{t+1},a^{\prime}). \tag{5}\]  
A Q update with received (misleading) experiences comes with the effect of oscillation as the non-deterministic property of the environment creates rewards and follow-up states that might lead in completely opposite directions (e.g., brings the agent closer to the goal vs. ends the episode in a hole).