text:
Why is the reward function $\text{reward} = 1/{(\text{cost}+1)^2}$ better than $\text{reward} =1/(\text{cost}+1)$?
I have implemented a simple Q-learning algorithm to minimize a cost function by setting the reward to the inverse of the cost of the action taken by the agent. The algorithm converges nicely, but there is some difference I get in the global cost convergence for different orders of the reward function. If I use the reward function as:
$$\text{reward} = \frac{1}{(\text{cost}+1)^2}$$
the algorithm converges better (lower global cost, which is the objective of the process) than when I use the reward as:
$$\text{reward} = \frac{1}{(\text{cost}+1)}$$
What could be the explanation for this difference? Is it the issue of optimism in the face of uncertainty?

Reinforcement learning (RL) control maximises the expected sum of rewards. If you change the reward metric, it will change what counts as optimal. Your reward functions are not the same, so will in some cases change the priority of solutions.
As a simple example, consider a choice between trajectories with costs A(0,4,4,4) and B(1,1,1,1). In the original cost formula B is clearly better, with 4 total cost compared with A's cost of 12 - A just has one low cost at the beginning, which I put in deliberately as it exposes the problem with your conversion.
In your two reward formulae:
reward = 1/(cost+1)**2.
  A: 1.0 + 0.04 + 0.04 + 0.04 = 1.12
  B: 0.25 + 0.25 + 0.25 + 0.25 = 1.0

reward = 1/(cost+1).
  A: 1.0 + 0.2 + 0.2 + 0.2 = 1.6
  B: 0.5 + 0.5 + 0.5 + 0.5 = 2.0

So with this example (numbers carefully chosen), maximising the total reward favours A for sum of inverse squares but B for sum of inverses, whilst B should be the clear preference for minimising sum of costs. It is possible to find examples for both of your formulae where the best sum of rewards does not give you the lowest cost.
In your case, if you truly want to minimise total cost, then your conversion to rewards should be:
reward = -cost

Anything else is technically changing the nature of the problem, and will result in different solutions that may not be optimal with respect to your initial goal.

Thank you for that illustration. The reward function you have proposed works fairly well with a neural  actor-critic, but when am using a Q-table, it returns a poorer convergence (with higher  global cost) than my two functions. What do you think is the matter? I initialized Q-values with zeros.

@EArwa: Sorry I don't know. I suggest you ask a new question about that if you are stuck.


text:
How does the gradient increase the probabilities of the path with a positive reward in policy gradient?
Pieter Abbeel in his deep rl bootcamp policy gradient lecture derived the gradient of the utility function with respect to $\theta$ as $\nabla U(\theta) \approx \hat{g} = 1/m\sum_{i=1}^m  \nabla_\theta logP(\tau^{(i)}; \theta)R(\tau^{(i)})$, where $m$ is the number of rollouts, and $\tau$ represents the trajectory of $s_0,u_0, ..., s_H, u_H$ state action sequences.
He also explains that the gradient increases the log probabilities of trajectories that have positive reward and decreases the log probabilities of trajectories with negative reward, as seen in the picture. From the equation, however, I don't see how the gradient tries to increase the probabilities of the path with positive R?
From the equation, what I understand is that we would want to update $\theta$ in a way that moves in the direction of $\nabla U(\theta)$ so that the overall utility is maximised, and this entails computing the gradient log probability of a trajectory.
Also, why is $\theta$ omitted in $R(\tau^{(i)})$, since $\tau$ depends on the policy which is dependent on $\theta$ ?

Think of a surface where z-axis is $U$, x and y axis are $\theta_{1}$ and $\theta_{2}$ accordingly. Since you are following the gradient direction with respect to $\theta$ vector, that means you are moving at the direction that increases the $U$. If $R(\tau)$ is positive, you are moving towards the uphill direction and vice-versa. More formally you will say the following:
In the policy gradient algorithm, our update step is:
$ \theta_{new} = \theta_{old} + \alpha \nabla_{\theta}U(\theta) $
So, if we select a very bad trajectory the sum of all rewards ($R(\tau)$) will be negative and the following update will shift the $\theta_{new}$ vector away from $\nabla_{\theta}U(\theta)$ vector.
If we select a good trajectory means $R(\tau)$ is positive, the update will shift $\theta_{new}$ vector towards the $\nabla_{\theta}U(\theta)$ vector. So, it will increase the probability of selecting path with positive $R$

Hey thanks for your answer. The reward, $R(\tau)$ is a scalar quantity and the grad log probability of a trajectory is negative and the grad log probability of the trajectory returns the gradient of the weights in the neural network rite  ?

yes, $R(\tau)$ is a scalar quantity, but the later part you say can not able to understand what you mean by that.

the grad log probability of a trajectory i meant refers to the term $\nabla_{\theta}log P(\tau^{(i)}, \theta)$. so the scalar quantity of the reward is multiplied by this vector to give the gradient of the Utility function w.r.t $\theta$ rite ?

yes. reward$(R(\tau)$ is scalar and you are multiplying the scalar$(R)$ with the vector $\nabla_{\theta}logP(\tau^{i},\theta)$.

how would a negative reward shift $\theta_{new}$ to not favour that bad reward trajectory ? because whether or not a positive scalar or negative scalar is multiplied by the weights, $\theta$ will be updated to move in the direction of the gradient, which means $\theta$ the new $\theta$ will overall increase the utility received but the equation does not show how it affects the log probability of a good or bad trajectory ?

based on the overall increase in utility we can make the conclusion that the probabilities of trajectories with higher rewards are increased ?

When the agent gets neagative $R(\tau)$, it will just decrease the probability of selecting those actions by updating $\theta$.

and that is based on the update rule $\theta_{new} = \theta_{old} + \alpha \nabla_{\theta}U(\theta)$ ?

yes, it's based on this update.

The grad log probability of the trajectory parameterised by $\theta$ tells us the direction $\theta$ should move to increase the probability of that trajectory $P(\tau;\theta)$ the most.
If the reward is positive, $\nabla U(\theta)$ tells us how much we want to increase/decrease the probability of that path $\tau$. The scalar quantity $R(\tau)$ determines the magnitude and direction of shift. If $R(\tau)$ is positive, and $\theta$ is updated based on equation $\theta_{new}$ = $\theta_{old} + \alpha\nabla_{\theta}U(\theta)$, then $\theta$ will move in the direction of it's steepest increase, leading to an increase in probability of $\tau$. If $R(\tau)$ is negative, then $\theta$ moves in the direction of steepest decrease, leading to a decrease in probability of $\tau$.

source: Stack Exchange

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

sort: votes


text:
How should I handle invalid actions in a grid world?
I'm building a really simple experiment, where I let an agent move from the bottom-left corner to the upper-right corner of a $3 \times 3$ grid world.
I plan to use DQN to do this. I'm having trouble handling the starting point: what if the Q network's prediction is telling the agent to move downward (or leftward) at the beginning?
Shall I program the environment to immediately give a $-\infty$ reward and end this episode? Will this penalty make the agent "fear" of moving left again in the future, even if moving left is a possible choice?
Any suggestions?

Here is a similar question in the context of REINFORCE and here is another similar question but in the context of a specific reward function (and DQN).

In a toy environment, this is a choice you can make relatively freely, depending on what you want to achieve with the learning challenge.
It may help if you think through what the actual consequences for making the "wrong" move are in your environment. There are a few self-consistent options:

The move simply cannot be made and count as playing the game as intended. In which case, do not allow the agent to make that choice. You can achieve that by filtering the list of choices that the agent is allowed to make. In DQN that will mean supplying an action mask to the agent based on the state so it does not include the action at the stage it makes a choice. This "available actions" function is usually coded as part of the environment.

The move can be attempted, but results in no change to state (e.g. the agent bumps into a wall). If the goal is to reach a certain state in shortest possible time, then you will typically have 0 reward and a discount factor, or negative reward for each attempted action. Either way, the agent should learn that the move was wasted and avoid it after a few iterations.

The move can be attempted, but results in disaster (e.g. the agent falls off a cliff). This is the case where a large negative reward plus ending the episode is appropriate. However, don't use infinite rewards, positive or negative, because that will cause significant problems with numeric stability. Simply large enough to offset any interim positive rewards associated with that direction should be adequate. For a simple goal-seeking environment with no other positive rewards than reaching the goal, ending the episode early is already enough.

When you don't have a toy environment where you get to decide, then the three basic scenarios above can still help. For instance, in most board games we are not interested in having the agent learn the rules for valid moves when they are already supplied by the environment, so the first scenario applies - only select actions from the valid ones as provided by the environment.

Thanks! In my toy project, the first solution is appropriate. What should I do if I want to add a mask to prevent the agent to behave "downward" and "leftward"?  My current solution is to end this episode immediately if the agent makes those actions and gives a fairly large negative reward. I think an action mask is better than my current solution. How can I implement the action mask in the environment? My DQN network inputs states and outputs Q(s, a).

Will it be similar to adding a manual drop-out, and keeps the out-put "downward" and "leftward" neurons always inactive when in this beginning state?

@o_yeah: It depends on how you have implemented the neural network. But either way, the filtering is done outside of the neural network, by the learning algorithm when it selects an action. If your NN takes s,a as input in a mini-batch to find the best action, then filter the list of action choices before making the mini-batch. If your NN outputs an array of Q values for every action, write code to somehow ignore values of non-valid actions (e.g. set value to -inf before argmax). In both cases you will need a function defined in the environment that tells you what the valid action choices are.

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


text:
How can I design a hierarchy of agents each of which with different goals?
I read some light material earlier about the possibility of building a hierarchy of agents, where the agents at the leaves solve primitive tasks while higher-level agents are optimized for orchestrating direct-descendant agents.
According to my understanding, each agent would have different objective functions and possible moves.
How can I design such a hierarchy of agents each of which with different goals? Are there any examples?

In the context of reinforcement learning, the idea of modeling your goal-oriented problem as a hierarchy of multiple sub-problems is called hierarchical reinforcement learning, which gives rise to concepts such as semi-Markov decision processes and options (aka macro actions). The article The Promise of Hierarchical Reinforcement Learning presents and describes the topic quite well, so I suggest you read it.
However, this idea of solving multiple sub-tasks in order to solve a bigger task isn't limited to RL. For example, in the paper Neural Programmer-Interpreters (NPIs), without referring to the traditional RL topics, a model is proposed to write programs by composing simpler ones.
Another example is genetic programming with automatically defined functions (ADFs), where sub-programs (the ADFs) can be re-used in different parts of the program if that's beneficial according to the fitness.
So, there are different ways you can design a system to solve a big task by solving multiple sub-tasks and then compose them. The approach that you choose depends on your use case. If you want to build programs, then NPIs can be a start. If you want to incorporate a time component in your system, then HRL is probably a viable approach. There are several HRL algorithms. Some of them (e.g. MAXQ-OP) have been successfully used to solve the RoboCup challenge.


text:
What made your DDPG implementation on your environment work?
I am working on scheduling problem that has inherent randomness. The dimensions of action and state spaces are 1 and 5 respectively.
I am using DDPG, but it seems extremely unstable, and so far it isn't showing much learning. I've tried to

adjust the learning rate,
clip the gradients,
change the size of the replay buffer,
different neural net architectures, using SGD and Adam,
change the $\tau$ for the soft-update.

So, I'd like to know what people's experience is with this algorithm, for the environments where it was tested on the paper but also for other environments. What values of hyperparameters worked for you? Or what did you do? How cumbersome was the fine-tuning?
I don't think my implementation is incorrect, because I pretty much replicated this, and every other implementation I found did exactly the same.
(Also, I am not sure this is necessarily the best website to post this kind of question, but I decided to give a shot.)

Did you test it on other environments ? Test it on some OpenAI gym environments and see if it's working

I just tested it on cart pole. It's not quite working. So, the algorithm may not be correct. I am going to double check, but regardless, I'd like to know what people's experience is when working with these algorithms on their own environments. I've implemented SAC. It wasn't very difficult to make it work, especially because my environment is not very challenging.

Update to my last comment. It is working, the training is just very slow and the reward somewhat noisy, but overall, i works. I used Pendulum-v0.

Indeed, DDPG is extremely unstable. A huge improvement related to DDPG is certainly D4PG. You should take a look a recent paper by Gabriel Barth-Maron, Matthew W. Hoffman, and others, called Distributional Policy Gradients, published in 2018 : https://paperswithcode.com/search?q_meta=&q=Distributed+Distributional+Deterministic+Policy+Gradients

Thanks for sharing! I'll certainly take a look at their paper. Also, for anyone reading this, please feel free to share improvements upon DDPG.

Below are some tweaks that helped me accelerate the training of DDPG on a Reacher-like environment:

Reducing the neural network size, compared to the original paper. Instead of:

2 hidden layers with 400 and 300 units respectively

I used 128 units for both hidden layers. I see in your implementation that you used 256, maybe you could try reducing this.

As suggested in the paper, I added batch normalization:

... to manually scale the features so they are in similar ranges across
  environments and units. We address this issue by adapting a recent technique from deep learning
  called batch normalization (Ioffe & Szegedy, 2015). This technique normalizes each dimension
  across the samples in a minibatch to have unit mean and variance.

The implementation you used does not seem to include this.

Reducing the value of $\sigma$, which is a parameter of the Ornstein-Uhlenbeck process used to enable exploration. Originally, it was $0.2$, I used $0.05$. (I can't find where this parameter is set in your code.)

I am not entirely sure if this will help in your environment, but it was just to give you some ideas.
PS: Here is a link to the code I followed to build DDPG and here is a plot of rewards per episode.

do the actor and critic have the same architecture in your case?

@Schach21 , yes, similar to the paper. I just reduced the number of neurons in the first hidden layer from 400 to 128, and in the second hidden layer from 300 to 128.

what did you reward curve look like? Did learning happen and the reward curve stay up (like in the paper)? or was it rather noisy? I included batch normalization. That helped significantly. But I am not getting a smooth learning curve. Moreover, I've never seen a smooth learning curve from DDPG besides the original paper.

ok, perhaps I should mention that in my case, the goal was to solve the environment based on a known benchmark mean reward. The environment is solved when the mean reward remains above a threshold for 100 consecutive episodes. When this objective has been reached, I stopped the learning process. I did not test whether the reward curve stayed up or not after that (in fact, it's possible that it doesn't). If I have the time to test this specific aspect, I'll update my answer to include the resuts.

@Schach21 , I updated the answer with a plot of rewards and the code I based my implementation on. The plot of rewards is shown for 890 episodes, where each episode lasts 1000 steps at most. As it can be seen, there is a number of drops of the reward below 30, which is the target for solving this environment.

thanks! My implementation is working as well. My reward curve looks very similar to yours.


text:
How would researchers determine the best deep learning model if every run of the code yields different results?
There are many factors that cause the results of ML models to be different for every run of the same piece of code. One factor could be different initialization of weights in the neural network.
Since results might be stochastic, how would researchers know what their best performing model is? I know that a seed can be set to incorporate more determinism into the training. However, there could be other pseudo-random sequences that produce slightly better results?

Maybe it would be better that you list the parameters that introduce stochasticity in your training process, model, etc.

I know that a seed can be set to incorporate more determinism into the training. However, there could be other pseudo-random sequences that produce slightly better results?

That is correct. If you fix the seed for a process which inherently has stochastic behaviour by design (such as initialising neural network params), then what you know about the model is that it is the best one given the hyperparameters you have selected and that specific seed. Sometimes the value of the seed is highly relevant, other times less so.

Since results might be stochastic, how would researchers know what their best performing model is?

In general, as with any experiment where measurements are variable, by running the experiment multiple times and taking statistics over the set of results. This will give you a much better sense of how the algorithm does in general, independently of specific seeds. You can still fix your RNG seeds for repeatability, but you will need multiple sets of them.
For certain goals, such as making the best possible model that you can, independently of whether the approach you take is "best in general", this is not necessary. A single run which creates a state-of-the-art performance is still of interest, for instance. Or if you are creating a model that you want to use in production, you may care less about the stability of the technique (and being "lucky") than being in possession of a high performing agent for the task.


text:
Which neural network to use for optical mark recognition?
I've created a neural net using the ConvNetSharp library which has 3 fully connected hidden layers. The first having 35 neurons and the other two having 25 neurons each, each layer with a ReLU layer as the activation function layer.
I'm using this network for image classification - kinda. Basically it takes inputs as raw grayscale pixel values of the input image and guesses an output. I used stochastic gradient descent for the training of the model and a learning rate of 0.01. The input image is a row or column of OMR "bubbles" and the network has to guess which of the "bubble" is marked i.e filled and show the index of that bubble.
I think it is because it's very hard for the network to recognize the single filled bubble among many.
Here is an example image of OMR sections:

Using image-preprocessing, the network is given a single row or column of the above image to evaluate the marked one.
Here is an example of a preprocessed image which the network sees:

Here is an example of a marked input:

I've tried to use Convolutional networks but I'm not able to get them working with this.
What type of neural network and network architecture should I use for this kind of task? An example of such a network with code would be greatly appreciated.
I have tried many preprocessing techniques, such as background subtraction using the AbsDiff function in EmguCv and also using the MOG2 Algorithm, and I've also tried threshold binary function, but there still remains enough noise in the images which makes it difficult for the neural net to learn.
I think this problem is not specific to using neural nets for OMR but for others too. It would be great if there could be a solution out there that could store a background/template using a camera and then when the camera sees that image again, it perspective transforms it to match exactly to the template
I'm able to achieve this much - and then find their difference or do some kind of preprocessing so that a neural net could learn from it. If this is not quite possible, then is there a type of neural network out there which could detect very small features from an image and learn from it.  I have tried Convolutional Neural Network but that also isn't working very well or I'm not applying them efficiently.

What is the structure of your dataset(any bounding boxes/meta data?). Also, how many images are you using in your dataset?

@UdayrajDeshmukh The dataset consists of a little more than 2,000 preprocessed images (as shown above) that have been labeled. No, there is no such bounding box or metadata to go with the dataset.

So there are only cropped vertical strips? Also is applying ML a necessity to solve your problem?

@UdayrajDeshmukh Sorry for the late replies.
Initially, the image comes in as a full document, it is then preprocessed and cropped to these vertical strips of options/bubbles.
The reason why I must use ML is the fact that the sheet is arbitrary, it can be of any color, design and the bubbles can be of any size or shape, all of this depends on the user and in the program I've provided the user with an interface to train their models. I hope that answers your question.

So if OMR Checking is your problem statement. It's coincidence that I have been working on a solution for the same, and it works pretty well for document scanned images currently

It is scheduled to be launched on product hunt soon. After that I will be able to write an answer to your question

That's interesting. I'll be waiting for it, can you provide an estimate on the launch date maybe?.

Done! Please check https://www.producthunt.com/posts/omr-checker/
I can discuss the details over discord chat(link on repo). If you like it, do leave a star!

From what I understand, don't bother with a CNN, you have essentially perfectly structured images.
You can hand code detectors to measure how much filled in a circle is.
Basically do template alignment and then search over the circles.
Ex a simple detector would measure the average blackness of the circle which you could then threshold.

I'm not familiar with ConvNetSharp library, and the tag convolutional-neural-networks is a bit confusing me, but from :

So I've created a neural net using the ConvNetSharp library which has 3 fully connected hidden layers. The first having 35 neurons and the other two having 25 neurons, each with a ReLU layer as the activation function layer.

I assume you are building just a densely connected neural network. Correct me if I'm wrong.

The type of neural network you need is Convolutional Neural Network.
For image recognition (which is your case), convolutional network are almost always the answer.
There is plenty of type of CNN, just pick one that seems appropriate and try.
In my opinion, your task seems quite simple, you won't need really deep / complex architecture.

It would be great if there could be a solution out there that could store a background/template using a camera and then when the camera sees that image again

I am not aware of a model that could do what you are asking.
But what you are asking is not really in the 'neural network' mindset. The goal of building a neural network is that you don't specify anything. The neural network will learn and find the features for you. So you just have to feed him a lot of data, and he will be able to recognize your pattern.
Take a look at this visualization of CNN filters :

Here, no one gave the neural network the template of a nose or the template of an eye or the template of a face. The CNN learned it over a lot of image.

Hi Astariul,
I've tried using the convolutional neural network approach, but the results are not good for some reason. Maybe, its because the size of images are so small that the network isn't able to extract features and learn from them.

I've updated the question to clarify things further, thanks for your consideration.

Is it the case that one of the numbers if filled in? If so a CNN with 10 output should work well. Just choose the output that has the highest probability. If your data allows no number to be filled in, then have 11 outputs where the eleventh output indicates none is filled in. I would recommend transfer learning using the MobileNet model. Documentation is here. Here is the code to adapt MobileNet to your problem:
image_size=128
no_of_classes=10  # set to 11 if in some cases no numbers are filled in
lr_rate=.001
dropout=.4
mobile = tf.keras.applications.mobilenet.MobileNet( include_top=False,
                                                           input_shape=(image_size,image_size,3),
                                                           pooling='avg', weights='imagenet',
                                                           alpha=1, depth_multiplier=1)
x=mobile.layers[-1].output
x=keras.layers.BatchNormalization(axis=-1, momentum=0.99, epsilon=0.001 )(x)
x=Dense(128, kernel_regularizer = regularizers.l2(l = 0.016),activity_regularizer=regularizers.l1(0.006),
                bias_regularizer=regularizers.l1(0.006) ,activation='relu')(x)
x=Dropout(rate=dropout, seed=128)(x)
x=keras.layers.BatchNormalization(axis=-1, momentum=0.99, epsilon=0.001 )(x)
predictions=Dense (no_of_classes, activation='softmax')(x)
model = Model(inputs=mobile.input, outputs=predictions)
for layer in model.layers:
    layer.trainable=True
model.compile(Adam(lr=lr_rate), loss='categorical_crossentropy', metrics=['accuracy'])

I would also create a training, test and validation set with about 150 images in the test set and 150 images in the validation set leaving 1700 images for training. I also recommend you use two useful callbacks. Documentation is here. Use the ReduceLROnPlateau callback to monitor the validation loss and adjust the learning rate downward by a factor. Use ModelCheckpoint to monitor the validation loss and save the model with the lowest validation loss to use to make predictions on the test set.


text:
How do I convert an MDP with the reward function in the form $R(s,a,s')$ to and an MDP with a reward function in the form $R(s,a)$?
The AIMA book has an exercise about showing that an MDP with rewards of the form $r(s, a, s')$ can be converted to an MDP with rewards $r(s, a)$, and to an MDP with rewards $r(s)$ with equivalent optimal policies.
In the case of converting to $r(s)$ I see the need to include a post-state, as the author's solution suggests. However, my immediate approach to transform from $r(s,a,s')$ to $r(s,a)$ was to simply take the expectation of $r(s,a,s')$ with respect to s' (*). That is:
$$ r(s,a) = \sum_{s'} r(s,a,s') \cdot p(s'|s,a) $$
The authors however suggest a pre-state transformation, similar to the post-state one. I believe that the expectation-based method is much more elegant and shows a different kind of reasoning that complements the introduction of artificial states. However, another resource I found also talks about pre-states.
Is there any flaw in my reasoning that prevents taking the expectation of the reward and allow a much simpler transformation? I would be inclined to say no since the accepted answer here seems to support this. This answer mentions Sutton and Barto's book, by the way, which also seems to be fine with taking the expectation of $r(s, a, s')$.
This is the kind of existential question that bugs me from time to time and I wanted to get some confirmation.
(*) Of course, that doesn't work in the $r(s, a)$ to $r(s)$ case, as we do not have a probability distribution over the actions (that would be a policy, in fact, and that's what we are after).

You might want to see this How are the reward functions $R(s)$, $R(s, a)$ and $R(s, a, s')$ equivalent? answer.

I actually had that thread linked in my question, but: 1) I'm not claiming that the different reward functions can be made equivalent, but that the optimal policy to the overall  MDP can; 2) In their solutions book, Norvig and Russell describe a transformation based on extending the state space with pre and post states, and a few more changes to the discount factor and the transitions to account for these additional states; 3) I wanted to know if taking the expectation over s' can do the trick too, at least for the R(s,a,s') to the R(s,a) case.

sorry, my bad for not noticing the link. Note that if you have a joint distribution of $(X,Y)$ you can't find $\mathbb{E}[Y]$ by simply summing over $y$ and using the joint pmf - you would first need to marginalise the joint pmf to get the single pmf of $Y$, so your expectation doesn't work out.

I understand, but I think I didn't imply that...? In fact I'm kinda saying that you could get away by marginalizing s,a in the r(s,a,s') function (if you can say marginalize in this context, since r(s,a,s') is not a probability distribution).

$r(s,a,s') = \mathbb{E}[R_t | S_{t-1} = s, A_{t-1} = a, S_t = s']$?

If so then you would be able to get  $\mathbb{E}[R_t | S_{t-1} = s, A_{t-1} = a] = \sum_{s'} \mathbb{E}[R_t | S_{t-1} = s, A_{t-1} = a, S_t = s'] \mathbb{P}(S_t = s' | s, a) = r(s,a)$

I think I may be in position to answer my own question. The Bellman equation (for the optimal policy) for a MDP with $r(s,a,s')$ rewards would look like this:
$$V(s) = \max_a \left\{ \sum_{s'} p(s'|s,a)(r(s,a,s') + \gamma V(s')) \right\} $$
$$V(s) = \max_a \left\{ \sum_{s'} p(s'|s,a) \cdot r(s,a,s') + \gamma \sum_{s'} p(s'|a,s) \cdot V(s') \right\} $$
Now, $ \sum_{s'} p(s'|s,a) \cdot r(s,a,s') $ is precisely $ \mathbb{E}\left[ r(s,a,s') | s,a \right] = r(s,a) $.
So all in all, the resulting Bellman equation looks like this:
$$V(s) = \max_a \left\{r(s,a) + \gamma \sum_{s'} p(s'|s,a) \cdot V(s') \right\} $$
It is clear, then, that a process with $ r(s,a,s') $ rewards can be transformed to a $ r(s,a) $ process without introducing artificial states and maintaining the optimal policies.
As a side note unrelated to the question itself, that leads me to believe that $ r(s,a,s') $ functions may be convenient in some scenarios, but they do not add "expressive power", in the sense that they do not allow to model problems more compactly (as it happens when we extend $ r(s) $ to $ r(s,a) $).

Fair enough, since I'm interested just in the optimal policy. Maybe I should edit the answer to reflect that (although I was under the impression that the Bellman equation already conveyed optimality)? I thought that $p(s,a,s')$ was a fairly understood notation for the transition probability, meaning: probability of transitioning to $s'$ after taking action $a$ in $s$. I've replaced it by $p(s'|s,a)$.

Good, made that clear.

"My BSc was in Maths and MSc in Stats" -> That would explain the obsession for rigor, clear notation and proper terminology ;) Thank you for your notes, mate.


text:
How and when should we update the Q-target in deep Q-learning?
I have recently watched David silver's course, and started implementing the deep Q-learning algorithm.
I thought I should make a switch between the Q-target and Q-current directly (meaning, every parameter of Q-current goes to Q-target), but I found a repository on GitHub where that guy updates Q-target as follows:
$$Q_{\text{target}} = \tau * Q_{\text{current}} + (1 - \tau)*Q_{\text{target}}$$.
where $\tau$ is some number probably between 0 and 1.
Is that update correct or I miss something?
I thought after some iterations (e.g. 2000 iteration), we should update Q-target as: $Q_{\text{target}}=Q_{\text{current}}$.

The update form $\theta^{\prime} \leftarrow \tau \theta+(1-\tau) \theta^{\prime}$ (where $\theta'$ and $\theta$ represent the weights of the target network and the current network, respectively) does exist and is correct.
It is called soft update and it has been used in the Deep Deterministic Policy Gradient (DDPG) paper, which uses the concept of a target network like DQN. The authors of the paper state that:

The weights of these target networks are then updated by having them slowly track the learned networks: $\theta ' \leftarrow \tau \theta + (1 − \tau )\theta'$ with $\tau << 1$. This means that the target values are constrained to change slowly, greatly
  improving the stability of learning.

This update will be made in each time step as follows. For example, for $\tau= 0.001$, the new weights for the target network will take $0.1\%$ of the main network’s weights and $99.9 \%$ of the old target network weights. This does not go against the purpose of fixed target networks (which have been introduced to address the problem of “moving targets”). In fact, by keeping $99.9\%$ of the old target network weights, they can still be considered as fixed.
Seeing that this resulted in improvements in DDPG, some DQN implementations/tutorials started to use soft updates for the target network.
This is opposed to the hard update scheme used in the original DQN paper, i.e. the weights are copied every $C$ steps. This means that the target network is kept fixed for $C$ steps (10000 in the paper) and then gets a significant update.

okay thank you so much.So in this repository this guy updates weights after every iteration, is that correct?It works on Lunalander perfectly, like you said he used soft update and changed target network after every iteration.Is that a coincidence that algorithm works or when you use soft update you can switch networks after every iteration?

Yes, it is correct. Instead of waiting C steps to make an update, you update your target network in each step, as follows. For example, for $\tau= 0.001$, the new weights for the target network will take $0.1%$ of the main network’s weights and $99.9 %$ of the old target network weights. This is not a coincidence, because recall that fixed target networks have been introduced to address the problem of “moving targets”. So, by keeping $99.9%$ of the old target network weights, they can still be considered as fixed.

thanks a lot, i completely understand now.


text:
Is this proof of $\epsilon$-greedy policy improvement correct?
The following paragraph about $\epsilon$-greedy policies can be found at the end of page 100, under section 5.4, of the book "Reinforcement Learning: An Introduction" by Richard Sutton and Andrew Barto (second edition, 2018).

but with probability $\varepsilon$ they instead select an action at random. That is, all nongreedy actions are given the minimal probability of selection, $\frac{\varepsilon}{|\mathcal{A}(s)|}$, and the remaining bulk of the probability, $1-\varepsilon+\frac{\varepsilon}{|\mathcal{A}(s)|}$, is given to the greedy action. The $\varepsilon$-greedy policies are

So, the non-greedy actions are given the probability  $\frac{\varepsilon}{|\mathcal{A}(s)|}$, and the greedy action is given the probability $1-\varepsilon+\frac{\varepsilon}{|\mathcal{A}(s)|}$. All clear up to this point.
However, I have a doubt in the policy improvement theorem that is mentioned in page 101, under section 5.4. I have enclosed a copy of this proof for your convenience:
$$
\begin{aligned}
q_{\pi}(s, \pi^{\prime}(s)) &=\sum_{a} \pi^{\prime}(a \mid s) q_{\pi}(s, a) \\
&=\frac{\varepsilon}{|\mathcal{A}(s)|} \sum_{a} q_{\pi}(s, a)+(1-\varepsilon) \max _{a} q_{\pi}(s, a) \\
& \geq \frac{\varepsilon}{|\mathcal{A}(s)|} \sum_{a} q_{\pi}(s, a)+(1-\varepsilon) \sum_{a} \frac{\pi(a \mid s)-\frac{\varepsilon}{|\mathcal{A}(s)|}}{1-\varepsilon} q_{\pi}(s, a)\\
&=\frac{\varepsilon}{|\mathcal{A}(s)|} \sum_{a} q_{\pi}(s, a)-\frac{\varepsilon}{|\mathcal{A}(s)|} \sum_{a} q_{\pi}(s, a)+\sum_{a} \pi(a \mid s) q_{\pi}(s, a) \\
&=v_{\pi}(s) .
\end{aligned}
$$
My question is shouldn't the greedy action be chosen with a probability of $1-\varepsilon+\frac{\varepsilon}{|\mathcal{A}(s)|}$?
The weighing factors do not add up to 1, as they are probability values. With this argument, the proof (with a slight modification) would be:
$$
\begin{aligned}
q_{\pi}(s, \pi^{\prime}(s))
&=\sum_{a} \pi^{\prime}(a \mid s) q_{\pi}(s, a) \\
&=\frac{\varepsilon}{|\mathcal{A}(s)|} \sum_{a} q_{\pi}(s, a)+ \left( 1-\varepsilon+\frac{\varepsilon}{|\mathcal{A}(s)|} \right) \max _{a} q_{\pi}(s, a) \\
& \geq \frac{\varepsilon}{|\mathcal{A}(s)|} \sum_{a} q_{\pi}(s, a)+\left(1-\varepsilon+\frac{\varepsilon}{|\mathcal{A}(s)|}  \right) \sum_{a} \frac{\pi(a \mid s)-\frac{\varepsilon}{|\mathcal{A}(s)|}}{1-\varepsilon+\frac{\varepsilon}{|\mathcal{A}(s)|}  } q_{\pi}(s, a)\\
&=\frac{\varepsilon}{|\mathcal{A}(s)|} \sum_{a} q_{\pi}(s, a)-\frac{\varepsilon}{|\mathcal{A}(s)|} \sum_{a} q_{\pi}(s, a)+\sum_{a} \pi(a \mid s) q_{\pi}(s, a) \\
&=v_{\pi}(s) .
\end{aligned}
$$
Though the end result isn't changed, I just want to know what I am conceptually missing, in order to understand the proof that is originally provided.

The weights do sum to one. Note that in the second line where we have
$$\frac{\epsilon}{|\mathcal{A}(s)|} \sum_a q_{\pi}(s,a) + (1-\epsilon)\max_aq_{\pi}(s,a) \; ,$$
the sum is over the whole action space, including the greedy action, so the sum of the weights will be $\frac{\epsilon}{|\mathcal{A}(s)|} \times |\mathcal{A}(s)| + (1-\epsilon) = 1$.


text:
How should I decay $\epsilon$ in Q-learning?
How should I decay the $\epsilon$ in Q-learning?
Currently, I am decaying epsilon as follows. I initialize $\epsilon$ to be 1, then, after every episode, I multiply it by some $C$ (let it be $0.999$), when it reaches $0.01$. After that, I keep $\epsilon$ to be $0.01$ all the time. I think this has a terrible consequence.
So, I need a $\epsilon$ decay algorithm. I haven't found script or formula about it, so can you tell me?

The way you have described tends to be the common approach. There are of course other ways that you could do this e.g. using an exponential decay, or to only decay after a 'successful' episode, albeit in the latter case I imagine you would want to start with a smaller $\epsilon$ value and then decay by a larger amount.


text:
What are finite horizon look-ahead policies in reinforcement learning?
I was reading the paper How to Combine Tree-Search Methods in Reinforcement Learning published in AAAI Conference 2019. It starts with the sentence

Finite-horizon lookahead policies are abundantly used in Reinforcement Learning and demonstrate impressive empirical success.

What is meant by "finite horizon look-ahead"?

Per this paper a look ahead policy is a policy that will make decisions based on some 'horizon'. Here horizon means some time steps into the future, and so a finite horizon is simply a finite amount of time steps into the future. For example, as we are typically concerned with maximising returns in RL, a 10-step look ahead policy would choose an action at time $t$ that maximises the (expected) rewards at time $t+1, ... t+10$.

Arent all policies finite horizon lookahead policies as per bellman equations where the discount factor determine how far to look ahead?

No, for instance you can get some bandit algorithms that assume an infinite horizon. Gittins Index is an example.


text:
Is there any good reference for double deep Q-learning?
I am new in reinforcement learning, but I already know deep Q-learning and Q-learning. Now, I want to learn about double deep Q-learning.
Do you know any good references for double deep Q-learning?
I have read some articles, but some of them don't mention what the loss is and how to calculate it, so many articles are not complete. Also, Sutton and Barto (in their book) don't describe that algorithm either.
Please, help me to learn Double Q-learning.

If you're interested in the theory behind Double Q-learning (not deep!), the reference paper would be Double Q-learning by Hado van Hasselt (2010).
As for Double deep Q-learning (also called DDQN, short for Double Deep Q-networks), the reference paper would be Deep Reinforcement Learning with Double Q-learning by Van Hasselt et al. (2016), as pointed out in
 ddaedalus's answer.
As for how the loss is calculated, it is not explicitly written in the paper. But, you can find it in the Dueling DQN paper, which is a subsequent paper where Van Hasselt is a coauthor. In the appendix, the authors provide the pseudocode for Double DQN. The relevant part for you would be:

$y_{j}=\left\{\begin{array}{ll}r & \text { if } s^{\prime} \text { is terminal } \\ r+\gamma Q\left(s^{\prime}, a^{\max }\left(s^{\prime} ; \theta\right) ; \theta^{-}\right), & \text {otherwise}\end{array}\right.$
Do a gradient descent step with loss $ \left\|y_{j}-Q(s, a ; \theta)\right\|^{2}$

Here, $y_j$ is the target, $\theta$ are the parameters of the regular network and $\theta^{-}$ are the target network parameters.
The most important thing to note here is the difference with the DQN target:
$y_{i}^{D Q N}=r+\gamma \max _{a^{\prime}} Q\left(s^{\prime}, a^{\prime} ; \theta^{-}\right)$.
In DQN, we evaluate the Q-values based on parameters $\theta^{-}$ and we take the max over actions based on these Q-values parametrized with the same $\theta^{-}$. The problem with this is that it leads to an overestimation bias, especially at the beginning of the training process, where the Q-values estimates are noisy.
In order to address this issue, in double DQN, we instead take the max based on Q-values calculated using $\theta$ and we evaluate the Q-value of $a^{max}$ based on a different set of parameters i.e. $\theta^{-}$.
If you want to learn more about this, by watching a video lecture instead of reading a paper, I'd suggest you take a look at this lecture from UC Berkley's DRL course, where the professor (Sergey Levine) discusses this in detail with examples.

You should first read the introductory paper of Double DQN.
https://arxiv.org/abs/1509.06461
Then, depending on what you would like to do, search for other relevant papers that use this method.
I also propose studying the original Double Q-learning paper to understand important concepts/issues, such as the overestimation bias of Q-learning: https://proceedings.neurips.cc/paper/2010/file/091d584fced301b442654dd8c23b3fc9-Paper.pdf


text:
How to fill missing values in a dataset where some properties can be inputs and outputs?
I have a dataset with missing values, I would like to use machine learning methods to fill.
In more detail, there are $n$
individuals, for which up to 10 properties are provided, all numerical. The fact is, there are no individuals for which all properties are given. The first rows (each row contains data for a given individual) do look as the following
\begin{bmatrix}
    1 & NA & 3.6 & 12.1 & NA \\
1.2 & NA & NA & 4 & NA \\
    NA & 4 & 5 & NA & 7
  \end{bmatrix}
What methods could be applicable in general?
I have some basic experience in classifiers and Random Forests. Modulo the obvious difference that this is not a classifying problem, what I struggle most with is that the same variable (described in the e.g
$n$-th column) is both an input and an output. Say I want to predict the value $A_{2,3}$ in the dataset above. In this case, all the values in the third column could be used as input, excluded of course $A_{2,3}$
itself, which would be an output.
This seems to be different than the more conventional set-up of predicting a property, given a set of other properties (e.g, predict income given education, work sector, seniority, etc.). In this case, sometimes the income is to be predicted, sometimes used for predicting another variable.
I am aware of methods which, given a vector $X_i$, could approximate a function $F$ and predict responses $Y_i$ with
$$ Y_i = F(X_i)$$
In the scenario I described though, it looks like some implicit function $\Phi$ is to be found, a function of all the variables $Z_i$ (columns in the dataset above)
$$ \Phi (Z_i) = 0$$
What methods could handle this aspect? I understand the question is probably too general, but I could not find much and could do with a starting point. I would be already content with some hints for my further reading, but anything more would be gratefully welcomed, thanks.

Hi and welcome to AI SE! Have you tried the typical methods of filling the missing values with the average (of the non-missing values in the corresponding column/property), zero, minimum, and maximum? I don't know if this will work, but that should be a starting point.

Yes that is what I have done so far, but it seems really inaccurate, as it grossly misses some obvious correlations. For example, if an individual is very tall, their weight will also tend to be larger. But if my dataset is populated mainly by short individuals, the average will be skewed and tall individuals will be assigned a smaller weight.

Hi, could you explain the data set more, what it represents?

@Igor, frankly the question is very general, I do not have a specific dataset in mind, more a general problem, which I thought must be quite common in Data Science. I re-read my post and the beginning might be confusing indeed..

As you mentioned in the comments about a possible problem of using mean, median type of imputations naively could lead to wrong predictions. In such cases, you need to first check whether you have enough data.
If you have enough data
You can try using MICE (Multivariate Imputation By Chained Equations) algorithm on your missing data. The method is based on Fully Conditional Specification, where each incomplete variable is imputed by a separate model. The MICE algorithm can impute mixes of continuous, binary, unordered categorical and ordered categorical data. One note of caution with this method: It is a computationally expensive method, so it use it if you are not short on time.
The important thing to keep in mind is that in order to tackle such problems, you would be needing multiple iterations as a part of your algorithm. The conventional setup you are describing, does not seem to iterative in nature and hence you are running into the problem of features being input and output at the same time.
If by any chance you insist on finding the missing values just for solving a downstream task like classification or regression, you can try the XgBoost algorithm. It can be used as a classifier or as a regressor. This algorithm can handle missing values inherently. Source: this answer
If you don't have enough data
In such a case you would need to introduce bias in your model using your insights or domain knowledge about the problem. For, e.g., in the a possible problem of estimating weights using heights, you had an insight that your data comprises more of short people. So instead of naively using median values of the total dataset for weight, you can try to bin the data according to their heights, say 'S', 'M', 'L', 'XL', and estimate the weights of each bin separately using the median values of their respective bins. The thing to keep in mind is that when data is low, you need to provide knowledge to the model by enforcing some bias using your insights and domain knowledge about the problem.


text:
What are the main differences between sparse autoencoders and convolution autoencoders?
What are the main differences and similarities between sparse autoencoders and convolution autoencoders?
When should one be preferred over the other? What are their applications?
(References are welcome. Somehow I was not able to find any comparisons of these autoencoders although I looked in a few textbooks and searched for material online. I was able to find the descriptions of each autoencoder separately, but what I am interested in is the comparison.)

Sparse auto-encoders (SAEs) are auto-encoders that impose constraints on the parameters so that they are sparse (i.e. zero or close to zero). This can be achieved in different ways. For example, you can train an auto-encoder with a loss function that includes a penalty term (to constraint the parameters to be close to zero or zero) or you e.g. set the smallest activations to zero.
Convolution auto-encoders (CAEs) are auto-encoders that use the convolution operation. So, they can be viewed as the auto-encoder version of convolutional neural networks. For this reason, they are particularly suited to compress and reconstruct images. The authors of the original paper, Stacked Convolutional Auto-Encoders for Hierarchical Feature Extraction, train them with gradient descent and back-propagation by minimizing the mean squared error, so there's e.g. no penalty term, but you can probably combine SAEs with CAEs.
Of course, you could say that CAEs are sparse with respect to the traditional auto-encoder (in the same way that you can say that CNNs are sparse with respect to fully connected neural networks), so, in this sense, CAEs are also sparse auto-encoders.


text:
How do I derive the gradient with respect to the parameters of the softmax policy?
The gradient of the softmax eligibility trace is given by the following:
\begin{align}
\nabla_{\theta} \log(\pi_{\theta}(a|s)) &= \phi(s,a) - \mathbb E[\phi (s, \cdot)]\\
&= \phi(s,a) - \sum_{a'} \pi(a'|s) \phi(s,a')
\end{align}
How is this equation derived?
The following relation is true:
\begin{align}
\nabla_{\theta} \log(\pi_{\theta}(a|s)) &= \frac{\nabla_{\theta} \pi_{\theta}(a|s)}{\pi_{\theta}(a|s)} \tag{1}\label{1}
\end{align}
Thus, the following relation must also be true:
\begin{align}
\frac{\nabla_{\theta} \pi_{\theta}(a|s)}{\pi_{\theta}(a|s)}  &=\phi(s,a) - \sum_{a'} \pi(a'|s) \phi(s,a')
\end{align}
Mathematically, why would this be the case? Probably, you just need to answer my question above because \ref{1} is true and it's just the rule to differentiate a logarithm.

Softmax policy $\pi_\theta(s,a)$ is defined as $\frac{\exp{(\phi(s,a)^T \theta})}{\Sigma \exp{(\phi(s,a) ^T \theta) }}$, where the summation is over the action space.
Taking log, this becomes
$$
\log \pi_\theta(s,a) = log(e^{\phi(s,a) ^T \theta}) - log({\Sigma e^{\phi(s,a) ^T \theta }}) \\
= \phi(s,a) ^T \theta - log({\Sigma e^{\phi(s,a)^T \theta }})
$$
Taking derivative wrt $\theta$, this becomes
$$
\nabla_\theta \log \pi_\theta(s,a) = \phi(s,a) - \nabla_\theta log({\Sigma e^{\phi(s,a) ^T \theta }})
$$
We can rewrite $\nabla_\theta log({\Sigma e^{\phi(s,a)^T \theta }})$ as follows.
$$
\nabla_\theta log({\Sigma e^{\phi(s,a)^T \theta }})
= \frac{\nabla_\theta \Sigma e^{\phi(s,a)^T \theta}}{\Sigma e^{\phi(s,a) ^T \theta}}
= \frac{\Sigma \phi(s,a) e^{\phi(s,a) ^T \theta}}{\Sigma e^{\phi(s,a) ^T \theta}}
= \Sigma \phi(s,a) \pi_\theta(s,a)
$$
The final equation then becomes
$$
\nabla_\theta \log \pi_\theta(s,a) = \phi(s,a) - \Sigma \phi(s,a) \pi_\theta(s,a)
$$

I'd recommend writing each of the $e^{\phi(s, a) \theta}$ things as $\exp(\phi(s, a)^{\top} \theta)$. Not having to write it in the smaller superscript makes it a bit more readable, especially for the in-text equations. And I like making the transpose a bit more explicitly visible too personally :) That last part is assuming we're dealing with feature and weight vectors of course, not just scalars


text:
How to calculate the advantage in policy gradient functions?
From my understanding of the REINFORCE policy gradient method, we gently nudge the probabilities of actions based on the advantages. More specifically, the positive advantages increase the probabilities, negative advantages reduce the probabilities.
So, how do we compute the advantages given the real discounted rewards (aggregated rewards from the episode) and a policy network that only outputs the probabilities of actions?

First let us note the definition of the advantage function:
$$A(s,a) = Q(s,a) - V(s) \; ,$$
where $Q(s,a)$ is the action-value function and $V(s)$ is the state-value function. In theory you could represent these by two different function approximators, but this would be quite inefficient. However, note that
$$Q(s,a) = \sum_{s',r} \mathbb{P}(s',r|s,a)(r + V(s') = \mathbb{E}[r + V(s')|a,s]\;,$$
so we can actually use a single function approximation, for $V(s)$, to completely represent the advantage function. To optimise this function approximator you would use the returns at each step of the episode as in e.g. the REINFORCE algorithm like you mentioned.

The advantage is basically a function of the actual return received and a baseline. The function of the baseline is to make sure that only the actions that are better than average receive a positive nudge.
One way to estimate the baseline is to have a value function approximator. At every step, you train a NN, using the trajectories collected via the current policy, to predict the value function for states.
I hope that answers your query.


text:
Do we have two Q-learning update formulas?
I have seen two deep Q-learning formulas:
$$Q\left(S_{t}, A_{t}\right) \leftarrow Q\left(S_{t}, A_{t}\right)+\alpha\left[R_{t+1}+\gamma \max _{a} Q\left(S_{t+1}, a\right)-Q\left(S_{t}, A_{t}\right)\right]$$
and this one
$$Q(s, a)=r(s, a)+\gamma \max _{a} Q\left(s^{\prime}, a\right)$$
Which one is correct?

Both are correct. The second one however is used in the deterministic case because applying the second one to stochastic environments with probabilistic state transitions will not cause the Q values to converge.

@calveeen It's not just about stochastic environments. It's also about the fact that the $Q(S_{t+1}, a)$ values being used for bootstrapping may be inaccurate even in deterministic environments (they're our own estimates which are probably not 100% accurate). Stochastic environments do make this worse though, yes.

The first one is the update rule that we use in the $Q$-learning algorithm.
The second one is the "definition" of $Q(s, a)$ values, although I would personally write it as follows, with an expectation around the reward, to also support cases where rewards might be non-deterministic;
$$Q(s, a) \doteq \mathbb{E} \left[ r(s, a) \right] + \gamma \max_a Q(s', a)$$
Here, the $Q(s', a)$ itself would also be similarly defined, and again that one is also assumed to be a "ground-truth" value.
In practice, when learning, we do not actually know what any of these $Q$-values exactly are; that's why we're doing learning in the first place, we're trying to learn what these values are! More precisely, when we wish to assign a new value to $Q(s, a)$, the definition tells us that we should use $Q(s', a)$ for that, but we can't because we don't know exactly what the correct $Q(s', a$) value is either.
We do generally have some $Q(S_{t+1}, a)$ values, but they're generally going to be only approximations, resulting from the previous steps of our own learning process (or maybe even randomly initialised values if we only just started training!). There may also be an additional approximation error in stochastic environments, where the true $Q(s', a)$ value may be a weighted average over multiple different possible successor states $s'$, but during the training we only observed a single concrete successor state $S_{t+1}$.
So, we can follow the definition and use $Q(S_{t+1}, a)$ as an approximation of $Q(s', a)$, but we know that it's just an approximation and not entirely reliable. Therefore, instead of fully applying the definition and completely replacing our $Q(s, a)$ value based on it, we interpolate between our current estimate $Q(s, a)$ and the new one that we should have according to the definition + our approximations. We only slightly shift towards it. The learning rate $\alpha$ determines how much we shift towards it. Normally we use a learning rate $0 < \alpha < 1$. Note that if you were to use $\alpha = 1$, you would actually recover the definition for $Q$-values again (except it would still use some observations to estimate unknown quantities).

I think that the definition of the $Q(s,a)$ as you have defined them would only hold if we were following the optimal policy. I don't think for a general policy $\pi$ that you definition would hold - it should be $Q_\pi(s,a) = \mathbb{E}[r + V_\pi(s') | s, a]$

@DavidIreland I left the policy that I'm defining it for off yeah, implicitly assuming that it would be for the optimal policy. But the definition would actually work for any greedy policy. In the context of $Q$-learning we do always try to learn about greedy policies.

I agree that it would hold for any greedy policy, but generally we want to learn an $\epsilon$-greedy policy to make sure we are exploring sufficiently. I guess once it is considered to be performing optimally (or close to) and you want to use it (e.g. playing Atari games) you could then just always choose the greedy action.

@DavidIreland Normally you'd use an $\epsilon$-greedy policy (or some other form of exploratory policy) to generate experience for training, yes. But in $Q$-learning, you do not aim to learn anything about that policy. You just use it to generate experience, which you then use to learn about a completely different policy (a policy that's greedy with respect to your $Q$-values). This is why $Q$-learning is an off-policy algorithm; it learns about a policy that's different from the one used to generate experience.

Ah sorry, in your answer I thought you were talking about the general definition of $Q(s,a)$ - not specifically in the context of Q-learning. My bad.


text:
Why do we need convolutional neural networks instead of feed-forward neural networks?
Why do we need convolutional neural networks instead of feed-forward neural networks?
What is the significance of a CNN? Even a feed-forward neural network will able to solve the image classification problem, then why is the CNN needed?

Here's a related question: What is the difference between a convolutional neural network and a regular neural network?.

Why are CNNs useful?
The main property of CNNs that make them more suitable than FFNNs to solve tasks where the inputs are images is that they perform convolutions (or cross-correlations).
Convolution
The convolution is an operation (more precisely, a linear operator) that takes two functions $f$ and $h$ and produces another function $g$. It's often denoted as $f \circledast h = g$, where $\circledast$ represents the convolution operation and $g$ is the function that results from the convolution of the functions $f$ and $h$.
In the case of CNNs,

$f$ is a multi-dimensional array (aka tensor) and it represents an image (or a processed version of an image, i.e. a feature map)
$h$ is a multi-dimensional array and it is called kernel (aka filter), which represents the learnable parameters of the CNN, and
$g$ is a processed version (with $h$) of $f$ and it is often called the feature map, so it's also a multi-dimensional array

Images as functions
To be consistent with the initial definition of the convolution, $f, h$, and $g$ can indeed be represented as functions.
Suppose that the input image is a greyscale (so it is initially represented as a matrix), then we can represent it as a function as follows
$$f: [a, b] \times [c, d] \rightarrow [0, 1],$$
i.e. given two numbers $x \in [a, b]$ and $y \in [c, d]$, $f$ outputs a number in the range $[0, 1]$, i.e. $f(x, y) = z$, where $z$ is the grayscale intensity of the pixel at coordinates $x$ and $y$. Similarly, the kernel $h$ and $g$ can also be defined as a function $h: [a, b] \times [c, d] \rightarrow [0, 1]$ and $g: [a, b] \times [c, d] \rightarrow [0, 1]$, respectively.
To be more concrete, if the shape of the image $f$ is $28 \times 28$, then it is represented as the function $f: [0, 28] \times [0, 28] \rightarrow [0, 1]$.
Note that the domain of the images doesn't have to range from $0$ to $28$ and the codomain doesn't have to range from $[0, 1]$. For example, in the case of RGB images, the codomain can also equivalently range from $0$ to $255$.
RGB images can also be represented as functions, more precisely, vector-valued functions, i.e.
$$
f(x, y) =
\begin{bmatrix}
r(x, y) \\
g(x, y) \\
b(x, y)
\end{bmatrix}
$$
where

$r: [a, b] \times [c, d] \rightarrow [0, 1]$ represents the red channel,
$g: [a, b] \times [c, d] \rightarrow [0, 1]$ represents the green channel, and
$b: [a, b] \times [c, d] \rightarrow [0, 1]$ represents the blue channel

Or, equivalently, $f: [a, b] \times [c, d] \times [0, 1]^3$.
Why is the convolution useful?
The convolution of an image with kernels (e.g. the median kernel) can be used to perform many operations.
For example, the convolution of a noisy image with the median filter can be used to remove noise from that image.

This is a screenshot of an image from this article, which you should read if you want to understand more about noise removal. So, on the left, there's the noisy image, and, on the right, there's the convolution of the median filter with the noisy image, which removes (at least, partially) the initial noise (i.e. those dots, which are due to the so-called "pepper and salt" noise).
The convolution of any image with the Sobel filter can be used to compute the derivatives of that image (both in the $x$ and $y$ directions, from which you can compute the magnitude and orientation of the gradient at each pixel of the image). See this article for more info.
So, in general, the convolution of an image with a kernel processes the image and the results (i.e. another image, which, in the case of CNNs, is called a feature map) can be different depending on the kernel.
This is the same thing as in CNNs. The only difference is that, in CNNs, the kernels are the learnable (or trainable) parameters, i.e. they change during training so that the overall loss (that the CNN is making) reduces (in the case CNNs are trained with gradient descent and back-propagation). For this reason, people like to say that CNNs are feature extractors or are performing feature extraction (aka feature learning or representation learning).
(Moreover, note that the convolution and cross-correlation are the same operations when the kernels are symmetric (e.g. in the case of a Gaussian kernel). In the case of CNNs, the distinction between convolution and cross-correlation doesn't make much sense because the kernels are learnable. You can ignore this if you are a beginner, but you can find more details here.)
Other useful properties
There are other useful properties of CNNs, most of them are just a consequence of the use of the convolution

Translation invariance (or equivariance), i.e. they can potentially find the same features (if you think of them as feature extractors) in multiple places of the image independently of their position, orientation, etc. See this answer for more details.

The equivalent FFNN has a lot more parameters (so CNNs may be less prone to overfitting)

They often use a sub-sampling operation  (known as pooling) to further reduce the number of parameters (which can possibly help to avoid overfitting) and introduce non-linearity.

Notes
Note that the FFNN can also be used to process images. It's just that the CNN is more suited to deal with images for the reasons described above.


text:
What is the intuition behind the attention mechanism?

Attention idea is one of the most influential ideas in deep learning. The main idea behind attention technique is that it allows the decoder to "look back” at the complete input and extracts significant information that is useful in decoding.

I am really having trouble understanding the intuition behind the attention mechanism. I mean how the mechanism works and how to configure.
In simple words (and maybe with an example), what is the intuition behind the attention mechanism?
What are some applications, advantages & disadvantages of attention mechanism?

Simply put, the attention mechanism is loosely inspired on well, attention. Consider we are attempting machine translation on the following sentence: "The dog is a Labrador." If you were to ask someone to pick out the key words of the sentence, i.e. which ones encode the most meaning, they would likely say "dog" and "Labrador." Articles like "the" and "a" are not as relevant in translation as the previous words (though they aren't completely insignificant). Therefore, we focus our attention on the important words.
Attention seeks to mimic this by adding attention weights to a model as trainable parameters to augment important parts of our input. Consider an encoder-decoder architecture such as the one Google Translate uses. Our encoder recurrent neural network (RNN) encodes our input sentence as a context vector in some vector space, which is then passed along to the decoder RNN which translates it into the target language. The attention mechanism scores each word in the input (via dot product with attention weights), then passes these scores through the softmax function to create a distribution. This distribution is then multiplied with the context vector to produce an attention vector, which is then passed to the decoder. In the example in the first paragraph, our attention weights for "dog" and "Labrador" would hopefully become larger in comparison to those for the other words during training. Note that all parts of the input are still considered since a distribution must sum to 1, just some elements have more effect on the output than others.
Below is a diagram from Towards Data Science that illustrates this concept very nicely in terms of an encoder-decoder architecture.

The advantages of attention is its ability to identify the information in an input most pertinent to accomplishing a task, increasing performance especially in natural language processing - Google Translate is a bidirectional encoder-decoder RNN with attention mechanisms. The disadvantage is the increased computation. In humans, attention serves to reduce our workload by allowing us to ignore unimportant features, however in a neural network, attention entails overhead as we are now  generating attention distributions and training our attention weights (we are not actually ignoring the unimportant features, just diminishing their importance).

Clarification: The input embedding is NOT used in the attention mechanism. The Attention Scores (usually called Alignment scores) are computed between the attention weights and the encoder hidden state (not the input embedding!). Similarly, the attention output is a linear combination between the attention distribution and encoder hidden states.


text:
What are the conditions of convergence of temporal-difference learning?
In reinforcement learning, temporal difference seem to update the value function in each new iteration of experience absorbed from the environment.
What would be the conditions for temporal-difference learning to converge in the end? How is it guaranteed to converge?
Any intuitive understanding of those conditions that lead to the convergence?

There are different TD algorithms, e.g. Q-learning and SARSA, whose convergence properties have been studied separately (in many cases).
In some convergence proofs, e.g. in the paper Convergence of Q-learning: A Simple Proof (by Francisco S. Melo), the required conditions for Q-learning to converge (in probability) are the Robbins-Monro conditions

$\sum_{t} \alpha_t(s, a) = \infty$
$\sum_{t} \alpha_t^2(s, a) < \infty,$

where $\alpha_t(s, a)$ is the learning rate at time step $t$ (that can depend on the state $s$ and action $a$), and that each state is visited infinitely often.
(The Robbins-Monro conditions (1 and 2) are due to Herbert Robbins and Sutton Monro, who started the field of stochastic approximation in the 1950s, with the paper A Stochastic Approximation Method. The fields of RL and stochastic approximation are related. See this answer for more details.)
However, note again that the specific required conditions for TD methods to converge may vary depending on the proof and the specific TD algorithm. For example, the Robbins-Monro conditions are not assumed in Learning to Predict by the Methods of Temporal Differences by Richard S. Sutton (because this is not a proof of convergence in probability but in expectation).
Moreover, note that the proofs mentioned above are only applicable to the tabular versions of Q-learning. If you use function approximation, Q-learning (and other TD algorithms) may not converge. Nevertheless, there are cases when Q-learning combined with function approximation converges. See An Analysis of Reinforcement Learning with Function Approximation by Francisco S. Melo et al. and SBEED: Convergent Reinforcement Learning with Nonlinear Function Approximation by Bo Dai et al.

Hi, thanks for the reply! Is there any requirement on the environment? What if the environment is totally random, and for each state, action, there is not even a fixed value in essence?

@MJeremy I don't know what you mean exactly by "totally random". There are some restrictions on the environment in certain proofs. For example, in the paper Convergence of Q-learning: A Simple Proof, F. Melo e.g. assumes that the reward function is deterministic. So, the assumptions probably vary from one proof to the other. It's probably a better idea that you read the specific papers that provide the proofs, if you want to know more details.


text:
How to train a reinforcement learning agent from raw pixels?
How would you train a reinforcement learning agent from raw pixels?
For example, if you have 3 stacked images to sense motion, then how would you pass them to neural networks to output Q-learning values?
If you pass that batch output, it would be a batch of values, so from here it is impossible to deduce which ones are the true Q-values for that state.
Currently, I am watching a YouTuber: Machine Learning with Phil, and he did it very differently. On the 13th minute, he defined a network that outputs a batch of values rather than Q-values for 6 states. In short, he outputs a matrix rather than a vector.

How would you train a reinforcement learning agent from raw pixels? For example, if you have 3 stacked images to sense motion, then how would you pass them to neural networks to output Q-learning values?

A Convolutional Neural Network (CNN) structure is a standard neural network architecture when working with 2D pixel input in reinforcement learning, and it is the technique used in the original DQN paper (see paragraphs 1 & 3 of Section 4.1 of https://arxiv.org/abs/1312.5602). CNNs typically take 3-dimensional input, where the first two dimensions are height and width of your images, and the third is rgb color. The technique in the paper was to convert each RGB frame (or image) to greyscale format (so it has only 1 color channel/dimension instead of 3) and instead use the rgb_color dimension as a frames dimension that is indexed by each stacked frame.

Currently, I am watching a YouTuber: Machine Learning with Phil, and he did it very differently. On the 13th minute, he defined a network that outputs a batch of values rather than Q-values for 6 states. In short, he outputs a matrix rather than a vector.

Later in the tutorial series, he most likely will discuss the training of the neural network. During training, you need to find the q-values of a batch of sets of stacked frames. Specifically, each element of the batch is a set of stacked frames. In other words, a set of stacked frames is treated as a single observation, so a batch of sets of stacked frames is a batch of observations.
To find these q-values, you will perform a forward pass of the batch of observations through the neural network. A forward pass of a single observation (set of stacked frames) through the neural network yields a vector of q-values (one for each action). Thus, a forward pass of a batch of observations (batch of stacked frames) will yield a matrix of q-values (one vector of q-values for each observation (or set of stacked frames)). This technique is used because many standard neural network libraries are designed to perform a forward pass on a batch of inputs through the neural network much faster than performing a forward pass on each input separately.


text:
Why is there an inconsistency between my calculations of Policy Iteration and this Sutton & Barto's diagram?
In equation 4.9 of Sutton and Barto's book on page 79, we have (for the policy iteration algorithm):
$$\pi'(s) = arg \max_{a}\sum_{s',r}p(s',r|s,a)[r+\gamma v_{\pi}(s')]$$
where $\pi$ is the previous policy and  $\pi'$ is the new policy. Hence in iterations $k$ it must mean
$$\pi_{k+1}(s) = arg \max_{a}\sum_{s',r}p(s',r|s,a)[r+\gamma v_{\pi_{k}}(s')]$$
But in the example given in the same book on page 77 we have:

Now, for the concerned state marked in red -

$v_{\pi_{1}} = -1$ for all four surrounding states
$r = -1$ for all four surrounding states
$p(s',r|s,a) = 1$ for all four surrounding states
$\pi_{2}(s) = arg \max_{a}[1*[-1+1*-1],1*[-1+1*-1],1*[-1+1*-1],1*[-1+1*-1]]$
$\pi _{2}(s) = arg \max_{a}(-2,-2,-2,-2)$

Hence this should give us a criss-cross symbol (4 directional arrow) in $\pi_{2}$(s) but here a left arrow symbol is given.
What's wrong with my calculations?

Your calculations are correct, but you have misinterpreted the equations and the diagram. The index $k$ in $v_k$ for the diagram refers to the policy evaluation update iteration only, and is not related to the policy update step (which uses the notation $\pi'$ and does not mention $k$).
Policy improvement consists of multiple sweeps through states to fully evaluate the current policy and estimate the value function for it. After that, it updates the policy in a separate policy improvement step. There are two loops - an inner loop indexed by $k$ in the equations and diagram, plus an outer loop which is not given an index notation.
The diagram is not showing incremental $\pi'$ policies from outer loops over policy iteration. Instead it is showing "Greedy Policy w.r.t. $v_k$" steps in the inner loop - you can think of that as the policy $\pi'$ that you would get inside the first outer loop, if you terminated the policy evaluation stage after that iteration $k$ of the inner loop.
The diagram only shows behaviour of policy iteration for a single outer loop. It demonstrates at least two interesting things:

In the case of this very simple environment, if you ran a single outer loop with long enough policy evaluation stage ($k \ge 3$) you would find the optimal policy.
Even before the value function estimate is close to convergence (with a high $k$), the policy that could be derived from the new estimates could be used to improve the policy. That leads to the idea of the value iteration method.


text:
Why does the state-action value function, defined as an expected value of the reward and state value function, not need to follow a policy?
I often see that the state-action value function is expressed as:
$$q_{\pi}(s,a)=\color{red}{\mathbb{E}_{\pi}}[R_{t+1}+\gamma G_{t+1} | S_t=s, A_t = a] = \color{blue}{\mathbb{E}}[R_{t+1}+\gamma v_{\pi}(s') |S_t = s, A_t =a]$$
Why does expressing the future return in the time $t+1$ as a state value function $v_{\pi}$ make the expected value under policy change to expected value in general?

Here is a related question.

Let's first write the state-value function as
$$q_{\pi}(s,a) = \mathbb{E}_{p, \pi}[R_{t+1} + \gamma G_{t+1} | S_t = s, A_t = a]\;,$$
where $R_{t+1}$ is the random variable that represents the reward gained at time $t+1$, i.e. after we have taken action $A_t = a$ in state $S_t = s$, while $G_{t+1}$ is the random variable that represents the return, the sum of future rewards. This allows us to show that the expectation is taken under the conditional joint distribution $p(s', r \mid s, a)$, which is the environment dynamics, and future actions are taken from our policy distribution $\pi$.
As $R_{t+1}$ depends on $S_t = s, A_t = a$ and $p(s', r \mid s, a)$,  the only random variable in the expectation that is dependent on our policy $\pi$ is $G_{t+1}$, because this is the sum of future reward signals and so will depend on future state-action values. Thus, we can rewrite again as
$$q_{\pi}(s,a) = \mathbb{E}_{p}[R_{t+1} + \gamma \mathbb{E}_{\pi}[ G_{t+1} |S_{t+1} = s'] | S_t = s, A_t = a]\;,$$
where the inner expectation (coupled with the fact its inside an expectation over the state and reward distributions) should look familiar to you as the state value function, i.e.
$$\mathbb{E}_{\pi}[ G_{t+1} |S_{t+1} = s'] = v_{\pi}(s')\;.$$
This leads us to get what you have
$$q_{\pi}(s,a) = \mathbb{E}_{p}[R_{t+1} + \gamma v_{\pi}(s') | S_t = s, A_t = a]\;,$$
where the only difference is that we have made clear what our expectation is taken with respect to.
The expectation is taken with respect to the conditional joint distribution $p(s', r \mid s, a)$, and we usually include the $\pi$ subscript to denote that they are also taking the expectation with respect to the policy, but here this does not affect the first term as we have conditioned on knowing $A_t = a$ and only applies to the future reward signals.

I now this post was closed a while ago, but I hope someone sees this.. How do you arrive at $E_\pi[G_{t+1} | S_{t+1} = s']$ in the second paragraph?

@mNugget because $R_{t+1}$ does not depend on the policy, since we have conditioned on $S_t, A_t$. This means that the only term which depends on the policy is the future returns $G_{t+1}$. We write the expectation explicitly conditioned on the $S_{t+1}$ so it resembles the value function, but it is valid because the outer expectation is also wrt to the dynamics functions $p$, so we are averaging over all possible next states.

David Ireland gives a fantastic answer, and I will provide an intuitive and gentle (but less rigorous) answer for those who are unfamiliar with the relevant statistical concepts.
Next reward $R_{t+1}$: The next reward $R_{t+1}$ is solely dependent on the current state $S_t$ and action $A_t$. It is only dependent on the policy because the policy details the probability distribution of actions given a state. Since we assume that the current state and action are given when calculating the expectation $\left(S_t = s, A_t = a\right)$, then the policy does not give us any new information, and therefore the next reward is independent of the policy.
Return $G_{t+1}$: By definition, $v_{\pi}(s') = \mathbb{E}_{\pi}[G_{t+1}|S_{t+1} = s']$. The value function is unaffected by sampling actions from the policy in the outer expectation $\left(\mathbb{E}_{\pi}[v_{\pi}(s')] = \mathbb{E}[v_{\pi}(s')]\right)$ since the value function is an expectation under the policy, and hence samples actions from the policy already.
Dropping $\pi$ from $\mathbb{E}_{\pi}$: The expectation under the current policy samples next states and rewards from the environment and also samples actions from our policy $\pi$. Because the next reward is independent of the policy given the current state and action, and because the value function is unaffected by sampling actions from the policy in the outer expectation, we can simply drop the policy from the outer expectation (the outer expectation will still sample next states and rewards from the environment).


text:
Can I apply DQN or policy gradient algorithms in the contextual bandit setting?
I have a problem which I believe can be described as a contextual bandit.
More specifically, in each round, I observe a context from the environment consisting of five continuous features, and, based on the context, I have to choose one of the ten available actions. The actions do not influence the next context.
Based on the above I have the following questions:

Is this a contextual bandit or an MDP with a discount equal to zero (one step RL)? I have read that, in contextual bandits, we receive a different context for each action and I am a little bit confused.
Can I use the DQN algorithm with TD Target only the observed reward instead of the reward plus the predicted value of the next state?
Can I use a policy gradient algorithm, like REINFORCE or A2C? If yes, should I use a baseline and what this baseline should be?
I have seen in the literature that there are some algorithms for contextual bandits such as LinUCB, LinRel, NeuralBandit, etc. And I am wondering why the DQN, A2C and REINFORCE algorithms, which seem to work well in MDP setting, are not used in contextual bandits, given the fact that this problem can be described as an MDP with a discount equal to zero?

The comments have been moved to chat.

MDPs are strict generalisations of contextual bandits, adding time steps and state transitions, plus the concept of return as a measure of agent performance.
Therefore, methods used in RL to solve MDPs will work to solve contextual bandits. You can either treat a contextual bandit as a series of 1-step episodes (with start state chosen randomly), or as a continuous problem with discount factor zero.

Can I use the DQN algorithm with TD Target only the observed reward instead of the reward plus the predicted value of the next state?

Yes. That's identical mathematically to having a discount of zero, or having 1-step episodes.

Can I use a policy gradient algorithm, like REINFORCE or A2C? If yes, should I use a baseline and what this baseline should be?

Yes. Once converted to an MDP, you can use the same baselines in these algorithms as normal (A2C's use of advantage instead of action value is already a baseline). Generally adding a baseline can help reduce variance, so it may still help when applying RL to contextual bandit problems.

I have seen in the literature that there are some algorithms for contextual bandits such as LinUCB, LinRel, NeuralBandit, etc. And I am wondering why the DQN, A2C and REINFORCE algorithms, which seem to work well in MDP setting, are not used in contextual bandits

There are a couple of reasons that contextual bandit problems are not solved using RL techniques more often:

The goal in contextual bandits is commonly focused on creating a highly efficient online learner that minimises regret. Regret is the long term difference in total reward between always exploiting the best action choice compared to the exploration necessary to find it. Some RL solvers - e.g. DQN - are poor by this metric.
The lack of timesteps and state transitions can be used in algorithm design to be more efficient.
Improvements to RL methods designed to help with sparse rewards and the assignment problem in MDPs are pointless for contextual bandits and may be wasteful or even counter-productive.

Some RL algorithms do resolve to be nearly identical to their contextual bandit counterparts, and have the same performance characteristics e.g. REINFORCE with baseline for 1-step episodes is essentially the Contextual Gradient Bandit algorithm.
It is also worth noting than many problem domains where contextual bandit algorithms do well - e.g. website recommendations and advertising - have research showing that that a more sophisticated MDP model and RL-like approach can do even better. Although that is not quite the same as your question, it typically means extending the model so that timesteps and state transitions are meaningful.

thank you very much for your answer.

Can you please share a link that describes the Contextual Gradient Bandit algorithm?
I believe that the regret performance of DQN has to do with the exploration strategy. If we use a more sophisticated exploration (for example https://arxiv.org/pdf/1606.01868.pdf) the performance will be better.

Thank you Neil for the link of the Contextual Gradient Bandit algorithm. Do you have a link where a counterpart of DQN is applied in Contextual Bandit setting? Finally, I am  struggling to understand what the baseline should be. For example, in REINFORCE the baseline is the average returns of m trajectories by following the policy. By analogy, in Contextual Bandit setting, the baseline might be just the average reward of the policy. Correct?

@gnikol No I don't have such a link, sorry. Once you convert to contextual bandit setting to MDP setting, there is no difference to a DQN used normally, so I am not sure what you are hoping to see. The same answer for REINFORCE - convert CB to MDP and use the same baseline (return) - yes that is the same as average reward, but if you are spending all your time trying to adapt the algorithm to something that is not quite an MDP, you'd be better off just using a contextual bandit solver instead anyway.


text:
Why does AlphaGo Zero select move based on exponentiated visit count?
From the AlphaGo Zero paper, AlphaGo Zero uses an exponentiated visit count from the tree search.
Why use visit count instead of the mean action value $Q(s, a)$?

The answer is surprisingly hidden in the original AlphaGo paper:

At the end of search AlphaGo selects the action with maximum visit count; this
  is less sensitive to outliers than maximizing action value.

Unfortunately, there did not appear to be further details in the paper or in the related reference. The root child node (corresponding to an action) with maximum visit count is fittingly known as the robust child, as described here and referenced in a MCTS survey here.

One obvious scenario where mean actual value falls short is when the count is small (say, 1).


text:
Should I use exploration strategy in Policy Gradient algorithms?
In policy gradient algorithms the output is a stochastic policy - a probability for each action.
I believe that if I follow the policy (sample an action from the policy) I make use of exploration because each action has a certain probability so I will explore all actions for a given state.
Is it beneficial or is it common to use extra exploration strategies, like UCB, Thompson sampling, etc. with such algorithms?

I believe that if I follow the policy (sample an action from the policy) I make use of exploration because each action has a certain probability so I will explore all actions for a given state.

Yes, having a stochastic policy function is the main way that a lot of policy gradient methods achieve exploration, including REINFORCE, A2C, A3C.

Is it beneficial or is it common to use extra exploration strategy like UCB, Thompson sampling etc. n such algorithms?

It can be, but needs to be done carefully, as the gradient sampling for the policy function is different. Many policy gradient methods are strictly on-policy and will not work if you simply add extra exploration. It is relatively straightforward to adjust the critic part of actor-critic methods by using e.g.  Q learning update rules for it. However, the gradient of the policy function is trickier.
There are some policy gradient methods that do work with a separate, tunable, exploration function. Deep Deterministic Policy Gradient (DDPG) may be of interest to you - as per the title, it works with a deterministic policy function, and exploration is achieved by adding a separate noise function on top. The sampling for policy gradient is then corrected for being off-policy.

Note this is an area where I have not delved into the maths in any depth, so I cannot help with questions about applicability or implementation of any specific noise function.

Neil Slater's answer is very nice, but I have a couple more suggestions:

You can use entropy regularization. Basically, you modify your loss function to penalize low policy entropy (so less loss for more entropy) which should prevent your policy from becoming "too deterministic" too early.
You can also try maximum-entropy methods, like SAC, which employ a different strategy for promoting policy entropy.


text:
How does $\mathbb{E}$ suddenly change to $\mathbb{E}_{\pi'}$ in this equation?
In Sutton-Barto's book on page 63 (81 of the pdf):
$$\mathbb{E}[R_{t+1} + \gamma v_\pi(S_{t+1}) \mid S_t=s,A_t=\pi'(s)] = \mathbb{E}_{\pi'}[R_{t+1} + \gamma v_\pi(S_{t+1}) \mid S_{t} = s]$$
How does $\mathbb{E}$ suddenly change to $\mathbb{E}_{\pi'}$ and the $A_t = \pi'(s)$ term disappears?
Also, in general, in the conditional expectation, which distribution do we compute the expectation with respect to? From what I have seen, in $\mathbb{E}[X \mid Y]$, we always calculate the expected value over distribution $X$.

Can you additionally provide a reference to the equation number, so that it's found more easily?

Its in a proof given below equation 4.8

Also, in general, in the conditional expectation, which distribution do we compute the expectation with respect to? From what I have seen, in $\mathbb{E}[X|Y]$, we always calculate the expected value over distribution $X$.

No, for $\mathbb{E}[X|Y]$ we take expectation of $X$ with respect to the conditional distribution $X|Y$, i.e.
$$\mathbb{E}[X|Y] = \int_\mathbb{R} x p(x|y)dx\;;$$
where $p(x|y)$ is the density function of the conditional distribution. If your random variables are discrete then replace the integral with a summation. Also note that $\mathbb{E}[X|Y]$ is still a random variable in $Y$.

How does $\mathbb{E}$ suddenly change to $\mathbb{E}_{\pi '}$ and the $A_t = \pi '(s)$ term disappears?

This is because in this instance $\pi '(s)$ is a  deterministic policy, i.e. in state $s$ the policy will take action $b$ with probability 1 and all other actions with probability 0. NB: this is the convention used in Sutton and Barto to denote a deterministic policy.
Without loss of generality, assume that $\pi'(s) = b$. The implication of this is that in the first expectation we have
$$\mathbb{E}[R_{t+1} + \gamma v(S_{t+1}) | S_t = s, A_t = \pi'(s) = b] = \sum_{s',r}p(s',r|s,a=b)(r + \gamma v(s'))\;,$$
and in the second expectation we have
$$\mathbb{E}_{\pi'}[R_{t+1} + \gamma v(S_{t+1}) | S_t = s] = \sum_a\pi'(a|s)\sum_{s',r}p(s',r|s,a)(r + \gamma v(s'))\;;$$
However, we know that $\pi'(a|s) = 0 \; \forall a \neq b$, so this sum over $a$ would equal 0 for all $a$ except when $a=b$, in which case we know that $\pi'(b|s) = 1$, and so the expectation becomes
$$\mathbb{E}_{\pi'}[R_{t+1} + \gamma v(S_{t+1}) | S_t = s] = \sum_{s',r}p(s',r|s,a=b)(r + \gamma v(s'))\;;$$
and so we have equality of the two expectations.

This conversation has been moved to chat.


text:
If the current state is $S_t$ and the actions are chosen according to $\pi$, what is the expectation of $R_{t+1}$ in terms of $\pi$ and $p$?
I'm trying to solve exercise 3.11 from the book Sutton and Barto's book (2nd edition)

Exercise 3.11 If the current state is $S_t$ , and actions are selected according to a stochastic policy $\pi$, then what is the expectation of $R_{t+1}$ in terms of $\pi$ and the four-argument function $p$ (3.2)?

Here's my attempt.
For each state $s$, the expected immediate reward when taking action $a$ is given in terms of $p$ by eq 3.5 in the book:
$$r(s,a) = \sum_{r \in R} r \, \sum_{s'\in S} p(s',r \mid s,a) = E[R_t \mid S_{t-1} = s, A_{t-1} = a] \tag{1}\label{1}$$
The policy $\pi(a \mid s)$, on the other hand, gives the probability of taking action $a$ given the state $s$.
Is it possible to express the expectation of the immediate reward over all actions $A$ from the state $s$ using (1) as
$$E[R_t \mid S_{t-1} = s, A] = \sum_{a \in A} \pi(a \mid s) r(a,s)  \tag{2}\label{2}$$
?
If this is valid, is this also valid in the next time step
$$E[R_{t+1} \mid S_{t} = s, A] = \sum_{a \in A} \pi(a \mid s) r(a, s) \tag{3}\label{3}$$
?
If (2) and (3) are OK, then
$$E[R_{t+1} \mid S_{t} = s, A] = \sum_{a \in A} \pi(a \mid s) \sum_{r \in R} r \, \sum_{s'\in S} p(s',r \mid s,a)$$

First note that $\mathbb{E}[R_{t+1} |S_t=s] = \sum_{s',r}rm(s',r|s)$ where $m(\cdot)$ is the mass function for the joint distribution of $S_{t+1},R_{t+1}$.
If you are currently in state $S_t$ and we condition on taking action $a$ then the expected reward at time $t+1$ is given as follows:
\begin{align} \mathbb{E}[R_{t+1} | S_t = s, A_t=a] & = \sum_{s',r}rp(s'r|s,a)\;.
\end{align}
However, action $A_t$ is taken according to some stochastic policy $\pi$ so we need to marginalise this out of our expectation by using the tower law - i.e. we take
$$\mathbb{E}_{A_t \sim \pi}[\mathbb{E}[R_{t+1} | S_t = s, A_t=a]|S_t = s] = \sum_a \pi(a|s)\sum_{s',r}rp(s'r|s,a) = \mathbb{E}[R_{t+1} | S_t = s]\;.$$
To see why this holds we can re-write using some arbitrary mass functions $f(\cdot),h(\cdot),g(\cdot),m(\cdot)$ as
$$\pi(a|s)p(s'r|s,a) = \frac{f(a,s)}{g(s)} \times \frac{h(s',r,a,s)}{f(a,s)} = m(s',r,a|s)\;,$$
so when we would end up with (after re-arranging the summations)
$$\sum_{s',r}r \sum_{a}m(s',r,a|s) = \sum_{s',r}r m(s',r|s) = \mathbb{E}[R_{t+1}|S_t = s]\;;$$
as required.
NB: what you have done is mostly correct except be careful when going from (2) to (3). They are exactly the same equation except for the time stamps, which means you would have to change the time stamps in your $r(s,a)$. Note that when you are at time step $t$ you take your action $A_t$ from your current $S_t$ to transition into state $S_{t+1}$ and then receive reward $R_{t+1}$ (and the next state).

How is the equation preceding the mention of "tower law" equal to the equation following "tower law"? Can you share some other references that help understanding this transition?

They are not equal. The latter is the expected value of the former over the conditional action distribution $\pi$. It is a standard use of the tower property which I’ve linked, no other resources should be necessary.

@David Why at the first summand you used the mass m(.) and in the next you used p(.) for the joint?

@David One more thing, when you took the expectation $\mathbb{E}{A_t \sim \pi} [\mathbb{E}[R{t+1}| S_t=s,A_t=a] | S_t=s]$, $A_t$ is fixed to $a$, in the same way of the last equation, but them you make it vary with the outer sum on $a$, this seems a little confusing, unless $\sum_{s',r}rp(s'r|s,a)$ is not meant to be a quantity, but actually a function of $a$ and $s$.


text:
Why do we also need to normalize the action's values on continuous action spaces?
I was reading here tips & tricks for training in DRL and I noticed the following:

always normalize your observation space when you can, i.e., when you know the boundaries
normalize your action space and make it symmetric when continuous (cf potential issue below) A good practice is to rescale your actions to lie in [-1, 1]. This does not limit you as you can easily rescale the action inside the environment

I am working on a discrete action space but it is quite difficult to normalize my states when I don't actually know the full range for each feature (only an estimation).
How does this affect training? And more specifically, why on continuous action spaces we need to normalize also the action's values?

Notably, these two tips/tricks are useful because we are assuming the context of deep reinforcement learning here, as you pointed out. In DRL, the RL algorithm is guided in some fashion by a deep neural network, and the reasons for normalizing stem from the gradient descent algorithm and the architecture of the network.

How does this affect training?

An observation from the observation space is often used as an input to a neural network in DRL algorithms, and normalizing the input to neural networks is beneficial for many reasons (e.g. increases convergence speed, aids computer precision, prevents divergence of parameters, allows for easier hyperparameter tuning, etc.). These are standard results in DL theory and practice, so I won't provide details here.

And more specifically, why on continuous action spaces we need to normalize also the action's values?

Most popular discrete action space DRL algorithms (e.g. DQN) have one output node for each possible action in the neural net. The value of the output node may be a q-value (value-based algorithm) or a probability of taking that action (policy-based algorithm).
In contrast, a continuous action space DRL algorithm simply cannot have an output node for each possible action, as the action space is continuous. The output is usually the actual action to be taken by the agent or some parameters that could be used to construct the action (e.g. PPO outputs a mean and standard deviation and then an action is sampled from the corresponding Gaussian distribution - this phenomenon is mentioned in your linked reference). Therefore, normalizing the action space of a DRL algorithm is analogous to normalizing the outputs of the corresponding neural network, which is known to increase training speed and prevent divergence. Again, a quick search will yield some good resources if you are interested in these results.


text:
What is meant by the rank of the scoring function here?
I've been reading the paper Reinforcement Knowledge Graph Reasoning for Explainable Recommendation (by Yikun Xian et al.) lately, and I don't understand a particular section:

Specifically, the scoring function $f((r,e)|u)$ maps any edge $(r,e)$ to a real-valued score conditioned on user $u$. Then, the user-conditional pruned action space of state $s_t$ denoted by $A_t(u)$ is defined as:
$A_t(u) = \{(r,e)| rank(f((r,e)|u))) \leq \alpha ,(r,e) \in A_t\} $
where $\alpha$ is a predefined integer that upper bounds the size of the action space.

Details about the scoring function can be found in the attached paper.
What I don't understand is: What does rank mean, here? Is the thing inside of it a matrix?
It would be great if someone could explain the expression for the user conditional pruned action space in greater detail.

$\text{rank}(f((r,e)|u))$ in $A_t(u)$ means to compute the value of scoring function $f$ for all pairs $(r,e)\in A_t$ which are conditioned by $u$, then sort them in a descending order. The rank of the $f((r,e)|u)$ in this order is equal to $\text{rank}(f((r,e)|u))$. Hence $\text{rank}(f((r,e)|u)) \leqslant \alpha$ means to select the $\alpha$ top most scored pairs.