Policy Gradient Methods for Reinforcement Learning with Function
Approximation and Action-Dependent Baselines
Philip S. Thomas
Carnegie Mellon University

Emma Brunskill
Stanford University

arXiv:1706.06643v1 [] 20 Jun 2017

We show how an action-dependent baseline can be used by the policy gradient theorem using
function approximation, originally presented with action-independent baselines by Sutton et al.
(2000).

1

Notation and Background

We assume that the reader is familiar with the seminal paper by Sutton et al. (2000), which shows how the policy gradient
theorem (Baxter and Bartlett, 1999) can be extended to include function approximation and action-independent baselines.
Our paper is intended to be read immediately after reviewing Section 3 of the paper by Sutton et al. (2000). Although
here we adopt the episodic setting, the extension of this work to the average reward setting is straightforward. We use
the notational standard MDPNv1 (Thomas and Okal, 2015) and the following additional definitions, where expectations
conditioned on θ denote that actions, At , are sampled from π(St , ·, θ) unless otherwise specified:
"∞
#
X
t
Objective function:
ρ(θ) :=E
γ Rt θ
vθ (s) :=E

State value function:

qθ (s, a) :=E

State-action value function:

"

t=0

∞
X

t=0
"∞
X

t

γ Rt S0 = s, θ

#

t

γ Rt S0 = s, A0 = a, θ

t=0

dθ (s) :=

Discounted state distribution:

∞
X

#

γ t Pr (St = s|θ)

t=0

∂
ln(π(s, a, θ))
fw (s, a) :=w|
∂θ

2
X
1X
L(w) :=
dθ (s)
π(s, a, θ) fw (s, a) − qθ (s, a)
2 s
a


∂
?
nθ
w ∈ w∈R :
L(w) = 0 .
∂w

Compatible function approximator:
Loss function:
Critical q-parameters:

2

The Policy Gradient Theorem With Function Approximation and ActionIndependent Baselines

The policy gradient theorem with function approximation and action-independent baselines, as presented by Sutton et al.
(2000), states that for all b : S → R,
X
X
∂
∇ρ(θ) =
dθ (s)
π(s, a, θ) (fw? (s, a) − b(s))
ln(π(s, a, θ)).
∂θ
s∈S

a∈A

The action-independent baseline, b, does not add bias because:

=0

z
}|
{
∂
∂ X
dθ (s)
π(s, a, θ)b(s) ln(π(s, a, θ)) =
dθ (s)b(s)
π(s, a, θ) = 0.
∂θ
∂θ
s∈S
a∈A
s∈S
a∈A
|
{z
}
X

X

X

=1

However, introducing an action-dependent baseline, b : S × A → R, can introduce bias because b(s, a) cannot be pulled out
of the sum over actions, and so the derivative of the sum over actions does not necessarily evaluate to zero.
1

3

The Policy Gradient Theorem With Function Approximation and ActionDependent Baselines

We will show how an action-dependent baseline, b : S × A → R, can be incorporated into the policy gradient theorem with
function approximation without introducing bias. To do so, we define a different loss function, L̃:

2
X
1X
L̃(w) :=
dθ (s)
π(s, a, θ) fw (s, a) − (qθ (s, a) − b(s, a)) .
2 s
a

Intuitively, L is minimized by weights, w, that cause fw (s, a) to approximate the state-action value function, qθ (s, a), while
L̃ is minimized by weights that cause fw (s, a) to approximate the residual error after the baseline is subtracted from the
state-action value function. Let


∂
?
nθ
w
e ∈ w∈R :
L̃(w) = 0 .
∂w
In Theorem 1 we show that using an action-dependent baseline does not introduce bias if the compatible function approximator
is trained to estimate the residual rather than the state-action value function, i.e., if we use w
e? rather than w? :

Theorem 1 (Policy gradient theorem with function approximation and action-dependent baseline). For any action-dependent
baseline, b : S × A → R,

∂
X
X
∇ρ(θ) =
dθ (s)
π(s, a, θ) fwe? (s, a) + b(s, a)
ln(π(s, a, θ)).
∂θ
s
a
Proof. By the definition of w
e? we have that:
X

dθ (s)

s

X

dθ (s)

s

X
a

X
a

∂
L̃(w
e? ) = 0
∂w
e?


 ∂
π(s, a, θ) fwe? (s, a) − (qθ (s, a) − b(s, a))
fwe? (s, a) = 0
e? {z
|∂ w
}
∂
= ∂θ
ln(π(s,a,θ))


∂
X
X
∂
π(s, a, θ) fwe? (s, a) + b(s, a)
ln(π(s, a, θ)) =
dθ (s)
π(s, a, θ)qθ (s, a) ln(π(s, a, θ)) .
∂θ
∂θ
s
a
|
{z
}
=∇ρ(θ)

4

Discussion

Theorem 1 has interesting ramifications—it suggests several new policy gradient algorithms. First, one might define b(s, a)
to be an estimate of qθ (s, a) constructed from an approximate MDP model, for example, one built from expert knowledge.
Alternatively, one might estimate b(s, a) from data. In this latter setting, one might parameterize b by a vector, x, and tune
x to make bx approximate qθ . This could be done prior to approximating w
e? , or could be done simultaneously by viewing
q̂w,x (s, a) := fw (s, a) + bx (s, a) as a new function approximator with parameter vector (w| , x| )| , and searching for weights
that make q̂w,x approximate qθ .

Acknowledgements
The research reported here was supported in part by a NSF CAREER grant and the Institute of Education Sciences, U.S.
Department of Education, through Grant R305A130215 to Carnegie Mellon University. The opinions expressed are those of
the authors and do not represent views of the Institute or the U.S. Dept. of Education or NSF.

References
J. Baxter and P. L. Bartlett. Direct gradient-based reinforcement learning: I. gradient estimation algorithms. Technical
report, Research School of Information Sciences and Engineering, Australian National University, 1999.
R. S. Sutton, D. McAllester, S. Singh, and Y. Mansour. Policy gradient methods for reinforcement learning with function
approximation. In Advances in Neural Information Processing Systems 12, pages 1057–1063, 2000.
P. S. Thomas and B. Okal. A notation for Markov decision processes. arXiv preprint arXiv:1512.09075v2, 2015.
2

