text:
How to deal with changing rewards in Q-learning? DQN?
I read the working of Q-learning through a grid-based taxi routing wherein a taxi has to pick and drop off a passenger from source to destination. Likewise, I have a routing problem and hence, I tried adapting the code from the article for my scenario. Visiting this page is not required, just gave the link for reference. https://www.learndatasci.com/tutorials/reinforcement-q-learning-scratch-python-openai-gym/
My Scenario: As an analogy to my network routing, say my source & destination are node A and node E. Say only two routes are possible: A-B-E and A-B-C-E. I want to select the next node at each 'action' stage that finally together forms a route. Hence, I take my 'state' and 'action' both as the set of all nodes.
Problem: BUT my reward is a value I assign that depends on the parameters of the links connecting the nodes. i.e.if I compute some network metric as x for the link A-B then I give this x as the reward since I want to minimize the x in my network. And obviously, this x would differ over time since my network links' status changes. It is not something I can pre-define for a given state-action as in the article example like obstacle means negative reward, destination means positive reward,etc.
So what should I do in this case? Is my definition of 'state' or 'action' wrong? Or do I need a deep Q-network? Is it for such kinds of cases? Please suggest.

Is my definition of 'state' or 'action' wrong?

I hesitate to say 'wrong', but that's not how state and action are defined in RL, and that mismatch might make the algorithms hard to understand.
In RL theory, the set of all nodes and the links between them is called the environment, the agent's current location is the state, and taking a route from one node to the next is the action. The reward is just as you said, except that usually the agent is trying to maximize the reward.
Once your terms are aligned, regular Q learning (which keeps a simple table of Q values instead of approximating the Q values with something like a neural network) should actually work better than deep Q learning on such a small problem, because training a neural net can be challenging.
Which brings us to the changing rewards. When the rewards change, the agent will need to find the new optimal path. To do that it will need to explore more than it would for a problem with fixed rewards that can settle into an optimal solution. For example, if you were using epsilon greedy exploration, epsilon would need to remain large, or be reset to a large value when the rewards change.
Of course, the agent will perform poorly until it adapts to the new rewards, but you might be able to recalculate the optimal route when the parameters change by running the simulation for some time before making any real decisions.
Hope that helps

Thanks for the detailed answer. I understand your view about dealing with changing rewards part. Actually this was precisely the reason why I was thinking that the tabular approach might not work. The below comment was my thought process. Please read it and tell me if there is a flaw.

My thought process, "ok, if I take state as the current position (which is a node) it would be finite in number. But as much as I may define the state as the current position i.e. a node number, my reward still depends on a link metric that can take any value which is similar to choosing a link as a state since choosing which next link or which next node are synonymous. And so maybe I need a DQN as the link metric will take different values".  I think I confuse between choosing a link vs node number i.e. current position as my state...

"choosing which next link or which next node are synonymous". Yep, you could think of that either way. "And so maybe I need a DQN as the link metric will take different values" I don't follow this part. A Q value in the table of Q values in regular Q learning can also change, and will change faster and be more accurate than an estimated Q value from the neural network in DQN.

Perhaps this will help: Q learning calculates a function Q(s,a) whose values are precisely updated according to the Bellman equation. DQN tries to estimate Q(s,a), but those estimates aren't as good as knowing the true value.

I understand. And what I meant by that "And so.." was, if I consider the selecting next link as action, link is something whose metrics change and those changes are not finite i.e. can take any value. So estimating Q-value would be like estimating for a continuous state space.......But with the idea you gave towards the end of your answer, I think I can do that with a tabular one by maybe avoiding updating the Q-table upon every single successful node or route discovery completion?

It's ok if the metrics/rewards and the Q-values are continuous, only the number of actions (options) needs to be finite. For example, if there were two links leading out of a node, the Q value table would only need two entries for that node, one per link, even if the metric/reward for each link were unconstrained.

Let us continue this discussion in chat.

Ok, I'm there now


text:
Does it make sense to provide a DQN with negative rewards for a network with relu and sigmoid activations?
The creation of negative rewards leads to the chance of Q-values being negative. However, networks with relu or sigmoid activations, just cannot predict negative values. This will lead to a case where erroneous Q-values are being predicted. Is my understanding correct?

A network with ReLU activation can predict negative values; we put ReLU between the hidden layers but return the output of the final layer without any activation function, or with a linear activation function to scale the output.

It is worth mentioning that some kind of non-linear activation function is necessary for hidden layers to be useful. Only in the output layer should be made linear in most cases (I hesitate to say all because although I cannot think of any reason, someone will probably know of a case where it is useful to have a linear hidden layer).

source: Stack Exchange

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

sort: votes


text:
Is it possible to add states to the Q-table after the game has started?
I would like to implement Q-learning in a game.
Here is the board:

It's a 2 player game. At each turn, each player can put a pawn on a line of their choice. They can't choose the column. The right player will put their pawn on the right column and the left player will put their pawn on the other side. At each turn, each pawn will advance in the direction of the opponent. Each pawn has a cost and each player has an amount of money and health points.
I was wondering how I could enumerate the number of states, and it seems impossible.
Given the number of possible states, is Q-learning a solution? If it is, is it possible to add states to the Q-table after the game has started? If Q-learning isn't a solution, what could I use?

Put your SPECIFIC question in the title. "Add states Q-learning" is not a question. Furthermore, Q-learning is an algorithm and saying "add states Q-learning" doesn't seem to make much sense. So, please, try to ask a clear specific question and put in the title.

No need to be so agressive. You understood the question. Anyway, I edited it.

Well, "Add states Q-table after initialization" still doesn't make sense and it's not a question, so now it should be clearer why I used capitals and bold. My intention was not to be aggressive but to be super clear. Apparently, it was highly ineffective, but sometimes it is. Here's a clear a question: "What is 2+2? Is it 4 or 5?"

@Dunno Hello and welcome to AI Stack Exchange! Sometimes we are very direct on this website because we want you to receive the best possible answer to your question. We appreciate that you are here, and we look forward to seeing your questions and answers in the near future! :)

As usual, I do the dirty work of making posts (even those that are not mine) great here. Thank you... This is the last time I do this for you. You should have followed my recommendation to improve your post. Next time, I will just leave the downvote.

Yes, it is possible to add states to a Q table after the game has started, for example by storing the "table" in a binary tree.
Nonetheless, with a simple interpretation of state (like all the pawn positions), Q learning won't work because there are just too many states. Most states will be new so the agent will choose most actions randomly.
Instead, you'll need to reduce the state space with hand-crafted features, or approximate Q values with a classic Q function approximation or a neural network.
I'd choose the latter alternative, which is called a Deep Q Network, but neural networks might be challenging if you aren't familiar with them.
Alternatively, you could use Monte Carlo Tree Search.

It's my problem: every state would be seen as new. I only have experience with neural networks for image recognition. Would you be so kind as to give me the name of a book that would point me in the right direction? I hope it isn't strictly forbidden.

Reinforcement Learning: An Introduction
by Richard S. Sutton and Andrew G. Barto is the book I learned from. And it's available online at: http://incompleteideas.net/book/the-book-2nd.html

But it's a full textbook covering a lot of RL, and the section on Q learning may be hard to understand on its own. You might find a good tutorial by searching for Approximate Q-Learning or Q function approximation.

Is it a legal version?

Yes, it's from the authors. The book is Creative Commons licensed, and also sold on Amazon.

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


text:
Does $R_{s}=E[R_{t}|S_{t}=s]$ indicate the reward we might expect on getting on average moving from any other state to $s$?
I'm trying to understand correctly what each "variable" in RL is and I'm not sure about $R_{s}$ the reward function. I used to think that it's the reward we may expect on average after taking an action $A_{t}$ at state $S_{t}=s$ and at time step $s$ but thinking about it more I think I was wrong.
If we consider that the agent at time step $t$ receives from the environment both an observation $O_{t}$ and a reward $R_{t}$ which will make up the agent's state $S_{t}=s$ depending on what function of the history we take, then it means that we got to state $S_{t}=s$ from a state $S_{t-1}$ taking action an action $A_{t-1}$ right?
I'd like to ask you to confirm or not my claim.

$$R_{s}=\mathbb{E}[R_{t}|S_{t}=s]$$
is the expected reward at time step $t$ given that the state at time $t$ is $s$, where

$R_{t}$ and $S_t$ are random variables that represent the reward and state at time $t$, respectively,
$S_{t}=s$ is an event, and
$\mathbb{E}[X]$ denotes the expected value of the random variable $X$.

It does not matter how you entered $S_t = s$. The only thing that matters is that the current state is $s$. So, the answer to your question in the title is - no. $R_s$ is defined as an expectation (average) of the reward for being in a state, and, in this case, it doesn't take into account next states.
Suppose that the reward space $\mathcal{R} \subset \mathbb{R}$ is a discrete set, then we can write $R_s$ as follows
$$R_{s}=\sum_{r \in \mathcal{R}} r p(r \mid S_{t}=s),$$
where $p(r \mid S_{t}=s)$ is a conditional probability distribution that describes how the reward is distributed in a given state. If you always get the same reward, i.e. $p(r \mid S_{t}=s) = 1$ for a particular $r$ and $0$ for all others, then you have a deterministic reward function, i.e. $R_s$ is equal to the $r$ for which $p(r \mid S_{t}=s) = 1$. In most RL examples, reward functions are deterministic.
Note that it is probably more common to define the reward function as a function of the state $S_t = s$ and action taken in $s$, $A_t =a$, and write it as $R(s, a)$ or $r(s, a)$, i.e.
\begin{align}
R(s, a)
&=\mathbb{E}[R_{t}|S_{t}=s, A_t = a]\\
&=\sum_{r \in \mathcal{R}} r p(r \mid S_{t}=s, A_t = a)
\end{align}
Note that we're now using $p(r \mid S_{t}=s, A_t = a)$ and not $p(r \mid S_{t}=s)$.
You could also define $R(s, a, s')$. See this or Sutton & Barto's book for more details.

I see, thank you for clarifying this and for providing the link.


text:
What is the Bellman equation for V(s) in the case of a deterministic environment?
I am currently trying to practice reinforcement learning for an agent on a grid. The grid is deterministic. Since the grid is deterministic, to calculate the value for each grid square from the reward and next state, we could simply apply the following Bellman equation:
$$V(s)=\max_a(R(s,a)+\gamma V(s'))$$
and not
$$V(s)=\max_a(R(s,a)+\gamma\sum_{s'}P(s,a,s')V(s'))$$
which would be used for non-deterministic grids?

as far as I can tell from your notation the two are actually equivalent, but as $P$ is deterministic you can omit writing this as it is simply 1 for the transition that happens and 0 otherwise.

Your 2nd equation is the Bellman optimality equation (BOE) for $V$. So, to emphasise that, you could write it as follows
$$
V^\color{red}{*}(s)
=
\max_a(R(s,a) + \gamma\sum_{s'} P(s,a,s') V^\color{red}{*}(s'))
\tag{1}\label{1}
$$
If you let

$P(s, a, s') = \mathcal{P}_{ss'}^a = Pr(s_{t+1} = s' \mid s_t = s, a_t = a)$,
$R(s,a) = \mathcal{R}_s^a = \mathbb{E}\left[R_{t+1} \mid s_t = s, a_t= a\right]$, where $R_{t+1}$ is a random variable that represents the reward at time step $t+1$,
$R(s, a, s') = \mathcal{R}_{ss'}^a = \mathbb{E}\left[R_{t+1} \mid s_t = s, a_t= a, s_{t+1} = s'\right]$, and
$R(s,a) = \sum_{s'} \mathcal{P}_{ss'}^a \mathcal{R}_{ss'}^a$ (by the law of total expectation)

then we can rewrite \ref{1} as follows
\begin{align}
V^\color{red}{*}(s)
&=
\max_a \left(\sum_{s'} \mathcal{P}_{ss'}^a \mathcal{R}_{ss'}^a + \gamma\sum_{s'} \mathcal{P}_{ss'}^a V^\color{red}{*}(s') \right) \\
&=
\max_a \sum_{s'} \mathcal{P}_{ss'}^a \left( \mathcal{R}_{ss'}^a + \gamma  V^\color{red}{*}(s') \right)
\tag{2}\label{2}
\end{align}
which exactly the same equation as equation 4.1 in Sutton & Barto's book, 1st edition, whose online version you can find here. In the 2nd edition, they use a different but equivalent notation.
Knowing the definition of $V^\color{red}{*}(s)$ is not sufficient to find it. You need an algorithm. If you are not familiar with dynamic programming algorithms applied to MPDs, then take a look at this chapter. Anyway, you can use e.g. policy iteration or value iteration.
Now, back to your actual question. If your environment is deterministic, then
$$
P(s,a,s')
=
\begin{cases}
1, \text{if } f(s, a) = s'\\
0, \text{otherwise}
\end{cases}
$$
where $f$ is the (deterministic) transition function.
This implies that only one summand in $\sum_{s'} P(s,a,s') V^\color{red}{*}(s')$ might be non-zero. That summand is specifically $V^\color{red}{*}(s')$, when $f(s, a) = s'$, because, in that case, $P(s,a,s') = 1$, and $1$ times $x$ is $x$.
So, the BOE simplifies to
\begin{align}
V^\color{red}{*}(s)
=
\max_a(R(s,a) + \gamma V^\color{red}{*}(f(s, a)))
\end{align}
So, you're correct.

Thanks for this incredibly detailed reply! If the agent comes across a state with a reward value, it can choose to collect the reward and enter a terminal state or to just move to the state and not collect the reward, thus not entering terminal state. Given this, we would then be introducing a possible transition probability of $T(s, exit, numberedState) = 1$ and $T(s, move, s') = 1$? For which we would then apply Equation 1?

@Krellex I'm not sure I understand what you mean. Why do you say that the agent can choose or not to collect the reward? The reward should always be collected. Maybe you mean that the reward function is stochastic (i.e. $R(s, a)$ does not always return the same number but with a certain probability returns some number)? I also don't understand why you mention the "terminal state". Do you know what a terminal state is? What do you mean by "numberedState"? Maybe the "numberedState" refers to the terminal state in your notation?

Anyway, I think you're asking whether you would apply or not the 1st equation for different actions. I don't think I can answer this question definitely because, as I said, the equations you're showing us are just the definitions of the Bellman optimality equation. In fact, we're taking a max with respect to $a$, so you cannot really "choose" with these equations. If you tell me which specific algorithm you're using to solve your problem, I might be able to address your doubts.

You're correct, that's the definition of the Bellman equation in the deterministic case.
You can refer to the Wikipedia article of the Bellman equation where $F(x, a)$ is the reward function, with $x$ the state, $T(x,a) = x'$, the transition function, and $\beta$ the discount factor.


text:
What is the difference between CNN-LSTM and RNN?
I'm starting to study RNN for a project of video prediction, but I encounter these CNN-LSTM models. Initially, I thought that is another name for RNN, but I think I get it wrong. Since I'm a beginner can someone explain me the difference between them?

Why would "CNN-LSTM" be another name for RNN, when it doesn't even have RNN in it? Can you clarify this? What is your knowledge of RNNs and CNNs? Do you know what an LSTM is?

An LSTM is a specific type of RNN. So let's just focus on the CNN part in CNN-LSTM.
What's the difference between a plain RNN and a CNN-RNN, (more generally called convolutional RNN or ConvRNN)?
The equations which define a vanilla RNN are (I'm omitting a bias term for clarity):
$h_t = \sigma_h(W_{hx}x_t + W_{hh}h_{t-1})$
$y_t = \sigma_y(W_{yh}h_t)$
where

$h_t \in \mathbb{R}^m$ is the hidden state
$x_t \in \mathbb{R}^n$ the input sequence (e.g.  a string of characters)
$y_t \in \mathbb{R}^l$ is the output vector
$W_{hh} \in \mathbb{R}^{m\times m}$, $W_{hx} \in \mathbb{R}^{m\times n}$ and $W_{yh} \in \mathbb{R}^{l\times m}$ are matrices of parameters
$\sigma_h$, and $\sigma_y$ are activation functions (such as the ReLu)

Now, in an CNN-RNN, the parameter matrices $W_{hh}$ and $W_{hx}$ are convolution matrices. We use them for input sequences which are typically better handled by convolutional neural networks, such as a sequence of images.


text:
What is the difference between a policy and rewards?
I don't understand the difference between a policy and rewards. Sure, a policy tells us what to do, but isn't the output of a neural network trained on rewards basically a policy (i.e. choose the maximum reward)? What is different about the policy? An extra softmax applied?

A (stochastic) policy is a set of conditional probability distributions, $$\pi(a \mid S=s), \forall s \in \mathcal{S}.$$ If the policy is deterministic, then it is a function $$\pi: \mathcal{S} \rightarrow \mathcal{A},$$ so $\pi(s) = a$ is the action that policy $a$ returns in the state $s$ - it always produces this same action for a given state, unless it's a non-stationary policy. A policy is also called a strategy (in game theory). To be usable, a stochastic policy must be turned into a decision rule, i.e. you need to sample from it. A stochastic policy generalises a deterministic one.
The rewards are the outputs of the reward function. A reward function can be deterministic (which is often the case) or stochastic. It can be defined as $$R : \mathcal{S} \times \mathcal{A} \rightarrow \mathcal{R},$$ where $\mathcal{R} \in \mathbb{R}$ is the reward space. If it's stochastic, then
\begin{align}
R(s, a)
&= \mathbb{E}\left[ R_t \mid S_t = s, A_t = a\right] \\
&=\sum_r r p(r \mid S_t = a, A_t=a),
\end{align}
where $R_t$ is the random variable that represents the reward at time step $t$ and assuming a finite MDP. Stochastic reward functions generalise deterministic ones.
So, policies are probability distributions or functions, while rewards are numbers. So, there's a difference between their definitions, even though they are related.
How are they related? In different ways. The most important one is that an optimal policy for a given MDP is the one that, if followed, maximises the expected return, which is a function of the reward (typically, a discounted  sum of rewards). The definition of an optimal policy makes more sense if you also know the definition of a value function - I recommend you take Sutton & Barto's book and read the relevant sections.

Detailed answer, thanks. But I still don't get how these two things are different under the hood, meaning the neural network output.

In deep RL, the neural network can represent the policy. To find the optimal policy, you need to explore the environment and collect rewards and understand which actions lead to more rewards. You then use these rewards to update the neural network, so the policy. So, the rewards are used to train the neural network. Maybe you should look at the equations of Q-learning or any other RL algorithm. In them, $Q(s, a)$ is the neural network, while $r$ is the reward. There's clearly a difference. One is a function, the other is a number, as I say in my answer.

I recommend that you read the first chapters of the book mentioned in my answer. I think you don't understand the difference because you're missing some details, but I don't know which ones. Let me give you this example - hopefully, you're more familiar with supervised learning. Do you think that labels (e.g. dog or cat) are the same thing as a neural network that classifies dogs and cats? Here, the labels would be analogous to the rewards, while the classifier would be analogous to the policy. See this.

Maybe I'm confused because a lot of papers, articles etc. refer to them as distinct things. What you're telling me I think is that the policy is the method (nn or other) and the reward is how we get to the method (which could also be value+advantage or something else).

I wouldn't say that a policy is a method, if you're using it as a synonym for algorithm, although a decision rule can be thought of as an algorithm. Maybe you meant model (and not method)? A neural network is essentially a model, i.e. it can be used to mimic something. That something is usually a function. Any (continuous) function. That's why neural networks are called function approximators, i.e. they approximate functions. In this case, the function that the neural network approximates is the policy. A policy is the solution to an optimisation problem defined in terms of an MDP.

So, we can say that a policy is the "solution" to an MDP, which is the "problem". As part of the definition of the MPD, you have a reward function. So, a problem is defined in terms of the reward function. Typically, the optimization problem you want to solve is defined in terms of this reward function. I could probably go on and on and try to explain more things, like the value function, but this discussion will become long. That's why I recommend you read the book. RL is not as trivial as it may seem at the beginning. It requires some time to get used to all the definitions and details.

Feel free also to ask more separate questions on the site, but comments should not be used for long discussions.

Thank you, this cleared up many things. It's just that the bibliography sometimes is a bit confusing.

Typically, the answer to a control problem in reinforcement learning (RL), is "What is the policy that maximises total reward?".
In really simple scenarios, that you might study to understand RL basics, this can be so obvious that you could just search ahead and discover the correct action without really using RL.
However, sticking to the formal definitions in RL allows you to tackle harder problems, where it is not obvious how to decide what to do, or maybe even how to access the best rewards.
In the formalism of RL:

Reward is a real-valued signal received after each time step. For RL theory to be useful, the distrbution of reward values should be the same if start state and action are the same (you may also make the distribution depend on the next state, but that doesn't change the rule, it just means reward and next state will be correlated).

A policy is a function for action choice, it takes the state as input, and returns a distribution over all possible actions $\pi(a | s): \mathcal{S} \times \mathcal{A} \rightarrow \mathbb{R} = \mathbb{Pr}\{A_t=a|S_t=s\}$. It may be deterministic and directly return a chosen action $\pi(s): \mathcal{S} \rightarrow \mathcal{A}$

These are clearly very different things. Often we are interested in finding a policy that maximises an aggregate of rewards, but that doesn't make the policy simply related to rewards. Think of a chess game - which piece should you move to win? There is no immediate reward, and the consequence for a good or bad move will happen much later. The relationship between the policy in an early game state, and the reward at the end (e.g. +1 for a win, -1 for a loss) is not at all clear.
Only in the very simplest of scenarios, where taking actions directly led to already-predictable rewards, could you use your idea of $\pi(s) = \text{argmax}_a r(s, a)$ where $r(s,a)$ was a reward function. For a start, this will not help you look ahead more than one time step. What if the best reward now was followed by a really bad reward?
RL has the toolkit you can use to decide how to offset immediate vs future gains, and also how to learn what to do when you don't already have a simple function $r(s,a)$ which tells you what is going to happen in advance.


text:
What are the steps to derive the original GAN loss function from the generalized version?
I am trying to understand how the loss function from the original GAN paper
$$\min_{G} \max_{D} V(D, G)=\mathbb{E}_{\boldsymbol{x} \sim p_{\text {data }}(\boldsymbol{x})}[\log D(\boldsymbol{x})]+\mathbb{E}_{\boldsymbol{z} \sim p_{\boldsymbol{z}}(\boldsymbol{z})}[\log (1-D(G(\boldsymbol{z})))]$$
relates to generalization in the Nagarajan & Kolter (2017)
$$\min_{G} \max_{D} V(D, G)=\mathbb{E}_{\boldsymbol{x} \sim p_{\text {data }}(\boldsymbol{x})}[f(D(x))]+\mathbb{E}_{\boldsymbol{z} \sim p_{\boldsymbol{z}}(\boldsymbol{z})}[f(-D(G(z)))]$$
where supposedly the original loss function could be recovered via
$$f(x) = -\log(1 + \exp(-x))$$
But when I try to substitute $f$ into the generalized version of the loss function I am not getting the original one. What would be the correct steps to recover the original loss function?

There are some definitions that may cause confusion here.
In the original GANs (the first formula), the output from the discriminator connects to a sigmoid activation, the second formula is the real value from the last layer of the D model which you can find in section 3.1

note that this convention slightly differs from the standard formulation
in that in this case the discriminator outputs the real-valued “logits”

Rewrite the first formula, consider the output from $D(x)$ is the real value, it will become:
$$ \min_{G} \max_{D} V(D, G)=\mathbb{E}_{\boldsymbol{x} \sim p_{\text {data }}(\boldsymbol{x})}[\log {\frac{1}{1+exp(-D(x))}})]+\mathbb{E}_{\boldsymbol{z} \sim p_{\boldsymbol{z}}(\boldsymbol{z})}[\log (1-\frac{1}{1+exp(-D(G(z)))})] $$
Now, it's able to proof the first and second formula is the same.


text:
What is exactly sparse annotation?
What is exactly sparse annotation? Is it different from labeling images?
I've been reading a paper about vessel segmentation and have some issues understanding this part.

Can you please provide the name of and link to the paper that you mention in this post, in order for us to have more context?

in computer vision sparse annotations are images for which only a bunch of pixels are annotated. The term sparse in fact is used as in linear algebra, where a sparse matrix indicate a matrix composed mostly of zeros (in this case zeros meaning no label given).
The idea is that is takes much less time to label just a bunch of pixels rather than entire images. This annotations of course can't be use to train models on fully supervised learning tasks, since classic supervised losses require dense annotations.
So this type of annotations are instead used in weakly supervised learning, a combination of unsupervised techniques combined with constrains coming from the sparse annotations, or in active learning set ups, as a staring point to generate automatically dense annotations from sparse ones, to then only use the automatically generate dense annotations for a classic supervised training.


text:
If Least-Squares TD is computationally more expensive, then why is it more data efficient than semi-gradient TD(0)?
In Sutton-Barto (Section: 9.8 Least-Squares TD, page 228):
Authors say that  Least-Squares TD is the most "data efficient" form of linear TD(0). Later, in this section, they say the computational complexity of semi-gradient TD(0) is $O(d)$ and that of Least-Squares TD is $O(d^2)$.
If Least-Squares TD is computationally more expensive, then why is it more data efficient than semi-gradient TD(0)? In fact, what do authors mean by "data efficiency"?
I think authors mean by data efficiency to avoid from iterative nature of semi-gradient TD(0). However, the Least-Squares TD is also iterative (please see the box at page 230 of the book). I am confused. How do we know that convergence of Least-Squares TD takes less time steps compared to semi-gradient TD(0)?

Can you also rephrase this sentence "I think authors mean by data efficiency to avoid from iterative nature of..." because it's not very understandable? It seems that some words are missing or there are typos.

This is just a partial/general answer that addresses one of your doubts. I will let others address your question about the specific algorithms that you are mentioning.
Data efficiency refers to the number of samples or observations that you use during learning, as a function of the number of episodes, time steps or maybe time, to achieve a certain performance (e.g. return). I think that data efficiency is a synonym for sample efficiency, at least, in reinforcement learning. In RL, a sample could e.g. be a tuple $\langle s_t, a_t, r_{t+1}, s_{t+1} \rangle$.
The time and space complexities of an algorithm indicate how much computation and memory the algorithm needs asymptotically. These are usually expressed as a function of the size of the input (which is measured in different ways, e.g. number of elements in a list or maybe the number of bits to represent a number), but this does not always have to be the case (e.g. you can also express the time complexity as a function of the output size, for a certain type of algorithm known as output-sensitive algorithm, or maybe as a function of the number of layers in a neural network). In your case, it's expressed as a function of $d$.
Now, let's say that we have 2 learning algorithms, $A$ and $B$, and that, on average, algorithm $A$ requires roughly $10^6$ samples to obtain the return $R$, while algorithm $B$ requires only $10^3$ samples to obtain the same return $R$. We can conclude that $B$ is more sample efficient than $A$. However, let's say that, at every time step, $B$ does an expensive calculation (e.g. it performs an algorithm that has exponential time complexity), while $A$ does a constant-time computation. We can say that $A$ has a better time complexity. Later, maybe we can come up with a new algorithm $C$, which has the same time complexity as $A$, but better sample efficiency, so we would probably use $C$ rather than $A$, but we could still choose $B$, provided that its time complexity is acceptable (e.g. exponential time would not be acceptable). So, you could also have an algorithm $D$ that is as sample efficient as $B$, but, at every step, it performs an update that requires exponential time, but it still requires the same number of time steps to get the same return $R$.
Note that time-steps in RL are not the same thing as time in time-complexity. Maybe this is where your confusion partially lies.
If the explanations above were confusing, then I think you should rigorously review the concepts of time/space complexity.
As a side note, computational learning theory is a branch of machine learning that studies learning algorithms from a theoretical/mathematical standpoint, i.e. the algorithms are analysed in terms of time complexity, space complexity and sample complexity, which is related to the sample efficiency, but not exactly the same thing.


text:
How do I design the network for Deep Q-Network?
I am playing with deep q-learning and I am thinking about what the proper architecture of a network used for deep q-learning is.
I have a very simple environment, basically a 18x18 matrix, where 3 objects live. It is basically a penalty shootout, one player, one ball and one keeper. The player should learn to score goals. The player can move forward, to the left, to the right, and 45° left and 45° right. The keeper moves left and right in front of his goal.
I already used a CNN approach where I fed the 18x18 matrix as image, onto three layers with 64 units each and let the agent learn. Then I used a network with one input layer and 38 features, three hidden layers with 64 units each, and finally I used 2 hidden layers with 256 units each. ReLU and Adam.
All approaches worked. Now, I want to find out which approach works "best". But I don't know in which direction to go. All of the training sessions so far took considerable long time. The last approach e.g. takes a few days till the agent figures out not to move of the environment, that he needs to hit the ball, and in which direction he need to shoot the ball.
During the training sessions, I need to adjust the reward function in order to improve the agent. I start with a learning rate of 0.01 and then I reduce it to 0.001 after 300.000 episodes, each limited to 100 steps.
I read about grid search, but I expect this needs enormous amount of time, and I don't have access to lots of processing power, only a simple laptop style GPU.
What is the strategy to get to a better network?

What is the strategy to get to a better network?

There are a few different strategies that you can use to search for good hyperparameters in reinforcement learning RL, but you should be aware that this is a hard problem:

Even with supervised learning on fixed datasets, efficient hyperparameter searches are not a solved problem.

RL adds more hyperparameters for exploration vs exploitation, and management of the training data (e.g. in DQN, the replay memory size, how often to update the target network). These hyperparameters also need to be tuned and will interact with NN-specific hyperparameters.

RL requires data collection as part of the learning process, and this can be more expensive than training any neural network internal within the agent. As well as simulating or sensing the environment and on-the-fly feature engineering, this usually requires running the network forward in order to enact the current policy, separate from prediction/loss calculations.

RL control involves learning then forgetting "interim" functions in a sequence of gradual improvement. Compared to learning an optimal policy directly in a supervised manner, this can take many times more effort.

In RL, learning curves can be highly variable, making quick decisions based on early performance unreliable.

It is not much a surprise given all this, if a bit disappointing for solo researchers, that cutting edge RL on complex problems is mainly handled by large organisations with deep pockets to cover the compute costs.
As a hobbyist, I don't know or have access to large scale solutions, where some new strategies could open up due to the amount of compute available. Assuming you are in a similar situation, perhaps some of the following could help:

First and foremost, decide what your goals are for with the current experiment. In different scenarios you will want to focus on certain kinds of change:

Is it to make the best agent possible for a target environment?
Is it to learn a specific RL technique?
Is it to test the limits of a specific RL method or agent?
Is it to noodle around with the agent and environment to gain general experience about how the combination behaves when you vary things?

For "best agent" scenarios, learning the problem domain and feature engineering based on that knowledge could help more than hyperparameter tweaking.

If you are not in a "best agent" scenario, consider whether you have learned enough from the current experiments and move on to some other environment.

If you and your computer have nothing better to do, and want to explore possible improvements, arrange for experiments to run when you are not using the computer for other projects, e.g. overnight, and keep an editable "TODO" list of next things to try. This could be simple grid searches (if training is relatively quick) or ideas for hyperparameters inspired from theory, effectively random search, third-party suggestions or simply to see what happens.

Automate as much of this as possible, including putting checkpoint files in dedicated per-experiment folders, using some kind of versioning system to label the experiments.

With some experience (maybe from just "noodling around" on this or other projects) you may spot learning patterns/behaviours that imply changing specific hyperparameters would be useful. This knowledge does not always transfer when systems (or other hyperparams) are very different, but often enough it does.

You can pre-test some NN architectures for capacity to learn a policy or value function by making a training dataset based on the policy or returns for a reasonably good agent - either an expert or a previous RL experiment - then choosing by loss or accuracy or some other metric. This will mainly help you rule out poor architectures without running a full RL training. It probably won't help you to select the best out of the good ones, because once a NN has capacity to learn your test data within reasonable accuracy, differences that you cannot test this way will become more important.

One good rule of thumb is to avoid large/complex NNs, and search for the simplest NN that learns your target function well. This will speed up training times, although it does mean you will rarely explore what happens with larger more sophisticated networks.

It is often worth working on code optimisation for speed, if your CPU time is a constraint, then extra developer time optimising the environment and the agent will pay back well, allowing you to run more experiments. You can look into Python toolkits like numba (which compiles a limited set of Python to C functions) to speed up custom environments.

Related to this, disabling visual output from the environment during training can give you a large speed improvement. You can switch it back on when reviewing agent behaviour.

There are more advanced hyperparameter searches than grid search that may be promising (including use of Bayesian statistics, or genetic algorithms, or even more RL to set hyperparameters), but when your compute budget is low you may find educated guessing and some random search works just as well or better.

Thank you very much for your input, it is highly appreciated. I jumped into DQN/RL beginning this year and I am still playing with my first environment. The code has already lots of parameters and switches so I can easily change stuff and try different settings. Like disabling visual output during training, record the environment as video during inference, prioritized vs. uniformly sampled experience replay and all the other stuff you mentioned.

When I started, I was little bit overwhelmed from the possibilities to try and lack of confidence in that I am doing, that I did not pay attention to record what I did. But the agent worked good enough and I was happy to have come so far. Then I started over again wirh a new model and more sorrow planning and recording. But still, its quite hard to understand the interplay of all the parameters. one of the bigger issues I have is to understand how to measure improvements.

I track the average episode rewards and from visually observing the agent after a training session I can see improvements, but when I look at the loss and accuracy of the NN, its going up and down, with a tendency to go up. And when I moved from the simulated environment to real robots with TF on Raspbian, even more work came up, to get the robot to behave somehow similar than the agent in the simulated environment. He is still an amateur in soccer, but he is able to score goals against a keeper with a simple hardcoded behavior driven by the position of the ball. :)


text:
When calculating the max in DQN, do I have to calculate the Q for every possible action for a particular state?
I'm trying to implement the DQN paper using python/pytorch for my needs (https://www.cs.toronto.edu/~vmnih/docs/dqn.pdf). I'm studying the main algorithm:

I am a bit confused about the $\gamma* \max Q$ when setting the $y$. My model essentially takes a state and outputs a single float value (reward, cost, call it whatever). Do I have to calculate the Q for every possible action in my action space for that particular state or simply the Q of the state?

Do I have to calculate the Q for every possible action in my action space

Yes, for the given state vector $\phi_{j+1}$ you must calculate the action value for all possible actions from that state. That is the only way that you can calculate $\text{max}_{a'} Q(\phi_{j+1}, a'; \theta)$ used to set the TD target $y_j$.

or simply the Q of the state?

That is not defined. Q is an action value, and can only be calculated when you know both the state and the action.
In practice, your neural network in DQN will be one of two designs:

It takes state and action concatenated as input and models the state-action value function directly: $Q(s,a): \mathcal{S} \times \mathcal{A} \rightarrow \mathbb{R}$. In this case you will need to run a mini-batch of all allowed actions in the same state in order to find $\text{max}_{a'} Q(\phi_{j+1}, a'; \theta)$

It takes state as input and models the state-action value for all actions at once: $f(s): \mathcal{S} \rightarrow \mathbb{R}^{|\mathcal{A}|}$. In this case you will only need to run the forward action once to find $\text{max}_{a'} Q(\phi_{j+1}, a'; \theta)$, but you will need to manipulate the resulting TD target data to ensure the only error gradient is from the selected action - typically this is done by running the network forward on the current state $\phi_{j}$ and modifying that vector with the new TD taget only for the taken action $a_j$

These designs are not mentioned in the pseudo-code because they are an implementation detail somewhat separate from the theory. You will find the second design is more common in DQN implementations, as it often has better performance (in terms of raw speed processing each state).

Thank you. Truth be told, my implementation is V-value rather than Q-value for various reasons, thus the confusion on my part.

@AntonisKarvelas You can use state value V if you are using a model and/or afterstates (which are a kind of hybrid state/action and common in e.g. board and card games)- in which case you will need to code to look ahead to get all possible $V(s')$ depending on the action or afterstate choices. You will almost definitely be using the first architecture in your case.

I'm doing exactly this. Is there a paper or an implementation I can look into? So far I'm following my idea of this hybrid and I may be doing something silly.

@AntonisKarvelas I am sure there will be some implentations using DQN online, as well as various MCTS/"Alpha Zero" variations. For just the Q-learning side I produced a tic tac toe learner in Python and published in on Kaggle here: https://www.kaggle.com/code/slobo777/tic-tac-toe-agent-using-q-learning (the original repo I deleted, as I never filled in with planned other games)


text:
Reinforcement learning algorithms for large problems that are not based on a neural network
I have a large control problem with multidimensional continuous inputs (13) and outputs (3). I tried several Reinforcement learning algorithms like Deep-Q-Networks (DQN), Proximal Policy Optimization (PPO) and  Advantage Actor Critic (A2C). Unfortunately, they all yield poor results. As far as I understand, they are all based on neural networks. Because of this I think it might be possible that the neural network itself could be a problem as it might not be able to learn the mapping between inputs and outputs (I have experienced this in several other applications).
So, are there state-of-the-art reinforcement learning algorithms for large problems with multidimensional continuous state spaces and actions?

There are many state-of-the-art reinforcement learning algorithms for large problems with multidimensional continuous state spaces and actions. All of them rely on some sort of function approximator.
You can use any RL algorithm with really any sort of function approximator, whether a neural network,  support vector machine, decision tree, or any other method. Every RL algorithm you mentioned can use any of these function approximators instead of a neural network, if so desired.
However, almost all state of the art results today use neural networks. This is largely due to 2 reasons, one theoretical and the other empirical. The theoretical reason is that neural networks have a universal function approximation theorem which roughly states that given an arbitrarily large network, they can approximate any continuous function. The empurical reason is that for complex problems, neural nets tend to outperform all other methods.
So to more directly address your question. Yes you can use the othe methods I mentioned above. But its probably a bad idea. You are likely better off with either a larger neural network, a neural network architecture more well suited to your problem, or perhaps there are other issues in your approach you have missed. However, it is very unlikely the issue you face is a fundamental problem of neural networks.

Thanks for your answer. You wrote that "You are likely better off with either a larger neural network, a neural network architecture more well suited to your problem". How can I change this in the algorithms Deep-Q-Networks (DQN), Proximal Policy Optimization (PPO) and Advantage Actor Critic (A2C)? I currently use StableBaselines3 (https://stable-baselines3.readthedocs.io/en/master/) and here you normally don't specify the network size and type of network. Is it generally possible to use e.g. DQN, PPO and A2C with another type of Neural network, like LSTM or Convolutional NN?

Thanks chessprogrammer for your answer. Any comments to my last comment? I'll highly appreciate every further comment from you.

Any further comments?

@PeterBe First off, if you appreciated my answer please upvote it and mark as correct. Second, Yes it is generally possible and even common to use all those algorithms with LSTMS or CNNs. If the library you use does not allow that simply use another one. I reccommend this:  https://www.tensorflow.org/agents

Thanks for your answer. I upvoted and accepted it.


text:
Why doesn't the inception score measure intra-class diversity
It's mentioned here that there is no measure of intra-class diversity with the inception score:

If your generator generates only one image per classifier image class,
repeating each image many times, it can score highly (i.e. there is no
measure of intra-class diversity)

However, isn't it "easy" to look at the variance of the outputs of the classifier for a given class (e.g. if you only output 0.97 for all the images of your GAN class then there is no intra-class diversity but if you output 0.97, 0.95, 0.99, 0.92, there is diversity?). I'm struggling to understand why this is hard to do (but I might be missing something!).

Can you please put your specific question in the title? I understand that you're confused about the inception score and how it is related to "intra-class diversity" (whatever that really means), but that is not a question. A question is something like "Why doesn't the inception score ...?"

Done! I edited my the post.

For reference, a recap of Inception Score:
The inception score is computed by comparing the categorical output distributions of an inception model, given examples from real vs synthetic images. If the synthetic images produce similar class distributions as the real images, the inception score is high, otherwise it is low.

However, isn't it "easy" to look at the variance of the outputs of the classifier for a given class

Say you want to generate multiple horses and the model learns to generate horses with different colors but always in the same pose - then your class probabilities will vary, but I wouldn't call this very diverse horse generation. This is how I would understand what is meant by your cited statement.
The output distributions from the inception model contain class information but very little information of specific image features. Thus, the inception score cannot be sensitive to intra-class variations of the generator.

"multiple horses and the model learns to generate horses with different colors but always in the same pose", yes you're right, I haven't thought of that, variance of the output's classifier would then vary but there isn't as much variability as we'd expect

Adding on top of Chillston answer:
regarding the variance, it is unfortunately not so straight forward. The problem being that most deep learning models are not calibrated, hence small intra-class variation might lead to large probability variations for the winning class. Maybe one way to account for this issue would be to compute the mutual information between the generated predictions and a prior expected distribution, for example uniform probability distribution 1/n with n number of expected difference within class, like horse poses to use the same example as Chillstone, but I found no reference about similar attempts, plus coming up with a proper prior expected distribution doesn't sound trivial at all. I guess the reason is that the inception score was designed for generic GANs (i.e. GANs trained to generate generic classes from CIFAR and similar dataset) so without having in mind to measure variability within classes.

That's a good point - Inception is trained to be invariant to intra-class variations, so to capture this a different model or at least a differently trained inception model might be better suited. Maybe something that identifies data transformations like Capsule Net

"small intra-class variation might lead to large probability variations for the winning class" is a weird concept to me, but I've seen this several times. Isn't the function output = f(input) continuous with regards to the input?

not sure if I'm missing something, but the continuity of the final activation function doesn't tell you much about the properties of the function learned by a  classifier.

@EdoardoGuerriero All the functions are continuous right? The last activation function is, the one to get from layer n-1 to n is too, etc.?

sure, but again continuity doesn't imply strong constrains. The final mapping learn by a classifier is highly non linear, hence it's not surprising (even though undesired in many situations) that small changes can lad to big differences in predictions.

Fair enough, isn't there some way to force the behaviour: small changes in the input -> small changes in the output? By integrating this into the loss or maybe by training n networks and picking the one that shows the behaviour the most out of the n networks if they all converge to similar but not same local minima?

the problem here is how to numerically define "small change". A topic that kinda fit in this discussion but limited to CNN is shift invariance, in which people try to solve the issue of CNN misclassifying images that are shifted by a few or just one pixel in one direction. That's already a way to force a model to behave constantly with respect to a predefined small change.

another problem, a more conceptual one, is that in general we do want to learn some big changes for small input differences. It's the trade off between generalization and overfitting. So I guess that what would be required to train such a a model is actually a proper dataset. And indeed a custom loss, with an extra error component that compare for example the probability returned for a class with the expected probability we want to observe for each element belonging to that class.

Just adding to some comments, I would think that in general, a classification model might not be the best type of model to use for intra-class variations, because its task is to be invariant to those. It always output the same result even though two horses look very different. As a general idea, maybe using a VAE model would be more suitable, as these models are build to capture as much detail as possible, right? Still experiments would have to show if this is feasible to use as a score metric like the inception model.


text:
Should the range of target values match the range of activation function used in the output layer?
Suppose I use a tansig activation function in the output layer of an artificial neural network giving me outputs in the range $[-1,1]$ and my model is applied to a binary classification problem, should my target labels be -1 and 1 or 0 and 1? I've always used 0 and 1, but now I'm questioning this.

Why are you not using sigmoid/softmax for binary classification?

Would you recommend this? Maybe I should do that. Are there any guidelines available in terms of suitable activation functions for the hidden layers too?

Yeah, In general, relu for hidden layers and sigmoid for the output layer.

Amazing!! Thank you! Seems to have improved results massively by replacing tansig with sigmoid. Now I'll try replacing my tansig hidden layer functions with relu.

Yes, you should use an activation function that match the range of your ground truth labels, or the other way around, i.e. apply a normalization function to the labels to match your activation function.
If the range of model predictions and target differ in range, the model might still learn but the convergence will be slower, since you're basically allowing a broader range or loss values. With both predictions and labels within range [0, 1] for example, the difference between a prediction and its label will also be in the same range. If you allow predictions to be in range [-1, 1] then you could have errors larger than 1, for example $p=-1, t=1, |t-p|=2$.
The decision about mapping the predictions to the targets range or the way around depends on the specific case you tackling. Sigmoid and tanh for example behave differently with respect to the gradients, the latter producing larger gradients, as you can see from the derivatives comparisons. So if you want larger gradients you might want to keep the tanh and map you targets to the range [-1,1]

If you have already trained your model to predict either -1 or 1, and now your target variable is either 0 or 1, if -1 predicted by your model is the same as 0 in your target variable, then there are two ways you can do this:

Use a postprocessing function, which maps the models output, -1 becomes 0, and 1 remains as it is
Replace your target labels, 0 becomes -1, and 1 remains as it is


text:
How can I vectorize fictional single word (not sentence!) for classification?
I am working on fictional single words (names) generator that have to sound like words from a given sample. I have the generator up and running that gives reasonable words 70% of time. I thought of improving this value, ideally to ~99% (so no manual step is necessary to discard clearly missed words).
I've already attempted fuzzy matching to any word in the initial sample (and rejecting words below given thresholds), and this winded up reasonable answers to 95%-99%, but in my experiments this approach is rejecting too many well-sounding names (even 60-70 rejections per 1 generated name - this removes a lot of entropy from the initial set).
Now, I am thinking of using classification instead to tackle the problem from another angle: using classification to discard the generated name.
The problem I have is I have to vectorize a single word based on its sound for classification. I've already excessively searched the Internet and the only solution I see are for vectorizing texts, not single words.
So, the question here: what kind of algorithm for vectorization of single fictional word based on its sounding have I missed?

After more excessive search I have found the description of Phonetic Matching algorithm by Alexander Beider and Stephen Morse which basically does what I need to do on filtering


text:
What algorithms are used in Artificial General Intelligence research?
I've read on wiki that already in 2017 there were over 40 institutions researching AGI, and I wonder what type of algorithms are being studied and developed in this field.
For example, for comparison with narrow AI, where models/techniques, such as ANNs, CNNs, SVMs, DT/RT, evolutionary algorithms, or reinforcement learning are used, how would AGI models differ? Do they also use these models but in some specialised way or maybe these algorithms are completely new and different from these currently used in narrow AI?

No one has ever invented a practical AGI. However, there are different approaches to the creation of AGI:

universalist (e.g. AIXI)
symbolic
sub-symbolic (e.g. neural networks)
hybrid

See also this answer.
So far, the only approach we can say that has really created a (theoretical) AGI is the universalist. The main universalist approach is known as AIXI, a theoretical framework for AGI proposed by Marcus Hutter at the beginning of the 2000s, but it is incomputable, although there are at least 2 computable approximations: AIXItl and MC-AIXI (FAC-CTW), the latter is also practical for simple problems, like tic-tac-toe. Another universalist solution is the Godel machine by Schmidhuber. Here is an answer that explores the importance of AIXI to the AI field.
So, if you really want to learn about and do research on AGI, you could start with AIXI or Godel machines. However, to understand them, you need to have some basic understanding of RL, theory of computation, probability theory, and other concepts. So, you could also start with reviewing these concepts, before getting into AIXI.
Having said that, people that are doing research on RL, neural networks, evolutionary algorithms, cognitive architectures, or other AI topics might have the ultimate goal of developing an AGI. Some people might think that some kind of reinforcement learning (see this) and neural networks (see this) to represent the learned information is necessary for developing an AGI, because humans and other animals also learn by reinforcement and have neural circuits. Other people think that we need some kind of cognitive architecture and some means of doing logical thinking. Other people think that we need to reverse engineer the neocortex (see Numenta's work) or that we need neuromorphic chips.
So, although our current approaches to RL and our current models have only been used to solve narrow problems, I think it is possible that these or advanced/modified versions of them can be used to create a practical AGI.
The other answer mentions knowledge graphs, but KGs have only been used to solve narrow problems too, e.g. they are used by Google to display specific information about important people when you search for them on their engine. They are also probably used in personal assistants, like Alexa, Siri and Google Assistant.
In short, if you're interested in AGI algorithms and models, look into AIXI, Godel machines, Numenta's work, cognitive architectures (like SOAR or OpenCog), in addition to the more traditional ML approaches, like RL. I also recommend that you read the paper Artificial General Intelligence: Concept, State of the Art, and Future Prospects.

Current AGI approaches are very heterogenous and therefore there are no dominant algorithms.
Nevertheless, I would suggest you to have a look at Knowledge Graphs and the related algorithms to build and query the graphs, for instance here.


text:
Does this modified version of the triplet loss function introduced with SBERT that uses the cosine similarity make sense?
I am working on a modified version of the triplet loss function introduced with SBERT, where instead of the Euclidean distance we use the cosine similarity. The formula to minimize is max( (|s_a*s_p| / |s_a|*|s_p|) - (|s_a*s_n| / |s_a|*|s_n|) + e, 0) where s_a is the embedding of the anchor sentences (the context), s_p is the embedding of the positive sentence (correct continuation) and s_n is the embedding of the negative sentence (wrong continuation).
I would like to check that the function I came up with makes sense from a theoretical point of view. Where should I look to check which features a loss function should satisfy?
Motivation for the question: I'm getting my hands dirty with contrastive loss functions, and this is an easy variation I came up with.

You should share with us the loss function (the formula) that you came up with. Maybe you should also explain how it's different from the original loss and why we came up with this new one.

I modified the question as recommended.

Edit your post to include this info directly there. Note that you can use mathjax on this site.

I'm getting my hands dirty with contrastive loss functions, and this is an easy variation I came up with.

I modified the title to be more specific and to be the question that I think you're asking. Make sure that's the case. Again, I would highly recommend that you use mathjax to format the loss function.

A Loss function is just a function with a minimum.
In machine learning though, we also require the loss function to be differentiable, otherwise no backpropagation and hence no weight updating. Moreover basically every deep learning library relies on autograd, so if the function is not differentiable your code will simply crash.
Stronger but not compulsory condition could be Lipschitz continuity, i.e. ensuring that the function decrease at a constant rate. Intuitively, a loss function should output high values for big differences between predictions/targets and small values for small changes, otherwise the update of the weights will risk to be too big (no convergence) or too small (easily stuck on local minima).
Regarding your loss, the only issue I see is that you're replacing a proper metric, i.e. euclidean distance, with a function that is not a metric, i.e. cosine similarity (which does not respect the triangular inequality, hence it's not a metric). So I would be careful and test what kind of values you get with some dummy data to understand if it still behave as a proper loss.

Thanks heaps! That's exactely what I was looking for.


text:
Why is $P(X_{t+1} \mid e_{1:t}, e_{t+1}) = \alpha P(e_{t+1} \mid X_{t+1}, e_{1:t}) P(X_{t+1} \mid e_{1:t})$ true in Norvig & Russell's book?
On page 572 of Norvig & Russell's AI book (edition 3)

Going from the first line to the second line in one shot like that, I am lost.
Can someone walk me through it step by step?
I tried but got:
$$
\frac{P(X_{t+1}) * P(e_{1:t} | X_{t+1}) * P(e_{t+1} | X_{t+1}) }{P(e_{1:t}, e_{t+1})}
$$
and then do not know how to turn it into that second line that says (using Bayes's rule)

You can use mathjax to format the equations.

Let me denote the events with simpler symbols

$A = X_{t+1}$
$C = e_{1:t} = e_1, \dots e_t$
$D = e_{t+1}$

So, we can rewrite
$$
P(X_{t+1} \mid e_{1:t}, e_{t+1}) = \alpha P(e_{t+1} \mid X_{t+1},  e_{1:t}) P(X_{t+1} \mid  e_{1:t})\tag{1}\label{1}
$$
as follows
$$
P(A \mid C, D) = \alpha P(D \mid A,  C) P(A \mid  C)
\tag{2}\label{2}
$$
Now, note that $C, D$ is a shorthand for $C \cap D = B$, so $P(A \mid C, D) = P(A \mid B)$.
So, by the Bayes rule, we have
\begin{align}
P(A \mid B)
&= \frac{P(B \mid A) P(A) }{P(B)} \\
&= \frac{\color{red}{P(C, D \mid A)} P(A) }{P(C, D)}
\tag{3}\label{3}
\end{align}
Let's expand the red term
\begin{align}
\color{red}{P(C, D \mid A)}
&= P(B \mid A) \\
&= \frac{P(B, A) }{P(A)}\\
&= \color{blue}{\frac{P(C, D, A) }{P(A)}}
\tag{4}\label{4}
\end{align}
Now, let $E = C, A = C \cap A$. So, let's continue writing \ref{4}
\begin{align}
\color{blue}{\frac{P(C, D, A) }{P(A)}}
&=\frac{P(D, E) }{P(A)} \\
&= \frac{P(D \mid E) P(E) }{P(A)} \\
&= \frac{P(D \mid C, A) P(C, A) }{P(A)} \\
&= \color{green}{\frac{P(D \mid C, A) P(A \mid C) P(C) }{P(A)}}
\tag{5}\label{5}
\end{align}
Let's put \ref{5} back into \ref{3}
\begin{align}
P(A \mid B)
&= \frac{\color{green}{\frac{P(D \mid C, A) P(A \mid C) P(C) }{P(A)}} P(A) }{P(C, D)} \\
&= \frac{ P(D \mid C, A) P(A \mid C) P(C) }{P(C, D)} \\
&= \frac{ P(D \mid C, A) P(A \mid C) P(C) }{P(D \mid C) P(C)} \\
&= \frac{ P(D \mid C, A) P(A \mid C) }{P(D \mid C)} \\
&= \frac{1}{P(D \mid C)} P(D \mid C, A) P(A \mid C) \\
&= \alpha P(D \mid C, A) P(A \mid C)
\tag{6}\label{6}
\end{align}

I got lost at that line, let A = C and A after (4).

@mLstudent33 It's let $E = C, A$. But $C, A$ is a shorthand for $C \cap A$ (i.e. the intersection of C and A, so I am denoting $C \cap A$ by $E$ in order to apply the regular definition of joint and conditional probabilities. Note that events are sets. I've edited the answer to add another step that clarifies what I did.

Thanks but I still do not see how 5 can be substituted for P(B | A).  Oops I see it now

P(C,D | A) is P(C,D | A) :)

Are you returning back or the question is impressive enough?

@hanugm I've restarted to answer questions every once in a while. I answer the ones that I either can answer quickly or I like. This was one that I liked because it was about the Bayes rule ;)


text:
Do the values over 0.5 mean my model classified the data as a "1" label and vice versa?
I am doing binary classification using an LSTM and my output layer is 1 neuron with a sigmoid function. My labels are either 0 or 1.
from tensorflow.keras.optimizers import SGD
model = Sequential()
model.add(LSTM(64,activation='sigmoid', input_shape=(PERCENT_DATA,1)))
model.add(Dropout(0.2))
model.add(Dense(1,activation='sigmoid'))
opt = SGD(lr=0.001)
model.compile(loss = "binary_crossentropy", optimizer = opt, metrics=['accuracy'])
model.summary()

An example of the outputs is
array([[0.9854203 ],
       [0.94532275],
       [0.946043  ],
       [0.5212766 ],
       [0.45969874],
       [0.53517556],
       [0.88838553],
       [0.05345109],
       [0.06565621],
       [0.5552153 ],
       [0.07443756],
       [0.62434113]])

Do the values over 0.5 mean my model classified the data as a "1" label and vice versa? Or should I try to find an optimal threshold from these values that will result in the highest accuracy? Or do these values mean something else like the confidence?

Yes, the values over 0.5 mean the output should have "1" label.
As I know with Keras you cannot set the optimal threshold, but you still can use the trick if you want, for example, the expected threshold is 0.8, you can minus the output then clamp the minimum cap of it to 0. {out = max(out-(thresh-0.5), 0)}
However, finding the optimal threshold for a model is not recommended in a real project since it may adapt to your validation set only, try to work more with data. I am not familiar with NLP data, but I am sure there are some methods to make data more variant. Label smoothing (as Keras documents) can be a good start.

Thanks for your help. I found that 0.5 isn't a good threshold for predictions, and have calculated a better one by testing other decimal numbers. Would this work?

maybe in this case. you can try it, by the method I said above


text:
Is the initial teacher model in the Noisy Student algorithm noised?
Reading through the paper on the Noisy Student algorithm, I have a quick question about how the initial teacher model is built.
In step 1 of the algorithm, the loss function is defined such that it looks like the initial teacher model is trained using noise. But then when you get to step 2 it says the teacher model you use to generate your labels for the unlabeled data should not be noised.
So, should you be adding noise or not for the first teacher model that you train?

Short answer: yes, the teacher model should always train with noise.
The noise here is just the augmentation and regularization that you may feel familiar with, the author used three kinds of noises:

Data augmentation
Dropout
Stochastic Depth (drop out for residual block).

In step 2, the authors said that only the sample which has a high score (high confidence)

Specifically, we filter images that the
teacher model has low confidences on since they are usually out-of-domain images.

And they even add or remove samples to ensure the distribution of the dataset

we duplicate images in classes where there are not enough images. For classes where we have too many images, we take the images with the highest confidence.

And the most important thing, they use the bigger (more capacity, more parameters) model as a student

we want the student to be better than the teacher by giving the student model enough capacity

Now, just think simple, those methods help to enhance the model, which makes the model stronger so teachers, students, or any model should apply those to the training phase and remove them to predict at the test phase (teacher predicts labels).
In my opinion, this method is just like label smoothing  but replaces the hyper-parameters with the learning one (the teacher).


text:
What is the difference between a loss function and reward/penalty in Deep Reinforcement Learning?
In Deep Reinforcement Learning (DRL) I am having difficulties in understanding the difference between a Loss function, a reward/penalty and the integration of both in DRL.

Loss function: Given an output of the model and the ground truth, it
measures "how good" the output has been. And using it, the parameters
of the model are adjusted. For instance, MAE. But if you were working
in Computer Vision quality, you could use, for instance, SSIM.

Reward: Given an agent (a model) and an environment, once the agent
performs an action, the environment gives it a reward (or a penalty)
to measure "how good" the action has been. Very simple rewards are +1
or -1.

So I see both the loss function and the reward/penalty are the quantitative way of measuring the output/action and making the model to learn. Am I right?
Now, as for DRL. I see the typical diagram where the agent is modelled using a Neural Network (NN).

I am trying to interpret it, but I do not understand it.
Is it the policy related the loss function somehow? Where is the loss function? How does the reward feed the NN? Is it a parameter for the loss function?
Maybe my confusion has to do with identifying NN with supervised learning, or with not getting this with Q-learning or so.. Can anyone help?

1. Question: The difference between loss and reward/penalty

So I see both the loss function and the reward/penalty are the quantitative way of measuring the output/action and making the model to learn. Am I right?

You are partially right:
You could interpret the negative reward as a loss that you want to minimize. But the model cannot learn from the reward directly. The reason for that is that you (usually) cannot formulate the reward as a differentiable function of the model parameters. Hence, you cannot compute a gradient purely from the reward. You need a second function - the loss - that is

Differentiable and
Depends on the parameters inside your model.

Only then you can compute a gradient w.r.t. the model parameters and make the model learn. This already answers another question:

Is it the policy related the loss function somehow?

Yes! The policy HAS to be a part of the loss function, otherwise you wouldn't be able to do gradient decent to optimize the model.
A simple way to get from reward to the loss is implemented in the REINFORCE algorithm. To understand its loss term, you have to know that the model does not output definitive actions, but rather a probability distribution over all possible actions. Here is the loss function that REINFORCE uses to optimize the model:
$loss = -log\_likelihood(action) \cdot return$
As you can see, the loss is the product of the negative log likelihood of the action and the $return$. The return correlates with the reward (Return is the discounted reward which distributes the reward received at timestep $t$ backwards to also reward actions that led to the reward). Intuitively this means that for a large reward, the model wants to be very certain about which action to take. So there you have it: The reward reflects how successful you are in the environment and the loss is the optimization objective maximizing the probability to take good actions.
2. Question: The Schematic doesn't include the loss function
The image you posted depicts how you collect the data which you use to optimize the model. You would run this loop of taking an action and receiving a reward until you have a full batch of data. On this batch you would then compute the loss and update the model. It's quite important for reinforcement learning to gather batches and not use single steps for optimization, because otherwise the resulting gradient would be very noisy and in most cases prevent proper optimization.
The main issue why your gradient would be noisy is the credit assignment problem:
Lets assume the environment is a grid world and the task is to walk forward for 7 steps. You start at $S$ and you will get a reward as soon as you reach location $G$:

The reward will show you that you have done something right but multiple actions where responsible for getting the reward (not just the last step forward). However, you never exactly know which actions where the right actions and which actions where actually bad. You might have taken a very inefficient route to the goal.
The problem that you don't know which actions contributed to getting the reward is called the credit assignment problem. And in fact you can only have a good heuristic to assign the reward. This has to be compensated by computing the model update on batches rather than single steps. One such heuristic is the general advantage estimate. This is a function that you apply to your reward before plugging it into the loss function.

Maybe my confusion has to do with identifying NN with supervised learning

One major difference of supervised learning and reinforcement learning lies in the credit assignment problem: In supervised learning you input a sample and you know what should come out. In RL you only have a rough estimate on how good you where but you will (usually) never know what should come out of your model, because there are multiple possible ways to reach the goal.
Hope this helps.

This all looks correct, but the focus on REINFORCE is adding a bit much IMO when the OP is considering the (IMO) conceptually simpler DQN. You also have the loss function wrong at the moment (it should be return, not reward used as multipler for log loss - you might use reward in a gradient bandit).

Thanks for the feedback, I understand your points. You are right, I was a bit lazy putting reward in the formula and I will update this in my answer. I agree that the core concept of Q-Learning is more straight forward, although I find the loss of REINFORCE a bit easier to understand that's why I went with that. IMO it's also a bit more aligned with the RL concepts, but to be honest it's what I have been in contact with more than Q-learning - so I might be biased

Ultimately, in RL, the policy is what you want to find. It's the solution to the Markov Decision Process (MDP). But you don't want to find any policy, but the optimal policy, i.e. the one that will make the agent collect the highest amount of reward in the long run (i.e. the highest return), if followed.
In deep RL, the policy might be represented by a neural network, which gets a state as input and produces a probability distribution over actions, which we can be denoted by $\pi(a \mid s; \theta)$, where $\theta$ is the parameter vector. If you change $\theta$, you also change the output of the policy.
The reward function function tells how good the actions that the agent takes are. So, it can be defined as the function $r : \mathcal{S} \times \mathcal{A} \rightarrow \mathcal{R}$, where $\mathcal{R} \subset \mathbb{R}$ is the reward space. So, $r(s, a)$ is the reward that the agent receives for taking action $a$ in state $s$. For example, in the game of chess, if you win the game, $r$ could return $1$, while, if you lose the game, it could return $-1$. The reward function is usually pre-defined, in the sense that it's part of the problem definition. You don't have to learn it, although you can learn reward functions with inverse RL techniques.
So, the reward function is not the objective/loss function, but the objective function is usually defined in terms of the reward function, in the same way that the mean squared error (MSE) in supervised learning is defined in terms of the correct labels or targets.
Now, what could be the loss function in RL? It depends on how you train the RL agent. For example, in DQN, the loss function is
$$
L_{i}\left(\theta_{i}\right)=\mathbb{E}_{s, a \sim \rho(\cdot)}\left[\left(y_{i}-Q\left(s, a ; \theta_{i}\right)\right)^{2}\right]
$$
where
$$
y_{i}=\mathbb{E}_{s^{\prime} \sim \mathcal{E}}\left[\underbrace{r}_{\text{Reward}}+\gamma \max _{a^{\prime}} Q\left(s^{\prime}, a^{\prime} ; \theta_{i-1}\right) \mid s, a\right]
$$
is the target value for $Q\left(s, a ; \theta_{i}\right)$, which is what we're trying to learn and it's represented by the neural network with parameters $\theta_{i}$. $Q$ is known as the value function, which is defined as the expected return, from which we can derive the policy. So, it gets as input a state and an action, not the reward. It produces an estimate of the expected return, which is defined as the sum of rewards.
This answer should answer all your questions and doubts. See also this answer about the relationship between supervised learning and reinforcement learning.


text:
How is state aggregation defined mathematically here?
Sutton-Barto's RL book (page 203):

State aggregation is a simple form of generalizing function approximation in which
states are grouped together, with one estimated value (one component of the weight
vector w) for each group. The value of a state is estimated as its group’s component,
and when the state is updated, that component alone is updated. State aggregation
is a special case of SGD (9.7) in which the gradient, $\nabla \hat{v}(S_t,w_t)$, is 1 for $S_t$’s group’s component and 0 for the other components.

Nothing is clear for me here. How is state aggregation defined mathematically here?

@nro,  it is done.

Do you understand this part "State aggregation is a simple form of generalizing function approximation in which states are grouped together"? Do you know what function approximation is? Can you edit your post to tell us what you understand about this definition? Note that it's a definition. So it's not something that you can derive from other things.

@nbro, I hate your comments and what you are doing is to prevent people receiving help from others. You should not be in this group. You are simply UNNECESSARY!

I'm trying to help, not just you, but people that would like to answer your question(s). That's what I've been doing here for a long time. I'm trying to understand what you understand or not about the definition. They are providing a definition and you're asking for another definition. This does not make sense to me, unless you didn't understand that this is a definition. Having said this, you should show some respect to someone that helped to shape this community and to make it a valuable place where people can come and receive good answers to their questions.

@nro, I have asked so far more than 20 questions and you never answered any: what you did was to be negative and undermine. Please leave the group!

We are volunteers here. If you ask a question, it doesn't mean it will be answered. Even if I knew the answer or I could try to give an answer, I might choose not to. People could not have the time or will to answer your questions. I would recommend that you do as I said, tell us what you understand about that definition and why you're asking for another definition. Then have you read this?

@nro, on top of  these you do not have any RL knowledge. My question is quite clear: they provided a definition by "words" which is very vague and I asked the mathematical definition to clearly understand what they mean. We are not stupid and you are not genius! Let me repeat again: please leave the group!

I have "some" RL knowledge. You see confirm that here.

What nbro is doing is helping to refine the question so that it is more likely to get a useful answer. That is a standard part of workflow on the site, and many of us do it. You may view it as some barrier to getting help (because it requires you to do work and define your problem more precisely), but if you engage with it and attempt to clarify the details that are being asked about, hopefully you will find it is not. This is unfortunately a common "clash" between new members asking questions and longer-term experts, and is why many Stack Exchange sites get a reputation for being unfriendly.

@Neil Slater, my question is indeed very clear: "How is state aggregation defined mathematically here?" I am asking its mathematical definition and really there is nothing to clarify.

I have answered with a mathematical definition, using notation (as well as I can, I am not a notation expert). If you want a more text-based answer or guide to what is going on, then we need to do the clarification that nbro is asking for. Some people from a maths background may appreciate my attempt, and perhaps you are one of them. However, that's unusual outside of math-heavy Stack Exchanges (where my attempts at notation would probably be laughed at)

Here is a mathematical definition for state aggregation, which I think covers all the necessary elements to make something an aggregation:

Define a collection of state groups $\mathscr{G} = \{\mathcal{G}_1, \mathcal{G}_2, \mathcal{G}_3 ...  \}$
$\forall \mathcal{G} \in \mathscr{G}: \mathcal{G} \subset \mathcal{S}$ (each group is a subset of all states)
$\mathcal{S} \subseteq \bigcup_{\mathcal{G} \in \mathscr{G}} \mathcal{G}$ (the groups cover all the states)
$\forall \mathcal{G} \in \mathscr{G}: \forall \mathcal{H} \in \mathscr{G}, \mathcal{H} \neq \mathcal{G}:\mathcal{G} \cap \mathcal{H} = \phi$ (all groups are disjoint - this is usefully relaxed for systems described later in S&B such as tile coding)
$|\mathscr{G}| \lt |\mathcal{S}|$ (number of groups is less than number of states - that is what makes it an aggregation as opposed to some other mapping)

The text

is 1 for $S_t$’s group’s component

Is referring to using the subscript $j$ in $\mathcal{G}_j$ for the group that contains $S_t$, or alternatively some function $g(s): \mathcal{S} \rightarrow \mathbb{Z}$ that returns a group id or index for each state. Using this function can map the state value $s$ into a one-hot encoded vector $\mathbf{x}$ which is then used in the linear regression estimator $\hat{v}(s, \mathbf{w}) = \mathbf{w}^T\mathbf{x}$.
Worth noting that the above defines an arbitrary state aggregation. Usually you would try to do better than that and group states together because there is some reason to expect them to have similar state values in general.

@ Neil Slater, I think that is what I need:  https://ai.stackexchange.com/questions/12206/state-aggregation-methods

@ Neil Slater,   I was looking for this definition:  \begin{equation}
v(\mathbf w) = x_1w_1 + x_2w_2 + ... + x_{10}w_{10}
\end{equation}

@ Neil Slater,  for your answer to be a full answer, we need the definition of $\hat{v}(\bf{w})$ to see clearly why  $\nabla \hat{v}(S_t,w_t)$, is 1 for $S_t$’s group’s component and 0 for the other components. If you have time, it may be better to include the definition of  $\hat{v}(S_t,w_t)$. I am sure that this is not clear for many readers of Sutton-Barto's  RL book.

@DSPInfitinity: That's not part of the definition for state aggregation, which is about how you get $\mathbf{x}$ from $s$ i.e. the part where you aggregate the states and form a feature vector. In fact it seems you were not really asking about state aggregation, but about the definition of linear regression in RL?

I added a note about the linear estimator.


text:
Without planning, why does each episode only add one additional step to the policy?
In Sutton & Barto's RL book at page 165 for Example 8.1, they say:

Figure 8.3 shows why the planning agents found the solution so much faster than the nonplanning agent. Shown are the policies found by the n = 0 and n = 50 agents halfway through the second episode. Without planning (n = 0), each episode adds only one additional step to the policy, and so only one step (the last) has been learned so far. With planning, again only one step is learned during the first episode, but here during the second episode an extensive policy has been developed that by the end of the episode will reach almost back to the start state.

I have the following question:
Why, without planning (n = 0), each episode adds only
one additional step to the policy? What does "adding one additional step to the policy" mean?

What does "adding one additional step to the policy" mean?

This is an informal shorthand for how many backup steps from a non-zero reward or learned value will receive a meaningful update. That is, an update with actual data other than the initial bootstrap.
This is due to three things:

Bootstrap updates in basic TD only look one timestep ahead, e.g. from $s,a$ to $s',a'$, with the update $Q(s, a) = Q(s, a) + \alpha(r + \gamma Q(s', a') - Q(s, a))$

Only the last step in the example environment has a non-zero reward.

Only values that have already received at least one "meaningful" update are themselves useful in bootstrapping real data back to earlier time steps. Without such an update, they only have initial arbitrary values.

With background planning, as in Dyna, there is a chance of choosing to base the update on a state, action pair that has already been updated with some non-zero* data, whilst the agent is exploring elsewhere.
Without background planning, and only using single-step backups, initially only the ends of episodes will receive updates with meaningful data.
You can also use multi-step backups, or eligibility traces - as in TD($\lambda$) - to increase the number of steps that get updated at once. These options each have their own pros and cons.

* Technically it is not non-zero that matters, but "different from other experience". Initially the agent experiences a bunch of states and actions that all look the same to it in terms of its estimates of expected future reward. Before an agent can learn to choose between actions it needs to experience results that are different between them.


text:
Which approach can I use to generate forged signatures from real ones?
I am in internship period and I'm working on a signature verification problem.
This process needs real and forged signatures. All I have are the real signatures (like 30 signatures per person), and I have to generate fake signatures (forged) from those real ones in order to augment data and balance it for the main purpose, which is signature verification.
During my search, I found amazing videos explaining GANs and conditional GANs, pix2pix, etc.
I'm wondering if you have an idea on how to fit this model or an other approach to generate forged signature close to the real one but not as much as real.
Here is an example to clear the view a little bit. Those are the 3 images real for person 8 (img1,9,17)

and those are the forged one :

Those examples are token from cedar dataset.

You could indeed try pix2pix or cycle gans. Considering that you already found an available dataset you could just clone the original CycleGAN repo, plug the dataset in and see how it does. Of course at the end you'll have 2 generators, one that map real signatures to forged ones and vice versa, but that's how image translation works, at the end of the training you can just discard the second one.

thanks for your reply, I already took a look at CycleGan, the ovjective here is to generate forgery signature from the real signature,
i can find a data forgery for the model like the exemples are from cedar dataset,
but in production when i will use the model to generate a forged signature to my real one, i have just reals, do i will not need the forged one as input?

a cycle gan train effectively 2 models. $G_{rf}$ and $G_{fr}$ in the drawing. Each model take a single image as input, $G_{rf}$ takes a real signature and generate the correspondent forged one and $G_{fr}$ takes a forged signature and try to generate the real version of it. You need both models only during training. But in production you can simply use just $G_{rf}$, feed it to it the new real signatures you'll collect and generate the unknown forged ones.

i clearly understand , thank you very much ,
is there any implementation close to my use case or some resources can facilitate this task for me?

well as I wrote in the answer I think the best way is to clone the official cycle gan implementation from github. The training scripts and config file are well written and documented so it will be as simple as typing in the terminal python train.py --dataroot path_to_your_dataset. Of course you'll need to download the cedar dataset yourself and rename the folders accordingly to the repo expecte format, which is trainA trainB testA testB where A in your case will contain real signatures and B forged ones.

Okey ,i will try this one , thank you verry much.

i tried the suggested solution and the output is like this :  it's too semilare, how can i deforme the signature please?


text:
Why does this neural network require 2 hidden layers to completely fit my data?
I have been working toward implementing my own Neural Network library in C++ for fun.
I have managed to implement an XOR solving network based on widely available information. Now, I wanted to try a classification problem and use the cross-entropy as my loss function.
I have created a dataset of 729 records (all possible combinations of 3 numbers between 0 and 8):
Input Features | expected Output
--------------------------------
{0, 0, 0}      | {0.0, 1.0}
{1, 0, 0}      | {1.0, 0.0}
...
{8, 8, 7}      | {0.0, 1.0}
{8, 8, 8}      | {0.0, 1.0}

The output should be {0.0, 1.0} when there is no 1 in the input, and {1.0, 0.0} when there is a 1 in the input. (the inputs are normalised to the -1.0 to 1.0 range).
I was having a hard time getting my network to correctly accomplish this classification. Because I had the whole dataset, I tried training it on the complete dataset in an attempt to have it fit perfectly. I wanted to see it fit perfectly to provide me some assurance that my implementation was correct.
Numerous attempts failed:
# hidden | learning |  results
  units  |  rate    | (accuracy)
--------------------------------
3        | 0.00001  | 72%
3        | 0.000001 | 60%
5        | 0.0001   | 80%
5        | 0.00001  | 75%
6        | 0.0001   | 79%
6        | 0.001    | 91%
10       | 0.001    | 72%
10       | 0.0001   | 91%
10       | 0.00001  | 71%
20       | 0.0001   | 91%
20       | 0.00001  | 74%
20       | 0.002    | 77%

These were all over 20k epochs, a momentum of 0.5, relu activation on all units, softmax and cross-entropy loss for the output. Some of these were unreliable too, meaning sometimes they would not learn at all, but starting with a new set of random weights worked.
You can see that it capped out at 91% accuracy. But, if I add a second hidden layer, so that my network looks like:
Input Layer | Hidden Layer 1 | Hidden Layer 2 | Output Layer
      3     |        6       |        2       |      2

I instantly get 100% accuracy using 0.001 learning rate after only 1000 epochs.
Why does this additional hidden layer work?
Is there a way to know when I should use additional layers?

Your data is simply too non linear. You can check it by simply plotting the 2 different classes with different colors on a 3d plot. Unfortunately this is not always possible, and there's no rule of thumb to establish when the data are too non linear or how many layer you should use.
But in general you should be aware that every layer in a neural network works as a linear transformation of you data coordinates, with some non linearity added only by the final activation function, but in general a single layer lead to an almost linear mapping, hence the failure of all your attempts with a single layer.
This blog post offer beautiful visualizations of what I mean with an in depth analysis of the limitations of the classic neural networks design (hidden layer = $Wx + b$). It surely offer lot of insights even though I repeat again that there's no explicit answer to your question about how to calculate or predict how many layers are required for a task.
Also just a technical note, combinations implies no repetition, so your dataset is actually a triple cartesian product of all numbers between 0 and 8.

code to generate the plot (in python):
import matplotlib.pyplot as plt
import itertools
import numpy as np

def main():
    # generate prods data
    numbers = [i for i in range(0, 9, 1)]
    prods = [c for c in itertools.product(numbers, repeat=3)]
    prods = np.array(prods)
    # get labels
    labels = np.array([1 if 1 in prods[i, :] else 0 for i in range(prods.shape[0])]).T
    # separate data in classes 1 and 0
    prods_0 = prods[labels == 0]
    prods_1 = prods[labels == 1]
    # plot data
    fig = plt.figure()
    ax = plt.axes(projection="3d")
    ax.scatter3D(prods_0[:, 0], prods_0[:, 1], prods_0[:, 2])
    ax.scatter3D(prods_1[:, 0], prods_1[:, 1], prods_1[:, 2])
    plt.show()

if __name__ == "__main__":
    main()


text:
Where can I find Norvig's version of the pseudocode for the A* search algorithm?
Can anybody point me to a link to Peter Norvig's version of the A* pseudocode. I've googled it interminably but found nothing.
It's the version that uses the Unexplored/Frontier/Explored data structures. I've looked at other versions (one from CMU), but I can't see how to get from that version to Norvig's version, and it's not in any of the versions of his text!
He wrote it down longhand in the online (Norvig & Thrun) lectures for his Stanford AI class. Those YouTube videos have since been taken down, and I don't have an old link to find it in the Wayback Machine. If anybody has the links to the whole suite of lectures on the Wayback Machine, that would be ideal.
But if a typewritten version were ever posted somewhere on the net (pdf, ppt, html, etc.), that would also be perfect.

The 2nd and 3rd editions of the Russell and Norvig's book (which you can find on the web) do not have a figure for the pseudocode of A*.
However, the graph search version of A* is equal to the pseudocode of uniform-cost search (UCS), which they provide in figure 3.14 (page 94, section 3.4.2.), but, rather than using $g$ (the cost of the shortest path from the start node to $n$), you use $f(n) = g(n) + h(n)$, where $h$ is an estimate of the shortest path to the goal from $n$, which should be admissible in order for A* to be optimal. See this answer.
You can find a screenshot of UCS below.

In the pseudocode, PATH-COST is $g(n)$. When they pop from the frontier, you should pop according to $f(n)$ in A*. See also section 3.5 of the 3rd edition of the book.


text:
What is multi-head attention doing mathematically, and how is it different from self-attention?
I'm trying to understand the difference between the concept of self-attention and multi-head attention. The latter is not actually too clear to me.
I understand that, in the case of self-attention, we start with a feature matrix $X \in \mathbb{R}^{n \times d}$, and then we use the same linear transformation $W$ to produce
\begin{align}
Q &= XW \\
K &= XW \\
V &= XW
\end{align}
and then we compute the following
$$X' = \text{softmax} \left(\frac{Q\cdot K^T}{\sqrt{d}} \right)V$$
where $X' \in \mathbb{R}^{n \times d}$ is a new version of the input matrix, where the pairwise interactions between the points will be encoded.
What is multi-head attention doing, from a mathematical point of view, and what's the difference? I know we are going to use three different linear transformations in this case (so no weight-sharing), but what exactly will be encoded using three different $W$? Maybe it's more the conceptual view that it's not too clear in this case.

First of all, I believe that in self-attention mechanism for Query, Key and Value vectors the different linear transformations are used,
$$
Q = XW_Q,\,K = XW_K,\,V = XW_V; W_Q \neq W_K, W_K \neq W_V, W_Q \neq W_V
$$
The self-attention itself is a way of using more general attention mechanism. You can check this post for examples of other mechanisms that can be used.
Multi-head attention is a way of grouping together a bunch of attention mechanism ( Usually they are all the same type ), which consists in just running multiple mechanism in parallel and aggregating the resulting set in some way. In here for example, the aggregation is done by concatenation and weighted sum of the outputs, e.g.
\begin{equation*}
\begin{aligned}
&\text{MultiHead}(Q, K, V)= [\text{head}_1, .., \text{head}_n]W^O & [..] \text{ meaning concatenation}\\
&\text{where head}_i = \text{Attention}(QW_i^Q,KW_i^K,VW_i^V) & \text{each head}_i\text{ is unique attention mechanism} \\
&\text{Attention}(\textbf{Q},\textbf{K},\textbf{V}) = \text{softmax}(\frac{\textbf{Q}\textbf{K}}{\sqrt{d_k}})\textbf{V} & \text{this can be other attention mechanism}\\
\end{aligned}
\end{equation*}

are you sure that they are different? In the following document people.tamu.edu/~sji/classes/attn-slides.pdf (slide 5) it is clearly stated that *in self-attention, we let Q=K=V=X *

Thanks for the comment, i checked it out.
I think what happens is a misunderstanding in what Q, K, V are. In the slides you have provided they are seen as already transformed X that is passed to attention mechanism and transformed once again, kind of in the same way as I have established i-th head in the multi-head attention.

But since they are transformed again after being passed to the self attention, it is actually equivalent to what I have described as self attention. The only difference is that its applied to pre-transformed X.
Imagine, that we are pre-transforming X to X*W. Now by applying the self attention I have described you are going to obtain the exact same result as in the slide 3 you have mentioned.
I adopted this point of view, since this is the way its described in Attention is All you need paper.
Check this for an example https://towardsdatascience.com/illustrated-self-attention-2d627e33b20a