Atari Games

Prioritized Experience Replay is a type of experience replay in reinforcement learning where we more frequently replay transitions with high expected learning progress, as measured by the magnitude of their temporal-difference (TD) error. This prioritization can lead to a loss of diversity, which is alleviated with stochastic prioritization, and introduce bias, which can be corrected with importance sampling. The stochastic sampling method interpolates between pure greedy prioritization and uniform random sampling. The probability of being sampled is ensured to be monotonic in a transition's priority, while guaranteeing a non-zero probability even for the lowest-priority transition. Concretely, define the probability of sampling transition $i$ as $$P(i) = \frac{p_i^{\alpha}}{\sum_k p_k^{\alpha}}$$ where $p_i > 0$ is the priority of transition $i$. The exponent $\alpha$ determines how much prioritization is used, with $\alpha=0$ corresponding to the uniform case. Prioritized replay introduces bias because it changes this distribution in an uncontrolled fashion, and therefore changes the solution that the estimates will converge to. We can correct this bias by using importance-sampling (IS) weights: $$ w\_{i} = \left(\frac{1}{N}\cdot\frac{1}{P\left(i\right)}\right)^{\beta} $$ that fully compensates for the non-uniform probabilities $P\left(i\right)$ if $\beta = 1$. These weights can be folded into the Q-learning update by using $w\_{i}\delta\_{i}$ instead of $\delta\_{i}$ - weighted IS rather than ordinary IS. For stability reasons, we always normalize weights by $1/\max\_{i}w\_{i}$ so that they only scale the update downwards. The two types of prioritization are proportional based, where $p\_{i} = |\delta\_{i}| + \epsilon$ and rank-based, where $p\_{i} = \frac{1}{\text{rank}\left(i\right)}$, the latter where $\text{rank}\left(i\right)$ is the rank of transition $i$ when the replay memory is sorted according to |$\delta\_{i}$|, For proportional based, hyperparameters used were $\alpha = 0.7$, $\beta\_{0} = 0.5$. For the rank-based variant, hyperparameters used were $\alpha = 0.6$, $\beta\_{0} = 0.4$.

A2C, or Advantage Actor Critic, is a synchronous version of the A3C policy gradient method. As an alternative to the asynchronous implementation of A3C, A2C is a synchronous, deterministic implementation that waits for each actor to finish its segment of experience before updating, averaging over all of the actors. This more effectively uses GPUs due to larger batch sizes. Image Credit: OpenAI Baselines

Trust Region Policy Optimization, or TRPO, is a policy gradient method in reinforcement learning that avoids parameter updates that change the policy too much with a KL divergence constraint on the size of the policy update at each iteration. Take the case of off-policy reinforcement learning, where the policy $\beta$ for collecting trajectories on rollout workers is different from the policy $\pi$ to optimize for. The objective function in an off-policy model measures the total advantage over the state visitation distribution and actions, while the mismatch between the training data distribution and the true policy state distribution is compensated with an importance sampling estimator: $$ J\left(\theta\right) = \sum\_{s\in{S}}p^{\pi\_{\theta\_{old}}}\sum\_{a\in\mathcal{A}}\left(\pi\_{\theta}\left(a\mid{s}\right)\hat{A}\_{\theta\_{old}}\left(s, a\right)\right) $$ $$ J\left(\theta\right) = \sum\_{s\in{S}}p^{\pi\_{\theta\_{old}}}\sum\_{a\in\mathcal{A}}\left(\beta\left(a\mid{s}\right)\frac{\pi\_{\theta}\left(a\mid{s}\right)}{\beta\left(a\mid{s}\right)}\hat{A}\_{\theta\_{old}}\left(s, a\right)\right) $$ $$ J\left(\theta\right) = \mathbb{E}\_{s\sim{p}^{\pi\_{\theta\_{old}}}, a\sim{\beta}} \left(\frac{\pi\_{\theta}\left(a\mid{s}\right)}{\beta\left(a\mid{s}\right)}\hat{A}\_{\theta\_{old}}\left(s, a\right)\right)$$ When training on policy, theoretically the policy for collecting data is same as the policy that we want to optimize. However, when rollout workers and optimizers are running in parallel asynchronously, the behavior policy can get stale. TRPO considers this subtle difference: It labels the behavior policy as $\pi\_{\theta\_{old}}\left(a\mid{s}\right)$ and thus the objective function becomes: $$ J\left(\theta\right) = \mathbb{E}\_{s\sim{p}^{\pi\_{\theta\_{old}}}, a\sim{\pi\_{\theta\_{old}}}} \left(\frac{\pi\_{\theta}\left(a\mid{s}\right)}{\pi\_{\theta\_{old}}\left(a\mid{s}\right)}\hat{A}\_{\theta\_{old}}\left(s, a\right)\right)$$ TRPO aims to maximize the objective function $J\left(\theta\right)$ subject to a trust region constraint which enforces the distance between old and new policies measured by KL-divergence to be small enough, within a parameter $\delta$: $$ \mathbb{E}\_{s\sim{p}^{\pi\_{\theta\_{old}}}} \left[D\_{KL}\left(\pi\_{\theta\_{old}}\left(.\mid{s}\right)\mid\mid\pi\_{\theta}\left(.\mid{s}\right)\right)\right] \leq \delta$$

The methon to overcome catastrophic forgetting in neural network while continual learning

A3C, Asynchronous Advantage Actor Critic, is a policy gradient algorithm in reinforcement learning that maintains a policy $\pi\left(a\_{t}\mid{s}\_{t}; \theta\right)$ and an estimate of the value function $V\left(s\_{t}; \theta\_{v}\right)$. It operates in the forward view and uses a mix of $n$-step returns to update both the policy and the value-function. The policy and the value function are updated after every $t\_{\text{max}}$ actions or when a terminal state is reached. The update performed by the algorithm can be seen as $\nabla\_{\theta{'}}\log\pi\left(a\_{t}\mid{s\_{t}}; \theta{'}\right)A\left(s\_{t}, a\_{t}; \theta, \theta\_{v}\right)$ where $A\left(s\_{t}, a\_{t}; \theta, \theta\_{v}\right)$ is an estimate of the advantage function given by: $$\sum^{k-1}\_{i=0}\gamma^{i}r\_{t+i} + \gamma^{k}V\left(s\_{t+k}; \theta\_{v}\right) - V\left(s\_{t}; \theta\_{v}\right)$$ where $k$ can vary from state to state and is upper-bounded by $t\_{max}$. The critics in A3C learn the value function while multiple actors are trained in parallel and get synced with global parameters every so often. The gradients are accumulated as part of training for stability - this is like parallelized stochastic gradient descent. Note that while the parameters $\theta$ of the policy and $\theta\_{v}$ of the value function are shown as being separate for generality, we always share some of the parameters in practice. We typically use a convolutional neural network that has one softmax output for the policy $\pi\left(a\_{t}\mid{s}\_{t}; \theta\right)$ and one linear output for the value function $V\left(s\_{t}; \theta\_{v}\right)$, with all non-output layers shared.

Random Ensemble Mixture (REM) is an easy to implement extension of DQN inspired by Dropout. The key intuition behind REM is that if one has access to multiple estimates of Q-values, then a weighted combination of the Q-value estimates is also an estimate for Q-values. Accordingly, in each training step, REM randomly combines multiple Q-value estimates and uses this random combination for robust training.

MuZero is a model-based reinforcement learning algorithm. It builds upon AlphaZero's search and search-based policy iteration algorithms, but incorporates a learned model into the training procedure. The main idea of the algorithm is to predict those aspects of the future that are directly relevant for planning. The model receives the observation (e.g. an image of the Go board or the Atari screen) as an input and transforms it into a hidden state. The hidden state is then updated iteratively by a recurrent process that receives the previous hidden state and a hypothetical next action. At every one of these steps the model predicts the policy (e.g. the move to play), value function (e.g. the predicted winner), and immediate reward (e.g. the points scored by playing a move). The model is trained end-to-end, with the sole objective of accurately estimating these three important quantities, so as to match the improved estimates of policy and value generated by search as well as the observed reward. There is no direct constraint or requirement for the hidden state to capture all information necessary to reconstruct the original observation, drastically reducing the amount of information the model has to maintain and predict; nor is there any requirement for the hidden state to match the unknown, true state of the environment; nor any other constraints on the semantics of state. Instead, the hidden states are free to represent state in whatever way is relevant to predicting current and future values and policies. Intuitively, the agent can invent, internally, the rules or dynamics that lead to most accurate planning.

V-trace is an off-policy actor-critic reinforcement learning algorithm that helps tackle the lag between when actions are generated by the actors and when the learner estimates the gradient. Consider a trajectory $\left(x\_{t}, a\_{t}, r\_{t}\right)^{t=s+n}\_{t=s}$ generated by the actor following some policy $\mu$. We can define the $n$-steps V-trace target for $V\left(x\_{s}\right)$, our value approximation at state $x\_{s}$ as: $$ v\_{s} = V\left(x\_{s}\right) + \sum^{s+n-1}\_{t=s}\gamma^{t-s}\left(\prod^{t-1}\_{i=s}c\_{i}\right)\delta\_{t}V $$ Where $\delta\_{t}V = \rho\_{t}\left(r\_{t} + \gamma{V}\left(x\_{t+1}\right) - V\left(x\_{t}\right)\right)$ is a temporal difference algorithm for $V$, and $\rho\_{t} = \text{min}\left(\bar{\rho}, \frac{\pi\left(a\_{t}\mid{x\_{t}}\right)}{\mu\left(a\_{t}\mid{x\_{t}}\right)}\right)$ and $c\_{i} = \text{min}\left(\bar{c}, \frac{\pi\left(a\_{t}\mid{x\_{t}}\right)}{\mu\left(a\_{t}\mid{x\_{t}}\right)}\right)$ are truncated importance sampling weights. We assume that the truncation levels are such that $\bar{\rho} \geq \bar{c}$.

Retrace is an off-policy Q-value estimation algorithm which has guaranteed convergence for a target and behaviour policy $\left(\pi, \beta\right)$. With off-policy rollout for TD learning, we must use importance sampling for the update: $$ \Delta{Q}^{\text{imp}}\left(S\_{t}, A\_{t}\right) = \gamma^{t}\prod\_{1\leq{\tau}\leq{t}}\frac{\pi\left(A\_{\tau}\mid{S\_{\tau}}\right)}{\beta\left(A\_{\tau}\mid{S\_{\tau}}\right)}\delta\_{t} $$ This product term can lead to high variance, so Retrace modifies $\Delta{Q}$ to have importance weights truncated by no more than a constant $c$: $$ \Delta{Q}^{\text{imp}}\left(S\_{t}, A\_{t}\right) = \gamma^{t}\prod\_{1\leq{\tau}\leq{t}}\min\left(c, \frac{\pi\left(A\_{\tau}\mid{S\_{\tau}}\right)}{\beta\left(A\_{\tau}\mid{S\_{\tau}}\right)}\right)\delta\_{t} $$

** Sigmoid Linear Units**, or SiLUs, are activation functions for neural networks. The activation of the SiLU is computed by the sigmoid function multiplied by its input, or $$ x\sigma(x).$$ See Gaussian Error Linear Units (GELUs) where the SiLU was originally coined, and see Sigmoid-Weighted Linear Units for Neural Network Function Approximation in Reinforcement Learning and Swish: a Self-Gated Activation Function where the SiLU was experimented with later.

A Dueling Network is a type of Q-Network that has two streams to separately estimate (scalar) state-value and the advantages for each action. Both streams share a common convolutional feature learning module. The two streams are combined via a special aggregating layer to produce an estimate of the state-action value function Q as shown in the figure to the right. The last module uses the following mapping: $$ Q\left(s, a, \theta, \alpha, \beta\right) =V\left(s, \theta, \beta\right) + \left(A\left(s, a, \theta, \alpha\right) - \frac{1}{|\mathcal{A}|}\sum\_{a'}A\left(s, a'; \theta, \alpha\right)\right) $$ This formulation is chosen for identifiability so that the advantage function has zero advantage for the chosen action, but instead of a maximum we use an average operator to increase the stability of the optimization.

A CoordConv layer is a simple extension to the standard convolutional layer. It has the same functional signature as a convolutional layer, but accomplishes the mapping by first concatenating extra channels to the incoming representation. These channels contain hard-coded coordinates, the most basic version of which is one channel for the $i$ coordinate and one for the $j$ coordinate. The CoordConv layer keeps the properties of few parameters and efficient computation from convolutions, but allows the network to learn to keep or to discard translation invariance as is needed for the task being learned. This is useful for coordinate transform based tasks where regular convolutions can fail.

Go-Explore is a family of algorithms aiming to tackle two challenges with effective exploration in reinforcement learning: algorithms forgetting how to reach previously visited states ("detachment") and from failing to first return to a state before exploring from it ("derailment"). To avoid detachment, Go-Explore builds an archive of the different states it has visited in the environment, thus ensuring that states cannot be forgotten. Starting with an archive beginning with the initial state, the archive is built iteratively. In Go-Explore we: (a) Probabilistically select a state from the archive, preferring states associated with promising cells. (b) Return to the selected state, such as by restoring simulator state or by running a goal-conditioned policy. (c) Explore from that state by taking random actions or sampling from a trained policy. (d) Map every state encountered during returning and exploring to a low-dimensional cell representation. (e) Add states that map to new cells to the archive and update other archive entries.

IMPALA, or the Importance Weighted Actor Learner Architecture, is an off-policy actor-critic framework that decouples acting from learning and learns from experience trajectories using V-trace. Unlike the popular A3C-based agents, in which workers communicate gradients with respect to the parameters of the policy to a central parameter server, IMPALA actors communicate trajectories of experience (sequences of states, actions, and rewards) to a centralized learner. Since the learner in IMPALA has access to full trajectories of experience we use a GPU to perform updates on mini-batches of trajectories while aggressively parallelising all time independent operations. This type of decoupled architecture can achieve very high throughput. However, because the policy used to generate a trajectory can lag behind the policy on the learner by several updates at the time of gradient calculation, learning becomes off-policy. The V-trace off-policy actor-critic algorithm is used to correct for this harmful discrepancy.

A Noisy Linear Layer is a linear layer with parametric noise added to the weights. This induced stochasticity can be used in reinforcement learning networks for the agent's policy to aid efficient exploration. The parameters of the noise are learned with gradient descent along with any other remaining network weights. Factorized Gaussian noise is the type of noise usually employed. The noisy linear layer takes the form: $$y = \left(b + Wx\right) + \left(b\_{noisy}\odot\epsilon^{b}+\left(W\_{noisy}\odot\epsilon^{w}\right)x\right) $$ where $\epsilon^{b}$ and $\epsilon^{w}$ are random variables.

Ape-X is a distributed architecture for deep reinforcement learning. The algorithm decouples acting from learning: the actors interact with their own instances of the environment by selecting actions according to a shared neural network, and accumulate the resulting experience in a shared experience replay memory; the learner replays samples of experience and updates the neural network. The architecture relies on prioritized experience replay to focus only on the most significant data generated by the actors. In contrast to Gorila, Ape-X uses a shared, centralized replay memory, and instead of sampling uniformly, it prioritizes, to sample the most useful data more often. All communications are batched with the centralized replay, increasing the efficiency and throughput at the cost of some latency. And by learning off-policy, Ape-X has the ability to combine data from many distributed actors, by giving the different actors different exploration policies, broadening the diversity of the experience they jointly encounter.

Rainbow DQN is an extended DQN that combines several improvements into a single learner. Specifically: - It uses Double Q-Learning to tackle overestimation bias. - It uses Prioritized Experience Replay to prioritize important transitions. - It uses dueling networks. - It uses multi-step learning. - It uses distributional reinforcement learning instead of the expected return. - It uses noisy linear layers for exploration.

Ape-X DQN is a variant of a DQN with some components of Rainbow-DQN that utilizes distributed prioritized experience replay through the Ape-X architecture.

This method proposes first discretizing observations and calculating the action distribution distance under comparable cases (intersection states).

ACKTR, or Actor Critic with Kronecker-factored Trust Region, is an actor-critic method for reinforcement learning that applies trust region optimization using a recently proposed Kronecker-factored approximation to the curvature. The method extends the framework of natural policy gradient and optimizes both the actor and the critic using Kronecker-factored approximate curvature (K-FAC) with trust region.

NoisyNet-DQN is a modification of a DQN that utilises noisy linear layers for exploration instead of $\epsilon$-greedy exploration as in the original DQN formulation.

Ape-X DPG combines DDPG with distributed prioritized experience replay through the Ape-X architecture.

Bayesian Reward Extrapolation is a Bayesian reward learning algorithm that scales to high-dimensional imitation learning problems by pre-training a low-dimensional feature encoding via self-supervised tasks and then leveraging preferences over demonstrations to perform fast Bayesian inference.

NoisyNet-A3C is a modification of A3C that utilises noisy linear layers for exploration instead of $\epsilon$-greedy exploration as in the original DQN formulation.

NoisyNet-Dueling is a modification of a Dueling Network that utilises noisy linear layers for exploration instead of $\epsilon$-greedy exploration as in the original Dueling formulation.