text:
Does there exist a resource for vetting banned words for chatbots?
So, Tay the racist tweeter bot... one thing that could have prevented this would have been to have a list of watchwords to not respond to, with some logic similar to foreach (word in msg) {if (banned_words.has(word)) disregard()}.
Even if that wouldn't, what I'm getting at is obvious: I am building a chatterbot that must be kid-friendly. For my sake and for the sake of whoever finds this question, is there a resource consisting of a .csv or .txt of such words that one might want to handle? I remember once using a site-blocking productivity extension that had visible its list of banned words; not just sexually charged words, but racial slurs, too.

Certainly, though, it could be useful to ban more obvious words? There is zero excuse for using, for example, the more strident and unambiguous racial slurs.

I have not found one other than scraping a few pages from Urban Dictionary, I built my list via crowdsourced style and got a number of interesting words I had not considered.
Start with the worst words you can think of, then try slang and accidental or on purpose misspellings of them


text:
Inner working of Bidirectional RNNs
I'm trying to understand how Bidirectional RNNs work.
Specifically, I want to know whether a single cell is used with  different states, or two different cells are used, each having independent parameters.
In pythonic pseudocode,
Implementation 1:
cell = rev_cell = RNNCell()
cell_state = cell.get_initial_state()
rev_cell_state = rev_cell.get_initial_state()
for i in range(len(series)):
    output, cell_state = cell(series[i], cell_state)
    rev_output, rev_cell_state = rev_cell(series[-i-1], rev_cell_state)
    final_output = concatenate([output, rev_output])

Implementation 2:
cell = RNNCell()
rev_cell = RNNCell()
cell_state = cell.get_initial_state()
rev_cell_state = rev_cell.get_initial_state()
for i in range(len(series)):
    output, cell_state = cell(series[i], cell_state)
    rev_output, rev_cell_state = rev_cell(series[-i-1], rev_cell_state)
    final_output = concatenate([output, rev_output])

Which of the above implementations is correct? Or is the working of Bidirectional RNNs completely different altogether?

The second implementation looks more correct and inline with how Bidirectional is defined. Specifically, bidirectionality doen't change the forward/backward logic of either direction, and just merges (concat/sum/...) the outputs of forward/backward at a matching timestep t.
You can check how Keras implements it here. There are distinct self.forward_layer and self.backward_layer that are initialized separately.
Your for loop doesn't look ok though. To calculate the output at time step 0 you'd have to calculate forward(0) and backward(n), which means you have to run backward on all the samples first. In practice, each direction is calculated separately and the results are merged afterwards. Check the implementaion in Keras here.

source: Stack Exchange

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

sort: votes


text:
CNN High Variance across multiple trained models, what does it mean?
Background:
I have a 2D CNN model that I am applying to a regression task with some uniquely extracted spectrograms. The specifics of the data set are mostly irrelevant and very domain specific so I won't go into detail, but it is essentially just image classification with a MSE loss function for each label and a unique image of 100x4000. When I re-train the model from scratch multiple times then provide it my testing data set, it has predictions that vary significantly across each iteration and thus a high variance. Supposedly the only difference between a trained model versus another would be the random initialization of weights and the random train/validation split. I feel that the train/validation split has been ruled out by when I've done k-fold cross validation and my model has done very good for all segments of my train/validation splits and acquired good results for the validation in each split. But these same models persist to have high variance in the test data set.
Question:
If I am seeing a high variance for the predictions from my trained model across multiple different runs of re-training, what do I attack first to reduce my variance on my predictions for my test data set?
I've found many articles talking about bias and variance in the data set but not as much criticism directed towards model design. What things can I explore in my dataset or model design, and/or tools I can use to strengthen my model? Does my model need to be bigger/smaller?
Ideas/Solutions:
A few Ideas I'd like to acquire some criticism for.

Regularization applied to model such as L1/L2 Regularization, dropout, or early stopping.
Data augmentation applied to dataset (inconveniently not an option right now, but in a more general scenario it could be).
Bigger or smaller model?
Is the random initialization of weight actually very important? Maybe train multiple models and take the average of their collective answers to get the best prediction on real world data (test set).

Personal Note:
I have had experience with all these items before on other projects and with personal projects and have some moderate confidence justifying regularization and data augmentation. However, I lack some perspective as to any other tools that might be useful to explore the cause of model variance. I wanted to ask this question here to start a discussion in a general sense of this problem.
Cheers
EDIT: CLARIFICATION. When I say 'variance' I mean specifically variance across models, not variance of predictions from 1 trained model across the test set. Example: Instead lets say I am trying to predict a value somewhere between 1 and 4 (expected_val=3). I train 10 models to do this and 4 of the models accurately predict 3 with a VERY low standard deviation across all the test set samples. Thus a low variance and high accuracy/precision for these 4 models. But the other 6 models predict wildly and some predict 1 very confidently every time and the others could be 4. And I've even had models that predicted negative values even though I have NO training or testing samples that have negative labels.

Firstly if you're doing spectrogram classification, you'd probably want to use a loss function like cross entropy. That would give you less "high-variance" like results when you're calculating your evaluation metrics.
About your ideas:

Dropout and early stopping would be enough
Data augmentation with speech is quite helpful, and there are a few libraries to help you with volume/speed/noise augmentation. Volume/speed augmentation is actually really important and you'd want to do it anyway for decent results in production. Speech processing is sometimes a bit tricky, in the sense that what we hear may not be what ends up in the spectrogram and parameters like noise, recording setup, encoding, accent end up causing a domain-mismatch (covariate shift)
In general, a smaller model (less parameters) helps with high variance. Start with small and simple models first, make sure eval metrics look ok, and then try larger models.
Random initialization doesn't really affect the results in a systematic way. You can indeed ensemble predictions of models trained with different initialization; that does help with variance but don't expect a lot of difference. The gain is not worth the computation cost for models applied in practice (ie not kaggle)

Other ideas:

Check that you shuffle data properly in train/test, and between folds
Do some error analysis on the mis-predicted test samples, do they have something in common. Check the label distribution in your dev/test set.
If the test set was captured in a process different from your dev set (total blind), don't expect a robust performance. In general, speech recognition is really data hungry with a decent "generic* model needing hundreds of hours of recording from different domains (tv, news, movies, telephone, lecture, echo, etc.).

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


text:
How to choosing the random value for parameter w in deep learning network?
I did watch the course DeepLearning of Andrew Ng and he told that we should create parameter w small like:
parameters['W' + str(l)] = np.random.randn(layer_dims[l], layer_dims[l - 1]) ** 0.001

But in the last application assignment. They choose another way:
layers_dims = [12288, 20, 7, 5, 1]
def initialize_parameters_deep(layer_dims):
    np.random.seed(3)
    parameters = {}
    L = len(layer_dims)

    for l in range(1, L):
        parameters['W' + str(l)] = np.random.randn(layer_dims[l], layer_dims[l - 1]) / np.sqrt(layer_dims[l - 1])
        parameters['b' + str(l)] = np.zeros((layer_dims[l], 1))
        assert (parameters['W' + str(l)].shape == (layer_dims[l], layer_dims[l - 1]))
        assert (parameters['b' + str(l)].shape == (layer_dims[l], 1))
    return parameters

And the result of this way is very good but if I choose w like the old above, It's just have 34% correct!
So do you can explain ?

Hi and welcome to AI SE! You accepted the answer https://ai.stackexchange.com/a/20242/2444, but if you feel that the answer is also valuable, you should also upvote it by clicking on the arrow that points upwards close to the answer. In this way, you encourage the user to provide more answers!

Weights initialisation is strictly related to the vanishing/exploding gradient problem. For a complete explanation, please check this awesome page (also from deeplearning.ai). Here I'll summarise the main concepts:

initialising weight all to zero will cause all weights to have the same derivative value with respect to the loss function, hence the network would be incapable of learning anything.
initialising to zero the biases has no drawback since they are constants (no effect at all when computing the derivative anyway).
initialising weights with too high or too small values will lead to an exploding gradient (oscillating gradient values without convergence) or a vanishing gradient (small gradient values variation that converge before reaching the loss global minimum).

In order to avoid these problems, a method called Xavier initialisation has been proposed: the weights should be initialised in such a way that they will generate activations scores with a distribution that has:

Mean 0
Constant variance across layers (i.e. no vanishing/exploding)

The value "np.sqrt(layer_dims[l - 1])" pup up when imposing the second constrain.  For a formal prove check the page I linked. To grasp the concept just focus on the fact that the variance of the weights of a layer depends on the amount of nodes of the previous layer. This mean that for layers preceded by layers with a big amount of hidden nodes, the weights will be initialised with a small variance, and this is ok cause we don't want a small bunch nodes to have stronger influence on the subsequent activations. But in layers which instead are preceded by layers with a small amount of nodes, it's ok to allow the weights to vary more.


text:
How is a validation set used to tune the hyperparameters in a non-biased way, if the new models depends on the values of these?
I've built a neural network from the scratch, choosing arbitrary numbers for the hyperparameters: learning rate, number of hidden layers and neurons for these, number of epochs and size of mini batches. Now that I've been able to build something potentially useful (~93% of accuracy with test data, unseen by the model before), I want to focus on hyperparameter tuning.
The conceptual difference between training and validation sets is clear and makes a lot of sense. It's obvious that the model is biased towards the training set, so it wouldn't make sense to use it to tune the hyperparameters, nor for evaluating its performance.
But, how can I use the validation set for this, if changing any of the parameters enforces me to rebuild a new model again? The final prediction depends on the values of X number of MxN matrices (weights) and X number of N vectors (biases), whose values depend on the learning rate, batch size and number of epochs; and whose dimensions depends on the number and size of hidden layers. If I change any of these, I'd need to rebuild my model again. So I'd be using this validation set for training different models, ending up as in the first step: fitting a model from the scratch.
To sum up: I fall in a recursive problem in which I need to fine tune the hyperparameters of my model with unseen data, but changing any of these hyperparameters implies rebuilding the model.

This is a standard ML problem: changing hyper-parameters changes the performance of the whole model. Ideally, you'd be cross-validating hyper-parameter choices, not merely comparing on a static validation set. That being said you need to be careful with hyper-parameter optimization because you could overfit these to the peculiarities of your validation set ; cross-validation helps to some extent but really what helps is having a test set that you hardly ever test against. Ideally never before you've chosen your HPs with (cross-) validation. And test-set performance will indicate how much your  HP-optimization procedure was biased.
I'm afraid training from scratch is your only solution. This does not however mean that you have to train until the end and many hyper-parameter optimization techniques out there will help you stop training early enough so you don't waste computational resources on HPs which are not worth it. A good starting point would be this blog post by Criteo's Aloïs Bissuel: Hyper-parameter optimization algorithms: a short review

The importance of having a totally separate test set is very crucial. Once you start to use the validation set performance as a measure to use to tune hyper parameters you are biasing your network to work well on the validation set so it can no longer be relied on as a true measure of performance. Eventually if you use your test set too often then adjust hyper parameters to improve performance on the test set you wind up in the same boat. I have actually used several test sets to try to avoid this trap.


text:
How to add weights to one specific input feature to ensure fair training in the network?
I am trying to create a multiclass product-rating network based on product reviews and other input features. Two of the other input features are "product category" and "gender". However, I want to avoid unfair bias in the classification task between male/female. Since some product categories are more likely to be reviewed by males or females (hence, not balanced), I am seeking for an approach to solve this "imbalance"-like issue.
The options and things that I consider at the moment are:

Downsample the training examples in each product category to balance for gender
Add weights to the training examples for gender, or
Add weights to the loss function (either log-likelihood or cross-entropy)

Even though downsampling might be the easiest option, I would like to explore the options of adding weights in the network in some way. However, most literature are only discussing adding weights to the loss function in order to solve for imbalanced data related to the target value (which is not the issue that I am addressing).
Can someone help me or point me in the right direction to solve this challenge?

Welcome to SE:AI!

Thank you @DukeZhou! Do you have any idea how I can solve my question?

unfortunately, I'm not the right guy to ask.  (I'm sort of the itinerant philosopher on SE:AI)

No worries! ;-) Anyone else that could help me?

I think your approach to tackle this as an imbalanced problem is correct. The easiest thing you could do is to add weights to the samples, during training, so that the model "pays more attention" to the under-represented class.
There are also a couple of other ways for this to be done: oversampling and undersampling, but initially, I'd focus on adding weights, since its easier to implement.

Thanks! I am pretty new to this and I am reading about it now. I stumbled upon the technique of importance sampling/weighting. Would you use this to add weights to the samples? If not, how would you do this? And will each sample weight be added to the loss function in this case? Maybe I haven't explained this in a clear way, sorry! But my challenge is that I don't want to focus on imbalanced gender in the entire dataset but per product category (which is another input feature in my model). Thanks for your help again!

If you add weights to each sample, you have the degree of freedom to weigh them as you like. A sample from a male that belongs to a female-dominated category could get a high weight, while a female item from the same category could get a lower one. What I'm trying to say is that you can weigh your samples per gender and category if you want to. The importance sampling technique I'm aware of is unrelated, but it's plausible that the same name is used for different techniques.


text:
Train a competitive layer on nonnormalized vectors using LVQ technique
How can we train a competitive layer on non-normalized vectors using LVQ technique ?
an example is given below from Neural Network Design (2nd Edition) book
The net input expression for LVQ networks calculates the distance between the input
and each weight vector directly, instead of using the inner product. The result is that the
LVQ network does not require normalized input vectors. This technique can also be
used to allow a competitive layer to classify non-normalized vectors. Such a network is
shown in figure below.

Use this technique to train a two-neuron competitive layer on the (non-normalized)
vectors below, using a learning rate $\alpha=0.5$
$p_1=\begin{bmatrix}
1 \\
1
\end{bmatrix}, p_2=\begin{bmatrix}
-1 \\
2
\end{bmatrix}, p_3=\begin{bmatrix}
-2 \\
-2
\end{bmatrix}$
Present the vectors in the following order : $p_1, p_2, p_3, p_2, p_3, p_1$
Initial weights : $W_1=\begin{bmatrix}
0 \\
1
\end{bmatrix}, W_2=\begin{bmatrix}
1 \\
o
\end{bmatrix}$

We have 2 classes , 1 subclass for each class
\begin{equation}
    W^2=\begin{vmatrix}
1 & 0\\
0 & 1\\
\end{vmatrix}
\end{equation}
$p_1$:
\begin{equation}
    \alpha^1=compet(n^1)=compet\begin{vmatrix}
||w_1-p_1||\\
||w_2-p_1||\\
\end{vmatrix} = compet\begin{vmatrix}
||\begin{vmatrix}
0 & 1\\
\end{vmatrix}^T-\begin{vmatrix}
1 & 1\\
\end{vmatrix}^T||\\
||\begin{vmatrix}
1 & 0\\
\end{vmatrix}^T-\begin{vmatrix}
1 & 1\\
\end{vmatrix}^T||\\
\end{vmatrix}=
compet(\begin{vmatrix}
1\\
1\\
\end{vmatrix}) = \begin{vmatrix}
1\\
0\\
\end{vmatrix})
\end{equation}
\begin{equation}
   \alpha^2=W^2\cdot\alpha^1= \begin{vmatrix}
1 & 0\\
0 & 1\\
\end{vmatrix}\begin{vmatrix}
1\\
0\\
\end{vmatrix}=\begin{vmatrix}
1\\
0\\
\end{vmatrix}
\end{equation}
\begin{equation}
    W_1(1) = W_1(0) + \alpha\cdot(p_1-W_1(0))=\begin{vmatrix}
0\\
1\\
\end{vmatrix}+0.5\cdot(\begin{vmatrix}
1\\
1\\
\end{vmatrix}-\begin{vmatrix}
0\\
1\\
\end{vmatrix})=\begin{vmatrix}
0\\
1\\
\end{vmatrix}+\begin{vmatrix}
0.5\\
0\\
\end{vmatrix}=\begin{vmatrix}
0.5\\
1\\
\end{vmatrix}
\end{equation}
$p_2$ :
\begin{equation}
    \alpha^1=compet(n^1)=compet\begin{vmatrix}
||w_1-p_2||\\
||w_2-p_2||\\
\end{vmatrix} = compet\begin{vmatrix}
||\begin{vmatrix}
0.5 & 1\\
\end{vmatrix}^T-\begin{vmatrix}
1 & 2\\
\end{vmatrix}^T||\\
||\begin{vmatrix}
1 & 0\\
\end{vmatrix}^T-\begin{vmatrix}
1 & 2\\
\end{vmatrix}^T||\\
\end{vmatrix}=
compet(\begin{vmatrix}
1.8027756377\\
2.8284271247\\
\end{vmatrix}) = \begin{vmatrix}
0\\
1\\
\end{vmatrix})
\end{equation}
\begin{equation}
   \alpha^2=W^2\cdot\alpha^1= \begin{vmatrix}
1 & 0\\
0 & 1\\
\end{vmatrix}\begin{vmatrix}
0\\
1\\
\end{vmatrix}=\begin{vmatrix}
0\\
1\\
\end{vmatrix}
\end{equation}
wrong class
\begin{equation}
    W_2(1) = W_2(0) - \alpha\cdot(p_2-W_2(0))=\begin{vmatrix}
1\\
0\\
\end{vmatrix}-0.5\cdot(\begin{vmatrix}
-2\\
2\\
\end{vmatrix}=\begin{vmatrix}
2\\
-1\\
\end{vmatrix}
\end{equation}
$p_3$ :
\begin{equation}
    \alpha^1= compet\begin{vmatrix}
||\begin{vmatrix}
0.5 & 1\\
\end{vmatrix}^T-\begin{vmatrix}
-2 & 2\\
\end{vmatrix}^T||\\
||\begin{vmatrix}
2 & -1\
\end{vmatrix}^T-\begin{vmatrix}
-2 & 2\\
\end{vmatrix}^T||\\
\end{vmatrix}=
compet(\begin{vmatrix}
70\\
5\\
\end{vmatrix}) = \begin{vmatrix}
1\\
0\\
\end{vmatrix})
\end{equation}
\begin{equation}
   \alpha^2=W^2\cdot\alpha^1\begin{vmatrix}
1\\
0\\
\end{vmatrix}
\end{equation}
wrong class
\begin{equation}
    W_1(2) = W_1(1) - \alpha\cdot(p_3-W_1(1))=\begin{vmatrix}
0.5\\
0\\
\end{vmatrix}-0.5\cdot(\begin{vmatrix}
-2.5\\
1\\
\end{vmatrix}=\begin{vmatrix}
1.75\\
0.5\\
\end{vmatrix}
\end{equation}
$p_2$ :
\begin{equation}
    \alpha^1=compet(n^1)= compet\begin{vmatrix}
||\begin{vmatrix}
1.75 & 0.5\\
\end{vmatrix}^T-\begin{vmatrix}
-1 & 2\\
\end{vmatrix}^T||\\
||\begin{vmatrix}
2 & -1\
\end{vmatrix}^T-\begin{vmatrix}
-1 & 2\\
\end{vmatrix}^T||\\
\end{vmatrix}=
compet(\begin{vmatrix}
3.13\\
4.24\\
\end{vmatrix}) = \begin{vmatrix}
1\\
0\\
\end{vmatrix})
\end{equation}
\begin{equation}
   \alpha^2=W^2\cdot\alpha^1\begin{vmatrix}
1\\
0\\
\end{vmatrix}
\end{equation}
\begin{equation}
    W_1(3) = W_1(2) - \alpha\cdot(p_2-W_1(2))=\begin{vmatrix}
1.75\\
0.5\\
\end{vmatrix}+0.5\cdot(\begin{vmatrix}
-2.75\\
1.5\\
\end{vmatrix}=\begin{vmatrix}
0.375\\
1.25\\
\end{vmatrix}
\end{equation}
$p_3$ :
\begin{equation}
    \alpha^1=compet(n^1)= compet\begin{vmatrix}
||\begin{vmatrix}
0.375 & 1.25\\
\end{vmatrix}^T-\begin{vmatrix}
-2 & 2\\
\end{vmatrix}^T||\\
||\begin{vmatrix}
2 & -1\
\end{vmatrix}^T-\begin{vmatrix}
-2 & 2\\
\end{vmatrix}^T||\\
\end{vmatrix}=
compet(\begin{vmatrix}
2.95\\
5\\
\end{vmatrix}) = \begin{vmatrix}
1\\
0\\
\end{vmatrix})
\end{equation}
\begin{equation}
   \alpha^2=W^2\cdot\alpha^1\begin{vmatrix}
1\\
0\\
\end{vmatrix}
\end{equation}
wrong class
\begin{equation}
    W_1(4) = W_1(1) - \alpha\cdot(p_3-W_1(3))=\begin{vmatrix}
0.375\\
1.25\\
\end{vmatrix}-0.5\cdot(\begin{vmatrix}
-2.375\\
0.75\\
\end{vmatrix}=\begin{vmatrix}
1.5625\
0.875\\
\end{vmatrix}
\end{equation}
p_1 :
\begin{equation}
    \alpha^1=compet(n^1)= compet\begin{vmatrix}
||\begin{vmatrix}
1.5625 & 0.875\\
\end{vmatrix}^T-\begin{vmatrix}
1 & 1\\
\end{vmatrix}^T||\\
||\begin{vmatrix}
2 & -1\
\end{vmatrix}^T-\begin{vmatrix}
1 & 1\\
\end{vmatrix}^T||\\
\end{vmatrix}=
compet(\begin{vmatrix}
0.57\\
2.23\\
\end{vmatrix}) = \begin{vmatrix}
1\\
0\\
\end{vmatrix})
\end{equation}
\begin{equation}
   \alpha^2=W^2\cdot\alpha^1\begin{vmatrix}
1\\
0\\
\end{vmatrix}
\end{equation}
\begin{equation}
    W_1(5) = W_1(4) - \alpha\cdot(p_1-W_1(4))=\begin{vmatrix}
1.5625\\
0.875\\
\end{vmatrix}+(\begin{vmatrix}
-0.28125\\
0.0625\\
\end{vmatrix}=\begin{vmatrix}
1.28125\
0.9375\\
\end{vmatrix}
\end{equation}


text:
Neural networks with internal dynamics in the state-space form
Neural networks with feedback (Hopfield, Hamming, etc.) differ from ordinary neural networks (multilayer perceptrons, etc.), which turns them into a dynamic element with its own internal dynamics (if we consider them as a separate dynamic link). The following question naturally arises - is it possible to represent them in the form of state spaces?
Nuance is that feedback is created by introducing a delay element, which means recording a neural network exclusively in a discrete form. Is continuous recording possible? What acts as matrices A, B, C, D? How does the presence of nonlinear activation functions affect?
The only more or less useful information that I managed to find is in this article:
On neural networks in identification and control of dynamic systems. 3.2 Paragraph. Page 8
But my assumptions are only confirmed there, which does not clarify the situation.
In general, if someone has come across this and can assist in studying the issue, please share links, possibly examples, etc.

I think that the book "Neural Networks and Learning Machines" of Haykin can help you. In his book the chapter 13 is about neural dynamics, and there are some examples of how analise the dynamics of network.

This is a very comprehensive book. I read the chapter "Neurodynamics". Some old questions were gone, but new ones appeared instead. In general, I feel that this material needs to be started. Thank you for the answer, I will think about how to adapt it to my tasks.


text:
Is there a notion of generalization in unsupervised learning?
I've been learning a little bit about generalization theory, and in particular, the PAC (and PAC-Bayes) approach to thinking about this problem.
So, I started to wonder if there is an analogous version of "generalization" in Unsupervised Learning? I.e., is there a general framework that encapsulates how "good" an unsupervised learning method is? There's reconstruction error for learning lower dimensional representations, but what about unsupervised clustering?
Any ideas?

Cross-posted: https://ai.stackexchange.com/q/20382/1794, https://cstheory.stackexchange.com/q/46660/5038.  Please do not post the same question on multiple sites.

In the paper Generalization in Unsupervised Learning (2015), Abou-Moustafa and Schuurmans develop an approach to assess the generalization of an unsupervised learning algorithm $A$ on a given dataset $S$ and how to compare the generalization ability of two unsupervised learning algorithms $A_1$ and $A_2$, for the same learning task.
They first provide a more abstract and general definition of an unsupervised learning algorithm and loss function. Then they define the expected risk, empirical risk and generalization gap in a similar way to the case of supervised learning. Finally, they derive an upper bound on $A$'s expected loss.
Of course, you should read the paper for more details. Specifically, section 2 (page 3) describes their setting in detail.


text:
Do policy independent state and action values exist in reinforcement learning?
The state value function $V(s)$ is defined as the expected return starting in state $s$ and acting according to the current policy $\pi(a|s)$ till the end of the episode. The state-action values $Q(s,a)$ are similarly dependent on the current policy.
Is it also possible to get a policy independent value of a state or an action?
Can the immediate reward $r(s,a,s')$ be considered a noisy estimate of the action value?

Do policy independent state and action values exist in reinforcement learning?

No. They do not exist, because in order to progress in any MDP and receive any reward - i.e. to get any measure of value - you must take an action. Any consistent means of selecting actions is a policy, and the nature of that policy impacts which transitions and rewards you expect to observe, which in turn affects the expected value. Inconsistent means of selecting actions would have no meaning with respect to "expected future return", they would just be measurements that you made in the past.
The closest you can get to a no-policy definition would be values with respect to "special" policies that apply in general to nearly all MDPs:

Value functions for the uniformly distributed random policy.
Value functions for any optimal policy (if there is more than one optimal policy, then all the value functions for them will be equal).
Value functions for any "inverse optimal" policy - i.e. the policy that has lowest possible return. This one is not so useful, although it exists theoretically.

The first two can be useful measurements of an MDP. Although the uniform random policy might not be the best, it encapsulates the situation where the agent has absolutely no knowledge of the MDP, and can be a baseline for comparison. The optimal value functions are often a target for learning algorithms, and sometimes you can calculate bounds or even exact targets for these independently of the learning process, to measure how well an algorithm performs on some test MDP.

Can the immediate reward $r(s,a,s')$ be considered a noisy estimate of the action value?

No. Using that notation of the function, it is typically already the expected immediate reward. It is entirely independent of reward seen in any other transitions or time steps, so is systematically incorrect as an estimate for future return in many cases - the only exception being if you know all future rewards will be precisely $0$. So it is an unbiased estimate of an action value if $s'$ is a terminal state.
Immediate reward is also a good estimate of an action value if the discount factor $\gamma = 0$. However, that requires you to define the problem as solving for immediate rewards only, which is not usually a free choice when trying to optimise the behaviour of the agent.

So a policy independent action-value contradicts the definition of the RL problem, which aims at optimizing the expected return? The agent has to choose actions that are good in the long run and not in the short term. And setting the discount factor $\gamma$ to zero would optimize for immediate reward which probably will result in a policy not performing well on the task.

@RayWalker: That is a reasonable summary. I would add that you don't have to attempt to optimise an expected return in RL, but it is probably the most common application. Other goals include might include measuring performance of some fixed policy, or discovering aspects of the model used by some other system (e.g. inferring the reward model that an agent is using by observing its behaviour - part of inverse reinforcement learning)

Great to learn that we might actually choose another goal to optimize for with reinforcement learning!

You inspired another question  you might find interesting.


text:
Can we use a neural network that is trained using Reinforcement Learning for dynamic game level difficulty designing in realtime?
I am a newbie to Machine Learning and AI. As per my understanding, with the use of reinforcement learning
(reward/punishment environment), we can train a neural network to play a game. I would like to know, whether it possible to use this trained model for deciding the difficulty of the next game level dynamically in realtime according to a player's skill level? As an example, please consider a neural network is trained using Reinforcement Learning for playing a mobile game (chess/puzzle, etc.). The game is not consists of a previously designed static set of game levels. After the training, can this model use to detect a particular player's playing style(score, elapsed time) to dynamically decide the difficulty of the next game level and provide customized game levels for each player in realtime?
Thank you very much and any help will be greatly appreciated.

"can this model use to detect a particular player's playing style..to dynamically decide the difficulty" -marginally possible but not practical. Anything more interesting then basic cumulative win/loss score require a lot of data(records of played games) and a lot of computation

@mirror2image, Thank you very much for the clarification.

There have been many researches in dynamic difficulty adjustment (DDA). I see this one is quite explaining: AI for Dynamic Difficulty Adjustment in Games. However, there are many factors when we are trying to do dynamic difficulty adjustment. As explained in paper above, one major problem is it is sometimes hard to make sure the created model will still deliver the intended experience.
You can also read this paper about game design and DDA on ace05The Case for Dynamic Difficulty Adjustment in Games .
So for short, you can use neural network -- or other learning methods -- to do dynamic difficulty adjustment. But it's more about game design and experience impact of your DDA.


text:
Can optimizing for immediate reward result in a policy maximizing the return?
The goal of a reinforcement learning agent is to maximize the expected return which is often a discounted sum of future rewards. The return indeed is a very noisy random variable as future rewards depend on the state-transition-probabilities and the often stochastic policy. Lots of trajectories have to be sampled to approximate its expected value.
The immediate reward indeed does not have these dependencies. Therefore the questions:
If we train a policy to maximize the immediate reward, will it also perform well in the long term? What properties would the reward function need to fulfill?

If we train a policy to maximize the immediate reward, will it also perform well in the long term?

In general, no. The delay of long term reward in real world problems, and often a lack of easy-to-compute heuristics, is a key motivation for developing reinforcement learning in the first place.
It is easy to construct a counter-example to demonstrate this. Any state where the transitions into it are high and positive, but the transitions out of it are higher and negative would "trap" an agent that only considered immediate reward. More complex traps include high immediate gains but ending an episode vs lower gains that continue for longer.
Many real-world environments have sparse rewards where it is not possible to tell the difference between two action choices by immediate reward, but the consequences of being in one part of the state space rather than another early in a trajectory are critical. Consider any two-player strategy board game for instance, where the only goal is to win at the end. Only the last move in such a game is associated with an immediate reward, but there are often important differences between early moves.

What properties would the reward function need to fulfill?

In all states, the expected immediate reward for taking the correct long term action would need to be higher than the expected immediate reward for any other action choice.
Solving a problem framed in this way could be done with discount factor $\gamma=0$. If the action choices were always the same and valid in each state, then the problem could also be simplified to a contextual bandit, where the fact that the choices exist within a larger trajectory is not relevant.
In practice you can construct environments like this. Simple ones are possible to do manually. Doing that is similiar to adding a heuristic function for search, but with different restrictions. For many search algorithms, admissible heuristic functions are allowed to over-estimate future gains (or under-estimate costs), because a planning/search algorithm will resolve longer-term differences. In your case, you can maybe consider stochastic reward functions, but the expected reward for the correct action must always be highest.
Needing to know the correct optimal action in the first place is clearly a circular problem - if you knew it already you would have no need to perform reinforcement learning to discover the optimal policy. An exception might be if you constructed an easy environment in order to test an algorithm, and prove that it could find the optimal policy. Although even then usually you are interested in the algorithm solving a harder variant of your problem than one you have deliberately constructed to be easy.
In brief, there is no way to create a shortcut here and avoid the need to solve a harder RL problem.

A good action is always the one that is good in the long-term, so using the immediate short-term reward will not help to find the optimal action. An exception would be a reward function that already rates the long-term effect of an action, but this seem to be hard and is the reason why we need RL.
Thank you for the always great, detailed, and deeply insightful answers!

Can previous actions actually influence the reward of the current action? It seems they can as in your example with the game, where the immediate reward is bigger zero only for the last action. It definitely makes sense but feels like a contradiction of the Markov Property. Can you please helpt me out?

When we use RL to train an agent to follow reference trajectories, do you think we can estimate the long term effect of an action by looking at the current state and the reference trajectory?

Previous actions do influence the reward of a current action - but if your MDP has the markov property, that influence is encapsulated by the state - in some games this is very direct e.g. Tic Tac Toe stores all actions as a marks on the board, and the board is the full state. In some situations you may want to include previous actions as part of the state variable, but for simple perfect information games it should not be necessary. I don't know how the reference trajectories training works, so if you want an answer to that you should ask a new question.


text:
Understanding the W term in off policy monte carlo learning
In Sutton and Barto's RL textbook they included the following pseudocode for off policy Monte Carlo learning. I am a little confused, however, because to me it looks like the W term will become infinitely large after a couple thousand iterations (and this is exactly what happens when I implement the algorithm).
For example, say that the MC algorithm always follows the behavioral policy for each episode (ignoring epsilon soft/greedy for examples sake). If the probability of the action specified by the policy is 0.9, then after 10,000 iterations W would have a value of 1.11^10,000. I understand that the ratio of W to C(a,s) is what matters, however this ratio cannot be computer once W becomes infinite. Clearly I am misunderstanding something.

The pseudocode you have copied looks incorrect to me, and I think it is from the first edition.
The main issue is at the end of the loop. Where the book has

$\qquad W \leftarrow W \frac{1}{\mu(A_t|S_t)}$
$\qquad \text{If } W = 0 \text{ then ExitForLoop}$

It should have either

$\qquad W \leftarrow W \frac{1}{\mu(A_t|S_t)}$
$\qquad \text{If } \pi(S_t) \neq A_t \text{ then ExitForLoop}$

or

$\qquad W \leftarrow W \frac{\pi(A_t|S_t)}{\mu(A_t|S_t)}$
$\qquad \text{If } W = 0 \text{ then ExitForLoop}$

This latter one is more general - it covers situations where the target policy can be stochastic - but doesn't fit with the notation used elsewhere for a deterministic policy. For some reason the first edition book had a mistake using hybrid algorithm which adjusted to a deterministic target policy except for the exit loop statement. This is fixed in the second edition (page 111).

after 10,000 iterations

Are your episodes really 10,000 time steps long? If so, the chances of off-policy MC control learning anything for early time steps seems remote unless $\epsilon$ is really low (and in which case $W$ will not get too high). If not, have you missed that $W \leftarrow 1$ occurs at the start of each episode?


text:
How to know if the hyperparameters of a neural network relate to each other?
According this thread some hyperparameters are independent from each other while some are directly related.
One of the answers give an example where two hyperparameters affect each other.

For example, if you're using stochastic gradient descent (that is, you train your model one example at a time), you probably do not want to update the parameters of your model too fast (that is, you probably do not want a high learning rate), given that a single training example is unlikely to be able to give the error signal that is able to update the parameters in the appropriate direction (that is, the global or even local optimum of the loss function).

How would someone creating a neural network know how the hyperparameters affect each other?
In other words, what are the heuristics for hyperparameter selection when trying to build a robust model?

This is one of the most difficult and unsolved problems in machine learning and deep learning!
There are many different ways to estimate the most appropriate hyper-parameters, such as grid search, random search, Bayesian optimization, meta-learning, reinforcement learning, and evolutionary algorithms (e.g. NEAT).
However, the problem is that most if not all these approaches are typically not very computationally efficient if your model isn't anything but very small. The number of possible configurations of the hyper-parameters is very large. If you don't have good computational resources (e.g. GPUs and powerful servers), you probably out of luck or require some days to get some insight.
In certain cases, it is obvious that certain hyper-parameters are dependent on each other, e.g. in the case of the batch size and the learning rate, because we have some decent understanding of gradient descent, but, in other cases, the situation isn't so nice.
As far as I know, there isn't a very good general rule of thumb or method to solve this issue (i.e. find the dependence of hyper-parameters on each other). Maybe, as our knowledge of our models (especially, neural networks) increases, we'll get some more insights and we'll develop more efficient approaches to understand the dependence of the hyper-parameters.
Nowadays, there's automatical machine learning (AutoML), which is a fancy name to denote services that provide hyper-parameter optimization (plus some other stuff).


text:
Is an SVM the same as a neural network without a hidden layer?
A neural network without a hidden layer is the same as just linear regression.
If I then use squared hinge loss and encoporate the l2 regularisation term, is it fair to then call this network the same as a linear SVM?
Going by this assumption, then if I need to implement a multiclass SVM, i can just have n output nodes (where n is the number of classes). Would this then be equivalent to having n number of SVMs, similar to a one-vs-rest method?
If I then wanted to encoporate a kernel into my SVM, could I then use an activation function or layer prior to the final output nodes (where I compute loss and add regularisation) which would then transfer this data into another feature plane the same as that of an SVM kernel?
This is my current hunch, but would like some confirmation or correction where my understanding is incorrect.

"A neural network without a hidden layer is the same as just linear regression.", this is not true. This is only true if the activation functions are identities. So you'd better review your post and question.

First, what makes the neural network different than linear regression is the non-linearity (activation function), not the number of layers. So, a neural network with $n$ layers with no non-linearities is still the same as linear regression. Second, SVM finds the hyperplane of maximum margin. You are not guaranteed to find that hyperplane that has maximum margin with a neural network (using non-linearities).

okay fair enough, does this (see link below) then have any valid points? or will it ultimately just be an aproximation to the functionality of an SVM? https://stackoverflow.com/questions/54414392/convert-sklearn-svm-svc-classifier-to-keras-implementation

it will be an approximation. Unless you mathematically guarantee that is the maximum margin, it is just an approximation (That's why SVM is interesting, because it guarantees maximum margin, otherwise you stay with linear regression). Whenever you use a neural network, you can't guarantee you satisfy a constraint on the hyperplane found by the neural net. The math to do that doesn't exist yet.

okay that makes sense, cheers for the insight.


text:
How to apply hyperparameter optimization on Monte Carlo Tree Search?
I have a basic MCTS agent for the game of Hex (a turn based game). I want to tune the parameters of UCT (the Cp parameter) and the number of rollouts parameter.
Where do I have to begin? The problem is that the agent is smart enough to always win if it plays first against another agent. So I don't know how to do the evaluation of each pair of hyperparameters.
If anyone has any ideas let me know.

Since no one answers, I will say the approach I used.
It was inspired by the successive halving algorithm. The concept is that we find good performing hyperparameters for one agent by playing manually against it. Then, we put the agent we want to tune to play against it. We assign different configurations. All of these configurations are tried for a predefined number of games per configuration. We keep the best performing half, and then go to the next round with the half we kept and repeat this process. The last configuration that remains is the best performing configuration.


text:
Is A2C loss function taking smaller steps for larger mistakes?
A2C loss is usually defined as advantage * (-log(actor_predictions)) * target where target is a one-hot vector (with some clipping/noise/etc...) with the selected target.
Does this mean that we get larger losses for smaller mistakes?
If for example the agent has predicted $\pi(a|s)=0.9$ but the advantage is negative, this would mean a larger mistake than if the agent predicted that $\pi(a|s)=0.1$, however, putting the numbers in the formula means a larger loss for the 0.1 prediction.
Assuming advantage=-1, advantage * (-log(actor_predictions)) * target would mean:
$$
-1 * (-log(0.9)) * 1 = log(0.9)=-0.045
$$
$$
-1 * (-log(0.1)) * 1 = log(0.1)=-1
$$
Is my understanding correct?

So this question is due to a misunderstanding I had with how the loss function works in A2C.
Usually loss functions are always positives, but in A2C it can be negative as well. I thought that minimizing the loss function means moving it closer to zero, but in fact reducing the loss is indifferent to the sign of the loss value and is about making the loss value smaller.
In other words, the loss for 0.1 is smaller than the loss for 0.9 prediction for a disadvantageous action.
When the advantage is positive, $-log (p) * advantage$ will be smaller if $p$ is growing, and when the advantage is negative, $-log (p) * advantage$ will be smaller if $p$ is decreasing.


text:
Applying Eligibility Traces to Q-Learning algorithm does not improve results (And might not function well)
I am trying to apply Eligibility Traces to a currently working Q-Learning algorithm.
The reference code for the Q-Learning algorithm was taken from this great blog by DeepLizard, but does not include Eligibility Traces. Link to the code on Google Colab.
I wish to add the Eligibility Traces by implementing this pseud code:
Initialize Q(s,a) arbitrarily and e(s,a) = 0, for all s,a
Repeat (for each episode):
    Initialize s,a
    Repeat (for each step of episode):
        Take action a, observe r,s’
        Choose a’ from s’ using policy derived from Q (e.g., ϵ-greedy)
        δ ← r + γ Q(s’,a’) – Q(s,a)
        e(s,a) ← e(s,a) + 1
        For all s,a:
            Q(s,a) ← Q(s,a) + α δ e(s,a)
            e(s,a) ← γ λ e(s,a)
        s ← s’ ; a ← a’
    until s is terminal

Taken from HERE
This is my code as I have implemented the pseudo-code - Link
The part that needs to be improved is here:
#Q learning algorithem
for episode in range(num_episodes):
  state = env.reset()
  et_table = np.zeros((state_space_size,action_space_size))
  done = False
  reward_current_episode = 0

  for steps in range(max_steps_per_episode):
    #Exploration-Explotation trade-off
    exploration_rate_thresh = random.uniform(0,1)
    if exploration_rate_thresh > exploration_rate:
      action = np.argmax(q_table[state,:])
    else:
      action = env.action_space.sample()

    new_state, reward, done, info = env.step(action)

    #Update Q-table and Eligibility table
    delta = reward + discount_rate * np.max(q_table[new_state,:]) - q_table[state,action]
    et_table[state, action] = et_table[state, action] + 1

    for update_state in range(state_space_size):
      for update_action in range(action_space_size):
        q_table[update_state, update_action] = q_table[update_state, update_action] + learning_rate * delta * et_table[update_state, update_action]
        et_table[update_state, update_action] = discount_rate * gamma * et_table[update_state, update_action]

    state = new_state
    reward_current_episode = reward

    if done==True:
      break

  #Exploration rate decay
  exploration_rate = min_exploration_rate + (max_exploration_rate - min_exploration_rate) * np.exp(-exploration_decay_rate*episode)

  rewards_all_episodes.append(reward_current_episode)

For a while, I was getting pure results (avg. rewards for 1000 episodes were around 0.14 while the original NON-ET algorithm was averaging 0.69 on the last 1000 episodes), but now I get these errors:
/usr/local/lib/python3.6/dist-packages/ipykernel_launcher.py:27: RuntimeWarning: overflow encountered in double_scalars
/usr/local/lib/python3.6/dist-packages/ipykernel_launcher.py:22: RuntimeWarning: invalid value encountered in double_scalars

The thing is, that while I was posting the question, I tried to tweak with the parameters and it seems that my discount rate (set for 0.99) was causing these errors.
Also - it seems that the is_slippery argument passed to the environment (True - the agent's action will be fulfilled 33% of the times, the rest of the times will be in a random direction, False - the agent's action will be fulfilled 100% of the times) is crucial for Eligibility Traces. The results improve from 0.39 to 0.993.
My assumption is that the randomness of the "Slippery" part of the environment is crucially hurting the Eligibility Traces due to the fact that it is relying on the actions that were taken (and assuming they were fulfilled and not randomly changed).
After changing it to 0.9 I receive these results:
*** Average award per 1000 episodes ***
1000 :  0.2640000000000002
2000 :  0.7560000000000006
3000 :  0.9140000000000007
4000 :  0.9600000000000007
5000 :  0.9820000000000008
6000 :  0.9870000000000008
7000 :  0.9860000000000008
8000 :  0.9830000000000008
9000 :  0.9930000000000008
10000 :  0.9930000000000008

******* Q-Table *******

[[0.53144572 0.59049007 0.59046218 0.53144103]
 [0.53292711 0.         0.65610941 0.5864814 ]
 [0.58892359 0.729037   0.59954581 0.6546992 ]
 [0.65324248 0.         0.53612877 0.55540024]
 [0.59049001 0.65610007 0.         0.53143728]
 [0.         0.         0.         0.        ]
 [0.         0.8099945  0.         0.65015572]
 [0.         0.         0.         0.        ]
 [0.65610004 0.         0.72900006 0.59049002]
 [0.65610024 0.81       0.80996651 0.        ]
 [0.73156036 0.9        0.         0.72830918]
 [0.         0.         0.         0.        ]
 [0.         0.         0.         0.        ]
 [0.         0.8100008  0.9        0.72900011]
 [0.81000015 0.89999998 1.         0.80998688]
 [0.         0.         0.         0.        ]]

Comparing it to the original !-Learning algorithm by DeepLizard (LINK):
*** Average award per 1000 episodes ***
1000 :  0.22900000000000018
2000 :  0.7250000000000005
3000 :  0.8990000000000007
4000 :  0.9610000000000007
5000 :  0.9860000000000008
6000 :  0.9900000000000008
7000 :  0.9870000000000008
8000 :  0.9970000000000008
9000 :  0.9870000000000008
10000 :  0.9890000000000008

******* Q-Table *******

[[0.94148015 0.95099005 0.93206533 0.94148015]
 [0.94148015 0.         0.71778349 0.84678222]
 [0.88367728 0.43945604 0.0084652  0.27374571]
 [0.15097126 0.         0.         0.        ]
 [0.95099005 0.96059601 0.         0.94148015]
 [0.         0.         0.         0.        ]
 [0.         0.98009092 0.         0.36957636]
 [0.         0.         0.         0.        ]
 [0.96059599 0.         0.970299   0.95099004]
 [0.96059598 0.98009932 0.9801     0.        ]
 [0.97029894 0.99       0.         0.97021962]
 [0.         0.         0.         0.        ]
 [0.         0.         0.         0.        ]
 [0.         0.89329522 0.99       0.91080933]
 [0.98009934 0.98999961 1.         0.98009962]
 [0.         0.         0.         0.        ]]

We see a bit better results (we can see that on the 10K episode our agent is making the right path at 0.993% of the times, in appose to 0.989% in the original algorithm).
The bottom line is that the Eligibility Traces implementation can be done using these formulas:
a. create the et_table:
et_table = np.zeros((state_space_size,action_space_size))

b. Set gamma for the decaying of the Eligibility Traces:
gamma = 0.9

c. At each step - apply these calculations:
#Update Q-table and Eligibility table
    delta = reward + discount_rate * np.max(q_table[new_state,:]) - q_table[state,action]
    et_table[state, action] = et_table[state, action] + 1

    for update_state in range(state_space_size):
      for update_action in range(action_space_size):
        q_table[update_state, update_action] = q_table[update_state, update_action] + learning_rate * delta * et_table[update_state, update_action]
        et_table[update_state, update_action] = discount_rate * gamma * et_table[update_state, update_action]

d. After each episode - reset the et_table to zeros.
Full code can be found here:
import numpy as np
import gym
import random
import time
from IPython.display import clear_output

env = gym.make("FrozenLake-v0", is_slippery=False)

action_space_size = env.action_space.n
state_space_size = env.observation_space.n

q_table = np.zeros((state_space_size,action_space_size))
et_table = np.zeros((state_space_size,action_space_size))
print("Q Table:\n", q_table)
print("Eligibility Traces:\n", et_table)

num_episodes = 10000
max_steps_per_episode = 100

learning_rate = 0.1
discount_rate = 0.9
gamma = 0.9

exploration_rate = 1
max_exploration_rate = 1
min_exploration_rate = 0.01
exploration_decay_rate = 0.001

rewards_all_episodes = []
q_table = np.zeros((state_space_size,action_space_size))

#Q learning algorithem
for episode in range(num_episodes):
  state = env.reset()
  et_table = np.zeros((state_space_size,action_space_size))
  done = False
  reward_current_episode = 0

  for steps in range(max_steps_per_episode):
    #Exploration-Explotation trade-off
    exploration_rate_thresh = random.uniform(0,1)
    if exploration_rate_thresh > exploration_rate:
      action = np.argmax(q_table[state,:])
    else:
      action = env.action_space.sample()

    new_state, reward, done, info = env.step(action)

    #Update Q-table and Eligibility table
    delta = reward + discount_rate * np.max(q_table[new_state,:]) - q_table[state,action]
    et_table[state, action] = et_table[state, action] + 1

    for update_state in range(state_space_size):
      for update_action in range(action_space_size):
        q_table[update_state, update_action] = q_table[update_state, update_action] + learning_rate * delta * et_table[update_state, update_action]
        et_table[update_state, update_action] = discount_rate * gamma * et_table[update_state, update_action]

    state = new_state
    reward_current_episode = reward

    if done==True:
      break

  #Exploration rate decay
  exploration_rate = min_exploration_rate + (max_exploration_rate - min_exploration_rate) * np.exp(-exploration_decay_rate*episode)

  rewards_all_episodes.append(reward_current_episode)

#Print average reward per thousend episodes
reward_per_thousend_episodes = np.split(np.array(rewards_all_episodes),num_episodes/1000)
count = 1000
print("*** Average award per 1000 episodes ***")
for r in reward_per_thousend_episodes:
  print(count, ": ", str(sum(r/1000)))
  count+=1000

#Print Q-Table
print("\n\n******* Q-Table *******\n")
print(q_table)

print("\n\n******* ET-Table *******\n")
print(et_table)


text:
Are bandits considered an RL approach?
If a research paper uses multi-armed bandits (either in their standard or contextual form) to solve a particular task, can we say that they solved this task using a reinforcement learning approach? Or should we distinguish between the two and use the RL term only when it is associated with an MDP formulation?
In fact, each RL course/textbook usually contains a section about bandits (especially when dealing with the exploration-exploitation tradeoff). Additionally, bandits also have the concept of actions and rewards.
I just want to make sure what the right terminology should be, when describing either approach.

Several important researchers distinguish between bandit problems and the general reinforcement learning problem.
The book Reinforcement learning: an introduction by Sutton and Barto describes bandit problems as a special case of the general RL problem.

The first chapter of this part of the book describes solution methods for the special case of the reinforcement learning problem in which there is only a single state, called bandit problems. The second chapter describes the general problem formulation that we treat throughout the rest of the book — finite Markov decision processes — and its main ideas including Bellman equations and value functions.

This means that you can represent your bandit problem as an MDP with a single state and possibly multiple actions.
In section 1.1.2 of the book Bandit Algorithms (2020), Szepesvari and Lattimore describe the differences between bandits and reinforcement learning

One of the distinguishing features of all bandit problems studied in this book is that the learner never needs to plan for the future. More precisely, we will invariably make the assumption that the learner's available choices and rewards tomorrow are not affected by their decisions today. Problems that do require this kind of long-term planning fall into the realm of reinforcement learning

This definition is different than the one by Sutton and Barto. In this case, only bandit problems where the learner doesn't need to plan for the future are considered.
In any case, bandit problems and RL problems have a lot of similarities. For example, both attempt to deal with the exploration-exploitation trade-off and, in both cases, the underlying problem can be formulated as a Markov decision process.

Thanks @nbro . In fact, in one of his lectures on bandits, Tor Lattimore referred to bandits as “baby RL”, but I wouldn’t use that term in a formal context :) Szepesvari also includes bandit algorithms in his book Algorithms for Reinforcement Learning (https://sites.ualberta.ca/~szepesva/rlbook.html , Section 4.2.1). In any case, I think the key difference is as they mention it “the learner's available choices and rewards tomorrow are not affected by their decisions today.”

If there is only one state in the bandit problem, so what is it actually? Is it possible to describe it in detail? Give a cartpole problem, the state could be cart position, cart velocity, pole angle, pole angular velocity. In the bandit problem, my understanding is that the state can be the combination of the pattern, if you get a specific pattern you get the corresponding reward. However, it is hard to model and not only one. So when we say there is only one state, what we are referring to?

Let's have a look at the introduction of Chapter 2: Multi-armed Bandits in the
Reinforcement Learning: An Introduction by Sutton, Barto

The most important feature distinguishing reinforcement learning from other types of learning is that it uses training information that evaluates the actions taken rather than instructs by giving correct
actions. This is what creates the need for active exploration, for an explicit search for good behavior.
Purely evaluative feedback indicates how good the action taken was, but not whether it was the best or
the worst action possible. Purely instructive feedback, on the other hand, indicates the correct action
to take, independently of the action actually taken. This kind of feedback is the basis of supervised
learning, which includes large parts of pattern classification, artificial neural networks, and system
identification. In their pure forms, these two kinds of feedback are quite distinct: evaluative feedback
depends entirely on the action taken, whereas instructive feedback is independent of the action taken.
In this chapter we study the evaluative aspect of reinforcement learning in a simplified setting, one
that does not involve learning to act in more than one situation. This nonassociative setting is the
one in which most prior work involving evaluative feedback has been done, and it avoids much of the
complexity of the full reinforcement learning problem. Studying this case enables us to see most clearly
how evaluative feedback differs from, and yet can be combined with, instructive feedback.
The particular nonassociative, evaluative feedback problem that we explore is a simple version of
the k-armed bandit problem. We use this problem to introduce a number of basic learning methods
which we extend in later chapters to apply to the full reinforcement learning problem. At the end
of this chapter, we take a step closer to the full reinforcement learning problem by discussing what
happens when the bandit problem becomes associative, that is, when actions are taken in more than
one situation.

Since bandits involve evaluative feedback they are indeed a type of a (simplified) reinforcement learning problem.

Thanks @Tomasz Bartkowiak. I accepted nbro’s answer, as it is more comprehensive, in the sense that it includes views from authors primarily working in the full RL setup (the ones you already referenced) and authors primarily working on bandits.


text:
How can Siamese Networks be viewed as RNNs?

"Single-object tracking commonly uses Siamese networks, which can be seen as an RNN unrolled over two time-steps."

(from the SQAIR paper)
I'm wondering how Siamese networks can be viewed as RNNs, as mentioned above. A diagrammatic explanation, or anything that helps understand the same, would help! Thank you!

Well, here in the picture we have the unrolled or unfold RNN on the right side. Siamese network is formed when it is said to be "unrolled over two time-steps". So, take part where there is two first iterations of RNN and yes, you have kind of Siamese network.
One take from the source of the image:

Unlike a traditional deep neural network, which uses different parameters at each layer, a RNN shares the same parameters (U, V, W above) across all steps. This reflects the fact that we are performing the same task at each step, just with different inputs. This greatly reduces the total number of parameters we need to learn.

Sounds familiar to siamese network used on single-object tracking: there we take two signals (image and the tracked object), drive it through identical paths and make some maths to get results. Just something the RNN makes to time separated values!
For proof of similarity, a take from a site where siamese networks are nicely explained:

Side note: I don't know then, how closely those relate in real world (could a Siamese network in anyway be a RNN or vice versa), but supposedly so, because the comparison is made by researcher to say so. At diagrammatic level at least there would be no problem on that.

Single object tracking using a Siamese Network is a Detect and compare approach, where an object of interest is detected and the one to be tracked is passed through a siam network with next consecutive frame to get a correlation between them, if you look at the related reference, it is a correlation-based tracking, ie. correlation between objects detected in one frame and the ones detected in next frame, which you can imagine as samples considered across 2 timesteps or an RNN unrolled to 2 timesteps


text:
How do you know if an agent has learnt its environment in reinforcement learning?
I'm new to reinforcement learning and trying to understand it.
If you train an agent using a reinforcement learning algorithm (discrete or continuous) on an environment (real or simulated), then how do you know if the agent has learnt its environment? Should it reach its goal on every run (episode)? (Any literature references are also welcome)
Is this related to the reward threshold defined in the environment?
What happens if you continue training after the agent has learnt the environment? Will it perform by reaching its goal every time or will there be failed episodes?

This depends on the complexity of the environment being learned, and the purpose for learning it. There is no general answer.
For the simple environments used to teach reinforcement learning (RL), often the optimal solution is obvious, or can be calculated and proven optimal. For instance, any environment that can be solved using policy iteration will have a known optimal policy and optimal value function. The goals of these environments are to teach, or to check correctness of agents - it helps in these cases to have a well known correct answer.
At the next level up in terms of complexity are well-studied environments which can have achievable targets set for learning agents. The goals of these environments include getting useful metrics for learning agents, such as how many episodes it takes a particular implementation to learn it well enough. Defining "well enough" is a matter of experience with existing agents.
Getting more complex still, in general it is not possible to know whether an agent has fully optimised against its environment. The subject area of sequential decision making that includes RL agents can cover scenarios such as driving a car or playing a computer game. We don't know when any agent, whether they are based on RL or some other approach, has fully learning an environment, and instead must construct tests of behaviour - e.g. make an agent simulate driving in a set of scenarios, and expect at least safe behaviour in each of them, essentially a driving test similar to one a person might take. In these environments, often the tests are based on "good enough to use" goals. We can say an agent has learned to drive if it drives more safely than an average human.
In the special case of competitive games, we can score agents against each other or against human players. You might say that an agent has learned its environment if it beats some standard player, but also you can rank agents against each other and declare a particular agent as the current best.
It is possible to mix and match these ideas. The Atari games learning suite has benchmark scores to reach that count as "standard human", and recently agents have been published that beat all of those scores.

What happens if you continue training after the agent has learnt the environment? Will it perform by reaching its goal every time or will there be failed episodes?

If you include training episodes, then RL learns mainly by "trial and error". So you should expect an agent to make deliberate mistakes as it tests to see what happens. In some environments these could be critical mistakes leading to failed episodes.
If you ignore the training episodes and are interested only in performance without exploration - e.g. testing every few hundred episodes - then you can expect performance to vary depending on the type of agent and environment. Some agents even exhibit "catastrophic forgetting", which as the name implies causes performance to drop significantly - this can be caused by a successful agent over-fitting to all the recent successful episodes without errors it just experienced, and losing the ability to predict the true lower value of incorrect actions.
Neither failed episodes during training nor catastrophic forgetting are inevitable. It depends on the environment and type of agent.

Thank you for the detailed answer. Please tell me what is the difference between training and testing (aka evaluation if I understood correctly)? As I see it, both imply the same procedure: select an action, apply to the environment, get reward and state...

@CristianM: During training the agent will - with some probability - deliberately take actions that it currently evaluates as not optimal, in order to refine its understanding of them (maybe its estimates are wrong, it can only find out by trying). This can reduce its performance. That is what I am referring to in the paragraph starting "If you include training episodes . . ."

OK. I am referring in a general sense. I will post a separate question for this.


text:
solving xor function using a neural network with no hidden layers
xor is a non-linear dataset. It cannot be solved with any number of perceptron based neural network but when the perceptions are applied the sigmoid activation function, we can solve the xor dataset.
But I came across a source where the following statement is stated as False
A two layer (one input layer; one output layer; no hidden layer) neural network can represent the XOR function.
However, I have trained a model with no hidden layers, gives the following result:
[INFO] data=[0 0],ground-truth=0, pred=0.5161, step=1
[INFO] data=[0 1],ground-truth=1, pred=0.5000, step=1
[INFO] data=[1 0],ground-truth=1, pred=0.4839, step=0
[INFO] data=[1 1],ground-truth=0, pred=0.4678, step=0

So, in if I apply a softmax classifier, I can separate the xor dataset with a nn without any hidden layer. This makes the statement incorrect.
Is it true that we cannot separate a non linear dataset without any hidden layers in a neural network? If yes, where am I wrong in my reasoning from the training of the nn I have done above

What do you think softmax does? what change will it make if you replace a sigmoid with a softmax when the output layer is only one neuron?

I meant placing the softmax after the last layer, but now realize that it would no longer be a nn with no hidden lalyers

last layer has weights, you just replace a sigmoid with a softmax

But adding a softmax or a sigmoid will make the output of the network nonlinear right (because sigmoid or softmax are nonlinear functions), and the xor is a non linear dataset too. Is there any proof/justification that we cannot  separate

Softmax is a probability distribution you use when you want probability for all multiple classes you are predicting which are not independent, ie, exp(xi)/sum(exp(xj) for j in all x), where xi is the score of one neuron, so softmax is good if you have more than 1 neurons, but for just 1 neuron(in this case), the output of softmax will be 1, always (exp(xi)/exp(xi)).
Now lets visualize your dataset, ie plot the points of XOR as a function of X,Y on coordinate space.
, [src: https://www.researchgate.net/figure/The-exclusive-or-XOR-function-is-a-nonlinear-function-that-returns-0-when-its-two_fig4_322048911]
Now, whatever you do, you cannot separate the points with a single wx+b straight line, and after passing it to sigmoid, you just squeeze the values for those, ie, a clipped wx+b.
Now, it is still a linear equation. Now when you add another layer, a hidden one, you can operate again on the 1st output, which if you squeeze between 0 and 1 or use something like relu activation, will produce some non linearity, otherwise it will just be (w2(w1*x + b1)+b2, which again is a linear equation not able to separate the classes 0 and 1.
So after adding a hidden layer and passing it through activation function, you get non linear output, example, with sigmoid you get w2*(1/+exp(w2*x+b1))+b2 which has a fairly non linear term of x, and after passing it through sigmoid again, you are able to squeeze the outputs(otherwise they can be higher than 1 or lower than 0,but XOR outputs are binary) after fitting the curve so that both classes are separate.
Now, food for thought, what will happen if you use 2 output neurons for XOR (represent 0 as [1,0] and 1 as [0,1])?

Thank you for the answer and a wonderful question. In my opinion, using 2 output neurons will not be sufficient because each of the output from neurons is still just 'clipped' from a linear function. But the xor data(even though it's representation is by a matrix now) is still non linear, we just increased it's space representation from 1d to 2d. It would be great, if you can reason your question


text:
Is there 1-dimensional reinforcement learning?
From what I can find, reinforcement algorithms work on a grid or 2-dimensional environment.  How would I set up the problem for an approximate solution when I have a 1-dimensional signal from a light sensor.  The sensor sits some distance away from a lighthouse.  The intent would be to take the reading from the sensor to determine the orientation of the lighthouse beam.
The environment would be a lighthouse beam, the state would be the brightness seen at the sensor for a given orientation, and the agent would be the approximate brightness/orientation?  What would the reward be?  What reinforcement learning algorithm would I use to approximate the lighthouse orientation given sensor brightnesses?

From what I can find, reinforcement algorithms work on a grid or 2-dimensional environment.

A lot of teaching materials use a "grid world" presentation to demonstrate basic reinforcement learning (RL). However, the underlying Markov Decision Process (MDP) theory works on an arbitrary graph of connected states. This graph could be based on subdividing a metric space of any dimensions into a grid of the same dimensions (and using tiles of any shape that worked in that dimension). However, it is not limited to that, the state space does not need to be a metric that represents distances or physical properties.
In practice, the set of states can be arbitrary objects, connected via state transitions in any consistent way. Provided the transition probability function $p(s'|s,a)$ is consistent, the environment could be used in a RL problem.
A very common state description is that the state is a vector of numbers that capture all the variables relevant to the problem. The environment can then be measurements taken in the real world of those variables, or the same quantities provided by a simulation. That state vector can be of any size, and have arbitrary constraints on individual components. This is no different from numerical representations of other machine learning problems, such as the inputs allowed to a neural network.

The environment would be a lighthouse beam, the state would be the brightness seen at the sensor for a given orientation, and the agent would be the approximate brightness/orientation?

Something not quite right about the description there. There does not seem to be any action that the agent takes.

What would the reward be?

It would be whatever measure of reaching a goal or maintaining a "good" result that is appropriate for the problem. You do not give any information about the goal in your description.
If your goal is to light up a moving sensor with the highest brightness, then the brightness measured at the sensor, transformed into suitable units, would seem to be a good candidate for a reward function (you would also need the state to give information about the target - where it had been seen last for instance). Assuming the problem is continuous, you would also need a discount factor.

What reinforcement learning algorithm would I use to approximate the lighthouse orientation given sensor brightnesses?

Generally RL algorithms estimate rewards, or generate policies. If the lighthouse orientation is the action you wanted to take, then pretty much all RL algorithms can do one or the other to allow you to do this. The differences are in things like complexity or speed of the algorithm, what approximations you are willing to take etc.
You don't give enough information about the problem to even nearly suggest a "best" algorithm. Before you start, you will need to determine a more thorough description of state, action and rewards, that will define the problem. Once you have a more formal description of the problem, that may suggest which algorithms would be good starting points.

If you do want to give more information, it is best done in another question.


text:
Random value generator using a single neuron or DNN
AI is supposed to do anything human or traditional computer can do, that is what we expect AI to be.
So 'generating random value' is also a task included in the scope that AI should be able to do
I'm trying to generate random value using a single neuron but the outcome isn't much good.
Any suggestions?
PS.
Random weight initialisation is allowed coz weights are constants at start.
Using 'random' function is forbidden anywhere else.

AI is supposed to do anything human or traditional computer can do, that is what we expect AI to be.

Technically you would need AGI (Artifical General Intelligence) to do anything a human can do. This is not a technology that exists, but a goal of some AI research to perform more and more general tasks.

So 'generating random value' is also a task included in the scope that AI should be able to do

Humans are actually very bad at generating random values directly. In fact it is possible to identify a person by getting them to generate random numbers from their mind. Indirectly, a human could pick up a die, roll it, and read the number - this is also something that is within capabilities of modern AI, but not something you could implement with a small neural network.
Computer software cannot generate random numbers directly, only pseudo-random numbers that are deterministic but follow a statistical pattern very similar to theoretical randomness. When combined with frequently changing seed data from the environment, this becomes very close to an ideal random source, but it does require some hardware input. Modern computer chips include an internal source of randomness to provide this seed data, but it is important to note that it is a piece of specialised hardware, not something that can be coded or simulated using a simple neural network.

I'm trying to generate random value using a single neuron but the outcome isn't much good. Any suggestions?

This is going to be much harder than you assumed. Random number generators are always more complex than a single function, and require at least a little bit of architecture. The simplest architecture would be to add a state value to use as the next input to the generator, and which is somehow affected by the previous output. A simple feed-forward neural network does not have any architecture like this, you need to add it.
My first suggestion would be to learn how some simple software pseudo-random number generators (PRNGs) work. A good place to start might be linear congruential generators which are considered very poor quality PRNGs nowadays, but are the sort found in early computer systems.
It should be possible to create a rough approximation to a PRNG from a single neuron. Picking the weight, bias and non-linear functions carefully should allow you to produce something similar to the linear congruential generator, where it generates the next pseudo-random number when you input the previous one. A slightly more sophisticated approach would be to make this a simple recurrent neural network (RNN) so that the neural network has an internal state - such a network could still have a single neuron.
An example neuron that works like this might have a weight of 3, bias of 1 (to generate a logit from input $x$ of $z= 3x+1$) and have activation function $y = 1000\text{sin}(z) \text{ mod } 1$. This is not a normal activation function that you would use to train a neural network - in fact this neural network probably could not be trained at all. It has been specially designed to achieve your goal of generating (pseudo-)random numbers using a single neuron. It is a valid neural network though.
I created the above example neuron, started it with a seed of 0, and got the sequence 0.4710, 0.8543, 0.1536, 0.9479, 0.1142, 0.0683, 0.7741, 0.2985, 0.7315, 0.0777, 0.5078 by feeding back previous values - you can see it is working, although it is probably a very bad random number generator even compared to linear congruential generators. Possibly better than a human though.


text:
Can I do state space quantization using a KMeans-like algorithm instead of range buckets?
Are there any reference papers where it is used a KMeans-like algorithm in state space quantization in Reinforcement Learning instead of range buckets?

There is this paper Representation and Reinforcement Learning for
Personalized Glycemic Control in Septic Patients, presented in the Machine Learning for Health Workshop in NIPS 2017. Here is a quote from the paper where the authors describe the clustering approach:

After we generated the state representation,
  we used the k-means clustering algorithm to categorize millions of patient states into 500 clusters
  such that similar clinical states can collapse into the same cluster.


text:
How do updates in SARSA and Q-learning differ in code?
The update rules for Q-learning and SARSA each are as follows:
Q Learning:
$$Q(s_t,a_t)←Q(s_t,a_t)+α[r_{t+1}+γ\max_{a'}Q(s_{t+1},a')−Q(s_t,a_t)]$$
SARSA:
$$Q(s_t,a_t)←Q(s_t,a_t)+α[r_{t+1}+γQ(s_{t+1},a_{t+1})−Q(s_t,a_t)]$$
I understand the theory that SARSA performs 'on-policy' updates, and Q-learning performs 'off-policy' updates.
At the moment I perform Q-learning by calculating the target thusly:
target = reward + self.y * np.max(self.action_model.predict(state_prime))

Here you can see I pick the maximum for the Q-function for state prime (i.e. greedy selection as defined by maxQ in the update rule). If I were to do a SARSA update and use the same on-policy as used when selecting an action, e.g. ϵ-greedy, would I basically change to this:
if np.random.random() < self.eps:
    target = reward + self.y * self.action_model.predict(state_prime)[random.randint(0,9)]
else:
    target = reward + self.y * np.max(self.action_model.predict(state_prime))

So sometimes it will pick a random future reward based on my epsilon greedy policy?

Picking actions and making updates should be treated as separate things. For Q-learning you also need to explore by using some exploration strategy (e.g. $\epsilon$-greedy).
Steps for Q-learning:

initialize state $S$
For every step of the episode:
choose action $A$ by some exploratory policy (e.g. $\epsilon$-greedy) from state $S$
take action $A$ and observe $R$ and $S'$
do the update $Q(S, A) = Q(S, A) + \alpha(R + \gamma*\max_aQ(S', a) - Q(S, A))$
update the state $S = S'$ and keep looping from step 2 until the end of episode

Steps for Sarsa:

initialize state $S$
initialize first action $A$ from state $S$ by some exploratory policy (e.g. $\epsilon$-greedy)
For every step of the episode:
take action $A$ and observe $R$ and $S'$
choose action $A'$ from state $S'$ by some exploratory policy (e.g. $\epsilon$-greedy)
do the update $Q(S, A) = Q(S, A) + \alpha(R + \gamma * Q(S', A') - Q(S, A))$
update state and action $S = S'$, $A = A'$ and keep looping from step 3 until end of the episode

Thanks for that, much appreciated. So with Sarsa, you actually follow the action A' that was chosen by the ϵ-greedy policy while performing the update. What do you do if it's a board game, and S' isn't actually the same because the other player has changed the state by taking their turn after my agent has performed its action? S' isn't what you thought it would be, and the chosen A' might not even be a legal move anymore.  Can you not use Sarsa in that situation?

With board games you would consider something called afterstates. When you make a move, you don't immediately transfer to new state $S'$, you only move to new state after your opponent makes a move aswell. So the new state happens only after entire turn of play. In that case you would pick $A'$ in completely new state after 1 turn of play

So to be clear, in that scenario and $S'$ is the state when other players have perform their action and it comes back round to my agent's turn, the state at that moment would be $S'$?  At that point if it were to always pick the most-greedy action $maxaQ(S′,a)$ at that $S'$ then that would be Q-learning, if I were to choose an ϵ -greedy action then it would be Sarsa?

Yes, when the action returns to you, you are in $S'$. Again, don't confuse updates and action choices, for updates in Q-learning you would choose the Q value of maximum action of state $S'$  and for Sarsa you would pick an action with $\epsilon$-greedy and use its value for the update. For action choice, for Q-learning you would use $\epsilon$-greedy in state $S'$, in next loop iteration after you made the update, and for Sarsa you would use action $A'$ you already picked from last loop iteration.


text:
Using NEAT, will the child of two parent genomes always have the same structure as the more fit parent?
I'm trying to implement the NEAT Algorithm using c#, based off of Kenneth O. Stanley's paper. On page 109 (12 in the pdf) it states "Matching genes are inherited randomly, whereas disjoint genes (those that do not match in the middle) and excess genes (those that do not match in the end) are inherited from the more fit parent."
Does this mean that the child will always have the exact structure that the more fit parent has? It seems like the only way the structure could differ from crossover was if the two parents were equally fit.

Yes, if you follow the original implementation the children will inherit the topology from the most fit parent.
Keep in mind that the goal is to obtain a good population, maintaining the genetic diversity high but at the same time selecting the best individuals from the population; so, in theory you are allowed to give the topology you prefer to the children.
Here there is an example of an alternative topology inheritance in which a child gets the genes that lead to an excess node while another child gets only the genes that create a new connection.


text:
Each training run for DDQN agent takes 2 days, and still ends up with -13 avg score, but OpenAi baseline DQN needs only an hour to converge to +18?
Status:
For a few weeks now, I have been working on a Double DQN agent for the PongDeterministic-v4 environment, which you can find here.
A single training run lasts for about 7-8 million timesteps (about 7000 episodes) and takes me about 2 days, on Google Collab (K80 Tesla GPU and 13 GB RAM). At first, I thought this was normal because I saw a lot of posts talking about how DQNs take a long time to train for Atari games.
Revelation:
But then after cloning the OpenAI baselines repo, I tried running python -m baselines.run --alg=deepq --env=PongNoFrameskip-v4  and this took about 500 episodes and an hour or 2 to converge to a nice score of +18, without breaking a sweat. Now I'm convinced that I'm doing something terribly wrong but I don't know what exactly.
Investigation:
After going through the DQN baseline code by OpenAI, I was able to note a few differences:

I use the PongDeterministic-v4 environment but they use the PongNoFrameskip-v4 environment
I thought a larger replay buffer size was important, so I struggled (with the memory optimization) to ensure it was set to 70000 but they set it to a mere 10000, and still got amazing results.
I am using a normal Double DQN, but they seem to be using a Dueling Double DQN.

Results/Conclusion
I have my doubts about such a huge increase in performance with just these few changes. So I know there is probably something wrong with my existing implementation. Can someone point me in the right direction?
Any sort of help will be appreciated. Thanks!

Although what @Jaden said may be true by itself, it does not really serve to answer my question as I have seen after conducting numerous experiments, and finally reaching close to Dueling Network performance using a normal Double DQN (DDQN).
I made the following changes to my code after closely examining the OpenAI baselines code:

Used PongFrameskip-v4 instead of PongDeterministic-v4
Used a small replay buffer of size 10000
During a step_update() or replay() call, changed the condition for a  return from buffer_fill_size < learn_start to t < learn_start, where t is the current timestep, buffer_fill_size is the current size of buffer that has been filled up with experience tuples, and learn_start is the number of timesteps to wait before starting to learn from the experience collected.
Made sure that the make_atari() wrapper function is also called on the env:
ENV_GYM = 'PongFrameskip-v4'
env = make_atari(ENV_GYM)
env = wrap_deepmind(env, frame_stack=True, scale=False)

These wrappers may be implemented from scratch or can be obtained from the OpenAI baseline Atari wrappers. I personally used the latter since there is no point in reinventing the wheel.

Conclusion:
The biggest step that I overlooked, or rather didn't pay much attention to was the input preprocessing. These few changes improved my DDQN from an average score saturation at -13 in almost 5000 episodes to +18 in about 700-800 episodes. That is indeed a huge difference. You can check out my implementation here.

Could you mention specifically what was different between your original input processing and the improved version? Was this about scaling of NN inputs for instance?

By input processing, I mean the environment chosen (PongFrameskip-v4, instead of PongDeterministic-v4 in this case) and the wrapper methods make_atari and wrap_deepmind. I did not have the make_atari wrapper.

Dueling architectures create bigger differences in the values of actions in the state space. This is because the state-value V(s) function is estimated separately from the state-action value Q(s, a). A new quantity, the advantage of an action, can then be defined as A(s, a) = Q(s, a) - V(s).

The Q function, however, measures the the value
  of choosing a particular action when in this state. The advantage
  function subtracts the value of the state from the Q
  function to obtain a relative measure of the importance of
  each action.
Dueling Network Architectures for Deep Reinforcement Learning

To better direct you, here are 2 resources that could really help you understand why those differences are important.
Speeding up DQN on PyTorch: how to solve Pong in 30 minutes
The main points of the blog are:

Use a larger batch size and play several steps before updating
Play and train in a separate process
Use asyncronous cuda transfers

RL Adventure
This github library has easy to follow jupyter notebooks and links to all of the papers.
It includes:

DQN
Double DQN
Dueling DQN
Prioritized Experience Replay
Noise Networks for Exploration
Distributional RL
Rainbow (That network that deepmind made that had so many things in it they couldn't find a good name)
Distributional RL with Quantile Regression
Hierarchical Deep RL

Thanks for your response. Are you telling me that this sort of performance, even anything close to it, is impossible using a normal DDQN?

Yep. Its not that a DDQN is a bad architecture. Its great and does what it was intended to do (i.e., prevent maximization bias (see section 6.7 in http://incompleteideas.net/book/bookdraft2017nov5.pdf)). But there exist qualities that an environment can posses which, when taken into consideration, allow a method to perform better within the same amount of computation time as methods which do not consider these qualities.


text:
In online one step actor critic, why does the weights update become less significant as the episode progresses?
The Reinforcement Learning Book by Richard Sutton et al, section 13.5 shows an online actor critic algorithm.

Why do the weights updates depend on the discount factor via $I$?
It seems that the more we get closer to the end of the episode, the less we value our newest experience $\delta$.
This seems odd to me. I thought discounting in the  recursive formula of $\delta$ itself is enough.
Why does the weights update become less significant as the episode progresses?
Note this is not eligibility traces, as those are discussed separately, later in the same episode.

This "decay" of later values is a direct consequence of the episodic formula for the objective function for REINFORCE:
$$J(\theta) = v_{\pi_\theta}(s_0)$$
That is, the expected return from the first state of the episode. This is equation 13.4 in the book edition that you linked in the question.
In other words, if there is any discounting, we care less about rewards seen later in the episode. We mainly care about how well the agent will do from its starting position.
This is not true for all formulations of policy gradients. There are other, related, choices of objective function. We can formulate the objective function as caring about the returns from any distribution of states, but in order to define it well, we do need to describe the weighting/distribution somehow, it should be relevant to the problem, and we want to be able to get approximate samples of $\nabla J(\theta)$ for policy gradient to work. The algorithm you are asking about is specifically for improving policy for episodic problems. Note you can set $\gamma = 1$ for these problems, so the decay is not necessarily required.
As an aside (because someone is bound to ask): Defining $J(\theta)$ with respect to all states equally weighted could lead to difficulties  e.g. the objective would take less account of a policy's ability to avoid undesirable states, and it would require a lot of samples from probably irrelevant states in order to estimate it. These difficulties would turn up as a hard  to calculate (or maybe impossible) expectation for $\nabla J(\theta)$