4
$\begingroup$

I recently finished Course on RL by David Silver (on YT) and thought about trying it out on simple application in Unity Game Engine, where I've built simple labyrint with ball and want to teach the ball to get from point A to point B in there while avoiding obstacles and fire (the place where you'll get burnt so big negative reward)

The problem I encountered while designing the whole thing (programming-wise) is: What is the correct (or at least good) way of representing the position in 2D space? It is continuous so I thought about representing it as feature vector consisting of [up, down, left, right, posX, posY] where direction is whether I am pressing button of moving in that direction in binary (or actions if you want) and pos are floats (0-1) representing normalized position from one corner on the plane where the whole map is. That would be accompanied by vector W that would represent the weights adjusted using Gradient Descent.

Question is: will this work?? I am asking for 2 reasons. One is that I am not so sure about that posX and posY since it can be 0 and if I multiply it by the weights vector then how could be resulting reward anything but 0? Second reason is that I am not sure if the actions should be part of the features. I mean, it makes sense to me but I could easily be very wrong since I am a beginner.

Thanks a lot guys in advance. If you have any more questions or think the problem is not described deeply enough just ask in the comments and I'll edit the question. :)

PS: I could just code it the way I think is right, but I also want to get gasp of designing applications on paper before coding them (project management).

$\endgroup$
  • $\begingroup$ Shouldn't the action be the output not the input? If you also learn a bias vector you mitigate the pos==(0,0) problem. $\endgroup$ – BlindKungFuMaster Sep 9 '16 at 12:42
  • $\begingroup$ @BlindKungFuMaster That's the second reason there. To explain my thought process - The vector there is intended to be used as input to Q(s, a) which will be a function with parameters W (vector) that will be learned. The exact action then will be extracted from there finding max a in that Q(s, a) where S will be extracted from actual position of the ball and A will be found in some sort of loop. What do you mean by the bias vector? Is it that W vector I mentioned or something else? Thanks. $\endgroup$ – Dominik Sep 9 '16 at 13:06
  • $\begingroup$ Ah, ok, so Q predicts the expected reward. A bias vector would be added to the product of input and W. So it would B would contain additional parameters for Q. $\endgroup$ – BlindKungFuMaster Sep 9 '16 at 15:17
  • $\begingroup$ So in the end it would be something like: Q(Sa, B) = W*Sa + B where B would be just some value so the Q of state (0, 0) won't be always 0 and therefore everything will be shifted by B which will not matter because in the end as W gets learnt the Q will converge to the actual values anyway, just W will be different then as if I did it without B. Do I understand correctly? $\endgroup$ – Dominik Sep 9 '16 at 16:56
  • $\begingroup$ Yes, though I would suspect that you'll need more layers anyway, which would look like Q(Sa, B) = W2*f(W1*Sa + B1)+B2, except if your labyrinth is extremely simple. $\endgroup$ – BlindKungFuMaster Sep 9 '16 at 17:09
3
$\begingroup$

I think your net should have the various actions as outputs, but I am not an expert in Deep Nets. I just think that that light form of multi-task learning might be better. The idea of multi-task learning is that a predictor predicting multiple variables (in this case the various Q(s,a1), Q(s,a2), ...) using mostly the same structure (varying only the output weights) will learn more sensible things. Though I admit applying this here might be a bit of a stretch.

As for the real question, a popular technique in Reinforcement Learning is Tile Coding.

The basic idea is to discretize the (2-dimensional, in your case) state-space - imagine a grid laid over the 2D space - and assigning an input feature to each cell; all of these variables are set to zero except for the one your continuous variables fall into. For example, if your grid is 20x20, you will have 400 variables, 399 of which are set to zero, and 1 set to one.

Tile Coding takes this one step further and repeats this using slight offsets for the grid. Imagine you create an identical grid but you move it slightly to the right by 1/10 of the width of a cell: you will have another set of 400 variables like before, but it is possible that the cell set to one is not the same. Then you repeat this moving the grid by 2/10 and you have another set of 400 variables, again, only 1 of which is set to one. In total you have 10 sets of 400 variables (if you repeat more than that, you get the same grids as before); of your 4000 variables, only 10 are set to one. Now you repeat this by adding a 1/10 of a cell offset in the Y axis and obtain another 4000 variables. Repeat with 2/10 and you get another 4000. By the end of it, you have 40000 variables, 100 of which are set to one.

Now your net can more easily learn different weights for different positions. I recommend you to follow the link above for a better explanation than mine (and figures!)

My suggestion is to feed all of these variables to your net and have it predict the Q-value for all of the actions. But, again, I am no expert in deep nets so I may be wrong.

Also, according to Andrej Karpathy, "most people prefer to use Policy Gradients, including the authors of the original DQN paper who have shown Policy Gradients to work better than Q Learning when tuned well.". This means that you may be better off not using Q-learning (as they did in the original DQN formulation) to train your net. Have a look at Andrej's blog and the paper he points to.

| improve this answer | |
$\endgroup$
  • $\begingroup$ So basically you are suggesting to divide continuous space into tiles so effectively making it discrete and therefore simplify the problem. Yeah that would work. I just wanted to try doing continuous space to see if I understand the point. But still, the answer is great so thanks. I may try it if the continuous thing suggested by BlindKungFuMaster will fail. About Policy Iterations, I am just beginning so first I want to try classic Q-Learning and then move on Policy methods, still thanks for the suggestion. $\endgroup$ – Dominik Sep 9 '16 at 17:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.