Relational reinforcement learning (RRL) is a Q-learning technique which uses first order regression techniques to generalize the Qfunction. Both the relational setting and the Q-learning context introduce a number of difficulties which must be dealt with. In this paper we investigate a few different methods that do incremental relational instance based regression and can be used for RRL. This leads us to different approaches which limit both memory consumption and processing times. We implemented a number of these approaches and experimentally evaluated and compared them to each other and an existing RRL algorithm. These experiments show relational instance based regression to work well and to add robustness to RRL.