<jupyter_start><jupyter_text>Banana Collection DRL Report This report presents the experiment results collected during the [Udacity DRL Nanodegree](https://www.udacity.com/course/deep-reinforcement-learning-nanodegree--nd893)[Project 1 - Navigation.](https://github.com/udacity/deep-reinforcement-learning/tree/master/p1_navigation). This report is organized as follows:1) [Algorithm Details](Algorithm-Details)1) [Experimental Approach](Experimental-Approach)1) [Model Results](Model-Results)1) [Conclusion](Conclusion)  Algorithm Details  Reinforcement Learning Theory The environment, described in detail [here](https://github.com/joeworsh/drl_agent_navigation/blob/main/README.md), is well suited for a Deep Reinforcement Learning (DRL) approach. Reinforcement Learning, is a form of machine learning that is designed to optimize policies (i.e. decision makers) which know how to take optimal actions within an environment to reap some optimal reward or return from the environment. Mathematically we can represent the environment and the policy as:$$\tag{1}(s_{t+1}, r_{t+1}) = env(s_t, a_t),$$$$\tag{2}a_t = \pi(s_t).$$where:* $s_t$ is the environment state at time $t$* $a_t$ is the action performed at time $t$* $r_t$ is the reward from the environment received at time $t$* $\pi$ denotes the policy which decides on the action to perform given the current environment stateThis environment will run from time $0 \leq t \leq T$ with $T$ denoting the final timestep. The objective is to find an optimal policy, denoted $\pi_*$, which maximizes the cumulative reward received over all time steps. This is more than just picking an action that will return the best $r_t$ at every timestep $t$, the agent must consider future rewards as well. There are instances where an undesirable action may lead to a larger reward many states in the future. It is important to optimize and that cumulative reward to learn more realistic and better performing policies. The cumulative return is defined at each timestep $t$ as the current reward and all future rewards (not including past rewards):$$\tag{3}G_t=\sum_{i=0}^{T-t} r_{t+i}.$$ The difficulty here is that in practice we don't know these future rewards. The only thing we know with certainty is the past and current rewards. The best we can do here is predict the expected rewards the agent will receive if it were to follow a known policy $\pi$. This concept is denoted mathematically as:$$\tag{4}\tilde{G}_t=\mathbb{E}_\pi\left[\sum_{i=0}^{T-t} r_{\pi, t+i}\right]$$where $r_{\pi, i}$ is the reward received from $env(s_i, \pi(s_i))$. Here the policy $\pi$ is being used to anticipate the future states, and an expectation is used to represent uncertainty about those future returns. One important addition must be made in order to handle this uncertainty: how confident are we in our ability to predict the future rewards? If we are very confident then it would make sense to consider all future rewards with equal weighting to ensure we getting the highest cumulative reward possible. However, if we're not confident in our ability to predict future rewards we need to consider that error to ensure we don't act too confidently when we're wrong. This is addressed with a discounting factor $0 \leq \gamma \leq 1$ which is exponentially applied at each timestep as:$$\tag{5}\tilde{G}_t=\mathbb{E}_\pi\left[\sum_{i=0}^{T-t} \gamma^i r_{\pi, t+i}\right].$$The farther this equations gets from the current time $t$ the smaller this discount factor gets. The discount is visualized below for several different values of $\gamma$ up $1000$ timesteps forward.<jupyter_code>plt.figure(figsize=(8,6))
g_vals = [1.0, 0.999, 0.99, 0.9, 0.5, 0.1, 0.0]
g = np.array(g_vals).reshape([-1, 1])
g = np.tile(g, [1, 1000])
g = np.cumprod(g, axis=1)
for g_val, g_axis in zip(g_vals, g):
    plt.plot(g_axis, label=f"$\gamma={g_val}$")
plt.xlabel("Time into future $i$")
plt.ylabel("$\gamma$")
plt.legend()
plt.show()<jupyter_output><empty_output><jupyter_text>It is evident here how far into the future each of these $\gamma$ values will look. The selection of $\gamma$ is of paramount importance with every Reinforcement Learning problem. An important realization emerges while inspecting the formula of $\tilde{G}_t$ above. This represents the "score-to-go" where at the final timestep $T$, $G_T=r_T$ and $G_{T-1}=r_{T-1} + G_T$. This recursive pattern holds true for any value of $t$: $G_t=r_t+G_{t+1}$. This recursive pattern is the same pattern that is used in [Dynammic Programming](https://en.wikipedia.org/wiki/Dynamic_programming) (DP), which is the discipline of optimizing sequential (dynamic) problems. In DP this is called the [Bellman Equation](https://en.wikipedia.org/wiki/Bellman_equation) and is traditionally represented as the value $v$ of a state. In the RL paradigm the value of a state (with discounting) is defined as:$$\tag{6}v_\pi(s)=\mathbb{E}_\pi\left[r_t + \gamma v_\pi(s_{t+1}) \; \middle| \; s_t=s\right].$$ This value function is important, but it still doesn't give any information on which action should be selected at any state. The value function can be adapted to consider the value of an action at any given state easily. This is called the action-value function, $q$:$$\tag{7}q_\pi(s, a)=\mathbb{E}_\pi\left[r_t + \gamma \; \underset{a_{t+1}}{\text{max}}\:q_\pi(s_{t+1}, a_{t+1}) \; \middle| \; s_t=s, a_t=a\right].$$ $q_\pi$ tells us the expected cumulative return of selecting action $a$ given state $s$ and then continuing to follow policy $\pi$ until the episode ends. It accomplishes this was the recurrent relation from the Bellman Equation. The importance of this equation is that it identifies what truely needs to be learned for any decision making process. An optimal policy, $\pi_*$, will always select the action that maximizes it's expected cumulative return:$$\tag{8}\pi_*(s) = \underset{a}{arg\:\text{max}}\:q(s, a).$$ The objective then is to learn a good representation of the action-value function $q$. If we can learn a good representation of $q$ then we know how to use it to act optimally within the environment.  Learning $q(s, a)$ The action-value function can be represented by any parametric or non-parametric mathematical structure that is capable of handling the forms of $s$ and $a$ as inputs and producing a real-valued number as output. This is simple when $s$ and $a$ are both discrete options from a finite set. For example:* $s \in \left[1, 2, 3, 4, 5, 6, 7, 8, 9 \right]$* $a \in \left[\text{move up}, \text{move down}, \text{move left}, \text{move right} \right]$which can represent discretes cell on a 3x3 grid and options to move in each direction. When states and actions are discrete like this a table can be used where the rows are the different states, the columns are the different actions and the value in each cell is $q(s, a)$. However, a table will not work if one or both of $s$ and $a$ are not integers that come from a finite set.  Deep Q-Networks When the inputs are one or more real-valued numbers, represented by the $n$-dimensional vector $s \in \mathbb{R}^n$, this vector would need to be discretized in order to use a table to represent $q(s, a)$. However, it may not be feasible to discretize $s$ in a way that is both sufficiently representative and computationally feasible. In this case a model capable of handling real-valued vector input, such as a [neural network](https://en.wikipedia.org/wiki/Neural_network), is required. In this case the input to the neural network is the real-valued $n$-dimensional vector $s$ and it has an output node for each of the $m$ actions. The value in each of the output cells corresponds to the action-value for the input cell and the associated action. An example of this neural network architecture is shown below: Neural networks are parameterized by a set of learnable weights and biases denoted as the learnable parameters $\theta$. These weights allow the network to represent any function that is intended to be learned in a machine learning problem. The correct values of $\theta$ are learned incrementally by computing a loss, that evaluates how well a neural network is performing, and then making small updates to $\theta$ that will improve the loss. Overtime these values will converge on an optimized set of parameters that enable the neural network to make intelligent decisions related to the problem it was trained on. When using a parameterized model, like a neural network, the parameters $\theta$ will be shown as an input to the action-value function to indicate which model is being used to compute the value: $q(s, a; \theta)$.In RL, specifically Q-Learning, the loss is defined as:$$\tag{9}\ell(\theta)=\mathbb{E}_{(s,a,r,s') \sim p(D)}\left[\left(r + \gamma \; \underset{a'}{\text{max}}\:q(s', a'; \theta^{-}) - q(s, a; \theta)\right)^2\right].$$ This loss can seem intimidating at first but it can be simply broken down and will begin to look like a standard [mean-squared-error](https://en.wikipedia.org/wiki/Mean_squared_error) which is common in any machine learning or regression problem.First, observe that the inputs to the action-value function in the loss function, $(s, a, r, s')$ are sample from a dataset $D$ distributed according to some probability of the samples within dataset $D$. We assume that we have a dataset of experiences, capturing previously seens states, the action that was performed at the state, the reward that was received and the state that followed. This tuple represents a single experience that we wish to learn from. As we engage with the environment we are building this dataset with real experiences that our model is having. The likelihood of this dataset, $p(D)$ helps to determine which experiences we should learn from. This could be a simple uniform distribution, i.e. $p(D) \triangleq U(d)$, or it adapt to give a higher likelihood to experiences that the model is not as familiar with. The latter is called Prioritized Experience Replay [[1]](1) and it uses the magnitude of the loss above to decide how familiar the model is with that experience. When the loss is larger for some sample it will be more likely to see that sample again. The $\mathbb{E}_{(s,a,r,s') \sim p(D)}$ component of the loss function is simply showing that while learning the experiences we are learning on are being sampled from that dataset.The next component to understand is $q(s, a; \theta)$ which tells us what the model, parameterized by $\theta$, thinks the action-value function for $s$ and $a$ should be. This is ultimately the value we hope our model will be able to produce accurately. It is used here as the prediction input to a mean-squared-error loss function.Finally, $r + \gamma \; \underset{a'}{\text{max}}\:q(s', a'; \theta^{-})$ acts as an approximation of the actual value we hope our model will learn to represent. Ultimately we hope that our model will learn the true cumulative reward that follows any state action pair - however it would be computationally inefficient if we were to simulate full episodes and train only on sequential experiences. It is far more important that we can learn from individual experiences which is why the cumulative return is approximated by the known reward given for an experience and the approximated return of the next state: $\underset{a'}{\text{max}}\:q(s', a'; \theta^{-})$.  Target Networks Notice that in the loss function above there are two sets of learnable parameters present: $\theta$ and $\theta^-$. This is an important feature of the Deep Q-Network (DQN) [[2]](2) which helps to address an important problem that causes divergence while training. If $\theta$ were used directly to compute both the label and prediction, as described above, it would be equivalent to trying to optimize on a moving target. It's as if the model is a dog chasing the its own tail: as it gets closer to its tail the tail pulls away. Interestingly Mnih et al [[2]](2) showed that this circular dependency can be broken by simply creating a target network that lags slightly behind the learned model, denoted $\theta^-$. An additional hyperparameter is added that controls how often the target network parameters $\theta^-$ are updated towards the actual $\theta$ values.  Double Q-Networks An important discovery regarding DQN performance, presented by Van Hasselt et al [[3]](3), is that the DQN is susceptable to overestimating the value of actions. This overestimation can lead to poor performance during training because it always selects the action with the highest estimated value when computing the loss. Overestimation can destabilize training and cause the learner to pursue policies that are not optimal in the context of the environment. One way to address this overestimation is regularize the estimating with another Q model that must learn to agree on which actions are best. It easy to see how Equation 7 can be rewritten to split the max operation into a call to $q$ and an argmax call:$$\tag{10}q_\pi(s, a)=\mathbb{E}_\pi\left[r_t + \gamma \; q(s_{t+1}, \underset{a}{arg\:\text{max}}\:q(s_{t+1}, a; \theta); \theta^{-}) \; \middle| \; s_t=s, a_t=a\right].$$ Note that the primary network, called the online network, is used to decide which action is best but the target network, $\theta^{-}$, is used to estimate the value of the selected action. It has been proven that this discontinuation is powerful enough to help stabilize the learning process [[3]](3). When put into the loss function it now looks like:$$\tag{11}\ell(\theta)=\mathbb{E}_{(s,a,r,s') \sim p(D)}\left[\left(r + \gamma \; q(s', \underset{a'}{arg\:\text{max}}\:q(s', a'; \theta); \theta^{-}) - q(s, a; \theta)\right)^2\right].$$  Dueling Q-Networks One final improvement to the vanilla DQN will be mentioned here: the dueling DQN [[4]](4). In the RL literature the value of a state $v(s)$ is related to the action-value $q(s, a)$ through the advantage, $A(s, a)$ of the action $a$ in state $s$:$$\tag{12}q(s, a)=v(s)+A(s, a).$$In the same way that creating a Double DQN helps to eliminate internal interdependency to stabilize training, a network can be updated to independently predict both the value and advantage and then combine them to produce $q(s, a)$ [[4]](4). An example of a Dueling DQN architecture is shown below:  Experimental Approach In this project, a DQN [[2]](2) with options to support Prioritized Replay [[1]](1), Double DQN [[3]](3) and Dueling DQN [[4]](4) is implemented using only [PyTorch](https://pytorch.org/). The objective of this project is to train an agent that is capable of the winning the Banana Collection game by getting an average score of 13 or greater over 100 episodes. The way to achieve this goal is to implement the code correctly and find a set of hyperparameter values that enables good learning for this environment. The hyperparameters that may be tuned for this model are as follows:* hidden_layers: comma-separated list of integers describing the number of nodes in each layer (where the length of the list describes the number of layers). Defaults to [256,].* episodes: The number of episodes to train over. Defaults to 10000.* batch_size: The number of (s, a, r, s') experiences included in each mini-batch. Defaults to 128.* buffer_size: The experience replay buffer is first-in-first-out structure. This parameter sets the maximum number of entires that can be in the buffer at the same time. Defaults to 10000.* update_rate: Sets the rate, in steps, at which the online network parameters $\theta$ are trained. Defaults to 10.* learning_rate: Sets the step size to use during stochastic gradient descent updates. Defaults to 1e-3.* discount_rate: Sets the value of $\gamma$ as described [above](gamma). Defaults to 1e-3.* epsilon: Sets the starting value of $\epsilon$ for an $\epsilon$-greedy policy. Defaults to 1.* epsilon_decay: Sets the exponential decay rate for $\epsilon$. $\epsilon_{i+1}=\text{epsilon_decay}*\epsilon_i$. Defaults to 0.99.* epsilon_decay_rate: Sets the rate, in epsidoes, at which to apply the epsilon to decay. When set to 1 this creates a smooth, continuous curve for $\epsilon$. When set to a larger integer it will create a stair-step function with each stair width being equal to this decay rate. Defaults to 1000.* min_epsilon: Sets minimum allowable value of $\epsilon$ while decaying. Once this minimum is hit it will stop decaying. Defaults to 1e-1.* tau: Controls the step size used when updating the target network parameters $\theta^{-}$ towards the online network $\theta$. This step is performed at the update rate defined above. Defaults to 1e-3.* replay: Determine the type of replay buffer to use. Options: "uniform" to sample $U(D)$; "prioritized" to sample with priority sampling as described [above](prioritized_replay). Defaults to uniform.* prioritized_replay_damp: Sets the damping term $\alpha$ when using prioritized replay as defined by Schaul et al [[1]](1) where $0 \leq \alpha \leq 1$. Defaults to 0.1.* e_constant: Sets constant $e$ when using prioritized replay to ensure samples don't get starved out [[1]](1). Defaults to 0.01.* prioritized_replay_beta_anneal_rate: Sets the $\beta$ annealing rate, in episodes, when using prioritized replay as defined by Schaul et al [[1]](1). $\beta$ starts at 1 and anneals towards zero at the rate defined over training. Defaults to 1 (i.e. every episode it decays toward zero).* learning_start: The required number of experiences in the buffer before learning will officially start. Defaults to 1000.* double_dqn: True to use a [Double DQN](Double-Q-Networks) approach; False otherwise. Defaults to False.* dueling_dqn: True to use a [Dueling DQN](Dueling-Q-Networks) approach; False otherwise. Defaults to False. In this project three different experiments are performed:1) Train a network with some good default values (according to open source libraries like [RLLib](https://docs.ray.io/en/master/rllib.html))1) Perform a grid search over the most important set of hyperparameters1) Perform a training run with [RLLib](https://docs.ray.io/en/master/rllib.html)) to act as a reference benchmark The results of these three experiments are presented below.  Model Results  Experiment 1 - Good Default Parameters In this experiment a model is trained with the parameters listed below. Parameters that are not included in the list fallback to the default values listed above. With the default hidden layers set, this is a simple 3-layer feed forward network with the hidden layer having 256 nodes. This architecture is used in all experiments shown below.<jupyter_code>params = {
    "episodes": 5000,
    "batch_size": 64,
    "learning_rate": 5e-4,
    "discount_rate": 0.99,
    "update_rate": 4,
    "epsilon_decay": 0.99,
    "epsilon_decay_rate": 1,
    "min_epsilon": 0.01,
    "replay": "prioritized",
    "prioritized_replay_damp": 0.6,
    "e_constant": 1e-6,
    "prioritized_replay_beta_anneal_rate": 100,
    "learning_start": 64,
    "double_dqn": True,
    "deuling_dqn": True
}<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.08929885419951646, 'fraction_numerical': 0.010722169662567014, 'mean_word_length': 4.701827989211867, 'pattern_counts': {'":': 15, '<': 9, '<?xml version=': 0, '>': 9, 'https://': 10, 'lorem ipsum': 0, 'www.': 1, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '2', 'dir': 'jupyter-structured-clean-dedup', 'id': '518532', 'license': 'MIT', 'n_tokens_mistral': 5247, 'n_tokens_neox': 4912, 'n_words': 2735, 'path': 'Report.ipynb', 'repo_name': 'joeworsh/drl_agent_navigation', 'size': '19026'}