Dynamical Distance Learning for Semi-Supervised and Unsupervised Skill Discovery
deep learning machine learning reinforcement learning deep rl auxiliary reward distance value function shortest path neural networks maze unsupervised discovery exploration
DDL is an auxiliary task for an agent to learn distances between states in episodes. This can then be used further to improve the agent's policy learning procedure.

Paper: https://arxiv.org/abs/1907.08225
Blog: https://sites.google.com/view/dynamical-distance-learning/home

Abstract:
Reinforcement learning requires manual specification of a reward function to learn a task. While in principle this reward function only needs to specify the task goal, in practice reinforcement learning can be very time-consuming or even infeasible unless the reward function is shaped so as to provide a smooth gradient towards a successful outcome. This shaping is difficult to specify by hand, particularly when the task is learned from raw observations, such as images. In this paper, we study how we can automatically learn dynamical distances: a measure of the expected number of time steps to reach a given goal state from any other state. These dynamical distances can be used to provide well-shaped reward functions for reaching new goals, making it possible to learn complex tasks efficiently. We show that dynamical distances can be used in a semi-supervised regime, where unsupervised interaction with the environment is used to learn the dynamical distances, while a small amount of preference supervision is used to determine the task goal, without any manually engineered reward function or goal examples. We evaluate our method both on a real-world robot and in simulation. We show that our method can learn to turn a valve with a real-world 9-DoF hand, using raw image observations and just ten preference labels, without any other supervision. Videos of the learned skills can be found on the project website: this https URL.

Authors: Kristian Hartikainen, Xinyang Geng, Tuomas Haarnoja, Sergey Levine

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
 Hi there! If you look at this robot, this robot has learned to turn this valve by itself. Now by itself isn't really correct, but it has learned it in a semi-supervised way with only 10 human inputs along the entire learning trajectory. So only 10 times was there a true reward for this reinforcement learning procedure and the rest is unsupervised discovery of this skill. And the paper we're going to look at today and the technique by which this was achieved is dynamical distance learning for semi-supervised and unsupervised skill discovery by Kristian Hartikeinen, Xin Yang Geng, Thomas Harnoja and Sergei Levine. So this is a technique for reinforcement learning. So they claim reinforcement learning requires manual specification of a reward function to learn a task. And they say while in principle this reward function only needs to specify the task goal, in practice reinforcement learning can be very time-consuming or even infeasible unless the reward function is shaped so as to provide a smooth gradient towards a successful outcome. So what does this mean? Let's look at it. So if you want the robot here to turn the valve to the right, ideally you simply want to say, so the robot is here, this is the start state, ideally you just want to say I want this, I want the thing to be at the right, so this is good. All of this I don't want any of that. And the reinforcement learning, I mean this is enough, this is a reward function, all of this is zero and this is one. This is a reward function and in theory if you apply any sort of reinforcement learning algorithm with any sort of guarantee, this should get you there. But of course we all know that it's not that easy, right? There is basically an exploration bottleneck where your robot has these three digits and lots of joints to move around and the probability that by itself it discovered that it needs to do this here and get this reward is very very slim. So what you want to do is in your reward function that you're providing to the robot, you would want to say okay so this here I see the blue thing is a bit more turned so I'm maybe going to give this a 0.1 and then here it's a bit more turned so maybe this is 0.2 and this I really like 0.3 here is 0.6 maybe because it's even more right and then one at the end right so this is what they would call a smooth gradient in the reward function where it's kind of the reward function ramps up until the goal is reached but oftentimes this isn't really possible because if you already knew how exactly to do the task which then you could you can only shape the reward function truly if you know how to perform the task in the first hand and then why exactly do you do reinforcement learning except for as an academic exercise. So the issue this paper has is clear right? What they want to say is like let's assume that your reward function is actually pretty bad can we provide artificially a way that this discovery of these of these what they call of these new skills is facilitated as if the reward function had some sort of a gradient. So that's the the outset let's actually go back to the to this for a second and they have these mazes as a kind of an example. So if you look at these mazes what we want to keep in mind is let's actually draw this over here. So let's say you have one of these mazes right and always there is a start state so you're here and then there is a goal state right let's say over here and the task is you can move up down left right and the task is to reach the goal right but if the reward function is simply that if you reach the goal you get a reward of one and otherwise you get a reward of zero then all the agent can do is kind of explore around right until it reaches the goal. Now if you do random exploration like a lot of reinforcement learning algorithms for example Q learning or policy gradient they'll have some sort of a just of a random exploration element where they if they don't if they don't absent of what they of the when they know what to do they just kind of boogle around like up up up right left right left down right up that doesn't work okay down down left down so it's sort of and then up again right and then they just kind of wonk around so this this method takes issue with that and it says okay while the agent is doing its thing trying to reach the goal right what we can do is we can learn a distance function between states now we'll reduce the problem for now and just say the task is always that the goal state is reached in the shortest amount of steps right so let's say the agent does something right it goes here here here here and then here right it that's that's one rollout of the policy and then it crashes into a wall okay that's bad so it gets a negative reward right but in addition to that we can we can learn so it has visited all of these states here in between right these are intermediate states this paper wants us now to to learn a distance function between the states so this distance function let's call it D it learns how far two states are away so it'll you can you can tell it okay this state here let's call that state a and this state here state B how far are those away now this is not super well defined yet but you want to say how far are they away for this agent here so the agent has maybe policy pi like that's what it used to create this trajectory under policy pi how far away are states a and B and how far away is simply going to be the amount of steps that it takes the agent to go from a to B so in this case that would be two right so the the and you can do this between any two states right this and this this and this right here here these all of these states you can also start from this state right let's do it in a different color and do every so the the this distance function D can actually has a pretty tight reward signal like a pretty wealth of information that it can learn these things from right that so the policy pi in this case can't learn much because it just got a reward of zero or something because it didn't reach the goal but the distance function has very very big reward or a big rework it has a very dense reward signal where it can learn distances between two states right now let's say we've explored a bunch right a bunch we've had many trajectories some here like to here and then here sometimes we even reach the goal right so so sometimes we actually reach the goal so we learn the two distances between all of the states now if we had a perfect distance function let's assume we have a perfect distance function our task now becomes very very simple so let's assume that's so let's assume I am here where the green agent is and I have these I can either go up or down and let's go that's up let's say that's X and the down is Y right which one should I choose now without even asking my policy per se what I can do is I can ask hey distance function so I can ask the distance function two different things so first let's do it like this distance function what do you think of the distance between X to the goal and what do you think of the distance from Y to the goal and the distance function if it's learned correctly it will tell you the distance of X to the goal is whatever maybe you need eight steps the distance of white the goal is ten steps right so definitely you would go with X right so if you had a good distance function then you could solve the task fairly fairly easily now this by itself isn't super interesting you will quickly notice that if you are able to learn such a good distance function especially with the goal state here then you might as well learn a good policy because that means you've reached the goal a fair number of times right so that the kind of information theoretic signal of D versus the signal on pi if you just want to reach the same goal to me it seems the same this this paper it tries to talk this up I feel but to me if you are in the situation where you have a fixed goal and that's it then this doesn't seem too interesting or too beneficial with compared to let's say just learning a value function right like you would do in a 3c or something the difference between this and a value function so if if if the number of steps is actually your reward so your negative reward you want to reach the goal in the shortest amount of time then learning a value function is the same the difference is for a value function the value function simply takes a state s right and the policy pi while the distance function takes a state s and a goal state for the policy pi the goal state for the value function is implicit right so it implicitly has the goal state because you assume that the goal is always the same with the distance function you can technically change your goal and this is where it becomes interesting so let's say you've explored but you haven't quite reached the goal yet right but we said okay most of these are algorithms they have some sort of some notion of random of random exploration right in order to to reach the goal what if you went from here to here and to here and to here and you learn the distances fairly well for the trajectories that you can do but you just haven't been able to go any further what you can say is you can go to your replay buffer write your memory of everything you've done and you can ask which of these states has the furthest distance from my starting state and the answer will be okay this state here as the furthest distance so now what you can do is you can make this your goal right you can just try to reach that state right and once you reach the state you can explore from that state right because this is the farthest away from your original starting state that probably means that you know if you that's kind of the frontier of what you know so if you explore from here you can go even further noticeably because it is the farthest that you know so it might turn out that from here you can only go back right so that's a possibility but probably you could go even further right so then you go further and you might reach this state here right and again you ask your your replay buffer it tells you this state here is the farthest so far so you take this as your new goal and now you're just trying to reach that and explore from here this is extremely similar to an algorithm like go explorer that I already made a video about where it remembers what it did and then it it will always travel to the furthest states it has seen so far and then from there try to go farther right so this this if you if you can learn a good distance function here that will help you in exploring the space and eventually of course you think you might actually reach this goal state so you might go far enough into in this maze you might explore it enough such that you you stumble over the goal state by itself alright so this is this is sort of the the goal this can be used in a number of different ways now instead of always going for the furthest what they did in the robot is they just let the algorithm explore right you explore explore explore if this is like a state tree and then at some point it it asked the human which one is closest to what you want and then the human says this one and then they say okay cool so this is now the new goal right so we'll try to reach this as much as possible and then explore from here right so this in the case of the robot the robot simply just like does some things it explores in in the unsupervised manner and then at some point you ask the human which of these things that the robot has done you like the most and then that becomes the new intermediate goal state and the algorithm explores from there right so that's the the main gist and how you can use this now the entire learning thing is actually pretty simple so what they propose is simply to to learn the distance function that they put it pretty formal here they say okay if you're two states that were visited after one another in an episode then you can define the distance function as the sum from i to j if if the they were visited at time steps I and J respectively this is a discounted cost function across this but ultimately they consider problems where it's shortest path problems so the cost function simply becomes how many steps does it take you to reach to reach the goal so the cost function so this becomes this this becomes the identity I guess you can you can set it to to one and this you can also set to one so this simply becomes J minus I how many steps does it take you to reach state state in time step J from the state you visited in time step I and then they simply train a pot a neural network or I'm not even sure if it's a neural network but you train a bunch of a parameterized function that learns to map the distance between these states to how many steps it took you from one to the other right and you do this simply by having by regressing so mean squared regression mean squared loss regression simple as that and that's how you learn the distance function and then you can use the distance function in the ways we discussed to either to improve your shortest path policy by giving it by providing it so what you want to do is you want to provide the distance function as the negative reward right so they say they they they provide the distance function as a negative reward for this or you can do this in an unsupervised fashion where you always propose the furthest away goals or you can do this in the semi supervised fashion so they have a bunch of things that they did here they have a bunch of videos of things that they trained this is from the human sorry from the semi supervised where the humans were simply selecting the hoppers that went furthest to the right and you can see over time this hops to the right with very very sparse input only so this is semi supervised right and then it goes to the right and it also has an unsupervised video where you simply let it perform and it on in unsupervised fashion it tries to discover states that are as far away as possible from its initial states and you can see it actually learns to move to the right and to the left because these are these rich states that are very far from its original state right so that's it's pretty cool that it turns out that the unsupervised method will discover such states alright so what to make of this this if you recognize this already it's very plausible because I had seen this some sort of this idea in many many papers before so and they make some connections in their related work so if you know for example universal value functions sorry universal value estimation universal value functions and so on where basically it's also an unsupervised way where you always just you'd select two states you say this and this agent now try try to go from here to here right just try that and so it is and then you select two new states so you basically teach your agent to go between two states that you choose at random and it's supposed to in an unsupervised fashion learn something about the environment very similar to what we have here right also a bunch of other a bunch of other things like just pure value functions are also pretty similar I think to this go explore there is a big connection to go explore so this has been around in one way or the other but possibly not in this specific formulation and what I think is cool applied to this specific semi supervised task so if I had to formulate a criticism to this method I would guess that it probably doesn't work when let's say the branching factor of the task is super high you see here you can you can only really turn the valve in one way or another of course the digits and the joints are are they have they have degrees of freedom but if you think if the branching factor is super high right so from a from a given state here you can go in many many many different ways and then from each of those you can go in many many different ways right then the the notion of something being far away right you go to this thing and use what's the farthest away all right is is almost meaningless because you have so much not explored right so if you have if you are three steps deep here right it will always tell you well this state here is the farthest away but you haven't explored these you know 15 directions here right so it might be that you actually miss so that you you go so here's the goal and here's the start and you go a long way but you miss this obvious shortcut here because you always want to go along the longest path around so it seems like there is there there are probably environments where this works well right but they're right but but it appears that if if either the branching factor is super high or if there are maybe this this kind of loops in the game loops between states non obvious combinatorial things it might be somewhat even counterproductive sometimes not not sure about that but it seems to be very specific environments where this would work all right so this was my commentary I invite you to read the paper check it out and bye bye
 Hi there! If you look at this robot, this robot has learned to turn this valve by
 itself. Now by itself isn't really correct, but it has learned it in a
 semi-supervised way with only 10 human inputs along the entire learning
 trajectory. So only 10 times was there a true reward for this reinforcement
 learning procedure and the rest is unsupervised discovery of this skill.
 And the paper we're going to look at today and the technique by which this was
 achieved is dynamical distance learning for semi-supervised and unsupervised
 skill discovery by Kristian Hartikeinen, Xin Yang Geng, Thomas Harnoja and Sergei
 Levine. So this is a technique for reinforcement learning. So they claim
 reinforcement learning requires manual specification of a reward function to
 learn a task. And they say while in principle this reward function only
 needs to specify the task goal, in practice reinforcement learning can be
 very time-consuming or even infeasible unless the reward function is shaped so
 as to provide a smooth gradient towards a successful outcome. So what does this
 mean? Let's look at it. So if you want the robot here to turn the valve to the
 right, ideally you simply want to say, so the robot is here, this is the
 start state, ideally you just want to say I want this, I want the
 thing to be at the right, so this is good. All of this I don't
 want any of that. And the reinforcement learning, I mean this
 is enough, this is a reward function, all of this is zero and this is one.
 This is a reward function and in theory if you apply any sort of reinforcement
 learning algorithm with any sort of guarantee, this should get you there. But
 of course we all know that it's not that easy, right? There is basically an
 exploration bottleneck where your robot has these three digits and lots of
 joints to move around and the probability that by itself it discovered that
 it needs to do this here and get this reward is very very slim. So what you
 want to do is in your reward function that you're providing to the robot, you
 would want to say okay so this here I see the blue thing is a bit more
 turned so I'm maybe going to give this a 0.1 and then here it's a bit more
 turned so maybe this is 0.2 and this I really like 0.3 here is 0.6 maybe
 because it's even more right and then one at the end right so this is what
 they would call a smooth gradient in the reward function where it's kind of the
 reward function ramps up until the goal is reached but oftentimes this isn't
 really possible because if you already knew how exactly to do the task which
 then you could you can only shape the reward function truly if you know how to
 perform the task in the first hand and then why exactly do you do reinforcement
 learning except for as an academic exercise. So the issue this paper has
 is clear right? What they want to say is like let's assume that your
 reward function is actually pretty bad can we provide artificially a way that
 this discovery of these of these what they call of these new skills is
 facilitated as if the reward function had some sort of a gradient. So that's
 the the outset let's actually go back to the to this for a second and they have
 these mazes as a kind of an example. So if you look at these mazes what we want
 to keep in mind is let's actually draw this over here. So let's say you have one
 of these mazes right and always there is a start state so you're here and
 then there is a goal state right let's say over here and the task is you
 can move up down left right and the task is to reach the goal right but if the
 reward function is simply that if you reach the goal you get a reward of one
 and otherwise you get a reward of zero then all the agent can do is kind of
 explore around right until it reaches the goal. Now if you do random
 exploration like a lot of reinforcement learning algorithms for
 example Q learning or policy gradient they'll have some sort of a just of a
 random exploration element where they if they don't if they don't absent of what
 they of the when they know what to do they just kind of boogle around like up
 up up right left right left down right up that doesn't work okay down down left
 down so it's sort of and then up again right and then they just kind of wonk
 around so this this method takes issue with that and it says okay while the
 agent is doing its thing trying to reach the goal right what we can do is we can
 learn a distance function between states now we'll reduce the problem for now and
 just say the task is always that the goal state is reached in the shortest
 amount of steps right so let's say the agent does something right it goes here
 here here here and then here right it that's that's one rollout of the policy
 and then it crashes into a wall okay that's bad so it gets a negative reward
 right but in addition to that we can we can learn so it has visited all of these
 states here in between right these are intermediate states this paper wants us
 now to to learn a distance function between the states so this distance
 function let's call it D it learns how far two states are away so it'll you can
 you can tell it okay this state here let's call that state a and this state
 here state B how far are those away now this is not super well defined yet but
 you want to say how far are they away for this agent here so the agent has
 maybe policy pi like that's what it used to create this trajectory under policy
 pi how far away are states a and B and how far away is simply going to be the
 amount of steps that it takes the agent to go from a to B so in this case that
 would be two right so the the and you can do this between any two states right
 this and this this and this right here here these all of these states you can
 also start from this state right let's do it in a different color and do every
 so the the this distance function D can actually has a pretty tight reward
 signal like a pretty wealth of information that it can learn these
 things from right that so the policy pi in this case can't learn much because it
 just got a reward of zero or something because it didn't reach the goal but the
 distance function has very very big reward or a big rework it has a very
 dense reward signal where it can learn distances between two states right now
 let's say we've explored a bunch right a bunch we've had many trajectories some
 here like to here and then here sometimes we even reach the goal right
 so so sometimes we actually reach the goal so we learn the two distances
 between all of the states now if we had a perfect distance function let's assume
 we have a perfect distance function our task now becomes very very simple so
 let's assume that's so let's assume I am here where the green agent is and I have
 these I can either go up or down and let's go that's up let's say that's X
 and the down is Y right which one should I choose now without even asking my
 policy per se what I can do is I can ask hey distance function so I can ask the
 distance function two different things so first let's do it like this distance
 function what do you think of the distance between X to the goal and what
 do you think of the distance from Y to the goal and the distance function if
 it's learned correctly it will tell you the distance of X to the goal is
 whatever maybe you need eight steps the distance of white the goal is ten steps
 right so definitely you would go with X right so if you had a good distance
 function then you could solve the task fairly fairly easily now this by itself
 isn't super interesting you will quickly notice that if you are able to learn
 such a good distance function especially with the goal state here then you might
 as well learn a good policy because that means you've reached the goal a fair
 number of times right so that the kind of information theoretic signal of D
 versus the signal on pi if you just want to reach the same goal to me it seems
 the same this this paper it tries to talk this up I feel but to me if you are
 in the situation where you have a fixed goal and that's it then this doesn't
 seem too interesting or too beneficial with compared to let's say just learning
 a value function right like you would do in a 3c or something the difference
 between this and a value function so if if if the number of steps is actually
 your reward so your negative reward you want to reach the goal in the shortest
 amount of time then learning a value function is the same the difference is
 for a value function the value function simply takes a state s right and the
 policy pi while the distance function takes a state s and a goal state for the
 policy pi the goal state for the value function is implicit right so it
 implicitly has the goal state because you assume that the goal is always the
 same with the distance function you can technically change your goal and this is
 where it becomes interesting so let's say you've explored but you haven't
 quite reached the goal yet right but we said okay most of these are algorithms
 they have some sort of some notion of random of random exploration right in
 order to to reach the goal what if you went from here to here and to here and
 to here and you learn the distances fairly well for the trajectories that
 you can do but you just haven't been able to go any further what you can say
 is you can go to your replay buffer write your memory of everything you've
 done and you can ask which of these states has the furthest distance from my
 starting state and the answer will be okay this state here as the furthest
 distance so now what you can do is you can make this your goal right you can
 just try to reach that state right and once you reach the state you can explore
 from that state right because this is the farthest away from your original
 starting state that probably means that you know if you that's kind of the
 frontier of what you know so if you explore from here you can go even
 further noticeably because it is the farthest that you know so it might turn
 out that from here you can only go back right so that's a possibility but
 probably you could go even further right so then you go further and you might
 reach this state here right and again you ask your your replay buffer it tells
 you this state here is the farthest so far so you take this as your new goal
 and now you're just trying to reach that and explore from here this is extremely
 similar to an algorithm like go explorer that I already made a video about where
 it remembers what it did and then it it will always travel to the furthest
 states it has seen so far and then from there try to go farther right so this
 this if you if you can learn a good distance function here that will help
 you in exploring the space and eventually of course you think you might
 actually reach this goal state so you might go far enough into in this maze
 you might explore it enough such that you you stumble over the goal state by
 itself alright so this is this is sort of the the goal this can be used in a
 number of different ways now instead of always going for the furthest what they
 did in the robot is they just let the algorithm explore right you explore
 explore explore if this is like a state tree and then at some point it it asked
 the human which one is closest to what you want and then the human says this
 one and then they say okay cool so this is now the new goal right so we'll try
 to reach this as much as possible and then explore from here right so this in
 the case of the robot the robot simply just like does some things it explores
 in in the unsupervised manner and then at some point you ask the human which of
 these things that the robot has done you like the most and then that becomes the
 new intermediate goal state and the algorithm explores from there right so
 that's the the main gist and how you can use this now the entire learning thing
 is actually pretty simple so what they propose is simply to to learn the
 distance function that they put it pretty formal here they say okay if
 you're two states that were visited after one another in an episode then you
 can define the distance function as the sum from i to j if if the they were
 visited at time steps I and J respectively this is a discounted cost
 function across this but ultimately they consider problems where it's shortest
 path problems so the cost function simply becomes how many steps does it
 take you to reach to reach the goal so the cost function so this becomes this
 this becomes the identity I guess you can you can set it to to one and this
 you can also set to one so this simply becomes J minus I how many steps does
 it take you to reach state state in time step J from the state you visited in
 time step I and then they simply train a pot a neural network or I'm not even
 sure if it's a neural network but you train a bunch of a parameterized
 function that learns to map the distance between these states to how many steps
 it took you from one to the other right and you do this simply by having by
 regressing so mean squared regression mean squared loss regression simple as
 that and that's how you learn the distance function and then you can use
 the distance function in the ways we discussed to either to improve your
 shortest path policy by giving it by providing it so what you want to do is
 you want to provide the distance function as the negative reward right so
 they say they they they provide the distance function as a negative reward
 for this or you can do this in an unsupervised fashion where you always
 propose the furthest away goals or you can do this in the semi supervised
 fashion so they have a bunch of things that they did here they have a bunch of
 videos of things that they trained this is from the human sorry from the semi
 supervised where the humans were simply selecting the hoppers that went furthest
 to the right and you can see over time this hops to the right with very very
 sparse input only so this is semi supervised right and then it goes to the
 right and it also has an unsupervised video where you simply let it perform
 and it on in unsupervised fashion it tries to discover states that are as far
 away as possible from its initial states and you can see it actually learns to
 move to the right and to the left because these are these rich states that
 are very far from its original state right so that's it's pretty cool that it
 turns out that the unsupervised method will discover such states alright so
 what to make of this this if you recognize this already it's very
 plausible because I had seen this some sort of this idea in many many papers
 before so and they make some connections in their related work so if you know for
 example universal value functions sorry universal value estimation universal
 value functions and so on where basically it's also an unsupervised way
 where you always just you'd select two states you say this and this agent now
 try try to go from here to here right just try that and so it is and then you
 select two new states so you basically teach your agent to go between two
 states that you choose at random and it's supposed to in an unsupervised
 fashion learn something about the environment very similar to what we have
 here right also a bunch of other a bunch of other things like just pure value
 functions are also pretty similar I think to this go explore there is a big
 connection to go explore so this has been around in one way or the other but
 possibly not in this specific formulation and what I think is cool
 applied to this specific semi supervised task so if I had to formulate a
 criticism to this method I would guess that it probably doesn't work when let's
 say the branching factor of the task is super high you see here you can you can
 only really turn the valve in one way or another of course the digits and the
 joints are are they have they have degrees of freedom but if you think if
 the branching factor is super high right so from a from a given state here you
 can go in many many many different ways and then from each of those you can go
 in many many different ways right then the the notion of something being far
 away right you go to this thing and use what's the farthest away all right is is
 almost meaningless because you have so much not explored right so if you have
 if you are three steps deep here right it will always tell you well this state
 here is the farthest away but you haven't explored these you know 15
 directions here right so it might be that you actually miss so that you
 you go so here's the goal and here's the start and you go a long way but you miss
 this obvious shortcut here because you always want to go along the longest path
 around so it seems like there is there there are probably environments where
 this works well right but they're right but but it appears that if if either the
 branching factor is super high or if there are maybe this this kind of loops
 in the game loops between states non obvious combinatorial things it might be
 somewhat even counterproductive sometimes not not sure about that but it
 seems to be very specific environments where this would work all right so this
 was my commentary I invite you to read the paper check it out and bye bye