2
$\begingroup$

I'm trying to solve the Mountain Car task on OpenAI Gym (reach the top in 110 steps or less, having a maximum of 200 steps per episode) using linear Q-learning (the algorithm in figure 11.16, except using maxQ at s' instead of the actual a', as required by Q-learning; I've solved it with other methods easily, the question is about linear Q-learning). Also, I'm using 1 output for each action, so I can select an action in a single forward pass. Important: my input features are the identity function of the state, i.e., the state variables themselves. I know it can be solved with other features, I want to know about this one specifically.

Here is a description of the algorithm I'm using: https://youtu.be/vVDKzIxzkzQ

Unfortunately, this method never solves the task. Actually, it rarely reaches the top. I'm aware that vanilla Q-learning has no convergence guarantees, so I tried some variants which reduce or even solve this issue: I've tried experience replay, double q-learning, GTD and advantage learning. Nothing helped.

I know that this task can be solved linearly on the state inputs directly, since I've done it by manually tuning the weights so the car always apply the force in the same direction as its velocity, so the representation is not an issue. But it seems that the learning algorithm is.

So the question is: is linear Q-learning able to learn the mountain car task directly from the state variables? A paper where the author solves this task with Q-learning in a single-layer network (and shows the algorithm or code) with features = state variables would be enough.

$\endgroup$
2
$\begingroup$

I just found out the answer and it's actually pretty simple: while there is a good linear policy for the mountain car task, the value function itself is non-linear.

The state space of this task is like a spiral, and there is no linear approximation possible even for a mediocre value function. If you increase the value for going right and reaching the top, going left will have the lowest values. This is why the car never reaches the top.

By applying a simple random projection and transforming the input space, it is possible to show that the task becomes linearly solvable (with a value-based method).

$\endgroup$
  • 1
    $\begingroup$ What sort of random projection are you talking about here? I'm not sure if I fully understand how a random projection would help. Can you explain what you did? $\endgroup$ – evanescent Aug 9 '17 at 3:09

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.