# Deep Reinforcement Learning Algorithms for Path Planning Domain in Grid-like Environment
## 3 Materials and Methods
### Advantage Actor-Critic and Proximal Policy Optimisation
The formula for step update is presented by Equation (3):  
\[V(S_{t})\gets V(S_{t})+\alpha[R_{t+1}+\gamma V(S_{t+1})-V(S_{t})] \tag{3}\]  
where:  
\(V(S_{t})\)--value of a state \(S\) at time \(t\),  
\(R_{t+1}\)--reward obtained from transforming between states \(S_{t}\) and \(S_{t+1}\),  
\(\alpha\)--actor learning rate,  
\(\gamma\)--discount factor. Equation (3) [8; 45; 46; 47] describes one of the first widely used reinforcement learning algorithm. It is still commonly used as one of the most reasonable ways of learning value-based estimators to solve more straightforward or particular problems or as the critic part of the Actor-Critic algorithms [8; 10; 44]. The update is based on the estimation of this and consecutive state--both of them utterly wrong at the very beginning of the learning--with the one fundamental element--reward generated by the actions. Since the values provided by the value function represent the estimation of all the rewards that are obtainable from this particular state, the values of two consecutive states should differ only by the value of reward generated during the transition. Updating the parameters so that the obtained difference is closer to the actual reward allows the critic to learn how to predict those values precisely. Since both the previous and following state values have to be estimated, the constant shift of the parameters affects not only the estimations but the learning targets as well. This affects the learning in an undesired way and has led to the approach referred to as target critic networks--using slightly outdated parameters for estimating the learning targets and updating them periodically to stabilise the learning process. As the targets become fixed for a period of time, the value function can tune its parameters to resemble expected outputs rather than shift chaotically with every update. This particular approach is widespread and extremely effective [48; 49]; hence it should not be surprising that a somewhat similar technique has been adapted to the actor learning process under the name of Proximal Policy Optimisation. The main concepts of the PPO remain the same--stabilise the learning in order to increase its efficiency. However, it is driven by a slightly different mechanism--clipping the learning loss to reduce the variance. The clipping equation is presented in the Equation (4) [9; 50]. \[L_{CLIP}(\theta)=min(r_{t}(\theta)*A_{t},clip(r_{t}(\theta),1-e,1+e)*A_{t}) \tag{4}\]  
where:  
\(r_{t}(\theta)\)--ratio between the probabilities calculated with current and old parameters,  
\(A_{t}\)--estimated advantage at time \(t\),  
\(\epsilon\)--clip ratio. In Equation (4), the probability of performing the action has been replaced by the ratio between probability under current vs. previous (target) parameters. Even though this increase the absolute value of the losses--as the ratio much often takes higher values (close to 1) than the probability of performing a particular action--this approach decreases the possible variance between the losses. As mentioned previously, the optimisation step's size increases with an agent's increasing belief in action. This can lead to a situation when upon discovery, a new action becomes mistaken for a lucrative and a cycle of exploitation; this possibility creates an avalanche-like process of a massive shift in parameters towards this action, as with every learning iteration, the losses increase drastically. PPO prevents such a situation by ensuring that the loss correlated with agents predictions can only grow as much as the \(\epsilon\) parameter allows during a short period of time [9]. Due to that, minor variances causing the agent to look more optimistically at some actions do not destabilisethe learning as much as they possibly would, thus usually increasing the stability of the entire process [51]. Both implementations of the algorithms used in this paper are utilising the deep neural network as functions approximators.