Hamiltonian Q-Learning: Leveraging Importance-sampling for Data Efficient RL
Authors: Udari Madhushani
Biswadip Dey
Naomi Leonard
Amit Chakraborty
Venue:  (2021)
Keywords: Data efficient RL
$Q$-Learning
Hamiltonian Monte Carlo

Abstract: Model-free reinforcement learning (RL), in particular $Q$-learning is widely used to learn optimal policies for a variety of planning and control problems. However, when the underlying state-transition dynamics are stochastic and high-dimensional, $Q$-learning requires a large amount of data and incurs a prohibitively high computational cost. In this paper, we introduce Hamiltonian $Q$-Learning, a data efficient modification of the $Q$-learning approach, which adopts an importance-sampling based technique for computing the $Q$ function. To exploit stochastic structure of the state-transition dynamics, we employ Hamiltonian Monte Carlo to update $Q$ function estimates by approximating the expected future rewards using $Q$ values associated with a subset of next states. Further, to exploit the latent low-rank structure of the dynamic system, Hamiltonian $Q$-Learning uses a matrix completion algorithm to reconstruct the updated $Q$ function from $Q$ value updates over a much smaller subset of state-action pairs. By providing an efficient way to apply $Q$-learning in stochastic, high-dimensional problems, the proposed approach broadens the scope of RL algorithms for real-world applications, including classical control tasks and environmental monitoring.

Under review as a conference paper at ICLR 2021
HAMILTONIAN Q-LEARNING: LEVERAGING IMPORTANCE-SAMPLING FOR DATA EFFICIENT RL
Anonymous authors Paper under double-blind review
ABSTRACT
Model-free reinforcement learning (RL), in particular Q-learning is widely used to learn optimal policies for a variety of planning and control problems. However, when the underlying state-transition dynamics are stochastic and high-dimensional, Q-learning requires a large amount of data and incurs a prohibitively high compu- tational cost. In this paper, we introduce Hamiltonian Q-Learning, data efficient modification of the Q-learning approach, which adopts an importance-sampee sampling based technique for computing the Q function. To exploit stochastic structure the
dynamics, we employ Hamiltonian Monte Carlo to update Q function estimates by approximating the expected future rewards using Q values associated with a subset of next states. Further, to exploit the latent low-rank struc- ture the dynamic system, Hamiltonian Q-Learning uses a matrix completion algorithm reconstruct the updated Q function from Q value updates over much smaller subset of state-action pairs. By providing an efficient way to apply Q- learning in stochastic, high-dimensional problems, the proposed approach broadens the scope of RI. algorithms for real-world applications, including classical control tasks and environmental monitoring.
INTRODUCTION
In recent years, reinforcement learning (Sutton & Barto 2018 have achieved remarkable success with sequential decision making tasks especially in complex, uncertain environments. RL algorithms have been widely applied to variety of real world problems, such as resource allocation (Mao et al. 2016), chemical process optimization (Zhou et al., 2017), automatic control (Duan et al.) 2016), and robotics (Kober et al. 2013). Existing RI. techniques often offer satisfactory performance only when it is allowed to explore the environment long enough and generating a large amount data in the process (Mnih et al.] 2015 Kamthe & Deisenroth 2018 Yang et al. 2020a). This can be prohibitively expensive and thereby limits the use of RL. for complex decision support problems.
Q-Learning (Watkins 1989 Watkins & Dayan 1992) is model-fres RL framework that captures the salient features of sequential decision making, where an agent, after observing current state of the environment, chooses action and receives reward. The action chosen by the agent is based on a policy defined by the state-action value function, also called the Q function. Performance of such policies strongly depends on the accessibility of sufficiently large data set covering the space spanned by the state-action pairs. In particular, for high-ddmeensioal problems, existing model-free RL methods using random sampling techniques leads to poor performance and high computational cost. To overcome this challenge, in this paper we propose an intelligent sampling technique that exploits the inherent structures of the underlying space related the dynamics of the system.
It has been observed that formulating planning and control tasks in a variety of dynamical systems such as video games (Atari games), classical control problems (simple pendulum, cart pole and double integrator) and adaptive sampling (ocean sampling, environmental monitoring) as Q-Learning problems leads to low-rank structures in the Q matrix (Ong) 2015 Yang et al., 2020b Shah et al. 2020). Since these systems naturally consist of large number of states, efficient exploitation of low rank structure of the Q matrix can potentially lead to significant reduction in computational complexity and improved performance. However, when the state space is tigh-dimensional and further, the state transition is probabilistic, high computational complexity associated with calculating the expected Q values of next states renders existing Q-Learning methods impractical.

---

Under review as a conference paper at ICLR 2021
A potential solution for this problem lies in approximating the expectation of Q values of next states with the sample mean of Q values over a subset of next states. A natural way to select a subset of next states is by drawing IID samples from the transition probability distribution. However, this straight forward approach becomes challenging when the state transition probability distribution is high- dimensional and is known only up constant. We address this problem by using Hamilton Monte Carlo (HMC) to sample next states; HMC draws samples by integrating a Hamiltonian dynamics governed by the transition probability (Neal et al. 20TT). We improve the data efficiency further by using matrix completion methods to exploit the low rank structure of Q matrix.
RELATED WORK
Data efficient Reinforcement Learning: The last decade has witnessed growing interest in improving data efficiency in RL methods by exploiting emergent global structures from underlying system dynamics. Deisenroth & Rasmussen T) Pan & Theodorou (2014); Kamthe & Deisenroth (2018); [Buckman et al. (2018) have proposed model-based RL. methods that improve data efficiency by explicitly incorporating prior knowledge about state transition dynamics of the underlying sys- tem. [earden et al. (1998); Koppel ct al. (0018);)oon) et al. (2017) propose Baysean methods to approximate the Q2 function. Ong (2015) and Yang et al. (2020b) consider a model-free RL approach that exploit structures of state-action value function. The work by Ong (2015) decomposes the Q matrix into a low-rank and sparse matrix model and uses matrix completion methods (Candes & Plan 2010: Wen et al.] 2012 Chen & Chil (018) to improve data efficiency. A more recent work by Yang ct al. 2020bb has shown that incorporation of low rank matrix completion methods for recovering Q matrix from small subset of Q values can improve learning of optimal policies. At each time step the agent chooses a subset of statc-action pairs and update their Q value according to the Bellman optimally equation that considers discounted average between reward and expectation of the Q values of next states. [Shah et al. (2020) extends this work by proposing a novel matrix estimation method and providing theoretical guarantees for the convergence a e-optimal Q function. On the other hand, entropy regularization (Ahmed et al., 2019 Yang et al. 2019 Smirnova & Dohmatob 2020). by penalizing excessive randomness in the conditional distribution of actions for a given state, provides an alternative means to implicitly exploit the underlying oww-iimensional structure of the value function. Lee et al. (2019) proposes an approach that samples a whole episode and then updates values in recursive, backward manner.
CONTRIBUTION
The main contribution of this work is three-fold. First, we introduce modified Q-learning framework, called Hamiltonian Q-learning, which uses HMC sampling for efficient computation of Q values. This innovation, by proposing to sample Q values from the region with the dominant contribution to the expectation of discounted reward, provides a data-efficieet approach for using Q-learning in real-worid problems with high-dimensionll state space and probabilistic state transition. Furthermore, integration of this sampling approach with matrix-completion enables us to update Q values for only a small subset of state-action pairs and thereafter reconstruct the complete Q matrix. Second, we provide theoretical guarantees that the error between the optimal Q function and the Q function obtained by updating Q values using HMC sampling can be made arbitrarily small. This result also holds when only handful of Q values are updated using HMC and the rest are estimated using matrix completion. Further, we provide theoretical guarantee that the sampling complexity of our algorithm matches the mini-mar sampling complexity proposed by Tsybakov (208). Finally, we demonstrate the effectiveness of Hamiltonian Q-learning by applying it to cart-pole stabilization problem and an adaptive ocean sampling problem. Our results also indicate that our proposed approach becomes more effective with increase in state space dimension.
2 PRELIMINARY CONCEPTS
In this section, we provide a brief background on Q-Learning, HMC sampling and matrix completion, as well as introduce the mathematical notations. In this paper, |2| denotes the cardinality of a set 2. Moreover, R represent the real line and AT denotes the transpose of matrix A.
2.1 Q-LEARNING
Markov Decision Process (MDP) is a mathematical formulation that captures salient features of sequential decision making (Bertsekas) 1995). In particular, finite MDP is defined by the tuple
2

---

Under review as a conference paper at ICLR 2021
(,,,,,,,,,)) where S is the finite set of system states, A is the finite set of actions, P. 8 Axx - [0, is the transition probability kernel, r : S x A R is a bounded reward function, and y E [0. 1) is a discounting factor. Without loss of generality, states E S and actions a E A can be assumed to be -.-ddimensional and -addimensional real vectors, respectively. Moreover, by letting s² denote the ith element of state vector, we define the range of state space in terms of the following intervals [d7 ddj] such that s E [dr d,] Vi E {I,...,2) D.J. At each time & E {I....,T} over the decision making horizon, an agent observes the state of the environment 9; S and takes an action a according to some policy æ which maximizes the discounted cumulative reward. Once this action has been executed, the agent receives a reward r(st: at) from the environment and the state of the environment changes to 81+11 according to the transition probability kernel P. (-|st, ax). The Q function, which represents the expected discounted reward for taking a specific action at the current time and following the policy thereafter, is defined as a mapping from the space of state-action pairs to the real line, i.c. Q : x A + R. Then, by letting Q' represent the Q matrix at time t, i.c the tabulation of Q function over all possible state-action pairs associated with the finite MDP, we can express the Q value iteration over time steps as
Q'+ (5t; 0r)
Σ (s(ss,,, at) (t) + +7 (s).a)). .ES
Under this update rule, the Q function converges to its unique optimal value Q' (Melo 2001). But computing the sum ( over all possible next states is computationally expensive certain problems; in these cases taking the summation over a subset of the next states provides an efficient alternative for updating the Q values.
2.2 HAMILTONIAN MONTE CARLO
Hamiltonian Monte Carlo is a sampling approach for drawing samples from probability distributions known up to a constant. It offers faster convergence than Markov Chain Monte Carlo (MCMC) sampling (Neal al. 2011 Betancourt Betancourt et al.) 2017, Neklyudov et al.) 2020). To draw samples from smooth target distribution P(s), which is defined on the Euclidean space and assumed to be known up to a constant, HMC extends the target distribution to a joint distribution over the target variable s (viewed as position within the HMC context) and an auxiliary variable (viewed as momentum within the HMC context). We define the Hamiltonian of the system as
H v) - log P(s, v)
log P(s) log P(uls) (s) + K(v,s),
where Uss) A - log P(s) and K (v, s) & log P(r)s) fu" - represent the potential and kinetic energy, respectively, and M is suitable choice of the mass matrix.
HMC sampling method consists of the following three steps - (i) a new momentum variable is drawn from a fixed probability distribution. typically a multivariate Gaussian; (ii) then new proposal (s', e²) is obtained by generating a trajectory that starts from (s, v) and obeys Hamiltonian dynamics, i.c. 3 0H ú aH; and (iii) finally this new proposal is accepted with probability min {1, exp (H(s v) H(s', -('))} following the Metropolis Hastings acceptance/rejection rule.
Be
2.3
LOW-RANK STRUCTURE IN Q-LEARNING AND MATRIX COMPLETION
Prior work (Johns & Mahadevan| 2007 Geist& & Pietquin 2013 Ong 2015 Shah et al. (020) on
value function approximation based approaches for RL has implicitly assumed that the state-action value functions are low-dimensional and used various basis functions to represent them, e.g. CMAC, radial basis function, etc. This can be attributed to the fact that the underlying state transition and reward function are often endowed with some structure. More recently. Yangg et al. (2020b) provide empirical guarantees that the Q-matrices for benchmark Atari games and classical control tasks exhibit low-rank structure.
Therefore, using matrix completion techniques (Xu et al. 2013 Chen & Chil 2018) to recover Q ||S|X|4 from small number of observed Q values constitutes viable approach towards improving data efficiency. As low-rank matrix structures can be recovered by constraining the nuclear norm, the Q matrix can be reconstructed from its observed values (Q) by solving
EER six|A| [|인l|- subject to Ja(Q) In((),
arg min
(2)
where || ||. denotes the nuclear norm (i.c., the sum of its singular values), Q is the observed set of elements, and Jn is the observation operator, i.e. F2(x) x: if Ω and zero otherwise.
3

---

Under review as a conference paper at ICLR 2021
3 HAMILTONIAN Q-LEARNING
large class of real world sequential decision making problems for example, board/video games, control robots' movement, and portfolio optimization involves high-dimensional state spaces and often has large number of distinct states along each individual dimension. As using Q-Learning based approach to train RL-agents for these problems typically requires tens to hundreds of millions of samples (Mnih et al. 2015 Silver et al. 2017), there is strong need for data efficient algorithms for Q-Learning In addition, state transition in such systems is often probabilistic in nature: even when the underlying dynamics of the system is inherently deterministic; presence of external disturbances and parameter variationssunneeraaittiee lead to probabilistic state transitions.
Learning an optimal Q" function through value iteration methods requires updating Q values of state-action pairs using sum of the reward and discounted expectation of Q values associated with next states. In this work, we assume the reward to be a deterministic function of state-action pairs. However, when the reward is stochastic, these results can be extended by replacing the reward with its expectation. Subsequently, we can express T as
('t a1) = r(st, a.) + +HE max Q' (s)
(3)
where E denotes the expectation over the discrete probability measure P. When the underlying state space is high-dimensional and has large number of states, obtaining the expectation is computationally very expensive. The complexity increases quadratically with the number of states and linearly with number of actions, rendering the existing algorithms impractical.
accurate estimate of
In this work, we propose a solution to this issue by introducing an importance-sampling based method approximate the aforementioned expectation from sample mean of Q values over subset of next states. A natural way sample a subset from the set of all possible next states is to draw identically and independently distributed (IID) samples from the transition probability distribution P(- st, at). However, when the transition probability distribution is high-dimensions. and known only up to constant, drawing IID samples incurs a very high computation cost.
Dimnersse nal
1-Dimetnsional
2-Dimensional
3. DDDmmn
MMdde
Made
8 Mode
(()
ds
P(s)ds
HMC Samples
The first row illustrates that, as the dimension of the space increases, the relative volume inside partition compared to the volume outside of the partition decreases. When the dimension increases from I through the relative volume red partition decreases as 1/3, 1/9 and 1/27, respectively. The second row illustrates that the HMC samples are concentrated in the region that maximizes probability mass. Here P(s). SMode and ds represent probability density, mode of the distribution and volume, respectively.
Figure 1:
3.1 DATA EFFICIENCY THROUGH HMC SAMPLING
A number of importance-sampling methods LLu 1996 Betancourt) have been developed for estimat- ing the expectation of function by drawing samples from the region with the dominant contribution to the expectation. HMC is one such apportance-sampliigg method that draws samples from the typi- cal set, i.c., the region that maximizes probability mass, which provides the dominated contribution to the expectation. As shown in the second row of Figure I most of the samples in limited pool of HMC samples indeed concentrate around the region with high probability mass. Since the decay in Q function is significantly smaller compared to the typical exponential power law decays in transition probability function, HMC provides better approximation for the expectation of the Q value of the next states (Yang al. 2020b Shah al. 2020). Then by letting He denote the set of
4

---

Under review as a conference paper at ICLR 2021
HMC samples drawn at time step t, we update the Q values as:
(st, az) r(s az) + [74
?
max Q'
(4)
a
SEH.
HMC for a smooth truncated target distribution: Recall that region of states subset of Euclidean space given as E [ :d]] x x... : RR Thus the main challenge to using
HMC sampling is to define a smooth continuous target distribution P(a (4) which is defined on
R P, with sharp decay at the boundary of the region of states (Yi & Doshi Velez, 2017 Chevallier
al.
2018). In this work, we generate the target distribution by first defining the transition probability
kernel from the conditional probability distribution defined on RR,, and then multiplying it with
smooth cut-off function.
We first consider probability distribution P(-|st. ar) : RR" - R such that the following holds pste
P(S|Se, 0x) x P(s|,,, 4z)ds
(5)
for some arbitrarily small > 0. Then the target distribution can be defined as
Dr
P(s|s,, ax) P(s|ss, az)
II ==
(6)
1+ exp(-x(dd s))) 1 1+ exp(- nx(s d)
Note that there exists a large x > 0 such that if [d , x... x [db, di. then P(s|st, az) x P(s|s;, dz) and P(s]st az) = O otherwise. Let uust, at), E(s,, at) be the mean and covariance of the transition probability kernel. In this paper we consider transition probability kernels of the form
P(s|st, de) & exp (-21s= uuss, -s(ss,, a.)) - as), u(ss,a))) (-
Then from (5) the corresponding mapping can be given as multivariate Gaussian P(s 0t) (N (5e, ae). E(st, at).. Thus from (6) it follows that the target distribution is
D.
P(s|se, a.) = (N or), Ess,, at) II
(8)
t=1 1 exp(=x(d s¹)) 1 exp(-n(s' d)))
Choice of potential energy, kinetic energy and mass matrix: Recall that the target distribution
P(ssss, a.) ) is defined over the Euclidean space R. For brevity of notation we drop the explicit
dependence on (st. ae) and denote the target distribution as P(s). As explained in Section 2.2 we choose the potential energy U(s) = - log (P(s)). We consider an Euclidean metric M that S)TM(S 8). Then we define M, E RD.xD,
induces the distance between 6, 5 as d(E,, 8) = Thus, any metric M that defines an Euclidean
as diagonal scaling matrix and M, E R.DD.
rotation matrix in dimension D.. With
this we can define M as M = M,M.MMM structure on the target variable space induces inverse structure on the momentum variable space as d(ū 8) = (ö- 8) TMT M- -). This generates a natural family of multivariate Guassian distributions such that P(u)
(0, M) leading the kinetic energy K s) - log P(rls) 1 M- where M- 11 is the covariance of the target distribution.
3.2 Q-LEARNING WITH HMC AND MATRIX COMPLETION
In this work we consider problems with a high-dimensional state space and large number of distinct states along individual dimensions. Although these problems admit a large Q matrix, we can exploit low rank structure of the Q matrix to further improve the data efficiency.
At each time step we randomly sample a subset Q2 of state-action pairs (each state-action pair is sampled independently with some probability p) and update the Q function for state-action pairs in Ωr Let @++1 be the updated Q matrix at time t. Then from (4) have
+ (st, az) = r(s,, az) + HH
7
Σ max (s,a), V(s,, ax) E 9z-
Then we recover the complete matrix Q++1 by using the method given in 2 Thus we have
g++1=
arg min ||@++I|1 subject to In, (Q++)) Ja. (Q++1).
(10)
T lenis XIA
5

---

Under review as a conference paper at ICLR 2021
Algorithm 1 Hamiltonian Q-Learning
Inputs: Discount factor Y Range of state space; Time horizon T; Initialization: Randomly initialize Q"
for / to do
Step 1: Randomly sample a subset of state-action pairs Q2
Step 2: HMC sampling phase Sample set of next states He according to the target distribu-
tion defined in (6)
Step 3: Update phase- For all (st, dr) E St
+++ (st, 0e) r(st, ae) ािं EoEn. max (s)
Step 4: Matrix Completion phase
da, (ōlt1)= Ba, (Q++1)
Q++1= = arg ming LERISIXIAI ||Q subject to
end for
Similar to the approach used by Yang ct al. (2020b), we approximate the rank of the Q matrix as the minimum number of singular values that are needed capture 99% of nuclear norm.
3.3 CONVERGENCE, BOUNDEDNESS AND SAMPLING COMPLEXITY
In this section we provide the main theoretical results of this paper. First, we formally introduce the following regularity assumptions:
(A1) The state space S C RR and the action space A S I are compact subsets.
(A2) The reward function is bounded, i.e., r(s, a) E Ramin Rmax for all (s, a) E x
(A3) The optimal value function Q" is C-Lipschitz, i.e.
(*) Q* a
C C(Is= s'Ile + ||a a'lle)
where || || is the Frobenius norm (which same as the Euclidean norm for vectors).
We provide theoretical guarantees that Hamiltonian Q-Learning converges to an e-optimal Q function 27 number of samples. This matches the mini-max lower bound Ω (,,,
with Ô proposed in Tsybakov 2008). First we define a family of c-optimal Q functions as follows.
Definition 1 (e-optimal functions). Let Q" be the unique fixed point of the Bellman optimality equation given as (TQ) d')= E.ess Pssss', a') (r(s',d) d') + max, Q(s, V(s', .') E S x A where T denotes the Bellman operator. Then, under update rule (3), the Q function almost surely converges to the optimal Q' We define c-optimal Q functions as the family of functions Qe such that IIQ' 10 S whenever Q' E EQ.
= (a [IQ'(s, a) -0* a)ll. any c-optimal Q function is element wise e-optimal. Our next result shows that under HMC sampling rule given in Step of the Hamiltonian Q-Learning algorithm (Algorithm[]) []. the Q function converges to the family e-optimal Q functions. Theorem 1 (Convergence of Q function under HMC). Let T be an optimality operator under HMC given as (TQ) a') = =r(ssaa' + T
As
h ESEN max, ((s, a), V(s',a') E S x A, where H. is a subset of next states sampled using HMC from the target distribution given in (6) Then, under update rule (4) and for any given 0, there exists nu. t 0 such that I|'' Q' oo <evt t'.
Refer Appendix A. for proof of this theorem. The next theorem shows that the Q matrix estimated via suitable matrix completion technique lies in the c-neighborhood of the corresponding Q function obtained via exhaustive sampling.
Theorem 2 (Bounded Error under HMC with Matrix Completion). Let Q'+ ac) = r(st, at) + E.es P(s]st; as) max, (s, a), V(s,, at) S x A be the update rule under ex- haustive sampling, and Q' be the Q function updated according Hamiltonian Q-Learning
10
Then, for any given ē 2 0, there exists = min, |H,,,t' > 0, such that I|Q - QOyll E P.
Please refer Appendix A.2 for proof of this theorem. Finally provide guarantees sampling complexity of Hamiltonian Q- L-Larnning algorithm.
Theorem 3. (Sampling complexity of Hamiltonian Q-Learning) Let Da. D. be the dimension of state space and action space, respectively. Consider the Hamiltonian Q-Learning algorithm presented in Algorithm Then, under a suitable matrix completion method, the function convergea the family of c-optimal Q functions with Ô (D_t..D number of samples.

---

Under review as a conference paper at ICLR 2021
Proof of Theorem B is given in Appendix
4 EXPERIMENTS
4.1 EMPIRICAL EVALUATION FOR CART-POLE
Experimental setup: By letting 0, 0 denote the angle and angular velocity of the pole and x; a denote the position and velocity of the cart, the 4-dimensional state vector for the cart-pole system can be defined as s (0, (0,0,x;) x, After defining the range of state space as 0 E [- 2/2], i E |-3.0,3.0,, E [-2.4, and J E 3.5, we define the range of the scalar action as a E [-10 10). Then each state space dimension is discretized into distinct values and the action space into 10 distinct values. This leads to a Q matrix of size 625 x 10. To capture parameter uncertaintics and external disturbances, we assume that the probabilistic state transition is governed by multivariate Gaussian with zero mean and covariance D diag (0.143, 0.990, 0.635, 1.346]. To drive the pole to an upright position, we define the reward function as r(s, a) = cos cos$(15 (150) (Yang et al. 2020b). After initializing the Q matrix using randomly chosen values from [0, 1], sample state-action pairs independently with probability 0.5 at each iteration. Additional experimental details and results are provided in Appendix
Results: As it is difficult to visualize heat map for a 4-dimensional state space, we show results for the first two dimensions 0, & with fixed r, i. The color in each cell of the heat maps shown in Figures 2aa), (bb) and indicates the value of optimal action associated with that state. These figures illustrate that the policy heat map for Hamiltonian Q-Learning is closer to the policy heat map for Q-Learning with exhaustive sampling. The two curves in Figure 2 d). that show the Frobenius norm of the difference between the learned Q function and the optimal Q' illustrate that Hamiltonian Q-Learning achieves better convergence than Q-Learning with IID sampling. We also show that the sampling efficiency of any Q-Learning algorithm Hamiltonian Q Q-Learning. We illustrate this by incorporating Hamiltonian Q-Learning with vanilla Q-Learning, DQN, Dueling DQN and DDPG. Figure shows how Frobenius norm of the error between Q function and the optimal Q" varies with increase in the number of samples. Red solid curves correspond the case with exhaustive sampling and black dotted curves correspond to the case with Hamiltonian Q Q-Laanning. These results illustrate that Hamiltonian Q Q-Learning converges to an optimal Q function with significantly smaller number of samples than exhaustive sampling.
be significantly improved by incorporating
30
0000
25
201
42
12
100
150
137
13
Time (t)
(a) Exhaustive Sampling
(b) HMC Sampling
(c) HID Sampling
(d) Q Function Convergence
Figure 2: Figure tonian Q-Learning and L-Lamingg with IID sampling, respectively. Figure (] provides a comparison for
2 a). b) and ((c) show policy heat maps for Q-Leaming with exhaustive sampling, Hamil-
convergence of Q function with Hamiltonian Q- Q-Learning and Q-Learning with IID sampling.
1.0
0.8
INCC
194C
Pattes
DarG
0.6
0.4
0.2
0.0
0.0
0.5
0.5
1.0
0.0
0.5
Number samples 168
Number of samples
Number samples
Number samples 168
Figure 3: Mean square error vs number of samples of Q function with exhaustive sampling and Hamiltonian Q-Learning for vanila Q-Learning DQN, Dueling DQN and DDPG.
4.2 EMPIRICAL EVALUATION FOR ACROBOT (L.E., DOUBLE PENDULUM)
Experimental setup: of the first pole, angle of the second pole and angular velocity of the second pole, respectively, the d-dieensional state vector for the acrobot can be defined (0,, 01, 02 0z) AAteer defining the
By letting 01, 0,,02, d denote the angle of the first pole, angular velocity
7

---

Under review as a conference paper at ICLR 2021
range of state space as 01 E [- oT] E 3-0.0 [ E [- n| and 02 3-3.0, 3.0,, we define the range of the scalar action as a E [-100, 10). Then each state space dimension is discretized into distinct values and the action space into 10 distinct values. This leads to Q matrix of size 625 x 10. Furthermore, we assume that the probabilistic state transition is governed by a multivariate Gaussian with zero mean and covariance Σ diag (0. (4.143, 0.990, 0.635, 1.346]. Following [Sutton & Barto (2018). we define an appropriate reward function for stabilizing the acrobot to the upright position. After initializing the Q matrix using randomly chosen values from [0, 1]. we sample state-action pairs independently with probability p = 0.5 at each iteration.
Figure Iillusraates how Frobenius norm of the error between Q function and the optimal Q" varies with the number of samples. Red solid curves correspond to the case with exhaustive sampling and black dotted curves correspond to the case with Hamiltonian Q-Learning. These results show that for the same level of error Hamiltonain Q-Learning requires a significantly smaller number of samples compared to exhaustive sampling.
Results:
1.0
0.8
1
500 1942
Sastep t
0
0.4
0.2
0.0
0.0
0.5
1.0
0.0
0.5
1.0
0.0
0.5
1.0
0.0
0.5
1.0
Number of samples le8
Number of samples 168
Number of samples 1e8
Number of samples Jef
Figure 4: Mean square error vs number of samples of Q function with exhaustive sampling and Hamiltonian Q-Learning for vanila Q-I.carning, DQN, Dueling DQN and DDPG.
4.3 APPLICATION TO OCEAN SAMPLING
Ocean sampling plays a major role in a variety of science and engineering problems, ranging from modeling marine ecosystems to predicting global climate. Here, we consider the problem of using an under water glider to obtain measurements of a scalar field (c.g., temperature, salinity or concentration of certain zooplankton) and illustrate how the use of Hamiltonian Q-Learning in planning the glider trajectory can lead to measurements that minimize the uncertainty associated with the field.
States, actions and state transition: By assuming that the glider's motion is restricted to an horizontal plane (Refael& & Degani 2019), we let Ir and 0 denote its center of mass position and heading angle, respectively. Then we can define the 6-dimensional state vector for this system as s = (x, y,, 4. y, 0, 0) and the action a as scalar control input to the glider. Also, to accommodate dynamic perturbations due to the ocean current, other external disturbances and parameter uncertainties, assume that the probabilistic state transition is governed by a multivariate Gaussian.
Reward: As ocean fields often exhibit temporal and spatial correlations (Leonard et al., 2007).
this work focuses on spatially correlated scalar fields. Following the approach of Leonard et al.) (2007), we define ocean statistic correlation between two positions q = (2r, y) and q = (x', y as B(q. q') = exp(-llq //2)²/o²), where is the spatial decorrelation scale. The goal of the task is to take measurements that reduce the uncertainty associated with the field. Now we assume that the glider takes N measurements at positions {qi..... qN ). Then covariance of the collected data set can be given by a N x N matrix W such that its ith row and the jth column element is: W.y no.j + B(q:, 9;), where dy is the Dirac delta and v is the variance of the uniform and uncorrelated measurement noise. Then using objective analysis data assimilation scheme (Kalnay 2003 Bennet| 2005), the total reduction of uncertainty of the field after the measurements at positions 4v ) can be expressed as
N Σ
B(q.q B(q; 9).
(11)
qEOi.j= i-
By substituting the formulas from (Kalnay 2003
Bennett 2005 into 11 this formulation can be
generalized to Gaussian measurement noise.
Recall that the task objective is to guide the glider to take measurements at multiple locations/posiiions which maximize the reduction in uncertainty associated with the scalar field. Therefore the reward assigned to each state-action pair (s, a) is designed to reflect the amount of uncertainty that can
8

---

Under review as a conference paper at ICLR 2021
be reduced by taking measurement the position corresponding to the state and at the positions that correspond to the set maximally probable next states, i.c., arg max, P[s'|a a). Then, by letting 2, = {s} A (arg max, P(s' (s, [s,aa) a}}} denote the set of current state and the maximally probable next states for all possible actions, the reward function associated with reducing uncertainty can be given
Ta aa(3,a)= = - Blq. B(g, g).
9E EJEI
Without loss of generality, we assume that the glider is deployed from q = (0, 0) and retrieving the glider incurs a cost depending on its position. To promote trajectories that do not incur a high cost for glider retrieval, we define the following reward function
ra(3,a) a) = -q" Eq
where e = et 2 0. Then we introduce the total reward that aims to reduce uncertainty of the scalar field while penalizing the movements away from the origin, and define it as
r(s, a) = (s) + ro(s, a) -kq- Cq+
Σ Σ
B(g W. B(qi, q),
q iJEZ.
where x > 0 is trade-off parameter that maintains balance between these two objectives.
Experimental setup We define the range of state and action space x, [-10, 10). 2, [-25, 25]. 0 E [- n]. á [-3,3], and dimension into 5 distinct values and the action space into 5 distinct values, we have Q matrix of size 15625 Also, assume that the state transition kernel is given by multivariate Gaussian with zero mean and covariance Σ diag[11.111 69.444 11.111, 69.44. 19,444, 0.143, 0.9 0.990). After initializing the matrix using randomly chosen values from [o, 1], we sample state-action pairs independently with probability = 0.5 at each iteration. Also, we assume = 2.5, X 0.1, e diag [1, 0j. Additional experimental details and results are provided Appendix D
[], respectively and then discretizing each state
.04
379
ors
I0-9)
000
IME-0
525
628
101
45c
50
100
150
15.
Time (t)
(a) Exhaustive Sampling.
(b) HMC Sampling.
(c)
IID Sampling.
(d) Q-function Error.
Figure 5: Figure 5 a). b) and ((c) show policy heat maps for Q-Learning with exhaustive sampling, Hamil-
tonian Q-Learning and Q- QeLemrnnn with IID sampling respectively. Figure () provides comparison for
convergence of Q function with Hamiltonian Q-Learning and Q-Learning with IID sampling.
Results Figures 5 (a. 5)b) (]c show the policy heat map over first two dimensions x, y with fixed é. U. and 8. The color of each cell indicates the value of optimal action associated with that state. These figures illustrate that the difference between policy heat maps associated with Hamiltonian Q-Learning and Q-Learning with exhaustive sampling is smaller than the difference between policy heat maps associated with Q-Learning with IID sampling and Q-Learning with exhaustive sampling. The two curves in SigureBdd) that show the Frobenius norm of the difference between the learned Q function and the optimal Q*, illustrate that Hamiltonian Q-Learning achieves better convergence than Q-Learning with IID sampling. A comparison between results of the ocean sampling problem and the cart-pole stabilization problem indicates that Hamiltonian Q-Learning provides increasingly better performance with increase in state space dimension.
5 DISCUSSION AND CONCLUSION
Here we have introduced Hamiltonian Q-Learning which utilizes HMC sampling with matrix completion methods to improve data efficiency. We show, both theoretically and empirically, that the proposed approach can learn very accurate estimates of the optimal Q function with much fewer data points. We also demonstrate that Hamiltonian Q-Learning performs significantly better than Q-Learning with IID sampling when the underlying state space dimension is large. By building upon this aspect, future works will investigate how importance-samme -aapeeennnmingg based methods can improve data-efficiency in multi-agent Q-learning with agents coupled through both action and reward.

---

Under review as a conference paper at ICLR 2021
REFERENCES
Zafarali Ahmed, Nicolas Le Roux, Mohammad Norouzi, and Dale Schuurmans. Understanding the impact of entropy on policy optimization. In International Conference on Machine Learning, pp- 151-160. PMLR, 2019.
Andrew F Bennett. Inverse modeling of the ocean and atmosphere. Cambridge University Press, 2005.
Dimitri P Bertsekas. Dynamic Programming and Optimal Control, volume 1. Athena Scientific Belmont, MA, 1995.
Michael Betancourt. A conceptual introduction Hamiltonian Monte Carlo.
Michael Betancourt, Simon Byrne, Sam Livingstone, Mark Girolami, et al. The geometric foundations of Hamiltonian Monte Carlo. Bernoulli, 23(4A):2257-223) 2017.
Jacob Buckman, Danijar Hafner, George Tucker, Fugene Brevdo, and Honglak Lee. Sample- efficient reinforcement learning with stochastic ensemble value expansion. In Advances in Neural Information Processing Systems, pp. 8224-8234, 2018.
Emmanuel Candes and Yaniv Plan. Matrix completion with noise. Proceedings of the IEEE, 98(6): 925-936, 2010.
Yudong Chen and Yuejie Chi. Harnessing structures in big data via guaranteed low-rank matrix estimation: Recent theory and fast algorithms via convex and nonconvex optimization. IEEE Signal Processing Magazine, 35(4): 2018.
Augustin Chevallier Sylvain Pion, and Frédéric Cazals. Hamiltonian Monte Carlo with boundary reflections, and application polytope volume caleulations. 2018.
Richard Dearden, Nir Friedman, and Stuart Russell. Bayesian q-learning, Aaai/iaai, pp. 761-768, 1998.
Mare Deisenroth and Carl Rasmussen. Pilco: A model-based and data-efficient approach to policy search. In International Conference on Machine Learning (ICMI), pp. 465-472, 2011.
Yan Duan, Chen, Rein Houthooft, John Schulman, and Pieter Abbeel. Benchmarking deep reinforcement learning for continuous control. In International Conference on Machine Learning (ICML), pp. 1339, 2016.
Jianqing Fan, Bai Jiang, and Qiang Sun. Hoeffding's s lemma for markov chains and its applications /1 2018
to statistical learning. arXiv preprint
Matthieu Geist and Olivier Pietquin. Algorithmic survey of parametric value function approximation. IEEE Transactions on Neural Networks and Learning Systems, 24(6):845-867, 2013.
Susan Holmes, Simon Sobinsttin-Salzzedee and Christof Seiler. Curvature and concentration of Hamiltonian Monte Carlo in high dimensions, arXiv:1407.1114, 2014.
Heejin Jeong, Clark Zhang, George Pappas, and Daniel D Lee. Assumed density filtering q-learning. arXiv preprint arXiv: /7/2:077 2017.
Jeff Johns and Sridhar Mahadevan. Constructing basis functions from directed graphs for value function approximation. In Proceedings of the 24th international conference on Machine learning, pp. 385-392, 2007.
Eugenia Kalnay. Amospheric modeling, data assimilation and predictability. Cambridge University Press, 2003.
Sanket Kamthe and Mare Deisenroth. Data-efficient reinforcement learning with probabilistic model predictive control. International Conference on Artificial Intelligence and Statistics, pp. 1701-1710. PMLR, 2018.
10

---

Under review as a conference paper at ICLR 2021
Jens Kober, J Andrew Bagnell, and Jan Peters. Reinforcement learning in robotics: A survey. The International Journal of Robotics Research, (2(11):1238-122 1274, 2013.
Alec Koppel, Ekaterina Tolstaya, Ethan Stump, and Alejandro Ribeiro. Nonparametric stochastic compositional gradient descent for q-learning in continuous markov decision problems. arXiv preprint arXiv: 2018.
Su Young Lee, Choi Sungik, and Sae- Young Chung. Sample-efficient deep reinforcement learning via episodic backward update. Advances in Neural Information Processing Systems, pp. 2112-2121, 2019.
Naomi E. Leonard, Derek A. Paley, Francois Lekien, Rodolphe Sepulchre, David M. Fratantoni, and Russ E. Davis. Collective motion, sensor networks, and ocean sampling. Proceedings of the IEEE. 95(1):48-744 2007.
Jun S Liu. Metropolized independent sampling with comparisons to rejection sampling and impor- tance sampling. Statisties and Computing, 6(2): 13-119,, 1996.
TWU Madhushani, DH Sanjeeva Maithripala, and Jordan Berg. Feedback regularization and geometric pid control for trajectory tracking of mechanical systems: Hoop robots inclined plane. In 2017 American Control Conference (ACC), pp. 3938-3943. IEEE, 2017.
DHS Maithripala, TWU Madhushani, and JM Berg. A Geometric PID Control Framework for 2016.
Mechanical Systems.
Hongzi Mao, Mohammad Alizadch, Ishai Menache, and Srikanth Kandula. Resource management with deep reinforcement learning. In Proceedings of the 15th ACM Workshop on Hot Topics in Networks, pp. 50-56. 2016.
Rowan McAllister and Carl Edward Rasmussen. Data-efficient reinforcement learning in continuous state-action 2040-2049, 2017.
In Advances in Neural Information Processing Systems, pp.
Francisco S Melo. Convergence of Q-learning: A simple proof. Institute Of Systems and Robotics, Tech. Rep, pp. 1-4, 2001.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Marc G Bellemare, Alex Graves, Martin Riedmiller, Andreas Fidjeland, Georg Ostrovski, al. Human-level control through deep reinforcement learning. Nature, 518(7540):529-53 2015.
Radford M Neal et al. MCMC using Hamiltonian dynamics. Handbook of Markov Chain Monte Carlo, 2(11):2, 2011.
Kirill Neklyudov. Max Welling, Evgenii Egorov, and Dmitry Vetrov. Involutive MCMC: A Unifying Framework. arXiv:2006. 16653, 2020.
Hao Yi Ong. Value function approximation via low-rank models. 100.00150,.00061,
Yunpeng Pan and Evangelos Theodorou. Probabilistic differential dynamic programming. In Advances in Neural Information Processing Systems, pp. 1907-1915, 2014.
Gilad Refael and Amir Degani. A single-actuated swimming robot: Design, modelling, and experi- ments. Journal of Intelligent & Robotic Systems, 94(2):471-489, 2019.
Devavrat Shah, Dogyoon Song, Zhi Xu, and Yuzhe Yang. Sample efficient reinforcement learning via low-rank matrix estimation. arXiv:2006.061.55 2020.
David Silver, Julian Schrittwieser, Karen Simonyan, Ioannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lueas Baker, Matthew Lai, Adrian Bolton, et al. Mastering the game of Go without human knowledge. Nature, 550(7676):354
2017.
Elena Smirnova and Elvis Dohmatob. On the convergence of smooth regularized approximate value iteration schemes. Advances in Neural Information Processing Systems, 33, 2020.
Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.

---

Under review as a conference paper at ICLR 2021
Alexandre B Tsybakov. Introduction nonparametric estimation. Springer Science & Business Media, 2008.
Christopher JCH Watkins. Learning from delayed rewards. PhD thesis, King's College, Cambridge, Cambridge, UK, 1989.
Christopher JCH Watkins and Peter Dayan. Q-learning. Machine learning, 8(3-4):279-22) -222,, 1992.
Zaiwen Wen, Wotao Yin, and Yin Zhang. Solving low-rank factorization model for matrix completion by nonlinear successive over-relaxation algorithm. Mathematical Programming Computation, ((4):333-361)) 2012.
Yangyang Xu, Ruru Hao, Wotao Yin, and Zhixun Su. Parallel matrix factorization for low-rank tensor completion. arXiv: /3/2. 1254, 2013.
Wenhao Yang, Xiang Li, and Zhihua Zhang. A regularized approach to sparse optimal policy in reinforcement learning. In Advances in Neural Information Processing Systems, pp. 5940-5950, 2019.
Yuxiang Yang. Ken Caluwaerts, Atil Iscen, Tingnan Zhang, Jie Tan, and Vikas Sindhwani. Data efficient reinforcement learning for legged robots. In Conference on Robot Learning, pp. 1-10. PMLR, 2020a.
Yuzhe Yang, Guo Zhang, Zhi Xu, and Dina Katabi. Harnessing structures for value-based planning and reinforcement learning. In International Conference on Learning Representations (ICLR), 2020b.
Kexin Yi and Finale Doshi Velez. Roll-back Hamiltonian Monte Carlo. arXiv:1709.02830 2017.
Zhenpeng Zhou, Xiaocheng Li, and Richard N Zare. Optimizing chemical reactions with deep reinforcement learning. ACS Central Science, 3(12)11337-1444, 2017.
A CONVERGENCE AND BOUNDEDNESS RESULTS
proceed to prove theorem by stating convergence properties for HMC as follows. the initial sampling stage, starting from the initial position Markov chain converges towards to the typical set. In the next stage Markov chain quickly traverse the typical set and improves the estimate by removing the bias. In the last stage Markov chain refine the exploration of typical the typical set provide improved estimates. The number of samples taken during the last stage is referred as effective sample size.
A.1 PROOF OF THEOREM
Theorem 1. Let T be an optimality operator under HMC given as (TQ) d') r(5''a'
Esen max, Q(s, a), V(s', a') S A, where H a subset of next states sampled using HMC from the target distribution given in (6). Then, under update rule ( and for any given e 2 0, there exists Tex l' > 0 such that IIQ T 5 Vt 2 t..
H
Ao max, Q'( a), V(s,a) E A. Here we consider nh to be the effective number of samples. Let EpQ', Var be the expectation and covariance Q' with respect to the target distribution. From Central Limit Theorem for HMC we have
Proof of Theorem 1. Let Q'
VVaro'' Yi
Q' N [pp'
Since Q function does not decay fast we provide a proof for the case where Q' is C-Lipschitz. From Theorem 6.5 in (Hommes et al. 2014) we have that, there exists co 0 such that
11'' - E S co.
(12)
12

---

Under review as a conference paper at ICLR 2021
Recall that Bellman optimality operator T is a contraction mapping. Thus from triangle inequality we have
JQ1 - JQ2
$ max s
a((s +
7
max Q1(s.a)
[H1]
a
SES
-r(s',a')
max Q2 a)
|72
#ES
max e'.''
max Qi(s,a)
max Q2(s,
H2
SES
sES
Let M4l
|H2]
nz4 Then using triangle inequality we have
JQ1 T0Q
S
maxy
[ EpQi + ||0z Q2
+ max 8'a'
BpQi EpQ2
a
Since Q function almost surely converge under exhaustive sampling we have
EpQ: - EpQ2| s <> Q: Q2
max
(13)
From equation
12 and equation
13 we have after time steps
JQI JQ2
2co + > 1 Q2
Dc
Let Rmar and Rmin be the maximum and minimum reward values. Then we have that
Q1 22
S 7 Rmer Rmin-
1 1-7
Thus for any 2 by choosing y such there exists a E' such that Vt 2 t'
||Q' - -= Se
This concludes the proof of Theorem
A.2 PROOF OF THEOREM 2
Theorem 2. Let Q'+++ (St, (st, 0e) = r(se, ue) + E.Es (Ps))ss St, az) max. (s,,,,), V(s, at) ax) E A be the update rule under exhaustive sampling, and Q' be the function updated according to Hamiltonian Q-Learning, i.e. by 10) Then, for any given 2 0, there exists nH, t' > 0, such that ||Q* Qf S EEvt
Proof of Theorem 2. Note that each time step attempt recover the matrix Q i.e., Q function time time under exhaustive sampling though matrix completion method starting from Q'. which is the Q updated function at time using Hamiltonian Q-Leaniing From Theorem 4 in (Chen & Chi 2018) we have that Vt 2 t' there exists some constant 8 >> such that when the updated Q function Q' satisfy
o - Q'è Sc
where e some positive constant then reconstructed (completed) matrix Q' satiesfies
| fee-oell_
< <ol@: 0%
(14)
for some 8= > 0. This implies that when the initial matrix used for matrix completion is sufficiently close to the matrix we are trying to recover matrix completion iterations converge to a global optimum. From the result of Theorem we have for any given 0, there exists ny, t' > 0 such that Vt 2 t
@ Q- <
(15)
Recall that under the update equation 1
(sx, az) = r r(se, a+) +7 E Eses max, Q% 8, a), V(s,, a.) e A we have that Qe almost surely converge the optimal Q" Thus there exists tt such that
Vt 2
| - - 0=
Let & max(t), (,,(ttt)) fJ. Then from triangle inequality we have that
Q
0'
| Q-
02 0-|| 2c.
13

---

Under review as a conference paper at ICLR 2021
Thus from equation
14 have that
q - 0
28c
This concludes the proof Theorem 2
B SAMPLING COMPLEXITY
In this section we provide theoretical results on sampling complexity of Hamiltonian Q-Learning, For brevity of notation we define ()(ss max, ((s, a). Note that we have the following regularity conditions on the MDP studied in this paper.
Regularity Conditions
1. Spaces and A (state space and action space) are compact subsets of RP, and Rp. respectively.
2. All the rewards are bounded such that r(s, a) E [Rmine Rmax], for all (s, a) E A.
3. The optimal Q* C-Lipschitz such that (* (s',''')) s C s'11 + a' [PP)
Now we prove some useful lemmas for proving sampling complexity of Hamiltonian Q-Learnig Lemma 1. For some constant C1, if
max {18) maxx(15)1443))|144422) ||
Q4 C1
log
with (s) Se then there exists constart 02 such that
Q'(s.a) (s) c2c
Proof of Lemma 1. Recall that in order to complete a low rank matrix using matrix estimation methods, the matrix can not sparse. This condition can be formulated using the notion of incoherence. Let Q be matrix of rank rq with the singular value decomposition Q UEVT, Let To be the orthogonal projection of Q R (|IIA to its column space. Then incoherence parameter of (QQ) can be give as
S
AA
((Q) max
max 1sig(s)
||TUc
TTcell TQ IS
max
.q
where e; are the standard basis vectors. Recall that Qf is the matrix generated in matrix completion phase from Q From Theorem 4 in Chen & Chi (2018) we have that for some constant C₁ if a fraction of elements are observed from the matrix such that
o 6.r2 D.D.
C2
log (D, D..)
where o, is the coherence parameter of Q' then with probability at least 1 - C2(D, Da) for some constant C2 with @)( - (s, I there exists a constant such that
(o((s,a) Q" a)
S C2E
Note that p
10 A
Further we have for some constant C3
DrrD.Da log (D, + D.)
max |11 | DeDa
log (D, + D.)
Thus follows that for some constant 01 if
14 max [|S/2,1411 1.A12] | |SA.D..
log (D, + D.))
14

---

Under review as a conference paper at ICLR 2021
with ())
I e then there exists a constant C2 such that
('( - Q" Q"(s,a) S C2F
This concludes the proof of Lemmal
Lemma 2. Let be the spectral gap of Markov chain under Hamiltonian sampling where
& E [0, 1]. Let R Rmax Rmin be the maximum reward gap. Then v(s', a') E x A we have that
- < 32
1 1+ 2 {
|mmax
2 log
AR+ +
HH
i
with at least probability 1 5.
Proof Lemma Let Q(5', a() = =((s' + -/4
EvEh max. Q(8 a). Recall that MQ(ss)
[7]
max, Q(s, a). Then we have that @(5',a) d = r(s',a') + [H] EeEn MQ(s). Then follows that
( Q"(s', a') r(s', a') + 7 Σ MQ(s) r(s' ,') MBP (s)
[71]
SEH
H
MQ(s:) - Bppp(Q(ss)
= H
Y
MQ(ss)) ?
MQ (s:)
H
171
MQ" -EPMQQ
(16)
H
Recall that all the rewards are bounded such that r(s, a) E [Amin Rmax], for all (s, $ x A. Thus for all s, a have that MQ(ss)
12g Rmax. Let AR Rmax Rmin- Then we have that
[96
[2
72
Ms(ss))
7
MQQ
(s:)
AR.
(17)
|7
|H]|
Let & E [0, 1] be a constant such that - is the spectral gap of the Markov chain under Hamiltonian sampling. Then from Fan al. 2018 have that
1 1- 17 (1 (1-?) 2)
P
(*) - EP
Sexp
17
1
2R max
Let 8 = exp
1- Hi I+t 21
Then we have that
1 1+ 2
<TRaax
)
2 log
2 5
0
1 E |7
1 1-7
Thus we see that
1 1+ E 2 ( Rmax log
2
MQ* EpMQQ(s)
(18)
I - E [
with at least probability 1-6 5. Thus it follows from equations equation that
16
equation
17
and equation
18
(sss,,a)) Q'' 32 1-7 AR+ + E 2
y
Rmax
2 log
1- E 17
with at least probability - 8. This concludes the proof of Lemma Lemma 3. For all (s, a) E x A we have that
72 Rmax
(Q,(s, - (s,
201
1-7
with probability at least 1 5
15

---

Under review as a conference paper at ICLR 2021
Proof of Lemma 3. From Lemma
2 and Shah al. (0200) have that for all (s,
+ E 2
(2 [BBaax 2
2
(8' a) - Q
- 1
AR+
log
(19)
1- (74l 1-7
with probability at least
4. Thus we have that
72
1 1 2
(>Rmax (1-7)
2
2 IT)
(s) - (s.
S c1
AR
log
1 E [Hel
8
with probability at least
4. Fro all 1 - T letting
H7 = 1 + g 2
2/ (T)
log
{ 72
we obtain
7² R Rmaxx 7
1 + 2
(>uax 1-7
2
2
log
E HHl
Thus have,
7-8 Rmax
(s, - (s)
$
1
with probability least 1 - 8. Recall that ((s also proves that
ES x A we have MQ(ss S 3AR. Thus this
(s, (sssa)-Qua (aaa)-Q"((e (s, s 20 - (=
This concludes the proof Lemma 3
Now we proceed to prove the main theorem for sampling complexity as follows.
Theorem 3. Let D,, Da be the dimension of state space and action space respectively. Consider the Hamiltonian Q-Learning algorithm presented in Algorithm / Under suitable matrix completion method sampling complexity of the algorithm, Q function converge to the family of c-optimal Q functions with (c-(D.-D+4)) number of samples.
Proof of Theorem 3. Note that sample complexity of Hamiltonian Q-Learning can be given as
T
Hell S T. Qr. |HT.
log(
Rmaa
Let 3 be the discretization parameter time and it follows that
Then from Lemmas
and
log
T. 12, [2,1
(
(D+DD++
This concludes the proof of Theorem
C ADDITIONAL EXPERIMENTAL DETAILS AND RESULTS FOR CART-POLE
Let 0, Ô be the angle and angular velocity of the pole, respectively. Let æ. ø be the position and linear velocity of the cart, respectively. Let a be the control force applied to the cart. Then, by defining m, M, 1 and as the mass of the pole, mass of the cart, length of the pole and gravitational acceleration, respectively, the dynamics of cart-pole system can expressed
i g sin 0 mtmld sin
cos 0
m-M
meas?0 0
(20)
+ ml (0 0 - Ø cos 0
m + M
16

---

Under review as a conference paper at ICLR 2021
State space of cart-pole system is 4-dimensional (D, 4) and any state E S is given by (0, 0, .... We define the range of state space 0 [-pi/2, x/2), [33.0,3.0] and å E [-3.5,3 3.5). We consider action space to be 1 I-dimensional (D = 1) space such that [-10, 10). We discretize each dimension in state space into values and action space into 10 values. This forms a Q matrix of dimensions 625 x 10.
[-2.4, 2.4]
Although the differential equations (20) governing the dynamics of the pendulum cart system are deterministic, uncertainty of the parameters and external disturbances to the system causes the cart pole deviate from the defined dynamics leading stochastic state transition. Following the conventional approach we model these parameter uncertainties and external disturbances using multivariate Gaussian perturbation (Maithriplla al., 2016; Madhushani et al. 2017 McAllister & Rasmussen 2017). Here we consider the co-variance of the Gaussian perturbation to be 0.14,0 0.990, 0.635, 1.346].
Let 8t (0,, de, 2t, i+)) and of be the state and the action at time Then the state transition probability kernel and corresponding target distribution can be given using (7) and (8), respectively, with mean u(st, az)) (0, O,T, 02 + OcT, 2t + dtg,, in F,r), where O,, 3e can be obtained from (0 by substituting 0,, 0., at, and co-variance E(st, 04) E.
Our simulation results use the following value for the system parameters m = 0.1 M = 1kg. 1 = 0.5m and g 9.8ms We take 100 HMC samples during the update phase. We trajectory length L = 100 and step size 81 = 0.02. We randomly initialize the Q matrix using values between and 1. We provide additional comparison heat maps for first two dimensions 0, with fixed x. .t.
54
10
15
25
9..0
0.63
10.00
-15
-66
-50
-15
-50
(a) Exhaustive Sampling
(b) HMC Sampling
(c) HID Sampling
Figure 6: Figure 6 a) 6 b) and (()) show policy heat maps Q-Learning with exhaustive sampling, Hamilto-
nian Q-Learning and Q-I.can .aanning with IID sampling, respectively.
Further, provide additional comparison heat maps for last two dimensions x, & with fixed 0, Ó.
10.
180
100
35
74
355
35
L25
06
65
30
4.75
4.75
55
4.75
-75
35
-75
-35
0.
(a)
Exhmustive Sampling
(b) HMC Sampling
(c) IID Sampling
Figure 7: Figure 7 a). 7 b)) and c) show policy heat maps for Q-Learning with exhaustive sampling, Hamilto-
nian Q-Lerrning and Q L-Laning with IID sampling, respectively.
17

---

Under review as a conference paper at ICLR 2021
54
L75
10
40
-00
-10
-5.0
1000
1000
24
0.0
(a) Exhaustive Sampling
(b) HMC Sampling
(c) IID Sampling
Figure 8: Figure a), 8 b) and ()) show policy heat maps for Q-Learning with exhaustive sampling, Hamilto-
nian Q-Learning and Q-L.erming with IID sampling, respectively.
D ADDITIONAL DETAILS FOR OCEAN SAMPLING APPLICATION
Glider dynamics By assuming that the glider's motion restricted an horizontal plane (Refael & Degani 2019), we let æ, y and 0 denote its center of mass position and heading angle, respectively, Then we can define the 6-dimensional state vector for this system
(ar, ct. U, 0 0) and the action a as a scalar control input to the glider. Also, to accommodate dynamic perturbations due to the ocean current, other external disturbances and parameter uncertainties. we assume that the probabilistic state transition is governed by multivariate Gaussian. We consider that the motion of the glider is restricted to horizontal plane. Let 2, and / be the coordinates of the center of mass of glider and heading angle respectively. By introducing q x
8)² the dynamics of the glider
y
can be expressed as
Mî RF, Pb +
where
m
cos 0
sin cos 0
0
M diog
m
sin 0 0
Iin Tout_
0
a 0 sgn(0) sin(3 ( + 1)) a 02 cos(B + 2))
0 - sgm 00) Iina
Fj
Fb 0vV
22 + 1
L
ay 2 L
+ r cos 1/2
Hg = aa
+ cos vb
ab = OsdsTr
2
2
0g = 0.005;
a = 0.062; My = 0.0074;
0= 2.5.
Our simulation results system parameter values from Table I We define the range of state and [-3, 3), and [-1,
action space 2, y [010,, 10), &, [-25, 25), 0 [- -- m.. respectively and then discretizing each state dimension into distinct values and the action space into distinet values, have Q matrix of size 15625 x Also, we assume that the state transition kernel is given by multivariate Gaussian with zero mean and covariance [diag[11.11) 69.444, 11.111, 69. 444. 0. 04143, 0.990). After initializing the Q matrix using ran- domly chosen values from [0, 1], we sample state-action pairs independently with probability each iteration. Also, we assume a 2.5, 0.1, diag 1, 0). We take 100 HMC samples during the update phase. We use trajectory length L 100 and step size 51 = 0.02.
0.5
Additional experimental results dimensions x, y with fixed à, ú. 0,6
provide additional comparison heat maps for first two
18

---

Under review as a conference paper at ICLR 2021
Table 1: Notations
Notations
Description
Value
total mass
1.03 kg
Tin
inner body moment of inertia
0.5 kg m²
Lout
outer body moment inertia
0.174 kg m²²
radius
0.08
L
length of the flap
0.09 m
df
submersible depth of the flap
0.044
db
submersible depth of the body
0.02 m
B
angular location of the flap maximum open angle of the flap
30
20
Cj
drag coefficient of the flap drag coefficient of the body water density
C.
1027 kg m
p
1.50
L00
1.50
18.0
0.50
0.50
625
320
6.55
.00
-50
0.50
5.0
..50
-150
0.50
0.75
-175
(a) Exhaustive Sampling
(b) HMC Sampling
(c) HDD Sampling
Figure 9: Figure 9 a) b) and (c) show policy heat maps for e-rmnnnnng with exhaustive sampling, Hamilto- nian Q-Learning and g--ancnnn with IID sampling, respectively.
1.66
10
1.00
10.
6.5
16.0
10.6
0.25
5.0
025
0.5
0.00
300
0.00
5.0
-50
350
4.75
4.75
6.75
18.0
30.
30.0
-0.0
183
0.0
(a) Exhaustive Sampling
(b) HMC Sampling
(c) IID Sampling
Figure 10: Figure a)) b) and c) show policy heat maps for Q-Learning with exhaustive sampling. Hamiltonian Q-Learning and Q Leaamnngg with IID sampling, respectively.
1.50
675
1E0
0.55
10.0
6.75
0.50
5.0
5.0
0:0
0.50
4025
-33
425
5.0
-50
-075
-175
-035
-0.0
-1.00
4800
-1.03
300
-1.00
100
110
5-3
100
103
3.1
103
1000
010
100
(a) Exhaustive Sampling
(b) HMC Sampling
(c) Sampling
Figure 11: Figure 11 a). 11 (b) and (1(c) show policy heat maps for Q-Learning with exhaustive sampling, Hamiltonian Q-Learning and Q Q-Learing with IID sampling, respectively.
E APPLICATION OF HMC SAMPLING FOR Q- O-LEARNING: FURTHER DETAIL.S
In this section provide detailed explanation drawing HMC samples from given state transition probability distribution. Let (s),a) be the current state action pair. Let u(s,, a,), E(s, ax) be the mean and covariance of the transition probability kemnl.. In order draw HMC samples
19

---

Under review as a conference paper at ICLR 2021
required to define the corresponding potential energy and kinetic energy of the system. Let P( az) be the smooth target state transition distribution.
Potential energy, kinetic energy and mass: In this work consider P(s|st ae) to be truncated multivariate Gaussian as given in equation [8] Thus potential energy can be explicitly given as,
(s) = (P)()(ss) 2 (8 x -1)) 2
log (2x) det(E))
D2 Σ log (1 11+exp(-nd)
2'))) + log exp(<<nsx - - dr)))
where, l and E correspond to the mean and variance of the transition probability kernel. In the context of HMC s referred to as the position variable. Then we chose kinetic energy can be given as
(e) - (og(((((s)) = 2 M - uo
where e is the momentum variable and M = Σー1 corresponds to the mass/inertia matrix associated with the Hamiltonian.
Hamiltonian Dynamics: As the Hamiltonian is the sum of the kinetic and the potential energy, i.c. Hs, Us) K(v), the Hamiltonian dynamics can be expressed as
aK
Ee
Ov
and
0U ----- (s p)) [S(-x(dt - -(-ss))s(ss- ())
0
where S(E1.... {DD)) [S(E)). S(ED.)) T denotes element wise sigmoid function of the vector S. We initialize HMC sampling by drawing a random sample from the transition probability distribution and new momentum variable from the multivariate Gaussian (0, 1-)). We integrate the Hamiltonian dynamics for L steps with step size Al to generate the trajectory from (s, v) to (s',v"), v'). To ensure that the Hamiltonian is conserved along the trajectory, we use volume preserving symplectic integrator, in particular leapfrog integrator which uses the following update rule to go from step 1 1 Al:
(U)) as
(U(s)
11 Up 0.5A
81-A1 AIE VH4I t 0.5A
Ōs
H+
Acceptance of the proposal:
Then, following the Metropolis- acceptance/rejeetion rule, this new proposal accepted with probability
exp (H(s u))
min
exp (s', -0)))
Updating Q function using HMC samples: Let H, be the set of next states obtained via HMC
sampling, i.e., position variables from the accepted set of proposals. Then we update Q(+,, 0z) using
equation g
20


Reviews:
[{"review_id": "z0uFo8cdxHk", "reviewer": "AnonReviewer2", "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": "In this paper, a Hamiltonian Q-learning is proposed by combining Hamiltonian Monte Carlo with matrix completion. Evaluations are compared with Q-learning.\n\n1. How to interpret Eqn.(3)(9) as a Hamiltonian equation (usually consisting of coordinates and momenta) is not clear. The so-called Hamiltonian Q-learning takes minimization optimization and essentially claims an equivalence of energy in physics model, which might not always make sense. What is kinetic energy in your case? A Hamiltonian equation is usually defined as a functional of some parameters, is your problem defined over the policy?\n\n2. In experiments, the proposed method is compared against Q-learning, but not with more advanced RL algorithms, e.g. DQN, DDPG, etc. The scalability of proposed method can be further investigated. More environments are also necessary.\n\n3. It is not clear that how accurate it is to assume the Q-table to be a low-rank matrix. I agree it is a reasonable assumption, but highly doubt its practical performance, especially in large-scale problems. \n\n4. The analysis in Section 3.3 is trivial, not enough to justify an acceptance.\n\nTherefore, I am not convinced by the contributions.\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "n82y2ogRzNV", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper studies appling Hamiltonian sampling to computing Bellman equation (thus Q-learning iterations) approximately. I have a few questions:\n\n 1. The Hamiltonian sampling approach requires knowing the distribution in advance. How is this possible in our setting? If we are estimating this distribution, then since it is high dimensional, we still need large amount of data. This is the most confusing point from my point of view.\n2. As for the matrix completion approach: why is this reasonable? Why does the Q-table have low-rank property? I think at least this assumption should be justified empirically, otherwise, the theoretical result doesn't make any sense.  Also, the definition of the low-rank property itself is very suspicious, because it needs to hold for any policy. As a result, this may be very hard to verify rigorously. But at least some preliminary evidence should be presented.", "extra_scores": {}, "extra_text": {}}, {"review_id": "hd17clZLxvp", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "\nStrengths:\n\n1) To my knowledge, this is the first credible effort to apply Hamiltonian Monte Carlo to Q learning in order to avoid some degree of the random sampling required for its almost sure convergence. At least the algorithm novelty is apparent.\n\n2) The experiments clearly demonstrate the merits of the proposed importance sampling scheme for obtaining improved convergence of Q learning, and for yielding coverage of the space comparable to exhaustive sampling. \n\n3) The idea of using importance sampling *during* training is a key distinguishing feature from a majority of other works which use it for, upon the basis of a fixed prior policy, improving the current policy.\n\n\n\nWeaknesses:\n\n\n1) The preliminaries section is disjoint/fragmented. The limitations of Q learning (equation (1)) should directly motivate use of Hamiltonian Monte Carlo (HMC) in Section 2.2, but instead the manner in which HMC is presented is as additional preliminary material. This is not inherently disqualifying, but a number of exotic terms are introduced in the ``preliminaries\" Section 2.2 without explanation or otherwise connection to the RL problem, such as momentum variable, leapfrog integrator, Hamiltonian, etc. Why are these entities pertinent to MDPs and Q learning? This needs to be more carefully and conscientiously connected. A similar comment is true for Section 2.3 -- matrix completion or the need for addressing matrix estimation problems is nowhere to be found in 2.1 and 2.2, which leaves the reader confused as to why matrix completion is being discussed. This overall disjointedness then makes the conceptual innovation of this work more mysterious to understand, which is a concern. \n\n2) The reasoning in the paragraph before Section 3.1 seems incorrect. The fact that samples in a limited pool of IID samples concentrate around the region with high\nprobability density is not evidence that this is a poor estimate for the expected value, but rather that the expected value is not representative of a uniform distribution across  the space. Thus, I think the authors might have intended to  be talking about higher-order moments of this conditional distribution, such as the skewness, kurtosis, etc. or otherwise risk measures such as CVaR.\n\n3) The main convergence theory (Theorems 1-2) do not exhibit any discernible complexity or sample efficiency gains over vanilla Q learning. Moreover, a coherent discussion of the technical innovations required to establish these theorems is absent from the manuscript. These limitations alone are very concerning.\n\n4) The matrix completion step (equations (9)-(10) is playing the role of a proximal operator on the Q learning update, or otherwise some projection of the Bellman error onto a low-dimensional subspace of features. Therefore, the steps conducted in Section 3.2 are very similar mathematically to entropic regularization, which may also be seen as a special case of a proximal operator on the space of Q functions. This connection is not made in the paper, as well as the more computational/statistical motivation for where the matrix competition step comes from. I strongly suggest the authors consider better explaining the links between step (4) of Algorithm 1 and proximal methods in any revision of this work.\n\n5) Proofs seem fairly routine in my reading. What is new or innovative here? Again, this is not explained anywhere.\n\n\nMinor Comments:\n\n\n1) References missing on distributional/representational aspects of Q learning:\n\nDearden, R., Friedman, N., & Russell, S. (1998, July). Bayesian Q-learning. In AAAI (pp. 761-768).\n\nKoppel, A., Tolstaya, E., Stump, E., & Ribeiro, A. (2018). Nonparametric stochastic compositional gradient descent for q-learning in continuous markov decision problems. arXiv preprint arXiv:1804.07323.\n\nJeong, H., Zhang, C., Pappas, G. J., & Lee, D. D. (2019, August). Assumed density filtering Q-learning. In Proceedings of the 28th International Joint Conference on Artificial Intelligence (pp. 2607-2613). AAAI Press.\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "3mOcpAZPJM", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This work focuses on dynamic programming in the tabular setting. It proposes to use Hamiltonian Monte-Carlo (HMC) to sample the next states (instead of IID samples) and matrix completion to learn a low-rank Q matrix. It shows theoretical convergence. Experiments on discretized problems (CartPole and an ocean sampling problem) show that HMC and low-rank learning can behave more benignly compared to IID samples.\n\nThere are several issues with the current manuscript.\n\n1. It can be applied to only tabular problems with known dynamics, which is restricted as many control problems are continuous, and their underlying dynamics are unknown. Q-learning can be applied in the RL setting, but not the method proposed in this paper.\n\n2. Some technical details are not clearly described:\n- What is the distribution used for Fig.1?\n- Why is the \\euler{P} in Eq.(5) necessary? Why not directly use \\mathbb{P} as in Eq.(7) and (8)?\n\n3. Experiments:\n- It seems that the covariance matrices are defined arbitrarily for both CartPole and Ocean experiments.\n- Do Fig.2(a) to (c) correspond to the same (optimal) actions? Or the optimal actions wrt their own Q values?\n- Fig.2(d) is not very informative as we can have zero consecutive difference yet the Q function is far from the true optimal Q. Showing distance to the optimal Q values would be more meaningful.\n- For the Ocean experiment, it is not clear how the action will affect the dynamic. More specifically, it is clear in Eq.(16) that the action $a$ will affect the state dynamic, but not for the ocean experiment equations on page 14.\n- More descriptions about the ocean sampling problem would be helpful for the readers to understand the task. It seems that only the first term of the reward function on page 8 depends on the state (not sure where the action fits in this equation).\n\n4. Paper organization. Both Sec.3.4 and Sec.4 are experiments, so why not put them into the same section?\n\nMinors\n- In Fig.1 caption, 1 should be 1/3. \n- In reference, McAllister and Rasmussen: ta-efficient -> data-efficient", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: 
The paper considers exploiting low-rank structure in Q-function and the Hamiltonian Monte-Carlo (HMC) to approximate the expectation in Q-learning to reduce the stochastic approxiamtion error, and thus, achieves "efficient RL". The authors tested the algorithm empirically within some simple environments. 

As reviewers (R1, R3, R4) mentioned, the major bottleneck of this algorithm is the assumption that the dynamics is known up to a constant, which is extremly strong, and thus, limits the application of the algorithm. I suggest the authors to consider the common RL setting, without any knowledge about the transition models, and make fair empirical comparison with baselines in the same setting.


Decision: Reject