Esther Nicart

Bruno Zanuttini

Hugo Gilbert

Bruno Grilhères

Fredéric Praca

Building document treatment chains using reinforcement learning and intuitive feedback

Keywords: Artificial intelligence, Reinforcement learning, Extraction and knowledge management, Man-machine interaction, Open source intelligence (OSINT)

We model a document treatment chain as a Markov Decision Process, and use reinforcement learning to allow the agent to learn to construct custom-made chains "on the fly", and to continuously improve them. We build a platform, BIMBO (Benefiting from Intelligent and Measurable Behaviour Optimisation) which enables us to measure the impact on the learning of various models, algorithms, parameters, etc. We apply this in an industrial setting, specifically to a document treatment chain which extracts events from massive volumes of web pages and other open-source documents. Our emphasis is on minimising the burden of the human analysts, from whom the agent learns to improve guided by their feedback on the events extracted. For this, we investigate different types of feedback, from numerical feedback, which requires a lot of user effort and tuning, to partially and even fully qualitative feedback, which is much more intuitive, and demands little to no user intervention. We carry out experiments, first with numerical feedback, then demonstrate that intuitive feedback still allows the agent to learn effectively.

Introduction

Our research is driven by an industrial need, expressed by the Open Source INTelligence (OSINT) community. In the past, the OSINT analyst's task was finding hidden information. Now, faced with everincreasing volumes of web pages and other open source documents, the challenge is to find pertinent information from the huge wealth of data available. Many specialised treatment chains have been developed to ease this task (for example, [START_REF] Ogrodniczuk | Linguistic Processing Chains as Web Services: Initial Linguistic Considerations[END_REF] give an overview of some processing chains that are provided as web services).

We tackle the generic problem of the improvement of such a chain, specifically the extraction of events for OSINT assessment and surveillance. In this application, documents, sourced for the most part from the web, are inserted continuously into a treatment chain which aims to extract events (e.g., terrorist attacks) and their characteristics (date, place, agents, etc.).

In such applications, it is clear that the extraction cannot be perfect. Firstly, because of the huge diversity of documents on the Web, there cannot be a single optimal chain for all documents. Secondly, imagine, for example, a school blog recounting "the bombardment of a gold target by ions during an atomic physics demonstration at the school science fair". The treatment chain could erroneously recognise and extract an atomic bomb attack. Then, the need to treat documents coming from all over the world in diverse languages entails the use of dictionaries whose quality is variable. For these reasons, the analysts are typically forced to correct a posteriori the events extracted, a distracting, onerous and repetitive task.

The specific application which we examine uses a chain, defined by experts, which consists of a fixed (but potentially conditional) series of individual treatments, such as the detection of the document format, language recognition, translation, extraction of events using nouns and verbs as triggers, etc. There is currently no way to improve the chain over time without the intervention of an expert in consultation with the analysts.

Our objective is to remedy this situation by providing a mechanism which learns to modify its behaviour in real time, continuously improving the chain, and reducing human effort by decreasing the error rate. This mechanism receives feedback (see below) obtained as the analysts consult the system output. In other words, we allow the chain to "learn" from its mistakes. For instance, that if the document is a well-written scientific article in French, a translation to English before the extraction works well to make the most of the wealth of English extraction rules available, but for blogs containing slang, a direct extraction is preferable as the dictionaries are insufficient, and a translation only introduces more noise. The services, or building blocks for the chain, thus remain a "black box" for the analyst allowing her to distance herself completely from the extraction process.

We need to collect the feedback non-intrusively, that is, in a way that is invisible to the analyst without impacting on her work. A user's expertise can be modelled by tracing his actions [START_REF] Bratko | Learning qualitative models[END_REF]. In production, these action traces could be captured through the graphical interface which gives a summary of the events extracted. We can then base the feedback on the analyst-system interactions that currently occur. For example, an event might be corrected, in which case we can deduce an explicit feedback based on the corrections that the analyst might make, that is, a distance between the event as corrected and that which was extracted. Indeed, our first set of tests in Section 9 simulate this, in that the agent receives a numerical feedback as an automatically generated judgement on the quality of extractions.

The difficulty is that an event may also be not extracted, extracted in too long a time, etc. To interpret these "non-actions" as feedback, we must first answer questions such as "Is it preferable to extract something erroneously, or to miss an extraction ?", "Should I sacrifice speed for quality, or vice versa ?".

These questions cannot be answered naturally with a numerical response ; it is not easy to determine that "A partial, but fast extraction is worth 10.5 times more than a slow but complete extraction". It is therefore essential that we progress to giving intuitive feedback (Section 10), based on naturally expressed user preferences, such as "I prefer an extraction to no extraction" and "I prefer it to be as fast as possible". The requirements can thus be gathered very easily, and can be changed if necessary in an intuitive fashion.

Contribution

We formalise the improvement of a document treatment chain as a reinforcement learning (RL) problem, and the treatment chain itself as a Markov Decision Process (MDP) (Section 6). We investigate three different settings. In the first, the agent is rewarded with numerical feedback on the quality of the treatment, which is very informative but very time-consuming for the human user. The second and third use intuitive user feedback (a partially qualitative formalisation, and then a fully qualitative one). These are less informative but require much less, or no user interaction.

We build a platform, BIMBO (Benefiting from Intelligent and Measurable Behaviour Optimisation) into which we can "plug" different RL algorithms, models, web services, reward mechanisms etc., which enables us to measure their impact on the learning. We apply this in an industrial setting, specifically to a treatment chain which extracts events from web pages and other open-source documents.

We carry out experiments, first with numeric, potentially sporadic feedback data (Section 9), which show that automatically learning how to chain and parametrise services is perfectly feasible. Then we carry out experiments with intuitive feedback (Section 10), where even though the roughness of feedback makes learning less effective, it remains perfectly feasible, while requiring little or no tuning.

Related work

To our knowledge, an agent capable of dynamically constructing a chain of services, which constantly learns and self-improves from natural human feedback has not yet received academic attention. Nevertheless, the base elements are there:

Chaining together services to attain a desired result, for instance, is not a new concept. Service compositions can be computed, for example, to help the user to fill in forms [START_REF] Saïs | SOS-DLWD[END_REF], and the physical characteristics of documents are used to successfully construct adaptive, modular chains for Xerox photocopiers in real time [START_REF] Fromherz | Model-based computing for design and control of reconfigurable systems[END_REF]. However, the inputs and outputs of each service are known in advance, and it is a planning task to string them together. User preference is not taken into account, there is no measure of the result's quality, and no automatic feedback into the process to improve it next time.

The user can reconfigure the chain herself using a dedicated language, e.g., ReCooPLa [START_REF] Rodrigues | Towards an engine for coordination-based architectural reconfigurations[END_REF], or by choosing a service from directories of the same type [START_REF] Doucy | Méthodologie pour l'orchestration sémantique de services dans le domaine de la fouille de documents multimédia[END_REF]. The chain will not adapt dynamically without user intervention, however, and the user must have system expertise to appreciate the consequences of her choices.

Using human feedback, both explicit and implicit for model-based learning has also been explored. An agent can learn sequential tasks using continuous human evaluation of its actions, for instance, the trainer's positivity can influence the agent to learn trainer-dependent behaviour [START_REF] Knox | Framing reinforcement learning from human reward: Reward positivity, temporal discounting, episodicity, and performance[END_REF] or implicit, non-numeric feedback can be provided by inference on the observation of the trainers' actions (Loftin et al., 2016 01). Models of the user's behaviour [START_REF] Azaria | Strategic advice provision in repeated human-agent interactions[END_REF] and preferences [START_REF] Karami | Apprentissage de connaissances d'adaptation à partir des feedbacks des utilisateurs[END_REF] can be built up through human-system interactions to provide personalised systems. The agent can also learn by demonstrating two policies, which are ordered by the expert [START_REF] Akrour R | Preference-based policy learning[END_REF]. Although these systems react well to changing users and their preferences, they are not adapted to our problem, as they require continuous user interaction at each step to confirm or contradict their choice. This would be prohibitively expensive in our case as our users are not dedicated trainers and the human effort needed to yield a competent policy can be considerable.

We currently treat the services as "black boxes", aiming to improve the way they are combined. We note that information can be gleaned about the quality of each service [START_REF] Caron | Provenance-based quality assessment and inference in data-centric workflow executions[END_REF] and potential degradation in the chain [START_REF] Amann | WebLab PROV: Computing fine-grained provenance links for XML artifacts[END_REF], and that individual services can be automatically updated based on user edits [START_REF] Formiga | Leveraging online user feedback to improve statistical machine translation[END_REF]. We can imagine using a combination of techniques such as these in parallel with our approach.

The WebLab Platform

Our industrial application uses the open-source platform WebLab (2015) for economic, strategic and military surveillance. We also use it for our experiments. WebLab integrates web services which can be interchanged or permuted to create a treatment chain for the analysis and extraction of information from web pages and other open-source multimedia documents.

A typical WebLab treatment chain (Figure 1) first converts the source into an XML resource. This resource is then passed from service to service. Each service analyses the contents of the resource it receives and enriches it with annotations. Finally, the results are stored for the analyst to consult.

Text

Normaliser (e.g. [START_REF] Tika | Apache Tika -a content analysis toolkit[END_REF])

d → r 0 ; r 1 = r 0 + u 0
Language detector (e.g. NGramJ (2015))

r 2 = r 1 + u 1
Extractor (e.g. GATE (2016))

r 3 = r 2 + u 2 DB d r 1 r 2 r 3
FIGURE 1 -A simple but typical Weblab chain: a document, d, is converted into an XML resource, r 0 , and annotations, u j , are added by each service. Finally the results are stored in a database.

Example 1

Consider the following document:

4/29/1971: In a series of two incidents that might have been part of a multiple attack, suspected members of the Chicano Liberation Front bombed a Bank of America branch in Los Angeles, California, US. There were no casualties but the building sustained $1 600 in damages.

The simplified XML resource in Figure 2 is produced after passing the document through a normaliser, adding the annotations "text/plain" (line 12) and original content (line 19) ; and a language detector, adding the language "en" (line 16).

As our chain is dedicated to extracting events, we first define these formally. We chose a formalisation in the ontology WOOKIE [START_REF] Serrano | Vers une capitalisation des connaissances orientée utilisateur: extraction et structuration automatiques de l'information issue de sources ouvertes[END_REF], but any other definition of an event (e.g. [START_REF] Van Hage | Design and use of the Simple Event Model (SEM)[END_REF]) could be used. Definition 1 (Event) An event is a quadruplet (C, T, S, A) where: -C ⊆ C is the conceptual, or semantic dimension, given by a set of elements taken from the domain C common to all events ; -T is the temporal dimension, or when the event occurred. It is potentially ambiguous, e.g. "last Tuesday", and to model this ambiguity, we take T ⊆ T, where T is the set of all dates ; -S ⊆ S is the spatial dimension, or where the event occurred, also potentially ambiguous ; -A ⊆ A is the agentive dimension, or the participants.

Even though the definition is general, in this article we use precise domains: C is a fixed and finite set of elements in WOOKIE ; T is the set of all relative and absolute "dates", such as "tomorrow", "2001", "2001/9/11" ; S is the set of entities defined in Geonames (2015) ; finally, A is the infinite set of all extractable participants, seen as strings.

Example 2 (Example 1 continued) An event E = (C, T, S, A) could be extracted from the document above with C = {AttackEvent, BombingEvent}, T = {4/29/1971}, S = {Los Angeles, California, US}, and A = {Chicano Liberation Front, Bank of America}.

Building an efficient treatment chain depends not only on the services chosen but their parameters. For instance, the extractor GATE is parametrised by gazetteers, which are lists of nouns and verbs triggering the detection of a specific type of event ; the verb gazetteer for a bombing event would typically contain explode, detonate, etc. Hence we see GATE as a parametrised service: choosing the correct gazetteers for it to use is part of building an efficient treatment chain.

Reinforcement learning

In production, the treatment chain is complex. It is written and calibrated by experts who choose the services making up the chain, their order, and their parameters. The service order is fixed, but can be conditional (e.g., if the document is in French, send to extractor 1, and to service 2 otherwise).

Despite their expertise, it is impossible to create the perfect universal chain, as the treatment of open source documents gathered from the web means that: their format and contents are not standard, the source pages themselves are not controlled, URLs change or are pirated, and there is "noise" (e.g., adverts). The right web services have to be called in the correct order and supplied with the best parameters, and even then may or may not extract useful information from a document. Undetected events and partially or falsely extracted events (e.g., unconnected information in the same sentence erroneously associated) provoke extraction errors.

For example, imagine that the analyst wants information on aerial bombings. We saw in Section 1 that it is impossible to say with certainty that the word "bombardment" refers to this. The analyst can see that the page is a school blog only once the event has been extracted. Even from a specialist web page, it is possible that the word refers to the incessant questions of the journalists, and not an attack. Maybe the synonym "shelling" was used, and the event is not recognised. With these uncertainties, the experts who configure the chain try to envisage the most common situations. It is inconceivable that they construct individual chains by examining each source document.

Formalising this treatment chain and improving the event extraction is therefore not a trivial problem. The only information known before starting the treatment chain consists of the available services, their parameters, and the potential characteristics of the XML resource and system (see Section 4). The agent knows neither the form, nor the content of the documents in advance, nor even if an extraction is possible. Its actions are thus taken under uncertainty. Hence we model the problem as one of reinforcement learning (RL) for Markov Decision Processes (MDPs). We give an overview here, but recommend reading Sutton & Barto (1998) for more details.

In RL, the learner receives a reward, based on the results of its chosen actions. The closer the results are to the objectives, the higher the reward. The learner tries to maximise these rewards, typically by exploiting current knowledge to continue to receive good rewards, or by exploring new actions with the hope of obtaining even better ones.

RL is generally formalised as a Markov Decision Process (MDP, [START_REF] Puterman | Markov Decision Processes: Discrete Stochastic Dynamic Programming 1st[END_REF]), which models the environment in terms of states, in which actions are possible, leading to other states stochastically. The fact that the environment is in a given state at a certain instant bestows an immediate reward on the learner (or agent). The agent's objective is to choose actions such that it maximises its expectation of cumulated rewards.

Definition 2 (MDP)

A Markov Decision Process (MDP) is a quintuplet (S, A, P, R, γ) where: -S is a (here finite) set of possible states in the environment ; -A is a (here finite) set of actions (available to the agent) ; -P is a set of distributions {P a (s, •) | s ∈ S, a ∈ A} ; P a (s, s � ) is the probability that the environment is in state s � after the agent performs action a in s ; -R is a reward function, defined on the states ; R(s) is the reward obtained by the agent when it reaches state s ; γ ∈ [0, 1] is an discount factor, weighting expected future rewards against those currently expected.

In RL, the agent initially only has knowledge of the state / action space S × A, as well as the factor γ. At each instant t, it knows the current state s t of the environment, and chooses an action a t . The environment passes into state s t+1 according to the probability distribution P at (s t , •), and the agent is informed of the state s t+1 and the reward r t+1 = R(s t+1 ). The process continues in s t+1 . The agent, as it interacts with the environment, learns a series of policies π 0 , π 1 , . . . , π t , . . . , where a policy π t : S → A gives, at instant t, the action π t (s) to perform if the current state s t is s. Its goal at each moment is to maximise the expected accumulated reward, that is, the expected quantity

� ∞ t � =t γ t � R(s t � )
. This generic framework encompasses many variations (for a recent summary, see [START_REF] Szepesvári | Algorithms for reinforcement learning[END_REF]).

Numerous algorithms exist to solve RL problems. In our experiments we first use standard Q-learning [START_REF] Watkins | Learning From Delayed Rewards[END_REF] with numerical feedback. Tests were also carried out using RMax [START_REF] Brafman R | R-max-a general polynomial time algorithm for nearoptimal reinforcement learning[END_REF] and VMax [START_REF] Rao | V-MAX: A General Polynomial Time Algorithm for Probably Approximately Correct Reinforcement Learning[END_REF], which are conceptually different (learning the underlying MDP instead of a policy directly) but the convergence and calculation time proved prohibitively long for our problem. Then for the qualitative setting, which standard approaches cannot handle, we used a recently proposed algorithm, called SSB Q-learning [START_REF] Gilbert | Model-free reinforcement learning with skew-symmetric bilinear utilities[END_REF]. We give brief overviews of both below to keep this paper self-contained, but encourage the reader to read the original articles. Nonetheless, our contribution includes modelling the improvement of a treatment chain as an RL problem, and in practise, any RL algorithm could be used. Note that we present here the general algorithms. Our formalisation of user feedback for our application is detailed in Sections 9-10.

Q-learning

Q-learning is a simple algorithm with easily observable results, and parameters which can be set intuitively. It maintains, for each state / action couple (s, a), a value denoted Q(s, a) which represents the agent's current estimate of the expected reward if from s it executes a, then follows an optimal policy. It is controlled using an �-greedy (EG) strategy: when the agent is in state s t , it chooses a t which maximises Q(s t , a t ), except with probability �, when it chooses a random action (it explores). Then, upon reception of the new state s t+1 and immediate reward r t+1 , it updates Q(s t , a t ) as shown in Algorithm 1. The learning rate α ∈ [0, 1] fixes the importance of the latest experience (r t+1 + γ max(. . . )) with respect to the experience already gained (the previous value of Q(s t , a t )). The discount factor γ ∈ [0, 1] determines the importance of long-term gain.

Algorithm 1: Q-learning Data: MDP M 1 while True do 2 Choose a t using the EG exploration strategy 3 Play a t , observe s t+1 , and let

r t+1 = R(s t+1 ) 4 Qt+1 (s t , a t ) ← Qt (s t , a t ) + α t (s t , a t )(r t+1 + γ max b { Qt (s t+1 , b)} -Qt (s t , a t ))

SSB Q-learning

Our approach works very well with numerical feedback (Section 9), but very few humans could say "A false extraction is worth 10.5 times more than a missed extraction, which is worth 7.9 times more than an extraction taking 90 seconds". They would more likely reply "I prefer a false extraction to a missed extraction, as I don't want to lose information, and I'd rather it were as fast as possible". Note that there are two preferences expressed here, which although they impact each other (one might suppose that speed could result in poor extraction quality), cannot naturally be linked numerically. We therefore want to give feedback based on the decoupled user preferences: "I prefer an extraction to no extraction" and "I prefer it to be as fast as possible". This preferential information can be expressed as a partial order over possible results achieved (f 1 , . . . , f k ) (seen as final states) given by the human agent. For instance f i can stand for "a good extraction in 10 seconds" or "no extraction in 5 seconds", etc.

Solving RL problems based on this kind of ordinal/preferential information is the problem raised by preference-based RL [START_REF] Akrour R | APRIL: Active preference learning-based reinforcement learning[END_REF][START_REF] Fürnkranz | Preference-based reinforcement learning: a formal framework and a policy iteration algorithm[END_REF][START_REF] Tadepalli | A bayesian approach for policy learning from trajectory preference queries[END_REF][START_REF] Wirth | EPMC: Every visit preference monte carlo for reinforcement learning[END_REF][START_REF] Wirth | Model free preference-based reinforcement learning[END_REF]. In this context, maximizing the expectancy of cumulated rewards cannot be done directly as the numerical values of those rewards are not available. One approach would try to recover a consistent reward function from the given preferential information. This approach has the disadvantage of introducing some preferential information that was not expressed by the decision maker. Thus a second approach aims at using decision criteria adapted to ordinal information. One criterion of this kind is called probabilistic dominance [START_REF] Busa-Fekete R | Preference-based reinforcement learning: evolutionary direct policy search using a preference-based racing algorithm[END_REF] and aims to maximize the probability of yielding a preferred outcome. More formally, let π 1 and π 2 be two policies and let F 1 , F 2 be two random variables on (f 1 , . . . , f k ) where P(F i = f j ) is given by the probability of π i achieving result f j , and F x � F y indicates that the result achieved by π x is preferred or equal to that achieved by π y . Then according to the probabilistic dominance criterion:

π 1 � π 2 ⇔ P(F 1 � F 2 ) ≥ P(F 2 � F 1 )
In words, policy π 1 is preferred to π 2 if the probability of π 1 doing better than π 2 is greater than the converse.

In fact probabilistic dominance is a particular instance of a wide class of criteria called Skew Symmetric Bilinear (SSB) utility functions [START_REF] Fishburn | SSB utility theory: an economic perspective[END_REF]. Given φ, an SSB utility function, φ(π, π � ) > 0 (resp. φ(π, π � ) < 0) expresses the fact that the user prefers π to π � (resp. π � to π) whereas φ(π, π � ) = 0 expresses an indifference. Probabilistic dominance is the case when φ is always 1, 0, or -1, hence requires only purely ordinal feedback from the user.

To achieve reinforcement learning with this optimisation criterion, we use the recently proposed algorithm called SSB Q-learning [START_REF] Gilbert | Model-free reinforcement learning with skew-symmetric bilinear utilities[END_REF], which proposes a solution in the general setting of SSB optimisation criteria. Like Q-learning, SSB Q-learning uses EG exploration, and it updates the Q-values similarly. However instead of having the numerical values of the rewards given by the environment, they are defined by φ and the past experiences of the agent i.e. the frequencies p t with which it has achieved each possible final result so far (the resulting numerical value is denoted by R pt (s t+1 )). Intuitively, the algorithm continuously tries to act better, according to φ, than it has so far (Algorithm 2).

Algorithm 2: SSB Q-learning [START_REF] Gilbert | Model-free reinforcement learning with skew-symmetric bilinear utilities[END_REF] Data: MDP M, SSB function ϕ 1 while True do 2 Choose a t using the EG exploration strategy 3 Play a t , observe s t+1 , and let

r t+1 = R pt (s t+1 ) 4 Q t+1 (s t , a t ) = Q t (s t , a t ) + α t (s t , a t )(r t+1 + max b {Q t (s t+1 , b)} -Q t (s t , a t )) 5 if s t+1 is a final state f i and exploration is off then 6 p t+1 = p t + 1 η+1 (1 i -p t ) 7
# η is the number of times p has been updated.

Finally, for both algorithms we used versions with eligibility traces (Sutton & Barto, 1998, Section 7). In these, a decay parameter λ ∈ [0, 1] controls how far new experiences are back-propagated along the trace of decisions taken. λ = 0 corresponds to the algorithms as described above, while at the other extreme, λ = 1 corresponds to Monte-Carlo like RL algorithms.

Chain improvement as reinforcement learning

Given that it is impossible to create a unique chain capable of perfectly treating every type of document, the ideal would be to have a tailor-made chain for each one. Part of our contribution is to model the treatment of a document as an MDP, and its improvement as an RL problem. This is not as trivial as it may seem, as the treatment process and its input are heterogeneous, and yet a way must be found to standardise them into the states and actions of a decision problem. Neither can the rewards be easily specified, especially as our users are not dedicated trainers, and we are trying to collect feedback in a non-intrusive fashion.

We define the states using the characteristics of the original document and of the resource and system at a given moment (Section 7). The system thus perceives the task as the states of a process, and each passage through a service modifies the current state.

The system also has a certain number of actions available which it can apply in the current state. The repetition of the same action on the same document is technically authorised, but will penalise the system, as the treatment time will be longer, and due to the massive volumes being treated in production (potentially all possible documents from the web) faster results are preferred.

The actions take the system from one state to another, e.g., if 70% of the source documents are in English, the agent will perceive that taking the action "detect language" in a state s t leads with probability 0.7 to a state s t+1 similar to s t except that it contains the information "language detected" and the annotation "en".

More precisely, the states that the system perceives are combinatorial states, formed from the values of a certain number of descriptors of the documents. These states allow a generalisation of the learning ; we have already seen that the type of source web page (school blog vs. specialist) could greatly influence the utility of the word "bombardment" for the extraction of information. We might hope that the system would learn from the user interactions that: if the current state has the value "true" for the descriptor "typeExtracted" and the value "school blog" for the descriptor "type", then the best action to perform consists of stopping the treatment (useless to try to extract bombings from school blogs) ; if the type is extracted and is not "school blog", the best action consists of passing the document to an extraction service, using the word "bombardment" among the trigger words ; otherwise, the best action consists of passing the document to a type-recognition service. Finally, the rewards are defined by the user in three ways. The first is a quantitative value based on the corrections made to the extraction (if any) by the analyst and the time spent in treating a document (Section 9). The second is a qualitative reward based on the user's purely ordinal preference on the results, and the third, a middle-ground between the first two, is a weighted ordinal preference (Section 10). The rewards r(s) are thus given to the system only for the final states of a treatment. For this, we can use the fact that the analysts consult the summaries produced by the system, which show the events extracted and link to the original source documents. The actions of the analyst, such as correcting the extracted information or consulting a JFPDA 2016 document without correcting it, furnish indirectly a feedback on the treatment the document received.

Experimental framework

To assess the validity of our approach, we ran experiments with our industrial application, using a simple, but typical chain, as described in Section 4, to which we added the possibility of choosing a "useless" service Geo. The chain is written as a [START_REF] Camel | Apache Camel[END_REF] route in XML. Each service is defined as an endpoint, and we use the Dynamic Router to give BIMBO control over the services called, their order and their parameters, specifically the choice of gazetteers (trigger words) of GATE [START_REF] Cunningham | Developing Language Processing Components with GATE Version 8 (a User Guide)[END_REF] for event detection in a text. The available actions are therefore to choose the next service from {Tika, NGramJ, GATE, Geo}, to choose a GATE gazetteer, or to STOP the treatment and return any extracted events. Note that the services are "black boxes" to the algorithms and BIMBO, so that knowledge of, e.g., their WSDLs is unnecessary.1 A state is represented by an attribution of the following characteristics: -the information already extracted (if any): language ∈ {"en"," "} ; format ∈ {"text/plain"," "} ;

interesting ∈ {true, false} (true if a given type of event has been extracted) ; any ∈ {true, false} (true if any events have been extracted) ; -the parameters chosen: nounGazetteer (the noun gazetteer currently chosen, if any), similarly verb-Gazetteer ; -the system state: nbServices ∈ {0-5, 6-20, 21+} (the number of services through which the current document has already passed) ; timeTakenSoFar (seconds since the current document treatment started in timeInterval (parametrizable) steps. This restricted set of states and actions was chosen to demonstrate the validity of our approach. The next step is to take into account more characteristics (e.g., source website type, complete list of languages), services (e.g., web-crawling, translation) and their parameters.

Given the cost of an analyst's time, we simulate the feedback in our experiments. We use an open-source corpus in which the events are already known: the Global Terrorism Database (GTD LaFree ( 2010)), consisting of details of over 125 000 worldwide terrorist events from 1970 to 2014. We constructed a set of documents summarising these events {d 1 . . . d N } from which a perfect chain could extract perfect events E 1 , . . . , E N , respectively (as in Examples 1 and 2), if it had infinite time, and access to an infinite number of perfectly parametrised web services. Obviously such a chain does not exist in real life, so we use the results from a production chain tuned by hand as a reference, referred to hereafter as the "expert" chain. We expect our AI to learn to construct chains that approach and eventually improve on the "expert" chain, in learning not only the correct order of the services and the best parameters, but also the fact that certain services (in our case, the geographical inference) and certain parameters (some GATE gazetteers) are not useful.

As we explained in Section 5, in our tests, the AI starts learning with no a priori knowledge of the documents or the users needs. We say that such an AI is "untrained". Once the AI has treated a certain number of documents, it will have learnt what it considers to be an optimal policy. We say that it is "trained".

Note that here we test the learning capacity of an initially untrained AI. In production, to avoid learning "from scratch", we would capitalise on existing expertise by initialising BIMBO with a policy based on that of an "expert" chain.

Measuring the quality of the results

To measure the quality of the results, we must first define the similarity between an event extracted from the document by the chain E 1 = (C 1 , T 1 , S 1 , A 1 ), and the corresponding "perfect" event E 2 = (C 2 , T 2 , S 2 , A 2 ) in the GTD.

Numerous methods have been proposed for measuring similarity [START_REF] Pandit | A comparative study on distance measuring approaches for clustering[END_REF]; [START_REF] Tversky | Studies of similarity[END_REF]; [START_REF] Cohen | Very Fast Similarity Queries on Semi-Structured Data from the Web[END_REF]; [START_REF] Dutkiewicz | Knowledge-based highlyspecialized terrorist event extraction[END_REF] to give but a few), but we wanted a measure taking into account the events' four dimensions, and capable of differentiating between different types of event, therefore we define:

σ(E 1 , E 2 ) = aσ C (C 1 , C 2 ) + bσ T (T 1 , T 2 ) + cσ S (S 1 , S 2 ) + dσ A (A 1 , A 2 ) (a + b + c + d)
We define the semantic (resp. geographical) similarity σ C (C 1 , C 2 ) (resp. σ S (S 1 , S 2 )) to be 1 if there is a common element between the semantic (resp. geographical) dimensions of E 1 and E 2 , and 0 otherwise. For example, for C 1 = {Attack, Bombing} and C 2 = {Bombing}, we obtain

C 1 ∩ C 2 = {Bombing}, so σ C (C 1 , C 2 ) = 1.
The temporal similarity σ T (T 1 , T 2 ) is 1 for T 1 ∩T 2 � = ∅, but if there is no common element, we use partial and derived information (day, month, year, day of the week). For example, for T 1 = {7 October 1969}, T 2 = {October} and T 3 = {T uesday}, σ T (T 1 , T 2 ) = 1 10 . T 1 ∩ T 3 is ∅, but as 7 th October 1969 was a Tuesday, σ T (T 1 , T 3 ) = 1 7 . 2 Finally, for the agentive similarity, we use the Levenshtein distance (the minimum number of characters to delete, insert or replace to convert one string into the other) on each pair of agents a 1 , a 2 in A 1 , A 2 . As the named entity (NE) extractors such as Gate can make partial matches, or over-match, we make this distance "fuzzy" (F L(a 1 , a 2 )) by comparing the substrings [START_REF] Ginstrom R | The GITS Blog: Fuzzy substring matching with Levenshtein distance in Python[END_REF]

, and define σ

A (A 1 , A 2 ) as 1 -min{F L(a 1 , a 2 ) | ∀a 1 ∈ A 1 , ∀a 2 ∈ A 2 } if
over a certain threshold θ, and 0 otherwise (in practise, θ = 0.45 gave the best results). For example, if A 1 = {Dr Dolittle P hD} and

A 2 = {Doolittle}, σ A (A 1 , A 2 ) is 1 -F L( ✟ ✟ ❍ ❍ Dr Dolittle✘ ✘ ✘ ❳ ❳ ❳ P hD, Do ✁ ❆ olittle) = 1 -1 8 = 0.875.
We do not try here to associate named entities such as London / capital of England, but the modularity of the system would allow this.

The quality of the events extracted (if they exist) takes into account this similarity, and the time taken to treat the document. More precisely, if the extraction of Êi from document d i took time t with target event E i , we define the quality Q of the extraction to be σ( Êi , E i )/t if σ( Êi , E i ) � = 0, and -t otherwise (no event extracted, or null similarity with the target event).

We thus formalise the fact that the correct extraction of events is primordial, and must be done in a reasonable time, and that the AI should rapidly detect if there is no interesting event to extract.

Experiments with numerical feedback

In these experiments, the AI receives numerical feedback as defined in Section 7 on the quality Q of its results. In production, this corresponds to rewarding it based on the event which it has extracted (if any), and the extraction as corrected by the human analyst, considered to be the "perfect" event which could be extracted from the document (if any). This is indeed non-intrusive, as it relies on corrections which the analyst would need to make anyway, but requires fine-tuning of the definition of the similarity and its parameters, a cognitively difficult task. Note that the information given to the AI here is the same as that used for assessing the quality of the policy it has learnt, as is standard in RL but not natural in real life. In Section 10, we remove these requirements and report the results with qualitative feedback.

Training then testing with a given analyst preference

We first tested the quality of the policy learnt (1) after training repeatedly on a small set of documents, and (2) from scratch on a larger, randomly chosen set of documents.

(1) We trained our AI on 100 GTD documents treated in the same order 30 times. To avoid the AI running forever, if the treatment time for a document exceeded a threshold of 30 seconds, the chain was stopped after the current service finished, and any events extracted returned. The AI had the choice of the services or STOP (as in Section 7), and six gazetteers (three lists of verbs and three of nouns). Two pairs of gazetteers (bombing and injure verbs and nouns) contained lists of words likely to trigger the extraction of events of that type. Another pair of dummy gazetteers contained words not present in the GTD. We represented an analyst's preference by defining "interesting" events as Bombing events and emphasising semantic similarity (specifically a = 20, b = c = d = 1). We hoped the AI would take into account the analyst's preference by favouring the bombing gazetteers over the injury gazetteers, and ignoring the dummy ones as they never lead to an extraction. 64% of of the documents described these "interesting" Bombing events, 17% other events, and 19% contained no extractable events.

Q-learning was run with standard parameters: exploration rate � = 0.4, then divided by 2 every 500 documents until � = 0.1, learning rate α = 0.2. For these experiments λ was 0 (no eligibility traces).

The values 1

10 and 1 7 were chosen by experiment, and highlight the difficulty of giving an exact numerical value to a comparison.

(2) We tested both an untrained AI and the policy learnt by this trained AI on 1 000 documents chosen randomly from the GTD, "seeing" them for the first time. Only 29% of these contained "interesting" Bombing events, 7% other events, and 64% no extractable events. As a control, we also ran an "expert" chain which was tuned to extract only the Bombing events.

The untrained AI (starting "from scratch") managed to extract 39% of the possible events from the 1 000 unknown documents and we see in Figure 3 that it generalises well, its performance improving the more different documents it encountered. The trained AI demonstrated an "expert"-like policy, extracting 100% of the events, showing that it also generalises well, applying a learnt policy successfully to unknown documents. We also note that the AI learnt to order the chain, e.g., in the state corresponding to a document with neither format nor language detected, and 0 seconds passed, the best action learnt was to pass the document to the service Tika. In the state corresponding to a document where at least one event is extracted, whatever the values of the other attributes, the AI stopped the treatment of that document.

As hoped, the AI also learnt to optimise the chain. It didn't call the service Geo, and only used the bombing verb list. However, it unexpectedly preferred injure nouns to those of bombing. On investigation, we found that the GATE service provided only uses the verbs for event extraction, ignoring the nouns. This shows that the AI was able to discover strategies which were not clear even to the expert calibrating the chain.

Performance testing

The previous set of experiments aimed to assess the ability of the AI to extract events from unknown documents. We ran a second set of experiments, to assess how fast an untrained AI could learn an "expertlike" policy (one able to extract 100% of the events), and how well this policy performed, so as to verify that the events extracted were indeed similar to the target ones. For this, we took a set of 63 documents from the GTD, all of which contained events extractable by the "expert" chain. We treated these documents in the same order repeatedly (in rounds). To investigate to what extent the AI was able to extract the correct events, especially by choosing the best gazetteers for GATE, we expanded the action space by giving the AI the choice of the services or STOP plus ten gazetteers (five lists of verbs and five of nouns): three pairs (bombing, shooting and injure) containing lists of words likely to lead to the detection of only one type of event ; one pair (mixed) containing a mix of words likely to result in the detection of several types of events ; and one dummy pair. We sought to verify that the AI would learn to use the mixed gazetteers rather than the unique event gazetteers, that it would avoid the dummy gazetteers, and that it was not sensitive to a larger action space.

Q-learning was run with parameters similar to those of the first experiments: � = 0.4, divided by 2 every 10 rounds until � = 0.1, α = 0.2, and λ = 0. The timeout was set to 18 seconds.

We first trained the AI with feedback given for each document. It turned out that after only 1 008 documents (that is, 16 rounds), the learnt policy was able to extract 100% of the events. More importantly, the quality of the extraction with this policy was on a par with that of the "expert" chain, as shown in Figure 4a.

Naturally the analyst is not available 24×7 to consult each document as it is treated. We therefore ran a similar experiment, but giving feedback on all extractions only once all 63 documents had been treated, hence preventing the AI from learning during a round. The AI was understandably slightly slower to learn, but learnt an "expert"-like policy after only 1 260 documents (20 rounds), and again the quality of this policy was on a par with that of the "expert" chain (Figure 4b). Finally, the analysts are not dedicated trainers, and will not correct all extractions. We therefore only gave feedback at the end of the round with a probability of 10% on each extraction (otherwise the AI received no feedback at all for that extraction). Even with such sporadic feedback, the AI managed to extract 50% of the possible events after only 1 890 documents (30 rounds), and 100% after 5 103 documents (81 rounds). The quality of these two policies is depicted in Figures 4c,4d, and suggests that the ability to extract events and the ability to extract correct events increase together. Note that the lower quality (compared to the "expert" chain) that we observe in the latter plot is due to the processing time, and not the similarity with the target event.

Experiments with intuitive feedback

We performed a comprehensive set of experiments, with varying parameters γ (discount parameter, see Definition 2), � (exploration rate), and λ (decay parameter for eligibility traces, see Section 5). For each setting of these parameters, we compared the performance of the "expert" chain and those of three AIs learning "from scratch": -QL: Q-learning with numerical feedback as in Section 9 but with varying parameter settings, and eligibility traces ; -DOM: SSB Q-learning as presented in Section 5, with probabilistic dominance, that is, purely ordinal feedback, φ ∈ {-1, 0, 1} ; -MAG: SSB Q-learning expressing preferences of different magnitudes, φ ∈ {-1000, -100, -10, 0, 10, 100, 1000}. Recall that SSB Q-learning only requires feedback on the relative quality of two extractions. We therefore defined the feedback given to DOM in our experiments as: f � DOM f � ⇔ φ DOM (f, f � ) = 1 iff (i) treatment f extracted an event and f � did not, or (ii) neither or both extracted an event, and f was faster than f � ; f ∼ DOM f � ⇔ φ DOM (f, f � ) = 0 iff both took approximately the same time, i.e., the treatments' total times were within margin seconds (parametrisable) of each other.

We thus encouraged the AI, in an arguably very natural manner, to extract events first, and to do so fast, or to recognise quickly that there are no events to extract. This relies on the correlation, demonstrated in Section 9 for Q-learning, between the ability to extract any event, and to extract the correct events. DOM also demonstrates this correlation. Obviously, this preference relation could be completed with additional information over the obtained results, such as the perceived quality of the extraction, etc.

For the MAG type of feedback, we emphasised the importance of extracting events, compared to the importance of extracting the exact target events, in turn compared to the importance of running fast. Intuitively, it is a middle ground between QL and DOM, which can be seen as a weighted form of probabilistic dominance. Yet such feedback remains quite natural. Precisely, we define: φ MAG (f, f � ) = 1000 iff f extracted an event and f � did not ; φ MAG (f, f � ) = 100 iff both extracted an event but f extracted an event of higher quality (as measured in Section 8) than f � ; φ MAG (f, f � ) = 10 iff both extracted an event of similar quality or neither extracted an event, but f was faster by margin seconds ; φ MAG (f, f � ) = 0 iff f and f � were incomparable with respect to the previous conditions. Of course, we expect QL to be more effective than MAG, and MAG to be more effective than DOM, as QL receives much more information than MAG, and MAG receives more than DOM. We however demonstrate in this section that MAG and DOM are perfectly realistic approaches in an industrial setting.

To measure the performance of all approaches, we ran them, initially untrained, on a set of 5 000 GTD documents (presented in the same order, and only seen once in all experiments) from which the "expert" chain can extract events. The available actions were given by choices from ten gazetteers, the services Tika, NGramJ, GATE, Geo, and STOP. We measured the quality of the treatment of each document as described in Section 7, and emphasise that the quality of the extraction was measured in the same manner for all approaches (including the "expert" chain), though the feedback given for the AIs to learn from was different. Obviously, as the AIs learned from scratch, we could not expect that the extraction was good from the start. Rather, we were interested in how fast a "good" policy was learnt (after seeing how many documents), and how good this policy was.

The stopping time threshold was set to 10 seconds and margin to 5. Both Q-learning and SSB Q-learning were run with α set as in [START_REF] Gilbert | Model-free reinforcement learning with skew-symmetric bilinear utilities[END_REF], i.e. decreasing as the number of visits to the current state / action pair grows.

We varied the other parameters to get a comprehensive set of results and measured the robustness to parameter choice in the following 36 combinations of tests: -algorithms QL, DOM, and MAG ; -EG parameter � divided by 2 after 2500 or after 1000 documents ; γ = 0.9 and γ = 1 ; λ = 0, λ = 0.95, and λ = 1.0.

Results

As we cannot show all 36 plots here, we give general comments about the results, showing interesting and representative curves. On each plot, we show the extraction quality of a particular approach (blue dotted line) against that of the "expert" chain (red solid line). We only consider the results for the documents for which the AI "exploited", i.e., followed its "best" policy for the whole treatment (which is why the red line varies between plots). For readability, we smooth the curve, taking averages on sets of 50 documents in the same order as they are treated.

QL gave excellent results, but proved quite sensitive to changing parameters. For both � reduction strategies, γ = 0.9 gave excellent results with λ = 0.95 (Figure 4e) where the AI learnt a "good enough" policy after only 250 documents, and a "expert"-like one after 1 200 documents. γ = 0.9 also gave very good results with λ = 0 (not shown). With γ = 0.9 and λ = 1, however, the results were mediocre, and with γ = 1 (for example, Figure 4f), the results were very bad regardless of λ: the AI learnt to STOP very early, suggesting a risk-adverse behaviour.

DOM, like QL, was sensitive to the choice of γ and λ. With γ = 0.9, the results were very bad for λ = 1 (not shown) and λ = 0.95 (Figure 4j). However, reasonably good results (not shown) were achieved with γ = 0.9, λ = 0 for the longer � reduction strategy, and with γ = 0.9, λ = 0 and γ = 0.9, λ = 0.95 for the shorter strategy. With γ = 1, the results were good to excellent, and Figure 4i shows the best results for γ = 1, λ = 1, which learnt a "good enough" policy after 1 000 documents and stabilises with an "expert"-like policy after 3 750. Note that we continued this run on a further 5 000 documents (not shown), and it stayed "expert"-like.

MAG proved robust to changes in parameters, quickly learning a "good enough" policy in every case. γ = 0.9, λ = 0.95 (Figure 4g) is particularly good, learning a "good enough" policy almost straight away, and improving rapidly by speeding up to out-perform the "expert" chain after 3 000 documents.

We also noticed that the AI was capable of improving on a chain which was already good (where the events were extracted correctly but which took a few seconds longer than the "expert" chain). It learnt to speed up, eventually matching the "expert" chain.

Finally, we noted that SSB Q-Learning sometimes learnt an "expert"-like policy but then the performance degrades. Even though the events are still well extracted, it starts taking too long (see Figures 4k and4l). The logs show that the AI learnt that passing through GATE from a given state gives a good reward, and if γ and λ are not correctly set, although it takes longer, it starts to prefer this action to stopping.

Summary

-We noted a slight improvement in the results with a faster reduction in � (every 1 000 documents vs every 2 500), that is, with less exploration overall. -QL can give excellent results, but is sensitive to parameter variation and depends on numerical feedback. -At the other extreme, DOM only requires purely ordinal feedback, and yet with the correct parameters is able to learn "expert"-like policies, proving to be a feasible approach. -MAG offers a good middle ground: it is quite robust to parameter choice, uses mostly intuitive feedback, and still learns a good to "expert"-like policy very quickly. All in all, the experiments demonstrate that it is feasible to automatically improve a document treatment chain, and even to learn one from scratch, in settings where very little or no numerical information is given.

Conclusion and future work

We modelled a document treatment chain which extracts events from web pages and other open source documents as a Markov Decision Process, and solved it using reinforcement learning. Our approach is not specific to a document treatment chain. It could be applied to any treatment where the component modules can be varied to change the result, so long as we can define the states in terms of the object being processed, and the actions in terms of those modules.

We developed an application BIMBO (Benefiting from Intelligent and Measurable Behaviour Optimisation) into which we can "plug" different algorithms, web services and models to measure their impact on the learning. We established that our approach gave good results with full numerical feedback, and evolved to a more realistic scenario by giving delayed, partial feedback. We then introduced further realism by integrating a reward function formalising naturally expressed user preferences, demonstrating that this still gives good results while requiring much less cognitive effort to define the feedback. Hence we showed that it is possible to have a self-improving treatment chain, which does not require intervention or tuning by a human user, and which collects its feedback in a non-intrusive manner, from analysts' habitual actions. Our work also evaluates, in an industrial context, the applicability of various algorithms and the impact of various parameters for important RL approaches, which is of independent interest. The next step is to make the chain more complex, by adding alternative services, expanding the state set, and introducing a wider range of input. We aim to show that the system is capable of continuously improving the chain, by building different chains for different types of input. For example, learning whether a document in French should be translated to make use of the GATE extractors in English, or if the original text should be passed to GATE directly and the French extractors used. Even with a more complex system, the calculation time should not be an obstacle with a Q-learning type algorithm, where the calculations are instantaneous at each time step.

FIGURE 2 -

 2 FIGURE 2 -Simplified XML of a WebLab resource mid-chain.

  FIGURE 3 -Percentage events extracted by the untrained AI in production simulation

Of course, any such extra information could be used by BIMBO to generalise over actions, for instance, or to build a prior model of the actions and states, but we leave this for future work.


Esther Nicart

Bruno Zanuttini

Bruno Grilhères

Fredéric Praca

Dora Q-Learning -making better use of explorations

Eligibility traces for Q-Learning(λ) [Watkins (1989), Peng (1996), Baird (1995), Cichosz (1995), Sutton & Barto (1998), Wang et al (2013), . . . ] (hereafter referred to as Q(λ)) record the stack of (state, action) pairs enacted during a learning episode, enabling any rewards observed to be back-propagated down the stack, thus speeding up learning.

In standard Q(λ), after an explore action, the eligibility trace is cut (reset to an empty stack), meaning that any good results found further on can take a long time to percolate back to the initial state. We present here Dora, an adaptation of Q(λ) which makes better use of results found when exploring, and therefore learns consistently faster.

In Dora, our aim is to avoid cutting the trace on an explore if possible. This idea is quite simple and natural, but to the best of our knowledge, it has not been developed like this before. We note that the principle of Dora could be argued to resemble that of experience replay [Long-Ji Lin, 1991], but Dora is not model-based, has fewer parameters, and consumes less memory, whilst still giving excellent results.

In both Q(λ) and Dora, whenever the algorithm chooses to explore in a given state s (that is, it tries an action a which does not currently have the greatest estimated Q-value Qt (s, •)) and ends up in a state s , earning an immediate reward r, we update, as usual, the Q-value of a in s using the temporal difference

δ t = r + γ max b Qt (s , b) -Qt (s, a), resulting in Qt+1 (s, a) = Qt (s, a) + α t (s, a)δ t .
Standard Q(λ) would clear the trace here, but with Dora, if the new experience now makes a a greedy action in s, that is if Qt+1 (s, a) ≥ max b Qt (s, b), we continue just as though a was an exploit in s (which in retrospect is the case). Precisely, we do not cut the trace and we back-propagate the temporal difference Qt (s, a) + α t (s, a)δ t -max b Qt (s, b). Only if Qt+1 (s, a) is still less than max b Qt (s, b), do we admit that a really was an explore, and clear the trace.

Observe that if a becomes a greedy action in s, not only do we back-propagate the temporal difference at time t, but we also keep the trace intact, enabling the propagation of results from further in the run back across this "explore" join. This is in sharp contrast with Q(λ), which does neither.

Experiments

We tested Dora against Q(λ) taking the average results over at least 50 runs. The discount value γ and the decay rate λ were both set to 0.9. We measured the quality of their learning by recording the evolution of the distance of their current value function V t from the optimal V * at each time-step. We measured this distance in three ways (where s 0 is the starting state) :

episodic-distance(V * , V t ) = |V * (s 0 ) -V t (s 0 )| ; infinite-distance(V * , V t ) = max s {|V * (s) -V t (s)|} ; and L 2 -distance(V * , V t ) = ( s (V * (s) -V t (s)) 2 ) 1/2 .
We first tested their comparative performance on randomly generated MDPs from 10 to 100 states, and 5 to 10 actions. The rewards for each couple (s, a) were integers generated randomly between 0 and 100, and the transitions unbounded. We observed that Dora consistently learnt faster than Q(λ) (e.g. Figure 1b), the larger the MDP, the more significant her advantage.

Intuitively, we thought that Dora should perform even better on "long thin" or "cliff-walk" MDPs with long trajectories, and lots of exploration potentially necessary to reach the goal (see Figure 1a), and indeed, we found that in this case, Dora significantly outperforms Q(λ) (Figure 1c), especially with a decreasing (Figure 1d).

Another natural baseline for assessing the efficiency of Dora is a naive version with no trace-clearing at all (even on explorations) as mentioned in Sutton & Barto (1998). We ran some preliminary experiments which

s 0 s 1 s 2 s m r = 100 × m a n a 0 , . . . , a n-1
a n a 0 , . . . , a n-1 ; p = 0.5 a 0 , . . . , a n-1 ; p = 0.5 (a) "Long thin" MDP (n actions, m states) with p(si, a1 . . . an-1, s0) = 0.5 and p(si, a1 . . . an-1, si) = 0.5 (zero reward) ; p(si, an, si+1) = 1.0. State sm is the only one to offer a reward of 100 × m suggest that on generic MDPs this gives much worse results than both Q(λ) and Dora. A more thorough investigation we leave for future work.

Ongoing Work

We plan to run experiments in a wider variety of settings, for example, with rewards which reduce the optimism rather than increase it, and with several optimal paths in a "long thin" MDP. We also conjecture that there are families of "long thin" MDPs for which we can prove that Dora learns exponentially faster than Q(λ) or other algorithms. Apart from the improved algorithm, we believe that such formal results would help gain insight into the interplay between exploration and back-propagation.

  FIGURE 1 -The "long thin" MDP, and a very small, but typical selection of the results comparing standard Q(λ) with Dora QL, showing their average distance from the optimal policy.

Acknowledgements

We wholeheartedly thank the reviewers for their thought-provoking questions and comments.