# Anticipatory Classifier System with Average Reward Criterion in Discretized Multi-Step Environments
## 2 Materials and Methods  
### Anticipatory Learning Classifier Systems  
In 1993, [PERSON] proposed a theory of _\"Anticipatory Behavioral Control\"_ that was further refined in [15]. It states that higher animals form an internal environmental representation and adapt their behavior through learning anticipations. The following points (visualized in Figure 1) can be distinguished:  
1. Any behavioral act or response (\(R\)) is accompanied by anticipation of its effects. 2. The anticipations of the effects \(E_{ant}\) are compared with the real effects \(E_{real}\). 3. The bond between response and anticipation is strengthened when the anticipations were correct and weakened otherwise. 4. Behavioral stimuli further differentiate the \(R-E_{ant}\) relations. This insight into the presence and importance of anticipations in animals and man leads to the conclusion that it would be beneficial to represent and utilize them in animals. [PERSON] took the first approach in 1997 [17]. He presented a system called ACS (_\"Anticipatory Classifier System\"_), enhancing the classifier structure with an anticipatory (or effect) part that anticipates the effects of an action in a given situation. A dedicated component realizing [PERSON]'s theory was proposed--_Anticipatory Learning Process_ (ALP), introducing new classifiers into the system. The ACS starts with a population \([P]\) of most general classifiers (\"#' in a condition part) for each available action. To ensure that there is always a classifier handling every consecutive situation, those cannot be removed. During each behavioral act, the current perception of environment \(\sigma(t)\) is captured. Then, a match set \([M](t)\) is formed, consisting of all classifiers from \([P]\) where the condition matches the perception \(\sigma(t)\). Next, one classifier \(cl\) is drawn from \([M](t)\) using some exploration policy. Usually, an epsilon-greedy technique is used, but [18] describes other options as well. Then, the classifier's action \(cl.a\) is executed in the environment, and a new perception \(\sigma(t+1)\) and reward \(\phi(t+1)\) values are presented to the agent. Knowing the classifiers' anticipation and current state, the ALP module can adjust the classifier \(cl\)'s condition and effect parts. Based on this comparison, certain cases might be present:  
* _Useless-case_. After performing an action, no change in perception is perceived from the environment. The classifier's quality \(cl.q\) decreases. * _Unexpected-case_. When new state \(\sigma(t+1)\) does not match the anticipation of \(cl.E\). A new classifier with a matching effect part is generated, and the incorrect one is penalized with a quality drop. * _Expected-case_. When the newly observed state matches the classifier prediction. Classifiers' quality is increased. After the ALP application, the Reinforcement Learning (RL) module is executed (see Section 2.3 for details). Later, in 2002, [PERSON] presented an extension to the described system called ACS2 [16]. Most importantly, he modified the original approach by:  
1. explicit representation of anticipations,
2. applying learning components across the whole action set \([A]\) (all classifiers from \([M]\) advocating selected action),
3. introduction of _Genetic Generalization_ module for generating new classifier using promising offsprings,
4. changing the RL module motivated by the Q-Learning algorithm. Figure 2 presents the complete behavioral act, and [PERSON]. [19; 20] describe the algorithm thoroughly. Figure 1: The theory of anticipatory behavioral control; the figure was adapted from [16], p. 4. Some modifications were made later to the original ACS2 algorithm. [PERSON] et al. integrated the action planning mechanism [21], [PERSON] et al. extended the classifier structure with _Probability-Enhanced-Predictions_ introducing a system capable of handling non-deterministic environments and calling it PEPACS [22].