Aliasing in XCS and the Consecutive State Problem: 1 - effects
Alwyn M. Barry · 1999
Whilst XCS (Wilson, 1998) has been shown to be more robust and reliable than previous LCS implementations (Kovacs, 1996, 1997), Lanzi (1997) identified a potential problem in the application of XCS to certain simple multi-step non Markovian environments. The 'Aliasing Problem' occurs when the environment provides the same message for two states in environmental positions that generate different constant payoffs. This prevents classifiers forming a correct payoff prediction for that message. This paper introduces a sub-class of the aliasing problem termed the 'Consecutive State Problem' and uses the subclass to identify the effects of consecutive state aliasing on the learning of the State Action Payoff mapping within XCS. It is shown that aliasing states can prevent the formation of classifiers covering preceding states due to the trade-off of accuracy for match set occupancy made by the classifiers covering the aliasing states. This can be prevented by identifying a condition encoding which makes such match set 'piracy' improbable. However,