Online Feature Discovery in Relational Reinforcement Learning
Scott Sanner · 2006
We introduce a technique for model-free relational reinforcement learning in indefinite horizon undiscounted domains with bounded reward. Previous work has represented the value function as a ground relational naive Bayes net and has leveraged Bayes net parameter and structure learning techniques to refine successive approximations of the value function. Unfortunately, while value function evaluation and parameter inference are very efficient under this framework, even greedy optimal learning of highly restricted naive Bayes net structure can be computationally prohibitive in practice. In this paper, we propose a novel learning algorithm that focuses Bayes net structure learning on the frequently visited portions of state space. Inspired by the Apriori frequent-itemset data mining algorithm, this structure learning algorithm has the dual benefits of efficiency and low-variance parameter estimates. To demonstrate the efficacy of this approach, we present encouraging initial results in the game domains of TicTac-Toe, Backgammon, and Othello.