Gabriela Montoya
email: gmontoya@cs.aau.dk

Hala Skaf-Molli

Katja Hose
email: khose@cs.aau.dk

The Odyssey Approach for Optimizing Federated SPARQL Queries

Answering queries over a federation of SPARQL endpoints requires combining data from more than one data source. Optimizing queries in such scenarios is particularly challenging not only because of (i) the large variety of possible query execution plans that correctly answer the query but also because (ii) there is only limited access to statistics about schema and instance data of remote sources. To overcome these challenges, most federated query engines rely on heuristics to reduce the space of possible query execution plans or on dynamic programming strategies to produce optimal plans. Nevertheless, these plans may still exhibit a high number of intermediate results or high execution times because of heuristics and inaccurate cost estimations. In this paper, we present Odyssey, an approach that uses statistics that allow for a more accurate cost estimation for federated queries and therefore enables Odyssey to produce better query execution plans. Our experimental results show that Odyssey produces query execution plans that are better in terms of data transfer and execution time than state-of-theart optimizers. Our experiments using the FedBench benchmark show execution time gains of at least 25 times on average.

Introduction

Federated SPARQL query engines [START_REF] Acosta | ANAPSID: An Adaptive Query Processing Engine for SPARQL Endpoints[END_REF][START_REF] Basca | Querying a Messy Web of Data with Avalanche[END_REF][START_REF] Görlitz | SPLENDID: SPARQL Endpoint Federation Exploiting VOID Descriptions[END_REF][START_REF] Quilitz | Querying Distributed RDF Data Sources with SPARQL[END_REF][START_REF] Schwarte | FedX: Optimization Techniques for Federated Query Processing on Linked Data[END_REF] answer SPARQL queries over a federation of SPARQL endpoints. Query optimization is a particularly complex and challenging task in a federated setting. The query optimizer minimizes processing and communication costs by selecting only relevant sources for a query. It decomposes the query into subqueries, and produces a query execution plan with good join ordering and physical operators. With limited access to statistics, however, most federated query engines rely on heuristics [START_REF] Acosta | ANAPSID: An Adaptive Query Processing Engine for SPARQL Endpoints[END_REF][START_REF] Schwarte | FedX: Optimization Techniques for Federated Query Processing on Linked Data[END_REF] to reduce the huge space of possible plans or on dynamic programming (DP) [START_REF] Charalambidis | SemaGrow: Optimizing Federated SPARQL queries[END_REF][START_REF] Görlitz | SPLENDID: SPARQL Endpoint Federation Exploiting VOID Descriptions[END_REF] to produce optimal plans. However, these plans may still exhibit a high number of intermediate results or high execution times because of inadequate heuristics or inaccurate estimations of cost functions [START_REF] Gubichev | Exploiting the query structure for efficient join ordering in SPARQL queries[END_REF].

In this paper, we propose Odyssey, a cost-based query optimization approach for federations of SPARQL endpoints. Odyssey defines statistics for representing entities inspired by [START_REF] Neumann | Characteristic Sets: Accurate Cardinality Estimation for RDF Queries with Multiple Joins[END_REF] and statistics for representing links among datasets while guaranteeing result completeness. In a federated setting, computing statistics naturally requires access to more than one dataset. To reduce the overhead, Odyssey uses entity synopsis to identify links among datasets. This comes at the risk of losing some accuracy in the link identification but still guarantees that no links will be missed during query optimization, i.e., there is a small risk that more sources are queried than strictly necessary but the query result will be complete.

Odyssey uses the computed statistics to estimate the sizes of intermediate results and dynamic programming to produce an efficient query execution plan with a low number of intermediate results. In summary, this paper makes the following contributions:

• Concise statistics of adequate granularity representing entities and describing links among datasets while guaranteeing result completeness. • A lightweight technique to compute federated statistics in a federated setup that relies on entity synopsis. • A query optimization algorithm based on dynamic programming using our statistics to find the best plan. • Extensive evaluation using a well-accepted standard benchmark for federated query processing [START_REF] Schmidt | FedBench: A Benchmark Suite for Federated Semantic Data Query Processing[END_REF], including comparison against a broad range of state-of-the-art related work [START_REF] Charalambidis | SemaGrow: Optimizing Federated SPARQL queries[END_REF][START_REF] Görlitz | SPLENDID: SPARQL Endpoint Federation Exploiting VOID Descriptions[END_REF][START_REF] Saleem | HiBISCuS: Hypergraph-Based Source Selection for SPARQL Endpoint Federation[END_REF][START_REF] Schwarte | FedX: Optimization Techniques for Federated Query Processing on Linked Data[END_REF]. The results show Odyssey's superiority with a speed-up of up to 126 times and a reduction of transferred data of up to 118 times on average. This paper is organized as follows. Section 2 presents related work, Section 3 describes the Odyssey approach and its algorithms. Section 4 discusses our experimental results. Finally, conclusions and future work are outlined in Section 5.

Related Work

Query optimization in state-of-the-art federated query engines, such as FedX [START_REF] Schwarte | FedX: Optimization Techniques for Federated Query Processing on Linked Data[END_REF] and ANAPSID [START_REF] Acosta | ANAPSID: An Adaptive Query Processing Engine for SPARQL Endpoints[END_REF], relies on heuristics. For instance, FedX [START_REF] Schwarte | FedX: Optimization Techniques for Federated Query Processing on Linked Data[END_REF] integrates the variable counting heuristic, where relative selectivity of triple patterns is heuristically estimated according to the presence of constants and variables in the triple patterns. These heuristics are lightweight but might not lead to the best query execution plan [START_REF] Stocker | SPARQL Basic Graph Pattern Optimization Using Selectivity Estimation[END_REF]. To find an optimal plan, several approaches [START_REF] Charalambidis | SemaGrow: Optimizing Federated SPARQL queries[END_REF][START_REF] Görlitz | SPLENDID: SPARQL Endpoint Federation Exploiting VOID Descriptions[END_REF][START_REF] Quilitz | Querying Distributed RDF Data Sources with SPARQL[END_REF][START_REF] Wang | LHD: Optimising Linked Data Query Processing Using Parallelisation[END_REF] rely on dynamic programming. However, given the high number of alternative query plans for SPARQL queries with many triple patterns, dynamic programming is very expensive [START_REF] Gubichev | Exploiting the query structure for efficient join ordering in SPARQL queries[END_REF]. Another important factor of query optimization is source selection. Several approaches [START_REF] Acosta | ANAPSID: An Adaptive Query Processing Engine for SPARQL Endpoints[END_REF][START_REF] Görlitz | SPLENDID: SPARQL Endpoint Federation Exploiting VOID Descriptions[END_REF][START_REF] Saleem | HiBISCuS: Hypergraph-Based Source Selection for SPARQL Endpoint Federation[END_REF][START_REF] Schwarte | FedX: Optimization Techniques for Federated Query Processing on Linked Data[END_REF][START_REF] Wang | LHD: Optimising Linked Data Query Processing Using Parallelisation[END_REF] try to determine the relevance of a source by sending ASK queries, which increases the costs for a single query but might amortize in large federations for an overlapping query load. Another technique is to estimate whether combining the data of multiple sources can lead to any join results, e.g., by computing the intersection of the sources' URI authorities [START_REF] Saleem | HiBISCuS: Hypergraph-Based Source Selection for SPARQL Endpoint Federation[END_REF] or detailed statistics [START_REF] Harth | Data Summaries for On-Demand Queries over Linked Data[END_REF][START_REF] Prasser | Efficient Distributed Query Processing for Autonomous RDF Databases[END_REF].

Federated query optimization can also rely on cardinality estimations based on statistics and used, for instance, to reduce sizes of intermediate results. Most available statistics [START_REF] Aranda | SPARQL Web-Querying Infrastructure: Ready for Action?[END_REF] use the Vocabulary of Interlinked Datasets VOID [START_REF] Alexander | Describing Linked Datasets[END_REF], which describes statistics at dataset level (e.g., the number of triples), at the property level (e.g., for each property, its number of different subjects), and at the class level (e.g., the number of instances of each class). However, approaches based on VOID [START_REF] Charalambidis | SemaGrow: Optimizing Federated SPARQL queries[END_REF][START_REF] Görlitz | SPLENDID: SPARQL Endpoint Federation Exploiting VOID Descriptions[END_REF][START_REF] Hagedorn | Resource planning for SPARQL query execution on data sharing platforms[END_REF] and other statistics, such as QTrees [START_REF] Harth | Data Summaries for On-Demand Queries over Linked Data[END_REF] and PARTrees [START_REF] Prasser | Efficient Distributed Query Processing for Autonomous RDF Databases[END_REF], share the drawback of missing the best query execution plans because of errors in estimating cardinalities caused by relying on assumptions that often do not hold for arbitrary RDF datasets [START_REF] Neumann | Characteristic Sets: Accurate Cardinality Estimation for RDF Queries with Multiple Joins[END_REF], e.g., a uniform data distribution and that the results of triple patterns are independent.

Characteristic sets (CS) [START_REF] Du | Partitioned Indexes for Entity Search over RDF Knowledge Bases[END_REF][START_REF] Neumann | Characteristic Sets: Accurate Cardinality Estimation for RDF Queries with Multiple Joins[END_REF] aim at solving this problem in centralized systems by capturing statistics about sets of entities having the same set of properties. This in-formation can then be used to accurately estimate the cardinality and join ordering of star-shaped queries. Typically, any set of joined triple patterns in a query can be divided into connected star-shaped subqueries. Subqueries in combination with the predicate that links them, define a characteristic pair (CP) [START_REF] Gubichev | Exploiting the query structure for efficient join ordering in SPARQL queries[END_REF][START_REF] Meimaris | Extended Characteristic Sets: Graph Indexing for SPARQL Query Optimization[END_REF]. Statistics about such CPs can then be used to estimate the selectivity of two star-shaped subqueries. Such cardinality estimations can be combined with dynamic programming on a reduced space of alternative query plans. Whereas existing work on CSs and CPs were developed for centralized environments, this paper proposes a solution generalizing these principles for federated environments.

The Odyssey Approach

Inspired by the latest advances in statistics for centralized triple stores [START_REF] Gubichev | Exploiting the query structure for efficient join ordering in SPARQL queries[END_REF][START_REF] Meimaris | Extended Characteristic Sets: Graph Indexing for SPARQL Query Optimization[END_REF][START_REF] Neumann | Characteristic Sets: Accurate Cardinality Estimation for RDF Queries with Multiple Joins[END_REF], Odyssey uses statistics about individual datasets to derive detailed statistics for optimizing federated queries. In the following, we first describe the foundations of our statistics on individual datasets (Section 3.1) and then propose a novel method for computing such statistics in a federated environment based on entity descriptions (Section 3.2). As the detailed entity descriptions cause too much overhead in a federated setup, we propose a method for reducing the sizes of the descriptions (Section 3.3). Finally, we present the Odyssey approach for query optimization and its main steps (Section 3.4): source selection, join ordering, and query decomposition.

Dataset Statistics on Individual Datasets

Star-Shaped Subqueries To estimate the cardinality and costs of BGPs sharing the same subject (or object), i.e., star-shaped subqueries, we exploit the principle that entities sharing the same set of properties are similar. In this context, we refer to the set of an entity's properties as its characteristic set (CS) and use cs s (e) to denote the CS of entity e in dataset s or cs(e) if s is clear from the context. For instance, in DBpedia 3.5.1 cs(dbr:Gary Goetzman)=C CSs can be computed by scanning once a dataset's triples sorted by subject; after all the entity properties have been scanned, the entity's CS is identified. For each CS C, we compute statistics, i.e., the number of entities sharing C (count(C)) and the number of triples with predicate p occurring with these entities (occurrences(p, C)). Listing 1.1 shows the statistics for the above mentioned example CS C 1 . Entities of C 1 occur on average in 1 triple with property dbo:birthDate and in 3.94 triples with property rdf:type.

For a star-shaped query, only CSs including all of the query's properties are relevant as entities that only satisfy a subset of these properties cannot contribute to the answer. For star-shaped queries asking for the set of unique entities described by some properties (query with DISTINCT modifier), the exact number of answers can be determined precisely (no estimation). For example, the cardinality of the query given in Listing 1.2 can be obtained by adding up the count(C) of all CSs containing the properties dbo:birthDate, dbo:activeYearsStartYear, and foaf:name. In DBpedia 3.5.1, there are 7,059 CSs that include these three properties, and the total number of entities with these CSs is 83,438. Formally, the number of entities for a given set of properties P, cardinality(P), is computed based on the CSs C j that include all the properties in P as:

cardinality(P ) = P ⊆C j count(Cj ) (1)
For queries without the DISTINCT modifier, we need to account for duplicates by considering the number of triples with predicate p i ∈ P that an entity is associated with on average:

estimatedCardinality(P ) = P ⊆C j count(Cj ) * p i ∈P ocurrences(pi, Cj ) count(Cj ) (2)
In DBpedia 3.5. Once the relevant CSs for a query have been identified, they can be used to find the join order minimizing the sizes of intermediate results. For the query in Listing 1.2, we start by estimating the cardinalities for each subquery with two out of the three triple patterns using Formula 1: {tp1, tp2}: 98,281, {tp1, tp3}: 209,731, and {tp2, tp3}: 127,712. The triple pattern not included in the cheapest subquery ({tp1, tp2}) is executed last (tp3). We proceed recursively with the cheapest subquery and determine the cardinalities for its subsets: {tp1}: 232,608 and {tp2}: 143,004. Again, the triple pattern not included in the cheapest subquery (tp1) will be executed last of the currently considered set of triple patterns. As a result, we will execute the join between tp2 and tp1 first and afterwards compute the join with tp3. We also get the order in which the triple patterns should be evaluated for the first join: first tp2 and then tp1.

Arbitrary Queries To estimate the cardinality for queries with more complex shapes, we need to consider the connections (links) between entities with different CSs. Entity dbr:Evan Almighty, for example, is linked to dbr:Tom Shadyac via property dbo:director by triple (dbr:Evan Almighty, dbo:director, dbr:Tom Shadyac).

The links between CSs via properties can formally be described by characteristic pairs (CPs), they are defined as (cs s (e1), cs s (e2), p) for entities e1 and e2 if (e1, p, e2) ∈ s. The statistics -count((C i , C j , p)) -capture the number of links between a pair of CSs (C i and C j ) using a particular property p. For example, given the CSs of dbr:Tom Shadyac and dbr:Evan Almighty as C 1 and C 2 the number of links via property dbo:director is given by: count((C 2 , C 1 , dbo:director)). ( t p 2 ) ? f i l m dbo : budget ? budget .

( t p 3 ) ? d i r e c t o r dbo : b i r t h D a t e ? date .

( t p 4 ) ? d i r e c t o r dbo : a c t i v e Y e a r s S t a r t Y e a r ?sy . ( t p 5 ) ? d i r e c t o r f o a f : name ?name ( t p 6 ) }

The number of unique results (pairs of entities, query with DISTINCT modifier) can be exactly computed (not estimated) using the formula:

cardinality((Pi, Pj , p)) = P i ⊆C k ∧P j ⊆C l count((C k , C l , p)) (3)
For the query in Listing 1.

estimatedCardinality((Pi, Pj , p)) = P i ⊆C k ∧P j ⊆C l count((C k , C l , p)) * p i ∈P i -{p} ocurrences(pi, C k ) count(C k ) * p j ∈P j ocurrences(pj , C l ) count(C l ) (4)
Assuming that the order of joins within star-shaped subqueries has already been determined based on the CSs as described above, we treat each star-shaped subquery as a single meta-node to reduce complexity. We estimate the cardinalities of the metanodes using the statistics on CPs and use dynamic programming (DP) to determine the optimal join order that minimizes the size of intermediate results. Although the presentation in this section focuses on subject-subject joins, the same principle can be applied to other types of joins, e.g., object-object.

Federated Statistics

In general, entities might occur in multiple datasets in a federation S. Hence, we define a federated characteristic set (FCS) as follows: fcs S (e)= s∈S cs s (e), S might be omitted if clear from the context. However, triples describing the same entity are typically part of a single dataset so that most CSs can be computed over each dataset independently from the others 3 Whereas single dataset statistics can be computed once and provided by the sources in the same way they currently provide VOID statistics, FCSs and FCPs require more effort and centralized knowledge about all entities in the considered datasets. A naive way to compute FCSs and FCPs is evaluating expensive SPARQL queries with FILTER expressions involving NOT EXISTS, but this can take weeks for a dataset with thousands of CSs. It is much more efficient if the sources directly share information about local subjects and objects with the federated query engine. local subjects s (C) contains the entity set with CS C for source s, while local objects s (p, C) contains the set of entities connected via p to CS C. Such information can, for instance, be obtained efficiently while computing CSs and CPs locally and then shared with the federated query engine.

The federated query engine can then use this information to compute FCSs and FCPs. Consider, for instance, the two datasets LMDB and DBpedia in Fig. 1; based on the CSs (Fig. 1a)), the sources compute entity descriptions (local subjects i and local objects i in Fig. 1b)). Entity film:28350 has properties { movie:language,...,owl:sameAs}= C LMDB,1 . Hence, film:28350 ∈ local subjects LMDB (C LMDB,1 ). Entity dbr:Evan Almighty is the value of property owl:sameAs for an entity with CS C LMDB,1 (film:28350) so dbr:Evan Almighty ∈ local objects LMDB (owl:sameAs, C LMDB,1 ) (Fig. 1b)). The overlap between the set of entities local objects DBpedia (C DBpedia,1 ) and local subjects LMDB (owl:sameAs, C LMDB,1 ) are links from LMDB to DBpedia via property owl:sameAs. Hence, we obtain FCP (C LMDB,1 , C DBpedia,1 , owl:sameAs) (Fig. 1c)). count((C LMDB,1 , C DBpedia,1 , owl:sameAs)) corresponds to the cardinality of the intersection between all the local objects DBpedia and local subjects LMDB .

Algorithm 1 describes in more detail how to compute FCPs only based on the pre- FCPs can be used for cardinality estimation and join ordering using the same principles as described in Section 3.1. Consider a federation consisting of DBpedia (160,061 CSs) and LMDB (8,466 CSs) with 22,592 FCPs. We can use Formula 4 with FCPs to estimate the result cardinality: 171. This is close to the real cardinality (293).

Reducing the Sizes of Entity Descriptions

As the entity descriptions (local subjects d and local objects d ) introduced above are often very expensive to compute, maintain and exchange, we propose a technique to reduce their sizes. We organize the entity descriptions in a tree structure that summarizes the entities used as subject or object in any pf the dataset's triples. Inspired by [START_REF] Harth | Data Summaries for On-Demand Queries over Linked Data[END_REF][START_REF] Prasser | Efficient Distributed Query Processing for Autonomous RDF Databases[END_REF][START_REF] Saleem | HiBISCuS: Hypergraph-Based Source Selection for SPARQL Endpoint Federation[END_REF], we factorize common prefixes, transform suffixes into integers, and summarize sets of integers in buckets, i.e., a set synopsis consisting of minimum value (mn), maximum value (mx), mn, mx , number of elements, num, and their set of two least significant bytes (lsb). lsb(i) is computed as i mod 2 16 and is included to improve the synopsis' accuracy.

The tree structure is organized in three levels. The top level summarizes the prefixes of entity IRIs occurring as subjects and objects in the dataset. Suffixes are mapped to integers using a hash function, these integers are summarized in the middle and bottom levels. The middle level includes buckets where parent nodes subsume the synopsis of their children (ranges are included, nums are added) and aids in efficiently accessing only the integer's lsb to reduce the space use while improving the synopsis' accuracy.

In Fig. 2 we present a fragment of the reduced descriptions for LMDB. The reduced descriptions include all the entities that are subject or object in the dataset's triples. In particular, it includes the entity with IRI http://data.linkedmdb.org/resource/film/28350 (Fig. 2c)). This IRI prefix identifies the subtree that summarizes the entity (light gray ellipses in Fig. 2a)), while the hash code of its suffix (resource/film/28350), 1093595742, is used to identify the leaf that includes its lsb (-3490), i.e., with 1093595742 between its minimum and maximum values (gray rectangle in Fig. 2b)). Its lsb is in local subjects(C LMDB,1 ) and local objects(mol:link source, C LMDB,2 ) in the identified leaf (trapezium in Fig. 2b)). This tree structure exhibits size reduction and eases the computation of FCPs by allowing to discard large portions of the descriptions contrary to descriptions in Fig. 1b), where all the local subjects and local objects should be pair-wise tested for overlap.

Computation costs are greatly reduced by pruning large portions of the tree and comparing only a few pairs of leaves, the ones that have common prefixes and overlapping representation of the suffixes. An important feature of these summaries is that entities present in more than one dataset are always detected.

These trees are considerably lighter than the entity descriptions discussed in Section 3.2, but they might reduce accuracy. For FedBench's DBpedia 3.5.1 subset, a dataset with 43,126,772 triples that occupies 6.1GB, the local subjects and local objects occupy 1.37GB and the tree only occupies 68MB 4 . They have compression ratios of 4.45 and 91.86, respectively. Regarding the quality, the tree summary allows for computing all the FCSs and FCPs.

To reduce the resources used by the tree, we have reduced the number of CSs as suggested in [START_REF] Gubichev | Exploiting the query structure for efficient join ordering in SPARQL queries[END_REF][START_REF] Neumann | Characteristic Sets: Accurate Cardinality Estimation for RDF Queries with Multiple Joins[END_REF] to 10,000. Only the CSs that are shared by a greater number of entities are kept, and the others are merged into existing CSs if possible. For instance, by selecting from the CSs that include all the properties of the merged CS the one with the smallest number of properties and adding count and ocurrences values to its own values, or splitting the CS into property subsets that can be merged with other CSs. This may reduce the accuracy of the query cardinality estimation, but it allows to bound the resources used to store and access these statistics.

Entity summaries can be kept up-to-date in two ways. For datasets that are rarely updated the subtree representing the entities with the prefix affected by the updates, e.g., Fig. 2b) in our example, can be re-computed. For datasets that are often updated, leaves should support removal of entities, this can be easily done by storing the multiplicity of each least significant byte, so they are removed only if all the entities with that least significant byte have been removed from the dataset.

Optimizing Federated Queries

Query optimization in Odyssey can logically be divided into the following steps: i) preprocessing and source selection, ii) join ordering, and iii) query decomposition. Arbitrary queries can be handled incrementally by optimizing its subqueries. In the following, we address the optimization of queries with bounded predicates, Odyssey relies on existing optimizers to handle other queries.

Preprocessing and source selection We first parse the query and identify its starshaped subqueries. Then, properties in each star-shaped subquery are used to identify relevant CSs and sources. For example, the subquery composed by tp3 and tp4 in Fig. 3(a) has relevant CSs that include both owl:sameAs and movie:sequel. In the FedBench federation described in Table 1, these CSs are only part of LMDB. Therefore, LMDB is the only relevant source for this subquery. Afterwards, we use CPs/FCPs to identify relevant sources for the links between the star-shaped subqueries.

Join ordering Once we have identified the set of relevant sources, we can estimate cardinalities of subqueries and find the best join ordering. We first optimize the order of joins and triple patterns within each star-shaped subquery as explained in Section 3.1 using the reduced entity descriptions described in Section 3.3. Afterwards, as described in Section 3.1, each subquery is treated as a meta-node and we estimate cardinalities of the joins between these meta-nodes using formulas in Section 3.1 for FCPs to estimate subquery cost and apply DP. Fig. 4 (left) shows the estimated cardinality and cost of the subqueries of Q F (Fig. 3

Fig. 4: Example query optimization

In our current implementation, the cost function is solely defined on the cardinalities of intermediate results and how many results need to be transferred from endpoints during execution. This favors query plans with selective subqueries. For instance, the cost of the join between meta-nodes ?star1 and ?star2 (1,965) includes the result sizes (417) and the incurred intermediate results [START_REF] Acosta | ANAPSID: An Adaptive Query Processing Engine for SPARQL Endpoints[END_REF]548). This cost function assumes that all endpoints have the same characteristics. We can easily extend this cost function by additional parameters that can be fine-tuned to represent the characteristics of each endpoint individually, e.g., communication delays, response times, etc.

Query decomposition Finally, we optimize the SPARQL queries that are actually sent to the endpoints and try to minimize their number. For instance, we combine all triple patterns and logical subqueries to a particular endpoint into a single SPARQL query to a particular endpoint whenever possible. For instance, meta-nodes ?star2 and ?star3 in Fig. 4 are combined into one subquery (Fig. 3(b)) and evaluated by the DBpedia endpoint.

Evaluation

In this section, we present the results of our experimental study that compares our approach, Odyssey, with state-of-the-art federated query engines: HiBISCuS (FedX-HiBISCuS, cold and warm cache) [START_REF] Saleem | HiBISCuS: Hypergraph-Based Source Selection for SPARQL Endpoint Federation[END_REF], SemaGrow [START_REF] Charalambidis | SemaGrow: Optimizing Federated SPARQL queries[END_REF], FedX (cold and warm cache) [START_REF] Schwarte | FedX: Optimization Techniques for Federated Query Processing on Linked Data[END_REF], and SPLENDID [START_REF] Görlitz | SPLENDID: SPARQL Endpoint Federation Exploiting VOID Descriptions[END_REF]. Full implementations, statistics, and results are available at https://github.com/gmontoya/federatedOptimizer. Datasets and queries: We use the real datasets and queries proposed in the FedBench benchmark [START_REF] Schmidt | FedBench: A Benchmark Suite for Federated Semantic Data Query Processing[END_REF]. Queries are divided into three groups Linked Data (LD1-LD11), Cross Domain (CD1-CD7), and Life Science (LS1-LS7). They have 2-7 triple patterns and star and hybrid shapes. They have between 1 and 9,054 answers. Basic statistics about the datasets are listed in Table 1. We ran each query ten times and report the averages over the last nine runs. Standard deviation is included as error bars on the plots. Implementation: Odyssey is implemented in Java using the Jena library to parse and transform queries into queries with SPARQL 1.1 service clauses. Our implementation uses the FedX 3.1 framework with deactivated native optimization to execute Odyssey's query plans.

Hardware configuration: For our experiments we used virtual machines (VMs). A VM using up to 4GB of RAM to run the federated query engine and nine VMs with 2 processors, 8GB of RAM and CPU 2294.250 MHz to host Virtuoso endpoints with the datasets described in Table 1 (one dataset and endpoint per VM).

Statistics computation: As DBpedia has a very high number of CSs (160,061), we reduced them to 10,000 by merging (as suggested in [START_REF] Gubichev | Exploiting the query structure for efficient join ordering in SPARQL queries[END_REF][START_REF] Neumann | Characteristic Sets: Accurate Cardinality Estimation for RDF Queries with Multiple Joins[END_REF] and explained in Section 3.3) without significant losses in the quality of estimations. Details on creation times of statistics are listed in Table 1. Odyssey's statistics can be more expensive to compute for datasets with more than 3,419 CSs and cheaper than HiBISCuS's for datasets with less than 67 CSs. In total, Odyssey's statistics are computed five times faster than VOID's.

Evaluation metrics: i) Optimization time (OT): is the elapsed time since the query is issued until the optimized query plan is produced, ii) number of selected sources (NSS): is the number of sources that have been selected to answer a query, iii) number of subqueries (NSQ): is the number of subqueries that are included in the query plan, iv) execution time (ET): is the time elapsed since the evaluation of the query plan starts until the complete answer is produced (with a timeout of 1,800 seconds), v) number of transferred tuples (NTT): is the number of tuples transferred from all the endpoints to the query engine during query evaluation.

Result completeness: All approaches produce the complete result set for non-timed out queries, except SPLENDID for query LS7.

Experimental Results

Optimization time Fig. 5 shows the optimization time (OT) for the studied approaches. Because of the detailed statistics and dynamic programming, one might expect Odyssey to suffer from a considerable overhead in OT. As our experimental results show, however, Odyssey's query planner is competitive to most other approaches with a slight advantage for FedX-Warm as this system has cached information about the query relevant sources. For instance, Odyssey is up to 69 times faster (SemaGrow) than other approaches on average. Number of selected sources As Fig. 6 shows, Odyssey selects only a small number of relevant sources; for instance, at least 1.81 times less (FedX-Cold/Warm and Sema-Grow) and up to 1.93 times less (HiBISCuS-Cold/Warm) on average. For some queries, e.g., LS4, existing approaches already select the optimal number of sources. For LD7, Odyssey selects a larger number of sources than the optimum because our approach does not perform ASK queries during execution to prune irrelevant sources. Sometimes Odyssey overestimates the set of relevant sources -but on the other hand it never misses any relevant sources. For LS1, most approaches select just one (10 0 ) source because there is only one dataset that have triples with the predicate in the query. Number of subqueries As Fig. 7 shows, Odyssey uses considerably fewer subqueries than other approaches, at least 2.62 times less (HiBISCuS-Cold/Warm) and up to 3.41 times less (SPLENDID) on average. The fact that Odyssey always produces the correct and complete answers confirms that Odyssey correctly identifies and exploits cases for which it is advantageous to combine subqueries. Odyssey's reduction of the number of relevant sources has a positive impact on the number of subqueries (NSQ), Odyssey's pruning of non relevant sources allows for combining triple patterns into subqueries without affecting the result completeness. Some queries, like LD2, LD4, and LD9, include triple patterns that can be evaluated by a unique endpoint of the federation and existing approaches already decompose the query into the optimal NSQ. Only for LD7, FedX-Cold/Warm, SPLENDID, and SemaGrow decompose the query into fewer subqueries than Odyssey, this is because they use ASK queries to assess a source's relevance. Odyssey could be enhanced with this strategy.

Execution time Some approaches failed to answer all queries before the timeout: SPLENDID (2 queries) and SemaGrow (4 queries). Even when considering only those queries that completed before the timeout, Odyssey is on average 126.26 times faster than SPLENDID and 28.30 times faster than SemaGrow. Fig. 8 shows the execution times (ET) for the studied approaches. Number of transferred tuples Fig. 9 shows the number of transferred tuples (NTT) for the studied approaches. Odyssey transfers fewer tuples than other approaches. Even when considering only those queries that completed before the timeout, Odyssey transfers on average 1.15 times fewer tuples faster than SemaGrow and 108.4 times fewer tuples than SPLENDID. For the approaches that completed all the queries, Odyssey transfers at least 117.55 fewer tuples (HiBISCuS-Cold/Warm) on average. Most approaches are competitive in terms of NTT. The largest difference is observed for LS6, where Odyssey clearly outperforms the other approaches transferring 500 times fewer tuples. In contrast to other approaches, Odyssey not only reduces the number of requests sent to the endpoints but also avoids non-selective queries, which significantly reduces network traffic and the local load at the endpoints.

Combining Odyssey with Existing Optimizers

We have also integrated Odyssey techniques into an the FedX optimizer and obtained: -Odyssey-FedX-Cold, which relies on CSs and CPs to select sources and decomposes the query but uses FedX join ordering. -FedX-Cold-Odyssey, which relies on the FedX optimizer for source selection but uses Odyssey for query decomposition and join ordering. Fig. 10 compares the execution times (ET) of these two implementations with Odyssey, FedX-Cold, and FedX-Warm. In most cases the combined approaches are considerably faster than native FedX. In a few cases, however, their ET can increase considerably. In these cases, queries include a highly selective subquery with one triple pattern and using FedX's heuristic to execute subqueries with more than one triple pattern first leads to plans that are more expensive than others. On average, the combined approaches are 26.86 and 3.99 times faster than FedX-Cold.

For query LD7, Odyssey and FedX-Cold/Warm exhibit similar ETs whereas FedX-Cold-Odyssey is considerably faster. For this query it happens that the advantages of both Odyssey and FedX coincide, i.e., we can take advantage of the good join ordering by Odyssey but also of the additional pruning based on ASK queries by FedX.

Even if Odyssey's OT can be higher in comparison to existing approaches, Odyssey produces better plans composed of fewer subqueries and fewer selected sources per triple pattern without compromising result completeness. Benefits of these features have been evidenced with significantly faster ETs and less transferred data from endpoints to the federated query engine.

Conclusion

In this paper, we have presented Odyssey, an approach for optimizing federated SPARQL queries based on statistics. These statistics detail information about the data provided by remote endpoints as well as the links between them. This enables more accurate cost estimations, query optimization, and selection of relevant sources. Our extensive experimental evaluation shows that Odyssey produces query execution plans that are better in terms of data transfer and execution time than state-of-the-art optimiz-ers. In our future work, we plan to further improve Odyssey by considering in which situations exactly it is worthwhile to use additional aspects of other optimizers, such as ASK queries and associated statistics. Another interesting perspective work is to further reduce the computation time and sizes of the entity descriptions and provide efficient strategies to update the descriptions and statistics.

Listing 1 . 3 :

 13 Find movies and their directors SELECT DISTINCT ? f i l m ? d i r e c t o r WHERE { ? f i l m dbo : r u n t i m e ? r u n t i m e . ( t p 1 ) ? f i l m dbo : d i r e c t o r ? d i r e c t o r .

Fig. 3 :

 3 Fig. 3: Query Q F and its Optimized Plan

Fig. 5 :

 5 Fig. 5: Optimization Time in ms (OT, log scale). CD1 and LS2 have variable predicates and Odyssey relies on FedX to find plan.

Fig. 6 :

 6 Fig. 6: Number of Selected Sources (NSS, log scale, 10 0 =1)

Fig. 7 :

 7 Fig. 7: Number of Subqueries (NSQ, log scale, 10 0 =1)

Fig. 8 :Fig. 9 :

 89 Fig. 8: Execution Time in ms (ET, log scale)

Fig. 10 :

 10 Fig. 10: Execution Time in ms (ET, log scale)

  . The federated characteristic pair (FCP) of entities e1 and e2 via property p

		LMDB				DBpedia
	film:28350	mo vie :lan gua ge owl :sam eAs	linguo:en . . .	dbr:Evan Almighty	dbo :pro duce r dbo:d irecto r	dbr:Gary Goetzman . . .
		dbr:Evan Almighty				dbr:Tom Shadyac
	il:49900	mo l:lin k sou rce mol :link targ et	film:28350 . . .	dbr:Gary Goetzman	dbo: birth Date skos: subje ct	1952-11-06 . . .
		photos:Evan Almighty				dbc:American film producer
		CLMDB,1={movie:language,...,owl:sameAs} CSs and CPs at the sources	CDBpedia,1={dbo:producer,...,dbo:director}
		CLMDB,2={mol:link source, mol:link target}	a)		CDBpedia,2={dbo:birthDate,...,skos:subject}
		(CLMDB,2,CLMDB,1,mol:link source)			(CDBpedia,1,CDBpedia,2,dbo:producer)
		...					...
	local subjectsLMDB(CLMDB,1)={ film:28350, ... }	Entity Descriptions		local subjectsDBpedia(CDBpedia,1)={ dbr:Evan Almighty, ... }
	local objectsLMDB(movie:language, CLMDB,1)={ linguo:en,...} local objectsLMDB(owl:sameAs,CLMDB,1)={ dbr:Evan Almighty, ...} b)	local objectsDBpedia(dbo:producer,CDBpedia,1)={ dbr:Gary Goetzman, ...} local objectsDBpedia(dbo:director,CDBpedia,1)={ dbr:Tom Shadyac, ...}
			(CLMDB,1,CDBpedia,1,owl:sameAs)	FCPs (and FCSs)
				c)

1

Fig.

1

: Federated Computation of Statistics in federation S is defined as (fcs S (e1), fcs S (e2), p). For FCSs FC i and FC j and property p, we compute statistics count(FC i ), occurrences(p, FC i ), and count((FC i ,FC j ,p)) as before for CSs and CPs. For simplicity, the following sections focus on FCPs connecting CSs instead of FCSs. The generalization using FCSs is straightforward.

  Algorithm 1 Compute FCPs AlgorithmInput: local objects d1 and local subjects d2 for datasets d1 and d2 Output: A set of FCPs (FCPs) with links from d1 to d2 count(fcp) for each fcp in FCPs 1: function ComputeFCPs(local subjects d2 , local objects d1 ) 2:computed statistics local objects d1 and local subjects d2 . First, all common entities in local objects d1 and local subjects d2 are identified in line 7. These common entities represent links between CSs C d1,i and C d2,j via property p and are captured by a FCP (lines 9-10).

	3: 4: 5: 6: 7: 8: 9: 10: 11:	FCPs ← { } count ← a function with default value 0 for (p, C d1,i ) ∈ domain(local objects d1 ) do entities ← local objects d1 (p,C d1,i ) for C d2,j ∈ domain(local subjects d2 ) do entities ← entities local subjects d2 (C d2,j ) if entities = ∅ then FCPs ← FCPs { (C d1,i , C d2,j , p) } count((C d1,i , C d2,j , p)) ← count((C d1,i , C d2,j , p)) + cardinality(entities) end if
	12:	end for
	13:	end for
	14:	return CPs, count
	15: end function

Listing 1.4: Find LMDB movies that are also DBpedia movies SELECT ? f i l m ?movie WHERE { ? f i l m dbo : budget ? budget . ? f i l m dbo : d i r e c t o r ? d i r e c t o r . ?movie owl : sameAs ? f i l m . ?movie lmdb : sequel ?seq }

  (a)), arrows indicate which smaller subqueries were combined by the DP algorithm to form a larger subquery. As the number of subqueries is usually considerably lower than the number of triple patterns, applying DP becomes affordable.

				?star3
		?star2			db o:b irt hD at e	?sy	subqueries	cardinality	cost
	?m ?star1 ow m o v ie :s e q u e l l: sa m eA s	?f	d b o: d ir ec to r d b o :b u d g e t	?d ?b	db o:a ct ive Ye ar sS ta rtY ea r	?bd	{ ?star1 } { ?star2 } { ?star3 } { ?star1, ?star2 } { ?star2, ?star3 } { ?star1, ?star3 }	1,548 6,057 125,003 417 979 1.9e8	1,548 6,057 125,003 1,965 979 1.9e8
		?s					{ ?star1, ?star2, ?star3 }	68	1,047
		?star1		?star2		?star3
						1

Table 1 :

 1 FedBench[START_REF] Schmidt | FedBench: A Benchmark Suite for Federated Semantic Data Query Processing[END_REF] dataset statistics: number of distinct triples (#DT), number of predicates (#P), number of CSs (#CS), number of CPs (#CP), Odyssey statistics and synopsis computation time in s, HiBISCuS summaries computation time in s, and VOID statistics computation time in s

	Dataset	#DT	#P # CS	#CP	#FCP Odyssey HiBISCuS VOID
	ChEBI	4,772,706	28	978	9,958	19,360 82.91	96.02	73.89
	KEGG	1,090,830	21	67	239	13,822 30.15	95.23	12.84
	Drugbank	517,023	119 3,419 12,589 103,070 1,299.9	76.4	6.98
	DBpedia subset 42,855,253 1,063 10,000 1,069,431 6,583	2,739	770.48 1,465.36
	Geonames 107,949,927 26	673	7,707 322,672 1,885.97 609.52 39,694.07
	Jamendo	1,049,647	26	42	190	1,259	31.25	99.17	14.66
	SWDF	103,595	118 547	6,713	17,557	7.27	69.21	2.03
	LMDB	6,147,916 222 8,466 94,188 359,340 947.16	317.21	355.45
	NYTimes	335,119	36	47	158	3.96	10.01	72.56	4.22
	Federated						620.35
	Total						7,654.27 2,205.8 41,629.5

  Odyssey is on average at least 25.46 times faster (FedX-Warm). Only for few queries Odyssey is (slightly) slower than other approaches, e.g., LS3. As for the other metrics, Odyssey's ET can be improved if ASK queries were used during query execution to further reduce the relevant sources similarly as it is done by other approaches. For five of the queries, Odyssey is one of the fastest approaches and for 11 queries, Odyssey is the fastest approach. Odyssey's achieved reductions on the NSS and NSQ have a positive impact on the ET, as fewer endpoints are queried fewer times, Odyssey produces results faster than most approaches in most cases.

				10 6
		Odyssey HiBISCuS-Warm HiBISCuS-Cold FedX-Warm FedX-Cold SemaGrow	ET (ms)	10 2 10 4		TIMEOUT
		SPLENDID		10 0
				LD1 LD2 LD3 LD4 LD5 LD6 LD7 LD8 LD9 LD10LD11
		10 6			10 6
	ET (ms)	10 2 10 4		ET (ms)	10 2 10 4	TIMEOUT	TIMEOUT TIMEOUT	INCOMPLETE RESULT ABORT
		10 0			10 0
		CD1 CD2 CD3 CD4 CD5 CD6 CD7		LS1 LS2 LS3 LS4 LS5 LS6 LS7

FCSs describing entities across multiple datasets are very rare. In FedBench, for instance, they affect less than 0.5% of all CSs.

Implementation based in Java's HashSet and HashMap was used to measure their sizes.

Acknowledgments

This research was partially funded by the Danish Council for Independent Research (DFF) under grant agreement no. DFF-4093-00301.


Jilles S Dibangoye

Olivier Buffet

Learning to Act in Continuous Dec-POMDPs

Keywords:

Nous nous attaquons au problème d'apprentissage par renforcement dans le cadre des processus décisionnels de Markov partiellement observables et décentralisés. Les tentatives précédentes ont conduit à différentes variantes de la méthode généralisée d'itération de politiques, qui dans le meilleur des cas abouties à des optima locaux. Dans ce papier, nous nous restreindrons au plans, qui sont des formes plus simples que des politiques. Nous dériverons, sous certaines conditions, le premier algorithm algorithme optimal d'apprentissage par renforcement coopératif. Afin d'accroître le passage à l'échelle de cet algorithme, nous remplacerons l'opérateur glouton traditionnel par un programme linéaire en nombre entier. Les résultats expérimentaux montrent que notre méthode est capable d'apprendre de fac ¸on optimale dans plusieurs bancs de test de la litérature.

Introduction

Decentralized partially observable Markov decision processes (Dec-POMDPs) emerged as the standard framework for sequential decision making by a team of collaborative agents [START_REF] Bernstein | The Complexity of Decentralized Control of Markov Decision Processes[END_REF]. A key assumption of Dec-POMDPs is that agents can neither see the actual state of the system nor explicitly communicate their noisy observations with each other due to communication cost, latency or noise, hence providing a partial explanation of the double exponential growth at every control interval of the required memory in optimal algorithms [START_REF] Hansen | Dynamic Programming for Partially Observable Stochastic Games[END_REF], [START_REF] Szer | MAA*: A Heuristic Search Algorithm for Solving Decentralized POMDPs[END_REF], [START_REF] Oliehoek | Optimal and Approximate Q-value Functions for Decentralized POMDPs[END_REF][START_REF] Oliehoek | Incremental Clustering and Expansion for Faster Optimal Planning in Dec-POMDPs[END_REF], [START_REF] Dibangoye | Optimally Solving Dec-POMDPs as Continuous-State MDPs[END_REF]. While planning methods for finite Dec-POMDPs made substantial progress in recent years, the formal treatment of the corresponding reinforcement learning problems received little attention so far, let alone its continuous counterpart. The literature of multi-agent reinforcement learning (MARL) can be divided into two main categories: concurrent and team approaches [START_REF] Tan | Multi-agent Reinforcement Learning: Independent vs. Cooperative Agents[END_REF], [START_REF] Panait | Cooperative multi-agent learning: The state of the art[END_REF]. Perhaps the dominant paradigm in MARL is the concurrent approach, which involves multiple simultaneous learners: typically, each agent has its learning process. Self-interested learners, for example, determine their best-response behaviors considering their opponents are part of the environment, often resulting in local optima [START_REF] Brown | Iterative Solutions of Games by Fictitious Play[END_REF], [START_REF] Hu | Multiagent Reinforcement Learning: Theoretical Framework and an Algorithm[END_REF], [START_REF] Littman | Markov games as a framework for multiagent reinforcement learning[END_REF]. While concurrent learning can apply in Dec-POMDPs, a local optimum may lead to severely suboptimal performances [START_REF] Peshkin | Learning to Cooperate via Policy Search[END_REF], [START_REF] Zhang | Coordinated Multi-Agent Reinforcement Learning in Networked Distributed POMDPs[END_REF], [START_REF] Kraemer | Multi-agent reinforcement learning as a rehearsal for decentralized planning[END_REF]. Also, methods of this family face two conceptual issues that limit their applicability. The primary concern is that of the co-adaptation dilemma, which arises when each attempt to modify an agent behavior can ruin learned behaviors of its teammates. Another major problem is that of the multiagent credit assignment, that is, how to split the collective reward signal among independent learners. Alternatively, the team approach involves a single learner acting on behalf of all agents to discover a collective solution [START_REF] Salustowicz | Learning Team Strategies: Soccer Case Studies[END_REF], [START_REF] Miconi | When Evolving Populations is Better Than Coevolving Individuals: The Blind Mice Problem[END_REF]. Interestingly, this approach circumvents the difficulties arising from both the co-adaptation and the multi-agent credit assignment. Coordinated agents, for example, simultaneously learn their control choices and the other agent strategies assuming instantaneous and free explicit communications [START_REF] Guestrin | Coordinated Reinforcement Learning[END_REF], [START_REF] Kok | Sparse Cooperative Q-learning[END_REF]. While methods of this family inherit from standard single-agent techniques, they need to circumvent two significant drawbacks: the explosion in the state space size; and the centralization of all learning resources in a single place. Recently, team algorithms ranging from Q-learning to policy-search have been introduced for finite Dec-POMDPs, but with no guaranteed global optimality [START_REF] Kraemer | Multi-agent reinforcement learning as a rehearsal for decentralized planning[END_REF], [START_REF] Wu | Monte-Carlo Expectation Maximization for Decentralized POMDPs[END_REF], [START_REF] Liu | Stickbreaking policy learning in Dec-POMDPs[END_REF][START_REF] Liu | Learning for Decentralized Control of Multiagent Systems in Large, Partially-Observable Stochastic Environments[END_REF]. So, it seems one can either compute local optima with arbitrary bad performances or calculate optimal solutions but assuming noise-free, instantaneous and explicit communications.

A recent approach to optimally solving finite Dec-POMDPs suggests recasting them into occupancy-state MDPs (oMDPs) and then applying (PO)MDP solution methods [START_REF] Dibangoye | Optimally Solving Dec-POMDPs as Continuous-State MDPs[END_REF]. In these oMDPs, the states called occupancy states are distributions over hidden states and joint histories of the original problem, and actions called decision rules are mappings from joint histories to controls [START_REF] Nayyar | Optimal Control Strategies in Delayed Sharing Information Structures[END_REF], [START_REF] Oliehoek | Sufficient Plan-Time Statistics for Decentralized POMDPs[END_REF], [START_REF] Dibangoye | Optimally Solving Dec-POMDPs as Continuous-State MDPs[END_REF]. This approach achieves scalability gains by exploiting the piece-wise linearity and convexity of the optimal value function. Since this methodology successfully applied for planning in finite Dec-POMDPs, it is natural to wonder which benefits it could bring to the corresponding MARL problem. Unfortunately, a straightforward application of standard RL methods to oMDPs will face three severe limitations. First, occupancy states are unknown, and hence must be estimated. Second, they lie in a continuum making tabular RL methods inapplicable. Finally, the greedy maximization is computationally demanding in decentralized stochastic control problems [START_REF] Radner | Team Decision Problems[END_REF], [START_REF] Kumar | Constraint-based dynamic programming for decentralized POMDPs with structured interactions[END_REF].

This paper extends the methodology of Dibangoye et al. to MARL, focussing on the three major issues that limit its applicability. Our primary result is the proof that, by restricting attention to plans instead of policies, a linear function over occupancy states and decision rules, which is simple to store and update, can capture the optimal performance for Dec-POMDPs. We further use plans instead of policies in a policy iteration algorithm, with the plan always being improved with respect to a linear function and a linear function always being driven toward the linear function for the plan. Under accurate estimation of the occupancy states, the resulting algorithm, called occupancy-state SARSA (oSARSA) [START_REF] Rummery | On-line Q-learning using connectionist systems[END_REF], is guaranteed to converge with probability one to an optimal plan for any finite Dec-POMDP. To extend its applicability to higher-dimensional domains, oSARSA replaces the greedy (or soft) maximization by a mixed-integer linear program for finite settings, and a gradient approach for continuous ones. Altogether, we obtain a MARL algorithm that can apply to continuous Dec-POMDPs. Experiments show our approach can learn to act optimally in many finite domains from the literature. We organize the remainder of this paper as follows. Section 2 extends a recent planning theory from finite to continuous settings, starting with a formal definition of finite and continuous Dec-POMDPs. We proceed with the introduction of a framework for centralized MARL in Dec-POMDPs in Section 3. Also, we discuss our solutions to the three limitations mentioned above. We present the resulting algorithm oSARSA along with convergence guarantees in Section 4. Finally, we conduct experiments in Section 5, demonstrating our approach can learn to act optimally in many finite domains from the literature.

2 Planning in Dec-POMDPs as oMDPs

Continuous Dec-POMDPs

A continuous Dec-POMDP is a tuple M . " pn, X, tU i u, tZ i u, p, r, , γ, b 0 q, where n denotes the number of agents involved in the decentralized stochastic control process; X is a set of hidden world states, denoted x or y; U i is a private control set of agent i P v1; nw, where U " U 1 ˆ¨¨¨ˆU n specifies the set of controls u " pu 1 , . . . , u n q; Z i is a private observation set of agent i, where Z " Z 1 ˆ¨¨¨ˆZ n specifies the set of observations z " pz 1 , . . . , z n q; p describes a transition probability kernel with conditional density p u,z px, yq; r is a reward model with immediate reward rpx, uq, we assume rewards are two-side bounded, i.e., for some c P R `, @x P X, u P U : |rpx, uq| ď c; is the planning horizon; γ P r0, 1s denotes the discount factor; and b 0 is the initial belief state with density b 0 px 0 q. We shall restrict attention to finite planning horizon ă 8 since an infinite planning horizon solution is within a small scalar ą 0 of a finite horizon solution where " rlog γ pp1 ´γq {cqs. A Dec-POMDP is usually either finite, i.e., sets X, U i and Z i for all i P v1; nw are finite, or continuous, i.e., the same sets are continuous. The remainder of this section extends concepts and standard results from finite to continuous settings. Because we are interested in MARL, we assume an incomplete knowledge about M , i.e., p and r are either unavailable or only through a generative model. Hence, the goal of solving M is to find a joint plan, i.e., a tuple of individual decision rules, one for each agent and time step: ρ . " pa 1 0: , . . . , a n 0: q. A tth individual decision rule a i t : O i t Þ Ñ PpU i q of agent i prescribes private controls based on the whole information available to the agent up to the tth time step, i.e., history of controls and observations o i t " pu i 0:t´1 , z for the average reward case. For any control interval t, joint plans a 0:t of interest are those that achieve the highest performance measure Jpa 0:t q . " E a0:t tR 0 | b 0 u starting at b 0 , where E a0:t t¨u denotes the expectation with respect to the probability distribution over state-action pairs joint plan a 0:t induces, in particular Jpρq . " Jpa 0: ´1q for ρ . " a 0: ´1. One can show that, in Dec-POMDPs, there always exists a deterministic plan that is as good as any stochastic plan [see Puterman, 1994, Lemma 4.3.1]. Unfortunately, there is no direct way to apply the theory developed for Markov decision processes [START_REF] Bellman | Dynamic Programming[END_REF], [START_REF] Puterman | Markov Decision Processes, Discrete Stochastic Dynamic Programming[END_REF] to Dec-POMDPs, including: the Bellman optimality equation; or the policy improvement theorem. To overcome these limitations, we rely on a recent theory by Dibangoye et al. that recasts M into an MDP, thereby allowing knowledge transfer from the MDP setting to Dec-POMDPs.

Occupancy-State MDPs

To overcome the fact that agents can neither see the actual state of the system nor explicitly communicate their noisy observations with each other, [START_REF] Szer | MAA*: A Heuristic Search Algorithm for Solving Decentralized POMDPs[END_REF] and later on [START_REF] Dibangoye | Optimally Solving Dec-POMDPs as Continuous-State MDPs[END_REF] suggest formalizing M from the perspective of a centralized algorithm. A centralized algorithm acts on behalf of the agents by selecting a joint decision rule to be executed at each control interval based on all data available about the system, namely the information state. The information state at the end of control interval t, denoted ι t`1

. " pb 0 , a 0:t q, is a sequence of joint decision rules the centralized algorithm selected starting at the initial belief state. Hence, the information state satisfies the following recursion: ι 0 . " pb 0 q and ι t`1 . " pι t , a t q for all control interval t, resulting in an ever-growing sequence. To generalize the value from one information state to another one, Dibangoye et al. introduced the concept of occupancy states. The occupancy state at control interval t, denoted s t . " Ppx t , o t |ι t q, is a distribution over hidden states and joint histories conditional on information state ι t at control interval t. Interestingly, the occupancy state has many important properties. First, it is a sufficient statistic of the information state when estimating the (current and future) reward to be gained by executing a joint decision rule:

Rps t , a t q . " ş X ş O s t px, oq ş U a t pu|oq ¨rpx, uqdudodx.
In addition, it describes a deterministic and fully observable Markov decision process, where the next occupancy state depends only on the current occupancy state and next joint decision rule, for all y P X, o P O, u P U, z P Z: T ps t , a t q . " s t`1 s t`1 py, po, u, zqq . " a t pu|oq ş X s t px, oq ¨pu,z px, yqdx. The process the occupancy states describe is known as the occupancy-state Markov decision process (oMDP), and denoted M 1 .

" pS, A, R, T, , γ, s 0 q. This is an -steps deterministic and continuous MDP with respect to M , where

S

. " Y tPv0; ´1w S t is the set of occupancy states up to control interval ´1; A . " Y tPv0; ´1w A t is the set of joint decision rules up to control interval ´1; R is the reward model; and T is the transition rule; s 0 is the initial occupancy state, which is essentially the initial belief in M ; γ and are as in M . It is worth noticing that there is no need to construct explicitly M 1 ; instead we use M (when available) as a generative model for the occupancy states T ps t , a t q and rewards Rps t , a t q, for all control intervals t. Note that, using control terminology, planning (or learning) in M 1 can be made either open-loop or closed-loop. M is called an open-loop planning problem because the class of considered solutions (i.e., plans) are only function of time (and not of the underlying occupancy states). It is called a closed-loop planning problem since it is a Markov decision process, whose solution is known to be a policy (mapping from occupancy states to joint decision rules). Policies π : S Þ Ñ A, mappings from occupancy states to decision rules, generalizes plans ρ, by prescribing a joint decision rule depending on the current time and occupancy state. Plans are in general sub-optimal compared to policies, as they prescribes a decision rule depending only upon the current time. However, here, both open-and closedloop approaches can lead to an optimal solution. Below, we review a closed-loop approach based on the dynamic programming theory [START_REF] Bellman | Dynamic Programming[END_REF]. Due to the deterministic nature of the dynamics in oMDP M 1 , planning (or learning) in M 1 can be seen, without loss of optimality, not only as closed-loop-a solution being a policy π : S Þ Ñ A, mapping (encountered/reachable) occupancy states to joint decision rules-, but also as openloop-a solution being a(n inconditional) plan ρ, that is, a sequence of joint decision rules. Below, we review a closedloop approach based on the dynamic programming theory [START_REF] Bellman | Dynamic Programming[END_REF]. For any finite M , the Bellman equation is written as follows: for all occupancy state s t P S t , and some fixed policy π,

V π t ps t q . " Rps t , πps t qq `γ1 V π t`1 pT ps t , πps t qqq (1)
with boundary condition V π p¨q . " 0, describes the return of a particular occupancy state s t when taking decision rule a t " πps t q prescribed by π. The equation for an optimal policy π ˚is referred to as the Bellman optimality equation: for any control interval t, and occupancy state s t ,

V t ps t q . " max atPA Rps t , a t q `γ1 V t`1 pT ps t , a t qq (2)
with boundary condition V ˚ p¨q . " 0. Unfortunately, occupancy states lie in a continuum, which makes exact dynamic programming methods infeasible. When optimized exactly, the value function solution of (2) along with the boundary condition is always piece-wise linear and convex in the occupancy-state space [START_REF] Dibangoye | Optimally Solving Dec-POMDPs as Continuous-State MDPs[END_REF]. Similarly to continuous POMDPs [START_REF] Porta | Point-Based Value Iteration for Continuous POMDPs[END_REF], we generalize this property to continuous Dec-POMDPs.

Lemma 1. For any arbitrary M1 , the solution V 0: of (2) is convex in the occupancy-state space. If we restrict attention to deterministic policies and finite M (and corresponding M 1 ), the solution of ( 2) is piece-wise linear and convex in the occupancy-state space. Hence, the optimal value at any occupancy state s t is as follows:

V t ps t q . " max αtPΓt xs t , α t y, (3)
where xs t , α t y is used to express the expectation of a linear function α t (also called α-function 1 ) in the probability space defined by sample space X ˆO, the σ-algebra X ˆO and the probability distribution s t ; and Γ t is the set of all tth α-functions.

Proof. Consider the α-function induced when agents follow plan a t: ´1 from control interval t onwards, denoted α a t: ´1 and given by α a t: ´1 px, oq . " EtR t |x t " x, o t " o, a t: ´1u. Hence, the optimal value starting at any occupancy state s t is given by taking the maximum over values of all possible plans from control interval t onwards: V t ps t q " max a t: ´1 xs t , α a t: ´1 y. In addition, the linearity of the expectation also implies that α a t: ´1 is linear in the occupancy-state space. The proof directly follows from [Rockafellar, 1970, Theorem 5.5].

Lemma 1 shows that for any arbitrary M and corresponding M 1 , the solution of (2), represented by sets Γ 0: , is convex in the occupancy-state space. Each α-function defines the value function over a bounded region of the occupancy-state space. In addition, it is associated with a plan, defining the optimal plan for a bounded region of the occupancy-state space. Sets Γ 0: are iteratively improved by adding a new α-function that dominates current ones over certain regions of the occupancy-state space. The α-function to be added is computed using point-based Bellman backup operator H:

rHΓ t`1 sps t q "
arg max

α a t : aPAt,αt`1PΓt`1 xs t , α a t y,
where α a t px, oq .

" Etrpx, uq `γ1 α t`1 py, po, u, zqq|au, for each hidden state x P X, and joint history o P O. Interestingly, H remains both a contracting and isotonic operator in continuous settings [START_REF] Porta | Point-Based Value Iteration for Continuous POMDPs[END_REF]. To keep the number of α-functions manageable, one can prune those that are dominated over the entire occupancy-state space. All in all, the oMDP reformulation permits us to solve finite M by means of M 1 using near-optimal planning methods leveraging on the special structure of the optimal value function [START_REF] Shani | A survey of pointbased POMDP solvers[END_REF]. This methodology results in the current state-of-the-art algorithm to optimally solving finite Dec-POMDPs [START_REF] Dibangoye | Optimally Solving Dec-POMDPs as Continuous-State MDPs[END_REF]. So it seems natural to wonder if the same methodology can also succeed when applied to the corresponding reinforcement-learning problem. In other words, how can a centralized algorithm learn to coordinate a team of agents with possibly contradicting perceptual information?

3 Learning in Dec-POMDPs as oMDPs

Using the oMDP reformulation, a natural approach to achieve centralized RL for decentralized stochastic control suggests applying exact RL methods. In the Q-learning algorithm [START_REF] Watkins | Q-Learning[END_REF], for example, one would learn directly the Q-value function when following a fixed policy π: for any control interval t P v0; ´1w,

Q π t ps t , a t q . " Rps t , a t q `γ1 V π t`1 pT ps t , a t qq (4)
with boundary condition Q π p¨, ¨q " 0. The policy improvement theorem provides a procedure to change a sub-optimal policy π into an improved one π Howard [1960]: for any control interval t P v0; ´1w,

πps t q .
" arg max atPAt Q π t ps t , a t q.

(5)

Unfortunately, this approach has three severe limitations. First, the occupancy states are unknown and must be estimated. Second, even if we assume a complete knowledge of the occupancy states, they lie in a continuum, which precludes exact RL methods to accurately predict α-functions even in the limit of infinite time and data. Finally, the greedy maximization required to improve the value function proved to be NP-hard in finite settings and problematic in continuous ones [START_REF] Radner | Team Decision Problems[END_REF], [START_REF] Kumar | Constraint-based dynamic programming for decentralized POMDPs with structured interactions[END_REF].

Addressing Estimation Issues

Although mappings T and R in M 1 are unknown to either agents or a centralized algorithm, one can instead estimate on the fly both T ps 0 , a 0:t´1 q and RpT ps 0 , a 0:t´1 q, a t q for some fixed plan ρ . " a 0: ´1 through successive interactions of agents with the environment. To this end, we shall distinguish between two settings. The first one assumes a generative model is available during the centralized learning phase, e.g. a black box simulator; and the second does not. In both cases, we build on the concept of replay pool [START_REF] Mnih | Human-level control through deep reinforcement learning[END_REF], except that we extend it from stationary singleagent domains to non-stationary multi-agent domains. If a generative model is available during the learning phase, then a Monte Carlo method can approximate T ps 0 , a 0:t´1 q and RpT ps 0 , a 0:t´1 q, a t q arbitrary closely. To this end, the generative model allows the agents to sample experiences generated from M . A -steps experience is a 4-tuple ξ .

" px 0: ´1, u 0: ´1, r 0: ´1, z 1: q, where x 0: ´1 are sampled hidden states, u 0: ´1 are controls made, r 0: ´1 are reward signals drawn from the reward model, and z 1: are the resulting observations, drawn from the dynamics model. If we let D ρ .

" tξ ris u iPv1:Kw be the replay pool of K i.i.d random samples created through successive interactions with the generative model, then empirical occupancy state ŝt « T ps 0 , a 0:t´1 q and reward Rt « RpT ps 0 , a 0:t´1 q, a t q corresponding to the current D ρ are given by: for any control interval t P v0 : ´1w, ŝt px, oq

.

" 1 K ř K i"1 δ x px ris t q ¨δo pu ris 0:t , z ris
1:t q (6) and Rt . " 1 K ř K i"1 r ris t , (7)
where δ x p¨q and δ o p¨q denote the delta-Dirac mass located in hidden state and joint history pair, respectively. By the law of large numbers the sequence of averages of these estimates converges to their expected values, and the standarddeviation of its error falls as 1{ ? K [Sutton and Barto, 1998, chapter 5]. The error introduced by Monte Carlo when estimating T pŝ t´1 , a t´1 q instead of T ps 0 , a 0:t´1 q is upper bounded by 2 { ? K. The proof follows from the performance guarantee of the policy-search algorithm by [START_REF] Bagnell | Policy Search by Dynamic Programming[END_REF]. Hence, to ensure the learned value function is within ą 0 of the optimal one, one should set the replay-pool size to K " Op4 2 2 q. When no generative model is available, the best we can do is to store samples agents collected during the learning phase into replay pools D ρ , one experience for each episode within the limit size of K. We maintain only the K recent experiences, and may discard2 hidden states since they are unnecessary for the updates of future replay pools and the performance measure. The rationale behind this approach is that it achieves the same performances as a Monte Carlo method for the task of approximating T ps 0 , a 0:t´1 q and RpT ps 0 , a 0:t´1 q, a t q given a fixed plan ρ . " a 0: ´1. In fact, if we let D ρ be a replay pool of K i.i.d. samples generated according to ρ, the empirical occupancy state ŝt « T ps 0 , a 0:t´1 q and reward Rt « RpT ps 0 , a 0:t´1 q, a t q corresponding to D ρ are given by ( 6) and ( 7), respectively. One can further show this approach preserves performance guarantees similar to those obtained when using a generative model.

Addressing Prediction Issues

The key issue with large (possibly continuous) spaces of occupancy states and decision rules is that of generalization, that is, how experiences with a limited subset of occupancy states and decision rules can produce a good approximation over a much larger space. Fortunately, a fundamental property of oMDPs is the convexity of the optimal value function over the occupancy-state space, see Lemma 1. Building on this property, we demonstrate a simple yet important preliminary result before stating the main result of this section.

Lemma 2. For any arbitrary M 1 (resp. M ), the optimal Q-value function is the upper enveloppe of sets Ω 0: of αfunctions over occupancy states and joint decision rules: for any control interval t, Q t ps t , a t q " max qtPΩ t xs τ d a τ , q t y, where q t P Ω t are appropriate α-functions, and s τ d a τ denotes the Hadamard product3 . Proof. We proceed by induction to prove this property. In the following we assume that all operations (e.g. integrals) are well-defined in the corresponding spaces. For control interval t " ´1, we only have to take into account the immediate reward and, thus, we have that Q ˚ ´1ps ´1, a ´1q " Rps ´1, a ´1q. Therefore, if we define the set Ω ˚ ´1 " tq ´1u, where q ´1px, o, uq .

" rpx, uq, the property holds at control interval t " ´1. We now assume the property holds for control interval τ `1 and we show that it also holds for control interval τ . Using (2) and ( 4), we have that, Q τ ps τ , a τ q " Rps τ , a τ q γ1 max aτ`1 Q τ `1pT ps τ , a τ q, a τ `1q, and by the induction hypothesis, let s τ `1 .

" T ps τ , a τ q:

Q τ `1ps τ `1, a τ `1q " max qPΩ τ `1 ş X,O,U s τ px, oqa τ pu|oq ş X,Z,U p u,z px, yqa τ `1pu 1 |o, u, zq qpy, po, u, zq, u 1 qdudodxdydzdu 1 .

With the above, Q τ ps τ , a τ q " max aPAτ`1,qPΩ τ `1 ş X,O,U s τ px, oqa τ pu|oq rrpx, uq `γ1 ş Y,Z,U p u,z px, yqapu 1 |o, u, zq qpy, po, u, zq, u 1 qdydzdu 1 sdudodx.

At this point, we can define the bracketed quantity as q aτ`1 px, o, uq . " rpx, uq `γ1 ş X,Z,U p u,z px, yq a τ `1pu 1 |o, u, zqqpy, po, u, zq, u 1 qdydzdu 1 .

Note that α-function q aτ`1 is independent of occupancy state s τ and decision rule a τ for which we are computing Q τ . With this, we have that Q τ ps τ , a τ q " max q a : aPAτ`1,qPΩ τ `1 xs τ d a τ , q a y and, thus the lemma holds.

Lemma 2 generalizes the convexity property demonstrated in Lemma 1 from optimal value functions over occupancy states to optimal value functions over occupancy states and decision rules. As a consequence, finite sets Ω 0: ´1 of α-functions can produce solutions arbitrarily close to the optimal Q-value function Q 0: ´1. Though Q-value function Q 0: ´1 generalizes from a pair of occupancy state and decision rule to another one, storing and updating a convex hull is non trivial. Instead of learning the optimal Q-value function over all occupancy states and decision rules, we explore a simpler yet tractable alternative, which will prove sufficient to preserve ability to eventually find an optimal plan starting at initial occupancy state s 0 .

Theorem 1. For any arbitrary M 1 (resp. M ), the Q-value function Q ρ 0 : ´1 under an optimal plan ρ ˚. " a 0: ´1 starting at initial occupancy state s 0 is linear in occupancy states and decision rules: Q ρ t ps t , a t q " xs t d a t , q ρ t y where q ρ t .

" arg max qtPΩ t xT ps 0 , a 0:t´1 q d a t , q t y .

Proof. The proof derives directly from Lemma 2. First, notice that any arbitrary non-dominated joint plan ρ induces a sequence of α-functions q ρ 0: ´1 stored in Ω 0: ´1, which proves the Q-value function under a fixed plan is linear over occupancy states and joint decision rules. In addition, each α-function q ρ t P Ω t describes the expected returns from t P v0; ´1w onward, when agents follow non-dominated joint plan ρ. If we let ρ ˚be a greedy joint plan with respect to Q 0: ´1, then q ρ 0: ´1 is maximal along tT ps 0 , a 0:t´1 qu tPv0; ´1w .

Theorem 1 proves that the Q-function for a given optimal joint plan achieves performance at the initial occupancy state s 0 as good as the Q-value function for an optimal joint policy. Standard policy iteration algorithms search for an optimal joint policy, which requires a finite set of α-functions to approximate V ˚/Q ˚, hence the resulting PWLC approximator is tight almost everywhere. Building upon Theorem 1, we search for an optimal ρ, which requires only a single α-function to approximate V ρ {Q ρ , thus the resulting linear approximator is loose everywhere except in the neighborhood of a few points. The former approach may require less iterations before convergence to an optimal joint policy, but the computational cost of each iteration shall increase with the number of α-functions maintained. The latter approach may require much more iterations, but all iteration shares the same computational cost.

Addressing Plan Improvement Issues

This section introduces a procedure to improve a plan starting with a sub-optimal one. Suppose we have determined the value function V ρ 0: ´1 for any arbitrary ρ . " a 0: ´1. For some control interval t P v0; ´1w, we would like to know whether or not we should change decision rules a 0:t to choose ā0:t ‰ a 0:t . We know how good it is to follow the current plan from control interval t onward-that is V ρ t -but would it be better or worse to change to the new plan? One way to answer this question is to consider selecting ā0:t at control interval t and thereafter following decision rules a t`1: ´1 of the existing ρ. The value of the resulting joint plan is given by Jpā 0:t´1 q `γ1 V ρ t`1 pT ps 0 , ā0:t´1 qq. The key criterion is whether this quantity is greater or less than Jpρq. Next, we state the plan improvement theorem for occupancy-state Markov decision processes.

Theorem 2. Let ρ . " a 0: ´1 and ρ . " ā0: ´1 be any pair of plans and J 0: be a sequence of α-functions such that, for all t, J t px t , o t q . " Etα 0 r 0 `. . . `αt r t |b 0 , x t , o t , a 0:t´1 u. Let st . " T ps 0 , ā0:t´1 q and s t . " T ps 0 , a 0:t´1 q be occupancy states at any control interval t P v0; ´1w under ρ and ρ, respectively. Then, xā 0:t ˚´1 , a t ˚: ´1y such that t ˚" arg max tPv0; ´1w xs t ´st , J t ´γ1 V ρ t y is as good as, or better than, ρ.

Proof. The proof follows from the difference between the performance measure of ρ . " a 0: ´1 and ρ . " ā0: ´1. Let ς t pρ, ρq be the advantage of taking plan xā 0:t´1 , a t: ´1y instead of ρ: for any control interval t P v0; ´1w, ς t pρ, ρq " Jpā 0:t´1 q `γ1 V ρ t pT ps 0 , ā0:t´1 qq ´Jpρq " Jpā 0:t´1 q ´Jpa 0:t´1 q `γ1 pV ρ t ps t q ´V ρ t ps t qq " xs t ´st , J t ´γ1 V ρ t y.

If we let t ˚. " arg max t"0,1,..., ´1 ς t pρ, ρq, then plan xā 0:t ˚´1 , a t ˚: ´1y achieves the highest advantage among plan set txā 0:t´1 , a t: ´1yu tPv0; ´1w constructed based on ρ.

If t ˚" 0, then xā 0:t ˚´1 , a t ˚: ´1y " ρ, and no improved plans were found from plan set generated from ρ. Otherwise, new xā 0:t ˚´1 , a t ˚: ´1y must be better than ρ.

The plan improvement theorem shows how, given ρ . " a 0: ´1 and α-function q ρ 0: ´1, we can easily evaluate a change in ρ at any control interval to a particular (possibly improved) plan. To ease exploration towards promising plans, we investigate the -greedy maximization (or softmaximization). At each control interval t and occupancy state s t , it randomly selects ât with probability ; otherwise, it greedily selects ât w.r.t. the current Q-value function

Q ρ t : ât . " arg max at : a 1 t PA 1 t ,...,a n t PA n t Q ρ t ps t , a t q,
where ρ . " â0: ´1. Unfortunately, this operation proved to be NP-hard for finite M and problematic in continuous M Radner [1962], [START_REF] Kumar | Constraint-based dynamic programming for decentralized POMDPs with structured interactions[END_REF]. We present a mixed-integer linear programming method, which successfully performs the greedy maximization for finite M . Mixed-Integer Linear Program 1 builds on MacDermed and Isbell [2013], which introduced an integer program for the greedy maximization in finite M . We also exploit the occupancy state estimation, in which ŝt replaces s t , and the current α-function q ρ t .

Mixed-Integer Linear Program 1 (For finite M ).

Maximize

s.t.: ř u j a t pu j , u i |oq " a i t pu i |o i q, @i, u i , o (9) ř u a t pu|oq " 1, @o (10)

where ta t pu|oqu and ta i t pu i |o i qu are positive and boolean variables, respectively.

Mixed-Integer Linear program 1 optimizes positive variables ta t pu|oqu uPU,oPOt , one positive variable for each control-history pair. More precisely, each variable represents the probability a t pu|oq of control u being taken given that agents experienced joint history o. Constraints must be imposed on these variables to ensure they form proper probability distributions (10), and that they result from the product of independent probability distributions (9), one independent probability distribution for each agent. In order to make the description of the conditional independence,

a t pu|oq " a 1 t pu 1 |o 1 q ˆ¨¨¨ˆa n t pu n |o n q, (11)
we use additional variables ta i t pu i |o i qu iPv1;nw,u i PU i ,o i PO i t . Marginalizing out both sides of (11) over all control-history pairs of all agents except agent i, denoted ´i, leads to (9). That is not sufficient to ensure conditional independence in general. If we further constrain ta i t pu i |o i qu to be boolean, then system of equations ( 9) implies (11).

Given ( 9) and (10), agent variables ta i t pu i |o i qu u i PU i ,o i PO i t describe a proper probability distribution, so we omit corresponding constraints. Our greedy maximization approach is fundamentally different from previous ones, including the integer program by [START_REF] Macdermed | Point Based Value Iteration with Optimal Belief Compression for Dec-POMDPs[END_REF] and the constraint optimization program by [START_REF] Kumar | Constraint-based dynamic programming for decentralized POMDPs with structured interactions[END_REF], [START_REF] Dibangoye | Optimally Solving Dec-POMDPs as Continuous-State MDPs[END_REF]. First, while previous approaches made use of boolean variables, we use both positive and boolean variables instead. Next, prior approaches optimize a value function represented as a convex hull; we optimize an α-function instead.

The oSARSA Algorithm

This section presents the oSARSA algorithm with tabular representations and function approximations (using either linear functions or deep neural networks) along with convergence guarantees. oSARSA algorithms are specializations of Policy Iteration, except that we use plans instead of policies. For the sake of conciseness, we describe a generic algorithm, which can fit to either tabular or approximate representations.

In Dec-POMDPs, the goal of oSARSA is to learn q 0: ´1, a sequence of α-vectors of an optimal plan ρ ˚. In particular, we must estimate q t px, o, uq for the current plan ρ and for all reachable state x, joint history o, control u, and any control interval t. At the same time, the algorithm changes ρ towards improved plans according to the plan improvement theorem. The improved plans are constructed by exploring the occupancy-state space according to -greedy plans (see Section 3.3). To provide good estimations, we store all experiences in data set D ρ , from which we estimate the occupancy states and returns under ρ for any control interval (see Section 3.1). Upon estimating occupancy state ŝ and selecting joint decision rule a, we update parametrized αfunction q t with parameter θ t using q t`1 , D Initialize ḡ " ´8, ρ and q 0: ´1 arbitrary, and D ρ. while q 0: ´1 has not converged do Select -greedily ρ w.r.t. q 0: ´1 and D ρ.

Compose D ρ with N trajectories tξ rτ s u N τ "1 . Estimate pg, ςq from r ř ´1 t"0 Rt |D ρ , ŝ0 " s 0 s. If g ´ς ě ḡ then pρ, ḡ, D ρq " pρ, g `ς, D ρ q. Update α-functions q 0: ´1 as described in (12). end while occupancy state and joint decision rule is visited infinitely often. Under these assumptions, the sequence q rτ s 0: ´1 generated by oSARSA converges with probability 1 to q 0: ´1.

Proof. Under these assumptions, we define H ρ that maps a sequence of α-vectors q 0: ´1 to a new sequence of αvectors H ρ q 0: ´1 according to the formula: for all hidden state x, joint history o and control u, at control interval t, pH ρ q 0: ´1qpx, o, uq " rpx, uq `γ1 12), we converge with probability 1 to q ρ 0: ´1. It now remains to be verified that the plan improvement step of the oSARSA algorithm changes the current plan for an improved one. Initially, ḡ is arbitrarily bad, so any new plan is an improved one. Then, ḡ " Jpρq for the current best plan ρ since occupancy state and return are accurately estimated. Hence, when ever g ě ḡ, we know that the new plan ρ yields a performance measure Jpρq superior to Jpρq, thus ρ improves ρ. We conclude the proof noticing that in finite M , the number of deterministic plans is finite. As a consequence, by visiting infinitely often every pair of occupancy state and decision rule we are guaranteed to visit all deterministic plans, hence an optimal one.

It is now important to observe that we meet assumption (2) in Theorem 3 only when M is available. Otherwise, we rely on confidence bounds rg ´ς, g `ςs, e.g. Hoeffding's inequality, on estimate g « Jpρq. In particular, we use lower-bounds g ´ς on sample means instead of the sample means g themselves, to limit situations where g is overestimated. Small data sets often lead to suboptimal solutions, but as the number of experiences in data set D ρ increases, sample means and corresponding lower bounds get close to the mean, i.e., ς tends to 0. It is worth noticing that the memory complexity of the oSARSA algorithms is linear with the size of an α-function, i.e., Op|D ρ |q; and its time complexity is linear with the episodes.

Experiments

We ran the oSARSA algorithm on a Mac OSX machine with 3.8GHz Core i5 and 8GB of available RAM. We solved the MILPs using ILOG CPLEX Optimization Studio. We define features to use sequences of K last joint observations instead of joint histories, hence the dimension of the parameter vector θ is |X|p|U ||Z|q K for finite M . We evaluate our algorithm on multiple benchmarks from the literature all available at masplan.org: Mabc, Recycling, Gridsmall, Grid3x3corners, Boxpushing, and Tiger. These are the largest and the most challenging benchmarks from the Dec-POMDP literature. For each of them, we compare our algorithm to the state-of-the-art algorithms based on either a complete or a generative model: FB-HSVI [START_REF] Dibangoye | Optimally Solving Dec-POMDPs as Continuous-State MDPs[END_REF], RLaR [START_REF] Kraemer | Multi-agent reinforcement learning as a rehearsal for decentralized planning[END_REF], and MCEM [START_REF] Wu | Monte-Carlo Expectation Maximization for Decentralized POMDPs[END_REF]. We also reported results of the state-of-the-art model-free solver: (distributed) REIN-FORCE Peshkin et al. [2000]. For REINFORCE and oS-ARSA, we used hyper-parameters and β ranging from 1 to 10 ´3 with a decaying factor of 10 4 , sample size |D| " 10 4 . We use maximum episodes and time limit 10 5 and 5 hours, respectively, as our stopping criteria. Surprisingly, REINFORCE performs very well on domains that consist of weakly coupled agents, see Figure 1. However, for domains with strongly coupled agents, e.g., Tiger or BoxPushing, it often gets stuck at some local optima. In contrast, oSARSA converges to near-optimal solutions when enough ressources are available over all domains, see Figure 1 and Table 1. Regarding the most challenging benchmarks, which require more resources, oSARSA stops before the convergence to a near-optimal solution; yet, it often outperforms the other RL algorithms. RLaR can achieve near-optimal result for small domains and short planning horizon ( ď 5q, assuming there exists a unique optimal plan. As for MCEM, it can solve infinite horizon problems, but similarly to REINFORCE may get stuck in local optima; this is essentially as they both use a form of gradient descent in a parametrized policy space. [START_REF] Foerster | Counterfactual Multi-Agent Policy Gradients[END_REF], namely RL for decentralized control, from model-based to model-free settings. This paradigm allows a centralized algorithm to learn on behalf of all agents how to select an optimal joint decision rule to be executed at each control interval based on all data available about the system during a learning phase, while still preserving ability for each agent to act based solely on its private histories at the execution phase. In particular, we introduced tabular and approximate oSARSA algorithms, which demonstrated promising results often outperforming Table 1: Comparing V ρ ps 0 q of all solvers when available, where the "-" sign mean "out of memory" and/or "out of time".

Discussion

Figure 1: Comparing V ρ ps 0 q of solvers with " 8 and γ " 0.9.

state-of-the-art MARL approaches for Dec-POMDPs. To do so, oSARSA learns a value function that maps pairs of occupancy state and joint decision rule to reals. To ease the generalization in such high-dimensional continuous spaces, we restrict attention to plans rather than policies, which in turn restricts value functions of interest to linear functions.

To speed up the greedy maximization, we used a MILP for finite settings-we shall use a gradient approach instead of a MILP for continuous settings in future works. Finally, we present a proof of optimality for a MARL algorithm when the estimation error is neglected. We shall investigate an approach to relax this somewhat restrictive assumption, perhaps within the probably approximately correct learning framework.

The RL for decentralized control paradigm is significantly different from the standard RL paradigm, in which agents have the same amount of information during both the learning and the execution phases. Another major difference lies in the fact that learned value functions in standard (deep) RL algorithms are mapping from histories (or states) to reals. In contrast, oSARSA learns a value function that maps occupancy-state/decision-rule pairs to reals-spaces of occupancy states and joint decision rules are multiple orders of magnitude larger than history or state spaces. As a consequence, standard (MA)RL methods, e.g. REINFORCE and MCEM, may converge towards a local optimum faster than oSARSA, but the latter often converges towards a nearoptimal solution. oSARSA uses occupancy states instead of joint histories mainly because occupancy states are (so far minimal) sufficient statistics for optimal decision-making in Dec-POMDPs-using joint histories instead of occupancy states may lead to suboptimal solutions except in quite restrictive settings. For example, RLaR learns value functions mapping history/action pairs to reals, but convergence towards an optimal solution is guaranteed only for domains that admit a unique optimal joint plan-which essentially restricts to POMDPs [START_REF] Kraemer | Multi-agent reinforcement learning as a rehearsal for decentralized planning[END_REF].

  This paper extends a recent but growing (deep) MARL paradigm Szer et al. [2005], Dibangoye et al. [2016], Kraemer and Banerjee [2016], Mordatch and Abbeel [2017],

  denotes the time-step dependent weighting factors, often set to γ t " γ t for discounted problems or γ t " 1

	where α t
	i 1:t q, where o i 0 " H and o i t P O i t . A tth joint
	decision rule, denoted a t : O t Þ Ñ PpU q, can be specified as a t pu|oq . " ś n i"1 a i t pu i |o i q, where O t . " O 1 t ˆ¨¨¨ˆO n t , o i P O i t and o . " po 1 , . . . , o n q P O t . From control interval t
	onward, agents collectively receive discounted cumulative rewards, denoted by random variable R t . " γ 1 r t `¨¨¨`γ r ,

  where β τ is a step size, and quantity ∇q t px, o, uq denotes the gradient of q t at px, o, uq w.r.t. some parameter θ t . Using tabular representations (e.g., finite/small M ), θ t " q t and thus ∇q t px, o, uq is a unit vector e x,o,u whose value at px, o, uq is one and zero otherwise. Using linear function approximations (e.g., continuous/large M ), q t px, o, uq . " φ t px, o, uq J θ t , where ∇q t px, o, uq " φ t px, o, uq is the feature vector at px, o, uq. Algorithm 1 shows the pseudocode of oSARSA. To establish the convergence of oSARSA, we introduce the following assumptions. Theorem 3. Consider assumptions: (1) The stepsizes tβ τ u τ "1,2,... satisfy Robbins and Monro's conditions; (2) The occupancy states ŝ0: ´1 and immediate returns R0: ´1 are accurately estimated; and (3) Every pair of reachable Algorithm 1 The oSARSA Algorithm

					ρ and a t`1 by
	means of temporal difference learning: for all px, o, uq,
	θ t rτ `1s	. " θ	rτ s t `βτ E ŝ,a,D,at`1 tδ t ∇q	rτ s t px, o, uqu (12)
	δ t " r `γ1 q t`1 py, o 1 , u 1 q rτ s	´qrτs t px, o, uq,

  Etv t`1 py, o ' pu, zqqu, where v t px, oq . " q t px, o, ρpoqq and ρpoq is the control prescribed by ρ at joint history o. Then, the plan evaluation step of the oSARSA algorithm is of the form

	q	rτ `1s t	px, o, uq " p1 ´βt qq t px, o, uq `βt κ rτ s rτ s t px, o, uq,
		κ rτ s t px, o, uq " pH ρ q 0: ´1qpx, o, uq `wt px, o, uq, rτ s
	where w t px, o, uq " rpx, uq `γ1 v	rτ s t`1 py, o ' pu, zqq	ṕH
		ρ q 0: ´1qpx, o, uq is a zero mean noise term. Using this rτ s
	temporal-difference update-rule, see (

In continuous M , α-functions represent linear functions (including parametric ones); whereas in finite M , α-functions become α-vectors, that is finite-dimensional vectors.

Note that one should keep hidden states when available since they often speed up the convergence.

@px, o, uq : rsτ d aτ spx, o, uq . " sτ px, oq ¨aτ pu|oq.