"The objective of variable selection is three-fold: improving the prediction performance of the predictors, providing faster and more cost-effective predictors, and providing a better understanding of the underlying process that generated the data."

  * They present a hierarchical method for reinforcement learning.
  * The method combines "long"-term goals with short-term action choices.

### How
  * They have two components:
    * Meta-Controller:
      * Responsible for the "long"-term goals.
      * Is trained to pick goals (based on the current state) that maximize (extrinsic) rewards, just like you would usually optimize to maximize rewards by picking good actions.
      * The Meta-Controller only picks goals when the Controller terminates or achieved the goal.
    * Controller:
      * Receives the current state and the current goal.
      * Has to pick a reward maximizing action based on those, just as the agent would usually do (only the goal is added here).
      * The reward is intrinsic. It comes from the Critic. The Critic gives reward whenever the current goal is reached.
  * For Montezuma's Revenge:
    * A goal is to reach a specific object.
    * The goal is encoded via a bitmask (as big as the game screen). The mask contains 1s wherever the object is.
    * They hand-extract the location of a few specific objects.
    * So basically:
      * The Meta-Controller picks the next object to reach via a Q-value function.
      * It receives extrinsic reward when objects have been reached in a specific sequence.
      * The Controller picks actions that lead to reaching the object based on a Q-value function. It iterates action-choosing until it terminates or reached the goal-object.
      * The Critic awards intrinsic reward to the Controller whenever the goal-object was reached.
    * They use CNNs for the Meta-Controller and the Controller, similar in architecture to the Atari-DQN paper (shallow CNNs).
    * They use two replay memories, one for the Meta-Controller (size 40k) and one for the Controller (size 1M).
    * Both follow an epsilon-greedy policy (for picking goals/actions). Epsilon starts at 1.0 and is annealed down to 0.1.
    * They use a discount factor / gamma of 0.9.
    * They train with SGD. 

### Results
  * Learns to play Montezuma's Revenge.
  * Learns to act well in a more abstract MDP with delayed rewards and where simple Q-learning failed.

--------------------

# Rough chapter-wise notes


* (1) Introduction
  * Basic problem: Learn goal directed behaviour from sparse feedbacks.
  * Challenges:
    * Explore state space efficiently
    * Create multiple levels of spatio-temporal abstractions
  * Their method: Combines deep reinforcement learning with hierarchical value functions.
  * Their agent is motivated to solve specific intrinsic goals.
  * Goals are defined in the space of entities and relations, which constraints the search space.
  * They define their value function as V(s, g) where s is the state and g is a goal.
  * First, their agent learns to solve intrinsically generated goals. Then it learns to chain these goals together.
  * Their model has two hiearchy levels:
    * Meta-Controller: Selects the current goal based on the current state.
    * Controller: Takes state s and goal g, then selects a good action based on s and g. The controller operates until g is achieved, then the meta-controller picks the next goal.
  * Meta-Controller gets extrinsic rewards, controller gets intrinsic rewards.
  * They use SGD to optimize the whole system (with respect to reward maximization).

* (3) Model
  * Basic setting: Action a out of all actions A, state s out of S, transition function T(s,a)->s', reward by state F(s)->R.
  * epsilon-greedy is good for local exploration, but it's not good at exploring very different areas of the state space.
  * They use intrinsically motivated goals to better explore the state space.
  * Sequences of goals are arranged to maximize the received extrinsic reward.
  * The agent learns one policy per goal.
  * Meta-Controller: Receives current state, chooses goal.
  * Controller: Receives current state and current goal, chooses action. Keeps choosing actions until goal is achieved or a terminal state is reached. Has the optimization target of maximizing cumulative reward.
  * Critic: Checks if current goal is achieved and if so provides intrinsic reward.
  * They use deep Q learning to train their model.
  * There are two Q-value functions. One for the controller and one for the meta-controller.
  * Both formulas are extended by the last chosen goal g.
  * The Q-value function of the meta-controller does not depend on the chosen action.
  * The Q-value function of the controller receives only intrinsic direct reward, not extrinsic direct reward.
  * Both Q-value functions are reprsented with DQNs.
  * Both are optimized to minimize MSE losses.
  * They use separate replay memories for the controller and meta-controller.
  * A memory is added for the meta-controller whenever the controller terminates.
  * Each new goal is picked by the meta-controller epsilon-greedy (based on the current state).
  * The controller picks actions epsilon-greedy (based on the current state and goal).
  * Both epsilons are annealed down.

* (4) Experiments
  * (4.1) Discrete MDP with delayed rewards
    * Basic MDP setting, following roughly: Several states (s1 to s6) organized in a chain. The agent can move left or right. It gets high reward if it moves to state s6 and then back to s1, otherwise it gets small reward per reached state.
    * They use their hierarchical method, but without neural nets.
    * Baseline is Q-learning without a hierarchy/intrinsic rewards.
    * Their method performs significantly better than the baseline.
  * (4.2) ATARI game with delayed rewards
    * They play Montezuma's Revenge with their method, because that game has very delayed rewards.
    * They use CNNs for the controller and meta-controller (architecture similar to the Atari-DQN paper).
    * The critic reacts to (entity1, relation, entity2) relationships. The entities are just objects visible in the game. The relation is (apparently ?) always "reached", i.e. whether object1 arrived at object2.
    * They extract the objects manually, i.e. assume the existance of a perfect unsupervised object detector.
    * They encode the goals apparently not as vectors, but instead just use a bitmask (game screen heightand width), which has 1s at the pixels that show the object.
    * Replay memory sizes: 1M for controller, 50k for meta-controller.
    * gamma=0.99
    * They first only train the controller (i.e. meta-controller completely random) and only then train both jointly.
    * Their method successfully learns to perform actions which lead to rewards with long delays.
    * It starts with easier goals and then learns harder goals.

This paper develops algorithms and mistake bounds for learning non-noisy boolean functions.  It considers the case when there is a very large number of possible attributes, but each example (and the concept) depends on only a few attributes, so we want ot avoid having to ever explicitly list or consider all possible attributes.  The concept classes it deals with learning are boolean formulas. The paper is a good cite but (for my work) probably not directly applicable.

#### Introduction

* Automated Theorem Proving (ATP) - Attempting to prove mathematical theorems automatically.
* Bottlenecks in ATP:
    * **Autoformalization** - Semantic or formal parsing of informal proofs.
    * **Automated Reasoning** - Reasoning about already formalised proofs.
* Paper evaluates the effectiveness of neural sequence models for premise selection (related to automated reasoning) without using hand engineered features.
* [Link to the paper](https://arxiv.org/abs/1606.04442)

#### Premise Selection

* Given a large set of premises P, an ATP system A with given resource limits, and a new conjecture C, predict those premises from P that will most likely lead to an automatically constructed proof of C by A

#### Dataset

* Mizar Mathematical Library (MML) used as the formal corpus.
* The premise length varies from 5 to 84299 characters and over 60% if the words occur fewer than 10 times (rare word problem).

#### Approach

* The model predicts the probability that a given axiom is useful for proving a given conjecture.
* Conjecture and axiom sequences are separately embedded into fixed length real vectors, then concatenated and passed to a third network with few fully connected layers and logistic loss.
* The two embedding networks and the joint predictor path are trained jointly.

##### Stage 1: Character-level Models

* Treat premises on character level using an 80-dimensional one hot encoding vector.
* Architectures for embedding:
    * pure recurrent LSTM and GRU Network
    * CNN (with max pooling)
    * Recurrent-convolutional network that shortens the sequence using convolutional layer before feeding it to LSTM.

##### Stage 2: Word-level Models

* MML dataset contains both implicit and explicit definitions.
* To avoid manually encoding the implicit definitions, the entire statement defining an identifier is embedded and the definition embeddings are used as word level embeddings.
* This is better than recursively expanding and embedding the word definition as the definition chains can be very deep.
* Once word level embeddings are obtained, the architecture from Character-level models can be reused.

#### Experiments

##### Metrics

* For each conjecture, the model ranks the possible premises.
* Primary metric is the number of conjectures proved from top-k premises.
* Average Max Relative Rank (AMMR) is  more sophisticated measure based on the motivation that conjectures are easier to prove if all their dependencies occur earlier in ranking.
* Since it is very costly to rank all axioms for a conjecture, an approximation is made and a fixed number of random false dependencies are used for evaluating AMMR.

##### Network Training

* Asynchronous distributed stochastic gradient descent using Adam optimizer.
* Clipped vs Non-clipped Gradients.
* Max Sequence length of 2048 for character-level sequences and 500 for word-level sequences.

##### Results

* Best Selection Pipeline - Stage 1 character-level CNN which produces word-level embeddings for the next stage.
* Best models use simple CNNs followed by max pooling and two-stage definition-based def-CNN outperforms naive word-CNN (where word embeddings are learnt in a single pass).

Lauer and Needham explain the duality in expressiveness and performance between

 - message-oriented concurrency models in which there are a small number of fixed tasks that communicate explicitly, and
 - process-oriented concurrency models in which there are a larger number of dynamic processes that share memory.

Message-oriented systems can be characterized by the following hallmarks, consequences, and provided facilities.

| Hallmark                                                                                 | Consequences                                                                                            | Facilities                                                                                              |
|------------------------------------------------------------------------------------------|---------------------------------------------------------------------------------------------------------|---------------------------------------------------------------------------------------------------------|
| Long standing communication channels are typically created during program initialization | Synchronization is implicitly performed in the queues connecting processes                              | Messages and message ids                                                                                |
| There are a fewer number of long lasting processes                                       | Shared structures are passed by reference; only processes with a reference to a structure can act on it | Message channels and ports that provide the ability to Send, WaitForReply, WaitForMessage, or SendReply |
| Processes don't share memory                                                             | Peripheral devices are treated like processes and communicated with                                     | Process creation (but no deletion)                                                                      |
| Processes read a small number of messages at a time                                      |                                                                                                         |                                                                                                         |

Process-oriented systems can be similarly characterized:

| Hallmark                                                 | Consequences                                                         | Facilities                     |
|----------------------------------------------------------|----------------------------------------------------------------------|--------------------------------|
| Global data can be protected and accessed via interfaces | Synchronization is performed in locks                                | Procedures                     |
| Process creation and deletion is a lightweight task      | Data is shared directly, with small portions being locked            | fork/join procedure invocation |
| Processes typically have a single job                    | Peripheral interaction typically involves locking and sharing memory | Modules and monitors           |
| Module instantiation                                     |                                                                      |                                |
| Condition variables                                      |                                                                      |                                |

There is a duality between the two concurrency models. Any program in one has a corresponding program written in the other. Lauer and Needham demonstrate the duality not by simulating model's primitives using the other, but by drawing similarities between the two's components:

| Message-oriented                        | Process-oriented                  |
|-----------------------------------------|-----------------------------------|
| Processes, CreateProcess                | Monitors, NEW/START               |
| Message Channels                        | External Procedure identifiers    |
| Message Ports                           | ENTRY procedure identifiers       |
| SendMessage; AwaitReply                 | simple procedure call             |
| SendMessage; ... AwaitReply             | FORK; ... JOIN                    |
| SendReply                               | RETURN                            |
| WaitForMessage loop with case statement | monitor lock, ENTRY attribute     |
| arms of case statement                  | ENTRY procedure declarations      |
| selective waiting for messages          | condition variables, WAIT, SIGNAL |

This correspondence can be used to directly rewrite a canonical program between the two models. In fact, the differences between the two models becomes simply a matter of keyword choice. Moreover, if both models are implemented with identical blocking and scheduling mechanism, then the two models lead to identical performance as well. Since the choice of model does not affect the user or implementor, the decision of which model to use should be based on the architecture of the underlying hardware.