Reinforcement Learning

I finally completed the Summer Schools in Logic and Learning (SSLL 09) video lecture for Reinforcement Learning presented by Scott Sanner.  It was a good introduction into Reinforcement Learning.  It is a six part lecture.  Plan for time to watch the videos.  He starts with an introduction into the topic.  Next is model based solutions with Markov Decision Process (MDP) and dynamic programming (DP) with value iteration and policy iteration.  The Bellman equations are introduced.  Lastly, he reviews model free approaches from Chapters 5, 6, and 7 of the Reinforcement Learning: An Introduction (Sutton and Barto 1998).  He covers Monte Carlo and Temporal Difference (TD) algorithms, in particular TD lamdba and SARSA.  However due to large state spaces of problems, he discussion function approximators (both linear and nonlinear) along with gradient descend approaches.  A worth while video lecture.

Warnsdorf Algorithm

As part of my follow research to my paper, I did some preliminary research for the Warnsdorf’s algorithm for finding knight’s tours.  I found three relevant papers on the subject (Pohl 1967, Pohl-Stockmeyer 2004, and Ganzfried 2004).  Basically, the Warnsdorf algorithm is to traverse the path with least degree.  In the case of a tie, the a path is randomly selected.  In reality, the Warnsdorf algorithm is not consistently successful as pointed out by (Ganzfried 2004).  The (Ganzfried 2004) paper modifies the Warnsdorf algorithm with key squares in which the move order changes, which improves finding knight tours.  The next step is generate a prolog program using the Pohl-Warnsdorf and Ganzfried algorithms.

The Art of Prolog

The book The Art of Prolog (Sterling and Shapiro 1994) is an excellent treatise in the subject of Logic Programming and Prolog.  The book is divided into four parts – Logic Programming, The Prolog Language, Advance Prolog Programming Techniques, and Applications.

Beginning with Logic Programming, chapter one provides the best introduction into Logic Programming as well as the first definition of the abstract interpreter for logic programming.  The definitons for term, functor, compound term, clause or rules, logic programs, and the meaning for logic programs are presented.  The summary is worth reading.

Relational Reinforcement Learning

I start this month reading the articles in Relational Reinforcement Learning.  It began as a curiosity due to a response in the Reinforcement Learning mailing list.  The authors point a speech by Rich Sutton and Leslie Pack Kaelbling at the IJCAI 1997 conference in Japan, in which they recommended the combination of Induction Logic Programming (aka Relational Learning) and Reinforcement Learning.  The authors of the paper demonstrate this concept by using the blocks world domain to illustrate the combination of both fields.  Perhaps, this is exactly what I needed since I have done much reading, studying, and video lectures with logic programming, ILP, and reinforcement learning.  Of course, this paper spawn much researching according to CiteSeerX and Google Scholarly.

I found the web site to the 2004 Workshop in Relational Reinforcement Learning and downloaded the proceedings.

I shall continue this path of research interest.