0
$\begingroup$

I am currently researching the usages of machine learning paradigms for pathfinding problems. I am currently looking into the reinforcement learning paradigm and I used QLearning for pathfinding.

When there are not many states QLearning seems to be working well, but as soon as the environment gets bigger and the amount of states gets bigger it is performing rather bad. Since the convergence of QLearning is so slow I am wondering if it is possible with QLearning to interpolate the QValue of unexplored states since QLearning does not use a model? Is it possible with reinforcement in general or does it require to learn all possible states?

$\endgroup$
  • $\begingroup$ Maybe give a more detailed description of your pathfinding problem? Especially relevant is what information the agent truly has access to, because a lot of toy examples such as grid world deliberately constrain knowledge to demonstrate learning, and you may not need to. A more complete description may help to assess whether Q learning is appropriate for your problem. $\endgroup$ – Neil Slater Apr 18 '18 at 12:57
  • $\begingroup$ I am researching how the usage of machine learning for pathplanning relates to the traditional pathfinding algorithms like A* and Dijkstra's algoritm. I am comparing the different learning paradigms to gain more knowledge about the potential pitfalls of applying machine learning for common problems. The environment is a grid where a bot has to reach a destination avoiding moving and static obstacles. $\endgroup$ – Steven Schenk Apr 18 '18 at 17:39
  • $\begingroup$ With A* you are letting the algorithm use the map directly, but in Q learning based on "grid world" mechanics, you are not - instead you are using the map outside of the algorithm to score results of the learning in a simulation. So these algorithms are not directly comparable given your problem (a map to solve). Dyna-Q would be a more fair comparison, although still not quite the same. If you encode maps as input data, you may eventually train a Q Learning agent that solves maps from your generator distribution in general whilst A* will not improve in the same way. $\endgroup$ – Neil Slater Apr 21 '18 at 5:55
1
$\begingroup$

Since the convergence of QLearning is so slow I am wondering if it is possible with QLearning to interpolate the QValue of unexplored states since QLearning does not use a model?

When Q learning is described as "model free", it means that the agent does not need access to (or use) a predictive model of the environment. It cannot refer to state transitions and rewards in advance, but has to experience them in order to learn.

This does not mean that you have to avoid using a learning data model (such as a neural network) in order to generalise to new unseen data.

So, yes, Q learning can interpolate from unseen states and predict their Q value. To do this, you replace the state/action table with a supervised learning method based on descriptions of state $s$ and action $a$ as inputs, that you train as a regression model to predict $Q(s,a)$ (as a variant you can also have just state as input and predict $Q(s,a)$ for all possible actions as a vector in one go).

However, Q learning with a neural network suffers from instability. See Deep Mind's DQN paper for example of a system that solves that instability. In short:

  • Use experience replay - store S, A, R, S' data for each step and run the Q learning update on random mini-batches of the stored data, instead of online.

  • Keep two copies of the Q estimator neural network. Train one continuously, and copy it to a "frozen" version every now and then (e.g. every 100 mini-batches). Use the "frozen" copy to calculate the new $Q(s,a)$ targets.

This still might not match your learning scenario. If you want to solve mazes, think carefully about what data is truly available to the agent and how you might use it. For instance if you are using Q learning to solve a maze where you have a map, it is very inefficient approach. This is often shown as a toy problem, because it is possible to view the learning data very easily. But in that toy problem, the agent is not given the map, nor any knowledge of what a grid is.

Here are a couple of suggestions that may still help, separate to using a neural network value estimator:

  • If you do have a model of your environment (but not a map or other data that could be directly analysed for a solution), joining Q learning with a planning algorithm might work better for you than Q learning, as in Dyna-Q. This is relevant where you have an agent exploring in real time that would benefit from "looking" ahead before taking actions.

  • If your problem is very sparse rewards (due to larger maze, and only getting different reward at the end), then a worthwhile improvement is to look into multi-step TD learning, where the rewards are propagated back to previous steps more efficiently. Maybe look into $Q(\lambda)$

| improve this answer | |
$\endgroup$

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.