Batch Policy Learning under Constraints

Hoang M. Le

Cameron Voloshin

Yisong Yue

Abstract

When learning policies for real-world domains,

two important questions arise: (i) how to effi-

ciently use pre-collected off-policy, non-optimal

behavior data; and (ii) how to mediate among dif-

ferent competing objectives and constraints. We

thus study the problem of batch policy learning un-

der multiple constraints, and offer a systematic so-

lution. We first propose a flexible meta-algorithm

that admits any batch reinforcement learning and

online learning procedure as subroutines. We then

present a specific algorithmic instantiation and

provide performance guarantees for the main ob-

jective and all constraints. As part of off-policy

learning, we propose a simple method for off-

policy policy evaluation (OPE) and derive PAC-

style bounds. Our algorithm achieves strong em-

pirical results in different domains, including in a

challenging problem of simulated car driving sub-

ject to multiple constraints such as lane keeping

and smooth driving. We also show experimentally

that our OPE method outperforms other popular

OPE techniques on a standalone basis, especially

in a high-dimensional setting.

1. Introduction

We study the problem of policy learning under multiple con-

straints. Contemporary approaches to learning sequential

decision making policies have largely focused on optimizing

some cost objective that is easily reducible to a scalar value

function. However, in many real-world domains, choosing

the right cost function to optimize is often not a straight-

forward task. Frequently, the agent designer faces multiple

competing objectives. For instance, consider the aspirational

task of designing autonomous vehicle controllers: one may

care about minimizing the travel time while making sure

the driving behavior is safe, consistent, or fuel efficient. In-

California Institute of Technology, Pasadena, CA. Correspon-

dence to: Hoang M. Le

hmle@caltech.edu

Proceedings of the

36

International Conference on Machine

Learning

, Long Beach, California, PMLR 97, 2019. Copyright

2019 by the author(s).

deed, many such real-world applications require the primary

objective function be augmented with an appropriate set of

constraints (Altman, 1999).

Contemporary policy learning research has largely focused

on either online reinforcement learning (RL) with a focus on

exploration, or imitation learning (IL) with a focus on learn-

ing from expert demonstrations. However, many real-world

settings already contain large amounts of pre-collected data

generated by existing policies (e.g., existing driving behav-

ior, power grid control policies, etc.). We thus study the

complementary question:

can we leverage this abundant

source of (non-optimal) behavior data in order to learn se-

quential decision making policies with provable guarantees

on both primary objective and constraint satisfaction

We thus propose and study the problem of batch policy

learning under multiple constraints. Historically, batch RL

is regarded as a subfield of approximate dynamic program-

ming (ADP) (Lange et al., 2012), where a set of transitions

sampled from the existing system is given and fixed. From

an interaction perspective, one can view many online RL

methods (e.g., DDPG (Lillicrap et al., 2016)) as running a

growing batch RL subroutine per round of online RL. In

that sense, batch policy learning is complementary to any

exploration scheme. To the best of our knowledge, the study

of constrained policy learning in the batch setting is novel.

We present an algorithmic framework for learning sequential

decision making policies from off-policy data. We employ

multiple learning reductions to online and supervised learn-

ing, and present an analysis that relates performance in the

reduced procedures to the overall performance with respect

to both the primary objective and constraint satisfaction.

Constrained optimization is a well studied problem in su-

pervised machine learning and optimization. In fact, our ap-

proach is inspired by the work of Agarwal et al. (2018) in the

context of fair classification. In contrast to supervised learn-

ing for classification, batch policy learning for sequential

decision making introduces multiple additional challenges.

First, setting aside the constraints, batch policy learning

itself presents a layer of difficulty, and the analysis is signif-

icantly more complicated. Second, verifying whether the

constraints are satisfied is no longer as straightforward as

passing the training data through the learned classifier. In

sequential decision making, certifying constraint satisfac-

Batch Policy Learning under Constraints

tion amounts to an off-policy policy evaluation problem,

which is a challenging problem and the subject of active

research. In this paper, we develop a systematic approach

to address these challenges, provide a careful error analysis,

and experimentally validate our proposed algorithms. In

summary, our contributions are:

•

We formulate the problem of batch policy learning un-

der multiple constraints, and present the first approach

of its kind to solve this problem. The definition of con-

straints is general and can subsume many objectives.

Our approach utilizes multi-level learning reductions,

and we show how to instantiate it using various batch

RL and online learning subroutines. We show that

guarantees from the subroutines provably lift to pro-

vide end-to-end guarantees on the original constrained

batch policy learning problem.

•

While leveraging techniques from batch RL as a sub-

routine, we provide a refined theoretical analysis for

general non-linear function approximation that im-

proves upon the previously known sample complexity

result (Munos & Szepesv

ari, 2008).

•

To evaluate off-policy learning performance and con-

straint satisfaction, we propose a simple new technique

for off-policy policy evaluation (OPE), which is used

as a subroutine in our main algorithm. We show that it

is competitive to other OPE methods.

•

We validate our algorithm and analysis with two ex-

perimental settings. First, a simple navigation do-

main where we consider safety constraint. Second, we

consider a high-dimensional racing car domain with

smooth driving and lane centering constraints.

2. Problem Formulation

We first introduce notation. Let

⊂

be a bounded and

closed

-dimensional state space. Let

be a finite action

space. Let

: X

7→

]

be the primary objective cost

function that is bounded by

. Let there be

constraint

cost functions,

: X

7→

]

, each bounded by

. To simplify the notation, we view the set of constraints

as a vector function

: X

7→

]

where

(

x,a

)

is the column vector of individual

(

x,a

)

. Let

(

·|

x,a

)

denote the (unknown) transition/dynamics model that maps

state/action pairs to a distribution over the next state. Let

∈

denote the discount factor. Let

be the initial

states distribution.

We consider the discounted infinite horizon setting. An

MDP is defined using the tuple

,c,g,p,γ,χ

)

. A pol-

icy

∈

maps states to actions, i.e.,

(

)

∈

. The

value function

: X

7→

corresponding to the pri-

mary cost function

is defined in the usual way:

(

) =

[

∑

∞

(

)

]

, over the randomness of the

policy

and transition dynamics

. We similarly define the

vector-value function for the constraint costs

: X

7→

(

) =

[

∑

∞

(

)

]

. Define

(

)

and

(

)

as the expectation of

(

)

and

(

)

, respec-

tively, over the distribution

of initial states.

2.1. Batch Policy Learning under Constraints

In batch policy learning, we have a pre-collected dataset,

D =

{

(

′

(

)

(

)

}

, generated

from (a set of) historical behavioral policies denoted jointly

. The goal of batch policy learning under constraints is

to learn a policy

∈

from

that minimizes the primary

objective cost while satisfying

different constraints:

min

∈

(

)

s.t.

(

)

≤

(OPT)

where

(

) = [

(

)

,...,g

(

)]

and

∈

is a vector

of known constants. We assume that

(OPT)

is feasible.

However, the dataset

might be generated from multiple

policies that violate the constraints.

2.2. Examples of Policy Learning with Constraints

Counterfactual & Safe Policy Learning.

In conventional

online RL, the agent needs to “re-learn” from scratch when

the cost function is modified. Our framework enables coun-

terfactual policy learning assuming the ability to compute

the new cost objective from the same historical data. A

simple example is

safe

policy learning (Garcıa & Fern

andez,

2015). Define safety cost

(

x,a

) =

(

x,a,c

)

as a new

function of existing cost

and features associated with cur-

rent state-action pair. The goal here is to counterfactually

avoid undesirable behaviors observed from historical data.

We experimentally study this safety problem in Section 5.

Other examples from the literature that belong to this safety

perspective include planning under chance constraints (Ono

et al., 2015; Blackmore et al., 2011). The constraint here is

(

) =

[

(

∈

error

)] = P(

∈

error

)

≤

Multi-objective Batch Learning.

Traditional policy learn-

ing (RL or IL) presupposes that the agent optimizes a single

cost function. In reality, we may want to satisfy multiple

objectives that are not easily reducible to a scalar objective

function. One example is learning fast driving policies un-

der multiple behavioral constraints such as smooth driving

and lane keeping consistency (see Section 5).

2.3. Equivalence between Constraint Satisfaction and

Regularization

Our constrained policy learning framework accommodates

several existing regularized policy learning settings. Regu-

larization typically encodes prior knowledge, and has been

used extensively in the RL and IL literature to improve

Batch Policy Learning under Constraints

learning performance. Many instances of regularized policy

learning can be naturally cast into (OPT):

•

Entropy regularized RL

(Haarnoja et al., 2017; Ziebart,

2010) maps to policy-dependent constraint cost

(

) =

(

·|

)

, where

measures conditional entropy.

•

Conservative policy improvement

(Levine & Abbeel,

2014; Schulman et al., 2015; Achiam et al., 2017) is

equivalent to

(

) =

(

π,π

)

, where

is some

“well-behaving” policy.

•

Smooth imitation learning

(Le et al., 2016) is equiva-

lent to

(

) = min

∈

∆(

h,π

)

, where

is a class of

provably smooth policies and

∆

is a divergence metric.

•

Regularizing RL with expert demonstration

(Hes-

ter et al., 2018) is equivalent to

(

)

[

(

)

,π

∗

(

))]

, where

∗

is the expert policy.

We provide further equivalence derivation of the above

examples in Appendix A. Of course, some problems are

more naturally described using the regularization perspec-

tive, while others using constraint satisfaction.

More generally, one can establish the equivalence between

regularized and constrained policy learning via a simple

appeal to Lagrangian duality as shown in Proposition 2.1

below. This Lagrangian duality also has a game-theoretic

interpretation (Section 5.4 of Boyd & Vandenberghe (2004)),

which serves as an inspiration for developing our approach.

Proposition 2.1.

Let

be a convex set of policies. Let

: Π

7→

: Π

7→

be value functions. Consider the

two policy optimization tasks:

Regularization:

min

∈

(

) +

(

)

Constraint:

min

∈

(

)

s.t.

(

)

≤

Assume that the Slater’s condition is satisfied in the

Constraint

problem (i.e.,

∃

s.t.

(

)

< τ

). As-

sume also that the constraint cannot be removed with-

out changing the optimal solution, i.e.,

inf

∈

(

)

inf

∈

Π:

(

)

≤

(

)

. Then

∀

λ >

∃

, and vice versa,

such that

Regularization

and

Constraint

the same optimal solutions. (Proof in Appendix A.)

3. Proposed Approach

To make use of strong duality, we first

convexify

the policy

class

by allowing stochastic combinations of policies,

which effectively expands

into its convex hull

Conv

(Π)

Formally,

Conv

(Π)

contains

randomized policies

, which

we denote

∑

for

∈

and

∑

= 1

Executing a mixed

consists of first sampling

one

policy

from

according to distribution

, and then exe-

Constraint value function

(

)

can be viewed as the expec-

tation over discounted state visitation distribution. The lack of

explicit discount rate does not intefere with our overall approach.

Algorithm 1

Meta-algo for Batch Constrained Learning

for

each round

←

Best-response

(

)

←

∑

′

←

∑

′

max

= max

(

,λ

)

min

(

Best-response

(

)

max

−

min

≤

then

Return

end if

←

Online-algorithm

(

,...,π

−

,π

)

10:

end for

cuting

. Note that we still have

[

] =

∑

[

]

for

any first-moment statistic of interest (e.g., state distribution,

expected cost). It is easy to see that the augmented version

(OPT)

over

Conv

(Π)

has a solution at least as good as

the original

(OPT)

. As such, to lighten the notation, we will

equate

with its convex hull for the rest of the paper.

3.1. Meta-Algorithm

The Lagrangian of

(OPT)

(

π,λ

) =

(

) +

(

)

−

)

for

∈

. Clearly

(OPT)

is equivalent to the min-max

problem:

min

∈

max

∈

R

(

π,λ

)

. We assume

(OPT)

is feasible

and that Slater’s condition holds (otherwise, we can simply

increase the constraint

by a tiny amount). Slater’s con-

dition and policy class convexification ensure that strong

duality holds (Boyd & Vandenberghe, 2004), and

(OPT)

also equivalent to the max-min problem:

max

∈

R

min

∈

(

π,λ

)

Since

(

π,λ

)

is linear in both

and

(due to stochastic

mixture

) , strong duality is also a consequence of von

Neumann’s celebrated convex-concave minimax theorem

for zero-sum games (Von Neumann & Morgenstern, 2007).

From a game-thoeretic perspective, the problem becomes

finding the equilibrium of a two-player game between the

−

player and the

−

player (Freund & Schapire, 1999). In

this repeated game, the

−

player minimizes

(

π,λ

)

given

the current

, and the

−

player maximizes it given the

current (mixture over)

We first present a meta-algorithm (Algorithm 1) that uses

any no-regret online learning algorithm (for

) and batch

policy optimization (for

). At each iteration, given

, the

-player runs

Best-response

to get the best response:

Best-response

(

) = arg min

∈

(

π,λ

)

= arg min

∈

(

) +

(

)

−

)

This is equivalent to a standard batch reinforcement learn-

ing problem where we learn a policy that is optimal with

respect to

. The corresponding mixed strategy is the

uniform distribution over all previous

. In response to the

This places no restrictions on the individual policies. Individ-

ual policy can be non-linear and cost function can be non-convex.

Batch Policy Learning under Constraints

Algorithm 2

Constrained Batch Policy Learning

Input:

Dataset

D =

{

′

}

∼

. Online algo-

rithm parameters:

norm bound

, learning rate

1: Initialize

= (

,...,

)

∈

for

each round

Learn

←

FQI

(

)

FQI with cost

Evaluate

(

)

←

FQE

(

)

Algo 3 with

, cost

Evaluate

(

)

←

FQE

(

)

Algo 3 with

, cost

←

∑

′

(

)

←

∑

′

(

′

)

(

)

←

∑

′

(

′

)

←

∑

′

Learn

←

FQI

(

)

FQI with cost

10:

Evaluate

(

)

←

FQE

(

π,c

)

(

)

←

FQE

(

π,g

)

11:

max

= max

λ,

‖

(

) +

[

(

)

−

)

]

)

12:

min

(

) +

[

(

)

−

)

]

13:

max

−

min

≤

then

14:

Return

15:

end if

16:

Set

[

(

)

−

)

]

∈

17:

[

] =

[

]

−

ηz

[

]

∑

[

]

−

ηz

[

]

∀

[

]

the

coordinate

18:

end for

−

player, the

−

player employs

Online-algorithm

which can be

any

no-regret algorithm that satisfies:

∑

(

,λ

)

≥

max

∑

(

,λ

)

−

(

)

Finally, the algorithm terminates when the estimated primal-

dual gap is below a threshold

(Lines 7-8).

Leaving aside (for the moment) issues of generalization,

Algorithm 1 is guaranteed to converge assuming: (i)

Best-response

gives the best single policy in the class,

and (ii)

max

and

min

can be evaluated exactly.

Proposition 3.1.

Assuming (i) and (ii) above, Algorithm 1

is guaranteed to stop and the convergence depends on the

regret of

Online-algorithm

. (Proof in Appendix B.)

3.2. Specific Instantiation of Meta-Algorithm

We now focus on a specific instantiation of Algorithm 1.

Algorithm 2 is our main algorithm in this paper.

Policy Learning.

We instantiate

Best-response

with

Fitted Q Iteration (FQI), a model-free off-policy learning

approach (Ernst et al., 2005). FQI relies on a series of

reductions to supervised learning. The key idea is to ap-

proximate the true action-value function

∗

by a sequence

{

∈

}

, where

is a chosen function class.

In Lines 3 & 9,

FQI

(

)

is defined as follows. With

randomly initialized, for each

= 1

,...,K

, we form a

new training dataset

{

(

)

}

where:

∀

= (

) +

min

−

(

′

)

and

(

′

)

∼

(original dataset). A supervised

Algorithm 3

Fitted Q Evaluation:

FQE

(

π,c

)

Input:

Dataset

D =

{

′

}

∼

. Function class

Policy

to be evaluated

1: Initialize

∈

randomly

for

= 1

,...,K

Compute target

γQ

−

(

′

,π

(

′

))

∀

Build training set

{

(

)

}

Solve a supervised learning problem:

= arg min

∈

∑

(

)

−

)

end for

Output:

(

) =

(

x,π

(

))

∀

regression procedure is called to solve for:

= arg min

∈

∑

(

)

−

)

FQI returns the policy:

= arg min

(

)

. FQI has

been shown to work well with several empirical domains:

spoken dialogue systems (Pietquin et al., 2011), physical

robotic soccer (Riedmiller et al., 2009), and cart-pole swing-

up (Riedmiller, 2005), and clinical treatment (Prasad et al.,

2017). Another possible model-free subroutine is Least-

Squares Policy Iteration (LSPI) (Lagoudakis & Parr, 2003).

One can also consider model-based alternatives (Ormoneit

& Sen, 2002).

Off-policy Policy Evaluation.

A crucial difference be-

tween constrained policy learning and existing work on

constrained supervised learning is the technical challenge

of evaluating the objective and constraints. First, esti-

mating

(

π,λ

)

(Lines 11-12) requires estimating

(

)

and

(

)

Second, any gradient-based approach to

Online-learning

requires passing in

(

)

−

as part

of gradient estimate (line 15). This problem is known as

the off-policy policy evaluation (OPE) problem: we need to

evaluate

(

)

and

(

)

having only access to data

∼

There are three main contemporary approaches to OPE:

(i) importance weighting (IS) (Precup et al., 2000; 2001),

which is unbiased but often has high-variance; (ii)

regression-based direct methods (DM), which are typically

model-based (Thomas & Brunskill, 2016),and can be biased

but have much lower variance than IS; and (iii) doubly-

robust techniques (Jiang & Li, 2016; Dud

ık et al., 2011),

which combine IS and DM.

We propose a simple model-free technique using function

approximation, called Fitted Q Evaluation (FQE). FQE is

based on an iterative reductions scheme similar to FQI,

but for the problem of off-policy evaluation. Algorithm 3

lays out the steps. The key difference with FQI is that the

min

operator is replaced by

−

(

′

,π

(

′

))

(Line 3 of

Algorithm 3). Each

′

comes from the original

. Since we

know

(

′

)

, each

is well-defined. Note that FQE can be

plugged-in as a direct method if one wishes to augment the

policy evaluation with a doubly-robust technique.

Batch Policy Learning under Constraints

Online Learning Subroutine.

(

,λ

)

is linear in

many online convex optimization approaches can be used

for

Online-algorithm

. Perhaps the simpliest choice

is Online Gradient Descent (OGD) (Zinkevich, 2003). We

include an instantiation using OGD in Appendix G.

For our main Algorithm 2, similar to (Agarwal et al., 2018),

we use Exponentiated Gradient (EG) (Kivinen & Warmuth,

1997), which has a regret bound of

(

√

log(

)

instead

(

√

)

as in OGD. One can view EG as a variant of

Online Mirror Descent (Nemirovsky & Yudin, 1983) with a

softmax link function, or of Follow-the-Regularized-Leader

with entropy regularization (Shalev-Shwartz et al., 2012).

Gradient-based algorithms generally require bounded

. We

thus force

‖

≤

using hyperparameter

. Solving

(OPT)

exactly requires

∞

. We will analyze Algorithm

2 with respect to finite

. With some abuse of notation, we

augment

into a

(

+1)

−

dimensional vector by appending

− ‖

‖

, and augment the constraint cost vector

appending

(Lines 11, 12 & 15 of Algorithm 2).

4. Theoretical Analysis

4.1. Convergence Guarantee

The convergence rate of Algorithm 2 depends on the radius

of the dual variables

, the maximal constraint value

and the number of constraints

. In particular, we can show

(

)

convergence for primal-dual gap

Theorem 4.1

(Convergence of Algorithm 2)

After

itera-

tions, the empirical duality gap is bounded by

max

−

min

≤

log(

+ 1)

ηT

+ 2

ηB

Consequently, to achieve the primal-dual gap of

, setting

will ensure that Algorithm 2 converges after

log(

+1)

iterations. (Proof in Appendix B.)

Convergence analysis of our main Algorithm 2 is an exten-

sion of the proof to Proposition 3.1, leveraging the no-regret

property of the EG procedure (Shalev-Shwartz et al., 2012).

4.2. Generalization Guarantee of FQE and FQI

In this section, we provide sample complexity analysis

for FQE and FQI as

standalone

procedures for off-policy

evaluation and off-policy learning. We use the notion of

pseudo-dimension as capacity measure of non-linear func-

tion class

(Friedman et al., 2001). Pseudo-dimension

dim

, which naturally extends VC dimension into the re-

gression setting, is defined as the VC dimension of the

function class induced by the sub-level set of functions of

dim

VC-dim

(

{

(

x,y

)

7→

sign

(

)

−

) :

∈

}

)

Pseudo-dimension is finite for a large class of function ap-

The

(

+ 1)

coordinate of

is thus always satisfied. This

augmentation is only necessary when executing EG.

proximators. For example, Bartlett et al. (2017) bounded the

pseudo-dimension of piece-wise linear deep neural networks

(e.g., with ReLU activations) as

(

log

)

, where

is the number of weights, and

is the number of layers.

Both FQI and FQE rely on reductions to supervised learning

to update the value functions. In both cases, the learned

policy and evaluation policy induces a different state-action

distribution compared to the data generating distribution

We use the notion of concentration coefficient for the worst

case, proposed by (Munos, 2003), to measure the degree of

distribution shift. The following standard assumption from

analysis of related ADP algorithms limits the severity of

distribution shift over future time steps:

Assumption 1

(Concentrability coefficient of future

state-action distribution)

(Munos, 2003; 2007; Munos &

Szepesv

ari, 2008; Antos et al., 2008a;b; Lazaric et al., 2010;

2012; Farahmand et al., 2009; Maillard et al., 2010)

Let

be the operator acting on

: X

7→

s.t.

(

)(

x,a

) =

∫

(

′

,π

(

′

))

(

′

x,a

)

. Given data gen-

erating distribution

, initial state distribution

, for

≥

and an arbitrary sequence of stationary policies

{

}

≥

define the concentration coeffient:

(

) =

sup

,...,π

∥

(

χP

...P

)

dμ

∥

∞

We assume

= (1

−

)

∑

≥

mγ

−

(

)

∞

This assumption is valid for a fairly large class of MDPs

(Munos, 2007). For instance

is finite for any finite MDP,

or any infinite state-space MDP with bounded transition

density.

Having a finite concentration coefficient is equiva-

lent the top-Lyapunov exponent

≤

(Bougerol & Picard,

1992), which means the underlying stochastic system is

stable. We show below a simple sufficient condition for

Assumption 1 (albeit stronger than necessary).

Example 4.1.

Consider an MDP such that for any non-

stationary distribution

, the marginals over states satisfy

(

)

(

)

≤

(i.e., transition dynamics are sufficiently stochas-

tic), and

∃

∀

x,a

(

)

(i.e., the behavior

policy is sufficiently exploratory). Then

≤

Recall that for a given policy

, the Bellman (evalua-

tion) operator is defined as

(

)(

x,a

) =

(

x,a

) +

∫

(

′

,π

(

′

))

(

′

x,a

)

. In general

may not be-

long to

for

∈

. For FQE (and FQI), the main operation

in the algorithm is to iteratively project

−

back to

via

= arg min

∈

‖

−

‖

. The performance

This assumption ensures sufficient data diversity, even when

the executing policy is deterministic. An example of how learning

can fail without this assumption is based on the “combination lock”

MDP (Koenig & Simmons, 1996). In this deterministic MDP

example,

can grow arbitrarily large, and we need an exponential

number of samples for both FQE and FQI. See Appendix D.

Batch Policy Learning under Constraints

of both FQE and FQI thus depend on how well the function

class

approximates the Bellman operator. We measure

the ability of function class

to approximate the Bellman

evaluation operator via the worst-case Bellman error:

Definition 4.1

(inherent Bellman evaluation error)

Given

a function class

and policy

, the

inherent Bell-

man evaluation error

is defined as

sup

∈

inf

∈

‖

−

‖

where

‖·‖

is the

norm

weighted by the state-action distribution induced by

We are now ready to state the generalization bound for FQE:

Theorem 4.2

(Generalization error of FQE)

Under As-

sumption 1, for

∈

, after

iterations of

Fitted Q Evaluation (Algorithm 3), for

(

(log

dim

log

+log

dim

)

, we have with probability

−

∣

(

)

−

(

)

∣

≤

−

)

(

√

) +

−

)

This result shows a dependency on

(

)

, compared

(

)

from other related ADP algorithms (Munos &

Szepesv

ari, 2008; Antos et al., 2008b). The price that we pay

is a multiplicative constant 2 in front of the inherent error

The error from second term on RHS decays exponentially

with iterations

. The proof is in Appendix E.

We can show an analogous generalization bound for FQI.

While FQI has been widely used, to the best of our knowl-

edge, a complete analysis of FQI for non-linear function

approximation has not been previously reported.

Definition 4.2

(inherent Bellman optimality error)

(Munos

& Szepesv

ari, 2008) Recall that the Bellman optimal-

ity operator is defined as

(

)(

x,a

) =

(

x,a

) +

∫

min

′

∈

(

′

)

(

′

x,a

)

. Given a function class

, the

inherent Bellman error

is defined as

sup

∈

inf

∈

‖

−

‖

, where

‖·‖

is the

norm

weighted by

, the state-action distribution induced by

Theorem 4.3

(Generalization error of FQI)

Under Assump-

tion 1, for

∈

, after

iterations of Fit-

ted Q Iteration, for

(

(log

dim

log

dim

)

, we have with probability

−

∣

∗

−

(

)

∣

≤

−

)

(

√

) + 2

)

where

is the policy acting greedy with respect to the

returned function

. (Proof in Appendix F.)

4.3. End-to-End Generalization Guarantee

We are ultimately interested in the test-time performance

and constraint satisfaction of the returned policy from Al-

FQI for continuous action space from (Antos et al., 2008a)

is a variant of fitted policy iteration and not the version of FQI

under consideration. The appendix of (Lazaric & Restelli, 2011)

contains a proof of FQI specifically for linear function class.

gorithm 2. We now connect the previous analyses from

Theorems 4.1, 4.2 & 4.3 into an end-to-end error analysis.

Since Algorithm 2 uses FQI and FQE as subroutines, the

inherent Bellman error terms

and

will enter our over-

all performance bound. Estimating the inherent Bellman

error caused by function approximation is not possible in

general (chapter 11 of Sutton & Barto (2018)). We assume

existence of a sufficiently expressive

that can generally

make

and

arbitrarily small. To simplify our end-to-

end analysis, consider

= 0

and

= 0

, i.e., the function

class

is closed under applying the Bellman operator.

Assumption 2

(Bellman operator realizability)

We con-

sider function classes

sufficiently rich so that

∀

∈

for the policies

returned by Algorithm 2.

With Assumptions 1 & 2, we have the following error bound:

Theorem 4.4

(Generalization guarantee of Algorithm 2)

Let

∗

be the optimal policy to

(OPT)

. Denote

Let

be the number of iterations of FQE and FQI. Let

be the policy returned by Algorithm 2, with termina-

tion threshold

. For

∈

, when

(

(log

(

+1)

dim

log

+ log

dim

)

, we have

with probability at least

−

(

)

≤

(

∗

) +

(4 +

)

−

)

(

√

+ 2

)

and

(

)

≤

+ 2

−

)

(

√

−

)

The proof is in Appendix C. This result guarantees that,

upon termination of Algorithm 2, the true performance on

the main objective can be arbitrarily close to that of the

optimal policy. At the same time, each constraint will be

approximately satisfied with high probability, assuming suf-

ficiently large

, and sufficiently small

5. Empirical Analysis

We perform experiments on two different domains: a grid-

world domain (from OpenAI’s FrozenLake) under a safety

constraint, and a challenging high-dimensional car racing

domain (from OpenAI’s CarRacing) under multiple behav-

ior constraints. We seek to answer the following questions

in our experiments: (i) whether the empirical convergence

behavior of Algorithm 2 is consistent with our theory; and

(ii) how the returned policy performs with respect to the

main objective and constraint satisfaction. Appendix H

includes a more detailed discussion of our experiments.

5.1. Frozen Lake.

Environment & Data Collection.

The environment is an

8x8 grid. The agent has 4 actions N,S,E,W at each state.

The main goal is to navigate from a starting position to

Batch Policy Learning under Constraints

the goal. Each episode terminates when the agent reaches

the goal or falls into a hole. The main cost function is

defined as

−

if goal is reached, otherwise

= 0

everywhere. We simulate a non-optimal data gathering

policy

by adding random sub-optimal actions to the

shortest path policy from any given state to goal. We run

for 5000 trajectories to collect the behavior dataset

(with constraint cost measurement specified below).

Counterfactual Safety Constraint.

We augment the main

objective

with safety constraint cost defined as

= 1

if the agent steps into a hole, and

= 0

otherwise. We

set the constraint threshold

= 0

, roughly

75%

of the

accumulated constraint cost of behavior policy

. The

threshold can be interpreted as a counterfactually acceptable

probability that we allow the learned policy to fail.

Results.

The empirical primal dual gap

max

−

min

Figure 1 (left) quickly decreases toward the optimal gap

of zero. The convergence is fast and monotonic, support-

ing the predicted behavior from our theory. The test-time

performance in Figure 1 (middle) shows the safety con-

straint is always satisfied, while the main objective cost also

smoothly converges to the optimal value achieved by an

online RL baseline (DQN) trained without regard to the

constraint. The returned policy significantly outperformed

the data gathering policy

on both main and safety cost.

5.2. Car Racing.

Environment & Data Collection.

The car racing environ-

ment (OpenAI), is a high-dimensional domain where the

state is a

tensor of raw pixels. The action

space

A =

{

steering

gas

brake

}

takes 12 discretized

values. The goal in this episodic task is to traverse over

95%

of the track, measured by a given number of “tiles” as a

proxy for distance coverage. The agent receives a reward

(negative cost) for each unique tile crossed and no reward if

the agent is off-track. A small positive cost applies at every

time step, with maximum horizon of 1000 for each episode.

With these costs given by the environment, one can train

online RL agent using DDQN (Van Hasselt et al., 2016). We

collect

≈

5000

trajectories from DDQN’s randomization,

resulting in data set

with

≈

94000

transition tuples.

Fast Driving under Behavioral Constraints.

We study

the problem of minimizing environment cost while subject

to two behavioral constraints: smooth driving and lane cen-

tering. The first constraint

approximates smooth driving

(

x,a

) = 1

contains braking action, and

other-

wise. The second constraint cost

measures the distance

between the agent and center of lane at each time step. This

is a highly challenging setup since three objectives and con-

straints are in direct conflict with one another, e.g., fast

driving encourages the agent to cut corners and apply fre-

quent brakes to make turns. Outside of this work, we are not

aware of previous work in policy learning with 2 or more

constraints in high-dimensional settings.

Baseline and Procedure.

As a na

ıve baseline, DDQN

achieves low cost, but exhibits “non-smooth” driving behav-

ior (see our supplementary videos). We set the threshold for

each constraint to 75% of the DDQN benchmark. We also

compare against regularized batch RL algorithms (Farah-

mand et al., 2009), specifically regularized LSPI. We in-

stantiate our subroutines, FQE and FQI, with multi-layered

CNNs. We augment LSPI’s linear policy with non-linear

features derived from a well-performing FQI model.

Results.

The returned mixture policy from our algorithm

achieves low main objective cost, comparable with online

RL policy trained without regard to constraints. After sev-

eral initial iterations violating the braking constraint, the

returned policy - corresponding to the appropriate

trade-

off - satisties both constraints, while improving the main

objective. The improvement over data gathering policy is

significant for both constraints and main objective.

Regularized policy learning is an alternative approach to

(OPT)

(section 2). We provide the regularized LSPI base-

line the same set of

found by our algorithm for one-shot

regularized learning (Figures 2 (left & middle)). While

regularized LSPI obtains good performance for the main ob-

jective, it does not achieve acceptable constraint satisfaction.

By default, regularized policy learning requires parameter

tuning heuristics. In principle, one can perform a grid-search

over a range of parameters to find the right combination - we

include such an example for both regularized LSPI and FQI

in Appendix H. However, since our objective and constraints

are in conflict, main objective and constraint satisfaction

of policies returned by one-shot regularized learning are

sensitive to step changes in

. In constrast, our approach is

systematic, and is able to avoid the curse-of-dimensionality

of brute-force search that comes with multiple constraints.

In practice, one may wish to deterministically extract a

single policy from the returned mixture for execution. A

de-randomized policy can be obtained naturally from our

algorithm by selecting the best policy from the existing

FQE’s estimates of individual

Best-response

policies.

5.3. Off-Policy Evaluation

The off-policy evaluation by FQE is critical for updating

policies in our algorithm, and is ultimately responsible for

certifying constraint satisfaction. While other OPE meth-

ods can also be used in place of FQE, we find that the

estimates from popular methods are not sufficiently accu-

rate in a high-dimensional setting. As a standalone com-

parison, we select an individual policy and compare FQE

against PDIS (Precup et al., 2000), DR (Jiang & Li, 2016)

and WDR (Thomas & Brunskill, 2016) with respect to the

constraint cost evaluation. To compare both accuracy and