Joseph Millar, Utah Valley University
Machine learning is a branch of artificial intelligence which focuses on a machines ability to learn rules that make decisions based on some input without the rules being explicitly programmed. This project focuses on Relational Reinforcement Learning (RRL). This is a theory based on the combination of reinforcement learning and inductive logic programming. Reinforcement learning is the idea of learning which sequence of choices achieves the highest reward. Inductive logic programming is learning logical rules that consist of a set of features that are used to describe a situation. One of the problems that is prevalent in RRL is the curse of dimensionality. This means that as the dimensionality of data is increased the complexity of describing and analyzing the data increases, sometimes exponentially. The central research question of this study is to reduce the curse of dimensionality when RRL is used. To achieve this, our theory is that adding better situated features would reduce the curse. To test this theory, we studied the chess endgame of King and Rook vs. King on a 4x4 board. To learn our RRL rules we set up chess-board states of checkmate, checkmate-in-one, and checkmate-in-two. We found that for checkmate there were 40 possible board states, checkmate-in-one had 120 possibilities and checkmate-in-two had 1369 possibilities. We found that for checkmate we needed 30 features per rule, with checkmate-in-one we also needed 30 features and with checkmate-in-two we needed 1239 features. The ratio of features to board-states was 30/40 = .75, 30/120 = .25, and 1239/1369 = .905. The number of features per board-states should be shrinking instead of growing. This is an example of the curse of dimensionality. In order to begin to solve this we created two features that incorporated Rook moves that ended up in the same location. The projected outcome is that the number of features in a rule that are required to describe the board states should decrease by 20%-30%. Therefore, by modifying the set of rules, the curse of dimensionality would be reduced.