A neurally plausible model learns successor representations in partially observable environments
ml ai machine learning artificial ingelligence deep learning reinforcement learning model-free model-based search markov mdp pomdp implicit expectation wake-sleep
Successor representations are a mid-point between model-based and model-free reinforcement learning. This paper learns successor representation in environments where only incomplete information is available.

Abstract:
Animals need to devise strategies to maximize returns while interacting with their environment based on incoming noisy sensory observations. Task-relevant states, such as the agent's location within an environment or the presence of a predator, are often not directly observable but must be inferred using available sensory information. Successor representations (SR) have been proposed as a middle-ground between model-based and model-free reinforcement learning strategies, allowing for fast value computation and rapid adaptation to changes in the reward function or goal locations. Indeed, recent studies suggest that features of neural responses are consistent with the SR framework. However, it is not clear how such representations might be learned and computed in partially observed, noisy environments. Here, we introduce a neurally plausible model using distributional successor features, which builds on the distributed distributional code for the representation and computation of uncertainty, and which allows for efficient value function computation in partially observed environments via the successor representation. We show that distributional successor features can support reinforcement learning in noisy environments in which direct learning of successful policies is infeasible.

Authors: Eszter Vertes, Maneesh Sahani

Links:
YouTube: https://www.youtube.com/c/yannickilcher
Twitter: https://twitter.com/ykilcher
BitChute: https://www.bitchute.com/channel/yannic-kilcher
Minds: https://www.minds.com/ykilcher
 Alright, hi there! Today we're looking at a neurally plausible model, learned successor representations in partially observable environments, by Esther Vertes and Manish Sani. This paper is a paper on a topic that has been interesting me for a while, and that's successor representations. So we'll dive into all of this. The title is fairly lengthy and complicated, but ultimately we're dealing with a setting of reinforcement learning. So if you know something about reinforcement learning, in reinforcement learning usually you have an agent, which, let's just say this is you, and there is an environment which is a big black box that you don't know anything about. This is environment. And what the environment gives you is what's called an observation. So an observation could be anything, but in this case let's just assume you get a little picture of what's in front of you. So in front of you might be a tree, and in front of you might be a house. And then you can perform an action, and this action in this case might be to enter the house. And then the environment in the next step, it gives you back a new picture and says, ah you're now inside the house. So here is a door that leads you to this room, and the door that leads you that room, and there's a little table in front of you. So it's just this cycle of action observation. And with that you're trying to collect some reward over time. Now there are different ways of achieving this reward over time. So basically the reward is going to be, for example, you could get a reward for finding the kitchen, or for going into as many rooms as possible, or you know anything like this. So the other objective is to learn what's called a policy. So which actions to take. So action one, action two, action three, given the observations that maximizes your rewards. So there's mainly two ways to go about this. There's the model-free and the model-based reinforcement learning approach. Let's split them. So in the model-free approach, what you're trying to do is you're trying to simply learn a policy, and we call this here pi of s, and s is your state. And the state you can think of it as the observation. So in this policy we'll simply output an action. And this is the kind of the simple setup of model-free reinforcement learning. The important thing here is you're trying to learn this. Usually there's parameters theta of this policy pi. This could be a neural network and the theta are then the weights of the neural network. So you're trying to learn the neural network such that if you give it a state it just outputs the action. So you have this neural network with your state, you input the state into layer, layer, layer, layer, layer, and then it outputs one of maybe three actions. Go north, go south, go west, maybe go east. This could be four actions. You're just trying to train the neural network using backprop and the reward signal through what's called the reinforce trick or variance thereof. This is model-free reinforcement learning. It's very easy to implement, let's say, and it's very applicable. It will simply give you a mapping. You don't have to know nothing about how the world works. It'll simply tell you at the end if you're in this state do that action and the reward will be high. In contrast there is the other world. This is the model-based reinforcement learning. So in model-based reinforcement learning what you have is a model of the world. The model of the world is best described for example if you play chess. If you play chess, and this is a let's do a simplified chess board here, four by four, and you have a pawn right here. You have a pawn and you know if I do the action of moving the pawn forward, I know the pawn will then be in this square right here, in the next time step. I know that because I have a model of the world, I know how the world works, and I can predict basically the results of my actions. So if you have a model-based reinforcement learning setup, if you know how the world works, you can do something like a search. So given you're here in a state, you know if I do action one I go to this state, if I do action two I go to that state, and if I do action three I go to this other state. From each of the states you can then say ah but again I have three actions and I can you know go into these three states, go into these maybe here two, and maybe here I can go into these, actually let's do three as well. Then the question more becomes, can you find a path through this thing such that at the end you are in the state that you want to end up? So for example here is outside, and then here you can go to the tree, to the house, or to the field, and in the house you can go to the bedroom, the bathroom, the kitchen, and you know all of this, you have a model. So you can actually kind of compute what would happen if I do something and then search for the best path. Whereas in the model-free reinforcement learning approach, what you'd simply do is you'd say here is a state, and the state is for example I am in the house, and now give me the action that would maximize my future reward, and you're trying to learn this directly. So it's a very different style of reinforcement learning. Basically one is a pure machine learning approach, and the other one is a search problem. Now you can of course mix and match the two, like for example people in AlphaGo have done, they have a model-based reinforcement learning that also has kind of a learning machine learning elements, but in between now we have the successor features. So the successor representations, they are, if you will, they are somewhere in between the two. So they kind of trade off the advantages of model-free, where you you only have to learn a function, right, from state to something, with the advantages of model-based, the fact that you actually have a bit of an idea of how the world works, and can adjust quickly to let's say different reward structures or things like this. So what do successor representations do? Successor representations basically learn how states are connected, and this is a classic successor representation. So the successor representation M here of policy pi, the policy remember is what tells you which action you should take in a given state. You define it as a connection between state i and state j, and M of si as j means given that I am in si, so this could be the kitchen, and your goal is to find the bedroom, and if this is the kitchen, given that I am in state si, what's the probability that in the future at some point I will transition to si, right? Given that I'm in the kitchen, what's the probability that I'll end up in the bedroom at some point in the future? And this is formally expressed, this is the expectation over your policy, and it's the indicator function that the future state, sorry, this is the future state t plus k, you see k goes from zero to infinity, so for all of the future, and st is the one you're in now, so for any future state this is equal to sj. Now of course this makes no sense unless you kind of discount, have a discount factor here, so if you're in state, if you're in the bedroom further in the future, then this value would be lower. So this value is high if you will transition from si to sj with high probability in the near future, and this is a successor representation, right? It basically tells you if you want to go from state si to state sj, how likely is that in the near future, right? So if this number is high, you know that these two states are closely connected, that you can expect to end up in state sj somewhere down the line if you're in si now. One more representation, if you consider the vector m pi of si given all of the sj's, so I'm doing a dot here, so this is a vector, you can actually compare two states si, so if one is, if you plug in here, you plug in the kitchen, and then also you plug in the, I don't know, the garage. If they, and you'll get out two vectors, right? You get two vectors, if those vectors are very similar, then you know that if you're in the kitchen or in the garage, it doesn't matter, you're going to end up, you have a similar future trajectories basically. However, if those two vectors are far apart, you know that these two states are far apart with respect to your policy. So this is pretty cool things you can do with successor representations, and I hope this gives you kind of some insight. So another neat trick is that if you have a value function, so and the value function, in this case there's a simplified assumption, but you don't actually need it, the simplified assumption is that the reward only depends on the state you're in. Basically, it doesn't matter how you get to the state, like the actions you perform, if you're in a given state, if you're in a given room in the house, you'll get some reward. Like for example, if you find the bedroom, then you win. That's a reward that would only be characterized by the state. If that's the case, you can compute the value function of the reinforcement learning problem simply by integrating over the success representations. So for each state, you simply go over all of the possible other states, and you ask how likely am I to go to that state, and what reward will I have in that state, and that's your value function. So pretty simple. You can actually learn the successor representations by TD learning, by temporal difference learning, which is a method that's applied throughout reinforcement learning, especially in places like Q learning, and also for learning value functions. So pretty neat successor representations. This paper then goes from successor representations of individual state to successor representations over continuous space. So right now we have these states, state kitchen, you go to the bedroom, you go to somewhere, and these states were kind of discrete places. So there was a house and you have different rooms in the house, and you can go between them. Now we're dealing more with continuous states. So you can generalize these successor representations to continuous state by considering not the states themselves, but features of the state. And a feature, in this here you have to kind of imagine as binary features. And the features, let me give like some really dumb examples, but maybe it helps you. Like one feature could be the smell. Does it smell in the room? Like just binary. Does it smell or doesn't it smell? And then one feature could there be, is there sunlight? And then one feature could be, is it warm? And these are all binary features. So you have to build the features such that if the features are the same, then the states should be fairly close in whatever sense. So for example, if it smells but there is no sunlight, you're probably somewhere in the bathroom. Like where exactly in xy coordinates you are in the bathroom, it doesn't really matter to this as long as the features are high. And so if it smells and there is no sunlight, you're probably somewhere in the bathroom. And that makes all the states in the bathroom, all the coordinates, close together. So this is how you have to imagine these features. You can define your successor representations exactly the same over these features, except that the representation is now not from state i to state j, but from a state to a given feature. So that means if I am in state st at the current time, what is the probability that in the near future this feature will be high? So if I am right now in the or close to the bathroom, let's say, the probability that smell, oh sorry, this should be a highlight, the probability that smell is high in the future is very high, right? So this this number would be high. So exactly the same except for these continuous features now. And you can do the same thing including defining the value function as a simple linear multiplication with these features. That is an assumption under the assumption that the reward is a linear function of the features of the states, which is the analogous assumption to saying that the reward only depends on the state in the linear case, or somewhat of an analogous function, not entirely. All right, so you can also learn this by temporal difference learning exactly the same. So this is pretty cool. These are the successor representations and you can actually, if you learn them, you have kind of a model of how the world works. Not as much a model as the model based reinforcement learning where you know exactly how it works, right? Here you know exactly how the world works, you have this model. In model three, you don't know how the world works at all. You simply know, oh if I'm in this state and do this action, that that'll turn out really well. But in the successor representation framework, you have you have an idea of what states there are. We'll do the discrete case right now. So this could be kitchen, this could be outdoor, this could be bedroom. And so you have an idea what states there are and so on, and how they connect to each other. Like you say, from the kitchen I can easily go to the bedroom, but I cannot as well go to maybe the bathroom. From outdoor I can easily go to the kitchen, but I can't go to the bedroom and so on. So you have kind of an idea of how all of these states connect to each other. And that is the success representation. You can already see how that helps learning agent a lot if you introduce the successor, if you have the successor representation. Now what this this paper deals with in essence is it says, okay these successor representations are cool, but it has only so far been done in a case where you have full observability. And the full observability is the case where you kind of know what state you're in, right? You kind of know that, sorry, you are in the kitchen, you are outdoors, you are in the bedroom. That is not known. But what if you don't? And in most problems you don't. What if you just have a picture, like here, right? You just see a tree in the house, right? You don't, you kind of have to infer that you are outdoor, right? And if you're here, you just get this picture of a couple of doors and a table and you have to infer that you are now in the living room. So in essence there is an additional layer of complexity. Not only do you go from state to state to state, but you don't actually observe the states. What you observe is from each state you observe what are called observations, right? So you only observe these and you have to infer what the, you kind of have to guess what the underlying states are in order to know what you should do to get to the next state, right? You only ever observe the observations. So this here is the actual thing, this is kitchen, and this here could be a picture of the kitchen, right? There's a counter, there's a stove, yeah. And so you get kind of what I mean. In their example they simplify this to kind of a toy data setup where you have this environment and this is one beautiful picture. I don't know why. Oh well. Just you have one this setup and this is this box basically. This box and it has this wall, right? And then you have an agent that is able to walk around in here like with whatever policy. The policy determines how it walks around. But then what you observe is not the actual position, but what you observe is for example for this position you observe a random point here. So they basically add noise to each observer, to each state. And if you're in this state you will observe one of these points in this circle, right? So your trajectory might look to you as you observe it much more, much like for example from here to here to here to here. And you kind of have to guess what the underlying state is. And you see this here. This blue thing is what the agent actually does, but the gray thing is what it observes. And the observations are sometimes even outside of this boundary. And this orange thing is now the inferred thing. And that's what we actually want, is to go from the observed to these inferred. And we want that the inferred is as close as possible to this true latent state. So the way they do it is they introduce this distributional distributed coding for the expectation of the features. And basically what they say is they say we will build a framework where we represent the features as expectations over some distribution. And the expectation we'll call mu. And mu is simply the kind of mean of this feature under this distribution. This is very general so let's look at how to plug this in. So what they now have to do is they have to learn these two things. First of all if I draw this picture again these are the underlying states and they kind of transition into each other. So this is state one, state two, state three. And with action one, action two we transition from state to state. But also there are these observations. Observation one, observation two, observation three. So the agent needs to learn two different things. First of all it needs to learn, given an observation, what state am I probably in. This is the first thing it needs to learn. And then the second thing it needs to learn is given this state and this action what's the next state that I will go to. And of course these things down here they're not observed. So these things down here you can only do in distribution. So I'm going to represent this with a p here. You can only kind of do this in distribution and the way they handle it is they always maintain the expected value of these things. And that's, they do this in this wake-sleep algorithm. Alright so this is me re-recording this part because I have done a terrible job at the first time. So I want to understand this wake-sleep algorithm to compute the things that we don't know. Let me draw this actually again. So the way this algorithm does it is actually pretty cool. It has two phases, a sleep phase and a wake phase and it alternates between the two constantly. It's kind of like expectation maximization. Well ultimately what you want to learn are two different sets of parameters W and T. Now you, whenever you learn T you use W, the one that you've already learned. And whenever you learn W you use the T that you've already learned. So it's kind of a bootstrapping each other up. The two functions you learn here are this FW and the T here. So T is just a matrix and F of W is a function. The function has weights W. So you see in the sleep phase you update W and in the wake phase you update T. Now why is this called wake and sleep? It's because in the wake phase you're actually so called awake and you use real observations. So in the wake phase, and I find it easier to start actually at the wake phase, in the wake phase you collect observations. So you let your agent go around its environment and collect a bunch of observations. You don't know what the states are, but what you do is simply you collect these observations. Now it's not that important what the policy is here. So you basically follow some policy and you collect these observations. And then what you say is, okay I have the function F of W and remember since we're in the wake phase we're learning T so we assume we already have the W. In essence in practice we start out with a random one and then kind of alternate between the two phases until both get really good. So we already have a W and we use it to update T. How do we do this? We need to understand what this function F of W does. F of W takes this mu and the current observation and produces a new mu. So what is a mu? This mu here, this mu here as we saw above here, the mu is the expectation over the features. And in essence the mu is a guess. The mu is your best guess of what the features of the state are. Or in the discrete case you could also say a guess of what the state is. So you don't know the state, but what you want to maintain is a distribution over state. So you want to kind of maintain this distribution. But you can't calculate, you can't properly efficiently calculate with an entire distribution unless you assume it's some sort of Gaussian or so. But what you can do is you can simply take its mean, mu, and that's your best guess for what the state is. The state could be anywhere here according to this distribution, but you simply come up with mu which is your best guess. So the function F of W takes in the best guess of where you were up until the last step. And it also takes as an argument your current observation and it gives you the output of F is mu t. It's the best guess of where you are now. It's pretty straightforward if you think about it. So for every observation you want to have kind of a guess of what your state is. And that's mu. So what F does is it takes whatever observations you had, these observations gave rise to a mu that guess where you are. You take this mu and you take this observation and from that you derive the next guess of where you are. You just say I guessed I was in the kitchen before, now I moved, I observed that I moved through some sort of door and there's some sort of table. So given that I thought I was in the kitchen and that I observed this thing, now I'm probably in the living room. That's what FW does. So you input the observations that you had and you input your current observation to get the guess of where you're next. And these are real observations. And then you simply update t. What does t do? t relates your current and your next guess. And that's important. We already said that F takes your last guess and gives you the next guess. t does kind of the same thing, but t does it without relying on an additional observation. t simply says well if I am here or if my guess is that I am in the kitchen, then what's the probability that in the next step I'll be in the living room without observing anything? t is simply relating states to each other or relating guesses of states to each other. So it's simply saying well under the current policy that I am, what is the kind of distribution of going from one room to the next room? So in the wake phase you learn the t. The t simply represents how you move from state to state. So it's exactly basically this function here. Except that it's not from state to state, but it relates your guess about your guess, your mu of the state 1 to the mu of the state 2. And then in the sleep phase, you now assume that you have a good estimate of how the states relate to each other. And what you can then do is you can actually sample trajectories. And this is why it's called sleeping. It's kind of like dreaming. So given that you have a model t of how states transition to each other or your your guesses about states more precisely, you can now sample state trajectories. So you can dream up how you would move in an environment. And the assumption here is that you know the process that if you have a state that gives you an observation. For example in their experiments is always the state is x-y coordinates and that's corrupted by Gaussian noise. There is also ways to learn this transition. This is what's called the observation process. But you assume you know it. So you can sample trajectories of states and corresponding observations. Now this is not the real world, but this is using this t down here. You kind of know how or you kind of have some sort of model. You learn a model of how you move about the world. So you sample these trajectories and from these trajectories you can now learn the F of W function. So you see since you know what the state is, you can compute these features exactly. And then you can learn this F of W function that gives you a guess of the last state and the current observation and gives you the next the guess of the next state. And that you can then use temporal difference learning. This is always here. Also with the t here we have temporal difference kind of a temporal difference learning to learn the parameters W. So it's very kind of convoluted, but ultimately it's a simple process. In the wake phase you go into the world and actually collect real observations. And you have a method of deriving from these observations, deriving the guesses about the states. So what you can do is you can learn a transition between the states. If you have a good guess of what the states are given each observation you can learn how to transition from one state to the next state. Except you don't do it in actual states, you do it in guesses about states. Then once you have a model of how you move from one state to the next state you can go and dream up such state trajectories. You can dream state trajectories and therefore also you can dream how you would observe them. And given that you can learn then a better function that relates your guess about a state given the observation to the actual features of the state. Since for this particular thing you know what the state is. So this is this two-step process. Notice the cool thing. We've never actually had to learn this mu explicitly. We never had to learn how to go from observations to your guesses about states because we can compute this recursively. So you simply start out with mu0 which is a guess about the initial state and then you go to mu1 and mu2 and you never actually have to learn that function. So that's how they learn these success representations and the experiments of this are fairly cool. Here is another diagram of how that looks like. You have a state this gives you an observation and from that you derive a guess of what this state is. So you can now look at what the agent learned. The agent actually learns dynamics of this room. It means if you're here you probably go somewhere. There is no clear direction but if you're close to the wall your next states are probably going to be inwards of this wall. And yeah I've already shown you this picture. So they have a last cool experiment here where what they do is they specify a reward and the reward is down here. And from each state you want to know which way do I have to go to get the reward. Now if they give the agent the value of the latent state and the latent state here are just your x y coordinates. If they give this to the agent and they let it run, they let it learn the structure of the world, it will correctly conclude these are the high value states, lower, lower, lower, lower, lower value states. Up until over here are the most low value states because you travel the longest to go to the reward. If you just give it the observation, the noisy observation, it will actually assign high value to states here. Because of course it doesn't infer the latent state. It simply takes the observation as the phase value says. Well I was here and I reached here pretty quickly so it must be a good state. But in fact it wasn't here, it was here and the added noise would just corrupt the observation. So you see it learns kind of a wrong model of the world. Whereas if you use this DDC you see, sorry about that, if you use this DDC you see you're much closer to the true state of the world, like to the one on the left here. So on the left here you actually kind of cheat, you give it the actual state. But here you give it the observation but tell it it's actually a noisy observation. You use what this paper proposes and again it will learn to assign a low value to these states because it needs to go all the way around. Even though it has supposedly seen the agent go from here to here directly, but it kind of understands that it's just a noisy observation. Alright so this was this from this paper. It's a very very cool approach I think to reinforcement learning and there's some more experiments where you can see that this DDC actually helps. I'm excited about successor representations and how to incorporate them in reinforcement learning because it seems a perfect kind of middle ground between model-based and model-free RL. With that thanks for listening and bye bye!
 Alright, hi there! Today we're looking at a neurally plausible model,
 learned successor representations in partially observable environments,
 by Esther Vertes and Manish Sani.
 This paper is a paper on a topic that has been interesting me for a while,
 and that's successor representations.
 So we'll dive into all of this. The title is fairly lengthy and complicated,
 but ultimately we're dealing with a setting of reinforcement learning.
 So if you know something about reinforcement learning,
 in reinforcement learning usually you have an agent,
 which, let's just say this is you,
 and there is an environment which is a big black box
 that you don't know anything about. This is environment.
 And what the environment gives you is what's called an observation.
 So an observation could be anything, but in this case let's just assume
 you get a little picture of what's in front of you.
 So in front of you might be a tree, and in front of you might be a house.
 And then you can perform an action, and this action in this case might be to
 enter the house. And then the environment in the next step,
 it gives you back a new picture and says, ah you're now inside the house.
 So here is a door that leads you to this room, and the door that leads you that
 room, and there's a little table in front of you.
 So it's just this cycle of action observation.
 And with that you're trying to collect some reward
 over time. Now there are different ways of achieving
 this reward over time. So basically the reward is going to be,
 for example, you could get a reward for finding the kitchen,
 or for going into as many rooms as possible, or
 you know anything like this. So the other objective is to learn
 what's called a policy. So which actions to take. So action one,
 action two, action three, given the observations that maximizes your rewards.
 So there's mainly two ways to go about this. There's the model-free and the
 model-based reinforcement learning approach. Let's split them. So in the
 model-free approach, what you're trying to do
 is you're trying to simply learn a policy, and we call this here
 pi of s, and s is your state. And the state you can think of it as the
 observation. So in this policy we'll simply output
 an action. And this is the kind of the simple setup of
 model-free reinforcement learning. The important thing here is
 you're trying to learn this. Usually there's parameters theta
 of this policy pi. This could be a neural network and the theta
 are then the weights of the neural network. So you're trying to learn the
 neural network such that if you give it a state it just
 outputs the action. So you have this neural network with your state, you
 input the state into layer, layer, layer, layer, layer, and then it outputs one of
 maybe three actions. Go north, go south, go west, maybe go
 east. This could be four actions.
 You're just trying to train the neural network using backprop
 and the reward signal through what's called the
 reinforce trick or variance thereof. This is model-free reinforcement learning.
 It's very easy to implement, let's say,
 and it's very applicable. It will simply give you a mapping.
 You don't have to know nothing about how the world works. It'll simply
 tell you at the end if you're in this state
 do that action and the reward will be high.
 In contrast there is the other world. This is the model-based reinforcement
 learning.
 So in model-based reinforcement learning what you have is a
 model of the world. The model of the world
 is best described for example if you play chess.
 If you play chess, and this is a let's do a simplified chess board
 here, four by four, and you have a pawn right here.
 You have a pawn and you know if I do the action of moving the
 pawn forward, I know the pawn will then be in this
 square right here, in the next time step. I know that
 because I have a model of the world, I know how the world works,
 and I can predict basically the results of my actions.
 So if you have a model-based reinforcement learning setup,
 if you know how the world works, you can do something like a search.
 So given you're here in a state, you know if I do action one
 I go to this state, if I do action two I go to that state,
 and if I do action three I go to this other state. From each of the states
 you can then say ah but again I have three actions and I can you know go
 into these three states, go into these maybe here two, and maybe
 here I can go into these, actually let's do three as well.
 Then the question more becomes, can you find a path
 through this thing such that at the end you are in the state that you
 want to end up? So for example here is outside,
 and then here you can go to the tree, to the house,
 or to the field, and in the house you can go to the bedroom,
 the bathroom, the kitchen, and you know all of this, you have a model.
 So you can actually kind of compute what would happen if I do
 something and then search for the best path.
 Whereas in the model-free reinforcement learning approach,
 what you'd simply do is you'd say here is a state, and the state is for example
 I am in the house, and now give me the action that would
 maximize my future reward, and you're trying to learn this directly.
 So it's a very different style of reinforcement
 learning. Basically one is a pure machine learning approach, and the
 other one is a search problem. Now you can of course mix and match the two,
 like for example people in AlphaGo have done, they have a model-based
 reinforcement learning that also has kind of a learning machine learning
 elements, but in between now we have the successor
 features. So the successor representations, they are,
 if you will, they are somewhere in between the two.
 So they kind of trade off the advantages of model-free, where you
 you only have to learn a function, right, from state to something,
 with the advantages of model-based, the fact that you actually have a bit of an
 idea of how the world works, and can adjust quickly to
 let's say different reward structures or things like this.
 So what do successor representations do? Successor representations basically
 learn how states are connected, and this is a classic successor
 representation. So the successor representation M here
 of policy pi, the policy remember is what tells you which action you should take
 in a given state. You define it as a
 connection between state i and state j, and M of si as j means
 given that I am in si, so this could be the kitchen,
 and your goal is to find the bedroom, and if this is the kitchen,
 given that I am in state si, what's the probability
 that in the future at some point I will transition
 to si, right? Given that I'm in the kitchen, what's the probability that
 I'll end up in the bedroom at some point in the future?
 And this is formally expressed, this is the expectation over your policy,
 and it's the indicator function that the future state,
 sorry, this is the future state t plus k, you see k goes from zero to infinity, so
 for all of the future, and st is the one you're in now,
 so for any future state this is equal to sj.
 Now of course this makes no sense unless you kind of
 discount, have a discount factor here, so if you're in state, if you're in the
 bedroom further in the future, then this value would be lower.
 So this value is high if you will transition from si to sj with high
 probability in the near future, and this is a
 successor representation, right? It basically tells you if you want to
 go from state si to state sj, how likely is that in the near future,
 right? So if this number is high, you know that
 these two states are closely connected, that you can
 expect to end up in state sj somewhere down the line if you're in si now.
 One more representation, if you consider the vector
 m pi of si given all of the sj's, so I'm doing a dot here, so this is a vector,
 you can actually compare two states si, so if one is, if you plug in here,
 you plug in the kitchen, and then also you plug in
 the, I don't know, the garage. If they, and you'll get out two vectors,
 right? You get two vectors, if those vectors are very similar,
 then you know that if you're in the kitchen or in the garage, it doesn't
 matter, you're going to end up, you have a
 similar future trajectories basically. However, if those two
 vectors are far apart, you know that these two
 states are far apart with respect to your policy.
 So this is pretty cool things you can do with successor representations,
 and I hope this gives you kind of some insight.
 So another neat trick is that if you have a value function, so
 and the value function, in this case there's a simplified assumption, but you
 don't actually need it, the simplified assumption is that the
 reward only depends on the state you're in.
 Basically, it doesn't matter how you get to the state, like the actions you
 perform, if you're in a given state, if you're in a given room in the house,
 you'll get some reward. Like for example, if you find the bedroom,
 then you win. That's a reward that would only be
 characterized by the state. If that's the case,
 you can compute the value function of the reinforcement learning problem
 simply by integrating over the success representations. So for each
 state, you simply go over all of the possible other states, and you ask how
 likely am I to go to that state, and what reward will I have in that state, and
 that's your value function. So pretty simple.
 You can actually learn the successor representations
 by TD learning, by temporal difference learning,
 which is a method that's applied throughout reinforcement learning,
 especially in places like Q learning, and also for learning value functions.
 So pretty neat successor representations.
 This paper then goes from successor representations of individual state
 to successor representations over continuous space. So right now we have
 these states, state kitchen, you go to the
 bedroom, you go to somewhere, and these states were kind of
 discrete places. So there was a house and you have different
 rooms in the house, and you can go between them.
 Now we're dealing more with continuous states. So you can generalize
 these successor representations to continuous state by considering
 not the states themselves, but features of the
 state. And a feature, in this here you have to kind of imagine as
 binary features. And the features, let me give like some really dumb
 examples, but maybe it helps you. Like one feature could be the smell.
 Does it smell in the room? Like just binary. Does it smell or doesn't it smell?
 And then one feature could there be, is there sunlight?
 And then one feature could be, is it warm?
 And these are all binary features.
 So you have to build the features such that if the
 features are the same, then the states should be fairly close in
 whatever sense. So for example, if it smells but there is no
 sunlight, you're probably somewhere in the bathroom. Like where exactly in xy
 coordinates you are in the bathroom, it doesn't really matter to this as long
 as the features are high. And so if it smells and there is no
 sunlight, you're probably somewhere in the bathroom. And that makes
 all the states in the bathroom, all the coordinates, close together.
 So this is how you have to imagine these features. You can define your successor
 representations exactly the same over these features, except that the
 representation is now not from state i to state j, but from a state to
 a given feature. So that means if I am in state st at the current time, what is
 the probability that in the near future this feature will be high?
 So if I am right now in the or close to the bathroom, let's say,
 the probability that smell, oh sorry, this should be a highlight, the
 probability that smell is high in the future is very high, right? So this
 this number would be high. So exactly the same except for these continuous
 features now. And you can do the same thing including defining the value
 function as a simple linear multiplication with these features.
 That is an assumption under the assumption that the reward is a linear
 function of the features of the states, which is the analogous assumption to
 saying that the reward only depends on the state in the linear case, or
 somewhat of an analogous function, not entirely.
 All right, so you can also learn this by temporal difference learning exactly
 the same. So this is pretty cool. These are the successor representations and
 you can actually, if you learn them, you have kind of a model of how the world
 works. Not as much a model as the model based reinforcement learning where you
 know exactly how it works, right? Here you know exactly how the world works,
 you have this model. In model three, you don't know how the world works at all.
 You simply know, oh if I'm in this state and do this action, that that'll turn out
 really well. But in the successor representation framework, you have
 you have an idea of what states there are. We'll do the discrete case right now.
 So this could be kitchen, this could be outdoor, this could be bedroom.
 And so you have an idea what states there are and so on, and how they connect to
 each other. Like you say, from the kitchen I can easily go to the bedroom, but I
 cannot as well go to maybe the bathroom. From outdoor I can easily go to the
 kitchen, but I can't go to the bedroom and so on. So you have kind of an idea
 of how all of these states connect to each other. And that is the success
 representation. You can already see how that helps learning agent a lot if you
 introduce the successor, if you have the successor representation. Now what this
 this paper deals with in essence is it says, okay these successor
 representations are cool, but it has only so far been done in a case where you
 have full observability. And the full observability is the case where you kind
 of know what state you're in, right? You kind of know that, sorry, you are in the
 kitchen, you are outdoors, you are in the bedroom. That is not known. But what if
 you don't? And in most problems you don't. What if you just have a picture, like
 here, right? You just see a tree in the house, right? You don't, you kind of have
 to infer that you are outdoor, right? And if you're here, you just get this picture
 of a couple of doors and a table and you have to infer that you are now in the
 living room. So in essence there is an additional layer of complexity. Not
 only do you go from state to state to state, but you don't actually
 observe the states. What you observe is from each state you observe what are
 called observations, right? So you only observe these and you have to infer what
 the, you kind of have to guess what the underlying states are in order to know
 what you should do to get to the next state, right? You only ever observe the
 observations. So this here is the actual thing, this is kitchen, and this
 here could be a picture of the kitchen, right? There's a counter, there's a stove,
 yeah. And so you get kind of what I mean. In their example they
 simplify this to kind of a toy data setup where you have this environment
 and this is one beautiful picture. I don't know why. Oh well. Just you have
 one this setup and this is this box basically. This box and it has this wall,
 right? And then you have an agent that is able to walk around in here like with
 whatever policy. The policy determines how it walks around. But then what you
 observe is not the actual position, but what you observe is for example for this
 position you observe a random point here. So they basically add noise to each
 observer, to each state. And if you're in this state you will observe one of these
 points in this circle, right? So your trajectory might look to you as you
 observe it much more, much like for example from here to here to here to
 here. And you kind of have to guess what the underlying state is. And you see
 this here. This blue thing is what the agent actually does, but the gray
 thing is what it observes. And the observations are sometimes even outside
 of this boundary. And this orange thing is now the inferred thing.
 And that's what we actually want, is to go from the observed to these inferred.
 And we want that the inferred is as close as possible to this true latent
 state. So the way they do it is they introduce this distributional
 distributed coding for the expectation of the features.
 And basically what they say is they say we will build a framework where
 we represent the features as expectations over some distribution.
 And the expectation we'll call mu. And mu is simply the kind of mean of
 this feature under this distribution. This is very general so let's
 look at how to plug this in. So what they now have to do is they
 have to learn these two things. First of all if I draw this
 picture again these are the underlying states and they kind of transition into
 each other. So this is state one, state two, state three. And with action one,
 action two we transition from state to state. But also there are these
 observations. Observation one, observation two, observation three. So the agent needs
 to learn two different things. First of all it needs to learn, given an
 observation, what state am I probably in. This is the first thing it needs
 to learn. And then the second thing it needs to learn is given this state and
 this action what's the next state that I will go to. And of
 course these things down here they're not observed. So these things down here
 you can only do in distribution. So I'm going to represent this with a p here.
 You can only kind of do this in distribution and the way they handle it
 is they always maintain the expected value of these things. And that's, they
 do this in this wake-sleep algorithm. Alright so this is me re-recording this
 part because I have done a terrible job at the first time. So I want to
 understand this wake-sleep algorithm to compute the things that we don't know.
 Let me draw this actually again. So the way this algorithm does it is actually
 pretty cool. It has two phases, a sleep phase and a wake phase and it alternates
 between the two constantly. It's kind of like expectation maximization. Well
 ultimately what you want to learn are two different sets of parameters W and T.
 Now you, whenever you learn T you use W, the one that you've already learned. And
 whenever you learn W you use the T that you've already learned. So it's kind of
 a bootstrapping each other up. The two functions you learn here are this FW
 and the T here. So T is just a matrix and F of W is a function. The function has
 weights W. So you see in the sleep phase you update W and in the wake
 phase you update T. Now why is this called wake and sleep? It's because in the
 wake phase you're actually so called awake and you use real observations. So
 in the wake phase, and I find it easier to start actually at the wake phase, in
 the wake phase you collect observations. So you let your agent go around its
 environment and collect a bunch of observations. You don't know what the
 states are, but what you do is simply you collect these observations. Now it's not
 that important what the policy is here. So you basically follow some policy and
 you collect these observations. And then what you say is, okay I have
 the function F of W and remember since we're in the wake phase we're learning
 T so we assume we already have the W. In essence in practice we start out with a
 random one and then kind of alternate between the two phases until
 both get really good. So we already have a W and we use it to update T. How
 do we do this? We need to understand what this function F of W does. F of
 W takes this mu and the current observation and produces a new mu. So
 what is a mu? This mu here, this mu here as we saw above here, the
 mu is the expectation over the features. And in essence the mu is a guess. The mu
 is your best guess of what the features of the state are. Or in the
 discrete case you could also say a guess of what the state is. So you
 don't know the state, but what you want to maintain is a distribution
 over state. So you want to kind of maintain this distribution. But you can't
 calculate, you can't properly efficiently calculate with an entire
 distribution unless you assume it's some sort of Gaussian or so. But what you can
 do is you can simply take its mean, mu, and that's your best guess
 for what the state is. The state could be anywhere here
 according to this distribution, but you simply come up with mu which is your
 best guess. So the function F of W takes in the best guess of where
 you were up until the last step. And it also takes as an argument your current
 observation and it gives you the output of F is mu t. It's the best guess
 of where you are now. It's pretty straightforward if you think
 about it. So for every observation you want to have kind of a guess of
 what your state is. And that's mu. So what F does is it
 takes whatever observations you had, these observations gave rise to a mu
 that guess where you are. You take this mu and you take this observation and
 from that you derive the next guess of where you are. You just say I guessed I
 was in the kitchen before, now I moved, I observed that I moved through some
 sort of door and there's some sort of table. So given that I thought I
 was in the kitchen and that I observed this thing, now I'm probably in the
 living room. That's what FW does. So you input the observations that you had
 and you input your current observation to get the guess of where you're
 next. And these are real observations. And then you simply update t. What
 does t do? t relates your current and your next guess. And that's important. We
 already said that F takes your last guess and gives you the next guess.
 t does kind of the same thing, but t does it without relying on
 an additional observation. t simply says well if I am here or if my guess is that
 I am in the kitchen, then what's the probability that in the next step I'll
 be in the living room without observing anything? t is simply
 relating states to each other or relating guesses of states to each other.
 So it's simply saying well under the current policy that I am,
 what is the kind of distribution of going from one room to the next room?
 So in the wake phase you learn the t. The t simply represents how
 you move from state to state. So it's exactly basically this function here.
 Except that it's not from state to state, but it relates your guess about your
 guess, your mu of the state 1 to the mu of the state 2. And then in the
 sleep phase, you now assume that you have a good estimate of how
 the states relate to each other. And what you can then do is you can actually
 sample trajectories. And this is why it's called sleeping. It's kind of like
 dreaming. So given that you have a model t of how states transition to each other
 or your your guesses about states more precisely, you can now sample state
 trajectories. So you can dream up how you would move in an environment.
 And the assumption here is that you know the process that if you have a
 state that gives you an observation. For example in their experiments is always
 the state is x-y coordinates and that's corrupted by Gaussian noise. There is
 also ways to learn this transition. This is what's called the
 observation process. But you assume you know it. So you can sample
 trajectories of states and corresponding observations. Now this is
 not the real world, but this is using this t down here. You kind of know how
 or you kind of have some sort of model. You learn a model of how you
 move about the world. So you sample these trajectories and from these
 trajectories you can now learn the F of W function. So you see since you know
 what the state is, you can compute these features exactly. And then you
 can learn this F of W function that gives you a guess of the
 last state and the current observation and gives you the next the guess of the
 next state. And that you can then use temporal difference learning. This is
 always here. Also with the t here we have temporal difference kind of a
 temporal difference learning to learn the parameters W. So it's very kind of
 convoluted, but ultimately it's a simple process. In the wake phase you go into
 the world and actually collect real observations. And you have a method
 of deriving from these observations, deriving the guesses about the states.
 So what you can do is you can learn a transition between the states. If
 you have a good guess of what the states are given each observation you can learn
 how to transition from one state to the next state. Except you don't do it in
 actual states, you do it in guesses about states. Then once you have a model of how
 you move from one state to the next state you can go and dream up such state
 trajectories. You can dream state trajectories and therefore also you can
 dream how you would observe them. And given that you can learn then a better
 function that relates your guess about a state given the observation
 to the actual features of the state. Since for this particular thing you know
 what the state is. So this is this two-step process. Notice the cool thing.
 We've never actually had to learn this mu explicitly. We never had to learn how
 to go from observations to your guesses about states because we can compute this
 recursively. So you simply start out with mu0 which is a guess about the
 initial state and then you go to mu1 and mu2 and you never actually have to
 learn that function. So that's how they
 learn these success representations and the experiments of this are
 fairly cool. Here is another diagram of how that looks like. You have a state
 this gives you an observation and from that you derive a guess of what this
 state is. So you can now look at what the agent learned. The agent actually
 learns dynamics of this room. It means if you're here you probably go somewhere.
 There is no clear direction but if you're close to the wall your next
 states are probably going to be inwards of this wall. And yeah I've
 already shown you this picture. So they have a last cool experiment here where
 what they do is they specify a reward and the reward is down here. And from each
 state you want to know which way do I have to go to get the reward.
 Now if they give the agent the value of the latent state and the latent state
 here are just your x y coordinates. If they give this to the agent and they let
 it run, they let it learn the structure of the world, it will correctly conclude
 these are the high value states, lower, lower, lower, lower, lower
 value states. Up until over here are the most low value states because you
 travel the longest to go to the reward. If you just give it the observation, the
 noisy observation, it will actually assign high value to states here.
 Because of course it doesn't infer the latent state. It simply takes the
 observation as the phase value says. Well I was here and I reached here pretty
 quickly so it must be a good state. But in fact it wasn't here, it was here and
 the added noise would just corrupt the observation. So you see it learns kind of
 a wrong model of the world. Whereas if you use this DDC you see, sorry about
 that, if you use this DDC you see you're much closer to the true state of the
 world, like to the one on the left here. So on the left here you
 actually kind of cheat, you give it the actual state. But here you give it
 the observation but tell it it's actually a noisy observation. You use
 what this paper proposes and again it will learn to assign a low value to
 these states because it needs to go all the way around. Even though it has
 supposedly seen the agent go from here to here directly, but it kind of
 understands that it's just a noisy observation. Alright so this was this
 from this paper. It's a very very cool approach I think to reinforcement
 learning and there's some more experiments where you can see that this
 DDC actually helps. I'm excited about successor representations and how to
 incorporate them in reinforcement learning because it seems a perfect kind
 of middle ground between model-based and model-free RL. With that
 thanks for listening and bye bye!