Can Reinforcement Learning solve problems, where certain elements in the environement are randomly located?

Question

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.

Answer 1

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.

Answer 2

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.