## General Framework
Really **similar to DAgger** (see [summary](https://www.shortscience.org/paper?bibtexKey=journals/corr/1011.0686&a=muntermulehitch)) but considers **cost-sensitive classification** ("some mistakes are worst than others": you should be more careful in imitating that particular action of the expert if failing in doing so incurs a large cost-to-go). By doing so they improve from DAgger's bound of $\epsilon_{class}uT$ where $u$ is the difference in cost-to-go (between the expert and one error followed by expert policy) to  $\epsilon_{class}T$ where $\epsilon_{class}$ is the error due to the lack of expressiveness of the policy class. In brief, by accounting for the effect of a mistake on the cost-to-go they remove the cost-to-go contribution to the bound (difference in the performance of the learned policy vs. expert policy) and thus have a tighter bound. In the paper they use the word "regret" for two distinct concepts which is confusing to me: one for the no-regret online learning meta-approach to IL (similar to DAgger) and another one because Aggrevate aims at minimizing the cost-to-go difference with the expert (cost-to-go difference: the sum of the cost I endured because I did not behave like the expert once = *regret*) compared to DAgger that aims at minimizing the error rate wrt. the expert.

Additionally, the paper extends the view of Imitation learning as an online learning procedure to Reinforcement Learning. 

## Assumptions
**Interactive**: you can re-query the expert and thus reach $\epsilon T$ bounds instead of $\epsilon T^2$ like with non-interactive methods (Behavioral Cloning) due to compounding error.
Additionally, one also needs a **reward/cost** that **cannot** be defined relative to the expert (no 0-1 loss wrt expert for ex.) since the cost-to-go is computed under the expert policy (would always yield 0 cost).

## Other methods
**SEARN**: does also reason about **cost-to-go but under the current policy** instead of the expert's (even if you can use the expert's in practice and thus becomes really similar to Aggrevate). SEARN uses **stochastic policies** and can be seen as an Aggrevate variant where stochastic mixing is used to solve the online learning problem instead of **Regularized-Follow-The-Leader (R-FTL)**. 

## Aggrevate - IL with cost-to-go
![](https://i.imgur.com/I1otJwV.png)

Pretty much like DAgger but one has to use a no-regret online learning algo to do **cost-sensitive** instead of regular classification. In the paper, they use the R-FTL algorithm and train the policy on all previous iterations. Indeed, using R-FTL with strongly convex loss (like the squared error) with stable batch leaner (like stochastic gradient descent) ensures the no-regret property.

In practice (to deal with infinite policy classes and knowing the cost of only a few actions per state) they reduce cost-sensitive classification to an **argmax regression problem** where they train a model to match the cost given state-action (and time if we want nonstationary policies) using the collected datapoints and the (strongly convex) squared error loss. Then, they argmin this model to know which action minimizes the cost-to-go (cost-sensitive classification). This is close to what we do for **Q-learning** (DQN or DDPG): fit a critic (Q-values) with the TD-error (instead of full rollouts cost-to-go of expert), argmax your critic to get your policy. Similarly to DQN, the way you explore the actions of which you compute the cost-to-go is important (in this paper they do uniform exploration).

**Limitations**

If the policy class is not expressive enough and cannot match the expert policy performance this algo may fail to learn a reasonable policy. Example: the task is to go for point A to point B, there exist a narrow shortcut and a safer but longer road. The expert can handle both roads so it prefers taking the shortcut. Even if the learned policy class can handle the safer road it will keep trying to use the narrow one and fail to reach the goal. This is because all the costs-to-go are computed under the expert's policy, thus ignoring the fact that they cannot be achieved by any policy of the learned policy class. 

## RL via No-Regrety Policy Iteration -- NRPI
![](https://i.imgur.com/X4ckv1u.png)

NRPI does not require an expert policy anymore but only a **state exploration distribution**. NRPI can also be preferred when no policy in the policy class can match the expert's since it allows for more exploration by considering the **cost-to-go of the current policy**. 

Here, the argmax regression equivalent problem is really similar to Q-learning (where we use sampled cost-to-go from rollouts instead of Bellman errors) but where **the cost-to-go** of the aggregate dataset corresponds to **outdated policies!** (in contrast, DQN's data is comprised of rewards instead of costs-to-go).
Yet, since R-FTL is a no-regret online learning method, the learned policy performs well under all the costs-to-go of previous iterations and the policies as well as the costs-to-go converge. 

The performance of NRPI is strongly limited to the quality of the exploration distribution. Yet if the exploration distribution is optimal, then NRPI is also optimal (the bound $T\epsilon_{regret} \rightarrow 0$ with enough online iterations). This may be a promising method for not interactive, state-only IL (if you have access to a reward).

## General limitations
Both methods are much less sample efficient than DAgger as they require costs-to-go: one full rollout for one data-point.

## Broad contribution 
Seeing iterative learning methods such as Q-learning in the light of online learning methods is insightful and yields better bounds and understanding of why some methods might work. It presents a good tool to analyze the dynamics that interleaves learning and execution (optimizing and collecting data) for the purpose of generalization. For example, the bound for NRPI can seem quite counter-intuitive to someone familiar with on-policy/off-policy distinction, indeed NRPI optimizes a policy wrt to **costs-to-go of other policies**, yet R-FTL tells us that it converges towards what we want. Additionally, it may give a practical advantage for stability as the policy is optimized with larger batches and thus as to be good across many states and many cost-to-go formulations.

This paper shows how a family of reinforcement learning algorithms known as value gradient methods can be generalised to learn stochastic policies and deal with stochastic environment models.

Value gradients are a type of policy gradient algorithm which represent a value function either by:
* A learned Q-function (a critic)
* Linking together a policy, an environment model and reward function to define a recursive function to simulate the trajectory and the total return from a given state.

By backpropagating though these functions, value gradient methods can calculate a policy gradient. This backpropagation sets them apart from other policy gradient methods (like REINFORCE for example) which are model-free and sample returns from the real environment.

Applying value gradients to stochastic problems requires differentiating the stochastic bellman equation:
\begin{equation} 
V ^t (s) = \int \left[ r^t + γ \int  V^{t+1} (s) p(s' | s, a) ds'  \right] p(a|s; θ) da
\end{equation}

To do that, the authors use a trick called re-parameterisation to express the stochastic bellman equation as a deterministic function which takes a noise variable as an input. To differentiate a re-parameterised function, one simply samples the noise variable then computes the derivative as if the function were deterministic. This can then be repeated $ M $ times and averaged to arrive at a Monte Carlo estimate for the derivative of the stochastic function.

The re-parameterised bellman equation is: 

$ V (s) = \mathbb{E}_{ \rho(\eta) } \left[ r(s, \pi(s, \eta; \theta)) + \gamma \mathbb{E}_{\rho(\xi) }  \left[ V' (f(s, \pi(s, \eta; \theta), \xi)) \right]  \right] $

It's derivative with respect to the current state and the policy parameters is:

$ V_s = \mathbb{E}_{\rho(\eta)} \[ r_\textbf{s} + r_\textbf{a} \pi_\textbf{s} + \gamma \mathbb{E}_{\rho(\xi)} V'_{s'} (\textbf{f}_\textbf{s} + \textbf{f}_\textbf{a} \pi_\textbf{s}) \] $

$ V_\theta = \mathbb{E}_{\rho(\eta)} \[ r_\textbf{a} \pi_\theta + \gamma \mathbb{E}_{\rho(\xi)} \[ V'_{\textbf{s'}} \textbf{f}_\textbf{a} \pi_\textbf{s} + V'_\theta\] \] $

Based on these relationships the authors define two algorithms; SVG(∞), SVG(1) 

* SVG(∞) takes the trajectory from an entire episode and starting at the terminal state accumulates a gradients $V_{\textbf{s}} $ and $ V_{\theta} $ using the expressions above to arrive at a policy gradient. SVG(∞) is on-policy and only works with finite-horizon environments

* SVG(1) trains a value function then uses its gradient as an estimate for $ V_{\textbf{s}} $ above. SVG(1) also uses importance weighting so as to be off-policy and can work with infinite-horizon environments.

Both algorithms use an environment model which is trained using an experience replay database. The paper also introduces SVG(0) which is a similar to SVG(1), but is model-free.

SVG was analysed using several MuJoCo environments and it was found that:
* SVG(∞) outperformed a BBPT planner on a control problem with a stochastic model, indicating that gradient evaluation using real trajectories is more effective than planning for stochastic environments
* SVG(1) is more robust to inaccurate environment models and value functions than SVG(∞)
* SVG(1) was able to solve several complex environments

Over the last decade and a half, a plethora of image segmentation algorithms have been proposed, which can be categorized into belonging to roughly four categories, represented by a combination of two labels: explicit or implicit boundary representation, and variational or combinatorial methods. While classic methods like Snakes [1] and Level-Sets [2] belong to explicit/variational and implicit/variational category, there have been another set of algorithms falling under the combinatorial domain, which are DP or path-based algorithms which are  explicit/combinatorial, and finally Graph-Cuts, which are implicit/combinatorial. The main difference between the categories is the space of solutions where search is performed. For variational methods,  the search space is $\mathcal{R}^\infty$,  while for combinatorial methods the search space is confined to $\mathcal{Z}^n$. An obvious advantage of combinatorial methods seem to better computational performance, but they also provide a globally optimal solution, which is global to the image. This makes the algorithm performance independent of numerical stability design decisions, and only dependent on the quality of global  descriptors. Hence the algorithms provide a highly generalized, globally optimal framework which can be applied to a variety of problems, including image segmentation. 

Graph-Cut methods are based upon the $s-t$ decomposition of a given image graph (where pixels are nodes and edges are formed between 8-connected neighbours).  An $s-t$ decomposition of a graph $\mathcal{G} = \{V,E\}$ is a subset of edges $C \subset E$ such that the graph gets completely  separated into individual  components $s$ and $t$. The divided nodes are assigned to two terminal nodes, representing foreground and background of the image.  The best-cut in an image graph is optimal if the cost of a cut (defined as  $|C| = \sum_{e\in C}w_e$) is minimal. This corresponds to segmenting an image with a desirable balance of boundary and regional properties. 

Graph-Cut exposes a general segmentation energy function (which constitutes the ``cost") as a combination of a regional term and boundary term, given as $E(A) = \lambda.R(A) + B(A)$.  Regional term can be used to model apriori distribution of the pixel classes (probability of the pixel belonging to background or foreground). The boundary term can be represented by any boundary feature like local intensity gradients, zero-crossing, gradient direction or geometric costs. Although the region and boundary terms force the algorithm to find a boundary which strikes a good balance between the two, sometimes the lack of information for either or both terms may lead to incorrect segmentation.  To offset these terms, hard constraints can be applied to the energy function. The constraints can be anything, for instance, a term that defines that pixels of particular intensities would belong to either foreground or background. The constraint can also be shape based, where shapes like circles or ellipses can be forced upon the final segmentation. 

The proposed algorithm was applied on a variety of 2D and 3D images. Note that graph-cut can  be generalized to N-D segmentation problems as well. A number of qualitative observations are reported. However there is a lack of quantitative foundation of the algorithm performance, compared to other  state-of-art algorithms not necessarily from the same category as graph-cut. 

This model called Med2Vec is inspired by Word2Vec. It is Word2Vec for time series patient visits with ICD codes. The model learns embeddings for medical codes as well as the demographics of patients.

https://i.imgur.com/Zjj6Xxz.png

The context is temporal. For each $x_t$ as input the model predicts $x_{t+1}$ and $x_{t-1}$ or more depending on the temporal window size. 

  * They suggest a new architecture for GANs.
  * Their architecture adds another Generator for a reverse branch (from images to noise vector `z`).
  * Their architecture takes some ideas from VAEs/variational neural nets.
  * Overall they can improve on the previous state of the art (DCGAN).

### How
  * Architecture
    * Usually, in GANs one feeds a noise vector `z` into a Generator (G), which then generates an image (`x`) from that noise.
    * They add a reverse branch (G2), in which another Generator takes a real image (`x`) and generates a noise vector `z` from that.
      * The noise vector can now be viewed as a latent space vector.
    * Instead of letting G2 generate *discrete* values for `z` (as it is usually done), they instead take the approach commonly used VAEs and use *continuous* variables instead.
      * That is, if `z` represents `N` latent variables, they let G2 generate `N` means and `N` variances of gaussian distributions, with each distribution representing one value of `z`.
      * So the model could e.g. represent something along the lines of "this face looks a lot like a female, but with very low probability could also be male".
  * Training
    * The Discriminator (D) is now trained on pairs of either `(real image, generated latent space vector)` or `(generated image, randomly sampled latent space vector)` and has to tell them apart from each other.
    * Both Generators are trained to maximally confuse D.
      * G1 (from `z` to `x`) confuses D maximally, if it generates new images that (a) look real and (b) fit well to the latent variables in `z` (e.g. if `z` says "image contains a cat", then the image should contain a cat).
      * G2 (from `x` to `z`) confuses D maximally, if it generates good latent variables `z` that fit to the image `x`.
    * Continuous variables
      * The variables in `z` follow gaussian distributions, which makes the training more complicated, as you can't trivially backpropagate through gaussians.
      * When training G1 (from `z` to `x`) the situation is easy: You draw a random `z`-vector following a gaussian distribution (`N(0, I)`). (This is basically the same as in "normal" GANs. They just often use uniform distributions instead.)
      * When training G2 (from `x` to `z`) the situation is a bit harder.
        * Here we need to use the reparameterization trick here.
        * That roughly means, that G2 predicts the means and variances of the gaussian variables in `z` and then we draw a sample of `z` according to exactly these means and variances.
        * That sample gives us discrete values for our backpropagation.
        * If we do that sampling often enough, we get a good approximation of the true gradient (of the continuous variables). (Monte Carlo approximation.)

* Results
  * Images generated based on Celeb-A dataset:
    * ![Celeb-A samples](https://raw.githubusercontent.com/aleju/papers/master/neural-nets/images/Adversarially_Learned_Inference__celeba-samples.png?raw=true "Celeb-A samples")
  * Left column per pair: Real image, right column per pair: reconstruction (`x -> z` via G2, then `z -> x` via G1)
    * ![Celeb-A reconstructions](https://raw.githubusercontent.com/aleju/papers/master/neural-nets/images/Adversarially_Learned_Inference__celeba-reconstructions.png?raw=true "Celeb-A reconstructions")
  * Reconstructions of SVHN, notice how the digits often stay the same, while the font changes:
    * ![SVHN reconstructions](https://raw.githubusercontent.com/aleju/papers/master/neural-nets/images/Adversarially_Learned_Inference__svhn-reconstructions.png?raw=true "SVHN reconstructions")
  * CIFAR-10 samples, still lots of errors, but some quite correct:
    * ![CIFAR10 samples](https://raw.githubusercontent.com/aleju/papers/master/neural-nets/images/Adversarially_Learned_Inference__cifar10-samples.png?raw=true "CIFAR10 samples")