Are the labels updated during training in the algorithm presented in "An algorithm for correcting mislabeled data"?

I think that making some draws might help.

Below I tried to draw the model architecture. We start with classic feed-forward structure: input represented by a vector I with length f (number of features), a hidden layer H which does not have a fixed size, and output O of length c (number of classes). Then we have 3 extra vectors than usual:
a vector U they refer as input (a bit confusing I have to say), and two vectors V and P representing classes probabilities. All these vectors have length c.

P is what we want to learn, new class probabilities for each instance that should correct wrong labels of misclassified instances in the initial dataset.
So in some sense the aim of the work is not to train a model to make predictions but rather train a model to clean a training dataset. I think it's important to stress out this point because we talk about training but there is actually no test after the training, we just end with a modified training dataset with some instances relabelled.
The relabelling depends on the learning of V rather than P (because as I will say also later on, the final arrow that goes from V to P is the identity function). V depends on U that also depends on V, again it sounds a bit confusing, the tricks rely in the initialisation.

In the second picture I just copied some formulas from the paper. They don't specifically say how they get the vector P in the first place, but I treat it simply as given because we need it to initialise U by applying the inverse sigmoid function, element-wise. We need also to define the hyper parameter D, the initial probability value for the true class V$_y$ in the initial dataset. In the paper they set it to .95. Using D we can initialise the vector V.

Once we initialise U and V we have all the elements to iterate over the dataset.

A first thing to notice is that they don't use back propagation to update U,V and P, they just define some updating rules (which require to define some other initial parameters, $\textit{u$_0$}$ and L$_p$). I want to stress out again that the mapping between V and P is just the identity function, I guess that they define it just to avoid confusion, because in the paper P appear as an input element, but nevertheless is also the output we want to learn. Back propagation is used only to update the weights in H.

ANSWERS TO THE QUESTIONS:

So we can finally say that, regarding your first question, the answer is yes, they do start updating the classes probability vectors P from the very first iteration, even though is not clear how they initialise them (or from where they got them).

Regarding the second question instead I would say that no, this is definitely not as training a model with fixed label and then making predictions over the training dataset again. The whole point is that similar training instances will be initialised with the same P, and they will also produce similar U and V vectors. For misclassified instances, U will be updated with larger changes, because of the different produced O. For example an image of a 2 will generate a different output than an image of a 5, this would be reflected first on U and then on V and P . If training with fixed label instead you would just force the weight in the hidden layer to learn a function that treat the representation of a 2 and a 5 in a similar way, leading to low accuracy cause you would be telling the model "Hey, the straight line in the 5 is important also to recognise a 2".

I have to say that I never read about this dataset cleaning approach but it is interesting, and their results show that the cleaned version of the dataset lead to better performances, which is interesting because machine learning analysis usually gives for granted the correctness of the labels.

Hope this is of help in some ways!


Why do authors track $\gamma_t$ in Prioritized Experience Replay Paper?

In some cases we may wish to have a discount factor $\gamma_t$ which depends on time $t$ (or depends on state $s_t$ and/or action $a_t$, leading to an indirect dependence on time $t$). Indeed we do not usually do this, but it does happen sometimes.

I guess that, from a theoretical point of view, it was very easy of the authors to make their algorithm more flexible/general and also support this (somewhat rare) case of time-varying discount factor. If it had been very complicated for them to support this option, they may have chosen not to; but if it's trivial to do so, well, why not?

Practical implementations will often indeed ignore that possibility if they're not using it, and can avoid including $\gamma_t$ values in the replay buffer altogether if it is known to be a constant $\gamma_t = \gamma$ for all $t$. As far as I can see, in the experiments discussed in this paper they also only used a fixed, constant $\gamma$.


Is transistor the first artificial intelligence?

I think it might come down to whether the transistor is making a decision.  If the transistor is being used as a switch, that would seem to qualify as a decision, even though it's an extremely rudimentary decision.

Intelligence, in reference to Artificial (or Algorithmic) Intelligence, is not restricted to high intelligence.  A brute force Tic-Tac-Toe AI has extremely low, narrow intelligence but still constitute AI.  An automatic switch, which makes the most simple decision possible, a binary choice, would seem to be the most basic form of intelligence.

Norvig's definition seems rooted in game theory, which is important in terms of utility of intelligence.  But in a condition of intractability one is only assuming one's decision is more optimal than other choices. Outcomes can be evaluated, and a determination made as to whether the algorithm was "smart" or "dumb", but these terms refer to relative positions on a spectrum.

It's worth noting this fundamental definition of AI opens up a can of worms in that pre-transistor, automated mechanical switches such as the Strowger switch would also probably qualify.

And automata do not have to be electrical.  The History of Automation wiki suggests the first feedback control system was for a water clock invented by Ctesibius.  This device dates to the 3rd Century BCE, and water clocks were said to be the most accurate time pieces until Huygens.

This type of intelligence I tend to think of as autonomic, in the sense of involuntary, and distinct from higher functions, which are more commonly associated with "intelligence".

Note: The characteristics of an autonomic system in a computing context are quite interesting and include self-optimization, self-learning, and self-awareness.

ADDENDUM: After much thought, in reference to @JT's answer, I can't see how decisions can be separated from goals—there needs to be an intent, or the decision is merely random. This might prompt the question "can a simple switch be said to have a goal?"


Additional (Potential) Action for Agent in MazeGrid Environment (Reinforcement Learning)

You can definitely define an environment that accepts more types of action, including actions that take multiple steps in a direction.

The first thing you would need to do is implement support for that action in the environment. That is not really a reinforcement learning issue, but like implementing the rules of a board game. You will need to decide things such as what happens if the move would be blocked - does the move succeed up the point of being blocked, does it fail completely, is the reward lower depending on how much the agent tries to overshoot, etc.

After you do that, you will want to write an agent that can choose the new actions. You have a few choices here:

Simplest would be to enumerate all the choices separately and continue to use the same kind of agent as you already have. So instead of $\{U, D, L, R\}$ you might have $\{U1, U2, U3, D1, D2, D3, L1, L2, L3, R1, R2, R3\}$.
If you want to take advantage of generalisation between similar actions (e.g. that action $U3$ is similar to $U2$ and also to $R3$), then you can use some form of coding for the action, such as the relative x,y movement that it is attempting. So you could express $U2$ as $(0,2)$ and $L3$ as $(-3,0)$. For that to then work with Q values, you cannot easily use a table. Instead, you would need to use function approximation, for example a neural network, so you can implement $q(s,a)$ as a parametric function - combining $s,a$ into the input vector, and learn the parameters to that the neural network outputs the correct action value. This is what the Q learning variation DQN can do, as well as other similar RL algorithms that use neural networks.

Using a neural network, instead of tabular Q-learning, is not something you see often with grid world environments. It is a step up in complexity, but it is often required if state space or action space becomes large and might benefit from the generalisation possible from trainable function approximators.


Why does it make sense to study MDPs with finite state and action spaces?

In addition to the reason outlined in the comment, also note that if the state-space and action-space are both finite and of feasible size, tabular methods can be used, and there are some advantages to them (like the existence of convergence guarantees and generally a smaller number of hyperparameters to tune).


Almost, but no. When you maximize that objective function, you do so by adjusting the parameters $\phi$ and $\theta$. After you're done with training, you can use your word embeddings for other NLP tasks. You don't, however, do any prediction directly from the skip-gram model.

To maximize the first term, co-occuring words must have large inner products. That is, they must be "similar". To maximize the second term**, the randomly sampled words must have a small inner product with $\phi_u$. That is, they must be "dissimilar" to $\phi_u$. Moving these word embeddings around in the vector space to make some words similar and others not is the only thing that happens during skip-gram training.
$$$$

** $\sigma(-x)=1-\sigma(x)$, so maximizing $\sigma(-x)$ is minimizing $\sigma(x)$


Can mutation enable a disabled connection?

Yes, the original gene is disabled, but is left in the genome. This can be seen on page 10, figure 3 of the paper linked (taken from the original paper NEAT Paper) where gene 3 is disabled, but not removed from the genome. This gene can be re-enabled by receiving the gene with the identical innovation number from a mating partner with the gene enabled during crossover.

The original paper does not mention a mutation to re-enable genes, but various other publications and implementations after the original paper do. This is desirable for a number of reasons. Re-enable mutate allows for dropout to used in the implementation. It is also possible that certain genomes are disabling genes too quickly and this can help to correct for that.


How can alpha zero learn if the tree search stops and restarts before finishing a game?

You're right that AlphaGo Zero doesn't perform rollouts in its MCTS. It does complete many, many games, though.

Realize that AlphaGo Zero only iterates MCTS 1,600 times before taking an action. The next state resulting from that action becomes the root of future search trees. Since a typical game of Go only lasts a few hundred moves, the board will very quickly reach a terminal state.

None of this is dependent on the initial performance of the neural network. The neural net can be incredibly bad; actions/moves will still be taken at the same frequency. Of course, since AlphaGo Zero trains with self-play, one of its two selves in a game will usually be the winner (ties are possible). So the neural net will improve over time.

I recommend going over the "Self-Play Training Pipeline" section of the paper.


What kind of deep learning model does latest version of AlphaFold use for protein folding problem?

The accurate answer is 'we don't know for sure'. But that said, the Deepmind article about AlphaFold 2, which won the CASP 14 competition, says this:

A folded protein can be thought of as a “spatial graph”, where residues are the nodes and edges connect the residues in close proximity. This graph is important for understanding the physical interactions within proteins, as well as their evolutionary history. For the latest version of AlphaFold, used at CASP14, we created an attention-based neural network system, trained end-to-end, that attempts to interpret the structure of this graph, while reasoning over the implicit graph that it’s building. It uses evolutionarily related sequences, multiple sequence alignment (MSA), and a representation of amino acid residue pairs to refine this graph.

A reasonable assumption that can be formed from this paragraph is that it is using some kind of a Transformer-based architecture. Yannic Kilcher's review video on AlphaFold discusses this assumption, along with a detailed explanation of the previous version of AlphaFold.
The source code for this previous version of AlphaFold, the one that was used in CASP 13, seems to have been open-sourced by Deepmind in their Github repository:
https://github.com/deepmind/deepmind-research/tree/master/alphafold_casp13


Once the environments are vectorized, how do I have to gather immediate experiences for the agent?

class ExperienceSource():
    def __init__(self, env, agent, reward_steps):
        self.env = env
        self.agent = agent
        self.reward_steps = reward_steps

    def __iter__(self):
        histories = [deque(maxlen=self.reward_steps) for i in range(len(self.env.envs))]
        states = self.env.reset()

        while True:

            for idx, env in enumerate(self.env.envs):
                action = self.agent.choose_action(states[idx])
                state, reward, done, _ = env.step(action)

                current_rewards[idx] += reward
                histories[idx].append(Experience(state, action, reward, done))

                if len(histories[idx]) == self.reward_steps:
                    yield tuple(histories[idx])

                if done:
                    yield tuple(histories[idx])
                    state = env.reset()

Be aware that self.reward_steps is simply the value defined by N-1 in the following formula $$Q(s,a) = \sum_{i=0}^{N-1} \gamma^i r_i
 + \gamma^N V(s_N)$$ and self.env is simply an instance of GymEnvVec class from the question.


Applying NNs to 2d image noise reduction?

You might want to look into autoencoders. What they do is learn the relationship between the input and a simplified version of it, and then try to reconstruct the original version of the input.

The good news about this architecture is that it is not a supervised learning technique, so you can feed it a lot of data without having to construct both input and output.

Hopefully, if you train it right, it will learn that the parts of the image that are not important in the result are the noisy parts that you intend to remove.

Note that autoencoders had already been used to reduce noise in audio and image with great success.

Update: Here's a quick not-so-technical explanation on why they work.

In the general architecture that auto-encoder networks have, you'll usually find an input layer, a certain amount of hidden layers which usually have less nodes than the input layer, and then a certain amount of hidden layers that gradually grow to have the same amount of input layers in the output layer.

Why they learn to reproduce the input in the output layer, the data representation needs to necessarily go through the narrow middle layer -- at that point, you can consider that the input has been "compressed", usually with a lossly approach to have a representation of the data that can later on use to reproduce the input.

(Side note: this compression feature has been tested in replacement of compression algorithms but they are not so good at performing compression as particular algorithms designed for it.)

When reducing the error between input and output, the network then starts forgetting the pieces that don't add as much information to the input as other bits of data in it. For instance, if you always train these images with figures in white backgrounds, it is likely that the encoded representation of the image will not have any information about the white background itself, since it is not required to be recreated.

As such, the most common pieces will start falling apart, and with the right tuning, a general amount of noise will go away too. Uniform noise is easier to remove (for the very same reason as the white background example), but variable noise can be worked around too with the right training.


What are the (general) sizes of AlphaGo and Deep Blue?

AlphaGo used data from the KGS Go Server, which had 160,000 games and 29 million board/next-move pairs. But crucially, after it was trained on the dataset, AlphaGo was trained through self-play, so its competence shouldn't be measured strictly in terms of its database.

I'm not 100% sure how Deep Blue worked, but I think it was a mix of 1. a "book" of opening theory 2. explicitly coded board evaluation functions 3. a "book" of endgames. So there isn't a "database" in your traditional "ML by big data" sense. But in any case, I would assume the bulk of the work is done by the evaluation function, so again its strength cannot be measured in terms of if its database.


What is the difference between hill-climbing and greedy best-first search algorithms?

Let's see their definition first:

Best First Search (BFS):

  Best-first search is a search algorithm that explores a graph by expanding the most promising node chosen according to a specified rule.

  estimating the promise of node n by a "heuristic evaluation function ${\displaystyle f(n)}$ which, in general, may depend on the description of n, the description of the goal, the information gathered by the search up to that point, and most importantly, on any extra knowledge about the problem domain."

Hill Climbing (HC):

  In numerical analysis, hill climbing is a mathematical optimization technique that belongs to the family of local search. It is an iterative algorithm that starts with an arbitrary solution to a problem, then attempts to find a better solution by making an incremental change to the solution. If the change produces a better solution, another incremental change is made to the new solution, and so on until no further improvements can be found.

Base on the definition, we can find the following differences:

The aim of BFS is reaching to a specified goal by using a heuristic function (it might be greedy) vs. HC is a local search algorithm
BFS is mostly used in the graph search (in a wide state space) to find a path. vs. HC is using for the optimization task.


Does the neural network calculate different relations between inputs automatically?

On paper, one expects a complex enough network to determine any complicated function of a limited number of inputs, given a large enough dataset. But in practice, there is no limit to the possible difficulty of the function to be learnt, and the datasets can be relatively small on occasion. In such cases - or arguably in general - it is definitely a good idea to define some combination of the inputs depending on some heuristics as you suggested. If you think some combination of inputs is an important variable by itself, you definitely should include it in your inputs.

We can visualize this situation in TensorFlow playground. Consider the circular pattern dataset on top left corner with some noise. You can use the default setting: $x_1$ and $x_2$ as inputs with 2 hidden layers with 4 and 2 neurons respectively. It should learn the pattern in less than 100 epochs. But if you reduce the number of neurons in the second layer to 2, it is not going to get as good as before. So, you are making the model more complicated to get the correct answer.

You can experiment and see that one needs at least one 3 neuron layer to get the correct classification from just $x_1$ and $x_2$. Now, if we examine the dataset, we see the circles so we know that instead of $x_1$ and $x_2$, we can try $x_1^2$ and $x_2^2$. This will learn perfectly without any hidden layers as the function is linear in these parameters. The lesson to be learnt here is that, our prior knowledge of the circle ($x_1^2 + x_2^2 = r^2$)  and familiarity with the data helped us in getting a good result with a simpler model (smaller number of neurons), by using derived inputs.

Take the spiral data at the lower right corner for a more challenging problem. For this one, if you do not use any derived features, it is not likely to give you the correct result, even with several hidden layers. Keep in mind that every extra neuron is a potential source of overfitting, on top of being a computational burden.

Of course the problem here is overly simplified but I expect the situation to be more or less the same for any complicated problem. In practice, we do not have infinite datasets or infinite compute times and the model complexity is always a restriction, so if you have any reason to think some relation between your inputs is relevant for your final result, you definitely should include it by hand at the beginning.


Can Alpha–Beta be used on symmetric zero sum games?

If the game is not sequential, there would be no game tree and no need for pruning.  Alpha-beta is a technique applied to look-ahead search.  Alpha-beta has demonstrated utility in algorithms that play combinatorial games.

(Even in iterated dilemmas, it doesn't really branch because it's simultaneous, more of a vine than a tree.  Decisionmaking would be based on mathematical analysis of the payoff matrix and statistical analysis of competitor behavior over time.)


Combining deep reinforcement learning with alpha-beta pruning

Yes it's possible to to combine AlphaZero with Minimax methods (including alpha-beta pruning). AlphaZero itself is combination of  Monte Carlo Tree Search (MCTS) and Deep Network, where MCTS is used to get data to train network and network used for tree leafs evaluation (instead of rollout as in classical MCTS). It's possible to combine selection-expansion part of AlphaZero MCTS with Minimax the same way as it was done for classical MCTS - "Monte-Carlo Tree Search and Minimax Hybrids", pdf.


What is the purpose of the actor in actor-critic algorithms?

For discrete action spaces, what is the purpose of the actor in Actor-Critic algorithms?

In brief, it is the policy function $\pi(a|s)$. The critic (a state action function $v_{\pi}(s)$) is not used to derive a policy, and in "vanilla" Actor-Critic cannot be used in this way at all unless you have the full distribution model of the MDP.

  It just seems to me that if you can accurately estimate the value function, then you have solved the RL challenge.

Often this can be the case, and this is how e.g. Q-learning works, where the value function is more precisely the action value function, $q(s,a)$.

Continuous or very large action spaces can cause a problem here, in that maximising over them is impractical. If you have a problem like that to solve, it is often an indicator that you should use a policy gradient method such as Actor-Critic. However, you have explicitly asked about "discrete action spaces" here.

The main issue with your statement "if you can accurately estimate the value function" is that you have implicitly assumed the the learning is complete. You are looking at the final output of the algorithm, after it has converged, and asking why not use just half of its output. Whilst choosing between RL algorithms is more often related to how they learn, how efficiently they learn, and how they behave during the learning process.

  My current understanding is that the critic estimates the future reward given an action, so why not just take the action that maximizes the estimated return?

The critic is $v_{\pi}(s)$ so does not take actions into account. You can of course learn $q_{\pi}(s,a)$ instead or as well - and some policy gradient methods also estimate the action value, such as Advantage Actor-Critic.

The main difference is in how data gathered from experience is applied to changing the policy. Recall at any step during reinforcement learning, that all estimates are based around a best guess at values of a current target policy. Policy gradient methods directly improve the policy, whilst value-based methods have an implied policy based on the same learned value functions. The $\text{argmax}_a q(s,a)$ approach used in Q-learning or SARSA gives a simple but crude mapping from values to policy, and means that the trajectory through policy space taken whilst learning is different when comparing policy gradient methods and value-based methods.

The following are notable differences affecting performance between policy-based methods and value-based methods:

Policy-gradient methods tend to make small changes to policy on each step, the policy changes smoothly, adjusting probabilities between choice of different actions by small amounts. This in turn means that the targets for estimated value functions change slowly. In comparison, when a value based method finds a new maximising action, it can make a big change to the policy, making the updates required less smooth.
Policy-gradient methods can learn to balance stochastic policies, whilst value-based methods assume deterministic policies. So if you have a situation like paper, scissor stone game where the ideal policy is random choice between actions, you should use policy gradients. This is a bit niche, but is worth noting.
Function approximators (typically neural networks) are easier to train on simpler target functions. The policy function $\pi(a|s)$ and action value function $q(s,a)$ are quite different views of the same problem, and it can be the case that one has a simple form whilst the other is more complex. This can make a big practical difference on which algorithms learn fastest.

For smaller, discrete action spaces, there is not always a clear choice between policy gradient and value-based methods. You could use either and it may be worth doing an experiment to find the most efficient algorithm for certain classes of problem.


Is it possible to combine or create conditional statements of 0 and 1, and optimize with an evolutionary algorithm (given that all computers use a binary system)?

Yes, evolutionary algorithms are very general, and can be used to modify almost any source data structure, including logic trees or even executable code, provided you have some measure of fitness to optimise for.

This can be taken to a highly abstract level, such as the paper Evolution of evolution: Self-constructing Evolutionary Turing Machine case study where an evolutionary algorithm is used to optimise other evolutionary algorithms which solve tasks using generic models of computing.

However, there are two important caveats:

There needs to be a measurement phase to establish the fitness of the algorithm. This can be very complex, depending on the problem you attempt to solve.
Genetic algorithms may be very general optimisers (capable of finding optimal solutions for problems when other algorithms may fail), but may also be very inefficient and slow depending on the size of the allowed genomes, and how the search space is structured relative to available genetic operations.

  begin with the most fundamental operations (0 and 1, if then) to develop intelligence.

Provided the fitness measure allows for the expression of intelligence, then this seems theoretically possible - in the sense that there are no known reasons why a sufficiently complex logical machine could not be intelligent by any measure we have of abstract intelligence (excluding measures deliberately constructed to exclude computational models such as "intelligence is the capability of a living system . . .")

However, such a project faces some barriers which currently look insurmountable:

There is no formal measure of general intelligence to use as a fitness function. This could be worked around using an e-life approach of providing a suitable rich virtual environment and allowing agents to compete for resources in the hope that the most competitive agents would exhibit intelligent behaviour - but that begs the question of how you could recognise and select those agents through any objective measure.
Any environment rich enough to select for general intelligence, whilst simulating low-level agent logic is likely to require a lot of computation.
Our one example of evolving basic building blocks into beings we call intelligent took billions of years, whilst processing billions upon billions of separate evolving entities at any one time.

These last two points imply a computational cost far beyond current technology, so there is no route to actually running this experiment for real.


The question, "Why do we need artificial intelligence?" is quite to the point.  Technically, the answer is, "No reason."  If we needed artificial intelligence, then we would have become extinct over the last 50,000 or more years we've been a species with human intelligence, so we want it.

We do want it, and there are benefits.  Some claim there are risks too, which is logical.  We should be open to all views.  Some of them may be spot on, and others may be without merit.

One list of benefits already seen might include these, with most beneficial on top.

Deeper interest in what exactly we mean when we say someone or some thing is intelligent
Revisiting of the validity of the g-factor belief
Revised interest in parallel computing architecture
Heightened awareness of the distinction between fake and authentic
Improved use of an interest in probability and statistics

These are further potential benefits that may also emerge.

Young students taking mathematics more seriously than hacking
The elimination of circular, wasteful job functions
More leisure time for families to enjoy together
Improved economic efficiency
Better planning regarding the use and preservation of natural resources

These are the risks from highest to lowest.

Possibly accidentally causing the emergence of an uncontained and potentially dangerous digital entity
Additional nihilism (belief that nothing matters) in our culture, which could emerge if the last refuge of human pride is overrun by smarter artificial systems
People losing their jobs, which may have only a temporary impact, if the AI does quality work, but the transition may be painful and destructive


Figuring out mapping between two matrices

Yes, with some limitations.

CNNs can be used to map images to related images, and that should include many simple matrix transformations. For instance, here is an example of de-blurring OCRed text using a CNN.

Basically, you would train your network with lots of A, B examples, with the input as B and desired output as A.

The limitation is that where you have transformations that are technically irreversible, then the CNN may learn to produce a best "mean" output. The symptom of this will be fuzzy images lacking high frequency components, and matrices which are not representative of the target distribution, but that do solve the transformation (within limits of training accuracy). If you want to improve on that, and produce a more realistic/precise original, then you will probably want to look at adding a generative component - a GAN, VAE/GAN or RBM etc. Note this would not accurately produce the original matrix, but would generate one that both transformed into your given transformed matrix (within some level of accuracy) and was sampled from your input distribution. That is, it could be more of a feasible original than one generated using a simpler CNN architecture.


What is an agent in Artificial Intelligence?

The acclaimed book Artificial Intelligence: A Modern Approach (by Stuart Russell and Peter Norvig) gives a definition of an agent

  An agent is anything that can be viewed as perceiving its environment through sensors and acting upon that environment through actuators.

This definition is illustrated by the following figure

This definition (and illustration) of an agent thus does not seem to include the agent as part of the environment, but this is debatable and can be a limitation, given that the environment also includes the agent.

According to this definition, humans, robots, and programs are agents. For example, a human is an agent because it possesses sensors (e.g. the eyes) and actuators (e.g. the hands, which, in this case, are also sensors) and it interacts with an environment (the world).

A percept (or perception) is composed of all perceptual inputs of the agents. The specific definition of the percept changes depending on the specific agent. For example, in the case of a human, the percept consists of all perceptual inputs from all sense organs of the human (eyes, ears, tongue, skin, and nose). In the case of a robot only equipped with a camera, the percept consists only of the camera frame (at a certain point in time). A percept sequence is a sequence of percepts.

An action is anything that has an effect on the environment. For example, in the case of a legged robot, an action can be "move forward".

An action is chosen by the agent function (which is illustrated by the white box with a black question mark in the figure above), which can also be called policy. The agent function highly determines the intelligent or intellectual capabilities of the agent and differentiates it from other agents.

Therefore, there are different agents depending on the sensors and actuators they possess, but, more importantly, depending on their policy, which highly affects their intellectual characteristics. A possible categorization of agents is

rational agents do the "right" thing (where "right", of course, depends on the context)
simple reflex agents select actions only based on the current percept (thus ignoring previous percepts)
model-based reflex agents build a model of the world (sometimes called a state) that is used to deal with cases where the current percept is insufficient to take the most appropriate action
goal-based agents possess some sort of goal information that describes situations that are desirable; for example, in the case of a human, a situation that is desirable is to have food
utility-based agents associate value with certain actions more than others; for example, if you need immediate energy, chocolate might have more value than some vegetable
learning agents update their e.g. model based on the experience or interaction with the environment

More details regarding these definitions can be found in section 2 of the book mentioned above (3rd edition). However, note that there are other possible categorizations of agents.

A reinforcement learning (RL) agent (which is a program) is an agent that interacts with an environment and can learn a policy (a behavioral strategy or agent function) or value (or utility) function (from which the policy can be derived) from this interaction, where the agent takes an action from the current state (or model) of the environment and the environments emits a percept, which, in the case of RL, consists of a reinforcement (or reward) signal and the next state. The goal of the RL agent is to maximize the cumulative reward (or reinforcement) signal. An RL agent can thus be considered a rational, goal, utility-based and learning agent. It can also be (or not) a simple reflex and model-based agent.


Transposition table is only used for roughly 17% of the nodes - is this expected?

I don't think that's necessarily a strange number. It's impossible for anyone to really tell you whether that 17% is "correct" or not without reproducing it, which would require much more info (basically would have to know every single tiny detail of your implementation to be able to reproduce).

Some things to consider:

The size of your transposition table / the number of bits you use for indexing into the TT. If you have a relatively small TT, meaning you use relatively few bits for indexing, you'll have bigger probabilities of collisions. That means you will have to replace existing entries more often, which means they might no longer be in the table anymore by the time you encounter transpositions during the search.
Where in the search tree are the nodes located that are recognized as transpositions already in the table? If you detect transpositions very high up in the search tree, you save a lot more search time than if you detect a transposition somewhere deep down in the search tree; once you detect a transposition that has already been searched sufficiently deep for the value stored in the table to be valid, you can cut off the complete subtree below that node from the search. This becomes more valuable as it happens closer to the root. So, just the number "17% of nodes" doesn't really tell us much.
Are you using iterative deepening? Since you mentioned only minimax + alpha-beta pruning in the question, I suspect you're not using iterative deepening. TTs become significantly more valuable once you do use iterative deepening, because then almost every state encountered becomes a "transposition". You'll already have seen all those states in a previous iteration with a lower search depth limit. Now, it is important to note with this combo of ID + TTs, that you can no longer completely cut off searches for all recognized transpositions. If an entry in the table holds a value that was computed with a search depth of $d$, that value will no longer be valid when performing a subsequent iteration of ID with a max search depth of $d + 1$ for example. However, that "outdated" value stored in the TT can still be used for move ordering, which can lead to significantly more prunings from alpha-beta pruning.
How efficient is the remainder of your engine? A TT is not 100% free, it takes a bit of additional time too (for example to compute the hash values for your game states). If the rest of your engine is relatively slow (i.e. inefficient implementation for playing moves, copying game states, etc.), the computational overhead of the TT won't matter much and even a low number of recognized transpositions will still be valuable. If the rest of your engine is very fast, it'll be more important to have a high number of transpositions for the TT to be really valuable.

As an "educated guess", I'd say the number of 17% you describe is not necessarily strange. Especially given your edit to the question, where you indeed mention that it is likely that transpositions are found high up in the tree (close to the root). When this happens, you immediately remove the probability of recognizing all those states deeper down in the tree of getting recognized as transpositions yourself. So, the pool of states that could "potentially" be found in the TT is much less than 100% of the states stored in the TT.

It's really just that though, just an educated guess. It's going to be very difficult for anyone to give a conclusive "yes" or "no".


How can I use deep reinforcement learning for vehicle rerouting in SUMO?

There is a platform called Flow, sounds like its what you're looking for

https://github.com/flow-project/flow


How do I calculate the return given the discount factor and a sequence of rewards?

You know all the rewards. They're 5, 7, 7, 7, and 7s forever. The problem now boils down to essentially a geometric series computation.
$$
G_0 = R_0 + \gamma G_1
$$
$$
G_0 = 5 + \gamma\sum_{k=0}^\infty 7\gamma^k
$$
$$
G_0 = 5 + 7\gamma\sum_{k=0}^\infty\gamma^k
$$
$$
G_0 = 5 + \frac{7\gamma}{1-\gamma} = \frac{5 + 2\gamma}{1-\gamma}
$$


Purpose of using actor-critic algorithms under deterministic MDP dynamics?

In deep reinforcement learning for portfolio optimization, many researchers (Xiong at al. for example) use historical market data for model training. The resulting MDP dynamics is of course completely deterministic (if historical prices are used as states) and there's no real sequentiality involved.

Whilst I cannot comment on the specific financial model, I think it unlikely that these researchers would apply RL without there being a sequence.

More likely in my opinion, the historic data feed forms a major part of the environment, but that there are still time steps and a state which depends on an agent's actions. For instance, in a trading simulation, provided the values of trades are below levels that would significantly alter the market itself, it may be a reasonable approximation to use the history of prices and other factual information that progress like a recording, plus have state include the agent's current portfolio of investment and working funds.

  What's the point of using DDPG for variance reduction when the underlying MDP used for training has deterministic dynamics? Why not simply use the Reinforce algorithm?

Variance in returns occurs due to stochastic dynamics (if they are present) and the behaviour policy. You cannot use any RL control algorithm with a deterministic behaviour policy*. It would never gain any data that allowed it to assess alternative behaviour.

So in REINFORCE, which is on-policy (the behaviour policy and target policy are the same), and typically starts with near equiprobable action choices, there is high variance. It could be very high when measured over a long episode with many action choices. In basic REINFORCE, the variance is not controlled for, and training uses individual Monte Carlo style returns.

In DDPG, which is off-policy (the target policy is deterministic**, the behaviour policy is stochastic), there is still variance, but it is much reduced with the actor-critic mechanism, plus can be constrained by choice of noise function that relates the behaviour policy to the target policy. In addition, updates to policy and value functions can be made independently of episode ends, which can significantly speed up learning.

To determine what difference this makes for any experiment, you would need to compare the two algorithms on the same task. In practice DDPG will significantly out-perform REINFORCE on many tasks, including those with deterministic environments. However, there might be specific combinations where the simplicity of REINFORCE wins out, if only because there are less hyperparameters to tune.

On one point:

  under an almost-deterministic policy our variance will be quite small

That's true, but how do you get to that stage of training with REINFORCE? It is by testing and working through more stochastic policies, which is what will take time. Your statement only applies to REINFORCE when the control problem is nearly complete, or if you take a short-cut and force the policy function into what you hope is a near-optimal policy. In which case you are engaging in a form of variance reduction - it may even work for some scenarios, but is likely not as general as applying an Actor-Critic algoirthm.

* Actually technically you can if the environment is stochastic in the right way so that you effectively explore all state/action combinations. But we are talking about deterministic environments here, and obviously the stochastic environment would introduce variance in returns.

** The target policy changes over time, and this introduces non-stationarity and bias for the critic component to deal with, but not technically variance.


How does Atlas from Boston Dynamics have human-like movement?

Because Boston Dynamics is a private, for-profit, company, we cannot know for sure how they achieve their results. However, we can examine the available public information and make educated guesses.
In the information posted with the video, Boston Dynamics tells us that they use

... an optimization algorithm transforms high-level descriptions of
each maneuver into dynamically-feasible reference motions.  Then Atlas
tracks the motions using a model predictive controller that smoothly
blends from one maneuver to the next.

This sounds like three older AI approaches have been blended together to create the video.
First, they mention using an optimization algorithm to assemble complex motions from "dynamically-feasible reference motions". This sounds like they have first learned, or possibly pre-programmed, a range of simple movements that, on their own, are not very impressive, but that can be composed together into more complex movements. This approach is called Layered Learning, and was pioneered by Peter Stone and Manuela Veloso in the late 1990s. It is widely and successfully used in academic robotics competitions. Basically, this algorithm tries out different combinations and sequences of simple actions until it finds one that is close to the desired complex action. This is usually done with a local search algorithm, or sometimes with other optimization tools.
The second technique is, of course, actually learning to perform the basic actions that layered learning can compose together into more complex actions. This is usually done with some form of reinforcement learning, but sometimes is done by a programming who explicitly solves the equations for the movement of a simple system.
Finally, they need to use a model predictive controller to smoothly interpolate between the sequence of actions that the layered learning approach has come up with. In this approach, the engineers designing the robot have very carefully measured, for this specific robot, exactly how parts of it tend to move or continue moving, and written this down as a mathematical model called a dynamical system. This model allows the algorithm to figure out how this specific robot's movements are slipping away from the planned ones as it executes the motions. The slippage occurs because of things like friction (the robot's parts are not all perfectly smooth, and may have different amounts of lubrication, or a motor might slip). The algorithm can then make small changes to the motion to smooth out these unexpected bumps. That's the part that makes everything look so smooth.
It's worth noting too, that the video is not fully representative of the typical results their algorithm obtains. Boston Dynamics claims in the video caption that their algorithm "succeeds" in achieving a desired motion about 80% of the time. They don't tell us what "success" means, but the video is probably just the best of many takes for a carefully planned and filmed routine.


Yes, it applies. If a statement cannot be derived in a finite number of steps, then it doesn't matter if the person trying to prove it is a human or a computer.

The mathematician has one advantage over a standard theorem proving algorithm: the mathematician can "step out of the system" (as Douglas Hofstadter called in Gödel, Escher, Bach), and start thinking about the system. From this point of view, the mathematician may find that the derivation is impossible.

However, an AI for proving theorems could be programmed to recognize patterns in the derivation, just like our hypothetical mathematician, and start reasoning about the formal system to derive properties of the formal system itself.
Both the AI and the mathematician would still be bound by the laws of mathematics, and not be able to prove a theorem if it was mathematically improvable.


Training Multi class classification (One-vs-all) on Neural network

Let us suppose that you are training a neural network for classfing images of vehicles , then the input vector , image of the "vehicle" will be a 2D array of pixels. This undergoes several transformations at each layer of the neural network , the last layer of the neural network produces another vector whose dimensions are lesser than the original image vector.

So the network is mapping images to some vectors in a high dimensional space. In order to classify the images it is now sufficient to classify the vectors obtained from the network of their corresponding images, you  can do this with a simple "linear" classifier using a softmax layer.

So all the layers of the network except the last layer are transforming the image representation to a "vector". This vector is classified by a linear softmax classifier by the last layer of neural network.


Which machine learning models are universal function approximators?

Support vector machines
In the paper A Note on the Universal Approximation Capability of Support Vector Machines (2002) B. Hammer and K. Gersmann investigate the universal function approximation capabilities of SVMs. More specifically, the authors show that SVMs with standard kernels (including Gaussian, polynomial, and several dot product kernels) can approximate any measurable or continuous function up to any desired accuracy. Therefore, SVMs are universal function approximators.
Polynomials
It is also widely known that we can approximate any continuous function with polynomials (see the Stone-Weierstrass theorem). You can use polynomial regression to fit polynomials to your labelled data.


You would not believe how difficult this task is, assuming you want a humanoid robot to tie laces with humanoid hands. It’s possible of course but compared to what the current state of the art in machine learning is, this task is very very complex because it’s a physical system with unknown variables (Eg. coefficient of friction on laces), physical limitations (Eg. dexterity of robotic hands), and occluded vision (Eg. hand in front of laces) to name a couple of the issues one faces not to mention robots are expensive but I digress.

Robots can perform amazing preprogrammed sequences but if you wanted to have a robot to be able to tie any shoe in any situation, machine learning is the right approach.

Training data should include all of the things that humans use when they approach this problem:

proprioception (the location of joints in space aka where are your fingers)

a sense of touch, a robot would need a quite a few touch sensors
vision, although not actually necessary (because blind humans are capable of learning to do this task), it may speed up learning

Using reinforcement learning as a framework, one needs to be able to give the RL agent a signal that it is closer to tying the lace. This could be done in a few ways and it’s unclear what would be the best.

One method would be to train a separate model using supervised learning and pictures of shoes laced up to look at the current state of the bow (or lack thereof) and report if it looks like a tight bow. This method requires a whole other network but it may be the most versatile in the end although the RL agent may just learn how to place laces so it looks like a tight bow.

Although simple for humans, this is an interesting problem and thinking about how it could be implemented helps one understand how to apply ML in other areas.


Importance of starting state and player in RL for Tic Tac Toe

My understanding - from comments on the question - is that you are looking to train a Reinforcement Learning agent on the game of Tic Tac Toe (perhaps just in theory), where the agent should learn to play against a "human" opponent. In practice you may want a model of a human opponent.

In this case, the RL agent will be presented with a board state, it will take an action (to put its mark on an empty place in the grid) and either:

Win immediately, receiving a positive reward. It is common to use +1 in a game like Tic Tac Toe, so I will assume that later.
Lose on opponent's turn, receiving a negative reward (assumed -1 later in the answer), as opponent makes a move that causes it to win. This is effectively "immediately" in terms of time steps, the agent does not get to act afterwards.
Receive zero reward, and a new board state that includes the opponent's move
Receive zero reward, and the game ends in a draw

In all cases, the opponent is considered part of the environment. That makes the opponent behaviour critical to the value function and choice of optimal play. Training versus different opponents can result in very different state values.

For training to be stable, the opponent should behave with the same probability of action choices for each interim state that it observes. That includes it behaving deterministically, even optimally, purely randomly or anything in-between provided the probability distribution is fixed.

With the above context, it is possible to give sound answers to your questions:

  In Tic Tac Toe what is the effect of starting state in the State and Action Value function?

Each state of the board, or each state/action pair if you want to track action values, should converge to a value, depending on the agent's estimated, expected result at the end of the episode. As there is only a single reward possible at the end of each game, this will vary between -1 and +1. If either the agent or the opponent can make mistakes at random, then non-zero values between -1 and +1 are possible.

  Does it converge to the same stable value for all starting states?

That depends on behaviour of the opponent. In the scenario you are working with, the agent may not learn to play optimally in general, instead it will learn to gain optimal results against the supplied opponent. If the opponent can make mistakes, then moves which take advantage of that fact will have higher values.

Without a detailed description of the opponent it is not possible to make many statements about the actual state values and action values.

Against a perfect opponent, with the RL going second, it should converge to state values which are all zero and action values which are all zero or -1 for moves which would be mistakes.

Against a completely random opponent, I would have to run it to be sure, but I would expect state values to have 3 different values, all slightly positive, depending if opponent chose middle, edge or corner cases - each of these would have slightly different chance of leading to a win for the agent going forward.

  Will the value functions change if the starting players are changed?

Due to the turn-based nature of the game, all the states observed would be different depending on who was the first player. When the agent goes first it will get to score the empty grid and action values of any position it would like to make a first mark in - it gets to see state after turn 0 on time step 1, after turn 2 on time step 2, after turn 4 on time step 3 etc. When the agent goes second it will get to see and evaluate the outpt of other turns - turn 1 at t=1, turn 3 at t=2, turn 5 at t=3 etc.

That means the sets of states and state/action pairs for each case (RL first or RL second) are disjoint, and you cannot ask if one agent has the same value for a specific state as the other agent - it simply won't know about the other agent's values.

If you train a single agent, sometimes starting first, sometimes starting second, the two sets of values never interact with each other directly - in an enumerated table, as per the question, this is not at all, but if an agent uses function approximation such as neural networks, then they can affect each other.


Equivalence between expected parameter increments in "Off-Policy Temporal-Difference Learning with Function Approximation"

First part is correct
\begin{align}
&\sum_{n=1}^{\infty} \alpha(1-\lambda)\lambda^{n-1} (\bar R_t^{(n)} - \theta^T \phi_t)\\
=& \alpha[\sum_{n=1}^{\infty} (1-\lambda)\lambda^{n-1} \bar R_t^{(n)} - \sum_{n=1}^{\infty} (1-\lambda)\lambda^{n-1} \theta^T \phi_t]
\end{align}
$\sum_{n=1}^{\infty} (1-\lambda)\lambda^{(n-1)}$ sums to $1$ so we have
\begin{equation}
\alpha[\sum_{n=1}^{\infty} (1-\lambda)\lambda^{n-1} \bar R_t^{(n)} - \theta^T \phi_t]
\end{equation}
For the second part it's enough to prove equivalence for any $n$ because result contains sum over $n$. If you have 2 sums $\sum x_n$, $\sum y_n$ then the sums will be equal if for any $n$, $x_n = y_n$.

For the third part, we are in state $s_t$ and we already took action $a_t$ so we have
\begin{align}
&E_b \{ \sum_{t=0}^{\infty} (\bar R_t^{(n)} - \theta^T\phi_t)\phi_t \rho_1\rho_2\cdots\rho_t\}\\
=& \sum_{t=0}^{\infty} E_b \{(\bar R_t^{(n)} - \theta^T\phi_t)\phi_t \rho_1\rho_2\cdots\rho_t\}\\
=& \sum_{t=0}^{\infty} E_b \{\phi_t \rho_1\rho_2\cdots \rho_t\} E_b \{(\bar R_t^{(n)} - \theta^T\phi_t)|s_t, a_t\}
\end{align}
that is because $\rho_i, i = 1, \ldots, t-1$ depends on $s_i, a_i$. Because of Markov property expectation over $\bar R_t^{(n)}$ doesn't depend on those state it only depends on $s_t, a_t$ so they are independent. We don't need to consider $\phi_t$ and $\rho_t$ in expectation over $\bar R_t^{(n)}$ either because, like I said, we are in state $s_t$ and we took $a_t$ so they are already decided they would be considered a constant. We can then split total expectation in part $E_b \{\phi_t \rho_1\rho_2\cdots \rho_t\}$ for getting to state $s_t$ and taking action $a_t$ and part $E_b \{(\bar R_t^{(n)} - \theta^T\phi_t)|s_t, a_t\}$ for expectation over $\bar R_t^{(n)}$ after we got to state $s_t$ and took action $a_t$.


How does this part of algorithm works?(K-means)

1_{c^(i) = j} means if c^(i) is equal to j the value is 1 and zero otherwise.

In summary, k-means try to solve Voronoi cells for each mean point, and then update mean of members of a cell and update Voronoi cells again. This step is repeated until there is no change in members of the cells.


How to reduce over-fitting on training set?

The problem of overfitting is given that your model is being too flexible with the training data. The approaches you could take will be:

Download pretrained models (VGG-16) and use transfer learning.
Increase the value of your dropout (e.g. from 0.25 to 0.50).
Use data augmentation for your images.
Reduce the number of fully connected layers.


Can we get the inverse of the function that a neural network represents?

Mathematical Exploration

let $\Theta^+$ be the pseudo-inverse of $\Theta$.

Recall, that if a vector $\boldsymbol v \in R(\Theta)$ (ie in the row space) then $\boldsymbol v = \Theta^+\Theta\boldsymbol v$. That is, so long as we select a vector that is in the rowspace of $\Theta$ then we can reconstruct it with full fidelity using the pseudo inverse. Thus, if any of the images happen to be linear combinations of the rows of $\Theta$ then we can reconstruct it.

To be more specific. let $f(\boldsymbol x)$ have a pseudo-inverse $f^+(\boldsymbol x)$ defined as you have. If we restrict our domain such that $\boldsymbol x \in C(\Theta^T)$ (column space of the transpose) then $f^+= f^{-1}_{res}$.

That is, under our domain restriction the pseudo inverse becomes a true inverse.

An Extrapolation

It would then seem that so long as we are under such domain restrictions then we could define a pseudo inverse for a general NN. Though, it might be possible that some NNs don't have any restriction that admits an inverse. Maybe, there is some way to regularize the parameters such that this is possible. NNs with ReLU wouldn't admit such an inverse since ReLU loses information on negative values. Leaky Relu might work.

Further Investigation

Finally, this presents a zone for further study. Some questions to answer might be:

Is it possible for optimized parameters to contain non-trivial examples in their row-space?
If so, under what conditions is this possible?
Are the examples in any way represented in the row space?
Is there some way to regularize a NN such that it admits an inverse over some desired restriction?
Under what conditions is invertibility useful?


One LSTM layer should be enough unless you have lots of data. The same thing goes for the number of nodes in the layer. Start small first so 5 to 10 nodes and increment it until the performance is reasonable.
Once you have a model working you can apply regularization if you think it will improve performance by reducing overfitting of the training data. You can check this by looking at the learning curves or compring the error on the validation and test sets.
In my experiments I've used the L1 and L2 regularizers along with dropout. These can all be mixed together in fact using both L1 and L2 at the same time is called the ElasticNet.
I tend to apply the regularizers on the kernel_regularizer because this affects the weights for the inputs. Basically feature selection.
The value for the L1 and L2 can start with the default (for tensorflow) of 0.01 and change it as you see fit or read what other research papers have done.
Dropout can start at 0.1 then increment it until there is no performance gain. This is basically a percentage so 0.1 would remove about 10% of your nodes.
Finding the best regularizer is the same as any other hyperparameter optimization which is mostly trial and error.


Could humans hurt a conscious or sentient AI?

The article Children Beating Up Robot Inspires New Escape Maneuver System is based on two research papers about an experiment in a Japanese mall that led to unsupervised children attacking robots. The research paper you're interested in is Escaping from Children’s Abuse of Social Robots.

In that research paper, researchers were able to program the robots to follow a planning simulation to reduce the probability of abuse by children. If it detects children, the robot is programmed to retreat into a crowd of adults (who can then discipline the children if needed). This happened because the researchers saw that it was only children who were beating up the robots in the mall in question.

They discuss trying out other options though:

  In this work the robot’s strategy to prevent abuse was to “escape”, i.e. move to a location where it is less likely abuse will occur. One could ask why the robot cannot overcome the abuse. In our preliminary trials we have tried several approaches, but we found that it is very difficult for the robot to persuade children not to abuse it. For example, we changed the robot’s wordings in many ways, using strong words, emotional or polite expressions, but none of them were successful. One partially successful strategy was the robot ‘physically’ pushing children. When its way was blocked, it would just try to keep going and behave as if it will collide into children and force its way through (under careful monitoring from a human operator). We observed that children at first accepted the robot’s requests and obeyed them; but, very soon they learned that they are stronger than the robot so they can win if they push, and also that they can stop it by pushing the bumper switch (attached on the robot for safety). After realizing that, they just continued with the abusive behavior. Obviously having a stronger robot would present a problem for safety and social acceptance so dealing with such abusive situations remains difficult.

But let's interrogate your question further:

  If conscious AI is possible and is wide spread, wouldn't it be easy for someone who knows what they are doing to torture AI?

Why would you consider such torture to be wrong? After all, one could argue that the machine won't really 'experience' pain if you torture it...so it should be morally okay to torture the machine then. It may be respond as if it is in pain, but it's dubious whether the ability to simulate an emotional state such as "being in pain" is equivalent to actually being in that emotional state. See the question Is the simulation of emotional states equivalent to actually experiencing emotion? for more discussion on this topic.

You can make such an argument, but it won't really work on an emotional level because most humans would feel empathy towards the machine. It may be hard to justify it logically (and it may be based on humans' tendencies to engage in anthropomorphism), but we feel this empathy. It's this empathy that caused you to ask this question in the first place, caused researchers to figure out how to protect a robot from being beaten up, enabled police officers to arrest a drunken Japanese man for beating up a SoftBank robot, and made many humans upset over the destruction of hitchBOT. And that's how AI abuse would be avoided - human empathy. If most humans care about the welfare of machines, they'll make it a priority to stop those few humans who are able and willing to abuse the machines.

EDIT: The OP has edited his question to clarify that he is talking about software, and not about robots. For robots, you can rely on anthropomorphism to produce some level of sympathy, but it's hard to sympathize with raw lines of code.

You're not going to stop abuse of algorithms. Put it frankly, since the algorithms aren't like us, we aren't going to extend the same sort of empathy that we would to robots. Even chatbots are kinda iffy. If you could get people to sympathize with lines of code though (possibly by making a convincing simulation of emotion and sapience), then the above answer applies - humans anthropomorphize the machine and will come up with countermeasures. We aren't that level yet, so "stopping AI abuse" will be a low priority.

Still, some failsafes could be programmed in to limit the damage of abuse, as detailed in this thread on chatbot abuse - making the bot respond in a boring manner to make the abuser feel bored and move onto the next target, responding back to the abuser in a "battle of wits", or even just blocking the abusers from using the service.

These failsafes are cold comfort to those that want to prevent abuse, not respond to it.

Also...an abuser can happily learn how to program an AI to then abuse to his/her heart's content. Nothing can be done to stop that, and any possible measures to stop said abuse (such as monitoring every human being to make sure they don't program an AI to abuse) will probably cause more damage than it'd solve.


Which features of a data set can be used for market campaigning using propensity scores?

The problem you are examining is called feature selection. There are many different techniques, but they fall broadly into three categories:

Filter approaches determine which features have high information content. A common approach is to score them based on their information gain.
Wrapper approaches score subsets of the features, using similar measurements. This is slower (since there are many subsets), but may yield better performance.
Embedded approaches use machine learning algorithms that can dynamically select features. For example, building a C4.5 decision tree learner on a dataset, and then selecting just the features that actually appear in the tree, yields a set of features similar to those found by information gain.


Pose estimation using CNNs on Point clouds

The answer is yes this is possible and here are the papers where they do almost exactly the same project you are describing above. Although none of the bellow combine gazebo, single point/single shot, 6D-pose and CNNs. In order to use synthetic data to train a model that works on real data.

Pose Estimation by Key Points Registration in Point Cloud
 (2019) By Weiyi ZHANG, Chenkun QI This paper uses gazebo to test validate the model they made.
Dex-Net 2.0: Deep Learning to Plan Robust Grasps with Synthetic Point Clouds and Analytic Grasp Metrics (2017) by Jeffrey Mahler, Jacky Liang, Sherdil Niyaz, Michael Laskey, Richard Doan, Xinyu Liu, Juan Aparicio Ojea, Ken Goldberg
Real-Time Seamless Single Shot 6D Object Pose Prediction (2018) by Bugra Tekin, Sudipta N. Sinha, Pascal Fua
This paper sounds like exactly what you want to do.
SSD-6D: Making RGB-Based 3D Detection and 6D Pose Estimation Great Again (2017) by Wadim Kehl, Fabian Manhardt, Federico Tombari, Slobodan Ilic, Nassir Navab
This paper is also referenced by them.

The model will be able to be trained but how effect a model trained on the synthetic data will be able to properly function on real data will be the challenge.


What kind of simulated environment is complex enough to develop a general AI?

I think this is one of the best AGI related questions I've see in this forum.

I will skip all thematic about "what is an AGI", "simulation game", ... These topics have been discussed during decades and nowadays they are, in my opinion, a dead end.

Thus, I can only answer with my personal experience:

It is a basic theorem in computing that any number of dimensions, including temporal one, in a finite size space, can be reduced to 1D.

However, in practical examples, the 1D representation becomes hard to analyze and visualize. It is more practical work with graphs, that can be seen as an intermediate between 1D and 2D. Graphs allows representation of all necessary facts and relations.

By example, if we try to develop an AGI able to work in the area of mathematics, any expression (that humans we write in a 2D representation with rationals, subscripts, integrals, ...) can be represented as 1D (as an expression written in a program source) but this 1D must be parsed to reach the graph that can be analyzed or executed. Thus, the graph that results after the parsing of the expression is the most practical representation.

Another example, if we want an agent that travels across a 3D world, this world can be seen as an empty space with objects that have some properties. Again, after the initial stage of scene analysis and object recognition (the equivalent to the parser in previous example), we reach a graph.

Thus, to really work in the area of AGI, I suggest skip the problems of scene analysis, object recognition, speech recognition (Narrow AI), and work directly over the representative graphs.


How to formalize learning in terms of information theory?

In short: It is easy to quantify information, but it is not easy to quantify its usefulness

I'm not sure how exactly you are looking to formalise your experiment, but it might be helpful to consider these points:

There is no such thing as an absolute measure of information. The amount of information contained in some dataset is dependent on the underlying assumptions that are made when interpreting it, and therefore, the quantity of information conveyed is also dependent on the encoder/decoder (for example, a neural network). See the Wikipedia article on Kolmogorov Complexity.
Entropy is a useful measure of information content when you assume each sample is iid, but this would be a very bad assumption to make for natural images, since they are highly structured. For example, imagine an image with 50% black pixels and 50% white pixels that can be arranged in any configuration - not matter how you arrange them, wether it looks like random noise, a text paragraph, or a chequer board, the entropy value will be identical for each, even though our intuition tells us otherwise (see attached image). The discrepancy between our intuition and the entropy value arises because our intuition does not interpret the image through the "lens" of iid pixels, but rather, hierarchical receptive fields in the visual cortex (somewhat analogous to convolutional neural networks).
Calculating the entropy of pixel values in one image is somewhat useful, but calculating the "entropy" of a set of images would not be useful, because each image as a whole is treated as if it were a unique arbitrary symbol. I assume this is what you meant by "the information size of all datasets"
KL-divergence is a distance function that is often used to compare two distributions. Intuitively, it represents the redundant bits generated by a non-ideal compression program that assumes an incorrect data distribution. However, KL-divergence between two natural images will not give you a particularly meaningful result.

If I am not mistaken, you want to find some information metric that will enable you to pick the smallest number of the most optimal images for training and get a good test score with the network. Is that correct? It is an interesting idea. However, in order to define such a metric, we might have to know in advance what features of an image are the most significant for classification, which in some ways defeats the point of using machine learning in the first place, where non-obvious and "hidden" features are exploited.


What happens with policy gradient methods if rewards are differentiable?

That's exactly the point of the Policy Gradient Theorem. Let's go through he proof of this theorem - it relies on our ability to "loop" the reward expression $J(\theta,s)$, expressing it through $J(\theta,s')$ in the next state:
$$J(\theta,s) = \mathbb{E}_{\tau\sim\pi_\theta}\left[ R(\tau) | s_0 = s\right]$$
$$\begin{align}
J(\theta,s) & = \sum_a\pi_\theta(a|s)\sum_{s',r}P(s',r|s,a)(r + J(\theta, s'))\\
& = \sum_aJ(\theta,a,s)
\end{align}
$$
Here, I've introduced the notation $J(\theta,a,s)$ to keep further derivation sane. Taking the gradient:
$$\begin{align}
\nabla_\theta J(\theta,s) = \sum_{a}\left(\vphantom{\sum_a}\right.&\nabla_\theta  \pi_\theta(a|s) \left(\sum_{s',r}P(s',r|s,a)(r + J(s',\theta))\right)  + \\
&+\pi_\theta(a|s) \nabla_\theta \sum_{s',r}P(s',r|s,a)(r + J(s',\theta)\left.\vphantom{\sum_a}\right)\end{align}
$$
With the first term in the sum we do the log trick:
$$
\frac{\nabla_\theta  \pi_\theta(a|s)}{\pi_\theta(a|s)} \left(\pi_\theta(a|s)\sum_{s',r}P(s',r|s,a)(r + J(s',\theta))\right) = J(\theta,a,s)\nabla_\theta\log\pi_\theta(a|s)
$$
And the second term simplifies to:
$$\pi_\theta(a|s) \nabla_\theta \sum_{s',r}P(s',r|s,a)(r + J(s',\theta)) =
\pi_\theta(a|s)  \sum_{s'}P(s'|s,a) \nabla_\theta J(s',\theta)
$$
The last equality is exactly where we loose the rewards $r$ - the gradient of the constant $r$ is zero, and we can sum over $r$ because of the transition probability normalization $\sum_{r}P(s',r|s,a) = P(s'|s,a)$.
So we've finally get the expression for the gradient:
$$\nabla_\theta J(\theta,s) = \sum_{a}\left(J(\theta,a,s)\nabla_\theta\log\pi_\theta(a|s) + \pi_\theta(a|s)  \sum_{s'}P(s'|s,a) \nabla_\theta J(s',\theta) \right)$$
The Policy Gradient Theorem proof goes on though a couple more steps: unroll the last expression, rewrite through the distribution over states, then convert back from summation to the expectation over trajectories -- going through all this in detail here would too long. While we've already passed the crucial point for your question - we've got rid of the gradient of the rewards.
Edit:
In response to your comment, let me just stress again that this expression is a statement of the Policy Gradient Theorem.
$$\nabla_\theta J(\theta) = \mathbb{E}_{\tau\sim\pi}\left[R(\tau)\sum\nabla_\theta\log \pi_\theta(a_t|s_t)\right]$$
The proof of Policy Gradient Theorem is pretty involved and certainly is not as simple as saying that $\nabla_\theta R(\tau) = 0$. Some authors abuse notation or cut corners when going through the proof of the theorem - for a reasonably strict exposition of the PG theorem I recommend Sutton and Barto, Chapter 13.
Another potential point of confusion is the notation $r(s_t,a_t,s_{t+1})$ that you've been using. In the most general MDP formulation rewards are random variables $r$. The probability of getting a reward $r$ and ending up in state $s_{t+1}$ is encoded in the transition probability $P(s_{t+1},r|s_t,a_t)$. (This covers the case of deterministic rewards by having a deterministic distribution over $r$ ). The derivation above uses this, most general, formulation of the MDP.


How does rotating an image and adding new 'rotated classes' prevent overfitting?

How can data augmentation reduce overfitting?

You write that you can already maybe see how data augmentation can help prevent overfitting in general, but it sounds a bit uncertain and it's still asked in the title of the question, so I'll address this first:

Generally, when we use Machine Learning for classification problems, we would ideally learn a classifier that can perform well on a population. An example of a population would be: the set of all handwritten characters in the entire world. Generally, we don't have that complete population available for training, we only have a (much smaller) training dataset. If a training set is large enough, it might be a good approximation of the true population we're interested in (a "dense sampling" of the space we're interested in), but it's still just that; an approximation.

We say that a learning algorithm is overfitting if it performs singificantly better on the training set than it is on the population (which we generally approximate again using a separate test set).

Now, data augmentation (like adding rotations / translations of images in the training set to the training set) can help combat overfitting because it bridges the gap between training set and population. The population (all handwritten characters in the entire world) will likely include characters at various offsets from the middle (e.g. translations) and at various rotations. So, data augmentation is simply adding more examples (and possibly more varied examples) to our training set, which importantly are considered to be a part of the population we're interested in. If, for example, the population we are interested in were only the set of all handwritten characters at a specific position in the image (e.g., centered), then augmenting the dataset by adding various translations would not help; we'd be adding instances that are outside the population we want to learn about.

Why doesn't adding extra classes for rotations cancel out augmentations?

There are two possible explanations I can come up with:

Maybe the "extra-class" rotations are different from the "data augmentation" rotations.

Here is the exact quote that's relevant from the paper:

  "To reduce the risk of overfitting, we performed data augmentation by randomly translating and rotating character images. We also created new classes through 90◦, 180◦ and 270◦ rotations of existing data."

That first sentence is not 100% clear in my opinion. I imagine the translations they use for data augmentation are relatively small (e.g. offsets of a few pixels), so maybe the rotations they use for data augmentation are also only "small" rotations (for example, between -10◦ and +10◦). The "larger" rotations (multiples of 90◦) described in the second sentence may then no longer be a part of the "data augmentation to reduce the risk of overfitting" in the first sentence; they're simply parts of a different action performed to increase the number of classes in the dataset (and, I imagine, for each of these larger rotations they may again perform "smaller rotations" for data augmentations).

This explanation is kind of hypothetical though, it's not 100% clear from the paper exactly what they mean here in my opinion.

"Overfitting" can have a slightly different interpretation in the case of one-shot learning than in traditional learning.

Note that this paper is about "one-shot learning", where the goal is to be able to classify accurately after being presented only a single example ("one shot") of a never-before-seen class. In such one-shot problems, you could in some sense say that an algorithm might "overfit" to the "distribution of classes" if it can only perform one-shot learning well on a certain set of similar classes, but not on others.

For example, if you only train one-shot learning on a set of handwritten characters that are "upright" (close to 0 rotation), your algorithm might be able to perform well in terms of one-shot learning when presented with new classes (new handwritten characters) that are also upright, but might be incapable of proper one-shot learning when presented with new classes (new handwritten characters) that are upside-down.


Unexpected results when comparing a greedy policy to a DQN policy

Your problems appear to derive from a non-Markov state description. In brief, the agent has no way to ever learn that "heavy jobs will make a server unavailable for longer" and this is further compounded by arbitrary state transitions every 10 steps whilst the agent cannot track time.

Looking at the example from Sutton & Barto, you should note that they took care to model a valid MDP. Servers become available at random on each time step, and there is no hidden state. In your case you have three sources of hidden data that affects state evolution systematically. If an agent had some data about these then it might be able to use to optimise choices better:

Servers in use due to tasks assigned by the agent return deterministically n steps after the action that assigned them. The agents inability to track this is likely to be your largest problem - there is no data flow in RL that will allow the agent to associate the heavier jobs or slower servers with making a server unavailable for longer, so it never "sees" the clash of resource management that you want it to resolve.
Every 10 timesteps there is an arbitrary change to server availability. This is a problem because it is entirely predictable on which time steps it can occur, but the agent does not know the current timestep.
You are driving this from a dataset, not randomly, so the impact on this will vary depending on how the dataset evolves over time. A particularly bad case here would be if the dataset represented a "working day" so that there were clear timezones when availability followed different patterns. The agent has no data input in the state in order to associate patterns of use (such as the time of day), so the environment either becomes an online learning problem (agent must continuously learn and adapt to new patterns as they arise), or it must come up with a strategy that works in some average over all possible patterns.

In addition I can see a possible secondary effect, an "exploit" in the simulation, that may have a noticeable effect depending on how often specific servers drop out of the pool. It would appear if an agent assigns a task to a server, that you have no mechanism to unassign that task should the server drop out. So an aggressive agent that assigns greedily to the best available servers will get extra "free" time on the high capacity servers if it always claims them. As the agent doesn't know when the drop outs could happen, this effect competes with the average of leaving servers available just in case a heavy task arrives.

How to fix it? It depends on how much of your simulation is fixed by your requirements. You can either adjust the simulation to match your current state representation, or you can change the state representation to capture more system data from the simulation.

Probably the simplest state change would be to expand the list of servers to always include all servers, and for each unavailable server to have a "ticker" to show how many time steps before it becomes available. To make the problem smaller, you could maybe just track 1-10 ticks and have a combined state for (>10), as that will expose enough of the key state information that the agent can make decisions about pushing easy tasks into medium or low capacity servers. This does not need to be done to the level server id if the servers truly are interchangeable otherwise. So instead of an array of number of free servers by type, consider that it expands to a table with number of free servers by type at one end, then a column of number of servers by type with 0.1s remaining until they are free, then a column for servers that still have 0.2s remaining etc etc


Concrete examples of unintentional adversarial AI behaviour

There is the case of the tesla accident where the car was in autopilot and crashed into a truck because it appears the vehicle mistook a lightly coloured truck for the sky, killing the driver: https://www.newscientist.com/article/2095740-tesla-driver-dies-in-first-fatal-autonomous-car-crash-in-us/

Having said that, it appears the car had been trying to tell the driver to pay attention: http://uk.reuters.com/article/us-tesla-crash-idUKKBN19A2XC


Understanding the update rule for the policy in the policy iteration algorithm

A policy can be stochastic or deterministic. A deterministic policy is a function of the form $\pi_{\text{deterministic}}: S \rightarrow A$, that is, a function from the set of states to the set of actions. A stochastic policy is a map of the form $\pi_{\text{stochastic}} : S \rightarrow P(A)$, where $P(A)$ is a set of probability distributions ($P(A) = \{ p_{s_1}(A), p_{s_2}(A), \dots, p_{s_{|S|}}(A) \}$, where $p_{s_i}(A)$ is a probability distribution over the set of actions $A$ for the state $s_i$ and $|S|$ is the size of the set of states of the environment) over the set of actions $A$. A deterministic policy can be interpreted as a stochastic policy that gives the probability of $1$ to one of the available actions (and $0$ to the remaining actions), for each state.

In the case of value iteration (VI) and policy iteration (PI), the policy is deterministic, both in the policy evaluation (PE) or policy improvement (PI) steps.

In the PE step, for a specific state $s$ (inside the for loop), you use $\pi(s)$, that is, you assume that the action taken in the specific state $s$ is the greedy action, because of the $\text{argmax}$ in the PI, according to the current policy. However, in general, $\pi_k(s_i) \neq \pi_k(s_j)$, for $i \neq j$, where $k$ is the current iteration step (of PE and PI).

The update rule

$$\pi_{k+1}(s) \leftarrow arg max_a \sum_{s'}p(s' \mid s, a)[r(s, a, s') + \gamma v_k(s')]$$

computes the action that is expected to give the highest return, given the current and fixed value function $(v_k$). Have a look at the definition of expectation for discrete random variables: it is defined as a weighted sum (like in the update rule above, where the weights are $p(s' \mid s, a)$).

Value iteration is a shorter version of policy iteration. In VI, rather than performing a PI step for each state of the environment, when performing PE, the action that is expected to give the highest return is chosen. In VI, the policy is updated only once and at the end of policy evaluation. In PI, you alternate between PE and PI, and, at each PI, you update the policy.


Is superintelligence a function of strength or a category?

I’ll have a stab at this.

Cognitive performance in narrow domains is determined by competency, efficiency and speed. Take calculating numbers, extremely narrow domain but compared to humans the ability of a calculator to calculate numbers exceeds normal human performance, it is much competent in terms of speed. In a bit broader domain, AlphaGo has defeated Go players, which is more difficult than chess, and requires intuition. In fact, there is an instance where the AlphaGo makes a long-term move that was previously unimagined. In all domains however Humans are well rounded, therefore Human Intelligence is called general intelligence. An AlphaGo or Calculator cannot speak eloquently or make music, but AIs are gaining pace in these areas too.

I agree with @nbro that Bostrom wants to keep the interpretation of Superintelligence open. But if there is a rough category, these are-

ANI- Artificial Narrow Intelligence
AGI- Artificial General Intelligence: Where the AI’s performance is at par with humans. After AGI, it quickly takes off to SI.
SI- Superintelligence: Superintelligence is beyond our imagination, we have not figured out yet what will a SI do, think or want.

While these categories are discrete, the functions of strength are not. I’d say they are rather discrete to continuous, because if you look at the computing power plots that follow Moore’s Law, a similar exponential graph can be drawn for AI’s performance towards general intelligence. In that graph, it seems the AI’s performance starts with discrete performance points, and then as it takes off, it becomes continuous.

This is why the term Singularity is often associated with Superintelligence. I hope this answers your question.


Is this learning rate schedule increasing the learning rate?

The higher (or smaller) the learning rate, the higher (or, respectively, smaller) the contribution of the gradient of the objective function, with respect to the parameters of the model, to the new parameters of the model. Therefore, if you progressively increase (or decrease) the learning rate, then you will accelerate (or, respectively, slow down) the learning process, so later training examples have higher (or, respectively, smaller) influence on the parameters of the model.

In your example, the function warmup_lr_scheduler returns an object of class LambdaLR, initialized with a certain optimizer and the function f, which is defined as

def f(x):
    if x >= warmup_iters:
        return 1
    alpha = float(x) / warmup_iters
    return warmup_factor * (1 - alpha) + alpha

The documentation of torch.optim.lr_scheduler.LambdaLR says that the function f should compute a multiplicative factor given an integer parameter epoch, so x is a training epoch. If the epoch x is greater than or equal to warmup_iters, then 1 is returned, but anything multiplied by 1 is itself, so, when the epoch x is greater than a threshold, warmup_iters (e.g. 1000), then the initial learning rate is unaffected. However, when x < warmup_iters, the multiplicative factor is given by

alpha = float(x) / warmup_iters
warmup_factor * (1 - alpha) + alpha

which is a function of the epoch x. The higher the epoch x, the higher the value of alpha, so the smaller (1 - alpha) and warmup_factor * (1 - alpha). Note that float(x) / warmup_iters will never be greater than 1 because x is never greater than warmup_iters. So, effectively, as the epoch increases, warmup_factor * (1 - alpha) tends to 0 and alpha tends to 1.

The learning rate can only increase if you multiply it with a constant greater than 1. However, this can only happen if warmup_factor > 1. You can verify this by solving the inequality warmup_factor * (1 - alpha) + alpha > 1.

To conclude, the initial learning rate is not being increased, but the learning process starts with a smaller learning rate than the given learning rate, for a warmup_iters epochs, then, after warmup_iters epochs, it uses the initially given learning rate (e.g. 0.002).


What career paths should be avoided with the growth in AI?

This has been studied pretty well academically. The most common study instrument is a survey of the opinions of AI researchers. The other mechanism is subjective assessment by business analysts about which sectors are most likely to be automated, using two criteria: ease of automation, and potential profit from automation (based on the size of the workforce). I have a fairly detailed discussion of some sources below.

The upshot is: any job that requires little training is probably a bad idea. Additionally, any job that requires directly caring for or educating another person, or involves the production of a fine-arts product is probably a good idea. In between, jobs like sales or administrative assistants are likely to become more "winner takes all": low-level sales jobs are likely to disappear, but high level ones that involve a lot of human contact, strong social skills, negotiation, and persuasion are likely to stay. In general, jobs that are plentiful, routine, and high salary are likely to be fully or partially automated first.

Sources:

This was discussed informally at AAAI a few years ago (2015?). One researcher's daughter was considering different career paths. The conclusion that was reached (half-jokingly) was that AI-researcher was the best bet. Everything else we could name, someone was working on automating.

More concretely, there are a number of recent papers and reports. A good starting place is the 2017 PWC report. Section 4.2 covers the different sectors at risk, and 4.3 provides a rationale based on what employees typically do in each sector. The report suggests that men without a high school diploma will be most readily affected, with about 3-4 times the rate of automation as compared to college graduates. The specific sectors at greatest risk are wholesale & retail trade (essentially: sales people), manufacturing, administrative support, transportation & storage, public administration and defense, financial & insurance, water, sewage & waste management, and electricity and gas supply.  All these sectors were estimated at being 30% or more automatable. The safest areas were education, and domestic assistants (e.g. live-in caretakers).

The PWC report is also mostly in line with the 2013 paper by Frey & Osborne. This paper proposed a 9 factor model (summarized in Table III), and then evaluated hundreds of occupations by their probability of automation. Jobs requiring a fine-arts component were very unlikely to be automated. Additionally, jobs that did not take place within cramped spaces were unlikely to be automated. Having a large component of caring for others, persuading others, negotiating with others, or social perception, reduced the risk of automation. Originality requirements also quickly reduced risk. Requirements for manual dexterity did not substantially reduce the risk, and actually increased it on average. I'm pretty sure there's a more recent followup paper, but I can't find it just now.

The 2016 Obama Administration also released a report summarizing the scope of the threat of automation. The main conclusions were that those with limited education, and jobs requiring a low amount of skill, were at greatest risk. They also pointed out that around 6% of US jobs are lost each quarter already though (and simply replaced by new jobs), so the proposed rate of job loss (up to ~50% over ~15 years) represents about a 15% increase in the rate of churn, which seems adaptable.


How is iterative deepening A* better than A*?

A* is a best-first search algorithm, which means that it is an algorithm that uses both "past knowledge", gathered while exploring the search space, denoted by $g(n)$, and an admissible heuristic function, denoted by $h(n)$, which estimates the distance to the goal node, for each node $n$. There are other best-first search algorithms, which differ only in the definition of their "evaluation function", denoted by $f(n)$. For example, the evaluation function of A* is $f(n) = g(n) + h(n)$, where $h$ is admissible.

A* is optimal, that is, it finds the optimal path between the starting and goal nodes or states. The optimality of A* is due to the use of an admissible heuristic function, which is a heuristic function which always underestimates the distance to the goal. A* is also complete, that is, it eventually finds this optimal path. However, the problem with A*, in many real-world situations, is that it has an exponential space complexity; more specifically, its space complexity is $\mathcal{O}(b^m)$, where $b$ is the (maximum) branching factor and $m$ is the maximum depth of the search tree. It also has a time complexity of $\mathcal{O}(b^m)$, but, in practice, it tends to find the solutions quite "fast" (for relatively small search spaces).

IDA* combines A* and IDDFS (or IDS). It does it "well", so it gets the advantages of both algorithms. It can be thought of as the IDDFS which uses, instead of the depth, the evaluation function $f(n) = g(n) + h(n)$ as the "cost threshold" or "cutoff". In the IDA* algorithm, a child $c$ of a node $n$ is added to the frontier (or fringe or border) if $f(c) < T$. This threshold $T$ is, at the beginning of the algorithm, the estimate of the distance to the goal from the starting node $s$, that is, $T = h(s)$. $T$ increases at each iteration of the algorithm (See the pseudocode of the IDA* algorithm for the details).

IDA* is also complete and optimal, but, as opposed to A*, it has a polynomial space complexity, more specifically, $\mathcal{O}(bd)$, where $b$ is the (maximum) branching factor and $d$ is the maximum depth fo the tree. IDA* still has an exponential time complexity of A*.

To conclude, IDA* has a better memory usage than A*. As in A* and unlike IDDFS, it concentrates on exploring the most promising nodes, and thus does not go to the same depth everywhere in the search tree (whereas ordinary IDDFS does). A* can be thought of as a dynamic programming algorithm. IDA* often ends up exploring the same nodes many times (as IDDFS), but, asymptotically, both A* and IDA* have the same exponential time complexity, that is, $\mathcal{O}(b^m)$.

So, which one is the best one? A* becomes impractical when the search space is huge, because of the memory constraints. So, in those cases, IDA* is definitely more appropriate. In general, IDA* is one of the very best optimal state space
search techniques around. However, A* is conceptually simpler than IDA*. As a consequence, in practice, A* may be easier to implement than IDA*, but, in real-world scenarios, this is not really a problem, as they are both relatively easy to implement (anyway).


Can non-sequential deep learning models outperform sequential models in time series forecasting?

You are right CNN based models can outperform RNN. You can take a look at this paper where they compared different RNN models with TCN (temporal convolutional networks) on different sequence modeling tasks. Even though there are no big differences in terms of results there are some nice properties that CNN based models offers such as: parallelism, stable gradients and low training memory footprint. In addition to CNN based models there are also attention based models (you might want to take a look at the transformer)


Given an axis-angle rotation vector, how can I find the unit rotation axis and angle?

Given the axis-angle rotation vector $\Theta = (2, 2, 0)$, you can find the unit vector in the same direction by diving by the norm (or length) of $\Theta$, denoted by $\|\Theta\| = \sqrt{2^2 + 2^2 + 0^2} = \sqrt{8} = 2\sqrt{2}$. Therefore, the unit vector in the direction of $\Theta$ is $k= \Theta/\|\Theta\| = (1/\sqrt{2}, 1/\sqrt{2}, 0)$, which should be the axis of rotation that you're looking for. The angle should just be the norm of $\Theta$, that is, $\theta = \|\Theta\| = 2\sqrt{2}$. Note that $k \theta$ gives you your original vector $\Theta$.