Reinforcement Learning and surrogate reward functions based on graph Laplacians

Abstract

Reinforcement learning is an upcoming area in machine learning with many applications. This thesis covers the basics of reinforcement learning: reward functions, value and policy iterations, and their algorithms. A value iteration algorithm for the game tic-tac-toe is given along with the results of a policy learning from itself. When the reward function is not straightforward to define, a surrogate reward function might be helpful. A surrogate reward function is defined by using the Fiedler vector of the Laplacian of the graph defined by the game. Laplacians based on weighted graphs in four different ways are defined and used to make different surrogate reward functions for a walking game. Finally, the surrogate reward functions are used in a value iterations algorithm and compared to the exact value function of the walking game.