Iou-Jen Liu

Xingdi Yuan

Marc-Alexandre Côté

Pierre-Yves Oudeyer

Alexander G Schwing

Asking for Knowledge : Training RL Agents to Query External Knowledge Using Language

To solve difficult tasks, humans ask questions to acquire knowledge from external sources. In contrast, classical reinforcement learning agents lack such an ability and often resort to exploratory behavior. This is exacerbated as few present-day environments support querying for knowledge. In order to study how agents can be taught to query external knowledge via language, we first introduce two new environments: the grid-world-based Q-BabyAI and the text-based Q-TextWorld. In addition to physical interactions, an agent can query an external knowledge source specialized for these environments to gather information. Second, we propose the 'Asking for Knowledge' (AFK) agent, which learns to generate language commands to query for meaningful knowledge that helps solve the tasks. AFK leverages a non-parametric memory, a pointer mechanism and an episodic exploration bonus to tackle (1) irrelevant information, (2) a large query language space, (3) delayed reward for making meaningful queries. Extensive experiments demonstrate that the AFK agent outperforms recent baselines on the challenging Q-BabyAI and Q-TextWorld environments. The code of the environments and agents are available at https://ioujenliu.github.io/AFK.

Introduction

To solve challenging tasks, humans query external knowledge sources, i.e., we ask for help. We also constantly create knowledge sources (e.g., manuals), as it is often more economical in the long term than users exploring via trial and 1. Mary's toy is a green ball.

2. The green ball is in the blue chest.

3. I don't know.

4. The green key. error. Moreover, cognitive science research [START_REF] Maratsos | Children's questions: A mechanism for cognitive development: Commentary[END_REF][START_REF] Mills | Preschoolers use questions as a tool to acquire knowledge from different sources[END_REF][START_REF] Ronfard | Question-asking in childhood: A review of the literature and a framework for understanding its development[END_REF] showed that learning to ask questions and to interpret answers is key in a child's development of problem-solving skills. Consequently, we hypothesize that autonomous agents can address more complicated tasks if they can successfully learn to query external knowledge sources. For querying, it seems desirable to use some form of language. Not only does this allow to leverage existing knowledge sources built for humans, but also does it enable us to interpret the queries.

However, the literature to teach agents to query external knowledge sources via language is scarce. [START_REF] Nguyen | Help, anna! visual navigation with natural multimodal assistance via retrospective curiosity-encouraging imitation learning[END_REF] consider agents that can request help in visual navigation tasks. The agent can issue a 'help' signal, and expects the environment to provide an instruction leading it to a place towards the goal. Hence, agents learn when to query, but do not have control of what to query. [START_REF] Zhong | Rtfm: Generalising to novel environment dynamics via reading[END_REF] show that agents can better address novel tasks when a manual is available. However, the manual contains all relevant information and agents don't need to learn to query. [START_REF] Kovac | Benchmarking socio-cognitive abilities in deep reinforcement learning agents[END_REF] discuss the open challenge of building agents that learn social interaction skills mixing physical action and language. They show that state-of-the-art deep reinforcement learning systems cannot learn several kinds of social interaction skills. Instead of social skills, we focus on the open challenge of learning to ask for knowledge using language and propose an effective approach.

To deliberately study how agents can be taught to You see a closed fridge. You can make out an oven. Look over there! a counter. The counter is wooden. However, the counter, like an empty counter, has nothing on it. Oh! Why couldn't there just be stuff on it? You can see a stove query, we introduce two environments: the grid-worldbased Q-BabyAI, illustrated in Fig. 1 and inspired by BabyAI [START_REF] Chevalier-Boisvert | A platform to study the sample efficiency of grounded language learning[END_REF], and the text-based Q-TextWorld inspired by TextWorld [START_REF] Côté | Textworld: A learning environment for text-based games[END_REF]. In addition to physical interactions, an agent can use a query language to gather information related to a task. Importantly, in Q-BabyAI and Q-TextWorld, the knowledge source is designed to be task-agnostic, i.e., it replies to all queries, even if irrelevant to the task at hand. This mimics many realworld knowledge sources, e.g., search engines, which return results based on a user's query, regardless of relevance.

When training agents to query external knowledge via language, three main challenges arise: (1) The action space for generating a language query is large. Even with a template language, the action space grows combinatorially and large action spaces remain a challenge for reinforcement learning [START_REF] Dulac-Arnold | Deep reinforcement learning in large discrete action spaces[END_REF][START_REF] Ammanabrolu | Graph constrained reinforcement learning for natural language action spaces[END_REF]. ( 2) Irrelevant knowledge queried from a task-agnostic knowledge source can confuse agents. As a result, learning to ask meaningful questions is critical. This challenge is in line with the cognitive science finding [START_REF] Mills | Preschoolers use questions as a tool to acquire knowledge from different sources[END_REF] that children must learn to ask questions that result in answers with useful information. (3) Rewards for queries are often significantly delayed and sparse. Since the knowledge source provides specific information rather than a solution, agents have to also understand how to use the acquired information before receiving a significant reward. This mimics the discovery of [START_REF] Mills | Preschoolers use questions as a tool to acquire knowledge from different sources[END_REF] that children must learn to use the received information.

To address the three challenges, we propose the 'asking for knowledge' (AFK) agent. The AFK agent is equipped with a pointer mechanism and a non-parametric memory, which we refer to as a 'notebook,' while using an episodic exploration strategy. The pointer mechanism addresses the challenge of a combinatorially growing action space by restricting the available actions based on the current context. The notebook keeps track of all the information related to the task at hand. The episodic exploration strategy deals with delayed and sparse rewards by issuing an exploration bonus when the agent makes novel and meaningful queries, inspired by information-seeking and epistemic curiosity observed in children [START_REF] Engel | Children's need to know: Curiosity in schools[END_REF][START_REF] Gottlieb | Information-seeking, curiosity, and attention: computational and neural mechanisms[END_REF][START_REF] Kidd | The psychology and neuroscience of curiosity[END_REF].

Comparing this AFK agent to recent baselines on Q-BabyAI and Q-TextWorld, we observe the AFK agent to ask more meaningful questions and to better leverage the acquired knowledge to solve the tasks.

Queryable Environments

We first discuss a reinforcement learning (RL) context where agents can query. We then introduce two new environments, Q-BabyAI and Q-TextWorld, each expanded from prior work [START_REF] Chevalier-Boisvert | A platform to study the sample efficiency of grounded language learning[END_REF][START_REF] Côté | Textworld: A learning environment for text-based games[END_REF].

Problem Setting

Reinforcement learning considers an agent interacting with an environment and collecting reward over discrete time. The environment is formalized by a partially observable Markov Decision Process (POMDP) [START_REF] Sutton | Reinforcement Learning: An Introduction[END_REF]. Formally, a POMDP is defined by a tuple (S, A, Z, T , O, R, γ, H). S is the state space. A is the action space. Z is the observation space. At each time step t, the agent receives an observation o t ∈ Z following the observation function O ∶ S → Z and selects an action a t ∈ A. The transition function T maps the action a t and the current state s t to a distribution over the next state s t+1 , i.e., T ∶ S × A → ∆(S). The agent receives a real-valued reward r t according to a reward function R ∶ S × A → R. The agent's goal is to maximize the return ∑ H t=0 γ t r t , where γ is the discount factor and H is the horizon.

In a queryable environment, in addition to observations representing its surrounding, an agent also receives a response from the knowledge source upon issuing a query. Formally, the observation space Z = Z env × Z q is composed of Z env and Z q , representing the agent's surrounding and the reponse to a query, respectively.

Similarly, at each step, the agent's action space A = A phy ∪ A q is composed of the physical action space A phy supported by classical RL environments (e.g., navigational actions, toggle, grasp) and the query action space A q .

Response Space Z q and Query Action Space A q : As a controllable starting point for this research, we equip the environments with a queryable oracle knowledge source. Specifically, whenever receiving a sequence of tokens as a query, the oracle replies with a sequence of tokens. To consider the compositionality of language while reducing the burden of precise natural language generation, we define a template format for queries and responses. This design is also compatible with our plan of extending the knowledge source to more natural forms like databases.

A query is defined as a 3-tuple of <func, adj, noun>.

In this 3-tuple, func is a function word selected from words like where's, what's and how's, which indicates the function of a query (e.g., inquire about an object's location or affordances). The combination of an adjective (adj) and a noun enables to refer to a unique object within the environment.

Given a query, the oracle replies with a sequence of tokens. For this, the oracle has access to a set of "knowledge facts" associated with a particular instantiation of the environment.

The knowledge facts are key-value pairs, where keys are the aforementioned 3-tuple of <func, adj, noun> and values are sequences of tokens. If a given query matches a key in the set of knowledge facts, the oracle will return the corresponding value. Otherwise, the oracle returns the message I don't know.

Crucially, the set of knowledge facts is much larger than necessary and irrelevant information is, by design, accessible to the agent. For instance, when tasked to find Mary's toy, information about Tim and Tim's toy is also available if queried. Gathering irrelevant information may lead to confusion and subsequent sub-optimal decisions. Moreover, some tasks require multi-hop information gathering (e.g., Object in Box), in which the agent must ask follow-up questions to get all information needed to solve it.

Information Sufficiency: Practically, agents that can query have two main advantages. First, for environments containing sufficient information to be solved via exhaustive exploration, querying can provide a more natural and effective way to gather information (e.g., reducing the policy length). Second, for environments that only provide partial information (e.g., an agent must recognize and avoid danger tiles by trial-and-error, but danger tiles are randomly assigned per episode), only querying will lead to successful completion of the tasks.

To study both advantages, we augment BabyAI [START_REF] Chevalier-Boisvert | A platform to study the sample efficiency of grounded language learning[END_REF] and TextWorld [START_REF] Côté | Textworld: A learning environment for text-based games[END_REF] with a queryable knowledge source. We design tasks where the environment contains sufficient information, but we add knowledge facts which can help the agent to reduce exploration if used adequately. In addition, we design other tasks where agents can only succeed when they are able to query. We provide details next.

Q-BabyAI

We first introduce Q-BabyAI, an extension of the BabyAI environment [START_REF] Chevalier-Boisvert | A platform to study the sample efficiency of grounded language learning[END_REF]. We devise four level 1 tasks, namely Object in Box, Danger, Go to Favorite and Open Door. In Fig. 2, we provide examples of agents querying the knowledge source for each of the level 1 tasks after receiving the goal instruction for that episode. The four tasks permit to study the two advantages mentioned above.

Specifically, both the Object in Box and Danger tasks can only be solved 100% of the time when querying is used to reveal the necessary knowledge -opening the wrong box or stepping on the danger tile terminates the game. In contrast, for the Go to Favorite and Open Door tasks, an agent can exhaust the environment to accomplish the goals. However, querying the knowledge source can greatly boost the agent's efficiency in both tasks. To prevent agents from memorizing solutions (e.g., Mary's toy is in the red box), we randomly place objects and tiles in the environment, as well as shuffle the entity names and colors in every episode.

For the Object in Box and Danger tasks, we use a singleroom setting to separate the difficulties of navigation and querying. In the Go to Favorite and Open Door tasks, we use a multi-room setting. It is worth noting that in the Open Door task, only querying at specific locations (i.e., next to doors) can result in meaningful answers.

Having the four level 1 tasks defined, we increase the diffi- culty by composing them into more challenging higher-level tasks. For level k tasks, we combine k different tasks selected from the four level 1 tasks. As a result, we have six level 2 tasks, four level 3 tasks and one level 4 task. As an example, Open Door + Object in Box is a level 2 task where the instruction could be Find the key to the door, and find Mary's toy. To solve the task, an agent must figure out what is Mary's toy, where it is, and which key opens the locked door. We provide full details of the Q-BabyAI tasks including statistics in Appendix A.1.

Q-TextWorld

We also develop Q-TextWorld, augmenting the TextWorld environment [START_REF] Côté | Textworld: A learning environment for text-based games[END_REF] with a queryable knowledge source. Given a few configuration parameters, Q-TextWorld can generate new text-based games on the fly. Those interactive text environments are POMDPs with text-only observations and action space. Agents interact with the game by issuing short text phrases as actions, then get textual feedback. Text-based games provide a different view from their vision-or grid-based counterparts that can make things harder: 1) states are represented by highly abstracted signals requiring language understanding to interpret correctly; 2) the action space is combinatorially large due to compositionality of language; 3) levels of verbosity, i.e., amount of irrelevant text, can potentially confuse an agent.

In this work, we adopt the cooking themed setting from prior work [START_REF] Adhikari | Learning dynamic belief graphs to generalize on text-based games[END_REF]. An example is shown in Fig. 2. In all games, an agent must gather cooking ingredients, which are placed randomly in the room, either visible to the agent, or hidden inside some containers that need to be opened first. In a more difficult setting, each ingredient also needs to be cut in a specific way (i.e., chopped, sliced, or diced). The agent must query the knowledge source to obtain that information and then act accordingly by issuing the right action while holding both the ingredient and a knife. We provide full details of the Q-TextWorld tasks including statistics in Appendix A.2.

Being consistent with the Q-BabyAI tasks, we study both advantages of having a querying behavior -improve efficiency and acquire necessary information. In games where cutting is not involved, agents can rely on exhaustive exploration to gather all portable objects and win. However, knowing what and where the required ingredients are can improve efficiency significantly. In contrast, in games where the ingredients need to be cut, an incorrect operation on the ingredient terminates the game. Hence, querying the recipe is the only way to perform above random.

Asking for Knowledge (AFK) Agent

In this section, we first present an overview of the 'Asking for Knowledge' (AFK) agent before we discuss details.

Overview: As illustrated in Fig. 3, the goal of the agent is to solve a task specified by an instruction. The language-based instruction (sequence of tokens) v 0 is provided at the start of each episode. At each time step t, the agent receives an environment observation o env t ∈ Z env . Moreover, if the agent issued a query at time step t -1, it also receives a language response v t ∈ Z q from the oracle, otherwise v t = ∅.

To reduce the amount of noisy information (i.e., v t unrelated to the task at hand), we develop a non-parametric memory for gathered information, which we refer to as a 'notebook.' The notebook is a collection of sets where related information are being combined into a single set. The AFK agent only looks at the set that contains the task instruction v 0 , which determines relevance to the task. Upon processing the notebook we obtain a representation h s (details in Sec. 3.1).

We combine the environment observation o env t and the notebook representation h s relevant for the task via an aggregator module [START_REF] Perez | Film: Visual reasoning with a general conditioning layer[END_REF][START_REF] Vaswani | Attention is all you need[END_REF]. Given the output of the aggregator, h x ∈ R l , where l is the encoding size, we use five heads to generate the physical actions and the language query actions. Specifically, we use a switch head π switch (⋅|h

x ) ∶ R l → ∆({0, 1}), a physical action head π phy (⋅|h x ) ∶ R l → ∆(A phy ), a func- tion word head: π func (⋅|h x ) ∶ R l → ∆(V func ), an adjec- tive head π adj (⋅|h x ) ∶ R l → ∆(V adj ), and a noun head π noun (⋅|h x ) ∶ R l → ∆(V noun ).
Here, ∆(X) represents a distribution with support X, A phy is the physical action space, and V func , V adj , V noun are the function word, adjective, and noun vocabulary spaces.

The switch head decides whether the agent executes a physical action or issues a query. Conceptually, the agent first samples a value z according to π switch (⋅|h x ). If z = 0, the agent will sample a physical action a phy from π phy (⋅|h x ) which is subsequently executed. In contrast, if z = 1, the agent will issue the query [w func , w adj , w noun ] by sampling a function word w func , an adjective w adj , and a noun w noun independently from π func (⋅|h x ), π adj (⋅|h x ), and π noun (⋅|h x ). Note that the query action space A q is large, which makes RL training challenging. We provide detailed statistics in Appendix A.

To alleviate issues due to the large action space, we adopt a pointer network [START_REF] See | Get to the point: Summarization with pointer-generator networks[END_REF] to generate queries. Specifically, the pointer network is restricted to 'point' to words occurring in the notebook. This ensures that the generated query uses words that are related to the already gathered information (details in Sec. 3.2).

In addition, to deal with delayed and sparse rewards, we propose an episodic exploration method which further incentivizes an agent to ask questions that are related to the task at hand (details in Sec. 3.3).

Notebook

In the following, we discuss the notebook's construction and describe the computation of the encoding h s .

Notebook construction: Let F (for facts) denote the notebook, which is a non-parametric memory. Formally, F is a set of disjoint sets, i.e., F = {A i } |F |-1 i=0 and A i ∩ A j = ∅, ∀i ≠ j. For each set A i , each element v ∈ A i represents either a response from the oracle or the task instruction.

At the beginning of each episode, the notebook F is initialized with a singleton A 0 = {v 0 } that contains the task instruction v 0 , i.e., F = {{v 0 }}. When an agent receives a new response v i ≠ ∅, we first find all sets that contain information related to v i in the notebook. Formally, we construct an index set S that consists of the indices of related sets, i.e., S = {j|∃v ∈ A j s.t. Sim(v i , v) ≥ α}, where Sim(u, v) ∈ [0, 1] is a similarity function and α ∈ [0, 1] is a threshold. We study both the uni-gram and bi-gram similarity [START_REF] Kondrak | N-gram similarity and distance[END_REF]. If S is not empty, we combine all the related sets and the new response v i to obtain a new set

A k . Formally, A k = ⋃ j∈S A j ∪ {v i }, where k = min j∈S j.
Then, all sets {A j } j∈S are replaced with the new set A k . If the index set S is empty, we add A k = {v i } to F , where k is the next available index. Importantly, note that the task instruction v 0 is always part of the set A 0 .

Notebook encoding: To discard noisy information coming from responses unrelated to the task at hand, the AFK agent only considers the set A 0 which contains the task instruction v 0 . We use a recurrent neural network f note [START_REF] Cho | Learning phrase representations using RNN encoder-decoder for statistical machine translation[END_REF] to encode each 'note' in A 0 , i.e., for each

v i ∈ A 0 (i ∈ {1, . . . , |A 0 |}), we have h i = f note (v i ) ∈ R |v i |×l ,
where |v i | is the number of words in v i and l is the hidden dimension. To further encode the instruction related notes (i.e., A 0 ) as a whole, we use a Deep Set model f set [START_REF] Zaheer | Deep sets[END_REF], i.e.,

h s = f set ([h 1 , . . . , h |A 0 | ]) ∈ R l ,
where h s is the resulting encoding. In addition, the input observation o env is encoded via a neural network f obs , i.e.,

h o = f obs (o env ) ∈ R l
, where h o is the resulting observation

encoding. An aggregator module is used to combine h o and h s , i.e.,

h x = f att (h o , h s ) ∈ R l .

Pointer Mechanism for Language Generation

To address the challenge of a combinatorially growing action space, we develop a pointer mechanism for the policies π adj and π noun . Concretely, the pointer mechanism restricts the AFK agent queries to use only the words appearing in the set A 0 .

We achieve this by first applying a mask before computing the policy distributions π adj and π noun , i.e., π adj and π noun only have non-zero probability for adjectives and nouns in the instruction related set of notes A 0 . We use the generation process of the noun as an example. Let m noun denote the number of nouns in A 0 , and let h w ∈ R m noun ×l denote the word encodings of all nouns in A 0 . Using attention queries q ∈ R l and keys k ∈ R m noun ×l such that

q = h x ⋅ W q , and k = h w ⋅ W k , (1)
with learnable parameters W q , W k ∈ R l×l , we compute the attention e noun over all nouns in A 0 as

e noun = softmax(q ⋅ k T ) ∈ R m noun . (2)
A distribution over the noun vocabulary, i.e., V noun , is then constructed from e noun . Specifically, for each word w ∈ V noun , we have

π noun (w) = ∑ m noun i=1 e i noun I[d(i) = w]
, where d(i) maps the index i to the corresponding word in A 0 and e i noun represents the i-th element of e noun . I is the indicator function. The pointer mechanism for π adj is constructed similarly. We defer details to Appendix C.

Episodic Exploration

To deal with delayed and sparse rewards, inspired by [START_REF] Savinov | Episodic curiosity through reachability[END_REF], we develop an episodic exploration mechanism to encourage the agent to ask questions related to the task at hand. At each time step, the agent receives reward r = r env + b, where r env is the external reward and b is the bonus reward.

A positive bonus reward b is obtained whenever a query's response v i ≠ ∅ expands the agent's knowledge about the task, i.e., A 0 . The reward is only given for new information.

Formally,

b = β(I[(v i ∈ A 0 ) ∧ (v i ∉ A ′ 0 )]), (3)
where v i denotes a new response returned by the oracle, and A ′ 0 denotes the set from the previous game step containing the task instruction v 0 . β > 0 is a scaling factor and I is the indicator function.

Experimental Results

In this section, we present the experimental setup, evaluation protocol, and our results on Q-BabyAI and Q-TextWorld.

Experimental Setup: We adopt the publicly available BabyAI and TextWorld code released by the authors 1,2 as our non-query baseline system, denoted as No Query. We consider a vanilla query agent [START_REF] Kovac | Benchmarking socio-cognitive abilities in deep reinforcement learning agents[END_REF]) (Query Baseline), in which query heads are added to the baseline agent to generate language queries. We refer to the pro- posed agent via AFK, which is the agent with 1) notebook, 2) pointer mechanism, and 3) episodic exploration.

We follow the original training protocols used in BabyAI and TextWorld. Specifically, we train all agents in Q-BabyAI environments with proximal policy optimization (PPO) [START_REF] Schulman | Proximal policy optimization algorithms[END_REF] for 20M -50M environment steps, depending on the tasks' difficulty. For Q-TextWorld agents, we use the Deep Q-Network [START_REF] Mnih | Playing atari with deep reinforcement learning[END_REF][START_REF] Hessel | Rainbow: Combining improvements in deep reinforcement learning[END_REF] and the agents are trained for 500K episodes.

We provide implementation details in Appendix C.

Evaluation Protocol: In Q-BabyAI, the policy is evaluated in an independent evaluation environment every 50 model updates and each evaluation consists of 500 evaluation episodes. has to be queried. This demonstrates that the AFK agent asks more meaningful questions and successfully leverages oracle replies to solve tasks. We provide extra analysis to support this in a later subsection. In addition, we observe that in tasks where the instruction provides sufficient information, e.g., Go to Favorite (♦) and Open Door (♥), all agents are able to solve the tasks. However, as shown in Tab. 2, an AFK agent needs fewer steps to solve the tasks. This suggests that meaningful queries can result in better efficiency. Training curves are shown in Fig. 4. See Appendix E for training curves and results of all experiments.

To show the limitation of the proposed approach, we run experiments on the very challenging level 3 and level 4 tasks of Q-BabyAI. As shown in Tab. 1, AFK as well as all baselines fail to solve the level 3 and level 4 tasks due to the tasks' high complexity and very sparse rewards. This shows that training RL agents to query in language is still a very challenging and open problem which needs more attention from our community.

Q-TextWorld Results: We compare AFK with the baseline agents on Q-TextWorld in Tab. 3. Specifically, we conduct experiments on four settings with gradually increasing difficulty. Here, 'Take k' denotes that an agent needs to collect k food ingredients, which may spawn in containers and are hence invisible to the agent before the container is opened. 'Cut' indicates that the collected food ingredients need to be cut in specific ways, for which the recipe needs to be queried. As shown in Tab. 3, AFK significantly outperform the baselines on three of the tasks. Analogously to Q-BabyAI experiments, the No Query agent sometimes outperforms the Query Baseline agent. We believe this is caused by 1) the larger action space of the Query Baseline compared to No Query, and 2) a missing mechanism helping the agent to benefit from queries -together they reduce the Query Baseline's chance to experience meaningful trajectories. We observe that none of the agents can get non-zero scores on the Take 2 Cut task. We investigate the agents' training reward curves (Fig. 10, Appendix E): while the baselines get 0 reward, AFK actually learns to obtain higher reward. We suspect that due to the richer entity presence in Q-TextWorld, and the resulting larger number of valid questions (connected to A 0 ), AFK may exploit the exploration bonus and ask more questions than necessary. This suggests that better reward assignment methods are needed for agents to perform in more complex environments.

Ablation Study:

We perform an ablation study to examine the effectiveness of the proposed 1) notebook, 2) pointer mechanism, and 3) episodic exploration. For this, we use various level 1 and level 2 Q-BabyAI tasks. The results are reported in Tab. 4. As shown in Tab. 4, removing the notebook, the pointer mechanism, or the episodic exploration results in the success rate dropping by 22.9%, 11.4%, and 25.2% on average. This demonstrates that all three proposed components are essential for an AFK agent to successfully generate meaningful queries and solve tasks.

Generalization: To assess an AFK agent's capability of making meaningful queries and solving different, novel, unseen tasks, we perform a generalization study. Specifically, we train AFK agents on a set of level 2 source tasks. Then the trained AFK agent is tested on an unseen level 2 target task (new combination of sub-tasks used in training). The results are summarized in Tab. 5. As shown in Tab. 5, upon training on source tasks, an AFK agent achieves 22.1% and 35.6% success rate on the level 2 target tasks 'Object in Box + Danger'(♣♠) and 'Danger + Go to Favorite'(♠♦), which the agent has never seen during training. In contrast, the Query Baseline only achieves a 0.0% and 0.2% success rate on the target tasks after training 20M steps directly on the target tasks (Tab. 1).

Query Quality: To gain more insights, we study the quality of the queries issued by an agent. Each episode of our tasks is associated with a set of queries Q t which are useful for solving the task. If an agent issues a query q ∈ Q t , the query is considered 'good.' We refer to the number of good queries (not counting duplicates) and total number of queries (counting duplicates) generated by the agent in one episode as n g and n tot . We report the average precision, recall, and F1 score [START_REF] Sasaki | The truth of the f-measure[END_REF] of the generated queries over 200 evaluation episodes. Specifically, precision =

n g n tot , recall = n g |Q t |
, and F1 score is the harmonic mean of precision and recall. As shown in Tab. 6, the AFK agent achieves high F1 scores across various tasks. In contrast, the Query Baseline converges to a policy that does not issue any query and thus has zero precision and recall in all tasks. This demonstrates AFK's ability to learn to ask relevant questions.

Related Work

Information Seeking Agents: In recent years a host of works discussed building of information seeking agents. [START_REF] Nguyen | Help, anna! visual navigation with natural multimodal assistance via retrospective curiosity-encouraging imitation learning[END_REF] propose to leverage an oracle in 3D navigation environments. The oracle is activated in response to a special signal from the agent and provides a language instruction describing a subtask the agent could follow. [START_REF] Kovac | Benchmarking socio-cognitive abilities in deep reinforcement learning agents[END_REF] design grid-world tasks similar to ours, but focus on the social interaction perspective. For instance, some agents are required to emulate their social peers' behavior to successfully communicate with them. [START_REF] Potash | Playing log (n)-questions over sentences[END_REF] propose a game setting which requires agents to ask sequences of questions efficiently to guess the target sentence from a set of candidates. Yuan (2021); [START_REF] Nakano | Webgpt: Browser-assisted question-answering with human feedback[END_REF] propose agents that can generate sequences of executable commands (e.g., Ctrl+F a token) to navigate through partially observable text environments for information gathering. The line of research on curiosity-driven exploration and intrinsic motivation shares the same overall goal to seek information (Oudeyer et al., 2007;Oudeyer & Kaplan, 2007). A subset of them, countbased exploration methods, count the visit of observations or states and encourage agents to gather more information from rarely experienced states [START_REF] Bellemare | Unifying Count-Based Exploration and Intrinsic Motivation[END_REF][START_REF] Ostrovski | Count-based exploration with neural density models[END_REF][START_REF] Savinov | Episodic curiosity through reachability[END_REF][START_REF] Liu | Cooperative Exploration for Multi-Agent Deep Reinforcement Learning[END_REF]. Our work also loosely relates to the active learning paradigm, where a system selects training examples wisely so that it achieves better model performance, while also consuming fewer training examples [START_REF] Cohn | Improving generalization with active learning[END_REF][START_REF] Bachman | Learning algorithms for active learning[END_REF][START_REF] Fang | Learning how to active learn: A deep reinforcement learning approach[END_REF]. Different from existing work, we aim to study explicit querying behavior using language. We design tasks where querying behavior can either greatly improve efficiency or is needed to succeed.

In a concurrent work, [START_REF] Nguyen | Learning When and What to Ask: a Hierarchical Reinforcement Learning Framework[END_REF] propose a framework tailored to 3D navigation environments: agents can query an oracle to obtain useful information (e.g., current state, current goal and subgoal). They show that navigation agents can take advantage of an assistance-requesting policy and improve navigation in unseen environments.

Reinforcement Learning with External Knowledge:

Training reinforcement learning agents which use external knowledge sources also received attention recently [START_REF] He | Reinforcement learning with external knowledge and two-stage q-functions for predicting popular reddit threads[END_REF][START_REF] Bougie | Deep reinforcement learning boosted by external knowledge[END_REF][START_REF] Kimura | Reinforcement learning with external knowledge by using logical neural networks[END_REF][START_REF] Argerich | Tutor4rl: Guiding reinforcement learning with external knowledge[END_REF][START_REF] Zhong | Rtfm: Generalising to novel environment dynamics via reading[END_REF] [START_REF] Nogueira | Task-oriented query reformulation with reinforcement learning[END_REF][START_REF] Buck | Ask the right questions: Active question reformulation with reinforcement learning[END_REF]. Another loosely related area is multi-hop retrieval [START_REF] Das | Go for a walk and arrive at the answer: Reasoning over paths in knowledge bases using reinforcement learning[END_REF][START_REF] Xiong | Answering complex open-domain questions with multihop dense retrieval[END_REF][START_REF] Feldman | Multi-hop paragraph retrieval for open-domain question answering[END_REF], where a large scale supporting knowledge source is involved and systems must gather information in a sequential manner. Inspired by these works, we leverage properties of language such as compositionality, to help form a powerful query representation that is manageable by RL training.

Limitations and Future Work

In this section, we conclude by discussing limitations of this work and future directions.

Environments: As an initial attempt to study agents that learn to query knowledge sources with language, we settled on oracle-based knowledge sources. This ensures better experimental controllability and reproducibility. However, it can be improved in multiple directions.

1. Beyond the use of hand-crafted key-value pairs as the knowledge source, a set of more realistic knowledge sources can be considered. For instance, databases can be queried using similar template language [START_REF] Zhong | Seq2sql: Generating structured queries from natural language using reinforcement learning[END_REF]; an information retrieval system or a pretrained question answering system can be used to extract knowledge from large scale language data [START_REF] Lewis | Question and answer test-train overlap in open-domain question answering datasets[END_REF][START_REF] Borgeaud | Improving language models by retrieving from trillions of tokens[END_REF]; a search engine is naturally queryable [START_REF] Nakano | Webgpt: Browser-assisted question-answering with human feedback[END_REF]; pre-trained language models can be queried via prompt engineering [START_REF] Huang | Language models as zero-shot planners: Extracting actionable knowledge for embodied agents[END_REF]; humans can also be a great knowledge source [START_REF] Kovac | Benchmarking socio-cognitive abilities in deep reinforcement learning agents[END_REF].

2. The query grammar can be extended to be more natural and informative (e.g., Where's Mary's toy and where can I find it?).

3. We plan to include tasks that require non-linear reasoning. This will further decrease agents' incentive to memorize an optimal trajectory, and presumably increase generalizability.

Agent design: For agents, future directions include:

1. When the state space is large (e.g., in Q-TextWorld), agents sometimes keep on querying different question to exploit the exploration bonus. This demands a better reward assignment strategy, since agents performing in more complex environments may encounter this issue too.

2. It is worth exploring other structured knowledge representations [START_REF] Ammanabrolu | Graph constrained reinforcement learning for natural language action spaces[END_REF] and parametric memories [START_REF] Weston | Memory networks[END_REF][START_REF] Munkhdalai | Metalearned neural memory[END_REF] beyond the notebook we used.

3. Asking questions essentially serves to reduce entropy. One could further use exploration strategies that maximize information gain [START_REF] Houthooft | Vime: Variational information maximizing exploration[END_REF].

Overall, we are excited by the challenges and opportunities posed by agents that are able to learn to query external knowledge while acting in their environments. We strive to call attention from researchers for the development of agents capable of querying external knowledge sourceswe believe this is a strong and natural skill. We make an initial effort towards this goal, which hopefully can be proven to be valuable and helpful to the community. The general statistics of Q-BabyAI tasks are summarized in Tab. 7. The statistics for each individual Q-BabyAI task are summarized in Tab. 8, where |Q t | represents the number of 'good queries' an agent should make to solve a task efficiently. 'Early Terminate' indicates that an episode will be terminated if the agent makes a mistake, e.g., stepping on a danger zone or opening the wrong box. In addition, we present the details of the four basic Q-BabyAI tasks in the following. Otherwise, it doesn't receive any reward.

A. Environment and Task Details

Object in

Danger ♠: There are different colors of tiles in the environment. One of the colors represents the danger zone.

The episode terminates if the agent steps on a danger zone. The instruction is avoid danger zone, and go to the green target square. However, the agent doesn't know what color represents the danger zone. Therefore, to safely reach the target square and receive rewards, the agent must ask the oracle for information on the danger zone. Importantly, the color of the danger zone differs from episode to episode.

Go to Favorite ♦:

There are nine rooms in the environment. The instruction is Go to <name>'s favorite toy, where <name> and <name>'s favorite toy are sampled from a set of names and a set of toys at the start of each episode. There are irrelevant objects scattered around the environment. To solve the task efficiently, the agent should issue queries to figure out what and where is the referred toy. Note, if the agent doesn't ask any question, it can still solve the task, but in a much less efficient manner, i.e., by exhaustively searching all rooms for the referred toy. The agent receives positive reward when it goes to the referred toy.

Open Door ♥: There are three keys and one door in the environment. One of the three keys could open the door. The agent needs to find the right key and open the door to complete the task and receive a positive reward. The instruction is Find the key to the door. Note, the agent could still complete the task without asking any question, i.e., by exhaustively trying all keys.

A.2. Q-TextWorld

For all games, the objective is to find cooking ingredients which are randomly hidden throughout the kitchen. Once found, those ingredients may require some processing depending on the task difficulty. Once all required ingredients are in the player's inventory and processed the right way, the game terminates with a reward of 1. We provide statistics of the Q-TextWorld environment in Tab. 9 and a transcript of a game can be seen in Fig. 5.

Take [1/2]: In this task, the player has to find 1 or 2 ingredients mentioned in the instruction. Ingredients are either

Tasks |Q t | # of rooms room size Early Terminate Lv. 1 ♣ 3 1 9×9 True ♠ 1 1 7×7 True ♦ 2 9 5×5 False ♥ 1 2 7×7 False Lv. 2 ♣♠ 5 2 7×7 True ♣♦ 4 9 5×5 True ♣♥ 5 2 7×7 True ♠♦ 3 2 7×7 True ♠♥ 2 2 7×7 True ♦♥ 4 9 5×5 False Lv. 3 ♣♠♦ 5 2 7×7 True ♣♠♥ 6 3 7×7 True ♣♦♥ 5 9 5×5 True ♠♦♥ 4 3 7×7 True Lv. 4 ♣♠♦♥ 7 9 7×7 True
Table 8. Statistics of each task in Q-BabyAI. ♣: Object in Box, ♠: Danger, ♦: Go to Favorite, ♥: Open Door.

Instruction: You find yourself at friend's house and you are both hungry! Collect some parsley to prepare a delicious meal. Ask Charlie to know where to find each ingredient and for the recipe directions.

Description: You are in a kitchen. A messy kind of place.

You see a closed fridge. You can make out an oven. Look over there! a counter. The counter is wooden. However, the counter, like an empty counter, has nothing on it. Oh! Why couldn't there just be stuff on it? You can see a stove. The stove appears to be empty. You see a griller. Is this what you came to TextWorld for? This... griller?

There is a cookbook on the floor.

Inventory: You are carrying: a knife. visible to the agent right from the start (e.g., on the table), or hidden inside some container that needs to be opened first (e.g., in the fridge). The player can ask the oracle where it can find a particular object (e.g., Ask Charlie 3 where's hot pepper?). In return, the oracle will indicate where the object can be found (e.g., Hot pepper is in the fridge.).

Take [1/2] + Cut: This task extends Take [1/2] as the ingredients also need to be cut in the right way (i.e., chopped, sliced, or diced). Each cutting type is achieved by a different action command (i.e., chop X, slice X, or dice X) while the player is holding a knife in their inventory.

The player can also ask the oracle how to process a particular ingredient (e.g., Ask Charlie how to cut the hot pepper? (2019), we use a gated recurrent unit (GRU) [START_REF] Chung | Empirical evaluation of gated recurrent neural networks on sequence modeling[END_REF] to perform word encoding. Specifically, for each v i ∈ A 0 , we have

h i = f gru (v i ) ∈ R |v i |×l , where |v i | is
the number of words in v i and l = 128 is the encoding dimension.

Aggregator (f att ): Following the No Query baseline [START_REF] Chevalier-Boisvert | A platform to study the sample efficiency of grounded language learning[END_REF], the aggregator consists of FiLM [START_REF] Perez | Film: Visual reasoning with a general conditioning layer[END_REF] modules, f FiLM , followed by a long short term memory (LSTM) f LSTM [START_REF] Hochreiter | Long short-term memory[END_REF]. That is, f att = f LSTM • f FiLM . Specifically, we stack two FiLM modules. Each FiLM module has 128 filters with size 3 × 3 and the output dimension is 128.

The LSTM has 128 units.

Physical

Action and Query Heads (π switch , π phy , π fun , π adj , π noun ): The switch head π switch , physical action head π phy , and function word head π fun are two-layer MLPs with 64 units in each layer. The output dimension of π switch , π phy , π fun are 2, 7, 2. π adj and π noun are single-head pointer networks (Sec. 3.2) with hidden dimension l = 128.

B.2. AFK-Q-TextWorld

Text Encoder (f obs , f note ): Due to the nature of the Q-TextWorld environment, where all inputs are in pure text, we share the two encoders (i.e., f obs and f note ) in our text agent.

We use a transformer-based text encoder, which consists of an embedding layer and a transformer block [START_REF] Vaswani | Attention is all you need[END_REF]. Specifically, we tokenize an input sentence (either a text observation or an entry in the notebook) with the spaCy tokenizer. 5 We convert the sequence of tokens into 128-dimensional embeddings, the embedding matrix is initialized randomly. We apply a residual connection on top of the multi-head attention mechanism in order to maintain the original information contained in P . Specifically,

h P Q = Tanh(Linear([P Q ; P ])), (4)
where

h P Q ∈ R |P |×H , brackets [⋅; ⋅] denote vector con- catenation.
We denote the above attention layer as

P Q = Attention(P, Q). (5)
Using two of such layers (without sharing parameters), we aggregate three inputs: h obs,task = Attention(h obs , h task ),

h obs ∈ R |obs|×H , h task ∈ R
h x = Attention(h obs,task , h s ). (6)
Here,

h obs,task ∈ R |obs|×H , h x ∈ R |obs|×H .
Action Generator (π func , π adj , π noun ): In Q-TextWorld, all actions follow the same format of <func, adj, noun>.

Therefore, the query action space A q and the physical action space A phy are shared (i.e., the vocabularies are shared). We use a three-head module to generate three vectors. Their sizes correspond to the function word, adjective, and noun vocabularies. The generated vectors are used to compute an overall Q-value.

Taking the aggregated representation h x ∈ R |obs|×H as input, we first compute its masked average, using the mask of the text observation. This results in h s ∈ R H .

Specifically, the action generator consists of four multi-layer perceptrons (MLPs):

h shared = ReLU(Linear shared (h s )), Q func = Linear func (h shared ), Q adj = Linear adj (h shared ), Q noun = Linear noun (h shared ). (7)
Here,

Q func ∈ R |func| , Q adj ∈ R |adj| , Q noun ∈ R |noun| .
|func|, |adj|, and |noun| denote the vocabulary size of function words, adjectives, and nouns.

In order to alleviate the difficulties caused by a large action space, similar to the pointer mechanism in the Q-BabyAI agent, we apply masks over vocabularies when sampling actions. In the masks, only tokens appearing in the current notebook are labeled as 1, i.e., the text agent only performs physical interaction with objects noted in its notebook. It also only asks questions about objects it has heard of.

Finally, we compute the Q-value of an action <u, v, w>:

Q <u,v,w> = (Q u + Q v + Q w )/3, (8)
where u, v and w are tokens in the function word, adjective, and noun vocabulary.

C. Implementation Details

In this section, we provide implementation and training details of our agents. In Appendix C.1, we provide implementation details for our agent used for the Q-BabyAI environments. In Appendix C.2, we provide implementation details for our agent used for the Q-TextWorld environments.

C.1. AFK-Q-BabyAI

We closely follow the training procedure of the publicly available code of the BabyAI No Query agent [START_REF] Chevalier-Boisvert | A platform to study the sample efficiency of grounded language learning[END_REF]. We train our AFK and all baselines with PPO [START_REF] Schulman | Proximal policy optimization algorithms[END_REF]. Specifically, we use the Adam [START_REF] Kingma | A method for stochastic optimization[END_REF] optimizer with learning rate 0.0001. We update the model every 2560 environment steps. The batch size is 1280. The PPO epoch is 4 and the discount factor is 0.99. We use 64 parallel processes for collecting data from the environment. The scaling factor β of the episodic exploration bonus is set to 0.1 for all experiments. For all experiments, we study uni-gram and bi-gram similarity models and report the better results. We tuned the episodicexploration scaling factor β ∈ {0.001, 0.01, 0.1, 0.5}, hidden size of the pointer network l ∈ {32, 64, 128, 256}, learning rate ∈ {10 -5 , 10 -4 , 10 -3 }, and similarity function ∈ {uni-gram, bi-gram}. We train all agents with 5 different random seeds: [24,42,123,321,3407].

C.2. AFK-Q-TextWorld

We adopt the training procedure from the official code base released by TextWorld authors [START_REF] Côté | Textworld: A learning environment for text-based games[END_REF]. Our text agent is trained with Deep Q-Learning [START_REF] Mnih | Playing atari with deep reinforcement learning[END_REF]. We use a prioritized replay buffer with memory size of 500, 000, and a priority fraction of 0.5. During model update, we use a replay batch size of 64. We use a discount factor γ = 0.9. We use noisy nets, with a σ 0 of 0.5. We update the target network after every 1000 episodes. We sample the multi-step return n ∼ Uniform [1,3]. We refer readers to [START_REF] Hessel | Rainbow: Combining improvements in deep reinforcement learning[END_REF] for more information about different components of DQN training.

For all experiments, we use Adam [START_REF] Kingma | A method for stochastic optimization[END_REF] as the optimizer. The learning rate is set to 0.00025 with a clip gradient norm of 5. We train all agents with 5 different random seeds: [24,42,123,321,3407]. For replay buffer data collection, we use a batch size of 20. We train our agents with 500K episodes, each episode has a maximum number of steps 20. After every 2 data collection steps, we randomly sample a batch from the replay buffer, and perform a network update.

Resources: We use a mixture of Nvidia V100, P100 and P40 GPUs to conduct all the experiments. On average, experiments on Q-BabyAI take 1 day, experiments on Q-TextWorld take 2 days.

D. Additional Results

Success rate and episode length: In Tab. 10 we report success rate and episode length of No Query, Query Baseline, and AFK on all levels of Q-BabyAI tasks. Note, due to the early termination mechanism, the comparison of episode length is only meaningful when the agent is able to solve the task. For instance, in Object in Box (♣) and Danger (♠), No Query and Query Baseline have shorter episode length than AFK because they either step on the danger tile or open the wrong box, resulting in the termination of an episode.

Number of queries made by an AFK agent in seen and unseen tasks: To better understand the agent's behavior in seen and unseen tasks, we report the number of queries an agent made across 500 evaluation episodes. As shown in Fig. 6 (left), when an agent is trained and evaluated on the same tasks (♣♠), in most episodes, the agent makes four queries, which is the optimal number of queries of the task. In contrast, when the agent is trained and evaluate on different tasks, Fig. 6 (right), it made more queries.

E. Training Curves

The training curves of all Q-BabyAI and Q-TextWorld experiments in terms of success rate and episode length are shown in Fig. 7

Figure 1 .

 1 Figure 1. Proposed Q-BabyAI. Here the agent has to query the knowledge source to succeed.

  Avoid danger zone, and go to the green square Go to Jack's favorite toy Find the key, and open the blue door Agent navigates to the blue door Collect some hot pepper to prepare a delicious meal. Ask Charlie to know where to find each ingredient and for the recipe directions. Agent wins when it uses green key to open the blue door Agent wins when it moves to the green ball Agent wins when it moves to the green square without stepping onto yellow tiles Agent wins when it grasps the blue ball Agent wins when sliced hot pepper is in its inventory Agent navigates to green key… Agent navigates to grey box… Agent navigates to green square… Agent navigates to green ball… … You are in a kitchen. A messy kind of place.

JackFigure 2 .

 2 Figure2. Querying interactions in Q-BabyAI and Q-TextWorld. We illustrate standard physical interactions as gray colored stage directions and highlight the questions (green) and oracle replies (blue) upon receiving the instruction (red).

Figure 3 .

 3 Figure 3. An overview of the AFK agent. An embedding of the notebook (h s ; see Sec. 3.1) and the environment (h o ) is combined (h x ) for use in five policy functions. The policies for query generation make use of notebook information (h w ) (see Sec. 3.2).

  Box ♣: There are two suitcases in the environment. Each suitcase contains one toy. The instruction is find <name>'s toy, where <name> is sampled from a set of names at the start of each episode. However, the agent doesn't know what is the referred toy. Neither does it know the content of each suitcase. The episode terminates when a suitcase is opened by the agent. Therefore, the agent needs to ask multiple question to figure out what the desired toy is and which suitcase to open. If the opened suitcase contains the desired toy, the agent receives a positive reward.

  Notebook: {"You find yourself . . . for the recipe directions."} Action 1: ask Charlie where's the parsley Feedback: The parsley is in the oven. Notebook: {"You find yourself . . . for the recipe directions.", "The parsley is in the oven.ask Charlie how to cut the parsley Feedback: The parsley needs to be sliced. Use a knife to cut it. Notebook: {"You find yourself . . . for the recipe directions.", "The parsley is in the oven.", "The parsley needs to be sliced. Use a knife to cut it."} Action 5: slice parsley Feedback: Sliced. Done after 5 steps. Score 1/1.

Figure 5 .

 5 Figure 5. An excerpt from a Q-TextWorld game.

  |task|×H and h s ∈ R |note|×H , where |obs|, |task| and |note| denote the number of tokens in a text observation, the number of tokens in the instruction, and the number of nodes in the notebook:

Figure 6 .

 6 Figure 6. Evaluation episode count over number of queries. Left: train on ♣♠, evaluate on ♣♠. Right: train on ♠♦+♦♣, evaluate on ♣♠. ♣: Obj. in Box, ♠: Danger, ♦: Go to Favorite.

  , Fig. 8, Fig. 9, Fig. 10, and Fig. 11.

Figure 7 .Figure 8 .Figure 11 .

 7811 Figure 7. Success rate of AFK and baselines on Q-BabyAI.

Table 1 .

 1 Success

		Tasks	No Query	Query Baseline	AFK (Ours)
		♣	50.5±2.0	49.8±1.2	100.0±0.0
	Lv. 1	♠ ♦	68.3±2.4 98.9±0.8	73.8±1.2 99.3±0.3	100.0±0.0 100.0±0.0
		♥	99.7±0.3 85.3±22.3	100.0±0.0
		♣♠	0.0±0.0	0.0±0.0	90.3±1.8
		♣♦	0.1±0.1	0.6±0.5	94.3±2.3
	Lv. 2	♣♥ ♠♦	0.0±0.0 0.4±0.1	0.0±0.0 0.2±0.2	99.0±0.4 100.0±0.0
		♠♥	0.0±0.0	0.0±0.0	0.0±0.0
		♦♥	84.1±0.3	94.0±3.3	98.7±0.2
		♣♠♦	0.0±0.0	0.0±0.0	0.15±0.2
	Lv. 3	♣♠♥ ♣♦♥	0.0±0.0 0.0±0.0	0.0±0.0 0.0±0.0	0.0±0.0 2.1±0.8
		♠♦♥	4.3±1.0	4.4±0.8	4.8±0.9
	Lv. 4 ♣♠♦♥	0.0±0.0	0.0±0.0	0.0±0.1
	Tasks No Query Query Baseline AFK (Ours)
	♦	30.2±1.5	26.7±1.5	16.8±6.7
	♥	26.2±0.9	36.8±1.0	20.6±0.2

rate (%) on Q-BabyAI. ♣: Object in Box, ♠: Danger, ♦: Go to Favorite, ♥: Open Door.

Table 2 .

 2 Number

of steps required to solve a task. ♦: Go to Favorite, ♥: Open Door.

Table 3 .

 3 Success rate (%) on Q-TextWorld.

	Task		No Query Query Baseline AFK (Ours)
	Take 1	75.1±4.1	73.5±5.8	85.1±2.9
	Take 2	24.0±6.6	13.7±8.5	61.9±6.5
	Take 1 Cut	24.6±1.0	22.9±3.6	43.5±15.9
	Take 2 Cut	0.0±0.0	0.0±0.0	0.0±0.0
	Task	AFK w/o Notebook	AFK w/o Pointer Mechanism	AFK w/o Episodic Exploration	AFK (Ours)
	♣	50.0±0.8	49.4±0.7	49.8±0.7	100.0±0.0
	♠	99.1±0.2	100.0±0.0	93.8±0.7	100.0±0.0
	♦	99.2±0.4	99.7±0.2	99.3±0.2	100.0±0.0
	♥	85.1±1.0	100.0±0.0	77.8±0.7	100.0±0.0
	♣♥	48.5±1.9	90.5±1.4	50.0±1.8	99.0±0.4
	Mean	76.4	87.9		74.1	99.8

1 BabyAI: github:mila-iqia/babyai 2 TextWorld: github:xingdi-eric-yuan/qait public

Table 4 .

 4 Ablation

Study. Success rate (%) on Q-BabyAI. ♣: Object in Box, ♠: Danger, ♦: Go to Favorite, ♥: Open Door.

Table 5 .

 5 The final metric is the average evaluation success rate of the last ten models in the training process, i.e., average success rate of the last 5000 evaluation episodes. In Q-TextWorld, we report the final running average training scores with a window size of 1000. Note, in each episode, entities are randomly spawned preventing agents from memorizing training games. All experiments are repeated five times with different random seeds. Training curves of AFK, non-query baseline, query baseline on Q-BabyAI (left) and Q-TextWorld (right). Zero-shot generalization study of AFK.

				Danger				Obj in Box + Open Door				Take 2					Take 1 Cut
	Avg. Succ. Rate	0.0 0.2 0.4 0.6 0.8 1.0																			AFK Query Base No Query
		0.0	0.5	1.0 Env. Steps	1.5	2.0 1e7	0.0	0.5	1.0 Env. Steps	1.5	2.0 1e7	0	1	2 Episodes 3	4	5 1e5	0	1	2 Episodes 3	4	5 1e5
		Figure 4. Target Task Source Tasks Succ. (%) Eps. Len.
		♣♠		♠♦+♦♣	22.1±0.7	32.0±0.3
		♠♦		♠♣+♦♣	35.6±2.1	71.6±1.1
		Task |Q t | Precision Recall	F1
		♣♥		5	0.804		0.823 0.812
		♦♥		4	0.771		0.560 0.601
		♠♦		3	0.989		0.989 0.989

To ensure a fair and rigorous evaluation, we follow the evaluation protocols suggested by

[START_REF] Henderson | Deep reinforcement learning that matters[END_REF]

;

[START_REF] Colas | Decoupling exploration and exploitation in deep reinforcement learning algorithms[END_REF]

and report the 'final metric'.

Q-BabyAI Results:

We first compare our AFK agent with baselines on all level 1 and level 2 tasks of Q-BabyAI. The final metrics and standard deviation of average evaluation success rate are reported in Tab. 1. As shown in Tab. 1, for level 1 and level 2 tasks, the AFK agent achieves significantly higher success rates than the baselines, particularly in Object in Box (♣) and Danger (♠) where information

Table 6 .

 6 Query quality of AFK.

♣: Object in Box, ♠: Danger, ♦: Go to Favorite, ♥: Open Door.

Table 7 .

 7 Statistics of the Q-BabyAI environment.

	General information
	Word vocabulary size	62
	Function word vocabulary size (|V func |) 2
	Adjective vocabulary size (|V adj |)	22
	Noun vocabulary size (|V noun |)	24
	# of Physical action	7
	Visual range	7 × 7
	# of object colors	6
	# of actionable object types	4
	# of names	2
	# of danger zone colors	2

A.1. Q-BabyAI

Table 9 .

 9 Statistics of the Q-TextWorld environment. The first convolutional layer has 128 filters of size 8 × 8 and stride 8. The second and third convolutional layers have 128 filters of size 3 × 3 and stride 1. Batch normalization and ReLU unit are applied to the output of each layer. At the end, a 2D pooling layer with filter size 2 × 2 is applied to obtain the representation h o of 256 dimensions.Word Encoder (f note ): Following Chevalier-Boisvert et al.

		General information
	Word vocabulary size	835
	# Function word (|V func |)	7
	# Adjective (|V adj |)	38
	# Noun (|V noun |)		45
	# holders			6
	# ingredients		42
	# cuttable ingredients	26
			Take 1
	# recipes			42
	# configurations		1242
	Avg. instruction length	33.75 ± 0.44
	Avg. walkthrough length	1.49 ± 0.50
	Avg. nb. entities		8.63 ± 0.96
	Avg. observation length	150.94 ± 65.43
	Avg. valid actions per step 4.90 ± 1.29
			Take 2
	# recipes			1722
	# configurations		1332156
	Avg. instruction length	36.48 ± 0.60
	Avg. walkthrough length	3.01 ± 0.70
	Avg. nb. entities		10.69 ± 1.22
	Avg. observation length	141.76 ± 57.56
	Avg. valid actions per step 5.83 ± 1.65
			Take 1 Cut
	# recipes			17576
	# configurations		1026
	Avg. instruction length	33.80 ± 0.40
	Avg. walkthrough length	2.50 ± 0.50
	Avg. nb. entities		9.37 ± 0.84
	Avg. observation length	143.00 ± 59.30
	Avg. valid actions per step 5.45 ± 1.70
			Take 2 Cut
	# recipes			274625000
	# configurations		859620
	Avg. instruction length	36.61 ± 0.55
	Avg. walkthrough length	5.00 ± 0.71
	Avg. nb. entities		11.67 ± 1.13
	Avg. observation length	138.59 ± 50.04
	Avg. valid actions per step 7.73 ± 2.54
	B.1. AFK-Q-BabyAI
	Observation	Encoder	(f obs ):	Following
	BabyAI (Chevalier-Boisvert et al., 2019), the envi-
	ronment observation o	env of Q-BabyAI is a 7 × 7 × 4
	symbolic observation that contains a partial and local
	egocentric view of the environment and the direction of
	the agent. To encode o	env , we use a convolutional neural
	network (CNN). Following Chevalier-Boisvert et al. (2019),
	the observation encoder consists of three convolutional
	layers.

  , where |o| denotes the number of tokens in o, the encoder produces a representation h o ∈R|o|×H , with H = 128 the hidden size.In practice, we use mini-batches to parallelize the training. Following standard NLP methods, we use special padding tokens when the number of tokens within a batch are different, we use masks to prevent the model from taking the padding tokens into computation. A text input o will be associated with a mask m o ∈ R |o| .Note for all the three agent variants (i.e., No Query, Query Baseline and AFK), we use the concatenation of [feedback, description, inventory] as the input to f obs . See examples of feedback, description and inventory text in Fig.5.[START_REF] Vaswani | Attention is all you need[END_REF]. Specifically, we use P as the query, Q as the key and value. This results in an output P Q ∈ R |P |×H , where at every time step i ∈ [0, |P |),

	Aggregator (f att ): To aggregate two input encodings P ∈ R |P |×H and Q ∈ R |Q|×H , we use the standard multi-head
	attention mechanism (P i Q is the weighted sum of Q, the weight is the attention
	of P	i on Q. We refer readers to Vaswani et al. (2017) for
	detailed information.
		The transformer block consists of a stack of 4 convolutional
		layers, a self-attention layer, and a 2-layer MLP with a
		ReLU non-linear activation function in between. Within the
		block, each convolutional layer has 128 filters, with a kernel
		size of 7. The self-attention layers use a block hidden size
		of 128, with 4 attention heads. Layer normalization (Ba
		et al., 2016) is applied after each layer inside the block. We
		merge positional embeddings into each block's input.
		Given an input o ∈ R

|o|

Table 10 .

 10 Evaluation success rate and episode length on Q-BabyAI. ♣: Object in Box, ♠: Danger, ♦: Go to Favorite, ♥: Open Door.

			No Query	Query Baseline	AFK (Ours)
		Tasks	Succ.(%) Eps. Len. Succ.(%) Eps. Len.	Succ.(%)	Eps. Len.
		♣	50.5±0.6	5.9±0.1	49.8±1.1	6.0±0.1	100.0±0.0	10.8±0.1
	Lv. 1	♠ ♦	68.3±0.8 98.9±0.4 30.2±1.5 99.3±0.2 26.7±1.5 100.0±0.0 8.2±0.0 73.8±0.9 8.3±0.1 100.0±0.0	10.4±0.0 16.8±6.7
		♥	99.7±0.2 26.2±0.9 85.3±1.1 36.8±1.0 100.0±0.0	20.6±0.2
		♣♠	0.0±0.0	43.3±0.7	0.0±0.0	44.1±0.6	90.3±1.8	15.5±0.3
		♣♦	0.1±0.1 224.8±0.4 0.6±0.5 224.3±0.5 94.3±2.3	18.8±0.3
	Lv. 2	♣♥ ♠♦	0.0±0.0 0.4±0.1	98.0±0.0 90.8±1.3	0.0±0.0 0.2±0.2	98.0±0.0 91.4±1.1 100.0±0.0 99.0±0.4	32.3±0.6 14.5±0.0
		♠♥	0.0±0.0	76.8±2.1	0.0±0.0	79.5±1.7	0.0±0.0	79.0±0.9
		♦♥	10.8±1.6 202.9±4.0 10.2±2.1 203.2±5.1 98.7±0.2	66.9±3.2
		♣♠♦	0.0±0.0	91.8±1.1	0.0±0.0	92.2±0.6	0.15±0.2	85.8±1.4
	Lv. 3	♣♠♥ ♣♦♥	0.0±0.0 0.0±0.0 225.0±0.0 0.0±0.0 225.0±0.0 93.9±3.4 0.0±0.0 102.5±3.5	0.0±0.0 2.1±0.8	109.4±2.3 220.9±1.1
		♠♦♥	4.3±1.0	99.3±2.9	4.4±0.8	97.7±3.0	4.8±0.9	105.0±2.0
	Lv. 4 ♣♠♦♥ 0.0±0.0	96.6±8.1	0.0±0.0 150.5±7.5	0.0±0.1	177.2±9.2

). In return, the oracle will indicate which type of cutting is needed (e.g., Hot pepper needs to be sliced, use a knife to cut it). Note, in the reported games, the player always start with a kitchen knife in their inventory.B. Modeling DetailsIn this section, we provide detailed information regarding our agents. In Appendix B.1, we describe our agent used for the Q-BabyAI environments. In Appendix B.2, we describe our agent used for the Q-TextWorld environments.3 In Q-TextWorld, the oracle is named Charlie.4 Nonessential words can be omitted, e.g., Ask Charlie how hot pepper?

https://spacy.io/

Acknowledgement

This work is supported in part by Microsoft Research, the National Science Foundation under Grants No. 1718221, 2008387, 2045586, 2106825, MRI #1725729, NIFA award 2020-67021-32799, and AWS Research Awards.

Appendix: Asking for Knowledge : Training RL Agents to Query External Knowledge Using Language

The appendix is structured as follows:

1. In Sec. A, we provide the details of each task in Q-BabyAI and Q-TextWorld.

2. In Sec. B, we provide the model details of our AFK agent.

3. In Sec. C, we provide the implementation and training details for the AFK agent.

4. In Sec. D, we provide additional experimental results on Q-BabyAI.

5. In Sec. E, we provide training curves for all experiments on Q-BabyAI and Q-TextWorld.

The Python code of Q-BabyAI, Q-TextWorld, the AFK agent and all baselines are available at https://ioujenliu. github.io/AFK.


Sébastien Bigaret
email: sebastien.bigaret@telecom-bretagne.eu

Patrick Meyer
email: patrick.meyer@telecom-bretagne.eu

diviz: an MCDA workflow design, execution and sharing tool

Keywords: algorithmic MCDA workflows, open-source software, method comparison

The diviz software is a tool for designing, executing and sharing Multiple Criteria Decision Aid (MCDA) techniques. The target user community of diviz reaches from researchers who require to construct algorithmic workflows from elementary MCDA components to teachers who need to present MCDA methods and let their students experiment them. Besides, one of the principal features of diviz is to ease the comparison of results results issued from different methods on the same decision problem. This allows among others to check the robustness of the output of a decision aid process with respect to the choice of the decision aid technique.

INTRODUCTION

Research activities in and around the field of Multiple Criteria Decision Aid have developed quite rapidly over the past years, and they have resulted in various streams of thought and methodological formulations for the resolution of complex decision problems. In particular, many so-called MCDA methods have been proposed in the literature and are very often available as software programs.

Unfortunately, at least four major difficulties arise when it comes to using these procedures in practice:

1. Different techniques are generally implemented in separate software products, with heterogeneous user interfaces;

2. Testing multiple MCDA algorithms on one problem instance is not easy, because of the various input data formats required by the software applications;

3. A lot of MCDA algorithms which are presented and published in scientific articles are not easily available and consequently often only used by their authors;

4. Several MCDA software products are not free (neither from a financial, nor from an open-source point of view), which can be considered as a weakness for their large dissemination.

In other scientific research fields, as, e.g., statistics or data mining, there exist software platforms which allow to easily compare different analysis methods and to test them on a given dataset inside a common framework. Among the most famous ones, one can cite platforms such as the GNU R statistical system (R [START_REF] Development | R: A language and environment for statistical computing[END_REF] or the Weka suite of machine learning software [START_REF] Hall | The WEKA Data Mining Software: An Update[END_REF].

Both of these suites are open-source and OS independent, which has certainly contributed to their large dissemination and acceptance among many researchers and users.

The diviz software is one of the initiatives of the Decision Deck1 project and is developed at the LUSSI department of Télécom Bretagne in France. Its essential purpose is to overcome the main difficulties of the current software situation in MCDA research mentioned above. diviz is an open-source software which allows to design complex workflows2 of MCDA algorithms in a very intuitive way and to execute them. One of the key characteristics of these executions is that they are performed via web-services on distant servers.

In this article, we present diviz, its properties and its latest developments in Section 2. Then, in Section 3 we detail its use on a well-known example from the literature. Finally, we conclude in Section 4 and present the perspectives of diviz.

DESCRIPTION AND PROPERTIES OF DIVIZ

The diviz tool is an easy to use software to build, execute and share complex workflows of MCDA algorithms. In the literature, such workflows are often called methods (consider, e.g., the ELECTRE method [START_REF] Roy | Classement et choix en présence de points de vue multiples (la méthode ELECTRE)[END_REF], the UTA method (Jacquet-Lagrèze and Siskos, 1982), etc). diviz enables to conveniently combine programs implementing MCDA algorithms, which can originate from various methodological schools, researchers and programmers.

In this section we present the main features of diviz and show how it allows to rebuild classical MCDA methods, to develop new ones by combining various elementary calculation components3 , and how it can be used as a research and dissemination tool.

Workflow design

The design of the MCDA workflows is performed via an intuitive graphical user interface, where each algorithm is represented by a box which can be linked to data files or supplementary calculation elements by connectors. Thus, the design of complex algorithmic workflows does not require any programming skills, but only necessitates to understand the functioning of each calculation module.

The inputs and outputs of these elementary components can be manifold and are typed. To illustrate this, consider the following example.

Example: diviz allows to use a component called weightedSum. This element calculates the weighted sum of alternatives' profiles with respect to a set of weights associated with a list of criteria. Consequently, weightedSum requires four inputs: the description of the criteria (at least their ids), the description of the alternatives (at least their ids), the performance table containing the numerical evaluation of each alternative on each of the criteria and the set of numerical weights associated with the criteria. The main output of this component is a list of alternatives' ids associated with the weighted sum of their evaluations. Note that we present later further details on the data typing.

To construct a new MCDA workflow, the user chooses one or more modules from a list of available calculation elements which he can drag and drop in a dedicated workspace. Then he adds data files to the workspace and connects them appropriately to the inputs of the elements. Finally he connects the inputs and outputs of the components by connectors to define the structure of the workflow.

Execution and results

Once the design of the MCDA workflow is finished, it is possible to execute it in order to obtain the possibly multiple outputs of the algorithms. In diviz, these calculations are performed on computing servers through the use of web-services4 published by the Decision Deck project. The idea behind these web-services is to allow anyone who is connected to the Internet to access a large amount of MCDA algorithms without having to install them on their personal computer. As a consequence, diviz does not contain any algorithmic modules, but requires a connection to the Internet to access the calculation resources.

If the execution of the workflow is successful, the outputs of each of the components can be viewed and analysed by the user. Some of these outputs might represent results of intermediate calculation steps of the decision aid workflow which has been built by the user. This allows to help to tune the parameters of the algorithms as shown in the following example.

Example: Consider the following workflow (typically a UTA-like disaggregation method): a first module determines piecewise linear value functions on basis of a ranking of alternatives provided by the user; a second module transforms a performance table by applying these value functions on the performances of the alternatives; a third module calculates the sum of these performances for each of the alternatives; a fourth module draws a ranking of the alternatives on basis of the overall value previously computed. The intermediary results are the value functions, the transformed performance table and the overall values of the alternatives. As each of these elements is explicitly available for the user, first he can gain a deeper understanding of the decision aid method which he has constructed, and second the fine-tuning of the input parameters is facilitated.

Among other things, this enables to check and validate the robustness of the output of a decision aid process with respect to the choice of the decision aid technique and the input parameters.

Furthermore, the history of the past executions is kept in diviz and can be viewed by the user. In particular, if a workflow is modified, the former executions' results and their associated workflows are still available. Again this is a key feature which helps calibrating the parameters of the algorithms which are used in a workflow, as any past execution can be recalled and reanalysed.

Available algorithmic components

As already mentioned earlier, the algorithmic elements are available in diviz via web-services. At the time of writing, there are 32 components present which are divided into 4 main categories:

1. calculation components containing aggregation operators, disaggregation techniques, analysis elements, etc.;

2. methods containing full MCDA methods;

3. visualization components containing modules allowing to represent graphically certain input and output data elements;

4. reporting components containing techniques to create aggregated reports of multiple output data pieces.

Currently diviz contains, among many others, functions from the kappalab library [START_REF] Grabisch | Non additive measure and integral manipulation functions[END_REF] which can be used for Choquet integral-based MCDA, disaggregation techniques based on outranking relations [START_REF] Bisdorff | Inverse analysis from a Condorcet robustness denotation of valued outranking relations[END_REF] and additive value functions (ACUTA, [START_REF] Bous | ACUTA: A novel method for eliciting additive value functions on the basis of holistic preference statements[END_REF], as well as the SMAA method [START_REF] Lahdelma | SMAA -Stochastic multiobjective acceptability analysis[END_REF]. A detailed list of all available components can be found on the website of diviz5 .

Note that at the time of writing, various researchers of the Decision Deck project are working on the implementation of MCDA techniques in view of publishing them as web-services which can then be accessed from diviz. In particular, classical methods like the ELECTRE [START_REF] Roy | Classement et choix en présence de points de vue multiples (la méthode ELECTRE)[END_REF]) and PROMETHEE [START_REF] Brans | A preference ranking organization method[END_REF] series will be available soon. This should lead to a high interest in the diviz software and the web-services offered by Decision Deck.

XMCDA: the key to interactions and data visualization

One of the key points of diviz is the possibility to combine various MCDA algorithms originating from heterogeneous researchers in complex workflows. To facilitate this interoperability, the Decision Deck project suggests to use a data standard called XMCDA6 to store the inputs and outputs of MCDA programs. The XMCDA markup language is written in XML, a general-purpose syntax for defining markup languages.

It follows that the web-services proposed by Decision Deck accept data written according to XMCDA and generate data in this same format.

In diviz this has three direct consequences:

• first, all components available in diviz can interoperate. Typically, the output of one algorithm can be injected into other elementary modules without requiring data transformations; • second, the inputs and the outputs of the elementary components in diviz are typed with respect to the different data types defined in XMCDA. This allows a very precise control of the various algorithms, and facilitates the creation of complex combinations of components;

• third, we exploit a powerful feature of XML based markup languages to convert XMCDA documents into HTML pages for a convenient visualisation of their contents in a web browser integrated in diviz.

"Methods" comparison

Next to designing and executing MCDA workflows, diviz can also be a convenient tool to compare the outputs of various methods on the same input data. Up to now, such a task has been far from easy, as no unified software platform for MCDA techniques existed. However, with diviz and its possibility to construct complex workflows, it is easy to connect a set of data to various workflows in a single workspace, each representing a different MCDA method, and to compare their outputs. Again, this is an interesting feature to check the robustness of the output of an analysis with respect to the choice of the decision aid technique.

Workflow sharing

The diviz software enables to export any workflow, with or without the data, as an archive. The latter can then be shared with any diviz user, who can then import it (by loading the archive) into his software and continue the development of the workflow or execute it on the original data.

Consequently, diviz can be used as a dissemination tool in combination with a research article. Indeed, the authors of a new MCDA technique could propose the corresponding diviz workflow together with an appropriate data set as supplementary electronic material with their article. This would certainly contribute to a larger dissemination of new MCDA algorithms and facilitate their acceptance among many researchers.

A quick look at the architecture Technically speaking, diviz is a classical 3-tier application made of: the client which has been described in this section, a component accessing the Decision Deck web-services, and a server. The diviz server's main task consists in planning and controlling the execution of the submitted workflows, making it possible for different components in the workflow to be executed in parallel, when appropriate. diviz users download the client only; the latter connects to the server which takes care of distributing the computations to the dedicated web-services; it gathers all intermediary and final results which are ultimately sent back to the user.

APPLICATION

In this section, we illustrate the use of diviz on a classical MCDA problem which has been widely discussed in the literature, namely the choice of a sports car (Bouyssou et al., 2000, chapter 6). Let us briefly recall the main features of this example and the underlying data.

In 1993, Thierry, a student aged 21, is passionate about sports cars and wishes to buy a middle range 4 years old car with a powerful engine. He selects five viewpoints related to cost (criterion l), performance of the engine (criteria 2 and 3) and safety (criteria 4 and 5). The list of alternatives and their evaluations on these five criteria is presented in Table 1. The cost criterion (€) and the performance criteria acceleration (seconds) and pick up (seconds) have to be minimised, whereas the safety criteria brakes and road-hold have to be maximised. Note that the values of the latter two criteria are average evaluations obtained from multiple qualitative evaluations which have been re-coded as integers between 0 and 4. Further details on these data can be found in (Bouyssou et al., 2000, chapter 6). As done in (Bouyssou et al., 2006, chapter 7), we suppose that Thierry has already some knowledge about the 14 cars, and that he is able to express the following ranking on a few of them:

P309-16 ≻ Sunny ≻ Galant ≻ Escort ≻ R21t.
To present the use of diviz, we detail the construction of a variant of UTA [START_REF] Bous | ACUTA: A novel method for eliciting additive value functions on the basis of holistic preference statements[END_REF] named ACUTA to determine a preference model that will allow us to evaluate the 14 cars and to rank them. The screenshot of the corresponding workflow is given in the upper part of Figure 1 below (area 1).

The workflow contains 7 elementary components, including the one implementing the ACUTA method.

For short, ACUTA determines piecewise linear partial value functions on basis of an input ranking of a subset of alternatives, compatible with an additive value model. Consequently, the ACUTAR module requires as inputs the description of the alternatives and the criteria, a performance table evaluating each alternative on the criteria, a ranking of a subset of alternatives, the preference directions on the values of the criteria and the number of segments of each piecewise linear value function. One of the outputs of this component is a description of a set of compatible value functions with the input ranking.

These value functions are then used by computeNormalisedPerformanceTable to transform the original performance table into a normalized version, where all the evaluations of the alternatives are in the real unit interval.

The generalWeightedSum module is used to calculate the aggregated value of each of the alternatives of the performance table by a simple sum. This output is then plotted in a bar chart via the plotAlternativesValues component. Finally, the component plotNumericPerformanceTable is used to graphically represent the normalized version of the performance table, plotValueFunctions is used to plot the value functions outputted by the ACUTAR module, and the rankAlternativesValues module is used to obtain the ranks of the alternatives according to their overall values.

On Figure 2, we show the output of plotAlternativesValues, where we can observe that alternative a11(P309-16) obtains the highest overall value.

Besides, on the output of plotNumericPerformanceTable on Figure 3, one can easily understand why a11 scores so well. Each bar represents an alternative, whose evaluations for the 5 criteria are stacked up. The partial values of a11 for the various criteria are generally very good, which produces by summation a high overall value.

Finally, on Figure 4, one can observe the preference model (via the partial value functions) of Thierry based on the ranking of the few alternatives. Clearly, the cost criterion (g1) has the biggest influence in his choice and Thierry has a preference for cars which cost less than 18000€.

These outputs (as well as many other results) can easily be viewed in diviz in an associated viewer window.

Let us now exploit the flexibility of diviz in order to compare these results with the output of a much simpler MCDA technique, namely the weighted sum. This workflow is drawn in the lower part of Figure 1 (area 2).

The 3 components computeNormalisedPerformanceTable, generalWeightedSum and rankAlternativesValues are used for this aggregation. In order to normalise the data of the performance table, we divide the performances on each of the criteria by the maximal values they take. This is equivalent to using appropriate linear value functions, which can be done via computeNormalisedPerformanceTable.

The set of weights used by the weighted sum is given hereafter (the negative values are used for criteria 6 which are to be minimised):

{-0.4, -0.18, -0.14, 0.11, 0.17}.

Note that the absolute values of these weights correspond to the maximal values taken by the partial value functions (see Figure 4). The ranks of the alternatives obtained by this technique are then compared to those obtained by the earlier described workflow based on the ACUTA disaggregation.

This comparison is performed in the right part of Figure 1 (area 3), where Kendall's tau (rank correlation coefficient) between both rankings is computed via the alternativesValuesKendall module and a graphical representation of both rankings is plotted via the XYPlotAlternativesValues component (see Figure 5).

Kendall's tau coefficient equals 0.68, which shows that there are a lot of inversions between both rankings.

7 On Figure 5 7 we can see that Thierry's initial preferences (a11 ≻ a03 ≻ a13 ≻ a09 ≻ a14) are satisfied via the ACUTA model, whereas this is not the case with the weighted sum model (a03 ≻ a11 ≻ a09 ≻ a13 ≻ a14).

Conclusion and perspectives

In this short article we have presented diviz which can be used to design and execute algorithmic MCDA workflows and to disseminate research results. The diviz software is being constantly improved, and the number of available components is quickly growing.

The very simple example detailed in Section 3 shows the big potential of the software for the various targeted user communities. Researchers can easily share and test MCDA workflows or experiments, explore robustness issues linked to the choice of the algorithm or the values of the input parameters and spread their own algorithms very conveniently. diviz is also an easy to use pedagogical tool for teachers who need to present and compare classical MCDA methods. Last but not least, diviz may also be used by consultants who wish to solve real world decision problems with a given method.

To conclude this article, we would like to make a call for participation: your MCDA algorithm is welcome in diviz, and if you would like to make it available as a web-service via diviz, please have a look at the developers corner on the website of Decision Deck's web-services8 and contact the authors of this article for any help request or question.

Figure 1 :

 1 Figure 1: The initial workflow for the car selection problem

Figure 2 :

 2 Figure 2: Bar chart representing the overall values of the alternatives

Figure 4 :

 4 Figure 4: Plots of the partial value functions

car ID car name cost acceleration pick up brakes road-h

	a08	Astra 18319	28.9	35.3	1.66	2
	a09	Escort 19800	29.4	34.7	2	1.75
	a10	R19	16966	30	37.7	2.33	3.25
	a11	P309-16 17537	28.3	34.8	2.33	2.75
	a12	P309	15980	29.6	35.3	2.33	2.75
	a13	Galant 17219	30.2	36.9	1.66	1.25
	a14	R21t	21334	28.9	36.7	2	2.25
	a01	Tipo	18342	30.7	37.2	2.33	3
	a02	Alfa	15335	30.2	41.6	2	2.5
	a03	Sunny 16973	29	34.9	2.66	2.5
	a04	Mazda 15460	30.4	35.8	1.66	1.5
	a05	Colt	15131	29.7	35.6	1.66	1.75
	a06	Corolla 13841	30.8	36.5	1.33	2
	a07	Civic	18971	28	35.6	2.33	2

Table 1 :

 1 Data for Thierry's car selection problem

http://www.decision-deck.org

By algorithmic workflow we mean a sequence of connected algorithmic steps.

Note that in the sequel we will unthinkingly use the words component, program or module to describe the algorithms which can be combined in diviz.

http://www.decision-deck.org/ws

http://www.decision-deck.org/diviz

http://www.decision-deck.org/xmcda

On Figure5, the alternatives called fictiveBest (resp. fictiveWorst) are fictive alternatives having the best (resp. worst) performances on all the criteria. They are used by the ACUTA algorithm to correctly scale the domains of the partial value functions.

http://www.decision-deck.org/ws/howtos.html