Qgraph-bounded Q-learning: Stabilizing Model-Free Off-Policy Deep Reinforcement Learning
Authors: Sabrina Hoppe
Marc Toussaint
Venue:  (2020)
Keywords: deep learning
reinforcement learning
model-free reinforcement learning
Q-learning
DDPG

Abstract: In state of the art model-free off-policy deep reinforcement learning (RL), a replay memory is used to store past experience and derive all network updates. Even if both state and action spaces are continuous, the replay memory only holds a finite number of transitions.  We represent these transitions in a data graph and link its structure to soft divergence. By selecting a subgraph with a favorable structure, we construct a simple Markov Decision Process (MDP) for which exact Q-values can be computed efficiently as more data comes in - resulting in a Qgraph. We show that the Q-value for each transition in the simplified MDP is a lower bound of the Q-value for the same transition in the original continuous Q-learning problem. By using these lower bounds in TD learning, our method is less prone to soft divergence and exhibits increased sample efficiency while being more robust to hyperparameters. Qgraphs also retain information from transitions that have already been overwritten in the replay memory, which can decrease the algorithm's sensitivity to the replay memory capacity.


Under review as a conference paper at ICLR 2020
QGRAPH-BOUNDED Q-LEARNING: STABILIZING MODEL-FREE OFF-POLICY DEEP RL
Anonymous authors Paper under double-blind review
ABSTRACT
In state of the art model-free off off-policy deep reinforcement learning (RL), replay memory is used to store past experience and derive all network updates. Even if both state and action spaces continuous, the replay memory only holds finite number of transitions. We represent these transitions structure soft divergence. By selecting a subgraph with a favorable structure, we construct a simple Markov Decision Process (MDP) for which exact Q-values can be computed efficiently as more data comes resulting a QGRAPH. We show that the Q-value for each transition in the simplified MDP is a lower bound of the Q-value for the same transition the original continuous Q-learning prob- lem. By using these lower bounds in TD learning, our method is less prone to soft divergence and exhibits increased sample efficiency while being more robust hyperparameters. QGRAPIIS also retain information from transitions that have al- ready been overwritten the replay memory, which can decrease the algorithm's sensitivity to the replay memory capacity.
data graph and link its
INTRODUCTION
With the wide-spread success of neural networks, also deep reinforcement learning (RL) has enabled rapid improvements in many domains including computer games (Silver et al.) 2017) and simulated continuous control tasks (Mnih et al. (016). Particularly in areas where correct environment models are hard to obtain, such robotic manipulation, model-free approaches have the potential to out- perform model-basee solutions (Fazeli et al. 2017 Levine et al. 2016) as long as enough training data is available can be generated.
Although efforts in the research community on building an understanding of deep RL for sim- ple examples seem be rising (Mania et al., 2018), deep reinforcement learning remains under- investigated from a theoretical point of view. Many algorithms use function approximation, off- policy learning and bootstrapping together which has even been called deadly triad by /Sutton] & Barto (0118) because this is a very unstable combination of techniques. Although Q-learning known have convergence issues even with linear function approximation (Baird 1995). deep
Q-learning descendants like DQN and DDPG often excel empirically (Van Hasselt et al. 2018). At
the same time their performance can be unreliable and hard to reproduce (Henderson al. (0118).
The contribution in this work is two-fold: To add to the community's 's understanding of when deep Q-learning diverges, we first propose a graph-perspectie on the replay memory which allows to analyze its structure and show on educational examples that specific types of structures are linked to divergence. Second, we derive our method from these insights and show that prevents many cases of soft divergence. Further analyses reveal that this increases sample efficiency, robustness to hyperparameters and preserves information from transitions that have already been overwritten in the replay memory.
2 PRELIMINARIES
We consider a standard reinforcement learning setup where an agent interacts discrete time steps t = 1,..., T with environment that is modeled as a Markov decision process (MDP) with state space S. action space A, initial state distribution p(s1). transition dynamics p($++1|s, | a,) and a reward function r(st, a.). In the following, will assume deterministic transition dynamics.

---

Under review as a conference paper at ICLR 2020
replay memory
data graph
Qgraph
0
-100
50
81
Q1
1
82
0
F3
62
4s
B2
92
02
$2
43
83
0
83 (14
0
84
-1
100
Figure We take a graph perspective on past experience (middle) and extract subgraph (right) such that its structure allows to compute exact Q-values using Q-iteration for the resulting finite MDP. Its Q-values represent lower bounds to the Q-values the actual continuous MDP.
At each time I, the agent can observe its state 8; and take an action a, which determines the next state 81+1 and an associated reward A policy is function that maps from states to actions. The sum over future expected rewards when following policy æ is called return: R "/=,"" >'"rr, where is the so-called discount factor. For 7 < 1 and a constant reward r for infinite trajectories, the return forms a geometric series and converges to - This also means, that if the reward function bounded by Rein and Rmax, the smallest and largest possible Q-value can be computed as
Ruinn
R 1-7) ]
Rmax
min
Rmin: 1
max
(1)
respectively (Lee & Kim 2015). The min/max operations required for terminal states.
Analogously, if the reward only depends on the current state and the agent stays in a state s forever, because action (s)) does not lead change in states, then Q(s, a) -ー This transfers to (1, larger loops, e.g. transitions (81, 01, 11, 82) to (8n, On, 81) are known to be induced by a policy
π,
= + 222 + + 70 r, ty + ty r2 +... FT. Σ (7))²
TL
(2)
1- 7"
The expected future return for executing an arbitrary action a, and then following the policy is called Q" (x), E 1r + R[+1] The agent's goal is find the optimal policy x" such that the expected future return is maximized from any state. This can be achieved by finding (a good approximation to) the Q-function and then choosing the action with highest Q-value each state.
One popular way to learn Q-function is temporal difference (TD) learning. Given a transition (s, a, a,r,"s)) the next Q-value (s),sa) computed based on the current estimate for state s',
00 Q'(s,a) =rt { Q(s', =ss)),
if s' terminal
else
Such process with updates that are based on the current estimates of the function to be approxi- mated is called bootstrapping. Note that bootstrapping is actually only applied in the case of non- terminal states (i.e. in the second line of the equation). We refer states that do not require boot- strapping to estimate a Q-value as anchors.
In small settings with finitely many states and actions, can be represented as a table this form of Q-learning is referred to as tabular. The policy in tabular Q-learning can be read of the table as (ss) arg max, Q(x, a). In continuous state action spaces, Eq. (3 can be used with function approximation.
3 RELATED WORK
One of the most popular function approximators for O-functions are neural networks: deep Q networks (DQN), single network is trained to take states input and predict Q-value
2

---

Under review as a conference paper at ICLR 2020
for each possible action (Mnih et al. 2015). For continuous actions, an actor-critic architecture called deep deterministic policy gradient (DDPG, [Liliirrp et al. (2015)) can be used: The critic is represented by one network that computes the Q-value for given state-action pair. These Q- estimates are used as a training signal for the actor, which is a neural network that represents the policy.
Both DDPG and DQN are model-free algorithms, i.e. do not assume nor learn a model of the en- vironment (including dynamics and other objects in the environment). Furthermore, they use off- policy data, i.e. they store past experience in a replay memory and update their networks based on this experience, even if the policy π has changed since the data was collected. It is insightful to note that this replay memory only contains finite number of transitions (s, a, s', .) that all networks are updated from, even for continuous sate-action spaces.
The original reasoning behind replay memories and experience replay was to break dependencies be- tween transitions (Mnih et al. 2015), which is important for most function approximation schemes. We will therefore keep the principle of random selection of data for our learning process, but at the same time we will make use of additional information that a graph perspective can provide and would be lost otherwise. Prior work has incorporated trajectory-centric perspectives already: Monte Carlo updates for example do not estimate Q-values based on single transitions as in Eq. 3 but on empirical returns for full episodes. The resulting gradients on the Q-function often suffer from large variance though (Deerr et al.) 2019) and therefore many intermediate algorithms exist, mixing TD-learning and Monte Carlo approaches, (e.g. AAmirnnahvilii et al. (2018); Munos et al. (2016). Trajectories have also been combined to graph structures, for instance to guide exploration (Shkolnik & Tedrake| ) allow for planning (Farquhar et al. 2018)) to re-visit previously discovered states (Dong et al. 2019). Simultaneously to this work. Anonymous (2020) have suggested to build a graph structure from states in the replay memory and thus to propagate information from one tra- jectory to another if they share a state. Our method also uses cross trajectory information as side effect because of the graph perspective it takes on data in the replay memory.
Despite its success in many applications, model-free off- deep reinforcement learning can be rather unstable: On the one hand, many algorithms are very sensitive to hyperparameters and even subtle differences in their implementation (Henderson et al. (2018), making it hard to provide sensible empirical comparisons. On the other hand, the theoretical underpinning is quite weak: Reinforcement learning with (even linear) function approximation has already been known to be instable for more than 20 years (Baird 1995). Since DQN and DDPG combine (highly non- non-linear) function approximation with bootstrapping and off-policy learning, these algorithms egory of methods that Sutton & Barto (2018) call deadly triad because it is even more prone to divergence. Removing one of the three critical properties, e.g. by reducing off-policy exploration can therefore have positive effects on learning stability (Kumar et al. 2019: Fujimoto et al., 2019)) Our work in contrast focuses on how to stabilize learning with all three properties intact. Other types of off-policy reinforcement learning are much better understood and proven to converge un- der certain conditions, e.g. for prediction finite MDPs with non-lineat function approximation as
in cat-
in (Maei et al. 2009) or control under the assumption of a stationary policy (Maei et al.) 2010). Also
simplified MDPs have been examined for reinforcement learning, for instance to combine model- based and model-free methods as in Seijen et al.) (20TT). We will propose new type of simplified MDP that is based on novel insights into the crucial role of the data graph structure.
Since empirical success seems to be on the side of DQN and DDPG though, there has been in- creasing number of works on simpler reinforcement learning on the one hand (Mania et al., 2018) and analyses of small examples to build understanding of why this often works so well. Van Has- selt et af.] (2018) for instance show that unbounded divergence, which would cause floating point NaNs, as expected for the deadly triad, barely happens in deep Q-learning. Instead, typically only soft divergence, causing Q-values beyond the realizable range, is observed. Nonetheless, all variants of divergence not just lead instable Q-estimates but also prolong the learning phase which is particularly painful for areas with high costs associated to new data samples such as robotics. In this work, we show that many cases of soft divergence are caused by specific data graph structures in TD learning. Our method uses Q-values from the simplified MDP with favorable graph structure to construct lower bounds for Q-values in the original learning problem.
3

---

Under review as a conference paper at ICLR 2020
full example:
10
10
10-2
exemplary transition subsets:
2
10"
dacomeeted
Figure 2: Educational example with four transitions and three states (state 0 is terminal). We char- acterize transitions based on the graph structure: (in-)directly connected to a terminal state (blue, orange); loose ends (green) and disconnected but infinite paths (red). The right plot illustrates the standard deviation over predicted Q-values for each type of transition.
EDUCATIONAL EXAMPLES
Let's assume a continuous state-action space, but the replay memory only contains up to four tran- sitions and three states (one of which is terminal). |Figure 2 illustrates this as a graph, where each node a state and each edge represents a transition. Under the assumption that possible for an agent to have discovered any subset of transitions, 2 = 16 cases emerge from this setting (one of which is empty and therefore ignored).
We have trained DDPG critic network for each of the 15 cases under the following conditions: The reward for each step that leads to a non-terminal state 1 (to encourage fast solutions), the reward for reaching the terminal state is O. The states were assigned 2D-coordinates
from the graph illustration (0: [0,0], 1: [], 2: 1I, and the action to move from state 8 to state s' was defined the offset s' s. For the critic network we chose layers with 4 hidden states, ReLU activations (except on the output) and Xavier-initializaton.. The policy was computed as in tabular Q-learning by selecting the action with highest Q-value for a given state. We performed ten thousand updates for each case consisting of all available transitions. The whole procedure was repeated with 10 random seeds that were drawn uniformly from [0, 1000].
Confirming the finding in Van Hasselt et al. (2018), no unbounded divergence occurred (which would cause floating point NaNs). However, we found occurrences of soft divergence, i.e. Q-values beyond the realizable range as given in Eq. (I]
For further analysis we use the standard deviation of Q-values that were estimated over different random seeds as measure of soft divergence: if Q-learning for a transition converges, all Q-values should be identical and thus have a standard deviation close to zero. The more soft divergence occurs however, the larger the standard deviation becomes. Even if all trials diverge, it is highly unlikely that the resulting Q-values are identical.
Evaluating the distribution of standard variations reveals link between the structure of the Q-graph and soft divergence:
Transitions (s, a, r, s', t) where s' is terminal are referred as directly connected. Their Q-values are estimated almost perfectly, because Q-learning is reduced to supervised learning in these cases (cf Eq. 33).
Transitions that end in a non-terminal state from which terminal state is reachable are referred as connected. Their Q-estimates exhibit only slightly more variance than the directly connected transitions. Presumably the reachable terminal state still acts an anchor for the Q-value (as long as all transitions on the path are regularly used for updates). line with this hypothesis, the two following categories that do not have anchor show significantly more variance in their predictions:
no terminal state is reachable from and there is no infinite path from s', the transition is referred to as loose end. These transitions occur for instance the end of each episode in episodic learning setups, when the agent is reset to a starting position. is insightful to note that Q-values for such transitions conceptually ill-defined in tabular Q-learning where state without successors would be defined as terminal. For non-terminal states, a Q-value could be determined under the assump- tion that further transitions exist (and just have not been experienced yet), but then the Q-value is
4

---

Under review as a conference paper at ICLR 2020
estimated using bootstrapping from another Q-value that has never been explicitly updated. This may be okay, if the learned function generalizes nicely but there is no guarantee for this to happen. Transitions are referred to disconnected if no terminal state is reachable from s' but there exists at least one infinite path from s'. These transitions caused the highest variance in Q-estimates. In contrast to loose ends however, the Q-value for these transitions well-defined under the assump- tion that all possible transitions are known and can even be computed analytically (cf. Eq. (2). Even in our educational toy example, where the replay memory was not changed during training, the Q-values for disconnected transitions were rarely found and caused soft divergence instead.
In our method, all available exact Q-values (under the assumption that all possible transitions are known), including those for disconnected transitions, will be used as lower bound for the Q-value in the original learning problem. We will show empirically that, besides further effects, this reduces the variance of predicted Q-values.
METHOD
Despite the continuous state-action space, the networks in DDPG are updated based on a finite set of transitions from the replay memory. It is therefore possible take graph perspective on this data: A transition (s, a, r; 8', () can be seen as an edge between the nodes corresponding to states & and 8' (which is terminal iff indicated by t); and can be annotated with and a. Any hashing function can be used to encode nodes and detect if the same node is revisited. For small spaces, it is enough to use the state vector directly. This is not supposed to introduce any discretization beyond the limits of precision. We refer to this directed graph as data graph (see Figure I for an illustration).
QGRAPH
Building on the insights from section 4 we select the largest set of transitions from the data graph for which exact Q-values be computed under the assumption that the resulting graph is complete (i.e. that all possible transitions and all states are included). That is, we extract all transitions from the data graph except for loose ends. Formally, this induces smaller finite MDP for which the associated Q-function can be computed using tabular Q-iteration with guaranteed convergence due to its contraction property. Our method is agnostic to the algorithm that computes these Q-values, so for instance it is also possible to solve the linear equation system for sparse transition matrix. In any case, the computational overhead compute these Q-values can depend on the number of transitions in the replay memory, but it is independent of the input dimensionality. We annotate the subgraph with the resulting Q-values and refer to as QGRAPH.
In many settings, there are known zero actions a, that do not change the agent's state at all, e.g. moving by 0 units or applying 0 force. If those are applicable all states, it may be possible to add a solf-loop to every single node in the data graph. This effectively eliminates all lose ends and turns them into disconnected states, in other words enables the QGRAPH to contain all transitions from the data graph.
QGRAPE PH values lower bounds on the original Q-learning problem
The original MDP contains more states or transitions than the QGRAPH unless the environment has discrete state-action spaces and the replay memory contains at least one sample for each possible transition. Then, the Q-values do not transfer to the original MDP as a correct solution but in deterministic environments, they can serve lower bound for the true Q-values:
Each Q-vuuue Q(s,, a) on the QGRAPH is based on actually experienced trajectories, but it is possible that unseen states and transitions exist. Assume that transitions (Sg. a1, (1. $1) and ($1, 02 r2, $2) are already known and part of the QGRAPH, APH, but in fact at least one further transition from 81 exists. Then the Q-value for the first transition lower bounded by Q(s1, 42) because of the max operation: ((s0, a1) + max, @(s1, a) 2 + Q(s1, 42)
Thus, each Q-value for a transition in our QGRAPH is a lower bound of the Q-value for the same transition in the original MDP continuous state and action spaces.
If the environment is non-deterministic, less tight bounds can be established under additional as- sumptions. For instance, let's 't's assume that for all states and any given series of actions M., the empir- ical returns R, that an agent can observe when following 2 differ by at most 8. Then all Q-values from the simplified MDP apply as lower bounds with margin 8: Qime (s,a) a) 2 Qsimplined (s, a) 5.
5

---

Under review as a conference paper at ICLR 2020
2wng
2wp
Figure 4: The 7-state star problem (Baird 1999). Using vanilla TD-learning, state values and weights spiral out to infinity (orange dots). Applying our graph- lower bounds however makes TD-learning converge to the correct solution (blue solid line).
QGRAPH-bounded Q-learning
Q-values from QGRAPH be used as lower bounds in bootstrapping for temporal difference learning as in Eq. (3 method we call QGRAPH-bounded Q-learning:
('(s,a) max(LB, + max Q(s',a'))
(4)
where LB represents per-sample lower bound. Loose ends are not associated with such lower bound but could potentially still carry important information (e.g. in cases where the function ap- proximator has generalized nicely to the states involved). The transitions associated with loose ends can therefore still be used as usual, i.e. using unbounded TD-learning
EXPERIMENTAL RESULTS
We evaluated the core of our method on a classical toy example for con- vergence issues in value learning (Section 6.1). The simulated continu- ous control problem for all further experiments is described in Section We first present overview of learning performance with focus on sample efficiency and robustness to hyperparameters in Section 6.3 In Section 6.44 we verify that the observed effects are in line with the guiding hypothesis from our educational example in Section + Finally, we examine additional aspects our method: the impact of zero ac- tions and more trivial bounds on Q-values (Section 6.5) well as the method's interaction with limited replay memory capacity (Section
6.2
Figure 3: Simulated Peg- In-Hole task.
6.1 BAIRD'S S STAR PROBLEM
The 7-state star problem (Figure 4) was proposed by Baird (199)) to demonstrate convergence issues in value iteration with (linear) function approximation. The agent receives a reward of zero for each action and thus the correct solution to the problem is to set all weights to zero and obtain state-values of zero. If all weights are initially positive and wo larger than the others, this causes oscillatory behavior of both state values and weights. We reproduced the exact setting and result plots for Figure 4.2 in Baird 1999). Applying our graph view the problem, we derive lower bound of zero for Vy because it has a self-loop with reward O; and thus this lower bound recursively leads lower bound of + 7 0 for all other states. These graph-based bounds can be applied in TD learning in analogy to Eq. (4) as (*()) max(LE +r+V((sV)) As a result, our method converges the correct state values rather than diverging infinity as Figure fillustrates.
6.2 EXPERIMENTAL SETUP
All further experiments details in Appendix A. and DDPG implementation details in Appendix A.2 After each epoch, the
conducted simulated continuous control task, see environment
Q-targets were updated, i.c. no explicit target network was used, since those known to prolong training and thereby postpone convergence issues but not solve them (Van Hasselt et al.) 2018). All algorithms were tested for 300 episodes. We tested vanilla DDPG on a grid learning rates for actor and critic in {10-2 10-3 10-4) and chose three cases that are representative for the spec- trum of DDPG performance. The learning curves for all learning rates are shown in Appendix 7 Most results will be presented in the form of learning curves, where the line represents the mean performance over ten runs with different random seeds and the shaded area highlights the standard deviation of the mean estimator, i.e. vx

---

Under review as a conference paper at ICLR 2020
Cun wwl.llbre TOWME
C www.l
cun MWW
spsedes
Boddes
Figure 5: Learning curves for vanilla DDPG and QGRAPH-bounded Q-learning('QGG on the left; number of baselines in the center; and performance under limited graph capacity on the right.
6.3 SAMPLE EFFICIENCY AND ROBUSTNESS TO HYPERPARAMETERS
We hypothesized that RGsee lower bounds would correctly limit the range of Q-values which prevents
cases of soft divergence and thereby increases sample efficiency. We further hypothesized that explicit bounds would barely have any impact in cases when vanilla Q-learning works well, because our method described in Eq. (4) reduces standard TD learning when no bound is violated. In other words this implies that QGRAPII-bounded Q-learning should never decrease performance.
For first overview, we compared learning curves of (GRAPH-bounder Q-learning (' ('QG') to those of vanilla DDPG in Figure 5] (left). As expected, QGRAPHS speed up learning for all examined learning rates. The effect size varies and is larger for those learning rates that lead to relatively poor performance in vanilla DDPG. This decreases the gap in performance between different learning rates and can therefore be interpreted an indicator for increased robustness to hyperparameters.
6.4 VARIANCE OF PREDICTIONS
+
10-
To assess if this performance is due to similar effects as in our educational examples, we evaluated the variance in predicted Q-values at the end of each experiment under the learning rate with largest effect size (10-9). We covered the state space with regular grid of 27 states and evaluated the learned Q- value for each of these states with a set of eleven given actions as well as with the action that the actor network suggests for each state. The full list of all states and given actions that were tested can be found in Appendix [A.4.
Figure 6: Standard deviation of pre- dicted Q-value.
For the boxplot in Figure 6) we collected the standard deviations over the predicted Q-values for each state-action pair from 10 runs with different random seeds. The orange line indicates the median value, the box extends from the lower to the upper quartile value, the whiskers cover 1.5 times the inter quartile range and outliers are shown as circles. The results shows very clearly that QGRAPH- runs resulted in significantly less variance for predicted Q-values, indicating that QGRAPH-boundee Q-learning does indeed prevent cases of soft divergence.
6.5 FURTHER BASELINES
We ran the following baselines to deepen our understanding of the previously reported effects: In many settings zero action is known that does not change the agent's 's state (in our case it is the offset in position by zero meters). Adding hypothetical transitions with the zero action after each physical transition ('vanilla-Z.A'' improves the structure of the data graph by turning loose ends into disconnected transitions. Using zero actions in our method ('QG-ZA') not only improves the structure of the data graph but also spreads information in the form of lower bounds to predecessors in the QGRAPH. The results in the center of Figure 5) show that zero actions improve marginally over vanilla DDPG and structure of the data graph matters and that in particular vanilla DDPG benefits from a structure without loose ends. At the same time, adding our QGR APH is much more effective than changing
Q-learning. This implicates
the one hand that the
7

---

Under review as a conference paper at ICLR 2020
the data graph only. This demonstrates that the propagation of information through the QGRAPH and the integration of lower bounds into TD-leaming are the main contribution of our method.
The next set of baselines was designed to evaluate how much influence the exact bounds have. Bounded temporal difference learning could, besides our QGRAPH-based bounds, integrate two fur- ther types of lower and upper bounds: A priori bounds may be known in the case of bounded reward function, see Eq. (T) Empirical bounds may seem like an alternative for correct a priori bounds: rather than using known bounds on the reward, these bounds could be estimated from expe- rience. Note that the true Q-values are guaranteed to lie within QGRAPII-bar
bounds and correct a priori bounds, while empirical bounds might be too tight. We combined (GGAAH--bondde Q- learning and vanilla DDPG with both types of bounds. When several bounds were available for one Q-value, the tightest upper and lower bound were chosen. The results in Figure 5] confirm that incorrect empirical bounds (green lines) have adverse effects on both methods, while a priori bounds do not seem to have any significant effect. We conclude that the tight sample-speciff lower bounds from our QGRAPH are key and much more informative than more general bounds.
6.6 LIMITED GRAPH CAPACITY
In deep reinforcement learning, the replay memory is typically a FIFO-buffer ('first in, first out'), ), i.e. those elements that were added first are overwritten first when the buffer is full. For a data graph, is possible to delete single transitions but there are two possible effects: On the one hand, some information from deleted transitions can be implicitly contained in its predecessors' Q-values on the QGRAPH, which could imply that our method is more robust to small memory capacities. On the other hand, cuts from deleted transitions can stop information propagation through the QGRAPH, which could in turn slow down further progress. We therefore empirically compared the drop in performance for vanilla DDPG and our QGRAPII-bounded Q-learning with graph capacities of 1000 and 5000 transitions. For comparison, the average unlimited graph contained roughly 30,000 unique transitions at the end of our 300 episode experiments. As the right plot in Figure 5) illustrates, a QGRAPH based method that is limited to only 1000 samples still performs on par with unlimited vanilla DDPG, while the vanilla DDPG performance decreases for a limit of 1000 transitions. Higher graph capacities do not seem to impact performance significantly.
7 CONCLUSION
From the observation that even for continuous state and action spaces, model-free off- deep reinforcement learning algorithms perform network updates on a finite set of transitions, we have developed graph perspective on the replay memory that allows closer analysis and induces new MDP under the assumption that the replay memory is complete. In this setting, two types of struc- tures are most likely to lead to soft divergence: non-terminal states without successors, for which the Q-value is conceptually ill-defined; and infinite loops with no path to a terminal state.
It is possible however construct simplified MDP from subgraph for which all Q-values well-defined and can be analytically computed. In deterministic environments, these Q-values are lower bounds for the Q-values of the original MDP: in probabilistic environments some further assumptions are required to apply lower bounds. Enforcing these bounds in TD-learning solves Baird's classical star problem and empirically prevents cases of soft divergence on continuous control task. The bounds can also be seen as way to spread information back along the full trajectory without the increase in gradient variance that is linked to Monte Carlo Backups. The largest effect was found for those hyperparameters that lead to worst performance, supporting the view that our method prevents some degenerate cases in function approximation for model-free off-policy deep reinforcement learning. Additionally, the QGRAPH that holds the lower bounds, provides an additional kind of memory for information from transitions which have already been overwritten in the replay memory.
This work gives rise to series of questions for future work: there may be tighter bounds including data-driven upper bounds, the formulation for probabilistic environments may be extended to cover further cases, and the reward function most likely interacts with soft divergence and indirectly with method. We may thus examine potential implications for reward shaping in the future.
8

---

Under review as a conference paper at ICLR 2020
REFERENCES
Artemij Amiranashvili, Alexey Dosovitskiy, Vladlen Koltun, and Thomas Brox. Td or not td: Ana- lyzing the role of temporal differencing deep reinforcement learning. In International Confer- ence on Learning Representations (ICLR), 2018.
Anonymous. Episodic reinforcement learning with associative memory. In Submitted to Interna tional Conference on Learning Representations, 2020. URL httpp::/cppaeeeieew...o
Eorum?ide www.uniid-kxjjxBBBXXC under review.
Leemon Baird. Residual algorithms: Reinforcement learning with function approximation. In Machine Learning Proceedings 1995, pp- 30-37. Elsevier, 1995.
Leemon C Baird. Reinforcement learning through gradient descent. PhD thesis, Carnegie Mellon adm. cs cmu, edu/anon/1999/
University, 1999. URL hatp::/reports-aazee
CC0-CC-99--0 132 pdf
Andreas Doerr, Michael Volpp, Mare Toussaint, Trimpe Sebastian, and Christian Daniel. Trajectory- based off-policy deep reinforcement learning. International Conference on Machine Learning. pp. 1636-1645, 2019.
Honghua Dong, Jiayuan Mao, Xinyue Cui, and Lihong Li. Explicit recall for efficient exploration, 2019. URL http:p///pppeerrrreveeeeeerrrrrr GIBBAAY
Gregory Farquhar, Tim Rocktaeschel, Maximilian Igl. and Shimon Whiteson. TreeQN and ATreec: Differentiable tree planning for deep reinforcement learning. In International Confer- ence on Learning Representations, 2018. URL htttts:://peeeeeeeeeeee
net fest/forum?id
H1ch6Ax0Z
Nima Fazeli, Samuel Zapolsky, Evan Drumwright, and Alberto Rodriguez. Learning data-efficient rigid-body contact models: Case study of planar impact. In Conference Robot Learning, pp- 388-397, 2017.
Scott Fujimoto, David Meger, and Doina Precup. Off-policy deep reinforcement learning without exploration. International Conference on Machine Learning, pp. 2052-2062, 2019.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Delving deep into rectifiers: Surpassing human-level performance imagenet classification. In Proceedings of the IEFF international conference on computer vision, pp. 1026-1034, 2015.
Peter Henderson, Riashat Islam, Philip Bachman, Joelle Pineau, Doina Precup, and David Meger. Deep reinforcement learning that matters. In Thirty-Second AAAI Conference Artificial Intel- ligence, 2018.
Aviral Kumar, Justin Fu, George Tucker, and Sergey Levine. Stabilizing off-policy q-learning via bootstrapping error reduction. arXiv preprint arXiv: 00949, 2019.
Kanghoon Lee and Kee-Eung Kim. Tighter value function bounds for bayesian reinforcement learn- ing. In Twenty-Ninth AAAI Conference on Artificial Intelligence, 2015.
Sergey Levine, Peter Pastor, Alex Krizhevsky, and Deirdre Quillen. Learning hand-eye coordination for robotic grasping with deep learning and large-scale data collection. CoRR, abs//603.00 1603.02199, 2016.
Timothy Lillicrap, Jonathan Hunt, Alexander Pritzel, Nicolas Heess, Tom Erez, Yuval Tassa, David Silver, and Daan Wierstra. Continuous control with deep reinforcement learning. arXiv preprint wwX.v:/500.02971,. 2015.
Hamid Reza Maei, Csaba Szepesvári, Shalabh Bhatnagar, Doina Precup, David Silver, and Richard S. Sutton. Convergent temporal-difference learning with arbitrary smooth function ap- proximation. In NIPS, 2009.
Hamid Reza Maei, Csaba Szepesvári, Shalabh Bhatnagar, and Richard S Sutton. Toward off off-policy learning control with function approximation. In ICMI,, pp. 719-726, 2010.

---

Under review as a conference paper at ICLR 2020
Horia Mania, Aurelia Guy, and Benjamin Recht. Simple random search of static linear policies is competitive for reinforcement learning. In Advances in Neural Information Processing Systems, pp. 1800-1809, 2018.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Mare G Belle- mare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, et al. Human-level control through deep reinforcement learning. Nature, 518(7540):529, 2015.
Volodymyr Mnih, Adria Puigdomenech Badia, Mehdi Mirza, Alex Graves, Timothy Lillicrap, Tim Harley, David Silver, and Koray Kavukcuoglu. Asynchronous methods for deep reinforcement learning. International Conference on Machine Learning, pp. 1928-1937, 2016.
Rémi Munos, Tom Stepleton, Anna Harutyunyan, and Mare Bellemare. Safe and efficient off-policy reinforcement learning. In Advances in Neural Information Processing Systems, pp. 2016.
Harm van Seijen, Shimon Whiteson, Hado van Hasselt, and Marco Wiering. Exploiting best-match equations for efficient reinforcement learning. Journal of Machine Learning Research, 12(Jun): 2045-20944 2011.
A Shkolnik and R Tedrake. Path planning in 1000+ dimensions using task-space voronoi bias. Robotics and Automation, pp. 2061-2067, 2009.
David Silver, Julian Schrittwieser, Karen Simonyan, loannis 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)3354, 2017.
Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
Hado Van Hasselt, Yotam Doron, Florian Strub, Matteo Hessel, Nicolas Sonnerat, and Joseph Mo- dayil. Deep reinforcement learning and the deadly triad. arXiv preprint urXiv:1812.02660 2018.
10

---

Under review as a conference paper at ICLR 2020
A
APPENDIX
A.1 PEG-IN-HOLE ENVIRONMENT DETAILS
The environment was implemented using A blue peg supposed to inserted into green object (see Figure 3). The peg is always upright and velocity velocity-controlled:: an action represents the dineedimeesional offset to the next position. The simulation stepped forward until a stable new position is reached. The actions are box-constrained to [-1, 1] in each dimension which corresponds to a movement of lem. The green object has a width of 5cm and is within a cubic state space of width 20cm. The peg has diameter of lem, the hole's diameter is 2cm. The agent receives distance-based reward 7 = exp( 0.03 1, where is the Euclidean distance to the goal position in meters.
A.2 NETWORK DETAILS
The critic network consists of three fully connected layers with 200 nodes each. For the inner layers, ReLU activations were used. The network was initialized with weights sampled from normal distri- bution of mean O and std 0.001. The actor network also consists of three fully connected layers with 200 nodes each, but used tanh activations and was initialized from a He-uniform distributions (He) al. 2015).
All neural networks were implemented using tensorflow and optimized using the AdamOptimizer, with 50 training epochs after each episode (i.e. 200 agent steps) and up to 15 random mini batches of data per epoch.
A.3 DETAILED PERFORMANCE FOR DIFFERENT LEARNING RATES
We ran vanilla DDPG a grid of learning rates where both actor and critic learning rates is cho- sen from (10-2 10-3 3 10 10-4). We chose the three curves with solid lines as representative for the spectrum performance and based all further evaluation on these learning rates.
C10-1AA110
A,10
-25
C10-1,
A11
-50
A110
cumulative reward
A10-
A110
A1101
1,10
-150
-200
100
200
250
episodes
Figure 7: Vanilla DDPG performance for all tested learning rates.
3et
www.tensorflo.orgg

---

Under review as a conference paper at ICLR 2020
A.4 STATE-ACTION PAIRS TESTED FOR VARIANCE PREDICTED Q- D-VALUES
Here we show all states and actions that were used to examine the variance in Q-estimates in ure 6
Fig-
Or
4y
0z
0
0
0
0
0
1
Znd
0
0
-1
0
1
0
0
-1
0
1
0
0
-1
0
0
0.5
0.5
0.5
Zuna
-0.5
-0.5
-0.5
Yess
1
1
Xmn
-1
-1
-1
Yaa
12


Reviews:
[{"review_id": "rygpYvGTKr", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "\nThe paper proposes Qgraph, an algorithm that  addresses the problem of extrapolation error that appear in RL tasks with continuous action spaces. The authors describe a method to construct a graph from transitions generated by some policy. In this graph nodes correspond to states and (s, a, r, s’, t) define transitions between these nodes. Then this representation is simplified and  used to compute Q-values using methods for tabular MDPs.\n\nThe related work section is missing several methods that attempt to address the same problem. Batch Constrained Q-learning (Fujimoto etal, 2018) introduces a formulation of Q-learning that constrains action selection with a generative model trained on a replay buffer in order to omit unseen actions. BEAR-QL (Kumar etal, 2019) describes a similar approach that uses a hard constraint based on MMD. It would be interesting to discuss connections with the recent work on off-policy batch RL.\n\nThe clarity of the paper can be improved. In particular, I have several questions regarding the method:\n1) How are node of the graph are constructed? Does one state correspond to a single node or several states are merged into a different node?\n2) How the actions are selected?\n3) What are the assumption regarding the initial state distribution? Does the set of initial states have to be finite?\n4) If two similar states appear in different branches of the graphs, are the corresponding nodes merged or not?\n5) If the considered environments are deterministic, what is the motivation for stochastic approximation of dynamic programming?\n\nThe approach has several major limitations. One of the main limitations of the approach is that it can be applied only to deterministic tasks. Although it is not stated clearly in the paper, it seems also requires to have a finite set of initial states. \n\nThe experimental evaluation is performed on a limited set of tasks and it is rather unclear whether the method can be scaled to higher dimensional control problems.\n\nOverall, I feel that the paper needs to be significantly improved. \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 at least twice and used my best judgement in assessing the paper.", "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": "HJgus3ATFH", "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 is trying to tackle the soft divergence issue in deep RL when algorithms combine function approximation, off-policy learning and bootstrapping, which is also called deadly triad by Sutton & Barto (2018). The paper proposes a way to represent the transitions in the replay memory as a data graph, then construct a simple MDP from it. Much more accurate Q values could be computed from the simple MDP and it provides a lower bound for the Q-values in the original problem. In this way, the method becomes less prone to soft divergence.\n\nThe idea of constructing a smaller MDP whose Q-values can be computed exactly by dynamic programming on tabular states, then use these Q-values to help dealing with the instability issues in deep RL is very interesting. In the rebuttal, I'd like the authors to address my major concern of the paper, where the proposed method seems to assume that the finite number of transitions could form a graph, which might not be always true. In typical continuous state spaces, the same state might not appear twice in the sampled transitions. In these cases, the graph becomes a number of disconnected chains and the Q-values from this MDP might not be accurate. Maybe I'm missing something, it's not very clear to me how the proposed method could be applied in the common case in deep RL where there's seldom a loop and the states are rarely visited twice. ", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "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": "HJg27xDRtH", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 1, "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 paper aims to build an understanding of deep RL. Because RL remains under-investigated from a theoretical point of view. Many algorithms use function approximation, off-policy learning and bootstrapping together--This is an unstable combination of techniques. In this paper, the authors propose a graph-perspective on the replay memory which allows to analyze the structure of deep RL.\n\nThe paper aims at an important issue in deep RL. The motivation of the paper is meaningful.\nThe paper gives a good summary of the previous related works in Section2.\n\nThe paper in the current form needs to be polished again. To obtain a better score, I suggest the authors to modify this paper in these ways: First, the introduction section needs to provide more details, including the pros and cons of previous related works on the research problem of this paper, the challenges you face when dealing with this issue and the contributions; Second, there were more than a few spelling and grammatical errors, please proofread the work and improve the writing; Third, the paper lacks logic in writing. The writing from Section.2 to Section.6 needs to be organized better. It is difficult for readers to grasp the key ideas of the paper through a quick assessment.\nThe paper focuses on the understanding of RL when deep Q-learning diverges, however, most of the conclusions in the paper are not based on the necessary theoretical proof, but the observations on the experiments.\n\nIt would be better if this paper can provide a clear illustration for the proposed method as well as the experiments section.", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I made a quick assessment of this paper.", "review_assessment:_checking_correctness_of_experiments": "I did not assess the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "N/A"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes a method to reduce the instability issues of off-policy deep reinforcement learning.  The proposed solution constructs a simple MDP from the experience in the agent's replay memory.  This graph is used to compute a lower bound for the values from the original problem. Incorporating this bound can make the learning system less prone to soft divergence.

The reviewers appreciated the motivation of the paper and the direction of this research.  However, the reviewers were not convinced that the formulation was sufficiently complete.  There were concerns that the method makes additional assumptions about the data distribution (the presence of state aggregation and the absence of repeated states in continuous spaces).  Reviewers found related work was missing.  The reviewers also found multiple aspects of the presentation unclear even after the author response.  

This paper is not ready for publication as the generality of the proposed method was not sufficiently clear to the reviewers after the author response.
Decision: Reject