1908/1908.06973.md

¹https://deepmind.com/blog/alphastar-mastering-real-time-strategy-game-starcraft-ii/

²https://blog.openai.com/openai-five/

³https://blog.openai.com/learning-dexterity/---

2 RECOMMENDER SYSTEMS

A recommender system can suggest products, services, information, etc. to users according to their preferences. It helps alleviate the issues with overwhelming information these days by personalized recommendations, e.g., for news, movies, music, restaurants, etc.

In user-centric recommender systems, it is essential to understand and meet genuine user needs and preferences, using natural, unobtrusive, transparent interaction with the users. Recommender systems need to estimate, elicit, react to, and influence user latent state, e.g., satisfaction, transient vs. persistent preferences, needs, interests, patterns of activity etc. by natural interaction with users, and acting in user's best interests, i.e, user preferences, behavioural processes governing user decision making and reasoning, etc. RL will play a central role in all of these.

User-facing RL encounters some challenges, 1) large scale with massive number of users and actions, multi-user (MDPs), and combinatorial action space, e.g., slates; 2) idiosyncratic nature of actions, like stochastic actions sets, dynamic slate sizes, etc.; 3) user latent state, leading to high degree of unobservability and stochasticity, w.r.t. preferences, activities, personality, user learning, exogenous factors, behavioral effects, etc, which add up to long-horizon, low signal noise ratio (SNR) POMDPs; and, 4) eco-system effects, e.g., incentives, ecosystem dynamics, fairness, etc.

2.1 DECISION SERVICE

Contextual bandits are effective to select actions based on contextual information, e.g., in news article recommendation, selecting articles for users based on contextual information of users and articles, like historical activities of users and descriptive information and categories of content. This framework covers a large number of applications, and Table 1 shows some examples.

	news website (News)	tech support assistance (TechSupp)	could controller (Cloud)
decision to optimize	article to display on top	response to query	wait time before reboot unresponsive machine
context	location, browsing history, ...	previous dialog elements	machine hardware/OS, failure history, ...
feasible actions	available news articles	pointers to potential solutions	minutes in $\backslash \{1,\; 2,\; \backslash dots,\; 9\backslash \}$
reward	click/no-click	(negative) human intervention request	(negative) total downtime

Table 1: Example applications of the Decision Service. (reproduced from Agarwal et al. (2016))

However, such setting encounters two challenges. 1) Partial feedback. The reward is for the selected action only, but not for unexplored actions. 2) Delayed rewards. Reward information may arrive considerably later after taking an action. As a result, an implementation usually faces the following failures: 1) partial feedback and bias; 2) incorrect data collection; 3) changes in environments; and 4) weak monitoring and debugging.

A/B testing is an approach for exploration to address the issue of partial feedback. It tests two policies by running them on random user traffic proportionally. Thus the data requirements scale linearly with the number of policies. Contextual bandits allows to test and optimize exponential number of policies with the same amount of data. And it does not require policies to be deployed to test, to save business and engineering effort. Such capacity is referred to as multiworld testing (MWT). Supervised learning does not support exploration, so it does not tackle contextual settings or the issues of partial feedback and bias.

The Decision Service defines four system abstractions, namely, explore to collect data, log data correctly, learn a good model, and deploy the model in the application, to complete the loop for effective contextual learning, by providing the capacity of MWT with techniques of contextual bandits and policy evaluation.Figure 5 shows the Decision Service architecture. The Client Library implements various exploration policies to implement the Explore abstraction. It interfaces with the App, takes context feature and event key as input and outputs an action. It sends data to the Log component, which generates data correctly by the Join Service to log data at the point of decision. Log sends the exploration data to the Online Learner and the Store. The Explore and Log components help address failure 1, partial feedback and bias and failure 2, incorrect data collection. The Online Learner provides online learning from contextual bandit exploration data to implement the Learn abstraction. It continuously incorporates data and checkpoints models at a configurable rate to the Deploy component. This helps address failures 3, changes in environments and failure 4, weak monitoring and debugging. The Store provides model and data storage to implement the Deploy abstraction. The Offline Learner also uses the data for offline experimentation, to tune hyperparameters, to evaluate other learning algorithms or policy classes, to change the reward metric, etc., in a counterfactually correct way. The Feature Generator generates features automatically for certain types of content.

graph TD
    App[App] -- context --> ClientLibrary[Client Library or Web API]
    ClientLibrary -- action --> App
    ClientLibrary -- reward --> App
    ClientLibrary --> Log[Log]
    ClientLibrary --> Store[Store]
    Log -- exploration data --> OnlineLearner[Online Learner]
    Log --> JoinService[Join Service]
    JoinService -- interaction reward --> ClientLibrary
    OnlineLearner -- models --> Store
    OnlineLearner -- real-time eval --> Dashboard[dashboard safeguards etc.]
    Store -- models --> OnlineLearner
    Store -- models/data from Store --> OfflineLearner[Offline Learner]
    OfflineLearner -- params models --> OnlineLearner
    FeatureGenerator[Feature Generator] -- context --> ClientLibrary
  

Figure 5: DecisionService Architecture (from Agarwal et al. (2016))

The design also helps make the system responsive, reproducible, scalable, fault tolerant, and flexible for deployment. The Decision Service has several deployment options: self-hosted in a user’s Azure account, hosted in Microsoft’s Azure account to share resources with other users, and local model on a user’s machine.

We list several applications of Decision Service in the following. MSN is basically the News problem in Table 1, where MSN’s front-end servers decide how to order articles on the homepage according to a user’s requests. Experiments show > 25% click through rate (CTR) improvements. Complex recommends videos to come with news articles and recommends top news articles, and achieves a lift of > 30%. TrackRevenue maximizes revenue with recommendation of landing pages for in-app advertisement, and achieves 18% revenue lift. Toronto provides answers to technical support questions to reduce the load. Azure Compute optimizes wait time before rebooting unresponsive virtual machines in a cloud service, and estimates a 19% reduction of waste time.

2.2 HORIZON: AN OPEN SOURCE APPLIED RL PLATFORM

Horizon is Facebook’s open source applied RL platform. It has the following features.

1. 1. Data preprocessing. A Spark pipeline converts logged data into the format suitable for training various deep RL models. In production systems, data are logged as they come, and an offline logic joins the data into the format for RL training.
2. 2. Feature normalization. Horizon analyzes the training data and optimizes the transformation function and parameters to normalize features to learn faster and better.
3. 3. Data understanding tools. Horizon uses a data-driven, model-based approach to check if several problem properties conform to the MDP formulation, e.g., if state features are not important to predict next states, then the problem is not sequential, and, if state features do not predict rewards, then the problem may be formulated as multi-arm bandits. The model can be used to compute feature importance and select important ones for training. This provides explainability to RL practitioners.---
4. 4. Model implementation. Horizon contains variants of DQN for problems with discrete action spaces, parametric action DQN to handle large action spaces, and DDPG and soft actor-critic for problems with continuous action spaces.
5. 5. Multi-node and multi-GPU training. Horizon supports training with a CPU, a GPU, multiple GPUs, and multiple nodes.
6. 6. Model understanding and evaluation. Horizon provides training metrics of temporal difference loss (TD loss) and Monte Carlo loss (MC loss) to show the stability and convergence of the training process. TD loss measures the function approximation error. MC loss measures the difference between the model's Q-value and the logged value.

Counterfactual policy evaluation (CPE) methods can predict the performance of a policy without deploying it. Otherwise, many A/B tests may be required to find the optimal model and hyperparameters.

1. 7. Optimized serving. Horizon exports trained models from PyTorch to Caffe2 via ONNX. Data are logged with unique keys, including possible actions, the propensity of choosing an action, the selected action, and the received reward. The reward usually comes later, and join operations are needed to form complete data points.
2. 8. Tested algorithms. Horizon borrows ideas from best practices in building software systems and tests algorithms with unit tests and integration tests.

The Horizon RL pipeline, as illustrated in Figure 6, consists of: 1) timeline generation, which runs across thousands of CPUs; 2) training, which runs across many GPUs; and 3) serving, which spans thousands of machines.

graph TD; Spark[Spark: Timeline Generation] --> Scipy[Scipy: Feature Identification]; Scipy --> PyTorch[PyTorch 1.0: Preprocessing -> Training -> Evaluation]; PyTorch --> OpenAI[OpenAI Gym: Gym Environment]; PyTorch --> ONNX[ONNX: FBLearner Predictor];

The diagram illustrates the Horizon RL pipeline. It starts with 'Spark' for 'Timeline Generation', which leads to 'Scipy' for 'Feature Identification'. This is followed by 'PyTorch 1.0' which includes 'Preprocessing', 'Training', and 'Evaluation' steps. The 'PyTorch 1.0' block also interacts with 'OpenAI Gym' for 'Gym Environment' and 'ONNX' for 'FBLearner Predictor'.

Figure 6: Horizon RL pipeline. (from https://code.fb.com/ml-applications/horizon/)

Horizon has been deployed for notification services for push notifications and page administrator notifications at Facebook to deliver more relevant notifications, and has also been applied to video bitrate adaptation and other applications.

Push notifications are a channel for personalized and time sensitive updates, about posts or stories, friends updates, groups, pages, events, etc. An MDP is formulated as follows. An action is sending or dropping a notification. A state consists of features representing the person and the notification candidate. Rewards reflect interactions and activities on Facebook, and volume of notifications sent. If the difference between the values of sending and dropping is large, sending the notification has a significant value. A/B tests show that the tested RL model outperforms the control non-RL model.### 2.3 NEWS RECOMMENDATION

One approach using RL for single item recommender systems follows. The system may recommend multiple items; however, the recommender systems are not designed for multiple items in mind, e.g., by ordering items according to their $Q$ values.

The model is built for news recommendation; however, the principles applies to general recommender systems. Several challenges it needs to handle are: 1) difficulties in handling the dynamics in news recommendations, e.g., news becomes obsolete fast, and users change their preferences from time to time; 2) most recommender systems considering users' click/no click or ratings as feedback, but not including users' return behaviour; and 3) the diversity of recommended items.

To formulate a recommender system as an RL problem, we need to define the environment, the agent, states, actions, and rewards, as illustrated in Figure 7. Users and news form the environment. The recommendation algorithm is the agent.

The diagram illustrates the Deep RL news recommender system framework. It is divided into three main components: Environment, State, and Agent.

• Environment: Located at the top left, it contains 'User' and 'News' icons. It provides the 'State' to the Agent and receives 'Action' and 'Reward' from it.
• State: Located at the top right, it shows a sequence of colored blocks representing the current state. Below it, 'Action 1', 'Action 2', and 'Action m' are listed, each with a corresponding set of colored blocks.
• Agent: Located at the bottom right, it contains a 'DQN + Explore' block and a 'Memory' block. It receives the 'State' from the Environment and sends the 'Action' back to it.
• Reward: Located at the bottom left, it shows a 'Click / no click' icon (red checkmark and cross) and a 'User activiness' icon (red line graph). It receives the 'Action' from the Agent and sends the 'Reward' back to it.

Figure 7: Deep RL news recommender system. (from Zheng et al. (2018))

To define states and actions, we first discuss feature construction. There are four categories of features: news features, user features, user news features, and context features. News features describe if a piece of news contains certain properties like headline, provider, and topic category over several time granularities respectively. The time granularity can be the last 1 hour, 6 hours, 24 hours, 1 week, and 1 year. User features describe if the user clicks news with certain properties like those in news features over several time granularities respectively. User news features describe the interaction between users and news, including the frequency of the entity, category, topic category, and provider appearing in users' histories. Context features describe the context of the occurrence of a news request, including its time, weekday, and freshness of news, i.e., the gap between the publish time and the request time. Then, state features are defined with user features and context features, and action features are defined with user news features and context features.

Usually, for recommender systems, a reward is defined by the implicit click/no click information or explicit ratings. However, some factors, e.g., user activeness, may also play an important role. User activeness is related to the frequency users checking news and behaviours of users return. A reward is then defined as a combination of signals for clicks and user activeness.

Next we discuss the deep RL recommender system model framework, as illustrated in Figure 8.

The recommendation model starts with offline handling of the four features, extracting from users and news. The model is trained offline with user-news click logs using a Deep Q-Network (DQN). After this, the model enters the online mode.

When the agent receives a news request, it recommends a top- $k$ list of news, based on features of the user and news. Technically, the agent utilizes the state action value function $Q(s, a)$ to select the most $k$ preferable news for the user. The user then responds with click or not as a feedback. The agent may update the decision network $Q$ after each recommendation or after certain time duration,Figure 8: Deep RL recommender system model framework. (from Zheng et al. (2018))

e.g., 1 hour, with many recommendations. The model repeats the above procedure to refine the decisions.

Recommender systems also face the exploration vs. exploitation dilemma. The popular methods like $\epsilon$ -greedy or upper confidence bound (UCB) make random recommendations, which may cause undesirable results. Exploration is also necessary to improve the diversity of the recommended news. One method is to explore news candidates close to those the agent would recommend.

There are several performance metrics to evaluate a recommender system. Click Through Rate (CTR) is defined as the number of clicked items divided by the number of total items. Precision@ $k$ is defined as the number of clicks in top- $k$ recommended items divided by $k$ . Normalized Discounted Cumulative Gain (nDCG) is related to ranks of items in the recommendation list, the length of the list, the ranking function, and the information about click or not. nDCG is basically the sum of discounted clicks, where discount factors are related to ranks. One way to define recommendation diversity is the sum of cosine similarity between different recommended item pairs divided by the number of such item pairs. For two items, the more different one is from another, the lower is the cosine similarity in the range of $[0,1]$ .

The method compares with several baselines, using logistic regression, factorization machines, wide & deep neural networks, and linear UCB. The experiments are conducted with offline dataset and with online deployment in a commercial news recommendation application. The method outperforms the baselines.

2.4 MULTIPLE ITEMS RECOMMENDATION

A recommender system needs to recommend multiple items at the same time, which is also called slate recommendation, e.g., a slate of videos to users visiting YouTube. In this problem, there may be non-trivial long/short-term trade-offs, and RL is a natural solution.

In the MDP/RL formulation, states refer to user features, user history, and contextual features; actions refer to possible slates of recommendations; reward refers to immediate engagement of a selected recommendation, e.g., watched video; and the discount factor is chosen to reflect target/expected session length. The combinatorics of slates pose problems for generalization, exploration and optimization. An ideal way is to decompose value of slate into value of constituent items.

We may also encounter the item interaction problem, so that the presence of some items on the slate impacts user response (hence value) of other items. As a result, the value of slate depends on user choice model, which requires joint optimization of the slate.

One approach is SlateQ with slate decomposition. SlateQ decomposes slate Q-values into item Q-values, with specific assumptions about user choice from slate, i.e., user selects one item from slate,---

and state transitions and reward depend only on selected items. We will learn conditional-on-click, item-wise Q-values, and slate Q-values are derived and fed into item Q-values, with decomposed TD/SARSA updates and full Q-learning updates.

Slate optimization is tractable for certain user choice models. The standard formulation is fractional mixed-integer program. It is a simplified product-line or assortment optimization problem. It can be relaxed and transformed into linear program to obtain an optimal solution. We can also apply top- $k$ and greedy methods.

RecSim is a synthetic environment. Documents are represented by topic vector and quality score, both of which are random. Users are represented by interest vector over topics and satisfaction, which are random initially. User interaction describes that it is more likely for a user to consume an item on the slate if interested. User state dynamics describes that, interests move stochastically in the direction of the consumed item, satisfaction increases or decreases stochastically with item quality, and less satisfied scenarios occur with greater odds of terminating session, e.g., due to time budget. There are tradeoffs between nudging toward higher-quality topics and decreasing immediate engagement. Experiments are conducted with 20 documents, 10 candidates and 3 items per slate to test full Q-learning.

2.5 ANNOTATED BIBLIOGRAPHY

Recommender systems have attracted a lot of attention recently. Popular approaches include content based methods, collaborative filtering based methods, and hybrid methods. Recently, deep learning plays an important role. See Zhang et al. (2018) for a survey.

The discussion of the Decision Service is based on Agarwal et al. (2016). Li et al. (2010) formulate personalized news articles recommendation as a contextual multi-armed bandit problem, considering contextual information of users and articles, such as historical activities of users and descriptive information and categories of content. In addition, Karampatziakis et al. (2019) discuss lessons from real life RL in a customer support bot.

The discussion about Horizon is based on Gauci et al. (2019) and a blog titled Horizon: The first open source reinforcement learning platform for large-scale products and services at https://code.fb.com/ml-applications/horizon/.

The discussion about single item recommendation, in particular, news recommendation, is based on Zheng et al. (2018). See Zhao et al. (2019) for a survey on deep RL for search, recommendation, and online advertising.

The discussion of user-facing RL in the beginning and multiple item recommendation is based on the invited talk by Craig Boutilier titled Reinforcement Learning in Recommender Systems: Some Challenges in the ICML 2019 Workshop on Reinforcement Learning for Real Life, at https://sites.google.com/view/RL4RealLife. Ie et al. (2019a) discuss SlateQ. Ie et al. (2019b) discuss RecSim. Chen et al. (2019) and Shi et al. (2019) also discuss model building.

In addition, Theocharous et al. (2015) formulate a personalized ads recommendation systems as an RL problem to maximize life-time value (LTV) with theoretical guarantees; Chen et al. (2018) propose to stabilize online recommendation with stratified random sampling and approximate regretted reward. Zhao et al. (2018a) study page-wise recommendation; Zhao et al. (2018b) study the effect of not only positive but also negative feedback; Hu et al. (2018) study ranking in e-commerce search engine.### 3 COMPUTER SYSTEMS

Many problems in computer systems are about sequential decision making, and manual design is common for strategies involved. RL is an approach to automate and optimize such strategies.

3.1 NEURAL ARCHITECTURE SEARCH

Deep learning has significant achievements recently in image processing, speech processing, and natural language processing. How to design neural network architectures is a critical issue. Neural architecture search is an approach using RL.

In neural architecture search, as illustrated in Figure 9, a recurrent neural network (RNN) is used to generate neural network descriptions and is trained to maximize the expected accuracy on a validation data set with RL. A variable-length string represented by the RNN specifies the structure and connectivity of a neural network. The list of tokens in the string can be regarded as a list of actions to design a neural network architecture. This can represent different components in neural networks, like 1) for a convolutional layer, including hyper-parameters like filter width, filter height, stride width, stride height, and the number of filters; 2) for pooling, batchnorm, local contrast normalization, skip connections, and branching layers; 3) for a recurrent cell; and 4) for a feedforward layer, etc. A state is implicit, and can be regarded as the partial network architecture yielded by the RNN. With the parameters of the RNN, a neural network can be sampled, and it can be trained to convergence to obtain an accuracy on a validation data set, which serves as the reward, based on which the parameters of the RNN will be updated with REINFORCE, a policy gradient RL algorithm. To reduce variance for policy gradient estimation, a baseline is included by taking an exponential moving average of the previous validation accuracies.

graph LR; Controller["The controller (RNN)"] -- "Sample architecture A with probability p" --> Training["Trains a child network with architecture A to get accuracy R"]; Training -- "Compute gradient of p and scale it by R to update the controller" --> Controller

Figure 9: An overview of neural architecture search. (from Zoph and Le (2017))

Experiments are conducted on CIFAR-10 for image classification and the Penn Treebank dataset for language modelling.

It is computationally expensive to search for good neural network architectures over a large dataset like ImageNet. It is thus desirable to transfer a good architecture searched over a small dataset like CIFAR-10 to ImageNet.

An approach is to search for the best generic convolutional layer or cell structure consisting of convolutional filters, nonlinearities, and connections as the motif to repeat multiple times to build convolutional networks. Two types of convolutional layers are designed for image classification: 1) a Normal Cell returns a feature map of the same dimension and 2) a Reduction Cell returns a feature map with the height and width halved. An RNN is used to search for the structures of a Normal Cell and a Reduction Cell with RL. The RNN predicts each cell as a group of multiple blocks, and each block has 5 prediction steps: in Step 1 and 2, select two hidden states respectively from two outputs from lower cells or the input image, or two hidden states from previous blocks; in Step 3 and 4, select operations to apply to the hidden states in Step 1 and 2, respectively; in Step 5, select a method, element-wise addition or concatenation, to combine outputs of Step 3 and 4.

In Step 3 and 4, the RNN chooses operations from the following prevalent ones: identity, $1 \times 3$ then $3 \times 1$ convolution, $1 \times 7$ then $7 \times 1$ convolution, $3 \times 3$ dilated convolution, $3 \times 3$ averagepooling, $3 \times 3$ max pooling, $5 \times 5$ max pooling, $7 \times 7$ max pooling, $1 \times 1$ convolution, $3 \times 3$ convolution, $3 \times 3$ depth-wise-separable convolution, $5 \times 5$ depth-wise-separable convolution, and $7 \times 7$ depth-wise-separable convolution.

The overall architectures of convolutional networks are predetermined manually, with multiple normal cells being stacked between reduction cells, and the number of normal cells is a hyperparameter.

Experiments show that, convolutional neural networks with such transferable structures can achieve comparable or better performance on CIFAR-10 and ImageNet, as well as on mobile and embedded platforms.

3.2 DEVICE PLACEMENT

The computational requirements for training and inference with neural networks are increasing recently. A common approach is to use a heterogeneous environment including a mixture of hardware devices like CPUs and GPUs. How to optimize device placement, e.g., placing TensorFlow computational graphs onto hardware devices, thus becomes an issue. In the following, we discuss an approach with RL.

A sequence-to-sequence model with long short-term memory (LSTM) and an attention mechanism are used to predict how to place operations in a TensorFlow graph onto available devices. The sequence of operations is input to the encoder recurrent neural network (RNN), and is embedded by concatenating their information about type, output shape, and adjacency information. The decoder is an attentional LSTM with the number of time steps equal to the number of operations in the computational graph. At each step, the decoder output a device to place the corresponding operation in the encoder, and the embedding of the device becomes an input to the decoder in the next step. Figure 10 illustrates the device placement model architecture.

Figure 10: Device placement model architecture. (from Mirhoseini et al. (2017))

With the parameters of the encoder and decoder RNNs and the attention mechanism, we can sample a device placement and run it to check the performance of running time. The reward signal is the square root of running time. The parameters are tuned with an RL algorithm, in particular, REINFORCE; and a moving average baseline is used to reduce the variance. To improve efficiency, co-locating groups are formed either manually or automatically with the assistance of a neural network, so that operations in the same group are placed on the same device.

Experiments are conducted on ImageNet classification with Inception-V3, language modelling, and neural machine translation.

3.3 DATA AUGMENTATION

Data augmentation increases data amount and diversity by random augmentations. It is desirable to automate data augmentation, rather than to do it manually, or to directly hardcode invariances into the model architecture. In the following, we discuss how to find an optimal augmentation policy by formulating it as a discrete search problem and solving it with RL.

The search space consists of policies, each of which is composed of 5 sub-policies, and each sub-policy is formed by two sequential image operations with two hyperparameters for the probability of applying it and its magnitude.We discuss image operations in the following, where $m$ denotes the parameter magnitude. ShearX/Y, shear the image horizontally/vertically with a rate $m$ ; TranslateX/Y, translate the image horizontally/vertically by the number of $m$ pixels; Rotate, rotate the image $m$ degrees; AutoContrast, maximize the image contrast; Invert, invert image pixels; Equalize, equalize the image histogram; Solarize, invert pixels above a threshold $m$ ; Posterize, reduce up to the number of $m$ bits for each pixel; Contrast, control the image contrast; Color, adjust the image color balance; Brightness, adjust the image brightness; Sharpness, adjust the image sharpness; Cutout, set a random square patch with side-length $m$ of pixels to grey; Sample Pairing, add the image linearly with another image weighted by $m$ , and keep the label.

A recurrent neural network (RNN) is used as a controller, which has 30 softmax predictions for 5 sub-policies, each having 2 operations, and each operation having operation type, magnitude, and probability. A neural network model is trained with augmented data generated by applying the 5 sub-policies on the training dataset, in particular, one of 5 sub-policies is selected randomly to augment an image in the mini-batch. The accuracy of the model on the validation dataset is the reward for training the controller. Proximal Policy Optimization (PPO) algorithm is used for training the RNN controller. At the end, the best 5 policies, i.e., 25 sub-policies, are concatenated to form a single final policy. Figure 11 shows an example. Experiments are conducted on CIFAR-10, CIFAR-100, SVHN, and ImageNet datasets.

Figure 11: A policy found on SVHN, and how to use it. (from Cubuk et al. (2019))

3.4 CLUSTER SCHEDULING

Data processing clusters are common in data center and cloud computing. It is critical to design efficient cluster scheduling algorithms considering workload characteristics.

Usually a directed acyclic graph (DAG) encodes job stages and dependencies. A graph embedding with a graph neural network takes job DAGs as input and outputs three types of embeddings: per-node embeddings, per-job embeddings and a global embedding. A graph embedding can encode state information like attributes of job stages and DAG dependency structure. Nodes of DAGs carry stage attributes like the number of remaining tasks and expected task duration. Per-node embeddings encode information about the node and its children. Per-job embeddings encode information about the entire job. The global embedding encode a cluster-level summary from information of all per-job embeddings. Such embeddings are learned via end-to-end training.

A feature vector of a node in a job DAG is composed of: 1) the number of tasks remaining in the stage; 2) the average task duration; 3) the number of executors currently working on the node; 4) the number of available executors; and 5) whether available executors are local to the job.

Figure 12 illustrates an RL framework for cluster scheduling. When scheduling events like completion of a stage or arrival of a job occur, the agent observes the state of the cluster, i.e., the status of the DAGs in the scheduler’s queue and the executors, uses the graph neural network to convert the state into a feature vector, and decides on a scheduling action using the policy network. The reward can be the average of job completion time, which is used to optimize the scheduling policy. The reward can also be the makespan.Figure 12: RL framework for cluster scheduling. (from Mao et al. (2019b))

3.5 AN OPEN PLATFORM FOR COMPUTER SYSTEMS

Many computer systems problems are by nature sequential decision making problems, and can be formulated as MDPs, thus RL is a solution method. One challenge is that there are many details about computer systems. Park is an open platform for learning augmented computer systems, hiding details of computer systems to machine learning researchers. Park provides environments for a wide range of systems problems, namely, 1) adaptive video streaming; 2) Spark cluster job scheduling; 3) SQL database query optimization; 4) network congestion control; 5) network active queue management; 6) circuit design; 7) Tensorflow device placement; 8) content delivery networks (CDN) memory caching; 9) account region assignment; 10) server load balancing; and, 11) switch scheduling. Table 2 shows their RL formulations and relevant issues, w.r.t. environment, type, state space, action space, reward, step time, and challenges.

environment	type	state space	action space	reward	step time	challenges
adaptive video streaming	real/sim	past network throughput measurements, playback buffer size, portion of unwatched video	bitrate of the next video chunk	combination of resolution and stall time	real: ~3s Sim: ~1ms	input-driven variance, slow interaction time
Spark cluster job scheduling	real/sim	cluster and job information as features attached to each node of the job DAGs	node to schedule next	runtime penalty of each job	real: ~5s Sim: ~5ms	input-driven variance, state representation, infinite horizon, reality gap
SQL database query optimization	real	query graph with predicate and table features on nodes, join attributes on edges	edge to join next	cost model or actual query time	~5s	state representation, reality gap
network congestion control	real	throughput, delay and packet loss	congestion window and pacing rate	combination of throughput and delay	~10ms	sparse space for exploration, safe exploration, infinite horizon
network active queue management	real	past queuing delay, enqueue/dequeue rate	drop rate	combination of throughput and delay	~50ms	infinite horizon, reality gap
Tensorflow device placement	real/sim	current device placement and runtime costs as features attached to each node of the job DAGs	updated placement of the current node	penalty of runtime and invalid placement	real: ~2s Sim: ~10ms	state representation, reality gap
circuit design	sim	circuit graph with component ID, type and static parameters as features on the node	transistor sizes, capacitance and resistance of each node	combination of bandwidth, power and gain	~2s	state representation, sparse space for exploration
CDN memory caching	sim	object size, time since last hit, cache occupancy	admit/drop	byte hits	~2ms	input-driven variance, infinite horizon, safe exploration
multi-dim database indexing	real	query workload, stored data points	layout for data organization	query throughput	~30s	state/action representation, infinite horizon
account region assignment	sim	account language, region of request, set of linked websites	account region assignment	serving cost in the future	~1ms	state/action representation
server load balancing	sim	current load of the servers and the size of incoming job	server ID to assign the job	runtime penalty of each job	~1ms	input-driven variance, infinite horizon, safe exploration
switch scheduling	sim	queue occupancy for input-output port pairs	bijection mapping from input ports to output ports	penalty of remaining packets in the queue	~1ms	action representation

Table 2: Overview of the computer system environments supported by Park platform. (reproduced from Mao et al. (2019a))These problems are along three dimensions, in particular, a) global vs. distributed control; b) fast control loop vs. planning; and, c) real system vs. simulation. Some environments use real systems in the backend. For the other environments, simulators are provided with well-understood dynamics.

The authors also discuss challenges that off-the-shelf RL algorithms may not work, particularly, sparse meaningful space for exploration and representation for state-action space, and input-driven variance, infinite horizon, and reality gap for decision process.

As shown in Figure 13, an RL agent connects with the computer system through a request/response interface, which make the system complexity transparent. An RL agent can interact with a real system or a simulator.

Figure 13: Park architectures an RL-as-a-service design paradigm. (from Mao et al. (2019a))

3.6 NP-HARD PROBLEMS

NP-hard problems, e.g., minimum vertex cover, maximum cut, travelling salesman problems (TSP), and graph coloring, have many applications, like planning, scheduling, logistics, compilers, and design automation. However, we do not know polynomial time algorithms for the hard ones among them, like those mentioned above. Note the hardness is in the sense of worst case complexity, and in practice, even very large problems can be solved, approximately or heuristically. It is therefore desirable to design efficient and effective algorithms to solve such large-scale problems.

NP-hard problems may be tackled with exact, approximate, or heuristic algorithms.⁴ Exact algorithms may use enumeration or branch-and-bound, may be formulated as integer programming, and are usually prohibitive for large instances. Approximate algorithms have polynomial time complexity, with or even without sub-optimal performance guarantees. Heuristic algorithms are usually fast, yet without performance guarantee, and usually need considerable manual design. We discuss how to learn good heuristics for several graph combinatorial optimization problems with RL.

In the following we give brief definitions of several problems. In minimum vertex cover, we find a subset of nodes on a graph to cover all edges, and the number of nodes is minimal. In maximum cut, we find a subset of nodes on a graph to maximize the weight of the cut edges forming with nodes not in the subset. In TSP, we find a tour to visit all the nodes only once and to minimize the total weight. In coloring, we assign the minimal number of colors to nodes so that adjacent nodes are of different colors.

MINIMUM VERTEX COVER, MAXIMUM CUT, AND TSP

We first discuss RL formulations for addressing the problems of minimum vertex cover, maximum cut, and TSP. Nodes in a graph are represented with embeddings to allow algorithmic flexibility with diverse graphs. A state is a sequence of actions to choose nodes on a graph. An action is to choose a node not part of the current partial solution. Both a state and an action are represented by the node embeddings. The reward is the change in the cost function after taking an action in a state. The policy specifies which node to choose at the current state.

⁴Here, heuristic algorithms usually yield inexact solutions. Heuristic search, a branch in AI, like A* and IDA*, guarantees exact solutions if solved. Heuristic search is close to branch-and-bound.---

For minimum vertex cover, a state is the subset of nodes in the current partial solution, an action is to add a node to the partial solution, the reward is -1, and it terminates when all edges are covered. For maximum cut, a state is the subset of nodes in the current partial solution, an action is to add a node to the partial solution, the reward is the change in cut weight, and it terminates when the cut weight stops improving. For TSP, a state is the partial tour, an action is to add a node to the partial tour, the reward is the change in tour cost, and it terminates when the tour contains all nodes.

A combination of multi-step Q-learning and fitted Q-iteration are used to learn the action value Q function, which can derive an optimal policy directly. Experiments are conducted on generated graphs with number of nodes from 50 to 1200.

ALPHAGO ZERO

We give a brief review of AlphaGo Zero in the following. It is followed to learn an optimal policy for graph coloring as we discussed later.

AlphaGo Zero 1) learns from random play, with self-play RL, without human data or supervision; (2) does not need manual feature engineering; (3) uses a single neural network to represent both policy and value; and (4) utilizes the neural network for state evaluation and action sampling for MCTS, and it does not perform Monte Carlo rollouts.

AlphaGo Zero deploys several recent achievements in neural networks: ResNets, batch normalization, and rectifier nonlinearities. AlphaGo Zero has three main components in its self-play training pipeline executed in parallel asynchronously: (1) optimize neural network weights from recent self-play data continually; (2) evaluate players continually; and (3) use the strongest player to generate new self-play data. When AlphaGo Zero playing a game against an opponent, MCTS searches from the current state, with the trained neural network weights, to generate move probabilities, and then selects a move.

AlphaGo Zero follows a generalized policy iteration (GPI) scheme, incorporating Monte Carlo tree search (MCTS) inside the training loop to perform both policy evaluation and policy improvement. MCTS may be regarded as a policy improvement operator, outputting action probabilities stronger than raw probabilities of the neural network. Self-play with search may be regarded as a policy evaluation operator, using MCTS to select actions, and game winners as samples of value function. Then the policy iteration procedure updates the neural network's weights to match action probabilities and value respectively more closely with the improved search probabilities and self-play winner, and conducts self-play with updated neural network weights in the next iteration to make the search stronger.

As shown in Figure 14, in Step a with self play, AlphaGo Zero plays a program against itself; in Step b, AlphaGo Zero trains the neural network with data collected from self play.

As shown in Figure 15, in Step a, MCTS selects a move which most likely leads to a good result; in Step b, MCTS expands the leaf node and evaluates the associated position by the neural network; in Step c, MCTS backups information in the subtree traversed; and, in Step d, MCTS plays the game with the updated search probabilities.

GRAPH COLORING

Next we discuss an RL formulation for graph coloring. A state represents the current partial assignment of colors to nodes. An action is to assign a valid color to the next node. One way to define a reward is the negative total number of colors assigned so far. A policy maps a state to an action. To treat the graph coloring as a zero sum game, and to deploy self-play, an alternative way to define a reward is similar to computer Go, with win, lose and tie, for the cases that the policy has fewer, more, or the same number of colors, comparing with the current best policy.

For graph coloring, there are graph context, problem context, and colors context. Graph context contains embeddings for the number of nodes in the graph, the number of assigned colors, and the number of already colored nodes. Problem context contains embeddings for nodes just been colored and nodes scheduled for coloring next. Possible colors context contains embeddings for nodes colored with possible colors.Figure 14: Self-play RL in AlphaGo Zero. (from Silver et al. (2017))

Figure 15: MCTS in AlphaGo Zero. (from Silver et al. (2017))

A probability network computes the probability to assign a valid color to the current node, taking inputs of graph context, problem context, and context for each possible color. A value network computes the expected outcome of the coloring problem, i.e., win, lose, or tie, using problem context and colors context.

Comparing with computer Go, in graph coloring, we need to deal with diverse graphs, and problem sizes can be much larger. In experiments, the number of nodes varies from 32 to 10 million, and may require up to 300 GPUs for training. After training, we may distill the best heuristics into models as production tools.

3.7 ANNOTATED BIBLIOGRAPHY

The discussion about neural architecture search is based on Zoph and Le (2017). The discussion about transferable architecture search is based on Zoph et al. (2018). The discussion about device placement is based on Mirhoseini et al. (2017). The discussion about data augmentation is based on Cubuk et al. (2019). These are part of the effort of AutoML. See an overview of Google’s work on AutoML and future directions, video at https://slideslive.com/38917182.---

The discussion about cluster scheduling is based on Mao et al. (2019b). The discussion about Park, an open platform for learning augmented computer systems, is based on Mao et al. (2019a). See SysML Conference at https://www.sysml.cc.

The discussion about AlphaGo Zero is based on Silver et al. (2017). The discussion about minimum vertex cover, maximum cut, and TSP is based on Dai et al. (2017). The discussion about graph coloring is based on Huang et al. (2019). Kool et al. (2019) study an attention approach for vehicle routing problems. Segler et al. (2018) study chemical syntheses with AlphaGo techniques.## 4 ENERGY

Our mankind is facing issues of sustainable and green energy. It is critical to consume energy efficiently. We discuss data center cooling and smart grid in the following.

4.1 DATA CENTER COOLING

Data centers are widespread in the IT era, esp. after the prevalence of big data and AI. Cooling is essential for data center infrastructure to lower the high temperature and to reduce the amount of heat in order to improve the performance and to mitigate the potential of equipment damage. There are difficulties like unexpected events, safety constraints, limited data, and potentially expensive failures. RL is one approach to data center cooling.

We discuss how to control fan speeds and water flow in air handling units (AHUs) to regulate the airflow and temperature inside server floors, using model-predictive control (MPC). In MPC, the controller (agent) learns a linear model of the data center dynamics with random, safe exploration, with little or no prior knowledge. It then optimizes the cost (reward) of a trajectory based on the predicted model, and generates actions at each step, to mitigate the effect of model error and unexpected disturbances, at the cost of extra computation.

The controls or actions are variables to manipulate, including fan speed to control air flow and valve opening to regulate the amount of water. States refer to the process variables to predict and regulate, including differential air pressure (DP), cold-aisle temperature (CAT), entering air temperature (EAT) to each AHU, leaving air temperature (LAT) from each AHU. There are also system disturbances, referring to events or conditions out of manipulation or control, including, server power usage to surrogate the amount of generated heat, and entering water temperature (EWT) of the chilled water at each AHU. Figure 16 illustrates the data center cooling loop.

Figure 16: Data center cooling loop. (from Lazic et al. (2018))

The method is compared with a local proportional integral derivative (PID) controller and a certainty-equivalent controller, which updates parameters of the dynamics model assuming the estimated model were accurate. Experiments show that the method can achieve data center cooling in a large-scale commercial system in a safe, effective, and cost-efficient way.

4.2 SMART GRID

A smart grid may have many new components, namely, 1) advanced metering infrastructure (AMI), demand response and curtailable loads; 2) flexible power electronics; 3) photovoltaics and solar heating; 4) recharging electronic vehicle; 5) microgrid; 6) energy storage; 7) distributed generation; 8) storm management; 9) massive solar thermal and wind generation facilities; and 10) nanotechnologies.

As shown in Figure 17, the feedback loops for an adaptive stochastic controller for the smart grid takes data from distributed sources as input and optimizes capital asset prioritization, operative & preventive maintenance tasks, and safety & emergency responses simultaneously.

We discuss an approximate dynamic programming or RL formulation for the smart grid. A state variable consists of a physical state, an information state and a belief state. A physical state may```

graph LR Input --> Controller ITI[Indirect Training Information] -.-> Controller Controller -- Action --> Processes Processes -- Actual Outcome --> Critic Critic -- Performance Error --> Model Model -- Prediction Error --> Critic Critic -.-> Model CAP[Capital Asset Prioritization] <--> OM[Operatives & Preventive Maintenance] OM <--> SER[Safety & Emergency Response]

Figure 17: The feedback loops for an adaptive stochastic controller for the smart grid. (from Anderson et al. (2011))

include amount of energy in a battery, status of a diesel generator (on/off), or other physical dimensions of the system. An information state may include current and historical demand, energy availability from wind/solar, etc., and electricity prices. A belief refers to uncertainty in the state of the system, like probability distributions of demand, the reliability of the network, or best prices, etc. A state also includes the exogenous information, which refers to possible changes in demand, and/or supply of energy, as well as network contingencies and emergency failures. Decisions, or actions or controls, include whether to charge or discharge the battery, draw power from the grid or pump power into it, use backup generation, etc. The transition function consists of a set of equations describing the evolving of the system over time, and, given the state and the decision, determines the next state. The objective function governs how we make decisions and evaluates the performance of the designed policies. The goal is to find optimal decisions to minimize some cost or maximize some reward function, and at the same time, maintaining the risk or safety level.

#### 4.3 ANNOTATED BIBLIOGRAPHY

The discussion about data center cooling is based on Lazic et al. (2018). The discussion about smart grid is based on Anderson et al. (2011).---

## 5 FINANCE

Many problems in finance and economics are decision problems with sequential nature, e.g., asset pricing, portfolio optimization, risk management, and RL is a natural solution method. In the following, we discuss case studies for option pricing and order book execution.

### 5.1 OPTION PRICING

Options are important financial instruments, and are ubiquitous in all kinds of financial markets, e.g., equity, fixed income, convertible, commodity, and mortgage. A call option gives the holder the right, not the obligation, to buy an underlying asset, e.g., a share of a stock, by a certain date, i.e., the maturity date, for a certain price, i.e., the strike price. Similarly, a put option gives the holder the right to sell an underlying asset by the maturity date for the strike price. A European style option can be exercised only at the maturity date. An American style option has the flexibility to be exercised at any time up to the maturity date. A challenging problem is to determine the fair price of an option, i.e., option pricing.

To formulate option pricing as an RL problem, we need to define states, actions, and rewards. Here we discuss stock option, and the discussion is general for options with other types of underlying assets. A stock option is contingent on multiple sources of uncertainty, each of which is part of the state, thus the state may be high dimensional. The stock price is a state variable. Financial and economic factors, e.g., interest rates, can be part of the state. An option's price is related to the time, thus time can be part of the state too.

For options, there are two possible actions/strategies: exercise (stop) and continue. When exercising the option, the state action value function is the intrinsic value of the option, which can be calculated exactly. This is the reward for taking the action of exercise. When taking an action of continue, there is no immediate reward, or the reward is 0.

A value-based RL formulation to the option pricing problem then boils down to learning the state action value function for continuation. There are several methods: 1) a least square Monte Carlo (LSM) method to calculate the expected payoff from continuation backwards from the last time step to the first time step; 2) an approximate value iteration method; and 3) a method based on least square policy iteration (LSPI). These methods also provide empirical and theoretical results.

### 5.2 ORDER BOOK EXECUTION

Order book execution is a fundamental trading problem. In limit order markets, we specify not only the desired volumes, but also the desired prices. We discuss a simple form, in which, we need to optimize an execution strategy to trade a certain number of shares of a stock within a certain time horizon.

A state can be composed of private variables as well as market variable. Private variables include the elapsed time and the remaining inventory. Market variables include bid-ask spread, bid-ask volume imbalance, signed transaction volume, and immediate market order cost. Bid-ask spread is the difference between bid and ask prices in the current order books. Bid-ask volume imbalance is the difference of the numbers of shares at the bid and ask, respectively, in the current order books. Signed transaction volume is the difference of the number of shares bought and sold, respectively, in the last 15 seconds. Immediate market order cost is the cost to trade the remaining shares immediately with a market order.

An action is to reposition the limit order for the remaining volume relative to the current ask or bid, so that at any moment, there is a single outstanding order. The cost is the expenditure from a (partial) execution of an order. For normalizing price differences across stocks, performance is measured by the implementation shortfall, which is the difference between the average price paid and the midpoint of the ask bid spread at the start of the trading period. The lower the implementation shortfall, the better.

Experiments are conducted on 1.5 years of millisecond time-scale limit order data for Amazon, Nvidia and Qualcomm stocks from Nasdaq. The results confirm that, 1) for shorter trading periods and higher target volumes, trading cost are higher overall; and 2) the execution policy becomes more---

aggressive, 2.1) when the ask bid spread is large, and 2.2) when the immediate cost of trading the remaining shares is low, a bargaining is available.

### 5.3 ANNOTATED BIBLIOGRAPHY

Hull (2014) provides an introduction to options and other financial derivatives. Simulation based methods like RL or approximate dynamic programming are flexible to deal with complex, high dimensional scenarios.

Longstaff and Schwartz (2001) study the least squares Monte Carlo (LSM) method. It is a standard approach in the finance literature for pricing American options, following approximate dynamic programming. Tsitsiklis and Van Roy (2001) propose an approximate value iteration approach. Li et al. (2009) adapt least square policy iteration (LSPI) in Lagoudakis and Parr (2003) to the problem of American option pricing.

The discussion of order book execution is based on Kearns and Nevmyvaka (2013).

In addition, Bacoyannis et al. (2018) discuss idiosyncrasies and challenges of data driven learning in electronic trading.