text:
What is the purpose of a replay/memory buffer in Deep Q-Learning networks?
I'm trying to understand DQNs.
There is one concept that I cannot really understand yet. In the book "Introduction to Reinforcement Learning" as well this tutorial online introduce the concept of a memory buffer (most of the time a Python deque) which must be filled with the following data:
$S_{t}, a_{t}, r_{t}, S_{t+1}$
where $S_{t}$ is the current state, $r_{t}$ is the reward, $S_{t+1}$ is the next status of the system given the action $a_{t}$.
Now, the buffer will be filled up to a point. Then a batch of data will be taken randomly from the buffer.
A code representation can be seen here: link.
...
replay.append(exp) #H
state1 = state2

if len(replay) > batch_size:
    minibatch = random.sample(replay, batch_size)
    state1_batch = torch.cat([s1 for (s1,a,r,s2,d) in minibatch])
    action_batch = torch.Tensor([a for (s1,a,r,s2,d) in minibatch])
    reward_batch = torch.Tensor([r for (s1,a,r,s2,d) in minibatch])
    state2_batch = torch.cat([s2 for (s1,a,r,s2,d) in minibatch])
    done_batch = torch.Tensor([d for (s1,a,r,s2,d) in minibatch])
    Q1 = model(state1_batch)
...

The fact, that a batch is taken randomly is not intuitive for me for understanding the logic behind it. By taking the data randomly it would be very hard to figure out any possible pattern. It would be like going into a labyrinth marking the way and the directions choosen along the way. Then, after a while (an episode in our programming case), all those markings are randomly changing their direction/position.
Maybe I'm wrong with my example, but if the data is taken randomly, how can a DQN approximate a meaningful function?
UPDATE 17 October 2023
I really thanks @NeilSlater and @DeepQZero for their answers.
But it seems, that probably my question was not really clear and/or lead to misinterpretations.
So I would present now an example.
In many tutorials about DQN, the gymnasium (or gym) environment is going to be used. CartPole, FrozenLake and many more are simple application, where you can develop your DQN network and test it.
Let's take for instance the CartPole environment. In it you get a +1 as a reward, for every scene, in which the pole remains up within the +/- 12° range.
So we can imagine to run one episode. In this episode the pole soon or later will definetly falls down leading to the end of the episode.
In my tests, if my action is completely random, than an episode lasts about 20 steps, then it is over.
But... it could be, that one episode is particular lucly and that pole will stay vertical for...let's say 50-60 steps (it is just an example).
In other words, the sequence of actions led to a very high reward (+1 * number of steps). Which is good, because luckly or not, I got a sequence, which can be used to "solve" the next game.
But now, the problem. All those transistions are stored in one Python deque (or a long memory buffer). And now the surprise to me: one a small amount of those data taken from that buffer. Much worse, randomly.
For my limited intuition capacity, this is hard to believe. Because due to the randomness of this batch, the sequence of actions played in one episode doesn't play any role anymore. And this is my question: How it is supposed to work?
Maybe I'm missing some important points here. But my thought were stronger after I read the book "Deep Reinforcement Learning" by Maxim Lapan. In the very first example, he does the following things:

run one episode of CartPole
collect action, state, new state and reward for every step
create a new deque for every new episode
take a batch of data containing only the most rewarded episodes (he used a percentile of 70%)
train the network
repeat

As you can see, he takes a batch based on the most successful episodes.
That means, the sequence of actions is important.
But for DQN, the batch is taken randomly as the sequence is no important anymore.
I hope, I explained my thoughts...

first understand Q-learning, then pass to Deep Q Learning

I do not think, that that is the problem

"that a batch is taken randomly is not intuitive for me for understanding the logic behind it" if you would have studied Q-learning before DQN, you should get why this is fine

For anyone answering, the training method presented for CartPole is correctly described - it's the Cross Entropy Method, which is a form of policy search which is not commonly taught in RL courses. It is its own thing, but is somewhere in-between genetic algorithms and policy gradients conceptually.

This question is asking about randomness in the data, so I will first clarify one of the comments in this question made about randomness.

If the data is taken randomly, how can a DQN approximate a meaningful function? It would be like going into a labyrinth marking the way and the directions chosen along the way. Then, after a while (an episode in our programming case), all those markings are randomly changing their direction/position.

This phenomenon is a fundamental consideration in the design of reinforcement learning algorithms as opposed to other learning algorithms. For example, supervised learning algorithms would learn to map states to actions solely through the state and corresponding action pairs provided in a fixed dataset. Like you mentioned, any randomness in the corresponding action will generally degrade the learning process.
In contrast, reinforcement learning algorithms do not not assume to have any knowledge of the desired actions beforehand and must learn the desired actions through interacting with the environment and receiving a reward signal and a next state signal. Consequently, randomness or variation in the actions is necessary to investigate the possible actions to see which actions will accrue the most reward; training on the data will increase the probability of taking actions that accrued more reward, and vice versa. In other words, the training process of reinforcement learning is meant to assess the data instead of imitate a fixed dataset as in supervised learning.

All those transitions are stored in one Python deque (or a long memory buffer). And now the surprise to me: one a small amount of those data taken from that buffer. Much worse, randomly. For my limited intuition capacity, this is hard to believe. Because due to the randomness of this batch, the sequence of actions played in one episode doesn't play any role anymore. And this is my question: How it is supposed to work?

To understand why training on sequences of actions is unnecessary, it helps to understand why it is possible to train on old data using the Q-learning update (see equation 6.8 of Sutton and Barto's book):
$$Q(S_t, A_t) \leftarrow Q(S_t, A_t) + \alpha\left[(R_{t+1} + \gamma \max_{a}Q(S_{t+1}, a)) - Q(S_t, A_t)\right].$$
Here, the approximate Q-function $Q(S_t, A_t)$ is being updated with the state, action, reward, next state tuples $(s, a, r, s')$. Importantly, these tuples were generated by a policy that takes random actions a small percentage of the time ($\epsilon$-greedy exploration). This policy that generates the data is the behavior policy. In contrast, the policy being learned is the policy that never explores (and only exploits) through using $\underset{a}{\max}Q(S_{t+1}, a)$ as an estimate of the return from the next state. This policy that only exploits is called the target policy that doesn't match the behavior policy of taking exploratory actions. Under certain conditions that I won't detail (e.g. reducing the exploration hyperparameter $\epsilon$), successively performing Q-learning updates is shown to converge to the optimal Q-function. Therefore, old data from previous behavior policies can be used during the Q-learning update to approximate the target policy.
The above paragraph should answer the question of why old data can be used in the buffer. Now we address the question of why the data can be sampled randomly without regard to its original sequence. In the Q-learning update presented above, only a single $(s, a, r, s')$ experience tuple is used to update a single $(s, a)$ pair of the Q-function. The Q-learning update does not need to process an entire sequence of actions in order because it only looks one time step into the future and approximates the return from all future time steps using the current Q-function, making it a one-step method or one-step update rule. This provides a great benefit over learning from sequences, as the Q-learning update can assess the best action at each individual time step. This is in contrast to training only on good episodes, since it provides much more flexibility when assigning credit to actions. For example, algorithms need to take exploratory actions in the beginning of training to find the most return. Regardless of how the remainder of the episode turns out, Q-learning can assess the goodness of a single experience tuple that took an exploratory action by determining if the sum of immediate reward and the expected return from the next state is better than the expected return from current state (via the update rule above). If so, Q-function will learn to take that action more frequently, and vice versa. In summary, Q-learning is able to assess the contribution of individual actions on a time step scale of length 1 through approximating the return from the next state, preventing it from needing to train on sequences of data.
The final question that remains is if there is any benefit to training with random data as opposed to sequentially experienced data. Taking a look at the DQN paper (see section 4, paragraph 4), the primary reason to randomly sample past data is to break correlations in the data. First, the high variance of strongly correlated experience hinders learning when using neural networks and associated optimizers. Randomizing the data makes it much closer to i.i.d. data, which generally enables much more efficient training. Second, note that the data used to train the current policy is also generated by the current policy when not using an experience replay buffer. Averaging the learning by randomly sampling data from many previous policies by using an experience replay buffer can help prevent major oscillations or even complete divergence in the learned policy (refer to the paper for a more detailed discussion).
If any of the terms used in this answer do not make sense and you cannot find a suitable reference online, please post another comment and I can update this answer.

I think the Bellman equation is key here to OP's understanding - it adds the fact that you can learn a useful function using only a small part of the trajectory. Add in the need for iid data for a neural network, and that can becomes a should .

@NeilSlater You're absolutely right that some additional comments regarding the Bellman equation would most likely increase the quality of my answer. It was somewhat hard to answer this question since (i) the question posed in the title seems to be related but slightly different from the question in the main body and (ii) OP wanted a figurative explanation. My goal with this answer was to help OP understand how RL assesses data instead of imitates it. Do you think my answer adds sufficient value, or would you recommend that I include additional information on the Bellman equation?

My suggestion is based on the OP wanting to know why sampling randomly from the "memory buffer" (replay memory) is effective. This seems the strongest theme in their question. To me, the most salient points are as per my first comment. Namely that the Bellman equation links data from $t$ and $t+1$ time steps and needs no other data from any trajectory, and that neural networks prefer iid data which is not correlated (as it would be if you trained strictly in sequence)

@NeilSlater I see. I tried to answer more of the first question (regarding the function approximation and training on random data) since it is very important in understanding the second question. I'm starting to realize more and more why we try to limit posts to one question.
Also during my time on this board, I've seen that you have some of the best etiquette and do not 'snipe' answers from other people and instead offer comments for slight improvements. Just to be sure, by giving me this suggestion, do you want me to add on to my answer, or would you like to make a separate answer?

Generally, if there is already a good answer that I mostly agree with, then I prefer to offer a few things that IMO could help, instead of writing my own. It's still just my opinion, and it's your answer. If you don't think it improves things on balance, e.g. it over-complicates the answer, then there's no pressure.

Ok guys, thanks for the answers.
If I understood right: I interpret @DeepQZero 's answer more as "randomness increase robustness of the network".  While NeilSlater seems to have understood my question which is, I put it easly, "why is the batch random?". The problem is now, that I didn't understand NeilSlater's answer. Is this the (or part of) the answer? https://en.wikipedia.org/wiki/Independent_and_identically_distributed_random_variables

@Dave  I'll try to incorporate the Bellman equation into my answer and make edits over the next day. In the meantime, if you would reduce the post to contain a single question, it would help me out.

@DeepQZero I update the original question with more information. And asking only one question

@Dave I updated my answer. If it isn't satisfactory, please let me know which parts could use more explanation. This answer needs to be high-level, and I can point out other written sources if there are still concerns.

@NeilSlater See above. I didn't discuss the Bellman equation, but I think my answer is sufficient. That is about as much detail as I can write as an answer on this site without needing the question to be more focused.

It's all solidly correct as far as I can see, and I don't have any further suggestions.


text:
Input size for a RNN layer by modeling a dynamical system
I'm trying to understand the concept of dynamical system with NN by studying this very well explanation here.
But I stuck in the following problem:

The author uses a RNN and/or a LSTM network as a NN for replicating the system (a spring mass system). And then he feed the RNN network with the following input:

where textX is the in reality (as later explained) is just an example. trainX and validationX have the same shape.
In this case I do not understand why the RNN network has been fed with a vector with 2 columns. The first column is the input ($u$ in the system) but the second column is filled by zeros. What's the meaning of zeros? Why to feed a RNN network with an input, which contains only zeros?
EDIT:

Looking deeper into the code I realized, that the author uses the fit method of Keras for training the model.
history=model.fit(trainX, output_train , epochs=2000, batch_size=1, callbacks=callbacks_list, validation_data=(validateX,output_validate), verbose=2)

Now there is one thing, that for me is not clear here. Passing the training data trainX with the label output_train, the fit method doesn't get sequence of data as excepted, since the author makes use of RNN or LSTM. In this way he is passing one input and the corresponding target. So I do not see here too much difference from a conventional NN. Shouldn't one pass a sequence of data and a sequence of outputs, since the model is a RNN one?

This the the initial condition of the system, namely the first derivative of displacement.
You need somehow to provide the initial internal state of RNN and this is the way this could be done with Keras API.
You can find more in the video attached to the article you are referencing to at the 48:37.

I edited my question. The reason is, I realized later, that I missed the most important question. If you could answer it... No worry. I'll not put other questions here

Ok, now I got it. After seeing the video for the 4th time, I understood the concept.

source: Stack Exchange

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

sort: votes


text:
Is the Invalid Action Masking in RL related only to the state or can be dependent on the reward as well?
I'm reading about Invalid Action Masking in RL in order to use it in my PPO algorithm for a specific task.
The problem is that I read such explanations: here, here and here the there the invalid action is choosen based on a state of the environment. My question is: is it possible to determine the invalidity of an action based on the reward?
I want to make it clear based on a simple example. Let's take the old good Cartpole environment from OpenAI:

And let increase the action space from two to three. So there basically three discrete actions: $a_{t} \in [0, 1, 2]$, where 0 means left, 1 means right, 2 means do nothing.
How do I determine, which action - based on the state - should be masked out?
####   UPDATE   ####
Thanks to @Neil-Slater for answering the question. Reading his answer I understood, that my question was missleading and I didn't get to the point.
The example I provided above is too simplified and didn't reflect exactly my question. So I try again this time using the picture I posted already in this question here few days ago. In the picture a crane moves from the start position to the waypoint $a$ as a first move. Now... the agent could theoretically go directly to waypoint $d$ ignoring all the waypoints in between. So I thought to force the agent to move vertically at first by invaliding the actions along the $x, y$ axes.
Now... reading the answer from @Neil-Slater I can try to answer my question myself:

The movement from start to $a$ does not require any invalidation of actions, because moving along the other axis is still permitted but not wanted. So the actions should not be masked at all. Reward should be enough.
The movement form start to $a$ needs to be forced by using some masking of some sort, otherwise the agent would not learn a suitable policy for the vertical movement.

I hope, I could now express myself better and clearer

Why do you suppose that any of the actions be masked out in the cartpole environment? None of them seem "invalid" - the agent can clearly do all three, in all states. There is an important difference between "invalid" and "not good". Invalid actions are ones that you know that the agent cannot take, due to e.g. rules of a game, or constraints in the environment. Whilst going left when the pole is already fallen a lot to the right and was still falling would be bad, but it is not invalid

Thanks to your comment and reply. I updated the answer above. Your answer is very dense (I'm still studying it), thus it  would be nide, if you could answer the question above with just  a solution 1 or solution 2, since I don't want you to reelaborate your very nice answer

Having read the other question, I don't understand the environment setup. I get the feeling that you are overthinking the problem, but I cannot identify exactly what is wrong. Sorry

I wanted to link to the picture and not to question in the other thread. I should have posted twice the same picture

Invalid actions are invalid because they cannot be taken at all by the agent. In board game scenarios that is usually because they are not allowed by the rules of the game, so a rules engine for that game can be used to filter actions down to the allowed set.
An action that can be taken by an agent, but that would result in an unwanted reward is not considered invalid, and would therefore not be filtered by any approach that is called "invalid action masking".
Generally you would not want to remove an action from consideration entirely because something predicted a negative reward. That is already the role of the agent, to learn an optimal policy, and filtering out actions based on incomplete information will reduce the agent's ability to explore the space and find an optimal path.
The example extension of CartPole does not define any invalid actions. With no other information to go on, all three actions are always valid. The agent can take them, and the environment will move into a new state. Contrast this to chess, where an action is to pick up an opponent's piece and move it as if it was some different piece. This is invalid because it breaks the rules of the game and completing such a move would stop the environment being a normal game of chess. Such moves are usually filtered - although another option is to allow them to be requested, give a negative reward leaving the game in the same state, and let the agent re-request its move (or, more drastically, have the agent immediately forfeit the game). Most game-playing agents filter and don't process invalid moves in any way, since learning the rules of the game is not the main objective.
If you know more than the initial agent, it is possible to apply filtering to action choices any way you want to. The effect will be that the agent never experiences taking those actions, and never learns about them. So the same filtering must be left in place when you finish the learning, and should probably be considered a non-learning part of the agent.
You can filter an action in this way using any logic you like. And you might decide to do so for instance, if outside of the reinforcement learning agent, you were able to predict something disastrous, such as a robot falling off a table causing damage.
You can also "truncate" learning by having an exploration approach that cuts off for the worst action value predictions. This is not a usual approach, and has the same caveat as any other arbitrary action filtering - it may reduce the effectiveness of the agent, because maybe a trajectory that seemed bad initially would turn out to have a better end result once different actions are learned for later states. If you stop an agent from exploring that, it may never learn otherwise (although some off-policy and background planning approaches might have already collected enough data to self-correct).
Truncating learning in that way would be unusual. But "soft" versions of that approach where the worst predictions get the least exploration, are more common. Thompson sampling for reinforcement learning is one such approach.

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


text:
A question about the goal selection in the second loop in the HER algorithm
I have to admit, that I still have problem digesting the HER algorithm proposed in the famous paper and despite the fact, that the idea behind it should be intuitive, I realize that it is not so easy to implement as expected. Even studying some of the implementations out there I cannot get a working version of my HER implementation.
Let's go straight to the point.
The basic idea is: in case a given goal is not reached, then the trajectory collected in the episode should be replayed after changing the goal into a pseudo-goal. Just to keep it simple, let's take the case where the last reached state is the new goal. The data is then stored in the replay memory buffer $\mathbb{R}$:
$(s_{t} \parallel g, a_{t}, r_{t}, s_{t+1} \parallel g, d_{t}) \to \mathbb{R}$
Let's take a look into the algorithm:

In the original algorithm, the collection of the trajectory is done in the loop inside the orange box (in the next loop those collected data are store in the replay memory buffer - standard experience replay).
Now looking in the green box below, you can see that there is a loop going from $0$ to $T-1$ doing basically two things:

Storing the trajectory into the replay buffer. Ok
Sampling for additional goals for replay $G = \mathbb{S}(current episode)$

Given that, I want to take the last state as a pseudo-goal, does it make sense to "set" this goal at every step t from $0$ to $T-1$? Would it not generate $T-1$ identical trajectories, which basically fill up the replay memory buffer but do not contribute to create meaningful data to pass to a NN later on?

Instead of writing "a question about the algorithm", can you please just put your question in the title? Thanks


text:
Mining repeated subsequences in a given sequence
Given an alphabet $I=\left\{i_1,i_2,\dots,i_n\right\}$ and a sequence $S=[e_1,e_2,\dots,e_m]$, where items $e_j \in I$, I am interested in finding every single pattern (subsequence of $S$) that appears in $S$ more than $N$ times, and that has a length $L$ between two limits: $m<L<M$. In case of overlapping between patterns, only the longest pattern should be considered.
For example, given $N=3$, $m=3$ and $M=6$, an alphabet $I=\left\{A,B,C,D,E,F\right\}$, and the following sequence $S$ (the asterisks simply mark the positions of the patterns in this example):
$$
S=[A,A,*F,F,A,A*,B,D,E,F,E,D,*F,F,A,A*,F,C,*C,A,B,D,D*,C,C,*C,A,B,D,D*,C,A,C,B,E,A,B,C,*F,F,A,A*,E,A,B,C,A,D,E,*F,F,A,A*,B,C,D,A,E,A,B,*C,A,B,D,D*,]
$$
The sought algorithm should be able to return the following patterns:
$$
[C,A,B,D,D], [F,F,A,A]
$$
together with their respective positions within $S$.
An available Python implementation would be very desirable (and a parallel implementation, even more so).
I was reading about BIDE algorithms, but I think this is not the correct approach here. Any ideas? Thanks in advance!

The algorithm would not yield CABDD because you specify, that each pattern has to occur more than 3 times, but this pattern occurs exactly 3 times.

You can do this similar to the BIDE approach. It can be done like this:
class TreeNode:
    def __init__(self, element, depth, count=0, parent=None):
        self.count= count
        self.element= element
        self.depth= depth
        self.subnodes= dict()
        self.parent= parent

    def __repr__(self):
        return f'{self.__class__.__name__}({self.element}, {self.depth}, {self.count})'

    def get_subnode(self, element, create=True):
        if create is True:
            return self.subnodes.setdefault(element, TreeNode(
                element,
                self.depth+1,
                count=0,
                parent=self
            )
        )
        else:
            return self.subnodes.get(element)

    def get_subnode_increasing_count(self, element):
        subnode= self.get_subnode(element)
        subnode.count+= 1
        return subnode

    def harvest(self, N, m, M, prefix=[], append_result_to=None):
        # get all sequences which occurs more than N times
        # and have a length (depth) of m < depth < M
        prefix= prefix.copy()
        prefix_len= len(prefix)
        if append_result_to is None:
            result= list()
        else:
            result= append_result_to
        if self.element is not None:
            prefix.append(self.element)
            prefix_len+= 1
        if N >= self.count or prefix_len >= M:
            return result
        if N < self.count and m < prefix_len and prefix_len < M:
            # the subsequence matches the constraints
            result.append(prefix)
        for subnode in self.subnodes.values():
            subnode.harvest(
                N,
                m,
                M,
                prefix=prefix,
                append_result_to=result
            )
        return result

    def get_prefix(self):
        if self.parent is None:
            prefix= []
        else:
            prefix= self.parent.get_prefix()
        if self.element is not None:
            prefix.append(self.element)
        return prefix

    def print_tree_counts(self, leaves_only=False, min_count=0):
        if leaves_only is False or not self.subnodes:
            if self.count >= min_count:
                print(self.get_prefix(), self.count)
        for subnode in self.subnodes.values():
            subnode.print_tree_counts(leaves_only=leaves_only, min_count=min_count)

sequential approach
def find_patterns(S, N, m, M):
    root= TreeNode(None, 0, 0)
    active_nodes= []
    for el in S:
        root.count+=1
        # append the root node
        active_nodes.append(root)
        # now replace all nodes in active nodes by the node
        # that is reached one level deeper following el
        active_nodes= [node.get_subnode_increasing_count(el) for node in active_nodes if node.depth < M]

    # now harvest the tree after applying the restrictions
    return root, root.harvest(N, m, M)

S='AAFFAABDEFEDFFAAFCCABDDCCCABDDCACBEABCFFAAEABCADEFFAABCDAEABCABDD'
root, patterns= find_patterns(S, 3, 3, 6)
patterns

The result is:
[['F', 'F', 'A', 'A']]

Your second pattern occurs exactly 3 times and so doesn't fullfill the requirement of > 3 occurances ([C,A,B,D,D]).
modifications for parallel processing
To make it processable in parallel you can do a slide modification. Just create another method in TreeNode, that allows to merge nodes. Like this:
def merge_nodes(self, other_nodes):
    # merge other_nodes into this node
    # including all subnodes
    if len(other_nodes) > 0:
        elements= set()
        for other_node in other_nodes:
            self.count+= other_node.count
            elements.update(other_node.subnodes.keys())
        # elements now contains the set of the next elements
        # with which the sequence continues across the
        # other nodes
        for element in elements:
            # get the node of the resulting tree that represents
            # the sequnce continuing with element, if there is
            # no such subnode, create one, since there is at least
            # one other node that counted sequence seq + element
            my_subnode= self.get_subnode(element, create=True)
            other_subnodes= list()
            for other_node in other_nodes:
                # now get the subnode for each other node, that
                # represents the same sequence (seq + element)
                other_subnode= other_node.get_subnode(element, create=False)
                if other_subnode is not None:
                    other_subnodes.append(other_subnode)
            # merge the subnode the same way
            my_subnode.merge_nodes(other_subnodes)

Now you can call find_patterns on subtrees, but you need to take into account, that you may not split the input sequence normally. You need to define some overlapping sequence part, so that patterns, that begin at the end of one sequence-fragment can be completed but that this overlapping sequences need to be counted differently (otherwise you get double-counts, which lead to wrong inputs). So you have to make sure, that only patterns, which began in the sequence fragment are continued with the overlap part, but that no new patterns are started in the overlap part, because you count them elsewere:
def find_patterns(S, N, m, M, overlap=[]):
    root= TreeNode(None, 0, count=0, parent=None)
    active_nodes= []
    def process_element(active_nodes, element, M):
        return [
            node.get_subnode_increasing_count(element)
                for node in active_nodes
                    if node.depth < M
        ]
    for el in S:
        root.count+=1
        # append the root node
        active_nodes.append(root)
        # now replace all nodes in active nodes by the node
        # that is reached one level deeper following el
        active_nodes= process_element(active_nodes, el, M)
    # complete the already started sequences with the
    # overlapping sequence (the sequence that may be
    # processed in another process)
    for el in overlap:
        active_nodes= process_element(active_nodes, el, M)
    # now harvest the tree after applying the restrictions
    return root, root.harvest(N, m, M)

Now you can do:
split_point= len(S) // 2
S1= S[split_point:]
S2= S[:split_point]
S1_overlap= S2[:10]
# in fact you could have just used :5 above,
# but that doesn't affect the result
r1, _= find_patterns(S1, 3, 3, 6, overlap=S1_overlap)
# Note: you could safely start the comand in the next
# line in parallel to the previous call of find_patterns
# and of course, you could split your sequence in as
# many fragments, as you like, as long as you maintain
# the overlap correctly and call merge_nodes afterwards
r2, _= find_patterns(S2, 3, 3, 6)
r1.merge_nodes([r2])
patterns= r1.harvest(3, 3, 6)

This yields the same result as above. To make it a bit clearer, what I mean with the overlap part:
S1 is 'CBEABCFFAAEABCADEFFAABCDAEABCABDD'
S2 is 'AAFFAABDEFEDFFAAFCCABDDCCCABDDCA'
S1_overlap is 'AAFFAABDEF'

With find_patterns(S1, 3, 3, 6) you would only search for repeated patterns in S1, so it would not consider patterns which begin with the part BDD (starting at the end of S1) and are continued within S2. With find_patterns(S1, 3, 3, 6, overlap=S1_overlap) I consider these patterns as well.

That's pretty impressive, thanks! Any reference on how you got this solution? Did you make it from scratch?

Yes, I created it from scratch, but the idea with the tree is used in other data mining methods as well (but I don't remember, how they are called).

Cool! I would really appreciaty if you can provide a reference to those method, or their names


text:
How to prove that $V^\star$ is optimal if and only if it satisfies the Bellman equation?
The Question

I'd like to prove that a function $V$ (like in reinforcement learning) is optimal iff it satisfies the bellman equation. A lot of places online reference this fact, but none prove it. For formal details, see the following section, with the theorem at the end.
Formal definitions

In reinforcement learning, a value function $V$ is used to derive a policy: $$\pi_{V}\left(a\mid s\right)=\begin{cases}
1 & a=\underset{a'}{\mathrm{argmax}}Q^{\pi_{V}}\left(s,a\right)\\
0 & otherwise
\end{cases}$$ where $$Q^{\pi_{V}}\left(s,a\right)=r\left(s,a\right)+\gamma\underset{s'\sim p\left(s'\mid s,a\right)}{\mathbb{E}}\left[V\left(s'\right)\right]$$ (here $r$ is the reward function and $p$ is the transition probability from a state to another based on the action)
a policy $\pi^\star$ is called optimal if $$\pi^{\star}=\underset{\pi}{\mathrm{argmax}}\mathbb{E}_{\pi}\left[\sum_{t=0}^{\infty}\gamma^{t}\cdot r\left(s_{t},a_{t}\right)\mid s_{0}=s\right]$$ where $s$ is the initial state, and the expectation is over the transition probability under the assumption of following the policy $p$.
We also say that $V$ is optimal if $pi_{V}$ is optimal.
The Theorem I want to prove is that a function $V^\star$ is optimal if and only if it satisfies the Bellman equation:
$$V^{\star}\left(s\right)=\max_{a}r\left(s,a\right)+\gamma\mathbb{E}\left[V^{\star}\left(s'\right)\right]$$

I'll just give you a few tips. 1. To prove something of the form "A if and only if B", you need to prove 2 things: If A then B AND if B then A. 2. You need to know the definition of an optimal value function. How is an optimal value function different from a non-optimal one? But you also need to know the definition of a value function (in general).

I believe there is a proof in the David Silver's RL course, or the Sutton & Barto RL book

Your definition of a policy above is circular, and also you need to first differentiate Bellman equation with its optimality equation version.

@mohottnad where is the circularity?

@nbro haven't I defined what an optimal policy is? A non-optimal one is a policy with a smaller reward expectation

A friend of mine showed me the following "post", and the proof is actually quite short.
They prove that $$\lim_{k\to\infty}V_{k}=V^{\star}$$ where $V_k$ is defined in the post. Now if the original $V$ satisfies the bellman equation already, it means that $$\lim_{k\to\infty}V_{k}=V$$ and therefore $V^{\star}=V$. The other direction is of course easy.


text:
Relation between SDE diffusion and DDPM/DDIM
Background & Definitions

In DDPM, the diffusion backward step is described as follows (where $z\sim \mathcal{N}(0,I)$ and $x_{T}\sim \mathcal{N}(0,I)$):

and in DDIM we have

while in the SDE formulation (from the Fokker-Planck equation) the step is:

where $D_\theta$ is the denoiser network trying to predict $x_0$ (We can also instead predict the noise $\epsilon_\theta$ using the relation $x_t = x_0 + \sigma(t)\cdot\epsilon$), and $s,\sigma$ are the functions defining the diffusion forward process: $x_t \sim \mathcal{N}(s(t)\cdot x_0, s(t)\sigma(t)I)$.
The Question

I was wondering if the SDE formulation is actually a "generalized" version of DDPM. Meaning, can we find $s,\sigma$ s.t. the two processes are the same. (meaning, the discretization of SDE can result in DDIM/DDPM).
My hypothesis is that they are, and since in DDPM/DDIM I believe the forward process is  described by $$\begin{array}{c}
x_{t}\sim\mathcal{N}\left(\sqrt{\bar{\alpha}_{t}}x_{0},\left(1-\bar{\alpha}_{t}\right)I\right)\\
\alpha_{t}:=1-\beta_{t}\\
\bar{\alpha}_{t}=\prod\limits _{k=1}^{t}\alpha_{k}
\end{array}$$
and in the SDE formulation it is described by $$x_t \sim \mathcal{N}(s(t)\cdot x_0, s(t)\sigma(t)I)$$ an appropriate choice seems to be $$\begin{array}{c}
s\left(t\right)=\sqrt{\bar{\alpha}_{t}}\\
\sigma\left(t\right)=\frac{1-\bar{\alpha}}{\sqrt{\bar{\alpha}_{t}}}
\end{array}$$
but of course this is not defined for all $t$ values since SDE is continuous and DDPM/DDIM are discrete. I am unable to prove that the backwards processes are indeed the same. Perhaps a different choice of $s,\sigma$ is needed? or perhaps they can't be shown to be equivalent/need additional components.


text:
How to design my Neural Network for Game AI
For my school project, I have to develop an agent to play my game.

The base I have is a 'GameManager' which call 2 AIs, each taking a random move to do.
To make my AI perform, I decided to make a deep RL algorithm.
Here is how I've designed my solution.
1st : the board is a 8x8 board. making 112 possible lines to draw.
2nd : on each decision, my Agent has to choose 1 line in the remaining one.
3rd : each decision the Agent take is one among 112 possible.
I read some codes on the internet, the most relevant for me was a 'CartPole' example, which is a cart we have to slide to prevent a mass to fall.
I made an architecture which is this one:
a game is simulated:
the board is clean, making all 112 possibilities available.
Our Agent is interroged by the gameManager to make a move passing him the actual state of the game
(the state shape is a 112*1 vector of Boolean values, 1 means a line can be drawn, 0 means there is already a line on this position)
(the action shape is a vector of 112*1 Boolean values, All values are set to 'False' except the line we want to draw)
So, our Agent return his move decision.
Each time our agent perform a move, i store the initial state, the action we take, the reward we get performing the action, the state we reach and a boolean to know if the game is done or not.
The rewards I choose are:
+1 if our action make us close a box,
-1 if our action make other close a box,
+10 if our action make us win the game,
-10 if our action make us loose the game
The point is it's my 1st Deep learning project and I'm not sure about the mecanism i'm doing.
when i launch a simulation, the Neural Network is running, but the move he does seems not to be better and better.
I give you the code I've wrote:
Here is the gameManager code:
while True:
hasMadeABox = False
gameIsEnd = False
rewardFCB = 0
doneFCB = False

if GRAPHIC_MODE:
    for event in pygame.event.get():
        if event.type == pygame.QUIT:
            pygame.quit()
            sys.exit()
    disp_board()

if playerTurns=="1":
    stateFCB = possibilitiesToBoolList(possible_moves[0])

boolArrayPossibleMoves = possibilitiesToBoolList(possible_moves[0])

theAction = players[playerTurns].play(boxes, possible_moves[0], boolArrayPossibleMoves, False)
#print(possible_moves[0])
#print(theAction)
if playerTurns =="1":
    actionFCB = theAction

if playerTurns=="1":
    is_box = move(True, theAction)

elif playerTurns=="2":
    is_box = move(False, theAction)

if is_box:
    if playerTurns =="1":
        #rewardFCB = 1
        rewardFCB = 1
        pass
    else:
        rewardFCB = -1
    hasMadeABox = True

if check_complete():
    gameIsEnd = True
    rewardFCB += 10 if score[0]>score[1] else -10 #does loosing is a reward null or negativ ?
    queueOfLastGame.pop(0)

    #Scotch pour affichage winrate
    isWin = 1 if score[0]>score[1] else -1
    queueOfLastGame.append(isWin)
    if queueOfLastGame.count(-1)+queueOfLastGame.count(1) > 0:
        print(queueOfLastGame.count(1)/(queueOfLastGame.count(-1)+queueOfLastGame.count(1)) * 100 , " % Winrate")

    doneFCB = True

if playerTurns=="1" and hasMadeABox:
    #si c'est notre IA vient de faire un carré
    #on connait directement l'état qui succede
    nextStateFCB = possibilitiesToBoolList(possible_moves[0])

if playerTurns=="2":
    nextStateFCB = possibilitiesToBoolList(possible_moves[0])

if nextStateFCB is not None:
    bufferSARS.append([stateFCB, actionFCB, rewardFCB, nextStateFCB, doneFCB])
    #ai_player_1.remember(stateFCB, actionFCB, rewardFCB, nextStateFCB, doneFCB)
    rewardFCB = 0
    nextStateFCB = None

if gameIsEnd:
    flushBufferSARS()
    reset()
    continue

#switch user to play if game is not end
if not hasMadeABox:
    playerTurns="1" if playerTurns == "2" else "2"

And here's my code about the Agent:
class Agent:
def __init__(self, name, possibleActions, stateSize, actionSize, isHuman=False, alpha=0.001, alphaDecay=0.01, batchSize=2048, learningRate=0.1, epsilon= 0.9, gamma = 0.996, hasToTrain=True):

    self._memory = deque(maxlen=100000)
    self._actualEpisode=1
    self._episodes=7000
    self._name=name
    self._possibleAction=possibleActions
    self._isHuman=isHuman
    self._epsilon=epsilon
    self._epsilonDecay = 0.99
    self._epsilonMin = 0.05
    self._gamma=gamma
    self._stateSize=stateSize
    self._actionSize=actionSize
    self._alpha=alpha
    self._alphaDecay=alphaDecay
    self._hasToTrain=hasToTrain
    self._batchSize=batchSize

    self._totalIllegalMove = 0
    self._totalLegalMove = 0

    self._path = "./modelWeightSave/"

    self._model = self._buildModel()

def save_model(self):
    self._model.save(self._path)

def getName(self):
    return self._name

def _buildModel(self):
    model = Sequential()

    model.add(Dense(128, input_dim=self._stateSize, activation='relu'))
    model.add(Dense(256, kernel_initializer='normal', activation='relu'))
    model.add(Dense(256, kernel_initializer='normal', activation='relu'))
    model.add(Dense(256, kernel_initializer='normal', activation='relu'))
    model.add(Dense(128, kernel_initializer='normal', activation='relu'))
    model.add(Dense(self._actionSize, kernel_initializer='normal', activation='relu'))

    model.compile(loss='categorical_crossentropy', optimizer=Adam(lr=self._alpha), metrics=['accuracy'])
    #if os.path.isfile(self._path):
        #model.load_weights(self._path)
    return model

def act(self, UNUSED_state, stateAsBool):
    playableIndexes = []
    for i in range(len(stateAsBool[0])):
        if stateAsBool[0][i] == 1:
            playableIndexes.append(i)
    indexForRand = playableIndexes[random.randint(0, len(playableIndexes) - 1)]

    if np.random.random() <= self._epsilon:
        action= [0]*self._actionSize
        action[indexForRand]=1

    else:
        arrayState = np.array(stateAsBool)

        action = self._model.predict(arrayState)
        #Set index of max esperence to 1, we play this line.
        tmp=[0]*self._actionSize
        tmp[np.argmax(action)] = 1
        action = tmp

        isLegalMove = True
        if sum(action) != 1:
            isLegalMove = False
        for i in range(len(action)):
            if action[i] == 1:
                if stateAsBool[0][i] == 0:
                    isLegalMove = False
                    break

        if isLegalMove:
            pass
            #print("Legal move")
        else:
            #print("Illegal move")
            #AI try to play on an already draw line, we choose a random line in remainings
            self._totalIllegalMove+=1
            action = [0] * self._actionSize
            action[indexForRand] = 1

    #print("My AI took action : ",action)
    return action

def remember(self, state, action, reward, nextState, done):
    self._memory.append((state.copy(), action, reward, nextState, done))

    self._actualEpisode+=1
    if self._actualEpisode > self._episodes:
        self._actualEpisode = 0
        self.replay(self._batchSize)

def replay(self, batchSize):
    x_batch, y_batch = [], []
    minibatch = random.sample(self._memory, min(len(self._memory), self._batchSize))
    for state, action, reward, next_state, done in minibatch:
        actionIndex = np.argmax(action)
        y_target = self._model.predict(state)
        y_target[0][actionIndex] = reward if done else reward + self._gamma * np.max(self._model.predict(next_state)[0])
        x_batch.append(state[0])
        y_batch.append(y_target[0])
    self._model.fit(np.array(x_batch), np.array(y_batch),epochs=10, batch_size=len(x_batch), verbose=1)

    if self._epsilon > self._epsilonMin:
        self._epsilon *= self._epsilonDecay

    self.save_model()

def play(self, board, state, statesAsBool, player):
    actionTaken= self.act(state, statesAsBool)
    return actionTaken

def callBackOnPreviousMove(self, state, action, reward, nextState, done):
    self.remember(state, action, reward, nextState, done)

Example of output i have during fit method:
Epoch 1/10

1/1 [==============================] - 0s 0s/step - loss: 109.9612 - accuracy: 0.8867

Epoch 2/10

1/1 [==============================] - 0s 998us/step - loss: 109.9467 - accuracy: 0.8867

Epoch 3/10

1/1 [==============================] - 0s 0s/step - loss: 109.9456 - accuracy: 0.8867

Epoch 4/10

1/1 [==============================] - 0s 0s/step - loss: 109.9332 - accuracy: 0.8867

Epoch 5/10

1/1 [==============================] - 0s 998us/step - loss: 109.9339 - accuracy: 0.8867

Epoch 6/10

1/1 [==============================] - 0s 0s/step - loss: 109.9337 - accuracy: 0.8867

Epoch 7/10

1/1 [==============================] - 0s 997us/step - loss: 109.9305 - accuracy: 0.8867

Epoch 8/10

1/1 [==============================] - 0s 0s/step - loss: 109.9314 - accuracy: 0.8867

Epoch 9/10

1/1 [==============================] - 0s 0s/step - loss: 109.9306 - accuracy: 0.8867

Epoch 10/10

1/1 [==============================] - 0s 0s/step - loss: 109.9301 - accuracy: 0.8867

My questions are:

Is my architecture good
(inputs = [0,0,1,1,0,0,1,0.....,1,0] (112x1 shape) to represent the state, and
output = [0,0,0,0,0,0,0,0,0,1,0,0,0...0,0,0,0] (112x1 shape with only one '1') )
to represent an action ?

How to nicely choose the architecture of the Neural Network model (self._model) (I have only the basics of Neural Network, so I don't really know all activation fonction, how to design the hiden layers, choose a loss...)

To train my NN, is it good to call the 'fit' function with (state, action) as parameter to make it learn?

Is there something really important I forget in my design to make it work?

Please, ask one question per post. If you have multiple questions, ask each of them in their separate post.

they are highly linked :/ post 4 time the same description with only a different question should be a waste of time I think here, but i'll try to make differents posts for the next time, thanks


text:
How can I use Monte Carlo Dropout in a pre-trained CNN model?
In Monte Carlo Dropout (MCD), I know that I should enable dropout during training and testing, then get multiple predictions for the same input $x$ by performing multiple forward passes with $x$, then, for example, average these predictions.
Let's suppose I want to fine-tune a pre-trained model and get MCD uncertainty estimations, how should I add dropout layers?

on the fully-connected layers;
after every convolutional layer.

I've read some papers and implementations where one applies dropout at fully-connected layers only, using a pre-trained model. However, when using a custom model, usually one adds dropout after every convolutional layer. This work builds two configurations:

dropout on the fully-connected layers;
dropout after resnet blocks.

The first configuration performs better, but I'm unsure if this is an actual uncertainty estimation from resnet. The results show that there is a correlation between high uncertainty predictions and incorrect predictions. So, would this be a good way of estimating uncertainty? My shot is "yes", because even though there are no nodes being sampled from the backbone, the sampling in the fully-connected layer forces a smooth variation in the backbone, generating a low-variance ensemble. But, I'm quite a beginner on MCD so, any help would be appreciated.


text:
Explain the difference in graphical patterns between discriminator fake loss and generator loss in GAN
In GAN (generative adversarial networks), let us take "binary cross-entropy" as the loss function for discriminator $$(overall \; loss = -\sum log(D(x_i)) -\sum log(1-D(G(z_i))) $$
$$ where \; x_i = real \; image \; pixel \; matrix$$
$$ and \; z_i = a \; vector \; from \; latent \; space$$.
Let us define discriminator real loss and fake loss:
$$ d_{fake \; loss} = -\sum log(1-D(G(Z)))$$
$$ d_{real \; loss} = -\sum log(D(x))$$
$$ d_{fake \; loss} \; implies \; discriminator \; loss \; against \; fake \; images$$
$$ d_{real \; loss} \; implies \; discriminator \; loss \; against \; real \; images$$
Generator Loss :
$$ g_{loss} = -\sum log(D(G(z_i)))$$
Since the functions are similar, we should be expecting some similarity in graphical patterns (i.e since none of the functions are inherently oscillatory, I expect that if one comes out to be oscillatory, the other one should be the same as well). But, If you refer to chapter 10 of the book "Generative Adversarial Networks with python by Jason Brownlee", we find some difference. The following are the graphs published in the book

Can anyone explain the difference in the plots between discriminator fake loss and generator loss (mathematically)?

You can use latex on this site. So, please, edit your post to format it with latex.

Your statement that  we should be expecting some similarity in graphical patterns is not correct. The GAN loss takes the following form:
$$
\min_G \max_D V(D,G) = \mathbb{E}_{x \sim p_{data}(x)} [\log D(x)] + \\
+ \mathbb{E}_{z \sim p_z(z)} [\log (1 - D(G(z)))]\label{minimax}
$$
We want to maximize this loss w.r.t. D in order to distinguish between real and fake samples ($D(x)\rightarrow 1$ and $D(G(z))\rightarrow 0$), whereas the task of G is exactly the opposite. We want to minimize the function w.r.t. G so that the difference between real and generated data will be minimal. Thus, the problem becomes a minimax non-cooperative game. Here is a good explanation of the loss.
Training GANs requires finding a Nash equilibrium of a non-convex game with continuous, high dimensional parameters. GANs are typically trained using gradient descent techniques that are designed to find a low value of a cost function, rather than to find the Nash equilibrium of a game. Two models are trained simultaneously and each model updates its cost independently with no respect to another player in the game.
In other words, as soon as D becomes better, G becomes also better. Updating the gradient of both models concurrently cannot guarantee a convergence. For more information, see Improved Techniques for Training GANs and Wasserstein GAN.
Moreover, since D and G play a non-cooperative game, it can be shown that there are some cases when it is impossible to find a Nash equilibrium at all:


text:
What dataset might Elon Musk's Dall-E have used?
Dall-E, it can generate many imaginative images from the description, even some peculiar images, how did they actually create this kind of dataset to train this AI , because there is not much of that kind of data which include weird images and descriptive text, how did they create this massive dataset. Does anyone have any idea?
If you have no idea what I am talking about, please refer to this link: https://openai.com/blog/dall-e/.

Have you read the article that you're linking us to, i.e. https://openai.com/blog/dall-e/? It says they are using a smaller version of GPT-3. They even say that they use a dataset of descriptions and image pairs. I didn't fully read it, but this already looks like a partial answer to your question. So, what's your question?

yes, it gets clearer for me when I read deeper into it, and I don't quite understand how this data is obtained and reformatted for training to make this AI working. thank you

Ok, then edit your post to ask specifically that (although that will actually and partially invalidate the current answer below), i.e. how exactly is the dataset of text-images created? How many images does it contain? What are the sizes of these images, etc? Or whatever you are really insterested in. Because, otherwise, this post doesn't make much sense, given that the answer to the current question can be found in the article that you're linking to and suggesting us to read in order to be familiar with Dall-E (which you supposedly were).

That edit didn't really improve the post. Please, read my comments above again.

Some answers here point to DALL-E using the same dataset as GPT-3, but that doesn't answer HOW the dataset was created or anything about the images used in the dataset to train DALL-E. At some point, an image dataset was needed to train an AI, either one that generated more images for DALL-E to learn from, or directly to train DALL-E.

DALL·E is a 12-billion parameter version of GPT-3 trained to generate images from text descriptions

should be the same data they used to train the GPT-3

but what did they use as output for their input text

they are mapping text to images. so their dataset should have a pairs of text and image and their model trained on mapping these pairs.


text:
How is input defined for a biaxial lstm network for generating music?
I am reading Composing Music With Recurrent Neural Networks by Daniel D. Johnson. But I am really confused about the input passed to this network. If we pass notes of music along the time axis, then what is passed along the note axis?

The author says:

If we make a stack of identical recurrent neural networks, one for each output note, and give each one a local neighborhood (for example, one octave above and below) around the note as its input, then we have a system that is invariant in both time and notes: the network can work with relative inputs in both directions.

This might mean that the inputs passed to the network along the note axis are fixed representations of notes in the vocabulary. But I am not sure.
I am also having a hard time understanding the input passed to this network as the author explains a few paragraphs below. (Position, Pitchclass, Previous Vicinity, Previous Context, Beat).
Also, at some point, the author talks about RNN along the note axis. But in the architecture, there only seems to be RNN along the time axis. I would really appreciate is anyone could give me some more information to understand how this Biaxial Network is setup. This article by Deep Dark Learning was a little helpful but I am still not fully sure what is going on here.


text:
How is the shape of the anchor boxes predefined in YOLO algorithm?
I am not sure if I really understand how anchor boxes are defined. As far as I understand, in YOLO algorithm you define a set of "good" shapes (anchor boxes) that may contain the object you are trying to detect for each cell.
However, I don't really understand how do you predefine the shape of these anchor boxes. As far as I have seen, there are examples in which the algorithm outputs bx, by, bh and bw values for each anchor box. Are you actually giving "freedom" to the algorithm to define these four values, or somehow is it being defined a fixed ratio between bh and bw for each of the anchor boxes? And how is this ratio defined in the output?


text:
What are the benefits of Cross Stage Partial Connections over Residual Connections?
Cross Stage Partial Connections (CSPC) try to solve the next problems:

Reduce the computations of the model in order to make it more suitable for edge devices.
Reduce memory usage.
Better backpropagate the gradient.

I cannot really understand how the first two points are actually achieved with this type of connection. Furthermore, in CSPC, the skip connection is just a slice of the feature map, and in Residual Connections, the skip connection is all the feature map. Aren't CSPC and Residual Connections (with concatenation) actually "almost" the same thing? Then, what advantages do you get for connecting with deeper layers only a slice of the previous feature map (CSPC) vs the whole feature map (Residual Connection)?


text:
How vision models based on CNNs learn the relative positions of each pixel in the image?
A CNN model is based on a series of filters applied to an image. However, these filters can only "see" a small portion of the image and they have no information of the relative position of the pixels that they are analyzing with respect to the image coordinates. Likewise, deeper in the network, they have no information of the the position of the field of view that they are analyzing with respect to the coordinate-system of the image. In other words, if trained correctly, these modes are translation-invariant and they do not "know" the region of the image to which some features belong (ie, they have no information if some extracted features belong to the lower, upper, right or left part of the image).
I was wondering how a model like, for example, YOLO can infer the relative coordinates of the objects that it is detecting, without having this information. I understand that the image is divided in in a grid of cells and that gives some notion of region (ie, part of the image that is being analyzed). However, we still have to guess the width, height and relative x,y position with respect to the cell. Why don't we overlap the input image (or extracted features) with some kind of positional encoding (the x,y coordinates for example), so that the model has information of the region of the image to which some features belong?
This question also applies to other CNN models like, for example, U-Net architectures. I think that it may be useful to have some information of the position of the pixels/feature map with respect to the image's coordinates in some problems. For example, to segment the road in self-driving problems, it will be very useful to "know" if the region of the image that is being analyzed is in the bottom part of the image as, most-likely, the road will be found there.
How does these models infer this information? And, why is not common to add this "positional encoding" in deep learning projects applied to images?

Can you explain what you mean when you say it infers the coordinates? do you give it a single pixel and it tells you x=100 y=200?

With this I mean that it is some useful information. It depends on the model, but in some problems, knowing that some pixels belong to a particular region of the image may be useful (for example, when segmenting the road it is usefull to know if the region is the lower part of the image or the upper part). As well, some models like YOLO directly outputs the coordinates (x, y, w, h) of the objects it is detecting.

After the convolutional layers there are usually dense layers.

You are right. I guess that the dense layers may give a sense of spatial location as they are analyzing the image as a whole. However, I see it as a very indirect way to get this sense of spatial location. Why don't we usually add a positional encoding to the input directly? In addition, you don't have this in purely convolutional models such as CNNs for segmentation.

I don't know. You could try it and see. For segmentation the network is probably not aware of which part of the picture it's looking at although I suppose some positional encoding could help it decide (e.g. sky is at the top)

A filter value in a smaller deeper layer is in a fixed relationship to the geometry of the input.
Its position in the filter defines its relation to an image.
But positional encoding is actually needed and common in transformers etc, where that is not the case.

Your answer could be improved with additional supporting information. Please [edit] to add further details, such as citations or documentation, so that others can confirm that your answer is correct. You can find more information on how to write good answers in the help center.

Well, I see what you say that the deeper you go, the bigger is the field of view and the features extracted will be related to that field of view and nothing else. However, you still have the "problem" of not knowing to what exact region of the image (coordinates x,y) does those features belong.

In a purely convolutional network, shift equivariance is inherent (ignoring boundary effects), meaning the network lacks an awareness of specific x/y coordinates. Introducing positional information by overlaying the pixel grid with coordinates would enable the model to gain a sense of distance within the image.
However, incorporating absolute positional encoding would break this shift equivariance. Consequently, the model would lose this advantageous property and would function more similarly to applying an MLP directly to the entire image.
It is important to note that shift equivariance is typically considered a beneficial feature of CNNs, as it allows for the detection of objects regardless of their location within the image.
Nonetheless, if you require a sense of absolute position while still retaining the shared parameter architecture of CNNs, you can indeed opt for absolute positional encoding.


text:
Why do I get higher average dice accuracy for less data
I am working on image segmentation of MRI thigh images with deep learning (Unet). I noticed that I get a higher average dice accuracy over my predicted masks if I have less samples in the test data set.
I am calculating it in tensorflow as
def dice_coefficient(y_true, y_pred, smooth=0.00001):
y_true_f = K.flatten(y_true)
y_pred_f = K.flatten(y_pred)
intersection = K.sum(y_true_f * y_pred_f)
return (2. * intersection + smooth) / (K.sum(y_true_f) + K.sum(y_pred_f) + smooth)

the difference is 0.003 if I have 4x more samples.
I am calculating the dice coefficient over each MRI 2D slice
Why could this be?
This figure shows how the accuracy decreases with the fraction of samples. I start with 0.1 of the data until the whole data set. The splitting of the data was random

How did you create the subset of your test data (to generate the "less samples" group)? Did you sample a different group every time, and re-tested the accuracy each time? Exactly how much did the accuracy improve, and what is the variance of this accuracy as the subset test data varies?

well, I noticed that the validation accuracy was always higher by a small gap (around 0.003 of the dice ratio) I removed the dropout and it was still the same. So I did a crossvalidation and divided the sets randomly and it was the same. I also just manually divided a test dataset into 10% and 90% and saw that the accuracy was slightly bigger for the smaller portion

Not sure if I read it right, but if the difference in validation accuracy is only by a factor of 0.003 then it's very small and likely a statistically insignificant difference (probably due to some sort of variance somewhere). If you'd still like to dive deeper into this, I think would be interesting to graph accuracy vs data size and test many different data sizes. That way you can see if there is a clear curve/pattern which mean there's something meaningful, or if it is just a flat line that fluctuates up and down which means its just randomness/variance

Well, this gap is always there between the validation and training set, independently of the random splitting. I just uploaded a graph accuracy vs data size


text:
DQN Agent with a 2D matrix as input in Keras
I have a Reinforcement Learning environment where the state is a 2D matrix with 0s and 1s (only one column with the value of 1 in each row).
Example:
(
 (0, 1, 0),
 (0, 0, 1),
 (1, 0, 0),
 (0, 0, 0),
 (0, 1, 0)
)

The action the agent must take is for each row in the input, choose one resource out of 12 resources the agent has if there is a column with the value of 1 in that row, else choose no resource if the row has 0s only (example: row[3] wouldn't have any resources chosen for it by the agent). The rows correspond to the users the agent must allocate resources to.
In the step() method in the RL environment, the agent would receive a reward or a penalty depending on the action. If the reward is positive, the agent updates the state matrix, putting a 0 instead of 1 in the rows corresponding to the users that were allocated resources, which should be the next state. If the reward is negative, the episode ends, the environment resets and a new state is received by the agent
It came to my understanding that, in a deep learning approach, the DQN agent would receive a 2D matrix of 0s and 1s as input to its neural network (the state matrix), and output a vector with the chosen resources for each row of the input.
The network must choose a resource out of 12 resources for each row if that row has a 1 in it, and no resource is chosen if there is no column with the value of 1 in that row of the input. In other words, the network must choose an element out of 12 and output a vector with the chosen elements, depending on the input matrix.
Is there a way to do this using Deep Q-Learning and neural networks ?

I am having trouble picturing this - could you give an example so that it is clearer what " only one column with the value of 1 in each row" means, and also what the action selection looks like? Am I right in thinking there must be more rows than columns in this problem (or at least as many)? Also you should explain the consequence of the choice - is this to optimise some measure of success/results from the action vector, and if so what happens next?

For Q-learning to apply, two things should happen - 1) there needs to be some measure of usefulness or success, and 2) the input (state) should repeat with a variation, and the possible variations depend somehow on the action vector. It is not at all clear what these things might be from your description

@NeilSlater thank you for your comment, I edited my post. I hope it's better explained. Answering your questions, yes there are more rows than columns. In the step() method in the environment, the action choice is rewarded according to the constraints I have defined.

Thank you Ness, that is much clearer. I am still not sure what the purpose is though. Assuming for example that the agent chose (1, 5, 7, 0, 12) for allocating resources (where 0 is "no resource"), what would happen next? It is very important for choosing DQN and RL in general over some other algorithm: Will the values in the next matrix presented to the agent be in any way dependent on what the agent chose? Or another way to put things - are you trying to optimise a single function, or is there a time element with the goal of getting the best total result over multiple related inputs?

@NeilSlater originally, in my Q-learning agent, the action is another matrix of 0s and 1s, so row[0][1] = 1 would mean that resource0 was allocated to user1. But I got stuck trying to figure out how to do that. So, I had the idea of having the network choose from the resources. So, for example, the vector would have 10 elements (because we have 10 users (equals number of rows in the state matrix)), vector[1] = 5 would mean that resource5 was allocated to user1. That would help with the reward calculation later. I hope I answered your question.

It should be possible to have your original idea for an output. But that is not what what I was asking about. I am asking what happens after resource5 is allocated to user1 etc, and after you have worked out the reward. What happens next? Is there any concept of "next" here at all, or is the process you are trying to optimise a series of separate events each of which will be separately optimised according to the same kind of inputs and outputs?

@NeilSlater Hmm, I must say I'm a beginner at Reinforcement Learning, so I will try to answer you to the best of my ability. If the reward is positive, the agent updates the state matrix, putting a 0 instead of 1 in the rows corresponding to the users that were allocated resources, which should be the next state. If the reward is negative, the episode ends, the environment resets and a new state is received by the agent. The state wouldn't be exactly the same in each episode, the position of the 1 and 0s in each row would vary, hence the output would differ as well depending on the state.

OK, that is clearer. I suggest add this part to the question body, it is important: "If the reward is positive, the agent updates the state matrix, putting a 0 instead of 1 in the rows corresponding to the users that were allocated resources, which should be the next state. If the reward is negative, the episode ends, the environment resets and a new state is received by the agent". To me, this clearly describes a problem where reinforcement learning could be applied.

authors: عباس کیانوش فرد


text:
What does Deep Q-Learning (DQL) do?
Hello :) I'm required to write a document where I describe what DQL does in short.
This is what I wrote:
DQL: instead of a Q-table, a DNN is used to approximate the Q-values for each action based on a given state. Bear in mind that, we seek to find the optimal Q-value for a state-action pair at a time slot t, written as  $Q^* (s_t,a_t)$, which obeys the Bellman equation:
$$Q^*(s_t, a_t)=E\left [ R_{a_t}(s_t,s')+\gamma max_{a_{t+1}}Q^*(s_{t+1},a_{t+1}) \right ]$$
Where $Q^* (s_{t+1},a_{t+1})$ is the optimal Q-value for the next state-action pair $(s_{t+1},a_{t+1})$. The parameters of the DNN are updated every time step t, aiming to find the optimal policy $π^*=argmax_{a_t} Q^* (s_t,a_t)$ that maximizes the reward.
Is what I wrote correct? Should I say we seek to find the optimal Q-value for a state action pair at a time slot t or should I say we seek to train the DNN to resemble the optimal Q-value for a state action pair at a time slot t? Which one is correct?

Since DQL/DQN is usually deep it must efficiently utilize limited experience samples possibly multiple times during any mini-batch update according to above Bellman optimality equation. Also since the NN is really minimizing a loss function so you'd have another term involving your approximated Q-function's parameter, thus you'd better need 2 different networks for these two (same) function parameters to reduce optimization complexity.

yes it is somehow correct, but it doesn't give much info about the approximation part. also, note that TD methods (as q-learning) generally do not converge to local optima in approximation. For instance, in the case of linear approximation they can converge to TD fixed point which may differ from local optima. Also, off-policy methods like Q-learning may generally diverge. So while your saying they seek to find optimal Q-value, the generally don't in the case of approximation.


text:
How do we get the optimal value-function?
In here it says that: (is it correct?)
$$V^\pi = \sum_{a \in A}\pi(a|s)*Q^\pi(s,a)$$
And we have:
$$ V^*(s) = max_\pi V^\pi(s)$$
Also:
$$ V^*(s) = max_a Q^*(s, a) $$
Can someone demonstrate to me step by step how we got from $ V^*(s) = max_\pi V^\pi(s)$ to $ V^*(s) = max_a Q^*(s, a) $ ?
And is it correct that $ V^\pi(s) = max_{a \in A} Q^\pi(s,a) $ ?

Are you still having conceptual trouble for your two questions?

Bellman Expectation Equations
Let's first look at the definition of the value functions.
The state-value function $V^\pi(s_t)$ is defined as the expected return $G_t=\sum_{t'=t} \gamma^{t-t'} r_{t'}$ we get from state $s_t$, and then following the policy $\pi$ until termination:
$$\begin{align}
V^\pi(s_t)
&= \mathbb{E}_\pi\big[r_t + \gamma r_{t+1} + \gamma^2 r_{t+2}+\cdots\mid s_t\big] \\
&= \mathbb{E}_\pi\big[G_t\mid s_t\big] \\
&= \mathbb{E}_\pi\big[r_t + \gamma G_{t+1}\mid s_t] \\
&= \mathbb{E}_\pi\big[r_t + \gamma V^\pi(s_{t+1})\mid s_t]
\end{align}$$

Basically, we get a recursive equation in which $V^\pi(s_t)$, at the current time $t$, is defined as the immediate reward $r_t=r(s_t,a_t)$ plus the discounted state-value of the next timestep $t+1$.

Now, the definition of the action-value function, $Q^\pi(s_t,a_t)$ is similar in that we start from state $s$, but take action $a$, and then follow $\pi$:
$$\begin{align}
Q^\pi(s_t,a_t)
&= \mathbb{E}_\pi\big[G_t\mid s_t,a_t\big] \\
&= \mathbb{E}_\pi\big[r_t + \gamma Q^\pi(s_{t+1}, a_{t+1})\mid s_t,a_t] \\
\end{align}$$
Turns out that these two value functions are related, in the sense that one can be written in terms of the other: such relationship is depicted by the backup diagrams.

For the $V$-function, the root of the backup tree is a state $s$ whose leaves are all the possible actions $a\in A$.
When computing $V^\pi(s)$ we need to consider all the leaves, i.e. the action-values. This is done by averaging their values and weighting by the probability of that action to occur (thus computing an expectation), which is provided by the policy. So, the diagram on the left provides a first relationship:
$$\begin{align}
V^\pi(s)
&=\mathbb{E}_\pi\big[Q^\pi(s,a)\big]\\
&= \sum_{a\in A}\pi(a\mid s) Q^\pi(s,a)
\end{align}$$
If we further expand the diagram (right) by executing a given action in the env, we experience a reward $r$, landing in a new state $s'\in S$. But we still need to reason in "expectation", this time starting from an action node. Stating that the Q-value can be written in terms of the state-value as follows:
$$\begin{align}
Q^\pi(s,a)
&=r(s,a) + \gamma\sum_{s'\in S}p(s'\mid s,a) V^\pi(s')
\end{align}$$
where $p(s'\mid s, a)$ is the probability (determined by the environment) of transitioning to next state $s'$ by tacking action $a$ in the current state $s$.

A similar diagrams exists for $Q$, except that we start from an action. Now we can substitute the new equations to compute both $V$ and $Q$ functions:
$$\begin{align}
V^\pi(s) &= \sum_{a\in A}\pi(a\mid s)\Big(r(s,a) + \gamma\sum_{s'\in S} p(s'\mid s,a) V^\pi(s') \Big)\\
Q^\pi(s,a)
&=r(s,a) + \gamma\sum_{s'\in S}p(s'\mid s,a) \sum_{a'\in A}\pi(a'\mid s') Q^\pi(s',a')
\end{align}$$
The last two equations allow to estimate both value functions in terms of them selves, instead the previous ones in terms of each other. Being able to compute such functions allow to evaluate the goodness of a policy $\pi$, know also as policy evaluation.
Bellman Optimality Equations
The expectation equations can be modified to obtain the optimal value functions: the key idea is to take the $\max$ instead of the expectations. In general we have:
$$\begin{align}
V^\star(s) &= \max_\pi V^\pi(s) \\
Q^\star(s,a) &= \max_\pi Q^\pi(s,a)
\end{align}$$
Considering the previous relationships between $V$ and $Q$, we can write:
$$\begin{align}
V^\star(s)
&= \max_\pi V^\pi(s) \\
&= \max_a Q^\star(s,a) \\
&= \max_a r(s,a) + \gamma \sum_{s'\in S}p(s'\mid s,a) V^\star(s')
\end{align}$$
In a similar way is possible to rewrite $Q^\star$ too. In general these formulas are explained by the following backup diagrams:

This is the optimal backup diagram for $V^\star$, a similar one exists for $Q^\star$.
Notice that the $\max$ is only taken over actions (that replaces $\sum_{a\in A}\pi(a\mid s)$ in the expectation eq.), and not over states. For the states we still consider an expectation but computed accordingly to the transition probability, i.e. $\sum_{s'\in S}p(s'\mid s, a)$.

Is it correct that $V^\pi(s)=\max_{a\in A}Q^\pi(s,a)$?

If you're doing policy evaluation no. Because $V^\pi(s)$ is the value averaged over actions, not the maximum which is useful for policy improvement instead: i.e. to derive the best action that the policy should take in $s$, which turns out to improve the current policy and so $V^\pi$ since it's an action that exploits.
Reference: David Silver's RL course.

There's no way to prove in general for any policy $\pi$ you always have $ V^\pi(s) = \max_{a \in A} Q^\pi(s,a) $ since there's no $\max$ operator on the left hand side and semantically there could exist averaging relationship over actions between them if your $\pi$ is a stochastic policy, but not $\max$ relationship.
For you main concern, here's the steps from your definition of $V^*(s), Q^*(s)$ and define optimal policy $$\pi^* = \arg \max_\pi (\sum_{a\in A}\pi(a | s) Q^\pi(s,a)) $$, then we have:
$$\begin{align}  V^*(s)
&= \max_\pi V^\pi(s) \\
 &= \max_\pi (\sum_{a\in A}\pi(a | s) Q^\pi(s,a)) \\
 &= \sum_{a\in A}\pi^*(a | s) Q^{\pi^*}(s,a) \end{align}$$
In case an optimal policy $\pi^*$ is deterministic, we have $\pi^*(a | s) = \begin{cases} 1,  a=a^*(s) \\ 0,  a \neq a^*(s) \end{cases}$, where $$a^*(s)=\arg \max_a Q^{\pi^*}(s,a)$$, thus we further have:
$$\begin{align} V^*(s)
 &= Q^{\pi^*}(s,a^*) \\
 &= \max_{a \in A} Q^{\pi^*}(s,a) \end{align}$$
Finally note if $\pi^*$ is deterministic, $$Q^{\pi^*}(s,a)=\max_\pi Q^\pi (s,a)=Q^*(s,a)$$, so you arrive at $$V^*(s) = \max_{a \in A} Q^*(s,a) $$


text:
DQN layers when state space and action space are multi dimensional
I have built my own RL environment, where a state is composed of two elements: the agent's position and a matrix of 0s and 1s (1 if a user has requested a service from the agent, 0 otherwise); an action is composed of 3 elements: the movement the agent chooses (up, down, left or right), a matrix of 0s and 1s (1 if a resource has been allocated to a user, 0 otherwise), and a vector representing the allocation of another type of resource (the vector contains the values allocated to the users).
I am currently trying to build a Deep Q Learning agent, I am a bit confused however as to what model (example Sequential), what type of layers (example Dense layers), how many layers, what activation mode I should use, and what the state and action sizes are. (Taking this code as a reference cartpole dqn agent)
I also do not know what my inputs and outputs should be.
The examples I have come across are rather simple and I don't know how to approach setting it all up for my agent.

assuming your agents position is a vector in $\mathbb{R}^d$, you could have a network that takes as input the position and passes it through a fully connected layer, the matrix passed through a convolutional layer, and the concatenate the two outputs of those layers to pass through further fully connected layers.

Genius ! Thank you so much for your answer ^^

I'll add my comment as an answer since you seem happy with it. :-)

This is not necessarily the only way to do this but it would be the approach I'd take.
Assuming your agents position is a vector in $\mathbb{R}^d$, then I would have the network take as input this position vector and pass it through a fully connected layer. I would also take as input the matrix and pass it through a convolutional layer(s) and flatten the output so it is now also a vector in $\mathbb{R}^{d'}$. I would then concatenate these together so you have a vector in $\mathbb{R}^{d + d'}$ and pass this through some fully connected layers as usual.
As for how many layers and which activation to use this is something you'll have to do by trial and error as this really is problem specific.
Your output would typically be a score for each of the action combinations, though as one of your outputs is a matrix this could potentially make things expensive to compute as you would need $2^{n \times m}$ binary representations just for the matrix ($n$ is the number of rows and $m$ is the number of columns).


text:
Keras DQN Model with Multiple Inputs and Multiple Outputs
I am trying to create a DQN agent where I have 2 inputs: the agent's position and a matrix of 0s and 1s.
The output is composed of the agent's new chosen position, a matrix of 0s and 1s (different from the input matrix), and a vector of values.
The first input is fed to an MLP network, the second input (matrix) is fed to a convolutional layer, then their outputs are fed to a FC network, or at least that's the idea.
This is my attempt so far, having this tutorial as a reference.
Here is the code:
First, create the MLP network
def create_mlp(self, arr, regress=False): # for the position input
        # define MLP network
        print("Array", arr)
        model = Sequential()
        model.add(Dense(env.rows * env.cols, input_shape=(len(arr)//2, len(arr)), activation="relu"))
        model.add(Dense((env.rows * env.cols)//2, activation="relu"))

        # check to see if the regression node should be added
        if regress:
            model.add(Dense(1, activation="linear"))

        # return our model
        return model

Then, the CNN
def create_cnn(self, width, height, depth=1, regress=False): # for the matrix
        # initialize the input shape and channel dimension
        inputShape = (height, width, depth)
        output_nodes = 6e2

        # define the model input
        inputs = Input(shape=inputShape)

        # if this is the first CONV layer then set the input
        # appropriately
        x = inputs

        input_layer = Input(shape=(width, height, depth))
        conv1 = Conv2D(100, 3, padding="same", activation="relu", input_shape=inputShape) (input_layer)
        pool1 = MaxPooling2D(pool_size=(2,2), padding="same")(conv1)
        flat = Flatten()(pool1)
        hidden1 = Dense(200, activation='softmax')(flat) #relu

        batchnorm1 = BatchNormalization()(hidden1)
        output_layer = Dense(output_nodes, activation="softmax")(batchnorm1)
        output_layer2 = Dense(output_nodes, activation="relu")(output_layer)
        output_reshape = Reshape((int(output_nodes), 1))(output_layer2)
        model = Model(inputs=input_layer, outputs=output_reshape)

        # return the CNN
        return model

Then, concatenate the two
def _build_model(self):
        # create the MLP and CNN models
        mlp = self.create_mlp(env.stateSpacePos)
        cnn = self.create_cnn(3, len(env.UEs))

        # create the input to our final set of layers as the *output* of both
        # the MLP and CNN
        combinedInput = concatenate([mlp.output, cnn.output])

        # our final FC layer head will have two dense layers, the final one
        # being our regression head
        x = Dense(len(env.stateSpacePos), activation="relu")(combinedInput)
        x = Dense(1, activation="linear")(x)

        # our final model will accept categorical/numerical data on the MLP
        # input and images on the CNN input, outputting a single value
        model = Model(inputs=[mlp.input, cnn.input], outputs=x)

        opt = Adam(lr=self.learning_rate, decay=self.epsilon_decay)
        model.compile(loss="mean_absolute_percentage_error", optimizer=opt)

        print(model.summary())

        return model

I have an error:
A `Concatenate` layer requires inputs with matching shapes except for the concat axis. Got inputs shapes: [(None, 32, 50), (None, 600, 1)]

The line of code that gives the error is:
combinedInput = concatenate([mlp.output, cnn.output])

This is the MLP summary

And this is the CNN summary

I'm a beginner at this, and I'm not where my mistakes are, the code does not work obviously but I do not know how to correct it.

Programming questions are off-topic here. Please, next time, ask this type of question on Stack Overflow. See https://ai.stackexchange.com/help/on-topic for more details.

Oh okay, sorry.

Here we focus on the theoretical aspects of AI, including RL. So, if you have a question about the theory of RL, feel free to ask it here :)

Firstly, concatenate only works on identical output shape of the axis. Otherwise, the function will not work.
Now, your function output size is (None, 32, 50) and (None, 600, 1). Here, '32' and '600' must be same when you want to concatenate.
I would like to suggest some advice based on your problem. You can flatten both of them first and then concatenate. Because you need to flatten feature to use dense layer later.
def create_mlp(self, arr, regress=False):
        # define MLP network
        print("Array", arr)
        model = Sequential()
        model.add(Dense(env.rows * env.cols, input_shape=(len(arr)//2, len(arr)), activation="relu"))
        model.add(Dense((env.rows * env.cols)//2, activation="relu"))
        **model.add.flatten() ### shape = (None, 1600)**
        # check to see if the regression node should be added
        if regress:
            model.add(Dense(1, activation="linear"))
        # return our model
        return model

And just remove the reshape layer in create_cnn function.
(output shape should be = (None, 600)).
then concatenate two model
combinedInput = concatenate([mlp.output, cnn.output])  ## output shape =(None, 2200)
Later you can just use Dense layer as your code. I don't know how can you used dense (next to concatenate layer) without flatten the feature in create_mlp function.
Your code should work this way.
You can read this simple one for better understanding.


text:
DQN fails to learn useful policy for the Taxi environment (Dietterich 200)
I'm building an agent to solve the Taxi environment. I've seen this problem solved with Q-Learning algorithms but my DQN consistently fails to learn anything. The environment has a discrete observation space, I one-hot encode the state before feeding it to the DQN. I also went ahead to implement Hindsight Experience Replay to help the learning process but the DQN still doesn't learn anything. What can I do to fix this?
I've heard that DQN doesn't excel at environments that require planning to succeed, if that's the case, which algorithms would work well for this environment?
EDIT
When I posted this question, my DQN was learning from only 2 step transitions, since this environment can go on for several timesteps without any positive reward, I updated the agent to use transitions of 200 steps. Since I'm using Hindsight Experience Replay, my agent is sure to receive rewards within 200 timesteps even if it didn't meet the goal. I tried this and my agent still hasn't improved, it continually performs worse than the random agent baseline. I checked the contents of the buffer, I observed transitions that do lead to several rewards because their goals have been modified during HER and yet the DQN agent doesn't learn anything.
Also, I'm using TensorFlow's tf_agents for my implementation. Here's a link to the code. I repurposed this example.
I hope this helps

Could you explain how you are encoding the space. There are ~500 discrete states - have you encoded all of them separately or combined state information in some different way?

@NeilSlater I used one-hot encoding.

It is very likely that you have an implementation detail wrong. It is not clear from your description what that could be.

@NeilSlater I added some links. Also, I have changed the encoding method as you will see in the code, it didn't make any difference though. Now, I'm focusing on how I set goals. Maybe the goals are too difficult?


text:
Generating fake faces containing specific features with GANs
I'm trying to understand how DeepFakes are generated and so far I understood that they're mostly generated through the usage of GANs and autoencoders.
The autoencoders part is understandable, but what I cannot understand is how to generate faces with GANs that match destination face.
GANs consist of a generator and a discriminator. The generator is getting noise input which is randomly selected from a normal distribution and feedback from the discriminator. The discriminator is taught how the real data looks like and just classifies if the data fed to him is real or fake. Depending on the answer - one of them (generator/discriminator) updates its model. If the discriminator guesses right, the generator is getting updated if not, then the discriminator is the one that is updating its model.
So after the training part is over, we can feed the generator more noise to achieve more fake data. In DeepFake videos, we normally try to swap the destination face with the input face. My problem with that is that the destination face has specific features for example it has closed eyes, smiles, rotates its head. If we feed the generator noise, how can we control the process to achieve similar facial features that are in the destination face?
I've found papers about GANs that can control some of the features of generated faces (StyleGANs). Although I'm not sure how would it be possible to extract "special features" of destination face and generate them with StyleGANs.
I will be extremely grateful for any help in understanding the concept of DeepFake with GANs.
Thanks a lot.


text:
How to use and update a shared/global policy between Reinforcement Learning Agents
I would be grateful for some guidance on a RL problem I am trying to solve where multiple RL agents use a common/global policy at the initial state of an episode in the RL Environment, and then update this common/shared policy once the episode is completed.
Below is an example of the problem scenario:

An alert triggers a RL agent to execute a "episode" in the Environment
Multiple alerts (e.g., episodes) can occur at the same time, or, one alert may still be being processed (e.g., the episode has not finished) before another alert is triggered (e.g., another episode begins).

Below are the conditions of the Environment and desired behaviour of the RL Agent:

Multiple episodes can run at once (e.g., another episode starts before another finishes).
For each episode a "instance" of the RL agent uses the latest version of a common policy.
After each episode the RL agent updates the common policy.
Common policy updates are "queued" using versioning in code to prevent race conditions.

Q: How can multiple RL agents in this case use a common policy at the beginning of an episode and then update a common policy after completing it? - All I have found are discussions related to Q-Learning, where agents can update a shared Q-table, or later update a "global" Q-table without any examples of how this can be achieved and whether there are also methods for other approaches such as TD rather than only Q-Learning, for example
Q: Does this sound like a traditional multi-agent scenario, at least conceptually? If so, how might one go about implementing this, any examples would be really helpful.
Any help on this is greatly appreciated!
EDIT:
Since doing more investigation I have found this reference on Mathworks:
Link, which is similar to the above problem, but not exact.

This sounds like distributed RL, and most of the work goes in building the distributed system; the actual RL part is just a DQN (+some tricks from Rainbow DQN).
NB: multi-agent RL arises when the agents interact with each other in the same environment (like Hanabi the card game), while in this case we have multiple agents that collect experiences in parallel.
Here's a possible design from the Ape-X paper:

Thanks @kaiwenw for your response and for reference! From my continued reading I was also leaning to towards this definition of dsitributed RL as well. In this case, does distributed RL assume parallel episodes "start", with different learners, at the same time, or is that just an aspect of the design, and not related? For example, where one episode starts with a learner, then say a minute later another episode starts with another new learner (with the original still running), and they are both updating a common policy.

Excuse me, I meant actor, not learner in the above comment.

@RL_NOOB everything can be asynchronous, and should be to minimize wait times; you can have some "master", perhaps the learner, decide when to share weights with the actors, or you can have a separate weight server that actor threads will periodically fetch from (in that case you have no direct interaction between learner and actor threads)


text:
How does bootstrapping work with the offline $\lambda$-return algorithm?
In Barton and Sutton's book, Reinforcement Learning: An Introduction (2nd edition), an expression, on page 289 (equation 12.2), introduced the form of the $\lambda$-return defined as follows
$$G_t^{\lambda} = (1-\lambda)\sum_{n=1}^{\infty} \lambda^{n-1}G_{t:t+n} \label{12.2}\tag{12.2}$$
with the truncated return defined as
$$ G_{t:t+n} \doteq R_{t+1} +\gamma R_{t+2} + \ldots + \gamma^{n-1} R_{t+n} + \gamma^{n}\hat{v}(S_{t+n}, \mathbf{w}_{t+n-1}) \label{12.1}\tag{12.1}$$
However, slightly later in the text, page 290 (equation 12.4), the update algorithm for the offline $\lambda$-return algorithm is defined as
$$
\mathbf{w}_{t+1} \doteq \mathbf{w}_{t}+\alpha\left[G_{t}^{\lambda}-\hat{v}\left(S_{t}, \mathbf{w}_{t}\right)\right] \nabla \hat{v}\left(S_{t}, \mathbf{w}_{t}\right), \quad t=0, \ldots, T-1 \label{12.4}\tag{12.4}
$$
My question is: how do we bootstrap the truncated returns in the update algorithm?
The way the truncated return is currently defined can not plausibly be used, since we would not have access to $\mathbf{w}_{t+n-1}$, as we are in the process of finding $\mathbf{w}_{t+1}$. I suspect $\mathbf{w}_{t}$ is used for bootstrapping in all returns, but that would alter the definition of the truncated return which I just wanted to clarify.

And as a follow-up question: What weights are used for bootstrapping in the online $\lambda$-return algorithm described on page 298?
I assume it's either $\mathbf{w}_{t-1}^{h}$ or $\mathbf{w}_{h-1}^{h-1}$, it's briefly mentioned that the online $\lambda$-return algorithm performs slightly better than the offline one at the end of the episode which leads me to believe the latter is used otherwise the two algorithms would be identical.
Any insight into either question would be great.


text:
Can the law of iterated expectation be used on the inner expectation of the DQN cost function described in the DQN paper
Is the expression for the DQN cost function, Equation (2) of the DQN paper
$$\begin{align}L_1 &= E_{\mu,\pi}\left[\left(y_i - q(s,a;\theta)\right)^2\right]\\
&=E_{\mu,\pi}\left[\left(E_{\mathcal{E}}[r + \gamma \max\limits_{a'}q(s',a';\theta^-)] - q(s,a;\theta)\right)^2\right] \end{align}$$
equivalent to this? (Substituting the expression for $y_i$ defined in the paragraph directly after, $\mathcal{E}$ represents the transition distribution governed by the environment, $\pi$ represents the behaviour policy and $\mu$ represents the stationary distribution of states)
$$L_2 = E_{\mu,\pi,\mathcal{E}}\left[\left(r + \gamma \max\limits_{a'}q(s',a';\theta^-) - q(s,a;\theta)\right)^2\right]$$
Can the law of iterated expectation be used to derive the second expression from the first, if not, is there another way to go about showing their equivalence IF they are equivalent.
It seems as though $L_2$ is used for sampling but I'm not sure how it's possible to get here from the original cost function $L_1$. If it is possible to use $L_2$ to sample I assume that means the two expressions must be equivalent. The second expression is used for sampling in the DQN paper here.
I do realise that the gradient for each function is the same and thus so is the $n^{th}$ derivative for some $n\geq1$ and since the curvature and optimas align I guess that also means they are the same function (minus some constant difference)?
$$\nabla_{\theta} L = E_{\mu,\pi,\mathcal{E}}\left[\left(r + \gamma \max\limits_{a'}q(s',a';\theta^-) - q(s,a;\theta)\right)\nabla q(s,a;\theta)\right]$$

Related Question
A related problem that concerns equivalence of sampling from $L_1$ and $L_2$. Is it possible to sample from a nested expectation that is squared as follows?
$$E[E[X|Y]^2] \approx \frac{1}{n}\sum X^2$$
Where $X$ is generated according to the marginalised distribution $P(X)$. I don't think it is true  since $E[X]^2 \neq E[X^2]$ which should mean sampling from $L_1$ and $L_2$ are not equivalent.

what is $\mathcal{E}$?

I don't see your first expression/formula anywhere in the DQN paper. Can you clarify this?

@nbro Equation (2) substitute y_i for the expression specified in the paragraph below

It's better you add this information to your post, i.e. how you get to your first expression given the expressions in the DQN paper.

The related question is just a simpler way of rephrasing what they do in the psuedocode of the DQN paper using the first form of the objective function described in the question. Fiddling around with the expected expression it's not obvious to me that this it's possible to sample in this way, which further highlights the discrepancy to me, between the sampling done in the pseudocode and objective function.

Using the related question and simplifying notation
$$\begin{align} E_{\mu,\pi}[E_{\mathcal{E}}[s'|s,a]^2] &= \sum_\limits{s,a}\left(\sum_\limits{s'}s'p(s'|s,a)\right)^2p(s,a) \\
&=\sum_\limits{s,a}\left(\sum_\limits{s_1'}s_1'p(s'_1|s,a)\cdot\sum_\limits{s_2'}s_2'p(s'_2|s,a)\right)p(s,a) \\
&= \sum_\limits{s,a,s_1',s_2'}s_1's_2'p(s_1'|s,a)p(s_2'|s,a)p(s,a) \\
&= E_{\mathcal{E}\sim (s_1',s_2'),\mu,\pi}[s_1'\cdot s_2']
\end{align}$$
This is the closest I could come up with, basically instead of the same sample squared, we pick two samples independently given the pair $(s,a)$.