text:
What is a result of a cross validation process?
I am trying to determine the result of a cross validation process. Is it just a set of standalone models which is produced after each cross-validation round, or is there some kind of final model which is "aware" of all the models created by the Kfold rounds and benefits from them?

The main purpose of a validation procedure is to obtain an accurate estimate of model performance.  In brief, in a typical hold out validation, the total dataset is split into a training and test set.  A model is then trained on a training set; however, the model's performance (e.g., accuracy) is evaluated on the test set.  The idea here is that estimating performance on the same dataset that you used to train the model is obviously going to give you a biased estimate of performance.  The performance estimate on the test set is supposed to be a more accurate / unbiased representation of how the model will perform when deployed.  However, the randomness of the train-test split may yield spurious results, especially when datasets are small.
This is where cross-validation comes in.  Cross-validation repeats this procedure multiple times using different train-test splits on the same dataset.  The performance on the different test sets are then averaged over all the iterations giving a more accurate estimate (along with confidence bounds if you calculate the standard deviation) for the model's performance.  This averaging approach is much less dependent on a single train-test split, which by chance may not have been representative of the distribution of the overall dataset.
Thus, to answer your question, a cross-validation generates multiple models on (overlapping) subsets of data that are not 'aware" of each other.  A k-fold cross-validation, for example, will execute k iterations, generating a new model at each iteration.  This scikit learn user guide explains cross-validation (and its many variations) very well.
The cross-validation procedure, as mentioned, is used to get an accurate estimate of model performance in the real world.  It's main purpose is not to generate a final model.  The final model can be generated by training on the total dataset, but you would not then estimate accuracy by evaluating the performance of that model on the total dataset (as explained this would be a highly biased estimate).  Instead, use the average accuracy from the cross-validation.
As an aside, if you decide to save these models after each iteration, you can combine them to make an ensemble model.  However, that is not technically a part of the cross-validation procedure.

Thank you. Things start getting more clear thanks to your answer.
Still, probably misunderstood something previously, not regarding the cross validation but the "simple" validation.
Please, correct me if  if I am wrong in the following:
A-during an epoch the weighs are adjusted each batch as I understand. The adjustion of weights after each batch is based on training set ground truth -  nothing to do with validation set here here, right?
B-If A is right, than, the validation is being done at the end of each epoch, but not with a goal to adjust weight, but in order to estimate. Right?

My pleasure.  It seems like you are referring to training of neural networks here by your use of "epoch".  The same principles apply.  A)  and  B) are correct.  Generally, the data are split into train-validation-test sets for training neural networks [1].

After each epoch, the performance of the model is assessed on the validation set.  The purpose is to assess for over/underfitting.  These articles will help you understand those concepts [1, 2, 3]

Thank you again. Your explanations are very clear.


text:
Why is my DQN agent not converging to a constant reward?
I'm currently training a DQN agent. I use an epsilon greedy exploration strategy where I decay the epsilon value linearly until it reaches 0 over 300 episodes. For the rest of the remaining 50 episodes, epsilon is always 0. Since the value is 0, I thought that the agent would always select the same actions throughout the training but that does not seem to happen since the reward of the last 50 episodes is not exactly the same as can be seen by the graph below. The blue graph is a plot of the reward for each episode and the orange one is the average reward of the last 100 episodes.

Is increasing the number of episodes after epsilon reaches 0 a correct solution for this? I have not tried this as each episode takes approximately 20 seconds to complete, so the training can become really long. Thanks in advance!

Annealing $\epsilon$ to 0 in $\epsilon$-greedy DQN is intended to reduce the exploration capability of the DQN agent, but it does not prevent the DQN agent from continuing to learn. Typically, DQN incorporates a replay buffer that stores previous experience tuples of the form $(\mbox{state},\ \mbox{action},\ \mbox{reward},\ \mbox{next state})$. The DQN agent is still able to store new experience tuples and learn from all stored experience tuples when $\epsilon=0$. As the agent continues to learn, its policy may change, and even a slight change in policy may alter its choice of actions - this phenomenon appears to be what your graph is displaying.
To answer your question, most deep reinforcement learning (DRL) algorithms have numerous moving parts, and from what I've read in the literature, convergence to a fixed policy over consecutive episodes has not traditionally been a goal when training DRL algorithms. I personally would say that your chart shows fantastic results, as it exhibits great stability with negligible fluctuations in the reward graph when $\epsilon=0$. If you are absolutely determined to reach a fixed policy or reward graph during training, it would be helpful to know the specifics of the underlying environment, possibly by asking another question on this site with all of the details.

source: Stack Exchange

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

sort: votes


text:
$E_{\pi}[R_{t+1}|S_t=s,A_t=a] = E[R_{t+1}|S_t=s,A_t=a]$?
I would like to solve the first question of Exercise 3.19 from Sutton and Barto:

Exercise 3.19 The value of an action, $q_{\pi}(s, a)$, depends on the expected next reward and
the expected sum of the remaining rewards. Again we can think of this in terms of a
small backup diagram, this one rooted at an action (state–action pair) and branching to
the possible next states:

Give the equation corresponding to this intuition and diagram for the action value,
$q_{\pi}(s, a)$, in terms of the expected next reward, $R_{t+1}$, and the expected next state value,
$v_{\pi}(S_{t+1})$, given that $S_t =s$ and $A_t =a$. This equation should include an expectation but
not one conditioned on following the policy.

I'm not sure how to write this equation so that it is not conditioned on $\pi$.  It's clear to me that
\begin{align*}
q_{\pi}(s, a) &= E_{\pi}[G_{t}|S_t=s,A_t=a]\\
& = E_{\pi}[R_{t+1} + \gamma G_{t+1}|S_t=s,A_t=a]\\
& = E_{\pi}[R_{t+1}|S_t=s,A_t=a] + E_{\pi}[\gamma G_{t+1}|S_t=s,A_t=a].
\end{align*}
The second term in the last expression  evaluates to (from Exercise 3.13) $$\sum_{s'}\gamma v_{\pi}(s')P(S_{t+1}=s'|A_t=a,S_t=s).$$
Therefore, I'm left with the first term which is $E_{\pi}[R_{t+1}|S_t=s,A_t=a]$.
Question: Can I write the term without the subscript as $$E_{\pi}[R_{t+1}|S_t=s,A_t=a] = E[R_{t+1}|S_t=s,A_t=a]?$$
My reasoning is that the expected reward, given we know what $A_t$ is, does not depend on $\pi$.

Question: Can I write it without the subscript? So $$E_{\pi}[R_{t+1}|S_t=s,A_t=a] = E[R_{t+1}|S_t=s,A_t=a]$$

Yes, your reasoning is sound, there is no need to condition the expectation on the policy, because the policy has no influence on the expected value of $R_{t+1}$ given that there is already a condition on $A_t=a$, and $a$ is provided as an argument.
This only works because you have split off the expected reward to evaluate separately. Overall, the value of $q_\pi$ does depend on the policy, and this is shown by using $v_\pi$ in the second term.

@Neil Slater In the expected answer it is said that
"This only works because you have split off the expected reward to evaluate separately. Overall, the value of $q_{\pi}$
does depend on the policy, and this is shown by using $v_{\pi}$
in the second term."
However, the following solution (from solution manual) does not support this:

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


text:
What is the probability of selecting the greedy action in a 0.5-greedy selection method for the 2-armed bandit problem?
I'm new to reinforcement learning and I'm going through Sutton and Barto. Exercise 2.1 states the following:

In $\varepsilon$-greedy action selection, for the case of two actions and $\varepsilon=0.5$, what is the probability that the greedy action is selected?

They describe the $\varepsilon$-greedy method on pages 27-28 as follows:

...behave greedily most of the time, but every once in a while,  say with small probability $\varepsilon$, instead select randomly from among all the actions with equal probability...

The above method makes the agent select an action randomly "every once in a while" from the action space uniformly with probability $\varepsilon$. I find the question imprecise since we don't know the "once in a while" in this exercise (i.e. is it once every $50$ timesteps? every time step?). If it's for every timestep, isn't it like a Bernouli problem where the parameter is $0.5$? I'd say that the agent has a $0.5$ chance to select a greedy action but I'm not sure at all.

I read section 2.2 of Sutton and Barto, and I understand your confusion: the $\epsilon$-greedy algorithm is not defined precisely on page 27-28. Selecting an action randomly "every once in awhile" with probability $\epsilon$ means selecting an action randomly with probability $\epsilon$ at each timestep and selecting an action greedily with probability $1-\epsilon$ at each timestep. This definition is standard and will be clear as you progress through the book and other relevant literature. For reference, the $\epsilon$-greedy algorithm is used in the pseudocode on page 32 of Sutton and Barto.
The key distinction in this problem is that it's asking for the probability that the greedy action is selected, NOT the probability that an action is selected greedily. Specifically, the greedy action can be selected when the agent selects an action randomly because the greedy action is in the action space and the entire action space is sampled uniformly when selecting an action randomly.
Since $\epsilon=0.5$, the agent will select an action greedily 50% of the time, which will 100% of the time be the greedy action. The agent will select an action randomly the other 50% of the time. Since there are two actions in the action space, the greedy action will be selected 50% of the time when the agent selects an action randomly. Therefore, the probability that the greedy action is selected at any single timestep is as follows:
\begin{align}
 &p(\mbox{greedy action}) \\
=\ &p(\mbox{greedy action AND greedy selection}) + p(\mbox{greedy action AND random selection})\\
=\ &p(\mbox{greedy selection}) \cdot p(\mbox{greedy action}\ |\ \mbox{greedy selection}) \\
&\hspace{1em}+ p(\mbox{random selection})\cdot p(\mbox{greedy action}\ |\ \mbox{random selection})\\
=\ &(1-\epsilon) \cdot p(\mbox{greedy action}\ |\ \mbox{greedy selection}) + \epsilon \cdot p(\mbox{greedy action}\ |\ \mbox{random selection})\\
=\ &0.5 \cdot p(\mbox{greedy action}\ |\ \mbox{greedy selection}) + 0.5 \cdot p(\mbox{greedy action}\ |\ \mbox{random selection})\\
=\ &0.5 \cdot 1 + 0.5 \cdot 0.5 \\
=\ &0.5+ 0.25 \\
=\ &0.75.
\end{align}

Thank you for your explanation, it's very clear and helpful. So the key difference that I've missed is between the action selection and the greedy selection. Thanks again !

could it be equal to $1$ if both actions yield the same reward, i.e. both actions are greedy?


text:
Why does the Atari Gym Amidar environment only move after a certain number of episodes?
When I try to run Amidar even without RL code, I cannot get the environment to move immediately. It takes about 100 steps before the game actually starts moving. I use the following simple code to display some images and print some actions (I always try to do the same action, namely going up):
env = gym.make('Amidar-v0')
env.reset()

for i in range(1000):
    action = 2
    next_state, reward, terminated, info = env.step(action) # take a random action
    print(f"Timestep {i}")
    print(next_state.shape)
    print(reward)
    print(action)
    print(info)
    plt.imshow(next_state)
    plt.show()

When running this code, it takes until about step 85 before the environment starts to move. After that, each step, it moves until the agent is hit by the enemy. Then the environment restarts in the start state, and it takes quite some time before it starts to move again. I have tried doing 'FIRE' as my first action; however, this is not working since it also takes a while before the environment starts moving. Because of this, my buffer is almost always filled with the same images and hence my network isn't learning anything. How do I get this environment to move immediately?

Hi @Lennart and welcome to AI Stack Exchange! It looks like this question was closed because it is off-topic. If you would like to keep this question open, you will need to edit it to meet the on-topic rules discussed here. Just comment here if you would like help in any way with this. I hope to see you around the site!

Hi @DeepQZero, thanks for the response. I just read the off-topic rules and it was probably closed because the question is about specific software. No need to keep this question open.

I reviewed some videos of Amidar on YouTube, and it seems that the game screen is fixed for a few seconds before the start of each level. This is probably to give the human player a chance to rest between levels and maybe even pause the game to take a break, as the gameplay looks very intense.

How do I get this environment to move immediately?

I suggest creating a gym wrapper to change the reset function of the environment to produce a different start state. Since the initial 85 frames are not influenced by the agent's actions, these frames are unhelpful and unnecessary for your agent's training. You could consider calling the step function 85 times in your new implementation of the reset function using a random action; then return the resultant state. When calling your newly implemented reset function, the agent's start state will be frame 85 instead of frame 0. As you noted, frame 85 is immediately followed with many frames of meaningful movement, which will provide higher-quality training data. In contrast, the original implementation of the reset function starts at frame 0, which is followed by 85 unhelpful fixed frames.

Because of this, my buffer is almost always filled with the same images and hence my network isn't learning anything.

ATARI environments are difficult even for some of the more powerful RL algorithms. For example, it is one of the harder environments for DQN to solve (see the Nature paper, pg. 531).  Don't worry if your agent isn't learning right away. It could take hours or even days to learn enough to noticeably improve, even with a correct implementation of a powerful algorithm. Good luck, and welcome to AI Stack Exchange!


text:
How does Importance Sampling compare against Policy Regularization in Offline RL?
In offline RL we are usually equipped with a dataset, often also called Replay Buffer, that contains transitions in an episode, that are created by some behavior policy. This behavior policy could either be random, or could also be optimized with something like SAC.
Generally, the goal of offline RL is to train a target policy on that dataset, that outperforms the behavior policy (like the random one or the policy trained with SAC): 'In offline RL, the whole point is to learn a policy that does something differently (presumably better) from the pattern of behavior observed in the dataset D.' (https://arxiv.org/abs/2005.01643)
One of the issues that come with off-policy and offline learning is the learning of a q-function with (action, state) pairs that come from the replay buffer (i.e. a mix of behavior policies) and (action, state) pairs that are sampled from the target policy which we are trying to learn. To be more precise, consider the loss of the q-function in SAC, which is usually the Mean Squared Error between the q-value of a state action pair (from the buffer) and a q-value of a next state action pair, where the action is not from the buffer, but from the target policy
Thus, we have an action distribution from the behavior policy, and an action distribution from the target policy when learning the q-function. If both differ a lot, we can a pretty bad approximation of the q-values, hence we want to keep the target policy close to the behavior policy: The fundamental challenge with making such counterfactual queries is distributional shift: while our function approximator (policy, value function, or model) might be trained under one distribution, it will be evaluated on a different distribution, due both to the change in visited states for the new policy and, more subtly, by the act of maximizing the expected return (https://arxiv.org/abs/2005.01643)
One way to handle this, is to keep the target policy close to the behavior policy by regularizing, for example by using a KL divergence penalty. So when the target policy deviates too much from the behavior one, it gets a penalty for the learning objective.
Another way, if I understood the concept of IS correctly, would be to introduce importance sampling (only works for multi-steps algorithms though, since we cannot compute the is ratio for single steps) to estimate the expected values from samples that are drawn from the behavior policy w.r.t to the target policy. This would keep the distribution close to the target policy, in contrast to the policy regularization approach, which keeps the distribution close to the behavior policy.

Are both assumptions correct?

Since I only see the first method used, what is the disadvantage of the second approach?

I'm not familiar with "policy regularization". It may only apply for certain RL methods. Could you please provide a link to the approach you want to compare with importance sampling? It may also help to explain what "the distribution" means to you, since I think there is some misunderstanding here that will contribute to any answer.

One way to handle this, is to keep the target policy close to the
behavior policy by regularizing, for example by using a KL divergence
penalty. So when the target policy deviates too much from the behavior
one, it gets a penalty for the learning objective.

Regularizing the target policy to be close to the behavior policy has been done with some success in previous works (e.g. see Related Work section of the Conservative Q-Learning paper). The regularizer acts as a safeguard by preventing unrealistically high queried values of unseen state-action pairs to heavily influence the expected values of the target policy in the bootstrapping update. Since you have seen this method used before, I will not expand further.

Another way, if I understood the concept of IS correctly, would be to
introduce importance sampling to estimate the expected values from
samples that are drawn from the  behavior policy w.r.t to the target
policy. This would keep the  distribution close to the target
policy...

You are correct in that importance sampling will estimate the expected values of the target policy from samples drawn from the behavior policy. However, importance sampling does not act as a safeguard as described previously. Specifically, implementing a reweighting scheme such as importance sampling when calculating the expected values does not prevent the agent from querying unseen state-action pairs. If these queried values are unrealistically high, then the target policy will learn to take those actions more often. This will result in an increase of the importance sampling weights corresponding to those state-action pairs, which will ultimately result in unrealistically high expected values of the target policy. From another point of view, the importance sampling weights for the state-action pairs with unrealistically high queried values may start small, but there is no safeguard against the weights increasing during learning; if the weights were to remain fixed, then the expected values of the target policy would be incorrect, possibly introducing other problems. Some newer offline RL algorithms such as Implicit Q-Learning (IQL, paper) attempt to circumvent this issue by using SARSA-style updates during training which do not query unseen state-action pairs, but there is no guarantee that the final extracted policy will not query actions that the behavior policy would have refrained from choosing, especially if function approximation is used.
For further study, note that the survey you linked discusses a few other considerations regarding importance sampling for ORL, especially in Section 3.


text:
Why is there no exploration-optimality trade-off in Q-learning?
I have seen this sentence while reading an RL source (slide 29): "As discussed with MC-based off-policy control: avoidance of the exploration-optimality trade-off for on-policy methods."
Question: Why doesn't the exploration-optimality trade-off persist for off-policy methods such as Q-learning?

not sure who said that, but it's either wrong, or it's implying that is supposedly an off policy method, thus you can start with a dataset sampled by another behavioural policy (which however has to deal with the dilemma)

see slide 29 here: https://groups.uni-paderborn.de/lea/share/lehre/reinforcementlearning/lecture_slides/built/Lecture05.pdf

The sentence in the linked slide states: "As discussed with MC-based off-policy control: avoidance of the exploration-optimality trade-off for on-policy methods."
That's different from the sentence in the post.

@DSPinfinity I edited the question to reflect what is stated in the link. Please review it when you have the chance in case this isn't the question you were wondering about.

Whilst it's not perfect separation, because you may still pay real costs for exploration during learning (in fact possibly worse than on-policy methods), then off-policy methods do offer a clean way to learn optimal control whilst worrying a lot less about how to converge towards the optimal policy.
With on-policy methods, the exploration Vs exploitation tradeoff directly affects learning - if you set a low exploration level (e.g. low $\epsilon$) then learning about alternatives is slow. If you set a high exploration level, then the algorithm learns about a high exploration policy which is likely to be far from optimal. Typical solutions require careful management of exploration, reducing it over time, approaching zero.
Off-policy methods free you from that specific part of the dilemma. They can learn about a policy which is the current best guess at a deterministic optimal policy, whilst still exploring.
In theory, off-policy methods can learn optimal control given a behaviour policy of random action selection without reference to any value function. This is an extreme separation between behaviour and target policies, and follows the statement in S&B - theoretically off-policy learning gives you freedom to choose any exploration rate, whilst still guaranteeing converging on optimal control (for the tabular version at least).
In practice you still need to care about the degree of exploration with off-policy methods, because too much exploration will provide values for states that the agent wouldn't visit for optimal behaviour which don't matter. In a lot of problem domains, this can be the vast majority of states that are not worth exploring, because they are not even close to an optimal trajectory and there's nothing useful to learn about them. Too much exploration with off-policy doesn't prevent learning (like it would with on-policy), but it may reduce the convergence rate so much that solutions are not practical.
So typical off-policy methods do also manage exploration rate, on the surface quite similarly to on-policy. However the difference is that the ranges of values that work for off-policy are much broader, and it is common to keep a moderate or small amount of exploration always (where an on-policy method would have trouble converging to optimal with the same exploration rate).

I feel that this question is more easily understood by contrasting on-policy methods with off-policy methods.
An off-policy method generates data in the environment with a behavior policy during training to update a target policy for evaluation. Off-policy methods usually navigate the exploration-exploitation trade-off by using a behavior policy that is suboptimal to better explore the environment and generate a rich set of experience during training. Since the target policy does not generate experience in the environment, it is often designed to neglect exploration and is therefore generally superior to the behavior policy during evaluation, sometimes up to complete optimality.
In contrast, on-policy methods use the experience generated in the environment with the behavior policy to update that same policy: the behavior and target policies for on-policy algorithms are identical. Since the exploration-exploitation trade-off still persists while generating the experience during training, the policy must be designed to take presumably suboptimal actions to explore. However, increasing exploration generally degrades the policy's performance during evaluation. The trade-off of needing to increase exploration during training that generally decreases the optimality of the policy during evaluation can be dubbed the exploration-optimality trade-off for on-policy algorithms.
To answer your question as posed, off-policy methods bypass the exploration-optimality trade-off by using separate behavior and target policies. Increasing exploration in the behavior policy during training does not generally decrease optimality of the target policy during evaluation. Note that I personally have not seen the exploration-optimality trade-off explicitly mentioned in any source; I have seen a discussion of the ideas of this trade-off in Example 6.6 of Sutton & Barto.


text:
Adding extra parameters to the inputs of a network?
I have a bunch of images of cells from a brightfield microscope that I want to segment. Cells have different morphologies, shapes, etc. depending on cell lines. I also have some metadata associated with each image (i.e. the cell types and some other qualitative information). My question is, would including that data along with the images provide a strong signal to guide the network during training, or is it better to just let the network train on images alone? Thanks ahead of time.


text:
question on Implementing the Simplest Policy Gradient from spinningup
In Part 3: Intro to Policy Optimization from spinningup documentation, there is a formula to compute the estimate of the policy gradient:
'''
This is an expectation, which means that we can estimate it with a sample mean. If we collect a set of trajectories $ D = \{\tau_i\}_{i=1,...,N} $ where each trajectory is obtained by letting the agent act in the environment using the policy $\pi_{\theta}$, the policy gradient can be estimated with
$$
\hat{g} = \frac{1}{|D|} \sum_{\tau \in D} \sum_{t=0}^{T} \nabla_{\theta} \log \pi_{\theta}(a_t |s_t) R(\tau),
$$
where $|D|$ is the number of trajectories in $D$ (here, $N$).
'''
Also in the code on the same page to compute loss:
# make loss function whose gradient, for the right data, is policy gradient
def compute_loss(obs, act, weights):
    logp = get_policy(obs).log_prob(act)
    return -(logp * weights).mean()

Here the mean() is calculated over all the (state, action) pairs. However, the formula above calculates the mean over trajectories. There seems to be a disconnect. Are these two forms equivalant?

Hi @Charles Ju and welcome to AI Stack Exchange. I wanted to commend you on writing a very clear and well-researched question. Thank you for posting, and we look forward to more of your questions here soon!

Note that the documentation states that the weights parameter is set to $R(\tau)$.
Therefore, the $\nabla_\theta \log \pi_\theta (a_t|s_t)R(\tau)$ terms are the same whether calculating the policy gradient over trajectories (the equation) or over state-action pairs (the pseudocode). Also, note that each state-action pair is associated with exactly one trajectory; therefore,
$$\hat{h} = \sum_{\tau \in D} \sum_{t=0}^T \nabla_\theta \log \pi_\theta (a_t|s_t)R(\tau)$$
calculates both the unnormalized policy gradient over the trajectories and also the unnormalized policy gradient over the state-action pairs. The policy gradient over the trajectories is given as $\hat{g} = \frac{1}{|D|}\hat{h}$. Assuming there are $|K|$ state-action pairs, the policy gradient instead averaged over the state-action pairs is $\frac{1}{|K|}\hat{h} = \frac{|D|}{|K|}\left(\frac{1}{|D|}\hat{h}\right) = \frac{|D|}{|K|}\hat{g}$. Thus, the policy gradient averaged over state-action pairs is proportional by factor $\frac{|D|}{|K|}$ to the policy gradient over trajectories. Since multiplying a gradient by a constant (generally) does not change the underlying optimization problem, these two forms are practically equivalent.


text:
What are the parameters to consider when I set the length of an episode during the training of an RL model?
I'm working on an RL algorithm that receive a list of orders and needs to find the optimal clusters considering different parameters such as due date, location, etc. I don't know what should be the length of the episode and how it can impact on the results of the training. Also I don't know how to consider the situation where the model won't take an action: should it be considered as a bad action or good? If it's a good action, how should I compute the reward?


text:
Is it possible for original Vision Transformer (ViT) to do fine-grained semanantic segmentation? if so, how?
As far as I know, in the original ViT, the image is first divided to a fixed size of patch (16x16, for example) then they are flattened and treated as tokens and fed into Transformer.
Without using later more recent techniques (such as Hierarchical patch merging in Swin transformer), I feel like it is not possible to do the fine-grained segmentation at all, the best it can do is to label the whole token (with 16x16 pixel) as one class, since the model no longer understands any spatial information in the token.
Is my understanding correct? I know that it didnt do as well as Swin Transformer which use more fine-grained hierachical patch merging. But can ViT still selectively label some pixels in one patch as one class and the other pixels as another class?


text:
How Do I Optimise a Black-Box Objective Function with DQN Using Reinforcement Learning?
I'm a beginner in the field of reinforcement learning, and I'm currently working on a problem that has me a bit stuck. I'm trying to optimize a black-box objective function using reinforcement learning, but I'm not sure if I'm on the right track. I would really appreciate any guidance or insights from the experienced folks in this field.
So, here's the deal: I have an objective function that takes two inputs (x, y) and outputs a scalar value z. The goal is to find the global maxima of this function. The tricky part is that I don't have access to the inner workings of the function. All I can do is start from a random position (x, y) and take small steps to explore the function's landscape.
The objective function could look something like this:
def objective_function(x, y):
    return -(x**2 - 10 * np.cos(2 * np.pi * x) + y**2 - 10 * np.cos(2 * np.pi * y) + 20)

The idea is to use Q-value estimation with a neural network to learn the optimal policy for maximizing the objective function.
Here's a rough outline of what I've been trying:
Set up a DQN model using PyTorch that takes the current state (x, y) as input and outputs Q-values for each action.
Create a replay buffer to store the transitions (state, action, reward, next state) during training.
Initialize the DQN model and the replay buffer.
Start the training loop:

Pick a random starting state.
For each step, choose an action based on the current state using epsilon-greedy exploration.
Take the action and observe the next state and reward.
Store the transition in the replay buffer.
If the replay buffer has enough samples, sample a batch of transitions and perform gradient descent to update the DQN model.

After training, find the optimal solution by starting from a random state and greedily selecting actions based on the learned Q-values.
Now, here's where I'm a bit unsure and could use some help:

Since there's no clear ending point or terminal state in this problem, I'm not sure how to adjust the Q-value estimation. Should I estimate the Q-value as the cumulative reward over a fixed number of steps instead of until reaching a terminal state? I might be way off here, so please correct me if I'm misunderstanding something! Also, without a terminal state, the Q-value will be different each time due to the random starting point and the limited number of steps. Is this expected, or am I approaching this problem in the wrong way?

I would be incredibly grateful for any guidance, suggestions, or alternative approaches from the amazing people on this site. If you have any experience with similar optimization problems or have ideas on how to improve the DQN approach for this scenario, please share your wisdom!
Thank you so much in advance for your help. I'm really excited to learn from all of you and hopefully make some progress on this challenging problem!

Since you mentioned that you are a beginner in RL, I highly suggest that you engineer the environment to be compatible with off-the-shelf RL libraries to compare with your implemented DQN algorithm. These libraries usually contain episodic algorithms, so the next step in designing this environment is determining the terminal condition(s) for the episode.
One approach is to only allow a fixed number of time steps $T$ before the episode terminates. Given a maximum step size $M$, it is helpful (albeit unnecessary), to bound the starting position at the beginning of the episode such that the agent is able to reach the maximum objective location before the end of any episode; the location would need to be within $M \cdot T$ of all starting states. From another perspective, if the greatest distance from a starting point to the location is $D$, then $D < T \cdot M$ would need to hold. With this constraint, the performance of the agent during training can be easily estimated by seeing if the agent ends near the location at episode completion. This method assumes that a general vicinity of the location is known, which seems to be a reasonable assumption.
We will continue this approach with the function you provided:
$$J(x, y) = -(x^2 - 10\cos(2\pi x) + y^2 - 10\sin(2\pi y) + 20).$$
Through inspection, we can see that the maximum objective location is at $(0, 0)$, the origin. A reasonable number of time steps per episode for baseline DRL algorithms is $T=100$. With a maximum step size of $M=0.1$, we have $D < 100 \cdot 0.1 = 10$. Therefore, if the initial states are sampled from a square grid centered at the origin, then the maximum side length of the grid could be $10/\sqrt{2} \approx 7.07$. For simplicity, we make the side length $5$ to make the problem slightly easier and speed up training. Below is a sample environment coded in Python that adheres to the current Gymnasium specifications.

import gymnasium as gym
import numpy as np
from stable_baselines3 import PPO

class BlackBoxEnv(gym.Env):
    def __init__(self):
        self.time_step = None
        self.x_pos, self.y_pos = None, None
        self.observation_space = gym.spaces.Box(
            np.array([-10, -10, 0]), np.array([10, 10, 1]), (3,))
        self.action_space = gym.spaces.Box(
            np.array([-0.1, -0.1]), np.array([0.1, 0.1]), (2,))

    def reset(self, seed=None, options=None):
        self.time_step = 0
        self.x_pos, self.y_pos = np.random.uniform(-5, 5, 2)
        return np.array([self.x_pos, self.y_pos, self.time_step/100]), {}

    def step(self, action):
        self.time_step += 1
        old_score = self.black_box(self.x_pos, self.y_pos)
        action_magnitude = np.sqrt(action[0] ** 2 + action[1] ** 2)
        self.x_pos += action[0]/action_magnitude * 0.1
        self.y_pos += action[1]/action_magnitude * 0.1
        new_score = self.black_box(self.x_pos, self.y_pos)
        rew = new_score - old_score
        obs = np.array([self.x_pos, self.y_pos, self.time_step/100])
        term = True if self.time_step == 100 else False
        trunc = False
        return obs, rew, term, trunc, {}

    @staticmethod
    def black_box(x, y):
        return -((x ** 2) - 10*np.cos(2*np.pi*x) + (y ** 2) - 10*np.cos(2*np.pi*y) + 20)

env = BlackBoxEnv()
model = PPO("MlpPolicy", env, verbose=1)
model.learn(total_timesteps=250_000)

This environment allows for continuous actions in the range $[-0.1, 0.1]$ in each dimension, and it scales the resulting action to have magnitude $0.1=M$. The observation vector is of length 3 and includes the exact $(x,y)$ position of the agent. The normalized current time step in the range $[0, 1]$ is included in the observation to model the environment as a Markov decision process; not including the time step would introduce uncertainty in the current time step which may hamper training. Considering we are only allowing a fixed number of time steps per episode, the reward at each step can be modeled as the difference in the objective between states. In this manner, the Q-value of a state will estimate the difference in the objective at the final state and current state under the current policy.
By sampling random points from the starting region and computing the difference in objective from the starting points and the objective at the origin, the average reward of the optimal policy can be computed as roughly $36.7$ across all possible start states. The Q-value being different for various start states is not a concern here since the Q-value is conditioned on a state (and action) and will be trained to simply maximize whatever remaining reward exists until reaching the origin. I did not see anything wrong with your description of the DQN algorithm. I will provide an example using the PPO algorithm, which is run for $0.25\mbox{M}$ time steps.  The average training reward and the average distance of the agent's final position to the origin is shown below.

The mean reward hovers near the optimal mean reward near the end of training. Similarly, the magnitude of the final position of the agent is near zero, suggesting that the agent has found the maximum of the objective at the origin. There is little exploration performed near the end of training, so running the trained algorithm greedily for a few test episodes should yield the same result.
Realize that the approach presented in this answer might not be perfectly suitable to your intended problem. To adapt this approach to your intended problem, consider the following:

DQN is a discrete algorithm. You will need to provide a discrete action space such as the cardinal directions.
PPO has generally been shown to outperform DQN on many tasks. You may need to add extensions to vanilla DQN such as Double DQN to yield good results.
If a terminal state is known to the environment (e.g. a vicinity near the maximum objective location), then this terminal state condition can be used in addition to the fixed number of time steps for faster training.

Good luck, and please provide an update when you have the chance!

Hi again! Thanks again for your detailed response earlier! I implemented the PPO version you suggested for my original problem which was adding a new wind turbine to a previously built wind park, and it almost worked! The model converged on two near-optimal solutions, which was great progress.
Now, I’m looking to scale this approach to an objective function with multiple inputs, as I’m optimising the entire layout of the wind park. I’ve posted a new question explaining the problem in more detail and would really appreciate it if you could share your insights there as well.

Awesome! I will take a look at it sometime this week, but I might not have a quick answer. Also, if you would upvote this post, it would help me out.

I will as soon as I get the minimum amount of reputation to do that :)

I upvoted your other question, so you should be able to upvote now. I'll take a look at the question later this week, but no promises on an answer from me.


text:
What is the right DRL algorithm to use when the goal in an environment is not fixed?
Let's take the LunarLander environment from the package Gym as an example.

In this case, one can run thousand of episodes until the agent learns a good policy. However, there is a condition: the goal region doesn't move anywhere. In every episode it stays exactly at the same place. It is intuitively "easy" to understand that the policy converges after many iterations with the environment.
What happens if the goal region is not in the same position, when a new episode begins?

Can the agent learn to generalize by running more and more episodes? (which I do not understand intuitively)
Should I change completely policy (PPO, A2C, TD3, SAC, etc) and look for a policy that takes into consideration that the goal region can change?

The reason of my question is that I saw that there are some frozen lake environments where the grid is generated randomly; therefore, the policy can be learned somehow.

There is a possibility that the agent can generalize to land in an arbitrary goal region if the goal region is varied at the start of each training episode. If the locations of the goal region and agent are provided in the observation or if the function approximator (e.g. convolutional neural network) is powerful enough to identify these objects, then the agent will be forced to learn that a high reward comes from landing in the goal region and vice versa (it is unable to memorize a single trajectory for a fixed goal region). From my past experience training on this environment, I think the possibility of successful generalization is quite good.
In the seminal work on generalization for deep reinforcement learning (link), there were many experiments performed to understand the effect of algorithmic additions on generalization, as follows:

Increasing the number of training levels improved generalization. Surprisingly, agents were shown to overfit to a large number of training levels.
Larger neural networks improved generalization at the expense of extra training time.
Regularization methods such as L2 regularization, dropout, data augmentation, and batch normalization improved generalization.
Adding stochasticity to the environment or the agent's policy produced a greater improvement than any of the regularization methods in the previous bullet point.

To help answer your second question, another work (link) determined that vanilla reinforcement learning algorithms such as A2C and PPO performed better than some other reinforcement learning algorithms specifically constructed to tackle the problem of generalization. I suggest first experimenting with some of the algorithmic additions mentioned above since many are fairly simple to implement. If those do not suffice, then I recommend scanning the literature for novel algorithms that have been developed since those two papers were written (2018) that aim to overcome the problem of generalization.

Sorry but what about reshaping the reward function? Could be a possible solution to the problem?

@Dave I read a few references and didn't see anything about reward shaping helping generalization.


text:
Confusing convention in Sutto-Barto on Monte Carlo Tree Search: is a leaf node a state leaf node or state-action leaf node?

Figure 8.10: Monte Carlo Tree Search. When the environment changes to a new state, MCTS
executes as many iterations as possible before an action needs to be selected, incrementally building a tree whose root node represents the current state. Each iteration consists of the four operations Selection, Expansion (though possibly skipped on some iterations), Simulation, and Backup, as explained in the text and illustrated by the bold arrows in the trees. Adapted from Chaslot, Bakkes, Szita, and Spronck (2008).

In more detail, each iteration of a basic version of MCTS consists of the following four
steps as illustrated in Figure 8.10:

Selection. Starting at the root node, a tree policy based on the action values attached to the edges of the tree traverses the tree to
select a leaf node.

Question: What is a "leaf node" in this context?
For instance, I'm unsure if a leaf node is a state leaf node or state-action leaf node. If by a leaf node a state leaf node is meant, then the figure on the leftmost is not consistent
because the root is a state but the last blue node is not a state leaf node because it has a child. On the other hand, if by a leaf node they mean a state-action leaf node, again there is an inconsistency because of two reasons: (i) the root node is not a state-action node (ii) the blue arrows in the leftmost figure do not cover the state-action leaf node.

The answer is somewhat of a puzzle using other neighboring text from the book. We will begin by determining if the selected leaf node is a state leaf node or state-action leaf node through some of the rest of the text:

Expansion. On some iterations (depending on details of the application), the
tree is expanded from the selected leaf node by adding one or more child nodes
reached from the selected node via unexplored actions.

Since the selected leaf node is connected to a child node through actions (via unexplored actions), it can be inferred that the selected leaf node is a state leaf node. Next, we will determine which node in the tree is the selected node.

Simulation. From the selected node, or from one of its newly-added child nodes
(if any), simulation of a complete episode is run with actions selected by the
rollout policy. The result is a Monte Carlo trial with actions selected first by
the tree policy and beyond the tree by the rollout policy.

The circled node in the expansion phase tree must be a newly-added child node because it is not present in the selection phase tree. Since this node is the child node of the node circled in the selection phase tree, the node circled in the selection phase tree must be the selected node during the selection phase. Therefore, since the text you provided states that the selection phase always selects a leaf node, we conclude that the authors are calling the circled node in the selection phase tree the selected leaf node.
Leaf nodes in tree data structures are usually defined as nodes without children, and as you mentioned, this seemingly contradicts the notion of the selected node in the tree being called a leaf node. Other sources use different conventions for designating the selected node which appear to prevent this contradiction. For example, a highly cited survey on MCTS (link) selects the most urgent expandable node. This node does not need to be a leaf since it only needs child nodes not yet present in the tree. In AlphaGo (link), the selected leaf node does not exist in the tree unless it is a terminal node: the selection phase incorporates a policy that chooses actions until it reaches a node not present in the tree (which must be a leaf node if it were to be added to the tree during the expansion phase) or a terminal node (also a leaf node). The node is added to the tree during the expansion phase if its visit count reaches a prespecified threshold.
In conclusion, it seems that using a term such as expandable node is better than leaf node in this section of Sutton & Barto. My advice is to simply understand the concepts in this section since the exact details of a MCTS are highly dependent on the application at hand.


text:
mathematics on monotonic e-greedy policy improvement

The picture is the shortcut from the Stanford CS234 RL course note. I have a question about the proof on the monotonic property of $\epsilon$-greedy policies. In the red underlined expression, if some $\tilde{a} \in A$ makes the value of the red underlined expression less than 0, then shouldn't
$$\frac{\pi_i(\tilde{a}|s)-\frac{\epsilon}{|A|}}{1-\epsilon} \max_{a'}Q^{\pi_i}(s, a') < \frac{\pi_i(\tilde{a}|s)-\frac{\epsilon}{|A|}}{1-\epsilon} Q^{\pi_i}(s, \tilde{a})$$ be true? Specifically, the inequality sign needs to be reversed -- it's no longer "greater than or equal to". Moreover, considering the scenario when $\epsilon$ tends to 1, which means we take uniformly random actions, why does the value function $V$ still have the monotonic improvement? Thanks.

The problem statement assumes that $\pi_i$ is $\epsilon$-greedy. By definition (see section 5.4 of Sutton & Barto), an action is chosen uniformly randomly with probability $\epsilon$ at each time step; otherwise, the greedy action is chosen. Since there are $|A|$ actions, each action $a \in A$ has a $\frac{\epsilon}{|A|}$ probability of being chosen randomly at each time step. Therefore, $\pi_i(a|s) \ge \frac{\epsilon}{|A|}$ for all $a \in A$, and the expression underlined in red can never be negative.
In the case that $\epsilon = 1$, both $\pi_i$ and $\pi_{i+1}$ will both choose actions uniformly randomly. Note that this "improvement" is still monotonic since $V^{\pi_i}=V^{\pi_{i+1}}$, and equality is allowed in the definition of (non-strict) monotonicity.


text:
Can two different non-optimal policies have the same value functions?
According Sutton and Barto second edition, page 79, policy improvement must give a better policy except when the policy is already optimal. This means that if two policies have the same value function then both are optimal. In other words, you cannot have two different non optimal policies with the same value function. Is this correct?

Hello @User1983 and welcome to AI Stack Exchange! Thank you for clearly defining your question in the title and body of the post. We hope to see more of your questions in the near future!

Sutton & Barto are stating that if the initial and resultant policies have the same value function after policy improvement, then both are optimal because the Bellman optimality equation is satisfied.
Section 3.6 discusses the following (true) statement: if two policies are optimal, then both have the same value function. The converse -- if two policies have the same value function, then both are optimal -- is not true for this statement. A simple counterexample can be constructed using a multi-armed bandit setup in which there are 3 actions: actions 1, 2, and 3 always yield rewards of 100, 100, and 200, respectively. The deterministic policies of choosing actions 1 and 2 have the same value function (a value of 100 at the start state, which is the only nonterminal state), but those policies are not optimal.

Thanks for the response. I see through your example that two different policies can have the same value function and not be optimal. I have just one more question, in Bellman optimal equation, you already have the optimal value function in both the left and right side of the equation. But during policy improvement optimization, I think you don’t have an optimal function in neither side. Well, At least while the sides are not equal and the process has not converged. I suppose that a proof of policy improvement should show that equality implies that value is optimal.


text:
Derivation of the relationship between state-value function and action-value function in SAC
Below is the relationship between state-value function and action-value function based on the source: https://spinningup.openai.com/en/latest/algorithms/sac.html

$$H(P) = \mathbb{E}_{x \sim P}[-\log P(x)].$$
In entropy-regularized reinforcement learning, the agent gets a bonus reward at each time step proportional to the entropy of the policy at that time step. This changes the RL problem to:
$$\pi^* = \arg \max_{\pi} \mathbb{E}_{\tau \sim \pi}\left[\sum_{t=0}^\infty \gamma^t\Bigl(R(s_t, a_t, s_{t+1}) + \alpha H (\pi(\cdot | s_t))\Bigr)\right],$$
where $\alpha > 0$ is the trade-off coefficient. (Note: we’re assuming an infinite-horizon discounted setting here, and we’ll do the same for the rest of this page.) We can now define the slightly-different value functions in this setting. $V^{\pi}$ is changed to include the entropy bonuses from every time step:
$$V^{\pi}(s) = \mathbb{E}_{\tau \sim \pi}\left[\sum_{t=0}^\infty \gamma^t \Bigl(R(s_t, a_t, s_{t+1}) + \alpha H(\pi(\cdot|s_t))\Bigr)\ \Big|\ s_0{=}s\right].$$
$Q^{\pi}$ is changed to include the entropy bonuses from every time step except the first:
$$Q^{\pi}(s,a) = \mathbb{E}_{\tau \sim \pi}\left[\sum_{t=0}^\infty \gamma^t R(s_t, a_t, s_{t+1}) + \alpha\sum_{t=1}^\infty \gamma^t H(\pi(\cdot|s_t))\ \Big|\ s_0{=}s, a_0{=}a\right].$$
With these definitions, $V^{\pi}$ and $Q^{\pi}$ are connected by:
$$V^{\pi}(s) = \mathbb{E}_{a \sim \pi}\left[Q^\pi(s, a)\right] + \alpha H(\pi(\cdot|s)).$$

Question: How is the derivation of the relationship between action-value function and state-value function given in the last line?

This relation is from the definition of action value function such as that defined in Sutton's RL book page 58.

we define the value of taking action $a$ in state $s$ under a policy $\pi$, denoted
$q_{\pi}(s, a)$, as the expected return starting from $s$, taking the action $a$, and thereafter following policy $\pi$

Thus in general following your reference's notation we have the obvious equational relation between state and action value functions of the same state as $V^{\pi}(s)=Q^{\pi}(s, \pi(s))=\mathbb{E}_{a \sim \pi}[Q^{\pi}(s, a))]$.
For SAC we need to add an additional policy's entropy bonus from every timestep for both state and action value functions, except the first timestep for action value function as your reference mentions since the entropy bonus is associated with the uncertainty of the policy when choosing among possible actions, but when we condition on having taken a specific action $a$ for $Q^{\pi}(s, a)$, we no longer consider the uncertainty of the policy at $s$ which has already been resolved by taking action $a$. Therefore we have to add the additional entropy bonus at state $s$ at the RHS to balance above equation as $V^{\pi}(s)=\mathbb{E}_{a \sim \pi}[Q^{\pi}(s, a))] + \alpha H(\pi(\cdot|s))$.

A great intuitive answer was provided by @cinch; I will provide an answer based on notation conversion. First, note that the sampled trajectory $\tau$ does not include $s_0$ because $s_0{=}s$ by definition of $V^\pi(s)$. We write out the first few terms of $\tau$ for clarity, condense $R(s_t, a_t, s_{t+1})$ into $R_t$, and distribute $\gamma^t$:
\begin{equation}
\begin{split}
V^{\pi}(s) &= \mathbb{E}_{\tau \sim \pi}\left[\sum_{t=0}^\infty \gamma^t \Bigl(R(s_t, a_t, s_{t+1}) + \alpha H(\pi(\cdot|s_t))\Bigr)\ \Big|\ s_0{=}s\right], \hspace{10em}\\
&= \mathbb{E}_{(a_0, r_0, s_1,\ \ldots) \sim \pi}\left[\sum_{t=0}^\infty \gamma^t \Bigl(R_t + \alpha H(\pi(\cdot|s_t))\Bigr)\ \Big|\ s_0{=}s\right],\\
&= \mathbb{E}_{(a_0, r_0, s_1,\ \ldots) \sim \pi}\left[\sum_{t=0}^\infty \gamma^t R_t + \sum_{t=0}^\infty \gamma^t\Bigl(\alpha H(\pi(\cdot|s_t))\Bigr)\ \Big|\ s_0{=}s\right].\\
\end{split}
\end{equation}
Next, we use the fact that the expectation is not taken over $s_0{=}s$, allowing us to change the index of summation and move the entropy term $\alpha H(\pi(\cdot|s))$ outside of the expectation.
\begin{equation}
\begin{split}
 &= \mathbb{E}_{(a_0, r_0, s_1,\ \ldots) \sim \pi}\left[\sum_{t=0}^\infty \gamma^t R_t + \left(\sum_{t=1}^\infty \gamma^t\Bigr(\alpha H(\pi(\cdot|s_t))\Bigr)\right) + \alpha H(\pi(\cdot|s_0))\ \Big|\ s_0{=}s\right],\hspace{2.5em}\\
&= \mathbb{E}_{(a_0, r_0, s_1,\ \ldots) \sim \pi}\left[\sum_{t=0}^\infty \gamma^t R_t + \alpha\sum_{t=1}^\infty \gamma^t H(\pi(\cdot|s_t))\ \Big|\ s_0{=}s\right] + \alpha H(\pi(\cdot|s)).\\
\end{split}
\end{equation}
We continue by splitting the expectation of $\tau = (a_0, r_0, s_1, \ldots)$ into an expectation over $a_0$ and an expectation over $(r_0, s_1, \ldots)$. Note that the expectation over $a_0$ is equivalent to the expectation over $a$ sampled from $\pi(\cdot|s)$ because $s_0{=}s$. Finally, we simplify using the definition of $Q^\pi(s, a)$:
\begin{equation}
\begin{split}
&= \mathbb{E}_{a_0 \sim \pi(\cdot | s_0)}\left[\mathbb{E}_{(r_0, s_1,\ \ldots) \sim \pi}\left[\sum_{t=0}^\infty \gamma^t R_t + \alpha\sum_{t=1}^\infty \gamma^t H(\pi(\cdot|s_t))\ \Big|\ s_0{=}s, a_0\right]\right] + \alpha H(\pi(\cdot|s)),\\
&= \mathbb{E}_{a \sim \pi(\cdot | s)}\left[\mathbb{E}_{\tau \sim \pi}\left[\sum_{t=0}^\infty \gamma^t R_t + \alpha\sum_{t=1}^\infty \gamma^t H(\pi(\cdot|s_t))\ \Big|\ s_0{=}s, a_0{=}a\right]\right] + \alpha H(\pi(\cdot|s)),\hspace{-2.5em}\\
&= \mathbb{E}_{a \sim \pi(\cdot | s)}\left[Q^\pi(s, a)\right] + \alpha H(\pi(\cdot|s)),\\
\end{split}
\end{equation}
as desired.


text:
Confused about Monte Carlo first visit algorithm
I'm really confused about understanding the Monte Carlo first visit algorithm as presented in the Sutton & Barto's book in chapter V. Here is the pseudocode:

The reason is that I'm trying to implement the same algorithm for the game "Blackjack" of OpenAI (Gymnasium). It is for learning purposes, so I'm trying to implement the algorithm from scratch in order to understand the concept of MC behind it. Sadly, after looking different videos and spending many days learning from the book, I have to admit, that I thought I understood the basic idea, but in its implementation I realized, I didn't. There are basically two problems:

In the algorithm from the cited book the trajectory is built up from the sequence:
$$S_{0}, A_{0}, R_{1}, S_{1}, A_{1}, ..., S_{T-1}, A_{T-1}, R_{T}$$
generated by running one single episode. THEN, it loops for each step of the episode from: $t = T-1, T-2$ to $0$. That means, that if the episode had 4 tuples ($T = 3$), then I would start the inner loop from $t = T-1 = 4-1 = 3$, followed by $t=2$, then $t=1$ and at the end $t=0$. In other words, as far as I understood, I need to sweep the trajectory backward and not from 0 to 4. So I don't understand, why many different tutorials (#1, #2) or videos(#3) don't calculate the discounted rewards backwards but upwards. Am I wrong? Or am I overlooking something important and maybe obvious?

The second thing is the statement:
"Unless the pair $S_{t}, A_{t}$ appears in $S_{0}, A_{0}, S_{1}, A_{1}, ..., S_{t-1}, A_{t-1}$". Here it is not clear to me, how to interpret this statement. In many code implementations out there, it is interpreted as "the first time the state $S_{t}, A_{t}$ is encountered". But looking exactly at the notation, you realize, that the pair $S_{t}, A_{t}$ can only appear after and only the previous pair $S_{t-1}, A_{t-1}$, making the statement (at least for me) a nonsense. Even in this case: I'm missing something obvious?

Can you please put your specific question in the title? If you have more than one question, please, focus on one and next time limit each post to a single question. Thanks.

To clarify notation (question 2 in your post), the phrase "unless pair $S_t$ appears in $S_0, S_1, S_2, \ldots, S_{t-1}$" is meant to assess if the state $S_t$ is identical to one of the previous states in the episode. I understand your confusion when trying to apply this line of pseudocode to the Blackjack environment. The episodes in the Blackjack environment are equivalent to one complete hand of Blackjack. Note that the state signal in this environment contains the current cards on the table, in particular the player's cards. One of the two actions in Blackjack is to 'hit', which gives another card to the player. Therefore, the next state $S_t$ will never be identical to the previous state $S_{t-1}$ because the number of cards increases after the hit action. In the case that the hand busts or the 'stay' action is chosen, the episode ends in a terminal state $S_T$. This terminal state has value 0 by convention (i.e. $V(S_T) = 0$), and its value does not ever need to be calculated or averaged in the pseudocode, which is why the loop starts at $T-1$ instead of $T$. Other environments such as the Frozen Lake grid world may see the agent return to states previously encountered during the episode, necessitating the loop in the pseudocode for the first-visit MC prediction algorithm.
Your understanding of the backwards sweep seems correct. The backwards and forwards sweeps are mathematically equivalent, as they both associate the state $S_{t}$ with the return $R_{t+1}+R_{t+2}+R_{t+3}+\ldots+R_{T}$. To see this equivalence, we can view the returns as follows:
$$ \begin{align}
S_0 &: R_1 + R_2 + R_3 + \ldots + R_{T-2} + R_{T-1} + R_T\\\\
S_1 &: R_2 + R_3 + \ldots + R_{T-2} + R_{T-1} + R_T \\\\
S_2 &: R_3 + \ldots + R_{T-2} + R_{T-1} + R_T \\\\
&\vdots \\\\
S_{T-3} &: R_{T-2} + R_{T-1} + R_T \\\\
S_{T-2} &: R_{T-1} + R_T \\\\
S_{T-1} &: R_T
\end{align} $$
The forwards view iterates through this list from top from bottom (i.e. from $S_0$ to $S_{T-1}$), and the backwards view iterates from bottom to top. The pseudocode most likely uses the backwards view for brevity and possible speed. The forwards view requires iterating through the list of rewards $[R_1, R_2, R_3, \ldots, R_T]$ twice: once to initially calculate $$R_1 + R_2 + R_3 + \ldots + R_{T-2} + R_{T-1} + R_T$$ and once when calculating the remaining returns. Specifically, to calculate the return for $S_1$, it suffices to subtract $R_1$ from the return for $S_0$. Similarly, the return for $S_2$ is the return for $S_1$ minus $R_2$. Calculating these forward returns amounts to a second iteration through the rewards list (aside from $R_{T-1}$) because the rewards $[R_1, R_2, \ldots, R_{T-2}]$ need to be subtracted. In contrast, the backwards view only needs to pass through the rewards list once: the return for $S_{T-1}$ is $R_T$, and the previous returns for $S_{T-2}$ through $S_0$ add a single reward at a time. Specifically, $R_{T-1}$ is added for $S_{T-2}$, $R_{T-2}$ is added for $S_{T-3}$, and so on. There is a slight speed savings (and possibly a one line of pseudocode savings) by preventing the need of initially calculating $R_1 + R_2 + \ldots + R_T$ as done in the forward view.


text:
RL agent for autonomous vehicle is able to follow the road but can't avoid crashing at all (Highway-Env / Racetrack Env.)
I coded some deep RL algorithms (DQN and SAC) with tf2/keras to solve an environment where a vehicle needs to follow the track and avoid crashing into one other vehicle (there is only one other vehicle). Whatever I do, the agent is able to follow road in one way or another but nearly always crashes into other vehicle. I use some kinematics information for observation. (the agent only controls steering)
My observation is the kinematics of the agent and the other vehicle. This includes coordinates, velocities, trigonometric headings, lateral and longitudinal offsets to the closest lane, and angular offsets to the lane.
A reward function could be defined to quantify how close is agent to the center. A negative reward (-1) is provided if the agent crashes. A negative reward is provided if the agent runs out off road.
If there is a crash or if the agent goes off-road, the episode is done.
With this information agent is able to follow the road but as soon as it reaches the other vehicle, it crashes into it. I trained 1000 episodes.
What did i try?

I ran my code in different environments and it works. Code structure is not a problem.
I added last actions (t and t-1) info to observations.
Hyper parameter tuning.
Changed crashing reward to different values.
Used Stable-Baselines3's PPO algorithm. (Had the same problem.)
Added the distance and angular between vehicles to the observation space.
I slowed down the discovery rate reduction in DQN.
Used PER as buffer in DQN.

None of these solved the crashing problem. Does anyone have any suggestions or ideas to solve this problem?

What is your reward function for lane closeness? Is it always positive? What is typical return for completed episodes?

Lane closeness reward is always positive, it's proportional to proximity to lane center. There are two lanes. Since environment is a loop, episodes ends only if vehicle crashes or goes off-road and each situation has negative rewards.

There are a few things I think worth looking into:

Is avoiding the other car actually possible in the environment? You may inadvertently be giving the agent a choice of crashing in lane, or going off road once it gets close to the other vehicle. If you have a human control interface you may be able to test how difficult avoiding the other car is.

If interactions with the other car are much less common than interactions with road bends, then you would expect the agent to require more examples before it finally figures out correct behaviour. You may also need to adjust learning rates and related params (epsilon decay) to avoid the steering behaviour becoming almost frozen by the time collisions are becoming possible.

One thing you could try is randomly varying how close a collision is at the start, including plenty of episodes that start with a collision imminent but avoidable.

Check your feature engineering:

Are any values related to the other car becoming large magnitude for a neural network? Most values should be in range $[-2,2]$ (with fixed training datasets you can aim for a standard deviation of $1$, but usually you have to compromise to within a range in reinforcement learning because you don't know the distribution)

If you have a visualization that shows the env, add a dump of current state and predicted values. Watch it and verify that your features are doing what you expect. One mistake in a key feature can change the appearance of the collision event for the agent from predictable (and avoidable) to apparently random.

One clue as to why the agent is crashing is to look at predicted values close to a collision. If predicted values are low and close to correct, then the agent "knows" it is about to crash, but doesn't know correct behaviour to avoid it. If the predicted values are high, then the agent is not correctly interpreting the state. That could be a training issue or perhaps feature engineering.

Thanks for sharing your opinions with me. I see what you mean. Environment actually has two lanes so avoiding is not difficult. I will try what you suggested. Thank you a lot.

@rafiqollective: My understanding of the environment is that the implementation is like a game with physics engine. And the car cannot change its speed, only steer. So depending on what physics applies to steering, and how the collision detection is done, it is possible to have a problem with this environment where your goal is not realisable, or very hard (e.g. perhaps collision detection is tooo wide, or in practice the agent's car has to steer into alternative lane a long way ahead of other car, and has to predict what lane the other car is in from cartesian co-ordinates)

Yes you get the environment very well. When you say it like that I'm afraid the environment may be too complicated for the agent to solve. I try feature engineering as you suggested and change reward function. I hope it works. @NeilSlater

@rafiqollective The environment does not sound too complex for RL, but you may want to rethink features or training routine to address your collision issue. And if possible do try to assess what the correct behaviour is, by e.g. playing the game yourself - that will give you more clues on what the agent should know and react to in order to succeed.


text:
Is it possible to build a convolutional autoencoder with fully connected bottleneck with low dimension?
I want to do a project with a small size image dataset (the size is about 50*50). There's another similar dataset, and I want to prove that the datasets are different. I built a convolutional autoencoder with fully connected bottleneck because I want to use the latent space which produced by encoder to get a scatter plot. I think if the scatter points are not in the same area, then it can said the similarity between the two datasets is not that high.
I tried many model architectures, and it just can’t perform well on validation data. I am wondering if there is any way to reduce the dimension to such a low level. Thanks!
Here's my model:
    self.conv1 = nn.Conv2d(1, 32, (2,2), 1,padding=1)
    self.conv2 = nn.Conv2d(32, 64, (2,2), 1,padding=1)
    self.conv3 = nn.Conv2d(64, 128, (2,2), 1,padding=1)
    self.conv4 = nn.Conv2d(128,256, (2,2), 1,padding=1)
    self.conv5 = nn.Conv2d(256, 128, (2,2), 1,padding=1)
    self.conv6 = nn.Conv2d(128, 32, (2,2), 1,padding=1)
    self.conv7 = nn.Conv2d(32, 8, (2,2), 2,padding=1)
    self.Flatten = nn.Flatten()
    self.lin1 = nn.Linear(8*30*30,512)
    self.lin2 = nn.Linear(512,128)
    self.lin3 = nn.Linear(128,10)

    self.lin4 = nn.Linear(10,128)
    self.lin5 = nn.Linear(128,512)
    self.lin6 = nn.Linear(512,8*30*30)
    #reshape here
    self.convtrans1 = nn.ConvTranspose2d(8, 32, (2,2), 2,padding=1)
    self.convtrans2 = nn.ConvTranspose2d(32, 128, (2,2), 1,padding=1)
    self.convtrans3 = nn.ConvTranspose2d(128, 256, (2,2), 1,padding=1)
    self.convtrans4 = nn.ConvTranspose2d(256, 128, (2,2), 1,padding=1)
    self.convtrans5 = nn.ConvTranspose2d(128, 64, (2,2), 1,padding=1)
    self.convtrans6 = nn.ConvTranspose2d(64, 32, (2,2), 1,padding=1)
    self.convtrans7 = nn.ConvTranspose2d(32, 1, (2,2), 1,padding=1)

In general, very simple datasets like MNIST and Fashion-MNIST can be encoded in just two dimensions, without sacrificing too much reconstruction quality.
For more complex data, this is often neither feasible nor advisable: even if you employ a very powerful encoder and decoder, the bottleneck is just too small to capture the relevant features (or hidden factors) that sufficiently describe your data. Usually, it happens that a very low bottleneck dimensionality can only capture something that is very simple and, therefore, also not very useful, which makes the reconstructions looks like random stuff or even just spurious patterns that are somewhat weakly correlated with your inputs.
I think the best way, is to apply dimensionality reduction methods (like UMAP or t-SNE) to a trained bottleneck to reduce its size to 2 or 3 dimensions such that you can inspect it nicely. As stated here, tSNE can behave quite arbitrarily due to its very random nature (and difficuly to tune the hyperparameters), and so you may end up visualizing some patters that, actually, are not in the data. For such reason I suggest using UMAP first, and recur to t-SNE only if you're not able to get good results.
I can also suggest that thinks like l2-normalization (during training) of the embeddings may help the subsequent dimensionality reduction.
Otherwise, a good way to measure similarity (or closeness) between samples is to train a Siamese network and then threshold the learned distance metric: have a look here. You can also use the triplet loss, or simply use a pre-trained VGG network in which you extract the 4096-d embedding.


text:
Support Vector Machine used in Image Classification
I am looking for a reference preferably a paper that details how Support Vector Machines (SVMs), and OpenCV were used to perform image classification before Convultional Neural Networks (CNNs). I am aiming to construct a SVM architecture that performs image classification. I would like to learn the history before CNNs came into play in AI history.


text:
How is per-decision importance sampling derived in Sutton & Barto's book?
In per-decison importance sampling given in Sutton & Barto's book:

Eq 5.12 $\rho_{t:T-1}R_{t+k} = \frac{\pi(A_{t}|S_{t})}{b(A_{t}|S_{t})}\frac{\pi(A_{t+1}|S_{t+1})}{b(A_{t+1}|S_{t+1})}\frac{\pi(A_{t+2}|S_{t+2})}{b(A_{t+2}|S_{t+2})}......\frac{\pi(A_{T-1}|S_{T-1})}{b(A_{T-1}|S_{T-1})}R_{t+k}$
Eq 5.13 $\mathbb{E}\left[\frac{\pi(A_{k}|S_{k})}{b(A_{k}|S_{k})}\right] = \displaystyle\sum_ab(a|S_k)\frac{\pi(A_{k}|S_{k})}{b(A_{k}|S_{k})} = \displaystyle\sum_a\pi(a|S_k) = 1$
Eq.5.14 $\mathbb{E}[\rho_{t:T-1}R_{t+k}] = \mathbb{E}[\rho_{t:t+k-1}R_{t+k}]$

As full derivation is not given, how do we arrive at Eq 5.14 from 5.12?
From what i understand :
1) $R_{t+k}$ is only dependent on action taken at $t+k-1$ given state at that time i.e. only dependent on $\frac{\pi(A_{t+k-1}|S_{t+k-1})}{b(A_{t+k-1}|S_{t+k-1})}$
2) $\frac{\pi(A_{k}|S_{k})}{b(A_{k}|S_{k})}$ is independent of $\frac{\pi(A_{k+1}|S_{k+1})}{b(A_{k+1}|S_{k+1})}$ , so $\mathbb{E}\left[\frac{\pi(A_{k}|S_{k})}{b(A_{k}|S_{k})}\frac{\pi(A_{k+1}|S_{k+1})}{b(A_{k+1}|S_{k+1})}\right] = \mathbb{E}\left[\frac{\pi(A_{k}|S_{k})}{b(A_{k}|S_{k})}\right]\mathbb{E}\left[\frac{\pi(A_{k+1}|S_{k+1})}{b(A_{k+1}|S_{k+1})}\right], \forall \, k\in [t,T-2]$
Hence, $\mathbb{E}[\rho_{t:T-1}R_{t+k}]= \mathbb{E}\left[\frac{\pi(A_{t}|S_{t})}{b(A_{t}|S_{t})}\frac{\pi(A_{t+1}|S_{t+1})}{b(A_{t+1}|S_{t+1})}\frac{\pi(A_{t+2}|S_{t+2})}{b(A_{t+2}|S_{t+2})}......\frac{\pi(A_{T-1}|S_{T-1})}{b(A_{T-1}|S_{T-1})}R_{t+k}\right] \\= \mathbb{E}\left[\frac{\pi(A_{t}|S_{t})}{b(A_{t}|S_{t})}\frac{\pi(A_{t+1}|S_{t+1})}{b(A_{t+1}|S_{t+1})}\frac{\pi(A_{t+2}|S_{t+2})}{b(A_{t+2}|S_{t+2})}....\frac{\pi(A_{t+k-2}|S_{t+k-2})}{b(A_{t+k-2}|S_{t+k-2})}\frac{\pi(A_{t+k}|S_{t+k})}{b(A_{t+k}|S_{t+k})}......\frac{\pi(A_{T-1}|S_{T-1})}{b(A_{T-1}|S_{T-1})}\right]\mathbb{E}\left[\frac{\pi(A_{t+k-1}|S_{t+k-1})}{b(A_{t+k-1}|S_{t+k-1})}R_{t+k}\right] \\= \mathbb{E}\left[\frac{\pi(A_{t}|S_{t})}{b(A_{t}|S_{t})}\right]\mathbb{E}\left[\frac{\pi(A_{t+1}|S_{t+1})}{b(A_{t+1}|S_{t+1})}\right]\mathbb{E}\left[\frac{\pi(A_{t+2}|S_{t+2})}{b(A_{t+2}|S_{t+2})}\right]....\mathbb{E}\left[\frac{\pi(A_{t+k-2}|S_{t+k-2})}{b(A_{t+k-2}|S_{t+k-2})}\right]\mathbb{E}\left[\frac{\pi(A_{t+k}|S_{t+k})}{b(A_{t+k}|S_{t+k})}\right]......\mathbb{E}\left[\frac{\pi(A_{T-1}|S_{T-1})}{b(A_{T-1}|S_{T-1})}\right]\mathbb{E}\left[\frac{\pi(A_{t+k-1}|S_{t+k-1})}{b(A_{t+k-1}|S_{t+k-1})}R_{t+k}\right] \\= \mathbb{E}[\frac{\pi_{t+k-1}}{b_{t+k-1}}R_{t+k}]\\=\mathbb{E}[\rho_{t+k-1}R_{t+k}]$
which is not equal to eq 5.14. What's the mistake in the above calculations? Are 1 and 2 correct?

To answer your last question, in general, the expectation of the product of two random variables is not equal to the product of the expectations of each random variable, unless the random variables are independent. That doesn't seem to be true in your case (given that the policies at successive time steps could be correlated), but I could be wrong (because I know little or almost nothing about importance sampling and related topics).

I don't think policies at successive time steps are correlated, otherwise there would have been no point of giving eq 5.13. Also in theory given in the book, $\pi$ is sometimes taken as epsilon-greedy which is not correlated

You made a mistake in step 2. State $S_{k+1}$ depends on $S_k$ and $A_k$ through conditional probability $p(s'|s,a)$ so you cant do what you did.

$S_{k+1}$ is indeed dependent on $S_k$ but $A_k|S_k $ is independent of $A_{k+1}|S_{k+1}$ because $P(A_k|S_k)$ means, given $S_k = s$, what's the probability of choosing $A_k = a$ , similarly for $P(A_{k+1}|S_{k+1})$ . Hence since we are given $S_{k+1} = s'$, there is no need to calculate $p(s'|s,a)$. Is something wrong in this way of thinking??

First Part
We can reduce variance in off-policy importance sapling, even in the absence of discounting ($\gamma = 1$). Notice that the off-policy estimators are made up of terms like
$$\rho_{t:T-1}G_t = \rho_{t:T-1} (R_{t+1} + \gamma R_{t+2} + \dots+ \gamma^{T-t-1}R_{T})$$
and consider the second term, imagine $\gamma$=$1$:
$$\rho_{t:T-1}R_{t+2} = \frac{\pi(A_t|S_t) \pi(A_{t+1}|S_{t+1})......\pi(A_{T-1}|S_{T-1})}{b(A_t|S_t) b(A_{t+1}|S_{t+1})...... b(A_{T-1}|S_{T-1})} R_{t+2}$$
In above equation, the term $\pi(A_t|S_t)$, $\pi(A_{t+1}|S_{t+1})$, $R_{t+2}$ are correleated, all the other terms are independent of each other.
Notice the very import property of expectation:
$E[ab] = E[a] E[b]$ if and only if $a$, $b$ are independent random variables.
Now:
$$  E[\frac{\pi(A_t|S_t) \pi(A_{t+1}|S_{t+1}).....\pi(A_{T-1}|S_{T-1})}{b(A_t|S_t) b(A_{t+1}|S_{t+1}).....b(A_{T-1}|S_{T-1})} R_{t+2}]$$
$$  = E[\frac{\pi(A_t|S_t) \pi(A_{t+1}|S_{t+1})}{b(A_t|S_t) b(A_{t+1}|S_{t+1})} R_{t+2}]  E[\frac{\pi(A_{t+2}|S_{t+2})}{b(A_{t+2}|S_{t+2})}] .....  E[\frac{\pi(A_{T-1}|S_{T-1})}{b(A_{T-1}|S_{T-1})}]$$
$$ = E[\frac{\pi(A_t|S_t) \pi(A_{t+1}|S_{t+1})}{b(A_t|S_t) b(A_{t+1}|S_{t+1})} R_{t+2}] \sum_a b(a|s_{t+2}) \frac{\pi(a|s_{t+2}}{b(a|s_{t+2}}.....\sum_a b(a|s_{T-1}) \frac{\pi(a|s_{T-1}}{b(a|s_{T-1}} $$
$$ = E[\frac{\pi(A_t|S_t) \pi(A_{t+1}|S_{t+1})}{b(A_t|S_t) b(A_{t+1}|S_{t+1})} R_{t+2}] \sum_a \pi(a|s_{t+2}).....\sum_a \pi(a|s_{T-1})$$
$$ = E[\frac{\pi(A_t|S_t) \pi(A_{t+1}|S_{t+1})}{b(A_t|S_t) b(A_{t+1}|S_{t+1})} R_{t+2}] 1 * 1  $$
$$ = E[\frac{\pi(A_t|S_t) \pi(A_{t+1}|S_{t+1})}{b(A_t|S_t) b(A_{t+1}|S_{t+1})} R_{t+2}]  $$
therefore
$$  E[\rho_{t:T-1}R_{t+2}] = E[\rho_{t:t+1} R_{t+2}]$$
If we repeat this analysis for the $k$th term, we will get:
$$E[\rho_{t:T-1}R_{t+k}] = E[\rho_{t:t+k-1} R_{t+k}]$$
It follows that the expectation of our original term can be written:
$$E[\rho_{t:T-1}G_{t}] = E[\tilde{G_{t}}]$$
where
$$\tilde{G}_t \doteq \rho_{t:t}R_{t+1} + \gamma \rho_{t:t+1}R_{t+2} + \gamma^{2} \rho_{t:t+2}R_{t+3} + ...... + \gamma^{T-t-1} \rho_{t:T-1}R_{T}$$
We call this idea per reward importance sampling. It follows immediately that there is an alternative importance sampling estimate, with the same unbiased expectation as the ordinary importance sampling estimate:
$$V(s) \doteq \frac{\sum_{t\in\mathcal{T}(s)} \tilde{G}_t}{|\mathcal{T}(s)|}$$
which we might expect to sometimes be of lower variance.
Second Part
The reward $R_{k+1}$ depends on the previous $\pi(a_1|s_1)$ up to $\pi(a_{k-1}|s_{k-1})$. So, you can't seperate them and treat them as independent variable just you did on the aforementioned example.


text:
Problem in understanding equation given for convergence of TD(n) algorithm
Given equation 7.3 of Sutton and Barto's book for convergence of TD(n):

$\max_s|\mathbb{E}_\pi[G_{t:t+n}|S_t = s] - v_\pi(s)| \leqslant \gamma^n \max_s|V_{t+n-1}(s) - v_\pi(s)|$

$\textbf{PROBLEM 1}$ : Why is this error $|\mathbb{E}_\pi[G_{t:t+n}|S_t = s] - v_\pi(s)|$ compared with the error $|V_{t+n-1}(s) - v_\pi(s)|$.
There can be two other logical comparisons for the convergence of algorithm($TD(n)$):
1) If we compare and say that $V_{t+n-1}(s)$ is more close to $v_\pi(s)$ than $V_{t+n-2}(s)$ i.e we compare $|V_{t+n-1}(s) - v_\pi(s)|$ with $|V_{t+n-2}(s) - v_\pi(s)|$
2) We can also compare $|\mathbb{E}_\pi[G_{t:t+n}|S_t = s] - v_\pi(s)|$ with $|\mathbb{E}_\pi[V_{t+n-1}(S_t)|S_t = s] - v_\pi(s)|$ to show that  $\mathbb{E}_\pi[G_{t:t+n}|S_t = s]$ is better than $\mathbb{E}_\pi[V_{t+n-1}(S_t)|S_t = s]$ hence moving $V_{t+n-1}(S_t)$ towards $G_{t:t+n}$(as done in eq 7.2) can lead to convergence.
$\textbf{PROBLEM 2}$ : Are the above 2 methods of comparison for testing convergence correct.
Equations for reference:
Eq 7.1: $G_{t:t+n} = R_{t+1} + \gamma R_{t+2} +......+\gamma^{n-1}R_{t+n} + \gamma^{n}V_{t+n-1}(S_{t+n})$
Eq 7.2: $V_{t+n}(S_t) = V_{t+n-1}(S_t) + \alpha [G_{t:t+n} - V_{t+n-1}(S_t)]$

It seems that you're asking more than a question here. I suggest you ask only one question. Regarding problem 1, what is the definition of the value function? Isn't it the expected value of the return given that you are in a certain state? Doesn't that answer your first question? If not, explain why. Note that I don't really know if this answers your question because I didn't really read that part of the book and I am just trying to understand what your question/doubt really is.

Nope because $V_{t+n-1}(s)$ is the estimate of $v_\pi(s)$ hence we should compare  error $|\mathbb{E}[V_{t+n-1}(s)] - v_\pi(s)|$ and not error $|V_{t+n-1}(s) - v_\pi(s)|$

Ok. I was suspecting that your doubt was about that detail. Maybe you can put your main question in the title so that to clarify what you're asking.


text:
Solution to exercise 3.22 in the RL book by Sutton and Barto
The goal is to find an optimal deterministic policy for this MDP:

There are two possible policies: left (L) and right (R). What is the optimal policy, when different discounts are used:
A $\gamma = 0$
B $\gamma = 0.9$
C $\gamma = 0.5$
The optimal policy $\pi_* \ge \pi$ if $v_{\pi^*}(s) \ge v_{\pi}(s), \forall s \in S$, so to find the optimal policy, the goal is to check which one of those results in the largest state value function for all states in the system given discount factors (A,B,C).
The Bellman equation for the state value function is
$v(s) = E_\pi[G_t | S_t= s] = E_\pi[R_{t+1} + \gamma v(S_{t+1}) | S_t = s]$
The suffix $_n$ marks the current iteration, and $_{n+1}$ marks the next iteration. The following is valid if the value function is initialized to $0$ or some random $x \ge 0$.
A) $\gamma = 0$
$v_{L,n+1}(S_0) = 1 + 0 v_{L,n}(S_L) = 1$
$v_{R,n+1}(S_0) = 0 + 0 v_{R,n}(S_R) = 0$
$L$ is optimal in case A.
B) $\gamma = 0.9$
$v_{L,n+1}(S_0) = 1 + 0.9 v_{L,n}(S_L) = 1 + 0.9(0 + 0.9 v_{L,n}(S_0)) = 1 + 0.81v_{L,n}(S_0)$
$v_{R,n+1}(S_0) = 0 + 0.9 v_{R,n}(S_R) = 0 + 0.9(2 + 0.9 v_{R,n}(S_0)) = 1.8 + 0.81v_{R,n}(S_0)$
$R$ is optimal in case B.
C) $\gamma = 0.5$
$v_{L,n+1}(S_0) = 1 + 0.5 v_{L,n}(S_L) = 1 + 0.5(0 + 0.9 v_{L,n}(S_0)) = 1 + 0.45v_{L,n}(S_0)$
$v_{R,n+1}(S_0) = 0 + 0.5 v_{R,n}(S_R) = 0 + 0.5(2 + 0.9 v_{R,n}(S_0)) = 1 + 0.45v_{R,n}(S_0)$
Both $R$ and $L$ are optimal in case C.
Question: Is this correct?

Yes, these are all correct. You can get numerical values for each state-value function by solving some linear equations, because the environment is deterministic and you are looking for a deterministic policy you don't need to take any horrible expectations and can be solved using dynamic programming, which you will get to in chapter 4. I'm not sure exactly on your method how you have arrived at these conclusions however, e.g. in the final case how do you know that $v_{R,n}(S_0) = v_{L,n}(S_0)$? You also calculated for each state, which is required when $\gamma \neq 0$.

"horrible expectations" As someone just starting to learn about this, I find them horrible as well. :) Regarding your question: this diagram is returning immediately from the next, to the initial state, so I just applied the Bellman equation for the value state function until I reached the root (starting) node. For this diagram, it turns out that a single look ahead step is sufficient to do this.  When you look at C, you'll find $\gamma = 0.5$ multiplied with the value at either $S_{L,n}$, or $S_{R,n}$ (depending on the policy), and this is the next reward + next value (root value).

I just posted a solution to section B so you can see a way of doing it to obtain numerical solutions. :-)

@DavidIreland: yes, there might be a serious flaw in my thinking, because I was focused on initial values too much. Meaning: $v_{L,0}(S_0) = v_{R,0}(S_0)=v(S_0)$. Then I can conclude what I did for C only in the first iteration, not for every iteration.

Your answer is correct but I am not sure exactly on how you arrived at it, as e.g. in the last case you don't know that $v_{L,n}(S_0) = v_{R,n}(S_0)$.
I will show for case B when $\gamma = 0.9$ as case A is trivial and hopefully you can apply what I've done in case B to case C so that you get exact answers.
Now, as you stated $v(s) = \mathbb{E}[R_{t+1} + \gamma v(S_{t+1}) | S_t = s]$. Assuming that $\gamma = 0.9$ we can calculate the values for each state under the policy of taking the left action. Note that because we are looking for deterministic policies and the environment is deterministic then a lot of the expectations can be disregarded as nothing random is happening.
'Left Policy'
\begin{align}v(s_0) &= 1 + 0.9 \times v(s_L) \\ v(s_L) &= 0 + 0.9 \times v(s_0) \\ v(s_R) &= 2 + 0.9 \times v(s_0)
\end{align}
We can solve this set of linear equations to get $v(s_0) = \frac{100}{19}, v(s_L) = \frac{90}{19}, v(s_R) = \frac{128}{19}\;.$
'Right Policy'
\begin{align}v(s_0) &= 0 + 0.9 \times v(s_R) \\ v(s_L) &= 0 + 0.9 \times v(s_0) \\ v(s_R) &= 2 + 0.9 \times v(s_0)
\end{align}
We can again solve these to obtain $v(s_0) = \frac{180}{19}, v(s_L) = \frac{162}{19}, v(s_R) = \frac{200}{19}\;.$
As we can see, for each of the states the value function is larger for all of the states under the policy 'go right', thus this is the optimal policy for the case of $\gamma = 0.9$.
It is important to note that if we take the 'left' action in state $s_0$ then our policy would never take us to state $s_R$, and the same for the right action and state $s_L$, however due to the definition of an optimal policy requiring $v_{\pi ^*}(s) \geq v_{\pi}(s)\; \forall s \in \mathcal{S}$ then we must evaluate the value function for all states, even ones that would not be visited under a policy you are evaluating. This means that the state for $s_R$ will change whether we go right or left, because the value of this state depends on the value of $s_0$, which clearly changes depending on whether we go right or left.

Hm. Still I don't understand why $v(s_R)$ is evaluated as if the right policy is taken, for the left policy? If I want to evaluate all states of this MDP for always following left (L), then $v(s_R)$ doesn't change, does it?

Because of the definition of the state-value function, if we are in state $s_R$ then the value function is the expected reward + the value function for the state we transition into, which is $s_0$. Under the policy of 'go left', if we start in $s_0$ we would never reach $s_R$ but it still needs to be updated because the definition of a value function is that we condition on the current state we are in, and to find an optimal policy involved calculating the value function for all states, even if it s a state the policy would never take us.

Also, $v(s_R)$ and $v(s_L)$ depend on the value of state $s_0$ due to the bellman equation, and the value of $v(s_0)$ will change depending on whether you take left or right in that state, as you can see from the workings out.

You're welcome, glad that I could help.


text:
How to choose an RL algorithm for a Gridworld that models a much more complex problem
I am considering using Reinforcement Learning to do optimal control of a complex process that is controlled by two parameters
$(n_O, n_I), \quad n_I = 1,2,3,\dots, M_I, n_O = 1,2,3,\dots, M_O$
In this sense, the state of the system is represented $S_t = (n_{O,t}, n_{I,t})$. It is represented, because there is a relatively complex system, a solution of coupled Partial Differential Equations (PDES), actually in the background.
Is this problem considered a partially observable Markov Decision Process (POMDP) because there is a whole mess of things behind $S_t = (n_{O,t}, n_{I,t})$?
The reward function has two parameters
$r(s) = (n_{lt}, \epsilon_\infty)$
that are results of the environment (solution of the PDEs).
In a sense, using $S_t = (n_{O,t}, n_{I,t})$ makes this problem similar to Gridworld, where the goal is to go from $S_0 = (M_O, M_I)$ to a state with smaller $(n_O, n_I)$, given reward $r$, where the reward changes from state to state and episode to episode.
Available action operations are
$inc(n) = n + 1$
$dec(n) = n - 1$
$id(n)  = n$
where $n$ can be $n_I$ or $n_O$. This means there are $9$ possible actions
$A=\{(inc(n_O), inc(n_I)),(inc(n_O), dec(n_I)),(inc(n_O), id(n_I)),(dec(n_O), inc(n_I)), \dots\}$
to be taken, but there is no model for the state transition, and the state transition is extremely costly.
Intuitively, as solving a kinematic equation for a point in space, solving coupled PDEs from fluid dynamics should have the Markov property (strongly if the flow is laminar, for turbulence, I have no idea). I've also found a handful of papers where a fluid dynamics problem is parameterized and a policy-gradient method is simply applied.
I was thinking to use REINFORCE as a start, but the fact that $(n_O, n_I)$ does not fully describe the state and questions like this one on POMDP and this one about simulations make me suspicious. Could REINFORCE be used for such a problem, or is there something that prevents this?


text:
Can reinforcement learning algorithms be applied on problems involving a very large number of possible actions?
There is a question already about applying RL to "large scale problems", where large scale refers to the problem of a relatively small number of actions (that could be from a continous space) resulting in a very large number of states.
A good exapmle of this kind of large-scale probems is modeling a motion of a boat as a point on a plane, with an action being a displacement vector $\mathbf{\delta}_b = (\delta_x, \delta_y)$ and there are infinitely many states, because the next state is given by the next position of the boat, in a circle surrounding the boat $\mathcal{B}(\mathbf{x}_b, \mathbf{\delta}_{b,max})$, where $\mathbf{x_b}$ is the boat's current position, and $\mathbf{\delta}_{b,max}$ the maximal possible displacement. So here, the displacement as an action (move the boat) is from an infinite space because it is a 2D vector ($\delta_b \in \subset \mathbb{R}^2$) and so is the state space $\mathcal{B}$. Still, I just have two actions to apply to the boat in the end: move in x-directions this much, and in y-direction that much.
What I mean, is something even larger. Considering the example of a boat, is it possible to apply reinforcement learning on a system that has 100 000 of such boats, and what would be the methods to look into to accomplish this. I do not mean to have 100 000 agents. The agent in this scenario is observing 100 000 boats, they are its environment, and let's say the agent is distributing them in a current on the sea in such a way that they have the least amount of resistance in the water (the wake of one ship influences the resistance of its downstream neighbors).
From this answer and from what I have read so far, I believe an approximation will be necessary for the displacements in $2D$ space $\mathbf{\delta}(x,y)$ as well as for the states and rewards, because there are so many of them. However, before digging into this, I would like to know if there are some references out there where something like this has already been tried, or if this is simply something where RL cannot be applied.

Why don't you want to use one agent to control each of the boats or a multi-agent system? Maybe you're looking for hierarchical reinforcement learning.

@nbro: I would like to use the single agent and I don't know enough currently to judge if multiple agents would help or not. The main problem here is that each boat (point) impacts itself and its neighbors with its motion because the reward is a function of relative positions of all boats with respect to their immediate neighbors. So if a single agent moves individually 100 000 boats, the action is computationally expensive, the state space is sampled continuously from the starting configuration, so I am interested if there are some references for this kind of a problem.


text:
How to take actions at each episode and within each step of the episode in deep Q learning?
In deep Q learning, we execute the algorithm for each episode, and for each step within an episode, we take an action and record a reward.
I have a situation where my action is 2-tuple $a=(a_1,a_2)$. Say, in episode $i$, I have to take the first half of an action $a_1$, then for each step of the episode, I have to take the second half of the action $a_2$.
More specifically, say we are in episode $i$ and this episode has $T$ timesteps. First, I have to take $a_1(i)$. (Where $i$ is used to reference episode $i$.) Then, for each $t_i\in\{1,2,\ldots,T\}$, I have to take action $a_2(t_i)$. Once I choose $a_2(t_i)$, I get an observation and a reward for the global action $(a_1(i), a_2(t_i))$.
Is it possible to apply deep Q learning? If so, how? Should I apply the $\epsilon$-greedy twice?

Do you only wait one timestep after taking action $a_1$ before action $a_2$ is executed? Do you have to choose $a_1$ and $a_2$ simultaneously, or are you given an observation of the environment after executing $a_1$ and then allowed to choose $a_2$?

At episode $i$, I choose $a_1(i)$. Now, for each time step $t_i$ in episode $i$, I choose $a_2(t_i)$. Only after choosing action $a_2(t_i)$ I get an observation and receive a reward for my chosen action $(a_1(i), a_2(t_i))$ at $(i, t_i)$.

Just to be sure, after choosing action $a = (a_1, a_2)$, then episode terminates (i.e. you don't choose another action for the remainder of the episode)?

No, the episode has, say, $T$ steps. After choosing action $a_1$, I may choose $a_2$ at time $t$ and action $a_2'$ at time $t'$.

Are $t$ and $t'$ in the same episode? If they are, it seems to contradict what is stated in the question "then for each step of the episode, I have to take the second half of the action $a_2$." It might help to edit your original question with some of this information. It seems like a very interesting question, and I'm eager to try and solve it.

Yes, $t$ and $t'$ are in the same episode. I am editing the question.

Can you explain your MDP further? Once you’ve chosen ($a_1,a_2$) do you then have to choose another two tuple before getting the next state and reward?

Once I choose $(a_1, a_2)$ at episode $i$ and timestep $t_i$, I get a reward and move to the next state at $t_i+1$ and I have to choose another $a_2$, etc.

To me, the fact that you are taking actions at two different time scales suggests a similarity with hierarchical reinforcement learning - HRL([1], [2]). Have you considered looking at your problem from this perspective? I do not have a deep knowledge about HRL, so I don't know if there would be an issue if you apply existing HRL algorithms to your problem, but it was really the first thing that came to mind when reading your question.


text:
In Deep Q-learning, are the target update frequency and the batch training frequency related?
In a Deep Q-learning algorithm, we perform a batch training every train_freq and we update the parameters of the target network every target_update_freq. Are train_freq and target_update_freq necessary related, e.g., one should be always greater than the other, or must they be independently optimized depending on the problem?
EDIT Changed the name of batch_freq to train_freq.

It's more usual in my experience to run a moderately sized batch on every step. However, there is a lot of variation within the DQN method. Where are you seeing the batch_freq parameter? If you link the library or paper where this param is discussed I can probably figure out an answer

If batch_freq is batch size then no. Neither in my experience nor in any paper I've read

@NeilSlater I think it's the standard implementation of DQN. The code is from https://github.com/JuliaPOMDP/DeepQLearning.jl/blob/master/src/solver.jl. Line https://github.com/JuliaPOMDP/DeepQLearning.jl/blob/b590c378b622204c20c57e05a26cdd797a3cfedc/src/solver.jl#L132 is doing the minibatch training every train_freq. Then, line https://github.com/JuliaPOMDP/DeepQLearning.jl/blob/b590c378b622204c20c57e05a26cdd797a3cfedc/src/solver.jl#L138 is doing the update every target_update_freq.

It is fairly common in DQN to train a minibatch after every observation received after the replay memory has enough data (how much is enough is yet another parameter). This is not necessary, and it is fine to collect more data between training steps, the alogrithm is still DQN. The value higher than 1 for train_freq here might be related to use of prioritised replay memory sampling - I have no real experience with that.
The update to target network generally needs to occur less frequently than training steps, it is intended to stabilise results numerically, so that over or under estimates of value functions do not result in runaway feedback.
The parameters choices will interact each other, most hyperparameters in machine learning do so unfortunately. Which makes searching for ideal values fiddly and time-consuming.
In this case it is safe to say that train_freq is expected to be much lower than target_update_freq, probably by at least an order of magnitude, and more usually 2 or 3 orders of magnitude. However, that's not quite the same as saying there is a strong relationship between choices for those two hyperparameters. The value of batch_size is also relevant here, as it shows the rate that memory is being used (and re-used) by the training process.
The library you are using has these defaults:
    batch_size::Int64 = 32
    train_freq::Int64 = 4
    target_update_freq::Int64 = 500

They seem like sane starting points. You are relatively free to change them as if they were independent, as there is no simple rule like "target_update_freq should be 125 times train_freq". As a very rough guide, you can expect that high values of train_freq, low values of batch_size and low values of target_update_freq are likely to cause instability in the learning process, whilst going too far in the opposite direction may slow learning down. You might be able to set train_freq to 1, but I am not completely certain about that either in combination with the prioritised replay memory sampling which seems to be the default in the library you are using.