Title: MULTI-ADVISOR REINFORCEMENT LEARNING

Abstract: We consider tackling a single-agent RL problem by distributing it to n learners. These learners, called advisors, endeavour to solve the problem from a different focus. Their advice, taking the form of action values, is then communicated to an aggregator, which is in control of the system. We show that the local planning method for the advisors is critical and that none of the ones found in the literature is flawless: the egocentric planning overestimates values of states where the other advisors disagree, and the agnostic planning is inefficient around danger zones. We introduce a novel approach called empathic and discuss its theoretical aspects. We empirically examine and validate our theoretical findings on a fruit collection task.

1. INTRODUCTION:

When a person faces a complex and important problem, his individual problem solving abilities might not suffice. He has to actively seek for advice around him: he might consult his relatives, browse different sources on the internet, and/or hire one or several people that are specialised in some aspects of the problem. He then aggregates the technical, ethical and emotional advice in order to build an informed plan and to hopefully make the best possible decision. A large number of papers tackle the decomposition of a single Reinforcement Learning task (RL, Sutton & Barto, 1998) into several simpler ones. They generally follow a method where agents are trained independently and generally greedily to their local optimality, and are aggregated into a global policy by voting or averaging. Recent works (Jaderberg et al., 2016; van Seijen et al., 2017b) prove their ability to solve problems that are intractable otherwise. Section 2 provides a survey of approaches and algorithms in this field.

Formalised in Section 3, the Multi-Advisor RL (MAd-RL) partitions a single-agent RL into a Multi-Agent RL problem (Shoham et al., 2003) , under the widespread divide & conquer paradigm. Unlike Hierarchical RL (Dayan & Hinton, 1993; Parr & Russell, 1998; Dietterich, 2000a) , this approach gives them the role of advisor: providing an aggregator with the local Q-values for all actions. The advisors are said to have a focus: reward function, state space, learning technique, etc. The MAd-RL approach allows therefore to tackle the RL task from different focuses.

When a person is consulted for an advice by a enquirer, he may answer egocentrically: as if he was in charge of next actions, agnostically: anticipating any future actions equally, or empathically: by considering the next actions of the enquirer. The same approaches are modelled in the local advisors' planning methods. Section 4 shows that the egocentric planning presents the severe theoretical shortcoming of inverting a max into a max in the global Bellman equation. It leads to an overestimation of the values of states where the advisors disagree, and creates an attractor phenomenon, causing the system to remain static without any tie-breaking possibilities. It is shown on a navigation task that attractors can be avoided by lowering the discount factor γ under a given value. The agnostic planning (van Seijen et al., 2017b) has the drawback to be inefficient in dangerous environments, because it gets easily afraid of the controller performing a bad sequence of actions. Finally, we introduce our novel empathic planning and show that it converges to the global optimal Bellman equation when all advisors are training on the full state space.

van Seijen et al. (2017a) demonstrate on a fruit collection task that a distributed architecture significantly speeds up learning and converges to a better solution than non distributed baselines. Section 5.2 extends those results and empirically validates our theoretical analysis: the egocentric planning gets stuck in attractors with high γ values; with low γ values, it gets high scores but is also very unstable as soon as some noise is introduced; the agnostic planning fails at efficiently gathering the fruits near the ghosts; despite lack of convergence guarantees with partial information in advisors' state space, our novel empathic planning also achieves high scores while being robust to noise.

2. RELATED WORK:

Task decomposition -Literature features numerous ways to distribute a single-agent RL problem over several specialised advisors: state space approximation/reduction (Böhmer et al., 2015) , reward segmentation (Dayan & Hinton, 1993; Gábor et al., 1998; Vezhnevets et al., 2017; van Seijen et al., 2017b) , algorithm diversification (Wiering & Van Hasselt, 2008; Laroche & Féraud, 2017) , algorithm randomization (Breiman, 1996; Glorot & Bengio, 2010) , sequencing of actions (Sutton et al., 1999) , or factorisation of actions (Laroche et al., 2009) . In this paper, we mainly focus on reward segmentation and state space reduction but the findings are applicable to any family of advisors. aggregation -Singh & Cohn (1998) are the first to propose to merge Markov decision Processes through their value functions. It makes the following strong assumptions: positive rewards, model-based RL, and local optimality is supposed to be known. Finally, the algorithm simply accompanies a classical RL algorithm by pruning actions that are known to be suboptimal. Sprague & Ballard (2003) propose to use a local SARSA online learning algorithm for training the advisors, but they elude the fact that the online policy cannot be locally accurately estimated with partial state space, and that this endangers the convergence properties. Russell & Zimdars (2003) study more in depth the theoretical guaranties of convergence to optimality with the local Q-learning, and the local SARSA algorithms. However, their work is limited in the fact that they do not allow the local advisors to be trained on local state space. van Seijen et al. (2017b) relax this assumption at the expense of optimality guarantees and beat one of the hardest Atari games: Ms. Pac-Man, by decomposing the task into hundreds of subtasks that are trained in parallel.

Subtasks:

MAd-RL can also be interpreted as a generalisation of Ensemble Learning (Dietterich, 2000b) for RL. As such, Sun & Peterson (1999) use a boosting algorithm in a RL framework, but the boosting is performed upon policies, not RL algorithms. In this sense, this article can be seen as a precursor to the policy reuse algorithm (Fernández & Veloso, 2006) rather than a multi-advisor framework. Wiering & Van Hasselt (2008) combine five online RL algorithms on several simple RL problems and show that some mixture models of the five experts performs generally better than any single one alone. Each algorithm tackles the whole task. Their algorithms were off-policy, on-policy, actor-critics, etc. Faußer & Schwenker (2011) continue this effort in a very specific setting where actions are explicit and deterministic transitions. We show in Section 4 that the planning method choice is critical and that some recommendations can be made in accordance to the task definition. In Harutyunyan et al. (2015) , while all advisors are trained on different reward functions, these are potential based reward shaping variants of the same reward function. They are therefore embedding the same goals. As a consequence, it can be related to a bagging procedure. The advisors recommendation are then aggregated under the HORDE architecture (Sutton et al., 2011) , with egocentric planning. Two aggregator functions are tried out: majority voting and ranked voting. Laroche & Féraud (2017) follow a different approach in which, instead of boosting the weak advisors performances by aggregating their recommendation, they select the best advisor. This approach is beneficial for staggered learning, or when one or several advisors may not find good policies, but not for variance reduction brought by the committee, and it does not apply to compositional RL.

The UNREAL architecture (Jaderberg et al., 2016) improves the state-of-the art on Atari and Labyrinth domains by training their deep network on auxiliary tasks. They do it in an unsupervised manner and do not consider each learner as a direct contributor to the main task. The bootstrapped DQN architecture Osband et al. (2016) also exploits the idea of multiplying the Q-value estimations to favour deep exploration. As a result, UNREAL and bootstrapped DQN do not allow to break down a task into smaller, tractable pieces.

As a summary, a large variety of papers are published on these subjects, differing by the way they factorise the task into subtasks. Theoretical obstacles are identified in Singh & Cohn (1998) and Russell & Zimdars (2003) , but their analysis does not go further than the non-optimality observation in the general case. In this article, we accept the non-optimality of the approach, because it naturally comes from the simplification of the task brought by the decomposition and we analyse the pros and cons of each planning methods encountered in the literature. But first, Section 3 lays the theoretical foundation for Multi-Advisor RL.

Domains -Related works apply their distributed models to diverse domains: racing (Russell & Zimdars, 2003) , scheduling (Russell & Zimdars, 2003) , dialogue (Laroche & Féraud, 2017) , and fruit collection (Singh & Cohn, 1998; Sprague & Ballard, 2003; van Seijen et al., 2017a; b) . The fruit collection task being at the centre of attention, it is natural that we empirically validate our theoretical findings on this domain: the Pac-Boy game (see Figure 1 ), borrowed from van Seijen et al. (2017a) . Pac-Boy navigates in a 11x11 maze with a total of 76 possible positions and 4 possible actions in each state: A = {N, W, S, E}, respectively for North, West, South and East. Bumping into a wall simply causes the player not to move without penalty. Since Pac-Boy always starts in the same position, there are 75 potential fruit positions. The fruit distribution is randomised: at the start of each new episode, there is a 50% probability for each position to have a fruit. A game lasts until the last fruit has been eaten, or after the 300 th time step. During an episode, fruits remain fixed until they get eaten by Pac-Boy. Two randomly-moving ghosts are preventing Pac-Boy from eating all the fruits. The state of the game consists of the positions of Pac-Boy, fruits, and ghosts: 76 × 2 75 × 76 2 ≈ 10 28 states. Hence, no global representation system can be implemented without using function approximation. Pac-Boy gets a +1 reward for every eaten fruit and a -10 penalty when it is touched by a ghost.

3. MULTI-ADVISOR REINFORCEMENT LEARNING:

Markov Decision Process -The Reinforcement Learning (RL) framework is formalised as a Markov Decision Process (MDP). An MDP is a tuple X , A, P, R, γ where X is the state space, A is the action space, P : X × A → X is the Markovian transition stochastic function, R : X × A → R is the immediate reward stochastic function, and γ is the discount factor.

A trajectory x(t), a(t), x(t + 1), r(t) t∈ 0,T -1 is the projection into the MDP of the task episode. The goal is to generate trajectories with high discounted cumulative reward, also called more succinctly return:

T -1 t=0 γ t r(t). To do so, one needs to find a policy π :

X × A → [0, 1] maximising the Q-function: Q π (x, a) = E π t ≥t γ t -t R(X t , A t )|X t = x, A t = a .

Advisor Advisor ...

Environment:



Figure 2: The MAd-RL architecture:

MAd-RL structure -This section defines the Multi-Advisor RL (MAd-RL) framework for solving a single-agent RL problem. The n advisors are regarded as specialised, possibly weak, learners that are concerned with a sub part of the problem. Then, an aggregator is responsible for merging the advisors' recommendations into a global policy. The overall architecture is illustrated in Figure 2 . At each time step, an advisor j sends to the aggregator its local Q-values for all actions in the current state.

Aggregating advisors' recommendations -In Figure 2 , the f function's role is to aggregate the advisors' recommendations into a policy. More formally, the aggregator is defined with f : R n×|A| → A, which maps the received q j = Q j (x j , • ) values into an action of A. This article focuses on the analysis of the way the local Q j -functions are computed. From the values q j , one can design a f function that implements any aggregator function encountered in the Ensemble methods literature (Dietterich, 2000b) : voting schemes (Gibbard, 1973) , Boltzmann policy mixtures (Wiering & Van Hasselt, 2008) and of course linear value-function combinations (Sun & Peterson, 1999; Russell & Zimdars, 2003; van Seijen et al., 2017b) . For the further analysis, we restrict ourselves to the linear decomposition of the rewards: R(x, a) = j w j R j (x j , a), which implies the same decomposition of return if they share the same γ. The advisor's state representation may be locally defined by φ j : X → X j , and its local state is denoted by x j = φ j (x) ∈ X j . We define the aggregator function f Σ (x) as being greedy over the Q j -functions aggregation Q Σ (x, a):

Q Σ (x, a) = j w j Q j (x j , a), f Σ (x) = argmax a∈A Q Σ (x, a).

We recall hereunder the main theoretical result of van Seijen et al. (2017b): a theorem ensuring, under conditions, that the advisors' training eventually converges. Note that by assigning a stationary behaviour to each of the advisors, the sequence of random variables X 0 , X 1 , X 2 , . . . , with X t ∈ X is a Markov chain. For later analysis, we assume the following. Assumption 1. All the advisors' environments are Markov:

P(X j,t+1 |X j,t , A t ) = P(X j,t+1 |X j,t , A t , . . . , X j,0 , A 0 ).

Theorem 1 (van Seijen et al. ( 2017b)). Under Assumption 1 and given any fixed aggregator, global convergence occurs if all advisors use off-policy algorithms that converge in the single-agent setting.

Although Theorem 1 guarantees convergence, it does not guarantee the optimality of the converged solution. Moreover, this fixed point only depends on each advisor model and on their planning methods (see Section 4), but not on the particular optimisation algorithms that are used by them.

4. ADVISORS' PLANNING METHODS:

This section present three planning methods at the advisor's level. They differ in the policy they evaluate: egocentric planning evaluates the local greedy policy, agnostic planning evaluates the random policy, and empathic planning evaluates the aggregator's greedy policy.

4.1. Egocentric PLANNING:

The most common approach in the literature is to learn off-policy by bootstrapping on the locally greedy action: the advisor evaluates the local greedy policy. This planning, referred to in this paper as egocentric, has already been employed in Singh & Cohn (1998), Russell & Zimdars (2003) , Harutyunyan et al. (2015) , and van Seijen et al. (2017a) . Theorem 1 guarantees for each advisor j the convergence to the local optimal value function, denoted by Q ego j , which satisfies the Bellman optimality equation:

Q ego j (x j , a) = E r j + γ max a ∈A Q ego j (x j , a ) ,

where the local immediate reward r j is sampled according to R j (x j , a), and the next local state x j is sampled according to P j (x j , a). In the aggregator global view, we get:

Q ego Σ (x, a) = j w j Q ego j (x j , a) = E   j w j r j + γ j w j max a ∈A Q ego j (x j , a )   . x 0 x 1 x 2 a 1 a 2 r 1 > 0 r 2 > 0 a 0 r 0 = 0 Figure 3: Attractor example.

By construction, r = j w j r j , and therefore we get:

Q ego Σ (x, a) ≥ E   r + γ max a ∈A j w j Q ego j (x j , a )   ≥ E r + γ max a ∈A Q ego Σ (x , a ) .

Egocentric planning suffers from an inversion between the max and operators and, as a consequence, it overestimate the state-action values when the advisors disagree on the optimal action. This flaw has critical consequences in practice: it creates attractor situations. Before we define and study them formally, let us explain attractors with an illustrative example based on the simple MDP depicted in Figure 3 . In initial state x 0 , the system has three possible actions: stay put (action a 0 ), perform advisor 1's goal (action a 1 ), or perform advisor 2's goal (action a 2 ). Once achieving a goal, the trajectory ends. The Q-values for each action are easy to compute: Q ego Σ (s, a 0 ) = γr 1 + γr 2 , Q ego Σ (s, a 1 ) = r 1 , and Q ego Σ (s, a 2 ) = r 2 . As a consequence, if γ > r 1 /(r 1 + r 2 ) and γ > r 2 /(r 1 + r 2 ), the local egocentric planning commands to execute action a 0 sine die. This may have some apparent similarity with the Buridan's ass paradox (Zbilut, 2004; Rescher, 2005) : a donkey is equally thirsty and hungry and cannot decide to eat or to drink and dies of its inability to make a decision. The determinism of judgement is identified as the source of the problem in antic philosophy. Nevertheless, the egocentric sub-optimality does not come from actions that are equally good, nor from the determinism of the policy, since adding randomness to the system will not help. Let us define more generally the concept of attractors. Definition 1. An attractor x is a state where the following strict inequality holds:

max a ∈A j w j Q ego j (x j , a) < γ j w j max a∈A Q ego j (x j , a).

Theorem 2. State x is attractor, if and only if the optimal egocentric policy is to stay in x if possible.

Note that there is no condition in Theorem 2 (proved in appendix, Section A) on the existence of actions allowing the system to be actually static. Indeed, the system might be stuck in an attractor set, keep moving, but opt to never achieve its goals. To understand how this may happen, just replace state x 0 in Figure 3 with an attractor set of similar states: where action a 0 performs a random transition in the attractor set, and actions a 1 and a 2 respectively achieve tasks of advisors 1 and 2. Also, it may happen that an attractor set is escapable by the lack of actions keeping the system in an attractor set.

For instance, in Figure 3 , if action a 0 is not available, x 0 remains an attractor, but an unstable one. Definition 2. An advisor j is said to be progressive if the following condition is satisfied:

∀x j ∈ X j , ∀a ∈ A, Q ego j (x j , a) ≥ γ max a ∈A Q ego j (x j , a ).

The intuition behind the progressive property is that no action is worse than losing one turn to do nothing. In other words, only progress can be made towards this task, and therefore non-progressing actions are regarded by this advisor as the worst possible ones. Theorem 3. If all the advisors are progressive, there cannot be any attractor.

The condition stated in Theorem 3 (proved in appendix, Section A) is very restrictive. Still, there exist some RL problems where Theorem 3 can be applied, such as resource scheduling where each advisor is responsible for the progression of a given task. Note that a MAd-RL setting without any attractors does not guarantee optimality for the egocentric planning. Most of RL problems do not fall into this category. Theorem 3 neither applies to RL problems with states that terminate the trajectory while some goals are still incomplete, nor to navigation tasks: when the system goes into a direction that is opposite to some goal, it gets into a state that is worse than staying in the same position. Navigation problem attractors -We consider the three-fruit attractor illustrated in Figure 4 : moving towards a fruit, makes it closer to one of the fruits, but further from the two other fruits (diagonal moves are not allowed). The expression each action Q-value is as follows:

Q ego Σ (x, S) = γ j max a∈A Q ego j (x j , a) = 3γ 2 , and Q ego Σ (x, N ) = Q ego Σ (x, E) = Q ego Σ (x, W ) = γ + 2γ 3 . That means that, if γ > 0.5, Q ego Σ (x, S) > Q ego Σ (x, N ) = Q ego Σ (x, E) = Q ego Σ (x, W ).

As a result, the aggregator would opt to go South and hit the wall indefinitely.

More generally in a deterministic1 task where each action a in a state x can be cancelled by a new action a -1

x , it can be shown that the condition on γ is a function of the size of the action set A. Theorem 4 is proved in Section A of the appendix. Theorem 4. State x ∈ X is guaranteed not to be an attractor if ∀a ∈ A, ∃a -1

x ∈ A, such that P (P (x, a), a -1

x ) = x , if ∀a ∈ A, R(x, a) ≥ 0 , and if γ ≤ 1 |A|-1 .

4.2. Agnostic PLANNING:

The agnostic planning does not make any prior on future actions and therefore evaluates the random policy. Once again, Theorem 1 guarantees the convergence of the local optimisation process to its local optimal value, denoted by Q agn j , which satisfies the following Bellman equation:

Q agn j (x j , a) = E r j + γ |A| a ∈A Q agn j (x j , a ) , Q agn Σ (x, a) = E   r + γ |A| j w j a ∈A Q agn j (x j , a )   = E r + γ |A| a ∈A Q agn Σ (x , a ) .

Local agnostic planning is equivalent to the global agnostic planning. Additionally, as opposed to the egocentric case, r.h.s. of the above equation does not suffer from maxinversion. It then follows that no attractor are present in agnostic planning. Nevertheless, acting greedily with respect to Q agn Σ (x, a) only guarantees to be better than a random policy and in general may be far from being optimal. Still, agnostic planning has proved its usefulness on Ms. Pac-Man (van Seijen et al., 2017b).

4.3. Empathic PLANNING:

A novel approach, inspired from the online algorithm found in Sprague & Ballard (2003) ; Russell & Zimdars (2003) is to locally predict the aggregator's policy. In this method, referred to as empathic, the aggregator is in control, and the advisors are evaluating the current aggregator's greedy policy f with respect to their local focus. More formally, the local Bellman equilibrium equation is the following one: Q ap j (x j , a) = E r j + γQ ap j (x j , f Σ (x )) . Theorem 5. Assuming that all advisors are defined on the full state space, MAd-RL with empathic planning converges to the global optimal policy. Proof.

Q ap Σ (x, a) = E   r + γ j w j Q ap j (x j , f Σ (x ))   = E [r + γQ ap Σ (x , f Σ (x ))] = E r + γQ ap Σ (x , argmax a ∈A Q ap Σ (x , a )) = E r + γ max a ∈A Q ap Σ (x , a ) .

Q ap Σ is the unique solution to the global Bellman optimality equation, and therefore equals the optimal value function, quod erat demonstrandum.

However, most MAd-RL settings involve taking advantage of state space reduction to speed up learning, and in this case, there is no guarantee of convergence because function f Σ (x ) can only be approximated from the local state space scope. As a result the local estimate fj (x ) is used instead of f Σ (x ) and the reconstruction of max a ∈A Q ap Σ (x , a ) is not longer possible in the global Bellman equation:

Q ap j (x j , a) = E r j + γQ ap j (x j , fj (x )) , Q ap Σ (x, a) = E   r + γ j w j Q ap j (x j , fj (x ))   .

5. EXPERIMENTS:



5.1. VALUE FUNCTION APPROXIMATION:

For this experiment, we intend to show that the value function is easier to learn with the MAd-RL architecture. We consider a fruit collection task where the agent has to navigate through a 5 × 5 grid and receives a +1 reward when visiting a fruit cell (5 are randomly placed at the beginning of each episode). A deep neural network (DNN) is fitted to the ground-truth value function V π * γ for various objective functions: TSP is the optimal number of turns to gather all the fruits, RL is the optimal return, and egocentric is the optimal MAd-RL return. This learning problem is fully supervised on 1000 samples, allowing us to show how fast a DNN can capture V π * γ while ignoring the burden of finding the optimal policy and estimating its value functions through TD-backups or value iteration. To evaluate the DNN's performance, actions are selected greedily by moving the agent up, down, left, or right to the neighbouring grid cell of highest value. Section B.1 of the appendix gives the details.

Figure 5a displays the performance of the theoretical optimal policy for each objective function in dashed lines. Here TSP and RL targets largely surpass MAd-RL one. But Figure 5a also displays the performances of the networks trained on the limited data of 1000 samples, for which the results are completely different. The TSP objective target is the hardest to train on. The RL objective target follows as the second hardest to train on. The egocentric planning MAd-RL objective is easier to train on, even without any state space reduction, or even without any reward/return decomposition (summed version). Additionally, if the target value is decomposed (vector version), the training is further accelerated. Finally, we found that the MAd-RL performance tends to dramatically decrease when γ gets close to 1, because of attractors' presence. We consider this small experiment to show that the complexity of objective function is critical and that decomposing it in the fashion of MAd-RL may make it simpler and therefore easier to train, even without any state space reduction.

5.2. PAC-BOY DOMAIN:

In this section, we empirically validate the findings of Section 4 in the Pac-Boy domain, presented in Section 2. The MAd-RL settings are associating one advisor per potential fruit location. The local state space consists in the agent position and the existence -or not-of the fruit. Six different settings are compared: the two baselines linear Q-learning and DQN-clipped, and four MAd-RL settings: egocentric with γ = 0.4, egocentric with γ = 0.9, agnostic with γ = 0.9, and empathic with γ = 0.9. The implementation and experimentation details are available in the appendix, at Section B.2. We provide links to 5 video files (click on the blue links) representing a trajectory generated at the 50 th epoch for various settings. egocentric-γ = 0.4 adopts a near optimal policy coming close to the ghosts without taking any risk. The fruit collection problem is similar to the travelling salesman problem, which is known to be NP-complete (Papadimitriou, 1977) . However, the suboptimal small-γ policy consisting of moving towards the closest fruits is in fact a near optimal one. Regarding the ghost avoidance, egocentric with small γ gets an advantage over other settings: the local optimisation guarantees a perfect control of the system near the ghosts. The most interesting outcome is the presence of the attractor phenomenon in egocentric-γ = 0.9: Pac-Boy goes straight to the centre area of the grid and does not move until a ghost comes too close, which it still knows to avoid perfectly. This is the empirical confirmation that the attractors, studied in Section 4.1, present a real practical issue. empathic is almost as good as egocentric-γ = 0.4. agnostic proves to be unable to reliably finish the last fruits because it is overwhelmed by the fear of the ghosts, even when they are still far away. This feature of the agnostic planning led van Seijen et al. (2017b) to use a dynamic normalisation depending on the number of fruits left on the board. Finally, we observe that DQN-clipped also struggles to eat the last fruits.

The quantitative analysis displayed in Figure 5b confirms our qualitative video-based impressions. egocentric-γ = 0.9 barely performs better than linear Q-learning, DQN-clipped is still far from the optimal performance, and gets hit by ghosts from time to time. agnostic is closer but only rarely eats all the fruits. Finally, egocentric-γ = 0.4 and empathic are near-optimal. Only egocentric-γ = 0.4 trains a bit faster, and tends to finish the game 20 turns faster too (not shown).

Results with noisy rewards -Using a very small γ may distort the objective function and perhaps even more importantly the reward signal diminishes exponentially as a function of the distance to the goal, which might have critical consequences in noisy environments, hence the following experiment: several levels of Gaussian centred white noise η σ with standard deviation σ ∈ {0.01, 0.1} have been applied to the reward signal: at each turn, each advisor now receives rj = r j + η σ instead. Since the noise is centred and white, the ground truth Q-functions remain the same, but their estimators obtained during sampling is corrupted by noise variance.

Empirical results displayed in Figure 5c shows that the empathic planning performs better than the egocentric one even under noise with a 100 times larger variance. Indeed, because of the noise, the fruit advisors are only able to consistently perceive the fruits that are in a radius dependent on γ and σ. The egocentric planning, incompatible with high γ values, is therefore myopic and cannot perceive distant fruits. The same kind of limitations are expected to be encountered for small γ values when the local advisors rely on state approximations, and/or when the transitions are stochastic. This also supports the superiority of the empathic planning in the general case.

6. CONCLUSION AND DISCUSSION:

This article presented MAd-RL, a common ground for the many recent and successful works decomposing a single-agent RL problem into simpler problems tackled by independent learners. It focuses more specifically on the local planning performed by the advisors. Three of them -two found in the literature and one novel -are discussed, analysed and empirically compared: egocentric, agnostic, and empathic. The lessons to be learnt from the article are the following ones.

The egocentric planning has convergence guarantees but overestimates the values of states where the advisors disagree. As a consequence, it suffers from attractors: states where the no-op action is preferred to actions making progress on a subset of subtasks. Some domains, such as resource scheduling, are identified as attractor-free, and some other domains, such as navigation, are set conditions on γ to guarantee the absence of attractor. It is necessary to recall that an attractor-free setting means that the system will continue making progress towards goals as long as there are any opportunity to do so, not that the egocentric MAd-RL system will converge to the optimal solution.

The agnostic planning also has convergence guarantees, and the local agnostic planning is equivalent to the global agnostic planning. However, it may converge to bad solutions. For instance, in dangerous environments, it considers all actions equally likely, it favours staying away from situation where a random sequence of actions has a significant chance of ending bad: crossing a bridge would be avoided. Still, the agnostic planning simplicity enables the use of general value functions (Sutton et al., 2011) as in van Seijen et al. (2017b) .

The empathic planning optimises the system according to the global Bellman optimality equation, but without any guarantee of convergence, if the advisor state space is smaller than the global state.

In our experiments, we never encountered a case where the convergence was not obtained, and on the Pac-Boy domain, it robustly learns a near optimal policy after only 10 epochs. It can also be safely applied to Ensemble RL tasks where all learners are given the full state space.

A THEOREMS AND THEIR PROOFS Theorem 1 (van Seijen et al. (2017b) ). Under Assumption 1 and given any fixed aggregator, global convergence occurs if all advisors use off-policy algorithms that converge in the single-agent setting.

Proof. Each advisor can be seen as an independent learner training from trajectories controlled by an arbitrary behavioural policy. If Assumption 1 holds, each advisor's environment is Markov and off-policy algorithms can be applied with convergence guarantees.

Theorem 2. State x is attractor, if and only if the optimal egocentric policy is to stay in x if possible.

Proof. The logical biconditional will be demonstrated by successively proving the two converse conditionals.

First, the sufficient condition: let us assume that state x is an attractor. By Definition 1, if state x is an attractor, we have:

max a ∈A j w j Q ego j (x j , a) < γ j w j max a∈A Q ego j (x j , a).

Let a 0 denote the potential action to stay in x, and consider the MDP augmented with a 0 in x. Then, we have :

Q ego j (x, a 0 ) = γ j w j max a∈A Q ego j (x j , a) > max a∈A j w j Q ego j (x j , a) = max a∈A Q ego Σ (x, a),

which proves that a 0 , if possible, will be preferred to any other action a ∈ A.

Second, the reciprocal condition: let us assume that, in state x, action a 0 would be preferred by an optimal policy under the egocentric planning. Then:

Q ego j (x, a 0 ) > max a∈A Q ego Σ (x, a) γ j w j max a∈A Q ego j (x j , a) > max a∈A j w j Q ego j (x j , a),

which proves that x is an attractor.

Theorem 3. If all the advisors are progressive, there cannot be any attractor.

Proof. Let sum Definition 2 over advisors:

j w j Q ego j (x j , a) ≥ γ j w j max a ∈A Q ego j (x j , a ), max a ∈A j w j Q ego j (x j , a ) ≥ j w j Q ego j (x j , a),

which proves the theorem.

Theorem 4. State x ∈ X is guaranteed not to be an attractor if:

• ∀a ∈ A, ∃a -1 x ∈ A, such that P (P (x, a), a -1 x ) = x , • ∀a ∈ A, R(x, a) ≥ 0 , • γ ≤ 1 |A|-1 .

Proof. Let us denote J x a as the set of advisors for which action a is optimal in state x. Q ego a (x) is defined as the sum of perceived value of performing a in state x by the advisors that would choose it:

Q ego a (x) = j∈J x a w j Q ego j (x j , a).

Let a + be the action that maximises this Q ego a (x) function:

a + = argmax a∈A Q ego a (x).

We now consider the left hand side of the inequality characterising the attractors in Definition 1:

max a ∈A j w j Q ego j (x j , a) ≥ j w j Q ego j (x j , a + ), = Q ego a + (x) + j / ∈J x a + w j Q ego j (x j , a + ), = Q ego a + (x) + j / ∈J x a + w j R(x, a + ) + γ max a ∈A Q ego j (x j , a ) .

Since R(x, a + ) ≥ 0, and since the a maximising Q ego j (x j , a ) is at least as good as the cancelling action (a + ) -1

x , we can follow with:

max a ∈A j w j Q ego j (x j , a) ≥ Q ego a + (x) + j / ∈J x a + w j γ 2 max a∈A Q ego j (x j , a).

By comparing this last result with the right hand side of Definition 1, the condition for x not being an attractor becomes:

(

1 -γ)Q ego a + (x) ≥ (1 -γ)γ j / ∈J x a + w j max a∈A Q ego j (x j , a), Q ego a + (x) ≥ γ a =a + j∈J x a w j Q ego j (x j , a), Q ego a + (x) ≥ γ a =a + Q ego a (x).

It follows directly from the inequality Q ego a + (x) ≥ Q ego a (x), that γ ≤ 1/(|A|-1) guarantees the absence of attractor. Similarly to the Taxi Domain Dietterich (1998) , we incorporate the location of the fruits into the state representation by using a 50 dimensional bit vector, where the first 25 entries are used for fruit positions, and the last 25 entries are used for the agent's position. The DNN feeds this bit-vector as the input layer into two dense hidden layers with 100 and then 50 units. The output is a single linear head representing the state-value, or a multiple in the case of the vector MAd-RL target. In order to assess the value function complexity, we train for each discount factor setting a DNN of fixed size on 1000 random states with their ground truth values. Each DNN is trained over 500 epochs using the Adam optimizer Kingma & Ba (2014) with default parameters.

B.1.2 OBJECTIVE FUNCTION TARGETS:

Four different objective function targets are considered:

• The TSP objective function target is the natural objective function, as defined by the Travelling Salesman Problem: the number of turns to gather all the fruits:

y T SP (x) = -min σ∈Σ k k i=1 d(x σ(i-1) , x σ(i) ) ,

where k is the number of fruits remaining in statex, where Σ k is the ensemble of all permutations of integers between 1 and k, where σ is one of those permutations, where x 0 is the position of the agent in x, where x i for 1 ≤ i ≤ k is the position of fruit with index i, where d(x i , x j ) is the distance (||•|| 1 in our gridworld) between positions x i and x j . • The RL objective function target is the objective function defined for an RL setting, which depends on the discount factor γ:

y RL (x) = max σ∈Σ k k i=1 γ i j=1 d(x σ(j-1) ,x σ(j) ) ,

with the same notations as for TSP. • The summed egocentric planning MAd-RL objective function target does not involve the search into the set of permutations and can be considered simpler to this extent: x0,xi) , with the same notations as for TSP. • The vector egocentric planning MAd-RL objective function target is the same as the summed one, except that the target is now a vector, separated into as many channels as potential fruit position: x0,xi) if there is a fruit in x i , 0 otherwise.

y ego (x) = k i=1 γ d(

y ego (x) = γ d(

B.2 PAC-BOY EXPERIMENT:

MAd-RL Setup -Each advisor is responsible for a specific source of reward (or penalty). More precisely, we assign an advisor to each possible fruit location. This advisor sees a +1 reward only if a fruit at its assigned position gets eaten. Its state space consists of Pac-Boy's position, resulting in 76 states. In addition, we assign an advisor to each ghost. This advisor receives a -10 reward if Pac-Boy

:

A more general result on stochastic navigation tasks can be demonstrated. We limited the proof to the deterministic case for the sake of simplicity.

Figures and Tables:

Figure 1: The Pac-Boy game: Pac-Boy is yellow, the corridors are in black, the walls in grey, the fruits are the white dots and the ghosts are in red.

Figure 4: 3-fruit attractor.

network trained on vector egocentric objective network trained on summed egocentric objective network trained on RL objective network trained on TSP objective optimal policy given egocentric objective optimal policy given RL objective optimal policy given TSP objective (a) Value function training.

Figure 5: Experiment results.

performed from the same state and the same network, which are described in Section B.1.1. Their only difference lies in the objective function targets that are detailed in Section B.1.2.B.1.1 NEURAL NETWORK SETTING

Peer review (iclr2018):
 Summary The paper is well-written but does not make deep technical contributions and does not present a comprehensive evaluation or highly insightful empirical results. Abstract / Intro I get the entire focus of the paper is some variant of Pac-Man which has received attention in the RL literature for Atari games, but for the most part the impressive advances of previous Atari/RL papers are in the setting that the raw video is provided as input, which is much different than solving the underlying clean mathematically abstracted problem (as a grid world with obstacles) as done here and evident in the videos. Further it is honestly hard for me to be strongly motivated about a paper that focuses on the need to decompose Pac-man into sub-agents/advisor value functions. Section 2 Another historically well-cited paper for MDP decomposition: Flexible Decomposition Algorithms for Weakly Coupled Markov Decision Problems, Ronald Parr. UAI 98. https://dslpitt.org/uai/papers/98/p422-parr.pdf Section 3 Is the additive reward decomposition a required part of the problem specification? It seems so, i.e., there is no obvious method for automatically decomposing a monolithic reward function over advisors. Section 4 * Egocentric: Definition 1: Sure, the problem will have local optima (attractors) when decomposed suboptimally -- I*m not sure what new insight we*ve gained from this analysis... it is a general problem with any function approximation scheme that does not guarantee that the rank ordering of actions for a state is preserved. * Agnostic Other than approximating some type of myopic rollout, I really don*t see why this approach would be reasonable? I am surprised it works at all though my guess is that this could simply be an artifact of evaluating on a single domain with a specific structure. * Empathic This appears to be the key contribution though related work certainly infringes on its novelty. Is this paper then an empirical evaluation of previous methods in a single Pac-man grid world variant? I wonder if the theory of DEC-MDPs would have any relevance for novel analysis here? Section 5 I*m disappointed that the authors only evaluate on a single domain; presumably the empathic approach has applications beyond Pac-Man? The fact that empathic generally performs better is not at all surprising. The fact that a modified discount factor for egocentric can also perform well is not surprising given that lower discount factors have often been shown to improve approximated MDP solutions, e.g., Biasing Approximate Dynamic Programming with a Lower Discount Factor Marek Petrik, Bruno Scherrer (NIPS-08). http://marek.petrik.us/pub/Petrik2009a.pdf *** Side note: The following part is somewhat orthogonal to the review above in that I would not expect the authors to address this on revision, *but* at the same time I think it provides a connection to the special case of concurrent action decomposition into advisors, which could potentially provide a high impact direction of application for this work (i.e., concurrent problems are hard and show up in numerous operations research problems covering inventory control, logistics, epidemic response). For the special case that each advisor is assigned to one action in a factored space of concurrent actions, the egocentric algorithm would be very close to the Hindsight approximation in Section 6 of this paper (including an additive decomposition of rewards): Planning in Factored Action Spaces with Symbolic Dynamic Programming Aswin Nadamuni Raghavan, Alan Fern, Prasad Tadepalli, Roni Khardon, and Saket Joshi (AAAI-12). https://www.aaai.org/ocs/index.php/AAAI/AAAI12/paper/download/5012/5336 This simple algorithm is hard to beat for the following reason that connects some details of your egocentric and empathic settings: rather than decomposing a concurrent MDP into independent problems per concurrent action, the optimization of each action (by each advisor) is done in sequence (advisors are ordered) and gets to condition on the previously selected advisor actions. So it provides an alternate paradigm where advisors actually get to see and condition their policy on what other advisors are doing. In my own work comparing optimal concurrent solutions to this approach, I have found this approach to be near-optimal and much more efficient to solve since it exploits decomposition. Why is this relevant to this work? Because (a) it suggests another variant of the advisor decomposition that at least makes sense in the case of concurrent actions (and perhaps shared actions though this would require some extension) and (b) it suggests there are more options than just the full egocentric and empathic settings in this important class of concurrent action problems that are necessarily solved in practice for large action spaces by some form of decomposition. This could be an interesting direction for future exploration of the ideas in this work, where there might be additional technical novelty and more space for empirical contributions and observations.