text:
How to deal with changing environment in reinforcement learning
I am new to RL and I'm currently working on implementing a DQN and DDPG agent for a 2D car parking environment. I want to train my agent so that it can successfully traverse the env and park in the designated goal in the middle.
So, my question is: what are the best practices when training an agent for a changing environment?
In my case, my goal is that a car can randomly spawn every episode anywhere in the dark grey-ish area and always successfully parks in the middle. My problem, in this case, is that if I for example train the agent from only one specified location, it usually won't know how to perform if it's spawned somewhere else.
I also tried making it so that the car starting location gets randomly updated every N step, but unfortunately came to no success.
It may be possible that I've not trained for long enough and with a sufficient number of steps in between the "position resets", but I still want to ask if there are any general practices in the cases like this?

I am correct in my understanding that you only provide the agent with the state of the car, i.e. a global x and y position, its angle, velocity, and steering angle?
How does the agent know that it is coming closer to the goal if it is not provided with information about where the goal is? Without this observation of the goal, the agent is operating blindly. That explains why it is so difficult for the agent to reach the goal and impossible when you randomize the starting position.
If my assumptions are correct, the agent takes random actions which are unlikely to reach the goal, but due to the law of large numbers after enough episodes, the agent will reach the goal at random and it can learn to remember this path if given enough reward. But if you then randomize the starting position the agent cannot apply the knowledge it has learned previously because the sequence of actions to reach the goal would now be different. Essentially, there is no correlation between what goal you want the agent to achieve and your state and action space.
To circumvent this problem, I suggest you add additional state information, here are a few suggestions:

The global x and y position of the goal
A distance measure measuring the distance from the agent and to the goal. Either the Euclidean distance or Manhattan distance.
Both of the above

I also support the suggestion of Elfurd: "Training in steps can be useful". This is called curriculum learning and the idea is to present easier training examples to the agent at the beginning of training and steadily increase the difficulty of the environment. In turn, the agent will reach the goal in the easier environments, obtain some reward, and learn. It can then apply what it has learned in the more advanced environments once it progresses through the curriculum.
In your environment, this could be as simple as decreasing the size of the gird world in early training. Or you could spawn the agent close to the goal so that the agent is more likely to reach the goal with just a few random actions, alternatively, you can also randomize the goal close to the starting position of the agent if it has to start from a specified position and then increase the distance to where the goal is sampled.

From the description it looks like the parking space is always at 0,0

Yeah, it seems so. But I imagine they want to be able to start from any arbitrary position and end at any arbitrary position in the environment.

Thank you. As you mentioned, I was missing additional state information, namely the distance from the agent to the goal.  With this agent is able to learn a good policy faster. I will also try experimenting with curriculum learning to see if the agent will have an easier and faster time learning a good policy.

My guess is that you haven't trained long enough, but there are things that can be done to possibly accelerate learning.
It depends on what you want the policy to do in the final version. If you want it to be able to be spawned at a random position on the map and park in some other (random) position on the map, then that is how you should train it.
Training in steps can be useful, for example training with a fixed start and terminal point, then randomize the parking spot, then randomize the starting position. In general, giving the agent fully randomization will take longer than setting multiple, sequential goals.

Tnx for the tip. I will try training the model for longer. The reason I wasn't sure before was that when I tried it (randomizing spawn location every N step), whenever the agent changed position, the loss exploded to an absurd number like 4mil+, it did go down eventually but didn't learn anything. I will try increasing the number of total steps and a reasonable amount of steps before randomizing the spawn location.

It could be a combination of more training and the right parameters. When you expand the observation space, the problem becomes more difficult and the algorithms needs to try harder to learn and explore. The main thing I have learned in ML is it is more like an experimental science, rather than a logical math-based problem. Even though the learning is built on some basic math results.


text:
What is the difference between a greedy policy and an optimal policy?
I am struggling to understand what is the difference between an optimal policy and a greedy policy.
Let $F(r_{t+1},s_{t+1}| s_t,a_t)$ be the probability distribution accorting to which, given action $a_t$ in state $s_t$, reward $r_{t+1}$ realizes and the process transitions to a new state $s_{t+1}$. The value function for a generic policy $\pi$ then is
$$v_\pi(s_t) = E_\pi \left[ E_F \left[ r_{t+1} |  s_t,a_t \right]+ \delta E_F \left[v_\pi \left(s_{t+1}\right)| s_t,a_t \right] \right],$$
and the optimal value function is
$$ v_*(s_t) = \max_\pi \, v_\pi(s_t).$$
I would like to know if the optimal value function can also be defined as
$$v_*(s_t) = \max_{a \in A(s_t)} \big\{ E_F \left[ r_{t+1} |  s_t,a \right]+ \delta E_F \left[v_* \left(s_{t+1}\right)| s_t,a \right] \big\},$$
and if not, why. Here, the bellman equation prescribes to behave greedily by always choosing the best action $a \in A(s)$.
To me, behaving greedily and choosing the optimal policy seem equivalent, which confuses me a bit.

I would like to know if the optimal value function can also be defined as
$$v_*(s_t) = \max_{a \in A(s_t)} \big\{ E_F \left[ r_{t+1} |  s_t,a \right]+ \delta E_F \left[v_* \left(s_{t+1}\right)| s_t,a \right] \big\},$$

This looks correct to me, although I am used to different notation, and viewing this after resolving the expectations. From Sutton & Barto, I would write the following:
$$v^*(s) = \text{max}_a \sum_{r,s'}p(r,s'|s,a)(r + \gamma v^*(s'))$$
which I think matches your equation term-for-term.

To me, behaving greedily and chosing the optimal policy seem equivalent, which confuses me a bit.

You have to take care with the self-reference to the optimal value function - it occurs on both sides of the Bellman equation.

Behaving greedily with respect to an optimal value function is an optimal policy.

Behaving greedily with respect to any other value function is a greedy policy, but may not be the optimal policy for that environment.

Behaving greedily with respect to a non-optimal value function is  not the policy that the value function is for, and there is no Bellman equation that shows this relationship.

Only the optimal policy has Bellman equation that includes $\text{max}_a$. All others must use the more general $v_{\pi}(s) = \sum_a \pi(a|s) \sum_{r,s'}p(r,s'|s,a)(r + \gamma v_{\pi}(s'))$

However, a greedy policy over a non-optimal value function is an improvement on the policy that resulted in that value function, which is shown by the policy improvement theorem.

If you can solve the Bellman equation for the optimal value function - either as a system of simultaneous equations, or using iteration in Dynamic Programming, then you will have the optimal value function and by implication behaving greedily with respect to it will be an optimal policy. This is the basis for Value Iteration.

source: Stack Exchange

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

sort: votes


text:
What do the square brackets $[ ]$ and $\mid$ mean in $[G_t \mid S_t=s]$?
Here is the formula of state-value function in Reinforcement Learning.

What do the square brackets $[ ]$ and $\mid$ mean in $[G_t \mid S_t=s]$? Why use square brackets? Why use $\mid$?
Why do mathematical formulas use all kinds of ambiguous symbols? Not as unique as the symbols of programming language?

The square brackets are part of the expectation operator (i.e. a function of a random variable, which in this case is $G_t$). This is common notation for the expectation. So, it's not $\left[ X \right]$, but rather $\mathbb{E}\left[ \cdot \right]$ or $\mathbb{E}\left[ X \right]$, for some random variable $X$. This notation is similar to the notation of a function $f(\cdot)$ or $f(x)$, but we use square brackets because expectations are taken with respect to random variables, which are actually functions (if this is too confusing, just ignore these details for now).
The $\mid$ is also common notation and means that we condition on knowing $S_t = s$ (an event). If you are not familiar with conditional expectations and probability distributions, you can take a look at them e.g. here.
So, you can read your formula as

the conditional expectation of $G_t$ (the return, i.e. the sum of future rewards), given that we know that the state at time $t$ is $s$ (i.e. the condition).

This is indeed the definition of the state value function.

Thanks for your patience, I have a similar question. $\sum_{r}\sum_{s'}p(s',r|s,a)[r+\gamma V\pi(s')]$, the $p(..|..)$ is probability, what's the meaning of the follow square bracket part $[r+\gamma V\pi(s')]$? Is it means the $p(..|..)$ multiply by $[r+\gamma V\pi(s')]$?

I found that this is really a multiplication operation. This notation inconsistency confuses me very much.

@JoeHuang Yes. Sorry for not answering immediately. Here, $[ \cdot]$ would be like $( \cdot )$, so, yes, it's just a multiplication. They probably used square brackets because, if you turn this equation into an expectation, you will see that it will be equivalent to an expectation of a random variable that looks like what is inside the square brackets. See my blog post here. It should clarify what I've just said.

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


text:
How does uniform offset tiling work with function approximation?
I get the fundamental idea of how tilings work, but, in Barton and Sutton's book, Reinforcement Learning: An Introduction (2nd edition), a diagram, on page 219 (figure 9.11), showing the variations of uniform offset tiling has confused me.

I don't understand why all 8 of these figures are instances of uniformly offset tilings. I thought uniformly offset meant ALL tilings have to be offset an equal amount from each other which is only the case for the bottom left figure. Is my understanding wrong?

@ quest ions,  did you find an answer to this problem? I have the same question.

@DSPinfinity the tiles they represent here refer to the features within the tilings. The tilings are still offset uniformly but the features/tiles can have this sort of formation. If you go back two pages you can see a visualisation of this

In this particular diagram, they are showing:

For a given state (shown by the small $+$ symbol), which tiles in each of the 8 tilings this state belongs to.

So the only difference between the cells in this diagram is the state the $+$ is from.
Following this, they show:

As such, the authors are showing how asymmetrically offset tilings tend to have less variance in how states are generalized by the tiles (in each tiling) they belong to.

Thanks! I realised this but hadn't gotten round to answer the question but you've done so here


text:
Is there a way to inject linear constrains during GAN training?
Given that I'm training a generative model, (say a generative adversarial network), and I know that my (real) inputs (let's say vectors $\textbf{x} \in \mathbb{R}^n$) satisfy linear constraints of the form e.g. $a_1\textbf{x}_1 + \dots a_n\textbf{x}_n =0$, where the coefficients are fixed, is there a way to inject this knowledge during training?

are the $a$ coefficient specific values, or generic values? Cause if the latter I suspect the model will collapse and generate only zero values, since that's equivalent to ask the model to solve $XX^{T}=0$ which is true only for $X=0$

also, just as a side note, GANs are not models but rather training approaches, the generative model is only the generator architecture

no, actually the coefficients are thought to be specific, we would assume that the original data lie in the union of hyperplanes for some fixed coefficients.

@JamesArten Can you please include these details in the post itself and rewrite the title in the form of a question, i.e. your specific question? Thanks.

Maybe a bit too trivial to work out of the shelf, but I would try to add a component to the adversarial loss based precisely on the given set of coefficients.
Something like:
$L_{linear}= \frac{\gamma}{k} \prod_{k}A_{k}\hat{x}$
which combined with the adversarial loss (assuming minimax, but any other choice is fine as well) would become:
$L(G, D)=E_{x}[log(D(x))] + E_{z}[(log(1 - D(G(z)))] + \frac{\gamma}{k} \prod_{k}A_{k}\hat{x} $
where $A_{k}$ is a set of fixed coefficients of an hyperplane, and $\hat{x}$ the vector sampled from the generator. I would use a product operator since the loss should drop to zero when $\hat{x}$ lies in one of the hyperplanes.
Instead $\gamma$ can be used to scale the loss to a value in the range of the generator and discriminator losses.

many thanks, that looks interesting. When you say adversarial loss , are you considering the mean loss between generator and discriminator? Are you considering the standard GAN approach where binary classification loss is considered?

precisely, I updated the answer to include the total loss, but I stress out again here that the choice of the adversarial loss doesn't matter, vanilla gan, non saturating gan, wasserstein gan are all good options. And you can add as many extra custom loss to it, as long as you formulate them to be converging to 0. (possibly smoothly, which is what my answer lack, it might be the case that as formulate naively now that extra component will assume large values now and then, fact that doesn't not prevent convergence per se).

many thanks Edoardo. Just as a quick clarification, is the constraining term in the loss function intended to be $\frac{\gamma}{k} \mathbb{E}_z[\Pi_k A_k G(z)]$ , so we take the mean over the batch?

good point! Yes it's definitely the case that for batches larger than 1 the loss score should be averaged


text:
How does stochastic gradient descent undo the normalization done by the batch normalization?
I want to understand the handshake between SGD (or mini-batch GD) and batch normalization. Below, an explanation quoted from this Medium article. However, I am confused about the denormalization by the SGD.

SGD ( Stochastic gradient descent) undoes this normalization if it’s a way for it to minimize the loss function.
Consequently, batch normalization adds two trainable parameters to each layer, so the normalized output is multiplied by a “standard deviation” parameter (gamma) and add a “mean” parameter (beta). In other words, batch normalization lets SGD do the denormalization by changing only these two weights for each activation, instead of losing the stability of the network by changing all the weights.

This Medium article!

I think this phrasing is a bit misleading. If I understand this passage correctly, another way to put it would be:
Applying batch normalization distorts the true data distribution: An arbitrarily distributed batch of data is transformed into a distribution with mean = 0 and standard deviation = 1. This might not be beneficial for the downstream task, so two scalars beta and gamma are introduced that are trainable and can modify the output of the BatchNorm. This formula for BatchNorm makes this clear:
$\text{BatchNorm}({\mathcal{X}}_{b}) = \gamma \cdot \frac{(\mathcal{X}_{b} - \text{mean}(\mathcal{X}_{b}))}{\text{std}(\mathcal{X}_{b})} + \beta$
Without the gamma and beta, you would simply normalize the batch. But SGD can modify beta and gamma and thereby shift the distribution around according to what the optimization task demands. By acting on beta and gamma, the SGD can then somewhat 'counteract' this normalization.

Thank you for the detailed answer, it's crystal clear now!

I'm glad it helped :)


text:
Why class embedding token is added to the Visual Transformer?
In the famous work on the Visual Transformers, the image is split into patches of a certain size (say 16x16), and these patches are treated as tokens in the NLP tasks. In order to perform classification, a CLS token is added at the beginning of the resulting sequence:
$$
[\textbf{x}_{class}, \textbf{x}_{p}^{1}, \ldots, \textbf{x}_{p}^{N}]
,$$
where $ \textbf{x}_{p}^{i}$ are image patches. There multiple layers in the architecture and the state of the CLS token on the output layer is used for classification.
I think this architectural solution is done in the spirit of NLP problems (BERT in particular). However, for me, it would be more natural not to create a special token, but perform 1d Global Pooling in the end, and attach an nn.Linear(embedding_dim, num_classes) as more conventional CV approach.
Why it is not done in this way? Or is there some intuition or evidence that this would perform worse than the approach used in the paper?

In their official repository, the author confirmed in the issue that the cls is not really important for the ViT, but they wanted to keep the ViT to be exactly the same with the NLP-Transformer, so they added it.
Issue link: https://github.com/google-research/vision_transformer/issues/61#issuecomment-802233921

However, for me, it would be more natural not to create a special token, but perform 1d Global Pooling in the end, and attach an nn.Linear(embedding_dim, num_classes) as more conventional CV approach.

Surprisingly, this approach was experimented in this new paper Better plain ViT baselines for ImageNet-1k and implemented as default in the torch-vit repository.
Along with other trivial improvements, the authors actually outperform other methods such as DieT or ViT with strong data augmentation.  The modification you described provides 1.8% accuracy gain in the ablation study.
The paper is essentially 1.5 pages so I definitely recommend having a look!
link: https://arxiv.org/abs/2205.01580


text:
How can I interpret the value returned by score(X) method of sklearn.neighbors.KernelDensity?
For sklearn.neighbors.KernelDensity, its score(X) method according to the sklearn KDE documentation says:

Compute the log-likelihood of each sample under the model

For 'gaussian' kernel, I have implemented hyper-parameter tuning for the 'bandwidth' parameter using Bayesian-Optimization as follows:
# The input data for which 'bandwidth' needs to be tuned-
data
# (2880, 64)

def kde_hyperopt_eval(bandwidth):
    params = {}
    params['bandwidth'] = bandwidth

    # Initialize a KDE model-
    kde_model = KernelDensity(
        kernel = 'gaussian',
        bandwidth = params['bandwidth']
    )

    # Train KDE model on training data-
    kde_model.fit(data)

    # Compute the total log-likelihood under the model.
    # Returns the log probability.
    '''
    Total log-likelihood of the data in X. This is normalized to be a
    probability density, so the value will be low for high-dimensional
    data.
    '''
    return kde_model.score(data)

optimizer = BayesianOptimization(
    f = kde_hyperopt_eval,
    pbounds = {
        'bandwidth': (0.01, 10)
        }
)

optimizer.maximize(n_iter = 40, init_points = 15)

and I'm getting the result as
|   iter    |  target   | bandwidth |
-------------------------------------
|  1        | -5.644e+0 |  8.527    |
|  2        |  2.142e+0 |  0.3419   |
|  3        | -1.287e+0 |  0.7963   |
|  4        | -5.916e+0 |  9.883    |
|  5        | -3.604e+0 |  2.817    |
|  6        | -5.71e+05 |  8.835    |
|  7        | -5.246e+0 |  6.868    |
|  8        | -4.385e+0 |  4.305    |
|  9        | -5.546e+0 |  8.082    |
|  10       | -5.86e+05 |  9.585    |
|  11       | -5.226e+0 |  6.794    |
|  12       | -5.196e+0 |  6.685    |
|  13       | -9.934e+0 |  0.6771   |
|  14       | -5.766e+0 |  9.111    |
|  15       |  6.816e+0 |  0.2584   |
|  16       |  6.565e+0 |  0.01     |
|  17       |  6.565e+0 |  0.01     |
|  18       |  6.804e+0 |  0.2585   |
|  19       |  6.804e+0 |  0.2585   |
|  20       |  6.804e+0 |  0.2585   |
|  21       |  6.804e+0 |  0.2585   |
|  22       |  6.804e+0 |  0.2585   |
|  23       |  6.804e+0 |  0.2585   |
|  24       |  6.804e+0 |  0.2585   |
|  25       |  6.804e+0 |  0.2585   |
|  26       |  6.804e+0 |  0.2585   |
|  27       |  6.804e+0 |  0.2585   |
|  28       |  6.804e+0 |  0.2585   |
|  29       |  6.804e+0 |  0.2585   |
|  30       |  6.804e+0 |  0.2585   |
|  31       |  6.804e+0 |  0.2585   |
|  32       |  6.804e+0 |  0.2585   |
|  33       |  6.804e+0 |  0.2585   |
|  34       |  6.804e+0 |  0.2585   |
|  35       |  6.804e+0 |  0.2585   |
|  36       |  6.804e+0 |  0.2585   |
|  37       |  6.804e+0 |  0.2585   |
|  38       |  6.804e+0 |  0.2585   |
|  39       |  6.804e+0 |  0.2585   |
|  40       |  6.804e+0 |  0.2585   |
|  41       |  6.804e+0 |  0.2585   |
|  42       |  6.804e+0 |  0.2585   |
|  43       |  6.804e+0 |  0.2585   |
|  44       |  6.804e+0 |  0.2585   |
|  45       |  6.804e+0 |  0.2585   |
|  46       |  6.804e+0 |  0.2585   |
|  47       |  6.804e+0 |  0.2585   |
|  48       |  6.804e+0 |  0.2585   |
|  49       |  6.804e+0 |  0.2585   |
|  50       |  6.804e+0 |  0.2585   |
|  51       |  6.804e+0 |  0.2585   |
|  52       |  6.804e+0 |  0.2585   |
|  53       |  6.804e+0 |  0.2585   |
|  54       |  6.804e+0 |  0.2585   |
|  55       |  6.804e+0 |  0.2585   |
=====================================

How can I interpret this value returned by score(X) method of sklearn.neighbors.KernelDensity?
For example, in case of Mean Squared Error or Mean Absolute Error, smaller means better, for accuracy, higher percentage value is better.

The KernelDensity model learns a probability distribution from the training data. The score reflects how likely it is that any given sample has been drawn from the learned probability distribution.
The higher this number is, the more the given sample matches the distribution.
For example: If the sample is x = 0 and your model has learned the standard normal distribution $\mathcal{N}(0, 1)$, the likelihood would be very high. In contrast, if x = 50 the likelihood is low, because the probability to draw 50 from $\mathcal{N}(0, 1)$ is very low.
Therefore: The higher the score, the better the model reflects the samples. And in your case, it seems that the model learns a distribution that fits your data best when the bandwidth is 0.2585.


text:
Why do we have $t$ as subscript in $V$ instead of $t+1$ in the expression of $G_{t:t+1}$?
In one-step  TD updates,  the target is the first reward plus the discounted estimated value of the next state, which we call the one-step return (page 143 of Sutton & Barto):
$$
G_{t:t+1} \triangleq R_{t+1}+\gamma V_{t}(S_{t+1})
$$
where $V_t: \mathcal{S} \to \mathbb{R} $ is the estimate at $\textbf{time t}$ of $v_{\pi}$.
My question is this: Why do we have $t$ as subscript in $V$ instead of $t+1$ in the expression of $G_{t:t+1}$? Since we are at time $t+1$ where state is $S_{t+1}$, it seems more logical to have $V_{t+1}(S_{t+1})$.

Can you provide the source of this notation? Where did you find it?

@ bro, Sutton-Barto's RL book, page 143. second paragraph.

Please, next time, for completeness, provide this info directly into your post.

I would imagine that here $V_t$ denotes your estimate of $V$ itself at time $t$. So even though we are estimating the value of the next step, it is only our estimate of $V$ at the $t$th iteration of the algorithm.

TD-learning is based on bootstrapping. The TD target $R_{t+1} + \gamma V_t(S_{t+1})$ describes the immediate reward (random variable), $R_{t+1}$, plus the discounted estimated return (starting from the next state $S_{t+1}$, which is also a random variable), $V_t(S_{t+1})$. The reason why the discounted estimated return of the next state is calculated based on $V_t$ is that we do not know $V_{t+1}$ yet, that is at the current iteration of the algorithm.
What we want to do, is to find the optimal $V = V^*$, which would be the same for all timesteps. Then, $V^*_t = V^*_{t+1}$.


text:
Why $ t=τ+n-1$ instead of $t=τ+n$ in n-step TD?
If $\tau$ is the time, whose state’s estimate is being updated, and $t$ is the current time, then, in n-step TD method, we have $t=\tau+n$ (because we have to wait n-steps, before we can update). However, in the following pseudocode (Sutton & Barto's RL book, page 144), they have: $\tau=t-n+1$ which means $t=\tau+n-1$. What is wrong in my reasoning?

The main detail that you are missing is that $t$ does not represent the "current time step" throughout the loop, but is just a variable giving a reference to a time step that you are processing.
The first statements in the loop are:

Take an action according to $\pi(\cdot,S_t)$
Obbserve and store the next reward $R_{t+1}$, and the next state as $S_{t+1}$

It is clear that after these two steps that the "current" time step is $t+1$. The value of $t$ is then just a reference to a particular time step that all the maths for the other loops is set up to use.
This in turn means that because the process has the values of $R_{t+1}$ and $S_{t+1}$, then it is ready to process the estimate for time step $\tau = t - n + 1$.
It would not really help to have $t$ one higher throughout the loop, because you would still need offsets allowing you to refer multiple time steps within a single loop. Instead of having the odd extra $+1$ you would see some $-1$s instead. E.g. you would need to take an action according to $\pi(\cdot,S_{t-1})$
You could swap the sequence of the two "If" blocks and have $\tau = t - n$ as the first statement.


text:
Is sklearn using both a threshold and a bias term?
Reading this Can a neuron have both a bias and a threshold? has confused me, as it appears to be more common to use a threshold of 0 when using bias. But reading this https://stackoverflow.com/questions/19984957/scikit-learn-predict-default-threshold indicates that the threshold is 0.5.
So my question is, is sklearn using both a threshold and a bias term ?

Questions about software libraries or APIs are off-topic here. You're asking about sklearn, so your question is off-topic.

The quick answer is yes. The implementation of sklearn use both a bias for each weight and a final threshold, by default set to 0.5
It sounds to me though that you don't have a clear idea about the purpose of the threshold in the first place, so let's elaborate more on that.
why do we use a threshold
A perceptron, and any other type of model, return continuous values. For some tasks (e.g. regression) we can compute error directly on these continuous values, but for other tasks (e.g. classification) we need to convert these values into discrete values, usually binary, which tell us if the model is predicting a yes or a no for a specific node. The threshold serves precisely for this purpose. We apply it to the very last probabilities returned by a model to convert them into discrete outputs (and I stress out probabilities, not logits, so you need to apply first either sigmoid of softmax).
when do we modify the threshold
The only moment in which is reasonable to change the threshold is after training. And the reason to do so is that we want to test if there are values different from 0.5 that lead to better metrics score. Usually this is performed using the ROC curve. i.e. we compute the amount of false positives an false negatives for different thresholds and we check what threshold lead to the highest AUC score (the red one in the plot, which maximize the ROC area).
But there is no point in using a different threshold from 0.5 during training. And there is no point in associating multiple threshold to each bias in a model. The only reason why the threshold is used is to discretize continuous values ad turn them into final predictions.

Thank you for your answer, but I was wondering why you wrote about threshold during training, as I thought the cost function directly used the output of the final activation function, without threshold.

In the sklearn code of the Perceptron you can see here that a threshold of 0 is used when calling the predict function. And here is where the bias is added (they call the bias _intercept).
Using both doesn't really change the behavior of the perceptron, because you can reformulate the formulation like this:
$$
\begin{align}
\mathbf{Wx} + b &> t && | \text{ Perceptron with bias $b$ and threshold $t$}\\
\Leftrightarrow \mathbf{Wx}+(b-t) &> 0 && | \text{ threshold 'included' in bias} \\
\Leftrightarrow \mathbf{Wx}       &> (t - b) && | \text{ bias 'included' in threshold}
\end{align}
$$
(From a learning perspective, there is a slight difference, because the threshold is not a learnable parameter, so it would change the optimum of the weights.)


text:
Why is it called "area of union" when calculating the Intersection over Union?
When calculating the Intersection Over Union the following explanation is widely used.

(Source: A Survey on Performance Metrics for Object-Detection Algorithms, by Padilla et al. 2020)
The image and name suggest that the denominator (the area of union) is the area of both boxes combined, box a + box b, when in reality it's not a union but rather a symmetric difference, box a + box b - intersection of box a and box b.
Why is it called "area of union" and not "area of symmetric difference"?

The question aims at the denominator which is called area of union even though its not really a union when considering the union definition from the set theory.

Consider these two sets $A = \{1, 2, 3, 4 \}$ and $B = \{0, 2, 3, 5, 6 \}$. Their union $A \cup B = \{0, 1, 2, 3, 4, 5, 6\}$. So, $|A \cup B| = 7$. The order of these numbers in $A \cup B$ does not matter, but you don't have any repeated number.
If you do $|A| + |B|$, you're effectively counting the number of elements in $A \cap B$ twice (in the example above, it would be like doing $4 + 5 = 9$, while in reality $|A \cup B| = 7$), so you subtract $|A \cap B|$ from $|A| + |B|$, i.e. $|A \cup B| = |A| + |B| - |A \cap B|$, where $|X|$ is the size of the set $X$.
See also the related Wikipedia article.


text:
What is the difference between the positional encoding techniques of the Transformer and GPT?
I know the original Transformer and the GPT (1-3) use two slightly different positional encoding techniques.
More specifically, in GPT they say positional encoding is learned. What does that mean? OpenAI's papers don't go into detail very much.
How do they really differ, mathematically speaking?

The purpose of introduction of positional encoding  is to insert a notion of location of a given token in the sequence. Without it, due to the permutation equivariance (symmetry under the token permutation) there will be no notion of relative order inside a sequence.
Given a token at $\text{pos}$-th position we would like to make the model understand, that this token is at particular position. See pretty nice blog here - https://kazemnejad.com/blog/transformer_architecture_positional_encoding/.
Fixed encoding
In the original Transformer one uses a fixed map from the token position $i$ to the embedding vector added to the original embedding:
$$
\begin{aligned}
PE(\text{pos}, 2i) &= \sin(\text{pos} / 10000^{2i / d_{\text{model}}}) \\
PE(\text{pos}, 2i + 1) &= \cos(\text{pos} / 10000^{2i / d_{\text{model}}})
\end{aligned}
$$
Here $\text{pos}$ is an index of the token in sequence, and $2i, 2i+1$ correspond to the dimension inside the embedding.
Learned encoding
Another strategy is to make map for $\text{pos}$ to the embedding vector of dimension $d_{\text{model}}$ learnable. One initializes somehow for each position in the sequence vector of positional embedding for each position from $0$ to $\text{max_length}$ and during the training these vectors are updated by gradient descent.

As far as I understood, the difference is the following: original Transformers use a fixed type of encoding, based on sine/cosine functions.
On the other hand, GPT produces two embedding vectors: one of the input tokens, as usual in language models, and another for token positions themselves.


text:
How should I initialize the weights of the neural network so that the initial policy is uniform?
I would like to train a neural network (NN) so that it learns the policy and value function for my agent.
Since I am using reinforcement learning and do not want to prefer certain actions in certain states at the beginning of the learning, ideally, my NN should be initialized in a way that it predicts a uniform policy for all of the actions in every state and then during training, it will adjust its weights based on the observations.
The idea for this weight initialization is to speed up the training process by not "delearning" random initial policy that can be off by quite some margin and to also guarantee equal exploration from every state straight from the beginning.
I would like to ask two questions about this topic:

Is this a good idea?
Are there any available tools for achieving this?

what you describe sounds like a simple uniform weight initialization, which all deep learning libraries allow out of the shelf. Be aware though that initializing a network to output uniform stuff doesn't necessary mean faster training. It's an assumption that sounds logical to us but it's not correlated at all with the optimization problem math the network is suppose to learn.

Can you please put your specific question in the title? "Weight initialization for Deep Reinforcement Learning" is not a question and it's quite general.

@EdoardoGuerriero uniform weight initialization in the last layer does not necessarily produce uniform policy, since final output also depends on the values coming from the previous layers, or am I thinking somewhere wrong? (e.g. if we would have same weights in last layer but use ReLU in the penultimate layer then final probabilities will be scaled by the input coming from the ReLU, won't they?)

@Druudik that is true, there will always be some unbalance due to the input values, but still uniform initialization would be the only one capable to minimize that variation. There's no way to generically account for input variation to output a constant value, or to say it differently, you would have to train the model on that task first. And that would be tricky as well, for example it's not hard to see that if using biases the model would probably converge immediately on a solution with zero weights an 1/n bias values. (n = amount f output nodes)

Thanks. The title was not really in the form of a question. Check it now. Is that your question? By the way, for completeness, it might be a good idea to specify also the RL algorithm you're using.

@nbro yes that is exactly what I was trying to ask! Regarding the RL algorithm, I meant it as a more of a general question that can be applied to any RL algorithm which uses NN as a model for value and policy function.

You may be interested in section 3.2 of this paper What Matters In On-Policy Reinforcement Learning? A Large-Scale Empirical Study (2020) by Google Research.
They claim that the initialization of the policy is very important to performance, sometimes making a huge (66%) improvement, just from the initialization of the policy.
I'm assuming you already know that the kernel weights in neural networks are initialized using the glorot uniform  distribution; in that paper, they suggest that for the output layer, those weights should additionally be divided by 100.


text:
How is the probability of a greedy action in "$\epsilon$-greedy policies" derived?
In Sutton & Barto's book on reinforcement learning (section 5.4, p. 100) we have the following:

The on-policy method we present in this section uses $\epsilon$ greedy policies, meaning that most of the time they choose an action that has maximal estimated action value, but with probability $\epsilon$ they instead select an action at random. That is, all nongreedy actions are given the minimal probability of selection, $\frac{\epsilon}{|\mathcal{A}|}$, and the remaining bulk of
the probability, $1-\epsilon+\frac{\epsilon}{|\mathcal{A}|}$, is given to the greedy action.

I understood the probability of a random action selection: since the total probability of random action selections is $\epsilon$ and since all actions can be selected as random we calculate the probability of an action to be selected randomly as $\frac{\epsilon}{|\mathcal{A}|}$.
However, I did not understand how the probability  $1-\epsilon+\frac{\epsilon}{|\mathcal{A}|}$ for greedy action selection was derived. How is it calculated?

I did not understand how the probability  $1-\epsilon+\frac{\epsilon}{|\mathcal{A}|}$

It is the sum of two mutally-exclusive possibilities:

The agent chooses to exploit, selecting the greedy action with probability $1 - \epsilon$

The agent chooses to explore (probability $\epsilon$), and so happens to randomly choose the original greedy action (probablility $\frac{1}{|\mathcal{A}|}$). Combined probability $\frac{\epsilon}{|\mathcal{A}|}$.

Although you might expect that exploring actions would exclude the greedy action, in $\epsilon$-greedy approach they do not. It keeps implementation simple, although it does result in this extra term cropping up in the expression for probability of choosing the greedy action.
Moving the excess probability to other actions, or adjusting the original exploration probability would also both result in an extra small term cropping up in other parts of the theory. There isn't a "clean" way to build an $\epsilon$-soft action probability distribution without this slight added complexity.

I understand that there's a probability $1-\epsilon$ of selecting the greedy action and there's also a probability $\frac{\epsilon}{|\mathcal{A}|}$ of selecting the greedy action when you select at random, and that these 2 events never occur at the same time, so their probability of occurring at the same time is zero, hence you can "just" sum the probabilities. But why do you need to sum, if you select the greedy action with probability $1- \epsilon$?

Anyway, $\pi$ is a probability distribution, so the sum of all probabilities should be 1. What do you sum to give 1? I think this is unclear from your answer. Surely, $(1 - \epsilon) + \epsilon = 1$. But this is the sum of probabilities of selecting the greedy action and not selecting the greedy action.

@nbro: I am not sure what you are asking. You summarised it well in your first sentence. Your very last sentence is not quiite correct. If you change it to "But this is the sum of probabilities of exploiting and exploring" that would be accurate, and avoid the problem of assuming that exploring is mutually exclusive to taking the greedy action. In $\epsilon$-greedy, sometimes you "explore" and end up taking the greedy action anyway.

Actually, I asked 2 questions in order to clarify this answer. 1) Why do we sum the probability of taking the greedy action when we select it at random to the probability of selecting the greedy action when we do not take it at random? Yes, that is the "total" probability of selecting the greedy action, but then what is $1- \epsilon$? This you answered in the last comment, i.e. the probability of exploiting, which is not the same thing as the probability of taking the greedy action?! 2) How do you show that $\pi$ sums up to $1$ using these probabilities?

Maybe these weren't the original doubts that the OP had, but, in my view, this answer isn't clear enough without an answer to these 2 questions. One could ask these as separate questions on the site.

I did not understand how the probability 1−ϵ+ϵ/|A|

It's about mutually exclusive probabilities. If A and B are mutually exclusive events, and C can happen in both:

Then, P(C) = P(C$\cap$A) + P(C$\cap$B) = (1−ϵ) +ϵ/|A|.
In English: the prob of C happening = (the prob of both C and A happening) + (the prob of C and B happening).


text:
Why doesn't dropout mislead results during evaluation?
I have seen that, usually, the dropout layer is used differently in training and evaluation modes, i.e. it is recommended to use during training but not in evaluation/testing.
Dropout does remove a few nodes at random so that model does not end up in co-adaption. But, logically, if you are using one layer in training and not in evaluation/testing, should not the result be inconsistent? How/ why do we achieve the same/similar results though we are skipping a layer altogether?

How/why do we achieve the same/similar results though we are skipping a layer altogether
Dropout is not a layer, even tough deep learning libraries implement it as a layer module for convenience.
Why do we achieve same results? We don't, that's why dropout is applied only during training and not during test. And the fact that results change is also the core idea of dropout as a regularization technique.
When we train a model we want the model to be robust, i.e. similar input data should lead to same predictions, but due to over fitting this is almost never the case. Over fitting comes from several sources, the one addressed by dropout is preventing some weights of a model becoming too large and others becoming too small.
Let's say our model is a simple equation like:
$w_1*x_2 + w_2*x_2 + b = y$
Where x1, x2 are two features and w1, w2 are the associate weights. It might be that the model starts over fitting, for example w1 might become too large and w2 to small, then our model will learn to focus only on feature x1, ignoring x2. By randomly "dropping" w1, we'll force the model to focus also on x2 as a valuable feature, preventing w2 becoming too small. Because of the randomness of dropout, the weights will converge to an optimal solution for both, not just one of them, so when applying both weights the prediction will be ideally more robust than when using only part of them. Of course in real use cases models never converge to a perfect minima where part of the weights lead to exactly the same predictions as the whole model, so in test phase dropout is disable to guarantee same predictions for same training instances every time.
There is though a nice example of dropout used during test case in Deep Active Learning. Active dropout in test phase can be leveraged to perform Monte Carlo sampling of different probability scores for a single instance. The sampled probability can be then used to compute statistics like standard deviation, which can be used as an approximation of the aleatory uncertainty of the model regarding that particular instance.


text:
How can I detect thin objects (like pens and pencils) without a bounding box but only 2 endpoints and the orientation?
I am looking to detect thin objects, like pens, pencils, and surgical instruments. The bounding box is not important, but I am looking to see if I can train a model to detect both the object as well as its orientation.
Typical object detection networks, like R-CNN, YOLO, and SSD encode the class name and bounding boxes. Instead of bounding boxes, I'm looking to encode only 2 points, one starting $x,y$ point and one ending $x,y$ point.  The start point for objects is where one would grip the object.  For instance:

The pencil eraser(start point) is pointed 50 degrees to the top right.
The surgical instrument is 10 degrees from the x-axis and the handle is pointed to the bottom right.
Pen tip (endpoint) is pointing vertically upwards.
Fork, the start point would be the grip handle part, and the endpoint would be in the middle where the 4 prongs are.

As long as I can encode the start and endpoints, then I can determine the orientation. I would need to define these points during training.
The question is whether there is an existing model (mobile net/inception/RCNN) that I can encode this information in?  One potential way I was thinking was to use YOLO and for the bounding box, the top left $x,y$ would be the starting point $x,y$ (handle), whereas the bounding box's width and height would be replaced with the endpoint $x,y$ (pencil writing tip, fork prongs.

I am looking for a solution for the same question.. I trained on YOLO4 and looking for orientation,,, Any update?

You could just go with any fully convolutional network that has the same output resolution as the image input resolution (e.g. from semantic segmentation) as your backbone.
Then
Solution 1: You could adapt the last layer to have 4 feature maps where the first 2 maps represent the proability of existance or non-existance of point 1. And the last 2 maps represent the proability of existance or non-existance of point 2. This then gives you a heatmap of the existance of such points. Here you should also do non-maximum supression to only get single likely points instead of areas. Furthermore you need to apply the softmax function correctly only on each 2 points separately. Or use a sigmoid layer where you only solve a binary problem and use 2 feature maps instead of 4.
Solution 2: If there is no clear physical/unique explaination of wich point should be regarded as point 1 and which point as point 2 then solution 1 might be problematic since you force the model to decide on that (by having dedicated point 1 and point 2 feature maps) which is then actually not possible.
In that case you could do e.g. this approach:
Use 4 feature maps where the first two maps represent the probability of existance or non-existance of a point in general. Then use the last 2 maps to represent the normalized x/y vector that points to the corresponding other point. Then afterwards you can filter out corresponding points by looking if their regression vector points towards each other. (This is somewhat similar and adapted to what center point net does). Here only the first 2 layers should be sigmoided and the last 2 are regression layers, but normalized. Non-max suppression should also be done here to filter out only single points.
These both approaches have the nice property of being fully convolutional and therefore translation invariant. It means for example you can easily adapt it to other image resolutions.

Recent work achieves a similar task: Object recognition together with the bounding box (e.g. YOLO---there are quite a few on Github too). The bounding box is not enough in your case, but it is an interesting pattern: Recognition plus some form of measurement. Such architectures could be good candidate to start with, and repurpose for stick orientation.
The problem could also leverage the current results in gait recognition. In fact, this looks closer to the problem at hand than object recognition. An example is this model based on multiview (many pictures input) recognition, with a demonstration on Github. Gait recognition is also popular these days, and many inspiring papers and OSS implementations are available.
The above presents two approaches your problem could benefit from, as a "combination". My gut feeling is that tilt and orientations may be easier than direction (i.e. where is the tip?).

The question calls for training a model. An alternative approach, perhaps to start with and get more insight, could be to go with "standard" computer vision algorithms, such as the Hough Transform. This transforms allows to find lines in an image. The mathematics are at reach, and it may work well enough for a quick demo. Also, your handle name suggests "embedded mobile" engineer, and a simple Hough Transform could be cheap on mobile.

Appreciate the feedback.  I am considering a modified version of any bounding box model.  Instead of the coordinates defining the box, it would just be the coordinates for the tip and end of the instrument.  So for instance, for a pencil, the tip would be the sharp lead writing part while the end would be the eraser.  For forceps, the tip would be the clamp of the forceps while the end would be the handle, where the forceps are attached.  I just do not know if this approach can work.  I wanted to get some confidence before labeling all the training data before going ahead with this approach.

Hough transform would be great for lines (like these), but cannot determine orientation.  You're right though, it is indeed good for mobile. :)

Is there a way to update the question to get more specific answers, and perhaps refine mine? As for the Hough transform, sorry if the explanation was vague (possible edit too). The transform detects lines only. The orientation takes a bit more work, but knowing two points on each line, and the orientation of the photo (e.g. EXIF metadata) are enough.

I've updated the question to be more specific.  Thanks.

I would say pose recognition is also very similar to OP's requirement. E.g. https://static.googleusercontent.com/media/research.google.com/en//pubs/archive/42237.pdf  - although achieving results like the paper requires a lot of labelled data, it might be achieved for simpler objects via using a game engine renderer.

@NeilSlater Your interesting comment could be a terrific alternative answer. How about posting an answer, perhaps elaborating a bit more?


text:
Equations for computing true positives and false positives when using object detection algorithms?
I am running some evaluation metrics using the YOLOv5 object detection algorithm, and wish to calculate my true positives and false positives. For instance, the evaluation metric outputs are as follows:
   Class          Images    Labels     Prec     Recall     mAP@.5     mAP@.5:.95:
     all          100         36      0.444      0.702      0.481      0.223
 Class 1          50          29      0.588      0.689      0.668      0.333
 Class 2          50           7      0.301      0.714      0.293      0.113

Looking at this source, I found that you could calculate the true positives and false positives with the following equations:
#Computed for Class 1

TP = Recall * Labels = 34.45 ≈ 34
FP = (TP / Precision) - TP = 23.82 ≈ 24

I am new to evaluation metrics, so at first glance, I'm thinking that the false positive number is fairly high. Is this the correct formula to compute the true positives and false positives? I'm just looking for some verification and some explanation as to why this works, if it does.

Recall is the fraction of the relevant documents that are successfully retrieved.
\begin{aligned}{\text{Recall}}&={\frac {tp}{tp+fn}}\,\end{aligned}
Labels for a Class is equal to total examples which are actually belonging to the class: P = FN + TP
Hence (FN + TP)* Recall = TP
Precision is the fraction of retrieved documents that are relevant to the query:
\begin{aligned}{\text{Precision}}&={\frac {tp}{tp+fp}}\end{aligned}
Using simple maths you will easily get FP = (TP / Precision) - TP
In your calculation your might have use Images instead of Labels:
TP = Recall * Labels = 19.98 ≈ 20
FP = (TP / Precision) - TP = 14

Reference: https://en.wikipedia.org/wiki/Precision_and_recall

Thanks, this is what I was looking for! You are right, I used "images" instead of labels.


text:
Why do terms in the computation of state space size scale exponentially?
The image below is from a Berkeley AI course pdf I found.

My question is, why do the terms accounting for the ghosts and pellets come in raised to the number of units?
For example, there are two ghosts so the exponent is 2, there are 30 foods so the exponent is 30.
Intuitively, I feel like if there are 30 foods, each with 2 states, then that is 60 states, no $2^{30}$.

Intuitively, I feel like if there are 30 foods, each with 2 states, then that is 60 states, no $2^{30}$.

Let's try it with 3 pellets. If you are right there would be $2 \times 3 = 6$ states, if the authors are right there would be $2^3 = 8$ states.
Using * for a pellet, and - for a space, we have the following states:

* * *
* * -
* - *
* - -
- * *
- * -
- - *
- - -

That's 8 states. The authors are correct.
In this case, intuitively the state is essentially one long 30-bit number - you can replace pellets with 1 and spaces with 0. In general, the rule is that if some component of the state can vary into $n$ different sub-states independently of other components, then the size of the whole state space multiplies by $n$.
There is a slight oversimplification, in that the pacman might not be able eat the pellets arbitrarily (although in the example given it looks like they can). Some states might not be reachable. However, trying to figure out all the reachable states and enumerate them in a useful way so that there is still a simple vector model to learn from would be complicated - possibly more complicated than solving the reinforcement learning problem for the same game. It is easier to simplify the state representation and have a larger overspecified state space.


text:
Where are the parentheses in the Bellman update rule?
I'm not having a lot of intuition about the equation. I have this Bellman update rule:
$$v_{\pi}(s) =\sum_a \pi(a|s)\sum_{s',r} p(s',r|s,a)[r+ \gamma v_{k}(s')]$$
But where are the parenthesis? Is the second sum using the index $a$ from the first sum? Or is it independent, and can I move out the $[r+ \gamma v_{k}(s')]$ term out of the sum?

Here's your equation with an additional couple of parenthesis that emphasizes the order of the operations (note that you had a small typo in your original equation).
$$v_{\pi}(s) =\sum_a \pi(a \mid s) \left(\sum_{s',r} p(s',r \mid s,a)[r+ \gamma v_\pi(s')] \right)$$
Now, let me answer your other questions.

Is the second sum using the index $a$ from the first sum?

Yes.

Or is it independent, and can I move out the $[r+ \gamma v_\pi(s')]$ term out of the sum?

No, and you cannot move this term out of the sum because the second sum is a sum over $r$ and $s'$ and $r+ \gamma v_\pi(s')$ depends on those terms.
Note that $v_{\pi}(s)$ is defined as an expectation and that $\pi(a \mid s)$ (the policy) and $p(s',r \mid s,a)$ (the model) are probability distributions.

Worth noting this is a common convention when concatenating $\sum$ terms, that they are nested with implied parens as you show. I'm sure there will be some discipline that does not do that, but all the ML I have read does this.

I'm sorry, I'm coming back and got confused, shouldn't be like this:
$$v_{\pi}(s) =\sum_a \left( \pi(a \mid s) \sum_{s',r} p(s',r \mid s,a)[r+ \gamma v_\pi(s')] \right)$$
Since the second sum uses the same $a$ index.. Putting the indexes the way @nbro does implies the sums are independent

@nammerkage You can also write that and with the parentheses that I show in my answer. Both are ok. Parentheses here are used just to emphasize the precedence of the operations. So, you can also write $$v_{\pi}(s) =\sum_a \left( \pi(a \mid s) \left( \sum_{s',r} p(s',r \mid s,a)[r+ \gamma v_\pi(s')]\right) \right)$$


text:
Why and how can the policy and value iteration methods converge to the OPTIMAL point?
I am reading Reinforcement Learning: An Introduction  by Sutton & Barto. According to this textbook, as far as I understood, the authors claim that the policy and value iteration methods converge to an optimal stationary point. Actually, I now understand the procedure of these two iterative algorithms, but I can't accept why they converge to an optimal point.
In the textbook and many posts that I found by googling, many people say that "The value functions are monotonically increased as the iteration progresses. Thus, it will go to the optimal policy, as well as optimal value functions."
I strongly agree that "only if the algorithm's performance is monotonically improved and there exist an upper bound in terms of performance, the algorithm will converge to a stationary point." However, I cannot accept the word "Optimal." I think, to claim an algorithm converges to an optimal stationary point, we need to show not only its monotonic improving property but also "its locally non-stopping property." (Sorry, I made these words myself, but I believe you experts can understand what I mean.)
I believe that there must be some points that I was not able to understand. Can someone let me know why the policy and value iteration methods converge to an "OPTIMAL" solution?
ps. Only if the system can be represented as a Markovian decision process, are either the policy or the value iteration method optimal algorithm?

These two algorithms converge to the optimal value function because

they are instances of the generalization policy iteration, so they iteratively perform one policy evaluation (PE) step followed by a policy improvement (PI) step

the PE step is an iterative/numerical implementation of the Bellman expectation operator (BEO) (i.e. it's numerical algorithm equivalent to solving a system of equations); here you have an explanation of what the Bellman operator is

the BEO is a contraction (proof here), so the iterative application of the BEO makes the approximate value function closer to the optimal one, which is unique, i.e. PE convergences to the optimal value function of the current policy (proof here)

Policy improvement is guaranteed to generate a policy that is better than the one in the previous iteration, unless the policy in the previous iteration was already optimal (see the policy improvement theorem in section 4.2 of the RL bible)

One thing that may confuse you is that you don't exactly know or have in mind the definition of the value function. A value function $v_\pi(s)$ is defined as the expected return that you will get starting in state $s$, then following policy $\pi$. So, if you have some policy $\pi$, then you perform one PE step until convergence, then you know that that value function is the optimal value function for $\pi$. Now, if $\pi_{t+1}$ is guaranteed to be a strict improvement over $\pi_{t}$, then it basically means that you will get more rewards with $\pi_{t+1}$ (which is the goal).
If you read the linked proofs and chapter 4 of the bible, then you should understand why these algorithms converge.
To address your last point, yes, we assume that we have an MDP. That's an assumption that most famous DP and RL algorithms make.

Thank you for your great answer. I have one more question. Can I say that "only if the system follows an MDP, the greedy-based policy iterative algorithm (despite not the epsilon-greedy-based one) provides an optimal policy as well as the corresponding optimal value functions for all states."?

For the $\epsilon$-greedy case we can do exploration with a probability of $\epsilon$, but for the greedy case we can't do. (I know, this does not imply that greedy cannot find an optimal solution, but it also does not imply that it will find an optimal solution.) Anyhow, is there no chance of getting stuck at $\pi$ such that $\pi<\pi^$, where $\pi^$ is the optimal policy? That is, is there a case where all the optimal value functions are found at a given $\pi$, and the policy improvement algorithm is executed based on them, but getting stuck at $\pi$ despite $\pi<\pi^*$.

I agree that if the $\epsilon$-soft (e.g., $\epsilon$-greedy)-based policy improvement is executed, a better policy will be found one day as long as it exists for a given set of value functions of all states. However, my intuition makes me think that if the greedy-based policy improvement is used, there might be the case where a better policy will not be found for a given current set of value functions of all states. Is my intuition totally wrong?

@Danny_Kim Did you understand why policy evaluation converges? Note that this happens only in the limit, i.e. if you execute "enough" iterations. Once you find the value function for a given policy, then you generate a new policy that is guaranteed to be a strict improvement over the previous one (if you read section 4.2 of the mentioned book, you will understand why). If you do this enough times, then (in the limit) you will get to the optimal policy. In practice, I am not sure how well policy iteration converges (it depends on $\gamma$ I think), but, in theory, they should converge.

Why can't you get stuck in a local optima? Because there's only one optimum. Note that we're not talking about Q-learning or SARSA, which are RL algorithms that do not use the model of the environment, while policy iteration does. Q-learning and SARSA do need to explore the environment (e.g. using the $\epsilon$-greedy policy) because they do not have the model of the environment, i.e. the probability distribution $p(s', r \mid s, a)$. The intuition of the convergence of PI can be found in the last diagram here.

To address your first question in the comments, I've never seen policy iteration being described in a context outside of MDPs, so I don't know if something similar exists for other mathematical frameworks. Which ones do you have in mind?

Base on the fantastic answer by @nbro, let me complement a little bit clue which may help understand Policy Iteration's optimality convergence.
So Danny you said:

However, I cannot accept the word "Optimal." I think, to claim an algorithm converges to an optimal stationary point, we need to show not only its monotonic improving property but also "its locally non-stopping property."

I think here you actually worry about it may miss some possible cases which contains the optimal one in the process of iteration. However it won't. Here is a excerpt on page 75 in Reinforcement Learing: An Introduction written by Richard S. Sutton:

All the updates done in DP algorithms are called expected updates because they are based on an expectation over all possible next states rather than on a sample next state.

So it's about all possible next states rather than on a sample next state, which won't miss some possible cases in the iteration.


text:
What is the benefit of using a neural network instead of a look-up table in this case?
Assuming one has collected the 24 pairs of the input-output datasets for a target system:

One can create a simple lookup table to describe the input-output behavior and utilize this as a controller.
One can also train a DNN model to learn the relationship.
What is the benefit of using DNN in this case?
In my view, for a DNN, one does not have to store the whole dataset for the lookup table. If one gives a new input value that is not included in the training dataset, the trained DNN would perform better, since, in the case of the lookup table, the predicted output is just an extrapolated value from the previously known output.
Any other benefits that can justify using DNN?

24 data points is too small a data set to use machine learning. Stick to a lookup table.

Why are people voting to close this as "opinion-based"? Rather than downvoting  (or actually just not upvoting: yes, people are upvoting unclear questions, not sure why) other poor questions (that we have received), people are trying to close this question, which is not (necessarily) opinion-based.

One detail is missing from this post: are you expecting inputs outside of the inputs in the training dataset? If yes, with a table you cannot directly do that, so you cannot use the table. From this sentence "If one gives a new input value that is not included in the training dataset, the trained DNN would perform better, since, in the case of the lookup table, the predicted output is just an extrapolated value from the previously known output." it seems that you're expecting values not seen during training. In that case, how would you predict for those values with a table?

The idea was to apply a fitting curve approach along with the identified input-output pairs and use the interpolation/extrapolation methods to predict those values that are in the lookup table.

@Joe Which interpolation/extrapolation methods do you have in mind? Please, edit your post to include these details directly there.

I think, that the answer depends on the actual setting and parameters of the problem.
Lookup table

One needs to store the whole lookup table in the memory - say N points.
The number of operations to extract elements depends on the way values are stored in the memory.
In order to get a single value given the input $x$, you need to perform $O(\log N)$ operations using a binary search in the sorted array.
If the data is represented as hast-table - you need only $O(1)$ operations - complexity of computing the hash-function.
Neural network

Given some dependence, you fit a neural network $\hat{f}(x)$, that approximates the function of interest (let us call it $f(x)$).
The approximation may not be exact, let us further assume, that some $\varepsilon$ is the allowed error, i.e:
$$
\Vert f(x) - \hat{f}(x)\Vert \leq \varepsilon \quad \forall x \in X
$$
For every value of $x$ inside the range of values of interest, approximation deviates at most by $\varepsilon$  from the true function.
Depending on the complexity of the problem, this quality of approximation can be achieved by the simple architecture with few hidden units, or large network with large width or depth is required to perform an accurate approximation.
In the setting, described by you, input and output are $1$-dimensional. Let MLP with the dimensions of hidden units $(h_0, h_1, h_2, \ldots h_{L})$, where $h_0 = h_{L+1} = 1$ and $L$ is the number of hidden layers, and the activation function $\sigma$ approximate the target dependence sufficiently well in the sense described above. NN is actually
$$
\hat{f}(x) = \sigma(\ldots \sigma (W_2 \sigma(W_1 x + b_1) + b_2))
$$
Here $W_i$ are the weights and $b_i$ are the biases.
Weigh matrices consist of $h_{i} h_{i+1}$  elements and biases of $h_{i+1}$ elements.
Then the network would require the following amount of memory to store parameters:
$$
\sum_{i=0}^{L} (h_{i} h_{i+1} + h_{i+1})
$$
And the number of operations to compute output $y$ per single $x$ is:

$\sum_{i=0}^{L} h_{i} h_{i+1}$ multiplications
$\sum_{i=0}^{L} h_{i} h_{i+1}$ additions
$\sum_{i=0}^{L-1} h_{i} h_{i+1}$ evalutations of activation function $\sigma$

Conclusion

So, in order to decide, whether you need DNN model or not, you need to compare the computational complexity for the Lookup table and DNN. For some architecture, DNN may be more expensive, for others cheaper. It can be the case, that there is no DNN architecture, suitable for this task.
For simple dependence and long timespan DNN can be helpful, whereas for small number of points and complicated dependence of $y$ on $x$ there is no point in trying to replace the Lookup table.
For the case, presented in the picture seems, that there is no reason to use DNN since the hash-table will extract value very fast.

The lookup can be done in O(1) in this case if we limit it to integer values.

You say "Then the network would require the following amount of memory to store parameters ..." and then you show a formula, which seems to be correct (because you're computing the # of elements in the matrix by using the # of units in the previous and next layer and adding the number of biases), but, given that the amount of memory that you need to save a NN is proportional to the # of weights and biases, why not simply use the weight matrices $W_i$ and biases $b_i$ to clarify what you need to store? I guess you did this because it would also be beneficial to show the number of operations.

I am not sure if Oliver meant that you need O(1) space or time, but, if you use a hash table, you can retrieve elements in O(1) time complexity, so you don't need to first sort the table, which would require $n \log n$ and, then, once it's sorted, as you point out, it would only require $\log n$ to search, but this would still be probably unnecessary, because given $x$ (the key for the hash table) you can retrieve $y$ in constant time (at least on average; in the worst case it would be $n$).

Thanks @nbro and OliverMason for your comments, I'll update the answer


text:
Is the optimal policy the one with the highest accumulative reward (Q-Learning vs SARSA)?
I was looking at the following diagram,

The reward obtained with SARSA is higher. However, the path that Q learning chooses is eventually the optimal one, isn't it? Why is the SARSA reward higher if it is not choosing the best path? shouldn't the best path and the safe path both be the optimal one because the reward would be higher?

It is important to note that the graph shows reward received during training. This includes rewards due to exploratory moves, which sometimes involve the agent falling off the cliff, even if it has already established that will lead to a large penalty. Q-learning does this more often than SARSA because Q learning targets learning values of the optimal greedy policy, whilst SARSA targets learning the values of the approximately optimal $\epsilon$-greedy policy. The cliff walking setup is designed to make these policies different.
The graph shows that during training, SARSA performs better at the task than Q learning. This may be an important consideration if mistakes during training have real expense (e.g. someone has to keep picking the agent robot off the floor whenever it falls off the cliff).
If you stopped training after episode 500 (assuming both agents had converged to accurate enough action value tables at that point), and ran both agents with the greedy policy based on their action values, then Q learning would score -13 per episode, and SARSA would be worse at -17 per episode. Both would perform better than during training, but Q learning would have the best trained policy.
To make SARSA and Q-learning equivalent in the long term, you would need to decay the exploration policy parameter $\epsilon$. If you did this during the training process, at a slow enough rate, ending with no exploration, then two approaches would converge to the same optimal policy and same reward per episode (of -13).

Adding to Neil's reply, though the path shown is optimal, following the so-called 'optimal path' will often result in sub-optimal returns because the action selection in this problem is stochastic due to the $\epsilon$-greedy exploration. That is, even though if we are in a block right above the cliff region and know that the best action to do is to move right, this action is selected only with a probability of 0.9. This causes the agent to deviate from the optimal path and fall into the cliff, resulting in minimized returns.
As can be seen below, this effect is captured by the SARSA algorithm as it is on-policy. However, in Q-learning, the updates are done over actions that have maximal Q-value and not over the actual action that was taken. Hence, the sub-optimality induced by the $\epsilon$-greedy action selection is not captured in the Q-value table in Q-Learning.
$\epsilon$-greedy exploration is required during training only to facilitate exploration. Unless the value of $\epsilon$ is very small, the expected reward achieved by SARSA would be higher. However, as you can imagine in Q-learning there would be a few rollouts where the stochasticity works in the agent's favor and the agent does indeed successfully move along the optimal path achieving the maximum cumulative reward. Nevertheless, the expected reward over multiple rollouts would be less than that of SARSA.

References:

Reinforcement Learning: An Introduction - Rich Sutton and Andrew Barto, 2018.

The stochastic action selection is not part of the problem definiton (or at least not from the environment specification), but is a feature of the agents that are being compared. This is an important distinction, and saying whether Q-learning or SARSA is "better" at this task depends on context outside of the optimal control problem definiton.


text:
Does "number of actions" refer to the number of actions taken or size of the action space?
In the original DDQN article (https://arxiv.org/pdf/1509.06461.pdf,) the phrase "number of actions" is used twice;
First, in the following context:

Secondly in Theorem 1.

I have a hard time understanding the way the phrase is being used or if it is being used in the same way, could anyone care to explain how it is meant to be understood?

nbro's answer is correct; I don't think I've ever seen anyone in RL literature referring to the number of actions that have already been taken as just the "number of actions" (they'd have to explicitly add something like "that have already been taken" to make that clear). Normally the latter would just be referred to as the time step $t$ instead.

The expression "number of actions" is being used in the same way in both cases. In fact, the letter $m$ is used in both cases. The number of actions (in the state $s$) is the number of possible actions that you can take in the state $s$. So, here, $m$ does not refer to the dimensionality of an action, but to the size of the action set for a state. So, if $A(s)$ is the set of actions that you can take in $s$, then $m = |A(s)|$. The paper that they refer to in the first excerpt actually uses (on page 3, in the lemma) $n$ to refer to $m$ and states that $n$ is the number of actions. Here there's a related question, which you may want to read.


text:
Is it the high probability action that is always selected by the agent in REINFORCE algorithm?
Consider the following algorithm from the textbook titled Reinforcement
Learning: An Introduction (second edition) by Richard S. Sutton and Andrew G. Bart

While playing the game for the generation of an episode trajectory, how is the action selected by the agent? I mean, how does the agent selection action $A_i$ from state $S_i$ for $0 \le i \le T-1$. I am getting this doubt as the policy is stochastic in nature and doesn't give a single action as output.
But the algorithm says to generate the episode following the stochastic policy function.
Is it always the action that has the high probability in $\pi(a|s,\theta)$?
Note: The trajectory here is $(S_0,A_0,R_1 \cdots S_{T-1},A_{T-1},R_{T})$,

you just sample an action from your current policy. the actions taken will depend on your current version of the policy but actions will be sampled with probability (proportional to, in the case of a continuous action space) given by the policy. this implies that it is more likely that actions with higher probability are more likely to be taken.

You sample according to the probability distribution $\pi(a \mid s, \theta)$, so you do not always take the action with the highest probability (otherwise there would be no exploration but just exploitation), but the most probable action should be sampled the most. However, keep in mind that the policy, $\theta$, changes, so also the probability distribution. This implementation could be useful, as it shows exactly what I've just said.
I've also seen another implementation that applied some kind of $\epsilon$-greedy policy to sample from $\pi$ (i.e. with probability $\epsilon$ you could choose the greedy action and with probability $1 - \epsilon$ any other action), but I am not sure how common or useful that could be in the basic REINFORCE algorithm. This question seems to be asking about additional exploration strategies in policy gradients, in case you're interested.


text:
What are the base rules for the symbolic integration implementation?
I want to implement a full symbolic integration. To achieve this. I've learned from Prof. Patrick Winston's AI lecture that Matlab uses

12 safe transformations, like that constant out, sums, etc.
12 heuristic transformation e.g. sin x, cos x...
and, a table that contains 26 anchors to the calculations.

So that every integration can be calculated using these rules.
In the lecture, they only listed 4 of the safe transformations, 3 of the 12 heuristic transformations, and 3 of the 26 anchors.
In order to implement the full symbolic integration, I need the rules. So; what are those? or where can I find them?

If this does not suit this site, let me know.

Hello, welcome to AI stack exchange. Please provide us with more information about the problem. Update with the necessary links and provide more content for the experts to understand in detail.

First of all, let me clarify that I think that this question is on-topic here, as symbolic integration is a problem that also humans solve, so it requires some kind of intelligence.
Second, I had also watched that interesting lecture by Winston a few months ago, so I remember that some of the rules that he mentions during the lecture are just rules that humans sometimes also use to solve integrals (e.g. integration by parts, which you should have an idea of, if you ever took a calculus course in high school), but he also mentions other problem-solving techniques used in AI, like And–Or trees.
That being said, I've never implemented any symbolic integration program, but I think that the paper A heuristic program that solves symbolic integration problems in freshman calculus (1963), by James R. Slagle, could (at least partially) answer this question, as it describes a symbolic integration program, SAINT (which stands for Symbolic Automatic INTegrator), and it also mentions a few transformations/rules that it uses, and the And-Or goal trees, which are also mentioned by Winston in that lecture, so I guess Winston may have been referring to the techniques in this or a similar paper (I would need to rewatch the lecture to confirm this). More details about SAINT are given in Slage's 1961 Ph.D. dissertation.
I suspect that, nowadays, there may be more efficient programs than SAINT to solve symbolic integration, so I will leave the details to an expert on the topic.
In addition to that, you can find on the web articles (for example, this, this, and this) that describe the common integration rules.

That is the answer to my question. I've looked at some of the websites, however, I was looking for the list. My flaw was not looking for a paper! Thanks.

Some interesting symbolic methods can also be found in the papers citing the Slagle's paper: Citing papers


text:
How many layers and neurons in a FFNN do I need to make it equivalent to a CNN?
I started to learn machine learning early, and I studied the convolutional neural network and its ability to understand images and how it helps to reduce the number of parameters that need to be tuned.
So, if I used CNN rather than a feed-forward network for the image classification problem, how many neurons and layers would I save or discard?

What do you understand about CNNs? Do you know how they work? For example, do you understand how the convolution works?

I don't have an exact answer to your question because I think your question is a bit ambiguous. It's like asking "How many defenders do you need to replace your forwards?": they do slightly different things, but a defender occasionally may be able to play as a forward. Anyway, given that I think this question arises because you don't understand how we can view a CNN as an FFNN or vice-versa, I will try to give you an idea of the relationship between the two and the number of parameters in a CNN and an FFNN.
Before proceeding, read my answer here (and maybe the other answer there too), which will give you an idea of what we could consider a neuron in a CNN, and how we can compare CNNs to FFNNs. After that, you could read this answer to understand why we need CNNs and why we use them in the context of computer vision. From now on, I will assume that you have an idea of how CNNs work, what filters are, etc., but I will remind you of a few details.
CNNs are specifically designed to deal with images, so CNNs have a more appropriate inductive bias than FFNNs for image processing.
A specific filter/kernel in a CNN can be thought of as extracting the same type of feature from different parts of the image. At a high level, this makes sense, because the same object/feature (e.g. an eye) can appear in different parts of an image. If you are familiar with image processing techniques, this interpretation of the role of kernels in CNNs shouldn't be too strange.
One of the main properties of CNNs, as explained in the linked answers, is that of weight sharing. This means that you apply the same filter (weights) to different parts of the image (this is basically what the convolution operation is doing). So, you try to extract the same "features" with the same kernel from different parts of the image.
Now, imagine if you didn't do that, and you had to learn different filters for different parts of the image: we would need weights for all these different parts, so we would need a lot more weights.
In the case of an FFNN, we can view the operation of a fully connected layer as a convolution with a kernel as big as the input image. More precisely, if you have $n$ neurons in layer $l$ and $m$ neurons in layer $l-1$, then you can view this FC layer as performing $n$ convolutions, one for each neuron in $l$, with a kernel with $m$ weights.
At this point, you should start to see the relationship between fully connected layers and convolutional layers.
So, what's the answer to your question? I don't know. It depends on what you mean by "equivalent". If by "equivalent" you mean they are the same hypothesis class, then that's a question to which I don't have an answer. However, both FC and CNNs are universal function approximators, so, in a way, they are equivalent, exactly how (which is your question), I don't know and this is probably an open research question. One thing we can say is that CNNs have a more appropriate inductive bias than FFNNs to deal with images.

I may delete this answer later as the question, in my view, is not clear enough. This would have been comment, if comments could be this long.


text:
Custom Tensorflow loss function that disincentivizes all black pixels
I'm training a Tensorflow model that receives an image and segments the image into foreground and background. That is, if the input image is w x h x 3, then the neural network outputs a w x h x 1 image of 0's and 1's, where 0 represents background and 1 represents foreground.
I've computed that about 75% of the true mask is background, so the neural network simply trains a model that outputs all 0's and gets a 75% accuracy.
To solve this, I'm thinking of implementing a custom loss function that checks if there are more than a certain percentage of 0's, and if so, to add a very large number to the loss to disincentivize the all 0's strategy.
The issue is that this loss function becomes non-differentiable.
Where should I go from here?

The background being an unbalance class is a well known problem in image segmentation. Before digging into custom losses you should take a look to existing ones that address this specific issue like the Dice Loss or Focal Loss, the latter being more tunable having a extra hyper parameter that can be optimized. You can easily find on github  tensorflow implementations of both.
For a more detailed comparison and reference to other similar losses you can also check this paper.

Can you briefly summarize Dice Loss and Focal Loss to make your answer more self-contained?


text:
Why is the cross-entropy a cost function?
The question looks foolish, but I think cross-entropy is somewhat weird as a cost function.
As a cost function for linear regression, the mean square error $ \sum_{i=1}^{n} (y_i - (ax_i+b)) ^2$ seems quite reasonable, because it literally/directly measures the error between real value and predicted value.
However, in the case of the cross-entropy, I do not understand what it is.
For multi-class classification, for example, with 3 classes, the true target is $[ 0, 0, 1 ]$, while the output of the model is $[ 0.2, 0.3, 0.5 ]$ (maybe with a softmax activation at the last layer). So, the error of it is: $C(x) = -(0*log(0.2) + 0*log(0.3) + 1*log(0.5))$.
It looks... I don't know, why is it an "error?" How can it be updated with backpropagation?
Also, what is the objective of it? Maybe optimization, so maybe minimizing error? Then what happens?

Optimizing the cross-entropy is equivalent to optimizing the log-likelihood of the parameters given the data, $\ell(\theta)$, which is what we want, i.e. find the parameters that most likely generated the data.
So, the likelihood is defined as $$\mathcal{L}(\theta) = P(y \mid x; \theta),$$
i.e. a function of the parameters $\theta$.
The log-likelihood is just the logarithm of the likelihood
$$\ell(\theta) = \log \mathcal{L}(\theta)$$
To understand why we take the logarithm, read this answer.
Now, for a fixed $\hat{\theta}$, $\mathcal{L}(\hat{\theta}) = P(y \mid x; \hat{\theta})$ is a conditional probability distribution.
For simplicity, let's assume that $\mathcal{L}(\hat{\theta}) = P(y \mid x; \hat{\theta})$ is a (conditional) Bernoulli distribution, which is defined by a single parameter $\hat{p}$, whose probability mass function (pmf) is defined as
$$\hat{p}^y (1-\hat{p})^{1-y},$$
where $y = \{0, 1\}$.
Now, in the context of neural networks, we use a neural network to output $\hat{p}$, i.e. an estimate of the parameter of the Bernoulli, which we plug into the cross-entropy loss function. So, if $f_\theta: \mathcal{X} \rightarrow [0, 1]$ is your neural network, then $f_{\hat{\theta}}(x) = \hat{p}$, given the input-output pair $(x, y)$.
So, the Bernoulli pmf for a given pair $(x, y) \in \mathcal{D}$ can be written as
\begin{align}
P(y \mid x; \hat{\theta})
&= \hat{p}^y (1-\hat{p})^{1-y} \\
&= f_{\hat{\theta}}(x)^y (1-f_{\hat{\theta}}(x))^{1-y}
\end{align}
So, without fixing the parameters, we can write the likelihood (which is not a probability distribution wrt $\theta$) as follows
\begin{align}
\mathcal{L}(\theta)
&= f_{\theta}(x)^y (1-f_{\theta}(x))^{1-y}  \\
\iff \ell(\theta) &= \log \left( f_{\theta}(x)^y (1-f_{\theta}(x))^{1-y}\right)  \\
&= \log f_{\theta}(x)^y + \log \left(1-f_{\theta}(x)\right)^{1-y} \\
&= y \log f_{\theta}(x) + (1-y)\log \left(1-f_{\theta}(x)\right)
\end{align}
which is our well-known binary cross-entropy for a single pair $(x, y)$ (note that only one of the addends above is not zero). For multiple pairs, you can apply the same reasoning, and you will see why we also use the log, i.e. it will allow you to simplify a few expressions in the derivation (specifically, multiplications will turn into sums, which is nice numerically).
So, if we maximize $\mathcal{L}$, with respect to $\theta$ (e.g. the parameters of your neural network), then we will find an estimate $\hat{\theta}$, that produces the parameter $\hat{p}$, such that this parameter can be used to construct/define the Bernoulli distribution that most likely (hence the name likelihood) produced our given dataset $\mathcal{D}$.
This reasoning also applies to the case where $P$ is categorical or even Gaussian distribution. So, actually, when you're minimizing the MSE, you're actually also optimizing the log-likelihood. It just turns out that the expression is different because Gaussians are not Bernoullis.
I will not talk about the back-propagation, but it's just the chain rule. If the log-likelihood is differentiable, then you can use it in the context of back-propagation and GD. You can ask another question, if you're interested, but note that, in the general case, computing the partial derivatives can be a pain in the neck, so your question may be too broad. Find a very simple case.
To conclude, don't dwell on the word error. Think in terms of probabilities, probability distributions, likelihoods, and why we can optimize likelihoods. Read my answer multiple times, if you didn't understand something.

Overall, I think I understand your point. However, It seems little complicated that "when you're minimizing the MSE, you're actually also optimizing the log-likelihood." Can you be more specific, please?

@JAEMTO I think I can show you mathematically why this is the case, if you ask another separate question. Maybe in your new question you can refer to this answer, so that people have some context.


text:
What is a "mask" in the context o RNN-based encoders?
While reading source code related to RNN encoders, I've come across the term mask as input to the encoder. What exactly is it?

Masks in Recurrent Neural Networks are used to transform variable-length inputs to one general length. Therefore we use padding and masking together.
Padding: Usually we create a vector for every sentence in the dataset initialized with 0s and the length of the longest sentence in the dataset. Then we fill the mask with 1s for every position the sentence has words in.
Masking: Now we need to inform the network that some values in the vector are actually padding and should not be used since they have no information.


text:
How to derive the dual function step by step in relative entropy policy search (REPS)?
TL:DR, (Why) is one of the terms in the expectation not derived properly?
Relative entropy policy search or REPS is used to optimize a policy in an MDP. The update step is limited in the policy space (?) by the KL-divergence metric to stabilize the update. Based on the KL-divergence constraints, and some constraints about the definition of a policy, we can derive its Lagrangian, and its dual optimization problem afterwards. And lastly, we find the appropriate update step (delta) by solving the dual problem.
However, I think we can also use it to find multiple optimal solutions in an optimization problem, just like (CMA)-evolutionary strategy algorithm.
So, based on the original paper and a section of REPS in this paper, I'm trying to derive the dual problem.
Suppose that we're finding set of solutions represented as a parametrized distribution $\pi(x|\theta)$ that maximizes $H(x)$. Suppose that the last parameters we came up with is denoted as $\hat{\theta}$, we find the optimal parameters $\theta$ by:

max $\int_x H(x)\pi(x|\theta) dx$

s.t.  $\int_x \pi(x|\theta) dx = 1$

$D_\text{KL}\left(\pi(.|\theta) || \pi(.|\hat{\theta})\right) \leq \epsilon $

with $D_\text{KL}\left(\pi(.|\theta) || \pi(.|\hat{\theta})\right) = \int_x \pi(x|\theta)\log\frac{\pi(x|\theta)}{\pi(x|\hat{\theta})}$

Based on the equations above, we can write the Lagrangian as follows:

$L(\theta, \lambda, \eta) = \int_x H(x)\pi(x|\theta) dx +
\lambda(1-\int_x \pi(x|\theta) dx) +
\eta(\epsilon-\int_x \pi(x|\theta)\log\frac{\pi(x|\theta)}{\pi(x|\hat{\theta})})$

Now, we can see that the term $\lambda(1-\int_x \pi(x|\theta) dx)$ is $0$, right? But here, it was not cancelled out. So, following the flow based on the two papers, We can simplify the Lagrangian by treating the integral wrt to $x$ as an expectation.

$L(\theta, \lambda, \eta) = \lambda + \eta\epsilon + \underset{\pi(x|\theta)}{\mathbb{E}}\left[H(x) -\lambda -\eta \log\frac{\pi(x|\theta)}{\pi(x|\hat{\theta})} \right]$

We will find the optimal $\pi(x|\theta)$ by solving $\frac{\partial L}{\partial \pi(x|\theta)} = 0$. Now, I got confused starting from this step.
If I mindlessly copy/follow the notations from here, the derivative of $L$ wrt the policy parametrized by $\theta$ is:

$\frac{\partial L}{\partial \pi(x|\theta)} = H(x) - \lambda - \eta \log\frac{\pi(x|\theta)}{\pi(x|\hat{\theta}}$

Where's the integral wrt $x$ goes? Is it because they are all multiplied by $\pi(x|\theta)$, so that it can cancel the integral/the expectation? If so, then why the derivative of the KL term in the expectation derived into this $\eta \log\frac{\pi(x|\theta)}{\pi(x|\hat{\theta})}$? Isn't the $\pi(x|\theta)$ in the log will derive something more?

What you did is incorrect and that's not what authors got either (if you're refering to the equation above equation (5) in paper "Non-parametric Policy Search with Limited Information Loss")
What you need here is the derivative of a functional. Functional has a general form
\begin{equation}
J(f) = \int_x L(x, f(x), f'(x), \ldots, f^{(n)}(x)) dx
\end{equation}
Derivative with respect to $f$ is
\begin{equation}
\frac{\partial J}{\partial f} =  \frac{\partial L}{\partial f} - \frac{d}{dx}\frac{\partial L}{\partial f'} + \ldots
\end{equation}
Since your functional (expectation) is only dependant on $f$ then it simplifies to $\frac{\partial J}{\partial f} =  \frac{\partial L}{\partial f}$
So what you have for example for the first term is
\begin{equation}
\frac{\partial \int_x H(x) \pi(x|\theta) dx}{\partial \pi(x|\theta)} = \frac{\partial H(x) \pi(x|\theta)}{\partial \pi(x|\theta)} = H(x)
\end{equation}
The more interesting functional is the one with term $\pi(x|\theta)\log(\frac{\pi(x|\theta)}{\pi(x|\hat \theta)})$.
Integral with respect to $\pi(x|\theta)$ is
\begin{equation}
\log(\frac{\pi(x|\theta)}{\pi(x|\hat \theta)}) + 1
\end{equation}
So in the end you get
\begin{equation}
\frac{\partial L}{\partial \pi(x|\theta)} = H(x) - \lambda - \eta \log\frac{\pi(x|\theta)}{\pi(x|\hat{\theta})} - \eta
\end{equation}

thanks for pointing that out, I will try to derive it until I get the dual. I think my confusion arises from not knowing/understanding the functional derivative.


text:
Which computer scientists have received the Turing Award specifically for their contributions to Artificial Intelligence?
Many people have heard of Hinton, Bengio, and LeCun in recent years, given the popularity of deep learning and neural networks, and their contributions to this subfield of Artificial Intelligence. For their contributions, they have conjointly received the Turing Award in 2019 (although, in my view, a few other people could also have received this award for the same reasons).
In addition to them, which computer scientists have received the Turing Award specifically for their contributions to Artificial Intelligence?
For each of them, please, describe the specific reason why they were awarded and/or provide the links to the official site that announces this or the Turing lecture.
Why am I asking this question? Alan Turing is considered one of the fathers, if not the father, of Artificial Intelligence and Computer Science. In particular, in addition to the development of Turing machines, which are widely studied in Theoretical Computer Science and Theory of Computation, he's also published the famous paper Computing Machinery and Intelligence in 1950, where he proposed what was later called the Turing test, and asked one of the most fundamental questions in AI: "Can machines think?". The Turing Award is given to people that make significant contributions to Computer Science (so also AI), so I think we should remember all these people that have contributed to AI.

The descriptions below are copied from Wikipedia or the ACM site.

Name
Year
Description
Link

Marvin Minsky
1969
For his central role in creating, shaping, promoting, and advancing the field of artificial intelligence
[1]

John McCarthy
1971
McCarthy's lecture "The Present State of Research on Artificial Intelligence" is a topic that covers the area in which he has achieved considerable recognition for his work
[2]

Allen Newell
1975
In joint scientific efforts extending over twenty years, initially in collaboration with J. C. Shaw at the RAND Corporation, and subsequently with numerous faculty and student colleagues at Carnegie Mellon University, they have made basic contributions to artificial intelligence, the psychology of human cognition, and list processing
[3]

Herbert A. Simon
Idem
Idem
[3]

Edward Feigenbaum
1994
For pioneering the design and construction of large scale artificial intelligence systems, demonstrating the practical importance and potential commercial impact of artificial intelligence technology
[4]

Raj Reddy
Idem
Idem
[4]

Judea Pearl
2011
For fundamental contributions to artificial intelligence through the development of a calculus for probabilistic and causal reasoning.
[5]