2
$\begingroup$

I want to solve a problem using Reinforcement Learning on a 20x20 board. An agent (a mouse) has to get the highest possible rewards as fast as possible by collecting cheese, which there are 10 in total. The agent has a fixed amount of time for solving this problem, namely 500 steps per game. The problem is, the cheeses will be randomly assigned to the fields on the board, the agent knows however, where the cheeses is located.

Is there any way how this could be solved using only Reinforcement Learning (and not training for an absurd amount of time)? Or is the only way to solve this problem to use algorithms like the A*-algorithm?

I've tried many different (deep)-q-learning models, but it always failed miserably.

Edit: I could not get any meaningful behavior after 6 hours of learning while using a GTX 950M. Maybe my implementation was off, but i don't think so.

$\endgroup$
  • $\begingroup$ Could you clarify what "an absurd amount of time" is for you? Do you have a GPU for accelerating training? $\endgroup$ – Neil Slater Mar 21 at 22:00
  • $\begingroup$ I don't think you will learn anything optimal in 6 hours on GTX 950M especially with millions of possible boards being generated one after another in each episode. I don't know if you would even learn optimal behavior on a single stationary board that doesn't change after every episode in that amount of time but that's just my opinion, maybe I'm wrong. I would recommend you to first try to solve a single fixed board and see how much time it takes. $\endgroup$ – Brale_ Mar 21 at 22:36
2
$\begingroup$

Yes you can use RL for this. The trick is to include the location of the cheese as part of the state description. So as well as up to 400 states for the mouse location, you have (very roughly) $400^{10}$ possible cheese locations, meaning you have $400^{11}$ states in total.

So you are going to want some function approximation if you want to use RL - you would probably train using a convolutional neural network, with an "image" of the board including mouse and cheese positions, plus DQN to select actions.

Viewed like this, a game where the mouse tries to get the cheese in minimal time seems on the surface a lot simpler than many titles in the Atari game environments, which DQN has been shown to solve well for many games.

I would probably use two image channels - one for mouse location and one for cheese location. A third channel perhaps for walls/obstacles if there are any.

Or is the only way to solve this problem to use algorithms like the A*-algorithm?

A* plus some kind of sequence optimisation like a travelling salesman problem (TSP) solver would probably be optimal if you have been presented the problem and asked to solve it any way you want. With only 11 locations to resolve - mouse start plus 10 cheese locations - then you can brute force the movement combinations in a few seconds on a modern CPU, so that part may not be particularly exciting (whilst TSP solvers can get more involved and interesting).

The interesting thing about RL is how it will solve the problem. RL is a learning algorithm - the purpose of implementing it is to see what it takes for the machine to gain knowledge towards a solution. Whilst A* and combinatorial optimisers are where you have knowledge of how to solve the problem and do so as optimally as possible based on a higher level analysis. The chances are high that an A*/optimiser solution would be more robust, quicker to code, and quicker to run than a RL solution.

There is nothing inherently wrong with either approach, if all you want to do is solve the problem at hand. It depends on your goals for why you are bothering with the problem in the first place.

You could even combine A* and RL if you really wanted to. A* to find the paths, then RL to decide best sequence using the paths as part of the input to the CNN. The A* analysis of routes would likely help the RL stage a lot - add them as one or more additional channels.

$\endgroup$
  • $\begingroup$ But isn't having such a high state space not computationally really expensive and wouldn't it have to learn for a really long time? What i have tried so far is using a Feed-Forward-Network and encoding the fields with cheese as '1' and with no cheese as '0' and strenghtening the board so it becomes a list. I did the same thing with the agent, the mouse. This means i had inputted 800 numbers into my network and this did not work. Would using a convolutional neural network be much better than my approach? $\endgroup$ – Pascal Mar 21 at 22:30
  • $\begingroup$ @Pascal: That is your state space for this problem whether you like it or not. Yes, it may take some training time - I would guess at a couple of hours on a GPU-accelerated machine (whilst this will take a few seconds for dedicated solution such as A*). CNNs will probably work better because they allow for the "space like" nature of the board. $\endgroup$ – Neil Slater Mar 22 at 7:37
0
$\begingroup$

A assume here OP is familiar with DQN basics.

"Standard" way to solve this problem with Deep RL would be using convolutional DQN.

Make net from 2 to 4 convolutional layers with 1-2 fully connected on top. The trick here is how you output Q-values. Input is board with cheese, without information about mouse. Instead net should output Q for every action from every field on the board (every possible position of mouse), that mean you output 20x20x(number_of_moves from the field) Q values. That would make net quite big, but that is most reliable way for DQN. For each move form the replay buffer only one Q value updated (gradient produced) with Time Difference equation

Because only one value form 20x20x(number_of_moves) updated per sample you need quite big replay buffer and a lot of training. After each episod (complete game) cheese should be randomly redistributed. Episodes should be mixed up in replay buffer, training on 1 episod is a big No. Hopefully that should at least give you direction in which do research/development. Warning: DQN is slow to train, and with such big action space (20 x 20 x number_of_moves) could require million or tens of millions of even more moves.

Alternatively, if you don't want such big action space, is to use actor-critic architecture (or policy gradient, actor-critic is a kind of policy gradient). Actor-critic network have small action space, with only number_of_moves outputs. On the down size complexity of method is much higher, and behavior could be difficult to predict or analyze. However if action space is too big it could be preferable solution. Practical issues and implementations of actor-critic is too huge area to go in depth here.

Edit: There is another way with lesser action space for DQN, but somehow less reliable and possibly more slow: shift the board in such way that mouse is in the center of the board and pad invalid parts with zero (size of the new board should be x2). In that case only number_of_moves should be in output.

$\endgroup$
  • $\begingroup$ Are you suggesting that the size of the output layer should be number_of_positions * number_of_actions? $\endgroup$ – DrMcCleod Mar 22 at 7:50
  • $\begingroup$ Yes, that is standard practice for DQN. More exactly it's number_of_potential_actions. $\endgroup$ – mirror2image Mar 22 at 7:52
  • $\begingroup$ but in the problem described (2d grid world) the number_of_potential_actions at any step is 4. $\endgroup$ – DrMcCleod Mar 22 at 10:01
  • $\begingroup$ I mean all possible action, with all possible position of mouse. $\endgroup$ – mirror2image Mar 22 at 10:13
  • 1
    $\begingroup$ @DrMcCleod This answer suggests an action representation similar to AlphaZero, which includes lots of non-valid moves and you need to filter. I would instead suggest something more like DQN as the problem feels intuitively more like the DQN Atari setup than like go or chess. For clarity - that means the actions are just the 4 (or 8 if you allow diagonal moves) movement directions you allow for the mouse. However, both representations are valid, used in highly successful systems, and neither mirror2image nor I has done the experiment on your test environment. $\endgroup$ – Neil Slater Mar 22 at 11:46

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.