TITLE: Permutation and Combination to find pairs
QUESTION [2 upvotes]: In how many different ways students can be paired such that no pair consists of 2 boys. Given :- Total students = 10, Girls = 7, boys = 3.
What my approach is 3 boys can be paired with 7 girls like G1B1,G2B1,G3B1 etc.which gives 21 ways.Not sure if this is true.
Answer given :630

REPLY [5 votes]: Boy1 can be paired with any one of $7$ girls. For each such choice, Boy2 can be paired with any one of $6$ girls, and Boy3 with any one of $5$ girls. The remaining girls can be divided into pairs in $3$ ways, for a total of $(7)(6)(5)(3)$.
To see that the remaining $4$ girls can be paired in $3$ ways, let one of the remaining girls be Alicia. She can choose her partner in $3$ ways.


TITLE: Is there a simpler method of polynomial multiplication?
QUESTION [0 upvotes]: I've been brushing up on my algebra lately and recently began to refresh my memory on polynomial multiplication. In the case of $monomial \cdot binomial$ this is very straight forward and I can see the usefulness of the expansion; for example: $2x(3 + 2x) = 6x + 4x^2$. This makes it easier to read in my opinion and thus is useful. However, given $polynomial \cdot polynomial$ where there are more than two terms on each it begins to easily confuse me:
$$(a + b + c)(d + e + f)$$
In this case we know that the multiplication is the equivalent of:
$$ad + ae + af + bd + be + bf + cd + ce + cf$$
This is a very simple case and is easy to understand but I can definitely see this growing out of control quickly:
$$(a + b + c)(d + e + f)(g + h + i)$$
Now in this case it expands very quickly and seems like it would be the cleanest answer to a more complex problem; plus it gets confusing to keep track of if you multiply the terms out:
$$adg + adh + adi + aeg + aeh + aei + afg + afh + afi +
bdg + bdh + bdi + beg + beh + bei + bfg + bfh + bfi +
cdg + cdh + cdi + ceg + ceh + cei + cfg + cfh + cfi$$
I understand that multiplication is a foundational operation and thus as a whole is typically the simplest answer (aside from addition); however, is there a simpler (or less confusing) way to perform the multiplication on larger polynomials; or a way to reduce the number of steps needed to reach the answer?
As a side question (if you feel like answering); is there a practical application for polynomial multiplication with more than two terms or is it typically reserved for educational purposes? A single example will do.

REPLY [1 votes]: While there is no simpler way to multiply larger polynomials, there is a method that may make performing the operation easier to visualize. It is commonly known as the box method.

If you line up each polynomial on adjacent sides of a box like the picture shows and multiply each term by every other term, you get boxes that contains every term. It makes the process neater and it makes it easier to see which terms cancel or combine.
I hope this helps.


TITLE: Why must we have $0<|x-p|$ in the definition of function limits?
QUESTION [1 upvotes]: The definition of a function limit is given in my lecture notes as:
$$f(x)\rightarrow L \text{ as } x\rightarrow p \text{ if } \forall \varepsilon>0, \exists \delta>0 \text{ such that }\forall x,\color{red}{0<|x-p|}<\delta \Rightarrow |f(x)-L|<\varepsilon$$
Why do we demand $x\neq p$?
In my lecture notes I also note that the definition for continuity of a function at $p$ stipulates only that $|x-p|<\delta$ and not this additional inequality - why the difference?

REPLY [0 votes]: Exactly as Mr Tim said a function need NOT ne defined at p in order to have existence of the limit. For instance domf=(-1,0)U(0,1) and f(x)=0 on the domain. Then clearly
$\displaystyle \lim_{x \to 0}f(x)$=O despite the fact that the function is not defined at O. The value at p has NOTHING to do with the limit and its existence!


text:
\begin{document}

\maketitle
\begin{abstract}
We introduce a new algorithm for reinforcement learning called Maximum a-posteriori Policy Optimisation (MPO) based on coordinate ascent on a relative-entropy objective. We show that several existing methods can directly be related to our derivation. We develop two off-policy algorithms and demonstrate that they are competitive with the state-of-the-art in deep reinforcement learning. In particular, for continuous control, our method outperforms existing methods with respect to sample efficiency, premature convergence and robustness to hyperparameter settings.
\end{abstract}

\section{Introduction}
Model free reinforcement learning algorithms can acquire sophisticated behaviours by interacting with the environment while receiving simple rewards. Recent experiments \citep{mnih2015human,Jaderberg2016aux, heess2017emergence} successfully combined these algorithms with powerful deep neural-network approximators while benefiting from the increase of compute capacity.

Unfortunately, the generality and flexibility of these algorithms comes at a price: They can require a large number of samples and -- especially in continuous action spaces -- suffer from high gradient variance. Taken together these issues can lead to unstable learning and/or slow convergence. Nonetheless, recent years have seen significant progress, with improvements to different aspects of learning algorithms including stability, data-efficiency and speed,  enabling notable results on a variety of domains, including locomotion \citep{heess2017emergence, Peng16}, multi-agent behaviour \citep{bansal2016multiagent} and classical control \citep{duan2016benchmarking}.

Two types of algorithms currently dominate scalable learning for continuous control problems: First, Trust-Region Policy Optimisation (TRPO; \citealt{schulman15}) and the derivative family of Proximal Policy Optimisation algorithms (PPO; \citealt{schulman2017ppo}). These policy-gradient algorithms are on-policy by design, reducing gradient variance through large batches and limiting the allowed change in parameters. They are robust, applicable to high-dimensional problems, and require moderate parameter tuning, making them a popular first choice \citep{ho2016gail}. However, as on-policy algorithms, they suffer from poor sample efficiency.

In contrast, off-policy value-gradient algorithms such as the Deep Deterministic Policy Gradient (DDPG, \citealt{silver2014deterministic,lillicrap2015continuous}), Stochastic Value Gradient (SVG, \citealt{heess2015learning}), and the related Normalized Advantage Function formulation (NAF, \citealt{gu2016continuous}) rely on experience replay and learned (action-)value functions. These algorithms exhibit much better data efficiency, approaching the regime where experiments with real robots are possible \citep{gu2016deep,her2017}. While also popular, these algorithms can be difficult to tune, especially for high-dimensional domains like general robot manipulation tasks.

In this paper we propose a novel off-policy algorithm that benefits from the best properties of both classes. It exhibits the scalability, robustness and hyperparameter insensitivity of on-policy algorithms, while offering the data-efficiency of off-policy, value-based methods.

To derive our algorithm, we take advantage of the duality between control and estimation by using Expectation Maximisation (EM), a powerful tool from the probabilistic estimation toolbox, in order to solve control problems. This duality can be understood as replacing the question ``what are the actions which maximise future rewards?'' with the question ``assuming future success in maximising rewards, what are the actions most likely to have been taken?''.  By using this estimation objective we have more control over the policy change in both E and M steps, yielding robust learning. We show below that several algorithms, including TRPO, can be directly related to this perspective.
We leverage the fast convergence properties of EM-style coordinate ascent by alternating a non-parametric data-based E-step which re-weights state-action samples, with a supervised, parametric M-step using deep neural networks.

In contrast to typical off-policy value-gradient algorithms, the new algorithm does not require gradient of the Q-function to update the policy. Instead it uses samples from the Q-function to compare different actions in a given state. And subsequently it updates the policy such that better actions in that state will have better probabilities to be chosen.

We evaluate our algorithm on a broad spectrum of continuous control problems including a 56 DoF humanoid body. All experiments used the same optimisation hyperparameters~\footnote{With the exception of the number of samples collected between updates.}. Our algorithm shows remarkable data efficiency often solving the tasks we consider an order of magnitude faster than the state-of-the-art. A video of some resulting behaviours can be found here \href{https://youtu.be/he_BPw32PwU}{\texttt{\bfseries youtu.be/he\_BPw32PwU}}.

\section{Background and Notation}

\subsection{Related Work}
Casting Reinforcement Learning (RL) as an inference problem has a long history dating back at least two decades~\citep{dayan97em}. The framework presented here is inspired by a variational inference perspective on RL that has previously been utilised in multiple studies; c.f.~\citet{dayan97em,neumann11variational,deisenroth2013survey,rawlik12,levine2013variational,florensa2017stochastic}.

Particular attention has been paid to obtaining \textit{maximum entropy} policies as the solution to an inference problem. The penalisation of determinism can be seen encouraging both robustness and simplicity. Among these are methods that perform trajectory optimisation using either linearised dynamics \citep{todorov2008general, toussaint2009robot, levine2013variational} or general dynamics as in path integral control \citep{Kappen05, Theodorou2010}. In contrast to these algorithms, here we do not assume the availability of a transition model and avoid on-policy optimisation. A number of other authors have considered the same perspective but in a model-free RL setting~\citep{neumann11variational,Peters10,florensa2017stochastic,Daniel16} or inverse RL problems~\citep{ziebart2008maximum}. These algorithms are more directly related to our work and can be cast in the same (EM-like) alternating optimisation scheme on which we base our algorithm. However, they typically lack the maximisation (M)-step -- with the prominent exception of REPS, AC-REPS, PI$^2$-GPS and MDGPS~\citep{Peters10,wirth2016model,chebotar2016path,montgomery2016guided} to which our algorithm is closely related as outlined below. An interesting recent addition to these approaches is an EM-perspective on the PoWER algorithm~\citep{LeRoux16a} which uses the same iterative policy improvement employed here, but commits to parametric inference distributions and avoids an exponential reward transformation, resulting in a harder to optimise lower bound.

As an alternative to these policy gradient inspired algorithms, the class of recent algorithms for soft Q-learning (e.g.  \citet{rawlik12,haarnoja2017reinforcement,Fox16} parameterise and estimate a so called ``soft'' Q-function directly, implicitly inducing a maximum entropy policy. A perspective that can also be extended to hierarchical policies \citep{florensa2017stochastic}, and has recently been used to establish connections between Q-learning and policy gradient methods~\citep{odonoghue2016pgq,schulman2017equivalence}. In contrast, we here rely on a parametric policy, our bound and derivation is however closely related to the definition of the soft (entropy regularised) Q-function.

A line of work, that is directly related to the ``RL as inference'' perspective, has focused on using information theoretic regularisers such as the entropy of the policy or the Kullback-Leibler divergence (KL) between policies to stabilise standard RL objectives. In fact, most state-of-the-art policy gradient algorithms fall into this category. For example see the entropy regularization terms used in \citet{mnih2016asynchronous} or the KL constraints employed by work on trust-region based methods \citep{schulman15,schulman2017ppo,Gu17,Ziyu17}. The latter methods introduce a trust region constraint, defined by the KL divergence between the new policy and
the old policy, so that the expected KL divergence over state space is bounded. From the perspective of this paper these trust-region based methods can be seen as optimising a parametric E-step, as in our algorithm, but are ``missing'' an explicit M-step.

Finally, the connection between RL and inference has been invoked to motivate work on exploration. The most prominent examples for this are formed by work on Boltzmann exploration such as \citet{Kaelbling96,Perkins02,sutton1990integrated,odonoghue17uncertainty}, which can be connected back to soft Q-learning (and thus to our approach) as shown in \cite{haarnoja2017reinforcement}.

\subsection{Markov decision Processes}
\label{sec_background}
We consider the problem of finding an optimal policy $\pi$ for a discounted reinforcement learning (RL) problem; formally characterized by a Markov decision process (MDP). The MDP consists of: continuous states $s$, actions $a$, transition probabilities $p(s_{t+1} | s_t, a_t)$ -- specifying the probability of transitioning from state $s_t$ to $s_{t+1}$ under action $a_{t}$ --, a reward function $r(s, a) \in \mathbb{R}$ as well as the discounting factor $\gamma \in [0, 1)$. The policy $\pi(a | s, \a)$ (with parameters $\a$) is assumed to specify a probability distribution over action choices given any state and -- together with the transition probabilities -- gives rise to the stationary distribution $\mu_\pi(s)$.

Using these basic quantities we can now define the notion of a Markov sequence or trajectory $\tau_\pi = \{(s_0, a_0) \dots (s_T, a_T)\}$ sampled by following the policy $\pi$; i.e. $\tau_\pi \sim p_\pi(\tau)$ with $p_\pi(\tau) = p(s_0) \prod_{t>=0} p(s_{t+1} | s_{t}, a_t) \pi(a_t | s_t)$; and the expected return $\bE_{\tau_\pi} \lbrack \sum_{t=0}^\infty \gamma^t r(s_t, s_t) \rbrack$. We will use the shorthand $r_t = r(s_t, a_t)$.

\section{Maximum a Posteriori Policy Optimisation}
\label{sec:MPO}

Our approach is motivated by the well established connection between RL and probabilistic inference. This connection casts the reinforcement learning problem as that of inference in a particular probabilistic model. Conventional formulations of RL aim to find a trajectory that maximizes expected reward. In contrast, inference formulations start from a prior distribution over trajectories, condition a desired outcome such as achieving a goal state, and then estimate the posterior distribution over trajectories consistent with this outcome.

A finite-horizon undiscounted reward formulation can be cast as inference problem by constructing a suitable probabilistic model via a likelihood function $p(O=1|\tau) \propto \exp( \nicefrac{\sum_t r_t}{\alpha} )$, where $\alpha$ is a temperature parameter. Intuitively, $O$ can be interpreted as \textit{the event of obtaining maximum reward by choosing an action}; or the event of succeeding at the RL task~\citep{toussaint2009robot,neumann11variational}. With this definition we can define the following lower bound on the likelihood of optimality for the policy $\pi$:

\begin{align}
\log p_\pi(O=1) &= \log \int p_\pi(\tau) p(O=1|\tau) d \tau
\geq \int q(\tau) \big [ \log p(O=1 | \tau) + \log \frac{p_\pi(\tau)}{q(\tau)} \big] d \tau \\
&=\bE_{q} \Big[ \sum_t r_t / \alpha \Big] - \mathrm{KL} \Big( q(\tau) || p_\pi(\tau) \Big) = \mathcal{J}(q,\pi), \label{eq:ELBO}

\end{align}
where $p_\pi$ is the trajectory distribution induced by policy $\pi(a|s)$ as described in section \ref{sec_background} and $q(\tau)$ is an auxiliary distribution over trajectories that will discussed in more detail below. The lower bound $\mathcal{J}$ is the evidence lower bound (ELBO) which plays an important role in the probabilistic modeling literature. It is worth already noting here that optimizing (\ref{eq:ELBO}) with respect to $q$ can be seen as a KL regularized RL problem.

An important motivation for transforming a RL problem into an inference problem is that this allows us draw from the rich toolbox of inference methods: For instance, $\mathcal{J}$ can be optimized with the familiy of expectation maximization (EM) algorithms which alternate between improving $\mathcal{J}$ with respect to $q$ and $\pi$. In this paper we follow classical \citep{dayan97em} and more recent works  (e.g.\ \citealt{peters2010relative,levine2013variational,Daniel16,wirth2016model}) and cast policy search as a particular instance of this family. Our algorithm then combines properties of existing approaches in this family with properties of recent off-policy algorithms for neural networks.

The algorithm alternates between two phases which we refer to as E and M step in reference to an EM-algorithm. The E-step improves $\mathcal{J}$ with respect to $q$. Existing EM policy search approaches perform this step typically by reweighting trajectories with sample returns \citep{kober2009policy} or via local trajectory optimization \citep{levine2013variational}. We show how off-policy deep RL techniques and value-function approximation can be used to make this step both scalable as well as data efficient. The M-step then updates the parametric policy in a supervised learning step using the reweighted state-action samples from the E-step as targets.

These choices lead to the following desirable properties: (a) low-variance estimates of the expected return via function approximation; (b) low-sample complexity of value function estimate via robust off-policy learning; (c) minimal parametric assumption about the form of the trajectory distribution in the E-step; (d) policy updates via supervised learning in the M step; (e) robust updates via hard trust-region constraints in both the E and the M step.

\subsection{Policy Improvement}
\label{sec:MPO:PI}
The derivation of our algorithm then starts from the infinite-horizon analogue of the KL-regularized expected reward objective from Equation \eqref{eq:ELBO}.
In particular, we consider variational distributions $q(\tau)$ that factor in the same way as $p_\pi$, i.e.\ $q(\tau)=p(s_0)\prod_{t > 0} p(s_{t+1}|s_t,a_t) q(a_t|s_t)$ which yields:

\begin{align}
\mathcal{J}(q, \a) = \bE_{q} \Big\lbrack \sum_{t=0}^\infty \gamma^t \big[ r_t - \alpha \textrm{KL}\big(q(a | s_t) \| \pi(a | s_t, \a) \big) \big] \Big\rbrack + \log p(\a). \label{obj_rl}
\end{align}

Note that due to the assumption about the structure of $q(\tau)$ the KL over trajectories decomposes into a KL over the individual state-conditional action distributions. This objective has also been considered e.g.\ by \cite{haarnoja2017reinforcement,schulman2017equivalence}. The additional $\log p(\a)$ term is a prior over policy parameters and can be motivated by a maximum a-posteriori estimation problem (see appendix for more details).

We also define the regularized Q-value function associated with \eqref{obj_rl} as
\begin{equation}
Q^q_\theta(s,a) = r_0 + \bE_{q(\tau), s_0 = s, a_0 = a} \left [ \sum_{t\geq 1}^\infty \gamma^t \big[r_t - \alpha \textrm{KL}(q_t \| \pi_t) \big] \right ],
\end{equation}
with $\textrm{KL}\big(q_t || \pi_t\big) = \textrm{KL}\big(q(a | s_t) \big) \| \pi(a | s_t, \a) \big)$.
Note that $\textrm{KL}\big(q_0 || \pi_0\big)$ and $p(\theta)$ are not part of the Q-function as they are not a function of the action.

We observe that optimizing $\mathcal{J}$ with respect to $q$ is equivalent to solving an expected reward RL problem with augmented reward $\tilde{r}_t = r_t - \alpha  \log \frac{ q(a_t | s_t)}{\pi(a_t | s_t, \a)}$. In this view $\pi$ represents a default policy towards which $q$ is regularized -- i.e. the current best policy. The MPO algorithm treats $\pi$ as the primary object of interest. In this case $q$ serves as an auxiliary distribution that allows optimizing $\mathcal{J}$ via alternate coordinate ascent in $q$ and $\pi_\a$, analogous to the expectation-maximization algorithm in the probabilistic modelling literature. In our case, the E-step optimizes $\mathcal{J}$ with respect to $q$ while the M-step optimizes $\mathcal{J}$ with respect to $\pi$. Different optimizations in the E-step and M-step lead to different algorithms. In particular, we note that for the case where $p(\a)$ is an uninformative prior a variant of our algorithm has a monotonic improvement guarantee as show in the Appendix \ref{sect:proof}.

\subsection{E-Step}
In the E-step of iteration $i$ we perform a partial maximization of $\mathcal{J}(q, \a)$ with respect to $q$ given $\theta = \theta_i$. We start by setting $q = \pi_{\a_i}$ and estimate the unregularized action-value function:
\begin{equation}
Q^q_{\a_i}(s,a) = Q_{\a_i}(s,a) =
\bE_{\tau_{\pi_i}, s_0 = s, a_0 =a } \left [\sum^\infty_t \gamma^t r_t \right],
\label{eq:q_one_step}
\end{equation}
since $\mathrm{KL}(q || \pi_i) = 0$. In practice we estimate $Q_{\a_i}$ from off-policy data (we refer to Section \ref{sec_policy_eval} for details about the policy evaluation step). This greatly increases the data efficiency of our algorithm.
Given $Q_{\a_i}$ we improve the lower bound $\mathcal{J}$ w.r.t. $q$ by first expanding $Q_{\a_i}(s,a)$ via the regularized Bellman operator $T^{\pi, q} = \bE_{q(a | s)} \Big[ r(s, a) - \alpha \textrm{KL}(q \| \pi_i ) + \gamma \bE_{p(s' | s, a)}[V_{\a_i}(s')]]$,
and optimize the ``one-step'' KL regularised objective

\begin{equation}
\begin{aligned}
 \max_q ~\mathcal{\bar{J}}_s(q, \theta_i) &= \max_q T^{\pi, q} Q_{\a_i}(s,a) \\ &= \max_q \bE_{\mu(s)} \Big[ \bE_{q(\cdot|s)}[Q_{\a_i}(s,a)]  - \alpha \textrm{KL}(q \| \pi_i ) \Big],

\end{aligned}
\label{eq:objective_decomposed}
\end{equation}
since $V_{\a_i}(s) = \bE_{q(a | s)} [Q_{\a_i}(s, a)]$ and thus $Q_{\a_i}(s, a) = r(s, a) + \gamma V_{\a_i}(s)$.

Maximizing Equation~\eqref{eq:objective_decomposed}, thus obtaining $q_i=\arg \max \bar{\mathcal{J}}(q,\theta_i)$, does not fully optimize $\mathcal{J}$ since we treat

$Q_{\theta_i}$
as constant with respect to $q$. An intuitive interpretation $q_i$ is that it chooses the soft-optimal action for one step and then resorts to executing policy $\pi$. In the language of the EM algorithm this optimization implements a partial E-step. In practice we also choose $\mu_q$ to be the stationary distribution as given through samples from the replay buffer.

\subsubsection*{Constrained E-step}

The reward and the KL terms are on an arbitray relative scale. This can make it difficult to choose $\alpha$. We therefore replace the soft KL regularization with a hard constraint with parameter $\epsilon$, i.e,
\begin{equation}
  \begin{aligned}
  & \max_q \bE_{\mu(s)} \Big[ \bE_{q(a|s)} \Big[ Q_{\theta_i}(s,a) \Big] \Big] \\
  & s.t. \bE_{\mu(s)} \Big[ \textrm{KL}(q(a|s) , \pi(a|s,\a_i) ) \Big] < \epsilon.
  \end{aligned}
  \label{eq:e_step_hard}
\end{equation}

If we choose to explicitly parameterize $q(a | s)$ -- option 1 below --
the resulting optimisation is similar to that performed by the recent TRPO algorithm for continuous control \citep{schulman15}; only in an off-policy setting. Analogously, the unconstrained objective \eqref{eq:objective_decomposed} is similar to the objective used by PPO \citep{schulman2017ppo}. We note, however, that the KL is reversed when compared to the KL used by TRPO and PPO.

To implement (\ref{eq:e_step_hard}) we need to choose a form for the variational policy $q(a|s)$. Two options arise:
\begin{enumerate}
    \item We can use a parametric variational distribution $q(a | s, \a^q)$, with parameters $\a^q$, and optimise Equation \eqref{eq:e_step_hard} via the likelihood ratio or action-value gradients. This leads to an algorithm similar to TRPO/PPO and an explicit M-step becomes unnecessary (see.~Alg.~\ref{alg:MPONON}).

    \item We can choose a non-parametric representation of $q(a | s)$ given by sample based distribution over actions for a state $s$. To achieve generalization in state space we then fit a parametric policy in the M-step. This is possible since in our framework the optimisation of Equation \eqref{eq:e_step_hard} is only the first step of an EM procedure and we thus do not have to commit to a parametric distribution that generalises across the state space at this point.
\end{enumerate}

Fitting a parametric policy in the M-step is a supervised learning problem, allowing us to employ various regularization techniques at that point. It also makes it easier to enforce the hard KL constraint.

\subsubsection*{Non parametric variational distribution}
In the non-parametric case
we can obtain the optimal sample based $q$ distribution over actions for each state -- the solution to Equation \eqref{eq:e_step_hard} -- in closed form (see the appendix for a full derivation), as,

\begin{equation}
q_i(a|s) \propto \pi(a|s,\a_i)\exp\Big( \frac{Q_{\theta_i}(s,a)}{\eta^{*}}\Big),
\end{equation}
where we can obtain $\eta^{*}$ by minimising the following convex dual function,
\begin{equation}
  g(\eta) = \eta \epsilon + \eta \int \mu(s) \log \int \pi(a|s, \a_i)\exp\Big( \frac{Q_{\theta_i}(s,a)}{\eta}\Big) da ds,
  \label{eq:dual}
\end{equation}
after the optimisation of which we can evaluate $q_i(a | s)$ on given samples.

This optimization problem is similar to the one solved by relative entropy policy search (REPS) \citep{Peters10} with the difference that we optimise only for the conditional variational distribution $q(a | s)$ instead of a joint distribution $q(a, s)$ -- effectively fixing $\mu_q(s)$ to the stationary distribution given by previously collected experience -- and we use the Q function of the old policy to evaluate the integral over $a$. While this might seem unimportant it \emph{is crucial} as it allows us to estimate the integral over actions with multiple samples without additional environment interaction. This greatly reduces the variance of the estimate and allows for fully off-policy learning at the cost of performing only a partial optimization of $\mathcal{J}$ as described above.

\subsection{M-step}

Given $q_i$ from the E-step we can optimize the lower bound $\mathcal{J}$ with respect to $\a$ to obtain an updated policy $\a_{i+1} = \arg \max_{\a} \mathcal{J}(q_i, \a)$. Dropping terms independent of $\a$ this entails solving for the solution of

\begin{equation}
  \max_\a \mathcal{J}(q_i, \theta) = \max_\a \bE_{\mu_q(s)} \Big[ \bE_{q(a|s)} \Big[ \log \pi(a|s,\a) \Big] \Big] + \log p(\a),
\end{equation}

which corresponds to a weighted maximum a-posteriroi estimation (MAP) problem where samples are weighted by the variational distribution from the E-step.

Since this is essentially a supervised learning step we can choose any policy representation in combination with any prior for regularisation.
In this paper we set $p(\a)$ to a Gaussian prior around the current policy, i.e, $p(\a) \approx \mathcal{N}\Big(\mu = \a_i , \Sigma =  \frac{F_{\a_i}}{\lambda}\Big),$
where $\a_i$ are the parameters of the current policy distribution, $F_{\a_i}$ is the empirical Fisher information matrix and $\lambda$ is a positive scalar.

As shown in the appendix this suggests the following generalized M-step:

\begin{equation}
\max_\pi \bE_{\mu_q(s)} \Big[ \bE_{q(a|s)} \Big[ \log \pi(a|s,\a) \Big]  - \lambda \textrm{KL}\Big(\pi(a|s,\a_i) , \pi(a|s,\a) \Big)  \Big]

\label{eq:m_step_soft}
\end{equation}

which can be re-written as the hard constrained version:

\begin{equation}
\begin{aligned}
\max_\pi \bE_{\mu_q(s)} \Big[ \bE_{q(a|s)} \Big[ \log \pi(a|s,\a) \Big] \Big] \\
s.t.\ \bE_{\mu_q(s)} \Big[ \textrm{KL}(\pi(a|s,\a_i) , \pi(a|s,\a) ) \Big] < \epsilon.
\end{aligned}
\label{eq:m_step_constraint}
\end{equation}

This additional constraint minimises the risk of overfitting the samples, i.e. it helps us to obtain a policy that generalises beyond the state-action samples used for the optimisation. In practice we have found the KL constraint in the M step to greatly increase stability of the algorithm.
We also note that in the E-step we are using the reverse, mode-seeking, KL while in the M-step we are using the forward, moment-matching, KL which reduces the tendency of the entropy of the parametric policy to collapse. This is in contrast to other RL algorithms that use M-projection without KL constraint to fit a parametric policy~\citep{Peters10,wirth2016model,chebotar2016path,montgomery2016guided}.  Using KL constraint in M-step has also been shown effective for stochastic search algorithms~\citep{abdolmaleki2017TRCMA}.

\section{Policy Evaluation}
\label{sec_policy_eval}
Our method is directly applicable in an off-policy setting. For this, we have to rely on a stable policy evaluation operator to obtain a parametric representation of the Q-function $Q_\theta(s,a)$. We make use of the policy evaluation operator from the Retrace algorithm \cite{munos2016safe}, which we found to yield stable policy evaluation in practice\footnote{We note that, despite this empirical finding, Retrace may not be guaranteed to be stable with function approximation \citep{Touati17}.}.
Concretely, we fit the Q-function $Q_{\theta_i}(s, a, \phi)$ as represented by a neural network, with parameters $\phi$, by minimising the squared loss:

\begin{equation}
\begin{aligned}
&\min_\phi L(\phi) = \min_\phi \bE_{\mu_b(s), b(a|s)} \Big[ \big( Q_{\theta_i}(s_t, a_t, \phi) - Q^{\text{ret}}_t \big)^2 \Big], \text{with } \\
  &Q^{\text{ret}}_t = Q_{\phi'}(s_t, a_t)+ \sum_{j=t}^\infty \gamma^{j-t} \Big( \prod_{k=t+1}^j c_k \Big) \Big[ r(s_j, a_j) + \bE_{\pi(a | s_{j+1})} [ Q_{\phi'}(s_{j+1}, a) ] - Q_{\phi'}(s_j, a_j) \Big], \\
  &c_k = \min\Big(1, \frac{\pi(a_k | s_k)}{b(a_k | s_k)}\Big),
\end{aligned}
\end{equation}
where $Q_{\phi'}(s, a)$ denotes the output of a target Q-network, with parameters $\phi'$, that we copy from the current parameters $\phi$ after each M-step. We truncate the infinite sum after $N$ steps by bootstrapping with $Q_{\phi'}$ (rather than considering a $\lambda$ return). Additionally, $b(a|s)$ denotes the probabilities of an arbitrary behaviour policy. In our case we use an experience replay buffer and hence $b$ is given by the action probabilities stored in the buffer; which correspond to the action probabilities at the time of action selection.

\section{Experiments}
For our experiments we evaluate our MPO algorithm across a wide range of tasks. Specifically, we start by looking at the continuous control tasks of the DeepMind Control Suite (\cite{tassa2018suite}, see Figure \ref{fig:images}), and then consider the challenging parkour environments recently published in \cite{heess2017emergence}. In both cases we use a Gaussian distribution for the policy whose mean and covariance are parameterized by a neural network (see appendix for details). In addition, we present initial experiments for discrete control using ATARI environments using a categorical policy distribution (whose logits are again parameterized by a neural network) in the appendix.

\subsection{Evaluation on control suite}

\begin{figure*}[ht]
\centering
\begin{minipage}[c]{1\textwidth}
\def\mywidth{0.14}
\def\myhsep{-0.01}
\includegraphics[width=\mywidth\textwidth]{./figures/acrobot.png}
\hspace{\myhsep\textwidth}
\includegraphics[width=\mywidth\textwidth]{./figures/ball-in-cup.png}
\hspace{\myhsep\textwidth}
\includegraphics[width=\mywidth\textwidth]{./figures/cart-pole.png}
\hspace{\myhsep\textwidth}
\includegraphics[width=\mywidth\textwidth]{./figures/cheetah.png}
\hspace{\myhsep\textwidth}
\includegraphics[width=\mywidth\textwidth]{./figures/finger.png}
\hspace{\myhsep\textwidth}
\includegraphics[width=\mywidth\textwidth]{./figures/fish.png}
\hspace{\myhsep\textwidth}
\includegraphics[width=\mywidth\textwidth]{./figures/hopper.png}\\
\vspace{-0.027\textwidth}

\includegraphics[width=\mywidth\textwidth]{./figures/humanoid.png}
\hspace{\myhsep\textwidth}
\includegraphics[width=\mywidth\textwidth]{./figures/manipulator.png}
\hspace{\myhsep\textwidth}
\includegraphics[width=\mywidth\textwidth]{./figures/pendulum.png}
\hspace{\myhsep\textwidth}
\includegraphics[width=\mywidth\textwidth]{./figures/point-mass.png}
\hspace{\myhsep\textwidth}
\includegraphics[width=\mywidth\textwidth]{./figures/reacher.png}
\hspace{\myhsep\textwidth}
\includegraphics[width=\mywidth\textwidth]{./figures/swimmers.png}
\hspace{\myhsep\textwidth}
\includegraphics[width=\mywidth\textwidth]{./figures/walker.png}
\caption{Control Suite domains used for benchmarking. \textit{Top}: Acrobot, Ball-in-cup, Cart-pole, Cheetah, Finger, Fish, Hopper.
\textit{Bottom}: Humanoid, Manipulator, Pendulum, Point-mass, Reacher, Swimmers (6 and 15 links), Walker.}
\label{fig:images}
\end{minipage}
\end{figure*}

The suite of continuous control tasks that we are evaluating against contains 18 tasks, comprising a wide range of domains including well known tasks from the literature. For example, the classical cart-pole and acrobot dynamical systems, 2D and Humanoid walking as well as simple low-dimensional planar reaching and manipulation tasks. This suite of tasks was built in python on top of mujoco and will also be open sourced to the public by the time of publication.

While we include plots depicting the performance of our algorithm on all tasks below; comparing it against the state-of-the-art algorithms in terms of data-efficiency. We want to start by directing the attention of the reader to a more detailed evaluation on three of the harder tasks from the suite.

\subsubsection{Detailed Analysis on Walker-2D, Acrobot, Hopper}
\label{sec_res_detailed}
We start by looking at the results for the classical Acrobot task (two degrees of freedom, one continuous action dimension) as well as the 2D walker (which has 12 degrees of freedom and thus a 12 dimensional action space and a 21 dimensional state space) and the hopper standing task. The reward in the Acrobot task is the distance of the robots end-effector to an upright position of the underactuated system. For the walker task it is given by the forward velocity, whereas in the hopper the requirement is to stand still.

Figure \ref{fig_detailed} shows the results for this task obtained by applying our algorithm MPO as well as several ablations -- in which different parts were removed from the MPO optimization -- and two baselines: our implementation of Proximal Policy Optimization (PPO)~\citep{schulman2017ppo} and DDPG. The hyperparameters for MPO were kept fixed for all experiments in the paper (see the appendix for hyperparameter settings).

As a first observation, we can see that MPO gives stable learning on all tasks and, thanks to its fully off-policy implementation, is significantly more sample efficient than the on-policy PPO baseline. Furthermore, we can observe that changing from the non-parametric variational distribution to a parametric distribution\footnote{We note that we use a value function baseline $\bE_\pi[Q(s,\cdot)]$ in this setup. See appendix for details.} (which, as described above, can be related to PPO) results in only a minor asymptotic performance loss but slowed down optimisation and thus hampered sample efficiency; which can be attributed to the fact that the parametric $q$ distribution required a stricter KL constraint. Removing the automatically tuned KL constraint and replacing it with a manually set entropy regulariser then yields an off-policy actor-critic method with Retrace. This policy gradient method still uses the idea of estimating the integral over actions -- and thus, for a gradient based optimiser, its likelihood ratio derivative -- via multiple action samples (as judged by a Q-Retrace critic). This idea has previously been coined as using the expected policy gradient (EPG) \citep{CiosekEPG} and we hence denote the corresponding algorithm with EPG + Retrace, which no-longer follows the intuitions of the MPO perspective. EPG + Retrace performed well when the correct entropy regularisation scale is used. This, however, required task specific tuning (c.f. Figure \ref{fig_suite} where this hyperparameter was set to the one that performed best in average across tasks).
Finally using only a single sample to estimate the integral (and hence the likelihood ratio gradient) results in an actor-critic variant with Retrace that is the least performant off-policy algorithm in our comparison.

\begin{figure}[ht]
\caption{Ablation study of the MPO algorithm and comparison to common baselines from the literature on three domains from the control suite. We plot the median performance over 10 experiments with different random seeds.}
\centering
\vspace{0.3cm}
\includegraphics[width=\textwidth]{figures/control_suite_detail_fix.pdf}
\label{fig_detailed}
\end{figure}

\subsubsection{Complete results on the control suite}
The results for MPO (non-parameteric) -- and a comparison to an implementation of state-of-the-art algorithms from the literature in our framework -- on all the environments from the control suite that we tested on are shown in Figure \ref{fig_suite}. All tasks have rewards that are scaled to be between 0 and 1000. We note that in order to ensure a fair comparison all algorithms ran with exactly the same network configuration, used a single learner (no distributed computation), used the same optimizer and were tuned w.r.t. their hyperparameters for best performance across all tasks. We refer to the appendix for a complete description of the hyperparameters. Our comparison is made in terms of data-efficiency.

From the plot a few trends are readily apparent: i) We can clearly observe the advantage in terms of data-efficiency that methods relying on a Q-critic obtain over the PPO baseline. This difference is so extreme that in several instances the PPO baseline converges an order of magnitude slower than the off-policy algorithms and we thus
indicate the asymptotic performance of each algorithm of PPO and DDPG (which also improved significantly later during training in some instances) with a colored star in the plot; ii) the difference between the MPO results and the (expected) policy gradient (EPG) with entropy regularisation confirm our suspicion from Section \ref{sec_res_detailed}: finding a good setting for the entropy regulariser that transfers across environments without additional constraints on the policy distribution is very difficult, leading to instabilities in the learning curves. In contrast to this the MPO results appear to be stable across all environments; iii) Finally, in terms of data-efficiency the methods utilising Retrace obtain a clear advantage over DDPG. The single learner vanilla DDPG implementation learns the lower dimensional environments quickly but suffers in terms of learning speed in environments with sparse rewards (finger, acrobot) and higher dimensional action spaces. Overall, MPO is able to solve all environments using surprisingly moderate amounts of data. On average less than 1000 trajectories (or $~ 10^6$ samples) are needed to reach the best performance.

\subsection{High-dimensional continuous control}
Next we turn to evaluating our algorithm on two higher-dimensional continuous control problems; humanoid and walker.
To make computation time bearable in these more complicated domains we utilize a parallel variant of our algorithm: in this implementation K learners are all independently collecting data from an instance of the environment. Updates are performed at the end of each collected trajectory using distributed synchronous gradient descent on a shared set of policy and Q-function parameters (we refer to the appendix for an algorithm description).
The results of this experiment are depicted in Figure \ref{fig_high_d}.

For the Humanoid running domain we can observe a similar trend to the experiments from the previous section: MPO quickly finds a stable running policy, outperforming all other algorithms in terms of sample efficiency also in this high-dimensional control problem.

The case for the Walker-2D parkour domain (where we compare against a PPO baseline) is even more striking: where standard PPO requires approximately \emph{1M trajectories} to find a good policy MPO finds a solution that is asymptotically no worse than the PPO solution in \textbf{in about 70k trajectories (or 60M samples)}, resulting in an order of magnitude improvement. In addition to the walker experiment we have also evaluated MPO on the Parkour domain using a humanoid body (with 22 degrees of freedom) which was learned successfully (not shown in the plot, please see the supplementary video).

\begin{figure}[ht]
\caption{MPO on high-dimensional control problems (Parkour Walker2D and Humanoid walking from control suite).}
\centering
\includegraphics[width=0.8\textwidth]{figures/humanoid_parkour_new.pdf}
\label{fig_high_d}
\end{figure}

\subsection{Discrete control}
As a proof of concept -- showcasing the robustness of our algorithm and its hyperparameters -- we performed an experiment on a subset of the games contained contained in the "Arcade Learning Environment" (ALE) where we used \emph{the same hyperparameter} settings for the KL constraints as for the continuous control experiments. The results of this experiment can be found in the Appendix.

\section{Conclusion}
We have presented a new off-policy reinforcement learning algorithm called Maximum a-posteriori Policy Optimisation (MPO). The algorithm is motivated by the connection between RL and inference and it consists of an alternating optimisation scheme that has a direct relation to several existing algorithms from the literature. Overall, we arrive at a novel, off-policy algorithm that is highly data efficient, robust to hyperparameter choices and applicable to complex control problems. We demonstrated the effectiveness of MPO on a large set of continuous control problems.

\begin{figure}[ht!]
\caption{Complete comparison of results for the control suite. We plot the median performance over 10 random seeds together with 5 and 95 \% quantiles (shaded area). Note that for DDPG we only plot the  median to avoid clutter in the plots. For DDPG and PPO final performance is marked by a star).}
\centering
\includegraphics[width=13cm]{figures/final_figure_suite.pdf}
\label{fig_suite}
\end{figure}

\subsubsection*{Acknowledgements}
The authors would like to thank David Budden, Jonas Buchli, Roland Hafner, Tom Erez, Jonas Degrave, Guillaume Desjardins, Brendan O'Donoghue and many others of the DeepMind team for their support and feedback during the preparation of this manuscript.

\bibliography{iclr2018_conference}
\bibliographystyle{iclr2018_conference}

\newpage

\appendix

\section{Proof of monotonic improvement for the KL-regularized policy optimization procedure}
\label{sect:proof}
In this section we prove a monotonic improvement guarantee for KL-regularized policy optimization via alternating updates on $\pi$ and $q$ under the assumption that the prior on $\theta$ is uninformative.

\subsection{Regularized Reinforcement Learning}
Let $\pi$ be an arbitrary policy. For any other policy $q$ such that, for all $x,a$, $\{\pi(a|x)>0\} \implies \{ q(a|x)>0\}$, define the $\pi$-regularized reward for policy $q$:
$$r^{\pi, q}_\alpha(x,a) = r(x,a) - \alpha \log\frac{q(a|x)}{\pi(a|x)},$$
where $\alpha > 0$.

\paragraph{Bellman operators:}
Define the $\pi$-regularized Bellman operator for policy $q$
$$T^{\pi, q}_\alpha V(x) = \bE_{a\sim q(\cdot|x)}\Big[ r^{\pi,q}_\alpha(x,a) + \gamma \bE_{y \sim p(\cdot|x,a)} V(y)\Big],$$
and the non-regularized Bellman operator for policy $q$
$$T^{q} V(x) = \bE_{a \sim q(\cdot|x)}\Big[ r(x,a) + \gamma \bE_{y \sim p(\cdot|x,a)} V(y)\Big].$$

\paragraph{Value function:} Define the $\pi$-regularized value function for policy $q$ as
$$V^{\pi, q}_\alpha(x) = \bE_{q}\Big[\sum_{t \geq 0 }\gamma^t r^{\pi, q}_\alpha(x_t,a_t) | x_0=x, q \Big].$$
and the non-regularized value function
$$V^{q}(x) = \bE_{q}\Big[\sum_{t \geq 0 }\gamma^t r(x_t,a_t) | x_0=x, q \Big].$$

\begin{proposition}{}\label{prop:inequality}
For any $q,\pi,V$, we have $V^{\pi, q}_\alpha \leq V^{q}$ and $T^{\pi, q}_\alpha V \leq T^{q} V$. Indeed
$$
\bE_{q}\Big[ \log\frac{q(a_t|x_t)}{\pi(a_t|x_t)} \Big]
= KL\big( q(\cdot|x_t) \| \pi(\cdot|x_t)\big) \geq 0.
$$
\end{proposition}

\paragraph{Optimal value function and policy}
Define the optimal regularized value function:
$V^{\pi,*}_\alpha(x) = \max_{q} V^{\pi,q}_\alpha(x)$, and  the optimal (non-regularized) value function: $V^{*}(x) = \max_{q} V^{q}(x)$.

The optimal policy of the $\pi$-regularized problem $q^{\pi,*}_\alpha (\cdot|x) = \arg\max_{q}V^{\pi,q}_\alpha(x)$ and the optimal policy of the non-regularized problem $q^*(\cdot|x) = \arg\max_{q}V^{q}$.

\begin{proposition}{Bellman equations} We have that $V^{\pi,q}_\alpha$ is the unique fixed point of $T^{\pi,q}_\alpha$, and $V^{q}$ is the unique fixed point of $T^{q}$. Thus we have the following Bellman equations:
 For all $x\in X$,
 \beqa
 V^{\pi,q}_\alpha(x) &=& \sum_a q(a|x) \Big[ r^{\pi,q}_\alpha(x, a) + \gamma \bE_{y\sim p(\cdot|x,a)} \big[ V^{\pi,q}_\alpha(y)\big] \Big] \label{eq:bellman.reg}\\
 V^{q}(x) &=& \sum_a q(a|x) \Big[ r(x, a) + \gamma \bE_{y\sim p(\cdot|x,a)} \big[ V^{q}(y)\big] \Big] \label{eq:bellman.non-reg}\\
 V^{\pi,*}_\alpha(x) &=& r^{\pi,q^{\pi,*}_\alpha}_\alpha(x, a) + \gamma \bE_{y\sim p(\cdot|x,a)} \big[ V^{\pi,*}_\alpha(y)\big] \mbox{ for all } a\in A, \label{eq:bellman.reg.optimal}\\
 V^{*}(x) &=& \max_{a\in A} \Big[ r(x, a) + \gamma \bE_{y\sim p(\cdot|x,a)} \big[ V^{*}(y)\big] \Big]. \label{eq:bellman.non-reg.optimal}
\eeqa
\end{proposition}
Notice that (\ref{eq:bellman.reg.optimal}) holds for all actions $a\in A$, and not in expectation w.r.t.~$a\sim q(\cdot|x)$ only.

\subsection{Regularized joint policy gradient}
We now consider a parametrized policy $\pi_{\theta}$ and consider maximizing the regularized joint policy optimization problem for a given initial state $x_0$ (this could be a distribution over initial states). Thus we want to find a parameter $\theta$ that (locally) maximizes
$$\mathcal{J}(\theta, q) = V^{\pi_{\theta},q}(x_0) = \bE_{q}\Big[\sum_{t\geq 0 }\gamma^t \big( r(x_t,a_t) - \alpha \mbox{KL}(q(\cdot | x_t) \| \pi_{\theta}(\cdot | x_t)) \big) \big| x_0, q \Big].$$

We start with an initial parameter $\theta_0$ and define a sequence of  policies $\pi_i = \pi_{\theta_i}$ parametrized by $\theta_i$, in the following way:
\begin{itemize}
 \item Given $\theta_i$, define
 $$q_i = \arg\max_{q} T^{\pi_{\theta_i},q}_\alpha V^{\pi_{\theta_i}},$$
 \item Define $\theta_{i+1}$ as
 \beq\label{eq:theta.k+1}
 \theta_{i+1}=\theta_i - \beta  \nabla_{\theta} \bE_{\pi_i}\Big[\sum_{t\geq 0 }\gamma^t \mbox{KL}\big( q_k(\cdot | x_t)\|\pi_{\theta}(\cdot | x_t)\big)_{| \theta=\theta_i} \big| x_0, \pi_i \Big].
 \eeq
\end{itemize}

\begin{proposition}{} We have the following properties:
 \begin{itemize}
  \item The policy $q_i$ satisfies:
\beq\label{eq:soft.policy}
q_i(a|x) = \frac{\pi_i(a|x) e^{\frac{1}{\alpha} Q^{\pi_i}(x,a)}}{\bE_{b\sim \pi_i(\cdot|x)}\big[ e^{\frac{1}{\alpha} Q^{\pi_i}(x,b)}\big] },\eeq
where $Q^{\pi}(x,a)=r(x,a) + \gamma \bE_{y\sim p(\cdot|x,a)} V^{\pi}(y)$.
\item We have
\beq\label{eq:E.improvement}
V^{\pi_i,q_i}_\alpha\geq V^{\pi_i}.
\eeq
 \item For $\eta$ sufficiently small, we have
 \beq \label{eq:improved.policy}
 \mathcal{J}(\theta_{i+1},q_{i+1}) \geq \mathcal{J}(\theta_{i},q_{i}) + c g_i,
 \eeq
where $c$ is a numerical constant, and $g_i$ is the norm of the gradient (minimized by the algorithm):
$$g_i = \Big\| \nabla_{\theta} \bE_{\pi_i}\Big[\sum_{t\geq 0 }\gamma^t \mbox{KL}\big( q_i(\cdot | x_t)\|\pi_{\theta}(\cdot | x_t)\big)_{| \theta=\theta_i} \big| x_0, \pi_i \Big] \Big\|.$$

Thus we build a sequence of policies $(\pi_{\theta_i},q_i)$ whose values $\mathcal{J}(\theta_{i},q_i)$ are non-decreasing thus converge to a local maximum. In addition, the improvement is lower-bounded by a constant times the norm of the gradient, thus the algorithm keeps improving the performance until the gradient vanishes (when we reach the limit of the capacity of our representation).
\end{itemize}
\end{proposition}

\begin{proof}
We have
\beqan
q_i(\cdot|x) &=& \arg\max_q \bE_{a \sim q(\cdot|x)}\Big[ \underbrace{r(x,a) + \gamma \bE_{y\sim p(\cdot|x,a)} V^{\pi_i}(y)}_{Q^{\pi_i}(x,a)} - \alpha\log\frac{q(a|x)}{\pi_i(a|x)}\Big],
\eeqan
from which we deduce \eqref{eq:soft.policy}.
Now, from the definition of $q_i$, we have
$$T^{\pi_i,q_i}_\alpha V^{\pi_i} \geq T^{\pi_i,\pi_i}_\alpha V^{\pi_i}= T^{\pi_i} V^{\pi_i}=V^{\pi_i}.$$
Now, since $T^{\pi_i,q_i}_\alpha$ is a monotone operator (i.e.~if $V_1\geq V_2$ elementwise, then $T^{\pi_i,q_i}_\alpha V_1 \geq T^{\pi_i,q_i}_\alpha V_2$) and its fixed point is $V^{\pi_i,q_i}_\alpha$, we have
$$V^{\pi_i,q_i}_\alpha=\lim_{t\rightarrow\infty} (T^{\pi_i,q_i}_\alpha)^t V^{\pi_i} \geq V^{\pi_i},$$
which proves \eqref{eq:E.improvement}.

Now, in order to prove \eqref{eq:improved.policy} we derive the following steps.

\paragraph{Step 1:}  From the definition of $q_{i+1}$ we have, for any $x$,
\beq\label{eq:prop.mu_k+1}
\bE_{a\sim q_{i+1}} \big[ Q^{\pi_{i+1}}(x,a)\big] - \alpha \mbox{KL}\big( q_{i+1}(\cdot | x) \| \pi_{i+1}(\cdot | x) \big)
\geq \bE_{a\sim q_{i}} \big[ Q^{\pi_{i+1}}(x,a)\big] - \alpha \mbox{KL}\big( q_{i}(\cdot | x) \| \pi_{i+1}(\cdot | x) \big).
\eeq

Writing the functional that we minimize
\beqan
f(\pi, q, \theta) = \bE_{\pi}\Big[\sum_{t\geq 0 }\gamma^t \mbox{KL}\big( q(\cdot | x_t) \| \pi_{\theta}(\cdot | x_t)\big) \big| x_0, \pi \Big],
\eeqan
the update rule is $\theta_{i+1}=\theta_i - \beta \nabla_{\theta} f(\pi_i, q_i, \theta_i)$. Thus we have that for sufficiently small $\beta$,
\beq\label{eq:gradient.step}
f(\pi_i,q_i, \theta_{i+1}) \leq f(\pi_i,q_i, \theta_i) -\beta  g_i,
\eeq
where $g_i = \frac 12 \big\| \nabla_{\theta} f(\pi_i,q_i, \theta_i)\big\|$.

\paragraph{Step 2:} Now define $\mathcal{F}$:
\beqan
\mathcal{F}(\pi, q, \theta, \pi') &=& \bE_{\pi}\Big[\sum_{t\geq 0 }\gamma^t \big( \bE_{a\sim q} \big[ Q^{\pi'}(x_t,a)\big] - \alpha \mbox{KL}\big( q(\cdot | x_t) \| \pi_{\theta}(\cdot | x_t) \big) \big) \big| x_0, \pi \Big] \\
&=& \delta_{x_0} (I-\gamma P^{\pi})^{-1} T^{\pi_{\theta},q}_\alpha V^{\pi'}\\
&=& \delta_{x_0} (I-\gamma P^{\pi})^{-1} T^{q} V^{\pi'} - f(\pi, q, \theta),
\eeqan
where $\delta_{x_0}$ is a Dirac (in the row vector $x_0$), and $P^{\pi}$ is the transition matrix for policy $\pi$.

From \eqref{eq:prop.mu_k+1} and \eqref{eq:gradient.step} we deduce that
\beqan
\mathcal{F}(\pi_{i}, q_{i+1}, \theta_{i+1},\pi_{i+1}) &\geq & \mathcal{F}(\pi_{i}, q_{i}, \theta_{i+1},\pi_{i+1}) \\
&\geq & \mathcal{F}(\pi_{i}, q_{i}, \theta_{i}, \pi_{i+1}) + \beta g_i.
\eeqan

We deduce
\beqan
&&\mathcal{F}(\pi_i, q_{i+1}, \theta_{i+1},\pi_{i}) \\ &\geq&
\mathcal{F}(\pi_{i}, q_{i}, \theta_{i}, \pi_{i}) + \beta g_i \\
&&+ \mathcal{F}(\pi_i, q_{i+1}, \theta_{i+1},\pi_{i})  - \mathcal{F}(\pi_i, q_{i+1}, \theta_{i+1},\pi_{i+1})  + \mathcal{F}(\pi_i, q_{i}, \theta_{i},\pi_{i+1})  - \mathcal{F}(\pi_i, q_{i}, \theta_{i},\pi_{i})  \\
&=& \mathcal{F}(\pi_{i}, q_{i}, \theta_{i}, \pi_{i}) + \beta g_i +\\
&&\underbrace{\bE_{\pi_i}\Big[\sum_{t\geq 0 }\gamma^t \big( \bE_{a\sim q_{i+1}} \big[ Q^{\pi_i}(x_t,a)- Q^{\pi_{i+1}}(x_t,a) \big] - \bE_{a\sim q_{i}} \big[ Q^{\pi_i}(x_t,a)- Q^{\pi_{i+1}}(x_t,a) \big] \big)\Big] }_{=O(\beta^2)\mbox{ since }\pi_i=\pi_{i+1}+O(\beta) \mbox{ and } q_i=q_{i+1}+O(\beta) }
\eeqan

This rewrites:
\beq\label{eq:almost.there}
\delta_{x_0} (I-\gamma^{\pi_i})^{-1}\big( T^{q_{i+1},\pi_{i+1}}_\alpha V^{\pi_i} - T^{q_{i},\pi_i}_\alpha V^{\pi_i} \big) \geq \eta g_i + O(\beta^2).
\eeq

\paragraph{Step 3:}
Now a bit of algebra. For two stochastic matrices $P$ and $P'$, we have
\beqan
&& (I-\gamma P)^{-1} \\ &=& (I-\gamma P')^{-1} + \gamma (I-\gamma P)^{-1}(P-P')(I-\gamma P')^{-1} \\
&=& (I-\gamma P')^{-1} + \gamma \big[ (I-\gamma P')^{-1} + \gamma (I-\gamma P)^{-1}(P-P')(I-\gamma P')^{-1}\big] (P-P')(I-\gamma P')^{-1}\\
&=& (I-\gamma P')^{-1} + \gamma (I-\gamma P')^{-1}(P-P')(I-\gamma P')^{-1} \\
& & + \gamma^2 (I-\gamma P)^{-1}(P-P')(I-\gamma P')^{-1} (P-P')(I-\gamma P')^{-1}.\\
\eeqan

Applying this equality to the transition matrices $P^{\pi_k}$ and $P^{\pi_{k+1}}$ and since $\| P^{\pi_{k+1}}-P^{\pi_k} \| = O(\eta)$, we have:
\beqan
&& V^{q_{i+1},\pi_{i+1}}_\alpha \\ &=& (I-\gamma P^{\pi_{i}})^{-1} r^{q_{i+1},\pi_{i+1}}_\alpha  \\
&=& (I-\gamma P^{\pi_{i}})^{-1}r^{q_{i+1},\pi_{i+1}}_\alpha + \gamma (I-\gamma P^{\pi_{i}})^{-1}  (P^{\pi_{i+1}}-P^{\pi_{i}})(I-\gamma P^{\pi_{i}})^{-1} r^{q_{i+1},\pi_{i+1}}_\alpha +O(\beta^2) \\
&=& (I-\gamma P^{\pi_{i}})^{-1}r^{q_{i},\pi_{i}}_\alpha+ (I-\gamma P^{\pi_{i}})^{-1}  (r^{q_{i+1},\pi_{i+1}}_\alpha - r^{q_{i},\pi_{i}}_\alpha + \gamma P^{\pi_{i+1}}-\gamma P^{\pi_{i}})(I-\gamma P^{\pi_{i}})^{-1} r^{q_{i},\pi_{i}}_\alpha +O(\beta^2) \\
&=& V^{q_{i},\pi_{i}}_\alpha + (I-\gamma P^{\pi_{i}})^{-1}  (T^{q_{i+1},\pi_{i+1}}_\alpha V^{\pi_{i}} - T^{q_{i},\pi_{i}}_\alpha V^{\pi_{k}}) +O(\beta^2).
\eeqan

Finally, using \eqref{eq:almost.there}, we deduce that
\beqan
\mathcal{J}(\theta_{i+1},q_{i+1}) &=& V^{q_{i+1},\pi_{i+1}}_\alpha(x_0) \\
&=& V^{q_{i},\pi_{i}}_\alpha(x_0)  + \delta_{x_0} (I-\gamma P^{\pi_{i}})^{-1}  (T^{q_{i+1},\pi_{i+1}}_\alpha V^{\pi_{i}} - T^{q_{i},\pi_{i}}_\alpha V^{\pi_{i}}) +O(\beta^2) \\
&\geq & \mathcal{J}(\theta_i, q_i)  + \eta g_i +O(\beta^2) \\
&\geq & \mathcal{J}(\theta_i, q_i)  + \frac 12 \eta g_i,
\eeqan
for small enough $\eta$.
\end{proof}

\section{Additional Experiment: Discrete control}
As a proof of concept -- showcasing the robustness of our algorithm and its hyperparameters -- we performed an experiment on a subset of the games contained contained in the "Arcade Learning Environment" (ALE). For this experiment we used \emph{the same hyperparameter} settings for the KL constraints as for the continuous control experiments as well as the same learning rate and merely altered the network architecture to the standard network structure used by DQN \cite{mnih2015human} -- and created a seperate network with the same architecture, but predicting the parameters of the policy distribution.
A comparison between our algorithm and well established baselines from the literature, in terms of the mean performance, is listed in Table \ref{tab:ale}.
While we do not obtain state-of-the-art performance in this experiment, the fact that MPO is competitive, out-of-the-box in these domains suggests that combining the ideas presented in this paper with recent advances for RL with discrete actions \citep{Bellemare17} could be a fruitful avenue for future work.

\begin{table}[t]
\caption{Results on a subset of the ALE environments in comparison to baselines taken from \citep{Bellemare17}}
\label{sample-table}
\begin{center}
\begin{tabular}{lrrrrr}
\multicolumn{1}{c}{\bf Game/Agent}  &\multicolumn{1}{c}{\bf Human} &\multicolumn{1}{c}{\bf DQN} &\multicolumn{1}{c}{\bf Prior. Dueling} &\multicolumn{1}{c}{\bf C51} & \multicolumn{1}{c}{\bf MPO} \\ \hline \\
Pong & 14.6 & 19.5 & 20.9 & 20.9 & 20.9  \\
Breakout &  30.5 & 385.5 & 366.0 & \textbf{748} & 360.5 \\
Q*bert & 13,455.0 & 13,117.3 & 18,760.3 & \textbf{23,784} & 10,317.0 \\
Tennis & -8.3 & 12.2 & 0.0 & \textbf{23.1} & 22.2 \\
Boxing & 12.1 & 88.0 & 98.9 & \textbf{97.8} & 82.0 \\
\end{tabular}
\end{center}
\label{tab:ale}
\end{table}

\section{Experiment details}

In this section we give the details on the hyper-parameters used for each experiment. All the continuous control experiments use a feed-forward network except for Parkour-2d were we used the same network architecture as in \cite{heess2017emergence}. Other hyper parameters for MPO with non parametric variational distribution were set as follows,
\begin{table}[ht]
\begin{center}
 \begin{tabular}{c||c|c}
 Hyperparameter & control suite & humanoid \\
 \hline

 Policy net & 100-100 & 200-200\\
 Q function net & 200-200 & 300-300\\
 $\epsilon$ & 0.1 & \textquotedbl\\
 $\epsilon_{\mu}$ & 0.1 & \textquotedbl\\
 $\epsilon_{\Sigma}$ & 0.0001 & \textquotedbl\\
 Discount factor ($\gamma$) & 0.99 & \textquotedbl\\
 Adam learning rate & 0.0005 & \textquotedbl\\
\end{tabular}
\end{center}
\caption{Parameters for non-parametric variational distribution}
\end{table}

Hyperparameters for MPO with parametric variational distribution were as follows,
\begin{table}[ht]
\begin{center}
 \begin{tabular}{c||c|c}
 Hyperparameter & control suite tasks & humanoid \\
 \hline
 Policy net & 100-100 & 200-200\\
 Q function net & 200-200 & 300-300\\
 $\epsilon_{\mu}$ & 0.1 & \textquotedbl\\
 $\epsilon_{\Sigma}$ & 0.0001 & \textquotedbl\\
 Discount factor ($\gamma$) & 0.99 & \textquotedbl\\
 Adam learning rate & 0.0005 & \textquotedbl\\
\end{tabular}
\end{center}
\caption{Parameters for parametric variational distribution}
\end{table}

\section{Derivation of update rules for a Gaussian Policy}

For continuous control we assume that the policy is given by a Gaussian distribution with a full covariance matrix, i.e,
$
  \pi(\vec a| \vec s,\a) = \mathcal{N}\left(\mu , \vec
  \Sigma \right)
$. Our neural network outputs the mean $\mu=\mu(s)$ and Cholesky factor $A=A(s)$, such that $\Sigma = AA^T$. The lower triagular factor $A$ has positive diagonal elements enforced by the softplus transform $A_{ii} \leftarrow \log(1 + \exp(A_{ii}))$.

\subsection{Non-parametric variational distribution }

In this section we provide the derivations and implementation details for the non-parametric variational distribution case for both E-step and M-step.

\subsection{E-Step}
The E-step with a non-parametric variational solves the following program, where we have replaced expectations with integrals to simplify the following derivations:

\begin{equation*}
  \begin{aligned}
  & \max_q \int \mu_q(s)\int q(a|s) Q_{\theta_i}(s,a) dads\\
  & s.t. \int \mu_q(s) \textrm{KL}(q(a|s) , \pi(a|s,\a_i) )da < \epsilon ,\\
  & \iint \mu_q(s) q(a|s) dads = 1.
  \end{aligned}
\end{equation*}

First we write the Lagrangian equation, i.e,

\begin{equation*}
  \begin{aligned}
L(q,\eta,\gamma) =& \int \mu_q(s)\int q(a|s) Q_{\a_i}(s,a) dads +\\
&\eta\left(\epsilon - \int \mu_q(s)\int q(a|s)\log \frac{q(a|s)}{\pi(a|s,\a_i)}\right) + \gamma\left(1 - \iint \mu_q(s) q(a|s)dads\right).
  \end{aligned}
\end{equation*}
Next we maximise the Lagrangian $L$ w.r.t the primal variable $q$. The derivative w.r.t $q$ reads,

$${\partial q}L(q,\eta,\gamma) = Q_{\a_i}(a,s) - \eta\log q(a|s) + \eta\log \pi(a|s,\a_i) - (\eta-\gamma).$$

Setting it to zero and rearranging terms we get

$$q(a|s) = \pi(a|s,\a_i)\exp\left(\frac{Q_{\a_i}(a,s)}{\eta}\right)\exp\left(-\frac{\eta-\gamma}{\eta}\right).$$
However the last exponential term is a normalisation constant for $q$. Therefore we can write,

$$\exp(-\frac{\eta-\gamma}{\eta}) = \int \pi(a|s, \a_i)\exp(\frac{Q_{\a_i}(a,s)}{\eta})da,$$
$$\gamma = \eta - \eta\log\left(\int \pi(a|s,\a_i)\exp(\frac{Q_{\a_i}(a,s)}{\eta})da\right).$$

Note that we could write $\gamma$ based on $\pi$ and $\eta$.
At this point we can derive the dual function,
$$g(\eta) = \eta\epsilon+\eta\int\mu_q(s)\log\left(\int \pi(a|s, \a_i)\exp(\frac{Q(a,s)}{\eta})da\right).$$

\subsection{M-step}

To obtain the KL constraint in the M step we set $p(\theta)$ to a Gaussian prior around the current policy, i.e,
$$p(\a) \approx \mathcal{N}\Big(\mu = \a_i , \Sigma =  \frac{F_{\a_i}}{\lambda}\Big),$$
where $\a_i$ are the parameters of the current policy distribution, $F_{\a_i}$ is the empirical Fisher information matrix and $\lambda$.

With this, and dropping constant terms our optimization program becomes
\begin{equation}
  \max_\pi \int \mu_q(s) \int q(a|s)\log \pi(a|s,\a)dads - \lambda (\a - \a_i)^T F^{-1}_{\a_i}(\a - \a_i).
\end{equation}

We can observe that $(\a - \a_i)^T F^{-1}_{\a_i}(\a - \a_i)$ is the second order Taylor approximation of $\int \mu_q(s) \textrm{KL}(\pi(a|s,\a_i) , \pi(a|s,\a) )ds$ which leads us to the generalized M-step objective:
\begin{equation}
\max_\pi \int \mu_q(s) \int q(a|s)\log \pi(a|s,\a)dads - \lambda \int \mu_q(s) \textrm{KL}(\pi(a|s,\a_i) , \pi(a|s,\a) ) ds
\end{equation}
which corresponds to Equation \eqref{eq:m_step_soft} from the main text, where expectations are replaced by integrals.

After obtaining the non parametric variational distribution in the M step with a Gaussian policy we empirically observed that better results could be achieved by decoupling the KL constraint into two terms such that we can constrain the contribution of the mean and covariance separately i.e.

\begin{align}
\int \mu_q(s) \textrm{KL}(\pi_i(a|s,\a) , \pi(a|s,\a)) = C_\mu + C_\Sigma,
\end{align}
where
$$C_{\mu} = \int \mu_q(s) \tfrac{1}{2}(\textrm{tr}(\Sigma^{-1}\Sigma_i) - n + \ln(\frac{\Sigma}{\Sigma_i})) ds, $$
$$C_{\Sigma} = \int \mu_q(s) \tfrac{1}{2}(\mu -\mu_i)^T\Sigma^{-1}(\mu -\mu_i) ds.$$

This decoupling allows us to set different $\epsilon$ values for each component, i.e., $\epsilon_\mu , \epsilon_\Sigma$
for the mean, the covariance matrix respectively.
Different $\epsilon$ lead to different learning rates. The effectivness of this decoupling has also been shown in \cite{abdolmaleki2017TRCMA}. We always set a much smaller epsilon for covariance than the mean. The intuition is that while we would like the distribution moves fast in the action space, we also want to keep the exploration to avoid premature convergence.

In order to solve the constrained optimisation in the M-step,
we first write the generalised Lagrangian equation, i.e,

$$L(\a,\eta_{\mu},\eta_{\Sigma}) = \int\mu_q(s)\int q(a|s) \log \pi(a|s,\a) dads + \eta_{\mu}(\epsilon_{\mu} - C_{\mu}) + \eta_{\Sigma}(\epsilon_{\Sigma} - C_{\Sigma})$$
Where $\eta_{\mu}$ and $\eta_{\Sigma}$ are Lagrangian multipliers.
Following prior work on constraint optimisation, we formulate the following primal problem,

$$\max_{\a}\min_{\eta_{\mu}>0,\eta_{\Sigma}>0} L(\a,\eta_{\mu},\eta_{\Sigma}).$$

In order to solve for $\a$ we iteratively solve the inner and outer optimisation programs independently: We fix the Lagrangian multipliers to their current value and optimise for $\a$ (outer maximisation) and then fix the parameters $\a$ to their current value and optimise for the Lagrangian multipliers (inner minimisation). We continue this procedure until policy parameters $\a$ and Lagrangian multipliers converge. Please note that the same approach can be employed to bound the KL explicitly instead of decoupling the contribution of mean and covariance matrix to the KL.

\subsection{Parametric variational distribution}

In this case we assume our variational distribution also uses a Gaussian distribution over the action space and use the same structure as our policy $\pi$.

Similar to the non-parametric case for a Gaussian distribution in the M-step we also use a decoupled KL but this time in the E-step for a Gaussian variational distribution. Using the same reasoning as in the previous section we can obtain the following generalized Lagrangian equation:

$$L(\a^q,\eta_{\mu},\eta_{\Sigma}) = \int\mu_q(s)\int q(a|s;\a^q) A_i(a,s) dads + \eta_{\mu}(\epsilon_{\mu} - C_{\mu}) + \eta_{\Sigma}(\epsilon_{\Sigma} - C_{\Sigma}).$$
Where $\eta_{\mu}$ and $\eta_{\Sigma}$ are Lagrangian multipliers. And where we use the advantage function $A(a,s)$ instead of the Q function $Q(a,s)$, as it empirically gave better performance.
Please note that the KL in the E-step is different than the one used in the M-step.
Following prior works on constraint optimisation, we can formulate the following primal problem,

$$\max_{\a^q}\min_{\eta_{\mu}>0,\eta_{\Sigma}>0} L(\a^q,\eta_{\mu},\eta_{\Sigma})$$

In order to solve for $\a^q$ we iteratively solve the inner and outer optimisation programs independently. In order to that we fix the Lagrangian multipliers to their current value and optimise for $\a^q$ (outer maximisation), in this case we use the likelihood ratio gradient to compute the gradient w.r.t $\a^q$. Subsequently we fix the parameters $\a^q$ to their current value and optimise for Lagrangian multipliers (inner minimisation). We iteratively continue this procedure until the policy parameters $\a^q$ and the Lagrangian multipliers converges. Please note that the same approach can be used to bound the KL explicitly instead of decoupling the contribution of mean and covariance matrix to the KL. As our policy has the same structure as the parametric variational distribution, the M step in this case reduce to set the policy parameters $\a$ to the parameters $\a^q$ we obtained in E-step, i.e, $$\a_{i+1} = \a^q$$

\section{Implementation details}

While we ran most of our experiments using a single learner, we implemented a scalable variant of the presented method in which multiple workers collect data independently in an instance of the considered environment, compute gradients and send them to a chief (or parameter server) that performs parameter update by averaging gradients. That is we use distributed synchronous gradient descent. These procedures are described in Algorithms \ref{alg:chief} and \ref{alg:MPON} for the non-parametric case and \ref{alg:MPONON} for the parametric case.

\begin{algorithm}
\caption{MPO (chief)}\label{alg:chief}
\begin{algorithmic}[1]
\State Input $G$ number of gradients to average
\While{True}
\State initialize N = 0
\State initialize gradient store $s_\phi = \{ \}$, $s_\eta = \{ \}$, $s_{\eta_{\mu}} = \{ \}$, $s_{\eta_{\Sigma}} = \{ \}$ $s_\theta = \{ \}$
\While{$N < G$}
\State receive next gradient from worker $w$
\State $s_\phi = s_\phi + [\delta\phi^w]$
\State $s_\phi = s_\theta + [\delta\theta^w]$
\State $s_\eta = s_\eta + [\delta\eta^w]$
\State $s_{\eta_\mu} = s_{\eta_\mu} + [\delta\eta_\mu^w]$
\State$s_{\eta_\theta} = s_{\eta_\theta} + [\delta\eta_\theta^w]$
\EndWhile
\State update parameters with average gradient from
\State $s_\phi$, $s_\eta$, $s_{\eta_{\mu}}$, $s_{\eta_{\Sigma}}$ $s_\theta$
\State send new parameters to workers
\EndWhile
\end{algorithmic}
\end{algorithm}

\begin{algorithm}
\caption{MPO (worker) - Non parametric variational distribution}\label{alg:MPON}
\begin{algorithmic}[1]
\State Input $={\epsilon, \epsilon_{\Sigma} , \epsilon_{\mu}, L_{\text{max}}}$
\State $i = 0$, $L_{\text{curr}} = 0$
\State Initialise $Q_{\omega_i}(a,s)$, $\pi(a|s,\a_i)$,
$\eta,\eta_{\mu},\eta_{\Sigma}$

\For{each worker}
    \While{$L_{\text{curr}} > L_\text{max}$}
    \State update replay buffer $\mathcal{B}$ with L trajectories from the environment
    \State $k = 0$
    \State // Find better policy by gradient descent
    \While{$k<1000$}
      \State sample a mini-batch $\mathcal{B}$ of $N$ ($s$, $a$, $r$) pairs from replay
      \State sample $M$ additional actions for each state from $\mathcal{B}$,  $\pi(a|s,\a_i)$ for estimating integrals
      \State compute gradients, estimating integrals using samples
      \State // Q-function gradient:
      \State$\delta_\phi = {\partial}_{\phi} L_\phi'(\phi)$
      \State // E-Step gradient:
      \State  $\delta \eta = {\partial}_\eta g(\eta) $
      \State Let: $q(a|s) \propto \pi(a|s,\a_{i}) \exp(\frac{Q_{\theta_t}(a,s,\phi')}{\eta})$
      \State // M-Step gradient:
      \State $[{\delta_{\eta_{\mu}}},{\delta_{\eta_{\Sigma}}}] = \alpha{\partial}_{\eta_{\mu},\eta_{\Sigma}} L(\a_k,\eta_{\mu},\eta_{\Sigma}) $
      \State $\delta_{\theta} = {\partial}_{\a} L(\a,{\eta_{\mu}}_{k+1},{\eta_{\Sigma}}_{k+1}) $
      \State send gradients to chief worker
      \State wait for gradient update by chief
      \State fetch new parameters $\phi, \theta, \eta, \eta_\mu, \eta_\Sigma$
      \State $k = k+1$
    \EndWhile
    \State $i= i+1$, $L_{\text{curr}} = L_{\text{curr}} + L$
    \State $ \a_i=\a , \phi'=\phi$
    \EndWhile
\EndFor
\end{algorithmic}
\end{algorithm}

\begin{algorithm}
\caption{MPO (worker) - parametric variational distribution}\label{alg:MPONON}
\begin{algorithmic}[1]
\State Input $={\epsilon_{\Sigma} , \epsilon_{\mu}, L_{\text{max}}}$
\State $i = 0$, $L_{\text{curr}} = 0$
\State Initialise $Q_{\omega_i}(a,s)$, $\pi(a|s,\a_i)$,
$\eta,\eta_{\mu},\eta_{\Sigma}$

\For{each worker}
    \While{$L_{\text{curr}} < L_\text{max}$}
    \State update replay buffer $\mathcal{B}$ with L trajectories from the environment
    \State $k = 0$
    \State // Find better policy by gradient descent
    \While{$k<1000$}
      \State sample a mini-batch $\mathcal{B}$ of $N$ ($s$, $a$, $r$) pairs from replay
      \State sample $M$ additional actions for each state from $\mathcal{B}$,  $\pi(a|s,\a_k)$ for estimating integrals
      \State compute gradients, estimating integrals using samples
      \State // Q-function gradient:
      \State$\delta_\phi = {\partial}_{\phi} L_\phi'(\phi)$
      \State // E-Step gradient:
      \State $[{\delta_{\eta_{\mu}}},{\delta_{\eta_{\Sigma}}}] = \alpha{\partial}_{\eta_{\mu},\eta_{\Sigma}} L(\a_k,\eta_{\mu},\eta_{\Sigma}) $
      \State $\delta_{\theta} = {\partial}_{\a} L(\a,{\eta_{\mu}}_{k+1},{\eta_{\Sigma}}_{k+1}) $
      \State // M-Step gradient: In practice there is no M-step in this case as policy and variatinal distribution $q$ use a same structure.
      \State send gradients to chief worker
      \State wait for gradient update by chief
      \State fetch new parameters $\phi, \theta, \eta, \eta_\mu, \eta_\Sigma$
      \State $k = k+1$
    \EndWhile
    \State $i= i+1$, $L_{\text{curr}} = L_{\text{curr}} + L$
    \State $ \a_i=\a , \phi'=\phi$
    \EndWhile
\EndFor
\end{algorithmic}
\end{algorithm}

\end{document}

config: arxiv


TITLE: Scalarmultiplying to the right
QUESTION [0 upvotes]: Is it commonplace to define scalarmultiplication to the right of a matrix? For example, in my book Linear Algebra and Its applications, David C Lay, I haven't seen it been used once. If s is a scalar and M is a matrix, can't we just define Ms as sM  ?

REPLY [0 votes]: It's not often used, but you can define right scalar multiplication of a matrix $M=(m_{ij})_{i,j}$ with a scalar $\lambda$ as $M\cdot \lambda := (m_{ij}\lambda)_{i,j}$. This is equal to $\lambda\cdot M$ in any commutative ring, such as $\mathbb{R}$.


TITLE: Proving a set of circles to be belonging to a family of circles.
QUESTION [2 upvotes]: Question:

Given a $\triangle ABC$, a pair of congruent circles are drawn(one pair at a time, in the figure colored Red,Orange,Blue) by taking $B,C$ as centers. They cut sides $BC,AC$ at pair of points $($in fig. $(D,G);(E,H);(F,I)$$)$.
  Now taking those pair of points and $A$ as vertices of triangles, circumcircles are drawn(in the fig. green colored.) Prove that they all pass through a common point which is $(X$ in the figure$)$

Figure:

The question was long, I solved it till here(where I'm stuck.)
Thanks for sparing time to view my question and providing hints,solutions.

REPLY [0 votes]: Let $U,V$ be points on $BA,CA$ such that $BU=CV$. Let $M$ be the midpoint of $BC$ and let $X$ be the midpoint of the major $BC$-arc in the circumcircle of $ABC$.
My claim is that $A,U,V,X$ belong to the same circle, i.e. $\widehat{UXV}=\widehat{BAC}=\widehat{A}$.

It is simple to notice that $\widehat{UBX}=\widehat{VCX}$, hence $UBX=VCX$ by SAS.
Indeed $\widehat{XBC}=\widehat{XCB}=\frac{\pi-\widehat{A}}{2}$ and
$$ \widehat{UBX}=\widehat{B}-\frac{\pi-\widehat{A}}{2} = \frac{\pi-\widehat{A}}{2}-\widehat{C}=\widehat{VCX}.$$
This gives
$$ \widehat{UXV}=\widehat{BXC}=\widehat{A}$$
as wanted.


TITLE: Linear disjointness and algebraic extensions
QUESTION [2 upvotes]: This question may have risen already, but I didn't find a clear answer.
So I was learning about linear disjoint extensions. Let's set the stage:
I'm considering a base field $k$ and two extensions $L$ and $K$ embedded into a
big extension $\Omega$:
\begin{array}{ccccc}
 & \Omega & \\
/ & & \backslash & \\
L & & K\\
\backslash & & /\\
 & k & \\
\end{array}
Now I know that $L/k$ and $K/k$ are said to be linearly disjoint if
$$\begin{aligned}
T:\ L\otimes_k K & \longrightarrow LK\\
l\otimes k & \longmapsto lk\\
\end{aligned}$$
is injective. Now this map intrigues me, for two reasons.

I heard someone say once that $L/k$ and $K/k$ are linearly disjoint iff $L\otimes_k K$ is a field. The implication $\Longleftarrow$ is clearly obvious, but is the reciprocal true in general?
I already saw in some notes that $T$ is surjective. Now I tried to wrap my head around this, and sampled some cases. The most generalcase I could find is if one of the extensions $L/k,\ K/k$ were algebraic, but I couldn't figure out the general case.

Any help would be appreciated.

REPLY [1 votes]: The first question follows from the fact that $T$ is a ring homomorphism, and therefore its kernel is an ideal of the tensor product. Were it a field, then its only ideals were itself or 0, then since the map is surjective, its kernel cannot be everything, then it is 0 and again we have an isomorphism, implying the second direction of your if and only if statement.
The second question follows from the definition of the ring homomorphism $T$. $T$ takes the tensor product of $a$ and $b$ into $ab$, now, take any element of $KL$, it can be written as a some over elements of the form $k_il_i$ for $k_i\in K$ and $l_i\in L$ by definition. Then the tensor monomial $k_i\otimes l_i$ is mapped under $T$ to $k_il_i$ and by linearity, a preimage of the sum over the $k_il_i$ is constructed. Implying surjectivity.


TITLE: Proof of Number of: *permutations of ‘n’ things, taken ‘r’ at a time, when ‘m’ specified things always come together*
QUESTION [5 upvotes]: I read below at many sources

Number of permutations of ‘n’ things, taken ‘r’ at a time, when ‘m’ specified things always come together =$ m!  * (n-m+1) !$

However no one gave the proof.
I reached till this:

First we have choose r out of n: $^nC_r=\frac{n!}{(n-r)!r!}$
Then choose m out of r: $^rC_m=\frac{r!}{(r-m)!m!}$
Next arrange m elements : $m! (r-m+1)!$
Next I have to multiply all above and do cancelation. So I reached to: $\frac{n!(r-m+1)!}{(n-r)!(r-m)!}$

But I don't to get how to proceed to get the given $ m!  * (n-m+1) !$

REPLY [0 votes]: This is permutation question, so objects can come in different order.

Treat M objects as single entity/object. Remember, inside this entity, m objects can be
arranged in M! ways.
Now, total count of objects is (n-m+1).
Ex. if, n = 3 and m=2 then if we treat 2 objects as single entity/object we will have 2 (3-2+1=2) objects.
Since, it is permutation, (n-m+1) can be arranged in (n-m+1)! ways.
i.e. (n-m+1) P (n-m+1).
Now; from step 1 and step 3; M objects can be arranged in M! ways, AND (n-m+1)
objects can be arranged in (n-m+1) ways.
Hence, total number of ways of selection is- Step 1 * Step 3.
Which is , M!*(n-m+1)!

Thanks!!


TITLE: I need to get the Derivative of Expectation of Gaussian w.r.t. mean and covariance
QUESTION [0 upvotes]: Say, I have $n$-dimensional multivariate Gaussian, $G(x:\mu, \Sigma)$.
($\mu$ is $n$ dimension vector and $\Sigma$ is $n\times n$ matrix.)
Say there is a goal  $n$-dimensional vector $a$.
I need to bring and modify multivariate Gaussian close to vector $a$ as much as possible, by updating parameter $\mu$ and $\Sigma$ in $n$-dimensional space.
In other word, I need to minimize $Cost$ function defined as below.
$Cost=E_{x \sim G(x:\mu, \Sigma)}[abs(X-a)]$
Or maybe I should define $Cost$ as squared below.
$Cost=E_{x \sim G(x:\mu, \Sigma)}[(X-a)^2]$
Either way, I need to calculate the derivative of $Cost$ function, which is derivative of expectation w.r.t. $\mu$ and $\Sigma$ as below
$\frac{\partial Cost}{\partial \mu}=?$
$\frac{\partial Cost}{\partial \Sigma}=?$
How can we  calculate that?
Thank you.

REPLY [0 votes]: I'd go with the squared error as you can differentiate it. We can compute the Cost function by expanding out the expectations, i.e. $E[X^2] - 2aE[X]+a^2$. Then we know by properties of the Gaussian r.v. what these are in terms of $\mu, \sigma^2$. You can find the derivative of the cost function with respect to a vector, it is the matrix who's rows correspond to differentiating the $i^{th}$ component of the cost function with respect to each of the vectors components, i.e.
The matrix $(\frac{\partial Cost}{\partial \mu})_{ij} = \frac{\partial Cost_i}{\partial \mu_j}$.
You would then set this equal to zero along with the corresponding $\sigma^2$ derivative.


TITLE: Understand a step in the derivation of the Stirling's approximation
QUESTION [2 upvotes]: The Stirling's approximation of the factorial function is defined as:
$$n! \sim \sqrt{2 \pi n} \left(\frac{n}{e}\right)^n$$
This Wikipedia's derivation starts by using the logarithm of $n!$

$$\ln n! = \ln 1 + \ln 2 + ... + \ln n$$

And then it says

The right-hand side of this equation minus
$${\displaystyle {\tfrac {1}{2}}(\ln 1+\ln n)={\tfrac {1}{2}}\ln n} $$
is the approximation by the trapezoid rule of the integral
$${\displaystyle \ln n!-{\tfrac {1}{2}}\ln n\approx \int _{1}^{n}\ln x\,{\rm {d}}x=n\ln n-n+1}$$
...

Before proceeding I of course need to understand every step, but I'm not understanding the text that I marked in bold.
What I understand from that statement is that we substract an equation, i.e. ${\displaystyle {\tfrac {1}{2}}(\ln 1+\ln n)={\tfrac {1}{2}}\ln n} $, from the right hand side of the previous equation, i.e. $\ln n! = \ln 1 + \ln 2 + ... + \ln n$, which is $\ln 1 + \ln 2 + ... + \ln n$. This does not make sense at all to me.
Could someone explain me what it's meant by that statement?
I must be honest, a great percentage of the times I don't understand something similar to this is because of the way things are explained in English, not because of the formulas. (Please, mathematicians, learn to write well!)

REPLY [1 votes]: The trapezoid with base $[k,k+1]$ has area
$$\frac12\big(\ln k+\ln(k+1)\big)\;;$$
when you sum these over $k=1,\ldots,n-1$, you get
$$\frac12\ln 1+\ln 2+\ln 3+\ldots+\ln(n+1)+\frac12\ln n\;,$$
because every height except the first ($\ln 1$) and the last ($\ln n$) appears twice, once as the righthand height of a trapezoid and then again as the lefthand height of the next trapezoid. This is the same as
$$(\ln 1+\ln 2+\ldots+\ln n)-\left(\frac12\ln 1+\frac12\ln n\right)\;.$$
It doesn’t actually say that you’re subtracting an equation from an equation: it says that you’re subtracting the quantity $\frac12(\ln 1+\ln n)$ from the quantity $\ln 1+\ldots+\ln n$ (which happens to be $\ln n!$), and that this quantity that you’re subtracting can be simplified to $\frac12\ln n$ (since $\ln 1=0$).

REPLY [0 votes]: We start with the equality
$$\log(n!)=\log(1)+\log(2)+\cdots +\log(n)$$
Then, note that
$$\begin{align}
\log(n!)-\frac12 (\log(1)+\log(n))&=\frac12 \log(1)+\log(2)+\cdots +\log(n-1)+\frac12 \log(n)\\\\
&\approx \int_1^n \log(x)\,dx\\\\
&=n\log(n)-n+1
\end{align}$$
Since the logarithm is concave, the trapezoidal rule approximation provides a lower bound.  Therefore, we find from $(1)$ that
$$n!<e\sqrt{n}\left(\frac ne\right)^n $$


TITLE: How to prove that a language `L` is not a regular language?
QUESTION [1 upvotes]: Given the following question:

Prove that the following language is not a regular language:
A language L in alphabet $\Sigma = \{a, b\}$ where every word $w$ have more $a$ than $b$.

How would you prove that it's not a regular language?
I need help and any hint is welcome.
Thanks in advance.

REPLY [0 votes]: One way is to use the pumping lemma for regular languages; the linked article has an example of how to use it. If you try that approach with the word $w=b^pa^{p+1}$, where $p$ is the pumping length, you’ll get the desired contradiction very easily. I find this the easiest approach, but you can also use the Myhill-Nerode theorem. If you use it, you might ask yourself whether any of the strings $a^k$ for $k\in\Bbb N$ have distinguishing extensions.


TITLE: Each $c \in R^*$ divides each polynomial of $R[X]$
QUESTION [2 upvotes]: We consider that $R$ is a commutative ring with $1_R$.
Each $c \in R^*$(if we see it as a constant polynomial), divides each polynomial of $R[X]$.
($c \in R^*$ means that $c$ is invertible.)
I haven't undersotod it..Could you explain it to me?
Does it mean that if we have a polynomial $p(X) \in R$,then $\frac{p}{c} \in \mathbb{Z}$ ?
If yes, why is it like that??

REPLY [2 votes]: Hint $\ $ An invertible element remains invertible in every extension ring (having the same $\,\color{#c00}1)$. Therefore $\,c c' = \color{#c00}1\,$ for $\,c'\in R\,$ yields $\, f = \color{#C00}1\cdot f = (cc')f = c(c'f),\,$ so $\,c\mid f\,$ in $\,R[x].$


TITLE: Hilbertspace adjoint
QUESTION [1 upvotes]: Im doing the following excercise: Ok, so let $(e_n)$ be a orthonormal basis of $l^2$, and fix arbitrary complex numbers $(\lambda_n)$ and define $T:l^2\to l^2 $ as $$T(\sum x_ne_n)=\sum \lambda_nx_ne_n, $$
and let $$D(T) = \{\sum x_ne_n: \sum |\lambda_nx_n|^2 <\infty\}.$$
Clearly $T$ is densely defined since $e_n\in D(T)$ for all $n$. I want to determine the adjoint $T^*$.  I thought as follows:
We find out how $T^*$ acts on the basis-vectors $e_j$. Note that $$(T(e_j), e_j)  = \lambda_j.$$
Let $T^*e_j = z = \sum z_ne_n$, then using the orthonormality of the $e_n$ $$( e_j, T^*e_j) = \sum_n \overline{z_n}( e_j, e_n) = \overline{z_j}. $$
Also $(T(e_j),e_k) = 0$ if $k\neq j$ which is equivalent with $(e_j,T^*{e_k}) =0$ for $k\neq j$. It follows that for all $\sum x_ne_n \in D(T^*)$ that $$T^*(\sum x_ne_n) = \sum_n\overline{\lambda_n}x_ne_n.$$
Is this correct? Now here's my problem:
As hint they say: Finite dimensional subspaces can be helpful for a precise argumentation that the domain of $T^*$ is what you think it is. I don't understand this, because it seems (assuming my $T^*$ is correct) that $D(T^*) = D(T)$. What am i missing?

REPLY [1 votes]: You are taking the second step before the first when you write "We find out how $T^\ast$ acts on the basis-vectors $e_j$"; the first step would be to prove that $e_j \in D(T^\ast)$. That's easily remedied.
And then, you jump from the representation of $T^\ast$ on subspaces of the form $H_n = \operatorname{span} \{ e_j : 0 \leqslant j \leqslant n\}$ that you computed to the conclusion that $T^\ast$ is defined on the largest domain that $$T^\ast_0 = T^\ast\lvert_{\bigcup H_n}$$
can be (naturally) extended to. That needs a justification.
Remember the definition:
$$\begin{align}
D(T^\ast) &:= \left\lbrace y\in l^2 : x\mapsto (T x,y) \text{ is continuous in the norm topology}\right\rbrace\\
&= \left\lbrace y \in l^2 : \bigl(\exists z\in l^2\bigr)\bigl(\forall x \in D(T)\bigr) \bigl( (Tx, y) = (x,z)\bigr)\right\rbrace.
\end{align}$$
Now it is easy to see that $e_j \in D(T^\ast)$ for all $j$, since $x\mapsto (Tx,e_j) = x\mapsto \lambda_j\cdot x_j$ is continuous in the norm topology, and indeed $T^\ast(e_j) = \overline{\lambda_j}\cdot e_j$. And thus, since $D(T^\ast)$ is a linear subspace, we know that $H = \bigcup H_n$, the space of all finite linear combinations of the $e_j$ is contained in $D(T^\ast)$, and the restriction $T_0^\ast = T^\ast\lvert_H$ is given by
$$T_0^\ast\left(\sum_{k=0}^m y_{j_k}\cdot e_{j_k}\right) = \sum_{k=0}^m \overline{\lambda_{j_k}} y_{j_k}\cdot e_{j_k}.$$
$T_0^\ast$ has a natural extension to $D(T)$, and not beyond, but is it a priori unthinkable that $D(T^\ast)$ is a proper subspace of $D(T)$?
You need to show that indeed $D(T) \subset D(T^\ast)$, and $T^\ast$ is given by the obvious extension from $H$. And then, for completeness, you need to show that $T^\ast$ is not defined by an unobvious extension on a larger subspace. (Both points aren't hard to show, but need to be shown.)


text:
\subsection{DNNs}
\label{subsec:DNNs}

\begin{definition}[DNNs]
	\label{Def:ANN}
	We denote by $\ANNs$ the set given by
		\begin{equation}
	\begin{split}
	\ANNs
	&=
	\cup_{L \in \N}
	\cup_{ (l_0,l_1,\ldots, l_L) \in \N^{L+1} }
	\left(
	\times_{k = 1}^L (\R^{l_k \times l_{k-1}} \times \R^{l_k})
	\right)
	\end{split}
	\end{equation}
	and we denote by 	$
	\paramANN,

	\lengthANN, \inDimANN, \outDimANN \colon \ANNs \to \N
	$ and
	$\dims\colon\ANNs\to  \cup_{L=2}^\infty\, \N^{L}$
	the functions which satisfy
	for all $ L\in\N$, $l_0,l_1,\ldots, l_L \in \N$,
	$
	\Phi
	\in  \allowbreak
	( \times_{k = 1}^L\allowbreak(\R^{l_k \times l_{k-1}} \times \R^{l_k}))$
	that
	$\paramANN(\Phi)
	=
	\sum_{k = 1}^L l_k(l_{k-1} + 1)
	$, $\lengthANN(\Phi)=L$, $\inDimANN(\Phi)=l_0$,  $\outDimANN(\Phi)=l_L$, and $\dims(\Phi)= (l_0,l_1,\ldots, l_L)$.
\end{definition}

\subsection{Realizations of DNNs}

\begin{definition}[Multidimensional versions]
	\label{Def:multidim_version}
	Let $d \in \N$ and let $\psi \colon \R \to \R$ be a function.
	Then we denote by $\mathfrak{M}_{\psi, d} \colon \R^d \to \R^d$ the function which satisfies for all $ x = ( x_1, x_2, \dots, x_{d} ) \in \R^{d} $ that
	\begin{equation}\label{multidim_version:Equation}
	\mathfrak{M}_{\psi, d}( x )
	=
	\left(
	\psi(x_1)
	, \psi(x_2),
	\ldots
	,
	\psi(x_d)
	\right).
	\end{equation}
\end{definition}

\begin{definition}[Realizations associated to DNNs]
	\label{Definition:ANNrealization}
	Let $a\in C(\R,\R)$.
	Then we denote by
	$
	\functionANNgeneral \colon \ANNs \to (\cup_{k,l\in\N}\,C(\R^k,\R^l))
	$
	the function which satisfies
	for all  $ L\in\N$, $l_0,l_1,\ldots, l_L \in \N$,
	$
	\Phi
	=
	((W_1, B_1), (W_2, B_2), \allowbreak \ldots, (W_L,\allowbreak B_L))
	\in  \allowbreak
	( \times_{k = 1}^L\allowbreak(\R^{l_k \times l_{k-1}} \times \R^{l_k}))
	$,
	$x_0 \in \R^{l_0}, x_1 \in \R^{l_1}, \ldots, x_{L-1} \in \R^{l_{L-1}}$
	with $\forall \, k \in \N \cap (0,L) \colon x_k =\activationDim{l_k}(W_k x_{k-1} + B_k)$
	that
	\begin{equation}
	\label{setting_NN:ass2}
	\functionANNgeneral(\Phi) \in C(\R^{l_0},\R^{l_L})\qandq
	( \functionANNgeneral(\Phi) ) (x_0) = W_L x_{L-1} + B_L
	\end{equation}
	(cf.\ \Cref{Def:ANN,Def:multidim_version}).
\end{definition}

\begin{definition}[Rectifier function]
	\label{Definition:Relu1}
	We denote by $ \mathfrak{r} \colon \R \to \R $ the function which satisfies
	for all $ x \in \R $ that $	\mathfrak{r} (x) = \max\{ x, 0 \}.$
\end{definition}

\subsection{Compositions of DNNs}
\label{subsec:DNN:composition}

\begin{definition}[Standard compositions of DNNs]
	\label{Definition:ANNcomposition}
	We denote by $\compANN{(\cdot)}{(\cdot)}\colon\allowbreak \{(\Phi_1,\Phi_2)\allowbreak\in\ANNs\times \ANNs\colon \inDimANN(\Phi_1)=\outDimANN(\Phi_2)\}\allowbreak\to\ANNs$ the function which satisfies for all
	$ L,\mathfrak{L}\in\N$, $l_0,l_1,\ldots, l_L, \mathfrak{l}_0,\mathfrak{l}_1,\ldots, \mathfrak{l}_\mathfrak{L} \in \N$,
	$
	\Phi_1
	=
	((W_1, B_1), (W_2, B_2), \allowbreak \ldots, (W_L,\allowbreak B_L))
	\in  \allowbreak
	( \times_{k = 1}^L\allowbreak(\R^{l_k \times l_{k-1}} \times \R^{l_k}))
	$,
	$
	\Phi_2
	=
	((\mathcal{W}_1, \mathfrak{B}_1),\allowbreak, (\mathcal{W}_2, \mathfrak{B}_2),\allowbreak \ldots, (\mathcal{W}_\mathfrak{L},\allowbreak \mathfrak{B}_\mathfrak{L}))
	\in  \allowbreak
	( \times_{k = 1}^\mathfrak{L}\allowbreak(\R^{\mathfrak{l}_k \times \mathfrak{l}_{k-1}} \times \R^{\mathfrak{l}_k}))
	$
	with $l_0=\inDimANN(\Phi_1)=\outDimANN(\Phi_2)=\mathfrak{l}_{\mathfrak{L}}$
	that
	\begin{equation}\label{ANNoperations:Composition}
	\begin{split}
	&\compANN{\Phi_1}{\Phi_2}=\\&
	\begin{cases}
	\begin{array}{r}
	\big((\mathcal{W}_1, \mathfrak{B}_1),(\mathcal{W}_2, \mathfrak{B}_2),\ldots, (\mathcal{W}_{\mathfrak{L}-1},\allowbreak \mathfrak{B}_{\mathfrak{L}-1}),
	(W_1 \mathcal{W}_{\mathfrak{L}}, W_1 \mathfrak{B}_{\mathfrak{L}}+B_{1}),\\ (W_2, B_2), (W_3, B_3),\ldots,(W_{L},\allowbreak B_{L})\big)
	\end{array}
	&: L>1<\mathfrak{L} \\[3ex]
	\big( (W_1 \mathcal{W}_{1}, W_1 \mathfrak{B}_1+B_{1}), (W_2, B_2), (W_3, B_3),\ldots,(W_{L},\allowbreak B_{L}) \big)
	&: L>1=\mathfrak{L}\\[1ex]
	\big((\mathcal{W}_1, \mathfrak{B}_1),(\mathcal{W}_2, \mathfrak{B}_2),\allowbreak \ldots, (\mathcal{W}_{\mathfrak{L}-1},\allowbreak \mathfrak{B}_{\mathfrak{L}-1}),(W_1 \mathcal{W}_{\mathfrak{L}}, W_1 \mathfrak{B}_{\mathfrak{L}}+B_{1}) \big)
	&: L=1<\mathfrak{L}  \\[1ex]
	(W_1 \mathcal{W}_{1}, W_1 \mathfrak{B}_1+B_{1})
	&: L=1=\mathfrak{L}
	\end{cases}
	\end{split}
	\end{equation}
	(cf.\ Definition~\ref{Def:ANN}).
\end{definition}

\begin{lemma}\label{Lemma:CompositionAssociative}
	Let
	$\Phi_1,\Phi_2,\Phi_3\in\ANNs$
	satisfy that
	$\inDimANN(\Phi_1)=\outDimANN(\Phi_2)$ and
	$\inDimANN(\Phi_2)=\outDimANN(\Phi_3)$
	(cf.\ Definition~\ref{Def:ANN}).
	Then
	\begin{equation}
	\compANN{(\compANN{\Phi_1}{\Phi_2})}{\Phi_3}=\compANN{\Phi_1}{(\compANN{\Phi_2}{\Phi_3})}
	\end{equation}
	(cf.\  Definition~\ref{Definition:ANNcomposition}).
\end{lemma}

\begin{definition}[Compositions of DNNs involving artificial identities]
	\label{Definition:ANNconcatenation}
	Let $\Psi\in \ANNs$.
	Then
	we denote by
	\begin{equation}
	\concPsiANN{(\cdot)}{(\cdot)}\colon \{(\Phi_1,\Phi_2)\in\ANNs\times \ANNs\colon \inDimANN(\Phi_1)=\outDimANN(\Psi) \text{ and } \outDimANN(\Phi_2)=\inDimANN(\Psi)\}\allowbreak\to\ANNs
	\end{equation}
	the function which satisfies for all $\Phi_1,\Phi_2\in\ANNs$ with $\inDimANN(\Phi_1)=\outDimANN(\Psi)$ and $\outDimANN(\Phi_2)=\inDimANN(\Psi)$ that
	\begin{equation}
	\begin{split}
	\concPsiANN{\Phi_1}{\Phi_2}
	= \compANN{\Phi_1}
	{
		(\compANN
		{\Psi}
		{\Phi_2})}
	=\compANN{(\compANN{\Phi_1}{\Psi})}{\Phi_2}
	\end{split}
	\end{equation}
	(cf.\ \Cref{Def:ANN,Definition:ANNcomposition} and \Cref{Lemma:CompositionAssociative}).
\end{definition}