text:
If neurons performed the operation of an entire layer, would that make the neural network more effective?
(I have a very primitive understanding of neural networks, so please forgive the lack of technicality here.)
I am used to seeing a neuron in a neural network as something that-

Takes the inputs and multiplies them by their weights,
then sums them up,
and after that it applies the activation function to the sum.

Now, what if it was "smarter"? Say, a single neuron could do the function of an entire layer in a network, could that make the network more effective? This comes from an article I was reading at Quanta, where the author says:

Later, Mel and several colleagues looked more closely at how the cell might be managing multiple inputs within its individual dendrites. What they found surprised them: The dendrites generated local spikes, had their own nonlinear input-output curves and had their own activation thresholds, distinct from those of the neuron as a whole. The dendrites themselves could act as AND gates, or as a host of other computing devices.

...realised that this meant that they could conceive of a single neuron as a two-layer network. The dendrites would serve as nonlinear computing subunits, collecting inputs and spitting out intermediate outputs. Those signals would then get combined in the cell body, which would determine how the neuron as a whole would respond.

My thoughts: I know that Backpropagation is used to "teach" the network in the normal case, and the fact that neurons are simply activation buttons is somehow related to that. So, if neurons were to be more complicated, it would reduce efficiency. However, I am not sure of this: why would complex individual components make the network less effective?

Say, a single neuron could do the function of an entire layer in a network, could that make the network more effective?

That depends what you mean by "more effective". In terms of number of neurons to achieve the same result, then you should need fewer units. In terms of being able to calculate an end result for any specific problem, then no, because you can generally solve a problem using simpler units by adding more of them.
If this could somehow be done using less resources, it might reduce overall costs. In a biological system, there are possibly overheads per cell in order to maintain it on top of the costs for calculation, so it may be better to do more than the simplest calculation in each cell. Further to that, there may be an optimal amount of processing that each cell could do (this is all conjecture on my part).
In an artifical neural network, the calculations are the only thing being considered, there is no separate overhead per neuron.
There are neural network architectures with complex "sub-units". Probably the most well known are the recurrent neural network designs for LSTM and gated recurrent units (GRU), plus "skip connections" in residual neural networks. For efficiency these are normally processed in groups per layer with matrix processing functions, but you can also view them as per-neuron complexities.

I am not sure of this- why would complex individual components make the network less effective?

If the complexity was not used, or not really needed, in some of the units, then it would be wasted capacity. In a biological system, this might correspond to maintaining cells larger than they needed to be. In an artificial system, it would mean using memory and CPU to calculate interim values that were not needed for the task at hand.


text:
What are the conceptual differences between regularisation and optimisation in deep neural nets?
I'm trying to wrap my mind around the concepts of regularisation and optimisation in neural nets, especially around their differences.
In my current understanding, regularisation is intended to tackle overfitting whereas optimisation is about convergence.
However, even though regularisation adds terms to the loss function, both approaches seem to do most of their things during the update phase, i.e. they work directly on how weights are updated.
If both concepts are focused on updating weights,

what are the conceptual differences, or why aren't both L2 and Adam, for example, called either optimisers or regularisers?

Can/should I use them together?

You are correct.
The main conceptual difference is that optimization is about finding the set of parameters/weights that maximizes/minimizes some objective function (which can also include a regularization term), while regularization is about limiting the values that your parameters can take during the optimization/learning/training, so optimization with regularisation (especially, with $L_1$ and $L_2$ regularization) can be thought of as constrained optimization, but, in some cases, such as dropout, it can also be thought of as a way of introducing noise in the training process.
You should use regularisation when your neural network is big (where big, of course, is not well-defined) and you have little data (where little is also not well-defined). Why do you want to use regularisation in this case? Because big neural networks have more capacity, so they can memorize the training data more easily (i.e. they can over-fit the training data). If the training data is not representative of the whole data distribution (that you are trying to capture with your neural network), then your neural network may fail on other data from that data distribution, i.e. it may not generalize. Regularization techniques, such as $L_1$ and $L_2$ penalties and dropout, limit the complexity of the functions that can be represented by your neural network (remember that, for a specific set of weights $\theta$, a neural network represents a specific function $f_\theta$), so they prevent your neural network from learning a complicated function that would just over-fit the training data.
Of course, you can also use regularisation when you have a very large dataset or your neural network is not that big. However, in principle, the case mentioned above is the case where you will likely need some kind of regularisation. So, as a rule of thumb, the bigger your NN is and the smaller your training dataset is, the more likely you will need some kind of regularisation.
The typical way to visualize that your neural network is over-fitting is to look at the evolution of the loss function (a type of objective function, which you want to minimize) for the training dataset and the validation dataset (a dataset that you do not use for training, i.e. updating the weights of the neural network). If the training loss is very small, while the validation loss is bigger (stays constant or even increases), as you train more the neural network, that's a good sign of over-fitting, and it suggests that you may need some kind of regularisation. However, note that, even with regularisation, it is not guaranteed that you will find a good set of weights that is able to generalize to all data (not seen during training), but it's more likely.
There are other forms of regularization, such as the KL divergence in the context of Bayesian neural networks or variational auto-encoders, but these are more advanced topics that you don't need to know now. In any case, the KL divergence has the same role as the other regularisation techniques that I mentioned above, i.e., in some way, it restricts/limits the possible functions that you can learn.

thank you. From your explanation that optimisation tries to identify the best parameters and regularisation tries to constrain them, is it correct to state that they can always work together as long as optimisation happens first? in other words, i first identify the parameters and them constrain them. Makes any sense?

@FelipeMartinsMelo You could do that, but you often do both at the same time, i.e. you include a "regularisation term" in your objective function, then you optimize this "regularized objective function". These explanations apply more to $L_1$ and $L_2$ regularisation than to dropout or other ad-hoc techniques. $L_1$ and $L_2$ regularisation are theoretically motivated as a "Bayesian way" of regularizing the weights (e.g. assuming that the weights are sampled from a normal distribution). You can actually derive $L_2$ regularisation from Bayes' rule by putting a Gaussian on the weights.

Maybe this answer will also be useful, especially one of the videos by Hinton that I am linking to there. Btw, in the case of dropout, we can think that regularisation is happening before updating the weights, the drop of the units happens before computing the output of the NN.

source: Stack Exchange

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

sort: votes


text:
Is the expected value we sample in TD-learning action-value Q or state-value V?
Both MC and TD are model-free and they both follow a sample trajectory (in the case of TD, the trajectory is cut-short) to estimate the return (we basically are sampling Q values). Other than that, the underlying structure of both algorithms is exactly the same. However, from the blogs and texts I read, the equations are expressed in terms of V and NOT Q. Why is that?

However, from the blogs and texts I read, the equations are expressed in terms of V and NOT Q. Why is that?

MC and TD are methods for associating value estimates to time step based on experienced gained in later time steps. It does not matter what kind of value estimate is being associated across time, because all value functions are expressing the same thing in general, which is the expected return conditioned on a "current position" within the MDP. In MC the association is directly with a sampled return, in TD with a sampled combination of immediate reward and a later value estimate - most commonly in TD the same kind of value estimate (e.g. matching later state value estimates to state values).
Both approaches can be analysed and used from the perspective of both state value (V) and action value (Q) functions. They also apply to other value functions - e.g. afterstate values.
It is quite common for textbooks and tutorials to use the slightly simpler state value function to explain how MC or TD learning work in general, outside of being used for any purpose. You can also use the state value function for model-free policy evaluation in MC and TD.
However, without a model, you cannot use state value function for control (i.e. to learn an optimal policy). To pick the best action using state values, you need to do something like this:
$$\pi(s) = \text{argmax}_a [ \sum_{r,s'} p(r,s'|s,a)(r + \gamma v(s'))]$$
The problem here is that $p(r,s'|s,a)$ is a model of the environment. So, if it is needed, the control method would not be model-free.
Hence when you learn about MC or TD in a control scenario, model-free methods to learn optimal policies, then you generally need to use an action value (sometimes you can use an afterstate value, if the action involves choosing the next state directly).
With an action value function, the greedy policy becomes:
$$\pi(s) = \text{argmax}_a q(s, a)$$
This does not refer to any model of the environment. So it can be used when you have none.

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


text:
What is the difference between Stochastic Hill Climbing and Simulated Annealing?
I am reading about local search: hill climbing, and its types, and simulated annealing
One of the hill climbing versions is "stochastic hill climbing", which has the following definition:

Stochastic hill climbing does not examine for all its neighbor before moving. Rather, this search algorithm selects one neighbor node at random and decides whether to choose it as a current state or examine another state

Some sources mentioned that it can be used to avoid local optima.
Then I was reading about simulated annealing and its definition:

At every iteration, a random move is chosen. If it improves the situation then the move is accepted, otherwise it is accepted with some probability less than 1

So, what is the main difference between the two approaches? Does the stochastic choose only random (uphill) successor? If it chooses only (uphill-successors), then how does it avoid local optima?

Russell and Norvig's book (3rd edition) describe these two algorithms (section 4.1.1., p. 122) and this book is the reference that you should generally use when studying search algorithms in artificial intelligence. I am familiar with simulated annealing (SA), given that I implemented it in the past to solve a combinatorial problem, but I am not very familiar with stochastic hill climbing (SHC), so let me quote the parts of the book that describe SHC.

Stochastic hill climbing chooses at random from among the uphill moves; the probability of selection can vary with the steepness of the uphill move. This usually converges more slowly than steepest ascent, but in some state landscapes, it finds better solutions.

So, SHC chooses at random one "uphill move", i.e. a move that improves the objective function (for example, if you're trying to solve the travelling salesman problem, a "uphill move" could be any change to the current Hamiltonian cycle, a solution, so that the new Halmitonian cycle has a shorter cost) among the uphill moves (so among some set of moves that improve the objective).
In simulated annealing, you perform some move. If that move leads to a better solution, you always keep the better solution. If it leads to a worse solution, you accept that worse solution with a certain probability. There are other details, such as how you accept the worse solution (which you can find in Russell and Norvig's book), but this should already clarify that SA is different from SHC: SA can accept worse solutions in order to escape from local minima, while SHC accepts only uphill moves.

thank you very much, now it is clear to me, one thing left, since SHC chooses only random uphill  moves, does this algorithm avoid local optima?

@yaminoyuki I think SHC can still get stuck in a local minimum. This should be due to the fact that SHC never takes a "downhill move". In any case, the book says that, in some "landscapes", SHC may find better solutions than the usual HC algorithm, and this may be true because SHC doesn't always choose the same uphill move and so has more stochasticity in it.


text:
How are afterstate value functions mathematically defined?
In this answer, afterstate value functions are mentioned, and that temporal-difference (TD) and Monte Carlo (MC) methods can also use these value functions. Mathematically, how are these value functions defined? Yes, they are a function of the next state, but what's the Bellman equation here? Is it simply defined as $v(s') = \mathbb{E}\left[ R_t \mid S_t = s, A_t = a, S_{t+1} = s' \right]$? If yes, how can we define it in terms of the state, $v(s)$, and state-action, $q(s, a)$, value functions, or as a Bellman (recursive) equation?
Sutton & Barto's book (2nd edition) informally describe afterstate value functions in section 6.8, but they don't provide a formal definition (i.e. Bellman equation in terms of reward or other value functions), so that's why I am asking this question.

Based on this and this resources, let me give an answer to my own question, but, essentially, I will just rewrite the contents of the first resource here, for reproducibility, with some minor changes to the notation (to be consistent with Sutton & Barto's book, 2nd edition). Note that I am not fully sure if this formulation is universal (i.e. maybe there are other ways of formulating it), but the contents of the first resource seem to be consistent with the contents in the second resource.
Setup
Let's assume that we have an infinite-horizon MDP
$$\mathcal{M} = (\mathcal{S}, \mathcal{Y}, \mathcal{A}, \mathcal{T}, \mathcal{R}, \gamma),$$
where

$\mathcal{S}$ is the set of states
$\mathcal{Y} \subseteq \mathcal{S}$ is the set of afterstates (aka post-decision states or "end of period" states [1], which can also be written as after-states)
$\mathcal{A}$ is the set of actions
$\mathcal{T}$ is the transition function
$\mathcal{R}$ is the reward function
$\gamma$ is a discount factor

Let

$y \in \mathcal{Y}$ be an afterstate
$f: \mathcal{S} \times \mathcal{A} \rightarrow \mathcal{Y}$ be a deterministic function (from state-action pairs to afterstates), so we have $f(s, a) = y$

The transition function $\mathcal{T}$ for $\mathcal{M}$ is defined as
\begin{align}
\mathcal{T}(s, a, s^{\prime})
&\doteq P ( s^{\prime} \mid f(s, a)) \\
&= P ( s^{\prime} \mid y)
\end{align}
A transition is composed of 2 steps

a deterministic step, where we apply the deterministic function $f(s, a) = y$, which depends on an action $a$ taken in the state $s$, followed by
a stochastic step, where we apply the probability distribution $P (s^{\prime} \mid y)$, which does not depend on the action $a$ anymore, but only on $y$

So, I have denoted afterstates with a different letter, $y$, because afterstates are reached with a deterministic function $f$, while other states, $s$ or $s'$, are reached with $P$.
After having taken the action $a$ in the state $s$, we get a reward (i.e. we get a reward in step 1), but we do not get a reward after the stochastic step (given that no action is taken).
So, we can define the reward function $\mathcal{R}$ for this MDP as follows
$$
\mathcal{R} (s, a, s^{\prime} ) \doteq \mathcal{R}(s, a)
$$
The situation is illustrated by the following diagram

So, here, $P$ is the stochastic transition function (i.e. a probability distribution) as used above. Note that, here, $r_t$ is a specific realization of $R_t$ (the random variable) in the formulas below.
State value function
Let's recall the definition of the state value function $v_\pi(s)$ for a given policy $\pi$ (as defined in Sutton & Barto, section 3.5)
\begin{align}
v_{\pi}(s)
&\doteq
\mathbb{E}_{\pi}\left[G_{t} \mid S_{t}=s\right] \\
&=
\mathbb{E}_{\pi}\left[\sum_{k=0}^{\infty} \gamma^{k} R_{t+k+1} \mid S_{t}=s\right],
\end{align}
for all $s \in \mathcal{S}$ and
\begin{align}
G_{t}
&\doteq
\sum_{k=0}^{\infty} \gamma^{k} R_{t+k+1} \\
&=
R_{t+1} + \gamma R_{t+2} + \gamma^{2} R_{t+3}+ \cdots \\
&=
\mathcal{R}(s_t, a_t) + \gamma \mathcal{R}(s_{t+1}, a_{t+1})+\gamma^{2} \mathcal{R}(s_{t+2}, a_{t+2}) +\cdots,
\end{align}
where $\pi(s_t) = a_t$ and $\mathcal{R}(s_t, a_t) = R_{t+1}$, for $t=0, 1, 2, \dots$. (So, note that $\mathcal{R} \neq R_t$: the first is the reward function, while the second is a random variable that represents the reward received after having taken action $a_t$ in step $s_t$)
The optimal state value function is defined as
$$
v_{*}(s) \doteq \max _{\pi} v_{\pi}(s)
$$
Afterstate value function
Similarly, we will define the afterstate value function, but we will use the letter $w$ just to differentiate it from $v$ and $q$.
\begin{align}
w_{\pi}\left(y\right)
&\doteq
\mathbb{E}_{\pi}\left[G_{t+1} \mid Y_{t}=y\right]
\\
&=
\mathbb{E}_{\pi}\left[\sum_{k=0}^{\infty} \gamma^{k} R_{t+k+2} \mid Y_{t}=y\right]
\\
&=
\mathbb{E}_{\pi}\left[
R_{t+2} + \gamma R_{t+3}+\gamma^{2} R_{t+4} + \cdots
 \mid Y_{t}=y\right]
\\
&=
\mathbb{E}_{\pi}\left[
\mathcal{R}(s_{t+1}, a_{t+1})+\gamma \mathcal{R}(s_{t+2}, a_{t+2}) + \gamma^{2} \mathcal{R}(s_{t+3}, a_{t+3}) + \cdots
 \mid Y_{t}=y\right] ,
\end{align}
where $\mathcal{R}(s_{t+1}, a_{t+1}) = R_{t+2}$, for all $t$.
In other words, the value of an afterstate $y$ (at time step $t$, i.e. given $Y_t = y$) is defined as the expectation of the return starting from the state that you ended up in after the afterstate $y$.
This seems reasonable to me and is similar to my proposal for the definition of the afterstate value function in the question, although I was not considering any deterministic functions in a potential formulation, and I was also not thinking of afterstates as intermediate states, reached by a deterministic step, between the usual states.
Similarly to the optimal state value function, we also define the optimal afterstate value function
$$
w_{*}(y) \doteq \max _{\pi} w_{\pi}(y)
$$
Afterstate value function defined in terms of the state value function
We can define the afterstate value function in terms
$$
w_{*}(y)
=
\sum_{s^{\prime}} P (s^{\prime} \mid y ) v_{*} ( s^{\prime} )
$$
In other words, $w_{*}(y)$ is defined as an expectation over the value of next possible states $s'$ from the afterstate $y$.
This seems to be correct and consistent with the above definitions.
More equations
In this and this resources, the state value function is also defined in terms of afterstate value function as follows
$$v_{*}(s)=\max_{a}\left(\mathcal{R}(s, a)+\gamma w_{*}(f(s, a))\right)$$
The Bellman equation for afterstate value function (from which an update rule can be derived) is given by
$$
w_{*}(y)
=
\sum_{s^{\prime}}
P(s^{\prime} \mid y )
\max_{a} (
\mathcal{R} (s^{\prime}, a)
+
\gamma
w_{*}(f ( s^{\prime}, a ))),
$$
which is really similar to the Bellman equation for the state value function.
Finally, we can also express the state-action value function in terms of the afterstate value function
$$
q_\pi(s_t, a_t)
=
\mathcal{R}\left(s_{t}, a_{t}\right)+\gamma w_{\pi}\left(f\left(s_{t}, a_{t}\right)\right)
$$
Given that this answer is already quite long, see the resource for more details (including an algorithm based on the afterstate Bellman equation).
Implementation
If you are the type of person that understands the concepts by looking at the code, then this Github project, which implements a Monte Carlo method that uses afterstates to play tic-tac-toe, may be useful. Afterstates are useful in tic-tac-toe because it is a 2-player game, where two agents take actions in turn, so we can estimate the action that you should take deterministically (as if it was the $f$ above) before the other agent takes an action (probabilistically), at least, this is my current interpretation of the usefulness of afterstates in this game (and similar games/problems).

In terms of "usefulness", one thing that is not captured so much in the formal treatment is  that the mapping function $f(s,a)$ can be a compression (and is in many games). If this applies, it means there are fewer afterstates to estimate values for than action/state pairs, which means less data is required to gain better estimates with lower error bounds.

@NeilSlater interesting ideas, are you working on this idea?


text:
Does this diagram represent several LSTMs, or one through several timesteps?
I'm trying to read this paper describing Google's LSTM architecture for machine translation. It features this diagram on page 4:

I'm interested in the encoder block, on the left. Apparently, the pink and green cells are LSTMs. However, I can't tell if the x-axis is space or time. That is, are the LSTM cells on a given row all the same cell, with time flowing forward from left to right? The diagram on the next page in the paper seems to suggest that.

are the LSTM cells on a given row all the same cell, with time flowing forward from left to right?

Yes this is correct
The x-axis on this figure is basically the time axis. Essentially all pink boxes in the same row are the same LSTM cell, with different inputs from the same sequence. At each timestep, the cell takes an input and produces an output which is fed to the next layer. At the 8-th layer, the outputs over all timesteps are inputted at the same time to the attention layer.


text:
If the reward function of an environment depends on some initial conditions, should I create a separate environment for each condition?
I would like some guidance on how to design an Environment for a Reinforcement Learning agent where the stopping conditions and rewards for the environment change based on an initial set of input parameters.
For example, let's say that a system generated alert triggers the instantiation of the RL environment, whereby the RL agent is launched to make decisions in the environment, based on the alert. The alert has two priorities "HIGH" and "LOW", when the priority is "HIGH" the stopping condition is a reward of "100" and when the priority is "LOW", the stopping condition is a reward of "1000".
In this scenario, is it preferable to create two separate environments based on the priority (input parameter) of the alert? Or is this a common requirement that should be designed into the environment/agent? If so, how? Note that I have simplified the scenario, so there could be multiple conditions (e.g., alert, system type, etc), but I am just trying to find a basic solution for the general case.

In this scenario, is it preferable to create two separate environments based on the priority (input parameter) of the alert?

It is difficult to make a hard rule here.
If the resulting environments can be cleanly sorted into a few different categories, and the ideal behaviour and/or the states visited are radically different in each scenario, then maybe a few different agents optimised for each scenario could work well.
A more general approach however, is to include the episode start data as part of the state that the agent observes on each time step. A single agent can then in theory learn the different behaviours required depending on the initial values, plus still generalise from anything shared between the multiple scenarios.

The alert has two priorities "HIGH" and "LOW", when the priority is "HIGH" the stopping condition is a reward of "100" and when the priority is "LOW", the stopping condition is a reward of "1000".

This may work against you. RL agents do not respond to the absolute values of rewards, other than how they compare to other rewards also available within the same episode (or continuing environment).
If there is only ever one issue to solve at a time, and no conflict between solving either of the "HIGH" or "LOW" priority problems (such as splittig resources or effort between them), the different reward system seems redundant. Solved is solved. You might rate the usefulness of an agent that solves the "LOW" priority issue well higher, but it seems to me that this describes what you should work on first, not the goals of the agent. To influence the goals of the agent, both rewards would need to be available within the same episode or continuing environment, requiring the agent to make a choice between them.

Thanks @neil-slater, I should have clarified the Alert can only be one priority in the example I gave e.g., "HIGH" or "LOW", such that the RL agent can learn what is the best policy (and therefore series of steps to be taken) based on this priority.
I feel myself leaning towards the first example you gave, but of course if one increases the number of parameters  in the inputs e.g., Alert Priority, System Criticality, Alert Triage Time (where there is a maximum time that the episode can run for), then, the separate environments for the different combinations likely wouldn't scale well.

with this approach "A more general approach however, is to include the episode start data as part of the state that the agent observes on each time step. A single agent can then in theory learn the different behaviours required depending on the initial values, plus still generalise from anything shared between the multiple scenarios." <- conceptually how might one go about implementing this? Are there any toy examples you can point me in the direction of?

@RL_NOOB: Add extra features to describe the nature of the goal (perhaps a boolean, or a one-hot-encoded class), and train agents as normal. Make sure to train with all possible variations of the goal. If you want the agent to generalise then you will need to use some kind of approximator - e.g. neural networks are popular in agents like DQN. Using an approximator will generalise behaviour to work in previously unseen states (caveat: as well as e.g. neural networks usually do). I assumed you were using something like DQN in the answer but if your state is simple enough you might not need to

@RL_NOOB: A clasic toy example where goal state is moved around is Taxi = https://gym.openai.com/envs/Taxi-v3/

Thanks @neil-slater your comments and insight have been really helpful :)


text:
What is the meaning of these equations in Noise2Noise paper?
I am trying to understand what is meant by following equations in the Noise2Noise paper by Nvidia.

What is meant by the equation in this image? What is $\mathbb{E}_y\{y\}$? And how should I try to visualize these equations?

Which equations are you referring to? There are at least 3 equations there and other math formulas.

The equation you are referring to is called Mean Squared Error (or $L_2$ loss) and it is used for regression tasks, where the goal is to predict a real value given some input.
In your case, the inputs are measurements of temperature $y$, either at a certain point in time or point in space or both or none, this is not clear from the image. Now, the goal would be to predict the temperature at a new point in space, time, or both, where we don't have access to a measurement. That is we would like to find a function $f$ (e.g. a simple linear function) which we can use for prediction. But how can we measure which function is "best"? We introduce a loss function $L(f,y)$, another function which tells us how good our proposed function is.
Visually it looks like this (image source):

Red crossed are measurements, the black line is our function we use for prediction and the green dotted lines are the errors (the distance from our prediction to the real measurement). In this example salary depends on experience.
Now, the paper introduces the constant mean of all measurements as $y$, $z = \mathbb{E}_y\{y\} = \frac{1}{N}\sum_i^N y_i$, as our function $f$, which is known to be the minimizer for the $L_2$ loss in the case where there is no dependence on other variables (e.g. time or space).

Note that the expectation is not exactly an average, unless you have access to all possible $y_i$ values. Moreover, you should probably comment on the symbol $\mathbb{E}$.

$\mathbb{E}_y{y}$ is for expected value of y?

Yes, correct. $\mathbb{E}_y{y}$ is the expected value of the variable y.


text:
What kind of problems is DQN algorithm good and bad for?
I know this is a general question, but I'm just looking for intuition. What are the characteristics of problems (in terms of state-space, action-space, environment, or anything else you can think of) that are well solvable with the family of DQN algorithms? What kind of problems are not well fit for DQNs?

I don't currently have much practical experience with DQN, but I can partially answer this question also based on my theoretical knowledge and other info that I found.
DQN is typically used for

discrete action spaces (although there have been attempts to apply it to continuous action spaces, such as this one)

discrete and continuous state spaces

problems where the optimal policy is deterministic (an example where the optimal policy is not deterministic is rock-paper-scissors)

off-policy learning (Q-learning is an off-policy algorithm, but the point is that, if you have a problem/application where data can only be or has been gathered by a policy that is unrelated to the policy you want to estimate, then DQN is suitable, though there are other off-policy algorithms, such as DDPG)

This guide also states that DQN is slower to train, but more sample efficient than other approaches, due to the use of the experience replay buffer.
Moreover, if you have a small state and action space, it is probably a good idea to just use tabular Q-learning (i.e. no function approximation), given that it is guaranteed to converge to the optimal value function.
See also this and this questions and this article (which compares DQN with policy gradients).


text:
What is the role of embeddings in a deep recurrent Q network?
When describing the model architecture for a deep recurrent q network, the authors of the paper Learning to Communicate with Deep Multi-Agent Reinforcement Learning

each agent consists of a recurrent neural network (RNN), unrolled for $T$ time-steps, that maintains an internal state $h$, an input network for producing a task embedding $z$, and an output network for the Q-values and the messages $m$. The input for agent $a$ is defined as a tuple of $\left(o_{t}^{a}, m_{t-1}^{a^{\prime}}, u_{t-1}^{a}, a\right)$.

Can someone explain what the purpose of the embedding layer is in this specific context?
Implementation can be found here.

The purpose of the input network is to embed the input tuple into a state/task representation, that can then be fed into the RNN hidden state at each time step.
$(o^a_t,m^a′_{t−1},u^a_{t−1},a)$ (input) $\rightarrow$ input network (embedding) $\rightarrow$ $z_t$ (task representation)

According to to section 6.1 of the paper, the input is a tuple represented as $(o^a_t,m^a′_{t−1},u^a_{t−1},a)$. Each of these  terms is described in sec 3 as:

$o_t$ - The observation. The authors assume a POMDP

Two types of actions:

$u_t$ - An environment action selects by all the agents at each time step in exchange for a team reward
$m_t$ - A communication action, observed by other agent but has no direct impact on the reward or env

$a$ - The agent (This being a multi-agent DQN algorithm)

They form the input to the Deep Recurrent Q-Network architecture.
The purpose of the embedding network is to receive a tuple of these inputs and produce a state
embedding $z$. This state embedding is then fed  into a hidden state $h^a_{t-1}$ of the RNN.
Though the authors refer to it as an input network that produces embedding, in practice, they use different embedding functions for each of these inputs. The final task/state embedding $z_t^a$ is expressed as a sum:
$$
z_t^a = \text{MLP}(o_t^a) + \text{MLP}(m_{t-1}) + \text{LookupTable}(u_{t-1}) + \text{LookupTable}(a)
$$
The summed embeddings are all of the same size.
This answer makes an assumption that by "embedding layer" you meant the input embedding network. Since the paper makes no reference to a single embedding layer in the model architecture.


text:
When does IDA* consider the goal has been found?
I was reading about IDA* and I found this link explaining IDA* and providing an animation for it.
Here is a picture of the solution.

I know what is the cutoff condition (it depends on F), and the search is like DFS if the value of (f) of the node is less or equal to the cutoff, and like IDF it is iterative
My question is:
In the animation, when the threshold is 7 and after expanding the parent of the goal (14), they stated that a solution has been found, so, if we found the goal after expanding a node which is <= the cutoff value, can we consider it the solution without applying any condition-test on it? (it's F <= threshold): for example, if there was another level where there is a goal and it can be found with value 13 (less than 14), like the following pic:

when the threshold is 7, 11 will not be expanded so we will never get (13)
So, what is the correct solution?

According to Artificial Intelligence: A Modern Approach 4th edition in IDA* the cutoff is the $f$-cost($g+h$); at each iteration, the cutoff value is the smallest $f$-cost of any node that exceeded the cutoff on the previous iteration.
In other words, each iteration exhaustively searches an $f$-contour, finds a node just beyond that contour, and uses that node's $f$-cost as the next contour.
And we must test if the node is a goal node when it was selected for expansion, otherwise, the algorithm is not optimal anymore (the proof is similar to that one in A*).
I think the animation that the site provided is misleading because in the code which is written in the last of the same site we have that:
function Search(node, g, threshold)              //recursive function
{

  f = g + heuristic(node);
  if(f > threshold)             //greater f encountered
         return f;
  if(node == Goal)               //Goal node found
         return FOUND;
  integer min = MAX_INT;     //min = Minimum integer
  foreach(tempnode in nextnodes(node))
  {

     //recursive call with next node as current node for depth search
     integer temp=search(tempnode, g + cost(node, tempnode), threshold);
     if(temp == FOUND)            //if goal found
       return FOUND;
     if(temp < min)     //find the minimum of all 'f' greater than threshold encountered
       min = temp;

     }
     return min;  //return the minimum 'f' encountered greater than threshold
}

And in the previous code, we test if the node is the goal node only when it was selected for expansion.

Thank you, I though that the animation was misleading, I needed a confirmation which you gave it to me


text:
Why does Monte Carlo policy evaluation relies on action-value function rather than state-value function?
Here is David Silver's lecture on that. Look at 9:30 to 10:30.
He says that, since it is model-free learning, the environment's dynamics are unknown, so the action-value function $Q$ is used.

But then state-values are already calculated (via first-visit or every-visit). So, why aren't these values used?

Secondly, even if we were to use $Q$, we have $Q^{\pi}(s,a) = R(s) + \gamma \sum_{s'}P(s'|s,a)V^{\pi}(s')$, so we still need to know the transition model, which is unknown.

What am I missing here?

This seems to be a duplicate of this.

In Model Based Reinforcement learning, state and state-action values for all states can be calculated based on the bellman equations. The equations are taken from Andrew Ng's Algorithms for Inverse Reinforcement Learning $$V^{\pi}(s) = R(s) + \gamma \sum_{s'}P(s'|s,a)V^{\pi}(s') \\ Q^{\pi}(s,a) = R(s) + \gamma \sum_{s'}P(s'|s,a)V^{\pi}(s')$$
In this setting, $Q^{\pi}$ can be obtained from $V^{\pi}$ because we have access to the transition model $P(s'|s,a)$. The $Q^{\pi}$ values allow us to carry out a step in $\textbf{policy improvement}$ as in policy iteration.
To answer the first bullet point, the first visit or every state visit policy evaluation in the model free setting for $\textbf{state values}$ is not helpful in determining how to carry out model free control because we cannot compute $Q^{\pi}(s,a)$ from $V^{\pi}$ in the model free case.
The update for SARSA in model free control is $$Q(s,a) \rightarrow Q(s,a) + \alpha (r(s) + \gamma Q(s',a') - Q(s,a))$$
Even though we do not know the transition model, we are essentially $\textbf{sampling}$ from $P(s'|s,a)$ by allowing the environment to provide us the possible next states $s'$ that we may end up in. The following update for SARSA is equivalent to computing $$Q^{\pi}(s,a) = R(s) + \gamma E_{s' \sim P(s'|s,a)}[Q^{\pi}(s',a')]$$
Essentially this should give the same $Q^{\pi}(s,a)$ values when we have the ground truth $P(s'|s,a)$ values for the model free case.

Awesome! Why are the formulas for V and Q the same in your answer? Isn't V = Pi * Q ?

Because SARSA update on the RHS utilises $Q(s',a')$. Also, as $a'$ is selected from the policy $\pi$, this is equivalent to the definition of $V^{\pi}$


text:
Can the (sparse) categorical cross-entropy be greater than one?
I am using AlexNet CNN to classify my dataset which contains 10 classes and 1000 data for each class, with 60-30-10, splits for train, validation, and test. I used different batch sizes, learning rates, activation functions, and initializers. I'm using the sparse categorical cross-entropy loss function.
However, while training, my loss value is greater than one (almost equal to 1.2) in the first epoch, but until epoch 5 it comes near 0.8.
Is it normal? If not, how can I solve this?

Both the sparse categorical cross-entropy (SCE) and the categorical cross-entropy (CCE) can be greater than $1$. By the way, they are the same exact loss function: the only difference is really the implementation, where the SCE assumes that the labels (or classes) are given as integers, while the CCE assumes that the labels are given as one-hot vectors.
Here is the explanation with examples.
Let $(x, y) \in D$ be an input-output pair from the labelled dataset $D$, where $x$ is the input and $y$ is the ground-truth class/label for $x$, which is an integer between $0$ and $C-1$. Let's suppose that your neural network $f$ produces a probability vector $f(x) = \hat{y} \in [0, 1]^C$ (e.g. with a softmax), where $\hat{y}_i \in [0, 1]$ is the $i$th element of $\hat{y}$.
The formula for SCE is (which is consistent with the TensorFlow implementation of this loss function)
$$
\text{SCE}(y, \hat{y}) = - \ln (\hat{y}_{y}) \label{1}\tag{1},
$$
where $\hat{y}_{y}$ is the $y$th element of the output probability vector $\hat{y}$ that corresponds to the probability that $x$ belongs to class $y$, according to $f$.
Actually, the equation \ref{1} is also the definition of the CCE with one-hot vectors as targets (which behave as indicator functions). The only difference between CCE and SSE is really just the representation of the targets, which can slightly change the implementation under the hood. Moreover, note that this is the definition of the CE for only $1$ training pair. If you have multiple pairs, you have to compute the CE for all pairs, then average these CEs (for a reference, see equation 4.108, section 4.3.4 Multiclass logistic regression of Bishop's book PRML).
Let's have a look at a concrete example with concrete numbers. Let $C=5$, $y = 3$, $\hat{y} = [0.2, 0.2, 0.1, 0.4, 0.1]$, then the SCE is
\begin{align}
\text{SCE}(y, \hat{y})
&=
- \ln (0.4) \approx 0.92,
\end{align}
If $\hat{y} = [0.2, 0.2, 0.2, 0.1, 0.3]$, so $\hat{y}_{y} = 0.1$, and we still have $y = 3$, then the CCE is $2.3 > 1$.
You can execute this Python code to check yourself.
import numpy as np
import tensorflow as tf # Install TensorFlow 2.3!

y = 1
y_true = [3] # sparse label (integer)
y_true2 = [0, 0, 0, 1, 0] # one-hot vector

for y_y in [0.4, 0.1]:
    sce_np = -(y * np.log(y_y))
    print("SCE (NumPy) =", sce_np)

y_preds = [[0.2, 0.2, 0.1, 0.4, 0.1],
           [0.2, 0.2, 0.2, 0.1, 0.3]]
for y_pred in y_preds:
    sce_tf = tf.keras.losses.sparse_categorical_crossentropy(y_true, y_pred)
    cce_tf = tf.keras.losses.categorical_crossentropy(y_true2, y_pred)

    print("SCE (TensorFlow) =", sce_tf)
    print("CCE (TensorFlow) =", cce_tf)

To answer the following question more directly.

However, while training, my loss value is greater than one (almost equal to 1.2) in the first epoch, but until epoch 5 it comes near 0.8. Is it normal? If not, how can I solve this?

Yes. It can happen, as explained above. (However, this does not mean that you do not have mistakes in your code.)


text:
Why don't neural networks project the data into higher dimensions first, then reduce the size of each layer thereafter?
Background
From my understanding (and following along with this blog post), (deep) neural networks apply transformations to the data such that the data's representation to the next layer (or classification layer) becomes more separate. As such, we can then apply a simple classifier(s) to the representation to chop up the regions where the different classes exist (as shown by this blog post).
If this is true and say we have some noisy data where the classes are not easily separable, would it make sense to push the input to a higher dimension, so we can more easily separate it later in the network?
For example, I have some tabular data that is a bit noisy, say it has 50 dimensions (input size of 50). To me, it seems logical to project the data to a higher dimension, such that it makes it easier for the classifier to separate. In essence, I would project the data to say 60 dimensions (layer out dim = 60), so the network can represent the data with more dimensions, allowing us to linearly separate it. (I find this similar to how SVMs can classify the data by pushing it to a higher dimension).
Question
Why, if the above is correct, do we not see many neural network architectures projecting the data into higher dimensions first then reducing the size of each layer thereafter?
I learned that if we have more hidden nodes than input nodes, the network will memorize rather than generalize.

To better understand this you should think in terms of capacity. Capacity is a theoretical notion that shows how much information your network can model.
The capacity of a network (given sufficient training) ties in directly with the bias/variance tradeoff:

too little capacity and your network isn't able to learn the complex relationships in the data.
too much capacity and your network has the capability of learning the noise in the dataset, besides the useful relationships.

At some point a network reaches a point where it has a high enough capacity to memorize the whole training set!
Now, by increasing the number of hidden neurons you essentially increase the capacity of your network. If the network already has enough capacity to learn the problem, then by increasing the neurons you are giving the network the capability of overfitting more easily.
Note: all the above assume that the network is trained sufficiently (i.e. no early stopping, etc).

The accepted answer does not answer the question

Why, if the above is correct, do we not see many neural network architectures projecting the data into higher dimensions first then reducing the size of each layer thereafter?

Yes, it's true that if you increase the number of hidden neurons, you generally increase the capacity (in fact, the VC dimension of neural networks is typically expressed as a function of the number of parameters), but you're also suggesting to decrease the size afterwards.
For example, in this tutorial, they use 10 hidden neurons for the first hidden layer of an MLP, while the dataset contains only 4 features, which means that there are $4*10 = 40$ weights (aka parameters). In this other tutorial, there are less than 20 features (and only a few of them are used) and the first hidden layer has 128 neurons, which means that each feature is connected to $128$ hidden neurons, so there should be $4*128 = 512$ weights. So, MLPs can easily have more hidden neurons in the first layer and weights that connect the input(s) to the hidden neurons than the number of features.
In the case of CNNs, you may have fewer scalar parameters because of the properties of CNNs, i.e. parameter sharing. For instance, if you have $64$ filters of shape $3 \times 3$ and you want to process grayscale images of shape $32 \times 32$, then you have $3 * 3 * 64 = 576  < 1024 = 32*32$. Note that the number of parameters of the first layer does not change as a function of the input in the case of CNNs, so if that same CNN processes an image of size $5 \times 5$, then the first layer contains more scalar parameters than pixels.
So, in general, NNs can project the data to higher-dimensional space. The typical NNs that project to a lower-dimensional space are auto-encoders or data compressors, in general, that's why they are called in this way.


text:
What is the difference between the uniform-cost search and Dijkstra's algorithm?
Every computer science student (including myself, when I was doing my bachelor's in CS) probably encountered the famous single-source shortest path Dijkstra's algorithm (DA). If you also took an introductory course on artificial intelligence (as I did a few years ago, during my bachelor's), you should have also encountered some search algorithms, in particular, the uniform-cost search (UCS).
A few articles on the web (such as the Wikipedia article on DA) say that DA (or a variant of it) is equivalent to the UCS. The famous Norvig and Russell's book Artificial Intelligence: A Modern Approach (3rd edition) even states

The two-point shortest-path algorithm of Dijkstra (1959) is the origin of uniform-cost search. These works also introduced the idea of explored and frontier sets (closed and open lists).

How exactly is DA equivalent to UCS?

The answer to my question can be found in the paper Position Paper: Dijkstra's Algorithm versus Uniform Cost Search or a Case Against Dijkstra's Algorithm (2011), in particular section Similarities of DA and UCS, so you should read this paper for all the details.
DA and UCS are logically equivalent (i.e. they process the same vertices in the same order), but they do it differently. In particular, the main practical difference between the single-source DA and UCS is that, in DA, all nodes are initially inserted in a priority queue, while in UCS nodes are inserted lazily.
Here is the pseudocode (taken from the cited paper) of DA

Here is the pseudocode of the best-first search (BFS), of which UCS is just a particular case. Actually, this is the pseudocode of UCS where $g(n)$ is the cost of the path from the source node to $n$ (although the title indicates that this is the pseudocode of BFS).

Dijkstra doesn't need to involve adding all the vertices to the priority queue at the start. See the alternatives at https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm#Using_a_priority_queue which don't involve a "decrease priority" operation. I think the difference is that uniform-cost search does not maintain a map between nodes and their distance from the source, and terminates when you find the target node.

@mic Well, here, I'm comparing the conventional Dijkstra's algorithm with UCS. I will maybe take a look at the other variants later.

@mic Both of you make sense, but Mic's reasoning is more fundamental. Since all other nodes are initially inf in Dijkstra, it actually does not matter if you put them in PQ or not. That is not the real reason.
If you compare AIMA and CLRS textbook pseudocode side by side, you will find that everything is the same except UFS divided the nodes that are unexplored further into two cases during expansion: (1) in frontier unexplored and (2) not in frontier unexplored.
If you don't maintain ALL estimated distances from the source to all other nodes at the beginning, then you have to maintain distances LATER using other methods, and that is exactly how UCS works.
UCS does the following: If not in the frontier (equivalent to inf), then put it into the frontier first, and start tracking its cost from now (equivalent to distance first update, no longer inf). If it is already in the frontier and still unexplored, then update with a shorter value. Since UCS only starts tracking the distance of nodes when they first enter the frontier, they don't need to track ALL node distances with inf at the beginning.
In other words, because Dijkstra chose to track ALL nodes with inf at the beginning, it does not matter whether the unexplored nodes are in the frontier or not anymore, the "inf" just means they are not in the frontier. This also tells us why UCS is always better than Dijkstra: it saves the memory of tracking all nodes, which is particularly useful in the AI when the number of the states are too large


text:
How to deal with Unix timestamps features of sequences, which will be classified with RNNs?
I want to use RNN for classifying whole sequences of events, generated by website visitors. Each event has some categorical properties and a Unix timestamp:
sequence1 = [{'timestamp': 1597501183, 'some_field': 'A'}, {'timestamp': 1597681183, 'some_field': 'B'}]
sequence2 = [{'timestamp': 1596298782, 'some_field': 'B'}]
sequence3 = [{'timestamp': 1596644362, 'some_field': 'A'}, {'timestamp': 1596647951, 'some_field': 'C'}]

Unfortunately, they can't be treated as classic time series, because they're of variable length and irregular, so timestamps contain essential information and cannot be ignored. While categorical features can be one-hot encoded or made into embeddings, I'm not sure what to do with the timestamps. It doesn't look like a good idea to use them raw. I've come up with two options so far:

Subtract the minimum timestamp from every timestamp in the sequence, so that all sequences start at 0. But in this case the numbers can still be high, because the sequences run over a month.
Use offsets from previous event instead of absolute timestamps.

I'm wondering if there are common ways to deal with this? I haven't found much on this subject.

I would say offsets from previous N-event is necessary in this case. You can also encode their max and avg as other features in order to compress the irregular sampling times into a vector.

yes, that's what I ended up doing. Also tried some discretization into 1-day periods.


text:
Is there some known pattern for selecting a batch of candidates for the next generation?
I'm a beginner with a classic "racing car" sandbox and a homemade simple neural network.
My pattern:

Copy the "top car" (without mutation) to the next generation

If there are some cars still running (because simulation reached the 30s win condition), then copy a mutated version of them for the next generation.

Fill the rest of the pool with mutation of the "top car".

But this is just some dumb intuitive pattern I made on the fly while playing with my code. Perhaps I should copy the cars that are still running as-is instead of mutating them. Or, perhaps, some selection method I don't know about.
A new random track is generated at each new generation. a "top car" may be good on a track and crash immediately on the next track. I just feel that basing everything on the top car is wrong because of the track randomness.
Is there some known pattern for selecting a batch of candidates? (paper, google-fu keyword, interesting blog, etc.)
I don't know what to search for. I don't even know the name of my network or any vocabulary related to AI.

What does your neural network represent? It's also not clear to me what you're trying to do. Are you trying to find the best car (that is able to drive in some environment: please, which specify which environment) by having a population of cars that you evolve my mutating? That seems to be just a genetic algorithm.

my post was originall post was bigger and explained what you want but i was told i wasn''t concise enough :D

I only asked you to ask one question, because you had multiple questions. I didn't say you should remove relevant details. Anyway, you can edit your post again.

The most general descriptive frameworks covering what you are trying to do are:

Sequential decision making (article is a stub, but the term a good launching point to discover different wys of modelling and solving these kind of problems)

Optimal control

These put some context around your problem, and might give you some pointers. For instance, reinforcement learning is an alternative approach to the evolutionary system you are trying to build.
The specific AI system you appear to be building is a genetic algorithm, and more specific still you are attempting to find a neural network that is optimal at a task by searching for the best network using a system of population generation, selection and mutation which repeats.
There are lots of ways to set up a system like this, so your approach is not necessarily wrong. However, I think there are two key things that would improve what you have built so far:

Use a fitness function for selection. Score each car, perhaps by how far it got before crashing when the episode ends. To reduce luck factor on random courses, you could make this score the mean result from e.g. 3 different courses (it is not necessary, but may address your concern that selection is too random in your case). Select some fraction of top scoring cars, or look into other selection approaches - e.g. weighted selection based on fitness score or ranking.

Add "sex", more properly known as genome crossover between selected population members. Mutating individuals is limiting because it silos improvements to a single line of ancestry - if there are two good mutations found at random you rely on that single line finding both of them. Whilst crossover allows sharing of good mutations between lines, making it much more likely that two good mutations will end up in the same individual.

There is a framework called NEAT which covers the issues above plus has other features useful for evolving neural networks. It often does well at control scenarios like the one you are considering. You may want to look into it, if your focus is mainly on solving the control problem. However, it is relatively advanced from where you are, so if your current focus to learn by building from scratch you may get more initially from implementing fitness functions and crossover yourself.

thank you very much. I've seen this NEAT in the past but didn't understand it. Now that i played with my simple NN i think i understand it. (and i think that the game called "GridWorld" is doing this). My NN have a fixed topology (defined by me : 7 raycasting input, 1 speed input, 2 hidden layer of 12 and 6 neuron, 2 for speed control and direction) and i'm not encoding phenotype and therefore make crossover more difficult in my code. But i will try this from now on. i could even let the NN try different input sensor by itself (ex : angle of the raycast, tyre friction (drifing in turn), etc)

It's ambitious but worth it i guess. i won't go anywhere if i keep playing with the same primitive NN forever and it's totally in the direction toward my end goal : a mini-game where you watch a NN learning, playing failing, evolving, ... i specifically don't want a sophisticated fitness function or error computation : it's either "win the right to reproduce/mutate" or "die without offspring". And neat seems to fit the need.


text:
In DQN, is it possible to make some actions more likely?
In a general DQN framework, if I have an idea of some actions being better than some other actions, is it possible to make the agent select the better actions more often?

you should construct your reward function so that it will reflect the main goal and the algorithm will learn the best action by itself

take a look at my answers in similar questions: this one, and one more

For single-step Q learning, the behaviour policy can be any stochastic policy without any further adjustment to the update rules.
You don't have to use $\epsilon$-greedy based on current Q function approximation, although that is a common choice because it works well in general cases. However, you should always allow some chance of taking all actions if you want the algorithm to converge - if you fixed things so that bad actions were never taken, the agent would never learn that they had low value.
Probably the simplest way to use your initial idea of best actions is to write a function that returns your assessment of which action to take, and use that with some probability in preference to a completely random choice. At some point you will also want to stop referencing the helper function (unles it is guaranteed perfect) and use some form of standard $\epsilon$-greedy based on current Q values.
I have done similar with a DQN learning to play Connect 4, where the agent would use a look-ahead search function that could see e.g. 7 steps ahead. If that was inconclusive it would use argmax of current Q values. Both these fixed action choices could be replaced, with probability $\epsilon$, with a random action choice to ensure exploration. It worked very well. You could replace the look-ahead search in my example with any function that returned "best" actions for any reason.
There are some other ways you can skew action selection towards better looking action choices. You could look into Boltzmann exploration or upper confidence bounds (UCB) as other ways to create behaviour policies for DQN.

The connect 4 example looks to be a very nice approach to implement what I need. When you implement the look ahead search, do you mean look ahead in time on what might be the consequence of the actions ? Doesn't that mean you're still somewhat doing an argmax of the actions ?

@user3656142: My search chose by win/loss only, ignoring Q values. So it was an independent function. Yes it was an argmax over that independent function. The function was technically a negamax ( https://en.wikipedia.org/wiki/Negamax ) based on the game rules.

@NeilSlater: So your suggestion is that for each step predefined actions are choosen with a certain probability and with (1- probability) a Deep-Q-learning action should be choosen?

@PeterBe: My suggestion for OP here is to use a modified $\epsilon$-greedy, where they could use their initial guesses as best action in place of the greedy action. In practice, they will also want to retire the best guess component at some stage  - whilst I didn't need to for Connect 4, because a negamax search that resolves to the end of the game is always perfect.

@NeilSlater: Thanks for your comment. But did the OP not ask whether you can make some actions more likely in Deep-Q-Learning? Is your suggestion not to use Deep-Q-learning but instead use e-greedy? Or is your suggestion actually trying to combine e-greey with Deep-Q-Learning? Further, I don't understand at all the second part of your comment "whilst I didn't need to for Connect 4, because a negamax search that resolves to the end of the game is always perfect." --> What do you mean by negamax search and why is it perfect at the end of the game?

@PeterBe: As per the answer Q-Learning action choice is flexible, so the OP is still "using" Deep-Q-Learning, but without the most commonly chosen behaviour policy. Negamax search: https://en.wikipedia.org/wiki/Negamax - it is generally only used in 2-player games, but within those is a well-known AI technique. If you have further questions about that, they would definitely be on topic for this site.


text:
Can we use Q-learning update for policy evaluation (not control)?
For policy evaluation purposes, can we use the Q-learning algorithm even though, technically, it is meant for control?
Maybe like this:

Have the policy to be evaluated as the behaviour policy.
Update the Q value conventionally (i.e. updating $Q(s,a)$ using the action $a'$ giving highest $Q(s',a')$ value)
The final $Q(s,a)$ values will reflect the values for the policy being evaluated.

Am I missing something here, given that I have not seen Q-learning being used anywhere for evaluation purposes?

For off-policy learning you must have two policies - a behaviour policy and a target policy. If the two policies are the same, then you end up with SARSA, not Q learning.
You cannot use Q learning directly for evaluating a fixed target policy, because it directly learns optimal value function as the target policy, regardless of the behaviour policy. Instead you must use another variant of off-policy learning that can evaluate an arbitrary target policy.
Your suggested algorithm is:

Have the policy to be evaluated as the behaviour policy.
Update the Q value conventionally (i.e. updating $Q(s,a)$ using the action $a'$ giving highest $Q(s',a')$ value)
The final $Q(s,a)$ values will reflect the values for the policy being evaluated.

This will not work for evaluating the behaviour policy. If the behaviour policy was stochastic and covered all possible state/action choices, then it will still be Q learning and converge on the optimal value function - maybe very slowly if the behaviour policy did not get to important states very often.
The "trick" to off-policy is that the environment interaction part uses the behaviour policy to collect data, and the update step uses the target policy to calculate estimated returns. In general for off-policy updates, there can be corrections required to re-weight the estimated returns. However, one nice thing about single-step TD methods is that there are no such additional corrections needed.
So this gives a way to do off-policy TD learning, using an approach called Expected SARSA. To use Expected SARSA, you will need to know the distribution of action choices i.e. know $\pi(a|s)$ for the target policy.
This is the variant of your description that will work to evaluate your target policy $\pi(a|s)$:

Have any stochastic policy that "covers" the target policy as the behaviour policy.
Update the Q value using Expected SARSA $Q(s,a) = Q(s,a) + \alpha(r + \gamma [\sum_{a'} \pi(a'|s')Q(s',a')]  - Q(s,a))$
The final $Q(s,a)$ values will reflect the values for the policy being evaluated.

Worth noting that Expected SARSA with a target policy of $\pi(s) = \text{argmax}_a Q(s,a)$ is exactly Q learning. Expected SARSA is a strict generalisation of Q learning that allows for learning the value function of any target policy. You may not see it used as much as Q learning, because the goal of learning an optimal value function is more common in practice.

Although I don't know the details yet, I think you may also want to take a look at off-policy (policy) evaluation (if you are not already aware of these concepts). Can you explain a little why expected SARSA would make this an off-policy evaluation method?

@Neil, Thanks for the detailed answer. I'm unclear why ESARSA would work though. I feel that it would only work if the target policy being learnt is the same as the behaviour policy. i.e. we have an on-policy setting.

@DhruvMullick: On-policy vs off-policy is a separate issue from evaluation vs control. The key for off-policy evaluation is that you set the target policy to be the policy that you want to evaluate. Nothing more is required. Can you explain more why you feel evaluation needs to be on-policy? Then I may be able to address that.

@NeilSlater, thank you, I understand now. I was earlier under the wrong impression that for Policy evaluation, I would have to set the behaviour policy as the policy to be evaluated.

@NeilSlater Thanks for the answer, this and many of your answers have been very helpful. Could you please help with a follow up question here? I am wondering, since we are evaluating value of the fixed given policy here, is it best to use a fully random behavior policy so that value is trained over more diverse states than we would see with the more commonly used eps-greedy behavior policy?

@ModCon Generally no, for evaluating a fixed policy where you are in control of the behaviour policy, then you should just use an on-policy method. That's because off-policy methods add variance to measurement. However you are not always in control of behaviour policy - e.g. you might have historical observations where it isn't even clear what the behaviour policy was.

@NeilSlater Thanks so much for replying! If I understand correctly, even if I follow fixed policy to choose every behaviour action, given that state is sampled randomly at t=0, we should get experiences for different initial states, proving enough for learning state value function. In my case, I am learning a state action value function, can I keep the action sampled t=0 randomly chosen and only the next actions as per fixed policy (instead of choosing even t=0 action as per fixed policy) so that there’s experiences starting from all possible actions?

@ModCon I'm not clear why you would want to do that. I don't think the comments section here will be enough to cover your question. Please consider asking a new question on the site


text:
Is average pooling equivalent to a strided convolution with a specific constant kernel?
It seems to me that average pooling can be replaced by a strided convolution with a constant kernel. For instance, a 3x3 pooling would be equivalent to a strided convolution (of stride $3$) with a $3 \times 3$ matrix of constants, with each entry being $\frac{1}{9}$.
However, I haven't found any mention of this fact online (perhaps it's too trivial of an observation)? Why then are explicit pooling layers needed if they can be realized by convolutions?

Is average pooling equivalent to a strided convolution with a specific constant kernel?

Yes.

Why then are explicit pooling layers needed if they can be realized by convolutions?

It is probably because the convolution is more expensive than the usual/natural implementation (i.e. just summing and then dividing).
To see why, let's consider your example. If you implement pooling with a convolution (or cross-correlation), we would need to perform $9$ multiplications, then $8$ summations, for a total of $17$ operations. If we implement pooling as usual, we would need to perform $8$ summations and $1$ division (or multiplication), for a total of $9$ operations.
Moreover, convolution may also be more prone to numerical instability (multiplications of numbers in the range $[0, 1]$ are not nice), but I am not completely sure about this, given that we multiply always by the same numbers.


text:
Why aren't exploration techniques, such as UCB or Thompson sampling, used in full RL problems?
Why aren't exploration techniques, such as UCB or Thompson sampling, typically used in bandit problems, used in full RL problems?
Monte Carlo Tree Search may use the above-mentioned methods in its selection step, but why do value-based and policy gradient methods not use these techniques?

You can indeed use UCB in the RL setting. See e.g. section 38.5 Upper Confidence Bounds for Reinforcement Learning (page 521) of the book Bandit Algorithms by Csaba Szepesvari and Tor Lattimore for the details.
However, compared to $\epsilon$-greedy (widely used in RL), UCB1 is more computationally expensive, given that, for each action, you need to recompute this upper confidence bound for every time step (or, equivalently, action taken during learning).
To see why, let's take a look at the UCB1 formula
$$
\underbrace{\bar{x}_{j}}_{\text{value estimate}}+\underbrace{\sqrt{\frac{2 \ln n}{n_{j}}}}_{\text{UCB}},
$$
where

$\bar{x}_{j}$ is the value estimate for action $j$
$n_{j}$ is the number of times action $j$ has been taken
$n$ is the total number of actions taken so far

So, at each time step (or new action taken), we need to recompute that square root for each action, which depends on other factors that evolve during learning.
So, the higher time complexity than $\epsilon$-greedy is probably the first reason why UCB1 is not so much used in RL, where interaction with the environment can be the bottleneck. You could argue that this recomputation (for each action) also needs to be done in bandits. Yes, it's true, but, in the RL problem, you have multiple states, so you need to compute value estimates for each action in all states (i.e. the full RL problem is more complex than bandits or contextual bandits).
Moreover, $\epsilon$-greedy is so conceptually simple that everyone can easily implement it in less than $5$ minutes (though this is not really a problem, given that both are simple to implement).
I am currently not familiar with Thompson sampling, but I guess (from some implementations I have seen) it's also not as cheap as $\epsilon$-greedy, where you just need to perform an argmax (can be done in constant time if you keep track of the highest value) or sample a random integer (it's also relatively cheap). There's a tutorial on Thompson sampling here, which also includes a section dedicated to RL, so you may want to read it.

Many techniques for the exploration/exploitation dilemma that are inspired by multi-armed bandit problems, such as UCB1, assume that you can explicitly enumerate all state-action pairs; in fact, multi-armed bandit problems usually only have just one "state", and then this requirement turns into only requiring the ability to enumerate actions.
In RL problems that are small enough to be handled with tabular approaches (without any function approximation), this may still be feasible. But for many interesting RL problems, the state and/or action spaces grow so large that you have to use function approximators (Deep Neural Networks are a popular choice, but others exist too). When you are unable to enumerate your state-action space, you can no longer keep track of things like the visit counts that are normally used in UCB1 and related approaches.
There certainly are more advanced exploration techniques for RL than just $\epsilon$-greedy though, and some may even resemble / take inspiration from bandit-based approaches. There's an excellent blog post on Exploration Strategies in Deep Reinforcement Learning here. For example, you may think of some of the approaches described under "Count-based Exploration" as trying to solve the issue of tracking visit counts as I described above in settings with function approximation.

In fact, I think that the formula can be used as it is for multi-state problems.
However, the formula probably overlaps with adjusting the reward bias because it considers the bias of the true expected value for a particular situation.
Rather, this makes learning unstable, so I think it is not used.


text:
Why are neural networks preferred to other classification functions optimized by gradient decent
Consider a neural network, e.g. as presented by Nielsen here. Abstractly, we just construct some function $f: \mathbb{R}^n \to [0,1]^m$ for some $n,m \in \mathbb{N}$ (i.e. the dimensions of the input and output space) that depends on a large set of parameters, $p_j$. We then just define the cost function $C$ and calculate $\nabla_p C$ and just map $p \to p - \epsilon \nabla_p C$ repeatedly.
The question is why do we choose $f$ to be what it is in standard neural networks, e.g. a bunch of linear combinations and sigmoids? One answer is that there a theorem saying any suitably nice function can be approximated using neural networks. But the same is true of other types of functions $f$. The Stone-Weierstrass theorem gives that we could use polynomials in $n$ variables: $$f(x) =  c^0_0 + (c^1_1 x_1 + c^1_2 x_2 + \cdots + c^1_n x_n) + (c^2_{11}x_1 x_1 + c^2_{12} x_1x_2 + \cdots + c^2_{1n} x_1 x_2 + c^2_{21} x_2x_1 + c^2_{22} x_2x_2 + \cdots) + \cdots,$$
and still have a nice approximation theorem. Here the gradient would be even easier to calculate. Why not use polynomials?

Here is a related question What are the differences between artificial neural networks and other function approximators?.

You can indeed fit a polynomial to your labelled data, which is known as polynomial regression (which can e.g. be done with the function numpy.polyfit). One apparent limitation of polynomial regression is that, in practice, you need to assume that your data follows some specific polynomial of some degree $n$, i.e. you assume that your data has the form of the polynomial that you choose, which may not be true.
When you use a neural network to solve a classification or regression problem, you also need to choose the activation functions, the number of neurons, how they are connected, etc., so you also need to limit the number and type of functions that you can learn with neural networks, i.e. the hypothesis space.
Now, it is not necessarily a bad thing to limit the hypothesis space. In fact, learning is generally an ill-posed problem, i.e. in simple terms, there could be multiple solutions or no solutions at all (and other problems), so, actually, you often need to limit the hypothesis space to find some useful solutions (e.g. solutions that generalise better to unseen data). Regularisations techniques are ways of constraining the learning problem, and the hypothesis space (i.e. the set of functions that your learning algorithm can choose from), and thus making the learning problem well-posed.
Neural networks are not preferred over polynomial regression because they are theoretically more powerful. In fact, both can approximate any continuous function [1], but these are just theoretical results, i.e. these results do not give you the magical formula to choose the most appropriate neural network or polynomial that best approximates the desired unknown function.
In practice, neural networks have been proven to effectively solve many tasks (e.g. translation of natural language, playing go or atari games, image classification, etc.), so I would say that this is the main reason they are widely studied and there is a lot of interest in them. However, neural networks typically require large datasets to approximate well the desired but unknown function, it can be computationally expensive to train or perform inference with them, and there are other limitations (see this), so neural networks are definitely not perfect tools, and there is the need to improve them to make them more efficient and useful in certain scenarios (e.g. scenarios where uncertainty estimation is required).
I am not really familiar with research on polynomial regression, but it is possible that this and other tools have been overlooked by the ML community. You may want to have a look at this paper, which states that NNs are essentially doing polynomial regression, though I have not read it, so I don't know the details about the main ideas and results in this paper.


text:
How can I classify houses given a dataset of houses with descriptions?
I have a dataset with a number of houses, for each house, I have a description. For example "The house is luxuriously renovated" or "The house is nicely renovated". My aim is to identify for each house whether it is luxuriously, well or poorly renovated. I am new to NLP so any tips on how to approach this problem would be much appreciated.

It all depends on what kind of annotations or other variables are present in your dataset. I see 2 possible scenarios here:

your dataset is made only of houses descriptions, without any indication of their luxury level.

you have annotations regarding the luxury level or another similar variables from which you can infer the luxury level (like the house price for example).

In the first case there's not much you can do except for trying to apply some unsupervised algorithms or transfer learning. Usually in NLP unsupervised techniques are used for tasks like Topic or language modeling, both of which are not really helpful for your specific application since they work at a really abstract level trying to learn relationships between words or documents in corpora containing huge variety of texts. The best you could try could be preprocessing the data to extract specific terms like entities (cities names, furnitures names, etc.) and adjectives from each description, and then try cluster them into n clusters were n is the number of classes you're interest in by applying for example Latent Dirichlet Allocation. Even though everything is possible with the right time and patience, I would never follow this road, especially because it relies on a perfect preprocessing, that involves already transfer learning, for the name entity recognition part for example. And even tough libraries like SpaCy offer really good models to perform these tasks, once you have these kind of annotations a rule based approach would probably be faster and easier to build than another unsupervised model, e.g. creating a simple dictionary contacting names of luxurious furnitures name and adjectives that indicate if the house is expensive would probably be sufficiently good.
In the second case, the story change completely because if you have annotations you could rely on supervised learning. If you already have explicit annotations like "luxuriously renovated" "nicely renovated" nothing stops you from trying to train whatever architecture you feel more comfortable with on this classification task. Even simple architecture like CNN that are easy and fast to train usually achieve good results in classification, and you definitely want to leverage some pre-trained embedding vectors like GloVe as an input feature (every deep learning framework like tensorflow or pytorch already implement the possibility to use them).
To conclude, if you don't have annotations you might try LDA just to check if you're lucky but if I were you I would start annotating data as quick as I can. A good practice in this case is to also ask someone else to perform the annotations, not only to be faster in the creation of the dataset but also to then calculate the Inter Annotator Agreement score, that gives an indication about the quality of the annotations (if the score is low, the dataset quality is poor and no model will be able to learn something from it).


text:
What makes Google Translate fail on the Latin language?
As it is discussed here, and I saw it on other Latin language forums too, everybody complains about how Google Translate fails to translate the Latin language. From my personal experience, it is not that much bad on other languages, including romance languages.
So, what makes Google Translate fail so much to translate the Latin language? Is it about its syntax and grammar or lack of data?

I don't know what model Google is using for their translations, but it's highly likely that they're using one of today's SOTA deep learning models.
The latest NLP models are trained on data scraped from the web, e.g. OpenAI's GPT-2 was trained on a dataset of 8 million web pages, Google's BERT was trained on the BookCorpus (800M words) and English Wikipedia (2.500M words) pages.
Now think about the amount of latin web pages and notice that there are over 6 million english wikipedia articles but less than 135.000 in latin (see here).
As you can see, massive amounts of data are crucial for neural machine translation and I assume there is simply not enough out there for latin. Plus latin is one of the most complex and complicated languages, this makes the task not easier. Maybe Google and Co also focus less on a 'dead' language which is not spoken anymore and has it's right to exist more for educational purposes.

Is Latin actually that complex and complicated compared to other languages? In terms of grammatical complexity Latin doesn't appear high in the ranks.

@MightestDuck, one type of complexity that Latin has is that it's more morphologically rich than English– you can produce a lot of distinct word forms by changing the word endings. Effectively it has a larger vocabulary than English, and this makes it harder to learn the patterns. Some word forms might be very rare in your training data, like imperative verbs in Wikipedia. Many researchers have thought about workarounds, but I think the most common one is to throw even more data at it.

Here I briefly describe what Google is apparently using for Translate now.

Simple old Latin is different from Latin and in the language words are added to written language that are not spoken as well as reverse order of words to have forward meaning.


text:
How do I design the rewards and penalties for an agent whose goal it is to explore a map
I am trying to train an agent to explore an unknown two-dimensional map while avoiding circular obstacles (with varying radii). The agent has control over its steering angle and its speed. The steering angle and speed are normalized in a $[-1, 1]$ range, where the sign encodes direction (i.e. a speed of $-1$ means that it is going backwards at the maximum units/second).
I am familiar with similar problems where the agent must navigate to a waypoint, and in which case the reward is the successful arrival to the target position. But, in my case, I can't really reward the agent for that, since there is no direct 'goal'.
What I have tried
The agent is penalised when it hits an obstacle; however, I am not sure how to motivate the agent to move. Initially, I was thinking of having the agent always move forward, meaning that it only has control over the steering angle. But, I want the ability for the agent to control its speed and be able to reverse (since I'm trying to model a car).
What I have tried is to reward the agent for moving and to penalise it for remaining stationary. At every timestep, the agent is rewarded ${1}/{t_\text{max}}$ if the absolute value of the speed is above some epsilon, or penalised that same amount if otherwise. But, as expected, this doesn't work. Rather than motivating the agent to move, it simply causes it to jitter back and forth. This makes sense since 'technically' the most optimal strategy if you want to avoid obstacles is to remain stationary. If the agent can't do that then the next best thing is to make small adjustements in the position.
So my question: how can I add in an exploration incentive to my agent? I am using proximal policy optimization (PPO).

Measure what you want to achieve as directly as possible, and reward that. Later you can add more sophisticated incentives for the type of motion etc, but the key to a good reward signal is that it measures the quality of a solution at a high level, without specifying how to achieve that solution.
If you want your simulated car to explore, you will want to give it a reward signal based on it encountering new unexplored areas. There are lots of reasonable choices here. I suspect a good one will depend on what sensors you can reasonably code for the car, and what you consider to count as exploration - e.g. is it a thorough search of an area, moving far from the original position, experiencing different "views"?
One likely component you will need to give your agent and incorporate into the state representation is a memory. In order to understand whether the agent is exploring, something will need to know whether the agent has experienced something before and how much. A very simple kind of memory would be to add counters to a grid map and allow the agent to know how many time steps it has spent in each position on the map. The reward signal can then be higher when the agent enters a point on the map that it has not been in recently. If you want a non-episodic or repeating tour of exploration you might decay the values over time, so that an area that has not been visited for a long time counts the same as a non-visited one.
A related concept that you might be able to borrow ideas from is curiousity. There have been some interesting attempts to encourage an agent to seek new/interesting states by modifying action selection. Curiosity-driven Exploration by
Self-supervised Prediction is one such attempt, and might be of interest to you. In that case, the authors use an intrinsic model of curiousity that can solve some environments even when there is no external reward signal at all!
Alternatively, if you don't care to get involved in technical solution, you could create a maybe acceptable behaviour for your vehicle by setting a random goal position, then granting a reward and moving it to a new random location each time the car reaches it.

Okay, thank you. What I am trying right now (as in running the experiment) is a distance-based reward. So the reward at a time $t$ is $k(d_t-d_{t-1})$ where $k$ is some multiplier. I've noticed that the cumulative rewards decreases after a bit of training; the agent just starts moving quick and colliding into obstacles. Why do you think this may be occurring? Is it because the agent is prioritizing moving away from the position, and the obstacle penalty is too low?

@ShonVerch: It could be that, I don't really know enough about the environment and what you are doingto say for sure. You will need to look at the behaviours and the total rewards that they generate. Also check your state values - does the agent have any way to predict the location of an obstacle in advance of moving?

Right! The observation consists of distance sensors, which is how the car knows if there are obstacles near it. It's interesting because after the agent has learned to go away from the initial position, even despite the fact that almost every episode ends in a collision, the reward is still going up. This is what I'm talking about. Though, this is also without memory, and I'm not randomizing the obstacles every episode (I read somewhere that PPO is not great in random environments?).

Looks like a fun project. Unless those animations are playing backwards, or you are deliberately not showing some of the sensors, it looks like the car is reversing away from obstacles it can see, but cannot see the ones it eventually hits?

Yea, that's exactly what's going on. I had hoped that the agent could learn to look around to see obstacles behind it. Not sure why it's always reversing though. I think it might be overfitting reversing behaviour because the environment is never changing.


text:
What is the difference between reinforcement learning and optimal control?
Coming from a process (optimal) control background, I have begun studying the field of deep reinforcement learning.
Sutton & Barto (2015) state that

particularly important (to the writing of the text) have been the contributions establishing and developing the relationships to the theory of optimal control and dynamic programming

With an emphasis on the elements of reinforcement learning - that is, policy, agent, environment, etc., what are the key differences between (deep) RL and optimal control theory?
In optimal control we have, controllers, sensors, actuators, plants, etc, as elements. Are these different names for similar elements in deep RL? For example, would an optimal control plant be called an environment in deep RL?

Most optimal control books focus on deterministic systems. RL is generally applied to systems which are probabilistic.

The same book Reinforcement learning: an introduction (2nd edition, 2018) by Sutton and Barto has a section, 1.7 Early History of Reinforcement Learning, that describes what optimal control is and how it is related to reinforcement learning. I will quote the most relevant part to answer your question, but you should read all that section to have a full understanding of the relationship between optimal control and reinforcement learning.

The term "optimal control" came into use in the late 1950s to describe the problem of designing a controller to minimize or maximize a measure of a dynamical system's behavior over time. One of the approaches to this problem was developed in the mid-1950s by Richard Bellman and others through extending a nineteenth-century theory of Hamilton and Jacobi. This approach uses the concepts of a dynamical system's state and of a value function, or "optimal return function", to define a functional equation, now often called the Bellman equation. The class of methods for solving optimal control problems by solving this equation came to be known as dynamic programming (Bellman, 1957a). Bellman (1957b) also introduced the discrete stochastic version of the optimal control problem known as Markov decision processes (MDPs). Ronald Howard (1960) devised the policy iteration method for MDPs. All of these are essential elements underlying the theory and algorithms of modern reinforcement learning.

To answer your specific questions.

In optimal control we have, controllers, sensors, actuators, plants, etc, as elements. Are these different names for similar elements in deep RL? For example, would an optimal control plant be called an environment in deep RL?

Yes. In reinforcement learning (see the first footnote of the cited book on page 48), the term control is often used as a synonym for action. Similarly, the term controller (or decision maker) is used as a synonym for agent (and sometimes also a synonym for policy, given that the policy usually defines and controls the agent, although the concept of the agent is more abstract and we could associate more than one policy with the same agent). The term environment is also used as a synonym for controlled system (or plant).
See also section 38.8 Notes (page 530) of the book Bandit Algorithms by Csaba Szepesvari and Tor Lattimore.

I think the controller is synonym for agent, at least Sutton & Barto agrees with this "We use the terms agent, environment, and action instead of the engineers’ terms controller, controlled system (or plant), and control signal because they are meaningful to a wider audience." (from http://incompleteideas.net/book/RLbook2020.pdf footnote p48)

@NeilSlater Thanks for noticing this. I was actually looking for that footnote (that I knew existed because I had answered another question based on it), but, for some reason, this time I didn't find it. Anyway, many times, a policy defines and controls the agent, so I would say that a policy is a controller, although an agent is a more abstract concept and we could indeed associate more than one policy with the same agent.

For posterity, the relevant part is point 6 in Section 38.8. Thanks for the link!

As a supplement to nbro's nice answer, I think a major difference between RL and optimal control lies in the motivation behind the problem you're solving. As has been pointed out by comments and answers here (as well as the OP), the line between RL and optimal control can be quite blurry.
Consider the Linear-Quadratic-Gaussian (LQG) algorithm, which is generally considered to be an optimal control method. Here a controller is computed given a stochastic model of the environment and a cost function.
Now, consider AlphaZero, which is obviously thought of as an RL algorithm. AlphaZero learns a value function (and thus a policy/controller) in a perfect information setting with a known deterministic model.
So, it's not the stochasticity that separates RL from optimal control, as some people believe. It's also not the presence of a known model. I argue that the difference between RL and optimal control comes from the generality of the algorithms.
For instance, generally, when applying LQG and other optimal control algorithms, you have a specific environment in mind and the big challenge is modeling the environment and the reward function to achieve the desired behavior. In RL, on the other hand, the environment is generally thought of as a sort of black box. While in the case of AlphaZero the model of the environment is known, the reward function itself was not designed specifically for the game of chess (for instance, it's +1 for a win and -1 for a loss, regardless of chess, go, etc.). Furthermore, the neat thing with AlphaZero is that we can use it to train agents in virtually any perfect information game without changing the algorithm at all. Another difference with RL here is that the agent iteratively improves itself, while optimal control algorithms learn controllers offline and then stay fixed.

Rather than saying "the environment is generally thought of as a sort of black box", I think you want to say that you don't have the model of environment's dynamics (i.e. the transition function/probability distribution). So, it may be better to be more specific. You may also want to mention "planning" and "dynamic programming" algorithms and how they relate to your description of "optimal control".

That's actually not what I'm saying though -- in AlphaZero you do have a dynamics model. My point was that in optimal control your task depends on how you model things, while in RL you have no control over it.

I am not sure if this is what you also mean, but in RL you typically have control over the reward function, so, in this sense, you can control the task.

Great answer, thank you. I would like to point out something about your last sentence: even in optimal control there are some kinds of models where the controllers can change and adapt in time, i.e. adaptive control and dual control.

I disagree that you have a complete dynamics model in the case of Alpha Go. You have the rules of the game, but you have no model of the opponent a priori. Treating the game as an MDP, the transition is the composition of the board rules and the opponent's policy, and that needs to be discovered throughout the learning process.


text:
Why don't we use auto-encoders instead of GANs?
I have watched Stanford's lectures about artificial intelligence, I currently have one question: why don't we use autoencoders instead of GANs?
Basically, what GAN does is it receives a random vector and generates a new sample from it. So, if we train autoencoders, for example, on cats vs dogs dataset, and then cut off the decoder part and then input random noise vector, wouldn't it do the same job?

Auto-encoders are widely used and maybe even more used than GANs (in fact, auto-encoders are older than GANs, although the main general idea behind GANs is quite old). For example, auto-encoders are used in World Models, for drug design (e.g. see this paper) and many other tasks that involve data compression or generation.

So, if we train autoencoders, for example, on cats vs dogs dataset, and then cut off the decoder part and then input random noise vector, wouldn't it do the same job?

Yes, the encoder part of the auto-encoder produces a vector that represents the input in a compressed form. You may also be interested in denoising auto-encoders, but there are other variations, such as convolutional auto-encoders or variational auto-encoders.

The work done in World Models blew my mind. Do you know about any application of generative modeling for robotics?

@MightestDuck Off the top of my head, no, but I am sure they have been used in robotics too.

In fact, autoencoders are used for generative tasks. Have a look at Tutorial on Variational Autoencoders (VAEs).
The coolest thing about VAE is that abstract features can be easily amplified or suppressed based on extracted vectors from the latent space. Let's imagine a model trained on MNIST to generate digits. If you take two images of the same digit which only vary in thickness, encode both of them and subtract the two vectors, the resulting vector will be a description of thickness in the latent space. Now you can generate an arbitrary digit and incrementally adjust its thickness based on that vector.