Studzinski Filipo

Perotto

Recognizing internal states of other agents to anticipate and coordinate interactions

Keywords: Factored Partially Observable Markov Decision Process (FPOMDP), Constructivist Learning Mechanisms, Anticipatory Learning, Model-Based RL

In multi-agent systems, anticipating the behavior of other agents constitutes a difficult problem. In this paper we present the case where a cognitive agent is inserted into an unknown environment composed of different kinds of other objects and agents; our cognitive agent needs to incrementally learn a model of the environment dynamics, doing it only from its interaction experience; the learned model can be then used to define a policy of actions. It is relatively easy to do so when the agent interacts with static objects, with simple mobile objects, or with trivial reactive agents; however, when the agent deals with other complex agents that may change its behaviors according to some non directly observable internal states (like emotional or intentional states), the construction of a model becomes significantly harder. The complete system can be described as a Factored and Partially Observable Markov Decision Process (FPOMDP); our agent implements the Constructivist Anticipatory Learning Mechanism (CALM) algorithm, and the experiment (called meph) shows that the induction of non-observable variables enable the agent to learn a deterministic model of most of the universe events, allowing it to anticipate other agents actions and to adapt to them, even if some interactions appear as non-deterministic in a first sight.

Introduction

Trying to escape from AI classic (and simple) maze problems toward more sophisticated (and therefore more complex and realistic) agent-based universes, we are led to consider some complicating conditions: (a) the situatedness of the agent, which is immersed into an unknown universe, interacting with it through limited sensors and effectors, without any holistic perspective of the complete environment state, and (b) without any a priori model of the world dynamics, which forces it to incrementally discover the effect of its actions on the system in an on-line experimental way; to make matters worse, the universe where the agent is immersed can be populated by different kinds of objects and entities, including (c) other complex agents, and in this case, the task of learning a predictive model becomes considerably harder.

We are especially concerned with the problem of discovering the existence of other agents' internal variables, which can be very useful to understand their behavior. Our cognitive agent needs to incrementally learn a model of its environment dynamics, and the interaction with other agents represents an important part of it. It is relatively easy to construct a model when the agent interacts with static objects, with simple mobile objects, or with trivial reactive agents; however, when dealing with other complex agents which may change its behaviors according to some non directly observable internal properties (like emotional or intentional states), the construction of a model becomes significantly harder. The difficulty increases because the reaction of each agent can appears to our agent as a non deterministic behavior, regarding the information provided by the perceptive elements of the situation.

We can anticipate at least two points of interest addressed by this paper: the first one is about concept creation, the second one is about agent inter-subjectivity. In the philosophical and psychological research community concerned with cognitive issues, the challenge of understanding the capability to develop new abstract concepts have always been a central point in most theories about how the human being can deal and adapt itself to a so complex and dynamical environment as the real world [START_REF] Murphy | The big book of concepts[END_REF], [START_REF] Piaget | [END_REF]. In contrast to the kind of approach usually adopted in AI, which easily slip into the strategy of treating exceptions and lack of information by using probabilistic methods, many cognitive scientists insist that the human mind strategy looks more like accommodating the disturbing events observed in the reality by improving his/her model with new levels of abstraction, new representation elements, and new concepts. Moreover, the intricate problem of dealing with other complex agents has also been studied by cognitive science for some time, from psychology to neuroscience. A classical approach to it is the famous "ToM" assumption (Astington, et al. 1988), [START_REF] Bateson | Steps to an Ecology of Mind: Collected Essays in Anthropology, Psychiatry, Evolution, and Epistemology[END_REF], [START_REF] Dennett | The Intentional Stance[END_REF] which claims that the human being have developed the capability to attribute mental states to the others, in order to represent their beliefs, desires and intentions, and so being able to understand their behavior.

In this paper, we use the Constructivist Anticipatory Learning Mechanism (CALM), defined in [START_REF] Perotto | Un Mécanisme Constructiviste d'Apprentissage Automatique d'Anticipations pour des Agents Artificiels Situés[END_REF], to solve the "meph problem", where a cognitive agent is inserted into an environment constituted of other objects and also of some other agents, that are non-cognitive in the sense that they do not learn anything, but that are similar to our agent in terms of structure and possible behaviors. CALM is able to build a descriptive model of the system where the agent is immersed, inducting, from the experience, the structure of a factored and partially observable Markov decision process (FPOMDP). Some positive results have been achieved due to the use of 4 integrated strategies [START_REF] Perotto | Un Mécanisme Constructiviste d'Apprentissage Automatique d'Anticipations pour des Agents Artificiels Situés[END_REF], (Perotto et al. 2007), [START_REF] Perotto | Un Mécanisme Constructiviste d'Apprentissage Automatique d'Anticipations pour des Agents Artificiels Situés[END_REF]Alvares, 2007): (a) the mechanism takes advantage of the situated condition presented by the agent, constructing a description of the system regularities relatively to its own point of view, which allows to set a good behavior policy without the necessity of "mapping" the entire environment; (b) the learning process is anchored on the construction of an anticipatory model of the world, what could be more efficient and more powerful than traditional "model free" reinforcement learning methods, that directly learn a policy; (c) the mechanism uses some heuristics designed to well structured universes, where conditional dependencies between variables exist in a limited scale, and where most of the phenomena can be described in a deterministic way, even if the system as a whole is not, representing what we call a partially deterministic environment; this characteristic seems to be widely common in real world problems; (d) the mechanism is prepared to discover the existence of hidden or non-observable properties of the universe, which cannot be directly perceived by the agent sensors, but that can explain some observed phenomena. This last characteristic is fundamental to solve the problem presented in this article because it enables our agent to discover the existence of internal states in other agents, which is necessary to understand their behavior and then to anticipate it. Further discussion about situatedness can be found in [START_REF] Wilson | How to Situate Cognition: Letting Nature Take its Course[END_REF][START_REF] Wilson | How to Situate Cognition: Letting Nature Take its Course[END_REF], [START_REF] Beer | A dynamical systems perspective on agent-environment interactions[END_REF], and [START_REF] Suchman | Plans and Situated Actions[END_REF].

Thus, the basic idea concerning this paper is to describe the algorithm CALM, proposed in [START_REF] Perotto | Un Mécanisme Constructiviste d'Apprentissage Automatique d'Anticipations pour des Agents Artificiels Situés[END_REF], presenting its features, and placing it into the Markov Decision Process (MDP) framework panorama. The discussion is supported, on one side, by these introductory philosophical conjectures, and on the other side, by the meph experiment, which creates a multi-agent scenario, where our agent needs to induce the existence of internal variables to the other agents. In this way, the paper presents some positive results in both theoretical and practical aspects. Following the paper, section 2 overviews the MDP framework, section 3 describes the CALM learning mechanism, section 4 introduces the experiment and shows the acquired results, and section 5 concludes the paper, arguing that the discover and induction of hidden properties of the system can be a promising strategy to model other agents internal states.

Markov Decision Process Framework

Markov Decision Process (MDP) and its extensions constitute a quite popular framework, largely used for modeling decision-making and planning problems. An MDP is typically represented as a discrete stochastic state machine; at each time cycle the machine is in some state s; the agent interacts with the process by choosing some action a to carry out; then, the machine changes into a new state s', and gives the agent a corresponding reward r; a given transition function δ defines the way the machine changes according to s and a. Solving an MDP is finding the optimal (or near-optimal) policy of actions in order to maximize the rewards received by the agent over time. When the MDP parameters are completely known, including the reward and the transition functions, it can be mathematically solved by dynamic programming (DP) methods. When these functions are unknown, the MDP can be solved by reinforcement learning (RL) methods, designed to learn a policy of actions on-line, i.e. at the same time the agent interacts with the system, by incrementally estimating the utility of state-actions pairs and then by mapping situations to actions [START_REF] Sutton | Reinforcement Learning: an introduction[END_REF].

The Classic MDP

Markov Decision Process first appeared (in the form we know) in the late 1950s [START_REF] Bellman | A Markovian Decision Process[END_REF], [START_REF] Howard | Dynamic Programming and Markov Processes[END_REF], reaching a concrete popularity in the Artificial Intelligence (AI) research community from the 1990s [START_REF] Puterman | Markov Decision Processes: discrete stochastic dynamic programming[END_REF]. Currently the MDP framework is widely used in the domains of Automated Control, Decision-Theoretic Planning [START_REF] Blythe | Decision-Theoretic Planning[END_REF], and Reinforcement Learning [START_REF] Feinberg | Handbook of Markov Decision Processes: methods and applications[END_REF]. A "standard MDP" represents a system through the discretization and enumeration of its state space, similar to a state machine in which the transition function can be non-deterministic. The flow of an MDP (the transition between states) depends only on the system current state and on the action taken by the agent at the time. After acting, the agent receives a reward signal, which can be positive or negative if certain particular transitions occur.

However, for a wide range of complex (including real world) problems, the complete information about the exact state of the environment is not available. This kind of problem is often represented as a Partially Observable Markov Decision Process (POMDP) [START_REF] Kaelbling | Planning and acting in partially observable stochastic domains[END_REF]. The idea of representing non-observable elements in a MDP is not new [START_REF] Astrom | Optimal Control of Markov Decision Processes with Incomplete State Estimation[END_REF], [START_REF] Smallwood | The optimal control of partially observable Markov decision processes over a finite horizon[END_REF][START_REF] Smallwood | The optimal control of partially observable Markov decision processes over a finite horizon[END_REF], but became popular with the revived interest on the framework, occurred in the 1990s (Christman, 1992), [START_REF] Kaelbling | Acting optimally in partially observable stochastic domains[END_REF][START_REF] Kaelbling | Planning and acting in partially observable stochastic domains[END_REF]. The POMDP provides an elegant mathematical framework for modeling complex decision and planning problems in stochastic domains in which the system states are observable only indirectly, via a set of imperfect, incomplete or noisy perceptions. In a POMDP, the set of observations is different from the set of states, but related to them by an observation function, i.e. the underlying system state s cannot be directly perceived by the agent, which has access only to an observation o. The POMDP is more powerful than the MDP in terms of modeling (i.e. a larger set of problems can be described by a POMDP than by an MDP), but the methods for solving them are computationally even more expensive, and thus applicable in practice only to very simple problems [START_REF] Hauskrecht | Value-function approximations for partially observable Markov decision processes[END_REF], [START_REF] Meuleau | Solving POMDPs by Searching the Space of Finite Policies[END_REF], [START_REF] Shani | Model-Based Online Learning of POMDPs[END_REF].

The main bottleneck about the use of MDPs or POMDPs is that representing complex problems implies that the state space grows-up and quickly becomes intractable. Real-world problems are generally complex, but fortunately, most of them are quite well-structured. Many large MDPs have significant internal structure, and can be modeled compactly if the structure is exploited in the representation. The factorization of states is an approach to exploit this characteristic. In the factored representation, a state is implicitly described by an assignment to some set of state variables. Thus, the complete state space enumeration is avoided, and the system can be described referring directly to its properties. The factorization of states enable to represent the system in a very compact way, even if the corresponding MDP is exponentially large [START_REF] Guestrin | Efficient Solution Algorithms for Factored MDPs[END_REF], [START_REF] Shani | Efficient ADD Operations for Point-Based Algorithms[END_REF]. When the structure of the Factored Markov Decision Process (FMDP) [START_REF] Boutilier | Stochastic dynamic programming with factored representations[END_REF] is completely described, some known algorithms can be applied to find good policies in a quite efficient way [START_REF] Guestrin | Efficient Solution Algorithms for Factored MDPs[END_REF]. However, the research concerning the discover of the structure of an underlying system from incomplete observation is still incipient [START_REF] Degris | Learning the Structure of Factored Markov Decision Processes in Reinforcement Learning Problems[END_REF], [START_REF] Degris | Factored Markov Decision Processes[END_REF].

Factored and Partially Observable MDP

In order to increase the range of representable problems, the classic MDP model can be extended to include factorization of states and partial observation, and it can be so called a Factored Partially Observable Markov Decision Process (FPOMDP). In order to be factored, the description of a given state s in the original model will be decomposed and replaced by a set {x1, x2, ... xn} in the extended model; the action a becomes a set {c1, c2, ... cm}; the reward signal r becomes {r1, r2, ... rk}; and the transition function δ is replaced by a set of transformation functions {T1, T2, ... Tn}.

A FPOMDP (Degris;[START_REF] Degris | Factored Markov Decision Processes[END_REF] can be formally defined as a 4-tuple {X, C, R, T}. The finite non-empty set of system properties or variables X = {X1, X2, ... Xn} is divided into two subsets, X = P È H, where the subset P represents the observable properties (those that can be accessed through the agent sensory perception), and the subset H represents the hidden or non-observable properties; each property Xi is associated to a specified domain, which defines the values the property can assume. C = {C1, C2, ... Cm} represents the controllable variables, composing the agent actions, R = {R1, R2, ... Rk} is the set of (factored) reward functions, in the form Ri : Pi  IR, and T = {T1, T2, ... Tn} is the set of transformation functions, as Ti : X  C  Xi , defining the system dynamics. Each transformation function can be represented as a Dynamic Bayesien Network (DBN) [START_REF] Dean | A model for reasoning about persistence and causation[END_REF][START_REF] Dean | A model for reasoning about persistence and causation[END_REF], which is an acyclic, oriented, two-layers graph. The first layer nodes represent the environment state in time t, and the second layer nodes represent the next state, in t+1 [START_REF] Boutilier | Stochastic dynamic programming with factored representations[END_REF]. A stationary policy π is a mapping X → C where π(x) defines the action to be taken in a given situation. The agent must learn a policy that optimizes the cumulative rewards received over a potentially infinite time horizon. Typically, the solution π* is the policy that maximizes the expected discounted reward sum, as indicated in the classical Bellman optimality equation (1957), here adapted to our FPOMDP notation.

V π* (x) = R(x) + maxc [ γ . Σx' P(x' | x, c) . V π* (x') ]
In this paper, we consider the case where the agent does not have an a priori model of the universe where it is situated (i.e. it does not have any idea about the transformation function), and this condition forces it to be endowed with some capacity of learning, in order to be able to adapt itself to the system. Even if there is a large research community studying model-free methods (that directly learn a policy of actions), in this work we adopt a model-based method, through which the agent must learn a descriptive and predictive model of the world, and so define a behavior strategy based on it. Learning a predictive model is often referred as learning the structure of the problem, which is an important research objective into the MDP framework community [START_REF] Degris | Learning the Structure of Factored Markov Decision Processes in Reinforcement Learning Problems[END_REF], as well as in related approaches like Induction of Decision Trees or Decision Graphs [START_REF] Jensen | Bayesian Networks and Decision Graphs[END_REF][START_REF] Jensen | Bayesian Networks and Decision Graphs[END_REF], Bayesian Networks (BN) [START_REF] Pearl | Causality: models of reasoning and inference[END_REF], [START_REF] Friedman | Being Bayesian about Network Structure: a bayesian approach to structure discovery in bayesian networks[END_REF]Koller, 2003) and Influence Diagrams [START_REF] Howard | Dynamic Programming and Markov Processes[END_REF][START_REF] Howard | Influence Diagrams[END_REF].

In this way, when the agent is immersed in a system represented as a FPOMDP, the complete task for its anticipatory learning mechanism is both to create a model of the transformation function, and to define an optimal (or sufficiently good) policy of actions. The transformation function can be described by a dynamic bayesian network, i.e. an acyclic, oriented, two-layers graph, where the first layer nodes represent the environment situation in time t, and the second layer nodes represent the next situation, in time t+1. A policy π : X → C defines the behavior to be taken in each given situation (the policy of actions). Several algorithms create stochastic policies, and in this case the action to take is defined by a probability. [START_REF] Degris | Factored Markov Decision Processes[END_REF] present a good overview of the use of this representation in artificial intelligence, referring several related algorithms designed to learn and solve factored FMDPs and FPOMDPs, including both the algorithms designed to calculate the policy given the model [START_REF] Boutilier | Stochastic dynamic programming with factored representations[END_REF], (Boutilier;[START_REF] Boutilier | Computing optimal policies for partially observable decision processes using compact representations[END_REF], [START_REF] Hansen | Dynamic programming for POMDPs using a factored state representation[END_REF][START_REF] Hansen | Dynamic programming for POMDPs using a factored state representation[END_REF], (Poupart;[START_REF] Poupart | VDCBPI: an approximate scalable algorithm for large scale POMDPs[END_REF], [START_REF] Hoey | SPUDD: Stochastic Planning Using Decision Diagrams[END_REF], [START_REF] St-Aubin | APRICODD: Approximate policy construction using decision diagrams[END_REF], [START_REF] Guestrin | Solving Factored POMDPs with Linear Value Functions[END_REF], [START_REF] Sim | Symbolic Heuristic Search Value Iteration for Factored POMDPs[END_REF], and [START_REF] Shani | Efficient ADD Operations for Point-Based Algorithms[END_REF] and the algorithms designed to discover the structure of the system [START_REF] Degris | Learning the Structure of Factored Markov Decision Processes in Reinforcement Learning Problems[END_REF], (Degris;[START_REF] Degris | Factored Markov Decision Processes[END_REF], [START_REF] Strehl | Efficient Structure Learning in Factored-State MDPs[END_REF], and [START_REF] Jonsson | A Causal Approach to Hierarchical Decomposition of Factored MDPs[END_REF][START_REF] Jonsson | A Causal Approach to Hierarchical Decomposition of Factored MDPs[END_REF].

Constructivist Anticipatory Learning Mechanism

The constructivist anticipatory learning mechanism (CALM), detailedly described in [START_REF] Perotto | Un Mécanisme Constructiviste d'Apprentissage Automatique d'Anticipations pour des Agents Artificiels Situés[END_REF], is a mechanism developed to enable an agent to learn the structure of an unknown environment where it is situated, trough observation and experimentation, creating an anticipatory model of the world, which will be represented as an FPOMDP. CALM operates the learning process in an active and incremental way, where the agent needs to choose between alternative actions, and learn the world model as well as the policy at the same time it actuates. There is no separated previous training time; the agent has an unique uninterrupted interactive experience into the system, quite similarly to real life problems. In other words, it must performing and learning at the same time.

The problem can be divided into two tasks: first, building a world model, i.e. to induce a structure which represents the dynamics of the system (composed by agent-environment interactions). Second, to establish a behavioral policy, i.e. to define the actions to do at each possible different state of the system, in order to increase the estimated rewards received over time.

The task becomes harder because the environment is only partially observable, from the point of view of the agent, constituting an FPOMDP. In this case, the agent has perceptive information from a subset of sensory variables, but the system dynamics depends also on another subset of hidden variables. To be able to create the world model, the agent needs, beyond discover the regularities of the phenomena, also discover the existence of non-observable variables that are important to understand the system evolution. In other words, learning a model of the world is more than describing the environment dynamics (the rules that can explain and anticipate the observed transformations), it is also discovering the existence of hidden properties (once they influence the evolution of the observable ones), and finally find a way to deduce the values of these hidden properties.

If the agent can successfully discover and describe the hidden properties of the FPOMDP which it is dealing with, then the world becomes treatable as a FMDP, and there are some known algorithms able to efficiently calculate the optimal (or near-optimal) policy. The algorithm to calculate the policy of actions used by CALM is similar to the one presented by [START_REF] Degris | Learning the Structure of Factored Markov Decision Processes in Reinforcement Learning Problems[END_REF]. On the other hand, the main challenge is to discover the structure of the problem based on the on-line observation, and CALM do it using representations and strategies inspired on (Drescher, 1993).

Knowledge Representation

CALM tries to reconstruct, by experience, each system transformation function Ti, representing it by an anticipation tree, which in turn is composed by schemas. Each schema represent some perceived regularity occurring in the environment, i.e. some regular event checked by the agent during its interaction with the world. A schema is composed by three vectors:  = (context  action → expectation). The context vector has each of their elements linked with a sensor. The action vector is linked with the effectors. The expectation represents the value expected for some specific sensor in the next time. In a specific schema, the context vector represents the set of equivalent situations where the schema is applicable. The action vector represents a set of similar actions that the agent can carry out in the environment. The expectation vector represents the expected result after executing the given action in the given context. Each element vector can assume any value in a discrete interval defined by the respective sensor or effector. In addition, the context vector can incorporate some "synthetic elements" not linked to any sensor but representing abstract or non-sensory properties which the existence is induced by the mechanism. Some elements in these vectors can undertake an "undefined value". For example, an element linked with a binary sensor must have one of three values: true, false or undefined (represented, respectively, by '1', '0' and '#'). In both the context and action vectors, '#' represents something ignored, not relevant to make the anticipations. There is compatibility between a schema and a certain situation when the schema's context vector has all defined elements equal to those of the agent's perception.

In the expectation vector, '#' means that the element is not deterministically predictable. The undefined value generalizes the schema because it allows to ignore some properties to represent a set of situations. Another symbols can be used to represent some special situations, in a way to reduce the number of schemas; it is the case of the symbol '=', used to indicate that the value of the expected element does not change in the specified context.

The use of undefined values makes possible the construction of an anticipation tree. Each node in that tree is a schema, and relations of generalization and specialization guide its topology (quite similar to decision trees or discrimination trees). The root node represents the most generalized situation, which has the context and action vectors completely undefined. Adding one level in the tree is to specialize one generalized element, creating a branch where the undefined value is replaced by the different possible defined values. This specialization occurs either in the context vector or in the action vector. In this way, CALM divides the state space according to the different expectations of changing, grouping contexts and actions with its respective transformations. The tree evolves during the agent's life, and it is used by the agent, even if until under construction, to take its decisions, and in consequence, to define its behavior. The structure of the schemas and an example of their organization as an anticipation tree are presented in Figure 1.

### # ### ### 0 #0# ### 1 111 0## 0 000 1## 0 10# context action expectation
Figure 1: the anticipation tree; each node is a schema composed of three vectors: context, action and expectation; the leaf nodes are decider schemas.

The context in which the agent is at a given moment (perceived through its sensors) is applied in the tree, exciting all the schemas that have a compatible context vector. This process defines a set of excited schemas, each one suggesting a different action to do in the given situation. CALM will choose one to activate, performing the defined action through the agent's effectors. The algorithm always chooses the compatible schema that has the most specific context, called decider schema, which is the leaf of a differentiated branch. This decision is taken based on the calculated utility of each possible choice. There are two kinds of utility: the first one estimates the discounted sum of rewards in the future following the policy, the second one measures the exploration benefits. The utility value used to take the decision depends on the circumstantial agent strategy (exploiting or exploring). The mechanism has also a kind of generalized episodic memory, which represents (in a compact form) the specific and real situations experimented in the past, preserving the necessary information to correctly constructs the tree. The implementation of a feasible generalized episodic memory is not evident; it can be very expensive to remember episodes. However, with some strong but well chosen restrictions (like limiting dependency representation) it can be computationally viable.

Anticipation Tree Construction Methods

The learning process happens through the refinement of the set of schemas. The agent becomes more adapted to its environment as a consequence of that. After each experienced situation, CALM checks if the result (context perceived at the instant following the action) is in conformity to the expectation of the activated schema. If the anticipation fails, the error between the result and the expectation serves as parameter to correct the model. In the schematic tree topology, the context and action vectors are taken together. This concatenated vector identifies the node in the tree, which grows up using a top-down strategy. The context and action vectors are gradually specialized by differentiation, adding, each time, a new relevant feature to identify the category of the situation. In general there is a shorter way starting with an empty vector and searching for the probably few relevant features than starting with a full vector and having to waste energy eliminating a lot of useless elements. Selecting the good set of relevant features to represent some given concept is a well known problem in AI, and the solution is not easy, even by approximated approaches. To do it, CALM adopts a forward greedy selection [START_REF] Blum | Selection of relevant features and examples in machine learning[END_REF], using the data registered in the generalized episodic memory.

The expectation vector can be seen as a label in each decider schema, and it represents the predicted anticipation when the decider is activated. The evolution of expectations in the tree uses a bottom-up strategy. Initially all different expectations are considered as different classes, and they are gradually generalized and integrated with others. The agent has two alternatives when the expectation fails. In a way to make the knowledge compatible with the experience, the first alternative is to try to divide the scope of the schema, creating new schemas, with more specialized contexts. Sometimes it is not possible and then it reduces the schema expectation.

Three basic methods compose the CALM learning function, namely: differentiation, adjustment, and integration. Differentiation is a necessary mechanism because a schema responsible for a context too general can hardly make precise anticipations. If a general schema does not work well, the mechanism divides it into new schemas, differentiating them by some element of the context or action vector. In fact, the differentiation method takes an unstable decider schema and changes it into a two level sub-tree. The parent schema in this sub-tree preserves the context of the original schema. The children, which are the new decider schemas, have their context vectors a little bit more specialized than their parent. They attribute a value to some undefined element, dividing the scope of the original schema. Each one of these new deciders engages itself in a part of the domain. In this way, the previous correct knowledge remains preserved, distributed in the new schemas, and the discordant situation is isolated and treated only in its specific context. Differentiation is the method responsible to make the anticipation tree grows up. Each level of the tree represents the introduction of some new constraint. The algorithm needs to choose what will be the differentiator element, and it could be from either the context vector or the action vector. This differentiator needs to separate the situation responsible for the disequilibrium from the others, and the algorithm chooses it by calculating the information gain, and considering a limited (parametrized) range of interdependencies between variables. Figure 2 When some schema fails and it is not possible to differentiate it in any way, then CALM executes the adjustment method. This method reduces the expectations of an unstable decider schema in order to make it reliable again. The algorithm simply compares the activated schema's expectation and the real result perceived by the agent after the application of the schema, setting the incompatible expectation elements to the undefined value ('#'). The adjustment method changes the schema expectation (and consequently the anticipation predicted by the schema). Successive adjustments can reveal some unnecessary differentiations. Figure 3 In this way, the schema expectation can change (and consequently the class of the situation represented by the schema), and the tree maintenance mechanism needs to be able to reorganize the tree when this change occurs. Therefore, successive adjustments in the expectations of various schemas can reveal unnecessary differentiations. When CALM finds a group of schemas with similar expectations to approach different contexts, the integration method comes into action, trying to join these schemas by searching for some unnecessary common differentiator element, and eliminating it. The method operates as shown in figure 4.

### A 0#0 0## A 0#0 1## A 0#0 (b) (a) ### A 0#0

Dealing with the Unobservable

When CALM reduces the expectation of a given schema by adjustment, it supposes that there is no deterministic regularity following the represented situation in relation to these incoherent elements, and the related transformation is unpredictable. However, sometimes a prediction error could be explained by considering the existence of some abstract or hidden property in the environment, which could be useful to differentiate an ambiguous situation, but which is not directly perceived by the agent sensors. So, before adjusting, CALM supposes the existence of a non-sensory property in the environment, which will be represented as a synthetic element. When a new synthetic element is created, it is included as a new term in the context and expectation vectors of the schemas. Synthetic elements suppose the existence of something beyond the sensory perception, which can be useful to explain non-equilibrated situations. They have the function of amplifying the differentiation possibilities.

In this way, when dealing with partially observable environments, CALM has two additional challenges: (a) inferring the existence of unobservable properties, which it will represent by synthetic elements, and (b) including these new elements into its predictive model. A good strategy to do this task is looking at the historical information. In the case where the POMDP is completely deterministic, it is possible to find sufficient little pieces of history to distinguish and identify all the underlying states [START_REF] Holmes | Looping Suffix Tree-Based Inference of Partially Observable Hidden State[END_REF][START_REF] Holmes | Looping Suffix Tree-Based Inference of Partially Observable Hidden State[END_REF], and we suppose that it is similar when the POMDP in non-deterministic but well structured.

CALM introduces a method called abstract differentiation. When a schema fails in its prediction, and when it is not possible to differentiate it by the current set of considered properties, then a new boolean synthetic element is created, enlarging the context and expectation vectors. Immediately, this element is used to differentiate the incoherent situation from the others. The method attributes arbitrary values to this element in each differentiated schema. These values represent the presence or absence of some non-observable condition, necessary to determine the correct prediction in the given situation. The method is illustrated in figure 5, where the new elements are represented by card suites. Once a synthetic element is created, it can be used in next differentiations. A new synthetic element will be created only if the existing ones are already saturated. To avoid the problem of creating infinite new synthetic elements, CALM can do it only until a determined limit, after which it considers that the problematic anticipation is not deterministically predictable, undefining the expectation in the related schemas by adjustment. Figure 6 explains didactically the idea behind synthetic element creation. The synthetic element is not associated to any sensory perception. Consequently, its value cannot be observed. This fact can place the agent in ambiguous situations, where it does not know whether some relevant but not observable condition (represented by this element) is present or absent. Initially, the value of a synthetic element is verified a posteriori (i.e. after the execution of the action in an ambiguous situation). Once the action is executed and the following result is verified, then the agent can rewind and deduce what was the situation really faced in the past instant (disambiguated). Discovering the value of a synthetic element after the circumstance where this information was needed can seem useless, but in fact, this delayed deduction gives information to another method called abstract anticipation. If the nonobservable property represented by this synthetic element has a regular dynamics, then the mechanism can propagate the deduced value back to the schema activated in the immediate previous instant. The deduced synthetic element value will be included as a new anticipation in the previous activated schema. Figure 7 shows how this new element can be included in the predictive model. For example, in time t1 CALM activates the schema 1 = (#0 + c → #1), where the context and expectation are composed by two elements (the first one synthetic and the second one perceptive), and one action. Suppose that the next situation '#1' is ambiguous, because it excites both schemas 2 = (♣1 + c → #0) and 3 = (♦1 + c → #1). At this time, the mechanism cannot know the synthetic element value, crucial to determine what is the real situation. Suppose that, anyway, the mechanism decides to execute the action 'c' in time t2, and it is followed by the sensory perception '0' in t3. Now, in t3, the agent can deduce that the situation really dealt with in t2 was '♣1', and it can include this information into the schema activated in t1, in the form 1 = (#0 + c → ♣1).

Experiment

The CALM mechanism has already been used to successfully solve problems such as flip, which is also used by [START_REF] Singh | Learning Predictive State Representations[END_REF] and [START_REF] Holmes | Looping Suffix Tree-Based Inference of Partially Observable Hidden State[END_REF][START_REF] Holmes | Looping Suffix Tree-Based Inference of Partially Observable Hidden State[END_REF], and wepp, which is an interesting RL situated problem. CALM is able to solve both of them by creating new synthetic elements to represent underlying states of the problem [START_REF] Perotto | Un Mécanisme Constructiviste d'Apprentissage Automatique d'Anticipations pour des Agents Artificiels Situés[END_REF], [START_REF] Perotto | Un Mécanisme Constructiviste d'Apprentissage Automatique d'Anticipations pour des Agents Artificiels Situés[END_REF]Álvares, 2007), (Perotto et al., 2007). In this paper, we

♣ 0 c (100%) ♣ 0 1 c (100%) (100%) ♦ 0 ♦ 0 (b) (a) 0 c 1 0 c 1 c t 0 t 1 t 2 t 3 1 c ♣ ♦ 0 1 0 c (50%) (50%) (b) (c) 0 1 0 c (100%) (100%) p 0 c h 0 c 0 (a) 0 c (100%) c 1 t 0 t 1 t 2
introduce an experiment that we call meph (acronym to the actions that the agent can do: move, eat, play, hit).

In the meph experiment, the agent is inserted into a bi-dimensional environment (like a "grid") where it should learn how to interact with other agents and objects that can be found during its life. Our agent needs to create a policy of actions in a way to optimize its feelings (internal rewards). When it is hungry, it feels good by eating some food (which is an object that can be sometimes found in the environment, among other non eatable objects like stones). Agents and objects can be differentiated by observable features, it means that our agent can sensorially distinguish what is the "thing" with which it is interacting. However, both food and stone have the same appearance, and in this way, to discover if the object is either food or stone, the agent needs to experiment, it means, the agent needs to explicitly experiment the environment in order to take more information about the situation, for example, hitting the object to listen what sound it makes. Figure 8 shows a random configuration of the environment. When our agent is excited, it founds pleasure by playing with another agent. However, the other agents also have internal emotional states; when another agent is angry, any tentative to play with results in an aggression, which causes a disagreeable painful sensation to our agent. Playing is enjoyable and safe only if both agents are excited, or at least if the other agent is not angry (and then, not aggressive), but these emotional states are internal to each agent, and cannot be directly perceived. With such configuration, our agent will need to create new synthetic elements to be able to distinguish what is food and what is stone, and to distinguish who are aggressive and who are peaceable.

At each time step, our agent can execute one of 4 actions: move, eat, play or hit. Moving itself is a good strategy to scape from other aggressive agents, but it is also the action that changes the context, allowing the agent to search for different contexts. The agent does not control precisely the movement it does; the action of moving itself causes a random rotation followed by a position changing to an adjacent cell. Eating is the good choice when the agent is hungry and it is in front of some food at the same time, action that ceases the bad sensation caused by hungry. Playing is the good action to be carried out when the agent is excited and in frontal contact with another non-aggressive agent. Hitting is the action that serves to interacting with other objects without compromise; doing it, the agent is able to identify the solution to some ambiguous situations; for example, hitting a stone has no effect, while hitting food provokes a funny sound. The same for another agents, that reacts with a noisy sound when hit, but only if it is already angry.

The agent has two limited external perceptions, both focused on the cell that is directly in front of it; the sense of vision allows it to see if the place before him contains an object, an agent, or nothing; the sense of hearing permits to listen the sounds coming from there. The agent's body has 5 internal properties, corresponding to 5 equivalent internal perceptions: pain, anger, hungry, excitation, and pleasure. Pleasure occurs always when the agent plays with another agent, independently of the other agent internal state (which is quite selfish). However, as we know, our agent can get punched if the other agent is angry, and in this case pain takes place. When our agent feels pain and hungry at the same time, it becomes angry too. Initially the agent does not know anything about the environment or about its own sensations. It does not distinguish the situations, and also does not know what consequences its actions imply.

The problem becomes interesting because playing can provoke both positive and negative rewards, the same for eating, that is an interesting behavior only in certain situations; it depends on the context where the action is executed, which is not fully observable by sensors. This is the model that CALM needs to learn by itself before establish the behavior policy. Figure 9 shows the involved variables, which will compose the schemas' identifying vectors. Figures 10 to 17 shows the anticipation trees created by the mechanism after stabilization.

Figure 9: the vectors that compose the context of a schema; synthetic properties, perceptive properties, and controllable properties (actions).

Figure 10: anticipation tree for hearing; the only action that provokes sound is hitting, it is true only if the object is food or the agent is hungry; when the agent hits (H) an object that is food or a non-aggressive agent, differentiated of their confounding pairs by the synthetic element (♣), then the agent listens a sound in the next instant; if the action is other (*) than hitting, then no sound is produced.

Figure 11: anticipation tree for vision; when the agent hits (H) another agent (A), it verifies the permanence of this other agent in its visual field, which means that hitting an agent makes it stay in the same place; however, no other actions (*) executed in front of an agent (A) can prevents it to go, and so the prediction is undefined (#); the same for moving itself (M), which causes a situation changing and the non predictability of the visual field for the next instant; in all of the other cases the vision stays unchanged.

Figure 12: anticipation tree for pain; the agent knows that playing (P) with an aggressive (♣) agent (A) causes pain; otherwise, no pain is caused.

Figure 13: anticipation tree for pleasure; playing with a peaceable (♦) agent (A) is pleasant, and it is the only known way to reach this feeling.

1

♣ # # # # # # # H 0 ♦ # # # # # # # H 0 ♣ # # # # # # # * # # # # # # # # H h a h e p p v h c h a h e p p v h c 1 ♣ # # # # # A # P 0 * # # # # # * # * h a h e p p v h c 1 ♦ # # # # # A # P 0 * # # # # # * # * h a h e p p v h c # # 0 0 # # # # # # 0 # * * # # # # # # h a h e p p v h c # # # # # # # A # * # # # # # # # * # M = # # # # # # * # * # # # # # # * # # A # # # # # # A # H # # # # # # A # #
h a h e p p v h c hearing vision pain pleasure excitation hungry anger action hidden Figure 14: anticipation tree for excitation; when the agent feels neither anger (0) nor hungry (0), it can (eventually) becomes excited; it happens in a non-deterministic way, and for this reason the prediction is undefined in this case (#), which can be understood as a possibility; otherwise (**) excitation will be certainly absent.

Figure 15: anticipation tree for hungry; eating (E) food (O♣) ceases hungry; otherwise, if the agent is already hungry, it will remains, but if it is not yet hungry, it can become.

Figure 16: anticipation tree for anger; if neither pain nor hungry, then anger turns off; if both pain and hungry, then anger turns on; otherwise, anger does not change its state.

Figure 17: hidden element anticipation tree; this element allows identifying whether an object is food or stone, and whether an agent is angry or not; CALM abstract anticipation method allows modeling the dynamics of this variable, even if t is not directly observable by direct sensory perception; the perception of the noise (1) is the result that enables the discovering of the value of this hidden property; the visual perception of an object (O), or the fact of hitting (H) another agent (A), also permit to know that the hidden element does not change.

Figure 18 shows the evolution of the mean reward comparing the CALM solution with a random agent, and with two classic Q-Learning [START_REF] Watkins | Q-learning[END_REF]Dyan, 1992) implementations: the first one non situated (the agent has the vision of the entire environment as flat state space), and the second one with equivalent (situated) inputs than CALM. The non-situated implementation of Q-Learning algorithm (Classic Q) takes much more time to start drawing a convergence curve than the others, and in fact, the expected solution will never be reached; it is due to the fact that Q-Learning tries to construct directly a mapping from states to actions (a policy), but the state space is taken as the combination of the state variables; in this implementation (because it is not situated) each of the cells in the environment compose a different variable, and then the problem becomes quickly big; by the same cause, the agent becomes vulnerable to the growing of the board (the grid dimensions imply directly in the complexity of the problem).

# # 1 # # 1 # # # 0 # # 0 # # 0 # # # = # # * # # * # # # = # # # # # # A # T # # # # # # # A # * # # # # # # # O # M # # # # # # A # # h a h e p p v h c = # # # # # # O # * # # # # # # O # # # # # # # # # N # # ♦ # # # # # # * 0 # ♣ # # # # # # * 1 #
The CALM solution converges much earlier than Q-Learning, even taken in its situated version, and CALM found a better solution also; it is due to the fact that CALM quickly constructs a model to predict the environment dynamics, including the non-observable properties in the model, and so it is able to define a good policy sooner. The "pause" in the convergence that can be seen in the graphic indicates two moments: first, the solution found before correctly modeling the hidden properties as synthetic elements, and then, the solution after having it. On the other side, Q-Learning stays attached to a probabilistic model, and in this case, without the information about the internal states of the other agents, trying to play with them becomes unsafe, and the Q-Learning solution will prefer do not do it.

Conclusions

The CALM mechanism, presented in [START_REF] Perotto | Un Mécanisme Constructiviste d'Apprentissage Automatique d'Anticipations pour des Agents Artificiels Situés[END_REF], can provide autonomous adaptive capability to an agent, because it is able to incrementally construct knowledge to represent the deterministic regularities observed during its interaction with the system, even in partially deterministic and partially observable environments. CALM can deal with the incomplete observation trough the induction and prediction of hidden properties, represented by synthetic elements, thus it is able to overpass the limit of sensory perception, constructing more abstract terms to represent the system, and to describe its dynamics in more complex levels. CALM can be very efficient to construct a model in non-deterministic environments if they are well structured. In other words, if the most part of transformations are in fact deterministic relatively to the underlying partially observable properties, and if the interdependence between variables are limited to a small range. Several problems found in the real world present these characteristics.

The proposed experiment (meph) can be taken as an useful problem that, even if simple, challenges the agent to solve some intricate issues such as the interaction with other complex agents. The next step in this way is to insert several cognitive agents like CALM in the same scenario; it means, agents that change our own internal model and policy of action, and in this way, present a non-stationary behavior. Again, the difficulty for one agent model the other agents in this kind of condition is even harder.

Finally, we believe that the same strategy can be adapted to several kinds of classification tasks, where a previous database of samples are available. In this case, the algorithm learns to classify new instances based on a model created from a training set of instances that have been properly labeled with the correct classes. This task is similar to several real world problems actually solved with the computer aim, such as e-mail filtering, diagnostic systems, recommendation systems, decision support systems, and so on.

Figure 2 .

 2 Figure 2. Differentiation method; (a) experimented situation and action; (b) activated schema; (c) real observed result; (d) sub-tree generated by differentiation.

Figure 3 .

 3 Figure 3. Adjust method; (a) experimented situation and action; (b) activated schema; (c) real observed result; (d) schema expectation reduction after adjust.

Figure 4 .

 4 Figure 4. Integration method; (a) sub-tree after some adjust; (b) an integrated schema substitutes the sub-tree.

Figure 5 .

 5 Figure 5. Synthetic element creation method; (d) incremented context and expectation vectors, and differentiation using synthetic element.

Figure 6 :

 6 Figure 6: discovering the existence of non observable properties; in (a) a real experienced sequence; in (b) what CALM does not do (the attribution of a probability); in (c) the creation of a synthetic element in order to explain the observed difference.

Figure 7 :

 7 Figure7: predicting the dynamics of a non observable property; in (a) a real experienced sequence; in (b) the pieces of knowledge that can explain the logic behind the observed transformations, including the synthetic property changing.

Figure 8 :

 8 Figure 8: the simulation environment to the meph experiment, where the triangles represent the agents (looking and hearing forward), and the round squares represent the objects (food or stones).

Figure 18 :

 18 Figure18: the evolution of mean reward in a typical execution of the meph problem, considering four different agent solutions: CALM, situated Q-Learning, Random, and Classic Q-Learning; the scenario is a 25x25 grid, where 10% of the cells are stones and 5% are food, in the presence of 10 other agents.


Filipo Studzinski Perotto
email: filipo.perotto@gmail.com

TOWARD SOPHISTICATED AGENT-BASED UNIVERSES Statements to introduce some realistic features into classic AI/RL problems

Keywords: Agency Theory, Factored Partially Observable Markov Decision Process (FPOMDP), Constructivist Learning Mechanisms, Anticipatory Learning, Model-Based Reinforcement Learning

In this paper we analyze some common simplifications present in the traditional AI / RL problems. We argue that only facing particular conditions, often avoided in the classic statements, will allow the overcoming of the actual limits of the science, and the achievement of new advances in respect to realistic scenarios. This paper does not propose any paradigmatic revolution, but it presents a compilation of several different elements proposed more or less separately in recent AI research, unifying them by some theoretical reflections, experiments and computational solutions. Broadly, we are talking about scenarios where AI needs to deal with true situatedness agency, providing some kind of anticipatory learning mechanism to the agent in order to allow it to adapt itself to the environment.

INTRODUCTION

Every scientific discipline starts by addressing specific cases or simplified problems, and by introducing basic models, necessary to initiate the process of understanding into a new domain of knowledge; these basic models eventually evolve to a more complete theory, and little by little, the research attains important scientific achievements and applied solutions. Artificial Intelligence (AI) is a quite recent discipline, and this fact can be easily noticed by regarding its history in the course of the years. If in the 1950s and 1960s AI was the stage for optimistic discourses about the realization of intelligence in machine, the 1970s and 1980s reveal an evident reality: true AI is a feat very hard to accomplish. This movement led AI to plunge into a more pragmatic and less dreamy period, when visionary ideas have been replaced by a (necessary) search for concrete outcomes. Not by chance, several interesting results have been achieved in these recent years, and it is changing the skepticism by a (yet timid) revival of the general AI field.

If on one hand the AI discourse mood has changed like a sin wave, on the other hand the academic practice of AI shows a progressive increment of complexity with respect to the standard problems. When the solutions designed to some established problem become stable, known, and accepted, new problems and new models are proposed in order to push forward the frontier of the science, moving AI from toy problems to more realistic scenarios. Make a problem more realistic is not just increasing the number of variables involved (even if limiting the number of considered characteristics is one of the most recurrent simplifications). When trying to escape from AI classic maze problems toward more sophisticated (and therefore more complex) agent-based universes, we are led to consider several complicating conditions, like (a) the situatedness of the agent, which is immersed into an unknown universe, interacting with it through limited sensors and effectors, without any holistic perspective of the complete environment state, and (b) without any a priori model of the world dynamics, which forces it to incrementally discover the effect of its actions on the system in an on-line experimental way; to make matters worse, the universe where the agent is immersed can be populated by different kinds of objects and entities, including (c) other complex agents, which can have their own internal models, and in this case the task of learning a predictive model becomes considerably harder.

In this paper, we use the Constructivist Anticipatory Learning Mechanism (CALM), defined in [START_REF] Perotto | Un Mécanisme Constructiviste d'Apprentissage Automatique d'Anticipations pour des Agents Artificiels Situés[END_REF], to support our assumption. In other words, we shows that the strategies used by this method can represent a changing of directions in relation to classic and yet dominant ways. CALM is able to build a descriptive model of the system where the agent is immersed, inducting, from the experience, the structure of a factored and partially observable Markov decision process (FPOMDP). Some positive results [START_REF] Perotto | Un Mécanisme Constructiviste d'Apprentissage Automatique d'Anticipations pour des Agents Artificiels Situés[END_REF], (Perotto et al. 2007), (Perotto;Alvares, 2007), (Perotto, 2011), have been achieved due to the use of 4 integrated strategies: (a) the mechanism takes advantage of the situated condition presented by the agent, constructing a description of the system regularities relatively to its own point of view, which allows to set a good behavior policy without the necessity of "mapping" the entire environment; (b) the learning process is anchored on the construction of an anticipatory model of the world, which could be more efficient and more powerful than traditional "model free" reinforcement learning methods, that directly learn a policy; (c) the mechanism uses some heuristics designed to well structured universes, where conditional dependencies between variables exist in a limited scale, and where most of the phenomena can be described in a deterministic way, even if the system as whole is not (a partially deterministic environment); which seems to be widely common in real world problems; (d) the mechanism is prepared to discover the existence of hidden or non-observable properties of the universe, which enables it to explain a larger portion of the observed phenomena. Following the paper, section 2 overviews the MDP framework and the RL tradition, section 3 describes the CALM learning mechanism, section 4 shows some experiments and acquired results, and section 5 concludes the paper.

MDP+RL FRAMEWORK

The typical RL problem is inspired on the classic rat maze experiment; in this behaviorist test, a rat is placed in a kind of labyrinth, and it needs to find a piece of cheese (the reward) that is placed somewhere far from it, sometimes avoiding electric traps along the way (the punishment). The rat is forced to run the maze several times, and the experimental results show that it gradually discovers how to solve it. The computational version of this experiment corresponds to an artificial agent placed in a bi-dimensional grid, moving over it, and eventually receiving positive or negative reward signals. Exactly as in the rat maze, the agent must learn to coordinate its actions by trial and error, in order to avoid the negative and quickly achieve the positive rewards. This computational experiment is formally represented by a geographical MDP, where each position in the grid corresponds to a state of the process; the process starts in the initial state, equivalent to the agent start position in the maze, and it evolves until the agent reaches some final reward state; then the process is reset, and a new episode take place; the episodes are repeated, and the algorithm is expected to learn a policy to maximize the estimated discounted cumulative reward that will be received by the agent in subsequent episodes.

These classic RM maze configurations present at least two positive points, when comparing to realistic scenarios: the agent needs to learn actively and on-line, it means, there is no previous separated time to learn before the time of the life; the agent must perform and improve its behavior at the same time, without supervision, by "trial-and-error". However, this kind of experiment cannot be taken as a general scheme for learning: on the one hand, the simplifications adopted (in order to eliminate some uncomfortable elements) cannot be ignored when dealing with more complex or realistic problems; on the other hand, there are important features lacking on the classic RL maze, what makes difficult comparing it to other natural learning situations. Some of these simplifications and lacks are listed below:

Non-Situativity: in the classic RL maze configuration, the agent is not really situated in the environment; in fact, the little object moving on the screen (which is generally called agent) is dissociated from the "agent as the learner"; the information available to the algorithm comes from above, from an external point of view, in which this moving agent appears as a controllable object of the environment, among the others. In contrast, realistic scenarios impose the agent sensory function as an imprecise, local, and incomplete window of the underlying situation stated by the real situation.

Geographic Discrete Flat Representation: in classic mazes, the corresponding MDP is created by associating each grid cell to a process state; so, the problem stays confined in the same two dimensions of the grid space, and the system states represent nothing more than the agent geographic positions. In contrast, realistic problems introduce several new and different dimensions to the problem. The basic MDP model itself is conceived to represent a system by exhaustive enumeration of states (a flat representation), and it is not appropriated to represent multi-dimensional structured problems; the size of the state space grows exponentially up with the number of considered attributes (curse of dimensionality), which makes the use of this formalism only viable for simple or small scenarios.

Disembodiment: in the classic configuration, the agent does not present any internal property, it is like a loose mind directly living in the environment; in consequence, it can be only extrinsically motivated, i.e. the agent acts in order to attain (or to avoid) some determined positions into the space, given from the exterior. In natural scenarios, the agent has a "body" playing the role of an intermediary between mind and external world; the body also represents an "internal environment", and the goals the agent needs to reach are given from this embodied perspective (in relation to the dynamics of some internal properties).

Complete Observation: the basic MDP design the agent as an omniscient entity; the learning algorithm observes the system in its totality, it knows all the possible states, and it can precisely perceive in what state the system is at every moment, it also knows the effect of its actions on the system, in general it is the only source of perturbation in the world dynamics. These conditions are far from common in real-world problems.

Episodic Life and Behaviorist Solution: in the classic enunciation, the system presents initial and final states, and the agent lives by episodes; when it reaches a final state, the system restarts. Generally this is not the case in real-life problems, where agents live a unique continuous uninterrupted experience. Also, solving a MDP is often synonymous of finding an optimal (or near-optimal) policy, and in this way most of the algorithms proposed in the literature are model-free. However, in complex environments, the only way to define a good policy is "understanding" what is going on, and creating an explicative or predictive model of the world, which can then be used to establish the policy.

The Basic MDP

Markov Decision Process (MDP) and its extensions constitute a quite popular framework, largely used for modeling decision-making and planning problems [START_REF] Feinberg | Handbook of Markov Decision Processes: methods and applications[END_REF]). An MDP is typically represented as a discrete stochastic state machine; at each time cycle the machine is in some state s; the agent interacts with the process by choosing some action a to carry out; then, the machine changes into a new state s', and gives the agent a corresponding reward r; a given transition function δ defines the way the machine changes according to s and a. The flow of an MDP (the transition between states) depends only on the system current state and on the action taken by the agent at the time. After acting, the agent receives a reward signal, which can be positive or negative if certain particular transitions occur.

Solving an MDP is finding the optimal (or nearoptimal) policy of actions in order to maximize the rewards received by the agent over time. When the MDP parameters are completely known, including the reward and the transition functions, it can be mathematically solved by dynamic programming (DP) methods. When these functions are unknown, the MDP can be solved by reinforcement learning (RL) methods, designed to learn a policy of actions on-line, i.e. at the same time the agent interacts with the system, by incrementally estimating the utility of state-actions pairs and then by mapping situations to actions [START_REF] Sutton | Reinforcement Learning: an introduction[END_REF].

However, for a wide range of complex (including real world) problems, the complete information about the exact state of the environment is not available. This kind of problem is often represented as a Partially Observable MDP (POMDP) [START_REF] Kaelbling | Planning and acting in partially observable stochastic domains[END_REF]. The POMDP provides an elegant mathematical framework for modeling complex decision and planning problems in stochastic domains in which the system states are observable only indirectly, via a set of imperfect, incomplete or noisy perceptions. In a POMDP, the set of observations is different from the set of states, but related to them by an observation function, i.e. the underlying system state s cannot be directly perceived by the agent, which has access only to an observation o. We can represent a larger set of problems using POMDPs rather than MDPs, but the methods for solving them are computationally even more expensive [START_REF] Hauskrecht | Value-function approximations for partially observable Markov decision processes[END_REF].

The main bottleneck about the use of MDPs or POMDPs is that representing complex universes implies an exponential growing-up on the state space, and the problem quickly becomes intractable. Fortunately, most of real-world problems are quite well-structured; many large MDPs have significant internal structure, and can be modeled compactly; the factorization of states is an approach to exploit this characteristic [START_REF] Boutilier | Stochastic dynamic programming with factored representations[END_REF]. In the factored representation, a state is implicitly described by an assignment to some set of state variables. Thus, the complete state space enumeration is avoided, and the system can be described referring directly to its properties. The factorization of states enables to represent the system in a very compact way, even if the corresponding MDP is exponentially large [START_REF] Guestrin | Efficient Solution Algorithms for Factored MDPs[END_REF]. When the structure of the Factored Markov Decision Process (FMDP) is completely described, some known algorithms can be applied to find good policies in a quite efficient way [START_REF] Guestrin | Efficient Solution Algorithms for Factored MDPs[END_REF]. However, the research concerning the discovery of the structure of an underlying system from incomplete observation is still incipient [START_REF] Degris | Factored Markov Decision Processes[END_REF].

FPOMDP

The classic MDP model can be extended to include both factorization of states and partial observation, then composing a Factored Partially Observable Markov Decision Process (FPOMDP). In order to be factored, the atomic elements of the non-factored representation will be decomposed and replaced by a combined set of elements. A FPOMDP (Guestrin et al., 2001), [START_REF] Hansen | Dynamic programming for POMDPs using a factored state representation[END_REF][START_REF] Hansen | Dynamic programming for POMDPs using a factored state representation[END_REF], [START_REF] Poupart | VDCBPI: an approximate scalable algorithm for large scale POMDPs[END_REF][START_REF] Poupart | VDCBPI: an approximate scalable algorithm for large scale POMDPs[END_REF], [START_REF] Shani | Model-Based Online Learning of POMDPs[END_REF], [START_REF] Sim | Symbolic Heuristic Search Value Iteration for Factored POMDPs[END_REF], can be formally defined as a 4-tuple {X, C, R, T}. The state space is factored and represented by a finite non-empty set of system properties or variables X = {X 1 , X 2 , ... X n }, which is divided into two subsets, X = P  H, where the subset P contains the observable properties (those that can be accessed through the agent sensory perception), and the subset H contains the hidden or non-observable properties; each property X i is associated to a specified domain, which defines the values the property can assume; C = {C 1 , C 2 , ... C m } represents the controllable variables, composing the agent actions; R = {R 1 , R 2 , ... R k } is a set of (factored) reward functions, in the form R i : P i  IR, and T = {T 1 , T 2 , ... T n } is a set of transformation functions, as T i : X  C  X i , defining the system dynamics. Each transformation function can be represented by a Dynamic Bayesien Network (DBN), which is an acyclic, oriented, two-layers graph. The first layer nodes represent the environment state in time t, and the second layer nodes represent the next state, in t+1 [START_REF] Boutilier | Stochastic dynamic programming with factored representations[END_REF]. A stationary policy π is a mapping X → C where π(x) defines the action to be taken in a given situation. The agent must learn a policy that optimizes the cumulative rewards received over a potentially infinite time horizon. Typically, the solution π* is the policy that maximizes the expected discounted reward sum

In this paper, we consider the case where the agent does not have an a priori model of the universe where it is situated (i.e. it does not have any idea about the transformation function), and this condition forces it to be endowed with some capacity of learning, in order to be able to adapt itself to the system. Although it is possible directly learn a policy of actions, in this work we are interested in model-based methods, through which the agent must learn a descriptive and predictive model of the world, and so define a behavior strategy based on it. Learning a predictive model is often referred as learning the structure of the problem.

In this way, when the agent is immersed in a system represented as a FPOMDP, the complete task for its anticipatory learning mechanism is both to create a predictive model of the world dynamics (i.e. inducing the underlying transformation function of the system), and to define an optimal (or sufficiently good) policy of actions, in order to establish a behavioral strategy. [START_REF] Degris | Factored Markov Decision Processes[END_REF] present a good overview of the use of this representation in artificial intelligence, referring algorithms designed to learn and solve FMDPs and FPOMDPs.

ANTICIPATORY LEARNING

In the artificial intelligence domain, anticipatory learning mechanisms refer to methods, algorithms, processes, machines, or any particular system that enables an autonomous agent to create an anticipatory model of the world in which it is situated. An anticipatory model of the world (also called predictive environmental model, or forward model) is an organized set of knowledge allowing inferring the events that are likely to happen. For cognitive sciences in general, the term anticipatory learning mechanism can be applied to humans or animals to describe the way these natural agents learn to anticipate the phenomena experienced in the real world, and to adapt their behavior to it [START_REF] Perotto | Anticipatory Learning Mechanisms[END_REF].

When immersed in a complex universe, an agent (natural or artificial) needs to be able to compose its actions with the other forces and movements of the environment. In most cases, the only way to do so is by understanding what is happening, and thus by anticipating what will (most likely) happen next. A predictive model can be very useful as a tool to guide the behavior; the agent has a perception of the current state of the world, and it decides what actions to perform according to the expectations it has about the way the situation will probably change. The necessity of being endowed with an anticipatory learning mechanism is more evident when the agent is fully situated and completely autonomous; that means, when the agent is by itself, interacting with an unknown, dynamic, and complex world, through limited sensors and effectors, which give it only a local point of view of the state of the universe and only partial control over it. Realistic scenarios can only be successfully faced by an agent capable of discovering the regularities that govern the universe, understanding the causes and the consequences of the phenomena, identifying the forces that influence the observed changes, and mastering the impact of its own actions over the ongoing events.

CALM Mechanism

The constructivist anticipatory learning mechanism (CALM), detailed in [START_REF] Perotto | Un Mécanisme Constructiviste d'Apprentissage Automatique d'Anticipations pour des Agents Artificiels Situés[END_REF], is a mechanism developed to enable an agent to learn the structure of an unknown environment where it is situated, trough observation and experimentation, creating an anticipatory model of the world. CALM operates the learning process in an active and incremental way, and learn the world model as well as the policy at the same time it actuates. The agent has a single uninterrupted interactive experience into the system, over a theoretically infinite time horizon. It needs performing and learning at the same time.

The environment is only partially observable from the point of view of the agent. So, to be able to create a coherent world model, the agent needs, beyond discover the regularities of the phenomena, also discover the existence of non-observable variables that are important to understand the system evolution. In other words, learning a model of the world is beyond describing the environment dynamics, i.e. the rules that can explain and anticipate the observed transformations, it is also discovering the existence of hidden properties (once they influence the evolution of the observable ones), and also find a way to deduces the dynamics of these hidden properties. In short, the system as a whole is in fact a FPOMDP, and CALM is designed to discover the existence of non-observable properties, integrating them in its anticipatory model. In this way CALM induces a structure to represent the dynamics of the system in a form of a FMDP (because the hidden variables become known), and there are some able to efficiently calculate the optimal (or near-optimal) policy, when the FMDP is given [START_REF] Guestrin | Efficient Solution Algorithms for Factored MDPs[END_REF].

CALM tries to reconstruct, by experience, each transformation function T i , which will be represented by an anticipation tree. Each anticipation tree is composed by pieces of knowledge called schemas, which represent some perceived regularity occurring in the environment, by associating context (sensory and abstract), actions and expectations (anticipations). Some elements in these vectors can undertake an "undefined value". For example, an element linked with a binary sensor must have one of three values: true, false or undefined (represented, respectively, by '1', '0' and '#'). The learning process happens through the refinement of the set of schemas. After each experienced situation, CALM updates a generalized episodic memory, and then it checks if the result (context perceived at the instant following the action) is in conformity to the expectation of the activated schema. If the anticipation fails, the error between the result and the expectation serves as parameter to correct the model. The context and action vectors are gradually specialized by differentiation, adding each time a new relevant feature to identify more precisely the situation class. The expectation vector can be seen as a label in each "leaf" schema, and it represents the predicted anticipation when the schema is activated. Initially all different expectations are considered as different classes, and they are gradually generalized and integrated with others. The agent has two alternatives when the expectation fails. In a way to make the knowledge compatible with the experience, the first alternative is to try to divide the scope of the schema, creating new schemas, with more specialized contexts. Sometimes it is not possible and the only way is to reduce the schema expectation.

CALM creates one anticipation tree for each property it judges important to predict. Each tree is supposed to represent the compete dynamics of the property it represents. From this set of anticipation trees, CALM can construct a deliberation tree, which will define the policy of actions. In order to incrementally construct all these trees, CALM implements 5 methods: (a) sensory differentiation, to make the tree grow (by creating new specialized schemas); (b) adjustment, to abandon the prediction of non-deterministic events (and reduce the schemas expectations) (c) integration, to control the tree size, pruning and joining redundant schemas: (d) abstract differentiation, to induce the existence of non observable properties; and (e) abstract anticipation, to discover and integrate these non-observable properties in the dynamics of the model.

Sometimes some disequilibrating event can be explained by considering the existence of some abstract or hidden property in the environment, which could be able to differentiate the situation, but which is not directly perceived by the agent sensors. So, before adjusting, CALM supposes the existence of a non-sensory property in the environment, which it will represent as a abstract element. Abstract elements suppose the existence of something beyond the sensory perception, which can be useful to explain non-equilibrated situations. They have the function of amplifying the differentiation possibilities.

EXPERIMENTS

In (Perotto et al., 2007) the CALM mechanism is used to solve the flip problem, which creates a scenario where the discovery of underlying nonobservable states are the key to solve the problem, and CALM is able to do it by creating a new abstract element to represent these states. In [START_REF] Perotto | Un Mécanisme Constructiviste d'Apprentissage Automatique d'Anticipations pour des Agents Artificiels Situés[END_REF] and (Perotto;Álvares, 2007) the CALM mechanism is used to solve the wepp problem, which is an interesting RL situated bi-dimensional grid problem, where it should learn how to behavior considering the interference of several dimensions of the environment, and of its body. Initially the agent does not know anything about the world or about its own sensations, and it does not know what consequences its actions imply. Figure 1 shows the evolution of the mean reward comparing the CALM solution with a classic Q-Learning implementation (where the agent have the vision of the entire environment as flat state space), and with a situated version of the Q-Learning agent. We see exactly two levels of performance improvement. First, the non-situated implementation (Classic Q) takes much more time to start an incomplete convergence, and it is vulnerable to the growing of the board. Second, the CALM solution converges much earlier than Q-Learning, taken in its situated version, due to the fact that CALM quickly constructs a model to predict the environment dynamics, and it is able to define a good policy sooner.

CONCLUSIONS

Over the last twenty years, several anticipatory learning mechanisms have been proposed in the artificial intelligence scientific literature. Even if some of them are impressive in theoretical terms, having achieved recognition from the academic community, for real world problems (like robotics) no general learning mechanism has prevailed. Until now, the intelligent artifacts developed in universities and research laboratories are far less wondrous than those imagined by science fiction. However, the continuous progress in the AI field, combined with the progress of informatics itself, is leading us to a renewed increase of interest in the search for more general intelligent mechanism, able to face the challenge of complex and realistic problems.

A necessary changing of directions in relation to the traditional ways to state the problems in AI is needed. The CALM mechanism, presented in [START_REF] Perotto | Un Mécanisme Constructiviste d'Apprentissage Automatique d'Anticipations pour des Agents Artificiels Situés[END_REF] has been used as an exemple of it, because it provides autonomous adaptive capability to an agent, enabling it to incrementally construct knowledge to represent the regularities observed during its interaction with the system, even in nondeterministic and partially observable environments.