DeepAveragers: Offline Reinforcement Learning By Solving Derived Non-Parametric MDPs
Authors: Aayam Kumar Shrestha
Stefan Lee
Prasad Tadepalli
Alan Fern
Venue: ICLR 2021 Spotlight (2021)
Keywords: Offline Reinforcement Learning
Planning

Abstract: We study an approach to offline reinforcement learning (RL) based on optimally solving  finitely-represented  MDPs  derived  from  a  static  dataset  of  experience. This approach can be applied on top of any learned representation and has the potential to easily support multiple solution objectives as well as zero-shot adjustment to changing environments and goals.  Our main contribution is to introduce the Deep Averagers with Costs MDP (DAC-MDP) and to investigate its solutions for offline RL.  DAC-MDPs are a non-parametric model that can leverage deep representations and account for limited data by introducing costs for exploiting under-represented parts of the model.  In theory, we show conditions that allow for lower-bounding the performance of DAC-MDP solutions. We also investigate the empirical behavior in a number of environments, including those with image-based observations. Overall, the experiments demonstrate that the framework can work in practice and scale to large complex offline RL problems.

Published as a conference paper at ICLR 2021
DEEPAVERAGERS: OFFLINE REINFORCEMENT LEARN- ING BY SOLVING DERIVED
MDPs
Aayam Shrestha, Stefan Lee, Prasad Tadepalli, Alan Fern
Oregon State University Corvallis, OR 97330, USA (shrestaa, leestef, tadepall, alan. alaerfeeen
ABSTRACT
We study an approach to offline reinforcement learning (RL) based on optimally solving represeyeeeeesentee MDPs derived from static dataset of experience. This approach can be applied on top of any Iearned representation and has the potential easily support multiple solution objectives well zero-shot adjust- ment to changing environments and goals. Our main contribution is to introduce the Deep Averagers with Costs MDP (DAC-MDP) and investigate its solutions for offline RL. DAC-MDPs are a non-parametric model that can leverage deep representations and account for limited data by introducing costs for exploiting under-represented parts of the model. In theory, we show conditions that allow for lower-bounding the performance of DAC-MDP solutions. We also investigate the empirical behavior in a number of environments, including those with image- based observations. Overall, the experiments demonstrate that the framework can work in practice and scale to large complex offline RL problems.
INTRODUCTION
Research in automated planning and control has produced powerful algorithms to solve for optimal, or near-optimal, decisions given accurate environment models. Examples include the classic value- and policy-iteration algorithms for tabular representations or more sophisticated symbolic variants for graphical model representations (e.g. [Boutilier et al. (2000); |Raghavan et al. (2012)). In concept, these planners address many of the traditional challenges in reinforcement learning (RL). They can perform "zero-shot transfer" to new goals and changes to the environment model, accurately account for sparse reward or low-probability events, and solve for different optimization objectives (e.g- robustness). Effectively leveraging these planners, however, requires an accurate model grounded in observations and expressed in the planner's representation. On the other hand, model-based reinforcement learning (MBRL) aims to learn grounded models to improve RL's data efficiency. Despite developing grounded environment models, the vast majority of current MBRL approaches do not leverage near-optimal planners to help address the above challenges. Rather, the models are used as black-box simulators for experience augmentation and/or Monte-Carlo search. Alternatively, model learning is sometimes treated as purely auxiliary task support representation learning.
The high-level goal of this paper is to move toward MBRL approaches that can effectively leverage near-optimal planners for improved data efficiency and flexibility complex environments. How- ever, there are at least two significant challenges. First, there is mismatch between the deep model representations typically learned in MBRL (e.g. continuous state mappings) and the representations assumed by many planners (e.g. discrete tables or graphical models). Second, near-optimal planners are well-known for exploiting model inaccuracies in ways that hurt performance in the real environ- ment, e.g. (Atkeson, 1998). This second challenge is particularly significant for offline RL, where the training experience for model learning fixed and limited.
We address the first challenge above by focusing tabular representations, which are perhaps the simplest, but most universal representation for optimal planning. Our main contribution an offline MBRL approach based on optimally solving MDP (DAC-MDP). DAC-MDP a non-parametric model derived from an experience dataset and corresponding (possibly learned) latent state representation. While the DAC-MDP is defined over the entire continuous latent state space, its full optimal policy can be computed by solving standard (finite) tabular MDP derived from the dataset. This supports optimal planning via any
model called the Deep Averagers with Costs

---

Published as a conference paper at ICLR 2021
Experiential Dataset
Derived Finite DAC-MDP Core
Salved DAC-MDP via Value Iteration
DAC-MDP Over Continuous State Space
(21.42)5211)
Compille
Value Iteration
1-step KNN
(22))))))))
DACMDP
look-ahead
Offline Reinforeement Learning Setting
Unseen States Online
Figure I: Overview of Offline RL via DAC-MDPs, Given static experience dataset, we first compile it into finite tabular MDP which is most the size of the dataset. This MDP contains the "core" states of the full continuous DAC-MDP. The finite core-state MDP is then solved via value iteration, resulting in policy and Q-value function for the core states. This finite Q-function used to define a non non-paraeetric Q-function for the continuous DAC-MDP, which allows for Q Q-values and hence a policy to be computed for previously unseen states.
tabular MDP solver, e.g. value iteration. To scale this approach typical offine RL problems, we develop a simple GPU implementation of value iteration that scales to millions of states. As an additional engineering contribution, this implementation will be made public.
To address the second challenge of model inaccuracy due to limited data, DAC-MDPs follow the pessimism in the face of uncertainty principle, which has been shown effective number of prior contexts (e.g. (Fonteneau et al., 2013)). ). In particular, DAC-MDPs extend Gordon's Averagers framework (Gordon| 1995) with additional costs for exploiting transitions that are under-represented in the data. Our second contribution is to give a theoretical analysis of this model, which provides conditions under which a DAC-MDP solution will perform near optimally in the real environment.
Our final contribution is to empirically investigate the DAC-MDP approach using simple latent rep- resentations derived from random projections and those learned by Q-iteration algorithms. Among other results, we demonstrate the ability to scale to Atari-scale problems, which is the first demon- stration of optimal planning being effectively applied across multiple Atari games. In addition, we provide case studies in 3D first-person navigation that demonstrate the flexibility and adaptability afforded by integrating optimal planning into offline MBRL. These results show the promise of our approach for marrying advances in representation learning with optimal planning.
2 FORMAL PRELIMINARIES
A Markov Decision Process (MDP) is tuple AS, R) (Puterman 1994). with state set S, ac- tion set A, transition function T(s, a, 8'), and reward function R[s a). A policy a maps states actions and has Q-function Q" a) giving the expected infinite-horizon 3-discounted reward of following after taking action a in s. The optimal policy π maximizes the Q-function over all policies and state-action pairs. Q" corresponds to the optimal Q-function that satisfies (s) arg max, (*(ss,) (s) Q" can be computed given the MDP by repeated application of the Bellman Backup Operator B, which for any Q-function Q, returns a new Q-function given by,
B()](s, R(s,a) a) + +TEg-T((a..) max Q()..a)).
The objective of RL is to find a near-optimal policy without prior knowledge of the MDP. In the online RL setting, this is done by actively exploring actions in the environment. Rather, in the offline RI. (Levine et al. 2020), which is the focus of this paper, learning is based on static dataset D {si, 04 Tı, {.)). where each tuple gives the reward r, and next state &f observed after taking action a; in state 8t.
In strict offline RL setting, the final policy selection must be done using only the dataset, without direct access to the environment. This includes all hyperparameter tuning and the choice of when to stop learning. Evaluations of offline RL, however, often blur this distinction, for example, reporting performance of the best policy obtained across various hyperparameter settings evaluated via new online experiences (Gulcehre et al. 2020). Here we consider an evaluation protocol that makes the amount of online access to the environment explicit. In particular, the offline RL algorithm is
2

---

Published as a conference paper at ICLR 2021
allowed to use the environment to evaluate Ne policies (e.g. average repeated trials for each policy), which, for example, may derive from different hyperparameter choices. The best of the evaluated policies can then be selected. Note that Nº corresponds to pure offline RL.
3 DEEP AVERAGERS WITH COSTS MDPs (DAC-MDPS)
From a practical perspective our approach carries out the following steps as illustrated in Figure T (1) We start with static experience dataset, where the states are assumed come from continuous latent state space. For example, states encoded via random or learned deep representations. (2) Next we compile the dataset into tabular MDP over the "core states" of the DAC-MDP (those in the dataset). This compilation uses k-nearest neighbor (kNN) queries to define the reward and transition functions (Equation 2) functions of the core states. (3) Next we use GPU implementation of value iteration to solve for the tabular MDP's optimal Q-function. (4) Finally, this tabular Q-function is used to define the Q-function over the entire DAC-MDP (Equation 3) Previously unseen states at test time are assigned Q-values and in turn policy action via KNN queries over the core states.
Conceptually, our DAC-MDP model is inspired by Gordon's 's (1995) early work that showed the con- vergence of (offline) approximate value iteration for a class of function approximators; averagers, which includes methods such as k nearest neighbor (kNN) regression, among others. It was also ob- served that approximate value iteration using an averager was equivalent to solving an MDP derived from the offline data. That observation, however, was not investigated experimentally and has yet to be integrated with deep representation learning. Here develop and evaluate such an integration.
The quality of an averagers MDP, and model-learning in general, depends on the size and distribution of the dataset. In particular, optimal planner can exploit inaccuracies in the underrepresented parts of the state-action space, which can lead to poor performance in the real environment. The DAC- MDPs aim avoid this by augmenting the derived MDPs with costs/penalties on under-represented transitions. This turns out to be essential to achieving good performance on challenging benchmarks.
3.1 DAC-MDP DEFINITION
A DAC-MDP is defined terms of an experience dataset D = {(s,, as Fi, 8{)) from the true MDP M with continuous latent state space S and finite action space A. The DAC-MDP M = (S, A. R, T) shares the same state and action spaces as M, but defines the reward and transition functions in terms of empirical averages over the k nearest neighbors of (s, a) in D.
The distance metric d(s, a, s', a') gives the distance between pairs (s,a) and (s',a'). This met- ric considers (s.a) pairs with different actions be infinitely distant. Otherwise, the distance be- tween pairs involving the same action is the euclidean distance between their states. In particular, the distance between (s, a) and data tuple (st, at, s() is given by d(s,, a, St, az). Also, we let KN N (s, a) denote the set of indices of the k nearest neighbors to (s, a) in D, noting that the depen- dence on D and d is left implicit. Given hyperparameters & (smoothing factor) and C' (cost factor) we can now specify the DAC-MDP reward and transition function.
A(s a) K
Σ ri C-C. a(s,a, az), (EKNN(s.O)
T(s,a,8) I (E.NN((s.)
Σ T|s'= (2)
The reward for (s, a) is simply the average reward of the nearest neighbors with a penalty for each neighbor that grows linearly with the distance neighbor. Thus, the farther (s, a) is its nearest neighbor set, the less desirable its immediate reward will be. The transition function is simply the empirical distribution over destination states of the nearest neighbor set.
Importantly, even though a DAC-MDP has an infinite contimuous state space, it has a special finite structure. Since the transition function T only allows transitions to states appearing as destination states in D. We can view M as having a finite core set of states Sp = {s{ (si, a; ri, +f) E D)- States in this core do transition to non-core states and each non-core state immediately transitions to the core for any action. Hence, the value of core states is not influenced by non-core states. Further, once the core values are known, we can compute the values of any non-core state via one- step look ahead using T. Thus, we can optimally solve a DAC-MDP by solving just its finite core
Specifically, let Q be the optimal Q-function of M. We can compute Q for the core states by solving the finite MDP MD (Sp. A, R, T). We can then compute Q for any non-core state demand
3

---

Published as a conference paper at ICLR 2021
via the following one-step look-ahead expression M, denoted ã. using any solver of finite MDPs.
This allows us compute the optimal policy of
((s
1
Σ
Ti T Y max m C -d((s,,ddss a, s;,
(3)
k
(s,,)(ss.))
3.2 DAC-MDP PERFORMANCE LOWER BOUND
We are ultimately interested in how well the optimal DAC-MDP M policy т performs in the true MDP M. Without further assumptions, म can be arbitrarily sub-optimal in M, due potential "non- smoothness" of values, limited data, and limited neighborhood sizes. We now provide a lower-bound on the performance of in M that quantifies the dependence these quantities. Smoothness is characterized via Lipschitz smoothness assumptions B[Q], where B is the Bellman operator for the true MDP and Q the optimal Q-function for M using hyperparameters and C. In particular, we assume that there is a constant L(k, C), such that for any state-action pairs (s, a) and (5',
BiQ](s, Bi .')) - L(k, C) a'',a')
This quantifies the smoothness of the Q-function obtained via one-step look-ahead using the true dynamics The coverage of the dataset is quantified in terms of the worst case average distance to a KNN set defined by dmaz=max,
(iERNN(s.a)) d(s, a, 8;. az). The bound also depends on Qman= Tmax= ( a) and My which is the maximum number of distinct kNN sets over dataset of size N. For L2 distance over d-dimensional space,MN,t bounded by O ((+:N)++1)
Theorem 3.1. For any data set D size N, let Q and π be the optimal Q-function and policy for the corresponding DAC-MDP with paramelers k and C. 1f B[Q) is Lipshitz continuous with constant L.k, C), then with probubility at least 1 1-6,
V=2V* V 2 (L(k, C): dmax c (k))
2MN.K
N,) = -V 2k
1-7
which for 1.2 distance over d-dimensional space yields c(k: N, (v (dIn In
The fall proof is in the Appendix A.22 The first term in the bound characterizes how well the dataset represents the MDP from a nearest neighbor perspective. In general, dyna decreases as the dataset becomes larger. The second term characterizes the variance of stochastic state transitions in the dataset and decreases with the smoothness parameter Counter-intuitively we see that for Eu- clidean distance, the second term can grow logarithmically in the dataset Tize.This worst-case be- havior is due to not making assumptions about the distribution of source states-actions in the dataset. Thus, can't rule out adversarial choices that negatively influence the kNN sets of critical states.
Practical Issues: There are some key practical issues of the framework regarding the scalability of VI and selection of hyperparameters. We exploit the fixed sparse structure of DAC-MDPs along with parallel compute afforded by GPUs to gracefully scale our VI to millions of states. This can provide anywhere between 20- 20- 1000x wall clock speedup over its serial counterpart. To reduce the sensitivity to the smoothness parameter k, we use weighted averaging based on distances to nearest neighbors instead of uniform averaging in Equation 2 Furthermore, we use different smoothness parameter k and k, to build the DAC-MDP and compute the policy respectively. We find that using larger values of ki is generally beneficial to reduce the variance. Finally we use simple rule-of- thumb of setting cost factor C' to be in the order of magnitude of observed rewards. These choices are further elaborated in detail appendix A.
3.3 REPRESENTATION LEARNING
While DAC-MDPs can be defined over raw observations, for complicated observation spaces, such as images, performance will likely be poor in practice for simple distance functions. Thus, com- bining the DAC-MDP framework with deep representation learning critical for observation-rich
Note that we can get V using value iteration on Mr. Q can then be computed via 1-step lookup as ((.,a)= a)) + Everrony a().a,')) ((a)
4

---

Published as a conference paper at ICLR 2021
Average Return ve Cost paramoter C
Average relurn ve MDP build parameter k
Average return va policy ift perammeter K
600
520
500
Groady Palay
400
1e-03
420
Greedy Pallyy
400
300
0.1
800
300
PB0
P00
5.0
Te-05
100
15.0
Randon MicwlBag
Delosel Optimrraagg
PondonnSSg
MoneBBg
Optmatlig
Rendon Bag MioelBagg Optimatlaag
Version
Vertaion
Figure 2: (a) Greedy Policy performance for CartPole with varying (a) cost paramter C. (b) smoothness
parameter k. (c) policy smoothing parameter 7
environments. Since the primary focus of this paper is on the introduction of DAC-MDPs, rather than representation learning. below describe three basic representation-llariig approaches used in our experiments. An important direction for future work is to investigate the effectiveness of other alternatives and develop representation-leanne
specifically for the DAC-MDP framework.
Random Projection (RN This baseline simply produces a representation vector as the out- put of a chosen network architecture with randomly initialized weights (e.g. CNN with random weights for images). Offline DQN (DQN): From the first term of Theorem 3.1 we see that de- creasing the Lipschitz constant of B[Q] can improve the performance bound. This suggests that a representation that is smooth with respect to the Q-function can be beneficial. For this purpose, our second representation directly uses the penultimate layer of DQN (Mnih et al. (2013) after it has been trained on our offline dataset D. Since the penultimate layer just linear mapping away from the DQN Q-values, it is reasonable to believe that this representation will be smooth with respect to meaningful Q-functions for the environment. BCQ Imitation (BCQ): The offline RI. algorithm BCQ (Fujimoto et al.] 2019) trains an imitation network to emulate the action distribution of the behavioral policy. This policy is used to help avoid backing up action values for under--epresented actions. We the penultimate layer of the imitation network trained type of representation. This representation is not as well-motivated by our performance bounds, but intuitively appealing and provides policy-centric contrast to Q-value modeling.
dataset as the third
4 EXPERIMENTS
The experiments are divided into three sections. First, we present exploratory experiments in Cart- pole to illustrate the impact of DAC-MDP parameters using an idealized representation. Second, we demonstrate the scalability of the approach on Atari games with image-based based observations. Finally, we demonstrate use-cases enabled by our planning-centie approach in a 3D first-person domain.
Exploring DAC-MDP Parameters: We explore the impact of the DAC-MDP parameters in Cart- pole. To separate the impact of staterrepresentation and DAC-MDP parameters, we use the ideal state representation consisting of the true d-dimensional system state. We generate three datasets of size 100k each: (1) Randommag (V** 20) Fl Trajectories collected by random poli- cies. (2) Oplimallaay (V** 140): Trajectories collected by well-trained DQN policy. (3) Mized (V*8- 500): Trajectories collected by mixed bag of e-greedy DQN policies using e E [0, 0,,, 0.2, 0.6, 1).
We first illustrate the impact of the cost parameter C by fixing k = K2 = and varying C' from 0 to 1e6. Figure 2 shows that for all datasets when there no penalty for under-represented transitions, i.e. C= 0 the policy is extremely poor. This shows that even for this relatively simple problem with a relatively large dataset, the MDPs from the original cost-free averagers framework, can yield low-quality policies. At the other extreme, when C' is very large, the optimal policy tries to stay as close as possible to transitions in the dataset. This results in good performance for the OptimalBag dataset, since all actions are near optimal. However, the policies resulting from the MixedBag and RandomBag datasets fail. This is due to those datasets containing a large number of sub-optimal actions, which the policy should actually avoid for purposes of maximizing reward. Between these extremes the performance is relatively insensitive to the choice C.
Figure p explores the impact of varying & using ky and C = 1. The main observation is that there is a slight disadvantage to using k- = 1. which defines a deterministic finite MDP, compared to k 1, especially for the non-optimal datasets. This indicates that the optimal planner is able
2 e is the expected performance of the hehavioral policy for the datasct.
5

---

Published as a conference paper at ICLR 2021
DOW
Abarts
Rowing
Alaent
Aesty
beabie (166)
Exrid En (1e6)
neaien (tel)
bontive (teds
taribiis (166)
boniion (166)
Figure 3: Results on Atari 100K (left)BQQ (right) DQN. Each agent is trained for 100K iterations(training steps), and evaluated 10 episodes every 10K steps. At each of these evaluation checkpoints, we use the internal representation compile DAC-MDPs. We then evaluate the DAC-MDPs for N: = 6. Runs averaged over 5 seeds and error bars plot the 95% confidence interval.
RCG BAC ACO,
DAC AMC--CCO-L M RCO 20
1:90
Del DON remaatzd
t0
1:30
5.00
80
0,000
0.23
1.
DOW
SAC DDN
Freneon
Anwaer
Pors
Sreabar Seacelwadee Ohis
Atart
boviro Frenwis
Aeado
Figure 4: Results for different sets of candidate policies Ne 100K dataset. Here we plot the final perfor-
mance of BCQ representation (left) and DQN representation (right) along with the DAC-MDP performances for different values of Ne. Runs averaged over 5 seeds. Error bars plot the 95% confidence interval.
to benefit by reasoning about the stochastic transitions of the DAC-MDP for k > 1. Otherwise the results are relatively insensitive to k. We set k = 5 for remaining experiments unless otherwise stated. Finally, Figure ? varies the policy smoothing parameter kig from 1 to 31. Similar to the results for varying k, there is a benefit to using value of k2 > 1, but otherwise the sensitivity is low. Thus, even for this relatively benign problem setting, some amount of averaging at time appears beneficial. We find that DAC-MDPs are slightly more sensitive to these parameters in low data regime. Similar experiments for low data regime are presented in Appendix AA.4 AA.4
We choose 8 stochastic Atari games ranging from small to medium action spaces: Pong, Breakout, Space Invaders, Q Bert, Atlantis, Bowling, Freeway, and Amidar. These are stochastic in nature as sticky actions have been enabled. Following recent work (Fujimoto et al.) 2019), we generate datasets by first training a DQN agent for each game. Next, to illustrate perfor- mance small datasets and scalability larger datasets, we generated two datasets of sizes 100K and 2.5 million for each game using an e-greedy version of the DQN policy. In particular, each episode had 0.8 probability of using 0.2 and 0.001 otherwise. This ensures mixture of both near optimal trajectories and more explorative trajectories.
Experiments on Atari:
We first trained offline DQN and BCQ agents on the 100K dataset for 100K iterations and evaluated on 10 test episodes every 10K iterations. At each evaluation iteration, we construct DAC-MDPs using the latent state representation at that point. We consider offline RL setting where N.=6, i.c. we evaluate 6 policies (on 10 episodes each) corresponding to 6 different DAC-MDPs, set to a parameter combination of k=5, (E(1, 100, LM1 }, and k, E 51]. For each representation and evalutaion point, the best performing DAC-MDP is recorded. The entire 100K iteration protocol was repeated times. Figure 3 shows the averaged curves with 90% confidence intervals.
The main observation is that for both BCQ and DQN representations the corresponding DAC-MDP performance (labeled DAC-BCQ and DAC-DQN) is usually better than BCQ or DQN policy at each point. Further, the DAC-MDP performance is usually better than the maximum performance of pure BCQ/DQN across the iterations. These results point an interesting possibility of using DAC- MDPs to select the policy at the end of training at any fixed number of training iterations, rather than using online evaluations along the curve. Interestingly, the first point on each curve corresponds to random network representation which is often non-trivial in many domains. However, do that in many domains the DAC-MDP performance further improves as the representation is learned, showing that the DAC-MDP framework is able to leverage improved representations.
Figures 4 investigates the performance at the final iteration for different values of N For N = use k k, C -1 and for N. 20 we expand the parameter used for

---

Published as a conference paper at ICLR 2021
DAC AAD
BCQ
2.0
DON nomalzed
1.6
BAC - DOW
1.0
0.5
0.0
Pong
Breakoud
Specslmadrrs
Obart
Allntii
Buwling
Frueway
Ansidrr
Figure 5: Atari results for 2.5M dataset. We show the final performance of BCQ and DQN trained for 2.5M iterations. We also use the same representation for the DAC-MDPs named as DAC-BCQ and DAC-DQN respectively, All DAC-MDPs are evaluated with No 6.
N₂ 6 (1, 10, 100, 1000, 1M), and k E (5, 11, 31,11, First we see that in the majority of cases, even N₂ is able to perform as well or better than BCQ or DQN and that increasing N: often significantly improves performance. We do see that for three games, SpaceInvaders, QBert, and Atlantis, DAC-BCQ (N₂ = 1) is significantly worse than the BCQ policy. This illustrates the potential challenge of hyperparameter selection in the offline framework without the benefit of additional online evaluations.
Finally show results for all representation the 2.5M dataset in Figure In all but (Breakout DAC-DQN), we see that DAC-MDP improves performance or is no worse than the cor- responding BCQ and DQN policies. Further in most cases, the DAC-MDP performance improves over the Online DQN agent used to generate the dataset which was trained on 10M online transi- tions. While random representations perform reasonably some cases, they significantly out- performed by learned representations. These results show, for the first time, that optimal planning can result in non-trivial performance improvement across diverse set of Atari games. Given the simplicity of the representation learning and the difference between random and learned representa- tions, these results suggest significant promise for further benefits from improved representations.
Agent View
View
GESRO
Figure 6: Agent and top view for 3D Navigation domains. (left) Simple Room, (center) Box and Pillar Room and (right) Tunnel Room.
Illustrative Use Cases 3D Navigation: We now show the flexibility of an optimal planning approach using three use cases in Gym Mini-World (Chevalier-Boiswe) 2018), first-person con- tinuous 3D navigation environment. In all scenarios the agent has three actions: Move Forward, Tur Right, and Turn Left. Episodes lasted for maximum of 100 time steps. The raw observa- tions are 84x84 RGB images. We use random CNN representations in all experiments, which were effective for this environment. Our offline dataset was collected by following random policy for 100K time steps. In these experiments we use N, 2 with k = 5, k2 E {11, 51}, and C = 0.01. All the rooms used for the experiments and their optimal policies are visualized in fig [5al We also ea compare our approach against baselines (Dee/Bes(DNN/BC)) in Appendix A.6 and find that DAC-MDPs perform better and more consistently across the tasks.
Case 1: Adapting to Modified Action Space. We designed simple room with blue box in fixed position and an agent that spawned in a random initial position. The agent gets reward for bumping into the walls and a terminal reward of +1 for reaching the blue box. The DAC-MDP achieves an average total reward of 0.98 using the offline dataset. Next, we simulate the event that actuator is damaged, this would require retraining the agent on a modified dataset from scratch. Rather our DAC-MDP approach account for such scenario by simply attaching huge penalty to all left actions. The solution to this modified DAC-MDP achieves an average score of 0.96 and substantially different than the original since it must find revolving paths with just the turn right action.
that the agent is unable turn left. For most offline RL approaches
Case 2: Varying Horizons. We create a new room by adding a pillar in the simple room described above. Additionally, the agent gets small non-terminal reward of 0.02 for bumping into the pillar.

---

Published as a conference paper at ICLR 2021
Depending the placement of the agent and the expected lifetime of the agent it may be better to go for the single +1 reward or to repeatedly get the 0.02 reward. This expected lifetime can be simulated via the discount factor, which will result in different agent behavior. Typical offline RL approaches would again need to be retrained for each discount factor of interest. Rather, the DAC-MDP approach simply allows for changing the discount factor used by VI and solving for the new policy in seconds. Using small discount factor (0.95) our short-term agent achieves an average score of 0.91 by immediately attempting to get to the box. However, the long-term agent with larger discount factor (0.995) achieves a score of 1.5 by repeatedly collecting rewards from the pillar. Qualitative observation suggests that both policies perform close to optimally.
Case 3: Robust/Safe Policies. Our third room adds narrow passage to the box with cones on the side. Tunnel Room simulates the classic dilemma of whether to choose a risky or safe path. The agent can risk getting a -10 reward by bumping into the cones or can optionally follow longer path around an obstacle to reach the goal. Even with a relatively large dataset, small errors in the model can lead an agent along the risky path to occasionally hit a cone. To build robustness, we find an optimal solution to a modified DAC-MDP where at each step there is a 10% chance of taking random action. This safe policy avoids the riskier paths where a random "slip" might lead to disaster and always chooses the safer path around the obstacle. This achieved an average score of 0.72. In contrast, the optimal policy for the original DAC-MDP achieved an average score of 0.42 and usually selected the riskier path to achieve the goal sooner (encouraged by the discount factor).
Computation Time Analysis: DAC-MDP has explicit con- vergence guarantees; however, the stopping condition of DQN and BCQ is not clear. We follow previous works and use batch updates equal to the size of the dataset. We
40
DAC-AND DON
Wall Time (minukes)
30
BCQ
define the first run for set of hyperparameterr/hhccctie as an algorithm's initial run. We assume that the rep- resentation is learned in the initial run and frozen for secondary objectives. Here secondary objectives can in- compares the wall time of different approaches. Here we can see that DAC-MDPs are 2-4x faster for the initial run. For secondary objectives, however, we can see wall-time speedup of anywhere between 25-40x. In the initial run of DAC-MDPs, KNN lookupsFacccunt most of the computation time. Since can reuse the KNN lookups for any secondary objective, the VI solver dominates the runtime for the new run, which is much faster. For a large dataset of 2.5M, it takes 60-90 minutes compile the DAC-MDP and less than 3 minutes to solve the MDP.
20
310
clude new hyperparameter sets or goals. Fig 7
Initiaa Run
Secondary Objective
Objective
Figure 7: Comparison of Computation Cost for different appraoches. [100k Dataset]
account for
The memory consumption scales linearly with the state count, action space, and the smoothness parameter k. Fully compiled MDPs for 2.5M approximately ranges from 2-6GB depending on the action space. The current implementation is not fully optimized for memory however one can perform state space aggregation favor of memory efficiency.
RELATED WORK
Averagers Framework. Our work is inspired by the original averagers framework of Gordon 1995) which showed the equivalence of derived MDP to type of approximate dynamic programming.
A construction similar to the derived MDP was explored in later work (Jong & Stone 2007) within
an online RL setting. A model similar Gordon's 's derived MDP was later theoretically studied for efficient exploration in online continuous-see state RL (Pazis & Parr 2013). Due to its exploration goals, that work introduced bonuses rather than penalties for unknown parts of the space. [Ormoeii] & Glynn| (2002) adapts fitted value iteration Gordon & Mitchell (1999) to kernel based reinforce- ment learning. Furthermore OOmoneet & Sen (2002) studied the theoretical convergence and con- sistency properties of this algorithm when combined with kernel- based regressors. Within the same framework [Ernst et al. (2005) employed tree-based regression algorithms to show scalability in high- dimensional spaces. However, none of these approaches have been shown to scale to image based domains. Also, our work is the first to integrate the averagers derived MDP with pessimistic costs
CCurently, KNN lookups are performed by using CPU based KD-trees and has throughput of 5k Inokups/sec. However, leveraging GPU optimized KD-trees ( (Martin 2012 Hu al. (0155) seems promising reduce the wall time of the algorithm further.
8

---

Published as a conference paper at ICLR 2021
in order to make it applicable to offline RL. Our work is also the first to demonstrate the framework in combination with deep representations for scaling to complex observation spaces such as images.
Optimal Planning with Deep Representations. Recent work (Corneil et al. 2018) uses variational autoencoders with Gumbel softmax discretization to learn discrete latent representations. These are used to form tabular MDP followed by optimal planning in online RL setting. More recently, van der Pol et al. (2020) introduced a contrastive representation-larniig and model-learning ap- proach that used to construct and solve a tabular MDP. Experimental results in both of these works were limited to a small number of domains and small datasets. Unlike these works, which primar- ily focus on representation learning, our focus here has been on providing theoretically -rouunddd model, which can be combined with representation-leant learning. Works like Kurutach et al. (2018) are mostly focused on learning plannable representations than planning. Instead, they train a GAN to generate a series of waypoints which can then be is leveraged by simple feedback controllers. Also, Yang et al. (020) And/Aal et al. (2020) attempt to incorporate long term relationships into their learned latent space and employ search algorithms such as A and eliptical planners.
Episodic Control and Transition Graphs. Several prior approaches for online RL, sometimes called episodic control, construct different types of explicit transition graphs from data that are used
to drive model-free RL (Blundell et al. 2016 Hansen 2017 Pritzel et al.) 2017 Lin et al.) 2018 Zhu et al. 20200 Marklund et al. (020). None of these methods, however, use solutions produced by planning as the final policy, but rather as a way of improving or bootstrapping the value estimates of model-free RL. The memory structures produced by these methods have a rough similarity to deterministic DAC-MDPs with k = 1.
Pessimism for Offline Model-Free Based RL. Fonteneau et al. 2013) studied "trajectory based" simulation model for offline policy evaluation. Similar in concept to our work, pessimistic costs were used based on transition distances to "piece together" disjoint observations, which allowed for theoretical lower-bounds on value estimates. That work, however, did not construct an MDP model that could be used for optimal planning. Most recently, concurrent work to ours. pessimistic MDPs have been proposed for offline model-based RL (Kidambi et al. [020 Yu et al.) (020)). Both approaches define MDPs that penalizes for model uncertainty based on an assumed "uncertainty oracle" signal and derive performance bounds under the assumption of optimal planning. In practice, however, due to the difficulty of planning with learned deep-network models, the implementations rely on model-free RL, which introduces extra level of approximation.
Model free RL for Offline settings: Agarwal et al. (2199) show that, for offline settings, stronger off policy methods stemming from distributional RL like REM and QR-DQN perform better to classic DQN. However recent offline RL. methods directly tackle the problem of distributional shift by [Atksson (1998), and more recently Fonteneau et al. (2013). in offline settings as pointed Nachum et al. (2019). Buckman et al. (2020) among others can Works like [Sutton et al. Nachuu directly estimate the policy gradient for offline learning. Moreover, [Fujimoto et al. (2019), Wang let al. (2020), Kumar et al. (2020). Wu et al. (2019) directly constrains off policy learning towards the dataset, in turn, introducing pessimism in their estimates.
SUMMARY
This work is an effort to push the integration of deep representation learning with near-optimal planners. To this end, we proposed the Deep Averagers with Costs MDP (DAC-MDP) for offline RL as a principled way leverage optimal planners for tabular MDPs. The key idea is to define a non-parametric continuous-state MDP based on the data, whose solution can be represented as a solution to a tabular MDP derived from the data. This construction can be integrated with any deep representation learning approach and addresses model inaccuracy by adding costs for exploit- ing under-represented parts of the model. Using planner based on a GGPllmpplemnntation of value iteration, we demonstrate scalability to complex tinage-based environments such as Atari with rel- atively simple representations derived from offline model-free learners. We also illustrate potential use-cases of our planning-based approach for zero-shot adaptation to changes in the environment and optimization objectives. Overall, the DAC-MDP framework has demonstrated the potential for principled integrations of planning and representation learning. There are many interesting direc- tions to explore further, including integrating new representation-leanee -learinnnnn approaches and exploiting higher-order structure for the next level of scalability.
9

---

Published as a conference paper at ICLR 2021
REFERENCES
A. Agarwal, Sham M. Kakade, A. Krishnamurthy, and W. Sun. Flambe: Structural complexity and representation learning of low rank mdps. ArXiv, abs/2006. 10814, 2020.
Rishabh Agarwal, D. Schuurmans, and Mohammad Norouzi. An optimistic perspective on offline reinforcement learning. ICML,, 2019.
Christopher Atkeson. Nonparametrie model-based reinforcement learning. Advances in neural information processing systems, pp. 1008-1014, 1998.
Richard Bellman and Samuel G. Kneale. Dynamic programming. Princeton University Press, 1958.
Charles Blundell, B. Uria, A. Pritzel, Li, Avraham Ruderman, Joel Leibo, Jack W, Rae, Daan Wierstra, and Demis Hassabis. Model-free episodic control. ArXiv, abs/1600.044600 2016.
Craig Boutilier, Richard Dearden, and Moisés Goldszmidt. Stochastic dynamic programming with factored representations. Artificial intelligence, 121(1-2):49-107, 2000.
J. Buckman, Carles Gelada, and Marc G. Bellemare. The importance of pessimism in fixed-datase, policy optimization, ArXiv, abx/2009.06799, 2020.
Maxime Bhevalier-Boisvent. gym-miniworld environment for openai gym. Com/maxinmet www.mmwwwwemmmememmmmmmeeem wowollddd 2018.
Dane S. Corneil, W. Gerstner, and Brea. Efficient model-based deep reinforcement learning with variational state tabulation. ArXiv, Abs/1882.04325, 2018.
D. Ernst, Geurts, and Wehenkel. Tree-based batch mode reinforcement learning. J. Mach. Learn. Res., 6:503-556, 2005.
R. Fonteneau, S. Murphy, L. Wehenkel, and D. Ernst. Batch mode reinforcement learning based on the synthesis of artificial trajectories. Annals of Operations Research, 208:383-416, 2013.
Scott Fujimoto, Edoardo Conti, Mohammad Ghavamzadeh, and Joelle Pineau. Benchmarking batch deep reinforcement learning algorithms. ArXiv, abs/1910.01108, 2019.
G. Gordon. Stable function approximation in dynamic programming. In ICML, 1995.
G. Gordon and Tom Michael Mitchell. Approximate solutions markov decision processes. In Ph.D. Thesis, MIT, 1999.
Caglar Gulcehre, Ziyu Wang, A. Novikov, T. L. Paine, Sergio Gomez Colmenarejo, Konrad Zolna, Rishabh Agarwal, Josh Merel, Daniel Mankowitz, Cosmin Paduraru, Gabriel Dulac-Arnold J. Li, Mohammad Norouzi, Matt Hoffman, Ofir Nachum, G. Tucker, Nicolas Heess, and N. D. Freitas. RI unplugged: Benchmarks for offline reinforcement learning. ArXiv, abs/2006.13888, 2020.
Steven Stenberg Hansen. Deep episodic value iteration for model-based meta-reinforcemmnt learn- ing. ArXiv, abs//705.03566 2017.
Linjia Hu, S. Nooshabadi, and M. Ahmadi. Massively parallel kd-tree construction and nearest neighbor search algorithms. 2015 IEEE International Symposium on Circuits and Systems (IS- CAS), pp. 2752-2755, 2015.
Nicholas K Jong and Peter Stone. Model-based function approximation in reinforcement learning- In Proceedings of the 6th international joint conference Autonomous agents and multiagent systems, pp. 1-8, 2007.
R. Kidambi, A. Rajeswaran. Pranceth Netrapalli, and T. Joachims. Morel Model offline reinforcement learning. ArXiv, abs/2005.059. 05951,, 2020.
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. abs/1412.6980, 2015.
CoRR,
10

---

Published as a conference paper at ICLR 2021
Aviral Kumar, Aurick Zhou, G. Tucker, and Sergey Levine. Conservative q-learning for offline reinforcement learning. NeurlPS, fbs//200600479, 2020.
Thanard Kurutach, A. Tamar, Ge Yang. S. Russell, and P. Abbeel. Learning plannable representa- tions with causal infogan. In NeurlPS, 2018.
Sergey Levine, Aviral Kumar, G. Tucker, and Justin Fu. Offline reinforcement learning: Tutorial, review, and perspectives on open problems. ArXiv, abs/2005.01643, 2020.
Zichuan Lin, Tianqi Zhao, G. Yang, and L. Zhang. Episodic memory deep q-networks. ArXiv, abs/l abs//8005077 885.00603... 2018.
Marlos C. Machado, Mare G. Bellemare, Erik Talvitie, J. Veness, Matthew J. Hausknecht, and Michael H. Bowling. Revisiting the arcade learning environment: Evaluation protocols and open problems for general agents. ArXiv, abs/1 00011709.0000 709.060099 2018.
Henrik Marklund, Suraj Nair, and Chelsea Finn. Exact (then approximate) dynamic programming for deep reinforcement learning. In Bian and Invariances Workshop, ICML, 2020.
W. W. Martin. Implementation of kd-trees on the gpu to achieve real time graphics processing. In CSci Senior Seminar Conference, 2012.
Yoan Miche, Antti Sorjamaa, Patrick Bas, Olli Simula, Christian Jutten, and Amaury Lendasse. Op- elm: optimally pruned extreme learning machine. IEEE transactions on neural networks, 21(1): 158-162, 2009.
V. Mnih, K. Kavukcuoglu, D. Silver, A. Graves, Ioannis Antonoglou, Daan Wierstra, and Martin A. Riedmiller. Playing atari with deep reinforcement learning. ArXiv, abs/1312.5602, 2013.
V. Mnih, K. Kavukcuoglu, D. Silver, Andrei A. Rusu, J. Veness, Marc G. Bellemare, A. Graves, Martin A. Riedmiller, Andreas K. Fidjeland, Georg Ostrovski, S. Petersen, C. Beattie, A. Sadik, Ioannis Antonoglou, H. King, D. Kumaran, Daan Wierstra, Legg, and Demis Hassabis. Human- level control through deep reinforcement learning. Nature, 318:529-534 2015.
Ofir Nachum, Bo Dai, Ilya Kostrikov, Yinlam Chow, L. Li, and D. Schuurmans. Algaedice: Policy gradient from arbitrary experience. OPTRL, (bb//192,,0274, 2019.
Ársæll Jóhannsson. Gpu-based markov decision process solver. Msc. Thesis Reykjavik Uni- versify, 2009.
Dirk Ormoneit and P. Glymn. Kernel-based reinforcement learning in average-cost problems. IEEE Trans. Autom. Control., 47:1624-1636 2002.
Dirk Ormoneit and S. Sen. Kernel-based reinforcement learning. Machine Learning, 2002.
Jason Pazis and Ronald Parr. Pac optimal exploration continuous space markov decision pro- cesses. In Twenty-Sevnnth AAAI Conference on Artificial Intelligence, 2013.
A. Pritzel, B. Uria, Srinivasan, Adrià Puigdomènech Badia, Oriol Vinyals, Demis Hassabis, Daan Wierstra, and Charles Blundell. Neural episodic control. In ICML, 2017.
Martin L. Puterman. Markov decision processes: Discrete stochastic dynamic programming. In Wiley Series in Probability and Statistics, 1994.
Aswin Raghavan, Saket Joshi, Alan Fern, Prasad Tadepalli. and Roni Khardon, Planning in factored action spaces with symbolic dynamic programming. In AAAI. Citeseer, 2012.
S. Ruiz and B. Hernández. A parallel solver for markov decision process in crowd simulations. In 2015 Fourleenth Mexican International Conference on Artificial Intelligence (MICAI), pp. 107- 116. 2015.
R. Sutton, A. R. Mahmood, and Martha White. An emphatic approach to the problem off-policy lemporal-difference learning. MI,, abs/1503.04269, 2016.

---

Published as a conference paper at ICLR 2021
Csaba D Toth, Joseph O' O'Rourke, and Jacob E Goodman. Handbook of discrete and computational geometry. CRC press, 2017.
Elise van der Pol, Thomas Kipf, Frans A. Olichoek, and M. Welling. Plannable approximations to mdp homomorphisms: Equivariance under actions. In AAMAS, 2020.
Ziyu Wang, Novikov, Konrad Zolna, Jost Tobias Springenberg, Scott Reed, B. Shahriari, N. Siegel, Josh Merel, Caglar Gulcehre, Nicolas Heess, and N. D. Freitas. Critic regularized regression. Neurips, abs/2006. 15134, 2020.
Y. Wu, G. Tucker, and Ofir Nachum. Behavior regularized offline reinforcement learning. ArXiv, abs/1911.11361, 2019.
Zhimin Wu, E. Hahn, A. Günay, L. Zhang, and Y. Liu. Gpu-accelerated value iteration for the computation of reachability probabilities in mdps. In ECAI, 2016.
G. Yang, A. Zhang, Ari S. Morcos, Joelle Pineau, P. Abbeel, and R. Calandra. Plan2vec: Unsuper- vised representation learning by latent plans. ArXiv, abs/2005.03644 2020.
Tianhe Yu, G. Thomas, Lantao Yu, S. Ermon, Zou, Sergey Levine, Chelsea Finn, and Tengyu Ma. Mopo: Model-basee offline policy optimization. ArXiv, abs/2005.13239 2020.
Guangxiang Zhu, Zichuan Lin, G. Yang, and C. Zhang. Episodic reinforcement learning with asso- ciative memory. In ICLR, 2020.
12

---

Published as a conference paper at ICLR 2021
A APPENDIX
A.1 PRACTICAL ISSUES
We now describe some of the key practical issues of the framework and how address them.
Optimal Planning. We use value iteration (VI) (Bellman & Kneale 1958) to optimally solve the core-state MDPs, which can have a number of states equal to the size of the dataset N. While in general storing a transition matrix with N states can take O(n²) space, the core-state MDPs have sparse transitions with each state having at most & successors, which our implementation exploits. Further, VI is highly parallelizable on GPUs, since the update of each state at each VI iteration can be done independently. We developed simple GPU implementation of VI, which can provide between 20- 1000x wall clock speedup over its serial counterpart. Our current implementation can solve MDPs with a million states in less than 30 seconds and easily scale to MDPs with several million states and medium action spaces (up to 10). Thus, this implementation is adequate for the dataset sizes that can be expected in many offline RL settings, where often we are interested in performing well given limited data. For extremely large datasets, expect that future work can develop effective sub-sampll sampling approaches, similar to those used for scaling other non paraameettiic models, e.g. Miiche et al. 2009). We will release an open-source implementation and further details are in Appendix|A. A.7
The above DAC-MDP construction and theory is based uniform averaging across KNN sets. In practice, however, most non-parametric regression techniques use weighted averaging, where the influence of neighbor decreases with its distance. Our implementation also uses weighted averaging, which we found has little impact on overall performance (see Appendix), but can reduce sensitivity the choice of k. especially for smaller datasets. In our implementation we compute normalized weights over kNN sets according to the inverse of distances. In particular, the modified DAC-MDP reward and transition functions become,
Weighted Averaging:
R(s,a) a)
Σ (ERNN((,0))
a(s, a, 84, a;);;):;; C C(d((s,,ss,00 s.,
(4)
a(s, = Σ
a 8 s,, a.) I[s = =/].
(5)
(EANN(s..)
d'(5..88.0)) where a(s,a, 81, EJeeNn(saa d'(s,,,ya;;) (s, a, s1 a.) = H(s,a,s,a and dg = 15- -5
Optimized Policy Computation. After solving the DAC-MDP, the policy computation for new states requires computing Q-values for each action via Equation 3 which involves a kNN query for each action. We find that we can reduce this computation by a factor of |A] via the following heuristic that performs just one kNN query at the state level. Here NNN(ss returns the data tuple of indices whose source states are the i nearest neighbors of
F(s)
max AEA K.
Σ (E)NN(()
als,s)) ('())a)
(6)
where, d' dsss d(s,8))+6, a(s, 8:) EvEANN() (s.s..)) and da is set to 15- We have found that this approach rarely hurts performance and results in the same action choices. However, when there is limited data, there some evidence that this computation can actually help since avoids splitting the dataset across actions (see the Appendix for ablation study).
('(,,.)
Hyperparameter Selection. The choice of the cost parameter C' can significantly influence the DAC-MDP performance. At one extreme, if C' is large, then the resulting policy will focus on "staying close" to the dataset. At the other extreme when C O, there is no penalty for exploiting the under-represented parts of the model. In general, the best choice will lie between the extremes and must be heuristically and/or empirically selected. Here, We use the simple rule-of-thumb of setting C to be in the order of magnitude of the observed rewards, to avoid exploitation but not dominate the policy. In addition, if the online evaluation budget N, (see Section 2 is greater than one, also consider values that are orders of magnitude apart span qualitatively different ranges.
The DAC-MDP construction used the same smoothness parameter l for both building the MDP and computing the policy for unknown states via Equation We have found it is useful to different
13

---

Published as a conference paper at ICLR 2021
values and in particular, there can be benefit for using larger value for the later use reduce variance. Thus, our experiments will specify a value of & used to construct the MDP and a value kn used compute the policy. Our default setting is k and k 11, with more values possibly considered depending on the evaluation budget NN.
A.2 THEORETICAL PROOFS
Let स bet the optimal policy of a DAC-MDP. We wish to bound the value V (*(s) क in the true MDP in terms of the optimal value (s) for any state Using the following lemma from Pazis & Parr (2013) it is sufficient bound the Bellman Error ((s,a) B[Q](s, a) of Q across all and
with respect to the true MDP.
Lemma A.I. PPagis & Parr 2013) Theorem 3.12 For any Q-function Q with greedy policy n, for all E S and a E A. -E_ (( .)- [[Q][s, S E., then for all s E S,
+
(*(s) 2 V (s)
1-7
In general, however, the Bellman Error can be arbitrarily large without further assumptions. Thus, in this work, we make Lipschitz smoothness assumptions on B[Q]. In particular, we assume that there is constant L(k: C') such that for any state-action pairs (s, a) and (s',a') we have
[iQ)(s, Bi d') - L(k, C) d(s, s',,".
Given the smoothness assumption for any (s, data sample as riy (s, 8)) and constant I. define a constant (, a) such that
((, B(Q(ss))=B(((s,..0 a.) a).
Note that based on the smoothness assumption we have that (s, a)) s L(k, d(s, a, si az).
Using this definition introduce new operator B, which will allow us relate B to B.
([Q](s,
Σ
+ max Q(1,,a') A))
(E.NN(s..))
The following lemma shows that this operator approximates B with high probability.
Lemma A.2. For any data set D of size N. value of k. and any cost parameter C, if Q is the optimal Q-function of the corresponding DAC MDP, then with probability at least for all (8, E x A.
(())(s, (s,) (maazekk N,8) for all (8,0) ESXA
1
2M
c(,,
2k
8
where Qmaz max Q(s, a) and is the dimensionality of the state-action encoding.
Proof. In order to capture the variance of B|Q) associated with the transition dynamics, for each state-action pair (s, a) and each nearest neighbor index i E kNN(ss a), define random variable (s, = ri y max, QSS, a') Ai(s,)) a), where St T(si, a;. Note that each term of B[Q) a) is single sample of one (, a). That is,
B())(s,a) =
Σ (s.a)
nr(s,a), where 1i(s,a) ~ (1(
14

---

Published as a conference paper at ICLR 2021
Also note that according to the definition of (,(s, a) the expected value of each X,(s, a) is equal to (()](s,a).
E [)) = y1p max Q(S) dD] - a)(s,a)
(s,) -,)
B(Q[(s,a)
Accordingly E [I B--BBQB as)
From the above, we can apply the Hoeffding inequality, which states that for independent random
variables X1..... XR with bounded support I X; S b;, if X E X2 is the empirical mean, then for all <> 0,
2
Pr (IX E
c)
exp
Ei(b; - a,)²
Applying this bound to (s, a) implies that:
-2ke
Pr [[Q](s, B(Q](s, 26) < 22ex
Quao
which can be equivalently written as
Pr (BiQ(s.))-BQ(((sss 2 maz
([(I(s,
1
In
2
2k
This bound holds for individual s, a pairs. However, we need to bound the probability across all 8, a pairs. To do this note that the computed value B[Q](s, a) is based on the nearest neighbor set kNN(s, a) and let Mx,e denote upper bound on the possible number of those sets across all x A. To ensure that the bound holds simultaneously for all such sets, we can apply the union bound using 8' 8/MN, This bounds the probability over all state-action pairs simultaneously by
Pr [BiQ(ssa)- - B(([(s, 2 Qmaa
1 2k
2MN. In
6.
8
Theorem 3.1 For any data set D of size N, let Q and स be the optimal Q-function and policy for the corresponding DAC-MDP with parameters i and C. If B[Q] is Lipschitz continuous with constant L(k, C), then with probability at least 1 -
v 2 V (T,H: C) -mar + Quar (k, N,
1 2M
c(k, N,)
In
2k
which for L.2 distance over d-dimensional space yields c(k: N.6) -0:0)00( (V
(d (dIn&N+In))
Proof. The proof first will bound the Bellman error of Q from above an below and then apply Lemma A.1 We first decompose the Bellman error into two parts by adding and subtracting B[Q).
(s),a) -(Q(s))
(Q(s.a) - (Q(s.))BB(((ss.0)) + -
Ea(s.a)
Extmn (5,a)
The first term corresponds to the enror due to the non-zer distance of the nearest neighbors and the second term is due to sampling emror.
15

---

Published as a conference paper at ICLR 2021
Noting that B and B only differ in one term, Ea(s, a) can be simplified as follows.
Ea(s,a) = ((x,a)= - (s))
B(Q](s,a) -
Σ A a) - C. &ú,
h
(s..)(
From this and the fact tht [A,ss a)l & L(k, -)-dd) a;,,,, we can immediately derive upper and lower bounds on Ea(s, a) for all s and a.
() dmaz I Ea(s, s (L(k,C) C) dmaz
We can bound Estm (s, a) by direct application of Lemma A.2 Specifically, with probability least 1 - 6, for all s and a, 1eei (s, a)l I (K,,,,) Putting these together we get that with probability least 1 6, for all and a,
(0),), a) s (I(K, C) C) to (k,, N, - ((L,(k, C) + C) dmaz + clk, N,)) S Q(s a)- ((Q)),
The proof is completed by applying Lemma A. 1 to this bound.
Note: For a Euclidean distance metric, Iloth et al. 2017)[Chappe 27] has established an upper bound on MN
MN,4 = O (NId//1 = =0 (
A.3 ABLATION STUDY
We highlight the deviation of the practical implementation of DAC-MDPs from theory in section A.T namely, weighted averaging based KNN distances (W A) and, KNN over states instead of state-action pairs NN..N). The theory for DAC-MDP derived for uniform averaging. i.e., the probability distribution to the candidate next states from KNN state action pairs is uniformly distributed irrespective of their relative distances. In contrast, weighted averaging normalizes the probability distribution according their relative distances from the query state-action pair. Sec- ondly, the theory states that we query the K nearest neighbors for each state-action pair to calculate the q values for any unseen state. This entails that | numbers of KNN calls have to be made for each action decision. However, we can reduce this by simply querying k nearest neighbors for states over state-action pairs. We query for nearest states when sK N option is turned on. We conduct the ablation study on the [ulk[100k] dataset well smaller dataset comprising of only 10% of the full dataset. Below Figure we show ablation study for each of these choices in the standard CartPole domain.
We find that for a larger dataset, neither weighted averaging nor the state KNN approximation affects the performance of DAC-MDPs. However, there is noticeable drop in performance for optimal Bag dataset for smaller dataset sizes when state KNN approximation is turned off. This suggests that when the dataset is mostly comprised of subsamples of optimal trajectories, the data is not divided uniformly over the actions, resulting in less accurate estimates, especially when the data limited and skewed towards a particular policy.
A.4 ADDITIONAL CARTPOLE EXPERIMENTS
To further investigate the impact of DAC-MDP parameters, we conduct similar experiments to sec- tion for different dataset sizes on CartPole. In addition to the greedy policy performance we also track the performance of e-greedy run of the policy further distinguish the quality/robustness of the policies learned.
We see very similar trend (as in 100k) for the choice of cost parameter C' even for the low data regime of 10k. Figure M shows that for all datasets, when there is no penalty for under-represented transitions,i.e. C O, the policy is extremely poor. At the other extreme, when C' is very large, the optimal policy tries to stay as close as possible to transitions in the dataset. This results in good performance for the Optimal Bag dataset, since all actions near optimal. However, the policies
16

---

Published as a conference paper at ICLR 2021
Ablation dataset dize 100k
Ab ation for dataset size 10c
400
Raaty
300
Oheey Puley
290
200
190
100
RandomBap Bag
MowdBag
Optrm Bag
Handomdaag
Minedllgg
Ootimatiigg
DAC-MDP,
290
BAC-MDDF wONNN
BAGAMDD atteN
DAG-MOP: na Wl, ww..noo.o00 sids
DAD MDP, no sKNN
200
Orealy Pulay
190
150
50
Random
Moudbag
Optima
Handomaagg
Ootimaling
Delaset Varsion
Datavet Var
Figure 8: (a) Ablation study for WA and sKNN in CartPole Domain. Greedy and eps-greedy policy returns for different of hyperparameters and dataset versions of size 100k. (left) and 10K (right) Hyperparameters: [k: 5, ki =1,C==1 1,
3000
Avenaga Ratum Cool Paramater
Average MDP build peramater k
Greedy Polixy (e 00:1) Paaeyy (e =0.3)
Avenige return panamater
16:03
a Graddy Palloy
200
0.1
200
200
fe+03
Qeundy
100
Twios
Twn07
331
RandomEag
MivodBogg
Optima Bog
Randon
Mixddlag
OptimlBag
MixedBag OptimaBag RandomBag
Dalasel Vension [10k]
Datasel Version [10k)
Dataset Version [10k]
7200
300
10
200
Oready
100
10+03
Te+07
Bag
Optimi Bag
OptimlBeg
Mow-Beg
OptimaBag
Version
Version
Dataset
Figure 9: Eps-Greedy performance for CartPole different dataset sizes. (a) Top row: dataset size 10k (b)
Bottom Row: dataset size 50k
resulting from the MizedBag and RandomBag datasets fail. This is due to those datasets contain- ing large number of sub-optimal actions, which the policy should actually avoid for purposes of maximizing reward. Between these extremes, the performance is relatively insensitive to the choice of C.
DAC-MDP, however, is more sensitive towards the choice of k for small dataset regime. Figure 9 second column, explores the impact of varying k using fixed k 1 and C = 1. The main observa- tion is that there slight disadvantage to using & = 1, which defines a deterministic finite MDP, 1, especially for the non-optimal datasets. Moreover, there is also slight disad- vantage in using larger k when the dataset is not dense. It is to be noted that although Random Bag dataset contains the same amount of experience, is much denser than other datasets as random trajectories are quite short compared to optimal trajectories. This indicates that the optimal planner
compared
17

---

Published as a conference paper at ICLR 2021
Average
Avaraga
Average palicy
Gready Pollyy
400
1w-05
400
Greedy Pookee
4400
Twx03
10
200
200
Twrds
RondomEag
MixndDag
RandomBBag
OptimlBag
Randomiag
Mondlagg Optiaaling
Datasee Version [10K]
Da baseet Version [10R]
Dataset Version [10kk
Gready Pales
400
0.1
400
Gready Policy
10
200
200
Te+05
Tw/07
RandomEag
MixcdBag Oysina
RandomBap
MacdEag
Optiollog
RandomBag
Maso-Eag OptmalBag
(50X]
[SOK]
Figure 10: Greedy performance for CartPole different dataset sizes. Top datset size 10k (b) Bottom
Row: dataset size 50k
is able to benefit by reasoning about the stochastic transitions of the DAC-MDP for 1. However, DAC-MDP suffers from high values of k when dataset sparse.
Finally Figure 9 third column, varies the policy smoothing parameter k from to 101. Similar to the results for varying smoothness parameter there benefit to using a value of k > 1, but should not be chosen to be too large depending on how large the dataset is.
Porformance comparisan for Diftoro sats candidate policies. [Dataset Stze: D3K
ow-pared DON molized sooe
2.00
8C0,
QAC - BCG, -
8CG, N, 20
DAC 8C0, N. 20
1.50
1,00
0.50
0.25
0.00
Porg
Bruakoud
Spaculrwadara
Obari
Allanis
Bowling
Freeway
Amida
DON, N₂ =1
DMC DON N2 =1
DON, N. m
DAC DDW -6
pre-trahad DON nomalzed
DQM, 20
DOW -0
Spaceerwaseers
Bowling
Figure 11: (a) Greedy performance for Atari using different learnt representations and evaluation candidate policies [.0kk dataset]. Runs averaged over runs. Error bars show the 95% confidence interval.
A.5 ADDITIONAL ATARI EXPERIMENTS
Policy search for DQN and BCQ: our experiments we consider an evaluation protocol that makes the amount of online access to the environment explicit. In particular, the offline RL algorithm allowed to use the environment to evaluate N. policies (e.g., each evaluation can be an average over repeated trials), which, for example, may derived from different hyperparameter choices. It is not clear how many of these evaluations will be actually needed for Q-learning algorithms such as DON that is primarily designed for online learning. Even approaches focusing on offline learning
18

---

Published as a conference paper at ICLR 2021
Performense comparison for Different sets of candidate policies. [Dalsnet Size:2.5M
BCD, DAC N.
Onloe DON nommatee ccaee
BCC,
BCG,
PCG, No 20
DAC BCD, Ne-22
0.0
Pong
Breakeid
Spacelrwadera
Gber
Alanis
Bowing
Freeway
Amide
2.5
DON, N2 =1
DAC
DON, NG =1
Online DIN nommelzzni sooee
DON, No
=
DO
DQW,
1.9
0.5
0.0
-0.5
Spacalmwaders
Bowling
Freeway
Figure 12: (a) Greedy performance for Atari using different learnt representations and evaluation candidate
policies N. [2.5M dataset]
not spared from hyperparameter search and stopping criteria. Hence it is not clear how to evaluate Q-iterating policies such DQN BCQ for different values of Ne where we already using the best parameters reported from previous works.
still assume that know the value of Ne before hand and tune the learning process accordingly. More specifically given a fixed number of training iterations the evaluation frequency be set such that complete Ng evaluations by the end of the training. We then use the last Ne evaluation checkpoints to obtain the set of candidate policies. We can then choose the best among them. It is worth noting that, even if we disregard the hyperparameter tuning, is still not entirely fair to compare BCQ.Ne 6 directly with DAC-BCQ. N.=6 as the DAC-MDP only has access the very last representation. Moreover, DAC-MDPs do not need stopping criteria and are more robust to small representational changes. We show the policy search results for both DQN and BCQ for 100k dataset as well as 2.5M dataset Figure and Figure 12 respectively.
However,
2.0
1/5
1.0
GAC N07
BCQ
DAC
- BCQ, R4 =1
DAC 8CO Ha-E LAC-
PDQ
Nu- 20
Porg
Broskout Spcoo inddurs
Qzort
Atrits
Bow ing
Freeway
Amiiarr
(a)
Figure 13: Results on Medium datasct size of 1M for (a) BCQ representation and BCQ agent is trained for Im timesteps, and evaluated
episodes every 50k steps. At each of 6 uniformly distributed evaluation checkpoints, we use internal representation to compile DAC-MDPs. We then evaluate DAC-MDPs for N. 6. (b) Final BCQ policy along with the corresponding performance of DAC-BCQ for different values of N.. Runs averaged over 3 runs, error bars so the 95% confidence interval.
Additionally also run the experiment dataset size 1M at different evaluation checkpoints as done in the main paper. We trained offline BCQ agent on the dataset for IM iterations. This allows compare to these baselines well the BCQ latent state representations for
19

---

Published as a conference paper at ICLR 2021
DAC-MDP construction. The performance of the corresponding BCQ policies is evaluated using 10 test episodes every 50K iterations. At some select position of BCQ evaluation iteration, we constructed DAC-MDPss using the latent state representation at that point. In particular, this first experiment considers the offline RL setting where N₂ = 6, meaning that we can evaluate poli- cies(using 10 episodes each) corresponding to 6 different DAC-MDP parameter settings comprised of the combinations of k = 5,C E 1, 100, 1M, andk, E 11, 51. For each representation the best performing DAC-MDP setting at each point is then recorded. The entire IM iteration protocol was repeated 3 times and Figure [ sholshow the averaged curves with 90%confidence intervals. Figure 13b investigates the performance of final iteration for different values of Ne. All hyperparameters and normalization were selected as in the 100K experiment. We see that in the DAC-MDPs can perform as good as BCQ or better most of the evaluation checkpoints even for the larger dataset size and training iterations.
A.6 ADDITIONAL 3D NAVIGATION EXPERIMENTS
We also compare DAC-MDPs performance against DQN and BCQ baselines for first person 3D navigation Domain. all scenarios the agent has three actions: Move Forward, Turn Right, and Tum Left and maximum episode time steps of 100. The raw observations 84x84 RGB images. We use the same settings for DAC-MDP as described in the main paper. We use the same basclines DON and BCQ from Atari experiments with different set of hyperparameters detailed in Appendix B.2
Smple Room
Simple Room
Simple Room
3.0
MW
1.0
3.4
Rowsrnds
6.5
Arg Rowonds
Avg Rewsndd
DON [1
-0.5
-35
DAC AND [LF]
DON (RLF)
BCO (RLi)
BCQ
-1.0
DAC
-1.0
RAC [RUF]
-1.0
0.2
2.4
68
1.5
0.2
0.4
0.6
0.0
1.0
0.2
3.4
5.6
0.
3.0
Train Stess
Training
Training Stops
(a)
(b)
(c)
langth 20)
length
1.0
DON
DAC BND (égi
2.0
b-g Regarrs
0.0
Avg Rowands
M
Avg Rewands
0.5
5.4
0.0
DON
0.0
0.2
DON BC0
-25
BCQ
DAC RND
Thein Steps Ie5
Thaining Steps 1e5
Treining Steps 1n5
(d)
(e)
(f)
Figure 14: Comparison of DAC-MDPs using randomly initialized representation networks (DAC-RND) with
baselines DQN and BCQ for 3D navigation Domains. (a) Simple Room Domain, (h) Simple Room Domain: DQN vs DAC-RND on right actuator failure[[.F] (c) BCQ vs DAC-RND on right actuator failure[[FF(dd) Box and Pillar Room: short horizon, maximum episode length of 20. (e) Box and Pillar Room: Long horizon. max- imum episode lengths of 100, (f) Tunnel Room. Rewards across the rooms are clipped at (-1,2) for normalized results.
Case 1: Adapting to Modified Action Space. Here an agent is spawned in a random initial position with a goale box) in fixed position. We call this Simple Room (V* -9.36 f The agent gets - reward for bumping into the walls and terminal reward of +1 for reaching the goal. We run DQN and BCQ on the same dataset in the simple room. figure this shows that DAC-MDP performs better. For the simulated event of damaged actuator, we simply discard the damaged action from the policy action space. While this allows for zero-shot transfer learning in this scenario, the methods
2 p is the expected performance of the hehavioral policy for the datasct.
20

---

Published as a conference paper at ICLR 2021
suffer with higher variance for DQN and fails to perform well in case of BCQ pointed in figure this and this. The DAC-MDP however can adapt to these changes very robustly.
room by adding pillar in the simple room described above. Additionally, the agent gets a small non non-terminal reward of 0.02 for bumping into the pillar. We call this BoxAndPillar Room (V*a the expected lifetime the agent it may be better to go for the single +1 reward or to repeatedly get the 0.02 reward. This expected lifetime can be simulated via the discount factor, which will result in different agent behavior. As the baselines do not allow for zero shot transfer in this setting, we retrain the DQN and BCQ agents for different discount factors: 0.95 for short horizon and 0.99 for long horizon task. We then evaluate these policies on BoxAndPillar room with different maximum episode steps. 20 and 100 for short and long horizon settings respectively.
Case 2: Varying Horizons. We create
-9.84). Depending
the placement of the agent and
Here as pointed in figure this and this we see that the baselines cannot account for the long horizon planning effectively and mostly choose to plan for the shorter horizon even with larger discount factor. hence it is clear that the discount factor do not translate to effective planning horizon in these baselines. However, the DAC-MDP approach using small discount factor (0.95) our short-term agent achieves an average score of 0.91 learns to immediately get to the box along with the long- term agent repeatedly collecting rewards from the pillar. Moreover DAC-MDP simply allows for changing the discount factor used by VI and solving for the new policy in seconds for this secondary objective.
Case 3: Robust/Safe Policies. The Tunnel room (V 25) adds narrow passage the box with cones on the side. This room simulates the classic dilemma of whether to choose a risky or safe path. The agent can risk getting -10 reward by bumping into the cones or can optionally follow longer path around an obstacle to reach the goal. Even with a relatively large dataset, small errors in the model can lead an agent along the risky path to occasionally hit a cone. We train DQN and BCQ agent using the same dataset and see that they do not perform as well as DAC-DON in the experiments. Moreover, it is not straight forward on how to add stochasticity in the baselines to achieve more robust policy. In contrast, we can easily find an optimal solution to modified DAC-MDP where at each step there is 10% chance of taking random action. This safe policy avoids the riskier paths where a random "slip" might lead to disaster and always chooses the safer path around the obstacle, and also achieves an average score of 0.72.
OOOOO
(A)
(b)
(c)
(d)
Figure 15: Visualization of DAC-MDP policies for 3D Navigation Domain (a) Simple Room Solid arrow: pol-
icy rollout of standard DAC-MDP, Dotted arrow: policy rollout modified DAC-MDP :iight Turn Penalized (b) Simple Room Solid arrow: policy rollout of standard DAC-MDD Dotted arrow: policy rollout of modified DAC-MDP; Left Turn Penalized. (c) Box and Pillar Room Dotted Arrow: policy rollout of DAC-MDP solved with small discount factor [short-term planning]. Solid Arrow: Policy rollout of DAC-MDP solved with Large Discount Factor [long-term planning] (d) Tunnel Room Dotted Arrow: Policy rollout of standard DAC-MDP. No stochasticity Introduced. [optimal policy]. Solid Arrow: Policy rollout of modified DAC-MDP with added stochasticity in dynamics. [safe policy]
Hence we see that typical Deep RL methods like DQN and BCQ do not excel for secondary objec- tives. There are settings such as failed actuator where they can perform zero-shot transfer learning but fail to give any guarantees, moreover they can fail sometimes as shown empirically. In cases where zero-shot transfer is not possible such as different horizons, they can be retrained for these secondary objectives, but this comes at huge cost (if and when they succeed) as compared to just solving for new objective in DAC-MDP as shown in the computational analysis in the main paper.
21

---

Published as a conference paper at ICLR 2021
Furthermore, these baseline methods not able tackle objectives such robustness in any triv- ial manner. In contrast DAC-MDP approaches have a fine-tuned control over the learned MDP and its planning parameters.
A.7 SCALING VALUE ITERATION WITH GPUs
Value iteration (VT) (Bellman & Kneale, 1958 successively approximates the value function, start- ing from an arbitrary initial estimate by turning the Bellman optimality equation into an update rule. While VI is simple and able to calculate the exact solution for any MDP, one of the major disad- vantages that they are computationally inefficient. large number of bellman backups has to be computed for each state before convergence and the memory required grows exponentially with the number of states in the MDPs. Hence, is only natural to optimize value iteration using parallel computing platforms such GPUs. för Jóhannsson| (2009) was one of the first introduce GPU based MDP solver. In particular, they introduce two algorithms: Block Divided Iteration and Result Divided Iteration. However, there have been works leveraging GPU optimized value iteration for specific domains. (eg. Ruiz & Hernandez/ (2015). Wu et al. (2016), there does not exist a standard public library for GPU optimized value iteration. To facilitate this, we implement version that is hybrid between the Block Divided Iteration and Result Divided Iteration approaches using simple CUDA kernel described in pseudo-code
Pseudocode 1 GPU Value Iteration Kernel
1: procedure BELLMANBACKKPP(TTT +T,, +R, +V, *V' *V'',,,,,''' +Q',+0)
2: i (((
3: U, Umax + 0,0
4: for j E range(A) do
5:
for k E (ange(ks) do
b ks is initialized externally as per the MDP build parameter kib
6:
Pas Jrli. J.
7:
I. T7 jkk] V + + Pas' [Wr
8:
9:
end for ii + v
10:
11:
Umaz f- mar U. Umax)
12:
end for
13:
Umar
14:
abs(V - (ii)
end procedure
Pseudocode 2 GPU Value Iteration Function
1: procedure VALUBITERATIOO(TTADDiia rew..iddeeewdddd. rewardDict, 8min)
2:
Tp. Tj,
(tranDict, rewardDict)
3:
Tp Tı. R = salloatee_guummemotn
TI. R)
4:
V. 2.Q'8 allocule. gpu. momommy.rr.... I for voluve veclors()
5:
while mán(ō) > 8min do
6:
V' allocate, gpp hatptatte.pp.mmmmrarr.. memory (V. Visize())
7:
RunGPU K eTn T7, R. V, V Q)
8:
V= V')
9:
8|1 abs( (V())
10:
release memory
end while
12:
end procedure
For compact representation the Transition matrix, we use list of lists as our sparse represen- tations. Here the Transition Matrix is divided into two matrices, that holds the index of next states with a non-zero transition probability (T,) and the other, which holds the actual transition
Note that the different versions of GPU implementation does not affect the convergence properties of Value Iteration as each approach is still carrying exact value iteration.
22

---

Published as a conference paper at ICLR 2021
probability(Tp). Each thread takes single row from these two matrices and the Reward matrix to compute each state-action pair's Q values and the new value state. The value vector is shared among the threads and synchronized after each bellman backup operation.
To benchmark the GPU implementation's performance, we compare its run-time with a standard serial implementation of Value iteration across MDPs of varying sizes. These MDPs are DAC-MDPs generated by different samples from a large pool of datasets with continuous state vectors. The serial implementation run Intel Xeon processor and does not use any CPU multi-processing. We plot the relative performance gain across different GPUs with varying CUDA cores. We consider GPUs, namely, GTX 1080ti, RTX 8000, and Tesla V100, each with a CUDA core count of 3584, 4608 and 6912, respectively. The GPU optimized implementation provides anywhere between 20- 1000X boost in solving speed over its serial counterpart, as shown in Figure [6] Currently, our implementation of VI can solve MDPs with million states less than 30 seconds.
Speedup (Intal CPU baseline)
1000
Cauadro RTX 0000
Tweks V100
Spane
100
10x
100k
1M
MDP Size
Figure 16: Compares the performance results for serial VI solvers with its GPU optimized implementation. The serial VI solver is henchmarked using Intel Xeon CPU. We plot the performance gain over different. MDP sizes.
23

---

Published as a conference paper at ICLR 2021
B EXPERIMENTAL DETAILS
B. ATARI PREPROCESSING
The Atari 2600 environment is processed in tch same manner previous work (Mnih et al. 2015 Machado et al. 2018) and we use consistent preprocesssing across all tasks and algorithms.
Table 1: Atari pre-processing details
Name
Value
Sticky actions
Yes
Sticky action probability
0.25
Grey-scaling
True
Observation down-sampling
(84,84)
Frames stacked
Frameskip (Action repetitions)
Reward clipping
[-1,1]
Terminal condition
Game Over
Max frames per episode
108K
B.2 ARCHITECTURE AND SEPPER-PRAMETERS
Same architecture and hyperparameters were used as Fujimoto al. (2019) with slight modifica- tions in the architecture.
Table 2: Architecture used by each Network
Layer
Number of outputs
Other details
Input frame size
(4x84x84)
Downscale convolution
12800
kernel 8x8, depth 32, stride 4x4
Downscale convolution
5184
kernel 4x4, depth 32, stride 2x2
Downscale convolution 3
3136
kernel 3x3, depth 32, stride 1x1
Hidden Linear Layer
512
Hidden Linear Layer? 2
16
Output Layer
[
Table 3: All Hyperparameters for DQN and BCQ [Atari]
Hyper-parameter
Value
Network optimizer
Adam Kingma & Ba (015)
Learning rate
0.0000625
Adam
0.00015
Discount
0.99
Mini-bate size
32
Target network update frequency
8k training updates
Evaluation
0.001
Threshold 5 (BCQ)
0.3
Table 4: All Hyperparameters for DQN and BCQ [3D Nav]
Hyper-parameter
Value
Network optimizer
Adam Kingma 2015
Learning rate
0.0003
Discount y
0.99/0.95
Mini-batch size
64
Target network update frequency
100 training updates
Evaluation
0.001
Threshold - (BCQ)
0.3
Table 5: All Hyperparameters for DQN*
24

---

Published as a conference paper at ICLR 2021
Hyper-parameter
Value
Replay buffer size Training frequency
million
Every 4th time step
Warmup time steps
20k time steps
Initial e
1.0
Final e
0.01
decay period
250k training iterations
25


Reviews:
[{"review_id": "RZCbSW2klt2", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes DeepAveragers: an adaptation of the \"averagers\" framework to the Deep RL setting.\nApproximate dynamic programming is performed over a batch of observed (s,a,r,s') except with a distance penalty applied to states that are not close to those observed in the training data.\nThe authors show that this formalism can lead to better performance than learning without penalty, and also that better representations of \"state similarity\" lead this method to perform better in aggregate.\n\nThere are several things to like about this paper:\n- The problem of \"batch RL\" is timely as people look to apply RL techniques in real world problems, where learning from tabula rasa may be prohibitive.\n- The proposed method appears sound, general and well thought through.\n- The experimental results provide a clear progression from theory -> didactic examples -> deep RL, and the approach performs well across the board.\n- The paper is overall well-written and easy to follow.\n\nHowever, there are a few places where it might be improved:\n- The discussion and results of \"3D navigation\" are not well-presented... large paragraphs of texts with relatively arbitrary numbers (0.98 vs 0.96) do not make a convincing presentation. Can these be displayed better visually?\n- I'm not convinced enough connection is given between the \"averager\" framework and the many other approaches to batch RL, which all essentially seem to work via a similar manner: give penalties to the state-actions that are poorly understood.\n- I think that some of the GPU-specific discussion is a bit distracting/incidental to the core work of the apper.\n\n\nOverall, I like the paper and think it seems like a strong contribution.\nI'm slightly worried that the comparison to other related work is insufficient, as I am not well-versed in the area.\nHowever, from what I can see it looks like it is suitable for the conference.", "extra_scores": {}, "extra_text": {}}, {"review_id": "QJBfC8g9-E", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The authors propose to learn a non-parametric MDP model from batch data, which can be solved efficiently using discrete value iteration (by solving for the “core” states which are all the end-states in observed transitions) and which provides a Q-value defined over the full continuous space through a kNN lookup. There is an interesting penalty term when the estimate relies on far-away support data. The value of the optimal policy in the approximated MDP can be bounded, under some smoothness assumptions, in the original MDP.\n\nMy main concern about this first contribution is about novelty. The authors have not cited other classic papers on this topic which have similar results, for example: Kernel-Based Reinforcement Learning by Ormoneit and Sen, 2002 (see in particular Section 4 which also mentions how dynamic programming can be run on the “core” states). The authors should discuss the relation to this work and surrounding literature. Follow-up papers like (Tree-Based Batch Mode Reinforcement Learning, Ernst et al. 2005) have been applied to large domains and fitted Q-iteration (FQI) has been studied in many papers afterwards both empirically and theoretically. It would be great if the authors could comment on that. \n\nThe second paper contribution is to explore the practicality of this approach using various ways to represent the state, including parametric functions as used in DeepRL. The studied domains are Cartpole, Atari (8 games) and 3D navigation tasks. The empirical results in Cartpole demonstrate the importance of the penalty term to obtain good performance. It would be nice to know the score of the pre-trained Cartpole policy for comparison in Fig 2 (same question for 3D nav domains). In Atari, it appears that the latent representation can be leveraged by the proposed approach to robustly improve the DQN score. In general these experiments are usefully presented, but some questions remains over how other approaches would do in similar settings. For example:\n* Instead of using the learned representation outside of the original DeepRL setting, can that extra computation be used instead within the same DQN framework by replaying the same data and updating the network further? (cf paper When to use parametric models in reinforcement learning? by van Hasselt et al. 2019)\n* Can LSPI be run using these representations? What are the accuracy/speed trade-offs there?\n* What about other FQI-style methods like Extra-trees cited above? Or in general how do other batch RL methods compare?\n\n3D Nav: “ For most offline RL approaches this would require retraining the agent on a modified dataset from scratch.” For this scenario, perhaps only the last layer could be retrained while keeping the same latent representation, which is similar to what is going on here? The DAC-MDP agent is retrained “from scratch” with this different cost function, though perhaps this is much faster in this case.\n\nThe 3D nav experiments are interesting, but it’s hard to know what to take away from them. If flexibility of task modifications using the same data batch + learned representation is the main point, it seems important to quantify this further (other approaches can do this zero-shot transfer, but perhaps not as well or quickly?). Also this method would presumably fail as the pre-learned representation becomes less relevant for the modified task.\n\nOverall, the paper is written clearly and it revisits older RL work to demonstrate their practicality combined with modern tools. The experiments do a good job with ablations of the proposed method but without clear baselines to compare to. As mentioned above,  previous work in this area needs to be more thoroughly referenced and discussed, the small “Averagers Framework” Related Section is missing some connections to past work.\n\n\nMinor points:\n\n* I am not sure k_\\pi is defined. Is it the k parameter in Eq 3?\n* “eucledian” distance\n* Fig 2 legend “parameter”\n* Clarify iterations in the Atari setting (frames? steps?)\n* “their optimal polcies are visualzed”\n\n\n---- Post-rebuttal ----\n\nThank you for addressing my concerns and providing the additional experiments and baseline which I think make the paper stronger. I have updated my score as a result.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "E0bdgnHplw", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The authors propose a method to construct non-parametric models for offline control based on the averager framework. The authors tested three typical latent representations including random projection, DQN representation, and BCQ representation. KNN is then used to construct the non-parametric model on the latent space. The reward function is augmented with a penalty term penalizing unseen transitions in the dataset. A novel GPU MDP solver based on value iteration is used to solve the non-parametric model. Theoretically, a performance lower bound is derived for the approximate MDP. Empirically, a thorough comparison with baselines is performed in the challenging Atari domains. I particularly like the case study in the 3D navigation domains, which highlights the flexibility of DAC-MDP.\n\nOverall I think the paper makes a good contribution in offline RL. The ideas are intuitive and the empirical results are convincing. \n\nMinor comment:\n(1) I can understand building the kNN table is a one time cost in offline setting as the dataset does not change. In the online learning setting, building such a kNN table is usually considered computationally intractable, so I think the paper may benefit from providing some statistics of the run time for compiling such a kNN table for 2.5M Atari frames, as well as the memory cost.\n(2) The paper implements a hybrid version of Block Divided Iteration and Result Divided Iteration. I think the paper may benefit from some discussion about the convergence of this hybrid GPU value iteration algorithm.\n(3) According to how I understand the paper, a Eucledian distance is used on the latent space. When random projection is used, I can see it can easily project (s, a) together. But when DQN or BCQ representation is used, I don't fully understand how they encode (s, a). In my understanding, the default DQN and BCQ encode only states, so how are actions encoded?\n(4) Contrastive learning has recently achieved great success in representation learning, as well as reinforcement learning as auxiliary tasks. I'm wondering if it can help improve the performance of DAC-MDP.", "extra_scores": {}, "extra_text": {}}, {"review_id": "9afjz3zhSK", "reviewer": "AnonReviewer5", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The authors present a nearest neighbour method for learning a model offline from the statistics of the given data set. Representations are provided from other off-policy deep RL methods. Value iteration is used on top of the model to learn the final policy. The algorithm is tested in several Atari games over two data set sizes. \n\nStrengths:\n- Overall, the proposed method is straightforward, intuitive, and outperforms baselines on a challenging task. The results are somewhat surprising given the simplicity of the approach. \n- With a few exceptions (discussed below), the presentation quality is high. Figures are clear/readable. Writing is clear.\n- With a few easily fixed exceptions (discussed below), reproducibility is high. The appendix is detailed & includes additional experiments. Code is provided. Most algorithmic and experimental details are provided.\n\nWeaknesses:\n- Experimental results suggest the method requires a representation derived from other off-policy deep RL algorithms, meaning running the proposed method also requires running another deep RL method to simply learn the representation. At the same time, the performance gains seem incremental for a lot of additional complexity.\n- I do feel like there is a contribution here, but novelty is not that high compared to other methods which build on tabular RL.\n- Although I can (personally) infer the purpose of $d(s,a,s_i,a_i)$ in the reward function from related work in the field, the use of $d$ is not well motivated by the authors. At the same time, both the choice of $C$ and $d$ would seem to be important hyper-parameters relative to the scale of the reward function. A choice which is difficult to make without interacting with the environment. Furthermore, I was unable to find the description of the distance $d$ anywhere in the main body or appendix.\n- The related work is missing discussion on recent offline RL methods such as [1,2,3,4].\n- Baselines are limited to only two methods. Possible additions [1,3]. Additionally, although its nice that additional experiments were includes the gym mini-world experiments don't add much to the paper without baselines.\n- Reproducibility Issues:\n    - The use of $N_e$ is unusual. Its role is not well described in Section 2 without reading the appendix.\n    - I was unable to find the number of seeds used in each experiment. Although error bars are provided in some figures, I was unable to find what quantity these error bars were describing.\n    - As previously mentioned, I could not find which distance function $d$ was used in the experiments.\n\nMinor Clarity Issues:\n- Eqn (1) and (3) describe the bellman equation over Q functions, however the method relies on state value functions $V$ which are learned with a transition function (such as described in Pseudocode 1 in Appendix A.6). Fixing this along with a clearer description of the 1-step kNN look ahead step would improve clarity. \n- Typo: Figure 2: \"Datset\" version.\n- Typo: A.2. \"Theoritial Proofs\".\n\nRecommendation:\n\nOverall, I think the results of the method are interesting, even if incremental. In its current state I would favor rejection, but I believe this would be a solid paper with enough corrections to the weaknesses I've listed. Either during the rebuttal phase of this conference or as a submission to a future conference. \n\nReferences:\n- [1] Agarwal, Rishabh, et al. \"An Optimistic Perspective on Offline Reinforcement Learning.\" 2020.\n- [2] Fujimoto, Scott, et al. \"Off-policy deep reinforcement learning without exploration.\" 2019.\n- [3] Wang, Ziyu, et al. \"Critic regularized regression.\" 2020.\n- [4] Levine, Sergey, et al. \"Offline reinforcement learning: Tutorial, review, and perspectives on open problems.\" 2020.\n\n**Post-Rebuttal**\n\nThe authors have done well with their additional page, and many of the concerns I had have been dealt with the latest iteration of the paper. I have increased my score. \n\nRe: Motivation for c and d. The current *objective* for c and d is described in the paper, but the motivation is not. I hope the authors add to this discussion in the next iteration. ", "extra_scores": {}, "extra_text": {}}, {"review_id": "9TsM1Iz1Ux-", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary\n=========\nAuthors introduced the Deep Averagers with Costs MDP (DAC-MDP) as an offline approach for solving MDPs\nThey addressed the following planning challenges: difference in representation used by model and planner, and 2) planners exploit inaccuracies of models\nTo address (1) authors relied on a simple tabular representation. To address (2), the adopted pessimism in the face of uncertainty by encouraging the agent to focus on known areas. \n\nPros / Cons\n[+] Theoretical analysis of DAC-MDP\n\n[+] Empirical results on toy domain (Cart pole), Atari and 3D first-person navigation task\n\n[+] The idea is very simple \n\n[-] Some of the decisions made by the authors felt arbitrary (See details/questions)\n\n[-] Authors used 3 seeds for empirical results which seems too small. Moreover, some plots lack statistical significance.\n\n[-] As with any planning approach, these algorithms are expected to perform better than their counter part without planning. \nHowever, there is no free lunch and the boost will come at the expense of computation. Currently the paper does not discuss that critical angle. \n\n[-] The main idea does not seem very novel (see below)\n\nQuestions:\n==========\nEqn. 2: Why not scale the rewards based on their distance to (s,a) instead of having the distance as a penalty?\n\nPage 6: \n\t- Atari domain has deterministic transition. How well this approach works for stochastic transitions?\n\t- The entire 100K iteration protocol was repeated 3 times => Is 3 times enough to provide statistical significance?\n\t- Figures 4 investigates the performance at the final iteration for different values of Ne. For Ne = 1 we use k=5,kπ =11,C=1 and \nfor Ne =20 we expand on the parameter set used for Ne=6. => How did you select these parameters?\n\nFigure 5: Where are the standard errors? Are all differences significant? Again you should also discuss wall clock time.\n\nPage 8: The idea of moving non-core states to core states for planning using a metric is not new (e.g. [1])\n\nGeneric: I am not sure how easily this approach can scale to large stochastic domains with continuous state space. Was the 3D first-person navigation task included stochasticity in the transition function?\n\nDetails\n=========\nP3: \"non-core state immediately transitions to the core for any action\" => How do you calculate the corresponding core state? Is it the closest using KNN?\nFigure 2: Where are the error bars?\nFigure 3: What about computation time?\n\n[1] J. Joseph, A. Geramifard, W. Roberts, J. How and N. Roy,  “Reinforcement Learning with Misspecified Model Classes”, IEEE International Conference on Robotics and Automation (ICRA), 2013\n\n\nPOST-REBUTTAL\n==============\n\"First, we would argue that there are not many examples of planning approaches outperforming non-planning approaches when using imperfect learned models. Providing such a demonstration in challenging image-based benchmarks is one of the contributions of this work.\"\n- I disagree with authors. The idea of planning using imperfect models have been explored as early as 1998 (e.g. Dyna algorithm in Reinforcement Learning: An Introduction by Sutton and Barto).\n\n\"computational analysis\"\n- Thank you for adding this section. It addressed my concern.\n\n\"non-determinism\"\n- Thank you for adding more clarity. It addressed my concern.\n\n\"Statistical significance\"\n- Great to see the extra runs. Please include the bars for Figures 5,7 in the final submission.\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes an algorithm for offline RL, that consists in solving a finite MDP derived from a fixed batch of transitions.
The initial reviews were overall positive, and the concerns raised at this stage were nicely addressed by the rebuttal and the revision from the authors.
The final discussion led to the consensus that this paper should be accepted at ICLR.
Decision: Accept (Spotlight)