text:
What is the meaning of log p(x) in VAE math and why is it constant
I was reading the article on medium, where the author cites this equation for Variational Inference:
\begin{align*}
\text{KL}(q(z|x^{(i)})||p(z|x^{(i)})) &= \int_z q(z|x^{(i)})\text{log}\frac{q(z|x^{(i)})}{p(z|x^{(i)})} dz \\
&= \mathbb{E}_{||}[\text{log}(q(z|x^{(i)}))] -  \mathbb{E}_{||}[\text{log}(p(z|x^{(i)}))]\\
&= \mathbb{E}_{||}[\text{log}(q(z|x^{(i)}))] - \mathbb{E}_{||}[\text{log}(p(x^{(i)}, z))] + \mathbb{E}_q[\text{log}(p(x^{(i)}))]\\
&= \mathbb{E}_{||}[\text{log}(q(z|x^{(i)}))] - \mathbb{E}_{||}[\text{log}(p(x^{(i)}, z))] + \text{log}(p(x^{(i)}))\\
&= -\text{ELBO} + \text{log}(p(x^{(i)}))\\
\end{align*}
I understand all of the math behind this equation, but I was wondering what is the underlying intuition behind each of the terms in this equation (KL divergence, ELBO, and logp(x))?
The author claims that $\text{log} p(x)$ is a constant in this equation and I'm having a hard time understanding why. Is $p(x)$ considered to be the theoretical data generating distribution which created our $x$'s and not the model that we are training?

Let me try to give you a less mathematical, more intuitive explanation.
You assume a latent space $\mathcal{Z}$ and you approximate the true distribution $p(x)$ as:
$$ p_\theta(x) = \sum_\mathcal{Z} p_\theta(x|z) p_Z(z) = \mathbb{E}_{z \sim p_Z} p_\theta(x|z) $$
Here you use a neural net with parameters $\theta$ to model $p(x|z)$.
However, there is a problem that arises in this setting. In order to optimize our model we actually want to sample $z$ that would be a good match for the given data point $x$, but there is actually very little chance that that would be the case. If there really exists an underlying latent space to your data, then the best distribution to sample $z$ from is $p(z|x)$. So what you do now is you try to approximate this with a second neural network $q_\phi(x)$.
You want to maximize the log-probability of the training data by optimizing $\theta$:
\begin{aligned}
\max_\theta \log p_\theta(x)
&= \log \mathbb{E}_{z \sim q_\phi(x)} \bigg[ p_\theta(x|z) \frac{p_Z(z)}{q_\phi(z|x)} \bigg] \\
& \geq \mathbb{E}_{z \sim q_\phi(x)} \log \bigg[ p_\theta(x|z) \frac{p_Z(z)}{q_\phi(z|x)} \bigg] \\
& = \mathbb{E}_{z \sim q_\phi(x)} \bigg[ \log p_\theta(x) - KL(q_\phi(x) \; || \;p_Z) \bigg]
\end{aligned}
And you also want to minimize the KL divergence between $q_\phi(x)$ and $p(z|x)$ by optimizing $\phi$:
\begin{aligned}
\min_\phi KL(q_\phi(z|x) \; || \; p_\theta(z|x) )
&= \mathbb{E}_{z \sim q_\phi(x)} \log \frac{q_\phi(z|x)}{p_\theta(z|x)} \\
&= \mathbb{E}_{z \sim q_\phi(x|z)} \Big[ q_\phi(z|x) - p_Z(z) - \log p_\phi(x|z) \Big] + \log p_\theta(x)
\end{aligned}
Note that the last term in the objective is constant with respect to $\phi$, so in the end we are left with the same equation but this time we optimize over $\phi$.
Finally, the objective is:
$$
\max_{\theta, \phi} \mathbb{E}_{z \sim q_\phi(x)} \bigg[ \log p_\theta(x) - KL(q_\phi(x) \; || \;p_Z) \bigg]
$$

Variational methods are designed for situations allowing us to avoid the intractable integral such as $p(x)$ parameterized by the amortized parameter $\theta$ along with $p(z|x)$ by transforming the Bayesian inference problem into an optimization problem wrt $\theta$ and additional $\phi$ parameterizing the needed variational $q(z|x)$. And since in your reference the marginal evidence $p(x)$ defined in the latent variable model evaluated at the $i$-th example of the training set (note your reference uses $p(x^{(i)})$ before notation simplification) integrates out $p_{\theta}(x|z)$ by all possible values of the latent variable $z$ to induce the said example, it's a (possibly very small) constant wrt the optimized parameters $\theta$ and $\phi$ and thus irrelevant of $q_{\phi}(z|x)$. But note for your confusion the marginal likelihood $p(x)$ itself as evidence is essentially a GMM as explained in VAE's wikipedia reference.
To further avoid the intractable $p(x)$ in the ELBO, your reference arrives at the same convenient form of ELBO as mentioned in wikipedia:

$${L_{\theta ,\phi }(x):=\mathbb {E} _{z\sim q_{\phi }(\cdot |x)}\left[\ln {\frac {p_{\theta }(x,z)}{q_{\phi }({z|x})}}\right]=\ln p_{\theta }(x)-D_{KL}(q_{\phi }({\cdot |x})\parallel p_{\theta }({\cdot |x}))}$$
The form given is not very convenient for maximization, but the following, equivalent form, is: $${L_{\theta ,\phi }(x)=\mathbb {E} _{z\sim q_{\phi }(\cdot |x)}\left[\ln p_{\theta }(x|z)\right]-D_{KL}(q_{\phi }({\cdot |x})\parallel p_{\theta }(\cdot ))}$$ where ${\ln p_{\theta }(x|z)}$ is implemented as ${-{\frac {1}{2}}\|x-D_{\theta }(z)\|_{2}^{2}}$, since that is, up to an additive constant, what ${x\sim {\mathcal {N}}(D_{\theta }(z),I)}$ yields. That is, we model the distribution of $x$ conditional on $z$ to be a Gaussian distribution centered on ${D_{\theta }(z)}$.

Thank you for your answer. If our goal in generative modeling is to maximize p(x), then why does VAE math all center around trying to approximate p(z|x), Is this because with q(z|x), p(z), and p(x|z) all of which we have after variation inference, we can calculate/approximate p(x). Also as a side note, I am confused by the use of theta. When we say p_theta(x), does theta refer to our neural network parameters or parameters to a theoretical unknown distribution that we don't have the analytical form for.

As clearly stated in your own ref, generative modeling goal is mostly about the first 2 problems, while the 3rd problem of prior evidence p(x) modeled as a GMM distribution or evaluated at an example as a constant is much less important (irrelevant to ELBO as explained in my answer). Theta is the non-variational decoder network parameters for the posterior multivariate Gaussian distribution p(x|z) which certainly has analytic form but unknown parameters such as mean vector and covariant matrix, the theta parameterized decoder’s outputs are nothing but the said Gassian’s unknown parameters.

so from what I am understanding the in the equation log p(x)=ELBO -KL(q(z|x)||p(z|x)), log p(x) represents the true data generating distribution and does not change because it is not dependent on theta or any parameters that exist within our model. Does this intuition sound right?

Check the line above "The term logp(x) is a constant" in your ref, '-' should be "+". Since the logp(x) is constant, then minimizing the KL-Divergence is equivalent o maximizing the ELBO which is the lower bound of log-evidence p(x) as KL-D is always greater than 0. Since x is continuous for image like data, as explained in my answer, here p(x) mean its pdf evaluated at the ith training data which is an intractable integral but we know it must be a constant w.r.t. the learning parameters theta and phi. So your intuition is correct except it's not true data generating distribution meant here.

@KiranManicka I recently went through this myself. Is the above clear? The short answer is that if p(z) and p(x|z) are known, then p(x) is well-defined. p(z) is chosen by us, and p(x|z) is fixed for each step of training, and so there is a well-defined p(x) at that step.


text:
The end-to-end Training Process for Knowledge Distillation
I'm a bit confused on the complete training process for Knowledge Distillation. I was reading the Geoffrey Hinton "Distilling the Knowledge in a Neural Network" 2015 paper and some random blog plots to figure out how to actually train it. However, I don't see any end-to-end training example for that paper. So, here is what I understand and want to confirm the training process. Let's say we will train one big binary classification teacher network and distill the knowledge to student network.

Train the Large Teacher Network
Distill the Knowledge

Use the temperature to soften the softmax (where T is temperature and it's used to reduce confidence such as [2.0, 0.5] with T=1 is [0.82, 0.18] and T=2 is [0.68, 0.32].)
$$\text{softmax}(x_i) = \frac{e^{\frac{x_i}{T}}}{\sum_{j=1}^{N} e^{\frac{x_j}{T}}}$$
Then, prepare the subset of training dataset with new labels which are soft targets instead of hard targets [0, 1, 1, ...].

Soft targets = [[0.68, 0.32], [0.44, 0.56], [0.39, 0.61], ...]

That new subset of dataset with soft targets is called transfer set.

Loss Function

To make it simple, let's say I'll use the CrossEntropyLoss with class probabilities between my outputs (with same temperate as transfer set) and soft targets.

That's it. Then, I can start the distillation training with transfer set.

Is this process/flow correct? Thank you in advance!

i would say so...

source: Stack Exchange

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

sort: votes


text:
How to correctly train policies in multi-agent RL?
I am diving into Multi-Agent Reinforcement Learning and after reading some literature, I would like to clarify some approaches because I am not quite sure. Now for the following two cases it is clear that:

independent learning: one distinct policy per agent with distinct rewards per agent of the same reward function.
$$
\pi_{\text{ag1}}: \text{obs}_{\text{ag1}}
\rightarrow \text{a}_{\text{ag1}}
\rightarrow \text{r}_{\text{ag1}}
$$
$$
\pi_{\text{ag2}}: \text{obs}_{\text{ag2}}
\rightarrow \text{a}_{\text{ag2}}
\rightarrow \text{r}_{\text{ag2}}
$$

joint learning: one (global) policy making decisions for all agents simultaneously with one global reward
$$
\pi_{\text{ag}}: [\text{obs}_{\text{ag1}},\text{obs}_{\text{ag2}},\text{obs}_{\text{ag3}}] \rightarrow  [\text{a}_{\text{ag1}},\text{a}_{\text{ag2}},\text{a}_{\text{ag3}}]  \rightarrow  \text{r}_{\text{glob}}=\text{r}_{\text{ag1}} + \text{r}_{\text{ag2}} + \text{r}_{\text{ag3}}
$$

But using the CTDE aproach (centralized critic decentralized execution), I am not quite sure how it should be correctly applied. There are the following options for policy and reward that can be implemented and combined:

distinct policy: each agent has its own policy: $\pi_{\text{ag_i}}$
shared policy: each agent uses the same policy: $\pi_{\text{ag}}$
distinct reward values to each agent (by same reward function): $\text{a}_{\text{ag_i}}\rightarrow\text{r}_{\text{ag_i}}$
shared/global reward given to all agents: $\text{a}_{\text{ag_i}}\rightarrow\text{r}_{\text{glob}}=\text{sum}(\text{r}_{\text{ag_i}})$

I further know that it is possible to assign a partial fraction $\alpha$ to the distinct reward in 3). i.e. $\text{r}_{\text{ag_i}} + \alpha\, \text{sum}(\text{r}_{\text{ag_j\i}})$ in order to enhance cooperation.
But what is the "correct way" of learning a coordinated behaviour in MARL with heterogeneous agents, especially when applying CTDE?
My goal is to apply MARL in a game, where the heterogeneous agents have to attack and destroy opponents. Currently I am using CTDE, where agents of the same type are using the same shared policy and they get distinct reward values (of the same reward function). I also tried a shared reward, but did not notice a significant change.  I update my policies by PPO, so I don't use an explicit MARL algorithm.
I just want to make sure I am going the correct way. It's not the issue with implementation, but rather a question about the whole concept.

the reward structure does not influence the category... independent learning means "everybody is trained assuming other agents are part of the env", thus the independent... joint is just a "big puppetier" controlling everybody (goes back to single agent)... CTDE is half way, centralizing the reward signal, but decentralizing the policy (every agent has his own local observation).... consider that CTDE usually works best in continuous case scenario exploiting the DDPG structure, in discrete case they don't improve that much

Hi. You can use mathjax on this site. I'd recommend you edit your post to do it.

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


text:
What's the best model to use for CNN(deep learning) regression task for small image dataset?
What are the best Deep learning models(with how many layers) to use in a regression task for a custom dataset containing around 100 images of only one object per image which is more or less centralized? The object is measured manually with a weight scale and the output of the model is the estimation of the density of an object expressed in g/mm.

In general Convolutional Neural Networks work well with images, be it a regression or a classification problem. In your case the number of images is very small, so heavy data augmentation should be used. And the network itself has to be fairly simple, to avoid overfitting. But without access to the data it is hard to recommend any actual architecture (number of layers, kernels, activations, ...).
Estimating the density is an interesting problem, it is a property of the material (assuming it isn't hollow) and is independent of the size of the object. If your objects are quite uniform in size the network might have problem with smaller and bigger objects than what you have in the training data.
If your images are high resolution, I'd consider splitting them into smaller crops (optionally with varying sizes, then resizing them into a common resolution) to get more training data.
I would also try altering the model to predict the weight and thickness as separate outputs, this way you can see which property is more difficult to predict and you can focus on that. If you feel fancy your model can have three outputs (weight, thickness, density) and optimize a weighted loss on all of them at once.
If you can publish the data I'd be interested to implement a reference solution and see how accurate it would be. By default I would not share the source code with you, just the results and give you guidance.
Edit:
I sorted the images by the known density, and noticed that it correlates quite well with the object's apparent size. This is unexpected (if you weren't measuring the mass), it sounds implausible that the largest objects would be the densest. The opposite could be explained if they started at a similar size and weight, and some were compressed down into a more dense form.
Or is it that several smaller object will back denser than fewer larger ones? I had thought of this only in the context of a single object. edit 2: this is irrelevant, in the data largest objects are densest.
The change in hue is due to normalization, and I didn't convert the images to grayscale.
Looks like the grid's first image's (_DSC3479.JPG) data entry is incorrect, it may have an extra zero after the decimal comma.

Anyway, fitting a linear regression to this data will give you a good starting point. It would give a prediction of 0.099 (median of the six nearest neighbours), which is off by just 5% from the presumed correct value of 0.104.
It seems that CNNs will not help you much here, due to low amount of data and after all small size of the objects. There isn't much detail in the texture, but shading seems to give some hint of the 3D structure. If possible, I would take 10 photos of each object in a random orientation. Naturally you need to measure their density just once :) This would be much better than rotating the images after the fact. And try to place the camera closer, so that the objects would be 250 - 400 pixels in width.
The dirty background shouldn't be an issue, actually it would be a good exercise to train a pre-processing network which would do the job for you.

To be honest I did not load and preprocess this dataset yet since my coding knowledge is poor(I am an amateur student). I only made high-resolution images that are all same sized and have the same distance from objects: https://drive.google.com/file/d/1ZhvdIjY7SPrpkP6JgVfxqtre1Xr200ZQ/view?usp=sharing
I also forgot to mention that I should calculate some interesting properties such as the area/volume of an object(in this case fertilizer granule). But the output is the estimation of the density of an object as said in the post.
However, I really appreciate your help and potential guidance.

Thanks for the link, images are indeed high resolution but the objects are rather small (100 - 200 px wide). Could you also upload a file which has known densities of these objects? It could be for example a CSV, with columns "filename" and "density".

https://docs.google.com/spreadsheets/d/1kcmNRK3EcWkmYErK1rKAwJsNKnfaDOe8/edit?usp=sharing&ouid=101648245388903582171&rtpof=true&sd=true
Here is the link for the CSV file for manually measured weights. The excel automatically remove some 0s on the end so two and one-digit numbers are actually three-digit numbers (0.06 = 0.060 or 0.1 = 0.100). Column A is the filename and Column B is a weight, which is easy to notice.  Btw, do you know some good tutorial to load and process images?

There are several image libraries for python, such as Scipy, Python Image Library and OpenCV. Any convolutional neural network tutorial should have examples as well, although they might load a pre-existing dataset such as MNIST. Oh and Kaggle is full of examples, for all the popular deep learning libraries.

Thanks for the help and suggestions, but I think I did not explain it well and led you to misunderstand. The weights in CSV file are mass estimations expressed in grams measured manually on a scale. I think I need to measure area/volume using object localization(deep learning?) through CNNs and in the end calculate density with the simple formula g/mm. Anyway, I am thinking about making more photos tomorrow from a closer distance. Did you think of angles when you said taking pictures in a random orientation? I am very low on time and that is also a big setback.

Also, the data entry on the image DSC3479 is wrong. The 0 is mistakenly added after comma. Now I am so confused now I think it's impossible to be made.  Could you please send me a portion of the code that made crops of these pictures and merged it into this plot. That would help me a lot.

If you want to train a network to predict the density, you need to provide it such training data. But ah if the CSV had masses, then this is actually quite solvable by a simple neural network even without extra data. (With more photos I thought of removing and re-placing the object in camera's view.) If this is a school project I think you should write the code yourself, and if you are stuck then ask a new question here. My code for cropping doesn't involve any AI, it just checks the row and column with the lowest mean pixel brightness.

I did some research last night. I used LabelImage to add a bit more data to the object. I think of adding more photos and also using Convex Hull to estimate the area/volume of an object after that or do you think there are easier ways to compute it? Maybe I do not need CNNs at all for this task.
Input > Object localization > Area estimation using Convex Hull > Some pooling layer?> Simple formula computation in dense output layer. Do you think this looks like good idea of a project? And what do you think which activation layer should I use and should I use different angles for images of objec

I tried a simple regression with Keras and it was suprisingly difficult to get working. I might ask a separate issue on this topic some day. Start with something simple and get it working first, and I suggest you to use Scipy rather than neural networks for simple "y = ax + b" regression.


text:
Which generalization of standard deviation to use for multidimensional input normalization
For machine learning tasks, it's common to normalize input data by subtracting the mean $\mu$ and dividing by the standard deviation $\sigma$ of the dataset:
$$\hat{x_i} = \frac{x_i - \mu}{\sigma}$$
—where the standard deviation is computed independently for each feature.
Suppose instead we compute another multidimensional generalization of the standard deviation—the matrix square root $\Sigma$ of the covariance matrix:
$$\Sigma\Sigma^T = \frac{1}{n}\sum_i^n (x_i - \mu)(x_i - \mu)^T$$
(Since covariance matrix $\Sigma\Sigma^T$ is positive semidefinite, it has a unique positive semidefinite square root $\Sigma$.)
And then normalize the samples by
$$\hat{x_i} = \Sigma^{-1}(x_i - \mu)$$
In a sense this is a "better" normalization—it will not only map the values to nice ranges, but also decorrelate different features.
However, I have never seen this done. Is there some non-obvious drawback to this approach I'm not seeing, aside from being more computationally intensive? Is there any research on what effect this would have on model training?

This idea is sometimes applied in computer vision, under the name of Whitening Transform, or ZCA sphering transform. The name whitening comes from signal processing, since removing correlation from a signal makes it look like white noise.
In images this transformation is applied to remove contrast and enhance edges, as you can see in the example below (taken from this paper, not open access unfortunately, but the authors made a github repo)

I'm not aware either about application of covariance matrix in domains other than computer vision for preprocessing, but I can image few points that make this approach unpractical:

Feature selection: it's easier to select features that are already uncorrelated (checking trough chi squared test or similar) rather than turning them into uncorrelated ones. And this approach has the advantage of reducing training features and therefore speed up training and reduce memory requirements.
Impracticality, for thousands of training features computing the covariance matrix become basically impossible, not just inefficient. This problem becomes relevant even with less features if we want to train with batches.
Generalization It seems to me your also suggesting the possibility to compute a unique covariance matrix from a set of training data. This approach would force us apply the same covariance matrix on every out of training data on which we want to apply our model, meaning that after applying that covariance matrix our data will probably not be truly covariance free. This is a problem common to standardization as well (the mean and variance computed on the training data always differ from the real mean and std of the population, but it's easy to compute mean and std of millions of training instances, so usually those estimation are quite robust).


text:
Image segmentation when given masking information is incomplete
In my problem, there are about 5,000 training images and there are about 50~100 objects of identical type (or class) on average, per image. And for each training images, there is a partial mask information that denotes the polygon vertices of objects, but the problem is there are only 3 ~ 5 objects per image with mask/annotation information.
So in summary there is 1 class, 5,000 * 50 ~ 5,000 * 100 instances of the class, and 5,000 * 3 ~ 5,000 * 5 instances with masking information.
So not a single training data image has a full masking information, and yet all the training data images have partial masking information. My job is to make instance segmentation model.
I did some search on semi-supervised segmentation, and to my understanding it seems like the papers are tackling problems where some training images have all the objects annotated while the other training images have 0 objects with annotation. That isn't exactly my situation. How should I approach this problem? Any tips are appreciated.

If you cannot share the actual data, you could help us by writing a python code which generates such data with similar features, the percentage of given correct labels etc. Actually you could even train your own network with such data, and use it as a basis for labeling the real dataset.

Welcome to AI.  If it were me then I would use the annotations to train a classifier to answer "would you find one of these under an annotated mask?" and then use it more broadly for semi-supervised outside of the mask.

If you are trying to make instance segmentation model, if you are trying to get full masking objects in your image then you are going into wrong direction.
Generally, when you train the model with partial mask your  predictions will also be partial masked.
Can you please list your input image sample and output expected sample so that I can help you with which type of instance segmentation you need to train.Also try to list which instance segmentation models are in your mind to train..

The images are grayscale and they look very similar in human eyes. I will upload a sample once I am allowed to do so. Just say white is object and dark is background and you won't be too wrong. But there are noises and simply getting pixels within certain range of luminance yields about 70% accurate segmentation. I tried unsupervised learning ignoring the given masks, and then fine tuning with the masks. It didn't go well. Currently trying Unet with preprocessed images(smaller pictures of area around given polygon masks)

If i understand correctly, you are trying to solve semantic segmentation task, rather than instance segmentation. Yes, Unet is good starting path to test your results. More more precise results you can try  Detectron2 model which have semantic segmentation model and you try train on different backbones to try your experiments on

It is instance segmentation task because I need to know how many instances are in the image as well as the segmentation mask. but I decided I just do semantic segmentation first and do the counting job with object detection algorithm or something. Only chose Unet because my images look similar to microscopy images and UNet is a popular solution in that field(they are not microscopy but looks kind of similar) Would have been easier if there was a popular method for instance segmentation for grayscale though.

If you have up-to 100 objects in a single image, their size must be fairly small percentage-wise. let's say their diameter is 50 pixels and the whole image is 1024 x 1024. Are the objects always non-overlapping, thus somewhat far apart? If so, you could label the known objects with a mask value of 1, their nearby pixels are set to a mask value of 0, and everything else is set to 0.5. Let's call this "Mask A".
Now you construct a normal CNN which maps a 1024 x 1024 x 1 image to a mask of the same size. But the network takes a second input as well: "Mask B". This is calculated as Mask B = (Mask A != 0.5), meaning that indicates to which pixels we know the correct answer (either 0 or 1). The network's output is modified so that it outputs the normal values where Mask B is true, and 0.5 to pixels where Mask B is false. The binary cross-entropy is calculated against the Mask A which has values 0, 0.5 and 1.
Note that regardless of the model's parameters, it will always output a value of 0.5 to those pixels which are also 0.5 at Mask A. Thus they won't contribute to the loss or its derivatives.
I did a simple network in Keras and trained it with simulated data:
inputs = [layers.Input((res,res,1)) for _ in range(2)]

x = inputs[0]

for dim in [8, 16, 8, 4, 1]:
    x = BN()(layers.Conv2D(dim, 7, activation='elu', padding='same')(x))

x = layers.Conv2D(1, 11, padding='same', activation='tanh')(x)
x = (x * inputs[1] + 1) * 0.5

model = keras.Model(inputs, x)

Note that tanh was used instead of sigmoid, since it made the "hard-code unknown pixels as 0.5" a bit easier. The generated dataset consists of grayscale images (shown left), partially labeled data (yellow = known circle, dark blue = known non-circle and blue-green for unlabeled pixels), the network's output and the ground-truth. The network is able to find all the circles quite well, but there are some false positives and the border seems to be labeled all ones.

But this approach cannot be used if the objects could overlap, and we cannot generate a sufficiently large "neighbourhood region" around it with known labels of "no object".

Unfortunately they overlap like crazy but good answer nonetheless. I will give a more detailed view on dataset and the task once I am done with this task. So far I got decent but not superb result and I would probably end as is, but I'd love to learn more even after the task due date is over


text:
A neural network with peculiar architecture?
I ended up working with a neural network $N(\cdot)$ characterized by the following structure:$$N(x)=V[\text{ReLU}(Ax+b)+Cx+d],$$
with input $x \in \mathbb{R}^n$ and parameters $V\in\mathbb{R}^{1\times m}$, $A$, $C \in \mathbb{R}^{m \times n}$ and $b$, $d \in \mathbb{R}^m$. Does anyone know what sort of "standard" architecture it represents?

Are there any constraints on the parameters? Otherwise, if $A$ and $b$ can vary freely, then $A-C$ and $b-d$ look like they don't do much, because neither $A$ nor $b$ appear anywhere else, which would allow $A-C$ and $b-d$ to be arbitrary with no loss of generalisation if you simply dropped the subtractions.

@NeilSlater You're right - just edited, accordingly.


text:
How to encode actions for training a Wordle agent?
I'm trying to train an AI using reinforcement learning to play the game Wordle.
The way the game works is that there is a secret five letter code word that you need to guess, and every time you guess a word (it has to be an actual word it can't just be any five letters) the game tells you what letters of your guess are correct and what letters of your guess are in the code word but not in the correct position. If you guess the word in six guesses or less, you win.
I want every step the AI to choose a string from a list of valid guesses. Afterwards I will reward it for discovering letters for the first time and discovering their position for the first time. It will be penalized for losing and rewarded for winning based on how early it won.
The problem is that I can't just number each word and have it choose a number (I think?) because the actual content of the string it chooses matter.
How should I tackle this issue?
One thing that might be worth mentioning is that while I'm aware this could be solved algorithmically without the use of reinforcement learning, I want to try this approach anyway. This is less about the finale product and more of an excuse to get familiar with machine learning.

re: "This is my first machine learning project", you can most likely write a strong Wordle bot without using ML. The ML component is likely to be complex due to the action space, as you've noticed. If learning ML/RL is the goal, you will be a lot better off picking a smaller challenge.

For people not familiar with this game, you need to explain how the "content of the string matters". Moreover, there's not description of how you're using RL here.

@nbro thanks for the feedback. I added those to the post.

I have heard of, but not played Wordle. This fact is important to possible strategies when designing an ML component: Could you explain whether Wordle only accepts valid 5-letter words as input, or if it will accept and score non-words like "ABCDE"?

What do you mean by "The problem is that I can't just number each word and have it choose a number (I think?) because the actual content of the string it chooses matter" ?

A quite effective way to solve Wordle is to maintain an active list of all five-letter words that meet criteria so far, choose one of them completely at random, then update the list of possible words based on new knowledge from the response.
A slightly smarter way would be to pick words from the subset of remaining ones that should maximise information gathered from the response on average. I believe I read a headline recently that "crane" is a good starting English word for that reason.
The trouble for you here is that those approaches do not involve ML in any form. Relatively simple logic and analysis are already pretty good at playing Wordle automatically.
However, to stick with the question as asked, your problem is how to get a machine learning algorithm to choose between maybe 10,000 options.
You have a couple of choices:

Brute force. Number the options, have the algorithm choose directly. If you do this, I recommend that you also filter out logically impossible words, as that makes the problem far easier. The 10,000 options may seem large at first, but actually this should be within reach of a personal/hobby setup. It will work mainly because it is possible to simulate the results of games very fast. So generating the training data within RL will be fast, the agent can get to see millions of games in a reasonable time frame, training with each target word thousands of times on average.

Actions represent additional constraints on word choice. For a simple example, you could have the agent decide whether the first unknown letter it wants to try is a vowel or consonant = just two actions. You can use that to further restrict word choice from the remaining words. This influences an otherwise random word selector, and the agent should learn situations in which to pick words with certain traits.

Actions describe a "word vector", and the selector picks the closest valid word to that vector, breaking ties randomly. In order to do this, you need to generate some short vector of each word in the dictionary. For a simple example* you might choose [part_of_speech, popularity] to qualify each word, scoring part_of_speech as 1 for noun, -1 for verb and 0 for everything else and popularity as 1 for common word, -1 for rare word, and 0 for moderately frequent. Then your action output would be a choice from the 9 combinations possible in this vector.

None of these approaches are simple, so not great if you are just starting in AI/ML, and I would recommend you tackle a simpler toy problem or two using RL before trying to write your Wordle training routine. Going straight to Wordle without solving smaller problems first is likely to cause a lot of incorrect decisions on your part that you won't spot and will frustrate you.

* I have given a very simple example, but this could logically lead to learned word embeddings, which are an important topic in natural language processing. These are typically quite large real-valued vectors though (maybe 64 or 128 elements) which would be an even larger space to learn about than the fixed list of words. So full word embeddings like word2vec and Glove are not really suitable for the Wordle puzzle.

Thanks for the suggestions! I'm not sure what you mean by "logically impossible words" though.

@YuvalAmir: After you choose your first word "hello" you may know that the word contains an "e"  (but not second position) and the "l" in fourth position is correct. That also implies "h" and "o" are not in the target word. So you can immediately remove all words from consideration that contain "h" or "o", that have "e" in second position, that have no "e" at all (because there is at least one), and that don't have "l" in fourth position. So you can keep "cable" and "eagle" in the list, but not "helps" because the latter is inconsistent with the new feedback.

oh I get it. Now that I think about it, could the idea of the "word vector" be used by having the ai describe what letters it wants and you find the closest fitting word?

@YuvalAmir Yes it could, although overall that is an even larger space than 10,000 words, it may be simpler to code and be reasonably effective.

"pick words from the subset of remaining ones": the optimal strategy has not this constraint, just to recover as much information as possible (that is, test a word that splits the set of valid words in equal sized sets).

@pasabaporaqui Depends which ones you count. I looked this up, and found this - https://wordfinderx.com/5-letter-words which varies considerably on what it counts, so I went for 10,000 as a "typical" number for choices. The actual list used by Wordle is only ~2500 words - see e.g. https://gist.github.com/cfreshman/a03ef2cba789d8cf00c08f767e0fad7b#file-wordle-answers-alphabetical-txt-L2315

"word2vec" maps distance between words taken into account their meanings (inferred from large corpus). Wordle distance between words is purely about word spell. Use word2vec or similar in this case will be a bad choice.

@pasabaporaqui Yes, I also explain why they are also not a great choice due to large space. However, they are an interesting way to characterise words in ML, as an aside to the idea of using word characteristic choice as an action space.

Finally, all the explanations about "actions" is also unrelated with the main strategy: use as next word a word that, in average, will discard the greatest amount of words still valid.

@pasabaporaqui I am not sure what you are getting at? OP wants an answer about RL, not about best strategy for Wordle. I explain the difference at start of the answer. RL works with terminology of actions, and if OP wants to not have a large action space, alternatives are suggested that should work, and might be trainable. The alternatives presented in the answer are not expected to create an optimal Wordle solver, but a trainable one that uses ML


text:
Sensible integer embedding/encoding for distinguishing elements of a set?
I am trying to train a model that takes in a set of feature vectors (which comes with an ID to uniquely identify elements of the set) and outputs a target for each element in the set (in a permutation-equivariant manner). It seems like a self-attention based model would work well here (because there's reason to believe that the target depends on the features of other elements).
However, I need help coming up with a sensible encoding for the integer ID that comes along with the feature vector. For context, I have at 3561 unique integers IDs (0 being the "out of vocabulary" ID (such as for elements not seen during training) and 1 to 3560 for the elements seen during training). Intuitively, it seems like a bad idea to just provide the integer itself concatenated to the feature vector.
The goal is to concatenate the integer embedding with the feature vector and train self-attention on this set.
The constraints for the encoding/embedding of integer IDs are:

No elements are similar: There are no physical/temporal relationships here, just a bag of elements. So, something like positional encoding as used in the Transformer paper might not be a good choice because there's no reason to believe that element #45 and element #46 have any special relationship compared to element #46 and #100.

They should be deterministic and more importantly, not trained. Trainable embeddings would only result in the embeddings changing during training which is undesirable.

Low dimensional: Definitely not more than, say, 50 dimensions (so one-hot encodings are not acceptable here).

My best idea right now is to use spherical codes. For example, unit vectors in say 24 dimensions that are distributed as far from each other as possible. Since the kissing number in 24 dimensions is 196,560 - 3560 unit-vectors can be easily placed in a way such that the pair-wise cosine similarity for any two vectors is quite low. The out-of-vocabulary embedding vector would be the zero-vector (at the origin).
Would this be sensible? I have heard that positional encoding had some desirable properties with respect to linear transformations. Would the kind of integer embedding I am imagining based on equidistant unit vectors cause problems as the self-attention module is largely a linear operation.
I am probably overthinking this and there likely exist sensible ways of embedding/encoding integer IDs that I simply haven't heard of. For all I know, just providing the binary representation would work just as well as any other embedding.

As you have asserted that the id is not meaningful of itself, it probably doesn't matter how you encode it.
I would recommend the following, in order:

Don't encode the id. It is not clear that you need it when you already have the feature vector. At the very least you should train the model initially without the id to get a baseline and find out out if using the id has any benefit.

Use a secure hash function, such as SHA1, which will "randomly" assign each id a byte array (e.g. effectively 16 bytes or 128 bits of pseudo-randomness using the data as an initial value or seed). You can then take the first N bits of each hash as a short vector of 1s and 0s. If N is small you may get collisions amongst the ids, but this may not be a practical issue, if only one or two ids are special enough to affect the target beyond the feature vector. About 30 bits should be enough to encode your ids with a low chance of collision. The advantage of this approach is you can get SHA1 as off-the-shelf function and the rest is easy.

The spherical mapping function or similar that you can think of. Don't set yourself up with lots of work though, unless you expect to be able to re-use the encoding in a more meaningful way.

Sorry, I probably didn't explain correctly. It is probably true that the target for element #46 heavily depends on the features of element #64. I just meant that the numerical value itself doesn't matter (which in retrospect is a silly thing to mention).

But I like the idea of using a hashing function! That's quite clever, thanks!


text:
Why is $l$-step lookahead better in RL?
The following is from the book "Reinforcement learning and optimal control", by D. P. Bertsekas.
Chapter 2, page 52:
"The motivation for $l$-step lookahead is that for increasing values of $l$,
one may require a less accurate approximation $\tilde{J}_{k+l}$ to obtain good
performance. Otherwise expressed, for the same quality of cost function approximation,
better performance maybe obtained as $l$ becomes larger. This makes intuitive sense,
since in this case, the cost of more stages is treated exactly with optimization."
My question:
Why is it that for increasing values of $l$,
one may require a less accurate approximation $\tilde{J}_{k+l}$ to obtain good
performance?

Let's first start with the intuitive explanation. If you just use q-learning (or any other temporal difference method like SARSA) you usually just look ahead one step. The other extreme is a monte-carlo method where you don't rely on estimates of the state-value function at all (your policy might depend on an estimate, but your updates don't). Monte-carlo methods can be viewed as an $\infty$-lookahead. So $l$-step lookaheads are somewhere in between (they take $l$ rewards in a monte carlo fashion and then only bootstrap from there), so they reduce the dependency on the estimates by quite some margin. Therefore you can have an estimate of the state-value function with higher variance for $l$-step lookahead as you could with only $1$-step lookaheads.
Now let's have a look at a more quantitative explanation. You are looking for the error reduction property (see derivation in Sutton-Barto notation) of $l$-step lookaheads, which can generally be given by
\begin{equation}
\min\limits_x \Bigl\lvert \mathbb{E}_{\pi}[T^{l-1}\tilde{J}_{t}| X_{t}=x] - J_{\pi}\Bigr\rvert \le \gamma^{l} \min\limits_s \Bigl\lvert \tilde{J}_{t} - J_{\pi}\Bigr\rvert
\end{equation}
This shows that the $l$-step lookahead will always have lower errors than a simple $1$ step solution. Hence one can have worse estimations to achieve the same quality of results with multi-step learning.


text:
It is not clear why sequential improvement is violated in the constructed rollout algorithm
Below is an example (p.89) from "RL and Optimal Control" book by D.Bertsekas on the construction of a a case study where the rollout algorithm is worse than the base heuristic on which the rollout algorithm is constructed.
It is not clear why sequential improvement is violated. First of all,
the first sentence is not clear to me: is it the rollout algorithm
or the base heuristic that accidentally produces an optimal control sequence?
It is not clear to me why sequential improvement is violated in the provided example. I will be happy for clear explanation.

The first sentence simply asserts the base heuristic accidentally produces an optimal control sequence, otherwise the rollout algo starting from initial state $x_0$  would not be strictly inferior to the one produced by the base heuristic starting from the same $x_0$ as the author stated later.
This unwanted result of rolling out a strict inferior target policy under this section's deterministic problems assumption is due to violation of the base heuristic's sequential improvement property, which is a weaker property than sequential consistency shared by a deterministic policy, for example. Thus the base heuristic $H$ here must not be a deterministic policy such as the random-restart hill climbing search algo applied for the traveling salesman problem.

Your explanation is less clearer than the explanation in the book.


text:
Unclear points for polynomial basis for function approximation
I have 3 questions for the following box from Sutton-Barto's RL book (page 211) on polynomial basis:
Q1- Why is each $x_i$ an "order-n" polynomial? I think this is wrong: in my opinion, order of $x_i$ can be in the range [1, n*k]
Q2- This sentence is not clear: "These
features make up the order-n polynomial basis for dimension k, which contains
$(n + 1)^k$ different features".  What does it mean "for dimension k"? Why specifically dimension k?
Q3- What is the range for index "i"?

Q1- Why is each $x_i$ an "order-n" polynomial? I think this is wrong: in my opinion, order of $x_i$ can be in the range [1, n*k]

The text does not claim that $x_i$ is an "order-n" polynomial - the order is instead associated with the whole polynomial basis set, and $x_i$ is a feature of that basis. The authors are using order-n as the higher level descriptor of a set of terms which have degree up to $n$.
The individual terms are polynomials of the original state features of degree from $0$ to $n$ in each feature separately.

Q2- This sentence is not clear: "These
features make up the order-n polynomial basis for dimension k, which contains
$(n + 1)^k$ different features".  What does it mean "for dimension k"? Why specifically dimension k?

The original state vector is an $\mathbb{R}^k$ vector. So $k$ refers to the original dimensionality of the state description.

Q3- What is the range for index "i"?

It is $[1, (n + 1)^k]$ if you are intending to have full coverage of all possible combinations of state features in degree up to $n$ in each feature, as described in the text.
It is not the only way to create a set of derived features using polynomials, and you might just as naturally limit the total degree of all original features within a single ploynomial to $n$ as allow each one to vary from $0$ to $n$ in all combinations.
For instance, the book gives an example with $k = 2, n = 2$ of $x(s) = (1, s_1, s_2, s_1s_2, s_1^2, s_2^2, s_1s_2^2, s_1^2s_2, s_1^2s_2^2)$, but you could instead consider  $x(s) = (1, s_1, s_2, s_1s_2, s_1^2, s_2^2)$. Which to use will depend on experimentation and results, no different from any other feature engineering.

@ Neil Slater,  "each order-n polynomial-basis feature $x_i$" means $x_i$ is a feature and its order is $n$. I asked a friend with math phd degree and he told me as well that the wording here is horrible.

@DSPinfinity DIfferent disciplines may use terms like degree and order in subtly different ways. I would agree that the sentence is written ambiguously. My answer provides what I read as the intended meaning, or at least a pragmatic reading given the rest of the description and how you might expand a state feature vector using polynomial combinations of the original state vector.


text:
What is $D_i$ in "Common Principal Components Analysis"?
The following is from Ethem Alpaydin, "Introduction to Machine Learning", Fourth Edition, MIT Press, 2020, page 129.

Here, $C$ is the orthogonal matrix found from the sample covariance of all matrices (S).
But I did not understand what $D_i$ is and why we should have the above relation.
Moreover, why does it allow pooling data?

$D_{i}$ merely refers to the diagonal matrix that captures the variance for each principal component specific to class $i$.
We can pool data because the $C$ matrix is the same for every class, meaning principal components are derived from the collective data of all classes.


text:
What does stationary state distribution mean in reinforcement learning?
What does stationary state
distribution mean in reinforcement learning?
The context it is used is as below.

Could you give some context where you saw or heard this please? There are a couple of things it could mean, which depends whether we are talking about this as a trait of an environment, or a trait of a policy (the latter typically in a continuing/non-episodic environment). There may be other contexts that I don't know as well.

I added the context it was used. I updated the question.

In general a stationary distribution is a distribution over something (e.g. actions, states, etc) that doesn't change over time, for example.
Example of non-stationary distributions can be easily found in multi-agent RL, when modelling the policy of some other agent: in this case the opponent's policy can be non-stationary since it can adapt itself to the other agents, and so on. In such case, that distribution will change with time, or, better said, with novel gathered experience from the environment and other agents.
In you case the distribution $d_\pi(s)$ is stationary over states: giving a fixed policy $\pi$ (that doesn't change), the distribution of states that the policy visits does not change too, e.g. with time. In simpler words, $\pi$ always visits the same states at each rollout. As the next line in the text says "the stationary distribution varies with the learned policy", means that if you update $\pi$ then $d_\pi$ will change consequently assigning a diverse probability mass over $s$.
I think that $d_\pi$ is also related to the transition dynamics of the environment: maybe the text is implicitly assuming that neither the underlying environment will change with time, so that fixing both the env and policy the visited/reached states and their probability are the same across timesteps/transitions.

Worth mention ergodicity assumption and linking https://ai.stackexchange.com/questions/27196/what-is-ergodicity-in-a-markov-decision-process-mdp - which is what the quote from the question is about


text:
What is the difference between "base heuristic" and a "rollout algorithm" based on this base heuristic?
In the following pages (p.84-85) of RL and Optimal Control book by  D.Bertsekas,
he is talking about  base heuristic" and a "rollout algorithm" based on this base heuristic.
However, I am very confused because based on Figure 2.4.2, it seems
that rollout algorithm and base heuristics are the same things.

As illustrated under your above flowchart figure 2.4.2, base heuristic/policy is just a simple heuristic that is used to help make a quick decision about what action to take in a given state $x_k$ via generating a heuristic Q-factor for every state-control pair ($x_k, u_k$) while satisfying the control system equations shown on your first screenshot. Then the on-line rollout algorithm selects the control with minimal Q-factor which is a specific heuristic search algorithm using the base heuristic (policy) to further simulate the behavior of the control system over a finite time horizon under the (suboptimal) rollout policy.


text:
Why can we have misclassifications for a perfect model in logistic regression?
I am reading  the book: MACHINE LEARNING- A First Course for Engineers and Scientists, by Lindholm et.al.
Chapter 3, page 50.
Link: http://smlbook.org/book/sml-book-draft-latest.pdf
Consider the logistic regression for classification.
$
\hat{y}(\mathbf{x})=
\begin{cases}
    &1   &  g(\mathbf{x})>r \\\\
   &-1   &  g(\mathbf{x})\le r &
\end{cases}
$
The book says "It can be shown that if $g(\mathbf{x})=p(y=1|\mathbf{x})$, that is, the model provides
a correct description of the real-world class probabilities, then the choice $ = 0.5$ will
give the smallest possible number of misclassifications on average."
I am confused here because if the model provides
a correct description of the real-world class probabilities, why do we have misclassifications?

Could you please give more context for the quote - e.g. chapter name, section name and pages in a specific edition -  because this is probably due to what else is assumed part of the problem (e.g. the quote refers to classifying new data, or allows for g(x) for different examples but same vector to be differen - I think it is simply the latter, that $x_i = x_j$ but $g(x_i) \neq g(x_j)$)

I updated the question to give the book details.

Are there two reasons? Non separability of classes and some error due to boundary estimation from finite data?

I am thinking about a very simple example to illustrate both. Classify numbers into positive and negative from uniform distributions in (-1,0) and (0,1) -separable with estimated boundary not exactly zero but close- and overlapping distributions, for example (-3/4,1/4) and (-1/4, 3/4).

I think book means something different.

I understand your question is "why is the smallest possible number of misclassifications larger than zero".

Since $g$ is your logistic regression model, over data samples $x$, the output of $g(x)$ is a scalar value between $0$ and $1$ that is usually interpreted as a probability value.

We have that $g(x)=\sigma(W x + b)$ essentially, where $W,b$ are the parameters that you learn and $\sigma$ is the sigmoid squashing function (the one that keeps everything in $[0, 1]$).
Furthermore, $g(x)=p(y=1\mid x)$ meaning that $g(x)$ represents the probability that the sample $x$ belongs to the positive or, as the book says in page 49, most probable class - as a side note, this is something that you can change and usually define before learning.

Now, let's assume that the two classes $y=1$ (the positive or most probable) and $y=0$ (the negative or less probable) have real-world probabilities of: $p(y=1\mid x) = 0.7$ and $p(y=0\mid x) = 1 - p(y=1\mid x) = 0.3$. Let's also be realistic, in the sense that the two class distributions overlap: this implies that you have some misclassification errors due to the fact that is not possible to separate the two classes perfectly. Note: there could be many reasons for this, such as mis-labelling, and similarity of data samples between the two classes.
At this point, we have $g(x)=p(y=1\mid x)$ that is the probability of $x$ to belong to the positive class ($y=1$), implying that there is a $70\%$ chance that $x$ has label $1$. In order to perform a binary classification, you need to get rid of the probabilities by thresholding them, such as: $\hat{y}(x) = g(x) > t$.

If $g(x)>t$ you assign label $1$ (so $\hat{y}(x)=1$), otherwise you assign label $0$.
In case the model $g$ predicts the real-world class probabilities correctly (i.e., $p(y=1)=0.7$ and $p(y=0)=0.3$) - as assumed by the book - you have that if the threshold is chosen to be $t=0.5$ (or $r=0.5$ as called in the book), happens that $g(x)>0.5$ minimizes the number of misclassifications, equivalently to maximize the accuracy of predictions.
In other words, for a threshold of $0.5$ you get maximum accuracy. But in real classification problems you care also about other measures, such as the AUC of ROC/PR curves, FPR and TPR, F1-score, etc. Basically, you can target a metric and tune the threshold $t$ to get the rate of error that best suits you application.

If still you have doubts about your question:

if the model provides a correct description of the real-world class probabilities, why do we have misclassifications?

Consider a classifier $g'(x)=0.7$ that always outputs a probability of $0.7$ regardless the data point, $x$. Even if the true class probability is $0.7$, this model is still erroneous $30\%$ of the times when classifying all the $x'$ such that $y(x') = 0$.

Note your book specifically claims 'the model provides a correct description of the real-world class probabilities', which exactly means the multi-explanatory variables logistic function $g(\mathbf{x})$ trained in your logistic binary classifier $\hat{y}(\mathbf{x})$, as a special type of S-shaped sigmoid function transforming the linear combination of input features into a probability between 0 and 1 could be possibly correct in the real world. And if this is true, then intuitively $r=0.5$ gives the best overall accuracy and the smallest possible number of misclassifications on average.
In summary it's the logistic model $g(\mathbf{x})$ could possibly provide a correct description of the real-world class probabilities, but even this is the case, the resulting binary classifier $\hat{y}(\mathbf{x})$ would still possibly have misclassification since its accuracy may not be 100% either on your training samples or unseen test samples.


text:
Why is laplace distribution less sensitive to outliers than normal distribution?
Why is laplace distribution less sensitive to outliers than normal distribution?. The following is the content.
(See page 103 of http://smlbook.org/book/sml-book-draft-latest.pdf)
"Also, in the regression case there is a duality between certain common loss functions and the maximum likelihood approach, as we have previously observed. For instance, in a regression model with additive noise, the squared error
loss is equivalent to the negative log-likelihood if we assume a Gaussian noise distribution, $\epsilon \sim N(0, \sigma_{\epsilon}^2)$. Similarly, we noted above that the absolute error loss
corresponds to an implicit assumption of Laplace distributed noise,
$\epsilon \sim \mathcal{L}(0, B_{\epsilon})$.
This statistical perspective is one way to understand the fact that the absolute error loss is more robust (less sensitive to outliers) than the squared error loss, since the Laplace distribution has thicker tails compared to the Gaussian distribution. The Laplace distribution therefore encodes sporadic large noise values (that is,
outliers) as more probable, compared to the Gaussian distribution"

Can you provide more context? Where did you find this claim?

I updated the question with the content.

Your reference doesn't claim Laplace distribution is less sensitive to outliers than normal distribution, the intended claim is the absolute error loss is more robust (less sensitive to outliers) than the squared error loss used in many regression models.
According to your quoted well-known duality between certain common loss functions and the maximum likelihood approach for regression problems in Bayesian statistics, and in particular the squared error loss is equivalent to the negative log-likelihood loss $J(\mathbf{\theta})$ (expressed on the same page) if we assume a same Gaussian distributed additive noise, and a detailed equivalence derivation is shown here. Similarly the absolute error loss corresponds to a Laplace distributed noise.
Further per probability theory Laplace distribution generally has thicker tails compared to the Gaussian distribution, therefore Laplace distribution encodes sporadic larger noise values (as outliers) as more probable and thus possibly all likelihood factors $p(.)$ (between $0$ and $1$) in the above $J(\mathbf{\theta})$ containing the same outlier data in the same training set would be larger in the Laplace noise case , given the parametric statistical model to be regressed. And due to negative log-likelihood loss formula, the positive $J(\mathbf{\theta})$ would actually be smaller after applying the 'negative log' functions. Therefore its dual which is the absolute error loss is also smaller in the sense that it's more robust (less sensitive to outliers) than the squared error loss.


text:
Unclear points in scaled Euclidean distance
The following is from a machine learning book.

I did not understand the explanation given in the figure caption. Could some expert make it clear? Why is the stretching class-dependent for the center case?

You provided very little context here without explicit reference, though it looks like the topic here is instance based machine learning such as KNN method using potentially beneficial scaled Euclidean distance. You need to first know why the left graph case of feature-dependent scaling is effective compared to its original unstretched classification learning in terms of their decision boundaries.
Consider a hypothetical dataset with two classes (spam and non-spam) having two features (length and ratio of number of blacklisted keywords). Obviously the original features have wildly different scales thus KNN method would provide an implicit highly nonlinear irregular decision boundary by the meshgrid in below plot around the possibly overlapping region of the feature space (code is provided at the end).
But if you scale the feature of ratio of blacklisted keywords to be of similar range of the other email length feature, the below implicit decision boundary provided by the same KNN classifier becomes much more regular and thus effective in many respects such as variance reduction.
This is exactly the case in your left graph where stretching the feature $x_2$ makes the classification boundary much more regular and statistically effective to predict any new data.
But if you're in the middle class-dependent scaling case, any such scaling elongation or compression obviously aren't effective compared to their original unscaled graph since any such scaling doesn't make the bottom-left possibly overlapping corner of the two classes any more clearly separable and regular. Similar case goes for the right case of correlated features since the usual linear correlation between $x_1$ and $x_2$ won't get affected at all by any scaling.
import numpy as np
import matplotlib.pyplot as plt
from sklearn.neighbors import KNeighborsClassifier
from matplotlib.colors import ListedColormap

np.random.seed(42)

spam_length = np.random.uniform(150, 500, 50)
spam_blacklisted_keyword = np.random.uniform(0.2, 0.8, 50)
spams = np.column_stack((spam_length, spam_blacklisted_keyword))

nonspam_length = np.random.uniform(30, 300, 50)
nonspam_blacklisted_keyword = np.random.uniform(0, 0.3, 50)
nonspams = np.column_stack((nonspam_length, nonspam_blacklisted_keyword))

# spam_length = np.random.uniform(150, 500, 50)
# spam_blacklisted_keyword = np.random.uniform(0.2*50, 0.8*50, 50)
# spams = np.column_stack((spam_length, spam_blacklisted_keyword))

# nonspam_length = np.random.uniform(30, 300, 50)
# nonspam_blacklisted_keyword = np.random.uniform(0*50, 0.3*50, 50)
# nonspams = np.column_stack((nonspam_length, nonspam_blacklisted_keyword))

X = np.vstack((spams, nonspams))
y = np.array([0] * 50 + [1] * 50)

knn = KNeighborsClassifier(n_neighbors=5)
knn.fit(X, y)

h = .2  # Step size in the mesh
x_min, x_max = X[:, 0].min() - 1, X[:, 0].max() + 1
y_min, y_max = X[:, 1].min() - 1, X[:, 1].max() + 1
xx, yy = np.meshgrid(np.arange(x_min, x_max, h), np.arange(y_min, y_max, h))
Z = knn.predict(np.c_[xx.ravel(), yy.ravel()])

# Plotting the decision boundary
Z = Z.reshape(xx.shape)
plt.contourf(xx, yy, Z, alpha=0.4)
plt.scatter(spams[:, 0], spams[:, 1], c='red', label='spams')
plt.scatter(nonspams[:, 0], nonspams[:, 1], c='green', label='nonspams')
plt.xlabel('Length')
plt.ylabel('# of blacklisted keywords')
plt.ylim(0, 1)
plt.legend()
plt.title('KNN Decision Boundary')
plt.show()


text:
What is the logic in including/not including subscript $\pi$ in in "E" for value functions?
Here are two relations for value functions:
Eq.1: $v_{\pi}(s)=E_{\pi}[q_{\pi}(S_t, A_t)|S_t=s]$
Eq.1: $q_{\pi}(s,a)=E[R_{t+1}+\gamma v_{\pi}(S_{t+1})|S_t=s, A_t=a]$
Question: Why is there subscript $\pi$ in the first expectation equation, but not in the second one? What is the logic in including/not including subscript $\pi$ in "E"?

Where did you find these equations?

Your second equation is defined on page 78 and in the same page there's a step on the lower part of derivations contains the answer to your confusion.

$q_{\pi}(s, {\pi'}(s)) \\= E[R_{t+1} + \gamma v_{\pi}(S_{t+1})|S_t=s,A_t={\pi'}(s)] \\= E_{\pi'}[R_{t+1}+ \gamma v_{\pi}(S_{t+1})|S_t=s]$

You see the key is when your expectation is conditioned on a specific action at time $t$, the only remaining random variable as the capitalized reward $R_{t+1}$ is solely determined by the stochastic environment not any agent's policy. If it's not conditioned on a specific action at time $t$, then according to the backup diagram in your another post the only remaining random variable as the capitalized reward $R_{t+1}$ is not solely determined by the stochastic environment but also determined by which specific action $a$ is taken at time $t$ probabilistically based on the distribution of the random action $A_t$ controlled by the policy.

The subscript just indicates over which variable the expectation is taken. For consistency it can be included everywhere. Sometimes, when the variable over which the expectation is taken is obvious, it is not precised. For example $E[x]$. In that case it's clear, however you can imagine, that the variable x is dependent on some latent feature and the expectation is not over the variable x, but its latent dependence, e.g. $E_z[x(z)] = E_z[x]$.
Regarding your case, I would assume, that in first case its emphasised that the expectation is taken over all the actions following the policy $\pi$. In the second case, you can conclude from the context, what is the variable of interest is.
You can find very similar question here. Hope it helps!

I think reasoning is different.

Following the answers, from the question I linked It may be that the  q is not dependent on the policy, it will appear strange to me however, since you put a subscript at q in your question. Can you share the reference to the equation, that is creating the confusion?

I think it is used to mean "conditioning" on $\pi$, but I want to understand this logic fully. These equations are from the solutions manual to an exercise, hence I cannot share.

You can say, that "conditioning" on $\pi$ in first case can mean that your actions are distributed with density $\pi$, so it will appear in expectation calculation.
However, it looks to me, that in the second expectation, the action is fixed by conditional expectation $E[\cdot | S_t = s, A_t = a]$. So the variable of interest for expectation is something else. You probably can conclude from context which variable it is.


text:
Can mini-batches for stochastic gradient be balanced but not representative of the training data?
When we construct mini-batches for stochastic gradient, it is important to ensure that the different mini-batches are balanced (for example, in case of classification they contain the same ratio for each class) and representative for the whole dataset.
Can mini-batches be balanced but not representative? Any example?

The problem is, what mathematical definition do you give to "balanced" and "representative"?
Balanced usually means that classes are uniformly distributed, but then you are screwing up your prior, but that's nothing that an importance sampling coefficient might not fix
However, the representative part is ill defined. By itself, you want enough data such that:
$$
\nabla L^*(\theta)^T \nabla L(\theta) \ge 0
$$
$L$ being the stochastic loss, and $L^*$ the actual "full" loss... in other words, you want that your stochastic gradient is pointing "pretty much" in the same direction as the full gradient.
Now, how do we know that this is true? we don't... however, the more "stochastic" it is, the more likely is this to happen (thus increasing batch sizes usually fixes this)
So, can a a batch of data be balanced and be not representative? Yes, you can pretty easily build an example where this is true

Since it seems that the words were not enough, here you are an example
Consider the following setting (dotted line is the decision boundary)

If you sample the two RED outliers, the gradient from that minibatch will still drive the decision boundary towards the optimal one (hope we agree on this point), thus
$$
\nabla L^\text{all}(\theta)^T \nabla L^\text{minibatch RED}(\theta) \ge 0
$$
However, now consider the following decision boundary

Clearly, the loss induced by this decision boundary, is much lower by the previous one... however, now if you sample the RED minibatch, the gradient will say "nope, totally disagree, you should completely flip the prediction since all O are predicted as X and all X are predicted as O", in other words:
$$
\nabla L^\text{all}(\theta)^T \nabla L^\text{minibatch RED}(\theta) \le 0
$$
Note: in all cases the ratio between O/X in the whole dataset and in the minibatch is preserved (1:1 ratio), thus the minibatch is indeed balanced, yet it's not representative

very hard to make a connection to the asked question.

@DSPinfinity what's not clear?

@DSPinfinity btw, your definition of balanced is not correct

Could you please correct it? I will be happy if you can give a simple definition for representativeness.

@DSPinfinity I already gave the usual definition for being balanced and for being representative in the answer, being uniformly distributed and to have correlated gradients it's pretty clear to me

@DSPinfinity From a statistical perspective, a sample (mini-batch) of a population (dataset) is representative if its statistics are pretty much the same of the population. Let's say you have a dataset $X$ with 1 feature, with mean $\mu_X=1$. Now you're mini-batches should have approximately the same mean value, therefore not something very different like $2$ or $-1$, for example. Anyway, I think that the important part is that the samples are representative if they follow the same distribution of the dataset. So balancing classes makes the "class" distribution uniform, without modes (peaks).

@LucaAnzalone, perfect answer. Could you please give an example like this where the data is balanced (for a classification problem) but not representative?

@LucaAnzalone No,  consider logistic regression, take 2 linearly separable classes, and add one "outlier" per class in the opposite cluster. Now, if your minibatch is composed by only these 2 outlier points, your batch is still balanced, but it's not representative, as the direction of the update will be almost opposite to the true gradient (and (1) your minibatch can be seen as a single sample MC estimate of your parameters (2) these two points might definitely come from the exact distribution of your data).

@LucaAnzalone To conclude, it makes little sense to define "representativeness" as closeness in the distribution statistics space, because then you should define a measure of closeness, and some threshold    over which is considered "not representative", where instead the definition with the gradient has no "subjectivity" innit, and as said earlier, you can most likely have a non representative sample, and it gets more likely the closer you get to your local minima

@LucaAnzalone added some illustrations on the answer, hope it helps

@DSPinfinity added some illustrations on the answer, hope it helps

Though you've already accepted an answer, from your comments it seems you're still somewhat unclear and need an example. Take your example of (binary) classification, usually balanced training data means you have more or less equal number of samples for each class label. Any due to the intrinsic random nature of each mini-batch during gradient descent (MBGD), it's very likely some mini-batches data will not be representative in the sense that it may become imbalanced. But so long as MBGD converges, it's generally converge faster and more computationally efficient leveraging parallelism than full batch GD, the impact of possibly many imbalanced mini-batches is typically minimized as the model updates its parameters based on the entire dataset and over multiple epochs.
Here's a simple binary logistic classification example for a balanced dataset with two class labels of equal number of samples (50 for each) and two features, code is provided at then end. Total dataset has 100 samples, mini-batch size is set to 5, and epoch is tuned to 1000. As you can see from the output many mini-batches are not representative for the whole dataset (many have 0%, 20%, 60%, 80% class_1 data), but the final result is still good and close to the full batch result as you can easily verify.

output result:
i=0, minibatch_size=5 class_1%=0.6
i=5, minibatch_size=5 class_1%=0.4
i=10, minibatch_size=5 class_1%=0.4
i=15, minibatch_size=5 class_1%=0.8
i=20, minibatch_size=5 class_1%=1.0
i=25, minibatch_size=5 class_1%=0.6
i=30, minibatch_size=5 class_1%=0.0
i=35, minibatch_size=5 class_1%=0.4
i=40, minibatch_size=5 class_1%=0.8
i=45, minibatch_size=5 class_1%=0.2
i=50, minibatch_size=5 class_1%=0.4
i=55, minibatch_size=5 class_1%=0.6
i=60, minibatch_size=5 class_1%=0.6
i=65, minibatch_size=5 class_1%=0.8
i=70, minibatch_size=5 class_1%=0.8
i=75, minibatch_size=5 class_1%=0.6
i=80, minibatch_size=5 class_1%=0.4
i=85, minibatch_size=5 class_1%=0.2
i=90, minibatch_size=5 class_1%=0.2
i=95, minibatch_size=5 class_1%=0.2
i=0, minibatch_size=5 class_1%=0.6
i=5, minibatch_size=5 class_1%=0.2
i=10, minibatch_size=5 class_1%=0.2
i=15, minibatch_size=5 class_1%=0.8
i=20, minibatch_size=5 class_1%=0.4
...
i=95, minibatch_size=5 class_1%=0.2
----
import numpy as np
import matplotlib.pyplot as plt

np.random.seed(42)

# Class 0: Generate points in a cluster around (-1, -1)
num_class_0 = 50
X_class_0 = np.random.randn(num_class_0, 2) - 1 * np.ones((num_class_0, 2))
y_class_0 = np.zeros((num_class_0,))

# Class 1: Generate points in a cluster around (1, 1)
num_class_1 = 50
X_class_1 = np.random.randn(num_class_1, 2) + 1 * np.ones((num_class_1, 2))
y_class_1 = np.ones((num_class_1,))

X = np.concatenate((X_class_0, X_class_1), axis=0)
X_b = np.c_[np.ones((X.shape[0], 1)), X]
y = np.concatenate((y_class_0, y_class_1))

# Sigmoid function for logistic regression
def sigmoid(z):
    return 1 / (1 + np.exp(-z))

# Initialize parameters for logistic regression (bias and weights)
theta = np.random.randn(X_b.shape[1], 1)

# Define hyperparameters
learning_rate = 0.2
batch_size = 5
n_iterations = 1000
m = len(X)
# Mini-batch gradient descent
for iteration in range(n_iterations):
    shuffled_indices = np.random.permutation(m)
    X_shuffled = X_b[shuffled_indices]
    y_shuffled = y[shuffled_indices].reshape(-1, 1)

    for i in range(0, m, batch_size):
        xi = X_shuffled[i:i+batch_size]
        yi = y_shuffled[i:i+batch_size]
        print(f'i={i}, minibatch_size={np.size(yi)} class_1%={np.sum(yi)/np.size(yi)}')
        gradients = 1/batch_size * xi.T.dot(sigmoid(xi.dot(theta)) - yi)
        theta -= learning_rate * gradients

# Function to predict classes
def predict(X):
    return (sigmoid(X.dot(theta)) >= 0.5).astype(int)

# Plotting the decision boundary
x_min, x_max = X[:, 0].min() - 1, X[:, 0].max() + 1
y_min, y_max = X[:, 1].min() - 1, X[:, 1].max() + 1
xx, yy = np.meshgrid(np.linspace(x_min, x_max, 1000), np.linspace(y_min, y_max, 1000))
X_new = np.c_[np.ones((len(xx.ravel()), 1)), xx.ravel(), yy.ravel()]
Z = predict(X_new).reshape(xx.shape)
print(f'theta={theta}')

plt.contourf(xx, yy, Z, alpha=0.3)
plt.scatter(X_class_0[:, 0], X_class_0[:, 1], label='Class 0')
plt.scatter(X_class_1[:, 0], X_class_1[:, 1], label='Class 1')
plt.xlabel('Feature 1')
plt.ylabel('Feature 2')
plt.title('MBGD Logistic Regression on Imbalanced Data')
plt.legend()
plt.show()


text:
is there a mathematical explanation of precision and recall tradeoff?
Is there a mathematical explanation of precision and recall tradeoff? Ie, is it possible
mathematically to see that as you increase one, the other decreases?
$\text{Precision}=\frac{TP}{P^*}=\frac{TP}{TP+FP}$
$\text{Recall}=\frac{TP}{P}=\frac{TP}{TP+FN}$.
When precision increases, why does Recall decease?

no, you can have definitely perfect precision and perfect recall

but in almost all ML material, they mention this tradeoff.

because you can have ideally the perfect classifier that nails both of them, but we don't have it

Your mentioned so called precision and recall tradeoff is a statistical tendency on average, not a mathematical necessity which can be easily shown in below example.
Let $TP=10, FP=5, FN=5$ for demonstration purposes of a trained (non-optimal) classifier, then $$\text{precision} = 10/(10+5) \approx 0.67, \text{recall} = 10/(10+5) \approx 0.67$$
Now let's say we improved the classifier to increase its precision by reducing false positives while keeping true positives constant, ie, now $TP=10, FP=2, FN=5$, then $$\text{precision} = 10/(10+2) \approx 0.83, \text{recall} = 10/(10+5) \approx 0.67$$
Thus recall remains the same despite precision increases in this case. Usually you can define a single F-score as weighted harmonic mean of both precision and recall to tradeoff and effectively weigh the lower of the two numbers more heavily.

The tradeoff between precision and recall occurs because increasing the threshold for classification will result in fewer false positives (increasing precision) but also more false negatives (decreasing recall), and vice versa. You cannot eliminate both false positives and false negatives simultaneously without the presence of a perfect classifier, so improving one often comes at the cost of the other.
But you can do is picking the best threshold for the trade-off from what you have. For example:
You can calculate Youden's J statistic $J = TPR - FPR$ for finding threshold:
J = tpr - fpr
# Get the index of the maximum J statistic
max_j_index = np.argmax(J)
# Get the best threshold value
best_threshold_j = thresholds[max_j_index]


text:
Confusion in notation for state-value functions in reinforcement learning
In state-value function estimation in reinforcement learning,
I see the following notations: $V_T(S_t),\, V_{T-1}(S_t)$. What is the difference between them?
The context is given below.

Please give some context - what was being described when using this notation. A link to where this is written or citing the book and chapter would also be useful. All I can tell you otherwise is that $T$ is an index to multiple state value functions. Plus there is probably an algorithm relating different state value functions. I could guess what that is, but much better to see the context

@NeilSlater, I added the context.

Thanks. Please could you give a link to the original, as it is an image which will be difficult for some users to read. I don't see the notation $V_{T-1}(S_t)$ anywhere in the image you posted? Could you either post an image with the notation you are asking about, or correct the notation you want to know about in the main question.

@NeilSlater, sorry It was the wrong photo. I updated it. There is no link, I had to take a screenshot.

A reference to whichever book, course etc this is from then? With page num etc. There is clearly some published source you are referencing.

The difference between $V_T(S_t)$ and $V_{T-1}(S_t)$ is simply that $V_{T-1}(S_t)$ is the estimate of $V$ after $T-1$ updates. The notation is a bit clumsy since there are two elements of 'time' here -- one being how many updates we have done, which is the subscript of the value function, and the other being the time point in the MDP, which is the subscript of the state.

it was a wrong picture. Could you please  update your answer based on the new picture?

This explanation still tracks with my reading of the new picture.

@foreverska and mine.

I think that the previous image also had some incorrect/awkward notation. The author also includes a note that they are being a bit loose with notation. I would note that the notaton does work, sort of, with a single timeline. The value function at time step $T-1$ can be just "the previous value function", as the author doesn't refer any other index values, and updates only occur at the end of episodes.

@NeilSlater true, though it would be much clearer if rather than $T-1$ they used something simple like a dash (') to denote the new value function -- similar to how SGD is usually presented.

$VT(St)$ is the state value function.
$\bar{v}_t$ is the average of $v_i$, where we make $v_i$ over a rolling period starting from time $t$.
$VT(St)$ is a state-value function, for any given time $St$, it is not time invariant. Because of initialization, we can say that $VT(St') = \bar{v}_t = v_t$ if $t=St'$. In this sense, it is $\text{stationary}$.
I write $VT−1(St)$ because I feel it is more close to the true equation ($V_t = \sum_i^n \frac{1}{n} RV_i^t$ is true), and $VT(St)$ is in fact a derivation over $V_t$ with using sample mean.

What's worth a downvote, simply a lack of relevant understanding?

There seem to be a lot of errors in this answer, as well as additional variables that you introduce but do not explain. As a result, it is confusing to read and hard to tell what you are trying to say, or whether it answers the question. Example of an error: "any given time $S_t$" - but $S_t$ is not a time, it is the state observed at time $t$. It also doesn't help that you are writing $VT$ and $VT - 1$ instead of $V_T$ and $V_{T-1}$


text:
Unclear sentence in Sutton-Barto in Temporal-Difference chapter
Sutton-Barto, Chapter 6, page:130

By 8000 time steps, the greedy policy was long since optimal (a trajectory from it is shown
inset); continued $\epsilon$-greedy exploration kept the average episode length at about 17 steps,
two more than the minimum of 15.

What is meant here by the first sentence: "By 8000 time steps, the greedy policy was long since optimal (a trajectory from it is shown inset)"?
I am confused also: the applied policy is $\epsilon$-greedy SARSA but in the sentence there is "greedy policy". Is the path shown from S to G for greedy policy, or for SARSA?

Underpinning an epsilon-greedy policy is a deterministic greedy policy.  What they are saying here is that this underlying policy has been near optimal for quite a few episodes.
They are still talking about this deterministic greedy policy when discussing the inset.

I am confused by your explanation as well.  is the one given in figure (from S to G)  greedy or epsilon-greedy?

My interpretation is greedy as it is the optimal path in this scenario.  Theoretically it could be a trajectory from epsilon greedy under which the epsilon is sufficiently low that all moves were made deterministically or that an exploration move was taken but it happened to be the same as the greedy move.  The simpler explanation is that it is simply greedy.


text:
Confusing statement in Sutton-Barto on trajectory sampling
Suuton-Barto, page 176:

experiment to assess the effect empirically. To isolate the e↵ect of the update distribution,
we used entirely one-step expected tabular updates, as defined by (8.1). In the uniform
case, we cycled through all state–action pairs, updating each in place, and in the on-policy
case we simulated episodes, all starting in the same state, updating each state–action pair
that occurred under the current $\epsilon$-greedy policy ($\epsilon$=0.1). The tasks were undiscounted
episodic tasks, generated randomly as follows. From each of the |S| states, two actions
were possible, each of which resulted in one of b next states, all equally likely, with a
different random selection of b states for each state–action pair. The branching factor, b,
was the same for all state–action pairs. In addition, on all transitions there was a 0.1
probability of transition to the terminal state, ending the episode. The expected reward
on each transition was selected from a Gaussian distribution with mean 0 and variance 1.

At any point in the planning process
one can stop and exhaustively compute
$v_{\tilde{\pi}}(s_0)$, the true value of the start state
under the greedy policy, $\tilde{\pi}$, given the current
action-value function Q, as an indication
of how well the agent would do on
a new episode on which it acted greedily
(all the while assuming the model is
correct).

Question: In the first paragraph, authors say the policy used for simulation is $\epsilon$-greedy and in the second paragraph, they are now specifying $\tilde{\pi}$ to be the greedy policy corresponding to the current action-value function Q. However, does not the current action-value function Q correspond to the $\epsilon$-greedy policy?

Note in the picture there are three red lines and three blue lines. Also, please don't paste screenshots full of text. Use text. you could then use pull quotes instead of referring to highlighted bits. The graph seems irrelevant to your question, but including it and referring to colours that are in it makes it appear relevant

I meant the underlined red and blue lines in the text, not red and blue lines in the plot. I updated this in the question.

Thanks. Still needs to be text, not a screenshot please. Screenshots of text from textbooks are not searchable on the site, and less easy for screenreaders to process.

I agree. Now, question statement is in text.

The text is about SARSA, so yes the action values in the Q table are estimates based on-policy, on the $\epsilon$-greedy policy used for learning, with a specific value of $\epsilon$.
However, this in no way constrains how the action values can or should be used to derive any other policy. Deriving a greedy policy from the current action values will typically be an improvement (as per the policy improvement theorem), and also a reasonable gauge of how well the agent has learned the environment so far.
It is fairly common approach in SARSA when using $\epsilon$-greedy policies to decay $\epsilon$, and for both Q-learning and SARSA to evaluate the current greedy policy at snapshots in order to track learning progress without the complication of allowing for exploratory actions.


text:
Why no falling off cliff in SARSA for the example in Sutton-Barto?
Sutton-Barto, page 132:

The graph to the right shows the
performance of the Sarsa and Qlearning
methods with "-greedy action
selection, " = 0.1. After an
initial transient, Q-learning learns
values for the optimal policy, that
which travels right along the edge
of the cli↵. Unfortunately, this results
in its occasionally falling o↵
the cli↵ because of the "-greedy action
selection. Sarsa, on the other
hand, takes the action selection into
account and learns the longer but
safer path through the upper part
of the grid.

SARSA is also using $\epsilon$-greedy and hence falling off cliff may happen with the same reasoning done for the Q-learning. I did not understand why this (falling off cliff) does not happen in SARSA.

I think the point here is that Q-learning may learn the optimal policy or value function faster. The optimal policy is to choose actions that are close to the cliff, but, during learning, to behave, you still use the $\epsilon$-greedy policy which is based on the (near-)optimal value function, so you may occasionally fall off the cliff. SARSA may learn a different value function, which during learning doesn't make the agent fall off the cliff as often. If we were not learning, and Q-learning had found the optimal policy, it would always act greedily, so it would not fall off the cliff (assuming the optimal policy doesn't do that).

Can you explain or rephrase the last sentence ? "If we were not learning, and Q-learning had found the optimal policy, it would always act greedily, so it would not fall off the cliff (assuming the optimal policy doesn't do that). "

@DSPinfinity After learning, Q-learning will not use the $\epsilon$-greedy policy to behave but it will use a deterministic policy derived from $q(s, a)$ that it's learned. That deterministic policy is simply $a^* = \text{argmax}_a q(s, a)$, i.e. it chooses the greedy action. If Q-learning has learned the optimal $q$, then it has also learned the optimal policy. Now, that optimal policy should not take actions that make you fall off the cliff, because that's probably not optimal, but it will take actions that are close to the cliff (because we know that's the optimal policy).

This explanation is confusing because in Q-learning  ϵ
-greedy policy is used to select the action A. Ie,  ϵ-greedy policy is behaviour policy.

@DSPinfinity Yes, $\epsilon$-greedy is used to select actions, but only during learning. Q-learning is a learning algorithm, i.e. it's trying to learn a value function $q$, from which you can derive the policy, which is not the behaviour policy you use during learning, but is the greedy policy with respect to $q$, i.e. $a^* = \text{argmax} q(s, a)$. So, after learning, you will not be using the $\epsilon$-greedy but $a^* = \text{argmax} q(s, a)$, which is the target policy and it's optimal if the learned $q$ is also optimal, assuming finite MDPs.

So, the reason why you use $\epsilon$-greedy during learning, instead of the target policy, is because, during learning, $q$ is typically not optimal (at least at the beginning of learning), so you need to explore (i.e. sometimes randomly choose actions) and sometimes you need to exploit (i.e. choose the best action according to your current estimate of $q$). This is one of the most important concepts in RL: the exploration-exploitation tradeoff.

So, you can't just use a greedy (deterministic) policy during learning, because $q$ may not be optimal, and you shouldn't use a stochastic policy after learning in finite MDPs if the learned $q$ is optimal, because there's a known result in RL that says that there's at least one optimal policy that is deterministic in finite MDPs. If you don't know the difference between stochastic and deterministic policies, see https://ai.stackexchange.com/q/12274/2444


text:
Confusing point point in Dyna-Q
Sutton-Barto, page 164:

In the (f) loop, $S,A, S', R$ are from real experience (Model(S,A)=(R, S') where R and S' are also real expereince).
This experience is used in direct RL part in (d). Why is the same experience used
again in the (f) part? Q-update in (d) uses the same info as Q-update in (f). I am totally confused.
It seems to me that part (f) is a n-times re-application in parts before it.

The hope in (f) is that the ${max}_aQ(S^\prime,a)$ has changed since it was previously evaluated so that it's effect on the present state's value can be propagated without the agent having to spend the steps to experience it.


text:
How to define a good reward function to keep output $y$ in the range $[y_{min}, y_{max}]$?
If I want the RL agent to keep the output in the range $[y_{min}, y_{max}]$, what can be the optimal definition of a reward function for this purpose? By output we mean this: assume that the agent is controlling the position of something and we want this position to remain in [pos_min, pos_max].

what exactly do you mean by output? Is the output an expected return or is it an action that the agent takes?

if that's the action space range, just use an appropriate activation function (something like $(tanh(f(x)+1)/2 \cdot (y_{max}-y_{min})+y_{min}$)

By output we mean this: assume that the agent is controlling the position of something and we want this position to remain in [pos_min, pos_max].

How directly is the agent controlling this position? Specifically is the agent's output directly the position, or is the position the result of the agent's action as it is impacted by the environment? E.g. is the agent's action some motor forces or on/off switches for a machine?

I have assumed in my answer that the agent's actions are not directly a choice of position, but something related to it such as choosing a force to apply or a speed etc.

There are multiple ways to structure a reward system to manage some form of homeostasis, i.e. where despite changes in external environment or forces acting against the agent, it takes action to maintain some important part of the state.
The simplest would be to have +1 reward for each time step that the agent met the conditions that you want. This will still allow the agent to learn conservative behaviour well - e.g. if random forces might force your variable $y$ out of bounds, the agent will learn that having $y$ as a (possibly weighted) mid-point of $y_{max}, y_{min}$ would have the highest expected return and would prefer that without you have to more directly reward it.
If your environment is not naturally episodic, you may want to use a discount factor $\gamma$ so that predicted return does not get very high, or use an average reward setting. Maintaining a stasis state can often be treated as either episodic or continuing though, so use whichever you are more comfortable for describing the problem overall.
It might equally be viable to reward -1 for every time step spent outside bounds, or a reward based on distance from a target value with maybe a step function (e.g. an additional -1 for being outside bounds) depending on the agent meeting constraints or not.
If the episode ends when constraints are not met (similar to CartPole toy environment), then the simple +1 reward per step is enough. The agent is effectively "punished" with a lower return if it cannot continue.
In short, there might be a few bad choices for reward function in your case, but there are quite a few good options. I'd recommend to start simple, as per this answer's second paragraph. If you are not sure whether you have picked a good choice, then you should ask a new question with more details on the environment, your goals for the agent and the reward function that you are considering.


text:
Derivation of update rule for Off-policy TD(0) with importance sampling ratio
Sutton-Barto, second edt, page 128, Exercise 6.7:

Design an off-policy version of the TD(0) update that can be used with
arbitrary target policy $\pi$ and covering behavior policy $b$, using at each step t the importance sampling ratio $\rho_{t:t}$ (5.3).

The answer is:
$V(S_t) \leftarrow  V(S_t) + \alpha\rho_{t:t}\left[R_{t+1} + V(S_{t+1})-V(S_t)\right]$
Normally, if we make a similarity to Monte Carlo method, the target here is $R_{t+1} + V(S_{t+1})$ and hence I was expecting the answer as:
$V(S_t) \leftarrow  V(S_t) + \alpha\left[\rho_{t:t}(R_{t+1} + V(S_{t+1}))-V(S_t)\right]$
Where is my mistake? Or, is the answer wrong?

Where are you getting the official answer from? They are not published in the book.

I have the solutions manual.

There is more than one place with published solutions. You can even get them from Sutton if you contact him and ask. Please give more information, link if online.

Please, put your specific question in the title. "off-policy TD(0)" is far from being a good title because it could be about 100 things.


text:
Sutton-Barto confusing notation for the target and behaviour policy in the expected sarsa
Sutton-Barto, page 134, second paragraph:

In these cliff walking results Expected Sarsa was used on-policy, but in general it
might use a policy different from the target policy $\pi$ to generate behavior, in which case
it becomes an off-policy algorithm.

I am confused here. Sutton-Barto was using $\pi$ for target policy and $b$ for the behaviour policy. Why now are they saying "target policy $\pi$ to generate behavior"?

I'm not sure I understand what the doubt is, but here they are saying that you may use a behaviour policy $b$ which is different than $\pi$ (the target policy). In SARSA, you usually have $b = \pi$, but this is expected SARSA. If this answers your question, I'll convert it to a format answer

Just look at the sentence again, you've quoted it correctly and then only pulled half the noun phrase into your question . . . it's not talking about a "target policy $\pi$" - it's talking about a "policy different from the target policy $\pi$"!

In my opinion the wording is bad. It must be like this: " it might use a policy different from the policy to generate behavior, in which case it becomes an off-policy algorithm."

It's normal English phrasing. "A cat different from next door's cat just walked past the window". Your suggestion doesn't make sense, and is ambiguous where S&B is not -  it would be like "A cat different from the cat just walked past the window" . . . unless you've missed something out in your comment above?

S&B introduced  $\pi$ for target policy and $b$ for the behaviour policy when discussing off-policy. In my opinion, when there is a discussion related to target and behaviour policy (or on-policy, off-policy), they should stick to this notation.

If you want a more formal approach with strict notation and less informal English,  there is an alternative to S&B with a good reputation

I will try to find a link to it for you

Nowdays it seems there are dozens. I think the book I am recalling is this https://sites.ualberta.ca/~szepesva/papers/RLAlgsInMDPs.pdf (official free version) But there's also this one: https://faculty.utrgv.edu/weidong.kuang/book/RL.pdf that seems like a work in progress. There's also this which looks promising: https://www.mit.edu/~dimitrib/RLCOURSECOMPLETE.pdf As your issue with S&B is with style and consistency I think you could take brief look at each and decide whether they are more in line with you like to learn


text:
Why is importance sampling ratio in n-step TD multiplying error rather than return n-step return?

Why is importance sampling ratio in n-step TD is multiplying error rather than return?
In Monte Carlo methods for state values, importance sampling ratio was simply a multiplier for the return.

can you please post to the part of the book stating the MC update reweighting as you are reporting?

No, also for MC Control the importance sampling weights the update, and not just the return

But the reason I think can be understood intuitively as:

if you have the same policy as the behavioral, then the updates should be the same, thus the ratio is 1
if the behavioral policy takes an action that you would have never taken, then the update should be 0 (as you would never go to that part of the MDP), thus the ratio is 0

I updated the question:  In Monte Carlo methods for state values, importance sampling ratio was simply a multiplier for the return.