summaries: This paper studies the problem of generating contracts by a principal to incentive agents to optimally accomplish multiagent tasks. The setup of the environment is that the agents have certain skills and preferences for activities, which the principal must learn to act optimally. The paper takes a combined approach of agent modeling to infer agent skills and preferences, and a deep reinforcement learning approach to generate contracts. The evaluation of the approach is fairly thorough.

summaries: This paper proposes a way to train a manager agent which would manage a bunch of worker agents to achieve a high-level goal. Each worker has its own set of skills and preferences and the manager tries to assign sub-tasks to these agents along with bonuses such that the agents can even perform tasks that are not preferred by them. Authors achieve this by training a manager which tracks the skills and preferences of the agents on the fly. Authors have done an extensive analysis of the proposed approach in two simple domains: resource collection and crafting.

abstractText: Most of the prior work on multi-agent reinforcement learning (MARL) achieves optimal collaboration by directly learning a policy for each agent to maximize a common reward. In this paper, we aim to address this from a different angle. In particular, we consider scenarios where there are self-interested agents (i.e., worker agents) which have their own minds (preferences, intentions, skills, etc.) and can not be dictated to perform tasks they do not want to do. For achieving optimal coordination among these agents, we train a super agent (i.e., the manager) to manage them by first inferring their minds based on both current and past observations and then initiating contracts to assign suitable tasks to workers and promise to reward them with corresponding bonuses so that they will agree to work together. The objective of the manager is to maximize the overall productivity as well as minimize payments made to the workers for ad-hoc worker teaming. To train the manager, we propose Mind-aware Multi-agent Management Reinforcement Learning (MRL), which consists of agent modeling and policy learning. We have evaluated our approach in two environments, Resource Collection and Crafting, to simulate multi-agent management problems with various task settings and multiple designs for the worker agents. The experimental results have validated the effectiveness of our approach in modeling worker agents’ minds online, and in achieving optimal ad-hoc teaming with good generalization and fast adaptation.1

authors:
Maruan Al-Shedivat
Trapit Bansal
Yuri Burda
Ilya Sutskever
Igor Mordatch
Pieter Abbeel

title: Continuous adaptation via meta-learning in nonstationary and competitive environments

venue: In The Sixth International Conference on Learning Representations (ICLR),

authors:
Jacob Andreas
Dan Klein
Sergey Levine

title: Modular multitask reinforcement learning with policy sketches

venue: In International Conference on Machine Learning (ICML),

authors:
Peter Auer
Nicolo Cesa-Bianchi
Paul Fischer

title: Finite-time analysis of the multiarmed bandit problem

venue: Machine Learning,

authors:
Bowen Baker
Otkrist Gupta
Nikhil Naik
Ramesh Raskar

title: Designing neural network architectures using reinforcement learning

venue: In The Fifth International Conference on Learning Representations (ICLR),

authors:
Chris L Baker
Rebecca Saxe
Joshua B Tenenbaum

title: Action understanding as inverse planning

authors:
André Barreto
Will Dabney
Rémi Munos
Jonathan J. Hunt
Tom Schaul
Hado van Hasselt
David Silver

title: Successor features for transfer in reinforcement learning

venue: In Advances in Neural Information Processing Systems (NIPS),

authors:
Michael Bowling
Peter McCracken

title: Coordination and adaptation in impromptu teams

venue: In The Twentieth National Conference on Artificial Intelligence (AAAI),

authors:
Lucian Busoniu
Robert Babuska
Bart De Schutter

title: A comprehensive survey of multiagent reinforcement learning

venue: IEEE Trans. Systems, Man, and Cybernetics, Part C,

authors:
Vincent Conitzer
Tuomas Sandholm

title: Complexity of mechanism design

venue: In The Eighteenth conference on Uncertainty in artificial intelligence (UAI),

authors:
Yan Duan
Marcin Andrychowicz
Bradly Stadie
OpenAI Jonathan Ho
Jonas Schneider
Ilya Sutskever
Pieter Abbeel
Wojciech Zaremba

title: One-shot imitation learning

venue: In Advances in neural information processing systems (NIPS),

authors:
Chelsea Finn
Pieter Abbeel
Sergey Levine

title: Model-agnostic meta-learning for fast adaptation of deep networks

authors:
Jakob Foerster
Ioannis Alexandros Assael
Nando de Freitas
Shimon Whiteson

title: Learning to communicate with deep multi-agent reinforcement learning

authors:
Carlos Guestrin
Daphne Koller
Ronald Parr

title: Multiagent planning with factored mdps

authors:
Bharath Hariharan
Ross Girshick

title: Low-shot visual recognition by shrinking and hallucinating features

venue: In IEEE International Conference on Computer Vision (ICCV),

title: Moral hazard and observability

venue: The Bell journal of economics,

authors:
Bengt Hlmstrom
Paul Milgrom

title: Multitask principal-agent analyses: Incentive contracts, asset ownership, and job design

venue: Journal of Law, Economics, and Organization,

authors:
Daphne Koller
Ronald Parr

title: Computing factored value functions for policies in structured mdps

venue: In International Joint Conference on Aritificial Intelligence (IJCAI),

authors:
Tejas D. Kulkarni
Ardavan Saeedi
Simanta Gautam
Samuel J Gershman

title: Deep successor reinforcement learning

venue: arXiv preprint arXiv:1606.02396,

authors:
Jean-Jacques Laffont
D. Martimort

title: The theory of incentives: the principal-agent model

title: Markov games as a framework for multi-agent reinforcement learning

venue: In The 11th International Conference on Machine Learning (ICML),

authors:
Ryan Lowe
Yi Wu
Aviv Tamar
Jean Harb
Pieter Abbeel
Igor Mordatch

title: Multi-agent actorcritic for mixed cooperative-competitive environments

venue: In Advances in Neural Information Processing Systems (NIPS,

authors:
Chen Ma
Junfeng Wen
Yoshua Bengio

title: Universal successor representations for transfer reinforcement learning

venue: arXiv preprint arXiv:1804.03758,

authors:
Dougal Maclaurin
David Duvenaud
Ryan P. Adams

title: Gradient-based hyperparameter optimization through reversible learning

authors:
Volodymyr Mnih
Adria Puigdomenech Badia
Mehdi Mirza
Alex Graves
Timothy Lillicrap
Tim Harley
David Silver
Koray Kavukcuoglu

title: Asynchronous methods for deep reinforcement learning

title: Optimal auction design

venue: Mathematics of operations research,

title: Optimal coordination mechanisms in generalized principalagent problems

venue: Journal of mathematical economics,

authors:
Frans A. Oliehoek
Matthijs TJ Spaan
Nikos Vlassis

title: Optimal and approximate q-value functions for decentralized pomdps

venue: Journal of Artificial Intelligence Research,

authors:
Shayegan Omidshafiei
Jason Pazis
Christopher Amato
Jonathan P. How
John Vian

title: Deep decentralized multi-task multi-agent reinforcement learning under partial observability

authors:
Peng Peng
Ying Wen
Yaodong Yang
Yuan Quan
Zhenkun Tang
Haitao Long
Jun Wang

title: Multiagent bidirectionally-coordinated nets emergence of human-level coordination in learning to play starcraft combat games

venue: arXiv preprint arXiv:1703.10069,

authors:
Neil C. Rabinowitz
Frank Perbet
H. Francis Song
Chiyuan Zhang
S.M. Ali Eslami
Matthew Botvinick

title: Machine theory of mind

venue: arXiv preprint arXiv:1802.07740,

authors:
Tabish Rashid
Mikayel Samvelyan
Christian Schroeder de Witt
Gregory Farquhar
Jakob Foerster
Shimon Whiteson

title: Qmix: Monotonic value function factorisation for deep multi-agent reinforcement learning

authors:
Ellis Ratner
Dylan Hadfield-Menell
Anca D. Dragan

title: Simplifying reward design through divide-and-conquer

venue: In Robotics: Science and Systems (RSS),

title: A continuous-time version of the principal-agent problem

venue: The Review of Economic Studies,

authors:
Jonathan Sorg
Richard L. Lewis
Satinder P. Singh

title: Reward design via online gradient ascent

authors:
Peter Stone
Gal A. Kaminka
Sarit Kraus
Jeffrey S. Rosenschein

title: Ad hoc autonomous agent teams: Collaboration without pre-coordination

venue: In The Twenty-Fourth Conference on Artificial Intelligence (AAAI),

authors:
Peter Sunehag
Guy Lever
Audrunas Gruslys
Wojciech Marian Czarnecki
Vinicius Zambaldi
Max Jaderberg
Marc Lanctot
Nicolas SOnnerat
Joel Z. Leibo
Karl Tuyls
Thore Graepel

title: Valuedecomposition networks for cooperative multi-agent learning based on team reward

venue: In International Conference on Autonomous Agents and MultiAgent Systems (AAMAS),

authors:
Tijmen Tieleman
Geoffrey Hinto

title: Lecture 6.5—rmsprop: Divide the gradient by a running average of its recent magnitude

venue: COURSERA: Neural Networks for Machine Learning,

authors:
Jane X Wang
Zeb Kurth-Nelson
Dhruva Tirumala
Hubert Soyer
Joel Z Leibo
Remi Munos
Charles Blundell
Dharshan Kumaran
Matt Botvinick

title: Learning to reinforcement learn

venue: arXiv preprint arXiv:1611.05763,

authors:
Olga Wichrowska
Niru Maheswaranathan
Matthew W Hoffman
Sergio Gomez Colmenarejo
Misha Denil
Nando de Freitas
Jascha Sohl-Dickstein

title: Learned optimizers that scale and generalize

venue: arXiv preprint arXiv:1703.04813,

authors:
Tianhe Yu
Chelsea Finn
Annie Xie
Sudeep Dasari
Pieter Abbeel
Sergey Levine

title: One-shot imitation from observing humans via domain-adaptive meta-learning

authors:
Haoqi Zhang
David Parkes

title: Value-based policy teaching with active indirect elicitation

venue: In AAAI Conference on Artificial Intelligence (AAAI),

authors:
Haoqi Zhang
David C. Parkes
Yiling Chen

title: Policy teaching through reward function learning

venue: In The 10th ACM conference on Electronic commerce,

authors:
Yuke Zhu
Daniel Gordon
Eric Kolve
Dieter Fox
Li Fei-Fei
Abhinav Gupta
Roozbeh Mottaghi
Ali Farhadi

title: Visual semantic planning using deep successor representations

venue: In International Conference on Computer Vision (ICCV),

heading: 1 INTRODUCTION

text:
As the main assumption and building block in economics, self-interested agents play a central roles in our daily life. Selfish agents, with their private beliefs, preferences, intentions, and skills, could collaborate (ad-hoc teaming) effectively to make great achievement with proper incentives and contracts, an amazing phenomenon that happens every day in every corner of the world.
However, most existing multi-agent reinforcement learning (MARL) methods focus on collaboration when agents selflessly share a common goal, expose its complete states and are willing to be trained towards the goal. While this is plausible in certain games, few papers address the more practical situations, in which agents are self-interested and inclined to show off, and only get motivated to work with proper incentives.
In this paper, we try to model such behaviors. We have multiple workers and a manager, together to work on a set of tasks. The manager gets an external reward upon the completion of some tasks, or one specific task. Each worker has a skill set and preference over the tasks. Note that their skills and preferences may not align with each other (Fig. 1(a)), and are not known to the manager (Fig. 1(b)). Furthermore, manager may not get any external reward until a specific task is complete, which depends on other tasks.
By default, the self-interested workers simply choose the most preferred tasks, which is often unproductive from the perspective of the entire project. Therefore, the manager gives additional incentives in the form of contracts. Each contract assigns a goal and a bonus for achieving the goal to a worker. ∗Work done while interning at Facebook AI Research. 1Code is available at https://github.com/facebookresearch/M3RL.
With the external incentives, workers may choose different goals than their preferences. Upon completion of assigned goals, the manager receives the rewards associated with those goals and makes the promised payments to the workers. To generate optimal contracts, the manager must infer the workers’ minds and learn a good policy of goal and reward assignment.
Conventional approaches of mechanism design tackle similar problems by imposing strong assumptions (e.g., skill/preference distributions, task dependencies, etc) to find an analytic solution. In contrast, we aim to train a manager using reinforcement learning to i) assess minds of workers (skills, preferences, intentions, etc.) on the fly, ii) to optimally assign contracts to maximize a collaborative reward, and iii) is adapted to diverse and even evolving workers and environments.
For this, we propose a novel framework – Mind-aware Multi-agent Management Reinforcement Learning (M3RL), which entails both agent modeling for estimating workers’ minds and policy learning for contract generation. For agent modeling, we infer workers’ identities by their performance history, and track their internal states with a mind tracker trained by imitation learning (IL). For contract generation, we apply deep reinforcement learning (RL) to learn goal and bonus assignment policies. To improve the learning efficiency and adaptation, we also propose high-level successor representation (SR) learning (Kulkarni et al., 2016) and agent-wise -greedy exploration.
As a proof of concept, we evaluate our approach in two environments: Resource Collection and Crafting in 2D Minecraft, to simulate multi-agent management problems. The setup and underlying assumptions are designed to mimic real world problems, where workers are not compelled to reveal their true preferences and skills, and there may be dependency between tasks resulting in delayed and sparse reward signals. Workers may also be deceitful (e.g., accepting a contract even when the assigned goal is unreachable). Our experiments demonstrate that the manager trained by our approach can i) estimate the mind of each worker from the recent behaviors, ii) motivate the workers to finish less preferable or intermediate tasks by assigning the right bonuses, iii) is adaptive to changing teams, e.g., change of members and/or change of workers’ skills and preferences, iv) and has good generalization in different team sizes and novel environments.
We have conducted substantial ablation studies by removing the key components, including IL, SR, agent-wise -greedy exploration, and performance history. Our approach shows a consistent performance in standard settings as well as in more challenging ones where workers’ policies are stochastic and sub-optimal, or there are multiple levels of bonuses required to motivate workers.

heading: 2 RELATED WORK

text:
Multi-agent reinforcement learning. For collaboration problems, common multi-agent reinforcement learning (Littman, 1994; Busoniu et al., 2008) usually trains agents (Oliehoek et al., 2008; Foerster et al., 2016; Peng et al., 2017; Omidshafiei et al., 2017; Lowe et al., 2017) so that they will jointly maximize a shared reward. There also have been work on contributing different credits to agents by factorized value functions (Koller & Parr, 1999; Guestrin et al., 2001; Sunehag et al., 2018;
Rashid et al., 2018), but the spontaneous collaboration assumption is still required. In contrast, we instead train a manager to manage multiple self-interested workers for an optimal collaboration.
Principal-agent problems. Our problem setup is closely related to principal-agent problems (Laffont & Martimort, 2002) (or moral hazard problems (Hlmstrom, 1979)) in economics. Our manager and workers can be considered as the principal and agents respectively, where agents and principal have different objectives, and the principal needs to provide the right incentives to ensure that the agents make the best choices for what the principal delegates. These problems face similar technical challenges as our problem setup, e.g., information asymmetry between principals and agents, how to setup incentive cost, how to infer agents types, how to monitor their behaviors, etc. Traditional approaches in economics (Myerson, 1982; Hlmstrom & Milgrom, 1991; Sannikov, 2008) build mathematical models to address these issues separately in stateless games, often with the assumption that the utility functions and the behavior patterns of the agents are known, leading to complicated models with many tunable parameters. In comparison, our paper provides a practical end-to-end computational framework to address this problem in a data-driven way without any assumption about the agents’ utilities and their decision making processes. Moreover, this framework is adaptive to changes of agents preferences and capabilities, which very few papers in economics have addressed. We also evaluate our approach in more complex game settings than the ones in the current economics literature.
Mechanism design. Similar to our problem setting, mechanism design also tackles problems where agents have different and private preferences (Myerson, 1981; Conitzer & Sandholm, 2002). Its core idea is to set up rules so that the agents will truthfully reveal their preferences for their own interests, and ultimately an optimal collective outcome can be achieved. Our work differs from mechanism design in several ways. First, in addition to preferences, we also acknowledge the fact that agents may have different skills. Second, mechanism design does not consider sequential decision problems, whereas we have to dynamically change the contracts over time.
Optimal reward design. The contract generation in our work can be seen as reward design. Some prior work has proposed optimal reward design approaches (Zhang et al., 2009; Zhang & Parkes, 2008; Sorg et al., 2010; Ratner et al., 2018), where a teacher designs the best reward so that the student will learn faster or alter its policy towards the target policy. In contrast, we try to use deep RL to train optimal reward design policies to manage multi-agents in more complex tasks.
Meta-learning. Our work also resembles meta-learning (Wang et al., 2016; Finn et al., 2017), which typically aims at learning a meta strategy for multiple tasks (Maclaurin et al., 2015; Duan et al., 2017; Hariharan & Girshick, 2017; Wichrowska et al., 2017; Yu et al., 2018; Baker et al., 2017) with good sample efficiency, or for a fast adaptation (Al-Shedivat et al., 2018). The meta-learning in this paper is for addressing the problem of ad-hoc teaming (Bowling & McCracken, 2005; Stone et al., 2010) by training from a limited set of worker population.
Theory of Mind. Our agent modeling is inspired by the prior work on computational theory of mind, where both Bayesian inference (Baker et al., 2009) and end-to-end training (Rabinowitz et al., 2018) have been applied to understand a single agent’s decision making by inferring their minds. In this work, we extend this to optimal multi-agent management by understanding agents’ minds.

heading: 3 PROBLEM SETUP

text:
In an environment, there is a set of goals G corresponding to several tasks, N self-interested workers with different minds, and a manager which can observe workers’ behaviors but is agnostic of their true minds. Different from the common Markov game setting for MARL in prior work (Littman, 1994), we use an independent Markov Decision Process (MDP), i.e., 〈Si,Ai, Ri, Ti〉, ∀i ∈ N , to model each worker, where Si and Ai are the state space and action space, Ri : Si × Gi → R is the reward function, and Ti : Si × Ai → Si is the state transition probabilities. For achieving goals, a worker has its own policy πi : Si × Gi → Ai. We define the key concepts in this work as follows. Contract. A contract is a combination of goal and bonus assignment initiated by the manager to a specific worker. For simplicity, we consider discrete bonuses sampled from a finite set B. Thus, for worker i at time t, it will receive a contract defined as (gti , b t i), where g t i ∈ G is the goal and bti ∈ B is the corresponding bonus for achieving the goal. Note that the contract will change over time.
Worker’s mind. We model a worker’s mind by its preferences, intentions, and skills. We do not study worker agents’ beliefs in this paper, which we leave as future work.
Preference. A worker’s preference is formally defined as its bounded internal utilities of achieving different goals, ui = (uig : g ∈ G), where 0 ≤ uig ≤ umax. Combined with received contract, the worker agent’s reward function can be defined as
rtig = Ri(s t i, g) = (uig + 1(g = g t i)b t i)1(s t i = sg), g ∈ G. (1)
where sg is the goal state.
Intention. The intention of a worker is the goal it is pursuing at any time, i.e., Iti ∈ G, which is not fully revealed to the manager. Based on the reward defined in Eq. (1), there are multiple ways to choose the goal. For a rational worker who is clear about its skills, it will choose the goal by maximizing expected return. I.e., Iti = arg maxg E[ ∑∞ t=0 γ t ir t ig], where 0 < γi ≤ 1 is its discount factor. However, this requires a worker to have a good estimate of its skills and to be honest, which is not always true. E.g., a worker may want to pursue some valuable goal that it can not reach. So an alternative way is to maximize the utility instead: Iti = arg maxg uig + 1(g = gti)bti. This will make a worker’s behavior more deceptive as it may agree to pursue a goal but will rarely produce a fruitful result. In this work, we focus on the second way to achieve a more realistic simulation. After determine which goal to pursue, a worker will decide whether to sign the assigned contact. We denote this by dti ∈ {0, 1}, where dti = 1 means that worker i signs the contract given at time t. Skill. The skill of a worker is jointly determined by its state transition probabilities Ti and its policy conditioned on its intention, i.e., πi(·|sti, Iti ). Manager’s objective. The manager in our setting has its own utility v = (vg : g ∈ G), where vg ≥ 0 is the utility of achieving goal g. To maximize its gain, the manager needs to assign contracts to workers optimally. For the sake of realism, we do not assume that the manager knows for sure if a worker agent is really committed to the assignment. The only way to confirm this is to check whether the goal achieved by the worker is consistent with its last assigned goal. If so, then the manager will gain certain reward based on its utility of that goal and pay the promised bonus to the worker. Thus, we may define the manager’s reward function as:
rt = RM (St+1) = ∑ g∈G N∑ i=1 1(st+1i = sg)1(g = g t i)(vg − bti), (2)
where St+1 = {st+1i : i = 1, · · · , N} is the collective states of all present worker agents at time t+ 1. The objective of the manager is to find optimal contract generation to maximize its expected return E[ ∑∞ t=0 γ
trt], where 0 < γ ≤ 1 is the discount factor for the manager. Note that the manager may get the reward of a goal for multiple times if workers reach the goal respectively.
Population of worker agents. The trained manager should be able to manage an arbitrary composition of workers rather than only specific teams of workers. For this, we maintain a population of worker agents during training, and sample several ones from that population in each episode as the present workers in each episode. The identities of these workers are tracked across episodes. In testing, we will sample workers from a new population that has not been seen in training.

heading: 4 APPROACH

text: Our approach has three main components as shown in Figure 2: i) performance history module for identification, ii) mind tracker module for agent modeling, and iii) manager module for learning goal and bonus assignment policies. We introduce the details of these three components as follows.

heading: 4.1 PERFORMANCE HISTORY MODULE AND MIND TRACKER MODULE

text:
To model a worker’s mind, we first need to infer its identity so that the manager can distinguish it from other agents. Previous work (Rabinowitz et al., 2018) typically identifies agents via their trajectories in recent episodes. This only works when diverse past trajectories of agents are available beforehand. However, this is impractical in our problem as the past trajectories of a worker depends on the manager’s policy, and thus are highly correlated and can hardly cover all aspects of that agent.
In this work, we propose performance history for agent identification, which is inspired by the upper confidence bound (UCB) algorithm (Auer et al., 2002) for multi-bandit arm (MAB) problems. Formally, the performance history of worker i is a set of matrices Pi = {P ti = (ρtigb) : t = 1, · · · , T}, where 0 ≤ ρtigb ≤ 1 is an empirical estimation of the probability of worker i finishing goal g within t steps after signing the contract if promised with a bonus of b. We discuss how to update this estimate in Algorithm 1. These matrices are then flatten into a vector and we encode it to a history representation, hi, for worker i.
With identification, the manager uses an independent mind tracker module with shared weights to update its belief of a worker’s current mental state online by encoding both current and past information: M(Γti, hi), where Γ t i = {(sτi , aτi , gτi , bτi ) : τ = 1, · · · , t} is a trajectory of the worker’s behavior and the contracts it has received upon current time t in the current episode.

heading: 4.2 MANAGER MODULE

text:
For contract generation, the manager has to consider all present workers as a context. Thus, we encode each worker’s information and pool them over to obtain a context representation, i.e., ct+1 = C({(st+1i ,mti, hi) : i = 1, . . . , N}). With both individual information and the context, we define goal policy, πg(·|st+1i ,mti, hi, ct+1), and bonus policy, πb(·|s t+1 i ,m t i, hi, c t+1), for each worker.
In addition to learning policies for individual workers, we also want the manager to estimate the overall productivity of a team. A common choice in previous literature (e.g., Lowe et al. (2017)) is to directly learn a centralized value function based on the context. However, this is not informative in our case, as the final return depends on achieving multiple goals and paying different bonuses. It is necessary to disentangle goal achievements, bonus payments, and the final net gain.
To this end, we adopt the idea of successor representation (SR) (Kulkarni et al., 2016; Zhu et al., 2017; Barreto et al., 2017; Ma et al., 2018), but use it to estimate the expectation of accumulated goal achievement and bonus payment in the future instead of expected state visitation. By defining two vectors φg(ct) and φb(ct) indicating goal achievement and bonus payment at time t respectively, we may define our high-level SR, Φg and Φb, as Φg(ct) = E[ ∑∞ τ=0 γ
τφg(ct+τ )] and Φb(ct) = E[ ∑∞ τ=0 γ τφb(ct+τ )]. We discuss the details in Appendix A.1.

heading: 4.3 LEARNING

text:
For a joint training of these three modules, we use advantage actor-critic (A2C) (Mnih et al., 2016) to conduct on-policy updates, and learn SR similar to Kulkarni et al. (2016). In addition, we also use imitation learning (IL) to improve the mind tracker. In particular, we predict a worker’s policy based on its mental state representation, i.e., π̂(·|sti, gti , bti,m t−1 i ), which is learned by an additional cross-entropy loss for action prediction. Section A.2 summarizes the details. As our experimental results in Section 5 and Appendix C show, in difficult settings such as random preferences and multiple bonus levels, the policies based on the mental state representation trained with IL have a much better performance than the ones without it.
As the manager is agnostic of workers’ minds, it is important to equip the manager with a good exploration strategy to fully understand each worker’s skills and preferences. A common exploration
strategy in RL is -greedy, where an agent has a chance of to take random actions. However, this may cause premature ending of contracts where a worker does not have sufficient amount of time to accomplish anything. Therefore, we adopt an agent-wise -greedy exploration, where a worker has as a chance of to be assigned with a random goal at the beginning of an episode and the manager will never change that goal assignment throughout the whole episode. In this way, it is easier for a manager to understand why or why not a worker is able to reach an assigned goal. The details can be seen from the rollout procedure (Algorithm 1) in Appendix B.

heading: 5 EXPERIMENTS

heading: 5.1 GENERAL TASK SETTINGS

text: We introduce the general task settings as follows. Note that without additional specification, workers are implemented as rule-based agents (detailed in Appendix D.2).

heading: 5.1.1 RESOURCE COLLECTION

text:
In Resource Collection, the goals are defined as collecting certain type of resources. There are 4 types of resources on a map (Figure 3a) and the total quantity is 10. A worker can find any resources but only has the skills to dig out certain types of resources. Note that it may not be skilled at collecting its preferred resources. We consider three different settings:
• S1: Each agent can collect up to three types of resources including its preferred type. • S2: Each agent can only collect one type of resource which may or may not be its preferred one. • S3: Similar to S2, except that an agent has a different random preference in each episode and thus
its preference can not be inferred from history.
A worker can take five actions: “move forward”, “turn left”, “turn right”, “collect”, and “stop”, and its skill is reflected by the effect of taking the “collect’ action. For workers, the internal utility of a resource is 1 if it is preferred; otherwise it is 0. The manager receives a reward of 3 for every resource collected under the contracts, and can choose to pay a worker with a bonus of 1 or 2.

heading: 5.1.2 CRAFTING

text:
Different from previous work (Andreas et al., 2017) where all items can be directly crafted from raw materials, we consider three-level recipes (Figure 3b): crafting a top-level item requires crafting certain intermediate item first. There are four work stations (colored blocks) for crafting the four types of items respectively. For the manager, each top-level item is worth a reward of 10, but collecting raw materials and crafting intermediate items do not have any reward. Note that certain materials are needed for crafting both top-level items, so the manager must strategically choose which one to craft. In each episode, there are raw materials sufficient for crafting one to two toplevel items. All collected materials and crafted items are shared in a common inventory.
We define 8 goals including collecting raw materials and crafting items. Each worker prefers one of the collecting goals (the internal utility is 1), and is only capable of crafting one type of items. We
expands the action space in Section 5.1.1 to include “craft”, which will only take effect if it has the ability of crafting the intended item and there are sufficient materials and/or intermediate items. The manager can choose a bonus from 0 to 2 for the contracts, where 0 means no employment.

heading: 5.2 BASELINES

text:
For comparison, we have evaluated the following baselines:
• Ours w/o SR: Learning a value function directly w/o successor representations. • Ours w/o IL: Removing action prediction loss. • Temporal -greedy: Replacing the agent-wise exploration with conventional -greedy exploration. • Agent identification using recent trajectories: Encoding an agent’s trajectories in the most recent
20 episodes instead of its performance history, which is adopted from Rabinowitz et al. (2018).
• UCB: Applying UCB (Auer et al., 2002) by defining the management problem as N multi-armed bandit sub-problems, each of which is for a worker agent. In each MAB sub-problem, pulling an arm is equivalent to assigning a specific goal and payment combination to a worker agent (i.e., there are |G| · |B| arms for each worker agent).
• GT types known: Revealing the ground-truth skill and preference of each worker and removing the performance history module, which serves as an estimation of the upper bound performance.

heading: 5.3 LEARNING EFFICIENCY

text:
During training, we maintain a population of 40 worker agents. In each episode, we sample a few of them (4 workers in Resource Collection and 8 workers in Crafting). All approaches we have evaluated follow the same training protocol. The learning curves shown in Figure 4 demonstrate that ours consistently performs the best in all settings, and its converged rewards are comparable to the one trained using ground-truth agent types as part of the observations. Moreover, in more difficult settings, e.g., S3 of Resource Collection and Crafting, the benefits of IL, SR, agent-wise -greedy exploration, and the history representations based on the performance history are more significant. In particular, when there are tasks that do not have any reward themselves such as in Crafting, SR and IL appear to offer the most critical contributions. Without them, the network hardly
gets any training signals. In all cases, the agent identification by encoding recent trajectories learns extremely slowly in Resource Collection and fails to learn anything at all in Crafting.

heading: 5.4 ADAPTATION AND GENERALIZATION

text:
In real world scenarios, the population of worker agents and their skills may evolve over time, which requires the manager to continuously and quickly adapt its policy to the unforeseeable changes through a good exploration. Thus we compare our agent-wise -greedy exploration with the temporal -greedy exploration in two cases: i) training with a population where workers’ skills change drastically after 100,000 episodes (the manager does not know when and which workers’ skill sets have been updated), and ii) testing with a team where 75% of the workers will be replaced with new ones after every 2,000 episodes. Both strategies keep the same constant exploration coefficient, i.e., = 0.1. To have a better sense of the upper bound in the testing case, we also show the performance of the baseline that knows ground-truth agent information where no exploration is need. The results of the two cases are demonstrated in Figure 5 and in Figure 6 respectively.
In the first case, there are moments when the significant change in a population’s skill distribution (i.e., how many workers can reach a specific goal) will need the manager to greatly change its policy. E.g., the first two changes in Figure 5a result in new types of resources being collected; the changes in Figure 5b force the team to craft a different type of top-level item. In such cases, our agentwise -greedy exploration significantly improves the learning efficiency and increases the converged rewards. When the change is moderate, the policy learned by ours is fairly stable.
In the second case, the managers trained by the three methods achieve similar converged rewards in training. While the converged reward of our approach is slightly lower than the upper bound due to exploration, it allows the manager to quickly adapt itself to a new team where it has never seen the most team members. The temporal -greedy on the other hand never achieves a comparable reward even though its performance is comparable to ours when managing a fixed population.
We also want the manager’s policy to have good generalization in novel scenarios unseen in training, which, in our problems, has two aspects: i) generalization in different numbers of present worker agents, and ii) generalization in new environments. It can be seen from Figure 7 that as the number of workers increases, the manager achieves higher reward until it hits a plateau. Our approach consistently performs better in all settings. It even gains higher rewards than the one with groundtruth does when there are fewer workers. We also add a few walls to create novel environments unseen in training. With the additional obstacles, workers’ paths become more complex, which increases the difficulty of inferring their true minds. As suggested by Figure 8, the performance indeed decreases the most in S3 of Resource Collection where online intention inference is critical as the workers do not have fixed preferences.
So far, we have only considered rule-based worker agents with deterministic plans. To see if our approach can handle stochastic and sub-optimal worker policies, we may randomize certain amount of actions taken by the workers (Figure 9) and train a manager with these random policies. When the randomness is moderate (e.g., ≤ 20%), the performance is still comparable to the one without random actions. As randomness increases, we start to see larger decrease in reward. In Crafting specifically, random policies make the workers unlikely to achieve assigned goals within the time limit, thus the manager may never get top-level items if the policies are too random.
More results. In addition to the main experimental results discussed above, we further test our approach from different perspectives: i) showing the effect of the minimum valid period of a contract
(i.e., constraints for the manager’s commitment), ii) multiple bonus levels, and iii) training RL agents as workers. We summarize these results in Appendix C.

heading: 6 CONCLUSIONS

text: In this paper, we propose Mind-aware Multi-agent Management Reinforcement Learning (M3RL) for solving the collaboration problems among self-interested workers with different skills and preferences. We train a manager to simultaneously infer workers’ minds and optimally assign contracts to workers for maximizing the overall productivity, for which we combine imitation learning and reinforcement learning for a joint training of agent modeling and management policy optimization. We also improve the model performance by a few techniques including learning high-level successor representation, agent-wise -greedy exploration, and agent identification based on performance history. Results from extensive experiments demonstrate that our approach learns effectively, generalizes well, and has a fast and continuous adaptation.

heading: A DETAILS OF APPROACH

text:
A.1 HIGH-LEVEL SUCCESSOR REPRESENTATION
We define two vectors indicating the goal achievement and bonus payment at time t: φg(ct) = ( ∑ i 1(s t+1 i = sg)1(g t i = g) : g ∈ G) and φb(ct) = ( ∑ i 1(s t+1 i = sgti )1(b t i = b) : b ∈ B). Let w = (b : b ∈ B) be the weights for different bonus payments, then the reward for the manager at the current moment can be written as rt = v>φg(ct)−w>φb(ct). Following the typical SR definition, we define our high-level SR as
Φg(ct) = E [ ∞∑ τ=0 γτφg(ct+τ ) ] , (3)
and
Φb(ct) = E [ ∞∑ τ=0 γτφb(ct+τ ) ] . (4)
Thus, the value function can be written as
V (ct) = v>Φg(ct)−w>Φb(ct). (5)
A.2 DETAILS OF LEARNING
The policy gradient for the goal assignment is:
∇θgJ(θg) = 1
N N∑ i=1 ∇θg [ log πg(gti |sti,mt−1i , hi, c t; θg)A(c t) + λH(πg) ] , (6)
where A(ct) is the advantage estimation defined as A(ct) = ∑∞ τ=0 γ
τrt+τ − (v>Φg(ct) − w>Φb(ct)) andH(·) is the entropy regularization weighted by the constant λ = 0.01 for encouraging exploration. Similarly, the policy gradient for the bonus assignment is
∇θbJ(θb) = 1
N N∑ i=1 ∇θb [ log πb(bti|sti,mt−1i , hi, c t; θb)A(c t) + λH(πb) ] . (7)
The successor representations may be updated by the following gradient:
∇θΦg 1
2 ( ∞∑ τ=0 γτφg(ct+τ )− Φg(ct; θφg ) )2 +∇θ Φb 1 2 ( ∞∑ τ=0 γτφb(ct+τ )− Φb(ct; θφb) )2 . (8)
For imitation learning, we use the following cross-entropy loss:
LIL = E [ − 1 N N∑ i=1 log π̂(ati|sti, gti , bti,mt−1i ) ] . (9)
Note that the gradient from IL will be combined with Eq. 6, Eq. 7, and Eq. 8 to update corresponding parameters (see Algorithm 2 in Appendix B for details).
In tasks where there the unknown dependency may introduce a large cost in the beginning of training, the manager’s exploration may be restricted as the policy becomes too conservative in spending, which is common in many real world scenarios. To encourage exploration in these tasks, we adopt a two-phase learning curriculum. Namely, we optionally conduct a warm-up phase before the standard learning described above. In this warm-up phase, we give loans to the manager to cover its cost (i.e., setting the total payments to be zero when optimizing the networks). In practice, we apply this only to Crafting, where we set a fixed number of episodes at the beginning of training to be the warm-up phase. Note that this only apply to the optimization; we still need to deduct the payments from the rewards as the actually outcomes (this is equivalent to paying back the loans).
Algorithm 1 Rollout(Tmax, Tc, , {Pi : i = 1, · · · , N}) Input: Maximum steps Tmax, commitment constraint Tc, exploration coefficient , and the performance history
of the present worker agents {Pi : i = 1, · · · , N} Output: Trajectories of all workers {ΓTi : i = 1, · · · , N}, and the rewards for the manager R
1: Initialize the environment 2: Set performance history update rate η = 0.1. 3: t← 0 4: Γ1i ← ∅, ∀i = 1, · · · , N 5: repeat 6: Observe current states (sti, a t i), ∀i = 1, · · · , N , from the environment 7: Encode Pi to hi, ∀i = 1, · · · , N 8: if t = 0 then 9: for i = 1, · · · , N do
10: Γ0i ← ∅ 11: Sample a random goal g0i ∼ G, and set a minimum bonus b0i as the initial contract. 12: ei ∼ U(0, 1) 13: Assign the contract (g0i , b 0 i ) to worker i and receive d t i (signing decision) 14: τi ← dti 15: Γti ← {(sti, ati, gti , bti)} 16: end for 17: rt ← 0 18: else 19: rt = ∑ g∈G ∑N i=1 1(s t i = sg)1(g = g t−1 i )(vg − b t−1 i ) 20: mt−1i ←M(Γ t−1 i , hi), ∀i = 1, · · · , N 21: ct ← C({(sti,mt−1i , hi) : i = 1, . . . , N}) 22: for i = 1, · · · , N do 23: τ ′i = τi 24: if (t− 1)%Tc 6= 0 or ei < then # Commitment constraint and agent-wise -greedy 25: gti ← gt−1i 26: else 27: Sample a new goal gti ∼ πg(·|sti,mt−1i , hi, c
t) 28: τi ← τi1(gti = gt−1i ) 29: end if 30: Sample a new bonus bti ∼ πb(·|sti,mt−1i , hi, c
t) (w/ temporal -greedy) 31: Assign the contract (gti , b t i) to worker i and receive d t i 32: τi ← τi + dti 33: Γti ← Γt−1i ∪ {(s t i, a t i, g t i , b t i)} 34: if τ ′i > τi or sti = sgt−1i then # the last contract was accepted and has been terminated now 35: ρτ ′ i
igt−1bt−1 ← (1− η)ρτ
′ i
igt−1bt−1 + η1(sti = sgt−1i )
36: end if 37: end for 38: end if 39: R← R ∪ {rt} 40: t← t+ 1 41: until t = Tmax or the task is finished 42: T ← t
Algorithm 2 Learning Algorithm 1: Initialize parameters 2: Set the maximum steps of an episode to be Tmax, maximum training episodes to be Ntrain, and the number
of worker agents in an episode to be N 3: The coefficient for the agent-wise -greedy exploration to be 4: Initialize a population of worker agents and set their performance history P to be all zeros. 5: for i = 1, · · · , Nmax do 6: Sample N worker agents from the training population and obtain their performance history {Pi : i =
1, · · · , N} 7: # Run an episode 8: {ΓTi : i = 1, · · · , N}, R← Rollout(Tmax, Tc, , {Pi : i = 1, · · · , N}) 9: Update parameters based on the IL loss LIL defined in Eq. (9) and the gradients defined Eq. (6),
Eq. (7), and Eq. (8) jointly. 10: end for

heading: B PSEUDO CODE OF OUR ALGORITHMS

text: We summarize the rollout algorithm and the learning algorithm in Algorithm 1 and Algorithm 2 respectively.

heading: C MORE EXPERIMENTAL RESULTS

text:
C.1 CONSTRAINING THE MANAGER’S COMMITMENT
The manager’s commitment is defined as the shortest time a contract must remain unchanged, which essentially constrains how frequent the manager can change its goal and bonus assignment. While short-term commitment allows the manager to quickly update contracts once it has a better mind estimation or once a goal has been reached, long-term commitment often leads to a more accurate skill assessment when the tasks are difficult (e.g., crafting high-level items depends on the results of other tasks and thus needs a longer time). This is supported by the results in Figure 10: shorter commitment works better in Resource Collection while Crafting needs a longer commitment. Note that the commitment constraint is 1 step and 10 steps for Resource Collection and Crafting respectively in all other experiments.
C.2 MULTIPLE BONUS LEVELS
In previous experiments, the internal utility of goals for a worker agent is either 0 or 1. Here, we sample the internal utility from 0 to 3. Consequently, the manager needs to select the right bonus from multiple choices to pay each worker (i.e., a bonus from 1 to 4 for Resource Collection and a bonus from 0 to 4 for Crafting). In Resource Collection, the manager will get a reward of 5 for every collected resource; in crafting, the reward for a top-level item is still 10. As shown in Figure 11, the advantage of our approach is even more significant compared to the ones in single payment level.
C.3 RL AGENTS AS WORKERS
Finally, we train a population of 40 RL worker agents for Resource Collection, where each one is trained with only one goal, and for each goal we train 10 agents using different random seeds.
This creates a population with similar skill distributions as in S2, but with very different policies. Figure 12 suggests that training to manage RL agents is slower as their policies are less predictable and less rational, but our approach can still gradually learn a good policy whose performance is comparable to the one using rule-based worker agents.
D IMPLEMENTATION DETAILS
D.1 NETWORK ARCHITECTURE
Performance History Module. We flatten the matrices in worker’s performance history Pi and concatenate them together to get a single vector. We then encode this vector into a 128-dim history representation hi.
Mind Tracker Module. We represent the state of a worker by multiple channels corresponding to different types of items. We also use four channels to indicate its orientation. We augment the state with additional |A||G||B| channels, where a channel is either all ones or all zeros for indicating the action it takes, and the goal and bonus it receives. We then encode the state into a 128-dim hidden state by a convolutional layer with 64 channels and kernels of 1 × 1, a fully connected (FC) layer (128-dim), and an LSTM with 128 hidden units. We fuse this vector with the history representation hi. Specifically, we adopt an attention-based mechanism for the fusion, where we first get an attention vector (128-dim) from the history representation by an FC layer with sigmoid activation, and then do element-wise product between the attention vector and the hidden state from the LSTM. The fused vector becomes mti. This can be formally written as mti = f(` t i, hi) = ` t i σ(hi), where σ(·) is an FC layer with sigmoid activation, `ti is the hidden state from the LSTM, and is element-wise product. We fuse it with the state using the same mechanism: f(φ(st+1i , g t+1 i , b t+1 i ),m t i) = φ(s t+1 i , g t+1 i , b t+1 i ) σ(mti), where φ(s t+1 i , g t+1 i , b t+1 i ) is the state encoding. By feeding the fused vector to an FC layer with softmax activation, we may get the predicted worker policy.
Manager Module. For each worker, we concatenate its mind representation and history representation together and fuse it with the worker’s state using the attention-based mechanism where the attention vector comes from the concatenated vector. By pooling over these fused vectors of individual workers, we can get the context vector, from which we construct the two successor representations by two separate FC layers. Here, we use average pooling, but one may also use other pooling mechanisms. Finally, for each worker, we concatenate the context vector with its fused vector we obtained before pooling, and consequently get the goal policy and bonus policy by two FC layers with softmax activation.
All modules are trained with RMSProp (Tieleman & Hinto, 2012) using a learning rate of 0.0004.
D.2 RULE-BASED WORKER AGENTS
Each rule-based worker finds a shortest path to the nearest location related to a goal, and its skill is defined as the post effect of its “collect” and “craft” actions. In particular, for collecting certain resource/material, it will go to the closest one that has the same type as the goal indicates and is currently not being collected by other agents, whereas for crafting an item, it will go to the corresponding work station if it is currently unoccupied. If a worker can perform collecting tasks, then after it takes “collect” action, the item will be collected from the map and appears in the inventory; otherwise no real effect will appear. This applies to crafting tasks as well, except in crafting, task dependencies must also be satisfied before “craft” action can take real effect.
When considering random actions, for each step, we sample a random action with the specified chance to replace the action from the rule-based plan.
D.3 RL WORKER AGENTS
We implement all RL worker agents using the same network architecture, where an agent’s state is augmented by additional channels to include the reward for each goal (i.e., |G||B| channels). We use a convolution layer with 64 channels and kernels of 1 × 1 to encode the state, and feed it to an 128-dim FC layer and then an LSTM with a 128-dim hidden state. We then predict the policy using
an FC layer with softmax activation based on the hidden state from the LSTM. For each goal, we train 10 RL worker agents using 10 random seeds. For each episode, we randomly assign a reward from b ∈ B to an agent as the hypothetical reward it may receive from a manager. We then set the corresponding channel to be all ones and set the remaining |G||B| − 1 channels to be all zeros. Note that we assume all RL workers have the ability to perform “collect” and “craft” actions.

title: MRL: MIND-AWARE MULTI-AGENT MANAGEMENT REINFORCEMENT LEARNING


summaries: This paper proposes a new type of recurrent neural network which takes into account five different features: in addition to the prevalent dense features, the author(s) also consider(s) sparse features, time features, global static and changing features. The differences in feature types are reflected in the cell state or output state update rules. Experiments on a modified UCI dataset and a proprietary dataset show that the proposed model outperforms the time-variant LSTM (TLSTM).

summaries: The paper addresses limitations of the LTSM method for modeling time series. The work is motivated by applications where multiple time series need to be combined while they may get updated in an asynchronous fashion. Authors mention IoT applications in the Intro and give examples from a power consumption data set and a churn prediction application in their numerical experiments sections.

abstractText: There are time series that are amenable to recurrent neural network (RNN) solutions when treated as sequences, but some series, e.g. asynchronous time series, provide a richer variation of feature types than current RNN cells take into account. In order to address such situations, we introduce a unified RNN that handles five different feature types, each in a different manner. Our RNN framework separates sequential features into two groups dependent on their frequency, which we call sparse and dense features, and which affect cell updates differently. Further, we also incorporate time features at the sequential level that relate to the time between specified events in the sequence and are used to modify the cell’s memory state. We also include two types of static (whole sequence level) features, one related to time and one not, which are combined with the encoder output. The experiments show that the proposed modeling framework does increase performance compared to standard cells.

authors:
Yoshua Bengio
Francois Gingras

title: Recurrent neural networks for missing or asynchronous data

venue: In Advances in neural information processing systems,

authors:
Mikolaj Binkowski
Gautier Marti
Philippe Donnat

title: Autoregressive convolutional neural networks for asynchronous time series

venue: In Proceedings of the 35th international conference on machine learning,

authors:
Zhengping Che
Sanjay Purushotham
Kyunghyun Cho
David Sontag
Yan Liu

title: Recurrent neural networks for multivariate time series with missing values

venue: Scientific reports,

authors:
Kyunghyun Cho
Bart Van Merriënboer
Caglar Gulcehre
Dzmitry Bahdanau
Fethi Bougares
Holger Schwenk
Yoshua Bengio

title: Learning phrase representations using RNN encoder-decoder for statistical machine translation

authors:
John Cunningham
Zoubin Ghahramani
Carl Rasmussen

title: Gaussian processes for time-marked time-series data

venue: In Artificial intelligence and statistics,

title: Time series analysis, volume 2. Princeton university

authors:
Kaiming He
Xiangyu Zhang
Shaoqing Ren
Jian Sun

title: Deep residual learning for image recognition

venue: In Proceedings of the IEEE conference on computer vision and pattern recognition,

authors:
Sepp Hochreiter
Jürgen Schmidhuber

title: Long short-term memory

venue: Neural computation,

authors:
Alex Krizhevsky
Ilya Sutskever
Geoffrey E Hinton

title: Imagenet classification with deep convolutional neural networks. In Advances in neural information processing

authors:
Martin Längkvist
Lars Karlsson
Amy Loutfi

title: A review of unsupervised feature learning and deep learning for time-series modeling

venue: Pattern recognition letters,

authors:
Steven Cheng-Xian Li
Benjamin M Marlin

title: A scalable end-to-end Gaussian process adapter for irregularly sampled time series classification

authors:
Zachary C Lipton
David Kale
Randall Wetzel

title: Directly modeling missing data in sequences with RNNs: Improved classification of clinical time series

venue: In Machine learning for healthcare conference,

authors:
Pankaj Malhotra
Lovekesh Vig
Gautam Shroff
Puneet Agarwal

title: Long short term memory networks for anomaly detection in time series

venue: In European symposium on artificial networks,

authors:
Daniel Neil
Michael Pfeiffer
Shih-Chii Liu

title: Phased LSTM: Accelerating recurrent network training for long or event-based sequences

authors:
Christian Szegedy
Wei Liu
Yangqing Jia
Pierre Sermanet
Scott Reed
Dragomir Anguelov
Dumitru Erhan
Vincent Vanhoucke
Andrew Rabinovich

title: Going deeper with convolutions

authors:
Volker Tresp
Thomas Briegel

title: A solution for missing data in recurrent neural networks with an application to blood glucose prediction

authors:
Ruofeng Wen
Kari Torkkola
Balakrishnan Narayanaswamy

title: A multi-horizon quantile recurrent forecaster

authors:
Yonghui Wu
Mike Schuster
Zhifeng Chen
Quoc V Le
Mohammad Norouzi
Wolfgang Macherey
Maxim Krikun
Yuan Cao
Qin Gao
Klaus Macherey

title: Google’s neural machine translation system: Bridging the gap between human and machine translation

authors:
Wenpeng Yin
Katharina Kann
Mo Yu
Hinrich Schütze

title: Comparative study of CNN and RNN for natural language processing

heading: 1 INTRODUCTION

text:
The study of time series has a long history and the literature for it covers many different methods (Hamilton (1994)). The study of asynchronous time series is an important subset of this. Asynchronous time series are series for which features are sampled at irregular time intervals, and at any given time step new values of any subset of features may be present. When a feature does not change values often it can be treated as being present only at times of change. For example, in industrial IoT several sensors can be monitored, each one with its own sampling rate. We can have a feature that corresponds to the production rate that seldom changes and it impacts predictions. This clearly presents difficulties from both a modeling and data input perspective. Fixed sampling, repeating missing values, and other types of data imputation have all been used to varying degrees of success. More recent attempts using machine learning for asynchronous time series use Gaussian processes (Cunningham et al. (2012); Li & Marlin (2016)), which are hard to scale in the presence of many features.
Deep learning is a much more recent development, and it is achieving great success in many fields, e.g. machine vision (Krizhevsky et al. (2012); Szegedy et al. (2015); He et al. (2016)) and natural language processing (Wu et al. (2016); Yin et al. (2017)). Recurrent neural networks (RNNs) are a type of a neural network that use shared weights applied to sequences. These types of networks achieve state of the art performance for sequential data. Time series can be thought of as sequences in the RNN context, and thus they are amenable to RNN-based solutions (Malhotra et al. (2015); Che et al. (2018); Längkvist et al. (2014)). However, many of the most widely used RNN cells, e.g. the Long Short Term Memory (LSTM) cell (Hochreiter & Schmidhuber (1997)), are built for problems where time either does not matter or there is a constant time step size.
The adaptation of these cells for asynchronous sequences is a more recent development, varying from combining traditional methods with deep learning (Binkowski et al. (2018); Wen et al. (2017)) to pure neural network approaches (Neil et al. (2016); Baytas et al. (2017)). These attempts may take into account time between samples and the patterns of missing values, but they do not fundamentally treat features that are present with varying levels of frequency any differently. Thus, a feature that occurs at every time step and a feature that almost never occurs at any given time step update the cell in the same manner.
We address this shortcoming by introducing a new recurrent cell that uses features that are present frequently, called dense features, differently from features that are rarely present, termed sparse features, when updating the cell’s hidden and memory states. In particular, our cell’s hidden state is split into two parts, one part for dense features and one part for sparse features. Additionally, each sparse feature maintains its own hidden and memory state that are updated only at time steps when that feature is present. Thus, the update for the sparse part of the overall hidden state depends on the subset of sparse features present at any given time step, while the update for the dense part of the overall hidden state happens in the standard LSTM manner.
In addition to handling these two feature types, our cell also accounts for the irregular time between time steps, expanding on the work of Baytas et al. (2017) by allowing more flexibility for ingesting time features. Specifically, we modify the decay function to handle an arbitrary number of decay features, not just the time elapsed since the last time step. The model also permits sequence level features, distinguishing time related features, called static decay features, which are handled in the same manner as within the recurrent cell, from the non-time related features, called static standard features, which are embedded and concatenated with the sequence output in the standard manner. Overall, we support five feature types.
The main contributions of this work are as follows. First, the introduction of a new recurrent cell that accounts for asynchronous feature sampling and treats features in a variable manner dependent on the frequency with which their values are present. Second, an expansion of the time-aware LSTM (TLSTM) to handle multiple time features, and the extension of this method applied to the output of the recurrent cell itself. Third and finally, a general recurrent framework to incorporate the five aforementioned feature types.

heading: 2 RELATED WORK

text:
When dealing with an irregularly sampled multivariate sequence, one can consider the variables not present at any given time step to be missing. Prior work done on recurrent networks with missing data includes (Bengio & Gingras (1996); Tresp & Briegel (1998)). Lipton et al. (2016) test the performance of different types of imputation and missing value indicator input features. This work inputs the missing values patterns into the recurrent network by concatenating with the feature vectors while using a standard LSTM network. They find zero filling missing features and using indicator features outperforms data imputation, which may actually interfere with the network’s ability to pick out missing values.
Che et al. (2018) investigate a similar approach and improve upon this by modifying a GRU (Cho et al. (2014)) cell to separately incorporate the missing value patterns as well as the time between successive measurements for each feature. It does this by introducing two decay mechanisms. The first decay acts to bring a missing value toward the baseline mean value from its last measured value so the old value is not input repeatedly. This work treats all features in the same manner, regardless of the frequency a missing value is present for any given feature. The work in Che et al. (2018) does not differentiate between features that never have missing values and features where almost all values are missing. The second decay mechanism uses the time feature to decay the hidden state before calculating the new hidden state. We note that missing data at a time is not the same as features not being present (sampled) or a feature rarely changing value. We focus on the latter while Che et al. (2018); Bengio & Gingras (1996); Tresp & Briegel (1998) focus on the former.
Baytas et al. (2017) incorporate the time between events for event based sequences with irregular intervals in a similar fashion to the second decay mechanism in Che et al. (2018). This is done by decomposing the memory state into short and long term components, and then multiplying the short term component by a decay factor that decreases as the time between events increases. We use this in our own recurrent cell, and also expand upon the idea by incorporating multiple time features, not just limited to the time between adjacent events. We also use the same decomposition and decay method outside of our recurrent cell since the prediction time occurs some time after the final event. Their work does not consider sparse features.
Neil et al. (2016) modify the standard LSTM cell to address its issues with asynchronous time series. They do this by incorporating a time gate into the network that controls when and to what extent the hidden and memory states can be updated. This means that there are time steps where no updates are
made, and so the network accumulates changes in the feature vector before updating the hidden and memory states. While the time gate has learnable parameters, they still do not differentiate between features that occur at every time step versus those that rarely occur in the cell updates.
In summary, there is no prior work that considers the notion of sparse features and a single model for all five feature types.

heading: 3 MODELS

text:
The main contribution of this paper is the development of a recurrent cell which handles five distinct feature types. The following subsections review each of the feature types and describes how they are handled in the Sparse Time LSTM (STLSTM model). The five types are referred to as the following: dense features, sparse features, decay features, static standard features, and static decay features. The dense features are the standard RNN sequence input, such as the embedding of an event type or the sequence state features at a given time step, and are present at any given time in a sequence. The sparse features change values infrequently, and thus they can be considered as being present only at select times. Stating that the value is not present means the feature value has not changed from the previous time. A further assumption is that these feature values do not decay with time. The decay features must be related to time measured with respect to some condition, such as time since the previous event in an event driven sequence. These features are particularly useful when events in the sequence are clustered, meaning that we observe many events in close proximity alternating with long gaps. Both the static standard and the static decay features give information about the sequence as a whole, rather than being tied to a specific time step. Static standard features are time invariant, e.g. the gender of a sequence’s object, whereas static decay features are time related, e.g. the time since last event in the sequence was observed. Figure 1 depicts these concepts.
We consider a neural network to be a mapping f(X), where f represents the network and X is the input to the network. We split X first into two parts, X = (xstatic, x) where xstatic represents the sequence level static features and x represents the sequence features. The static features can be split into two parts xstatic = (xstatic,s, xstatic,∆), for static standard and static decay features respectively. The sequence features can further be broken down into three parts, x = (xd, x∆, xsp) that represent the dense, decay, and sparse features respectively. For notational convenience, each of these features has a vector at each time step of the sequence (even though in our implementation the sparse features would be used only when the value changes). The dense features are denoted as xd = (xd1, x d 2, ..., x d T ) for a sequence with T time steps. The decay features are represented as x∆ = (x∆1 , x ∆ 2 , ..., x ∆ T ).The sparse features, however, are represented slightly differently than the previous two types of features, because their changes are not always present. We use the term present for a sparse feature when its value changes. A single sparse feature k can be represented as a sequence of tuples, xspk = ((m1k, x sv 1k), ..., (mTk, x sv Tk)), where mtk ∈ {0, 1} is a mask value that is 1 when the feature is present and 0 if the feature is missing. If mtk = 1, then xsvtk is the actual new feature value, and otherwise the value of xsvtk does not impact the feed forward computation. If a sparse feature is present at a time, then this input is passed into and used in the cell updates. If there is no sparse input at a given time step, the sparse part of the cell is untouched at that time step.
Our recurrent cell is built off of the commonly used LSTM Hochreiter & Schmidhuber (1997), as well as its time-aware variant (TLSTM) Baytas et al. (2017). For LSTM-type cells, there is a memory state, C, and a hidden state, h, which pass from the cell at the previous time step and into the cell along with the features at the current time step. The memory state boosts performance for
long term dependencies, and the gate structure of the LSTM allows selective parts of the memory to be forgotten and updated. The standard LSTM architecture does not address irregularly sampled events, however, and the TLSTM variant addresses this by using the time elapsed between events to modify the memory state.
In the TLSTM cell, at each time step, first a fully connected layer is used to decompose the cell’s memory state into short and long term components. The time elapsed is passed as the input to a non-increasing decay function that maps to a scalar decay factor. The short term component of the memory state is multiplied by the decay factor that decreases as more time passes. The equations for a single decay feature x∆t for this process are below on the left, where g is a decay function, x ∆ t is the decay input, and Ct−1 is the previous cell memory state.
After the memory state is modified, the cell update is performed in the standard LSTM manner, with the exception that the modified cell memory state calculated in Equation 1 is used to update the current memory state. The equations are as follows on the right where xdt is the feature vector to the current time step. A diagram of this base cell is given in Figure 2.
CSt−1 = tanh ( W∆Ct−1 + b ∆ )
ĈSt−1 = C S t−1 · g ( x∆t ) CLt−1 = Ct−1 − CSt−1 C∗t−1 = C L t−1 + Ĉ S t−1,
fdt = σ(W d fhht−1 +W d fxx d t + b d f )
idt = σ(W d ihht−1 +W d ixx d t + b d i )
C̃dt = σ(W d Chht−1 +W d Cxx d t + b d C)
Cdt = f d t ∗ C∗t−1 + idt ∗ C̃dt ,
odt = σ(W d ohht−1 +W d oxx d t + b d o)
hdt = o d t ∗ tanh(Cdt )

heading: 3.1 DENSE FEATURES

text: The dense features are the standard features used for recurrent models. It is assumed that the features are not time decay related, e.g. they encode attributes of events, but not times between events. At each time step, the hidden state from the previous time step, the memory vector, and the feature vector for the current time step are input into the cell, and the hidden state and memory vector are updated for the next time step.

heading: 3.2 DECAY FEATURES

text:
Decay features are not relevant or applicable for some RNN applications such as text or video, but for a sequence with measurements or events that occur with varying frequency, time information can add predictive power.
In the beginning of this section, a model expressed by Equation 1 is presented that allows a single decay feature. Here we extend this to multiple decay features. Incorporating multiple decays requires a simple modification to the decay function g. Instead of mapping from a scalar to a scalar, it maps from a vector to a scalar. The proposed g function is g(x∆t ) = 1
log(e+αT x∆t ) , where α ≥ 0 is a
trainable vector.

heading: 3.3 SPARSE FEATURES

text:
Sparse features are similar in nature to the dense features, with the exception that their values change very rarely throughout the sequence. Like the dense features, the sparse features describe the state of the sequence at a particular time step. However, since they rarely change from one step to another, when treated in the same manner as dense features, the sparse features would just repeat inputs the vast majority of time steps. There is no clear cutoff point in new value frequency for which a dense feature turns into a sparse feature.
We propose a new recurrent cell, called the Sparse Time Long Short Term Memory (STLSTM) cell, that attempts to more strongly capture the change in sparse features. The STLSTM cell has a hidden state split into two parts, one corresponding to the dense features, and the other corresponding to the sparse features, ht = (hdt , h sp t ). Further, each sparse feature has its own memory state, and this memory state is only updated when there is a change in the feature value. At each time step, the
dense part of the hidden state is updated based on Equation 1 and Equation 2. For the sparse part of the hidden state, there is a proposed hidden state from each sparse feature, and these proposed hidden states are aggregated together.
Let us denote the memory state of sparse feature k as Csptk and the corresponding hidden state as hsptk . The main idea is to not change C sp tk if mtk = 0, i.e. to simply carry it over, and otherwise if mtk = 1 to use the feature xsvtk within LSTM-like update equations. Formally, if mtk = 0, then there is no change to the memory state or the hidden state, that is,
Csptk = C sp t−1,k, h sp tk = h sp t−1,k.
If there is a change in the feature value (mtk = 1), the new memory state is determined by the following equations:
fsptk = σ(W sp fhht−1 +W sp fxx sv tk + b sp f )
isptk = σ(W sp ih ht−1 +W sp ix x sv tk + b sp i )
C̃sptk = σ(W sp Chht−1 +W sp Cxx sv tk + b sp C ) Csptk = f sp tk ∗ C sp t−1,k + i sp tk ∗ C̃ sp tk .
Once the memory state is calculated, the hidden state parts are calculated using standard output gates. The equations for this are as follows:
osptk = σ(W sp ohht−1 +W sp oxx sv tk + b sp o ) hsptk = o sp tk ∗ tanh(C sp tk )
ht = [ hdt ,L(h sp t1 , ..., h sp tm;Wah) ] ot = [ odt ,L(o sp t1 , ..., o sp tm;Wao)
] Here L is an aggregation function that yields a vector of the same dimension as hsptk and Wah,Wao are trainable parameters. For example, L can be simply averaging the hidden state proposals or we can place a fully connected layer over all of the sparse hidden states, and use this layer to compute a single hidden state for all sparse features. A diagram for the STLSTM cell is depicted in Figure 3.

heading: 3.4 STATIC STANDARD FEATURES

text:
All previous discussions dealt with features that can be assigned to a specific time step in a sequence, but we can also have features that are sequence level instead of time step level. These features, which are not time related, give information about the sequence as a whole, so they should not serve as inputs to the recursive part.
The incorporation of these features is fairly simple. First the features are passed through a fully connected layer to get an embedding, and then this embedding is concatenated with the output, hT , of the recurrent cell at the final time steps. A diagram of this can be seen in Figure 4.

heading: 3.5 STATIC DECAY FEATURES

text:
Similar to the static standard features, the static decay features apply to the sequence as a whole rather than an individual time step. Their values are related to the time since the last observed event, e.g. the time between the final time step and the prediction time.
These features are used in the same manner as the decay features within the STLSTM cell. The output of the recurrent network, hT , is decomposed into short and long term components, and the decay factor is applied to the short term component before being added back to the long term component. Formally, this is given as
hST = tanh ( W static,∆hT + b static,∆ )
ĥST = h S T · g
( xstatic,∆ ) hLT = hT − hST h∗T = h L T + ĥ S T
This modified output is then concatenated with the embedding of the static standard features before input to the decoder.

heading: 4 COMPUTATIONAL STUDY

text: For all experiments in this section we use Keras with a Tensorflow backend on a single GeForce GTX 1080 GPU card. We use ADAM as the optimization algorithm, and keep track of the validation F1 score to control the number of training epochs. If the validation F1 score does not increase for 15 epochs, then training is terminated. We use standard weight initialization, Glorot uniform for weights connected to the inputs and orthogonal initialization for the recurrent weights. To test out the STLSTM cell with all five feature types, we use two data sets, one public and one proprietary.

heading: 4.1 POWER CONSUMPTION DATA SET

text:
The public data set is a modified version of the UCI household electric power consumption dataset (Dheeru & Karra Taniskidou (2017)). This data set contains measurements for seven different electrical quantities and sub-metering values with a sampling rate of one minute taken over the course of nearly four years. All of the features are sampled every minute, except for approximately 1.25% of the records which have no measurements. We simply fill in these missing values by repeating the record that immediately precedes it. Since the data set does not have natural sparse and decay features, we have to artificially create them, which is described in the Appendix.
For the experiments described in this section, we use sequences covering two hours worth of power data. The recurrent part of our network is composed of two stacked RNN cells. We compare using two architectures: one has STLSTM at the bottom layer and LSTM at the second layer, and the other has TLSTM at the bottom layer and LSTM at the second layer. Experiments have shown that using two layers is optimal. We use a standard LSTM cell as the second layer instead of STLTSM or TLSTM cells because we assume the time and sparsity information is encoded in the output of the base layer that is fed into the second layer. These all have a hidden dimension of 64, which is also the size of the single embedding layer for the static standard features. Using a same hidden layer size means that STLSTM cells have more parameters than the TLSTM cells, but preliminary experiments on TLSTM cells showed this is the optimal architecture for performance during inference. For all results the static features are present, unless it is stated otherwise.
The first metric we investigate is the relative performance of the STLSTM cell versus the standard TLSTM cell versus sparsity of individual sparse features. For this we use a dense layer as the aggregation function in the STLSTM cell. For each of the seven features, we set that feature to be sparse with a sparse ratio ranging from 0.01 to 0.15 and the remaining six to be dense. For the TLSTM model, the sparse features are input at every time step as dense features. Figure 5 shows the relative performance on F1 scores between the TLSTM and STLSTM models for both types of record subsampling, with percentages greater than 0 meaning the STLSTM performs better. The F1 score of STLSTM, which corresponds to the denominator, is approximately 0.7 but depends on which feature is made to be sparse.
A common characteristic for all series is that the relative performance of the STLSTM cell increases as the sparsity increases, but only to a certain point where it then maintains or slightly drops. Further, STLSTM offers a larger improvement in the case of the group sampling in most cases. As can be seen in Figure 5, the relative performance of each model depends on the feature we are treating as sparse. It is not surprising that the feature with the largest dependence on sparsity is the voltage
variable itself (represented by blue), since this is the feature we are making predictions on. The features with the smallest relative performance change are found to have the smallest response to sparsity as well, which may indicate that they have less predictive power and thus it is not surprising that the difference between the TLSTM and STLSTM is also small.
Further than looking at individual sparse features, we also investigate groups of sparse features with different levels of sparsity. We report the results on groups of sparse features with size 2, 3, and 4 since it was shown that 3 of the features are not affected by sparsity. Figure 5 also shows the relative performance for STLSTM and TLSTM models for groups of sparse features that were found to have the largest effect at a given group size and sparsity. Unsurprisingly, the characteristics of the series are the same as in the analysis of single features.Using more sparse features does increase the relative performance of the STLSTM cell to a point, but for this dataset where the features are closely related to one another the effectiveness is limited.
In addition to focusing on the relative performance between the TLSTM and STLSTM cells, we also consider the performance of different aggregation methods L within the STLSTM cell. In particular, we compare using a dense layer, an averaging aggregation, and a maximum aggregation at four different levels of sparsity. The aggregation method clearly does not matter if there is only one sparse feature, and so for this comparison we must use sets of sparse features. In particular, we report results using the set of 3 sparse features that was found to give the largest relative improvement for STLSTM. The results are summarized in Table 1a based on group sampling datasets.
As can be seen in Table 1a, the dense layer aggregation performs as well or better than the other two methods at every level of sparsity. The average and maximum aggregation have similar performance, perhaps slightly leaning toward the average method at low sparsity and the maximum method for higher sparsity.
Finally, we study the effect of adding both types of static features to the model. Table 1b shows the average relative improvements in F1 score for adding in one or both types of static features for different subsets of sparse features with varying levels of sparsity. It is clear from Table 1b that both types of features improve the performance of the model, with the static standard features having a larger effect. This larger effect may be specific to the features of the power consumption data, but generally both types of features improve performance when properly integrated into the model. With respect to sparsity, both types of static features improve the model more as the features become more sparse, with the static decay features being more dependent on sparsity.
It is worth discussing the impact of the added complexity of the STLSTM cell on training time. With STLSTM, as the number of sparse features grows, so too does the number of parameters in the model. This makes training slower per epoch, but it is mitigated in wall-clock training time by the fact that it takes fewer epochs to reach convergence. Using standard TLSTM, an epoch of training time takes about 10 seconds with the given sequence parameters for the datasets. When using four sparse features, this increases to about 18 seconds per epoch. However, the STLSTM cell generally reaches convergence in 40-50 epochs while the TLSTM cell requires 70-80 epochs.

heading: 4.2 REAL WORLD CHURN DATA SET

text:
In addition to this constructed dataset, we also use a real world proprietary dataset with naturally sparse features for churn prediction within a future time span. At each time step, there is an event embedding that is treated as a dense feature. In addition to this, there are approximately 60 additional sequence state features. These state features have varying levels of sparse ratios, ranging from 0.03 to 0.6. We experiment with different subsets of dense and sparse features using the sequence state features. Additionally, we use two decay features, one static standard feature, and one static decay feature. For this dataset we use a training set with 700,000 samples and validation/test sets with 200,000 samples each. Sequence length ranges from 1 to 150, but the samples are not evenly distributed by sequence length. The distribution is exponential, with a large portion of sequences on the lowest end of that range and the mean is approximately 40.
For this data set, we compare two stacked architectures composed of three stacked RNN cells. As before, the bottom layer uses either STLSTM or TLSTM, and the higher levels use standard LSTM cells. When multiple sparse features are present, we use a dense layer as the aggregation method since it performs best. All results are given relative to the standard TLSTM model with all 60 additional sequence state features treated as dense features, as this was found to outperform an all LSTM model by approximately 2% under the all dense setting.
Since this data set is naturally sparse, we do not tune the sparsity, but instead investigate the relative performance for different subsets of sparse and dense features. There are four qualitative feature subsets we primarily study. The first sparse subset contains features that relate to relative changes, e.g. a customer can upgrade/downgrade his service to a different tier. The second sparse subset includes true counts for feature values, e.g. the total number of people associated with an account. These two subsets are the most sparse and have average sparsity of 0.065. The other two feature subsets contain features relating customer specific (e.g. a customer relocates) and sequence specific information (e.g. the number of emails to customer service). The relative performance for these sparse feature subsets is found in Figure 5. We observe that using only relative change features gives the smallest performance gain. This is not surprising because in this case a repeated value of 0 has meaning and the features are specifically designed to capture changes, somewhat mitigating the intended effect of the STLSTM cell. Using the raw counts does give a larger performance increase.
Both customer and sequence specific subsets show the largest improvement, indicating that these sub groups are responsive to STLSTM architecture. It is interesting that these two subgroups do not necessarily contain only the most sparse features, but a mix between sparsity ratios roughly from 0.03 to 0.3. This suggests that in real applications with naturally sparse features there is a large range of sparsity that can occur in the sparse sub group of features.

heading: 4.3 FUTURE WORK

text: For future work, it would be interesting to incorporate even more feature types than the five covered in this work. One in particular is a feature type that gives time information looking forward in the sequence. All features in this work use time information related to past events, but there are cases that can benefit from the utility of incorporating future knowledge when available. One example of this is the time to the prediction from the current time step so the network can have direct knowledge of its absolute time location in the sequence.

heading: 5 APPENDIX

text:
The power consumption dataset is one long sequence, and so we break this down into many sequences. We create the sequences based on three parameters: sample time Ts, shift window, and sequence length T . To create the first sequence we first set the start index to the first record. A full sequence is created by selecting Ts records beginning at the start index. We further subsample from the Ts records in order to obtain final sequences with decay features in two ways. In the first way we randomly sample individual records. The first record in the full sequence is always kept, but after the first record we randomly drop records based on Bernoulli until there are T remaining. In the second way, we create groups of 5 records. We start with the first 5 records from the start index. Next we focus on records from start index + 8 to start index + Ts. We select a random record and the surrounding 4 records. We then repeat the procedure until we have T selected records. We finish with groups of 5 consecutive records that do not overlap. In either way we sample, this means the sampling rate is no longer a uniform one minute, and we use the time between two adjacent events to be the decay feature. The seven electrical features are dense features present at every time step in the sequence. The start index is then increased by the shift window and the process continues until we run through the entire dataset. If the shift window is less than the sample time, then there can be some overlap in the sequences. We allow these overlaps in the training set, but remove any sequences in the validation and test sets with subsequences duplicated in the training set.
Once the sequences are all created, we can create sparse features on any subset of the seven dense features. This is done by choosing a sparse ratio for each feature in the sparse subset, where the sparse ratio is the ratio of feature values that are kept in each sequence. We keep feature values present with uniform probability equal to the sparse ratio for that feature. If a feature value is not kept at a time step, its mask value is set to 0 at the time step. This allows us to easily experiment with different numbers of sparse features and the extent of the sparsity.
Both types of static features are also used for this dataset. There is one static decay feature, and it is the time elapsed between the last event of the sequence and the prediction time for that sequence, which is Ts events from the time of the first event. There are three categorical static standard features, and these are the day of the week, day of the month, and time of day (morning, afternoon, evening, night). Each of the sequences we use spans two hours or less, and we assign the static standard feature values based on the first event in the sequence. Figure 6 depicts these concepts.
The training target for the power consumption dataset is a multi-class classification target. We predict whether the average voltage over some time interval after the prediction time of a sequence stays within half a standard deviation, increases by more than half a standard deviation, or decreases by more than half a standard deviation when compared to the value averaged over the time span of the sequence measured from the first event to Ts time steps after the first event. The standard deviation value here is taken over the entire training set. This is an unbalanced classification task. While the exact majority class percentage varies depending on the way the sequences are created, it falls between 65% and 80% for our experiments. For the experiments described in Section 4.1 we use two hours of data corresponding to Ts = 120. We also use a shift window of 30 and set T = 50.