FactoredRL: Leveraging Factored Graphs for Deep Reinforcement Learning
Authors: Bharathan Balaji
Petros Christodoulou
Xiaoyu Lu
Byungsoo Jeon
Jordan Bell-Masterson
Venue:  (2021)
Keywords: reinforcement learning
factored mdp
factored rl

Abstract: We propose a simple class of deep reinforcement learning (RL) methods, called FactoredRL, that can leverage factored environment structures to improve the sample efficiency of existing model-based and model-free RL algorithms. In tabular and linear approximation settings, the factored Markov decision process literature has shown exponential improvements in sample efficiency by leveraging factored environment structures. We extend this to deep RL algorithms that use neural networks. For model-based algorithms, we use the factored structure to inform the state transition network architecture and for model-free algorithms we use the factored structure to inform the Q network or the policy network architecture.  We demonstrate that doing this significantly improves sample efficiency in both discrete and continuous state-action space settings.

Under review as a conference paper at ICLR 2021
FACTOREDRL: LEVERAGING FACTORED GRAPHS FOR DEEP REINFORCEMENT LEARNING
Anonymous authors Paper under double-bling review
ABSTRACT
We propose simple class of deep reinforcement learning (RL) methods, called FactoredRL, that can leverage factored environment structures to improve the sample efficiency of existing model-based and model-free RL algorithms. In tabular and linear approximation settings, the factored Markov decision process literature has shown exponential improvements in sample efficiency by leveraging factored environment structures. We extend this to deep RI. algorithms that use neural networks. For model-based algorithms, inform the state transition network architecture and for model-free algorithms we use the factored structure to inform the Q network or the policy network architecture. We demonstrate that doing this significantly improves sample efficiency in both discrete and continuous state-action space settings.
use the factored structure
INTRODUCTION
In many domains, the structure of the Markov Decision Process (MDP) is known the time of problem formulation. For example, in inventory management, we know the structure of the state transition: how inventory flows from a vendor, to warehouse, to a customer (Giannoccaro & Pontrandolfo 2002; Oroojlooyjadid et al.] (017). In portfolio management, we know that a certain asset changes only when the agent buys or sells corresponding item (Jiang et al., 2017). Similar structural information is available in vehicle routing, robotics, computing, and many others. Our work stems from the observation that we can exploit the known structure of a given MDP to learn good policy. We build the Factored MDP literature (Boutilier et al. 1995 Osband & Van Roy 2014 Kearns & Singh 2002] Cui & Khardon 2016). and propose a factored graph to represent known relationships between states, actions and rewards in given problem. We use the factored graphs to inform the structure of the neural networks used in deep reinforcement learning (RL) algorithms improve their sample efficiency. We give literature references and example factor graphs for real
world applications in Appendix A
Consider a motivational example, where the goal of the agent is balance multiple independent cartpoles simultaneously, with each cartpole defined as per OpenAI gym (G. Brockman & Zarembal 2016). The agent can take 'left' 'right' action on each cartpole, and the state includes the position and velocity of each cart and each pole. We refer to this as the Multi-CartPole problem.
Both model-based and model-free algorithms treat the state-action space as a single entity, which makes exploration combinatorially complex. As a consequence, the sample efficiency of RL al- gorithms degrades exponentially with the number of cartpoles, despite the problem remaining conceptually simple for human. By allowing the agent access to the problem's 's factored structure (i.e. each action affects only one cartpole), we bypass the need to learn about each action's relationship with the entire state, and instead only need to learn about each action's 's relationship with its single, related cartpole.
We show how to integrate knowledge of the factored graph into both model-based and model-free deep RL algorithms, and thereby improve sample efficiency. In all cases, we first write down a factored graph as adjaceney matrix, representing the relationships between state, action, and reward. From this adjacency matrix, we then define a Factored Neural Network (Factored NN), which uses input and output masking reflect the structure of the factored graph.

---

Under review as a conference paper at ICLR 2021
Finally, we show how to integrate this Factored NN into existing deep RL algorithms. For model- based, we use the Factored NN to learn decomposed state transitions, and then integrate this state transition model with Monte Carlo Tree Search (MCTS) (Koesis & Szepesvári (006). For model-free. we use the Factored NN to learn a decomposed Q-function, and then integrate with DQN (Maih et al. (013). Also for model-free, we use the Factored NN to learn decomposed policy function, and then integrate with PPO (Schulman et al.) 2017). In all three cases, we demonstrate empirically that these Factored RL methods (Factored MCTS, DQN, and PPO) are able to achieve better sample efficiency than their vanilla implementations, on a range of environments.
2 RELATED WORK
Several methods have been proposed that exploit the structural information of a problem in the Factored MDP literature. Kearns & Koller (199) propose a method to conduct model-based RL
with a Dynamic Bayesian Network (DBN) (Dean & Kanazawa 1989) and learn its parameters
based on an extension of the Explicit Explore or Exploit (E") algorithm (Kearns & Singh 2002).
Guestrin et al. (2003) propose a linear program and dynamic program based algorithm learn linear value functions in Factored MDPs, and extend it to multi-agent settings (Guestrin et al. 2002).
They exploit the context specific and additive structure in Factored MDP that capture the locality of influence of specific states and actions. We use the same structures in our proposed algorithms. Cui & Khardon (2016) propose a symbolic representation of Factored MDPs. Osband & Van Roy (2014) propose posterior sampling and upper confidence bounds based algorithms and prove that they are near-optimal. They show that the sample efficiency of the algorithm scales polynomially with the number of parameters that encode the factored MDP, which may be exponentially smaller than the full state-action space. Xu & Tewari (2020) extend the results to non-episodic settings and Lattimore et al. (2016) show similar results for contextual bandits. The algorithms proposed in these prior works assume tabular (Cui et al.) (2015] Geißer et al.) or linear setting (Guestrin et al. 2003). or require symbolic expressions (Cui Khardon 2016). We extend these ideas to deep RL algorithms by incorporating the structural information in the neural network.
propose a factored DQN algorithm for urban driving applications. Our pro- posed algorithms are similar, but we extend the ideas to model- algorithms like MCTS (Kocsis) & Szepesvári 2006), and model-free on- on-policy algorithms like PPO (Schulman et al. 2017). We also evaluate our algorithms on variety of environments which encompass discrete and continuous state- action spaces. The Factored NN we propose closely related to Graph Neural Networks (Scarselli) eet al.) [2008] Zhou et al. 2018), which are deep learning based methods that operate graph domain and have been applied to domains such as network analysis (Kipl' & Welling 2016), molccule design(Liu al. 2018) and computer vision (Xu et al., 2018). Instead of explicitly embedding the neighbors of all the nodes with neural networks, we use a single neural network with masking.
Li Czarnecki 2019)
NerveNet Wang et al. (2018) addresses the expressiveness of structure in MDP, similar to work. They focus on robotics applications and demonstrate state-action factorization with PPO. In our work, we additionally demonstrate state transition and state-reward factorization in MCTS and DQN respectively. In addition, they propose imposing structure with Graph Neural Networks. In contrast, we propose using input and output masking without modifying the neural architecture.
Working Memory Graphs Loynd et al. (2020) uses Transformer networks for modeling both factored observations and dependencies across time steps. However, they only evaluate their method in grid world with single discrete action. In contrast, we demonstrate our methods on multiple environments and algorithms with factorization in state transition, state-action and state-reward relationships. In addition, our factored network is a simple extension to the existing network used to solve a problem, whereas they impose a complex network architecture.
Action masking has been used effectively to improve RL performance in multiple works (Williams & Zweig 2016: Williams et al. 2017 Vinyals et al.) 2017). We use a similar trick when applying our Factored NN to policy networks in model-free RL. However, we use both an action mask as well as a state mask to incorporate factored structure in policy networks. Our state transition networks for model- based RL also imposes masks both input and output corresponding current state-action and next state respectively. WW et al. (2018) introduce an action dependent baseline in actor-criin critic algorithms, where separate advantage function is learned for each action. Their method also exploits
2

---

Under review as a conference paper at ICLR 2021
structure available in the action space. Our method to incorporate structure is orthogonal, modify the policy network in actor-critic methods.
There is also relationship between work and the emerging intersection of reinforcement learning and causal inference, as factored graphs are are a super-set of causal graphs in the MDP setting. Lu et al. (2018) the backdoor criterion in causal inference and variational autoencoders, ZZhan & Bareinboim (2019) propose a near-optimal algorithm by taking advantage of causal inference in non-Markovian dynamic treatment regimes. Both works assume there exist unobserved confounders in the environment. We instead tackle a different problem where there are no unobserved confounders and show that there are still benefits to leverage structural information.
3 TERMINOLOGY
We briefly describe terminology used in this paper. We use Directed Acyclic Graphs (DAG) to represent relationships between the variables. DAGs consist of nodes and edges where the nodes correspond to random variables X (X1, Xd) and directed edge from variable X; to X, represents that X; has an effect on Xj (X; is also called the parent of Xj). Under Markov conditions, the joint distribution of the variables can be factored as p(X1:a) I ((X](((())))
Consider a general Markov Decision Process (MDP) defined by AS R. Po. 7), where S, denote the state and action space respectively, P denotes the transition probability. R. represents the reward function, Po and 7 represent the initial distribution of the state and discount factor respectively.
In the classic RL setting, one typically assumes each state S depends the entire previous states and actions, i.c.,)(($++.) = [(St [[ (A, ) }. where | denotes the cardinality of the space, and PA denotes the parents of node a bayesian network. However, in many scenarios, one component of the action A may only cause part of the state-space (S MeC,, to change, where C₁ is the index set of the related states of the htth component of the action. In other words, the parents of each state may only be subset of the actions and previous states, i.e., PA(S Simplifying the conditional dependencies helps to construct a more accurate model, enabling us to better decompose the the dynamics and reduce complexity of the learning tasks. We assume the factored structure of the environment does not change over time.
{ (A k J-
FACTORED NEURAL NETWORK
We introduce Factored Neural Networks (Factored NN), a generic method for using knowledge from factored graph to improve neural network predictions. The Factored NN works as follows: start with a factored graph represented as an adjacency matrix that tells us which of our inputs influence which of our outputs. Then, we predict each output one a time while masking all the inputs that irrelevant for the particular output according to our factored graph. We refer to the unmodified neural network as Ordinary NN.
Figure I gives an example. From the factored graph on the left, we observe that output 0₁ only depends on input i,. and output 02 depends on both inputs. An Ordinary NN takes (ii, iz) as input and outputs (01, 02) in one go. The Factored NN instead predicts and o2 separately using knowledge of the factored graph. When predicting 01, masks out in and only considers relevant input 11. When predicting 02, it does not mask any inputs. Then 0₁ and are combined into one vector so that the output form the Factored NN of the same form as with an Ordinary NN, so backpropagation can be done as normal.
Below, we show how to use the Factored NN in both model-based and model-free RI. algorithms, using the same underlying factored structure but varying which elements of (S,A, R) to take as input/output depending on the algorithm. Using the Malti-Cartpole environment as an example, Figure illlustrates how factored graph informs the Factored NN for learning decomposed state transitions, decomposed reward functions, or decomposed policy functions. The following sections discuss the applications of these to MCTS, DQN, and PPO respectively.
The factored structure of an environment has to be manually specified. While this may seem challenging for well established benchmarks, for real life application still need to define the
3

---

Under review as a conference paper at ICLR 2021
(1) Ordinary Neural Network
MN
(0: 02l
Factored Graph
(2) Factored Neural Network
Input
Oulpul
[ol._]
mask
i1
Causal
[2
Graph
mask
(01 Oz]
[1.
NN
L 02)
02
Figure I:
Illustration of Factored NN. Given the factored graph on the left, the Ordinary NN takes all the inputs and produce the corresponding outputs whereas the Factored NN masks out irrelevant input dimensions when predicting each output dimension, concatenating the outputs at the end.
MDP with state, actions and reward. Adding factorization information is relatively easy for domain expert familiar with the details of the problem. Appendix A shows examples factored graphs for few real world applications.
(a) Factored Graph
(b) Factored MCTS
(c) Factored DQN
(d) Factored PPO
x
N
M
R
A
Al
Rish
Ra
Ria
A!
Al
AL
Al
AL
Al
A
AL
Figure (a): Factored Graph for Multi Carti-C with 2 cartpoles. St. AA. R for E {0.1) represent the state vector, action, and reward for each individual cartpole. (b)-(d): Graphical representation Factored NN applications, in MCTS, DQN and PPO respectively. each case, input variables into the Factored NN are in blue and the outputs of the factored NN are in green.
FACTORED MCTS
In model-based RI, environment model uses the current state and chosen actions predict the next state, reward, and whether the episode done or not. The more accurate the environment model, the better can plan and the higher the rewards it can achieve ways of improving the accuracy of environment models are therefore of interest to all model-based RL algorithms.
In order learn environment model predicts next state given current state and action, according to the underlying factored structure of the problem. Taking Multi- Multi-Cartpole with factored graph displayed in Figure 2 as an example, the transition probability can be factored as p($ [St, a.) = I p(st=1ls/ af). where number of cartpoles, st and at represent the state vector and the action taken for the 4tth cartpole. This efficiently reduces the complexity from modeling perspective. The Factored NN takes input (St, ax).
efficiently,
construct a Factored NN that
the
4

---

Under review as a conference paper at ICLR 2021
decomposes accordingly and returns 81+1 output. Figure 2b gives graphical representation of Factored MCTS.
We can fold this Factored NN into model-basee RL algorithms anywhere model. this work, we demonstrate using Monte Carlo Tree Search (MCTS) (Koesis & Szepesvári 2006) with a learned model. We implement MCTS by iterating between: 1) learning the parameters of the environment model with a gradient- based approach from existing observations; and 2) acting in the world by rolling out samples from the environment model and picking the best action using tree search.
environment
6 FACTORED DQN
Model-free algorithms do not use an environment model, but rather directly learn a Q-value or policy. We still a Factored NN to obtain better sample efficiency, simply by specifying the relevant parts of (S, A, R) as input/output.
In the of DQN, need learn Q-value given the current state and action and update it with: Q(st. - Q(s,, az) + a [(s,, at) + Y max Q(st, a') Q(s;, a:)]
(1)
When the state and action space is high-dimensional, estimating Q-value becomes computationally expensive. Adhering to the underlying factored structure, we can decompose the Q-value with Factored NN. Taking Multi-Cartpole
illustrating example, the total reward is the summation of the individual rewards: R(s,, a²) = Σ R(s ).), where R(s, a) is the reward function. We can break down the Q-value in the same way as the factored structure does not change across the episode: Q(s az) == Q(s )²). The Factored NN takes the state-action pair (St, a²) as the input, decomposes into individual state-action pair (s/ af) for each cartpole, predicts individual Q-value Q(s at) and combines them into the final (s:, ax) which can then be updated with (1).
Figure 2c gives illustration of Factored DQN.
FACTORED PPO
Finally, we can also integrate the Factored NN into model-free algorithms that directly do policy optimization. this work, we show how to do this with PPO (Schulman et al. 2017). an actor-critic algorithm where a policy network determines the action based on the state, and a value network predicts the episode return from the current state.
The policy network π (s) directly optimizes the best action a, given the current state St. The factored structure can be used to reduce the complexity of a problem by decomposing the conditional distribution <aa,|s) accordingly. We then apply the Factored NN to the policy network, by mapping only the structurally related states to the actions. the Multi-Cartpole example, π (ayls:)) = I (aa (s{). Factored NN takes the entire state 8; input, decomposes into each individual state sf and predicts its corresponding action at for each cartpole k. See Figure 2d for illustration.
8 EXPERIMENTS
We show experimental results for Factored MCTS, DQN, and PPO on a variety of simulation environments. In all experiments, we first define factored graph representing the relationships among given problem's 's (S.A, R), then leverage that graph in Factored NN to learn policy with either MCTS, DQN, or PPO. The results below compare these FactoredRL algorithms with their vanilla counterparts. All experiments use the same hyper-parameters for Factored NN and Ordinary NN, they are reported Appendix Each experiment run on 5 different seeds.
FACTORED MCTS EXPERIMENTS
We experiment with Factored MCTS two environments: Multi Calti-Cartpple and Taxi. We chose these environments because we can easily decompose their state transitions, and they involve discrete actions which MCTS requires.
5

---

Under review as a conference paper at ICLR 2021
Multi-Cartpole Experiments: We first test using Factored NN with MCTS the Multi-Cartpan environment. In this environment, the agent balances multiple independent cartpoles at once, where a single cartpole is defined as per OpenAl gym (G. Brockman & Zaremba, 2016].
The state size is 4 multiplied by the number of cartpoles, as each cartpole has a state of size representing its position, velocity and angle. The action taken by the agent is binary vector representing the direction of force applied to each cartpole. The reward given to the agent the sum of rewards for each cartpole, receiving 1/(Number of Cartpoles) if a cartpole is upright, and 0 if not.
The factored structure for this environment that we leverage in the Factored NN is that the state transitions for each cartpole are independent.
The results are displayed in Figure Sa and For both cases we consider, i.e. 4, and 8 cartpoles, incorporating the factored structure into the problem via the Factored NN leads superior model prediction error and environment reward. In terms of sample efficiency, we find that Factored NN achieves the final score of the Ordinary NN in 25% and 10% of the time for 4 and cartpoles respectively.
MCTS: Multi Cartpole (4 cartpoles)
METS: Multi Caripole (8 cartpoles
MCTS: Text
5.036
MCTS
MCTS
0.01
NCTS
5.030
0.02
Factored
8.012
0.03
Pediciion
2.030
Brodiction
0
Prediction
0.02
0.006
0.01
3000
2000 Timestep
2000
4002
0.002
20002
40003
62003 02000
0.00
550
1200
2500
2000
Timestep
Timestep
125-
MCTS Factored MCTS
3.0
Episode Reward
202
Factored MCTS
35-
Episode Reward
102
0.0
Episodie
60-
-0.5
20
-1.0
Factored MCTS
3000
2000 Timestep
3000
4000
20020 40000 500O0 B0020
1300
2000
Timestep
Timestep
(a)
(b)
(c)
Figure 3: Environment model prediction loss (first row) and game score (second row) for each the environments. Columns a and represent environments with and 8 cartpoles respectively. Column shows the results for the Taxi environment. The solid lines show the average over 5 random seeds and the shaded area shows + standard deviation.
Taxi Experiments: We also Factored MCTS ment (G. Brockman & Zarembal 2016). In this environment there is a taxi and passenger, and the goal is for the taxi to pick up the passenger and drop him off at a specified location. S
simplified version of the Taxi environ-
The state is given by the location of the taxi, the passenger, and the target location. The action taken by the agent is discrete action to move up, down, left, right, or to pick up or drop off the passenger. A positive reward is given if the agent drops off the passenger in the correct location; a negative reward is given every timestep and if the taxi tries to dropoff or pickup a passenger illegally.
The factored structure for this environment that we leverage in the Factored NN is that the destination never changes and the location of the taxi and passenger only depends on a subset of actions.
The results are displayed in Figure 3c As with the Multi-Cartpole experiments, incorporating the factored structure into the problem via the Factored NN leads to superior model prediction error and environment reward. In terms of sample efficiency, we find that Factored NN achieves the final score of the Ordinary NN in 60% of the time.
'To make the environment solvable in reasonable amount of time using MCTS, we simplified the problem slightly by having the taxi always begin with the customer onboard and within certain distance of its destination.

---

Under review as a conference paper at ICLR 2021
8.2 FACTORED DQN EXPERIMENTS
We experiment with Factored DQN on two environments: Bitflip, and Multi-Cartpole. We chose these environments because factored structure in these two environments allow decompose Q-values (which we cannot do in the Taxi environment). and DQN requires discrete actions.
BitFlip Experiments: Our BitFlip problem formulation is inspired from the example introduced by Andrychowicz et al. (2017) In this environment, the agent tries to flip bits (0 or 1) in vector to match the values of a target vector of bits.
The state is given by two sets of n. bits, where one set consists of current n bits and another set consists of n target bits (2n state). The action taken by the agent each timestep discrete binary vector a of size n where a; 0, 1 means no flip and flip on the i-th current bit (2" possible actions). for each flipped bit and a positive reward of 2 for each flipped bit matched to target bit. This environment is episodic and it ends if it reaches the maximum number of time steps (= 3n) or current bits are same as target bits.
The reward given to the agent
Factored NN uses the independence of the reward corresponding to each bit to estimate the respective Q-value of each bit flip. The final Q value is the sum of Q-values for each bit. Note that only sum of independent rewards are available during training time, which differentiates the problem from solving each sub- problero independently.
The results displayed in Figure 4a For all cases consider, i.e., 2, 4, and 8 bits, incorporating the factored structure into the problem via the Factored NN leads to superior environment reward. In terms of sample efficiency, Factored NN achieves the asymptotic performance of the ordinary NN in 10% of the time in the bit case. The results for 2 and 4 bits are presented in Appendix [
Multi-Cartpole Cartpole Experiments: We also test Factored DQN the Multi-Cartpil environment, with the same problem statement described in Section 8.1 Factored NN leverages the information that the reward for cartpole independent from other cartpoles. Again, note that only sum of independent rewards are available during training time.
The results are displayed in Figure 4b and 4c| for environments with 4 and 8 cartpoles, respectively. Factored DQN is superior in terms of mean episodic rewards. The performance gap is bigger when as we increase the number of cartpoles because the number of outputs of the Q-function grows exponentially. Factored NN reduces the complexity by estimating the Q-value of each cartpole independently. terms of sample efficiency, Factored NN achieves asymptotic performance within 300000 timesteps while NN suffers from high-dimensional state-action pairs and does not improve its performance within million timesteps.
DQN: Bitflip (8 bits)
DON: Multi Cartpole (4 cartpoles)
DON: Multi Cartpale (8 caripoles)
200
Ep-sade Reward
6-
sode Reward
Episade Reward
DQN
DQN FactoredDON
100
DaN
100
DoN
1000000
100000 Timestep
200000
100000 Timestep
200000
Timestep
(a)
(b)
(c)
Figure 4: DQN with Factored NN vs. NN performance on Bitflip (a) and Multi-Cartpole (b, c). The solid lines show the average over 5 random seeds and the shaded area shows + standard deviation.
8.3 FACTORED PPO EXPERIMENTS
We experiment with Factored PPO on five environments: Bittlip, Multi Calti-Cartpole, Half-Cheetah, Ant, and Humanoid. We chose these environments to evaluate both discrete and continuous state-action spaces. We do not evaluate on Taxi because it has only one set of actions that are not separable by factored structure of a policy network.
Bitflip & Multi-Cartpole Experiments: We first test using a Factored NN with PPO on the Bitflip and Multi-Cartpon environments. These have the same setup described in Sections 8.1 and 8.2
7

---

Under review as a conference paper at ICLR 2021
For BitFlip, map the action of flipping bit to the state of the corresponding bit, the rest of the state is masked out. For Multi-Cartpole, we map the action of controlling each cartpole with the state of the corresponding cartpole, masking out the state of other cartpoles.
We show a subset the results in Figure []] and the rest are given in Appendix For both environ- ments, Factored PPO outperforms its vanilla implementation with respect to environment reward over the training period. In terms of sample efficiency, Factored NN achieves the final score of the Ordinary NN in 46% of the time for BitFlip with 8 bits; in 32% and 22% of the time for 4 and cartpoles respectively.
We also test Factored PPO three continuous control roboties envi- ronments: Ant, Half-Cheetah, and Humanoid with horizon of 1000 steps, as defined in PyBul- let (Coumans& Bai 2016 In these environments, the agent controls the robot joints, and its goal is to walk upright.
Robotics Experiments:
The state for each of these environments is slightly different, but in general state consists of joint angle and angular velocity as well as global state such as robot position and contact force with the ground. The action taken by the agent controls each joint torque. HalfCheetah, Ant and Humanoid have 6, 8 and 17 joints respectively. The reward given to the agent is positive if the robot is upright and moving. There negative reward for using electricity and if the robot falls or tangles its legs. The Factored NN leverages the structure that the state of each robot joint maps only to the respective joint actions.
The results are displayed in Figure 6 which shows the training curves for the baseline PPO and Factored PPO. In terms of sample efficiency, Factored PPO reaches the final episode reward of baseline PPO in 35%, 61% and 64% of the time for HalfCheetah, Ant and Humanoid respectively. We observe similar results when we remove the critic in PPO, and report detailed results in Appendix
19': Bithlip (8 bit))
PPO: MultiCCrrPPPic cartooll)))
PPO: MultiCarrPPlle (8 cartpolos)
Reward
150
225
102
200
75
PPO
PPO Factored
Factonal
Factored PPO
100000
Timestep
0.
05 Timestep
1.0
(a)
(b)
(c)
Figure 5: PPO with Factored NN vs. Ordinary NN performance on multi BitFlip with 8 bits @ and c cartpoles. The solid lines show the average over 5 random seeds and the shaded area shows + standard deviation.
4
b
PPO: Half-Chestah
PPO: Humanaid
1300
Epterde Reward
200
$20-
600-
400
500
PPO
PPO Factored PPO
-2000-
Factored PPO
400
Factared PRO
Timestep
39
Timestep
107
Timestep
(a)
(b)
(c)
Figure 6: PPO with Factored NN vs. Ordinary NN performance on Half Cheetah (a). Ant (b). and Humanoid ( The solid lines show the average over random seeds and the shaded area shows + 1 standard deviation.
The open source PyBullet environments are slightly different from the MuJoCo counterparts the converged episode rewards differ. PyBullet emulates physies accurately, and is as challenging solve as MuloCo.
8

---

Under review as a conference paper at ICLR 2021
9 CONCLUSION AND FUTURE WORK
We demonstrate how to exploit factored structural knowledge in both model-based and model-free RL. We leverage this factored structure through a Factored Neural Network (Factored NN), which uses input and output masking to reflect the factored graph. In model-based RL, we show how to use Factored NN to learn state transition model, which can then be integrated into algorithms like MCTS. In model-free RL, we show how to use a Factored NN to learn a factored Q function which can be integrated into DQN, and we also show how to a Factored NN learn factored policy function for use in PPO. Our method can be easily generalized to other model-based and model- free algorithms with the same idea. We have tested our FactoredRL approach on both continuous and discrete state-action spaces including bitflip, cartpole, taxi, and robotics environments, which show improved sample efficiency relative to vanilla algorithms.
The contribution of this work is in tying together factored graphs and deep reinforcement learning, showing that factored structure can improve the performance of RL algorithms. The theoretical properties of Factored NN, scalability to high dimensional inputs such as images, and alternative methods for incorporating factored structure into RL are interesting directions of future work. Critically, in this work we take given access ante. In many environments, doing so is either time consuming, inaccurate, or outright infeasible. In future work, will focus factored graph discovery in online, RL settings, where the agent's actions affect the distribution of data and therefore the quality of the learned graph.
accurate factored graph, specified manually ex
REFERENCES
Marein Andrychowicz, Filip Wolski, Alex Ray, Jonas Schneider, Rachel Fong, Peter Welinder, Bob McGrew, Josh Tobin, OpenAl Pieter Abbeel, and Wojeiech Zaremba. Hindsight experience replay. In Advances in neural information processing systems, pp. 5048-5058, 2017.
Bharathan Balaji, Jordan Bell-Masterson, Enes Bilgin, Andreas Damianou, Pablo Moreno Garcia, Arpit Jain, Runfei Luo, Alvaro Maggiar, Balakrishnan Narayanaswamy, and Chun Ye. Orl: Reinforcement learning benchmarks for online stochastic optimization problems. arXiv preprint 1rXiv:1911.10641 2019.
Jonathan Bassen, Bharathan Balaji, Michael Schaarschmidt, Candace Thille Jay Painter, Dawn Zimmaro, Alex Games, Ethan Fast, and John C Mitchell. Reinforcement learning for the adaptive scheduling of educational activities. In Proceedings of the 2020 CHI Conference on Human Factors in Computing Systems, pp. 1-12. 2020.
Craig Boutilier, Richard Dearden, Moises Goldszmidt, et al. Exploiting structure in policy construc- tion. In IJCAI, volume 14, pp. 110--111,, 1995.
Sandeep Chinchali, Pan Hu, Tianshu Chu, Manu Sharma, Manu Bansal, Rakesh Misra, Marco Pavone, and Sachin Katti. Cellular network traffic scheduling with deep reinforcement learning. In AAAI, pp. 766-774, 2018.
Erwin Coumans and Yunfei Bai. Pybullet, a python module for physics simulation for games, robotics and machine learning. GitHub repository, 2016.
Janos Csirik, David S Johnson, Claire Kenyon, James B Orlin, Peter W Shor, and Richard R Weber. On the sum-of-squares algorithm for bin packing. Journal of the ACM (JACM), 53(1):1-65, 2006.
Hao Cui and Roni Khardon. Online symbolic gradient-based based optimization for factored action mdps. In IJCAI, pp. 3075-3081, 2016.
Hao Cui, Roni Khardon, Alan Fern, and Prasad Tadepalli. Factored mets for large scale stochastic planning. In Twenty-Ninth AAAI Conference Artificial Intelligence, 2015.
Thomas Dean and Keiji Kanazawa, A model for reasoning about persistence and causation. Compu- tational intelligence, 12-):142-150, 1989.
Francesco Fraternali, Bharathan Balaji. Dhiman Sengupta, Dezhi Hong. and Rajesh K Gupta. Ember: energy management of batteryless event detection sensors with deep reinforcement learning. In Proceedings of the 18th Conference Embedded Networked Sensor Systems, pp. 503-516, 2020.

---

Under review as a conference paper at ICLR 2021
L. Pettersson J. Schneider J. Schulman J. Tang G. Brockman, V. Cheung and W. Zaremba. Openai gym. 2016.
Florian Geißer, David Speck, and Thomas Keller. Trial-based heuristic tree search for mdps with factored action spaces.
Ilaria Giannoccaro and Pierpaolo Pontrandolfo. Inventory management in supply chains: a rein- forcement learning approach. International Journal of Production Economics, 18(2)1553-61, 2002.
Joren Gijsbrechts, Robert N Boute, Jan A Van Mieghem, and Dennis Zhang. Can deep reinforcement learning improve inventory management? performance on dual sourcing. lost sales and multi- echelon problems. Performance Dual Sourcing, Lost Sales and Mulli-Echelon Problems (July 29, 2019), 2019.
Carlos Guestrin, Daphne Koller, and Ronald Parr. Multiagent planning with factored mdps. In Advances in neural information processing systems, pp. 1523-1530, 2002.
Carlos Guestrin, Daphne Koller, Ronald Parr, and Shobha Venkataraman. Efficient solution algorithms for factored mdps. Journal of Artificial Intelligence Research, 19:399-466 2003.
Varun Gupta and Ana Radovanovic. Online stochastic bin packing. arXiv preprint 2012.
Tuomas Haarnoja, Aurick Zhou, Pieter Abbeel, and Sergey Levine. Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with a stochastic actor. International Conference Machine Learning, pp. 1861-1870, 2018.
Victoria Hodge, Richard Hawkins, and Rob Alexander. Deep reinforcement learning for drone navigation using sensor data. Neural Computing and Applications, pp. 1 1-19, 2020.
Zhengyao Jiang, Dixing Xu, and Jinjun Liang. A deep reinforcement learning framework for the financial portfolio management problem. arXiv preprint a70i. /0059, 2017.
Michael Kearns and Daphne Koller. Efficient Efficientreinforcomm reinforcement learning in factored mdps. In Proceedings of the 16th International Joint Conference on Artificial Intelligence Volume 2, IJCAI'99 pp. 740-747, San Francisco, CA, USA, 1999. Morgan Kaufmann Publishers Inc.
Michael Kearns and Satinder Singh. Near-optimal reinforcement learning in polynomial time. Machine learning, (9(2-3)2209 2022-2232,-2 2002.
Thomas Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. arXiv preprint ar 1609 02907, 2016.
Levente Kocsis and Csaba Szepesvári. Bandit based monte-carlo planning, In European conference on machine learning, pp. 282-293. Springer, 2006.
Finnian Lattimore, Tor Lattimore, and Mark D Reid. Causal bandits: Learning good interventions via causal inference. In Advances in Neural Information Processing Systems. pp. 1181-1189 2016.
Changjian Li and Krzysztof Czarnecki. Urban driving with multi-objective deep reinforcement learn- ing. In Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems, pp. 359-367 International Foundation for Autonomous Agents and Multiagent Systems, 2019.
Eric Liang Richard Liaw, Robert Nishihara, Philipp Moritz, Roy Fox, Ken Goldberg, Joseph Gonzalez, Michael Jordan, and Ion Stoica. Rllib: Abstractions for distributed reinforcement learning. International Conference on Machine Learning, pp. 3053-3062, 2018.
Qi Liu, Miltiadis Allamanis, Mare Brockschmidt,, and Alexander Gaunt. Constrained graph variational autoencoders for molecule design. In Advances in neural information processing systems, pp. 7795-7804, 2018.
Ricky Loynd, Roland Fernandez, Asli Celikyilmaz, Adith Swaminathan, and Matthew Hausknecht. Working memory graphs. In ICML. 2020, July 2020.
10

---

Under review as a conference paper at ICLR 2021
Chaochao Lu, Bernhard Schölkopf. and José Miguel Hemándee--Lbbao Deconfounding reinforce- ment learning in observational settings. arXiv preprint arXiv: 181.11111.. 2018.
Hongzi Mao, Parimarjan Negi, Akshay Narayan, Hanrui Wang, Jiacheng Yang. Haonan Wang, Ryan Marcus, Mehrdad Khani Shirkoohi, Songtao He, Vikram Nathan, et al. Park: An open platform for learning-augmented computer systems. Advances in Neural Information Processing Systems, 32: 2494-2506, 2019.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Mare G Bellemare, Alex Graves, Martin Riedmiller, Andreas Fidjeland, Georg Ostrovski, al. Human-level control through deep reinforcement learning. Nature, 518(7540):529-555 533, 2015.
Afshin Oroojlooyjadid, MohammadReza Nazari, Lawrence Snyder, and Martin Takáč. A deep q- network for the beer game: A deep reinforcement learning algorithm to solve inventory optimization problems. arXiv preprint arXiv: 000.//088.00959 2017.
lan Osband and Benjamin Van Roy. Near-optimal reinforcement learning in factored mdps. In Advances in Neural Information Processing Systems, pp. 604-6122 2014.
Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. IEEE Trunsactions Neural Networks, 20(1):61-80 2008
John Schulman, Philipp Moritz, Sergey Levine, Michael Jordan, and Pieter Abbeel. High-dimensional continuous control using generalized advantage estimation. arXiv preprint urXiv:1506.1 02438, 2015.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint 177.v:1707.06347, 2017.
Nazneen N Sultana, Hardik Meisheri, Vinita Baniwal, Somjit Nath, Balaraman Ravindran, and Harshad Khadilkar. Reinforcement learning for multi-product multi-node inventory management in supply chains. arXiv preprint Xii::2006.040377, 2020.
Oriol Vinyals, Timo Ewalds, Sergey Bartunov, Petko Georgiev, Alexander Sasha Vezhnevets, Michelle Yeo, Alireza Makhzani, Heinrich Küttler, John Agapiou, Julian Schrittwieser, al. Starcraft ii: new challenge for reinforcement learning. arXiv preprint arXiv: 178.0077, 2017.
Tingwu Wang, Renjie Liao, Jimmy Ba, and Sanja Fidler. Nervenet: Learning structured policy with graph neural networks. In International Conference on Learning Representations, 2018.
Tianshu Wei, Yanzhi Wang. and Qi Zhu. Deep reinforcement learning for building hvac control. In Proceedings of the 54th Annual Design Automation Conference 2017, pp. 1-6, 2017.
Jason D Williams and Geoffrey Zweig. End-to-end Istm-based dialog control optimized with supervised and reinforcement learning. arXiv preprint 1606. 2016.
Jason D Williams, Kavosh Asadi, and Geoffrey Zweig. Hybrid code networks: practical and efficient end-to-end dialog control with supervised and reinforcement learning. arXiv preprint arXiv:1702.03274. 2017.
Cathy Wu, Aboudy Kreidich, Kanaad Parvate, Eugene Vinitsky, and Alexandre M Bayen. Flow: Architecture and benchmarking for reinforcement learning in traffic control. arXiv preprint 17X.0:1710.05665 pp. 10, 2017.
Cathy Wu, Aravind Rajeswaran, Yan Duan, Vikash Kumar, Alexandre M Bayen, Sham Kakade, Igor Mordatch, and Pieter Abbeel. Variance reduction for policy gradient with action-dependent factorized baselines. arXiv preprint MrXXiv1803.072444 2018.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? arXiv preprint arXiv:1810.00826 2018.
Ziping Xu and Ambuj Tewari. Near-optimal reinforcement learning in factored mdps: Oracle-efficient algorithms for the non-episodic setting. arXiv preprint 0200:2000..2202.... 2020.
11

---

Under review as a conference paper at ICLR 2021
Yunan Ye, Hengzhi Pei. Boxin Wang. Pin- Yu Chen, Yada Zhu, Ju Xiao, and Bo Li. Reinforcement- learning based portfolio management with augmented asset movement prediction states. In Proceedings of the AAAI Conference Artificial Intelligence, volume 34, pp. 11 1112-1119, 2020.
Liang Yu, Yi Sun, Zhanbo Xu, Chao Shen, Dong Yue, Tao Jiang, and Xiaohong Guan. Multi-agent deep reinforcement learning for hvac control in commercial buildings. IEEE Transactions on Smart Grid, 2020.
Junzhe Zhang and Elias Bareinboim. Near-optimal reinforcement learning in dynamic treatment regimes. In Advances in Neural Information Processing Systems, pp. 13401-13411, 2019.
Jie Zhou, Ganqu Cui, Zhengyan Zhang. Cheng Yang, Zhiyuan Liu, Lifeng Wang, Changcheng Li, and Maosong Sun, Graph neural networks: A review of methods and applications. arXiv preprint 1812.04812 2018.
Paul Zipkin. Old and new methods for lost-sales inventory systems. Operations Research, 56(5): 1256-12633 2008.
12

---

Under review as a conference paper at ICLR 2021
APPENDIX
A EXAMPLES OF FACTORED GRAPHS IN REAL WORLD APPLICATIONS
There are many real world RL applications where we can leverage the knowledge of factored graph. Application domains include supply chain (Sultana et al. 2020), portfolio management (Ye et al. 2020p, industrial control (Wei et al. 2017). robotics (Haarnoja et al. 2018), cellular networks (Chin chali et al. 2018), online education [Bassnn et al. 2020), Internet of Things (Fraternali et al. 2020 and many more (Wu et al.) 2017 Mao et al. 2019). Below include few examples of RL applications where we can employ our lactored RL approach.
A.1 OPERATIONS RESEARCH
Many problems in operations research, and especially supply chain, are natural environments for the use of factored graphs. This is because the historical dominant techniques, Linear and Dynamic Programming, require us to articulate problem structure in the form of model to be solved, and this problem structure can easily be expressed in factored graphs as well. Two canonical problems with wide-ranging industrial applications can demonstrate this. First, there is the Bin Packing problem (Csirik et al. 2006 Gupta & Radovanovic 2012 Balaji et al. 2019). which has industrial counterparts in truck packing and virtual machine packing, among others. In RL formulation, the state is given by the amount filled in each bin, the dimensions of a new item to be packed, and the action is to place the new item in one of the bins, with reward function for minimizing waste. The factored graph structure is key in this problem in the following way: The state of each bin in timestep t+1 is a function only of the same bin timestep t, and the action time t, meaning that RL can ignore spurious relationships between bin levels in predicting the state transition. Figure 7 depicts the factored graph.
Binpacking Factored Graph
I-1
ta Level Riz
1ot Bin Level figtt
Ron-
Fbex n te tae Ai
Flace in le TB Assi
and
Znc Bras
mermiore
8
Figure 7: Bin Packing Factored Graph
Second, there the Newsvendor problem Balaji et al. 2019 Zipkin 2008 Gijsbrechts et al. 2019);
which has common industrial counterpart purchase ordering decisions (e.g. from retailer to a vendor). an RL formulation, the state is given by the economic parameters of the item to be ordered, the inventory on-hand, and the inventory to-arrive from the vendor in timesteps t+1, 1+2, etc.,
13

---

Under review as a conference paper at ICLR 2021
the action is how much of the item to order, and the reward is function of inventory on-hand and customer demand. The factored graph structure this problem especially helpful for simplifying the dynamics of the inventory to-arrive, since this is linear pipeline from the vendor to the agent, i.c. the inventory that will arrive at t+ is the same as inventory in the previous period that will arrive at 1+2. Figure depicts the factored graph.
Newsvendor Factored Graph
1+1
Customer Demand Sot
Customer Demand Sp-1
Inventory Onhand
Inventory Onhand Sturt
Inventory Artive Sz1
Inventory 8ygn
Invantory Arrive in i+2 Sgi
Inventory To Arrive in i+2 Sg-1
Quaniity to Buy Vendar
Figure 8: Newsvendor Factored Graph
A.2 ROBOTICS
In robotics, the state may be high- nigh-dimensional, but the subspaces of the state may evolve independently of others, and only depend on low dimensional subspace the previous state. We have included examples of Ant, Half- Half-Cheetah, and Humanoid in the paper with factor graph given in appendix A.4, where the transition dynamics transition dynamics of its legs, similar example, we can use factored graphs for drone control with deep RL (Hodge et al. 2020).
robot's arms may be reasonably assumed to independent the
A.3 INDUSTRIAL. CONTROL
It is common in industrial control to have several components that work together to accomplish goal. For example HVAC (short for heating, ventilation and air conditioning) control, the building divided into zones each of which is controlled by set of damper, fan and heating element (Yu et al. 2020). All the zones need to work concert with a central air handler unit that supplies cold The state in this problem is the temperature of individual zones, the supply air temperature and weather conditions. The action is to set the controls of each zone. The reward is to ensure thermal comfort with minimal energy use. A state-action factored graph can be used inform the RL agent that
14

---

Under review as a conference paper at ICLR 2021
Drone Control Factored Graph
Motor Speed. PID Canfi
Motor Speed, PID Donigg Sqpt
Exntrol Sipeed Azt
Cantrdl Mf Ar--1
Mutter Speed PID Canfa
Molor Speed, PID Stprt
Spreec
Cantrdl Spuned
Drone Coonds, Assudo Sig
Drane Coorcs, Atlude 83st
Figure 9: Drone Control Factored Graph
control of each zone independent of each other. The reward function also be factorized the thermal comfort in each zone is measured independently. Figure 1O depicts the factored graph.
HVAC Factored Graph
I+
Theparstur
Samperkon San
AW
Tres 1-B0C Contril Aot
Para 1UAC Centri AXH1
Zona 2
Ztea San
Figure 10: HVAC Control Factored Graph
15

---

Under review as a conference paper at ICLR 2021
A.4 PORTFOLIO MANAGEMENT
These problems (e.g. Ye et al. 2020 generally have states of the form [stock of asset A, stock of asset ...] and action spaces of the form [buy/sell of asset A, buy/sell of asset B, ...... In this scenario we have important prior knowledge about the factor graph, for example we know that the sub-action of buying/selling asset will not influence the sub-state stock of asset B. The method would allow us to incorporate this prior knowledge into our RL Agent and improve performance. Figure [] depicts the factored graph.
Portfolio Management Factored Graph
I
Blook
Btuck Forr
Sel Aasot Arevs
Appet &
Asset B Rort
Reat
Bay or
Duy o
Figure 11: Portfolio Management Factored Graph
B FACTORED GRAPHS OF ENVIRONMENTS USED IN EVALUATION
B.I CULTIPLE-CARTTOLL
Let pl. of and ff represent the position, velocity and angle for cart at time and let A;, R; represent the force and reward for cart time then the factored graph for this environment can be resepented by
B.2 BITFLIP
Define St to be the bit at position at time I, define A to be the action of whether to flip the i-th bit time i and let Ri represents whether the i-th bit equals to the i-th bit of the target bits. Then the factored graph for this environment can be resepented by
B.3 TAXI
Define plari plest. .p. to be the location of the taxi, target destination and passenger at time t respectively, let at amnoue, qiok ag dropping off passengers at time t. Then the factored graph for this environment can be resepented by
drop to be the action of moving (up, down, left, right), picking up and
B.4 ROBOTICS
Define galobal to be the global features of the robot (e.g., position, contact force) and define si to be the state of joint at time The action for each joint is denoted by af. Here show only 3 actions
16

---

Under review as a conference paper at ICLR 2021
be Maea c--1
Cartpole 0
i si 091
AM
A245
Re+3
beyy the 6
Cartpole
(o] sf. ej]
R
A
A
x+1
Bit
stya
44
AV
Ri+1
St
R
Ai
A
(+1
apoore
pdeat
for simplicity, the graph scales similarly as we add more joints (e.g. 17 joints for the humanoid case). The factored graph for this environment can be represented by
17

---

Under review as a conference paper at ICLR 2021
4
of
+
at
of
C
HYPERPARAMETERS
Below we provide the hyperparameters used for each experiment.
Table I: Hyperparameters used for Factored MCTS Cart Pole experiments
Hyperparameter
Value
MCTS rollouts
50 (for and replicas), 200 (for 8 replicas)
Gamma
0.9
UCB Constant
6.4
Batch size
64
Learning rate
0.0005
Horizon
2
Warm up steps
100
Hidden layers
[100, 100]
Hidden layers
1000000
Table 2: Hyperparameters used for Factored MCTS Taxi experiments
Hyperparameter
Value
MCTS rollouts
200
Gamma
0.9
UCB Constant
6.4
Batch size
16
Learning rate
0.0005
Horizon
5
Warm steps
10000
Hidden layers
[100, 100]
Hidden layers
1000000
For PPO, we used the Ray RLlib library Liang et al. (0018). We use the default hyper-pane parameters in
the library unless specified below. We use the parer-par variable names as used in the library for ease of replicability. If some of the hyper-parameter names are unclear, please refer to the RLlib documentation for details.
18

---

Under review as a conference paper at ICLR 2021
Table 3: Hyperparameters used for Factored DQN experiments
Hyperparameter
Value (Bitllip / Multi-Carrpoll)
Gamma
0.99
Horizon
3n (n: # of bits) / 200
Train batch size
128
Learning rate
0.001
Initial epsilon
0.3
Target epsilon
0.05 0.2
Target network update frequency
10 timesteps
Max time steps
20000
Hidden layers
(64, 64, 64]
Table 4: Hyperparameters used for Half-Cheetal Factored PPO experiments. We tuned the hyper- parameters ensure convergence and improve sample efficiency.
Hyperparameter
Value
gamma
0.99
horizon
1000
kl <l_cefff
1.0
num sgd iter
32
agd_minibbtehh _izee
1024
train batch size
16384
Learning rate
0.0003
Hidden layers
[256,
256]
GAE
True
loss loss__coefff
0.5
grad_elip
0.5
clip_param param
0.2
Table 5: Hyperparameters used for Humanoid Factored PPO experiments.
Hyperparameter
Value
gamma
0.995
horizon
1000
kl_coeff
1.0
sgd iter
20
sgd_
ses_mmnnbbtchhssie
1000
train_batch size
25000
Learning rate 0.0005
Hidden layers [256, 256]
lambda 0.95
clip
clip_param param 0.2
GAE
True
19

---

Under review as a conference paper at ICLR 2021
Table 6: Hyperparameters used for Ant Factored PPO experiments.
Hyperparameter
Value
gamma
0.995
horizon
1000
kl_coeff
1.0
num num_sgd sgd iter
20
sgd minibatch size
8192
train train_batchh size
40000
Learning rate
0.0001
Hidden layers
[256, 256]
clip_param
0.2
GAE
True
observation filter
MeanStdFilter
Table 7: Hyperparameters used for Humanoid Factored PPO experiments.
Hyperparameter
Value
gamma
0.995
horizon
1000
coeef
1.0
sgd num__gd
num
iter
20
sgd mwnibatch size
1024
10000
Learning rate
0.0001
Hidden layers
[256, 256]
lambda
0.95
clip_param
0.2
GAE
True
clip_ dip_actions
True
normalize actions
True
Table 8: Hyperparameters used for Multi-Cartpole (8 cartpoles) Factored PPO experiments.
Hyperparameter
Value
gamma
0.995
horizon
1000
kl_coeff
1.0
num num_sgd _iter
5
@ed_mmnibatch_sse
1000
train_batch, size
25000
Learning rate
0.0005
Max episode steps
1000
Hidden layers
[256,
256]
GAE
True
20

---

Under review as a conference paper at ICLR 2021
Table 9: Hyperparameters used for rest of the Factored PPO experiments, including robotics experi- ments which exclude GAE.
Hyperparameter
Value
gamma
0.995
horizon
1000
kl coeeef
1.0
num_sgd iter
20
_ed__minibach____ _ize
1000
train_batch_s size
25000
Learning rate
0.0005
Max episode steps
1000
Hidden layers
[256, 256]
21

---

Under review as a conference paper at ICLR 2021
D ADDITIONAL DQN EXPERIMENTS
We compared Factored DQN with DQN on the BitFlip and Multi-Cartpole environments across various number of bits and cartpoles. We find that the Factored DQN consistently outperforms DQN and the performance gap is larger when the environment is harder.
DON: Bitflip bits)
Bitflip (4
Bitflip
Episade Reward
Episode Reward
Epicade Reward
1.00
DQN
DQN
DQN Factorad DQN
DQN
DaN
50000 Timestep
100000
50000 Timestep
100000
500000 Timestep
1000000
(b)
(c)
DON: Multi-Cartpole cartpoles)
DON: Carti-Cartpale (4 cartpoles)
DON: CartilCa (8 cartpoles)
200
200
200
Episode Reward
Episade: Reward
Epicode Reward
DQN
DQN FactoredDQN
100
Factored DQN
100
DQN
Factored DON
100000
200000
100000 Timestep
200000
100000
200000
Timestep
Timestep
(d)
(e)
Figure 12: DQN Factored DQN performance on Bitflip (a.b,c) and Multi Multi-Cartpole (d,e.f). The solid lines show the average over 5 random seeds and the shaded area shows = standard deviation.
22

---

Under review as a conference paper at ICLR 2021
E ADDITIONAL PPO EXPERIMENTS
We also compared PPO with Factored NN vs. with an ordinary NN on the BitFlip and multi marti-Cartpole environments with the results shown below. We find that the Factored NN algorithms perform better and that the difference increases the more complex the environment is.
PPO: BitFip (2 bits) without Critic
PPO: titrlip (4 bit))
PPO: Nulti CartPole (2 cartpoles)
1,003
Eulodl Rowardd
2.8-
Eppicdde Rueoorrd
t,50
2.955
5,75
2.03
Factored PPO
PPO
59022
100000
150003
200335
300500
2016000
2016000
Timestop
Timesto
Figure 13: PPO with Factored NN vs. NN performance on Bit Flip with 2 (left) and 4 (middle) bits as well Multi-CartPole with 2 poles (right). The solid lines show the average over 5 random seeds and the shaded area shows standard deviation.
(GhE) In addition, report PPO results when we disable the generalized advantage estimation (GAE) Schul- man et al. (2015) (Critic) and when we disable the critic altogether (without Critic).
PRo: BitFile (2 bits) without Critic
PPO: BiFllpo without
PPO: BitFlip bits) without Critic
1,002
Euloode Rewward
Epiaade Raoward
Spiodd Reward
5.05
0,955
0.85
2,02
PRO
Factored PPO
PPO
50932
100000
150000
200235
32000
100003
150200
200003
Timastop
Timestep
Figure 14: PPO (without a critic) with Factored NN vs. NN performance on Bit Flip with 2 (left), (middle) and 8 (right) bits. The solid lines show the average over 5 random seeds and the shaded area shows standard deviation.
PPO: BitFip (2 bits) with
PPO: BitFlip 14 bitst with Critic
Cotic
Epieante Resword
Epixeda Raward
Sppaaa Pe Reward
2.5
Factored PPO
Factored PPO
PackondPPO
20002
100002
155000
200030
$3000
150003
155200
200003
Timestap
Timestep
Timestep
Figure 15: PPO (with a critic) with Factored NN vs. NN performance on Bit Flip with (left), (middle) and 8 (right) bits. The solid lines show the average over 5 random seeds and the shaded area shows standard deviation.
23

---

Under review as a conference paper at ICLR 2021
Malli-Carpple
Mult-Caripii
230
173
Epiodd Reward
Episode Roward
15
Epioude Roward
130
125-
PPO
PPO
PPO
500000
1000000
330886
3000000
305000
3000000
Figure 16: PPO (without a critic) with Factored NN vs. NN performance on multi Cart Pole with (left), 4 (middle) and 8 (right) cartpoles. The solid lines show the average over 5 random seeds and the shaded area shows + I standard deviation.
100: Caripple cartpoladi Crtti
2PO Mulli-Cartede cortpoles) with Crici
2P0: Mull Mult-Caripul cartpoles) Crick
230
172
Epoede Reward
Eyroode Roward
Expoude Reward
52
FPC
PPO
PPO
200000
300cee
S06000
Figure 17: PPO (with a critic) with Factored NN vs. NN performance on multi Cart Pole with 2 (left), 4 (middle) and 8 (right) cartpoles. The solid lines show the average over 5 random seeds and the shaded area shows standard deviation.
HalfCheatah with Critc
PPO: Ant with Critic
PPO: humanoid with Critic
Epiiode Rewonn
Eptcoda huward
Esiooda Roward
-10-
335-
-20
-1380
PPO
-40
Fastored PPO
Factored PPO
2390000
Tmmsstp
2000010
Timestep
4000950
5003300
2026003 0330000
Timestep
6003000
Figure 18: PPO with Factored NN vs. NN performance on Half Cheetah (left), Ant (middle), and Humanoid (right). The solid lines show the average over 5 random seeds and the shaded area shows + standard deviation.
HalfCheetah without
PPO: Ant without Crtie
PPO: Humanoid without Critic
Epiocae Roward
Eptxode Ruwward
Gelooda Raward
-10-
-350
-20
-40
-1380
PPO
Factored PPO
Factored PPO
2300800
Timestep
2000350
Timestep
40003200
5003300
2000003
Timestep
8030000
0003E00
Figure 19: PPO with Factored NN vs. NN performance on Half Cheetah (left), Ant (middle), and Humanoid (right). The solid lines show the average over 5 random seeds and the shaded area shows standard deviation.
24


Reviews:
[{"review_id": "yEkHtl6UnVQ", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper looks at how to build deep RL agents that can perform more efficient learning by directly leveraging the factored structure of problems when that information is given. The approach proposed by the authors is to design a neural network architecture that explicitly honors the factored structure of the problem. The authors detail a version of MCTS that can leverage independent components of the state, a version of DQN that can leverage independent components of the reward, and a version of PPO that generates actions based on independent state components. I very much like the idea of making connections with the factored MDP literature. However, as the authors point out in the conclusion, an approach that actually discovers the causal factors of the problem would be much more interesting and generally applicable. In terms of leveraging the provided structure of the problem is concerned, the experiments seem convincing that the proposed approach by the authors has value. That said, it was not clear to me how common this setting is where the agent can directly leverage known structure about independent aspects of the state and reward like this. The experiments felt a bit contrived to me, which I think at least partially reflects this inherent difficulty of  finding an environment that naturally fits the setting the authors explore. Additionally, the environments considered of very low complexity. I do not usually like to focus on this, but see it as a potential issue in this case because it is unclear to me if the architecture implications of the factored neural network considered here would scale well for example to vision problems with complex feature spaces and CNN architectures. \n\nI am very much on the fence about this paper as I like the overall direction as a stepping stone towards a model that discovers factored state representation as well. However, I think the paper could really benefit from more evidence either theoretically or empirically that the factored neural network structure is always likely to lead to improvements when this structure is present. For example, could you say anything theoretically about the way that this leads to sample efficiency improvements during learning? Additionally, the authors should explain and potentially validate how their factored neural networks would extend to richer input streams like visual observation based environments. \n\nAfter The Rebuttal: I really appreciate the rebuttal and revisions submitted by the authors. They did a good job of detailing domains of interest where their approach may be applicable. I also agree with some of the points they made about the complexity of domains that they considered in their experiments. As such, I have revised my score and now lean towards acceptance of the paper. ", "extra_scores": {}, "extra_text": {}}, {"review_id": "RbOSxB7WnKx", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper presents a methodology for incorporating factor-graphs into model-based and model-free RL methods. The work starts by assuming access to a correct and factor graph showing the relationship between individual state factors, actions, and rewards. The authors propose to make use of this factor graph by using a Factored Neural Network - which is similar to the standard feed-forward MLP networks that would typically be used to parameterize a policy or Q-function - except that it masks out connections between input and output nodes that are not connected in the factor graph. Presumably this results in a sparser neural network which can lead to faster learning and better sample complexity. The authors demonstrate how these factored NNs can be incorporated with model-based MCTS as well as model-free DQN and PPO. In short - the algorithm remains unchanged and the only substition seems to be the Factored NN rather than a fully-connected NN. Experiments are performed on Multi-Cartpole (simultaneous control over several cartpoles), Taxi, BitFlip, and PyBullet's Ant, Half-Cheetah, and Humanoid. Each of the factored algorithms is compared with the un-factored equivalent and increased sample efficiency of learning is noted for the factored variants. The authors provide the manually-defined factor-graphs used for each of these environments in the Appendix.\n\nOn the positive side - I think the approach to creating factored-NNs to reflect the structure in the factor graph is sensible. Additionally, the results support the authors' claim that using these factored-NN can lead to greater sample efficiency. It's also nice to see that this approach - because it only modifies the underlying NN - is straightforward to integrate with many of the existing model-based and model-free algorithms.\n\nIn my opinion, the main drawback of this work is that many of the domains examined are either poor representatives of RL problems would ever be faced by an RL agent or simple enough to not require neural network function approximators. For example Multi-Cartpole is a highly-artificial environment which shows that current RL algorithms aren't equipped to simulatenously solve multiple MDPs. While this is a great motivating example - it's used extensively throughout the results. Similarly, Taxi and Bitflip are also toy domains that might not even require a neural network function approximators to solve (e.g. maybe the proper point of comparison for these domains is tabular methods built for factored MDPs?). The PyBullet environments are exceptions to this critique - but in these environments the performance improvement is not particularly notable.\n\nMore broadly, algorithms like DQN and PPO are commonly applied in environments featuring high-dimensional observation spaces such as pixel images, which don't admit easy factorization. Given that this paper is motivated by extending factorization techniques to Deep RL algorithms - the real question is \"What environments admit easy factorization and require deep neural networks to solve?\" It seems like the intersection of these criteria may leave vanishingly few opportunities for the community to apply the techniques in this paper.\n\nIn summary - the approach is reasonable, the results are impressive on toy domains but less impressive on realisitic domains. As pointed out in the future work, the real million dollar questions are 1) How to extract factor graphs from high dimensional pixel images and 2) How to infer latent structure of factor graphs from experience.\n\nMinor Note - In Section 3 - PA(.) is not defined anywhere. Does it refer to the parents of a node?\n\nOther related work - Working Memory Graphs; Loynd et al. has shown that using factored representations of state with transformer-based RL agents leads to improved sample complexity.\n\nI have read the authors response and updated paper and appreciate the discussion of applications that admit factor graphs.", "extra_scores": {}, "extra_text": {}}, {"review_id": "MCBt-_TKDly", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "D4RL: Datasets for Deep Data-Driven Reinforcement Learning\nreview:\n\nsummarization:\n\nIn this paper, the authors consider using factored neural network (NN),\ninstead of directly using forward NN in model-based or model-free reinforcement learning.\n\nPros:\n1. In general the project is nice and neat.\nA simple algorithm is proposed,\nand the performance is improved upon existing baselines.\n\n2. Extensions on PPO, MCTS, DQN is studied and evaluated,\nmaking the paper quite comprehensive and the conclusion proposed more robust and convincing.\n\n3. The paper is well written and in general easy to understand.\nThe figures in this paper are very helpful as well.\n\n4. The algorithm is also applicable to high dimensional problems such as humanoid.\n\nCons:\n1. The algorithms were not combined with existing state-of-the-art algorithms,\nwhich includes algorithms such as SAC, TD3, MBPO.\nIt would be interesting to see if the proposed method can lead to state-of-the-art performance.\n \nMisc:\n1. how efficient is it to train and evaluate (is it real-time?)\n2. Does it mean that the structure has to be manually specified for each environment?\n3. The paper reminds me a lot of NerveNet [1],\nwhich also considers factored or graph NN in reinforcement learning.\n\nSummary:\n\nIn general I believe the paper is nice and neat. I tend to vote for acceptance in this case.\n\n[1] Wang, T., Liao, R., Ba, J., & Fidler, S. (2018, February). Nervenet: Learning structured policy with graph neural networks. In International Conference on Learning Representations.", "extra_scores": {}, "extra_text": {}}, {"review_id": "2D376K7tnmu", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary:\n\nThe authors present a method by which the underlying MDP describing RL tasks can be factored into independent components in combination with Deep RL solutions to improve the efficiency and tractability of the problem.  The graph factorization of state, action and reward components is realized via an adjacency matrix that adds masking across input and output components.  \n\nThey evaluate factored RL approaches for both model based and model free RL algorithms:  MCTS, DQN, PPO.  In the case of model based approach (MCTS) the state transition function is factorized.  For model-free approachs, DQN & PPO, decomposed Q-functions and policy functions are used.  These approaches are evaluated across a number of domains: Multi-Cartpole, Taxi, BitFlip and robotics tasks Ant, HalfCheetah and Humanoid from the RL Control Suite.\n\nOverall, the paper is clear and well written.\n\nStrengths & Weaknesses:\n\nThe authors detail the scope of the problem domain and embed their approach well in the existing literature. The scope of the problem that the authors are addressing is broad and relevant as it applies to a whole host of problems where the underlying MDP is well understood.  The novelty of the approach lies in the extension to Deep RL algorithms from prior approaches which relied on tabular or linear methods.  The authors also consider state and input/output masking in addition to action masking, an approach taken by earlier methods.  The author also seek to address and take advantage of causal inference in the fully observable RL environment setting.\n\nThe paper is divided nicely among the MCTS, DQN and PPO sections and the authors clearly describe the factored inputs and outputs in each case with the Multiple Cartpole used as an example.  The authors have also chosen a diverse set of tasks over which to evaluate and have demonstrated that there are strong gains to be realized in both sample efficiency and top-line performance when using the factored approach.\n\nFor me the greatest weakness of the paper is that there was not a great deal of insight given with respect to how scalable this approach might be in terms of other RL domains such as for instance in navigation or planning and the impact that a factored approach might have on representation learning where experience across diverse parts of the environment may be important to learn how to encode information over a diverse set of experiences.  Furthermore, the factorization algorithm needs to be  defined by hand for each task which may incur additional complexity and pose problems when the aim is to optimize for generalization in RL agents.  However the authors do state this explicitly and note that a future direction for this work could be in online discovery of factored graphs.\n\n\nOther Points:\n\nFigure 4a only contains one curve (Presumably this should be FactoredDQN rather than DQN?)\n\n\nRecommendation:\n\nI recommend a score of 6 and would be happy to see this paper accepted.   I believe the approach sets out a fruitful direction for Deep RL which could be particulary powerful if this factorization could be learned.  In these early steps I believe the authors have laid out the problem well and provided strong results to support their claim.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper introduces variants of RL algorithms that can consume factored state representations. Under the assumption that actions only affect a few factors, these factored RL algorithms can learn more efficiently than their vanilla counterparts. Learning a factored dynamics model (to be used in a model-based algorithm) or representing factorized action-selection policies (to be optimized by a model-free RL algorithm) make intuitive sense in the problem settings that the paper considers. However, the paper should clarify the implicit assumptions being made about how the reward decomposes across factors. For instance, the factored DQN approach seems to require a linear reward decomposition across the factors.
The factored DQN approach is also reminiscent of the Hydra algorithm on MsPacMan (https://papers.nips.cc/paper/2017/file/1264a061d82a2edae1574b07249800d6-Paper.pdf Section 4.2) which assigns an RL agent to each factor ("ghost" in MsPacMan) to learn a factor-specific Q-function. The linear aggregator that they use is identical to the factored DQN in this paper.

The reviewers all rate the paper as borderline. All reviewers suggest that being able to learn the factor graph (or at least parts of it) will greatly widen the scope of applications where the approach can be fruitfully applied -- the paper acknowledges this as a compelling line of future work. The biggest weakness is originality -- the core message of the paper is just that, where factored representations of state/actions exist RL algorithms must use it. This is not a surprising or novel message. The paper advocates for incorporating the factorization information in the most straightforward way (state-masking, followed by action concatenation). Simple-in-retrospect is usually an excellent feature of an algorithm, not a bug; however, the proposal is literally the first idea a reader will likely think of. It might help to explore other ways of incorporating factorization information (e.g., rather than parameter sharing, have a separate network for each factor; rather than masking, have different width input layers to consume different number of parents in the DAG; etc.) and verifying that they are inferior to factored NN.
Decision: Reject