Actor-Critic for Linearly-Solvable Continuous MDP
with Partially Known Dynamics

arXiv:1706.01077v1 [] 4 Jun 2017

Tomoki Nishi
Toyota Central R & D Labs. Inc,
Nagakute, Aichi, Japan
nishi@mosk.tytlabs.co.jp
Michael R. James
Toyota Research Institute
Ann Arbor, MI, 48105
michael.james@tri.global

Prashant Doshi
THINC Lab, Dept. of Computer Science
University of Georgia, Athens, GA 30622
pdoshi@cs.uga.edu
Danil Prokhorov
Toyota R & D
Ann Arbor, MI, 48105
danil.prokhorov@toyota.com

Abstract
In many robotic applications, some aspects of the system dynamics can be modeled accurately while others are difficult to obtain or model. We present a novel
reinforcement learning (RL) method for continuous state and action spaces that
learns with partial knowledge of the system and without active exploration. It
solves linearly-solvable Markov decision processes (L-MDPs), which are well
suited for continuous state and action spaces, based on an actor-critic architecture.
Compared to previous RL methods for L-MDPs and path integral methods which
are model based, the actor-critic learning does not need a model of the uncontrolled
dynamics and, importantly, transition noise levels; however, it requires knowing
the control dynamics for the problem. We evaluate our method on two synthetic
test problems, and one real-world problem in simulation and using real traffic data.
Our experiments demonstrate improved learning and policy performance.

1

Introduction

Reinforcement learning (RL) offers a way of learning high-quality policies (control) for an agent by
exploring its environment. Methods for RL have predominantly focused on domains with discrete
state and actions. Those that operate on continuous states or actions resort to sampling or other
approximations because of the difficulty in analytically solving the continuous Bellman equation [20].
In this regard, Todorov [16] introduced the linearly-solvable Markov decision process (L-MDP), a
subclass of general MDPs, which allows us to quickly solve the continuous Bellman equation exactly
under a class of structured dynamics and rewards. Specifically, the Bellman equation in L-MDPs
is recast as a linearized differential, and its solution is efficiently obtained as a linear eigenfunction
when the whole dynamics model is available [18]. As such, L-MDPs are particularly well suited for
modeling robotic learning and planning, where the state and actions spaces are usually continuous.
In addition to continuous spaces, high-impact robotic applications such as autonomous vehicles
impose an additional constraint on RL. They preclude an exhaustive exploration of the state and action
space because it would be unacceptable for an autonomous vehicle to optimistically try maneuvers
that would lead to a crash or even a near-miss, leaving much of the state and action spaces unexplored.
However, at the same time, guaranteeing safe exploration has a high computational cost that is shown
to be NP-hard [9].
L-MDPs decompose the dynamics model into passive and active (control) dynamics with added
actuator noise. In this paper, we present a new method for semi model-free RL for L-MDPs,

which uses a partially-known system dynamics model. Specifically, the method requires the control
dynamics model, which represents the effect of actions to be specified, but not the passive dynamics
model nor the noise in the transitions. Knowing control dynamics is feasible in our motivating context
of autonomous driving because advanced driver assistance systems such as adaptive cruise control
are already available in most new vehicles, and these utilize a model of the control dynamics. More
importantly, knowing such a model makes safe active exploration unnecessary. Furthermore, the
correct actuator noise is often difficult to prespecify, which adds to this method’s appeal.
Our method called passive actor-critic (pAC) finds the policy within the standard two-step architecture
of actor-critic methods comprising a policy improvement step (actor) and state evaluation (critic).
Passive actor-critic combines the data collected on passive state transitions with the known control
dynamics. In the context of L-MDPs, the critic estimates the expected value function using the
linearized Bellman equation from the data and the actor improves the policy using the standard
Bellman equation on data and the active dynamics model. In addition to the well-known radial
basis function [18, 19], multi-layer neural networks are also introduced for approximating the value
function with demonstrated performance improvements. The method is evaluated on two known
synthetic domains and on our motivating domain of freeway merge by an autonomous car both in
simulation and using real-world traffic data. Interestingly, pAC improves on previous model-based
methods despite requiring reduced model specifications. Importantly, pAC finds policies that succeed
in freeway merge on real data at rates exceeding 90%, motivating transition to real-world testing as
future work.

2

Related Work

Previous approaches for solving L-MDPs are predominantly model based [17, 18, 21]. These
efficiently optimize control policies by solving the linearized Bellman in discrete- or continuous-state
L-MDPs when the system dynamics is fully known. Our method relaxes this requirement using
samples of passive dynamics, while knowing the control dynamics. We also introduce multi-layer
neural networks for approximating the value functions in L-MDPs in addition to the previously used
radial basis functions.
Uchibe and Doya [19] formulate Z-learning based on least-square TD learning for continuous LMDPs. The method optimizes the policy while requiring knowledge of the control dynamics and
transition noise. The motion noise inherent in robotic platforms is often unknown due to which
this method may not apply to robot learning. pAC learns the noise levels during optimization given
sampled data and knowledge of control dynamics by minimizing the error between the value and
action-value functions. This makes pAC well positioned for application to robot-based RL.
As pAC can learn from data containing samples of passive dynamics, it bears resemblance to batch
RL methods [8]. A popular and model-free batch RL method is fitted Q-iteration [1, 2], which finds
policy from collected data without a model of system dynamics. It searches for actions that minimize
the Q-value, which requires that either the action space be discrete or the Q-function has structure
such as being quadratic due to computational cost. In contrast, pAC uses policy that is analytically
derived from the estimated Z-value, parameter for transition noise, and known control dynamics.
Path integral control also learns a policy based on linearized Bellman equation [15, 3]. Unlike
approaches for L-MDPs, path integral control can directly optimize the policy. However, the approach
has to sample sample many trajectories under a training policy from a certain initial state. As we
mentioned previously, we seek to avoid such active and potentially unsafe explorations in the real
world.
Finally, many RL methods that use neural networks for continuous MDPs have been recently
proposed [5, 14]. These methods optimize a policy with active exploration while our method seeks
to find a policy from data on passive state transitions (of the underlying Markov chain) with known
control dynamics. On the other hand, the utility of networks to approximate the value function
remains the same.
2

3

Preliminaries

We briefly review L-MDPs for understanding our method. We focus on a discrete-time system with
a real-valued state x ∈ Rn and control input u ∈ Rm , whose stochastic dynamics is defined as
follows:
xk+1 = xk + A(xk )∆t + Buk ∆t + diag (σ) ∆ω,
(1)
where ∆ω is differential Brownian motion simulated by a Gaussian N (0, I∆t), where I is the
identity matrix. A(xk ), Buk and σ ∈ Rn denote the passive dynamics, control dynamics due to
action, and the transition noise level, respectively (B is an input-gain matrix). ∆t is a step size of
time and k denotes a time index. System dynamics structured in this way are quite general: for
example, models of many mechanical systems conform to these dynamics.
L-MDP [17] is a subclass of MDPs [13] defined by a tuple, hX , U, P, Ri, where X ⊆ Rn and
U ⊆ Rm are continuous state and action spaces. P := {p(y|x, u) | x, y ∈ X , u ∈ U} is a state
transition model due to action, which is structured as in Eq. 1, and R := {r(x, u) | x ∈ X , u ∈ U}
is an immediate cost function with respect to state x and action u. A control policy u = π(x) is a
function that maps a state x to an action u. The
hPgoal is to find a policy
i that minimizes the following
n−1
average expected cost: Vavg := limn→∞ n1 E
r(x
,
π(x
))
.
k
k
k=0
Grondman et al. [4] notes that the Bellman equation for MDPs can be rewritten using the value
function V (x) called V-value, state-action value function Q(x, u) called Q-value, and average value
Vavg under an policy.
Vavg + Qk = rk + Ep(xk+1 |xk ,uk ) [Vk+1 ].

(2)

As we may expect, Vk = minu∈U Qk . Ep(xk+1 |xk ) [·] is expectation over a probability distribution of
state transition under the passive dynamics. Here and elsewhere, subscript k is values at time step k.
An L-MDP defines the cost of an action (control cost) to be the amount of stochastic effect it has on
the system, adding it to the state cost:
r(xk , uk ) := q(xk )∆t + KL(p(xk+1 |xk )||p(xk+1 |xk , uk )).

(3)

Here, q(x) ≥ 0 is the state-cost function; KL(·||·) is the Kullback-Leibler (KL) divergence;
p(xk+1 |xk ) models the passive dynamics while p(xk+1 |xk , uk ) represents the active or control
dynamics of the system. L-MDPs further add a condition on the dynamics as shown below.
p(xk+1 |xk ) = 0 ⇒ ∀uk p(xk+1 |xk , uk ) = 0.
This condition ensures that no action introduces new transitions that are not achievable under passive
dynamics. The stochastic dynamical system represented by Eq. 1 satisfies this assumption naturally
because the dynamic is Gaussian. However, systems that are deterministic under passive dynamics
remain so under active dynamics. This condition is easily met in robotic systems where noise is
prevalent.
The standard Bellman equation for MDPs can then be recast in L-MDPs to be a linearized differential
equation for exponentially transformed value function of Eq. 2 (hereafter referred to as the linearized
Bellman equation) [18]:
Zavg Zk = e−qk ∆t Ep(xk+1 |xk ) [Zk+1 ],

(4)

where Zk := e−Vk and Zavg := e−Vavg . Here, Zk and Zavg are an exponentially transformed value
function called Z-value and the average cost under an optimal policy, respectively. Because the
passive and control dynamics with the Brownian noise are Gaussian, the KL divergence between
these dynamics becomes,
−1
KL(p(xk+1 |xk )||p(xk+1 |xk , uk )) = 0.5u>
uk ∆t,
kS
−1

>

(diag(σi2 ))−1 B

where S := B
for L-MDPs can we derived as,

(5)

and σi denotes i-th element of σ. Then, the optimal control policy
π(xk ) = −SB >

3

∂Vk
.
∂xk

(6)

4

Passive Actor-Critic for L-MDP

We present a novel actor-critic method for continuous L-MDP, which we label as passive actorcritic (pAC). While the actor-critic method usually operates using samples collected actively in
the environment [6], pAC finds a converged policy without exploration. Instead, it uses samples
of passive state transitions and a known control dynamics model. pAC follows the usual two-step
schema of actor-critic: a state evaluation step (critic), and a policy improvement step (actor).
1. Critic: Estimate the Z-value and the average cost from the linearized Bellman equation using
samples under passive dynamics;
2. Actor: Improve a control policy by optimizing the Bellman equation given the known control
dynamics model, and the Z-value and cost from the critic.
We provide details on these two components below.
4.1

Estimation by Critic using Linearized Bellman

The critic step of pAC estimates Z-value and the average cost by minimizing the least-square error
between the true Z-value and estimated one denoted by Ẑ.
Z 
2
1
Ẑavg Ẑ(x; ν)−Zavg Z(x) dx,
(7)
min
ν,Ẑavg 2 x
Z
1
Ẑ(x; ν)dx = C, ∀x 0 < Ẑ(x; ν) ≤
s.t.
,
Ẑ
x
avg
where ν is a parameter vector of the approximation and C is a constant value used to avoid
convergence to the trivial solution Ẑ(x; ν) = 0 for all x. The second constraint comes from
∀x, Z(x) := e−V (x) > 0 and ∀x, q(x) ≥ 0. The latter implies that V + Vavg > 0, and note that
Zavg Z(x) := e−(V +Vavg ) , which is less than 1.
We minimize the least-square error in Eq. 7, Ẑavg Ẑk − Zavg Zk , with TD-learning. The latter
minimizes TD error instead of the least-square error that requires the true Z(x) and Zavg , which are
not available. The TD error denoted as eik for linearized Bellman equation is defined using a sample
i
i
Ẑki − e−qk Ẑk+1
(xk , xk+1 ) of passive dynamics as, eik := Ẑavg
, where the superscript i denotes the
iteration. Ẑavg here is updated using the gradient as follows:

i 2
i+1
i
i ∂ ek
i
Ẑavg = Ẑavg − α1
= Ẑavg
− 2α1i eik Ẑki ,
(8)
∂ Ẑavg
where α1i is the learning rate, which may adapt with iterations.
In this work, we approximate the Z-value function in two ways: (i) using a linear combination of
weighted RBFs, and (ii) using a neural network (NN). When a NN with an exponentiated activation
function of output layer is used, the parameters ν are updated with the following gradient based on
backpropagation. 1
2
∂ 
∂ Ẑki
i
i i
Ẑ
Ẑ
−
Z
Z
≈
2e
Ẑ
,
(9)
avg
avg
k
k
k
avg
∂ν i
∂ν i
where eik is the TD error as defined previously.
On the other hand, when weighted RBFs are used, Ẑ(x; ν) := ν > f (x), and a Lagrangian relaxation
of the objective function is useful as it includes the three constraints weighted using Lagrangian
parameters λ1 , λ2 and λ3 . For convenience, denote ν̃ i as,
i
ν̃ i := ν i − 2α2i eik Ẑavg

∂ Ẑki
,
∂ν i

1 −tanh(x)
e
orR e−softplus(x) is used as an activation function of the output layer to satisfy the constraint Ẑ ≥ 0.
The constraint x Ẑ(x; ν)dx = C is ignored in practice because convergence to ∀x, Ẑ(x; ν) = 0 is rare.
i
i
min ([1, e−qk Ẑk+1
]) is used instead of e−qk Ẑk+1
to satisfy Ẑ ≤ 1/Zavg in Eq. 7.

4

where α2i is the learning rate. The update of ν cognizant of the constraints is then,
 Z




∂
i>
i>
i
i
i
λ
ν̃
f
(x)dx
−
C
+
λ
ν̃
−
0
+
λ
Ẑ
−
1/
Ẑ
,
ν i+1 = ν̃ i +
k
avg
1
2
3
∂ ν̃ i
x
= ν̃ i + λi1 1 + λi2 + λi3 fk ,
(10)
R
where we utilize x f (x)dx = 1 and replace the constraint ∀x Ẑ(x; ν) > 0 by ν > 0 because the
constraint on ν always satisfies the former. 1 is a vector of all ones.
Lagrangian parameters λ1 , λ2 and λ3 in each iteration are obtained by ensuring that the updated
parameter vector ν i+1 satisfies the three constraints in Eq. 7 for xk . Formally,
Ẑ(xk ; ν i+1 ) = (ν̃ i + λi1 1 + λi2 + λi3 fk )> fk ≤ 1/Ẑavg ,
ν i+1 = ν̃ i + λi1 1 + λi2 + λi3 fk > 0 and,
Z
>
Ẑ(x; ν i+1 )dx = ν̃ i + λi1 1 + λi2 + λi3 fk 1 = C.
x

4.2

Actor Improvement using Standard Bellman

The actor component improves a policy by computing S (Eq. 5) using the estimated Z-values from
the critic because we do not assume knowledge of noise level σ. It is estimated by minimizing the
least-square error between the V-value and the state-action Q-value:
Z 
2
1
min
Q̂(x, û(x)) − V (x) dx,
S 2 x
where V is the true V-value and Q̂ is the estimated Q-value under the estimated action û(x). Notice
from Eq. 6 that a value for S results in a policy as B is known. Thus, we seek the S that yields the
optimal policy by minimizing the error because the Q-value equals V-value iff û is maximizing.
Analogously to the critic, we minimize the least-square error given above, Q̂ik − Vk , with TD-learning.
To formulate the TD error for the standard Bellman update, let xk+1 be a sample at the next time
step given state xk under passive dynamics, and let x̃k+1 := xk+1 + B ûk ∆t be the next state using
control dynamics. Rearranging terms of the Bellman update given in Eq. 2, the TD error dik is,
dik := r(xk , ûk ) + V̂ i (x̃k+1 ) − V̂avg − V̂ki .
We may use Eqs. 3 and 5 to replace the reward function,
>

i −1
r(xk , ûk ) = (qk + 0.5û>
ûk )∆t = qk ∆t + 0.5
k (Ŝ )

∂ V̂ki
∂ V̂ i
B Ŝ i B > k ∆t.
∂xk
∂xk

∂ V̂ i

The last step is obtained by noting that ûik = −Ŝ i B > ∂xkk , where Ŝ denotes estimated S in Eq. 6.
The estimated V-value and its derivative is calculated by utilizing the approximate Z-value function
from the critic. Ŝ is updated based on standard stochastic gradient descent using the TD error,
2
∂  i
∂di
Ŝ i+1 = Ŝ i − β i
Q̂k − Vk ≈ Ŝ i − 2β i dik k ,
∂ Ŝ i
∂ Ŝ i
where β is the learning rate. The actor mitigates the impact of error from estimated Z-value by
minimizing the approximated least-square error between V- and Q-values under the learned policy.
4.3 Algorithm
We show a pseudo code of pAC in Algorithm 1. Z(x) and Zavg are estimated in the critic with samples, and S is done in the critic with samples, estimated Ẑ(x) and Ẑavg . In the critic, feedback from
the actor is not needed (unlike actor critic methods for MDPs) because the Z-value is approximated
with samples from passive dynamics only. We emphasize that the actor and critic steps do not use the
functions A and σ but does indeed rely on B, of Eq. 1. As such, the updates use a sample (xk , xk+1 )
of the passive dynamics, and the state cost qk . Consequently, pAC achieves semi model-free learning
for L-MDPs.
5

Algorithm 1 passive Actor Critic
0
1: Initialize parameters Ẑavg
, ν 0 , Ŝ 0 , α10 , β 0
2: for Iteration i = 1 to N do
3:
Sample set of a state, a next state and state cost (xk , xk+1 , qk ) from dataset randomly
4: critic:
i
i
5:
eik ← Ẑavg
Ẑki − exp (−qk )Ẑk+1
∂ Ẑ i

i
k
6:
Update ν i+1 with 2eik Ẑavg
∂ν i
i+1
i
7:
Ẑavg
← Ẑavg
− 2α1i eik Ẑki
8: actor:
i
i
i
i
9:
V̂ki ← − ln Ẑki , V̂k+1
← − ln Ẑk+1
, V̂avg
← − ln Ẑavg
∂ V̂ i

>

∂ V̂ i

10:

i
i
− V̂avg
− V̂ki
dik ← qk + 0.5 ∂xkk B Ŝ i B > ∂xkk ∆t + V̂k+1

11:

Ŝ i+1 ← Ŝ i − 2β i dik ∂ Ŝki

∂di

Car-on-a-Hill
"
A(x)
B
σ

Pendulum

xv (1 + s(xp ))

−9.8 sign(xp ) 1 + s(xp

>
0, 1

>
0, 1

Simulated freeway merge

#

1
−2

− 1
)−2 2



xv , sin(xp )

0,

0,

>



dv12 , 0, dv02 + 0.5a0 (x)∆t, a0 (x)

>
1
>
2

>


>
0.5∆t, 1, 0, 0

>
0, 2.5, 0, 2.5

Table 1: System dynamics of each domains

5

Numerical Experiments

We evaluate pAC for L-MDPs on two synthetic domains, Car-on-a-Hill and Pendulum, also used
previously on L-MDPs by Todorov [18]; and on our motivating domain of autonomous merging in a
congested freeway.
5.1

Problem settings

Car-on-a-Hill Car-on-a-Hill has a two-dimensional state space, x = [xp , xv ]> where xp and xv
denote position and velocity, respectively, and a one-dimensional action space. Table 1 shows the
dynamics in detail. The state cost is given by,



q(x) =4.0 exp −0.5(xp − 1)2 − (xv + 1)2 + exp −0.5(xp + 1)2 − (xv − 1)2 − 2 .
Initial states are randomly set in −2π ≤ xp ≤ 2π and −π ≤ xv ≤ π.
Pendulum The Pendulum problem also has a two-dimensional state space similar to the Car-on-aHill and a one-dimensional action space. Table 1 shows the dynamics in detail. State cost is given
by



q(x) = 4.0 exp −(xv − 3)2 + exp −(xv + 3)2 − 2) .
Initial states are randomly set in −2π ≤ xp ≤ 2π and −π ≤ xv ≤ π.
Simulated freeway merging This new contemporary domain simulates freeway merges by an
automated vehicle. We refer the reader to Fig. 1 for establishing the four-dimensional state space.
Here, x = [dx12 , dv12 , dx02 , dv02 ]> where dxij and dvij denote the horizontal signed distance and
relative velocity between cars i and j ∈ [0, 1, 2]. The action space is one-dimensional (acceleration).
Table 1 shows the dynamics in detail. The dynamics presume that the leading vehicle is driven
with a constant speed v2 = 30[m/sec], and the following vehicle is driven by a known car-following
model [12]. The acceleration of the vehicle a0 (x) is calculated with −αv2β dv02 /(−dx)γ02 , where if
the following vehicle is slower than the leading vehicle (dv02 < 0), α = 1.55, β = 1.08, γ = 1.65,
otherwise α = 2.15, β = −1.65, γ = −0.89. The assumptions are used to simulate maneuvers of
ambient vehicles in only the simulated freeway merge domain.
The state cost designed to motivate Car-1 to merge midway between Cars 0 and 2 with the same
velocity as Car-0, is:
!

2
2dx12
2
q(x) = k1 − k1 exp −k2 1 −
− k3 dv10
dx02

6

Figure 1: The 3-car system for studying merging. Merging vehicle (Car-1) should ideally merge midway
between the following vehicle (Car-0) and leading vehicle (Car-2). dx12 and dv12 denote Car-1’s relative
position and velocity from Car-2.

Figure 2: Learning curves of average costs for pAC(blue), QP(green) and Z-learning(red) in three experiments.
Results of pAC and Z-learning are illustrated in Freeway-Merge as QP could not learn any reasonable policies.

QP
Z-learning
pAC

A(x)
Known
Unknown
Unknown

B
Known
Known
Known

σ
Known
Known
Unknown

Table 2: Model requirements for the evaluated methods. Notice that pAC imposes least requirement on prior
model knowledge.

where k1 , k2 and k3 are weights for the state cost ([k1 , k2 , k3 ] = [1, 10, 10] if dx02 < dx12 <
0, [10, 10, 0] otherwise). Initial states are randomly picked in −100 < dx12 < 100 [m], −10 <
dv12 < 10 [m/sec], −100 < dx02 < −5 [m], and −10 < dx02 < 10 [m/sec].
5.2

Performance Evaluation

We compared pAC with two other methods: model-based learning based on quadratic programming
(QP) and Z-learning. QP requires all system dynamics and approximates the Z-value with quadratic
programming [17]. Z-learning assumes that B and σ are available to approximate Z-value using the
critic. QP and Z-learning calculate the policy with Eq. 6. We are unaware of any fully model-free
method for L-MDPs. model-free PI control (e.g. [15]) assume action cost is available and it is
equivalent to the assumption of the known transition noise level in L-MDPs. Table 2 gives the prior
knowledge requirement on components of the system dynamics in Eq. 1.

Figure 3: (Left) Merging success rate for pAC and Z-learning in 30 seconds. RBFs and NN were the two
function approximators used. (Right) Merging success rate for pAC and Z-learning on NGSIM. S is estimated
by a Gaussian process for Z-learning as true dynamics are not available. Raw and ANN denote states sampled
randomly and with ANN from data.

Gaussian RBFs are used to approximate the Z-value function in all methods and NNs are additionally
used in Z-learning and pAC. RBFs were spaced uniformly in the range of sampled data: 400 RBFs
were used for Car-on-a-Hill and Pendulum domains, and 4,096 RBFs were used for the Merging task.
The standard deviations of the bases were 0.7 of the distance between the closest two bases in each
dimension.
7

A three-hidden layer perceptron with 200, 200 and 50 units in first, second and third hidden layers
is used as the NN. The number of nodes in the input is same as the dimensions of state space and
one output, respectively. The rectified linear function [10] is used as the hidden layers’ activation function. The activation function in the output layer for Car-on-a-Hill is exp(−tanh(x)) and
exp(−softplus(x)) for other domains. We estimated S as constant in pAC. Inputs of the perceptron
were normalized to the range [0, 1].
In Fig. 2, we compared average cost calculated over periods of 10 seconds for Car-on-a-Hill and
Pendulum, and 30 seconds for Merging, under learned policies in each domain. Observe that pAC
finds a similar or better policy in comparison to other learning methods in all domains. QP could not
learn any reasonable policy in Merging domains because of an issue referred to in [18]: QP might
not converge to a principal Eigen pair, instead of converging to a 2nd or higher-order pair.
This improvement over Z-learning may come as a surprise because Z-learning makes greater use
of model knowledge – it calculates S using the true B and σ. Nevertheless, the presence of the
additional actor step in pAC makes the difference. The actor additionally minimizes the error in
Q-value to obtain S. This error is not minimized if S is obtained as in Eq. 5 due to the approximation
error of Z-value. Subsequently, pAC estimates S differently, in a more targeted way to obtain a better
policy.
We evaluated the rate of merging successfully in a time limit of 30 seconds starting from 125 different
states in Freeway-Merge. We defined success as being between the leading and following vehicles
after 30 seconds. Figure 3 (a) shows the success rate: pAC with RBFs and NN achieved 93% and 97%
success rate respectively, which is comparable to Z-learning. All results shows pAC is comparable or
better than Z-learning despite less prior knowledge instead of using actor step.
5.3

Experiment on real-world traffic

The NGSIM data set contains vehicle trajectory data recorded by cameras mounted on top of a
building for 45 minutes around the evening rush hour[11]. Vehicle trajectories were extracted using
a vehicle tracking method from collected videos [7]. We extracted three-vehicle systems (Fig. 1)
representing 637 freeway merge events.
We compared pAC and Z-learning based on RBFs and NN on the extracted data from NGSIM.
Z-learning calculated a policy with transition noise σ estimated with a Gaussian process due to
unknown true dynamics. We used the same state variables, action variable and reward function
as used in the simulated Freeway-Merge domain. We calculated next states xk+1 under passive
> D
D
dynamics by subtracting state change caused by actions:xk+1 = xD
k+1 − B uk , where xk+1 and
D
uk are the next state and the action recorded in the data set respectively. We resampled data to
mitigate any imbalance and sparseness by sampling randomly a state and choosing a nearest data
from the state using the approximate nearest neighbor method.

Figure 4: A snapshot of vehicles tracked in NGSIM. The bounding boxes denote the positions of tracked
vehicle and numbers are vehicle indices.
Success was defined as being between Car-0 and Car-2 at the merging point, for those instances in the
data set where Car-1 on entry ramp completed its merge. Trajectories of Car-0 and Car-2 were played
back from recorded logs, and trajectories of Car-1 were simulated with the control dynamics and
learned policies. The dataset was randomly partitioned into five sub-datasets where an almost equal
number of trajectories were included. Four sub-dataset were used as training data and a remaining
sub-dataset were used as the test data for testing the policy. Each method was evaluated five times
for each different test data. Figure 3(b) shows the success rate for each method. Firstly, we note
the significant performance improvement when NN is used as the function approximator. Both pAC
and Z-learning with RBFs simply do not perform well. Specifically, pAC with NN achieved a 93%
success rate significantly outperforming Z-learning with NN. The result shows that the actor, which
8

minimizes the error of Q-value, improves performance more than the noise level estimation from the
dataset. The model-free RL approaches cannot be applied here due to the need for active exploration.

6

Concluding Remarks

We presented a novel method for semi model-free RL for L-MDPs – an important subclass of MDPs.
The passive actor-critic optimizes a policy without active exploration, instead of using samples of
the passive dynamics and knowledge of the control dynamics. This is a first formulation of the
actor-critic schema in the context of L-MDPs. We evaluated the method using three domains. Results
show that pAC achieves comparable or better performances than benchmarked methods despite less
prior knowledge requirements. As such, pAC represents a significant step toward more efficient RL
in continuous domains.
Data under passive dynamics and accurate models of control dynamics are needed for pAC. This may
seem to limit applicability apparently but, as mentioned, it is well suited for contemporary robotic
applications such as automated driving in real-world traffic. In this case, passive and control dynamics
correspond to models of ambient and autonomous vehicles, respectively. pAC obtains a better policy
with the car’s own dynamics model, which is now commonly available, and uses data collected on
maneuvers of the ambient vehicles whose models are usually not known. An evaluation of the learned
policies toward freeway merging using a real traffic data set illustrates its usefulness for practical
applications. We are interested in exploring additional challenges, e.g., entering roundabouts.

References
[1] András Antos, Csaba Szepesvári, and Rémi Munos. Fitted q-iteration in continuous action-space
mdps. In Advances in neural information processing systems 21, pages 9–16, 2008.
[2] Matteo Gaeta, Vincenzo Loia, Sergio Miranda, and Stefania Tomasiello. Fitted q-iteration by
functional networks for control problems. Applied Mathematical Modelling, 40(21):9183–9196,
2016.
[3] Vicenç Gómez, Hilbert J Kappen, Jan Peters, and Gerhard Neumann. Policy search for path
integral control. In Joint European Conference on Machine Learning and Knowledge Discovery
in Databases, pages 482–497. Springer, 2014.
[4] Ivo Grondman, Lucian Busoniu, Gabriel AD Lopes, and Robert Babuska. A survey of actorcritic reinforcement learning: Standard and natural policy gradients. IEEE Transactions on
Systems, Man, and Cybernetics, Part C (Applications and Reviews), 42(6):1291–1307, 2012.
[5] Nicolas Heess, Gregory Wayne, David Silver, Tim Lillicrap, Tom Erez, and Yuval Tassa.
Learning continuous control policies by stochastic value gradients. In C. Cortes, N. D. Lawrence,
D. D. Lee, M. Sugiyama, and R. Garnett, editors, Advances in Neural Information Processing
Systems 28, pages 2944–2952. Curran Associates, Inc., 2015.
[6] Vijay R Konda and John N Tsitsiklis. Actor-critic algorithms. In Advances in neural information
processing systems 13, pages 1008–1014, 1999.
[7] Vijay Gopal Kovvali, Vassili Alexiadis, PE Zhang, et al. Video-based vehicle trajectory data
collection. In Transportation Research Board 86th Annual Meeting, 2007.
[8] Sascha Lange, Thomas Gabel, and Martin Riedmiller. Batch reinforcement learning. In
Reinforcement learning, pages 45–73. Springer, 2012.
[9] Teodor M Moldovan and Pieter Abbeel. Safe exploration in markov decision processes. In
Proceedings of the 29th International Conference on Machine Learning (ICML-12), pages
1711–1718, 2012.
[10] Vinod Nair and Geoffrey E Hinton. Rectified linear units improve restricted boltzmann machines.
In Proceedings of the 27th International Conference on Machine Learning (ICML-10), pages
807–814, 2010.
[11] NGSIM-dataset. http://ops.fhwa.dot.gov/trafficanalysistools/ngsim.
htm, 2005. U.S Department of Transportation, Federal Highway Administration, Accessed
August 20, 2016.
9

[12] Johan Janson Olstam and Andreas Tapani. Comparison of car-following models. Swedish
National Road and Transport Research Institute, Project VTI meddelande, 960, 2004.
[13] Martin L. Puterman. Markov Decision Processes. John Wiley & Sons, New York, 1994.
[14] John Schulman, Sergey Levine, Philipp Moritz, Michael I Jordan, and Pieter Abbeel. Trust
region policy optimization. CoRR, abs/1502.05477, 2015.
[15] E. Theodorou, Jonas Buchli, and Stefan Schaal. A Generalized Path Integral Control Approach
to Reinforcement Learning. Journal of Machine Learning Research, 11:3137–3181, 2010.
[16] Emanuel Todorov. Linearly-solvable markov decision problems. In Advances in neural
information processing systems 19, pages 1369–1376, 2006.
[17] Emanuel Todorov. Efficient computation of optimal actions. Proceedings of the national
academy of sciences, 106(28):11478–11483, 2009.
[18] Emanuel Todorov. Eigenfunction approximation methods for linearly-solvable optimal control
problems. In Adaptive Dynamic Programming and Reinforcement Learning, 2009. ADPRL’09.
IEEE Symposium on, pages 161–168. IEEE, 2009.
[19] Eiji Uchibe and Kenji Doya. Combining learned controllers to achieve new goals based
on linearly solvable mdps. In Robotics and Automation (ICRA), 2014 IEEE International
Conference on, pages 5252–5259. IEEE, 2014.
[20] Marco Wiering and Martijn Van Otterlo, editors. Reinforcement learning, volume 12. Springer,
2012.
[21] Mingyuan Zhong and Emanuel Todorov. Aggregation methods for lineary-solvable markov
decision process. In Proceedings of the World Congress of the International Federation of
Automatic Control, 2011.

10

