Harnessing Structures for Value-Based Planning and Reinforcement Learning
Authors: Yuzhe Yang
Guo Zhang
Zhi Xu
Dina Katabi
Venue:  (2020)
Keywords: Deep reinforcement learning
value-based reinforcement learning

Abstract: Value-based methods constitute a fundamental methodology in planning and deep reinforcement learning (RL). In this paper, we propose to exploit the underlying structures of the state-action value function, i.e., Q function, for both planning and deep RL. In particular, if the underlying system dynamics lead to some global structures of the Q function, one should be capable of inferring the function better by leveraging such structures. Specifically, we investigate the low-rank structure, which widely exists for big data matrices. We verify empirically the existence of low-rank Q functions in the context of control and deep RL tasks. As our key contribution, by leveraging Matrix Estimation (ME) techniques, we propose a general framework to exploit the underlying low-rank structure in Q functions. This leads to a more efficient planning procedure for classical control, and additionally, a simple scheme that can be applied to value-based RL techniques to consistently achieve better performance on "low-rank" tasks. Extensive experiments on control tasks and Atari games confirm the efficacy of our approach.

Published as a conference paper at ICLR 2020
HARNESSING STRUCTURES FOR VALUE-BASED PLANNING AND REINFORCEMENT LEARNING
Yuzhe Yang' Guo Zhang; Zhi Xu; Dina Katabi Computer Science and Artificial Intelligence Lab Massachusetts Institute of Technology (yuzhe, guozhang, zhixu, dk ) @mi t. edu
ABSTRACT
Value-based methods constitute a fundamental methodology in planning and deep reinforcement learning (RI.) In this paper; we propose to exploit the underlying structures the state-action value function, i.c.. Q function, for both planning and deep RL. In particular, if the underlying system dynamics lead to some global structures of the Q function, one should be capable of inferring the function better by leveraging such structures. Specifically, we investigate the low- rank structure, which widely exists for big data matrices. We verify empirically the existence of low-rank Q functions the context of control and deep RL tasks. As our key contribution, by leveraging Matrix Estimation (ME) techniques, we propose a general framework to exploit the underlying low-rank structure in Q functions. This leads to more efficient planning procedure for classical control, and additionally, simple scheme that can be applied to value- RL techniques consistently achieve better performance on "low-rank" tasks. Extensive experiments on control tasks and Atari games confirm the efficacy of our approach.
INTRODUCTION
Value-based methods are widely used in control, planning, and reinforcement learning (Gorodetsky al., 2018; Alora et al., 2016; Mnih al., 2015). To solve Markov Decision Process (MDP), one common method is value iteration, which finds the optimal value function. This process can be done by iteratively computing and updating the state-action value function, represented by Q(s, a) (i.e., the Q-value function). In simple cases with small state and action spaces, value iteration can be ideal for efficient and accurate planning. However, for modern MDPs, the data that encodes the value function usually lies in thousands or millions of dimensions (Gorodetsky et al., 2018 8; 2019), including images in deep reinforcement learning (Mnih et al., 2015; Tassa et al., 2018). These practical constraints significantly hamper the efficiency and applicability of the vanilla value iteration.
Yet, the Q-value function is intrinsically induced by the underlying system dynamics. These dynamics likely to possess some structured forms in various settings, such being governed by partial differential equations. In addition, states and actions may also contain latent features (c.g., similar states could have similar optimal actions). Thus, it is reasonable expect the structured dynamic to impose a structure on the Q-value. Since the Q function can be treated as a giant matrix, with rows as states and columns actions, structured Q function naturally translates to structured Q matrix.
In this work, we explore the low-rank structures. To check whether low-rank Q matrices are common, examine the benchmark Atari games, as well 4 classical stochastic control tasks. As demonstrate in Sections 3 and 4, more than 40 out of 57 Atari games and all control tasks exhibit low-rank Q matrices. This leads us to a natural question: How do leverage the low-rank structure in Q matrices to allow value- based techniques to achieve better performance on "low-rank" tasks?
We propose generic framework that allows for exploiting the low-rank structure in both classical planning and modern deep RL. Our scheme leverages Matrix Estimation (ME), a theoretically guar- anteed framework for recovering low-rank matrices from noisy or incomplete measurements (Chen Chi, 2018) 8). In particular, for classical control tasks, we propose Structured Value-based Planning (SVP). For the Q matrix of dimension |S] AA, at each value iteration, SVP randomly updates small portion of the Q(s, a) and employs ME to reconstruct the remaining elements. We show that
//gi "qqull contribution. Code is available at: ht h/ http//gtttttttt/////////t/.g.t thub. com wttp:///w//y//y////v..

---

Published as a conference paper at ICLR 2020
Apprestmate rank mabri
Meac Squared Brmor
Approsimate rank of mairrx
Mean Squaree Brror
0.0
0.5
0.6
0.0
rank
60
0.4
0.1
20
0.2
0.2
0.0
0.0
100
60 Iteration
200
40 iberation
Lorration
ibcration
(a) Vanilla value iteration (b) Vanilla value iteration (c) Online reconstruction (d) Online reconstruction
Figure 1: The approximate rank and MSE of Q(+) during value iteration. (a) & (b) use vanilla value iteration; (c) (d) use online reconstruction with only 50% observed data each iteration.
planning problems can greatly benefit from such a scheme, where fewer samples (only sample around 20% of (s,a) pairs at each iteration) can achieve almost the same performance as the optimal policy.
For more advanced deep RL tasks, we extend our intuition and propose Structured Value-based Deep RL (SV-RL), applicable for deep Q-value based methods such as DQN (Mnih et al., 2015). Here, instead of the full Q matrix, SV-RL naturally focuses on the "sub-matrix", corresponding to the sampled batch of states at the current iteration. For each sampled Q matrix, again apply ME to represent the deep Q learning target in a structured way, which poses a low rank regularization on this "sub-matrix" throughout the training process, and hence eventually the Q-network's predictions. Intuitively, as learning deep RL policy is often noisy with high variance, if the task possesses low-rank property. this scheme will give clear guidance on the learning space during training, after which better policy can be anticipated. We confirm that SV-RL indeed can improve the performance of various value-based methods on "low-rank" Atari games: SV-RL consistently achieves higher scores on those games. Interestingly, for complex, "high-rank" games, SV-RL performs comparably. ME naturally seeks solutions that balance low rank and a small reconstruction error (cf. Section 3. I). Such balance on reconstruction error helps to maintain or only slightly degrade the performance for "high-rank" situation. We summarize our contributions as follows:
We are the first to propose framework that leverages matrix estimation as a general scheme to exploit the low-rank structures, from planning to deep reinforcement learning.
We demonstrate the effectiveness of our approach on classical stochastic control tasks, where the low-rank structure allows for efficient planning with less computation.
We extend our scheme to deep RL, which is naturally applicable for bisue- techniques. Across a variety of methods, such as DQN, double DQN, and ducling DQN, experimental results all Atari games show that SV-RL can consistently improve the performance of value-based methods, achieving higher scores for tasks when low-rank structures are confirmed to exist.
2 WARM-UP: DESIGN MOTIVATION FROM A TOY EXAMPLE
To motivate our method, let us first investigate a toy example which helps to understand the structure within the Q-value function. We consider a simple deterministic MDP, with 1000 states, 100 actions and deterministic state transition for each action. The reward r(s, a) is randomly generated first for each (s, a) pair, and then fixed throughout. A discount factor 7 0.95 is used. The deterministic nature imposes strong relationship among connected states. In this case, our goal is to explore: (1) what kind of structures the Q function may contain; and (2) how to effectively exploit such structures.
The Low-rank Structure Under this setting, Q-value could be viewed 1000 x 100 matrix. To probe the structure of the Q-value function, we perform the standard Q-value iteration as follows:
((++1((s a) P(ssss,, + max d'eA
(00 (s', ((s,a)eSxA,
(1)
s'ES
where s' denotes the next state after taking action a at state We randomly initialize Q()) In Fig. 1, we show the approximate rank of Qlt) and the mean-square error (MSE) between ((1) and the optimal Q", during each value iteration. Here, the approximate rank is defined as the first singular values (denoted by σ) that capture more than 99% variance of all singular values, i.e.,
Di=1of of 2 0.99. As illustrated in Fig. ((a) and 1(b), the standard theory guarantees the
2

---

Published as a conference paper at ICLR 2020
convergence to Q"; more interestingly, the converged Q" is of low rank, and the approximate rank of Q(0) drops fast. These observations give a strong evidence for the intrinsic low dimensionality of this toy MDP. Naturally, an algorithm that leverages such structures would be much desired.
Efficient Planning via Online Reconstruction with Matrix Estimation The previous results moti- vate us to exploit the structure in value function for efficient planning. The idea is simple:
If the eventual matrix is low-rank, why not enforcing such a structure throughout the iterations? In other words, with the existence of a global structure, we should be capable of exploiting it during intermediate updates and possibly also regularizing the results to be in the same low-rank space. In particular, at each iteration, instead of every (s, a.) pair (i.e., Eq. (I)), we would like to only calculate Q(++1) for some (s, a) pairs and then exploit the low-rank structure to recover the whole Q(+++)) matrix. We choose matrix estimation (ME) as our reconstruction oracle. The reconstructed matrix is often with low rank, and hence regularizing the Q matrix to be low-rank well. We validate this framework in Fig. (c) and (d), where for each iteration, we only randomly sample 50% of the (8, a) pairs, calculate their corresponding ((++1) and reconstruct the whole Q(++1) matrix with ME. Clearly, around 40 iterations, we obtain comparable results to the vanilla value iteration. Importantly, this comparable performance only needs to directly compute 50% of the whole Q matrix at each iteration. It is not hard to see that in general, each vanilla value iteration incurs computation cost of ((S (A))). The complexity of our method however only scales as (pp) S| |2|4| + Oa where p is the percentage of pairs we sample and OME is the complexity of ME. In general, many ME methods employ SVD as subroutine, whose complexity is bounded by ( AAI S) }A (Trefethen & David Bau, 1997). For low-rank matrices, faster methods can have complexity of order linear in the dimensions (Mazumder et al., 2010). In other words, our approach improves computational efficiency, especially for modern high- digensenenii applications. This overall framework thus appears to be successful technique: it exploits the low-rank behavior effectively and efficiently when the underlying task indeed possesses such a structure.
STRUCTURED VALUE-BASED PLANNING
Having developed the intuition underlying our methodology, next provide formal description in Sections 3.1 and 3.2. One natural question is whether such structures and our method are general in more realistic control tasks. Towards this end, provide further empirical support in Section 3.3.
3.1 MATRIX ESTIMATION
ME considers about recovering full data matrix, based on potentially incomplete and noisy observa- tions of its elements. Formally, consider unknown data matrix X E RR and set of observed entries Q. If the observations are incomplete, is often assumed that each entry of X is observed independently with probability p E (0, 1]. In addition, the observation could be noisy, where the noise is assumed to be mean zero. Given such an observed set Ω the goal of ME is to produce an estimator M so that || - X| = O, under an appropriate matrix norm such as the Frobenius norm.
The algorithms in this field are rich. Theoretically, the essential message is: exact or approximate recovery of the data matrix X is guaranteed if X contains some global structure (Candès & Recht, 2009; Chatterjee et al., 2015; Chen Chi, 2018). In the literature, most attention has been focusing on the low-rank structure of matrix. Correspondingly, there are many provable, practical algorithms to achieve the desired recovery. Early convex optimization methods (Candès & Recht, 2009) seek to minimize the nuclear norm, || ||, of the estimator. For example, fast algorithms, such as the Soft- Soft-Impute algorithm (Mazumder et al., 2010) solves the following minimization problem:
min MERKKm
(Mr - x.;) + |||M (UJ)
Σ
(2)
Since the nuclear norm ||. favor solutions that are with small reconstruction errors and in the meantime being relatively low-rank, which are desirable for our applications. Apart from convex optimization, there are also spectral methods and even non-convex optimization approaches (Chatterjee et al., 2015; Chen & Wainwright, 2015; Ge et al., 2016). In this paper, we view ME as a principled reconstruction oracle to effectively exploit the low-rank structure. For faster computation, mainly employ the Soft-Impute algorithm.
||- is a convex relaxation of the rank, the convex optimization approaches
3

---

Published as a conference paper at ICLR 2020
Next Hemmiion
State-uction
Reconstructed value function
Incomplete observation
value function
Sample
Compute
Reconstruct
Q
ia
Q
Figure 2: An illustration of the proposed SVP algorithm for leveraging low-rank structures.
3.2 OUR APPROACI: STRUCTURED VALUE-BASED PLANNING
We now formally describe our approach, which we refer as structured value-basee planning (SVP). Fig. 2 illustrates overall approach for solving MDP with known model. The approach is based on the Q-value iteration. At the 1-th iteration, instead of a full pass over all state-action pairs:
1. SVP first randomly selects subset Ω of the state-action pairs, In particular, each state-action pair S x A observed (i.e., included in Q) independently with probability p.
For each selected (s, a), the intermediate Q(s, a) computed based on the Q-value iteration:
((s,a) a) + Σ P(s (r(s, a) + max
A (s.a) E
3. The current iteration then ends by reconstructing the full Q matrix with matrix estimation, from the set of observations in Q. That is, ((++1) = MB(( a) (s.))e))
Overall, each iteration reduces the computation cost by roughly 1 p (cf. discussions in Section 2). In Appendix A, we provide the pseudo-code and additionally, a short discussion on the technical diffieulty for theoretical analysis. Nevertheless, believe that the consistent empirical benefits, as will be demonstrated, offer a sound foundation for future analysis.
3.3 EMPIRICAL EVALUATION ON STOCHASTIC CONTROL TASKS
We empirically evaluate our approach on several classical stochastic control tasks, including the Inverted Pendulum, the Mountain Car, the Double Integrator, and the Cart-Pole. Our objective is to demonstrate, as in the toy example, that the optimal Q" has a low-rank structure, then the proposed SVP algorithm should be able to exploit the structure for efficient planning. We present the evaluation on Inverted Pendulum, and leave additional results on other planning tasks in Appendix B and C.
Inverted Pendulum In this classical continuous task, goal is to balance inverted pendulum to its upright position, and the performance metric is the average angular deviation. The dynamics is described by the angle and the angular speed, i.e., (0, 0), and the action a is the torque applied. We discretize the task to have 2500 states and 1000 actions, leading 2500 1000 Q-value matrix. For different discretization scales, we provide further results in Appendix G.I.
The Low-rank Structure We first verify that the optimal Q" indeed contains the desired low-rank structure. We run the vanilla value iteration until it converges. The converged Q matrix is found to have approximate rank of 7. For further evidence, in Appendix C, we construct "low-rank" policies directly from the converged Q matrix, and show that the policies maintain the desired performance.
The SVP Policy Having verified the structure, would expect our approach be effective. To this end, we apply SVP with different observation probability and fix the overall number of iterations to be the same as the vanilla Q-value iteration. Fig. 3 confirms the success of our approach. Fig. 3(a), 3(b) and 3(c) show the comparison between optimal policy and the final policy based on SVP. We further illustrate the performance metric, the average angular deviation, Fig. 3(d). Overall, much fewer samples are needed for SVP to achieve a comparable performance to the optimal one.
4 STRUCTURED VALUE-BASER DEEP REINFORCEMENT LEARNING
So far, our focus has been on tabular MDPs where value iteration can be applied straightforwardly. However, the idea of exploiting structure is much more powerful: propose natural extension of
4

---

Published as a conference paper at ICLR 2020
Optindl palis
(63% aleavell
SVP pokry (2Ai) cleaned)
Average: deviation (dogroc)
Pendulum
Optimal policy
--- SVP policy
mLRdA sood
60
100
Percentage
(a)
(b)
(c)
(d)
Figure 3: Performance comparison between optimal policy and the proposed SVP policy.
approach to deep RI.. Our scheme again intends exploit and regularize structures in the Q-value function with ME. As such, it can be seamlessly incorporated into malue-based RI. techniques that include Q-network. We demonstrate this on Atari games, across various value-based RL techniques.
4.1 EVIDENCE OF STRUCTURED Q-VALUE FUNCTION
Before diving into deep RL, let us step back and review the process we took to develop our intuition. Previously, start by treating the Q-value certain MDPs have essentially a low-rank Q" We argue that if this is indeed the case, then enforcing the low-rank structures throughout the iterations, by leveraging ME, should lead better algorithms.
matrix. To exploit the structure, first verify that
naive extension of the above reasoning to deep RI. immediately fails. In particular, with images as states, the state space is effectively infinitely large, leading a tall Q matrix with numerous number of rows (states). Verifying the low-rank structure for deep RL hence seems intractable. However, by definition, if a large matrix is low-rank, then almost any row is linear combination of some other rows. That is. if we sample small batch of the rows, the resulting matrix is most likely low-rank as well. To probe the structure of the deep Q function, it is, therefore, natural understand the rank of randomly sampled batch of states. In deep RL, our target for exploring structures is no longer the optimal Q", which is never available. In fact, like SVP, the natural objective should the converged values of the underlying algorithm, which in "deep" scenarios, are the eventually learned Q function.
With the above discussions, we now provide evidence for the low-rank structure of learned Q function on some Atari games. We train standard DQN on 4 games, with batch size of 32. To be consistent, the 4 games all have 18 actions. After the training process, we randomly sample a batch of 32 states, evaluate with the learned network and finally synthesize them into matrix. That is, 32 x 18 data matrix with rows the batch of states, the columns the actions, and the entries the values from the learned Q network. Note that the rank of such matrix is at most 18. The above process is repeated for 10,000 times, and the histogram and empirical CDF of the approximate rank is plotted in Fig. 4. Apparently, there is strong evidence supporting highly structured low-rank Q function for those games - the approximate ranks are uniformly small; in most cases, they are around or smaller than 3.
Defender
Knull
Roveraadd
Zaczon
100
103
1.00
100
Percentage (84
60
63
50
60
10
23
20
20
rank
raank
runk
zank
Figure 4: Approximate rank of different Atari games: histogram (red) and empirical CDF (blue).
4.2 OUR APPROACH: STRUCTURED VALUE-BASED RL
Having demonstrated the low-rank structure within some deep RL tasks, naturally seek approaches that exploit the structure during the training process. We extend the same intuitions here: eventually, the leamned Q function is of low rank, then enforcing/regulariiing the low rank structure for each iteration of the learning process should similarly lead to efficient learning and potentially better performance. In deep RI,, each iteration of the learning process is naturally the SGD step where one
5

---

Published as a conference paper at ICLR 2020
Target
SGD with loss
yuux, Ossl..
2 (y a0)""""0))"
Q( A)
(a) Original value-based RI.
6
Tanget
SGD with loss Ers (vD 2u. .2)
Sample
Reconstmct
yo tymas C thi
())
Q
(Sp.AA))
(b) SV-RL
Figure 5: An illustration of the proposed SV-RL scheme, compared to the original value-based RL..
would update the Q network. Correspondingly, this suggests us to harness the structure within the batch of states. Following our previous success, we leverage ME to achieve this task.
now formally describe our approach, referred as structured value-based RL (SV-RL). exploits the structure for the sampled batch at each SGD step, and can be easily incorporated into any Q-value based RL methods that update the Q network via a similar step as in Q-learning. In particular, Q-value based methods have common model update step via SGD, and only exploit structure of the sampled batch at this step - the other details pertained to each specific method are left intact.
Precisely, when updating the model via SGD, Q-value based methods first sample batch of B transitions, {(s (8) (6) (4)
[ and form the following updating targets:
y() r( + max Q (5
For example, DQN, Q the target network. The Q network then updated by taking a gradient step for the loss function Eí (y (s) (0) 0))² with respect to the parameter 6.
To exploit the structure, then consider reconstructing a matrix Q' from Q, via ME. The recon- structed Qt will replace the role of Q in Eq. (3) form the targets ( for the gradient step. In particular, the matrix Qt has a dimension of B x |A), where the rows represent the "next states" (i)
{s == in the batch, the columns represent actions, and the entries are reconstructed values. Let SB A (1-1// The SV-RL alters the SGD update step as illustrated in Algorithm and Fig.
Algorithm 1: Structured Value- RL (SV-RL)
follow the chosen value-based RL method (e.g., DQN) usual.
2: except that for model updates with gradient descent, do
3: /* exploit st struturre via matrix estimations/
4: sample a set Ω of state-action pairs from Sg x A. In particular, each state-action pair in
SB A is observed (i.e., included in !) with probability p. independently.
5: evaluate every state-action pair in Ω via Q, where Q is the network that would be used to form the targets {v( ( in the original 6: based on the evaluated values, reconstruct matrix Qt with ME, i.c.
methods (cf. Eq. (3)).
Qt ME((Q(s, (sssss)))))) ().GEE))))
7: /+ new targets with reconstructed Q! for the gradient step+/
8: replace Q in Eq. (3) with Qt evaluate the targets (
SV-RL Targets: y ri (i) max Q (s(
(4)
9: update the Q network with the original targets replaced by the SV-RL targets.

---

Published as a conference paper at ICLR 2020
Note the resemblance of the above procedure to that of SVP in Section 3.2. When the full Q matrix available, in Section 3.2, we sub-sample the Q matrix and then reconstruct the entire matrix. When only a subset of the states (i.e., the batch) is available, naturally, we look the corresponding sub-matrix the entire Q matrix, and seek to exploit its structure.
4.3 EMPIRICAL EVALUATION WITH VARIOUS VALUE-BASER METHODS
Experimental Setup We conduct extensive experiments on Atari 2600. We apply SV-RL on three representative value-based RL techniques, i.e., DQN, double DQN and dueling DQN. We fix the total number of training iterations and set all the hypee--paameters to be the same. For each experiment, averaged results across multiple runs are reported. Additional details are provided in Appendix D.
Consistent Benefits for "Structured" Games We present representative results of SV-RL applied to the three value-based deep RL techniques in Fig. 6. These games are verified by method mentioned in Section 4.1 to be low-rank. Additional results all Atari games provided in Appendix E. The figure reveals the following results. First, games that possess structures indeed benefit from approach, earning mean rewards that are strictly higher than the vanilla algorithms across time. More importantly, we observe consistent improvements across different value-based RL techniques. This highlights the important role of the intrinsic structures, which are independent of the specific techniques, and justifies the effectiveness of our approach in consistently exploiting such structures.
Further Observations Interestingly however, the performance gains vary from games games. Specifically, the majority of the games can have benefits, with few games performing similarly or slightly worse. Such observation motivates us further diagnose SV-RL in the next section.
7acoon
DCN
DO% sepo
Avcraee scora
500
500
0530
cCap entt
5060
300
0000
100
JU60
0.70
0225
0350
1.00
800
022
0.00
133
Breakout
Frostbite
Krrff
Zacoon
430
Couble
Double dol Dicke
DCN
Couble
Couble
Couble 200
Aucragescee
000
1000
1000
62.01
-20
200
0.50
0.25
0.50
8.75
1.30
655
0.5
3.35
0.00
322
Breakout
Prostbilc
Crull
Zo0xon
boN
D0N
00.00
Cool bow
Lood exparso
Dualkt ccateest
7000
Averoiee s0ore
6200
5000
4000
200
6.0
0.2
0200
0075
1.00
D20
0.25
0.75
1.00
0.00
025
322
3.55
1.00
step
Figure 6: Results of SV-RL on various value-based deep RL techniques. First row: results on DQN.
Second row: results on double DQN. Third row: results on ducling DQN.
DIAGNOSE AND INTERPRET PERFORMANCE IN DEEP RL
So far, we have demonstrated that games which possess structured Q-value functions can consistently benefit from SV-RL. Obviously however, not all tasks in deep RL would possess such structures. As such, we seek to diagnose and further interpret our approach at scale.
Diagnosis We select 4 representative examples (with 18 actions) from all tested games, in which SV-RL performs better on two tasks (i.e., FROSTBITE and KRULL), slightly better on one task (i.c., ALIEN), and slightly worse the other (i.e., SEAQUEST). The intuitions developed in Section
7

---

Published as a conference paper at ICLR 2020
incentivize us to further check the approximate rank of each game. As shown in Fig. 7, in the two better cases, both games are verified to be approximately low-rank (~~ 2). while the approximate rank in ALIEN is moderately high (~ 5). and even higher in SEAQUEST (~ 10).
Consistent Interpretations As our approach is designed to exploit structures, we would expect to attribute the differences in performance across games to the "strength" of their structured properties. Games with strong low-rank structures tend to have larger improvements with SV-RL (Fig. 7(a) and 7(b)), while moderate approximate rank tends induce small improvements (Fig. 7(c)), and high approximate rank may induce similar or slightly worse performances (Fig. 7(d). The empirical results are well aligned with our arguments: the Q-function for the task contains low-rank structure, SV-RL can exploit such structure for better efficiency and performance: if not, SV-RL may introduce slight or no improvements over the vanilla algorithms. As mentioned, the ME solutions balance being low rank and having small reconstruction error, which helps to ensure reasonable or only slightly degraded performance, even for "high rank" games. We further observe consistent results on ranks vs. improvement across different games and RL techniques in Appendix E, verifying our arguments.
Looe DDN
1890
DDei
vine
3500
2000
3X0
a00e
3800
3000
100
2.0412
32
0:25
0.90
6.75
0.00
0.25
6:50
675
3:5
2.24
0.25
0.30
6.75
03
80
80
80
03
40
40
40
20
rank
(a) Frostbite (better)
(b) Krull (better)
(c) Alien (slightly better)
(d) Seaquest (worse)
Figure 7: Interpretation of deep RL results. We plot games where the SV-based method performs
differently, More structured games (with lower rank) achieve better performance with SV-RL.
6 RELATED WORK
Structures in Value Function Recent work in the control community starts to explore the structure of value function in control/planning tasks (Ong, 2015; Alora al., 2016; Gorodetsky et al., 2015; 2018). These work focuses on decomposing the value function and subsequently operating on the reduced-order space. In spirit, we also explore the low-rank structure in value function. The central difference is that instead of decomposition, we focus on "completion". We seek to efficiently operate on the original space by looking at few elements and then leveraging the structure to infer the rest, which allows us to extend our approach to modern deep RL. In addition, while there few attempts for basis function learning in high dimensional RL (Liang et al., 2016), functions are hard to generate in many cases and approaches based basis functions typically do not get the same performance as DQN, and do not generalize well. In contrast, we provide a principled and systematic method, which can be applied to any framework that employs value-based methods or sub-modules. Finally, we remark that at higher level, there are studies exploiting different structures within a task to design effective algorithms, such as exploring the low-dimensional system dynamics in predictive state representation (Singh et al., 2012) or exploring the so called low "Bellman rank" property (Jiang et al., 2017). We provide additional discussions in Appendix
Value- Deep RL Deep RL has emerged as promising technique, highlighted by key successes such as solving Atari games via Q-learning (Mnih et al., 2015) and combining with Monte Carlo tree search (Browne et al., 2012; Shah et al., 2019) to master Go, Chess and Shogi (Silver et al., 7a;b). Methods based on learning value functions are fundamental components in deep RL, exemplified by the deep Q-network (Mnih et al., 2013; 2015). Over the years, there has been a large body of literature on its variants, such as double DQN (Van Hasselt et al., 2016), dueling DQN (Wang et al., 2015), IQN (Dabney al., 2018) and other techniques that aim to improve exploration (Osband et al., 2016; Ostrovski et al., 2017). Our approach focuses on general specific algorithms. As long as the method has similar model update step as in Q Q-learning our
RL methods, rather than
8

---

Published as a conference paper at ICLR 2020
approach can leverage the structure to help with the task. We empirically demonstrate that deep RL tasks that have structured value functions indeed benefit from our scheme.
Matrix Estimation ME is the primary tool we leverage to exploit the low-rank structure in value functions. Early work in the field is primarily motivated by recommendation systems. Since then, the techniques have been widely studied and applied different domains (Abbe & Sandon, 2015; Borgs et al., 2017), and recently even robust deep learning (Yang et al., 2019). The field is relatively mature, with extensive algorithms and provable recovery guarantees for structured matrix (Davenport & Romberg, 2016; Chen & Chi, 2018). Because of the strong promise, we view ME as a principled reconstruction oracle exploit the low-rank structures within matrices.
7 CONCLUSION
We investigated the structures in value function, and proposed complete framework to understand, validate, and leverage such structures in various tasks, from planning to deep reinforcement learning. The proposed SVP and SV-RL algorithms harness the strong low-rank structures in the Q function, showing consistent benefits for both planning tasks and value-based deep reinforcement learning techniques. Extensive experiments validated the significance of the proposed schemes, which can be easily embedded into existing planning and RL frameworks for further improvements.
ACKNOWLEDGMENTS
The authors would like to thank Luxin Zhang, the members of NETMIT and CSAIL, and the anonymous reviewers for their insightful comments and helpful discussion. Zhi Xu is supported by the Siemens FutureMakers Fellowship.
REFERENCES
Emmanuel Abbe and Colin Sandon. Community detection in general stochastic block models: Fundamental limits and efficient algorithms for recovery. In Foundations of Computer Science (FOCS), 2015 IEEE 56th Annual Symposium on, pp. 670-688. IEEE, 2015.
John Irvin Alora, Alex Gorodetsky. Sertac Karaman, Youssef Marzouk, and Nathan Lowry. Auto- mated synthesis of low-rank control systems from sc-ltl specifications using tensor-trasd traii decompo- sitions. In 2016 IEEE 55th Conference on Decision and Control (CDC), pp. 1131-1138 IEEE, 2016.
Pierre-Luc Bacon, Borja Balle, and Doina Precup. Learning and planning with timing information in markov decision processes. Proceedings of the Thirty-First Conference on Uncertainty in Artificial Intelligence, 2015.
Andrew Barto, Richard S Sutton, and Charles W Anderson. Neuronlike adaptive elements that can solve difficult learning control problems. IEEE transactions systems, man, and cybernetics, pp. 834 846, 1983.
Byron Boots, Sajid M Siddiqi, and Geoffrey J Gordon. Closing the learning-planninn loop with predictive state representations. The International Journal of Robotics Research, 30(7):954-966, 2011.
Christian Borgs, Jennifer Chayes, Christina E Lee, and Devavrat Shah. Thy friend is my friend: Iterative collaborative filtering for sparse matrix estimation. In Advances in Neural Information Processing Systems, pp. 4715-4726, 2017.
Cameron B Browne, Edward Powley, Daniel Whitehouse, Simon M Lucas, Peter Cowling, Philipp Rohlfshagen, Stephen Tavener, Diego Perez, Spyridon Samothrakis, and Simon Colton. A survey of monte carlo tree search methods. IEEE Transactions on Computational Intelligence and in games, 4(1):1-43, 2012.
Daniele Calandriello, Alessandro Lazaric, and Marcello Restelli. Sparse multi-tast reinforcement learning. In Advances in Neural Information Processing Systems, pp. 819-827, 2014.

---

Published as a conference paper at ICLR 2020
Emmanuel J Candès and Benjamin Recht. Exact matrix completion via convex optimization. Foun- dations of Computational mathematics, 96)):11, 2009.
Sourav Chatterjee et al. Matrix estimation by universal singular value thresholding. The Annals of Statistics, 43(1):1772214, 2015.
Yudong Chen and Yuejie Chi. Harnessing structures in big data via guaranteed low-rank matrix estimation. arXiv preprint 1xXv::882..08397, 2018.
Yudong Chen and Martin Wainwright. Fast low-rank estimation by projected gradient descent: General statistical and algorithmic guarantees. arXiv preprint arXiv: 2015.
Will Dabney, Georg Ostrovski, David Silver, and Rémi Munos. Implicit quantile networks for distributional reinforcement learning. arXiv preprint
2018.
Mark Davenport and Justin Romberg. An overview of low-rank matrix recovery from incomplete observations. arXiv preprint arXiv:1601.06422) 2016.
Lijun Ding and Yudong Chen. The lcave-one-out approach for matrix completion: Primal and dual analysis. arXiv preprint arXiv: 2018.
Jianqing Fan, Weichen Wang, and Yiqiao Zhong. An fx eigenvector perturbation bound and its application to robust covariance estimation. arXiv preprint arXiv: 2016.
Rong Ge, Jason D Lee, and Tengyu Ma. Matrix completion has spurious local minimum. In Advances in Neural Information Processing Systems. pp. 2973-2981, 2016.
Alex Gorodetsky, Sertac Karaman, and Youssef Marzouk. High-dimensional stochastic optimal control using continuous tensor decompositions. The International Journal of Robotics Research, 37(2-3):34-3377220 2018.
Alex Gorodetsky. Sertac Karaman, and Youssef Marzouk. continuous analogue of the tensor-trait decomposition. Computer Methods in Applied Mechanics and Engineering, 347:59-84 2019.
Alex Gorodetsky, Sertac Karaman, and Youssef M Marzouk. Efficient high-dimensional stochastic optimal motion control using tensor-train decomposition. In Robotics: Science and Systems, 2015.
Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, John Langford, and Robert E Schapire. Con- textual decision processes with low bellman rank are pac-learnable. In Proceedings of the 34th International Conference Machine Learning-Volun Volume 70, pp. 1704-1713, 2017.
Simon J Julier and Jeffrey K Uhlmann. Unscented filtering and nonlinear estimation. Proceedings of the IEEE, 92(3):401-40) 422,, 2004.
Diederik P Kingma and Jimmy Ba. Adam: method for stochastic optimization. arXiv preprint 1rX1v:1412.6980 2014.
Yitao Liang, Marlos C Machado, Erik Talvitie, and Michael Bowling. State of the control of atari games using shallow reinforcement learning. In Proceedings of the 2016 International Conference on Autonomous Agents Multiagent Systems. pp. 485-495 493. International Foundation for Autonomous Agents and Multiagent Systems, 2016.
Rahul Mazumder, Trevor Hastie, and Robert Tibshirani. Spectral regularization algorithms for learning large incomplete matrices. Journal of machine learning research, 11(Aug)2287-2332. 2010.
H Brendan McMahan, Maxim Likhachev, and Geoffrey Gordon. Bounded real-time dynamic programming: Rtdp with monotone upper bounds and performance guarantees. In Proceedings of the 22nd international conference on Machine learning. 569-576, 2005.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Alex Graves, Ioannis Antonoglou, Daan Wierstra, and Martin Riedmiller. Playing atari with deep reinforcement learning. arXiv preprint 132.5623 2013.
10

---

Published as a conference paper at ICLR 2020
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Mare G Bellemare, Alex Graves, Martin Riedmiller, Andreas Fidjeland, Georg Ostrovski, et al. Human-level control through deep reinforcement learning, Nature, 5 518(7540):529, 2015.
Hao Yi Ong. Value function approximation via low-rank models. arXiv preprint arXiv:150900000 2015.
Sylvie CW Ong, Yuri Grinberg, and Joelle Pineau. Goal-directed online learning of predictive models. In European Workshop on Reinforcement Learning, pp. 18 29. Springer, 2011.
Ian Osband, Charles Blundell, Alexander Pritzel, and Benjamin Van Roy. Deep exploration via bootstrapped dqn. In Advances in neural information processing systems, pp. 60226-4334 2016.
Georg Ostrovski, Marc G Bellemare, Aäron van den Oord, and Rémi Munos. Count-based exploration with neural density models. In Proceedings of the 34th International Conference on Machine Learning-Volene Volume 70, pp. 2721-2730. JMLR. org. 2017.
Wei Ren and Randal Beard. Consensus algorithms for double-integrator dynamics. Distributed Consensus in Mulli-vehicle Cooperative Control: Theory and Applications, pp. 77-104, 2008
Devavrat Shah, Qiaomin Xie, and Zhi Xu. On reinforcement learning using monte carlo tree search with supervised learning: Non-asymptotic analysis. arXiv preprint 1rXiv:1902.055
2019.
David Silver, Thomas Hubert, Julian Schrittwieser, Ioannis Antonoglou, Matthew Lai, Arthur Guez, Mare Lanctot, Laurent Sifre, Dharshan Kumaran, Thore Graepel, al. Mastering chess and shogi by self-play with a general reinforcement learning algorithm. arXiv preprint arXiv:1712.01815 2017a.
David Silver, Julian Schrittwieser, Karen Simonyan, Ioannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton, et al. Mastering the game of go without human knowledge. Nature, 550(7676):354-33) 2017b.
Satinder Singh, Michael James, and Matthew Rudary. Predictive state representations: A new theory for modeling dynamical systems. arXiv preprint arXiv: arXiv: 120..4167 2012.
Trey Smith and Reid Simmons. Focused real-time dynamic programming for mdps: Squeezing more out of a heuristic. In AAAI, pp. 1227-1232, 2006.
Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
Yuval Tassa, Yotam Doron, Alistair Muldal, Tom Erez, Yazhe Li, Diego de Las Casas, David Budden, Abbas Abdolmaleki, Josh Merel, Andrew Lefrancq, et al. Deepmind control suite. arXiv preprint 1rXiv:1801.00690 2018.
Russ Tedrake. Underactuated robotics: Algorithms for walking, running, swimming, flying, and manipulation. Course Notes for MIT 6.832, 2019. URL http:://nnderretuuteed mit. edu/.
Lloyd N Trefethen and III David Bau. Numerical linear algebra. Society for Industrial and Applied Mathematics (SIAM), 1997.
Hado Van Hasselt, Arthur Guez, and David Silver. Deep reinforcement learning with double q- learning. In Thirtieth AAAI Conference on Artificial Intelligence, 2016.
Ziyu Wang, Tom Schaul, Matteo Hessel, Hado Van Hasselt, Mare Lanctot, and Nando De Freitas. Dueling network architectures for deep reinforcement learning. arXiv preprint 111.005111.0681, 2015.
Yuzhe Yang, Guo Zhang, Dina Katabi, and Zhi Xu. ME-Net: Towards effective adversarial robustness with matrix estimation. Proceedings of the 36th International Conference on Machine Learning (ICML), 2019.
11

---

Published as a conference paper at ICLR 2020
A PSEUDO CODE AND DISCUSSIONS FOR STRUCTURED VALUE-BASED PLANNING (SVP)
Algorithm 2: Structured Value-based Planning (SVP)
1: Input: initialized value function (s, a) and prescribed observing probability p.
2: for = 1, 2, 3.... do
3: randomly sample a set Ω of observed entries from S x A, each with probability
4: /* update the randomly selected state-action pairs*/
5: for each state-action pair (s, a) E do
6:
Q(s,a)+ + P(o(ss, (r(s, + max Q7 (s',
7: end for
8: reconst the Q matrix via matrix estimationn/
9:
apply matrix completion to the observed values {Ô(s, as to reconstruct Q(++1);
Q(++1) (M(((((s.))))
10:
end for
While based on classical value iteration, we remark that theoretical analysis, even in the tabular case, is quite complex. (1) Although the field of ME is somewhat mature, the analysis has been largely focused on the "one-shot" problem: recover static data matrix given one incomplete observation. Under the iterative scenario considered here, standard assumptions warrants potentially new machinery. (2) Furthermore, much of the effort in the ME community has been devoted to the Frobenius norm guarantees rather than the infinite norm in value iteration. Non-trivial infinite norm bound has received less attention and often requires special techniques (Ding & Chen, 2018; Fan al., 2016). Resolving the above burdens would be important future avenues in its own right for the ME community. Henceforth, this paper focuses on empirical analysis and more importantly, generalizing the framework successfully to modern deep RL contexts. As we will demonstrate, the consistent empirical benefits offer sounding foundation for future analysis.
easily broken and the analysis
B EXPERIMENTAL SETUP OF STOCHASTIC CONTROL TASKS
Inverted Pendulum As stated earlier in Sec. 3.3, the goal balance the inverted pendulum on the upright equilibrium position. The physical dynamics of the system is described by the angle and the angular speed, i.e., (6, 6). Denote 7 as the time interval between decisions, u as the torque input on the pendulum, the dynamics can be written as (Ong, 2015; Sutton & Barto, 2018):
0 == 0 + 0 T,
(5)
Ú= 0 + sin 0 0 +u)
(6)
reward function that penalizes control effort while favoring an upright pendulum is used:
r(0, u) 1. + exp (cos 0 1).
In the simulation, the state space is (- T for 0 and [-10, 10] for Ó. We limit the input torque in [-1, 1] and set T = 0.3. We discretize each dimension of the state space into 50 values, and action space into 1000 values, which forms an Q-value function matrix of dimension 2500 x 1000. We follow (Julier Uhlmann, 2004) to handle the policy of continuous states by modelling their transitions using multi-lineas interpolation.
Mountain Car We select another classical control problem, i.e., the Mountain Car (Sutton & Barto, 20,8), for further evaluations. In this problem, an under-powered car aims to drive up a steep hill (Sutton & Barto, 2018). The physical dynamics of the system is described by the position and the
12

---

Published as a conference paper at ICLR 2020
velocity, i.., (z. Denote u as the acceleration input the car, the dynamics can be written as
x == x + d;, क == ã - 0.0025 cos (3x) + 0.001u.
(8)
(9)
The reward function is defined to encourage the car to get onto the top of the mountain at 20 0.5:
10, x 2 I0,
7(x)
(10)
-1,
else.
We follow standard settings to restrict the state space as [-0.07, 0.07] for and [-1.2, 0.6] for é and limit the input u E 1]. Similarly, the whole state space is discretized into 2500 values, and the action space is discretized into 1000 values. The evaluation metric we are concerned about is the total time it takes to reach the top of the mountain, given randomly and uniformly generated initial state.
Double Integrator We consider the Double Integrator system (Ren & Beard, 2008), as another classical control problem for evaluation. In this problem, a unit mass brick moving along the r-axis on a frictionless surface, with a control input which provides a horizontal force, u (Tedrake, 2019). The task is to design a control system to regulate this brick to x [0, 0j² The physical dynamics of the system is described by the position and the velocity (i.c., (z, i)), and can be derived as
= -
(11)
(12)
Follow Tedrake (2019), we use the quadratic cost formulation to define the reward function, which regulates the brick to [0,0]":
rlx x) xx,
(x² + x²)
(13)
We follow standard settings to restrict the state space as [-3,3] for both x and i, limit the input [] and set 7 0.1. The whole state space discretized into 2500 values, and the action space is discretized into 1000 values. Similarly, we define the evaluation metric as the total time it takes to reach to x [0, 0]",, given a randomly and uniformly generated initial state.
Cart-Pole Finally, we choose the Cart-Pole problem (Barto et al., 1983), harder control problem with 4-dimensional state space. The problem consists a pole attached to cart moving on a frictionless track. The cart can be controlled by means of a limited force within 10N that is possible to apply both to the left or to the right of the cart. The goal is to keep the pole on the upright equilibrium position. The physical dynamics of the system is described by the angle and the angular speed of the time interval
the pole, and the position and the speed of the cart, i... (0, 0, x, ž). Denote between decisions, u as the force input on the cart, the dynamics can be written as
Ø = g sin
24 m sin COs 0
+m
(14)
(
m cos &
m.
8 + ml (2 sin 0 - 0 cOS 0
(15)
m. +
0 = 0 + 0T,
(16)
0 = 0 0 T,
(17)
J x + i T,
(18)
;: i + i T
(19)
where g = 9.8m//² corresponds to the gravity acceleration, m. 1kg denotes the mass of the cart, m = k. denotes the mass of the pole, 1 = 0.5m is half of the pole length, and u corresponds to the force applied to the cart, which is limited by u E [-10, 10).
A reward function that favors the pole in an upright position, i.c., characterized by keeping the pole 12x is expressed as
in vertical position between [0]
T80
r(0) cos (150).
(20)
13

---

Published as a conference paper at ICLR 2020
In the simulation, the state space is | for 0. [-3, 3] for 0. 2-444 for and 3-3.5.3.5] for E. We limit the imput force in [-10, 10] and set T = 0.1. We discretize each dimension the state space into 10 values, and action space into 1000 values, which forms an Q-value function matrix of dimension 10000 x 1000.
C ADDITIONAL RESULTS FOR SVP
C.I INVERTED PENDULUM
We further verify that the optimal Q" indeed contains the desired low-rank structure. To this end, we construct "low-rank" policies directly from the converged Q matrix. In particular, for the converged Q matrix. we sub-sample a certain percentage of its entries, reconstruct the whole matrix via ME, and finally construct a corresponding policy. Fig. 8 illustrates the results, where the policy heatmap as well as the performance (i.e., the angular error) of the "low-rank" policy is essentially identical to the optimal one. The results reveal the intrinsic strong low-rank structures lie in the Q-value function.
We provide additional results for the inverted pendulum problem. We show the policy trajectory (i.e., how the angle of the pendulum changes with time) and the input changes (i.e., how the input torque changes with time), for each policy.
Optimal polcy
"Low makk' polier 130% clucrvod)
Inverted Pendulom
- Optimal policy
"Low-rank"
padi aqui
Average devtatton
20
40
80
100
Angle
Percentage (%)
(a)
(b)
(c)
Figure 8: Performance comparison between optimal policy and the reconstructed "low-rank" policy.
Optitaal majestory
Optizal input
"Lmw-rank" trujectory (3096)
"Low-ranik" isput (30%)
Angle (deg)
time
(a) Optimal policy
(b) "Low-rank" policy with 50% observed data
Figure 9: Comparison of the policy trajectories and the input torques between the two schemes.
In Fig. 9, we first show the comparison between the optimal policy and "low-rank" policy. Recall that the low-rank policies are directly reconstructed from the converged Q matrix, with limited observation of a certain percentage of the entries in the converged Q matrix. As shown, the "low-rank" policy performs nearly identical to the optimal one, in terms of both the policy trajectory and the input torque changes. This again verifies the strong low-rank structure lies in the Q function.
Further, we show the policy trajectory and the input torque changes of the SVP policy. We vary the percentage of observed data for SVP, and present the policies with 20% and 60% for demonstration. As reported in Fig. 10, the SVP policies are essentially identical to the optimal one. Interestingly, when we further decrease the observing percentage to 20%, the policy trajectory vibrates a little bit, but can still stabilize in the upright position with small average angular deviation < 5
14

---

Published as a conference paper at ICLR 2020
SVP trajectory (00%)
SVP zaput (00%)
SVP trajectary (2096)
SVP input (218)
A008 (dog)
aanee (doo))
Iapat
47
(a) SVP policy with 60% observed data
(h) SVP policy with 20% observed data
Figure 10: The policy trajectories and the input torques of the proposed SVP scheme.
C.2 MOUNTAIN CAR
Similarly, we first verify the optimal Q" contains the desired low-rank structure. We the same approach to generate "low-rank" policy based on the converged optimal value function. Fig. I1(a) and 11(b) show the policy heatmaps, where the reconstructed "low-rank" policy maintains visually identical to the optimal one. In Fig. 11(c) and 12, we quantitatively show the average time-to-goad the policy trajectory and the input changes between the two schemes. Compared to the optimal one, even with limited sampled data, the reconstructed policy can maintain almost identical performance.
Opeinal
"Janerakk" poliey
Mountain Car
70
Optimal policy Low-rank" policy
Average time guel
65
55
50
45
20
40
60
80
100
poitaan
posticn
Percentage (%)
(a)
(b)
(c)
Figure 11: Performance comparison between optimal policy and the reconstructed "low-rank" policy,
Optimal mnjeesoory
Optimal impat
"Loweranke" trajectary (500%)
"Low-rank"" ingur (50%)
C
(b) "Low-rank" policy with 50% observed data Figure 12: Comparison of the policy trajectories and the input changes between the two schemes.
(a) Optimal policy
further show the results of the SVP policy with different amount of observed data (i.e., 20% and 60%) in Fig. 13 and 14. Again, the SVP policies show consistently comparable results to the optimal policy, over various evaluation metrics. Interestingly, the converged Q matrix of vanilla value iteration is found have approximate rank of 4 (the whole matrix is 2500 1000), thus the SVP can harness such strong low-rank structure for perfect recovery even with only 20% observed data.
C.3 DOUBLE INTEGRATOR
For the Double Integrator, We first use the same approach to generate a "low-rank" policy. Fig. 15(a) and 1.5()) show that the reconstructed "low-rank" policy is visually identical the optimal one. In
15

---

Published as a conference paper at ICLR 2020
polay
paley (30%
Mountain Car
Average time gual (5)
70
Optimal policy
65
policy
50
8
80
20
40
60
80
100
poaliion
positio
Percentage (1)
(a)
(b)
(c)
Figure 13: Performance of the proposed SVP policy, with different amount of observed data.
SVP trajectory (806)
SVP Emput (611))
SVP tragettory (20%)
SVP opet (208))
gestiion
acocineatann
poeram
anvedraation
(a) SVP policy with 60% observed data
(b) SVP policy with 20% observed data
Figure 14: The policy trajectories and the input changes of the proposed SVP scheme.
Fig. 15(c) and 16, we quantitatively show the average time-to-goal, the policy trajectory and the input changes between the two schemes, where the reconstructed policy can achieve the same performance.
Oyctnal polley
'Lanstunk" pulicy (366 desersal
Double Integrator
Average time to goal
204
Optimal policy
policy
202
spost
200
198
196
20
40
60
80
100
postion
postion
Percentage (%)
(a)
(b)
(c)
Figure 15; Performance comparison between optimal policy and the reconstructed "low-rank" policy.
Further, show the results of the SVP policy with different amount of observed data (i.e., 20% and 60%) in Fig. 17 and 18. As shown, the SVP policies show consistently decent results, which demonstrates that SVP can harness such strong low-rank structure even with only 20% observed data.
C.4 CART-POLE
Finally, we evaluate SVP on the Cart-Pole system. Note that since the state space has dimension of 4, the policy heatmap should contain dims, but is hard to visualize. Since the metric we care the angle deviation, we here only plot the first two dims (i.e., the (0, 0) tuple) with fixed x and é, to visualize the policy heatmaps. We first use the same approach to generate a "low-rank" policy, Fig. 19(a) and 19(b) show the policy heatmaps, where the reconstructed "low-rank" policy is visually identical to the optimal one. In Fig. 19(c) and 20, quantitatively show the average time-to-goall the policy trajectory and the input changes between the two schemes. As demonstrated, the reconstructed policy maintain almost identical performance with only small amount of sampled data.
16

---

Published as a conference paper at ICLR 2020
Optinal trajectory
Optinal ingut
"Low-rank" Irggeloory (00%)
"Low-mank" ipput (203)
postion
postioo
time
time
timee
Optimal policy
"Low-rank" policy with 50% observed data
Figure 16: Comparison of the policy trajectories and the input changes between the two schemes.
policy dowreed)
polcc clorsedl
Double Integrator
Average time goal
204
Optimal policy
SVP policy
202
apard
200
198
196
20
40
80
100
postoon
postion
Percentage (%)
(a)
(b)
(c)
Figure 17: Performance of the proposed SVP policy, with different amount observed data.
SVP trojectory (605)
SVP input (6056)
SVP trajectory (20%)
SVP input (20%)
stnderaiie
p10ttoom
Line
Linzer
Lime
Lime
(a) SVP policy with 60% observed data
(b) SVP policy with 20% observed data
Figure 18: The policy trajectories and the input changes of the proposed SVP scheme.
Optinnal polcy
"Lor male' policy (30% obeervoli
Average devialion (degree)
Cart-Pole
Optimal policy
12
"Low-rank" policy ry
10
20
40
100
Percenlage (%)
(a)
(b)
(c)
Figure 19: Performance comparison between optimal policy and the reconstructed "low-rank" policy.
17

---

Published as a conference paper at ICLR 2020
Optiraal tragecory
Optinal ippot
"Low-rank" trujectory (3096)
ronk'rank' imput (3095)
Anggle (dog)
(a) Optimal policy
(h) "Low-rrnk" policy with 50% observed data
Figure 20: Comparison of the policy trajectories and the input changes between the two schemes.
We finally show the results of the SVP policy with different amount of observed data (i.e., 20% and 60%) in Fig. 21 and 22. Even for harder control tasks with higher dimensional state space, the SVP policies are still essentially identical to the optimal one. Across various stochastic control tasks, we demonstrate that SVP can consistently leverage strong low-rank structures for efficient planning.
poier (ar8 dbscvee)
SVP (2095 olearve))
Average devialion Lion (degree)
Cart-Pole
14
Optimal policcy cy
12
SVP policy
20
40
60
80
100
Percenlage (%)
(a)
(b)
Figure 21: Performance of the proposed SVP policy, with different amount observed data.
SVP trajectory (00%)
SVP Impat (00%)
SVP trajentory (20%)
SVP inport (205)
angle (deg))
Line
Eine
Line
tinse
(a) SVP policy with 60% observed data
(b) SVP policy with 20% observed data
Figure 22: The policy trajectories and the input changes of the proposed SVP scheme.
18

---

Published as a conference paper at ICLR 2020
D TRAINING DETAILS OF STRUCTURED VALUE-BASED RL (SV-RL)
Training Details and Hyper-parameters The network architectures of DQN and dueling DQN used in our experiment exactly the same in the original papers (Mnih al., 2013; Van Hasselt et al., 2016; Wang et al., 2015). We train the network using the Adam optimizer (Kingma & Ba, 2014). In all experiments, we set the hyper-parameters 0.99, and minibatch size of 32. The number of steps between target network updates set to 10, 000. We use simple exploration policy as the e-greedy policy with the decreasing linearly from 1 to 0.01 over 3e." steps. For each experiment, we perform at least 3 independent runs and report the averaged results.
follows: learning rate a 1e discount
coefficient
To reconstruct the matrix Q formed by the current batch of states, we mainly employ the Soft-Impute algorithm (Mazumder et al., 2010) throughout our experiments. We set the sub-sample rate to p 0.9 of the Q matrix, and use linear scheduler to increase the sampling rate every 2c steps.
SV-RL Details
E ADDITIONAL RESULTS FOR SV-RL
Experiments across Various based RL We show more results across DQN, double DQN and dueling DQN in Fig. 23, 24, 25, 26, 27 and 28, respectively. For DQN, we complete all 57 Atari games using the proposed SV-RL, and verify that the majority of tasks contain low-rank obtain consistent benefits from SV-RL. For each experiment,
structures (43 out of 57), where we associate the performance on the Atari game with its approximate rank. As mentioned in the main text, majority of the games benefit consistently from SV-RL. We note that roughly only 4 games, which have significantly large rank, perform slightly worse than the vanilla DQN.
Consistency and Interpretation Across all the experiments we have done, we observe that when the game possesses structures (i.e., being approximately low-rank), SV-RL can consistently improve the performance of various value-based RL techniques. The superior performance maintained through most of the experiments, verifying the ability of the proposed SV-RI. to harness the structures for better efficiency and performance in value-bar based deep RL tasks. In the meantime, when the approximate rank is relatively higher (e.g., SEAQUEST), the performance of SV-RL can be similar or worse than the vanilla scheme, which also aligns well with our intuitions. Note that the majority of the games have an action space of size 18 (i.e., rank is at most 18), while some (e.g., PONG) only have 6 or less (i.e., rank is at most 6).
19

---

Published as a conference paper at ICLR 2020
2000
22
350
C0
1200
1500
100
3300
4000
3000
1000
2000
0.30
0025
0350
E3x
0.
820
0.25
1.52
0.75
320
122
Time step
step
Time step
Time step
102
1.00
100
00
02
00
00
40
22
20
22
rack
rack
rack
Alien (hetter)
(b) Amidar (better)
(c) Assault (better)
(d) Asterix (hetter)
1003
Do
DOM6-5
con-cl
20000
20
12500000
20030
19833
500000
10650
0.55
3.5
235
Tome stop
370
Time
0.5
0.
slpp
0.50
0:25
Tim slap
300
100
100
30
50
60
70
20
rank
rank
rank
rank
(e) Asteroids (better)
(f) Atlantis (better)
(g) Bank Heist (similar)
(h) Battle Zone (hetter)
1300
k00
CON--SV
12.01
3300
553
380
135
350
333
Time SIRO
11mr step
1200 step
Time stop
302
1.30
1000
02
80
02
20
20
rank
rank
Beam Rider (hetter)
ii) Berzerk (slightly better)
(k) Bowling (similar)
(I) Boxing (similar)
5000
2000
Dols +it
c0000
L5c0
43000
2500
Time
Time
Time
025
0.2
0.30
202
100
80
50
60
60
mank
20
15
20
15
(m) Breakout (better)
(n) Centipede (better) (0) Chopper Com. (better) (p) Crazy Climber (better)
Figure 23: Additional results of SV-RL on DQN (Part A).
20

---

Published as a conference paper at ICLR 2020
1655
DCKi-S4
D2W-22
1200
DCWl-S
50060
5386
005
300
0.5
0.25
0.50
235
2.28
0.25
0.50
135
1.00
1.2
8.00
0.25
132
0.75
1.3
355
8.23
0.25
135
0.75
120
1.5
150
Time Mtep
mime step
Tome stop
Time slep
1.0
100
100
00
50
00
00
40
20
20
22
20
runk
rack
rack
(a) Defender (better)
(b) Demon Attack (hetter) (c) Double Dunk (better)
(d) Enduro (similar)
10030
520
Dolle Si
4000
230
DON-5VV
125
0.30
1.00
1:35
0.50
1:25
0.55
675
110
Time stop
Time Stop
Time Stop
Tlme step
300
102
1000
100
60
62
62
60
70
22
70
rank
rank
vaak
(e) Fishing Derby (better)
(1) Freeway (similar)
(g) Frostbite (better)
(h) Gopher (better)
DV
20
CON-CC
400
5000
503
260
4000
2000
140
352
335
375
1200 0.55
0.5
Time stop
Time step
Timm step
Time stop
302
100
200
822
62
60
20
20
20
rank
ii) Gravitar (better)
Hero (better)
(k) IceHockey (better)
(1) Jamesbond (similar)
12300
223
DON
40003
11:21
23000
380
19993
10000
5.
3300
2000
0.0
Timo stop
Time 5380
Time stop
Time
50
85
30
80
65
40
40
60
25
12
15
10
15
20
15
mank
(m) Kangaroo (worse)
(n) Krull (better)
(o) KungFuMaster (better) (p) Montezuma's (better)
Figure 24: Additional results of SV-RL on DQN (Part B).
21

---

Published as a conference paper at ICLR 2020
1000
Col--cl
0330
1000
2300
4200
3500
3200
1706
0.00
3.25
0.50
3.5
1,00
0.25
0.0
8.55
1.00
-35
0.25
0.30
1.35
1.30
0.2
0.25
0.50
0.35
Tirm X0M
100
100
100
100
02
00
00
50
20
20
22
20
rack
raak
rack
rank
(a) MsPacman (better) (b) Vame'ThisGame (worse)
Phocnix (hetter)
(d) Pirfall (slightly better)
2003
1000
500
1803
2000
322
210
Timb stop
Time stop
Time stop
(mm 5150
100
102
1.00
100
62
22
20
mank
TAnk
rank
rank
(c) Pong (slightly hetter)
(f) PrivateFye (hetter)
g Qhert (better)
(h) Riverraid (better)
DCW
-30000
30
-20000
Deveay
3003
-2000
22000
2002
-20000
1300
1007
-20.00
me st0p
Time step
Time
1.00
08
00
62
60
60
20
20
rank
(i) Road Runner (similar)
(i) Robotank (better)
(k) Seaquest (worse)
Skiing (similar)
562
DON
DCM
b0k
3330
663
183
25300
543
482
10300
13:30
5500
240
0.7
0.30
Time
Time
50
85
00
50
10
85
60
40
10
35
30
15
12
15
munk
rank
manl
cunk
(m) Solaris (better)
(n) SpaceInvaders (similar) (o) Star Gunner (better)
(p) Tennis (better)
Figure 25; Additional results of SV-RL on DQN (Part C).
22

---

Published as a conference paper at ICLR 2020
2000
800
800
725
0.15
Time ST8P
Time step
Timm slep
Time step
100
100
100
100
63
60
60
60
20
20
20
20
rank
rank
rank
(a) Time Pilot (similar)
(b) Tutankham (similar)
(c) UpNDown (better)
(d) Venture (worse)
CON-OV
BCtli
4330
11000
4002
33000
2000
2002
3200
235
Time Step
Time stop
Ti step
15mo stap
200
1.00
100
60
20
rank
(c) Vidco Pinball (better) (f) WizardOfWor (better) (g) YarsRevenge (better)
(h) Zaxxon (better)
Figure Additional results of SV-RL on DQN (Part D).
23

---

Published as a conference paper at ICLR 2020
Deuble e1l
Decate PQl
Double +
1091
2250
750
20
230
100
200
DON
0.00
022
0.5
235
135
0.50
0.25
3.33
035
120
325
0.50
0.25
323
100
125
0.00
0.25
0.30
0.75
Time step
117me step
step
Time step
100
100
100
100
00
60
60
40
20
20
20
rank
cunic
runk
Alien (slightly better)
(b) Berzerk (similar)
Bowling (similar)
(d) Breakout (hetter)
Couble CON
couble coN-
3300
400000
0300
300000
Phaiir repleeey
2.55
0.75
133
1.00
6.50 0.5
Time stop
Tirm step
Time stap
2.0
200
22
(c) Defender (better)
(f) Frostbite (better)
Hero (hetter)
(h) IceHockey (hetter)
1330
Ule dide com
Conable
utuidee DON
3.201
4330
4300
1100
2300
2300
2000
3
325
012
Time S180
Time S1e0
Time step
Time step
102
80
82
00
80
40
42
40
40
30
15
15
15
rank
Kangaroo (worse)
i Krull (hetter)
(k) Montezuma's 's (hetter)
(1) Pong (slightly better)
Deunte nou
200
Dodile DOM
1200
On All CON
Deaite DOM
2200
0003
6000
wec
4000
6003
4000
2000
1005
200
0.3
3333
022
675
0.25
0755
0.35
675
Time
Time
Time
Time
30
80
85
50
50
40
40
42
40
15
15
12
35
rank
ranic
rank
cunk
(m) Riverraid (better)
(n) Seaquest (worse)
(o) Venture (worse)
(p) Zaxxon (better)
Figure 27: Additional results of SV-RL on double DQN.
24

---

Published as a conference paper at ICLR 2020
1750
Gueling -00
199
Due ing Do
Dualing DoWes
Dualing PQive2)
300
Mary
1992
22
230
2.2
3.5
355
075
1.30
0.30
0.25
3.33
3.55
325
8'0
025
6.5
120
0.00
0.25
0.30
0.75
1,30
1.25
Time stap
Tirme step
Troe step
Time slep
300
100
100
100
60
60
20
20
20
0
runk
rank
runk
Alien (slightly better)
(b) Berzerk (similar)
Bowling (similar)
(d) Breakout (hetter)
D2
Cualing edh
000000
1000
400
400000
200
2000
.0000
3.75
Dhul eg repleeey
1.20
-150
C06-01
155
Timm stop
Term step
Timm SIMP
Time stop
200
100
80
80
20
20
20
rank
rank
(c) Defender (better)
(f) Frostbite (better)
Hero (hetter)
(h) IceHockey (hetter)
Dualing DON
Dealing DOM
Seeting DON
0003
10000
6000
6003
15
2000
2000
Dualing CON-O1
3.33
3000
Time step
Time step
Time step
Time step
1.00
80
80
50
80
60
40
40
40
40
20
10
15
15
rank
rank
Kangaroo (worse)
i Krull (better)
(k) Montezuma's 's (better)
11 Pong (slightly better)
Continn N0%
Ducling DCM
Diatting DGM
Duniling 201
0337
4000
2000
3000
5000
4230
2000
1000
230
075
032
672
0.25
375
323
Time
Time
02
80
30
00
60
40
40
40
40
5
30
15
30
15
10
15
30
15
nunk
runk
rank
(m) Riverraid (better)
(n) Seaquest (worse)
(o) Venture (worse)
(p) Zaxxon (better)
Figure 28: Additional results of SV-RL on dueling DQN.
25

---

Published as a conference paper at ICLR 2020
F ADDITIONAL DISCUSSIONS ON RELATED WORK
Different Structures in MDP We note that there are previous work on exploiting low-rank structure of the system dynamics, in particular, in model learning and planning for predictive state representa- tion (PSR). PSR is an approach for specifying dynamical system, which represents the system by the occurrence probabilities of future observation sequences (referred as tests), given the histories. When the prediction of any test is assumed to be a linear combination of the predictions of collection of core tests, the resulting system dynamics matrix (Singh et al., 2012), where the entries are the predictions of the core tests, is low-rank. Several extensions and variations are explored (Boots al., 201 I; Bacon et al., 2015; Ong et al., 2011), 1), and spectral methods that often employ SVD are developed to learn the PSR system dynamies. In contrast, remark that rather than exploiting the rank of a representation system dynamics, we study the low-rank property of the Q matrix. Instead of learning model, aim exploit this low-rank property in the Q matrix to develop planning and model-free RL approaches via ME.
In this work, focus the global. linear algebraic structure of the Q-value matrices, the rank, to develop effective planning and RI. methods. We remark that there are studies that explore different "rank" properties of certain RL quantities, other than the Q-value matrices, properties algorithmically. For instance, (Jiang et al., 2017) defines new complexity measure of MDPs referred as the Bellman rank. The Bellman rank captures the interplay between the MDPs and given class of value-function approximators. Intuitively, the Bellman rank is a uniform upper bound on the rank of a certain collection of Bellman error matrices. As consequence, the authors develop an algorithm that expedites learning for tasks with low Bellman rank. As another example, in multi-tast reinforcement learning with sparsity, (Calandriello et al., 2014) develops an algorithm referred as feature learning fitted Q-iteration which employs low-rank property of the weight matrices of tasks. It assumes that all the tasks can be accurately represented by linear approximation with a very small subset of the original, large set of features. The author relates this higher level of shared sparsity among tasks to the low-rank property of the weight matrices of tasks, through an orthogonal transformation. As result, this allows the author to solve a nuclear norm regularized problem during fitted Q-iteration.
to exploit such
MDP Planning In terms of MDP planning, we note that there is rich literature improving the efficiency of planning that trades off optimality, such as the bounded real-time dynamic programming method (BRTDP) (McMahan et al., 2005) and the focused real-time dynamic programming method (FRTDP) (Smith & Simmons, 2006). Both methods attempt to speed up MDP planning by leveraging information about the value function. In particular, they keep upper and lower bounds on the value function and subsequently, use them to guide the update that would focus on states that are most relevant and poorly understood. To compare, no bounds of the value function are used to guide the value iteration in our approach. We explicit use the low-rank structure of the Q matrix. Some entries (state-action pairs) of Q matrix are randomly selected and updated, while the rest of them are completed through ME.
26

---

Published as a conference paper at ICLR 2020
G ADDITIONAL EMPIRICAL STUDY
G.1 DISCRETIZATION SCALE ON CONTROL TASKS
We provide additional study the Inverted Pendulum problem with respect the discretization scale. As described in Sec. 3, the dynamics is described by the angle and the angular speed as (0, 0). and the action is the torque applied. To solve the task with value iteration, the state and action spaces need be discretized into fine-grids. Previously, the two-dimensional state space was discretized into 50 equally spaced points for each dimension and the one- ine-dimensional action space was evenly discretized into 1000 actions, leading to 2500 1000 Q-value matrix. Here we choose three different discretization values for state-action pairs: (1) 400 x 100, (2) 2500 x 1000, and (3) 10000 4000, provide different orders of discretization for both state and action values.
As Table 1 reports, the approximate rank is consistently low when discretization varies, demonstrating the intrinsic low-rank property the task. Fig. 29 and Table further demonstrates the effectiveness of SVP: it can achieve almost the same policy as the optimal one even with only 20% observations. The results reveal that as long as the discretization is fine enough to represent the optimal policy for the task, would expect the final Q matrix after value iteration have similar rank.
Optimal poliey
Optinal policy
Optinal policy
aitghla agaedd
angle
angle
(a) Optimal Policy (400 100)
(b) Optimal Policy (2500 1000) (c) Optimal Policy (10000 4000)
SVP policy (20% chserved)
SVP policy (20% oberved)
SVP polley (20% observed)
angle
angle
angle
(d) SVP Policy (400 X 100)
(e) SVP Policy (2500 1000) (f) SVP Policy (10000 x 4000)
Figure 29: Additional study on discretization scale. We choose three different discretization value on the Inverted Pendulum task, i.c. 400 (states, 20 each dimension) x 100 (actions), 2500 (states, 50 each dimension) x 1000 (actions), and 10000 (states, 100 each dimension) x 4000 (actions). First row reports the optimal policy, second row reports the SVP policy with 20% observation probability.
Average deviation (degree)
Discretization Scale
Approximate Rank
Optimal Policy
SVP Policy
400 x 100
4
1.49
2.07
2500 x 1000
7
0.53
1.92
10000 x 4000
8
0.18
0.96
Table 1: Additional study on discretization scale (cont.). We report the approximate rank well as the performance metric (i.e., the average angular deviation) different discretization scales.
27

---

Published as a conference paper at ICLR 2020
G.2 BATCH SIZE ON DEEP RL TASKS
To further understand our approach, we provide another study on batch size for games of different rank properties. Two games from Fig. are investigated; one with small rank (Frostbite) and one with a high rank (Seaquest). Different batch sizes, 32, 64, and 128, are explored and we show the results in Fig. 30.
Intuitively, for a learning task, the more complex the learning task is, the more data it would need fully learn the characteristics. For complex game with higher rank, small batch size may not be sufficient to capture the game, leading the recovered matrix via ME to impose structure that deviates from the original, more complex structure of the game. In contrast, with more data, i.e., larger batch size, the ME oracle attempts to find the best rank structure that would effectively describe the rich observations and at the same time, balance the reconstruction error. Such structure is more likely to be aligned with the underlying complex task. Indeed, this is what observe in Fig. 30. As expected, for Seaquest (high rank), the performance is worse than the vanilla DQN when the batch size is small. However, as the batch size increases, the performance gap becomes smaller, and eventually, the performance of SV-RL is the same when the batch size becomes 128. On the other hand, for games with low rank, one would expect that small batch size would be enough to explore the underlying structure. Of course, a large batch size would not hurt since the game is intrinsically low-rank. In other words, our intuition would suggest SV-RL to perform better across different batch sizes. Again, we observe this phenomenon as expected in Fig. 30. For Frostbite (low rank), under different batch sizes, vanilla DQN with SV-RL consistently outperforms vanilla DQN by a certain margin.
DON
DION
500
DON
400
Average
300
300
200
200
200
100
1.0
Time step
50
Time stop
Time step
112
(a) Frostbite (batchsize 32)
(b) Frostbite (batchsize 64)
(c) Frostbite (batchsize
128)
10000
DON
4000
DON-
6000
DV
6000
DON-SV
3000
Average
von
4000
6000
2000
4000
2000
1000
2000
0.25
0.50
0.75
1.00
1.25
0.25
0.30
0.75
1.00
1.25
0.25
0.50
0.75
1.00
125
Time step
Time step
Time step
(d) Seaquest (batchsize 32)
(e) Seaquest (batchsize = 64)
(I) Seaquest (batchsize 128)
Figure 30: Additional study on batch size. We select two games for illustration, one with a small rank (Frostbite) and one with high rank (Seaquest). We vary the batch size with 32, 64, and 128, and report the performance with and without SV-RL.
28


Reviews:
[{"review_id": "rke4w8yIKr", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "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\tThis paper develops a method for taking advantage of structure in the value function to facilitate faster planning and learning. The key insight is that MDPs with low rank Q^* matrices can be solved more expediently using matrix estimation methods, both for classical dynamic programming methods (value iteration) and for learning in rich environments using recent model-free deep RL techniques. Thorough empirical analysis is conducted both for value iteration in tabular MDPs and for deep RL in rich environments. These experiments highlight new findings about the role the rank of the Q matrix plays in planning convergence and learning rates.\n\n\tI view this paper as containing several key contributions: first, the analysis on the role of Q rank in planning and learning---experiments conducted indicate that even complicated environments tend to have low rank Q matrices (when approximated). Highlighting the role of this rank and the corresponding empirical analysis estimating it in benchmark RL and control tasks is, to my knowledge, novel. Second, and perhaps the most significant contribution, is \"Structured Value RL\" (SV-RL), an easy-to-apply method that can be incorporated into many Q-based deep RL methods with little overhead. The empirical results are compelling: across three different variations of DQN-like architectures, the SV RL augmentation tends to improve learning. Presentation of results is rigorous, too, and provide strong evidence that the method works.\n\n\tAs the paper mentions, theoretical analysis on the impact of Q-rank on dynamic programming (and perhaps learning) would be of great interest to the community. I take this analysis to be out of scope for this paper, but could see the work motivating future investigation into these questions.\n\nVerdict: Overall, I take this paper to present many novel insights, establish solid motivation with good writing and examples, and offers compelling evidence about the strength of SV RL. I recommend accepting the paper.\n\nComments:\n\tC1: The visuals throughout the paper are helpful!\n\tC2: The paper is well written: the use of examples was effective in developing the motivation.\n\tC3: Section 2 is helpful for understanding the ideas developed in the paper. However, there are many well developed planning frameworks for MDPs that trade-off optimality with computational efficiency. It might be worth discussing some of these methods up front. For instance, Bounded Real-Time Dynamic Programming (McMahan et al. 2005) explicitly uses value function structure to improve planning speed, with performance guarantees, as does Focused RTDP (Smith and Simmons 2006). I don't take the computational complexity improvements of the proposed method to be the primary contribution, so just a brief discussion to contextualize the work against other planning literature would be helpful.\n\tC4: While the \"rank\" studied here is of a different form, some discussion of the Bellman Rank work (Jiang et al. 2017) might be useful for differentiating the two notions of \"rank\" at play, and how they are each used to expedite learning. The Bellman Rank is used as a measure of complexity of an MDP---Jiang et al. develop an RL algorithm that has sample complexity that depends on this measure. It is not strictly necessary, but I could see multiple uses of \"rank\" appearing in the RL literature as a means of exploiting structure for faster learning being confusing. If space (perhaps in the appendix if not), a sentence or two differentiating the two ideas might be helpful to readers. Additionally, the study of sparsity in value function representation was studied by Calandriello et al. 2014. If space permits, the paper might benefit from some discussion of the relation to this work.\n\nQuestions:\n\tQ1: In the inverted pendulum results, I am curious about the effect of the discretization on plan quality. Specifically: how were 2500 states and 1000 actions chosen? Were different orders of magnitude (for both values) considered? How did this impact SVP? Does the rank change as the discretization becomes more or less coarse? I don't think this is strictly critical for the paper, but a few sentences clarifying this point would be informative.\n\n\tQ2: Figure 4 provides nice insights into how to scale these ideas to deep RL. How were the four games chosen? Is there anything special that motivated their selection?\n\n\tQ3: Additionally, I am curious about whether the results from Figure 4 are the consequence of algorithmic decisions, rather than the environment. Is it possible to determine whether different value based methods (or different choices of hyperparameters) lead to different outcomes? For instance, I could imagine a more shallow network, or a tighter bottleneck, leading to Q evaluations that produce higher rank. \n\n\nTypos and Writing Suggestions:\n\n[Abstract]\n\t- This sentence is quite long, and I had a hard time following it as a result: \"As our key contribution, by leveraging...\". Consider dividing into two sentences.\n\n[Intro]\n\t- Oxford comma: \"control, planning and reinforcement learning\"::\"control, planning, and reinforcement learning\n\t- \"the structured dynamic\"::\"the structure in the dynamics\"\n\t- \"where much fewer samples\"::\"where fewer samples\"\n\t- Consider rewording: \"almost the same policy as the optimal one\". Is it that the policies are in fact the same? Or that their values are close? Perhaps: \"a policy with near optimal value\".\n\t- When introducing Double DQN and Dueling DQN for the first time it would be appropriate to cite each (end of Section 1).\n\n[Sec. 2: Warm Up]\n\t- \"understand the structures\"::\"understand the structure\"\n\t- \"give a strong evidence for\"::\"provide evidence that\"\n\t- \"exploit the structures for\"::\"exploit structure in the value function for\"\n\t- I think the italicized statement at the top of page 3 could be sharpened. The antecedent currently stating \"why not\" is quite a soft statement compared to the motivation the section develops. Consider changing: \"...why not enforcing such a structure throughout the iterations?\"::\"...then enforcing such a structure throughout planning can improve the rate of convergence\".\n\n[Sec. 3: Structured ... Planning]\n\t- \"even non-convex optimization approaches (...\"::\"even non-convex optimization approaches to solving this problem (...\"\n\t- \"offer a sounding foundation for future\"::\"offer a sound foundation for future\"\n\n[Sec. 4: Structured ... RL]\n\t- \"Previously, we start by\"::\"Previously, we started by\"\n\t- \"which in deep scenarios\"::\"which in scenarios with large state spaces\", or perhaps: \"which in deep scenarios\"::\"which in scenarios where value function approximation is used\"\n\n\nReferences:\n\nCalandriello, Daniele, Alessandro Lazaric, and Marcello Restelli. \"Sparse multi-task reinforcement learning.\" Advances in Neural Information Processing Systems. 2014.\n\nJiang, Nan, et al. \"Contextual decision processes with low Bellman rank are PAC-learnable.\" Proceedings of the 34th International Conference on Machine Learning-Volume 70. JMLR. org, 2017.\n\nMcMahan, H. Brendan, Maxim Likhachev, and Geoffrey J. Gordon. \"Bounded real-time dynamic programming: RTDP with monotone upper bounds and performance guarantees.\" Proceedings of the 22nd international conference on Machine learning. ACM, 2005.\n\n\nSmith, Trey, and Reid Simmons. \"Focused real-time dynamic programming for MDPs: Squeezing more out of a heuristic.\" AAAI. 2006.\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "r1liO4xTtH", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "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 introduces an interesting idea of exploiting the low-rank structure of the value function to reduce the computation complexity of value-based RL algorithms. Instead of working in the reduced space, they focus to operate on the original space and reduce the computation by looking at few elements and inferring the rest.  They use a matrix completion/estimation strategy to infer the global structure from a smaller set of samples. They show empirical evidence of the low-rank structure in few classical control tasks (Mountain Car, Inverted Pendulum, Cart Pole), and provide an iterative procedure - Structure Value-based Planning (SVP), that is similar to value iteration but is able to exploit the low-rank structure to reduce the computational time.  They also provide a deep RL extension - SV-RL, that can be applied to value-based methods. They test the efficiency of their approach to Atari games. \n\n\nOverall this paper presents an interesting idea, that also scales to the deep RL algorithms. However, there are a few missing components that need to be addressed in order to fully support the claims.  Given these clarifications in the author's response, I would be willing to increase the score.\n\n1) Nature of the regularization for SV-RL.\nThe authors are proposing a form of regularization that enforces low-rank structure for the value function (and target Q-values in particular for deep RL agents).  The authors show that this form of regularization is helpful for improving the learning for low-rank tasks, and for tasks that have a high-rank the performance is worse.  This kind of regularization balances having a low-rank and small reconstruction error. However, shouldn’t the regularization also depend on the size of the sub-matrix (the minibatch)?  However, I didn’t find any experiments related to how changing it affects performance. Also, is the regularization related to due to the random projections (Johnson–Lindenstrauss lemma)?\n\n2) It is important to note that SV-RL is limited to Deep Q-learning based techniques. So it can’t be applied to any value-based method, especially when the samples in the sub-matrix are correlated.  \n\n3) Missing literature that exploits Low-rank structure for planning. There is literature on RL that is based on exploiting the low-rank structure for planning [1, 2, 3].  \n\n4) All the experiments are in deterministic environments? Is there a reason behind this? \n \n5) (Optional) This regularization introduces error in reconstructed approximate Q-values. It will be useful to have some analysis on how far it deviates from the optimal value function. There has been work in the field [4, 5] that I believe can be used to help derive an analysis of the kind of approximation error bounds that are being introduced here.\n\n\n\nReferences: \n\n\n[1] Byron Boots, Sajid M Siddiqi, and Geoffrey J Gordon. Closing the learning-planning loop with predictive state representations. The International Journal of Robotics Research, 30(7):954–966, 2011\n\n[2] Pierre-Luc Bacon, Borja Balle, and Doina Precup. Learning and planning with timing information in markov decision processes. In Proceedings of the Thirty-First Conference on Uncertainty in Artificial Intelligence , pp. 111–120. AUAI Press, 2015.\n\n[3] Sylvie CW Ong, Yuri Grinberg, and Joelle Pineau. Goal-directed online learning of predictive models. In European Workshop on Reinforcement Learning, pp. 18–29. Springer, 2011.\n\n[4] Klopp, Olga. \"Noisy low-rank matrix completion with general sampling distribution.\" Bernoulli 20.1 (2014): 282-303.\n\n[5] Recht, Benjamin. \"A simpler approach to matrix completion.\" Journal of Machine Learning Research 12.Dec (2011): 3413-3430.\n\n\n\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "N/A"}, "extra_text": {}}, {"review_id": "SJl0rjD2tr", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "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": "The study is motivated by the observation that the Q-value matrix in reinforcement learning problems often has a low-rank structure. The paper proposes an approach called structured value-based planning or learning, where the Q matrix or the Q function is estimated from incomplete observations based on the prior that it is low-rank. The proposed strategy is demonstrated in stochastic control tasks and reinforcement learning applications. \n\nThe paper is clearly written and the experimental results show that the proposed strategy leads to performance gains especially in problems where the Q matrix indeed conforms to a low-rank model. A few comments and questions:\n\n- The assumption that the Q matrix should be low-rank is demonstrated with several experiments. Is there any theoretical motivation or guarantee for this assumption as well?\n\n- The experimental results show that the proposed strategy performs well in problems that are low-rank, while the performance may degrade in problems where the low-rank assumption is not met. Would it be possible to detect the rank of the problem in a dynamical manner (i.e., during the learning), so that the number of incomplete observations of Q can be increased to improve the performance, or the solution strategy (e.g. whether to use the low-rank assumption or not) can be adapted to the nature of the problem?\n\n- The Q-value matrices and functions considered in the problem have a special structure as they result from Markov Decision Processes. Would it be possible to go beyond the low-rank assumption and propose and use a more elaborate type of prior that employs the special structure of MDPs?\n\n- Please clearly define the notation used in Section 4.2.", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I made a quick assessment of this paper."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper shows empirical evidence that the the optimal action-value function Q* often has a low-rank structure. It uses ideas from the matrix estimation/completion literature to provide a modification of value iteration that benefits from such a low-rank structure.
The reviewers are all positive about this paper. They find the idea novel and the writing clear.
There have been some questions about the relation of this concept of rank to other definitions and usage of rank in the RL literature.
The authors’ rebuttal seem to be satisfactory to the reviewers. Given these, I recommend acceptance of this paper.
Decision: Accept (Talk)