{'fraction_non_alphanumeric': 0.05358587902083755, 'fraction_numerical': 0.01375682783734574, 'mean_word_length': 3.950550826239359, 'pattern_counts': {'":': 0, '<': 8, '<?xml version=': 0, '>': 5, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 2, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 23, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Approximated Multi-Agent Fitted Q Iteration

We formulate an efficient approximation for multi-agent batch reinforcement learning, the approximated multi-agent fitted Q iteration (AMAFQI). We present a detailed derivation of our approach. We propose an iterative policy search and show that it yields a greedy policy with respect to multiple approximations of the centralized, learned Q-function. In each iteration and policy evaluation, AMAFQI requires a number of computations that scales linearly with the number of agents whereas the analogous number of computations increase exponentially for the fitted Q iteration (FQI), a commonly used approaches in batch reinforcement learning. This property of AMAFQI is fundamental for the design of a tractable multi-agent approach. We evaluate the performance of AMAFQI and compare it to FQI in numerical simulations. The simulations illustrate the significant computation time reduction when using AMAFQI instead of FQI in multi-agent problems and corroborate the similar performance of both approaches.


Introduction
Reinforcement learning is a framework which considers stochastic, sequential decision-making problems with unknown dynamics [1]. These problems are modelled as Markov decision processes (MDPs). In each decision round of an MDP, a decision maker observes the current state of the system and must provide a decision or equivalently, a control. A scalar reward is subsequently revealed, and the current state shifts to a new state according to a transition function defined by the dynamics of the problem. In reinforcement learning, the transition function is unknown. Only the reward, the initial and resulting states, and the control are used to improve future controls. Batch reinforcement learning [2,3,4] is a subfield of reinforcement learning in which information about the system in the form of a set of historical transitions is known a priori to the decision maker. This is in contrast to typical reinforcement learning algorithms, e.g., the Q-learning algorithm [5], in which information is gathered in an online fashion. Batch reinforcement learning improves over its online counterpart (i) by reusing the gathered information multiple times (experience replay [6]) to increase the approach's convergence speed, (ii) by fitting an approximated function (e.g., Q or value functions) in between updates to mitigate instabilities, and (iii) by averaging similar transitions from the batch information to better estimate the MDP's stochastic model [2]. In batch reinforcement learning, a prevalent approach [2] is the fitted Q iteration (FQI) [4].
In multi-agent reinforcement learning, agents make sequential decisions to maximize their joint or individual rewards [7, Email addresses: antoine.lesage-landry@polymtl.ca (Antoine Lesage-Landry), dcal@berkeley.edu (Duncan S. Callaway) 8]. The agents can be fully cooperative, i.e., maximizing a joint reward function, fully competitive, i.e., the agents' objectives are opposed, or a combination of both [7,8]. The main challenge when considering the multi-agent reinforcement learning problem comes from the cardinality of the joint control set as it increases exponentially with the number of agents. This adds to the difficulty that the curse of dimensionality already poses to (approximate) dynamic programming-based methods [9,7,8]. The design of an approach that relies only on local control sets is, therefore, highly desirable to enable the implementation of batch reinforcement learning methods in real-world multi-agent systems, e.g., electric power systems [10]. For example, the approach we present in this work could extend current methods for demand response or distributed energy resource management like [11,12,13] to multi-agent implementations and increase the benefits for the electric grid without significantly impacting the computational cost of the approach. Other applications for multi-agent reinforcement learning include the control of a robot team [14] or of an autonomous vehicle fleet [15], autonomous driving [16], and stock trading [17]. In this work, we consider the batch reinforcement learning framework and design the approximated multi-agent fitted Q iteration (AMAFQI), an efficient approximation of FQI [4] tailored to fully cooperative, multi-agent problems.

Related work
Multi-agent reinforcement learning has been studied by many authors and the main recent advancements to this body of work are reviewed in [7,18,19,20]. Multi-agent extensions to the Q-learning algorithm [5] are reviewed in [7]. Reference [18] focuses on theory-backed approaches. An overview of multiagent deep reinforcement learning is presented in [19,20]. In our work, we are interested in multi-agent extensions of batch reinforcement learning [2], and more specifically, of the kernelbased [3] FQI [4] framework. Multi-agent problems have also been studied under other reinforcement learning frameworks, e.g., classical Q-learning [21,22] or actor-critic approaches [23,8]. We review the literature relevant to multiagent FQI next.
To the best of the authors' knowledge, the only extension of FQI to the multi-agent setting are presented in [24,25,26]. References [24,25] only consider deterministic problems. The extension relies on the neural fitted Q (NFQ) algorithm [27]. The NFQ is a modified FQI approach that uses a neural network instead of a regression tree as the fitting method used to generalize the Q-value to all state-control pairs (see Section 2.1). Similarly to our approach, their work is based on the ideas of [22] in which an efficient multi-agent Q-learning algorithm [5], the Distributed Q-learning algorithm, for online, deterministic settings is presented, to obtain an approach that does not require computations over the joint control set. The work of [24,25] differs from ours because it uses an opportunistic approach enabled by the deterministic setting. Furthermore, [24,25] only provide an empirical analysis of their algorithm because the properties of the neural network are hard to analyze. In our work, we (i) consider general stochastic problems, (ii) present a detailed derivation for AMAFQI, and (iii) provide a convergence analysis of the approximated local Q-functions used by our approach. Moreover, we characterize the performance of the greedy policy for AMAFQI. Lastly, [26] proposes a general, fully decentralized, multi-agent fitted Q algorithm that accounts for competitive agents and where any function approximator can be used to approximated the local Q-function. The authors further derive a finite-sample performance guarantee for their approach. However, [26]'s algorithm requires optimizing local Q-function over the joint control space which grows exponentially with the number of agents. Our main contribution is to provide an approach which uses only local control spaces.
Our specific contributions are: • We formulate the approximated multi-agent fitted Q iteration (AMAFQI). AMAFQI is an efficient approximation of the FQI algorithm for multi-agent settings. In each iteration, AMAFQI's computation scales linearly in the number of agents instead of exponentially as in FQI.
• We propose a policy search for AMAFQI and show that it is a greedy policy with respect to the approximation of the centralized, learned Q-functions from each agent.
• We derive a very efficient extension of AMAFQI, AMAFQI-L, that further reduces the computation requirement of the approach.
• We show the convergence of the local Q-function approximations computed by AMAFQI to unique and finite functions.
• We numerically evaluate the performance of AMAFQI. We show the similar performance and significant decrease in computation times when AMAFQI and AMAFQI-L are used instead of FQI.

Preliminaries
We consider an MDP (X, U, f, r) where multiple agents must implement a control to maximize their expected joint cumulative reward. Let m ∈ N be the number of agents. We assume m > 1. Let X ⊆ R n×m , U ⊆ R p×m , and W ⊆ R s×m where n, p, s ∈ N be the joint state, control, and disturbance space, respectively. Let x ∈ X be a joint state, u ∈ U be a joint control, and w ∈ W be a random disturbance. Let f : X × U × W → X express the state transition function of the problem. The function f maps an initial state, a control and a disturbance to a resulting state. Lastly, let r : X × U × W → R be the function that returns the reward associated with an initial state, control, final state, and disturbance tuple. We make the following assumption regarding the reward function. Assumption 1. The reward function r is bounded below and above such that 0 ≤ r(x, u, w) ≤ R < +∞ for all (x, u, w) ∈ X × U × W.
The assumption on the upper bound of the reward function is a standard assumption for MDPs in reinforcement learning [4]. The lower bound assumption is mild because if not met, a constant can be added to the reward function so that it is nonnegative. This translation does not change the optima [22].
To easily differentiate local and joint controls, we define local control variables and spaces. We let A j ⊂ R p be the local control space of agent j where U = × m j=1 A j . We denote a local control by a ∈ A j and add the superscript j to refer to the j th agent if needed.
Formally, the m agents want to cooperatively solve the following problem: where β ∈ [0, 1) is the discount factor. The variables u T and x T represent the joint control and state at the decision round T , respectively. The random disturbance at T is represented by w T . Successive states are obtained from The expectation in (1) is taken with respect to the probability of w T given the state and control at round T . We consider the batch reinforcement learning framework [2,3,4]. In this setting, f is unknown and only examples of past transitions can be used to solve (1). The decision makers or agents have access to batch data representing historical transitions [4]. The batch data is used to first compute an approximation of the Q-function and, second, to evaluate a policy. Let L ∈ N be the number of available samples in the batch data. The batch data set S L is defined as: where x l + refers to the state observed after control u l was implemented in state x l . These samples do not need to be generated from continuous experiments. Specifically, we focus on regression tree-based FQI approaches [4]. FQI is introduced in detail in the next subsection.

Fitted Q iteration
We recall the motivation for FQI as presented in [4]. The state-action value or Q-function Q : X × U → R is the unique solution to the Bellman equation: where β ∈ [0, 1). The expectation is taken with respect to the probability of w given the state x and control u. By the contraction mapping theorem [28], the Q-function can be obtained by successively solving for all N ≥ 1 with the boundary condition Q 0 (x, u) = 0 for all (x, u) ∈ X × U. In the deterministic case, (2) can be expressed as: where δ : X × U → X is the deterministic function that returns the resulting state given a pair state-control. Given S L and supposing Q N−1 is available, then for all data points l = 1, 2, . . . , L, we can compute because r(x l , u l ) = r l and δ(x l , u l ) = x l + . The FQI then works in the following way. Pairs of x l , u l and their respective Q N x l , u l -value can be generated using (3) for all l in the batch data. Then, an approximationQ FQI N (x, u) of Q N (x, u) is obtained by fitting a function over the pairs x l , u l , Q N x l , u l for l = 1, 2, . . . , L. This is done to estimate the state-action values for all state-control pairs based on the batch data. Us-ingQ FQI N−1 in (3) instead of Q N−1 , we can compute the stateaction values at N, fit a function again based on the new pairs and obtainQ FQI N . This process is then repeated until convergence. Finally, the authors of [4] argue that the process described above provides an adequate approximationQ FQI N (x, u) for the stochastic case as well. In the stochastic case, the conditional expectation of (3)'s right-hand side given the current state and control is required for the update. Least squares regression [4] or the averaging at leaf nodes of regression tree methods [2] estimates the conditional expectation of the dependent variables given the independent variables, respectively thê Q FQI N (x l , u l ) and x l , u l , x l + , r l in this setting. Least squares and tree regression methods hence approximate the right-hand side of (3) in the stochastic case [2,4].

Regression tree methods
In this work, we use a regression tree to generalize the local Q-function and state-control pairs. Regression trees are chosen as the regression methods because (i) their properties allow us to establish the AMAFQI's convergence (see Section 4) and (ii) they are computationally efficient, scalable and robust to noisy data [4]. We now introduce regression tree methods. Let I ⊆ R n+p and O ∈ R be, respectively, the input and output sets of the data set D = i l , o l ∈ I × O, l = 1, 2, . . . , L . Regression tree methods subdivide the input set into partitions of input points i l using binary splits. Each partition is then given a unique output value. In regression trees, this is typically the average of all output points o l belonging to the partition. Multiple techniques exist to generate regression trees, e.g., KD-Tree [29], CART [30], Totally Randomized Trees [31], or Extra-Trees [31]. The reader is referred to [32] for a detailed description of regression trees. We now state relevant properties and assumptions which we use in the next sections.
Using a regression tree method, a functionĥ : I → O fitted to the data set D can be expressed as [4]: , where I x , the indicator function, returns 1 if x is true and 0 otherwise, and P(i) returns the tree partition input i is part of. For ensemble methods, the kernels , where the subscript k refers to the k th regression tree of the ensemble which consists of e trees.
In this work, two assumptions about the regression method we use are made. These assumptions are similar to [4].  Moreover, the aforementioned definition of the kernel implies that the sum of the kernel's absolute value is also one when Assumption 3 is satisfied because kernels are nonnegative. As noted by [4], Assumption 2 is satisfied naturally by a tree method like the KD-Tree. If the partitions generated by the tree method are random or depend on the output, this assumption can be met by computing the partitions and thus the kernels only once, i.e., when the first AMAFQI iteration is performed. This is the case, for example, for Totally Randomized Trees [31] which we use in Section 5. Regression tree approaches satisfy Assumption 3 by construction [33,3,4].

Approximated Multi-agent Fitted Q iteration
We now present our multi-agent approximation of FQI, AMAFQI. The fitting iterations and policy evaluation of AMAFQI only depend on the local control space of the agents and do not necessitate computations over the joint control space as would require FQI. This allows AMAFQI to be a tractable multi-agent approach for batch reinforcement learning problems because optimizing a fitted Q-function, e.g., in (3), must be done by enumeration due to the use of regression trees. The cardinality of the joint control space increases exponentially with the number of agents and the cardinality of the local control space. For FQI, this thus leads to a prohibitively large number of calculations when computing approximated Q-functions and when evaluating the policy in multi-agent settings. In the next subsections, we derive the AMAFQI algorithm and propose a greedy policy search for our approach.

Derivation
First, recall the standard Q-learning [5] update for deterministic settings [22]: with Q 0 (x, u) = 0 for all (x, u) ∈ X × U. We remark that in the deterministic setting, the reward r is not a function of the disturbance w. Second, consider for all agent j = 1, 2, . . . , m, the distributed Q-learning update for deterministic settings [22]: We refer to q j N as local q-functions. The proposition below establishes a relation between the centralized and distributed updates. Proposition 1] Let (x, a) ∈ X × A and suppose that r (x, u) ≥ 0 for all (x, u) ∈ X × U. Then, for a deterministic, fully cooperative problem, we have for all j = 1, 2, . . . , m and N ∈ N, where Q N and q j N are computed using (4) and (5), respectively.
Let N ∈ N and j ∈ {1, 2, . . . , m}. Consider the sample point x l , u l , x l + , r l ∈ S L . For now, let's assume that the function where u l ( j) is the j th component of the joint control u l , i.e., the control implemented by agent j. Proposition 1 leads to where Q N is computed via (4). We now depart from prior multi-agent reinforcement learning approaches to derive AMAFQI. We apply the reasoning behind FQI [4] to compute an approximationq j of the local q j -function. This is done iteratively. First, we compute the q j -function values at each batch data point using (5). Second, we fit the approximation functionq j N (x, a) to the set x l , u l ( j) ,q j N x l , u l ( j) , l = 1, 2, . . . , L using a regression tree method. Specifically, at iteration N ∈ N and for all samples l = 1, 2, . . . , L, let, Equivalently, we can express (6) aŝ for all j = 1, 2, . . . , m. The FQI-based approach is used to generalize the information obtained from the batch data to all statecontrol pairs [4]. The regression step estimates values of the localq j -function and thus approximates the maximum of the Qfunction for pairs not found in the batch data. From the above discussion, we have that In other words,q j N (x, a) can be interpreted as the maximum of the learned, centralized Q-function as approximated by agent j when they implement control a. LetQ j N be the approximation of the Q-function for agent j after N iterations given the available batch data. We can redefineq j N (x, a) in terms of the centralized Q-function approximation,Q j N , as: The right-hand side of (9) is similar to (8)'s and, hence, approximates the maximum of the centralized Q-function by the FQI approach [4]. We assume thatQ j N be a monotonically increasing. This assumption is justified by the fact that the learned Q-function, theq j -function, and the FQI approximation of the Q-function are all monotonic. The monotonicity follows in all three cases from the structure of the updates when r(x, u) ≥ 0 for all (x, u) ∈ X × U (see Lemma 1). Thus, we assume that an approximationQ j N of the centralized Q-function from each agent should share this property.
Next, we extend the aforementioned approach to the stochastic setting. Let j ∈ {1, 2, . . . , m} and N ∈ N. The stochastic analog of (5) [22] is: 4 The approximation of the local q j N -functions for stochastic problems are evaluated as follows. For all N ∈ N and l = 1, 2, . . . , L, let whereq j 0 (x, a) = 0 for all (x, a) ∈ X × A. We remark that (10), in comparison to the deterministic update given in (5), requires the evaluation of an expectation when the local q j -function is updated. Hence, the pairs i l, j and o l, j N cannot be fitted directly as it was done for the deterministic setting. Similarly to [4], a regression tree can be used to estimate an expectation. In our case, we apply a regression tree method over the set of joint states and actions to approximate the expectation from (10)'s second line. We refer to this expectation approximation as the local auxiliary q j N -functions,q j N , which we express as: where kernel x l , u l ; (x, u) , l = 1, 2, . . . , L are computed using a regression tree over the joint control set U. This is motivated by the fact that a regression tree averages the value of the outputs, viz., r (x, u, w) + β max a ∈A j q j N−1 ( f (x, u, w), a ), corresponding to the inputs in a given leaf node or partition, viz., the state-control pairs from the batch data. Alternatively, a linear regression or the Robbins-Monro approximation can be used to estimate the conditional expectation [4,22].
Finally, the approximation of the local q j N -function at (x, a) ∈ X × A is given by: where this time, kernel x l , u l ( j) ; (x, a) , l = 1, 2, . . . , L are computed using a regression tree over the local control space A j . We remark that whileq j N (x, u) is a function of the joint control space, we do need to evaluate its maximum over the joint control space and, therefore,q j N (x, u) leads to no scalability issue. Finally, we computeq j N , N = 1, 2, . . . , iteratively until a q j N −q j N−1 ∞ < , for some set tolerance > 0. A detailed representation of AMAFQI is provided in Algorithm 1. Lastly, establishing an exact relation between theq j -functions and the centralized Q-function as computed by FQI from Section 2.1 is a topic for future work.

Greedy policy search
Next, we propose a policy search for AMAFQI. We note that there are no guarantees that locally maximizingq j -functions leads to a joint optimal policy, e.g., if there are many joint optimal controls for a given state, maximizingq j across the agents j = 1, 2, . . . , m can lead to local controls belonging to different Generate the fitting pairs: Compute the auxiliaryq j N -function:

11:
Update theq j N -function: · max q j N−1 x l , u l ( j) ,q j N x l , u l .

12:
end for 13: end while joint optima, thus, resulting in a suboptimal joint control [22]. For this reason, our policy search sequentially identifies controls that yield an increase inq j 's maximum. The policy search is presented in Algorithm 2 and is shown to be a greedy policy in Theorem 1. The search can be extended to decentralized settings using a coordination mechanism [21,7,34]. Specifically, the decision set is ordered and tie breaking within the regression (Algorithm 1, Line 1) or classification (Algorithm 2, Line 9) trees is done according to this ordering. The batch data is also ordered and made available to all agents. Using this convention, each agent computes theq j -function for all j and uses Algorithm 2 to compute a unique greedy policy. Because the policy is unique, the local control implemented by agent j leads to a joint greedy control.
1: for all iteration N do 2: for x ∈ X do 3: for l in L(x) do 4: Update policy π N (x) according to (13). Generalize the greedy policy: larger than may enable the identification of suboptimal actions in cases where smaller values of γ lead to an inconclusive policy search. In this sense, by enabling a relaxation of the stringency of the policy, this parameter provides practical value, however we leave the exploration of its theoretical properties to future work. Let L(x) = l = 1, 2, . . . , L| x = x l , x l , u l , x l + , r l ∈ S L for all x ∈ X. The set L(x) identifies sample points l such data x l = x. Let N ∈ N where N ≥ 1. Consider the policy π N : X → U evaluated at a point from the batch data provided in (13) of page 7 with π 0 (x) = p1 for all x ∈ X. In (13), 1 is an m-dimensional vector consisting only of ones and p is an auxiliary parameter used to indicate that no control within the data set corresponds to the greedy maximum for state x after the N th AMAFQI iteration. It is used to restart the search. If π N (x) = p1 when the search ends, then the policy for state x must be approximated from similar states x for which a greedy decision has been identified, i.e., π N (x ) p1. This will be discussed at the end of this section. We now have the following results about the policy (13). Theorem 1. Let l ∈ {1, 2, . . . , L} such that π N x l p1 and u ∈ π N x l . Then, for all j = {1, 2, . . . , m}, we have: and π N x l is a 2γ-greedy policy at x l with respect to allQ j N , the monotonic approximations of the centralized Q-function from each agent.
The proof of Theorem 1 is presented in Appendix A. The above policy search identifies controls usingq j N -values that are within 2γ of theQ j N 's maximum for states x that belongs to the batch data. The search is inconclusive if the optimal control with respect toQ j N at state x ∈ X for some agent j is not in the batch data or if the optimal control performed poorly when sampled to generate the batch data because of stochasticity.

If π(x)
p1 for all x ∈ X, then the policy can be used directly. If π(x) = p1 for some x ∈ X, then we use an approximation to generalize the policy to all states similarly to the approach used to generalize theq-value to all state-control pairs. Letπ N : X → U be the approximation of the greedy policy with respect to allQ j N , j = 1, 2, . . . , m: Finally, if π(x) = p1 for all x ∈ X, the batch data does not permit to identify a 2γ-greedy policy with respect to allQ j Nfunctions. We remark thatπ N only needs to be computed once when the AMAFQI has converged to theq j functions. Thus, a significant advantage of AMAFQI's policy is that once the AMAFQI algorithm has converged, little to no computations are required to determine the controls when the policy is used. In comparison, the maximum over the joint control space U of the approximated Q-function needs to be computed when FQI is implemented. This must be done by enumeration because the maximization problem is neither analytically nor numerically solvable. In a multi-agent setting, the cardinality of the joint control space increases exponentially with the number of agents. Thus, removing the need to compute this maximum further reduces the computational burden of FQI when AMAFQI is used.

AMAFQI-L update
In the previous subsection, we presented a 2γ-greedy policy search with respect to the approximations of the centralized Qfunction of all agents j. This policy search can be modified to only use theq j N -function of a single agent j. We refer to this alternate policy as AMAFQI-L. Because of (8), the maximum of a singleq j N still approximates the centralized Q-function's maximum. The difference is that AMAFQI-L is now a 2γ-greedy policy with respect to agent j's approximation of the centralized Q-function rather than with respect to the approximation of all agents. Thus, this approximation is looser than the previous one. The main gain is, however, computational efficiency because only a singleq j -function must be iteratively computed. The computational requirement is thus constant with respect to the number of agents whereas it scales linearly and exponentially with the number of agents for AMAFQI and FQI, respectively.
AMAFQI-L's algorithm is similar to AMAFQI, except that j is set to a constant value within {1, 2, . . . , m} throughout the iterations N and the policy search. The algorithm is presented in Algorithm 3 of Appendix B. The AMAFQI-L policy search is identical to AMAFQI's, but uses (15) instead of (13): (15) The above discussion is formalized by the following result.
Corollary 1. Consider Theorem 1's assumptions, and suppose j ∈ {1, 2, . . . , m}. If u ∈ π L N x l , then we obtain: max u∈UQ j N x l , u −Q j N x l , u < 2γ, and π L N x l is a 2γ-greedy policy at x l with respect toQ j N . The proof follows from Theorem 1 for a single j.

Convergence
We show that each localq j N -function defined in (12) converges to a unique and finite function with respect to the infinity norm. We first establish the monotonicity ofq j N for all j.
We now state the convergence result.
Theorem 2. Suppose Assumptions 1−3 hold andq j 0 (x, a) = 0 for all (x, a, w) ∈ X×A×W and j = 1, 2, . . . , m. Thenq j N (x, a) converges to the unique limitq j S L (x, a), i.e., the unique maximum of theQ j -function for x and u( j) = a when estimated using the data set S L .
Moreover, for all > 0, there exists n( j) ∈ N such that for all N ≥ n( j), The proofs of Lemma 1 and Theorem 2 are in Appendix C and Appendix D, respectively. Theorem 2 ensures that there exist unique, finite-valuedq j -functions for the data set S L which can be used for the policy search. Thus,q j S L -functions for the data set S L can always be computed under the aforementioned assumptions. We remark that Theorem 2 applies to AMAFQI and AMAFQI-L because it holds for any j.
Similarly to [4], the error due to the regression-tree method (or any other supervised learning approach) is not modeled explicitly in this work. For AMAFQI, this error would translate inQ j -functions suffering itself from a larger approximation error. We remark that using a regression tree method allows us to establish the AMAFQI's convergence. The regression error is a topic for future investigation.

Numerical examples
In this section, we compare the performance of AMAFQI and FQI in numerical simulations. Our comparison uses FQI because it provides a learned Q-function that is the unique solution to Bellman's equation given the batch data [4]. It can, therefore, be considered as an adequate benchmark for the batch reinforcement learning setting. We test our approach on a multiagent, multi-state random problem similar to the example presented in [8,36].
LetQ FQI N : X × U → R be the approximated Q-function after N iterations evaluated via FQI [4]. Single problem instance simulations are run on a 2.4 GHz Intel Core i5 laptop computer and multiple instance simulations are run on the Savio computational cluster resource from the Berkeley Research Computing program. The computations ofq j N andQ FQI N for all samples l are parallelized to reduce the full computation time.

Setting
The multi-agent, multi-state random problem is as follows. We consider m agent having to coordinate their individual binary decision to reach one of the X joint states and maximize their reward over τ rounds. The joint binary decision determines the probability of moving from one state to another. Let P(x) : U × X → X be the transition matrix for state x ∈ X. All transition matrices are randomly generated according to uniform distributions and then normalized to obtain row-stochastic matrices. The reward is determined by the joint state at the end of a round. Let the mean reward for a state x ∈ X be R(x) ∼ Uniform[0,5]. The reward for reaching state x ∈ X is then r(x) ∼ Uniform[R(x) − 1 2 , R(x) + 1 2 ].

Experiments
We use Totally Randomized Trees [31] for the regression tree. We consider ensembles of 5 trees with each at a minimum of 10 data points in a leaf node. We let β = 0.5.

5 agents
We let m = 5 and card X = 5. We uniformly sample L = 2000 x l , u l , x l + , r l -tuples. The convergence of both AMAFQI and FQI implementations for this numerical experiment is shown in Figure 1. Figure 1 shows that q j N −q j N−1 ∞ and Q FQI N −Q FQI N−1 ∞ go to zero as N increases. Thus, both values converge to their respective unique and finite limits.
We compare the approximated value function at x for AMAFQI and FQI using the relative absolute difference between both maxima, defined as ∆( j, x) = , for j = 1, 2, . . . , m and x ∈ X. We sequentially compute theq j -andQ FQI -functions for 150 different problem instances, each time sampling a new data set S L . The average ∆( j, x) for all the problem instances are reported in Figure 2. The average over all problem instances of the relative difference ∆( j, x) is 2.92%.  For each problem instance, we compute the reward obtained by the greedy policies over 100 trials each with a time horizon τ = 100 rounds. For each trial, the initial state is randomly sampled. The average reward of FQI's, AMAFQI's, and AMAFQI-L's greedy policies are shown in Figure 3. The relative difference in average cumulative reward between AMAFQI and FQI is small and only 7.17%. The performance of AMAFQI-L is lower than AMAFQI's and leads to a 16.79% cumulative reward decrease in comparison to FQI.
We conclude by discussing the computation time of AMAFQI. The average computation time for a single iteration N and until convergence for FQI, AMAFQI and AMAFQI-L are reported in Table 1 for the 150 problem instances. The numbers from Table 1 given in parentheses and the subsequent similar tables represent the total computation times which includes the policy search. An iteration of AMAFQI and AMAFQI-L with and without the policy search has a shorter duration than an FQI iteration. Because the approximation requires more N iterations, AMAFQI still takes more time to converge. The amount of time to convergence for AMAFQI-L and FQI are similar. The problem size is still small given its binary controls and only 5 agents. Hence, an approach tailored to multi-agent settings is not necessarily needed yet. We provide this example of a small problem instance so that both AMAFQI and FQI can be simulated repetitively in an acceptable time frame. The comparison's bottleneck is FQI which is computationally very time consuming. Thus, given our computing infrastructure, we restrict our analysis to 10 agents or less as our objective is to compare AMAFQI's performances to FQI's on several instances.

9 and 10 agents
When the number of agents increases, the computational advantage of AMAFQI is clear. Tables 2 and 3 present the computation times for m = 9 with L = 5000 and m = 10 with L = 7000, respectively. The average ∆( j, x) is 8.17% when m = 9 and 7.90% when m = 10. We note that ∆( j, x) can be further reduced by increasing L at the expense of a longer computation time. The averaged cumulative reward for the 100 trials of each problem instance is provided in Figure 3 for both the 9-and 10-agent problem.
As shown in Tables 2 and 3, AMAFQI requires much less computation time than FQI to converge when m increases and only leads to a limited decrease in cumulative reward. In the present case, we register a 3.40% (m = 9) and 8.57% (m = 10) reduction of the average reward when using AMAFQI. Moreover, for AMAFQI, the total computation time until convergence includes most of the calculations required for the evaluation step. AMAFQI-L further reduces the total computation time. For m = 9, AMAFQI-L requires less than 8 minutes to convergence and to compute the policy instead of 84 minutes for AMAFQI and 3 hours (177 minutes) for FQI. When considering m = 10, AMAFQI-L needs 14 minutes whereas AMAFQI and FQI takes, respectively, 3 hours (181 minutes) and 12 hours (723 minutes). The performance of the AMAFQI-L policy is slightly lower and leads to a decrease in the cumulative reward of 8.65% (m = 9) and 10.32% (m = 10) with respect to FQI.

Conclusion
In this work, we propose the AMAFQI algorithm, a tractable multi-agent approximation of FQI for batch reinforcement  learning problems. We design an iterative policy search for AMAFQI and demonstrate that it is a greedy policy with respect to an approximation of the learned Q-function of all agents.
Our approach performs computations only over local control sets contrarily to FQI that works over the joint control space. The number of calculations required in each iteration of the algorithm grows linearly and exponentially with the number of agents, respectively, for AMAFQI and for FQI. Consequently, FQI is impractical and quickly intractable in presence of multiple agents. Our approach offers an efficient alternative for multi-agent batch reinforcement learning problems. We present a derivative of our approach, AMAFQI-L, which further reduces the computational burden of AMAFQI.
We consider a multi-agent batch reinforcement learning problem and compare the performance of AMAFQI with FQI. Numerical simulations show that the value functions computed by our approximation and by FQI are similar, e.g., with a discrepancy of 2.92% when m = 5, and that the performance level is also alike, e.g., with a difference of 7.12%. Lastly, computation times are compared and AMAFQI and AMAFQI-L outperform significantly FQI when the number of agent increases. For example, AMAFQI and AMAFQI-L require, respectively, only 181 minutes and 13 minutes against a total computation time of 723 minutes, on average, for FQI when m = 10.
In future work, we wish wish to investigate approaches to reduce the number of N iterations performed in AMAFQI before convergence, e.g., by considering the growing batch learning paradigm [2] in which an exploration policy is used, and new observed transitions are periodically incorporated in the batch data. Lastly, we would like to compare AMAFQI to FQI in a more sophisticated setting and use AMAFQI to dispatch flexible loads for network-safe demand response in unknown electric grids. This is a topic for future work.
We base our proof on [22,Proposition 2]. Consider the monotonic approximation of the centralized Q-functions from all agents,Q j N , j = 1, 2, . . . , m. Let l ∈ {1, 2, . . . , L}. Let 0 ≤ N < N such that for all j ∈ {1, 2, . . . , m} we have: and, max x, u l ( j) = max a∈A jq j N+1 (x, a) such that l ∈ L(x) for all j, then this last update was performed when the control u l was considered by the AMAFQI update. Otherwise, if there exists no l ∈ L(x) such that q j N+1 x, u l ( j) = max a∈A jq j N+1 (x, a) or the equality does not hold for all j, the search is inconclusive for the iteration N. By assumption, π N +1 (x l ) p1 and at least one policy update was performed.
Finally, iteration N + 1 coincides to the last time the max-imumQ j -function changed by at least γ for all j because of (A.1) and (A.2). Thus, for all u N +1 ∈ π N +1 (x l ) we have for all j ∈ {1, 2, . . . , m}. The monotonicity of theQ j N -function implies that (A.5) can be re-expressed as Using (A.7) in (A.6), we obtain max u∈UQ j N x l , u − Q j N x l , u N +1 < 2γ. Lastly, because the policy is not updated between N + 1 and N, we have that π N +1 x l = π N x l and thus, we have max u∈UQ j N x l , u −Q j N x l , u N < 2γ, where u N ∈ π N x l . Hence, the policy π N x l p1 is a 2γ-greedy policy for the approximation of the centralized Q-function of all agents. We prove this lemma by induction. Let (x, a) ∈ X × A and j ∈ {1, 2, . . . , m}. For N = 0, we haveq j 0 (x, a) = 0 for all x, a by assumption. For N = 1, we then have: · max q j 0 x l , u l ( j) ,q j 1 x l , u l = L l=1 kernel x l , u l ( j) ; (x, a) max 0, r l because L l=1 kernel x l , u l ; (x, u) = 1 for all (x, u) ∈ X × U. By assumption, r l ≥ 0 and, therefore,q j 0 (x, a) ≤q j 1 (x, a). We now show that, the induction hypothesis,q j N (x, a) ≤q j N+1 (x, a), holds for N → N + 1. At N + 1, theq j -function iŝ · max q j N+1 x l , u l ( j) ,q j N+2 x l , u l =q j N+2 (x, a) where we last used the definition ofq j N+2 . Thus, we have established thatq j N (x, a) is monotonically increasing for all (x, a) ∈ X × A and all N ∈ N.

Appendix D. Proof of Theorem 2
We first show thatq j N is bounded. By Assumption 1, we have r(x, u, w) ≤ R. Let j ∈ {1, 2, . . . , m}. By definition,q j 0 (x, a) = 0 for all (x, u) ∈ X × U. For N = 1, we have We further bound (D.1) and obtain: q j N (x, a) ∞ ≤ R 1−β for all N ∈ N. Therefore, q j N (x, a) ∞ is bounded from above for all j ∈ {1, 2, . . . , m}, and N ∈ N. We remark that this is an upper bound and not necessarily the supremum ofq j N .
By the monotone convergence theorem,q j N (x, a) → q j S L (x, a), whereq j S L (x, a) ≤ R 1−β is the supremum of the sequence given in (12) at (x, a) because the sequence is monotonically increasing by Lemma 1 and is bounded from above. A limit is unique if it exists and thereforeq j S L (x, a) is the unique solution of (7) at (x, a) ∈ X × A given the data set S L . It follows from (9) that the limit is the maximum of the centralized Q-function approximation at x and u( j) = a.
Lastly, for all > 0, there exists N(x, a) such that for all N ≥ N j (x, a) and we can write q j N (x, a) −q j S L (x, a) < . Consequently, for > 0, we have q j N −q j S L ∞ < . for all N ≥ n( j) = max x,a N j (x, a).