Estimating learning rates in evolution and TDL: Results on a simple grid-world problem

When learning to play a game or perform some task, it is important to learn as quickly and effectively as possible by making best use of the available information. Interesting insights can be gained by studying the learning process from an information theory perspective, and analysing the learning speed in terms of the maximum number of bits that could be learned per game/task, or per action. Previous work has applied this analysis to co-evolution and to temporal difference learning (TDL) for a simple board game with a fixed number of moves. This paper analyses a grid-world problem and calculates the upper bounds on the information rates for evolution and for TDL. The results show an interesting relationship between the upper bounds of the learning rates and the actual information acquisition rates that are achieved in practice. Also, which method works best is highly dependent on the choice of function approximator.