text:
What are the pros and cons of sparse and dense rewards in reinforcement learning?
From what I understand, if the rewards are sparse the agent will have to explore more to get rewards and learn the optimal policy, whereas if the rewards are dense in time, the agent is quickly guided towards its learning goal.
Are the above thoughts correct, and are there any other pros and cons of the two contrasting settings? On a side-note, I feel that the inability to specify rewards that are dense in time is what makes imitation learning useful.

What are the pros and cons of sparse and dense rewards in reinforcement learning?

It is unusual to refer to this difference as "pros and cons" because that term is often used to make comparisons between difference choices. Assuming you have a specific problem to solve, then whether or not the rewards are naturally sparse or dense is not a choice. You cannot say "I want to solve MountainCar, I will use a dense reward setting", because MountainCar has (relatively, for a starting problem) sparse rewards. You can only say "I won't attempt MountainCar, it is too difficult".
In short however, your assessment is correct:

if the rewards are sparse the agent will have to explore more to get rewards and learn the optimal policy, whereas if the rewards are dense in time, the agent is quickly guided towards its learning goal

There is not really any other difference at the top level. Essentially, sparser rewards make for a harder problem to solve. All RL algorithms can cope with sparse rewards to some degree, the whole concept of returns and value backup is designed to deal with sparseness at a theoretical level. In practical terms however, it may take some algorithms an unreasonable amount of time to determine a good policy beyond certain levels of sparseness.

On a side-note, I feel that the inability to specify rewards that are dense in time is what makes imitation learning useful.

Imitation learning is one of many techniques available to work around or deal with problems that have sparse reward structure. Others include:

Reward shaping, which attempts to convert a sparse reward scheme to a dense one using domain knowledge of the researcher.

Eligibility traces, which back up individual TD errors across multiple time steps.

Prioritised sweeping, which focuses updates on "surprising" reward data.

Action selection planning algorithms that look ahead from the current state.

"Curiousity" driven reinforcement learning that guides exploration to new state spaces independently of any reward signal.

Could you point me in the direction of interesting papers related to the techniques you've mentioned, besides imitation learning? That'd be helpful!

@cogito_ai: Not really, most are broad topics and you are better off using a web search to find tutorials. For eligibility traces and planning, Sutton & Barto has a good chapter on each. It also has a section on prioritised sweeping in planning context (DQN may also use it to select replay memory). Here's something on cuirosity: https://towardsdatascience.com/curiosity-driven-learning-made-easy-part-i-d3e5a2263359 - there were a few papers on that in 2018


text:
What is the surrogate loss function in imitation learning, and how is it different from the true cost?
I've been reading A Reduction of Imitation Learning and Structured Prediction
to No-Regret Online Learning lately, and I can't understand what they mean by the surrogate loss function.
Some relevant notation from the paper -

$d_\pi$ = average distribution of states if we follow policy $\pi$ for $T$ timesteps
$C(s,a)$ = the expected immediate cost of performing action a in state s for the task we are considering (assume $C$ is bounded in [0,1]
$C_\pi(s) = \mathbb{E}_{a\sim\pi(s)}[C(s,a)]$ is the expected immediate cost of $π$ in $s$.
$J(π) = T\mathbb{E}_{s\sim d_\pi}[C_\pi(s)]$ is the total cost of executing policy $\pi$ for $T$ timesteps

In imitation learning, we may not necessarily know or observe true costs $C(s,a)$ for the particular task. Instead, we observe expert demonstrations and seek to bound $J(π)$
for any cost function $C$ based on how well $π$ mimics the expert’s policy $π^{*}$. Denote $l$ the observed surrogate loss function we minimize instead of $C$. For instance, $l(s,π)$ may be the expected 0-1 loss of $π$ with respect to $π^{*}$ in state $s$, or a squared/hinge loss of $π$ with respect to $π^{*}$ in $s$. Importantly, in many instances, $C$ and $l$ may be the same function – for instance, if we are interested in optimizing the learner’s ability to predict the actions chosen by an expert.

I don't understand how exactly the surrogate loss is different from the true costs, and what are the possible cases in which both are the same. It'd be great if someone could throw some light on this. Thank you!

A surrogate loss is a loss than you use "instead of", "in place of", "as a proxy for" or "as a substitute for" another loss, which is typically the "true" loss.
Surrogate losses are actually common in machine learning (although almost nobody realizes that they are surrogate losses). For example, the empirical risk (which the mean squared error is an instance of) is a surrogate for the expected risk, which is incomputable in almost all cases, given that you do not know the underlying probability distribution. See An Overview of Statistical Learning Theory by V. N. Vapnik for more details. In fact, discussions on generalization arise because of this issue, i.e. you use surrogate losses rather than true losses.
The term "surrogate" is also used in conjunction with the term "model", i.e. "surrogate model", for example, in the context of Bayesian optimization, where a Gaussian process is the surrogate model for the unknown model/function that you want to know about, i.e. you use the Gaussian process to approximate the unknown function/model.
Regarding the excerpt you are quoting and your specific concerns, although I didn't read the paper and I am not an expert in imitation learning, let me try to explain what I understand from this excerpt. Essentially, in imitation learning, you use the expert's policy $\pi^*$ to train the agent, rather than letting him just explore and exploit the environment. So, what you know is $\pi^*$ and you can calculate the "loss" between $\pi^*$ and $\pi$ (the current agent's policy), denoted by $l$. However, this loss $l$ that you calculate is not necessarily the "true" loss (i.e. it is a surrogate loss), given that our goal is not really to imitate the "expert" but to learn an optimal policy to behave in the environment. If the goal was to just imitate the "expert", then $C$ and $l$ would coincide, because, in that case, $l$ would represent the "discrepancy" or "loss" between $\pi$ and the expert's policy $\pi^*$.

source: Stack Exchange

license: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/4.0/

sort: votes


text:
Reinforcement learning with action consisting of two discrete values
I'm new to reinforcement learning. I have a problem where an action is composed of an order (rod with a required length) and an item from a warehouse (an existing rod with a certain length, which will be cut to the desired length and the remainder put back to the warehouse).
I imagine my state as two lists of a defined size: orders and warehouse, and my action as an index from the first list and an index from the second list. However, I have only worked with environments where it was only possible to pick single action and I'm not sure how to deal with two indexes. I'm not sure how DQN architecture should look like to give me such action.
Can anyone validate my general idea and help me find a solution? Or maybe just point me to some papers where similar problems are described?

You would still be picking a single action. Your action space is now $\mathcal{A} = \mathcal{O} \times \mathcal{I}$ where I've chosen $\mathcal{O}$ to be the set of possible orders from your problem and $\mathcal{I}$ to be the set of possible items.
Provided both of these sets are finite, then you should still be able to approach this problem with DQN. Theoretically, this should be easy to see, as any element from $\mathcal{A}$ is still a single element it just happens that this element is now a tuple.
From a programming point of view, let's consider the simple example of cartpole, where the possible actions are left and right. Your $Q$-function obviously won't know the meanings of 'left' and 'right', you just assign it to an element of a vector, i.e. your $Q$-function would output a vector in $\mathbb{R}^2$ with e.g. the first element corresponding to the score for 'left' and the second element corresponding to the score for 'right'. This is still the case in your problem formulation, you will just have a $Q$-function that outputs a vector in $\mathbb{R}^d$ where $d = |\mathcal{A}|$ - you would just have to make sure you know which element corresponds to which action.
Also, there is the possibility that this approach could leave you with a large dimensional vector output, which I imagine would probably mean you'd need more simulations to properly explore the action space.
Hope this helps.

all_licenses: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/4.0/


text:
Why would the learning rate curve go backwards?
I'm working on recognizing the numbers 3 and 7 using the MNIST data set. I'm using cnn_learner() function from fastai library.
When I plotted the learning rate, the curve started going backward after a certain value on X-axis. Can someone please explain what does it signify?

I have not used fastai library but this also happens on tensorboard when you have more than one training being recorded on the same plot.
Looking at the picture, I think this is a very special type of graph because for a single LR value you have 2 loss values associated. Put in other words, you have the same LR value for different loss values. My guess it that some time-dependent issue is messing things here.
Another intuition that may help to solve the issue is representing data differently. If you rotate the graph 90º left-wise you could see how the LR is evolving with different loss values. LR should be decreasing along with loss value, but in this case it is not like that either. So review how you are setting the LR too!
My list of to-check would be:

Check how you update LR according to the loss value
Check the LR recorder instance is only being used by one training at a time
Try plotting the value of LR (y) against your loss values (x)
Try plotting the value of LR (y) against the current epoch number (x)

Hope it helps

no of epochs I ran is 1, and I split the running rates between (1e-5,1e-4) during training


text:
What is the difference between vanilla policy gradient with a baseline as value function and advantage actor-critic?
What is the difference between vanilla policy gradient (VPG) with a baseline as value function and advantage actor-critic (A2C)?
By vanilla policy gradient I am specifically referring to spinning up's explanation of VPG.

The difference between Vanilla Policy Gradient (VPG) with a baseline as value function and Advantage Actor-Critic (A2C) is very similar to the difference between Monte Carlo Control and SARSA:

The value estimates used in updates for VPG are based on full sampled returns, calculated at the end of episodes.

The value estimates used in updates for A2C are based on temporal difference bootstrapped from e.g. a single step difference, and the Bellman function.

This leads to the following practical differences:

A2C can learn during an episode which can lead to faster refinements in policy than with VPG.

A2C can learn in continuing environments, whilst VPG cannot.

A2C relies on initially biased value estimates, so can take more tuning to find hyperparameters for the agent that allows for stable learning. Whilst VPG typically has higher variance and can require more samples to achieve the same degree of learning.

Thanks for your answer! What does "continuing environments" mean?

@lyeeke: It's another way of saying "non-episodic" i.e. the environment has no terminal states and keeps going with no natural break points.

It there anything inbetween? Like having this bootstrapped critic evaluation after every step but being able to adjust in the end of the episode if/when it turns out the bootstrapped value was wrong?

@hypers: You could use eligibility traces with the critic, it can be trained in almost any value-based way. Unfortunately you cannot easily go back and adjust the advice it gave to the actor in previous steps.

I see from this TF Actor Critic article (https://www.tensorflow.org/tutorials/reinforcement_learning/actor_critic) that A2C can also be trained in the end of the episode (as done in that tutorial).
So my reckoning is that A2C is not necessarily different from VPG by this criteria (when the training is happening).

If I understand correctly, Neil's answer is correct because VPG uses rollouts/trajectories in place of the traditional episodes. A rollout has a max length, so that it can either end when max length is reached, or when a terminal state is reached.
VPG learns at the end of each rollout, which can also be during an episode. correct me if im wrong!

Given the formula for the policy gradient with baseline:
$$ \nabla J(\theta) = \mathbb{E}_{a,s \sim \pi_\theta} \bigg[ \nabla \log \pi_\theta(a|s) \Big(R(s, a) - V_\phi(s) \Big) \bigg] $$
How do you compute the return $R(s,a)$ ?
If you use a simple Monte-Carlo estimate, i.e. $R = \sum_{t=t'}^{T} r_{t+1}$, then you get the "vpg with baseline" as it is called in the spinning up documentation. Note that in this case you have to rollout episode until it is finished, otherwise you can't compute the return !
If you use a one-step bootstrapped estimate, i.e. $ R(s,a) = r + V_\phi(s')$, then you would get the actor-critic setup, where we have an actor (the policy network) that selects actions to perform the rollout and a critic (the value network) that is used to compute the returns, i.e. it grades the performance. And since you are baseline-ing with the value function you actually get an advantage actor-critic. Note that now you can calculate the return without the episode being finished. Thus, you could step the environment for a few steps, then update the policy, and then continue stepping.
Its all about how you calculate the return.
As a side note: I really don't like the fact that people use "vanilla policy gradient" to mean that they are using a Monte-Carlo estimate for the return. In my opinion "vanilla" policy gradient means that you perform a "vanilla" update of the policy using the calculated gradient, i.e.:
$$ \theta_{new} = \theta - \alpha \nabla J(\theta).$$
Instead of a "vanilla" update you could update the weights using the natural gradient (TRPO) or you could perform multiple clipped updates (PPO) (see here for more). There are of course other types of policy gradient algorithms, but the idea is that once you have the gradient estimate you do not perform a simple update in the direction of the gradient, but instead do something more sophisticated with it.


text:
Why do DQNs tend to forget?
Why do DQNs tend to forget? Is it because when you feed highly correlated samples, your model (function approximation) doesn't give a general solution?
For example:

I use level 1 experiences, my model $p$ is fitted to learn how to play that level.

I go to level 2, my weights are updated and fitted to play level 2 meaning I don't know how to play level 1 again.

Please, do not ask the same question in different posts only because you have not yet received an answer. You already asked about ER here: https://ai.stackexchange.com/q/22694/2444. I am sure someone will answer that question.

This question is very related to https://ai.stackexchange.com/q/13289/2444, although I wouldn't say it's a duplicate because yours is specific to DQN.

You are referring to catastrophic forgetting which could be an issue in any neural net. More specifically for DQN refer to this article.

I also have a question, the issue is our replay memory size can’t be too large because of performance issues, too small and it’s irrelevant, so if we have a large space state with multiple tasks, even replay memory wouldn’t be able to help with the catastrophic forgetting, so what can be the solution?

@Chukwudi I'm not really sure, sorry.


text:
Is it common to have extreme policy's probabilities?
I have implemented several policy gradient algorithms (REINFORCE, A2C, and PPO) and am finding that the resultant policy's action probability distributions can be rather extreme. As a note, I have based my implementations on OpenAI's baselines. I've been using NNs as the function approximator followed by a Softmax layer. For example, with Cartpole I end up with action distributions like $[1.0,3e-17]$. I could understand this for a single action, potentially, but sequential trajectories end up having a probability of 1. I have been calculating the trajectory probability by $\prod_i \pi(a_i|s_i)$. Varying the learning rate changes how fast I arrive at this distribution, I have used learning rates of $[1e-6, 0.1]$. It seems to me that a trajectory's probability should never be 1.0 or 0.0 consistently, especially with a stochastic start. This also occurs for environments like LunarLander.
For the most part, the resulting policies are near-optimal solutions that pass the criteria for solving the environments set by OpenAI. Some random seeds are sub-optimal
I have been trying to identify a bug in my code, but I'm not sure what bug would be across all 3 algorithms and across environments.
Is it common to have such extreme policy's probabilities? Is there a common way to handle an update so the policy's probabilities do not end up so extreme? Any insight would be greatly appreciated!

Are the eventual policies near optimal, do they solve the Gym environments? E.g. for LunarLander do you get consistently ~200 reward?

For the most part, yes. Some random seeds are sub-optimal.

Your policy gradient algorithms appear to be working as intended. All standard MDPs have one or more deterministic optimal solutions, and those are the policies that solvers will converge to. Making any of these policies more random will often reduce their effectiveness, making them sub-optimal. So once consistently good actions are discovered, the learning process will reduce exploration naturally as a consequence of the gradients, much like a softmax classifier with a clean dataset.
There are some situations where a stochastic policy can be optimal, and you could check your implementations can find those:

A partially observable MDP (POMDP) where one or more key states requiring different optimal actions are indistinguishable to the agent. For example, the state could be available exits in a corridor trying to get the end in a small maze, where one location secretly (i.e. without the agent having any info in the state representation that the location is different) reverses all directions, so that progressing along it is not possible for a deterministic agent, but a random agent would eventually get through.

In opposing guessing games where a Nash equilibrium occurs for specific random policies. For example scissor, paper, stone game where the optimal policy in self-play should be to choose each option randomly with 1/3 chance.

The first example is probably easiest to set up a toy environment to show that your implementations can find stochastic solutions when needed. A concrete example of that kind of environment is in Sutton & Barto: Reinforcement Learning, An Introduction chapter 13, example 13.1 on page 323.
Setting up opposing agents in self-play is harder, but if you can get it to work and discover the Nash equilibrium point for the policies, it would be further proof that you have got something right.

authors: Олександр Семенов


text:
Are tabular reinforcement learning methods obsolete (or getting obsolete)?
While learning RL, I came across some problems where the Q-matrix that I need to make is very very large. I am not sure if it is ever practical. Then I research and came to this conclusion that using the tabular method is not the only way, in fact, it is a very less powerful tool as compared to other methods such as deep RL methods.
Am I correct in this understanding that with the increasing complexity of problems, tabular RL methods are getting obsolete?

Am I correct in this understanding that with the increasing complexity of problems, tabular RL methods are getting obsolete?

Individual problems don't get any more complex, but the scope of solvable environments increases due to research and discovery of better or more apt methods.
Using deep RL methods with large neural nets can be a lot less efficient for solving simple problems. So tabular methods still have their place there.
Practically, if your state/action space (number of states times number of actions) is small enough to fit a Q table in memory, and it is possible to visit all relevant state/action pairs multiple times in a relatively short time, then tabular methods offer guarantees of convergence that approximate methods cannot. So tabular approaches are often preferred if they are appropriate.
Many interesting, cutting edge problems that are relevant to AI, such as autonomous robots acting in the real world, do not fit the tabular approach. In that sense, the approach is "obsolete" in that it no longer provides challenging research topics for practical AI (there are still unanswered theoretical questions, such as proof of convergence for Monte Carlo control).
It is still worth understanding tabular value-based methods in detail, because they form the foundations of the more complex deep learning methods. In some sense they represent ideal solutions that deep RL tries to approximate, and the design of tabular solutions can be the inspiration for changes and adjustments to neural-network methods.

Not many people understand the convergence proof shown in neuro-dynamic programming. I'm not even sure the professors I had which worked on this area remembered much of it.


text:
How does the target network in double DQNs find the maximum Q value for each action?
I understand the fact that the neural network is used to take the states as inputs and it outputs the Q-value for state-action pairs. However, in order to compute this and update its weights, we need to calculate the maximum Q-value for the next state $s'$. In order to get that, in the DDQN case, we input that next state $s'$ in the target network.
What I'm not clear on is: how do we train this target network itself that will help us train the other NN? What is its cost function?

The loss function and method of training Double DQN are specified in the Double DQN paper: https://arxiv.org/pdf/1509.06461.pdf

Both in DQN and in DDQN, the target network starts as an exact copy of the Q-network, that has the same weights, layers, input and output dimensions, etc., as the Q-network.
The main idea of the DQN agent is that the Q-network predicts the Q-values of actions from a given state and selects the maximum of them and uses the mean squared error (MSE) as its cost/loss function. That is, it performs gradient descent steps on
$$\left(Y_{t}^{\mathrm{DQN}} -Q\left(s_t, a_t;\boldsymbol{\theta}\right)\right)^2,$$
where the target $Y_{t}^{\mathrm{DQN}}$ is defined (in the case of DQN) as
$$
Y_{t}^{\mathrm{DQN}} \equiv R_{t+1}+\gamma \max _{a} Q\left(S_{t+1}, a ; \boldsymbol{\theta}_{t}^{-}\right)
$$
$\boldsymbol{\theta}$ are the Q-network weights and $\boldsymbol{\theta^-}$ are the target network weights.
After a usually fixed number of timesteps, the target network updates its weights by copying the weights of the Q-network. So, basically, the target network never performs a feed-forward training phase and, thus, ignores a cost function.
In the case of DDQN, the target is defined as
$$
Y_{t}^{\text {DDQN}} \equiv R_{t+1}+\gamma Q\left(S_{t+1}, \underset{a}{\operatorname{argmax}} Q\left(S_{t+1}, a ; \boldsymbol{\theta}_{t}\right) ; \boldsymbol{\theta}_{t}^{-}\right)
$$
This target is used to decouple the selection of the action (i.e. the argmax part) from its evaluation (i.e. the computation of the Q value at the next state with this selected action), as stated the paper that introduced the DDQN)

The max operator in standard Q-learning and DQN, in (2) and (3), uses the same values both to select and to evaluate an action. This makes it more likely to select overestimated values, resulting in overoptimistic value estimates. To prevent this, we can decouple the selection from the evaluation


text:
Why is the policy loss the mean of $-Q(s, \mu(s))$ in the DDPG algorithm?
I am trying to implement the DDPG algorithm based on this paper.
The part that confuses me is the actor network's update.
I don't understand why the policy loss is simply the mean of $-Q(s, \mu(s))$, where $Q$ is the critic network and $\mu$ is the policy network.
How does one arrive at this?

This is not quite the loss that is stated in the paper.
For standard policy gradient methods the objective is to maximise $v_{\pi_\theta}(s_0)$ -- note that this is analogous to minimising $-v_{\pi_\theta}(s_0)$. This is for a stochastic policy. In DDPG the policy is now assumed to be deterministic.
In general, we can write
$$v_\pi(s) = \mathbb{E}_{a\sim\pi}[Q(s,a)]\;;$$
to see this note that
$$Q(s,a) = \mathbb{E}[G_t | S_t = s, A_t=a]\;;$$
so if we took expectation over this with respect to the distribution of $a$ we would get
$$\mathbb{E}_{a\sim\pi}[\mathbb{E}[G_t|S_t=s, A_t=a]] = \mathbb{E}[G_t|S_t=s] = v_\pi(s)\;.$$
However, if our policy is deterministic then $\pi(\cdot|s)$ is a point mass (a distribution which has probability 1 for a specific point and 0 everywhere else) for a certain action, so $\mathbb{E}_{a\sim\pi}[ Q(s,a)] = Q(s,a=\pi(s)) = v_\pi(s)$. Thus the objective is still to maximise $v_\pi(s)$ it is just that now we know the policy is deterministic we say we want to maximise $Q(s,a=\pi(s))$.
The policy gradient of this term was shown to be
\begin{align}
\nabla_\theta Q(s,a=\pi_\theta(s)) & \approx \mathbb{E}_{s \sim \mu}[\nabla_\theta Q(s,a=\pi_\theta(s))]\;; \\ & =  \mathbb{E}_{s\sim\mu}[\nabla_aQ(s,a=\pi(s)) \nabla_\theta \pi_\theta(s)]\;;
\end{align}
where if we put a minus at the front of this term then we would arrive at the loss from the paper. Intuitively this makes sense, you want to know how much the action-value function changes with respect to the parameter of the policy, but this would be difficult to directly calculate so you use the chain rule to see how much the action-value function changes with $a$ and in turn how much $a$ (i.e. our policy) changes with the parameter of the policy.
I realise I have changed notation from the paper you are reading so here $\pi$ is our policy as opposed to $\mu$ and here where I have used $\mu$ I take this to be the state distribution function.


text:
Can GANs be used to generate something other than images?
AFAIK, GANs are used for generating/synthesizing near-perfect human faces (deepfakes), gallery arts, etc., but can GANs be used to generate something other than images?

They can indeed. Although generally they are kept to images because at the moment, they are the best at that, but not the best in other areas that you might consider.
GANs can be used for audio generation, with many examples such as GANsynth and GAN voice generation. But each of these tasks are outperformed by other methods. With music generation, WaveNet is the best (last I checked, and it also performs very well at speech synthesis), and a more powerful model for voice generation is achieved through the use of a VAE.
This is only looking at one area that you could use GANs for, because in reality you could use them for any kind of generation if you wanted to, but at the moment the vast majority of the research into GANs is into image generation, and as such other areas do not compete with the current SOTA techniques, unless there's some big paper I've missed within the last few months.


text:
How exactly is $Pr(s \rightarrow x, k, \pi)$ deduced by "unrolling", in the proof of the policy gradient theorem?
In the proof of the policy gradient theorem in the RL book of Sutton and Barto (that I shamelessly paste here):

there is the "unrolling" step that is supposed to be immediately clear

With just elementary calculus and re-arranging of terms

Well, it's not. :) Can someone explain this step in more detail?
How exactly is $Pr(s \rightarrow x, k, \pi)$ deduced by "unrolling"?

The unrolling step is due to the fact you end up with an equation that you can keep expanding indefinitely.
Note that we start with calculating $\nabla v_\pi(s)$ and arrive at
$$\nabla v_\pi(s) = \sum_a\left[ \nabla \pi(a|s) q_\pi(s,a) + \pi(a|s) \sum_{s'}p(s'|s,a) \nabla v_\pi (s') \right]\;,$$
which contains a term for $\nabla v_\pi(s')$. This is a recursive relationship, similar to the bellman equation, so we can substitute in a term for $\nabla v_\pi(s')$ which will be a term similar just with $\nabla v_\pi(s'')$. As I mentioned, we can do this indefinitely which leads us to
$$\nabla v_\pi(s) = \sum_{x \in \mathcal{S}} \sum_{k=0}^\infty \mathbb{P}(s\rightarrow x, k, \pi) \sum_a \nabla \pi(a|x) q_\pi(x,a)\;.$$
We need the term $\sum_{x \in \mathcal{S}} \sum_{k=0}^\infty \mathbb{P}(s\rightarrow x, k, \pi)$ because we want to take an average over the state space, however due to unrolling there are many different $s_t$'s that we need to average over (this comes from the $s',s'',s''',...$ in the unrolling) so we also need to add the probability of transitioning from state $s$ to state $x$ in $k$ time steps, where we sum over an infinite horizon due to the repeated unrolling.
If you are wondering what happens to the terms $\pi(a|s)$ and $p(s'|s,a)$ terms and why they are not explicitly shown in this final form, it is because this is exactly what the $\mathbb{P}(s\rightarrow x, k, \pi)$ represents. The average over all possible states accounts for the $p(s'|s,a)$ and the fact that we follow policy $\pi$ in the probability statement accounts for the $\pi(a|s)$.

It looks like "v of s prime" is just substituted with the already derived value for "v of s". You can call it a recursion of a kind.
In other words, v(s) is dependent on v(s') and that implies that v(s') is dependent on v(s''). So we can combine that and get the dependency of v(s) of v(s'').

Where exactly does $Pr(s\rightarrow x, k, \pi)$ come from?

This is in the right direction for the first unrolling line, but actually the substituted term is $\nabla v_\pi(s')$ - you can use LaTex to put that into the answer - i.e. $\nabla v_\pi(s')$

I see where the unrolling leads, in terms of simply recursively expanding the expression. What I don't see, is how $Pr$ is substituted in the unrolled expression.


text:
Why does every neuron in hidden layers of a multi-layer perceptron typically have the same activation function?
Why does every neuron in a hidden layer of a multi-layer perceptron (MLP) typically have the same activation function as every other neuron in the same or other hidden layers (so I exclude the output layer, which typically has a different activation function) of the MLP? Is this a requirement, are there any advantages, or maybe is it just a rule of thumb?

As you stated, it's popular to have some form of a rectified linear unit (ReLU) activation in hidden layers and the output layer is often a softmax or sigmoid (depending also on the problem: multi-class or binary classification, respectively), which provides an output that can be viewed as a probability distribution.
You could generalize this further to blocks of different activation functions within the same layer. This is something I've thought about, haven't done, but imagine has been attempted. In some sense, the idea here would be to allow for a subsection of the network to develop a representation that may not be feasible otherwise. These different representations within the same layer would then be unified by subsequent layers as we move closer to the output.

regarding your last paragraph that's what I'm thinking about. Is there ever a benefit to have a layer where each Perceptron has a different activation function?

I updated the answer, maybe it addresses the question a bit better. I think the larger point is that anything is possible; neural networks are highly flexible models afterall. But the motivation for doing so is crucial – what would you hope to gain by having a block of neurons with alternate activations in the same layer? Why is this gain not possible without it? I suspect that answers that motivate such an architecture are hard to find. Further, as far as I'm aware, these aren't features that are readily available in existing software libraries.

@Greenstick I suspect with some problems where characteristics of the objective function are not obvious that experimenting with a mixture of activation functions might afford a better approximation to the function trying to be learned.

@user8714896 This is in effect done. Certain activations (e.g. PReLU) take in parameters that have their own associated weights (multiple params could exist for a layer); the neural net then learns how to parameterize these activations to minimize the objective function. You lose some interpretability and (maybe) motivation doing this (e.g. the biological motivation discussed above), but the nice part is that you don't have to precisely know the activation ahead of time – the neural net figures it out. Hope that helps; if this is in line with the answer you're looking for, please accept it.

This answer would improve considerably if you could do a little bit of research to find some research papers that show that, indeed, different activation functions can be used for different hidden neurons.


text:
How artificial intelligence will change the future?
AI is the emerging field and biggest business opportunity of the next decade. It's already automating manual and repetitive tasks. And in some areas, it can learn faster than humans, if not yet as deeply.
From the Forbes article

In the AI-enabled future, humans will be able to converse and interact with each other in the native language of choice, not having to worry about miscommunicating intentions.

I would like to know more about how artificial intelligence will change the future?

Here is something I've noticed about humans: We're bad at projecting the future with all of its 2nd, 3rd ... N order effects, and we're REALLY bad a projecting and quantifying risk. So, I'm not sure that you'll get an answer that is anything more than either trivially true ("Chatbots will be commonplace") or a correct but wasn't justified ("We'll explore the stars by sending out swarms of AI-enhanced satellites that will use their computing power to improve themselves since they are always on but have copious amounts of down-time").
But if you want to limit the timeframe to the next decade and don't mind the previous caveat, here goes:

Chatbots will be commonplace. This will include ones that can handle conversation, like Gridspace but can also handle multiple languages and code-switching.
In professional use, AI will augment professionals (such as lawyers, physicians, teachers, and accountants) at the upper end (who will add value with strategy, experience, and research) and replace them at the lower end.
In military use, they will be used for target identification, automated assessment of damage, threat notification, and forecasting.
We'll explore the stars by sending out swarms of AI-enhanced satellites that will use their computing power to improve themselves since they are always on but have copious amounts down-time.

I don't hold a lot of hope out for communication without error of to speakers of different languages as you can have two native fluent speakers who have known each other for years speak to each and still have them miscommunicate.

The von Neumann idea is very far off in terms of physical technology to implement a first generation. I am not sure why you might consider that to be reachable within a decade, whilst your first three suggestions seem much more conservative as predictions.

I'll second what Neil said, and add that depending on what you mean by "improve themselves", that might belong to science fiction. Continual online training based on new data is something we might have our systems do. Rewriting their code during the mission is probably not. By contrast, reliable realtime translation is actually a quite plausible prediction (which surprised me; most articles of this sort are filled with nothing but wishful thinking).

I should clarify. I don't think we're going to launch some sort near General AI level satellite that will somehow how GAI-level intelligence. I'm talking more about iterating through a set of parameters for optimization that get used as the basis for the next set of inputs and possible then re-optimized. So, the magnetic field of Jupiter inputs get used for Saturn which gets used for Heliosphere edge refinement. Any actual code improvements would come from earth. Also, it was meant as a callback to the first part of the answer and let me reference justified true belief for the hidden joke.

@Ray -- I'm sorry guys but that was meant as a joke. I referencing the not justified part of "correct but wasn't justified". In other words, it's nothing to make a prediction that ends up being false as they aren't remembered. True ones where people had a good reason makes them look like seers. "Correct but wasn't justified" just means lucky guessers but in a world with no penalty for wrong guesses we see it a lot.


text:
How are training hyperparameters determined for large models?
When training a relatively small DL model, which takes several hours to train, I typically start with some starting points from literature and then use a trial-and-error or grid-search approach to fine-tune the values of the hyper-parameters, in order to prevent overfitting and achieve sufficient performance.
However, it is not uncommon for large models to have training time measured in days or weeks [1], [2], [3].
How are hyperparameters determined in such cases?

I've seen some papers which are deriving a small dataset which has more or less the same characteristics as the large one and do the hyper-parameter selection on it.

In general, it is definitely very computationally expensive, so an exhaustive search is not performed in practice. However, there are some recent approaches for determining whether the architecture is "fine" without training the neural network first - by looking at the covariance matrix after forwarding the data, for example, in a recent paper Neural Architecture Search without Training. However, such an approach is very limited.


text:
Can residual neural networks use other activation functions different from ReLU?
In many diagrams, as seen below, residual neural networks are only depicted with ReLU activation functions, but can residual NNs also use other activation functions, such as the sigmoid, hyperbolic tangent, etc.?

The problem with certain activation functions, such as the sigmoid, is that they squash the input to a finite interval (i.e. they are sometimes classified as saturating activation functions). For example, the sigmoid function has codomain $[0, 1]$, as you can see from the illustration below.

This property/behaviour can lead to the vanishing gradient problem (which was one of the problems that Sepp Hochreiter, the author of the LSTM, was trying to solve in the context of recurrent neural networks, when developing the LSTM, along with his advisor, Schmidhuber).
Empirically, people have noticed that ReLU can avoid this vanishing gradient problem. See e.g. this blog post. The paper Deep Sparse Rectifier Neural Networks provides more details about the advantage of ReLUs (aka rectifiers), so you may want to read it. However, ReLUs can also suffer from another (opposite) problem, i.e. the exploding gradient problem. Nevertheless, there are several ways to combat this issue. See e.g. this blog post.
That being said, I am not an expert on residual networks, but I think that they used the ReLU to further avoid the vanishing gradient problem. This answer (that I gave some time ago) should give you some intuition about why residual networks can avoid the vanishing gradient problem.


text:
What should the output of a neural network that needs to classify in an unsupervised fashion XOR data be?
XOR data, without labels:
[[0,0],[0,1],[1,0],[1,1]]

I'm using this network for auto-classifying XOR data:
H1  <-- Dense(units=2, activation=relu)    #any activation here
Z   <-- Dense(units=2, activation=softmax) #softmax for 2 classes of XOR result
Out <-- Dense(units=2, activation=sigmoid) #sigmoid to return 2 values in (0,1)

There's a logical problem in the network, that is, Z represents 2 classes,
however, the 2 classes can't be decoded back to 4 samples of XOR data.
How to fix the network above to auto-classify XOR data, in unsupervised manner?

Programming issues are off-topic here. You've been a user on this site for a long time, so I recommend you read our on-topic page: https://ai.stackexchange.com/help/on-topic.

nana, i meant to ask about theory, ie. how to design an autoencoder to group up unsupervised data

Ok. Please, next time make sure to clarify that, especially, when you add code to your post.

How to fix the network above to auto-classify XOR data, in unsupervised manner?

This cannot be done, except accidentally.
Unsupervised learning cannot replace or emulate supervised learning.
As a thought experiment, consider why you would expect the network to discover XOR, when simply considering outputs rounded to binary, you could equally find AND, OR, NAND, NOR or any of the 16 possible mapping functions from input to output. All of the possible maps are equally valid functions, and there is no reason why a discovered function mapping should become any one of them by preference.
Unsupervised learning approaches typically find patterns that optimise some measure across the dataset without using labelled data. Clustering is a classic example, and auto-encoding is sometimes considered unsupervised because there is no separate label (although the term self-supervised is also used, because there is still technically a label used in training, it happens to equal the input).
You cannot use auto-encoding approaches here anyway, because XOR needs to map $\{0,1\} \times \{0,1\} \rightarrow \{0,1\}$
You could potentially use a loss function based on how close to a 0 or 1 any output is. That should cause the network to converge to one of the 16 possible binary functions, based on random initialisation. For example, you could use $y(1-y)$ as the loss.

Unsupervised learning cannot replace or emulate supervised learning.
Actually, I disagree with it a bit. If you find a pattern/clusters with USL, and then label the pattern/clusters with some label, then you emulate SL a bit.

@DanielWiczew I think that is strectching definitions, but I suppose it is a matter of taste. I don't think I will include in the answer though, because it won't solve OP's problem.

@NeilSlater tks, i now use different fixed init weights for different grouping discovery :)

authors: ابو حسين المدم


text:
What exactly is the advantage of double DQN over DQN?
I started looking into the double DQN (DDQN). Apparently, the difference between DDQN and DQN is that in DDQN we use the main value network for action selection and the target network for outputting the Q values.
However, I don't understand why would this be beneficial, compared to the standard DQN. So, in simple terms, what exactly is the advantage of DDQN over DQN?

In $Q$-learning there is what is known as a maximisation bias. That is because the update target is $r + \gamma \max_a Q(s,a)$. If you slightly overestimate your $Q$-value then this error gets compounded (there is a nice example in the Sutton and Barto book that illustrates this). The idea behind tabular double $Q$-learning is to have two $Q$-networks, $Q_1,Q_2$, and you choose an action $a$ from them, e.g. from $Q_1 + Q_2$. You then flip a coin to decide which to update. If you choose to update $Q_1$ then the update target becomes $r + \gamma Q_2(s', \arg\max_a Q_1(s',a))$.
The idea is that if you overshoot your estimate on one $Q$ network then having the second will hopefully control this bias when you would take the max.
In Deep Double $Q$-learning the idea is essentially the same but instead of having to maintain and train two $Q$-networks, they use the target network from vanilla DQN to provide the target. To make this more concrete, the update target they use is
$$r + \gamma Q(s', \arg\max_aQ(s',a;\theta);\theta^-)\;,$$
where $Q(s,a;\theta^-)$ denotes the target network whose parameters are only updated to the current networks every $C$ time steps.
As before, the idea is that if we have overestimated our value of being state $s'$ in our current network when taking the max action, using the target network to provide the target will help control for this bias.
Maximisation Bias
I will here explain maximisation bias from the simple example given from the Sutton and Barto book.

The Markov Decision Process in the image is defined as follows: we start in state A and can take the 'right' action which gives us 0 reward and immediately leads to termination. If we choose 'left' we get 0 immediate reward where we then move to state B. From there, we have an arbitrary number of action we can take where they all lead to the terminal state and the reward is drawn from a Normal(-0.1,1) distribution.
Clearly, the optimal action is always to move to the right from state A as this gives 0 expected future returns. Taking the left action will give a $\gamma \times -0.1$ expected future returns (the $\gamma$ is our discount factor).
Now, if we got into state $B$ and took some random action our initial reward could be bigger than 0 -- after all it is drawn from a Normal(-0.1,1) distribution.
Now, consider we are updating our $Q$-function for state A and taking the left action. Our update target will be $0 + \gamma \max_a Q(B,a)$. Because we are taking the max over all possible actions, this will lead to a positive reward and so we are backing up the belief of our expected future rewards from taking action left in state A to be something positive -- clearly this is wrong since we know it should be -0.1. This is what is known as the maximisation bias, because it gives us a kind of 'optimistic' estimate of the action value!
I've attached an image below that shows the %age of time the agent chose the left action, which it shouldn't be choosing). As you can see, it takes normal $Q$-learning along time to even start to correct itself, whereas double $Q$-learning corrects the mistake almost immediately.

Suppose our target network is the one overestimating our Q values. We use our main value network for selecting the action and use our target for calculating Q values. Wouldn't this value still be overestimated?

Well, the target network is randomly initialized, so that is unlikely to be the case.

But, at the beginning of training, isn't our target network just a copy of our main value network? What happens if those weights overestimate the values?

Yes, exactly. However, your online/main value network is just randomly initialized... Depending on the method, they usually just initialize it to very small values, so, as I say, it is unlikely to have a strong effect.

Interestingly DDQN is not going to 0%!

@mohit yes, this is because of the $\epsilon$-greedy exploration.


text:
Who first coined the term "deep learning"?
AFAIK, deep learning became popular in 2012 with the victory of ImageNet Competition - Large Scale Visual Recognition Challenge 2012 where winners of this contest actually used deep learning techniques for optimizing the solution for object recognition.
Who first coined the term deep learning? Is there any published research paper that first used that term?

The term was introduced to the machine learning and computer science community by Rina Dechter in Learning While Searching in Constraint-Satisfaction-Problems (1986) [1], where she writes

Discovering all minimal conflict-sets amounts to acquiring all the possible information out of a dead-end. Yet, such deep learning may require considerable amount of work.

When deep learning is used in conjunction with restricting the level of learning we get deep first-order learning (identifying minimal conflict sets of size 1) and deep second-order learning (i.e. identifying minimal conflict-sets of sizes 1 and 2).

Our experiments (implemented in LISP on a Symbolits LISP Machine) show that in most cases both performance measures improve as we move from shallow learning to deep learning and from first-order to second order.

However, note that the term deep learning was used before 1986 in other contexts, for example, in [2]. Moreover, note that Rina Dechter did not use the term in the context of neural networks, which was probably used later.


text:
How to handle images that don’t pertain to image classifier at all?
I am trying to create a CNN model that classifies if a person is wearing a seatbelt or not to verify they drive safely. I know to get images of people wearing seatbelts and people not wearing seatbelts, but I have a problem.
What if the person doesn’t submit a picture of them in a car at all? How do I construct the rest of the dataset to determine if that picture is an actual picture of a person wearing a seatbelt?
Do I insert completely random pictures in a different category? Do I classify images that don’t have a high confidence score as "wrong" images? Or leave it?

Yes, thanks! If you can reference a Bayesian NN with CNNs in Tensorflow that would be a great help!

From what I understood, you want to be able to determine whether the input to your classifier is a valid picture or not. Where:

Valid picture: image of a person wearing or not wearing a seatbelt
Not valid picture: unrelated images (say a kitchen picture) or noise, or a black image (no input at all)

For that you could build a Bayesian model from your current deep-learning model. Check out Pyro (from pytorch). The main idea behind it, is that the model will always predict a class: person wearing or not wearing a seatbelt. But since it is a Bayesian model it will also tell you the confidence of the prediction in terms of the similarity of the input with the input distribution for which the model was trained. In other words, it will also tell you "how valid" is that prediction, or "how valid" is the input for that prediction.
Check out this post where it is very well explained. Hope it helps!

This may be a good suggestion, but, in practice, it isn't guaranteed that the Bayesian model will provide well-calibrated uncertainty estimates.

Thanks so much! If you can reference a way to do so using a CNN and/or Tensorflow, I would appreciate it as it would save time learning a new library. Thanks again.

Yes, a category "no person" or "random image" would make sense. Binary classification is only helpful if you know that your input always belongs to one or the other category, for example by pre-filtering the inputs.

I've heard using Bayesian Neural Networks are good for this sort of problem. BNNs print out a probability that doesn't add up to only one, and there is a threshold then for the confidence score for the model to be able to say "I don't know." Which approach would be more effective, do you think?

I can't say. In general, you need experience with several methods to judge which is best for a given case, or you need to ask an expert, which I am not in the image classification field.


text:
How could logistic loss be used as loss function for an ANN?
Normally, in practice, people use those loss functions with minima, e.g. $L_1$ mean absolute loss, $L_2$ mean squared error, etc. All those come with a minimum to optimize to.

However, there's another thing, logistic loss, I'm reading about, but don't get it why the logistic function could be used as a loss function, given that it has the so-called minimum at infinity, but that isn't a normal minimum. Logistic loss function (black curve):

How can an optimizer minimize the logistic loss?

I see why you might be confused. First, the logistic-loss or log-loss is technically called cross-entropy loss. This function is very simple:
$CE = -[y \log(p) + (1 - y) \log(1 - p)]$
This tells basically if the predicted class $y$ was right $y=1$ then the loss is $CE=-\log(p)$, if the predicted class was not the right one then the loss is $CE=-\log(1-p)$.
If we look at the function as a pure math concept we see that:
$CE = f(x) = - \log(x)$
And as you point out, that function is minima-unbounded as its domain is $D(f(x)) = [0, +\infty]$. You can check that in here:

However the trick is that the inputs must be bounded, meaning, the inputs to the loss function must be in range $[0, 1]$. This bounding is achieved by applying a sigmoid activation function as the final "layer" of the network. Then if the inputs to the loss function are bounded the function has a clear minima.
Check how the function looks in reality from one of the most important papers in loss function in the AI world: Focal Loss (I really encourage you to read it as the first section explains in detail the cross-entropy loss). The blue curve is the one you are looking for.

Finally, you might want to review your log-loss/CE function since it should have an asymptote for $f(x=0) = \infty$


text:
Do transformers have success in other domains different than NLP?
Everybody knows how successful transformers have been in NLP. Is there known work on other domains (e.g that also have a sequential natural way of occurring, such as stock price prediction or other problems)?

Image generation with transformers instead of GANs is a thing.

do you have a paper or a reference?

https://cdn.openai.com/papers/Generative_Pretraining_from_Pixels_V2.pdf see also the completions section at their website.  https://openai.com/blog/image-gpt/

I've recently start seeing transformer-based models being used for traffic forecasting. Here is an example: https://arxiv.org/abs/2001.02908

@razvanc92 Although this is an old question, you can provide a formal answer below. Comments are meant to be temporary.

@thepacker As I told razvanc92, you can provide a formal answer below.

When it talks to other domains such as image or music, using transformer will always face a problem of sequence length limitation. To the best of my knowledge, the bottleneck of self-attention which uses a $n^2$ matrix quite limits transformer being applied to other domains. For example, a 32x32 pixel image, means a sequence of 1024 tokens.
OpenAI did some related research, as the followings.
Generative Modeling with Sparse Transformers:
In the paper, transformers with sparse attention are applied to image and waveform.
ImageGPT:
A large transformer model trained on language can generate coherent text, the same exact model trained on pixel sequences can generate coherent image completions and samples. (Abstract from the blog)

You may also want to mention the vision transformer.


text:
Why is tic-tac-toe considered a non-deterministic environment?
I have been reading about deterministic and stochastic environments, when I came up with an article that states that tic-tac-toe is a non-deterministic environment.
But why is that?
An action will lead to a known state of the game and an agent has full knowledge of the board and of its enemies' past moves.

You say "when I came up with an article that states that TIC TAC TOE is a non-deterministic environment.". Can you please provide the link to the article?

The game of TIC-TAC-TOE can be modelled as a non-deterministic Markov decision process (MDP) if, and only if:

The opponent is considered part of the environment. This is a reasonable approach when the goal is to solve playing against a specific opponent.

The opponent is using a stochastic policy. Stochastic policies are a  generalisation that include deterministic policies as a special case, so this is a reasonable default assumption.

An action will lead to a known state of the game and an agent has full knowledge of the board and of Its enemies past moves.

Whilst this is true, the next state and reward as observed by an agent may not be due to the postion it plays in (with the exception being if it wins or draws on that move), but the position after the opponent plays.
It is also possible to frame TIC-TAC-TOE as a partially observed MDP (POMDP) if you consider the opponent to not have a fixed policy, but to be reacting to play so far, perhaps even learning from past games. In which case, the internal state of the opponent is the unknown part of the state. In standard game playing engines and in games of perfect information, this is resolved by assuming the opponent will make the best possible (or rational) move, which can be determined using a search process such as minimax. When there is imperfect information, such as in poker, it becomes much harder to allow for an opponent's action.

Thank you. But from this answer, every multi agent environment can be viewed as a non deterministic because the next state and reward as observed by an agent may not be due to the postion it plays in (with the exception being if it wins or draws on that move), but the position after the opponent plays. Is there any example of a multi-agent system with a deterministic environment ?

@EEAH: That is correct. It will depend on how you define and implement multi-agent environments. However, if the agent needs to account for the behaviour of the other agents then the result can be non-deterministic. You can reasonably say that the core of the environment is deterministic, in the same sense that TIC TAC TOE is a deterministic game, but the agents may often need to deal practically with non-deterministic and/or partially-observable features, regardless of whether you say that is due to the agents separately, or if you consider other agents to be part of the environment.


text:
Does this $\max$ mean that we need to maximize the regret in this regret formula?
I found that the regret in Online Machine Learning is stated as:
$$\operatorname{Regret}_{T}(h)=\sum_{t=1}^{T} l\left(p_{t}, y_{t}\right)-\sum_{t=1}^{T} l\left(h(x), y_{t}\right),$$
where $p_t$ is the answer of my algorithm to the question $x$ and $y_t$ is the right answer, while $h()$ is one of the hypotheses in the hypothesis space. Intuitively, as denoted in the paper, our objective is to minimize this Regret in order to optimize our algorithm, but in the following formula
$$
\operatorname{Regret}_{T}(\mathcal{H})=\max _{h^{\star} \in \mathcal{H}} \operatorname{Regret}_{T}\left(h^{\star}\right)
$$
they maximize this value. Am I interpreting the $max$ wrongly?

Yes, you're interpreting the $\max$ there wrongly. In your second formula
$$
\operatorname{Regret}_{T}(\mathcal{H})=\max _{h^{\star} \in \mathcal{H}} \operatorname{Regret}_{T}\left(h^{\star}\right) \label{1}\tag{1}
$$
The sign $=$ means "is defined as", so maybe the following notation is less confusing
$$
\operatorname{Regret}_{T}(\mathcal{H}) \triangleq \max _{h^{\star} \in \mathcal{H}} \operatorname{Regret}_{T}\left(h^{\star}\right)
$$
In fact, in section 2.1 of the same paper, there's a similar but more detailed formula that should clarify the meaning of $\max$
$$
\operatorname{Regret}_{T}(\mathcal{H})=\max _{h \in \mathcal{H}}\left(\sum_{t=1}^{T}\left|p_{t}-y_{t}\right|-\sum_{t=1}^{T}\left|h\left(\mathbf{x}_{t}\right)-y_{t}\right|\right)
$$
Note that $\operatorname{Regret}_{T}(\mathcal{H})$ is defined for $\mathcal{H}$, while your first formula is defined for $x$. So, \ref{1} is the regret for the whole hypotheses class $\mathcal{H}$, which is thus the maximum regret that you can have across all possible hypotheses $h \in \mathcal{H}$. This should make sense.

I corrected the argument of my first formula, it was h not x. Anyway thank you, I thought was "is defined as" but I was not sure

@FraMan But note that you had taken a screenshot of the formula and it was $x$ because I used a program to convert the screenshot to the latex formula.

I wrote the Latex formula wrong and then I uploaded a screenshot of that formula because I'm stupid :)

@FraMan Haah, don't worry, man :)


text:
Is a policy in reinforcement learning analogous to a field such as APF?
If a policy maps states to actions in reinforcement learning, then for a path planning with obstacles, can't we simply use Artificial Potential Field fields for path planning and model policy mathematically as a field where the obstacles form repulsive field and goal form attractive field?
So, technically, is a policy simply a field?

Since most policies depend solely on actions and states/observations, then if you model the space of this field as the Cartesian Product of your state and action spaces, then the policy learns a surface over this combined space, similar to the way a field is parameterized.
The policy an agent learns could exhibit the same behavior as the field you describe above (obstacles form an repulsive field, and goal(s) form an attractive field).  However, unlike the field described above, it is not guaranteed that the learned policy will capture this behavior - the policy learned depends on:

The learning algorithm used
The approximators (e.g. neural networks) used for learning, and their respective hyperparameters
The formulation of the reward function
The number of episodes/total steps the policy/agent is trained over.

To sum this answer up, I believe you could train the policy in such a way (using the mechanisms above) such that it resembles the field you describe.

The field has much closer analogy with a value function than with a policy function. The policy is analagous to a solution found by using the field.

So isnt technically a policy a field surface, with the exception of the fact that field is more or less deterministic while policy is field + probability assigned to it every action in the field?

@NeilSlater, if we merely assign probability to the field at each state, will then it be close analogy to the policy as policies are probabilistic transition from states to actions?

@gfdsal: A potential field cannot directly represent probabilities. You might derive them from it, according to the local gradients of the field. Again that is a closer analogy to a value function used as a heuristic, not a policy function. A policy can be derived from a state value function in a similar way as a plan can be derived from an APF.


text:
What are some best practices when trying to design a reward function?
Generally speaking, is there a best-practice procedure to follow when trying to define a reward function for a reinforcement-learning agent? What common pitfalls are there when defining the reward function, and how should you avoid them? What information from your problem should you take into consideration when going about it?
Let us presume that our environment is fully observable MDP.

Designing reward functions
Designing a reward function is sometimes straightforward, if you have knowledge of the problem. For example, consider the game of chess. You know that you have three outcomes: win (good), loss (bad), or draw (neutral). So, you could reward the agent with $+1$ if it wins the game, $-1$ if it loses, and $0$ if it draws (or for any other situation).
However, in certain cases, the specification of the reward function can be a difficult task [1, 2, 3] because there are many (often unknown) factors that could affect the performance of the RL agent. For example, consider the driving task, i.e. you want to teach an agent to drive e.g. a car. In this scenario, there are so many factors that affect the behavior of a driver. How can we incorporate and combine these factors in a reward function? How do we deal with unknown factors?
So, often, designing a reward function is a trial-and-error and engineering process (so there is no magic formula that tells you how to design a reward function in all cases). More precisely, you define an initial reward function based on your knowledge of the problem, you observe how the agent performs, then tweak the reward function to achieve greater performance (for example, in terms of observable behavior, so not in terms of the collected reward; otherwise, this would be an easy problem: you could just design a reward function that gives infinite reward to the agent in all situations!). For example, if you have trained an RL agent to play chess, maybe you observed that the agent took a lot of time to converge (i.e. find the best policy to play the game), so you could design a new reward function that penalizes the agent for every non-win move (maybe it will hurry up!).
Of course, this trial-and-error approach is not ideal, and it can sometimes be impractical (because maybe it takes a lot of time to train the agent) and lead to misspecified reward signals.
Misspecification of rewards
It is well known that the misspecification of the reward function can have unintended and even dangerous consequences [5]. To overcome the misspecification of rewards or improve the reward functions, you have some options, such as

Learning from demonstrations (aka apprenticeship learning), i.e. do not specify the reward function directly, but let the RL agent imitate another agent's behavior, either to

learn the policy directly (known as imitation learning [8]), or
learn a reward function first to later learn the policy (known as inverse reinforcement learning [1] or sometimes known as reward learning)

Incorporate human feedback [9] in the RL algorithms (in an interactive manner)

Transfer the information in the policy learned in another but similar environment to your environment (i.e. use some kind of transfer learning for RL [10])

Of course, these solutions or approaches can also have their shortcomings. For example, interactive human feedback can be tedious.
Reward shaping
Regarding the common pitfalls, although reward shaping (i.e. augment the natural reward function with more rewards) is often suggested as a way to improve the convergence of RL algorithms, [4] states that reward shaping (and progress estimators) should be used cautiously.  If you want to perform reward shaping, you should probably be using potential-based reward shaping (which is guaranteed not to change the optimal policy).
Further reading
The MathWorks' article Define Reward Signals discusses continuous and discrete reward functions (this is also discussed in [4]), and addresses some of their advantages and disadvantages.
Last but not least, the 2nd edition of the RL bible contains a section (17.4 Designing Reward Signals) completely dedicated to this topic.
Another similar question was also asked here.

If your objective is for the agent to attain some goal (say, reaching a target), then a valid reward function is to assign a reward of 1 when the goal is attained and 0 otherwise. The problem with this reward function is that it's too sparse, meaning the agent has little guidance on how to modify their behavior to become better at attaining said goal, especially if the goal is hard to attain through a random policy in the first place (which is probably roughly what the agent starts with).
The practice of modifying the reward function to guide the learning agent is called reward shaping.
A good start is Policy invariance under reward transformations: Theory and application to reward shaping by Ng et al. The idea is to create a reward potential (see Theorem 1) on top of the existing reward. This reward potential should be an approximation of the true value of a given state. For instance, if you have a gridworld scenario where the goal is for the agent to reach some target square, you could create a reward potential based on the Manhattan distance to this target (without accounting for obstacles), which is an approximation to the true value of a given position.
Intuitively, creating a reward potential that is close to the true values makes the job easier for the learning agent because it reduces the disadvantage of being myopic, and the agent more quickly gets closer to a "somewhat good" policy from which it is easier to crawl toward the optimal policy.
Moreover, reward potentials have the property that they are consistent with the optimal policy. That is, the optimal policy to the true problem will not become suboptimal under the new, modified problem (with the new reward function).


text:
Why do the standard and deterministic Policy Gradient Theorems differ in their treatment of the derivatives of $R$ and the conditional probability?
I would like to understand the difference between the standard policy gradient theorem and the deterministic policy gradient theorem. These two theorem are quite different, although the only difference is whether the policy function is deterministic or stochastic.  I summarized the relevant steps of the theorems below. The policy function is $\pi$ which has parameters $\theta$.
Standard Policy Gradient
$$
\begin{aligned}
\dfrac{\partial V}{\partial \theta} &= \dfrac{\partial}{\partial \theta} \left[ \sum_a \pi(a|s) Q(a,s) \right]  \\
&= \sum_a \left[ \dfrac{\partial \pi(a|s)}{\partial \theta}  Q(a,s) + \pi(a|s) \dfrac{\partial Q(a,s)}{\partial \theta} \right] \\
&= \sum_a \left[ \dfrac{\partial \pi(a|s)}{\partial \theta}  Q(a,s) + \pi(a|s) \dfrac{\partial}{\partial \theta} \left[ R + \sum_{s'} \gamma p(s'|s,a) V(s') \right] \right]  \\
&= \sum_a \left[ \dfrac{\partial \pi(a|s)}{\partial \theta}  Q(a,s) + \pi(a|s) \gamma \sum_{s'} p(s'|s,a) \dfrac{\partial V(s') }{\partial \theta} \right]
\end{aligned}
$$
When one now expands next period's value function $V(s')$ again one can eventually reach the final policy gradient:
$$
\dfrac{\partial J}{\partial \theta} = \sum_s \rho(s) \sum_a \dfrac{\pi(a|s)}{\partial \theta}  Q(s,a)
$$
with $\rho$ being the stationary distribution. What I find particularly interesting is that there is no derivative of $R$ with respect to $\theta$ and also not of the probability distribution $p(s'|s,a)$ with respect to $\theta$. The derivation of the deterministic policy gradient theorem is different:
Deterministic Policy Gradient Theorem
$$
\begin{aligned}
\dfrac{\partial V}{\partial \theta} &= \dfrac{\partial}{\partial \theta} Q(\pi(s),s)  \\
&= \dfrac{\partial}{\partial \theta} \left[ R(s, \pi(s)) + \gamma \sum_{s'} p(s'|a,s) V(s') \right] \\
&= \dfrac{R(s, a)}{\partial a}\dfrac{\pi(s)}{\partial \theta} + \dfrac{\partial}{\partial \theta} \left[\gamma \sum_{s'} p(s'|a,s) V(s')   \right]  \\
&= \dfrac{R(s, a)}{\partial a}\dfrac{\pi(s)}{\partial \theta} + \gamma \sum_{s'}  \left[p(s'|\mu(s),s) \dfrac{V(s')}{\partial \theta} + \dfrac{\pi(s)}{\partial \theta} \dfrac{p(s'|s,a)}{\partial a} V(s')   \right]  \\
&= \dfrac{\pi(s)}{\partial \theta} \dfrac{\partial}{\partial a} \left[ R(s, a) +  p(s'|s,a) V(s') \right] +  \gamma  p(s'|\pi(s),s) \dfrac{V(s')}{\partial \theta}  \\
&= \dfrac{\pi(s)}{\partial \theta} \dfrac{\partial Q(s, a)}{\partial a} +  \gamma  p(s'|\pi(s),s) \dfrac{V(s')}{\partial \theta}  \\
\end{aligned}
$$
Again, one can obtain the finaly policy gradient by expanding next period's value function. The policy gradient is:
$$
\dfrac{\partial J}{\partial \theta} = \sum_s \rho(s) \dfrac{\pi(s)}{\partial \theta} \dfrac{\partial Q(s,a))}{\partial a}
$$
In contrast to the standard policy gradient, the equations contain derivatives of the reward function $R$ and the conditional probability $p(s'|s, a,)$ with respect to $a$.
Question
Why do the two theorems differ in their treatment of the derivatives of $R$ and the conditional probability? Does determinism in the policy function make such a difference for the derivatives?

I don't have time to leave a full answer for now but in short it is because the latter requires the use of a chain rule because the parameters we differentiate with respect to are parameters of $\pi$ but we have access only to $Q$ -- it is like wanting to do the following $\frac{d}{dx} f(g(x))$. I can try and leave a better answer if nobody else has when I get chance.

Thank you @DavidIreland for your comment! I'd be very grateful to read your full answer! Can you elaborate a bit why the chain rule should not be applicable in the usual policy gradient theorem? Implicitly, $R(s,a)$ is also function of $\pi(a|s)$, although a stochastic function.

In the policy gradient theorem, we don't need to write $r$ as a function of $a$ because the only time we explicitly 'see' $r$ is when we are taking the expectation with respect to the policy. For the first couple lines of the PG theorem we have
\begin{align}
\nabla v_\pi(s) &= \nabla \left[ \sum_a \pi(a|s) q_\pi (s,a) \right] \;, \\ &= \sum_a \left[ \nabla \pi(a|s) q_\pi(s,a) + \pi(a|s) \nabla\sum_{s',r} p(s',r|s,a)(r+ v_\pi(s')) \right] \; ;
\end{align}
you can see that we are taking expectation of $r$ with respect to the policy, so we don't need to write something like $r(s,\pi(a|s))$ (especially because this notation doesn't really make sense for a stochastic policy). This is why we don't need to take the derivative of $r$ with respect to the policy parameters. Now, the next line of the PG theorem is
$$\nabla v_\pi(s) = \sum_a \left[ \nabla \pi(a|s) q_\pi(s,a) + \pi(a|s)\sum_{s'} p(s'|s,a) \nabla v_\pi(s') \right] \; ;$$
so now we have an equation similar to the bellman equation in terms of the $\nabla v_\pi(s)$'s, so we can unroll this repeatedly meaning we never have to take an explicit derivative of the value function.
For the deterministic gradient, this is a bit different. In general we have
$$v_\pi(s) = \mathbb{E}_\pi[Q(s,a)] = \sum_a \pi(a|s) Q(s,a)\;,$$
so for a deterministic policy (denoted by $\pi(s)$ which represents the action taken in state $s$) this becomes
$$v_\pi(s) = Q(s,\pi(s))$$
because the deterministic policy has 0 probability for all actions except one, where it has probability one.
Now, in the deterministic policy gradient theorem we can write
$$\nabla v_\pi(s) = \nabla Q(s,\pi(s)) = \nabla \left(r(s, \pi(s)) + \sum_{s'} p(s'|s,a)v(s') \right)\;.$$
We have to write $r$ explicitly as a function of $s,a$ now because we are not taking an expectation with respect to the actions because we have a deterministic policy. Now, if you replace where I have written $\nabla$ with the notation you have used for the derivatives you will arrive at the same result and you'll see why you need to use the chain rule, which I believe you understand because your question was more why don't we use the chain rule for the normal policy gradient, which I have hopefully explained -- it is essentially because of how an expectation over the action space works with a deterministic policy vs. a stochastic policy.
Another way to think of this is as follows -- the term you're concerned with is obtained by expanding $\nabla q_\pi(s,a) = \nabla \sum_{s', r}p(s',r|s,a)(r(s,a) + v_\pi(s'))$. Because, by definition of the $Q$ function, we have conditioned on knowing $a,s$ then $a$ is completely independent of the policy in this scenario - we could even condition on an action that the policy would have 0 probability for - thus the derivative of $r$ with respect to the policy parameters is 0.
However, in the deterministic policy gradient we are taking $\nabla q_\pi(s, \pi(s)) = \nabla \left(r(s, \pi(s)) + \sum_{s'} p(s'|s,a) v_\pi(s')\right)$ -- here $r$ clearly depends on the policy parameters because the action taken was the deterministic action given by the policy in the state $s$, thus the derivative wrt the policy parameters is not necessarily 0!

Thank you very much David! Your answer is extremely helpful to me. I mark the answer as accepted. Nevertheless, I still do not fully comprehend your answer - most likely because I am lacking the knowledge about how conditional expectations interact with derivatives. I understand your argument as saying that one cannot compute $\partial E[y(x) | x] / \partial x$? If, by any chance, you know a good book for how conditional expectations affect derivatives, I'd be happy to read that! Anyway - thanks again for the detailed answer!

it is not so much that we can't compute that derivate, in fact in general this derivative is possible to calculate. It is more that in the stochastic policy gradient the policy affects the reward through the expectation, if this makes sense. However, in the deterministic policy case, you do technically still take the same expectation it is just because of how deterministic expectations work out that it directly effects the reward, which is what I tried to stress in my answer.

@fabian also a good way to think of it is that in the standard policy gradient $r$ is a function of $s,a$ (denote this by $r(s,a)$) but we condition on knowing $a$ so this is independent of the policy, thus it is constant wrt policy parameters. In the deterministic PG we still condition on taking an action $a$ but here the action is $a=\pi(s)$ which shows there is a clear dependence on the policy parameters. Please let me know if this helps clarify things and I can edit it into my answer, as I feel my original explanation may have been a bit convoluted.

Thanks for your comments! I benefited particularly from your first comment. In the second comment, we could think of the stochastic policy just as the deterministic policy with a little bit of noise (as the behavioral exploration policy in DDPG) so there is also a clear dependence on the policy parameters as you said. Overall, its still a bit difficult for me to understand the precise mathematical reason / proof for the differences in the two theorems but your answers and comments illuminated many aspects greatly for me; thank you again for that.

@fabian no, not really. the deterministic policy is a limiting case for a stochastic policy, as shown in the deterministic policy gradient paper. If you read my edit on the paper, then it should clarify things further. Because we have conditioned on some $a$ in the stochastic case, there is no dependency on the policy, because as I mentioned it is just an arbitrary action - when this is done in the deterministic case there is absolutely a dependency because we are conditioning on the action the deterministic policy gives.

Your last comment (and also the last two paragraphs of your answer) brought the point home. This really makes sense. Thank you very much indeed!

Just to summarize and check whether I understood it: In the stochastic case (and under conditional expectation in general) $E[r|s,a]=f(s,a)$ for some function $f$. Because $a$ is stochastic $a \sim \pi(s; \theta)$ and because we have already conditioned on $a$ we cannot go back  and take the derivative w.r.t. $\theta$. In contrast for the deterministic case $E[r|s]=f(s) = f(\pi(s; \theta))$ we can take the derivative w.r.t $\theta$ as the entire chain is deterministic. Could I summarize your argument like this, @David?

Yes, exactly. Good job!

@David thank you for your answer, but could you elaborate on notation I am still unfamiliar with ? I can't find corresponding parts in the proof or justification for some of your statements. Eg.: (a) $(r + v_{\pi}(s'))$ akin more to the Bellman-equ. (2nd equ-line) never appears in the proof and I can't find it by basic rewriting of the equations (yet considering $\mathcal{P}{ss'}^a$). (b) The deterministic optimal state value function $v{\pi}(s)$ is the expected value (under policy $\pi$?) of all action value functions but just a sum of values? (c) Why condition on the action not state $s$?


text:
When would bias regularisation and activation regularisation be necessary?
For Keras on TensorFlow, a layer class constructor comes with these:

kernel_regularizer=...
bias_regularizer=...
activity_regularizer=...

For example, Dense layer:
https://www.tensorflow.org/api_docs/python/tf/keras/layers/Dense#arguments_1
The first one, kernel_regularizer is easy to understand, it regularises weights, makes weights smaller to avoid overfitting on training data only.
Is kernel_regularizer enough? When should I use bias_regularizer and activity_regularizer too?

Regularizer's are used as a means to combat over fitting.They essentially create a cost function penalty which tries to prevent quantities from becoming to large.  I have primarily used kernel regularizers. First I try to control over fitting using dropout layers. If that does not do the job or leads to poor training accuracy I try the Kernel regularizer. I usually stop at that point. I think activity regularization would be my next option to prevent outputs from becoming to large. I suspect weight regularization effectively can pretty much achieve the same result.


text:
What is the difference between simulated annealing and deterministic annealing?
Not sure if this is the right place, but I was wondering if someone could briefly explain to me the differences & similarities between simulated annealing and deterministic annealing?
I know that both methods are used for optimization and both originate from statistical physics with the intuition of reaching a minimum energy (cost) configuration by cooling (i.e. slowly reducing the temperature in the Boltzmann distribution to calculate probabilities for configurations).
Unfortunately, Wikipedia has no article about deterministic annealing and the one about simulated annealing does not mention any comparison.
This resource has a brief comparison section between the two methods, however, I do not understand why the search strategy of DA is

based on the steepest descent algorithm

and how

it searches the local minimum deterministically at each temperature.

Any clarification appreciated.

In that article that you mention, they say that "Stochastic search based on the Metropolis algorithm". However, although I am familiar with SA, I don't recall having read that anywhere (but my memory isn't that good). So, even though SA may have been based on or inspired by another algorithm/method, that information isn't probably very useful, unless you are already familiar with the Metropolis algorithm. Similarly, although I am not familiar with DA, I suspect that, generally, it may not be very relevant if it's based on the steepest descent algorithm or not, as long as you know how DA works.

Furthermore, in the introduction section of the original paper that introduced DA, the authors say k-means is a "steepest descent" algorithm, in the sense that k-means always moves in some space that decreases the cost function (so it can be trapped in a local minimum). Again, I am familiar with k-means, but I've never heard of this interpretation, even though it kind of makes sense to me. So, DA is a "steepest descent" algorithm in the sense that it always moves in some search space so that to decrease the cost (or loss), but it probably can get trapped in a local minimum.

Thanks for you comment. After some time I came to an insightful explanation as well.

After diving deeper into the material I am able to answer my own question:
Simulated Annealing tries to optimize a energy (cost) function by stochastically searching for minima at different temparatures via a Markov Chain Monte Carlo method. The stochasticity comes from the fact that we always accept a new state $c'$ with lower energy ($\Delta E < 0$), but a new state with higher energy ($\Delta E > 0$) only with a certain probability
$$p(c \to c') = \text{min}\{1, \exp(-\frac{\Delta E}{T}) \},$$
$$\Delta E = E(c') - E(c).$$
Where we used the Gibbs distribution $p(c) = \frac{1}{Z}\text{exp}(\frac{-E(c)}{T})$ to calculate probabilities for each state, with $Z$ being the partition sum. The temperature $T$ plays the role of a scaling factor for the probability distribution. If $T \to \infty $ we have a uniform distribution and all states are equally possible. If $T \to 0$ we have a Dirac delta function around the global optimum. By starting with a high $T$, sampling states and gradually decreasing it, we can make sure to sample enough states from the state space and accepting energetic higher states in order to escape local minima on the way to the global optimum. After sampling long enough while slowly decreasing the temperature, we theoretically arrive at the global optimum.
Deterministic Annealing on the other hand directly minimizes the free energy $F(T)$ of the system deterministically at each temperature, e.g. by Expectation-Maximization (EM-algorithm). The intuition behind it is that we like to find an optimum at a high temperature (where it is easier to find one because there are fewer local minima), accept this as intermediate solution, lower the temperature, thus scaling the cost function such it is more peaked around it's optima (making optimization a bit more difficult) and start deterministically looking for an optimum again. This is repeated until the temperature is low enough and we (hopefully) found a global solution to our problem. Major drawback is that there is no guarantee to arrive at a global optimum in contrast to simulated annealing. The whole idea of scaling the energy function is based on the concept of homotopy: "Two continuous functions [...] can be "continuously deformed" into each other."


text:
Why is symbolic AI not so popular as ANN but used by IBM's Deep Blue?
Everybody is implementing and using DNN with, for example, TensorFlow or PyTorch.
I thought IBM's Deep Blue was an ANN-based AI system, but this article says that IBM's Deep Blue was symbolic AI.
Are there any special features in symbolic AI that explain why it was used (instead of ANN) by IBM's Deep Blue?

ANNs as used today need 1. a lot of data 2. a lot of computational power. Before we had any of the above two, we didn't really know how to properly build ANNs since we didn't quite have the means to train the network, and thus couldn't evaluate it.
"Symbolic AI" on the other hand, is very much just a bunch of if-else/logical conditions, much like regular programming. You don't need to think too much about the whole "symbolic" part of it. The main/big breakthrough is that you had a lot of clever "search algorithms" and a lot of computation power relative to before.
Point being, is just that symbolic AI was the main research program at the time, and people didn't really bother with "connectionist" methods.

I think you should emphasize that Deep Blue started being developed in the 80s early 90s, but it was only in 1996-1997 that it beat Kasparov and, at that time, there was already active research in neural networks (e.g. LSTMs were developed during that period).

I'm not sure any intelligent mechanism can be entirely free of symbolic logic.

Even where a decision is statistically based, a machine that takes actions must include some form of:
IF {some condition}
THEN {some action}

As to the popularity of newly proven statistical AI methods (ANN and genetic algorithms), this derives from the greater utility they demonstrate at ever more complex problems compared to expert systems ("good old fashioned AI") for problems that do not have a mathematical solution.
(i.e. the statistical approach for 3x3 Tic-tac-toe is overkill and unnecessary b/c the 3x3 form is a solved game. But for larger-order gameboards $m*m$ or $m*n$, the n-dimensional game, $m^n$, barring a mathematical solution that applies to every variation, ANN is way to go.)
The main issue with expert systems, no matter how complex, is "brittleness"—inability to adapt to changes without human programmer intervention.  As conditions change, the mechanism demonstrates diminishing utility, or simply "breaks" (invalid input as an example.)

The amount of human effort required to create DeepBlue was monumental, which is why it took decades to achieve it goal, funded by a large corporation with a history of basic research.

Compare to a simple ANN that can be trained to achieve the same goal in an extremely short timeframe.
It's possible future artificial general intelligences of whatever strength would involve statistical AI programming and adapting its own symbolic functions.
Finally, symbolic AI is still vastly more widely implemented than statistical AI, in that all of the basic functions of modern computing, all of the mathematical functions, all traditional software and apps, utilize symbolic logic, even if the high level function is statistically driven. This will likely always be the case.
Thus, in terms of what method is best for a given problem, it really depends on the nature/structure of the problem, it's solvability or even decidability, as well as its tractability.

You might also ask if there's any particular reason why we would use a neural net. If we're to train a neural net to play chess, we need to be able to:
1. Feed it positions as input vectors (easy enough),
2. Decide on an output format. Perhaps a distribution over possible moves (but then, how to represent that such that the meaning of a specific output cell doesn't change drastically based on the board state?  Or perhaps instead, we let the resulting board state after a candidate move be the input, and let the output be a score that represents the desirability of that state. That'll require exponentially more forward/backprop passes, though.
3. Provide it with an error signal to whatever output vector it produces. This is the really tricky bit, since we don't know whether a given move will result in victory until the very end.
Do we play the game to the very end, storing decisions as we go, and then at the end, replay each input, feeding it an error signal if we lost? This will give the same error to the good moves as to the ones that actually lost the game. With enough games, this will work, since the good moves will get positive feedback a bit more often than negative, and vice versa for the bad ones. But it'll take a lot of games. More than a human is going to be willing to play.  We can have different networks learn by playing against each other, but not on 1996 hardware.
Do we instead provide a score based on another heuristic of the board state? In that case, why not just use minimax? It's provably optimal for a given heuristic up to however many moves deep we look, and it doesn't need training.

Add to this the fact that if we don't choose a good representation at each of these steps, there's a good chance that the network will only learn the positions it's specifically been trained on, rather than generalizing to unseen states, which is the main reason for using a neural network in the first place.
It's certainly possible to use neural nets to learn chess (DeepMind's approach can be found here, for instance), but they're not a natural fit to the problem by any means. Minimax, by contrast, fits the problem very well, which is why it was one of the techniques used by Deep Blue. Neural nets are an amazing tool, but they're not always the right tool for the job.
Addendum:
I didn't stress this point much, since K.C. already brought it up, but training large neural nets require us to perform a huge number of matrix vector multiplications, and this wasn't especially practical before GPUs got powerful and cheap.

Maybe you are not aware of Alpha Zero, but it's probably a good idea that you look at it and mention it, as it uses neural networks to play chess too. See e.g. Mastering Chess and Shogi by Self-Play with a General Reinforcement Learning Algorithm.

@nbro I suspected the DeepMind people would have done something (since if they can manage Go, chess can't be far behind), but didn't recall the paper. I've added a mention of it in the relevant part of the answer. Of course, it should be pointed out that even now, Google is one of the few organizations that has the hardware to train something like Alpha Zero (although it'll probably run fine on cheaper hardware), whereas Stockfish (one of the other top chess engines) doesn't require training, and will run on fairly normal hardware (although it'll be better/faster on better hardware).


text:
Is a reward given at every step or only given when the RL agent fails or succeeds?
In reinforcement learning, an agent can receive a positive reward for correct actions and a negative reward for wrong actions, but does the agent also receive rewards for every other step/action?

This question seems to be very similar to Can reinforcement learning be used for tasks where only one final reward is received?.

In reinforcement learning (RL), an immediate reward value must be returned after each action, along with the next state. This value can be zero though, which will have no direct impact on optimality or setting goals.
Unless you are modifying the reward scheme to try and make an environment easier to learn (called reward shaping), then you should be aiming for a "natural" reward scheme. That means granting reward based directly on the goals of the agent.
Common reward schemes might include:

+1 for winning a game or reaching a goal state granted only at the end of an episode, whilst all other steps have a reward of zero. You might also see 0 for a draw and -1 for losing a game.

-1 per time step, when the goal is to solve a problem in minimum time steps.

a reward proportional to the amount of something that the agent produces - e.g. energy, money, chemical product, granted on any stop where this product is obtained, zero otherwise. Potentially a negative reward based on something else that the agent consumes in order to produce the product, e.g. fuel.


text:
What is the Turing test?
I'm looking for intuition in simple words but also some simple insights (I don't know if the latter is possible). Can anybody shed some light on the Turing test?

The Turing test is a test proposed by Alan Turing (one of the founders of computer science and artificial intelligence), described in section 1 of paper Computing Machinery and Intelligence (1950), to answer the question

Can machines think?

More precisely, the Turing test was originally framed as an interactive quiz (denoted as the imitation game by Turing) where a human interrogator $C$ asks multiple questions to two entities, $A$ (a computer) and $B$ (a human), which stay in different rooms than the room of the interrogator, so the interrogator cannot see them, in order to figure out which one is $A$ (the computer) and which one is $B$ (the human). $A$ and $B$  can only communicate in written form or any form that avoids them being easily recognized by $C$. The goal of the computer is to fool the interrogator and make him/her believe that it is a human and the goal of $B$ is to somehow help him and make him believe that he/she is the actual human.
If the computer is able to fool the interrogator and make him/her believe that it is a human, then that would be an indication that machines can think. However, note that even Turing called this game the imitation game, so Turing was aware of the fact that this game would only really show that a machine can imitate a human (unless he was using the term "imitation" differently than its current meaning).
Nowadays, there are different variations of the Turing test and some people use the term Turing test to refer to any test that attempts to tell humans and computers apart. For example, some people consider the CAPTCHA test a Turing test. In fact, CAPTCHA stands for "Completely Automated Public Turing Test To Tell Computers and Humans Apart".
The Turing test also has different interpretations and meanings. Some people think that the Turing test is sufficient to test that a machine can actually think and possesses consciousness, other people think that this only tests human-like intelligence (and there could be other intelligences) and some people (like me) think that this test is limited and only tests the conversational skills (and maybe other properties too) of the machine. Even Turing attempted to address these issues in the same paper (section 2), where he discusses some advantages and disadvantages of his imitation game. In any case, we can all agree that, if machines (in particular, programs like Siri, Google Home, Cortana, or Alexa) were always able to pass the Turing test, they would be a lot more useful, interesting and entertaining than they are now.

According to Wikipedia

The "standard interpretation" of the Turing test, in which player C, the interrogator, is given the task of trying to determine which player – A or B – is a computer and which is a human. The interrogator is limited to using the responses to written questions to make the determination.

Please, next time, if you copy something from another site or another person, you should use the symbol > before the copied text to indicate that you're quoting it.