Samuel Landau

Olivier Sigaud

A Comparison between ATNoSFERES and Learning Classier Systems on non-Markov problems

Keywords: Evolutionary Algorithms, Perceptual Aliasing, Augmented Transition Networks, Learning Classier Systems

The automated design of the controller of software agents embedded in an environment is an important class of problems addressed in information sciences. In that class of problems, the case where agents face perceptual aliasing problems is particularly dicult. Within the evolutionary and adaptive approaches to controller design, there are several families of systems capable of dealing with such problems. This paper is devoted to a comparison of the way perceptual aliasing problems are solved by one family, namely Learning Classier Systems, compared to our own model, ATNoSFERES. We present this model based on an indirect encoding Genetic Algorithm which builds Augmented Transition Network controllers, and we compare it with dierent Learning Classier Systems, namely XCSM (a memorybased extension of the most studied Learning Classier System, XCS) and ACS (an Anticipatory Learning Classier System). To solve perceptual aliasing problems, the rst uses an explicit internal state management mechanism while the second uses a rule-chaining mechanism. To carry out our comparison, we apply these systems to three dierent benchmark experiments. Our results raise a discussion of the respective properties of the mechanisms used by XCSM and ACS. Then we show that ATNoSFERES is endowed with enough expressive power to represent the mechanisms used by the other two systems to deal with perceptual aliasing problems.

We conclude that ATNoSFERES provides a powerful framework to deal with such problems.

Introduction

The software design of decision making systems is a very general problem in information sciences. Roughly speaking, this problem can be split into two categories. First, there are single-step problems, where an agent must make one classication decision from some input. Data mining problems provide good examples of this category. Second, there are multi-step problems, where an agent must make a sequence of decisions in order to reach any arbitrary goal in a given environment. In this paper, we will focus on the second category.

Designing decision making systems by hand is often dicult, whether they belong to the rst category or to the second. So far, a lot of work has been devoted to engineering methods, architectures and theoretical frameworks whose purpose is to help human experts deal with these problems by hand. But in recent years, more and more work is focusing on automated techniques able to tune ecient decision making systems while requiring less design eort from human experts.

Evolutionary computing approaches are promising automated design techniques, because they can be applied to a very wide range of application domains with very few feedback from the applications and without any prior domain-dependent knowledge on the problem. In this family of approaches, Learning Classier Systems (LCSs) [START_REF] Holland | Cognitive Systems based on adaptive algorithms[END_REF] are a family of systems based on evolutionary and learning techniques where the decision making units are expressed in the form of rules called classiers. This formalism makes them very appealing because the rules produced are generally easy to read, interpret, and eventually modify.

While more and more LCSs are used to solve data mining problems, a lot of LCSs are also used to solve multi-step problems, e.g. control agents involved in a sensorimotor loop with their environment. Such agents perceive situations through their sensors as vectors of several attributes, each attribute representing a perceived feature of the environment. As pointed out by [START_REF] Lanzi | Learning Classier Systems from a Reinforcement Learning Perspective[END_REF], LCSs are adaptive architectures based on Reinforcement Learning (RL) techniques [START_REF] Sutton | Reinforcement Learning, an introduction[END_REF], but endowed with generalization capabilities. Thanks to an LCS, an agent can learn the optimal policy i.e. which action to perform in every situation, in order to maximize a reward obtained from the environment. The policy is dened by a set of rules or classiers specifying an action according to some conditions concerning the perceived situation.

Email addresses: muelFvndudfreeFfr (Samuel Landau), ylivierFiguddlipTFfr (Olivier Sigaud).

URLs: httpXGGwwwEpoleiFlipTFfrG£lndu (Samuel Landau), httpXGGwwwFisirFfr (Olivier Sigaud).

Standard RL algorithms perform well in situations where the state of the agent-environment interaction is always known without ambiguity. But in realworld environments, it often happens that agents perceive the same situation in several dierent states, eventually requiring dierent optimal actions, giving rise to the so called perceptual aliasing problem. In such a case, the environment is non-Markov, and in general agents cannot perform optimally if their decision at a given time step only depends on their perceptions at the same time step.

There are several attempts to apply LCSs to non-Markov problems, relying on dierent approaches to the problem. In this paper, we will focus on two approaches: an explicit internal state management mechanism, implemented in XCSM and XCSMH [START_REF] Lanzi | An Analysis of the Memory Mechanism of XCSM[END_REF], and a classier-chaining mechanism implemented in ACS [START_REF] Stolzmann | Anticipatory Classier Systems[END_REF]. So far, there has been no direct comparison between the two kinds of approaches. One of the side-eects of this paper is to provide an indirect comparison through a comparison to our own system, ATNoSFERES.

In previous papers [START_REF] Landau | ATNoSFERES: a Model for Evolutive Agent Behaviors[END_REF]2628], we have presented a new framework, ATNoS-FERES, also used to automatically design the behavior of agents and able to cope with non-Markov problems. ATNoSFERES relies on a pure evolutionary approach instead of the combination of evolutionary and learning techniques used in classical LCSs, but the resulting graph-based representation is semantically very similar to the LCS representation, raising the opportunity of a detailed comparison between the two classes of systems. In this paper, we will show that our approach to the perceptual aliasing problem in ATNoSFERES is endowed with enough expressive power to represent explicit internal state management mechanisms as well as classier-chaining mechanisms. Thus we will use ATNoSFERES as a tool to compare the mechanisms in a unied framework and claim that our system can express more ecient solutions than the two others taken separately. But we will also mention that compared to the LCSs studied here, ATNoSFERES takes more time to nd the solutions.

In the next section, we present the features and properties of the ATNoS-FERES model in the general context of evolutionary techniques. Then we emphasize the formal similarity between the representations in ATNoSFERES and in LCSs, and we present in more detail the dierent approaches used in LCSs to cope with non-Markov problems.

Next, we provide new experimental comparisons diering from the previously published ones in several respect: we make comparisons with new systems and the encoding language is smaller than in previous papers, resulting in a more ecient exploration. First, we compare ATNoSFERES with XCSM and XCSMH on the Maze10 problem, that was used as a benchmark by [START_REF] Lanzi | An Analysis of the Memory Mechanism of XCSM[END_REF] to assess the performance of XCSM and XCSMH. Then we compare ATNoSFERES with ACS, relying on a study [START_REF] Métivier | Anticipatory Classier System using Behavioral Sequences in Non-Markov Environments[END_REF] on two distinct environments, E1 and E2.

We claim that the study presented in this paper gives a rst approach to a more accurate understanding of some relevant properties of dierent classes of non-Markov problems.

From the results, we discuss the respective properties of explicit internal state management mechanisms and classier-chaining mechanisms on dierent problems. Since ATNoSFERES has the power to express the two mechanisms, we claim that it is able to choose the most suitable solution depending on the characteristics of the problem. But we also have to discuss the fact that AT-NoSFERES converges slower than the LCSs studied here on the benchmarks tested in this paper. Thus we conclude that we should include on-line learning mechanisms in our model, which is our goal for immediate future work.

2

Description of the ATNoSFERES model

The graph-building process

The control architecture provided by the ATNoSFERES model [START_REF] Landau | ATNoSFERES: a Model for Evolutive Agent Behaviors[END_REF][START_REF] Picault | Ethogenetics and the Evolutionary Design of Agent Behaviors[END_REF] involves an ATN graph [START_REF] Woods | Transition Networks Grammars for Natural Language Analysis[END_REF] which is basically an oriented, labeled graph with an initial node (labelled Start) and a nal node (labelled End). Nodes represent states and edges represent transitions of an automaton. The graph describing the behaviors is built from a genotype by adding nodes and edges to a basic structure containing only the Start and End nodes.

There are many dierent evolutionary techniques to automatically design structures such as circuits [START_REF] Koza | Automated Design of Both the Topology and Sizing of Analog Electrical Circuits Using Genetic Programming[END_REF], nite-state machines [START_REF] Fogel | Articial Intelligence through Simulated Evolution[END_REF], neural networks [START_REF] Yao | Evolving Articial Neural Networks[END_REF] or program trees [START_REF] Koza | Genetic Programming: On the Programming of Computers by Means of Natural Selection[END_REF]. Very roughly, we can sketch three categories.

The rst one uses the genotype as an encoding of a set of parameters for the structure (using an evolutionary algorithm like Genetic Algorithm [START_REF] Holland | Adaptation in Natural and Articial Systems: An Introductory Analysis with Applications to Biology, Control, and Articial Intelligence[END_REF][START_REF] De | An Analysis of the Behavior of a Class of Genetic Adaptive Systems[END_REF][START_REF] Goldberg | Genetic Algorithms in Search, Optimization, and Machine Learning[END_REF] or Evolutionary Strategies [START_REF] Schwefel | Evolution and Optimum Seeking[END_REF]), which can give rise to ne-grain evolution.

The problem with this approach is that the shape of the structures evolved is directly limited by the number of parameters through which the algorithm searches.

The second one identies the genotype with the structure evolved (e.g. Genetic Programming [START_REF] Koza | Genetic Programming: On the Programming of Computers by Means of Natural Selection[END_REF][START_REF] Montana | Strongly Typed Genetic Programming[END_REF] and Evolutionary Programming [START_REF] Fogel | Articial Intelligence through Simulated Evolution[END_REF]). It can evolve any structure of any shape, but because of the hierarchies and the dependencies between parts of the structure, the genetic operators must be carefully designed in order to produce correct ospring structures, and this involves strong biases in the way they explore the search-space. For example, when one uses Genetic Programming, one must set a limit to the depth of the pro-duced program trees. The consequences of these biases are dicult to evaluate, and much theoretical work is actually involved in studying this problem [START_REF] Poli | Schema Theory for Genetic Programming with One-point Crossover and Point Mutation[END_REF].

The third one uses a genotype relying on a language to build the structure (e.g. developmental program tree for neural networks [START_REF] Kodjabachian | Evolution and Development of Neural Controllers for Locomotion, Gradient-Following, and Obstacle-Avoidance in Articial Insects[END_REF][START_REF] Gruau | Neural Network Synthesis Using Cellular Encoding and the Genetic Algorithm[END_REF][START_REF] Luke | Evolving Graphs and Networks with Edge Encoding: Preliminary Report[END_REF]). This last approach combines the advantages of giving rise to ne-grain evolution of the structure while imposing no limitation on the structure evolved, provided that the genetic operators respect the syntactic rules of the language when producing the ospring.

Most of the languages used to build the structures are either rewriting rules inspired from L-systems [START_REF] Lindenmayer | Mathematical Models for Cellular Interaction in Development, parts I and II[END_REF], or context-free grammars [START_REF] Chomsky | Context-free grammars and pushdown storage[END_REF][START_REF] Chomsky | Handbook of Mathematical Psychology 2, chapter Introduction to the Formal Analysis of Natural Languages[END_REF] for the given structure. On the one hand, rewriting rules might be hard to control. For instance, the structures evolved might grow exponentially, unless limited. On the other hand, context-free grammars impose strict hierarchical constraints on the syntax of the genotypes. When designing the genetic operators, these constraints are easy to deal with thanks to the grammar. But during evolution, these strict hierarchies prevent gradual evolution. As a matter of fact, if a change occurs in a part of the genotype that is governed by a grammatical rule close to the root of the context-free grammar, the constraints on grammatical correctness will imply other major changes in the genotype.

In the ATNoSFERES model, we use a stack-based language [START_REF] Landau | Stack-Based Gene Expression[END_REF]. Its grammar is contextual and does not suer from hierarchical string dependencies.

Therefore we do not face the problem presented above when designing the genetic operators. Like some particular context-free grammatical approaches (e.g. Grammatical Evolution [START_REF] Ryan | Grammatical evolution: A steady state approach[END_REF]) that are nonetheless specialized on program tree evolution, the interpreter accepts any genotype, and always produces a correct structure. Furthermore, we do not need to put any limit (especially on the genotype length), because, as we have reported in previous papers [START_REF] Landau | ATNoSFERES: a Model for Evolutive Agent Behaviors[END_REF], some implicit regulation mechanisms seem to operate.

As a consequence of our choices, the graph building process operates in two steps (see gure 1):

(1) Translation: The bitstring (genotype) is translated into a sequence of tokens. Translation relies on a genetic code, i.e. a function

G : {0, 1} n -→ T (|T | ≤ 2 n ) ( 1
)
where T is the set of possible tokens (the roles of dierent tokens will be described in the next paragraph). Depending on the number of tokens available, the genetic code might be more or less redundant. Binary substrings of size n (decoded into a token each) are called codons.

(2) Interpretation: The token interpreter is fed with the token stream produced by the translator. The tokens are interpreted one by one as instruc-tions of a robust programming language, dedicated to graph building.

The interpretation of each successive token operates on a stack in which parts of the future graph are stored. The construction of the graph takes place during this interpretation process, by creating nodes and connections between nodes. As in other stack-based languages (e.g. Forth [START_REF] Moore | FORTH -A Language for Interactive Computing[END_REF] or PostScript [START_REF]Adobe Systems. The PostScript Language Reference Manual[END_REF]), the data in the stack can also be directly accessed by some instructions other than push/pop operations (e.g. connect, dup: see table 1) and if an instruction cannot be executed successfully, it is simply discarded. When all tokens have been interpreted, the nodes (each one carrying connections to other nodes) are popped from the stack and the graph is ready to use.

Since any sequence of tokens is meaningful, the graph-building language is highly robust to any variation aecting the genotype. Thus there is no specic syntactical or semantical constraint on the genetic operators.

In addition, the sequence of tokens is to some extent order-independent and a given graph can be produced from dierent genotypes. Finally, when all tokens have been interpreted, the unused conditions and actions remaining in the stack are added to the structure and the structure is popped from the stack (c).

Table 1 details the tokens that are used to build the graphs. There are three categories of token:

• behavior tokens (actions, conditions) that are specic to the description of a behavioral structure. These tokens are just pushed onto the stack.

• structure tokens (node, connect, ...) that perform atomic graph building steps, eventually using tokens already in the stack. These tokens are independent from the agent abilities.

• stack tokens (swap, dup, ...) that manipulate the stack. They are both independent from the agent abilities and from the structure built.

token resulting actions behavior tokens actions and conditions tokens, specic to the denition of behavior condition?

push the condition on the stack action! push the action on the stack structure tokens create nodes and connect them with edges node create a new node and push it on the stack connect create an edge from the rst to the second node token a , label the edge with the set of condition tokens and the list of action tokens from the top to the second node, delete the action and condition tokens that were used startConnect create an edge from the Start node to the rst node token, label the edge with the set of condition tokens and the list of action tokens from the top to the rst node, delete the action and condition tokens that were used endConnect create an edge from the rst node token to the End node, label the edge with the set of condition tokens and the list of action tokens from the top to the rst node, delete the action and condition tokens that were used selfConnect b create an edge from the rst node to itself label the edge with the set of condition tokens and the list of action tokens from the top to the rst node, delete the action and condition tokens that were used defaultSelfConnect b create an edge for each node in the stack to itself label the edges with the set of condition tokens and the list of action tokens from the top to the rst node, delete the action and condition tokens that were used stack tokens manipulate the stack nop no action, the token is just discarded swap swap the two rst tokens dup push a copy of the rst action or condition token del delete the rst action or condition token dupNode push a copy of the rst node token delNode delete the rst node token c popRoll pop the token, and put it on the bottom of the stack pushRoll take the token from the bottom of the stack, and push it a if both nodes are copies of the same node, the result is a self-connected edge b additional token c if the stack contains copies of that node, the copies remain in the stack Table 1 The graph building language. Here rst (node, action or condition) refers to the rst (node, action or condition) token encountered while going down the stack. The additional tokens are not strictly necessary since their eect might be obtained by other means. They were introduced in ATNoSFERES in order to cope more easily with generalization.

In [START_REF] Landau | Further Comparison between ATNoSFERES and XCSM[END_REF], we demonstrated that the performance of ATNoSFERES could be increased by using a new structure token, selfConnect, endowing our model with the ability to build self-connecting edges from a node to itself more easily.

This new token has been used in all the experiments presented below.

Integration into an evolutionary framework

In this paper, the ATNoSFERES model is applied inside an evolutionary algorithm to produce the controller of agents. Each agent has a bitstring genotype from which it can build a control graph. The tness of each agent is computed by evaluating its behavior in an environment. Then individuals are selected depending on their tness and bred to produce ospring.

The genotype of the ospring is produced by a classical crossover operation between the genotypes of the parents. Additionally, we use two dierent mutation strategies to introduce variations into the genotype of new individuals: classical bit-ipping mutations, and random insertions or deletions of one codon. This modies the sequence of tokens produced by translation, so that the complexity of the graph itself may change. Nodes or edges can be added or removed by the evolutionary process, as can condition/action labels on the edges.

To evaluate an agent, we use those graphs as follows (see also gure 3):

• At the beginning (when the agent is initialized), the agent is at the Start node (S).

• At each time step, the agent crosses an edge:

(1) It computes the set of eligible edges among those starting from the current node. An edge is eligible when either it has no condition label or all the conditions on its label are simultaneously true.

(2) An edge is chosen in this set. The rst versions of ATNoSFERES were choosing the eligible edges randomly, but then we found that a deterministic choice (e.g. choose the rst edge in the list of eligible edges) yieldeld better results. If the set is empty, then an action is chosen randomly over all possible actions, the current node remains unchanged, and we do not perform the next step.

(3) The actions on the label of the current edge are sequentially performed by the system. Assuming that only one action can be performed at a time, only the last action is actually performed. When the action part of the label is empty, an action is chosen randomly. In all the experiments described in this paper, the action part of all edges contains at most one action, in order to simplify the comparison with LCSs.

(4) The new current node becomes the destination of the edge.

• The agent stops when it is at the End node (E). This node is a general feature of our model and may never be reached. This appears to be the case in all the following experiments (since agents reaching the End node stop moving and thus have a very low tness, see 4).

3

LCSs, non-Markov problems, and ATNoSFERES

Learning Classier Systems

As explained in the introduction, LCSs are rule-based systems combining RL algorithms with generalization capabilities. In the context of multi-step problems, the problems tackled by LCS are characterized by the fact that situa-

Matching

Selected Action

[E]

Current Situation

Local Perception

Condition Action

[01010111] An historical presentation of research on LCSs can be found in [START_REF] Wilson | A critical review of Classier Systems[END_REF] and [START_REF] Lanzi | A roadmap to the last decade of Learning Classier Systems research (from 1989 to 1999[END_REF].

[N] [S] [NE] [W] ... Classifiers List [#00#0#1#] [#1010##1] [10###101] [0#10#0#0] : Move East 0 0 0 1 1 1 1 1 1 F [#10##1#1] [E] Selection [#10##1#1] [E]
Here, we will just present the modern view of LCSs resulting from the radical simplications achieved by Wilson in designing ZCS [START_REF] Wilson | ZCS, a Zeroth level Classier System[END_REF] and XCS [START_REF] Wilson | Classier Fitness Based on Accuracy[END_REF].

In this view, an LCS evolves a population of classiers with a [Condition] part, an [Action] part and some measure of the benet that the system can draw from performing the action if the condition holds. Generally, this measure is updated thanks to an RL algorithm and the population of classiers evolves according to a Genetic Algorithm (GA) [START_REF] Goldberg | Genetic Algorithms in Search, Optimization, and Machine Learning[END_REF] using this measure as tness function. Within this framework, the use of # symbols in the [Condition] part of the classiers results in a generalization capability, since don't care symbols make it possible to use a single vector of symbols to describe several situations 1 . Indeed, a don't care symbol matches any particular value of the considered attribute.

1 For instance, in a binary language, I5H matches both IHH and IIH.

In most early LCSs [START_REF] Holland | Cognitive Systems based on adaptive algorithms[END_REF], the tness of each classier was dened directly according to the expected utility associated to the classier. After having dened a very simple LCS called ZCS, [START_REF] Wilson | ZCS, a Zeroth level Classier System[END_REF] found it more ecient to use the accuracy of the utility prediction rather than the expected utility itself. In particular, this tness measure results in a better coverage of the state space since accurate classiers predicting a low reward far from the source of reward will be kept. The resulting system, XCS [START_REF] Wilson | Classier Fitness Based on Accuracy[END_REF], is now the most widely used LCS in the context of Markov problems and data mining problems [START_REF] Bernardó | XCS and GALE : a comparative study of two Learning Classifer Systems with six other learning algorithms on classication tasks[END_REF].

Anticipatory Learning Classier Systems (ALCSs) are a more recent family of LCSs. The rst ALCS, ACS, has been developed by [START_REF] Stolzmann | Anticipatory Classier Systems[END_REF] and then improved as ACS2 by [START_REF] Butz | Anticipatory Learning Classier Systems[END_REF]. It diers from classical LCSs by adding to the [Condition] and [Action] parts an [Effect] part that represents a perceptual anticipation of the consequences of the action upon the environment. ACS relies on an Anticipatory Learning Process (ALP) [START_REF] Stolzmann | Anticipatory Classier Systems[END_REF] and has been successfully applied to both Markov [START_REF] Stolzmann | An introduction to Anticipatory Classier Systems[END_REF] and non-Markov [START_REF] Stolzmann | Latent Learning in Khepera Robots with Anticipatory Classier Systems[END_REF] environments.

The main feature of ACS with respect to standard LCSs is that their use of anticipation make it possible to use some ecient heuristics helping the system to converge faster, though no explicit performance comparison has been published yet. GÃ c rard and Sigaud have proposed two ALCSs similar to ACS, namely YACS [START_REF] Gérard | YACS: a new Learning Classier System using Anticipation[END_REF] and MACS [START_REF] Gérard | Combining latent learning and dynamic programming in MACS[END_REF]. These systems have been shown to be faster than ACS and to give rise to a more compact set of classiers, but they are limited to Markov and deterministic environments.

Pittsburgh versus Michigan style

A LCS usually uses a GA to replace some classiers for improved performance.

But there are two dierent ways of using GAs in this context, giving rise to the distinction between Pittsburgh style LCSs (e.g. [START_REF] Smith | A Learning System based on Genetic Adaptive Algorithms[END_REF]) and Michigan style LCSs (e.g. [START_REF] Holland | Escaping brittleness: The possibilities of general-purpose learning algorithms applied to parallel rule-based systems[END_REF]).

In the Pittsburgh style, the GA evolves a population of controllers with their whole list of classiers. The lists of classiers of dierent controllers are combined using crossover operators and modied with mutations. The controllers are evaluated according to a tness measure and the more ecient ones with respect to the tness are kept. Thus a Pittsburgh style LCS evolves a population of controllers. On the contrary, in the Michigan style, the GA evolves a population of classiers belonging to a single controller: classiers are the individuals combined and modied by the GA. A tness is computed for each classier and the best ones are kept. Thus Michigan style LCSs use a GA to perform online learning: the classiers are improved during the life time of the agent. Usually, such LCSs rely on utility functions that depend on scalar rewards given by the environment, as dened in the RL framework (see [START_REF] Sutton | Reinforcement Learning, an introduction[END_REF]).

Most recent LCSs are Michigan style systems. As we will explain in the following sections, several research trends attempt to combine the advantages of the Michigan approach with those of the Pittsburgh approach.

Learning Classier Systems on non-Markov problems

Dealing with simple [Condition][Action] classiers does not endow an agent with the ability to behave optimally in perceptually aliased problems. In such problems, it may happen that the current perception does not provide enough information to always choose the optimal action: as soon as the agent perceives the same situation in dierent states, it will choose the same action though this action may be inappropriate in some of these states (see gure 4, page 17, for an example).

In such a case, it is necessary to provide the system with more than just current perceptions. In the general RL framework, several kinds of solutions have been tested.

• The rst one consists in adding explicit internal states to the perceptions involved in the decisions of the system. This approach was used by Holland in his early LCSs thanks to an internal message list [START_REF] Holland | Cognitive Systems based on adaptive algorithms[END_REF]. But both [START_REF] Robertson | A tale of two classier systems[END_REF] and [START_REF] Smith | Memory exploitation in learning classier systems[END_REF] reported unsatisfactory performance of Holland's system on non-Markov problems. In the context of more recent LCS research, a dierent form of the explicit internal state solution was adopted by [START_REF] Cli | Adding memory to ZCS[END_REF] in ZCSM and by [START_REF] Lanzi | Toward optimal classier system performance in non-markov environments[END_REF] in XCSM and XCSMH.

• The second one, memory window management, is a special case of explicit internal state management where the internal state consists in an immediate memory of the past. Some systems use a xed size window (see [START_REF] Lin | Memory approaches to reinforcement learning in non-markovian domains[END_REF] for a review) while others use a variable size window (e.g. [START_REF] Mccallum | Reinforcement Learning with Selective Perception and Hidden State[END_REF]). The next solution, rule-chaining, can be seen as an alternative view of the variable size window mechanism.

• The third one consists in chaining the decisions, making one decision depend on the decisions previously taken, so as to use a memory of previous actions to disambiguate the current situation. Among LCSs, this solution was used in ZCCS [START_REF] Tomlinson | A zeroth level corporate classier system[END_REF], CXCS [START_REF] Tomlinson | Learning Classier Systems: from Foundations to Applications[END_REF] and ACS [START_REF] Stolzmann | Latent Learning in Khepera Robots with Anticipatory Classier Systems[END_REF].

• The fourth one consists in splitting a non-Markov problem into several Markov problems, making sure that aliased states are scattered among different sub-problems. This solution has been investigated rst by [START_REF] Wiering | HQ-Learning[END_REF], and then improved by [START_REF] Sun | Multi-agent reinforcement learning with bidding for segmenting action sequences[END_REF]. To our knowledge, no LCS actually uses this solution, despite its very interesting properties.

• The last solution consists in building a nite state automaton corresponding to the structure of the problem, as [START_REF] Meuleau | Learning nite-state controllers for partially observable environments[END_REF] or [START_REF] Hansen | Finite Memory Control of Partially Observable Systems[END_REF] do, in a context where the structure of the problem is known in advance. This is the solution chosen in ATNoSFERES, but in a context where the agents do not know anything about the structure of the problem before starting. To do so, we use a Pittsburgh style evolutionary algorithm.

In the remainder of this section, we will examine more closely two strategies that have been used to solve non-Markov problems in LCSs, namely Explicit Internal State Management and Classier-Chaining.

Explicit Internal State Management

Shortly after the original ZCS [START_REF] Wilson | ZCS, a Zeroth level Classier System[END_REF] was published, an explicit internal state was added [START_REF] Cli | Adding memory to ZCS[END_REF] to ZCS. The resulting system was called ZCSM, where M stands for Memory.

Following the same idea and suggestions already present in [START_REF] Wilson | Classier Fitness Based on Accuracy[END_REF], Lanzi [START_REF] Lanzi | An Analysis of the Memory Mechanism of XCSM[END_REF] proposed XCSM as an extension of XCS with explicit internal states. XCSM manages an internal memory register composed of several bits that explicitly represents the internal state of the LCS. The memory register provides XCSM with more than just the environmental perceptions. Thus, dealing with perceptual aliasing is made possible by adding information from the past experience of the agent. As a result of this addition, a classier contains four parts: an external condition about the situation, an internal condition about the internal state, an external action to perform in the environment and an internal action that may modify the internal state.

The [Internal condition] and [Internal action] parts contain as many attributes as there are bits in the memory register. In order to be selected by the LCS, a classier must match with both the external and internal conditions. When it is selected, the LCS performs the corresponding action in the environment and modies the internal state if the internal action is not composed only of don't change symbols #. When a classier is red, a # in the internal action results in not changing the corresponding bit in the memory register. XCSM benets from generalization in the external condition (like XCS), in the internal condition and also in the internal action.

Results obtained with XCSM on several benchmark environments were presented in [START_REF] Lanzi | Toward optimal classier system performance in non-markov environments[END_REF], Maze10 (see gure 4, p. 17) being the most dicult. The very poor performance of XCSM on complex non-Markov problems led Lanzi to propose a further extension, XCSMH, where H stands for hierarchical. The only dierence between XCSM and XCSMH is that in the latter the dynamics of the internal state is deterministic even during exploration, and that the internal state cannot change if the perceptions do not change. This minor modication resulted in a signicant improvement in performance (see [START_REF] Lanzi | Toward optimal classier system performance in non-markov environments[END_REF]).

Classier-chaining mechanisms

LCSs that use a classier-chaining mechanisms are called corporate classier systems. The rst suggestion of a corporate classier system appears in [START_REF] Wilson | A critical review of Classier Systems[END_REF].

The authors provide a critical review of early LCSs and express the need for a good combination of Michigan and Pittsburgh approaches. After reviewing a few earlier seminal works, the solution they suggest consists in creating corporations of classiers by linking together classiers often red in sequences.

To our knowledge, the corresponding system has never been implemented.

More recently, ZCCS, a corporate classier system inspired from [START_REF] Wilson | A critical review of Classier Systems[END_REF] and based on ZCS [START_REF] Wilson | ZCS, a Zeroth level Classier System[END_REF], has been implemented [START_REF] Tomlinson | A zeroth level corporate classier system[END_REF], probabilistically linking classiers into behavioral sequences. In general, the length of the behavioral sequences is arbitrarily limited to a given parameter. This solution is adequate for solving perceptual aliasing problems since a behavioral sequence can result in bridging aliased situations: the sequences that help solve perceptual aliasing problems are sequences starting before the ambiguous states and ending after these states have been crossed. Since the ambiguous states are hidden in sequences, the agent never needs to guess what to do in an ambiguous context. The success of this solution relies on the probabilistic nature of the sequence building algorithm. Sequences providing a selective advantage (because they bridge an aliased state) are kept, the others are discarded.

The same authors then proposed CXCS [START_REF] Tomlinson | Learning Classier Systems: from Foundations to Applications[END_REF], a second corporate classier system based on XCS. In [START_REF] Tomlinson | An accuracy-based corporate classier system[END_REF], they experimented a lot of simple variations on the original corporation mechanism, exploration rate and corporate representation. Unfortunately, they tested their systems mostly on Markov problems and on a non-Markov hand-crafted delayed reward task that is too simple to provide a serious benchmark for comparison. On a dierent line of research, another classier-chaining mechanism was used in ACS in order to deal with non-Markov environments [START_REF] Stolzmann | Latent Learning in Khepera Robots with Anticipatory Classier Systems[END_REF]. In that case, the [Effect] part of a classier consisting in a behavioral sequence is intended to represent the perceptual consequence of the sequence of actions. The mechanism is restricted to deterministic domains and applies classier-chaining in particular situations, whereas CXCS forms many more connections so as to nd the relevant ones by chance. Despite its restricted use, its classierchaining mechanism makes ACS able to deal eciently with deterministic non-Markov environments. In order to build behavioral sequences, a new parameter was added to ACS, namely BS max . BS max represents the maximal length of the behavioral sequences that ACS may build. 3. Using ATNoSFERES to control an agent. In this example, the agent, located in a cell of the maze, perceives the presence/absence of blocks in each of the eight surrounding cells. It has to decide towards which of the eight adjacent cells it should move. From its current location, the agent perceives i ¬xi x ¬x ¬ ¬ ¬i (token i is true when the east cell is blank). From the current state (node) of its graph, two edges (in bold) are eligible, since the gondition part of their label matches the perceptions. One is selected, then its action part (move east) is performed and the current state is updated.

ATNoSFERES and

Like LCSs, ATNoSFERES binds conditions expressed as a set of attributes to actions, and is endowed with the ability to generalize conditions by ignoring some attributes. Indeed, an ATN such as those evolved by ATNoSFERES can be easily translated into a list of classiers, either using an explicit internal state or a classier-chaining mechanism. Whatever the LCS formalism, the conditions associated with the edges correspond to the conditions of the classiers and the actions associated to the edges correspond to the actions of the classiers.

In the explicit internal state view, the nodes of the ATN play the role of internal states and endow ATNoSFERES with the ability to deal with perceptual aliasing. The source and destination nodes of the edge correspond to internal states.

In the classier-chaining mechanism, all edges can be translated into classiers either independently from each other or in chains of any lengths, linking edges ending in a node to another edge starting from the same node.

Thus our model has the potential to express the dierent mechanisms found in LCSs listed above when confronted to non-Markov problems.

4

Experimental Comparisons

Experimental setup

All experiments presented in this paper take place in the context of non-Markov multi-step problems. In order to carry out some comparisons, we use benchmark experiments involving an agent looking for some food in a simple maze-like environment (see gures 4 and 6). We tried to reproduce an experimental setup as close as possible to that used in [START_REF] Lanzi | An Analysis of the Memory Mechanism of XCSM[END_REF] to test XCSM and XCSMH in the Maze10 environment and in [START_REF] Métivier | Anticipatory Classier System using Behavioral Sequences in Non-Markov Environments[END_REF] to test ACS in E1 and E2

environments, taking into account the specicities of our model. The same setup has been applied to all the experiments presented in this paper.

Perception/Action abilities and Tokens

The agents used for the experiments can perceive the presence/absence of walls or the presence of food in the eight adjacent cells of their environment, these three perceptions being mutually exclusive. They can move in all adjacent cells (the move will be eective if the cell is blank or contains food). Thus, the genetic code includes 24 condition tokens and 8 action tokens that depend on this particular setup. Additionally, it includes 7 stack manipulation tokens and 4 node creation/connection tokens that are independent of the problem.

With respect to the encoding used in previous publications, we used a new 6 bit encoding to dene these 43 tokens. Previously we used either 7 bit long tokens [START_REF] Landau | An Experimental Comparison between ATNoSFERES and ACS[END_REF] or dierent 6 bit long tokens [START_REF] Landau | A comparison between ATNoSFERES and XCSM[END_REF][START_REF] Landau | Further Comparison between ATNoSFERES and XCSM[END_REF]. Table 2 The genetic code used in the experiments.

Since 2 6 = 64, some tokens can be encoded twice or more. The choice to encode one token or another several times as it appears in table 2 is arbitrary: we took into account some soundness constraints such as having the same number of tokens with symmetrical eects (e.g. dupNode and delNode) but we did not try to improve it over several experiments. Looking for an optimal mapping between tokens and encoding would be computationally too expensive and is currently outside the scope of more theoretical tools such as the ones developed in [START_REF] Poli | Schema Theory for Genetic Programming with One-point Crossover and Point Mutation[END_REF].

Course of Experiments

Each experiment involves the following steps:

(1) Initialize the population with N = 300 agents with random bitstrings.

(2) For each generation, build the controller of each agent and evaluate it in the environment.

(3) Select the 20 % best individuals of the population and produce new ones by crossing the parents. The system performs probabilistic mutations (with a 1% rate) and insertions or deletions of codons (with a 0.5% rate) on the bitstring of the ospring.

(4) Go back to step 2 with the new generation.

Fitness function.

Each individual is evaluated in the environment, starting on a blank cell in the environment and looking for food within a limited duration (20 time steps in all experiments described below). The agent can perceive the food only in its immediate neighborhood, and it can perform only one action per time step; when this action is incompatible with the environment (e.g. go west when the west cell contains an obstacle), it has no eect (the agent loses one time step and stays on the same cell).

The tness of the agent for each run is the remaining time if the food has been found within the time limit, 0 otherwise. Thus, the selection pressure encourages short paths to food. To evaluate one generation, each agent is evaluated once starting on each blank cell, then its total tness for this generation is the sum of the tnesses computed for each run.

Each agent is reevaluated at each generation in order to average its tness over generations. This is necessary because of non-determinism in the automata.

Indeed, in a situation where no arc is eligible, or when an edge does not carry any action label, one action is chosen randomly. Thus an automaton will be fully deterministic only in the case where one arc can be elected in any encountered situation, and if all such arcs bear an action to perform.

Experimental environments 4.2.1 Maze10

We rst tested our model in the Maze10 environment (see g. 4), for which [START_REF] Lanzi | An Analysis of the Memory Mechanism of XCSM[END_REF] provides empirical results obtained with XCSM and XCSMH.

This environment is non-Markov, and presents 13 aliased situations (among the 18 free cells) which are perceived as 5 distinct situations. In gure 10, page 21, we show the optimal number of steps necessary to reach food from each starting cell, given a limited perception (an omniscient agent could perform even better). More precisely, in order to compute this optimal policy, we take into account the fact that an agent cannot choose the correct action in a perceptually aliased situation if it cannot determine its actual state from its past. In particular, an agent starting from an ambiguous situation can only choose an action from the probability that each action is the most favorable one across the possible states.

F S1 S1 S2 S2 S3 S3 S4 S4 S5 S5 S4 S1 S2
Fig. 4. The Maze10 environment. F represents the goal (food). Other marked cells represent aliased situations (identical names imply the same perception, but eventually not the same optimal action).

The experiments reported in [START_REF] Landau | A comparison between ATNoSFERES and XCSM[END_REF] were carried out on various initial genotype sizes, from 50 to 90 codons of 6 bits, and the food was not perceived. The original population genotype sizes changed during evolution. Here, we reconducted the experiments including the ability to perceive food, with initial genotype sizes from 50 to 300 codons of 6 bits. Each experiment is stopped after 10,000 generations and 20 experiments have been performed in each experimental situation. formance of XCSM and the performance of XCSMH, but that ATNoSFERES often outperforms XCSMH, going very close to the optimum. This result will be discussed in 5. The experiments described below take place in E1 and E2 environments (see gure 6) that have been used in [START_REF] Métivier | Anticipatory Classier System using Behavioral Sequences in Non-Markov Environments[END_REF] to study how ACS deals with non-Markov problems. E1 presents 20 aliased situations (among the 44 free cells) which are perceived as 9 distinct situations. E2 presents 36 aliased situations (among 48 free cells), which are perceived as 5 distinct situations.

E1 and E2

In gure 13, page 23, we show the number of steps an optimal agent among several may need to reach food from each starting cell, given that its perception is limited, as explained in 4.2.1.

Before comparing ACS with ATNoSFERES, we have to emphasize a major dierence between the way both systems deal with these environments. In ACS experiments, as they are described in [38, 4.1 and 4.2], the only movements tested in each free position are transitions towards surrounding free cells (for example, if the cell to the north contains an obstacle, going north is not considered as a possible move, thus it cannot be selected). This constitutes a kind of prior domain-dependent knowledge about consistent perceptionsactions bindings, which signicantly biases the learning process by reducing the number of possibilities. In [START_REF] Sigaud | Contribution au problème de la sélection de l'action en environnement partiellement observable[END_REF], we have shown that prohibiting the use of this bias can severely impair some learning algorithms. For instance, the U-Tree algorithm [START_REF] Mccallum | Reinforcement Learning with Selective Perception and Hidden State[END_REF] which works well in non-Markov mazes (such as those studied here) if the agent is prevented from bumping into walls, might grow an innitely deep tree if it keeps bumping into the same wall in an aliased situation.

In ATNoSFERES, on the contrary, any action can be used at any time. When the corresponding move is impossible, the agent stays where it is and loses a time step (it is penalized only in an indirect way, through the tness function).

The experiments reported in [START_REF] Landau | An Experimental Comparison between ATNoSFERES and ACS[END_REF] were carried out on various initial genotype sizes (from 50 to 150 codons), but the codons were 7 bit long. The experiments presented here are reconducted with 6 bit long codons, and the genotypes are between 50 and 200 tokens long (with step 10) in E1, and between 50 and 300 tokens long (with step 10) in E2. As with Maze10, each experiment is stopped after 10,000 generations. For E1 (resp. E2), 20 experiments (resp. 10 experiments) are performed in each experimental situation.

Figures 7 and8 give the respective tness values obtained by the best automata in E1 and E2 experiments, depending on initial lengths of the genotypes, and the average of these values, compared with the values published by [START_REF] Métivier | Anticipatory Classier System using Behavioral Sequences in Non-Markov Environments[END_REF] on ACS.

From gure 7 (a), it can be seen that in E1, ATNoSFERES easily reaches the performance of ACS in the case where BS max = 1, but never reaches the performance of ACS with BS max = 2, which is very close to the optimum. On average (see gure 7 (b)), ATNoSFERES reaches the performance of ACS in the case where BS max = 1 as soon as the initial length of the genotype is over 110. On the other hand, in E2, the performance obtained with ATNoSFERES (see gure 8) is signicantly better than the one obtained with ACS with BS max = 2 and BS max = 3. Indeed, ATNoSFERES is always performing better than ACS on average. Figure 9 gives the evolution of the best tnesses. We see that gradual improvements occur in the three environments. Fig. 10. An optimal policy in Maze10, represented by the number of steps needed to reach food from each start cell.

The optimal average number of steps to food is 5.0555. As in previous experiments [START_REF] Landau | A comparison between ATNoSFERES and XCSM[END_REF], the graph of the best automaton (see gure 12) has two internal nodes. This automaton is representative for the best solutions found with this environment. By scanning all the best solutions corresponding to crosses in gure 5 (a), we see that some good solutions have three internal nodes, but most good solutions have two internal nodes. The solutions with only one internal node have the worst performance (more than 10 steps to food on average). Thus the best solutions are the ones connecting two nodes with the good set of edges.

Thanks to the ability to perceive food, the tness reached is higher than in our previously published experiments. A comparison between gure 10 and 11

shows that the policy of the best automaton is very close to the optimal policy. Two steps are lost for every cell in the left-wing column because the agent goes to the bottom of the second left-wing column to check whether the food is there while this is not necessary: the left-wing top corner cell is sucient to disambiguate the situation. Other steps are lost in the top of the right-wing column because the agent goes north instead of going west or north-west, which would be optimal. (b) E2 environment Fig. 13. An optimal policy in E1 (resp. E2), represented by the number of steps needed to reach food from each start cell. Other equivalent policies can be obtained at least by applying all possible rotations and symmetries to all the numbers given.

E1 and E2 environments

In E1, the optimal average number of steps to food is 2.8181 steps. In E2, it is 2.9792 steps. Figures 13 and14 show some optimal policies on E1 and E2 environments respectively, and the best policies found on these environments with ATNoS-FERES. On gure 14, we can see that in some situations where food is visible the agent needs more than one step to reach it, though a more ecient behavior is obvious. ATNoSFERES has more diculties in nding these simple rules than an RL algorithm combining exploration and exploitation would.

This will be discussed in 5.4. This fact will be discussed in the next section.

A closer study of the automata obtained in E1 and E2 environments reveals that the main improvement mechanisms consists in adding one node when they contain a single node, and then add more edges to make prot of relevant situation-action couples. For instance, the performance is increased each time ATNoSFERES builds a new edge binding the perception of food to a move toward food. As we will discuss in the next section, this implies that good solutions generally contain more edges connected to the same nodes than poorer solutions.

5 Discussion

Nearly Markov versus highly non-Markov problems

As a result of the new experiments performed in this paper, it appears that dierent subclasses of non-Markov problems should be distinguished more accurately than is usually done. Indeed, some problems, like E1, are actually non-Markov, but in such a way that reactive behaviors can still perform well on such problems, as shown by the performance of all automata with one node, exemplied in gure 16. We call them nearly Markov problems.

In E1, our study has shown that an evolutionary process can gradually grow a set of correct rules (which are to some extent independent from each other), even more if the agent is tested from each cell. Thus an agent can start with a few rules that are ecient for a few cells, and add from one generation to another new rules that are useful for additional cells. Such reactive solutions already perform well in E1, and are easier to nd for ATNoSFERES than solutions implying several internal states. Indeed, building more complex solutions requires both additional nodes and consistent edges, with appropriate conditions and actions. We meet again the structural cost mentioned in [START_REF] Landau | A comparison between ATNoSFERES and XCSM[END_REF]: simple, incremental good solutions are preferred to structurally complex optima. As a matter of fact, ACS with BS max = 2 performs better than ATNoSFERES on E1.

On the contrary, other environments like E2 and Maze10 should be called highly non-Markov, since reactive policies perform very poorly on such problems, due to the location and the number of aliased situations.

Our comparative study has revealed that ACS performs very well on E1 and relatively poorly on E2, while ATNoSFERES performs consistently on both environments. In the remainder of this discussion section, we will try to explain why that is so.

Limits of classier-chaining

The rst point to explain is the fact that ACS performs relatively poorly on E2. On rst thoughts, one might consider that the maximal length of sequences in ACS is the key. One could expect that setting BS max to more than 3 in E2 could x the problem. A closer examination, however, reveals that this is not so.

In [START_REF] Métivier | Anticipatory Classier System using Behavioral Sequences in Non-Markov Environments[END_REF], the authors show that setting BS max to 3 is enough to let ACS build a completely reliable model of E2, under the form of a list of (situation, action, next situation) classiers. They mention that increasing the maximum length of the behavioral sequence does not improve the `steps to food' performances.

One explanation of the fact that building longer action sequences does not improve the performance is that these sequences specify a blind series of actions performed without interruption and without checking the situation perceived before its end. Once a sequence is elected, the agent will at least perform the number of actions specied in the sequence, unless it nds the food during the sequence. Since the number of steps to food given by the optimal policy in E1 and E2 is generally less than 4, it is very unlikely that letting the agent perform sequences of 4 actions or more will help reaching the optimal performance. given in gure 6. Doubly-circled nodes represent next to nal observations, linked to the nal F cell, which is not represented here for readability purpose. The complete policy structures starting from all ambiguous cells would be unreadable, but all local policies share a similar structure for both problems.

! E! Cd E! NW! Ce NE! NE! Cf N! N! N! 10 N! Cg N! E! (b) C in E2 C a ∈ {C 13 , C 14 , C 15 } C b ∈ {C 12 } C c ∈ {C 10 , C 16 } C d ∈ {C 9 } C e ∈ {C 13 } C f ∈ {C 10 , C 11 , C 12 , C 13 } C g ∈ {C 14 } (
A second explanation of the relatively poor performance of ACS on E2 with respect to E1 comes from an analysis of gure 18. This gure shows one optimal policy among several from selected ambiguous cells in the E1 and E2

environments. As it can be seen, optimal performance with a classier-chaining mechanism is not possible in E2 because the following happens:

• either we call upon 1-classier-long sequences in the initial situation but the optimal policy also requires at the next time step classiers with the same condition part (see the C c node on gure 18). • or we call upon longer sequences starting with the same condition part.

In both cases, the agent cannot choose the correct decision unit from the ambiguous situation. Thus the classier-chaining mechanism is formally unsuitable in front of such structures since the agent must decide in advance which sequence of classiers will be red before having encountered the perceptions informing it of the correct choice. On the contrary, this mechanism is appropriate in the case of E1 where the structure of the optimal policy is a simple list of action sequences connected to the same root node. Indeed, in small environments like Maze10, E1 and E2, the main issue for the agent consists in discovering as fast as possible where it is from an initially ambiguous situation and then follow the shortest path to the goal. In E1 this can be achieved with a list of classier-chains while this is not the case in E2.

One-to-one versus many-to-many associations

As clearly explained in [START_REF] Tomlinson | An accuracy-based corporate classier system[END_REF], associations in CXCS are direct and one-to-one while they are many-to-many in XCSM(H). More generally, in all systems relying on a classier-chaining mechanism, the association can be said oneto-one because the corporation mechanism connects only one classier to another. By contrast, an explicit internal state management mechanism builds many-to-many associations since all classiers sharing the same [Internal condition] part can be red after all classiers that specify the corresponding [Internal action] part. When one compares the mechanisms in CXCS to the one in XCSM(H), one might consider that a one-to-one association gives a greater control on the dynamics of the internal state than a many-to-many association.

Indeed, in XCSM(H), the internal state value is very unstable and in [START_REF] Lanzi | Toward optimal classier system performance in non-markov environments[END_REF] some special purpose mechanisms in XCSMH had been designed so as to overcome this problem. But our design of ATNoSFERES reveals that the problem does not come from many-to-many associations per se, but from the way they are represented in XCSM(H). Indeed, ATNoSFERES is clearly able to build many-to-many associations (when more than two edges are connected through the same node), as well as one-to-one associations (when just two edges are connected through the same node).

Thus ATNoSFERES combines the advantages of both approaches.

• Like XCSM(H), it is able to build many-to-many associations and we have seen in the previous section that this property is necessary to yield an excellent performance on environments like E2 and Maze10.

• Like CXCS and ACS, it is endowed with a good control over the internal state dynamics, and can eventually build one-to-one associations, which makes the ad hoc mechanisms added in XCSMH unnecessary.

Being able to build both kinds of associations, ATNoSFERES is also able to select the most appropriate combination of them thanks to the GA. This explains why ATNoSFERES can outperform both XCSMH on some environments and ACS on others. But the fact that ACS with BS max = 2 outperforms ATNoSFERES on E1 seems to imply that ATNoSFERES encounters more diculties to build ecient one-to-one associations when they are the most necessary, i.e. in nearly Markov problems. This can be easily explained since building exactly two edges connected by one node requires a lot of precise constraints on a genotype.

Reinforcement Learning and Classier Selection

In our results, the behavior obtained on all environments with all systems are never fully optimal, despite the relative simplicity of these environments. Thus a performance comparison must consider two dimensions:

• how close to the optimum did the system get?

• how long did it take to get there?

We have shown that, with respect to the rst point, ATNoSFERES can be compared favorably with the LCSs studied here. But, with respect to the second point, one important advantage of LCS over ATNoSFERES is that LCSs learn to act thanks to an RL algorithm.

Indeed, if we compare the number of elementary runs necessary to reach a good performance with LCSs against ATNoSFERES, the dierence is clear (see table 3). In this table, the LCS column gives the average number of elementary runs after which the LCSs converge to the performance indicated, known as the best performance of the corresponding system (see 4 E2 ACS (BSmax = 2 or 3) 6.5 2,000 83.84 835 14.10 6 7,000 Table 3 Comparison between ATNoSFERES and LCSs on the basis of the average number of trials necessary to reach the performance given in column perf.. P R is the percentage of evolution runs with ATNoSFERES that outperform the corresponding LCS. N G is the average number of generations after which this happens (see gure 9, but the average has been computed from an exhaustive computation on all the runs presented on gures 5, 7 and 8). Thus, with 300 individuals per generation, the average number of evaluation runs necessary to outperform the corresponding LCS From this table it is clear that ATNoSFERES still needs several orders of magnitude more runs than XCSMH and ACS to converge (from 7000 to 200,000 times more).

This can be easily explained by the fact that ATNoSFERES evolves automata thanks to a blind GA process while ACS and XCSMH rely on an RL algorithm extracting information about the environment from its experience. From this comparison, it is clear that a direction for improving ATNoSFERES consists in endowing it with RL capabilities. This is our immediate agenda for future work.

A source of inspiration in that direction comes from the Samuel system [START_REF] Grefenstette | Lamarckian learning in multi-agent environments[END_REF].

Like ATNoSFERES, Samuel is a Pittsburgh style system based on a single chromosome GA, but it also includes Lamarckian operators that endow it with basic learning capabilities. As a result, as claimed by the author, Samuel represents an integration of the major genetic approaches to machine learning, the Michigan approach and the Pittsburgh approach. Most of the operators used in Samuel can be transposed in ATNoSFERES, the main dierence being that ATNoSFERES does not provide a high level symbolic representation and that Samuel does not include any dedicated mechanism to solve perceptual aliasing problems.

Conclusion

In previous papers, we have emphasized some advantages of ATNoSFERES over LCSs. In particular, ATNoSFERES builds minimal controllers, which results in their improved readability.

In this paper, we have applied ATNoSFERES to non-Markov benchmark environments that have been investigated with ACS, XCSM and XCSMH. This study gave us the opportunity to compare two mechanisms designed to deal with non-Markov problems, namely explicit internal state management and classier-chaining. We have explained why the second was formally unable to reach optimality in some environments.

From that comparison, a new advantage of ATNoSFERES over the LCSs studied here is revealed. Since its representation has enough expressive power to include both one-to-one and many-to-many associations to solve non-Markov problems, the GA can select the most suitable approach or combination of approaches depending on the nature of the problem at hand. This explains why ATNoSFERES can outperform both ACS and XCSMH on dierent environments. But the price to pay with that richer formalism is probably a slower convergence to good solutions. However, as long as no RL mechanism is included in ATNoSFERES, a fair comparison along that line cannot be provided. We are actively working on integrating RL mechanisms into ATNoSFERES, so we hope to provide more accurate comparisons soon.

Finally, we would like to highlight the fact that the comparative studies we have carried out with ATNoSFERES in this paper were indirect. We have compared ATNoSFERES with XCSM and XCSMH on one environment and ATNoSFERES with ACS on other environments, relying on the experiments presented in the available literature. A more direct performance comparison between XCSMH and ACS on the same environments would certainly be of interest, but results with these systems have never been published yet. A lot of work deserves to be done to provide more global comparisons between several classes of systems, including LCSs. We strongly believe that such comparisons would greatly enhance the understanding of the current state of the art in LCS research and, more generally, in the evolutionary computation approach to multi-step problems in information sciences.

Fig. 1 .

 1 Fig. 1. Principles of the genetic expression used to produce the behavioral graph from the bitstring genotype. The string is rst decoded into tokens (a ), which are interpreted in a second step as instructions (b) to create nodes, edges, and labels.

Fig. 2 .

 2 Fig. 2. The sensorimotor loop with a standard LCS. The agent perceives the presence/absence (resp. 1/0) of blocks in each of the eight surrounding cells and must decide towards which of the eight adjacent cells it should move. The agent perceives HIHIHIII (starting north and rotating clockwise). Within the list of classiers characterizing it, the LCS rst selects those matching the current situation. Then, it selects one of the matching classiers and the corresponding action is performed. tions are dened by several attributes representing perceivable properties of the environment. In this context, an LCS builds classiers so as to dene the behavior of an agent as shown in gure 2.

Figures 5 (

 5 Figures 5 (a) and (b) show the performance of ATNoSFERES on this task compared with the performance of XCSM and XCSMH. Each cross in gure 5 (a) represents the performance of the best automaton obtained after 10,000 generations in one run. There are twenty crosses for each initial length. It can be seen that the performance of ATNoSFERES generally lies between the per-

Fig. 5 .

 5 Fig. 5. (a) Best average times over complete runs to reach food in Maze10 experiments as a function of the initial length of the bitstring, compared to XCSM and XCSMH performance. Since the numerical value of XCSM(H) performance was not given in publications, we have extracted it from gure 12 in [29], zooming in 16 times the (vector graphics) curves. (b) Average of the results shown in (a).

Fig. 6 .

 6 Fig. 6. E1 and E2 environments. F (food) is the goal. Capital letters marked cells represent aliased situations (identical letters imply the same perception). The remaining non-aliased marked cells are numbered so as to clarify the example given in page 27.

Fig. 7 .

 7 Fig. 7. (a) Best average times over complete runs to reach food in E1 experiments as a function of the initial length of the bitstring. (b) Average of the results shown in (a).

  110 130 150 170 190 210 230 250 270 290 fitness (10 experiments per initial length) initial length (number of codons) optimal ACS (BSmax=2 and BSmax=3) (b) average

Fig. 8 .

 8 Fig. 8. (a) Best average times over complete runs to reach food in E2 experiments as a function of the initial length of the bitstring. (b) Average of the results shown in (a).

20

 20

Fig. 9 .

 9 Fig.9. Representative evolution of the best tness in Maze10, E1, and E2 experiments as a function of generations; the shape and smoothness of the curves have been chosen as representative evolutions. The thickness of the curves (particularly manifest in Maze10 and E1) is due to the non-deterministic behavior of agents. In E1 and E2, it seems that the pressure towards deterministic behavior is stronger.

Fig. 11 .Fig. 12 .

 1112 Fig. 11. Best policy found with ATNoS-FERES in Maze10 in 10,000 generations (see gure 10 for an optimal policy). Its average number of steps to food is 5.6111.

Fig. 14 .

 14 Fig.[START_REF] Gruau | Neural Network Synthesis Using Cellular Encoding and the Genetic Algorithm[END_REF]. Best policies found with ATNoSFERES in E1 (resp. E2) in 10,000 generations, represented by the number of steps needed to reach food from each Start cell (see gure 13 for an optimal policy).

Fig. 18 .

 18 Fig. 18. Optimal policies beginning in the E1 and E2 environments presented in gure 6, page 18, on the aliased X (resp. C) cell. Edges represent transitions, labelled by the performed action. Nodes represent observations, labelled by the cell identier

  is N E = 300 * N G * 100/P R, and the average number of elementary runs N T for an environment with NS start cells (N S = 18 for Maze10, 44 for E1 and 48 for E2) is: N T = N S * N E. Thus N T gives the average number of elementary runs needed by ATNoSFERES to outperform the corresponding LCS. Finally, N T /LCS gives a good approximation of the factor by which the corresponding LCS is faster than ATNoSFERES to reach its best performance. Note that no performance comparison is given on E1 against ACS with BS max = 2 since ATNoSFERES never outperforms it.

Table 2

 2

	details the genetic

  Fig.[START_REF] Hansen | Finite Memory Control of Partially Observable Systems[END_REF]. The best automaton found with ATNoSFERES in E1 experiment (after 10,000 generations). Its average number of steps to food is about 3.4091The best automaton shown in gure 15 is representative of the best solutions found in E1 environment. We obtained similar results in previous experiments[START_REF] Landau | An Experimental Comparison between ATNoSFERES and ACS[END_REF] with a 7 bit encoding, but with a slightly better tness (about 3.3 steps to food on average, performing as well as ACS with BS max = 3).

												S	S
			fS?	N ~SW?	~NE NW?		~E? fE?	W ~N S?	W?	#?
		fS?	S!	fSE?	N! fSW?	SW! ~S?		S! ~NW? E!	W! ~NW?	NW! SE NW? S!
		S!		SE!		SW!	NW!		E!	#!	NE!
													fS?	W ~SE? ~N?	S NE? fNE?	#?
												0
													S!	NW!	W!	N!	NE!	SW!
								fN E? fSE? fNW? fNE? fSW? NE?	~SE?	fW?	#?
					0
								N!	SE!	NW!	NE!	SW!	NE!	NW!	W!	NW!
					fE?	~NW?	S SE N?		SE?	~NE NW?	~NE?	N ~SW?	#?
					E!	SE!	SE!		E!	SW!	S!	N!	NE!
			fS?		fW?		N E?		NW?	E?	#?
			S!		W!			SW!		NW!	SE!	SW!
			E									1
													#?
			E									1
													SW!
	Fig. 17. The best automaton found with ATNoSFERES in E2 experiment. Its av-
	erage number of steps to food is about 3.5833
	automaton in E2 requires more nodes than in E1. This seems to imply that
	reactive and nearly reactive behaviors perform much worse in E2 than in E1.
		S
	~N?	~NE fSW? SE S?	#?
	E!	SW!	N!	NW!
				fE S? fW?	NW ~S? S ~NW SE?	fSE? fN? ~SW N?	fNW? ~W?	E?	~NE? #?
		1
					E!	W!	NE!	SE!		N!	SE!	N!	NW!	N!	SW!	W!	S!
		fNE?
		NE!
		E
	Fig. 16. A representative good automaton found with ATNoSFERES in E1 experi-
	ment (after 10,000 generations). Its average number of steps to food is about 3.75
	In E1, 46% of the automata performing better than ACS with BS max = 1
	contained only a single node (in addition to the Start and End nodes that
	always exist in ATNoSFERES graphs), which means that a reactive behavior
	already performs well in this environment (see gure 16 for a representative
	example).
	Figure 17 gives the best automaton found in E2 environment. Representative
	best automata all have at least two internal nodes. Automata with only one
	internal node are the least ecient, but they generally perform better than
	ACS with BS max = 2 or 3. It is clear from our experiments that a good

  ).

	envir.	LCS type	perf. LCS P R(%) N G N T	NT/LCS
	Maze10	XCSM	15.1 7,000	100	8.42 45,000	6.42
	Maze10	XCSMH	6.12 6,500	7.30	4909 360.10 6	55,400
	E1	ACS (BSmax = 1)	4	4,400 30.92 5115 218.10 6	50,000