Title: EXPRESSIVENESS IN DEEP REINFORCEMENT LEARN-ING

Abstract: Representation learning in reinforcement learning (RL) algorithms focuses on extracting useful features for choosing good actions. Expressive representations are essential for learning well-performed policies. In this paper, we study the relationship between the state representation assigned by the state extractor and the performance of the RL agent. We observe that representations assigned by the better state extractor are more scattered than which assigned by the worse one. Moreover, RL agents achieving high performances always have high rank matrices which are composed by their representations. Based on our observations, we formally define expressiveness of the state extractor as the rank of the matrix composed by representations. Therefore, we propose to promote expressiveness so as to improve algorithm performances, and we call it Expressiveness Promoted DRL. We apply our method on both policy gradient and value-based algorithms, and experimental results on 55 Atari games show the superiority of our proposed method.

1. INTRODUCTION:

Deep reinforcement learning (DRL) algorithms, such as DQN (Mnih et al., 2015) , A3C (Mnih et al., 2016) , DDPG (Lillicrap et al., 2015) , and TRPO (Schulman et al., 2015) , have been applied in a range of challenging domains including Atari games (Mnih et al., 2015; Schaul et al., 2015; Van Hasselt et al., 2016) , robot locomotion tasks (Schulman et al., 2015; 2017) and the game of Go (Silver et al., 2016; 2017) . The combination of RL and high-capacity function approximators such as neural networks holds the promise of automating a wide range of decision making and control tasks.

The DRL model often contains two parts. First, a deep neural network is used to extract stateful information from raw signals, e.g, convolutional neural network for images-based games (Mnih et al., 2015; Vinyals et al., 2017) or recurrent neural network for natural language-based games (Narasimhan et al., 2015; Zhao & Eskenazi, 2016) . Without any confusions, we call such raw signals as observation, call the extracted stateful information as state and consider this deep neural network as state extractor. Given the representation of state, a feedforward neural network is further used to select different actions to maximize the potential rewards. From the above description, it is easy to see that the performance of an RL agent depends on two parts. First, it depends on whether the state extractor is good. With a good state extractor, the representation which is a depiction of the observation will retain necessary information for taking actions. Second, it depends on the accuracy of the policy: whether the feed-forward model can correctly take the optimal action given the state.

In this paper, we mainly study the relationship between representations extracted by the state extractor and the performance of the RL agents. We observe that when agents achieve better performances, matrices composed by their representations are approximately higher rank. 1 Firstly, we study representations assigned by state extractors in different performed RL agents over all Atari games. We find that representations assigned by the better extractor are more scattered. Furthermore, given different trajectories that lead to high/low rewards as inputs, matrices of representations from the better extractor are always higher rank. Secondly, we find changes of the approximate rank are highly consistent with changes of rewards, which also demonstrates the positive correlation between the rank and rewards. These observations motivate us to encourage matrices of representations to be high rank during training.

Based on our observations, we formally define expressiveness of the state extractor in reinforcement learning. For given markov decision process (MDP) and the initialization state, we can get a realization of the MDP, i.e., a trajectory. The state extractor extracts representations from observations in this trajectory. Representations compose a matrix, which we call it representation matrix. For given MDP with finite state space, expressiveness in RL for the state extractor model is defined as the rank of the representation matrix. According to the definition, expressiveness in RL is both related to the MDP which generates data and the state extractor model. Based on above experimental studies, we can conclude that higher expressiveness will lead to better performances. As we can see that expressiveness is not easy to calculate because the max operator and the infinite number of columns in representation matrix, so we consider the rank of the representation matrix composed by a mini-batch of representations, which is called empirical representation matrix. Empirical expressiveness in RL is defined as the approximate rank of the empirical representation matrix, i.e., if some singular values are approximately zero, we regard them as zero.

We further propose a novel method ExP (Expressiveness Promoted) DRL, which aims improve the expressiveness of the state extractor, so as to promote RL algorithm performances. Based on experimental observations and the definition, the empirical representation matrix is encouraged to be high rank in our method. The idea is implemented by adding a regularization term to the loss, which is computationally efficient and can be applied to multiple kinds of DRL algorithms.

We applied our method to A3C (Mnih et al., 2016) and DQN (Mnih et al., 2015) . Evaluation results on Atari games show that our method outperforms the baseline on most of games. Furthermore, we also demonstrate that the expressiveness of the state extractor is significantly enhanced by our proposed ExP DRL.

2. STATE EXTRACTOR EXPRESSIVENESS:



2.1. EXPERIMENTAL OBSERVATIONS:

In image classification tasks, many papers show that the representation of images (high-level features from top layers) contains useful and abstract information for decision makings, e.g., predicting the categorical labels (Coates et al., 2013) . In reinforcement learning, such high-level features will be used to find better actions in pursuit of larger reward.

However, the representation in reinforcement learning is much harder to learn compared to that in supervised learning problems. In image classification task, e.g., ImageNet, different images with the same label contain the same item and most of the images in different categories contain different items. This makes the neural network can learn discriminative information effectively and the learned features are good with intra-class compactness and inter-class separability (Liu et al., 2016) . In reinforcement learning, taking shooter games in Atari as an example, the input images which will be fed into the neural network are similar as most of them contains a group of enemies, bullets, the agent and different objects in the game. Based on similar observations, the neural network has to learn to extract fine-grained local features that contain the positions of enemies, the direction of bullets, the current position of the agent and related objects, which are essential for taking actions.

Therefore, to investigate the characteristic of good representations assigned by the state extractor, we compare state extractors in RL models with different performances. We find that representations generated by better state extractor are more scattered compared with worse extractors, and the matrix composed by better representation vectors is higher rank. We observe similar phenomena during training process, which shows that when the matrix formed by representations becomes higher rank, the reward of the RL model become higher. Furthermore, we notice that representations are not always getting more discriminative during training, which also motivates our proposed method.

2.1.1. COMPARISON BETWEEN BETTER AND WORSE STATE EXTRACTORS:

Comparison between representations assigned by state extractors in RL models with different performances is shown in Fig. 1 Besides, in order to exclude the bias of the model size, we also observe representations generated by the large model with its randomly initialized weights, which can only gets 0 game point because points are hard to obtained in this game. We refer to these three models with large trained model, small trained model and large random model respectively.

Fig. 1 shows the two-dimensional embedding of the representations in the last hidden layer assigned by three models to game observations in the trajectory played by the large trained model. Plots are generated by using SVD dimension reduction on the matrix composed by representation vectors.

Points in the embedding figure of the model with higher final reward are more scattered overall.

Observations only have subtle differences on the existence of enemies, the position and direction of the controlled agent. More scattered representations indicate that the better model can distinguish these subtle differences well, and can do better in extracting these fine-grained local features. These scattered representations can benefit policies and thus lead to better performances. In other words, representations assigned by the better state extractor is more discriminative.

To get more accurate and solid observations, we list some statistics over all Atari games in Table 1 .

For each of the Atari game, representations of a large trained model, a small trained model and a large random model are compared. To study the relation between performances and representations, we select games in which the large trained model performs best and the large random model performs worst. In this way, 39 games among 55 games are picked. Then for each game, we generate three trajectories with different final reward by interacting with the environment using three models.

Observations in these three trajectories are sent to three state extractor models respectively, and then 9 matrices composed of generated representations are obtained for every game. We sort singular values of the matrix from largest to smallest, and calculate the smallest ordinal number while the cumulative percentage of singular values is above a certain threshold. We list average smallest ordinal numbers of selected 39 games for threshold 80% and 90% in Table 1 . These data demonstrate that given different trajectories and model size, the average smallest ordinal number always positively correlates with the model performance: the smallest ordinal number of the better model is always larger then which of the the worse model. This means that the matrix composed of representations generated by the better model is always higher rank than which generated by the worse model, which suggests that regardless of input trajectories and model size, states assigned by the better extractor is more discriminative and expressive comparing with the worse model, because higher rank corresponds to better discrimination. Representations which are not expressive enough cause troubles for decision making. Therefore, representations should be encouraged to be more discriminative and expressive for obtaining good policies.

2.1.2. TRENDS DURING TRAINING:

In order to investigate the found phenomena extensively, and also make the observation more convincing, we study representation changes during training in this section. We train a model to play the Atari game WizardOfWor for 200M frames. Each time the model is updated with a mini-batch of transitions, representation vectors in the last hidden layer are regarded as a matrix, and singular values of this matrix are recorded. We calculate the smallest ordinal number while the cumulative percentage of singular values is above a certain threshold (i.e., 80%) as last section. Large ordinal number means that the matrix composed by representation vectors is high rank, and corresponding representations are discriminative. Two curves are plotted in Fig. 2 . The blue one tracks testing rewards, and the yellow one tracks smallest ordinal numbers. It shows that curve trends of testing rewards and smallest ordinal numbers are highly consistent: when smallest ordinal numbers increase/decrease, rewards also become high/low. Same phenomena on more games can also been seen in Fig. 6 . This consistency demonstrates that states assigned by the better extractor, which form high rank matrices, are more discriminative and expressive, and holding discriminative representations is necessary for learning good policies. Besides these same conclusions mentioned in last section, we also notice that during training, the smallest ordinal number is not always increase. But representations which are not expressive enough cause troubles for decision making. Thus, the expressiveness of state extractors should be promoted (i.e., formed matrices should be encourage to be high rank) during training.

2.2. DEFINITION OF THE EXPRESSIVENESS:

Based on previous observations, we formally define a new concept expressiveness in RL in this section. Consider an Markov decision process (MDP) M = (S, A, p, γ, r), where S denotes the observation space, A denotes the action space, p : S × A → µ(S) denotes the transition probability with µ(S) denoting the space of measures on S, γ ∈ (0, 1) denotes the discount factor and r : S × A → R is the reward function. The goal of reinforcement learning is to learn a policy π(x) that maximize the average future reward function

E π(x),p(x,a) [ ∞ k=0 γ k r(x k , a k )|x 0 ]. Assume that {x 1 , • • • , x b }

is a mini-batch of observations. We use operator h(x) : X → R d to denote the state extractor. For given observation x i , we obtain its the representation h(

x i ) = (h i1 , • • • , h id ).

The representations of a mini-batch of observation consist a matrix, which we call it representation matrix and denote it as

H = (h(x 1 ), • • • , h(x b )) T = {h ij } i=1,••• ,b;j=1,••• ,d

, where h ij denotes the j-th representation calculated using the i-th observation in the mini-batch. Definition 1. (Expressiveness in RL) For given MDP M = (S, A, p, γ, r) with finite observation space S and initial observation x 0 , the expressiveness E M (h) for extractor model h is defined as the rank of matrix composed by h(X t ), ∀t, i.e.,

EM(h) = rank{h(X1), • • • , h(Xt), • • • }.

(1)

The defined expressiveness is related to both the MDP M and the model h. For fixed MDP, the expressiveness is similar to that is defined in supervised learning which is related to the function approximation ability. For fixed h, the expressiveness is related to the MDP M. Consider two two MDP M 1 and

M 2 with |S 1 | = |S 2 |. If M 1 is ergodic and M 2 is non-ergodic (i.e.

, it can only visit a subset of observations), then the matrix {h(X 1 ),

• • • , h(X t ), • • • } will more possibly be low rank.

In practical, it is not easy to exactly calculate the rank for a trajectory with infinite length. Thus, we define the following empirical expressiveness. Definition 2. (Empirical expressiveness in RL) For given observations {x 1 , • • • , x b } and representation matrix H b×d , we order singular values of H from large to small as σ 1 (H), • • • , σ min{b,d} (H).

The empirical expressiveness E b, (h) for extractor model h is defined as

EQUATION

Please note that the empirical expressiveness is related to the number of sampled observations, given precision and the extractor model h. Please note that the rank of the representation matrix is full in practical because the singular values will not be exactly equal to zero. So we introduce in the definition.

3 EXP (EXPRESSIVENESS PROMOTED) DRL We propose our method named ExP DRL, which intends to improve the expressiveness of the state extractor, so as to promote DRL algorithm performances. Based on the new concept expressiveness, experimental observations in Sec. 2.1 can be summarized as: state extractors with better expressiveness lead to better policies, and the expressiveness not always becomes better during training. Hence, in order to obtain better policies, we propose to promote the expressiveness of the state extractor, which means encouraging matrices formed by extracted representations to be high rank.

To be specific, the general architecture of a DRL model and its representation matrix are shown in Fig. 3 . The state extractor extract features from the observation x to generate the representation vector h(x), then these representations are sent to a feedforward neural network to select the action a. For one observation x i , a representation vector h(x i ) is generated, and for a mini-batch of observations, {h(x 1 ), ..., h(x b )} of size b, these vectors compose a representation matrix H. In ExP DRL, this matrix H is encouraged to be high-rank.

To minimize computation costs, we adopt a simple way to encourage high rank representation matrices. A regularization term is added to the policy loss, making matrix H to be high rank. Thus, total loss is denoted as,

EQUATION

where α is the coefficient. According to description in Section 2.2, R(H) should be equal to -E b, (h) in order to encourage H to be high rank. Directly optimize -E b, (h) is not easy because of the argmax operator, thus we propose three types of regularizers which can reflect the scale of -E b, (h) to some extent.

Negative Nuclear Norm Minimizing the nuclear norm is usually used as a constrain in low-rank matrix completion problems (Cai et al., 2010) . The nuclear norm of a matrix is the sum of all singular values of this matrix, which is defined as

EQUATION

where σ i (H) is the ith singular value of H. Here we try to make the representation matrix to be high rank. Hence, we add a negative nuclear norm to the loss, so R(H) = -||H|| 1 .

Max Minus Min:

Besides enlarging all singular values, a more direct way to improve expressiveness of the state extractor is to reduce the gap between the maximum and the minimum singular value. This gap is defined as,

EQUATION

and R(H) = G(H).

Condition Number:

The aforementioned two kinds of rank regularization terms, ||H|| 1 and G(H), are sensitive with the scale of singular values. So in order to reduce this bias, we also try to use the condition number to be the regularization term.

Condition number is defined as the ratio of the maximum and the minimum singular value:

EQUATION

The scale bias can be resolved by the division operator in the condition number. Similar with the Max Minus Min term, the condition number should be minimized during training to improve the expressiveness, so R(H) = K(H) here.

Figure 4 : Improvements of our method ExP DRL compared to A3C, using the metric given in Eq. 7.

In summary, the key improvement in ExP DRL is that we change the loss function to Eq. 3. And we introduce three kinds of regularization terms: the negative nuclear norm -||H|| 1 , the max minus min G(H) and the condition number K(H). We analyze differences among these 3 terms in experiments.

Note that ExP DRL can be applied to various kinds of DRL algorithms. The expressiveness can be promoted by simply adding a regularization term when the RL model is updated. Excepting these transitions used for updating the RL model, no other data are introduced for encouraging highly expressive representations. Thus, our method can be widely applied to current DRL algorithms, with little extra computational cost.

4. EXPERIMENTS:

The experiment section is designed to answer these questions: (1) Can algorithm performances be improved by applying our proposed expressiveness promoted method? (2) What is the difference between 3 proposed rank regularization terms? (3) Is the expressiveness of the state extractor promoted after using ExP DRL? (4) Can ExP DRL improve performances of multiple kinds of DRL alogirithms? These questions are answered respectively in 4 subsetions below.

4.1. OVERALL PERFORMANCES ON A3C:



4.1.1. SETTINGS:

We evaluate our proposed method on 55 Atari games (Bellemare et al., 2013) . Atari game learning environment is one of the most popular and challenging RL task because of its high-dimensional and diverse observations. Here we use OpenAI Gym (Brockman et al., 2016) package.

In this section, we use A3C (Mnih et al., 2016) as our baseline, and use the pytorch-a3c package (Kostrikov, 2018) , which is also be adopted by Peysakhovich & Lerer (2017) , to implement. The network architecture is shown in Appendix A. An environment wrapper is utilized to simplify original visual screens, and they are processed to 42×42 gray-scale images. We use a frame-skip of 4 here.

The number of processes is set to be 16. Besides, each agent is trained for 200M game frames, and the obtained reward is averaged over 5 runs with different random seeds.

For our proposed method, outputs of the LSTM are taken as representations generated by the state extractor. Each time the A3C model is updated using a mini-batch of transitions, representations of observations in these transitions form the matrix R. To improve expressiveness, this matrix is encouraged to be high rank by adding the regularization term. Expect the coefficient α, other hyper parameters and settings are set as same as the baseline.

4.1.2. PERFORMANCES:

Following the previous work (Wang et al., 2015) , we use the measure below to compare the performance of ExP DRL over the baseline.

ScoreAgent -Score Baseline max{ScoreHuman, Score Baseline } -Score Random × 100%.

(7) We summarize the improvement of our method over the A3C baseline in Fig. 4 , and all raw scores and normalized socres are listed in Table 5 in the appendix. Among 55 games, ExP DRL outperforms the baseline for 43 games. These demonstrate that encouraging representation matrices to be high rank promotes performances of original algorithms. Improving expressiveness of state extractors benefits learning good policies. Nuclear Norm. This is reasonable because that enlarging all singular values may not increase the expressiveness of the state extractor. It is not certain that which singular value gets larger when applying the Negative Nuclear Norm. For example, the expressiveness will decrease when only the largest singular value becomes larger. Instead, the object of Max Minus Min and Condition Number is to reduce the gap between the largest and the smallest singular value, which directly enlarges the expressiveness of state extractors.

4.2. THREE RANK REGULARIZATION TERMS:

We use Max Minus Min and Condition Number with α as 0.01 to cover results of most games in the previous section. All hyper parameters we used are listed in Table 4 in the appendix.

4.3. EXPRESSIVENESS ANALYSIS:

In this section we analysis the expressiveness of the state extractor learned using the baseline and our proposed method. Curves tracking testing rewards and the empirical expressiveness are plotted in Fig. 6 .

From testing reward curves we can see that ExP DRL outperforms the A3C baseline on these games. These results show that improving expressiveness significantly benefits policy learning.

Combining testing reward figures and expressiveness figures, we can observe that: (1) the empirical expressiveness of the state extractor is increased by adding the regularization term, which demonstrate that the proposed method can really enhance the expressiveness.

(2) Curve trends of the reward and the expressiveness are highly consistent. Since our method ExP DRL does not contain any algorithm related operations, we investigate whether it can promote performances of another kind of DRL algorithm. Experiments on policy gradient algorithms have been done based on A3C in previous sections, so we choose Q-learning here, and use DQN (Mnih et al., 2015) as our baseline.

We use same network architecture and hyper-parameters as Mnih et al. (2015) . We run 30 Atari games (first 30 in alphabetical order) and run each game for 200M frames. All socres are listed in Table 6 in the appendix, and we summarize the overall performances of these 30 Atari games in Tab. 2. Results show that ExP DRL outperforms the baseline in most of games. This demonstrates the superiority of ExP DRL over the DQN baseline, and supports our claim that encouraging highly expressive state extractor can promote performances of multiple kinds of DRL algorithms.

5. RELATED WORKS:

State representation learning in RL has been studied in many research works. It focus on learning features which can capture useful information for taking good actions (Lesort et al., 2018) . In some of proposed methods, auxiliary models, including variational auto-encoder (van Hoof et al., 2016) , denoising auto-encoder (Higgins et al., 2017) , auto-encoder (Mattner et al., 2012) , Generative Adversarial Networks (Donahue et al., 2016; Shelhamer et al., 2016) and some other models (Oh et al., 2017; Weber et al., 2017) , are built for refining the representation learning. These models may be designed as a part of the network architecture, and are trained end-to-end (Oh et al., 2017; Pathak et al., 2017; Tamar et al., 2016) , or they can also be trained separately and are used for helping decision making (Weber et al., 2017) . These auxiliary models help to improve representation learning via completing some certain tasks, such as reconstructing current observation or state (Watter et al., 2015) , predicting future observations or states (Oord et al., 2018; Franc ¸ois-Lavet et al., 2018; Munk et al., 2016) , and recovering actions given transitions (Zhang et al., 2018) . Some essential information for taking actions can be retained by completing these auxiliary tasks. Different with these methods, none other models need to be built and trained in our method. We improve the expressiveness of the state extractor by simply adding a regularization term.

Task specific prior knowledge or information are utilized to improve representation learning in some proposed methods. For example, detection of moving objects is used in Goel et al. (2018) for better learning video games. Jonschkowski & Brock (2015) proposes to use robotic prior knowledge for robot learning. In some chatting systems (Zhao & Eskenazi, 2016) , task-related information, such as extracted named entities, are utilized for dialog state representation learning. For our method, we focus on the expressiveness of the state extractor, which does not contain task-specific informations.

Besides, there are some works discussing expressiveness in deep learning (Raghu et al., 2016; Cohen et al., 2016) . These works focus on the power of the model, but not internal representations. In addition, out basic setting is for DRL algorithms, which is different with these works.

6. CONCLUSIONS:

In this paper, we mainly study the relationship between representations extracted by the state extractor and the performance of the RL agents. We observe that when RL agents achieving high rewards, its representations become discriminative, and the representation matrix goes to be high rank. Therefore, we formally define the expressiveness of the state extractor as the rank of the representation matrix.

We then further propose a new method ExP DRL, in which algorithm performances are promoted via improving the expressiveness. Experiments of A3C on 55 Atari games and DQN on 30 games demonstrate that ExP DRL can promote their performances significantly. 

D USING L2 NORM REGULARIZER:

In this section, we run A3C with L2 norm regularizer on 10 Atari games, and performances are compared with performances of our proposed ExP DRL. We tune the coefficient of L2 norm regularizer (denoted as β here) in a similar way with what we used for α. We firstly choose best three β for 2 games from 1 to 10 -8 . These best three β are 10 -4 , 10 -5 and 10 -6 . Then we apply these three β to rest of 8 games, and choose the best performed one to repeat 4 times additionally. Thus the final reward is averaged over 5 times. We keep other settings same as Sec. 4.1.1.

Using the measure in Eq. 7, we list performances of our proposed ExP DRL and L2 norm in Fig. 8 . Among 10 games, ExP DRL outperforms L2 norm regularizer in 9 games. These results demonstrate that our method ExP DRL is more efficient than L2 norm regularizer. Besides, adding L2 norm regularizer not always improves performances. It seems that it has an uncertain effect on final performances. Our method and the L2 norm regularizer influence the final performance in a different way. The L2 norm prevents overfitting, and ExP DRL improves expressiveness of the state extractor, leading to better performed RL models.

:

Approximately low rank means that most of the singular values for a matrix are close to zero while only little of them have large values, and higher rank corresponds to more large singular values. In this paper, low/high rank refer to approximately low/high rank.

Figures and Tables:

Figure 2: Curves tracking testing rewards and smallest number of singular values during training process. Curves are smoothed.

Figure 3: General architecture of a DRL model and its representation matrix H. u is the number of hidden units, and b is the mini-batch size.

Figure 6: Testing rewards curves (left) and empirical expressiveness curves (right) on 4 Atari games for ExP DRL (yellow) and the baseline (blue).

Figure 5: Rewards of ExP DRL applying three regularization terms. Shaded areas depict variances.

Figure 8: Improvement comparison over baseline A3C between L2 norm regularizer and our method ExP DRL.

and Table1. We let two models with different model size but same Figure 1: Two-dimensional embedding of the representations assigned by different state extractors. Relationship between model performance and the smallest ordinal number of singular values. number of last hidden layer units play the Atari game Gravitar for 200M frames respectively. After training, the larger model achieves 3050 for the game score, while the smaller model gets 600 points.

Table content: <table><tr><td>Episode Data</td><td>Cumulative Percentage</td><td colspan="3">Average Smallest Ordinal Number of Different Models Large Small Large</td></tr><tr><td/><td/><td>Trained</td><td>Trained</td><td>Random</td></tr><tr><td/><td/><td>Model</td><td>Model</td><td>Model</td></tr><tr><td>Episode from</td><td>80%</td><td>164.9</td><td>137.8</td><td>103.8</td></tr><tr><td>Large Trained Model</td><td>90%</td><td>247.7</td><td>213.8</td><td>197.4</td></tr><tr><td>Episode from</td><td>80%</td><td>135.4</td><td>116.3</td><td>83.7</td></tr><tr><td>Small Trained Model</td><td>90%</td><td>210.8</td><td>187.6</td><td>166.1</td></tr><tr><td>Episode from</td><td>80%</td><td>72.1</td><td>64.7</td><td>50.9</td></tr><tr><td>Large Random Model</td><td>90%</td><td>120.6</td><td>112.0</td><td>105.5</td></tr></table>

This is same as what we observe in Sec. 2.1.2. High rewards and high expressiveness state extractors come out together, which imply that holding good representations is necessary for learning good policies.

Table content: <table><tr><td>4.4 PERFORMANCES ON DQN</td><td/></tr><tr><td>Metrics</td><td>Average Last Reward</td></tr><tr><td>#games perform better</td><td>20</td></tr><tr><td>#games perform worse</td><td>9</td></tr><tr><td>#games perform same</td><td>1</td></tr><tr><td colspan="2">Table 2: Performances of 30 Atari</td></tr><tr><td colspan="2">games. Average last reward is the</td></tr><tr><td colspan="2">average model testing reward after</td></tr><tr><td>training over 5 runs.</td><td/></tr></table>

Hyper Parameters Used in A3C Experiments.

Table content: <table><tr><td>Game Name</td><td colspan="2">Rank Regularization Term α</td></tr><tr><td>Alien</td><td>Condition Number</td><td>0.01</td></tr><tr><td>Asteroids</td><td>Condition Number</td><td>0.01</td></tr><tr><td>Berzerk</td><td>Condition Number</td><td>0.01</td></tr><tr><td>Breakout</td><td>Condition Number</td><td>0.01</td></tr><tr><td>CrazyClimber</td><td>Condition Number</td><td>0.01</td></tr><tr><td>DoubleDunk</td><td>Condition Number</td><td>0.01</td></tr><tr><td>IceHockey</td><td>Condition Number</td><td>0.01</td></tr><tr><td>Krull</td><td>Condition Number</td><td>0.01</td></tr><tr><td>MsPacman</td><td>Condition Number</td><td>0.01</td></tr><tr><td>NameThisGame</td><td>Condition Number</td><td>0.01</td></tr><tr><td>Phoenix</td><td>Condition Number</td><td>0.01</td></tr><tr><td>Pong</td><td>Condition Number</td><td>0.01</td></tr><tr><td>RoadRunner</td><td>Condition Number</td><td>0.01</td></tr><tr><td>Robotank</td><td>Condition Number</td><td>0.01</td></tr><tr><td>TimePilot</td><td>Condition Number</td><td>0.01</td></tr><tr><td>WizardOfWor</td><td>Condition Number</td><td>0.01</td></tr><tr><td>Zaxxon</td><td>Condition Number</td><td>0.01</td></tr><tr><td>Frostbite</td><td>Condition Number</td><td>0.0001</td></tr><tr><td>Gopher</td><td>Condition Number</td><td>0.0001</td></tr><tr><td>Hero</td><td>Condition Number</td><td>0.0001</td></tr><tr><td>Bowling</td><td>Condition Number</td><td>0.00001</td></tr><tr><td>KungFuMaster</td><td>Condition Number</td><td>0.00001</td></tr><tr><td>Assault</td><td>Max Minus Min</td><td>0.01</td></tr><tr><td>Asterix</td><td>Max Minus Min</td><td>0.01</td></tr><tr><td>Atlantis</td><td>Max Minus Min</td><td>0.01</td></tr><tr><td>BankHeist</td><td>Max Minus Min</td><td>0.01</td></tr><tr><td>BattleZone</td><td>Max Minus Min</td><td>0.01</td></tr><tr><td>BeamRider</td><td>Max Minus Min</td><td>0.01</td></tr><tr><td>Boxing</td><td>Max Minus Min</td><td>0.01</td></tr><tr><td>ChopperCommand</td><td>Max Minus Min</td><td>0.01</td></tr><tr><td>DemonAttack</td><td>Max Minus Min</td><td>0.01</td></tr><tr><td>Enduro</td><td>Max Minus Min</td><td>0.01</td></tr><tr><td>FishingDerby</td><td>Max Minus Min</td><td>0.01</td></tr><tr><td colspan="2">MontezumaRevenge Max Minus Min</td><td>0.01</td></tr><tr><td>Pitfall</td><td>Max Minus Min</td><td>0.01</td></tr><tr><td>Qbert</td><td>Max Minus Min</td><td>0.01</td></tr><tr><td>Riverraid</td><td>Max Minus Min</td><td>0.01</td></tr><tr><td>Skiing</td><td>Max Minus Min</td><td>0.01</td></tr><tr><td>SpaceInvaders</td><td>Max Minus Min</td><td>0.01</td></tr><tr><td>StarGunner</td><td>Max Minus Min</td><td>0.01</td></tr><tr><td>Tennis</td><td>Max Minus Min</td><td>0.01</td></tr><tr><td>UpNDown</td><td>Max Minus Min</td><td>0.01</td></tr><tr><td>Venture</td><td>Max Minus Min</td><td>0.01</td></tr><tr><td>YarsRevenge</td><td>Max Minus Min</td><td>0.01</td></tr><tr><td>Gravitar</td><td>Negative Nuclear Norm</td><td>1</td></tr><tr><td>Centipede</td><td>Negative Nuclear Norm</td><td>0.1</td></tr><tr><td>Freeway</td><td>Negative Nuclear Norm</td><td>0.1</td></tr><tr><td>Solaris</td><td>Negative Nuclear Norm</td><td>0.1</td></tr><tr><td>VideoPinball</td><td>Negative Nuclear Norm</td><td>0.1</td></tr><tr><td>Amidar</td><td>Negative Nuclear Norm</td><td>0.001</td></tr><tr><td>Kangaroo</td><td>Negative Nuclear Norm</td><td>0.0001</td></tr><tr><td>PrivateEye</td><td>Negative Nuclear Norm</td><td>0.0001</td></tr><tr><td>Seaquest</td><td>Negative Nuclear Norm</td><td>0.0001</td></tr><tr><td>Tutankham</td><td>Negative Nuclear Norm</td><td>0.0001</td></tr><tr><td>Jamesbond</td><td>Negative Nuclear Norm</td><td>0.00001</td></tr></table>

Raw scores and normalized scores for all games in A3C experiments.

Table content: <table><tr><td/><td>Raw</td><td/><td colspan="2">Normalized</td></tr><tr><td>Game Name</td><td>baeline</td><td>rank</td><td>baeline</td><td>rank</td></tr><tr><td>Alien</td><td colspan="2">274.0164 722.1259</td><td>2%</td><td>10%</td></tr><tr><td>Amidar</td><td colspan="2">907.5578 794.7486</td><td>59%</td><td>51%</td></tr><tr><td>Assault</td><td>2555.212</td><td>2673.75</td><td>517%</td><td>543%</td></tr><tr><td>Asterix</td><td colspan="2">1272.168 1002.487</td><td>15%</td><td>11%</td></tr><tr><td>Asteroids</td><td>261.4554</td><td>1061.01</td><td>-2%</td><td>1%</td></tr><tr><td>Atlantis</td><td colspan="4">1337938 2090013 10101% 15837%</td></tr><tr><td>BankHeist</td><td>562.3635</td><td>615.295</td><td>87%</td><td>95%</td></tr><tr><td>BattleZone</td><td>24921.86</td><td>4500</td><td>72%</td><td>3%</td></tr><tr><td>BeamRider</td><td colspan="2">14826.56 15418.49</td><td>99%</td><td>103%</td></tr><tr><td>Berzerk</td><td colspan="2">444.1128 632.8937</td><td>12%</td><td>21%</td></tr><tr><td>Bowling</td><td>29.43</td><td>30</td><td>-5%</td><td>-5%</td></tr><tr><td>Boxing</td><td colspan="2">-49.3083 -8.77755</td><td>-431%</td><td>-66%</td></tr><tr><td>Breakout</td><td>262.8333</td><td>249.875</td><td>993%</td><td>944%</td></tr><tr><td>Centipede</td><td colspan="2">1640.954 5106.617</td><td>-3%</td><td>38%</td></tr><tr><td colspan="2">ChopperCommand 1522.015</td><td>4147.24</td><td>11%</td><td>42%</td></tr><tr><td>CrazyClimber</td><td colspan="2">450.7576 483.6859</td><td>-38%</td><td>-38%</td></tr><tr><td>DemonAttack</td><td colspan="2">2288.795 6179.065</td><td>64%</td><td>185%</td></tr><tr><td>DoubleDunk</td><td>-1.25</td><td>-0.75</td><td>922%</td><td>953%</td></tr><tr><td>Enduro</td><td>10.01563</td><td>7.32</td><td>11%</td><td>11%</td></tr><tr><td>FishingDerby</td><td colspan="2">-10.6449 15.56085</td><td>81%</td><td>113%</td></tr><tr><td>Freeway</td><td colspan="2">32.76923 32.78659</td><td>128%</td><td>128%</td></tr><tr><td>Frostbite</td><td>133.3333</td><td>160</td><td>2%</td><td>2%</td></tr><tr><td>Gopher</td><td colspan="2">2751.741 12247.29</td><td>121%</td><td>582%</td></tr><tr><td>Gravitar</td><td colspan="2">332.663 263.7448</td><td>3%</td><td>1%</td></tr><tr><td>Hero</td><td>302.9514</td><td>37</td><td>-5%</td><td>-6%</td></tr><tr><td>IceHockey</td><td colspan="2">-8.36886 -11.6054</td><td>13%</td><td>-19%</td></tr><tr><td>Jamesbond</td><td colspan="2">888.6883 790.4797</td><td>255%</td><td>226%</td></tr><tr><td>Mean</td><td/><td/><td>485%</td><td>732%</td></tr><tr><td>Median</td><td/><td/><td>15%</td><td>38%</td></tr></table>

Raw scores and normalized scores for all games in DQN experiments.

Table content: <table/>

Peer review (iclr2019):
 The paper aims at characterizing and discussing the impact of the expressivity of a state representation on the performance. It then discusses three possible ways of improving performance with a specific regularization on the state representation. Overall the idea of studying the impact of expressiveness and comparing different ways of ensuring it is interesting. However, some parts in the paper are not well-supported and many important elements to understand the experiments are lacking. Some elements are not well supported and probably not true as stated. "For fixed h, the expressiveness is related to the MDP M: 1) if the transition p(xt+1|xt, at)π(at|xt) of the MDP is not ergodic, i.e., it can only visit a subset of observations, then the matrix {h(X1 ), · · · , h(Xt ), · · · } will more possibly be low rank; 2) if the reward is very sparse, the representation matrix will be low rank." If you compare two MDPs, where the first one has two states and is ergodic, while the second one has many more states but is not ergodic, do you think your consideration still applies? For a given h, why would the sparsity of the reward function plays any role? The paper states that the "method can be widely applied to current DRL algorithms, with little extra computational cost." However, it is not explained clearly how the regularization is enforced. If a supplementary loss is used and minimized at each step, the computational cost is not negligeable. In the experiment section, the protocol is not clear. For instance the coefficient .alpha is apparently set differently for some of the games? How are they chosen? And why are the hyper-parameters chosen not given? "However, as the observation type and the intrinsic reward mechanism vary considerably for each game, we also use some other regularization term and coefficient for some of games." Why are there no details related to the NN architecture? In Table 1, what does it mean "Times Better" and "Times Worse"? Other comments: - In Definition 1, what does it mean X_t .sim .mathcal M? .mathcal M is an MDP, not a distribution. Are the X_t taken following a given policy? are they taken on a given trajectory sequentially or i.i.d.? - (minor) "From the above description, it is easy to see that the performance of an RL agent depends on two parts. First, it depends on whether the state extractor is good. With a good state extractor, the representation which is a depiction of the observation will retain necessary information for taking actions. Second, it depends on the accuracy of the policy: whether the feed-forward model can correctly take the optimal action given the state." Do the two elements in that paragraph mean the same: "A good state extractor provides an abstract representation from which a performant policy can be obtained?" - Figure 2: The name of the ATARI game is not mentioned. - In section 2.2, the MDP framework is introduced (with a state space .mathcal S) but there is no mention of the concept of observation x that is used throughout afterwards. - In the conclusion, it is stated that "Experiments of A3C and DQN on 55 Atari games demonstrate that ExP DRL can promote their performances significantly." However, the algorithm is not tested on 55 games with DQN. - The related work discusses papers about state representation but even more directly related to this paper, other papers have also discussed the importance of disentangled representation or entropy maximization for deep RL: https://arxiv.org/abs/1707.08475, https://arxiv.org/abs/1809.04506, ... And papers that discuss expressiveness in deep learning such as https://arxiv.org/pdf/1606.05336.pdf should also be discussed. - There are many typos/english errors.