# BRPO: Batch Residual Policy Optimization

Sungryull Sohn111Equal contribution,1,2 Yinlam Chow∗,1 Jayden Ooi∗,1
Ofir Nachum1 Honglak Lee1,2 Ed Chi1&Craig Boutilier1 1Google Research
2University of Michigan<EMAIL_ADDRESS>{yinlamchow, jayden, ofirnachum,
honglak, edchi<EMAIL_ADDRESS>
###### Abstract

In batch reinforcement learning (RL), one often constrains a learned policy to
be close to the behavior (data-generating) policy, e.g., by constraining the
learned action distribution to differ from the behavior policy by some maximum
degree that is the _same at each state_. This can cause batch RL to be overly
conservative, unable to exploit large policy changes at frequently-visited,
high-confidence states without risking poor performance at sparsely-visited
states. To remedy this, we propose _residual policies_ , where the allowable
deviation of the learned policy is _state-action-dependent_. We derive a new
for RL method, BRPO, which learns both the policy and allowable deviation that
jointly maximize a lower bound on policy performance. We show that BRPO
achieves the state-of-the-art performance in a number of tasks.

##  1 Introduction

Deep reinforcement learning (RL) methods are increasingly successful in
domains such as games (Mnih et al., 2013), recommender systems (Gauci et al.,
2018), and robotic manipulation (Nachum et al., 2019). Much of this success
relies on the ability to collect new data through _online_ interactions with
the environment during training, often relying on simulation. Unfortunately,
this approach is impractical in many real-world applications where faithful
simulators are rare, and in which active data collection through interactions
with the environment is costly, time consuming, and risky.

_Batch (or offline) RL_ (Lange et al., 2012) is an emerging research direction
that aims to circumvent the need for online data collection, instead learning
a new policy using only offline trajectories generated by some behavior policy
(e.g., the currently deployed policy in some application domain). In
principle, any off-policy RL algorithm (e.g., DDPG (Lillicrap et al., 2015),
DDQN (Hasselt et al., 2016)) may be used in this batch (or more accurately,
“offline”) fashion; but in practice, such methods have been shown to fail to
learn when presented with arbitrary, static, off-policy data. This can arise
for several reasons: lack of exploration (Lange et al., 2012), generalization
error on out-of-distribution samples in value estimation (Kumar et al., 2019),
or high-variance policy gradients induced by covariate shift (Mahmood et al.,
2014).

Various techniques have been proposed to address these issues, many of which
can be interpreted as constraining or regularizing the learned policy to be
_close_ to the behavior policy (Fujimoto et al., 2018; Kumar et al., 2019)
(see further discussion below). While these batch RL methods show promise,
none provide improvement guarantees relative to the behavior policy. In
domains for which batch RL is well-suited (e.g., due to the risks of active
data collection), such guarantees can be critical to deployment of the
resulting RL policies.

In this work, we use the well-established methodology of conservative policy
improvement (CPI) (Kakade and Langford, 2002) to develop a theoretically
principled use of behavior-regularized RL in the batch setting. Specifically,
we parameterize the learned policy as a residual policy, in which a base
(behavior) policy is combined linearly with a learned candidate policy using a
mixing factor called the confidence. Such residual policies are motivated by
several practical considerations. First, one often has access to offline data
or logs generated by a deployed base policy which is known to perform
reasonably well. The offline data can be used by an RL method to learn a
candidate policy with better _predicted_ performance, but if confidence in
parts of that prediction is weak, relying on the base policy may be desirable.
The base policy may also incorporate soft business constraints or some form of
interpretability. Our residual policies blend the two in a learned, non-
uniform fashion. When deploying a new policy, we use the CPI framework to
derive updates that learn both the candidate policy and the confidence that
jointly maximize a lower bound on performance improvement relative to the
behavior policy. Crucially, while traditional applications of CPI, such as
TRPO (Schulman et al., 2015), use a constant or state-independent confidence,
our performance bounds and learning rules are based on state-action-dependent
confidences—this gives rise to bounds that are less conservative than their
CPI counterparts.

In Sec. 2, we formalize residual policies and in Sec. 3 analyze a novel
_difference-value function_. Sec. 4 holds our main result, a tighter lower
bound on policy improvement for our residual approach (vs. CPI and TRPO). We
derive the BRPO algorithm in Sec. 5 to jointly learn the candidate policy and
confidence; experiments in Sec. 6 show its effectiveness.

##  2 Preliminaries

We consider a _Markov decision process (MDP)_ $\mathcal{M}=\langle
S,A,R,T,P_{0}\rangle$, with state space $S$, action space $A$, reward function
$R$, transition kernel $T$, and initial state distribution $P_{0}$. A policy
$\pi$ interacts with the environment, starting at $s_{0}\sim P_{0}$. At step
$t$, the policy samples an action $a_{t}$ from a distribution
$\pi(\cdot|s_{t})$ over $A$ and applies. The environment emits a reward
$r_{t}=R(s_{t},a_{t})\in[0,R_{\max}]$ and next state $s_{t+1}\sim
T(\cdot|s_{t},a_{t})$. In this work, we consider discounted infinite-horizon
problems with discount factor $\gamma\in[0,1)$.

Let $\Delta=\\{\pi:S\times A\rightarrow[0,1],\;\sum_{a}\pi(a|s)=1\\}$ be the
set of Markovian stationary policies. The expected (discounted) cumulative
return of policy $\pi\in\Delta$, is
$J_{\pi}:=\mathbb{E}_{T,\pi}[\sum_{t=0}^{\infty}\gamma^{t}R(s_{t},a_{t})\mid
s_{0}\sim P_{0}]$. Our aim is to find an optimal policy
$\pi^{*}\in\operatorname*{arg\,max}_{\pi\in\Delta}\,J_{\pi}$. In reinforcement
learning (RL), we must do so without knowledge of $R,T$, using only trajectory
data generated from the environment (see below) or access to a simulator (see
above).

We consider pure offline or _batch RL_ , where the learner has access to a
fixed data set (or _batch_) of state-actions-reward-next-state samples
$B=\\{(s,a,r,s^{\prime})\\}$, generated by a (known) _behavior policy_
$\beta(\cdot|s)$. No additional data collection is permitted. We denote by
$d_{\beta}$ the $\gamma$-discounted occupation measure of the MDP w.r.t.
$\beta$.

In this work, we study the problem of _residual policy optimization (RPO)_ in
the batch setting. Given the behavior policy $\beta(a|s)$, we would like to
learn a _candidate policy_ $\rho(a|s)$ and a state-action _confidence_
$\lambda(s,a)$, such that the final _residual policy_
$\pi(a|s)=(1-\lambda(s,a))\cdot\beta(a|s)+\lambda(s,a)\cdot\rho(a|s)$
maximizes total return. As discussed above, this type of mixture allows one to
exploit an existing, “well-performing” behavior policy. Intuitively,
$\lambda(s,a)$ should capture how much we can trust $\rho$ at each $s,a$ pair,
given the available data. To ensure that the residual policy is a probability
distribution at every state $s\in S$, we constrain the confidence $\lambda$ to
lie in the set $\Lambda(s)=\left\\{\lambda:S\times
A\rightarrow[0,1]:\sum_{a}\lambda(s,a)\left(\beta(a|s)-\rho(a|s)\right)=0\right\\}.$

#### Related Work.

Similar to the above policy formulation, CPI (Kakade and Langford, 2002) also
develops a policy mixing methodology that guarantees performance improvement
when the confidence $\lambda$ is a constant. However, CPI is an online
algorithm, and it learns the candidate policy independently of (not jointly
with) the mixing factor; thus, extension of CPI to offline, batch setting is
unclear. Other existing work also deals with online residual policy learning
without jointly learning mixing factors (Johannink et al., 2019; Silver et
al., 2018). Common applications of CPI may treat $\lambda$ as a hyper-
parameter, which specifies the maximum total-variation distance between the
learned and behavior policy distributions (see standard proxies in Schulman et
al. (2015); Pirotta et al. (2013) for details).

_Batch-constrained Q-learning (BCQ)_ (Fujimoto et al., 2018, 2019)
incorporates the behavior policy when defining the admissible action set in
Q-learning for selecting the highest-valued actions that are similar to data
samples in the batch. _BEAR_ (Kumar et al., 2019) is motivated as a means to
control the accumulation of out-of-distribution value errors; but its main
algorithmic contribution is realized by adding a regularizer to the loss that
measures the kernel maximum mean discrepancy (MMD) (Gretton et al., 2007)
between the learned and behavior policies similar to KL-control (Jaques et
al., 2019). Algorithms such as SPI (Ghavamzadeh et al., 2016) and SPIBB
(Laroche and Trichelair, 2017) bootstraps the learned policy with the behavior
policy when the uncertainty in the update for current state-action pair is
high, where the uncertainty is measured by the visitation frequency of state-
action pairs in the batch data. While these methods work well in some
applications it is unclear if they have any performance guarantees.

##  3 The Difference-value Function

We begin by defining and characterizing the _difference-value function_ , a
concept we exploit in the derivation of our batch RPO method in Secs. 4 and 5.
For any $s\in S$, let $V_{\pi}(s)$ and $V_{\beta}(s)$ be the value functions
induced by policies $\pi$ and $\beta$, respectively. Using the structure of
the residual policy, we establish two characterizations of the _difference-
value function_ $\Delta V_{\pi,\beta}(s):=V_{\pi}(s)-V_{\beta}(s)$.

######  Lemma 1.

Let $A_{\pi}(s,a):=Q_{\pi}(s,a)-V_{\pi}(s)$ be the advantage function w.r.t.
residual policy $\pi$, where $Q_{\pi}$ is the state-action value. The
difference-value is $\Delta
V_{\pi,\beta}(s)\\!=\\!\mathbb{E}_{T,\beta}[\sum_{t=0}^{\infty}\gamma^{t}\Delta\hat{A}_{\pi,\beta,\rho,\lambda}(s_{t})\\!\mid\\!s_{0}=s],$
where

$\smash{\Delta\hat{A}_{\beta,\rho,\lambda}(s)=\sum_{a\in
A}\beta(a|s)\cdot\lambda(s,a)\cdot\frac{\rho(a|s)-\beta(a|s)}{\beta(a|s)}\cdot
A_{\pi}(s,a)}$

is the residual reward that depends on $\lambda$ and difference of candidate
policy $\rho$ and behavior policy $\beta$.

This result establishes that the difference value is essentially a value
function w.r.t. the residual reward. Moreover, it is proportional to the
advantage of the target policy, the confidence, and the difference of
policies. While the difference value can be estimated from behavior data batch
$B$, this formulation requires knowledge of the advantage function $A_{\pi}$
w.r.t. the target policy, which must be re-learned at every $\pi$-update in an
off-policy fashion. Fortunately, we can show that the difference value can
also be expressed as a function of the advantage w.r.t. the _behavior policy_
$\beta$:

######  Theorem 2.

Let $A_{\beta}(s,a):=Q_{\beta}(s,a)-V_{\beta}(s)$ be the advantage function
induced by $\beta$, in which $Q_{\beta}$ is the state-action value. The
difference-value is given by $\Delta
V_{\pi,\beta}(s)\\!=\\!\mathbb{E}_{T,\pi}\left[\sum_{t=0}^{\infty}\\!\gamma^{t}\Delta
A_{\beta,\rho,\lambda}(s_{t})\\!\\!\mid\\!\\!s_{0}=s\right]$, where

$\smash{\Delta A_{\beta,\rho,\lambda}(s)=\sum_{a\in
A}\beta(a|s)\cdot\lambda(a|s)\cdot\frac{\rho(a|s)-\beta(a|s)}{\beta(a|s)}\cdot
A_{\beta}(s,a)}$

is the residual reward that depends on $\lambda$ and difference of candidate
policy $\rho$ and behavior policy $\beta$.

In our RPO approach, we exploit the nature of the difference-value function to
solve the maximization w.r.t. the confidence and candidate policy:
$(\lambda^{*}(s,\cdot),\rho^{*}(\cdot|s))\\!\in\operatorname*{arg\,max}_{\lambda\in\Lambda(s),\rho\in\Delta}\Delta
V_{\pi}(s)$, $\forall s\in S$. Since $\lambda(s,\cdot)=0$ implies $\Delta
V_{\pi,\beta}(s)=0$, the optimal difference-value function $\Delta
V^{*}(s):=\max_{\lambda\in\Lambda(s),\rho\in\Delta}\Delta V_{\pi}(s)$ is
always lower-bounded by $0$. We motivate computing $(\lambda,\rho)$ with the
above difference-value formulation rather than as a standard RL problem as
follows. In the tabular case, optimizing $(\lambda,\rho)$ with either
formulation gives an identical result. However, both the difference-value
function in Theorem 2 and the standard RL objective require sampling data
generated by the updated policy $\pi$. In the batch setting, when fresh
samples are unavailable, learning $(\lambda,\rho)$ with off-policy data may
incur instability due to high generalization error (Kumar et al., 2019). While
this can be alleviated by adopting the CPI methodology, applying CPI directly
to RL can be overly conservative (Schulman et al., 2015). By contrast, we
leverage the special structure of the difference-value function (e.g., non-
negativity) below, using this new formulation together with CPI to derive a
less conservative RPO algorithm.

##  4 Batch Residual Policy Optimization

We now develop an RPO algorithm that has stable learning performance in the
batch setting and _performance improvement guarantees_. For the sake of
brevity, in the following we only present the main results on performance
guarantees of RPO. Proofs of these results can be found in the appendix of the
extended paper. We begin with the following baseline result, directly applying
Corollary 1 of the TRPO result to RPO to ensure the residual policy $\pi$
performs no worse than $\beta$.

######  Lemma 3.

For any value function $U:S\to\mathbb{R}$, the difference-return satisfies
$J_{\pi}-J_{\beta}\geq\frac{1}{1-\gamma}\widetilde{L}_{U,\beta,\rho,\lambda}-\frac{2\gamma}{(1-\gamma)^{2}}\cdot\epsilon_{U,\beta,\rho,\lambda}\cdot\mathbb{E}_{s\sim
d_{\beta}}\left[\sqrt{\frac{1}{2}D_{\mathrm{KL}}(\beta(s)\|\rho(s))}\right],$
where the surrogate objective and the penalty weight are

$\begin{split}&\widetilde{L}_{U,\beta,\rho,\lambda}\\!:=\\!\mathop{\mathbb{E}}_{(s,a,s^{\prime})\sim
d_{\beta}}\left[\lambda(s,a)\cdot\frac{\rho(a|s)-\beta(a|s)}{\beta(a|s)}\\!\cdot\\!\Delta
U(s,a,s^{\prime})\right],\\\
&\epsilon_{U,\beta,\rho,\lambda}\\!:=\\!\max_{s}\\!|\mathbb{E}_{\pi,T}[\Delta
U(s,a,s^{\prime})]|,\end{split}$

where $\Delta U(s,a,s^{\prime}):=R(s,a)+\gamma U(s^{\prime})-U(s)$.

When $U=V_{\pi}$, one has $\mathbb{E}_{a\sim\pi(s)}[\Delta
U(s,a,s^{\prime})]=0$, $\forall s\in S$, which implies that the inequality is
tight—this lemma then coincides Lemma 1. While this CPI result forms the basis
of many RL algorithms (e.g., TRPO, PPO), in many cases it is very loose since
$\epsilon_{U,\beta,\rho,\lambda}$ is a maximum over all states. Thus, using
this bound for policy optimization may be _overly conservative_ , i.e.,
algorithms which rely on this bound must take very small policy improvement
steps, especially when the penalty weight $\epsilon_{U,\beta,\rho,\lambda}$ is
large, i.e.,
$|\epsilon_{U,\beta,\rho,\lambda}/(1-\gamma)|>>|\widetilde{L}_{U,\beta,\rho,\lambda}|$.
While this approach may be reasonable in online settings—when collection of
new data (with an updated behavior policy $\beta\leftarrow\pi$) is allowed—in
the batch setting it is challenging to overcome such conservatism.

To address this issue, we develop a CPI method that is specifically tied to
the difference-value formulation, and uses a state-action-dependent confidence
$\lambda(s,a)$. We first derive the following theorem, which bounds the
difference returns that are generated by $\beta$ and $\pi$.

######  Theorem 4.

The difference return of $(\pi,\beta)$ satisfies

$J_{\pi}\\!-\\!J_{\beta}\\!\geq\\!\frac{1}{1-\gamma}\left(L^{\prime}_{\beta,\rho,\lambda}\\!-\\!\frac{\gamma}{1-\gamma}\\!\cdot\\!L^{\prime\prime}_{\beta,\rho,\lambda}\\!\cdot\\!\max_{s_{0}\in
S}\,L^{\prime\prime\prime}_{\beta,\rho,\lambda}(s_{0})\right)\\!,$

where the surrogate objective function, regularization, and penalty weight are
given by

$\begin{split}L^{\prime}_{\beta,\rho,\lambda}:=&\mathbb{E}_{(s,a)\sim
d_{\beta}}\left[\lambda(s,a)\cdot\frac{\rho(a|s)-\beta(a|s)}{\beta(a|s)}\cdot
A_{\beta}(s,a)\right]\\\
L^{\prime\prime}_{\beta,\rho,\lambda}:=&\mathbb{E}_{(s,a)\sim
d_{\beta}}\left[\lambda(s,a)\cdot\frac{|\rho(a|s)-\beta(a|s)|}{\beta(a|s)}\right]\\\
L^{\prime\prime\prime}_{\beta,\rho,\lambda}(s_{0}):=&\mathbb{E}_{(s,a)\sim
d_{\beta}(s_{0})}\\!\left[\lambda(s,a)\\!\cdot\\!\frac{|\rho(a|s)\\!-\\!\beta(a|s)|}{\beta(a|s)}\\!\cdot\\!|A_{\beta}(s,a)|\right]\end{split}$

respectively, in which $d_{\beta}(s_{0})$ is the discounted occupancy measure
w.r.t. $\beta$ given initial state $s_{0}$.

Unlike the difference-value formulations in Lemma 1 and Theorem 2, which
require the knowledge of advantage function $A_{\pi}$ or the trajectory
samples generated by $\pi$, the lower bound in Theorem 4 is comprised only of
terms that can be estimated directly using the data batch $B$ (i.e., data
generated by $\beta$). This makes it a natural objective function for batch
RL. Notice also that the surrogate objective, the regularization, and the
penalty weight in the lower bound are each proportional to the confidence and
to the relative difference of the candidate and behavior policies. However,
the $\max$ operator requires state enumeration to compute this lower bound,
which is intractable when $S$ is large or uncountable.

We address this by introducing a slack variable $\kappa\geq 0$ to replace the
$\max$-operator with suitable constraints. This allows the bound on the
difference return to be rewritten as:
$J_{\pi}-J_{\beta}\geq\frac{1}{1-\gamma}L^{\prime}_{\beta,\rho,\lambda}-\min_{\kappa\geq
L^{\prime\prime\prime}_{\beta,\rho,\lambda}(s_{0}),\,\,\forall
s_{0}}\frac{\gamma}{(1-\gamma)^{2}}L^{\prime\prime}_{\beta,\rho,\lambda}\cdot\kappa.$
Consider the Lagrangian of the lower bound:

$\begin{split}\frac{L^{\prime}_{\beta,\rho,\lambda}}{1-\gamma}-\min_{\kappa\geq
0}&\max_{\eta(s)\geq 0,\forall s}\frac{\gamma\cdot
L^{\prime\prime}_{\beta,\rho,\lambda}\cdot\kappa}{(1-\gamma)^{2}}-\sum_{s}\eta(s)(\kappa-L^{\prime\prime\prime}_{\beta,\rho,\lambda}(s)).\end{split}$

To simplify this saddle-point problem, we restrict the Lagrange multiplier to
be $\eta(s)=\eta\cdot P_{0}(s)\geq 0$, where $\eta\geq 0$ is a scalar
multiplier. Using this approximation and the strong duality of linear
programming (Boyd and Vandenberghe, 2004) over primal-dual variables
$(\kappa,\eta)$, the saddle-point problem on $(\lambda,\rho,\eta,\kappa)$ can
be re-written as

$\displaystyle\mathcal{L}_{\beta,\rho,\lambda}:=$ $\displaystyle\max_{\eta\geq
0}\min_{\kappa\geq
0}\frac{L^{\prime}_{\beta,\rho,\lambda}-L^{\prime\prime}_{\beta,\rho,\lambda}\cdot\kappa\cdot\frac{\gamma}{1-\gamma}-\eta\cdot\kappa+\eta
L^{\prime\prime\prime}_{\beta,\rho,\lambda}}{1-\gamma}$ $\displaystyle=$
$\displaystyle\frac{1}{1-\gamma}\left(L^{\prime}_{\beta,\rho,\lambda}-\frac{\gamma}{1-\gamma}L^{\prime\prime}_{\beta,\rho,\lambda}\cdot
L^{\prime\prime\prime}_{\beta,\rho,\lambda}\right),$ (1)

where $L^{\prime\prime\prime}_{\beta,\rho,\lambda}=\mathbb{E}_{s\sim
P_{0}}[L^{\prime\prime\prime}_{\beta,\rho,\lambda}(s)]$. The equality is based
on the KKT condition on $(\kappa,\eta)$. Notice that the only difference
between the CPI lower bound in Theorem 4 and the objective function
$\mathcal{L}_{\beta,\rho,\lambda}$ is that the $\max$ operator is replaced by
expectation w.r.t the initial distribution.

With certain assumptions on the approximation error of the Lagrange multiplier
parametrization $\eta(s)\approx P_{0}(s)$, we can characterize the gap between
the original CPI objective function in Theorem 4 and
$\mathcal{L}_{\beta,\rho,\lambda}$. One approach is to look into the KKT
condition of the original saddle-point problem and bound the sub-optimality
gap introduced by this Lagrange parameterization. Similar derivations can be
found in the analysis of approximate linear programming (ALP) algorithms
(Abbasi-Yadkori et al., 2019; Farias and Roy, 2003).

Compared with the vanilla CPI result from Lemma 3, there are two
characteristics in problem (1) that make the optimization w.r.t.
$\mathcal{L}_{\beta,\rho,\lambda}$ less conservative. First, the penalty
weight $L^{\prime\prime\prime}_{\beta,\rho,\lambda}$ here is smaller than
$\epsilon_{U,\beta,\rho,\lambda}$ in Lemma 3, which means that the
corresponding objective has less incentive to force $\rho$ to be close to
$\beta$. Second, compared with entropy regularization in vanilla CPI, here the
regularization and penalty weight are both linear in
$\lambda\in\Lambda\subseteq[0,1]^{|A|}$; thus, unlike vanilla CPI, whose
objective is linear in $\lambda$, our objective is quadratic in $\lambda$—this
modification ensures the optimal value is not a _degenerate extreme point_ of
$\Lambda$.222For example, when $\lambda$ is state-dependent (which
automatically satisfies the equality constraints in $\Lambda$), the linear
objective in vanilla CPI makes the optimal value $\lambda^{*}(\cdot|s)$ a _0-1
vector_. Especially when $\frac{2\gamma}{1-\gamma}\mathbb{E}_{s\sim
d_{\beta}}\left[\sqrt{\frac{1}{2}D_{\mathrm{KL}}(\beta(s)\|\rho(s))}\,\right]$
is large, then most entries of $\lambda^{*}$ become zero, i.e., $\pi$ will be
very close to $\beta$.

##  5 The BRPO Algorithm

We now develop the BRPO algorithm, for which the general pseudo-code is given
in Algorithm 1. Recall that if the candidate policy $\rho$ and confidence
$\lambda$ are jointly optimized

$(\rho^{*},\lambda^{*})\\!\in\\!\operatorname*{arg\,max}_{\lambda\in\Lambda,\,\,\rho\in\Delta}\mathcal{L}_{\beta,\rho,\lambda},$
(2)

then the residual policy
$\pi^{*}(a|s)=(1-\lambda^{*}(s,a))\beta(a|s)+\lambda^{*}(s,a)\rho^{*}(a|s)$
performs no worse than behavior policy $\beta$. Generally, solutions for
problem (2) use a form of minorization-maximization (MM) (Hunter and Lange,
2004), a class of methods that also includes expectation maximization. In the
terminology of MM algorithms, $\mathcal{L}_{\beta,\rho,\lambda}$ is a
surrogate function satisfying the following _MM properties_ :

$J_{\pi}-J_{\beta}\geq\mathcal{L}_{\beta,\rho,\lambda},\,\,\,J_{\beta}-J_{\beta}\\!=\\!\mathcal{L}_{\beta,\beta,\lambda}\\!=\\!\mathcal{L}_{\beta,\rho,0}=0,$
(3)

which guarantees that it minorizes the difference-return $J_{\pi}-J_{\beta}$
with equality at $\lambda=0$ (with arbitrary $\rho$) or at $\rho=\beta$ (with
arbitrary $\lambda$). This algorithm is also reminiscent of proximal gradient
methods. We optimize $\lambda$ and $\rho$ in RPO with a simple two-step
_coordinate-ascent_. Specifically, at iteration $k\in\\{0,1,\ldots,K\\}$,
given confidence $\lambda_{k-1}$, we first compute an updated candidate policy
$\rho_{k}$, and with $\rho_{k}$ fixed, we update $\lambda_{k}$, i.e.,
$\mathcal{L}_{\beta,\rho_{k},\lambda_{k}}\geq\mathcal{L}_{\beta,\rho_{k},\lambda_{k-1}}\geq\mathcal{L}_{\beta,\rho_{k-1},\lambda_{k-1}}$.
When $\lambda$ and $\rho$ are represented tabularly or with linear function
approximators, under certain regularity assumptions (the Kurdyka-Lojasiewicz
property (Xu and Yin, 2013)) coordinate ascent guarantees global convergence
(to the limit point) for BRPO.

However, when more complex representations (e.g., neural networks) are used to
parameterize these decision variables, this property no longer holds. While
one may still compute $(\lambda^{*},\rho^{*})$ with first-order methods (e.g.,
SGD), convergence to local optima is not guaranteed. To address this, we next
further restrict the MM procedure to develop closed-form solutions for both
the candidate policy and the confidence.

#### The Closed-form Candidate Policy $\rho$.

To effectively update the candidate policy when given the confidence
$\lambda\in\Lambda$, we develop a closed-form solution for $\rho$. Our
approach is based on maximizing the following objective, itself a more
conservative version of the CPI lower bound
$\mathcal{L}_{\beta,\rho,\lambda}$:

$\displaystyle\max_{\rho\in\Delta}\,\hat{\mathcal{L}}_{\beta,\rho,\lambda}:=\mathbb{E}_{s\sim
d_{\beta}}\\!\bigg{[}\\!\mathbb{E}_{a\sim\beta}\left[\lambda(s,a)\frac{\rho(a|s)-\beta(a|s)}{\beta(a|s)}A_{\beta}\right]$
$\displaystyle\quad-\frac{\gamma\max\\{\kappa_{\lambda}(s),\kappa_{|A_{\beta}|\lambda}(s)\\}}{2(1-\gamma)}\cdot
D_{\mathrm{KL}}(\rho\|\beta)(s)\bigg{]}\cdot\frac{1}{1-\gamma},$ (4)

where $\kappa_{g}(s)=(1+\log\mathbb{E}_{\beta}[\exp(g(a|s)^{2})])>0$ for any
arbitrary non-negative function $g$. To show that
$\hat{\mathcal{L}}_{\beta,\rho,\lambda}$ in (4) is an eligible lower bound (so
that the corresponding $\rho$-solution is an MM), we need to show that it
satisfies the properties in (3). When $\rho=\beta$, by the definition of
$\hat{\mathcal{L}}_{\beta,\rho,\lambda}$ the second property holds. To show
the first property, we first consider the following problem:

$\max_{\rho\in\Delta}\frac{1}{1-\gamma}\left(L^{\prime}_{\beta,\rho,\lambda}-\frac{\gamma}{1-\gamma}\widetilde{L}^{\prime\prime}_{\beta,\rho,\lambda}\cdot\widetilde{L}^{\prime\prime\prime}_{\beta,\rho,\lambda}\right),$
(5)

where $L^{\prime}_{\beta}(\rho,\lambda)$ is given in Theorem 4, and

$\begin{split}\widetilde{L}^{\prime\prime}_{\beta,\rho,\lambda}=&\mathbb{E}_{s\sim
d_{\beta}}\left[\sqrt{\kappa_{\lambda}(s)\cdot
D_{\mathrm{KL}}(\rho\|\beta)(s)/2}\right],\\\
\widetilde{L}^{\prime\prime\prime}_{\beta,\rho,\lambda}=&\mathbb{E}_{s\sim
d_{\beta}}\left[\sqrt{{\kappa_{|A_{\beta}|\lambda}(s)\cdot
D_{\mathrm{KL}}(\rho\|\beta)(s)}/{2}}\right].\end{split}$

The concavity of $\sqrt{(\cdot)}$ (i.e., $\mathbb{E}_{s\sim
d_{\beta}}[\sqrt{(\cdot)}]\leq\sqrt{\mathbb{E}_{s\sim d_{\beta}}[(\cdot)]}$)
and monotonicity of expectation imply that the objective in (4) is a lower
bound of that in (6) below. Furthermore, by the weighted Pinsker’s inequality
(Bolley and Villani, 2005)
$\sum_{a}|g(a|s)(\rho(a|s)-\beta(a|s))|\leq\sqrt{\kappa_{g}(s)D_{\mathrm{KL}}(\rho\|\beta)(s)/2}$,
we have: (i) $0\leq\widetilde{L}^{\prime\prime}_{\beta,\rho,\lambda}\leq
L^{\prime\prime}_{\beta,\rho,\lambda}$; and (ii)
$0\leq\widetilde{L}^{\prime\prime\prime}_{\beta,\rho,\lambda}\leq
L^{\prime\prime\prime}_{\beta,\rho,\lambda}$, which implies the objective in
(5) is a lower-bound of that in (2) and validates the first MM property.

Now recall the optimization problem:
$\max_{\rho\in\Delta}\,\hat{\mathcal{L}}_{\beta,\rho,\lambda}$. Since this
optimization is over the state-action mapping $\rho$, the Interchangeability
Lemma (Shapiro et al., 2009) allows swapping the order of $\mathbb{E}_{s\sim
d_{\beta}}$ and $\max_{\rho\in\Delta}$. This implies that at each $s\in S$ the
candidate policy can be solved using:

$\displaystyle\rho^{*}_{\lambda}\\!\in\\!$
$\displaystyle\operatorname*{arg\,max}_{\rho(\cdot|s)\in\Delta}\mathbb{E}_{a\sim\beta}\\!\left[\left(\\!\lambda\cdot\frac{\rho-\beta}{\beta}\cdot
A_{\beta}\right)\\!(s,a)-\tau_{\lambda}(s)\log\frac{\rho(a|s)}{\beta(a|s)}\right]$
$\displaystyle=$
$\displaystyle\operatorname*{arg\,max}_{\rho(\cdot|s)\in\Delta}\mathbb{E}_{a\sim\rho}\\!\left[\lambda(s,a)A_{\beta}\\!-\\!\tau_{\lambda}(s)\log\frac{\rho(a|s)}{\beta(a|s)}\right],$
(6)

where
$\tau_{\lambda}(s)={\gamma\max\\{\kappa_{\lambda}(s),\kappa_{|A_{\beta}|\lambda}(s)\\}}/{(2-2\gamma)}$
is the state-dependent penalty weight of the relative entropy regularization.
By the KKT condition of (6), the optimal candidate policy $\rho^{*}_{\lambda}$
has the form

$\rho^{*}_{\lambda}(a|s)=\frac{\beta(a|s)\cdot\exp\left(\frac{\lambda(s,a)A_{\beta}}{\tau_{\lambda}(s)}\right)}{\mathbb{E}_{a^{\prime}\sim\beta}[\exp({\lambda(s,a^{\prime})A_{\beta}(s,a^{\prime})}/{\tau_{\lambda}(s)})]}.$
(7)

Notice that the optimal candidate policy is a _relative softmax policy_ ,
which is a common solution policy for many entropy-regularized RL algorithms
(Haarnoja et al., 2018). Intuitively, when the mixing factor vanishes (i.e.,
$\lambda(s,a)=0$), the candidate policy equals to the behavior policy, and
with confidence we obtain the candidate policy by modifying the behavior
policy $\beta$ via _exponential twisting_.

#### The Closed-form Confidence $\lambda$.

Given candidate policy $\rho$, we derive efficient scheme for computing the
confidence that solves the MM problem:
$\max_{\lambda\in\Lambda}\mathcal{L}_{\beta,\rho,\lambda}$. Recall that this
optimization can be reformulated as a concave quadratic program (QP) with
linear equality constraints, which has a unique optimal solution (Faybusovich
and Moore, 1997). However, since the decision variable (i.e., the confidence
mapping) is infinite-dimensional, solving this QP is intractable without some
assumptions about this mapping, To resolve this issue, instead of using the
surrogate objective $\mathcal{L}_{\beta,\rho,\lambda}$ in MM, we turn to its
sample-based estimate. Specifically, given a batch of data
$B=\\{(s_{i},a_{i},r_{i},s^{\prime}_{i})\\}_{i=1}^{|B|}$ generated by the
behavior policy $\beta$, denote by

$\begin{split}&\overline{L}^{\prime}_{\beta,\rho,\lambda}:=\frac{1}{1-\gamma}\cdot\frac{1}{|B|}\sum_{i=1}^{|B|}\overline{\lambda}_{i}^{\top}\cdot\left((\rho-\beta)\cdot
A_{\beta}\right)_{i}\\\
&\overline{L}^{\prime\prime}_{\beta,\rho,\lambda}:=\frac{1}{1-\gamma}\cdot\frac{1}{|B|}\sum_{i=1}^{|B|}\overline{\lambda}_{i}^{\top}\cdot|\rho-\beta|_{i}\\\
&\overline{L}^{\prime\prime\prime}_{\beta,\rho,\lambda}:=\frac{\gamma}{1-\gamma}\cdot\frac{1}{|B|}\sum_{i=1}^{|B|}\overline{\lambda}_{i}^{\top}\cdot\left(|\rho-\beta|\cdot|A_{\beta}|\right)_{i}\end{split}$

the sample-average approximation (SAA) of functions
${L}^{\prime}_{\beta,\rho,\lambda}$,
${L}^{\prime\prime}_{\beta,\rho,\lambda}$, and
${L}^{\prime\prime\prime}_{\beta,\rho,\lambda}$ respectively, where
$((\rho-\beta)\cdot A_{\beta})=\\{(\rho(\cdot|s_{i})-\beta(\cdot|s_{i}))\cdot
A_{\beta}(s_{i},\cdot)\\}_{s_{i}\in B}$,
$\left(|\rho-\beta|\cdot|A_{\beta}|\right)=\\{(|\rho(\cdot|s_{i})-\beta(\cdot|s_{i})|\cdot|A_{\beta}(s_{i},\cdot)|)\\}_{s_{i}\in
B}$, and $|\rho-\beta|=\\{|\rho(\cdot|s_{i})-\beta(\cdot|s_{i})|\\}_{s_{i}\in
B}$ are $|A|\cdot|B|$-dimensional vectors, where each element is generated by
a state sample from $B$, and
$\overline{\lambda}=\\{\lambda(\cdot|s_{i})\\}_{s_{i}\in B}$ is a
$|A|\cdot|B|$-dimensional decision vector, where each $|A|$-dimensional
element vector corresponds to the confidence w.r.t. state samples in $B$.
Since the expectation in ${L}^{\prime}_{\beta,\rho,\lambda}$,
${L}^{\prime\prime}_{\beta,\rho,\lambda}$, and
${L}^{\prime\prime\prime}_{\beta,\rho,\lambda}$ is over the stationary
distribution induced by the behavior policy, all the SAA functions are
_unbiased_ Monte-Carlo estimates of their population-based counterparts. We
now define
$\overline{\mathcal{L}}_{\beta,\rho,\lambda}:=\overline{L}^{\prime}_{\beta,\rho,\lambda}-\overline{L}^{\prime\prime}_{\beta,\rho,\lambda}\overline{L}^{\prime\prime\prime}_{\beta,\rho,\lambda}$
as the SAA-MM objective and use this to solve for the confidence vector
$\overline{\lambda}$ over the batch samples.

Now consider the following maximization problem:

$\max_{\overline{\lambda}\in\overline{\Lambda}}\langle(\rho-\beta)\cdot
A_{\beta},\overline{\lambda}\rangle-\frac{\gamma}{|B|(1-\gamma)}\langle|\rho-\beta|,\overline{\lambda}\rangle\cdot\langle|\rho-\beta||A_{\beta}|,\overline{\lambda}\rangle,$
(8)

where the feasible set $\overline{\Lambda}=\\{\lambda\in[0,1]:\sum_{a\in
A}\lambda(s_{i},a)\cdot(\rho(a|s_{i})-\beta(a|s_{i}))\cdot=0,\forall
i\in\\{1,\ldots,|B|\\}\\}$ only imposes constraints on the states that appear
in the batch $B$.

This finite-dimensional QP problem can be expressed in the following quadratic
form:

$\max_{\overline{\lambda}\in\overline{\Lambda}}\,\,\overline{\lambda}^{\top}\Big{(}(\rho-\beta)\cdot
A_{\beta}\Big{)}-\frac{1}{2}\cdot\overline{\lambda}^{\top}\Theta\overline{\lambda},$

where the symmetric matrix is given by

$\Theta_{\beta,\rho}:=\frac{\gamma(D_{|A_{\beta}|}\cdot|\rho-\beta|\cdot|\rho-\beta|^{\top}+|\rho-\beta|\cdot|\rho-\beta|^{\top}\cdot
D_{|A_{\beta}|}^{\top})}{|B|(1-\gamma)},$

and $D_{|A_{\beta}|}=\text{diag}(\\{|A_{\beta}|\\}_{a\in A,s\in B})$ is a
$|B|\cdot|A|\times|B|\cdot|A|$-diagonal matrix whose elements are the absolute
advantage function. By definition, $\Theta$ is positive-semi-definite, hence
the QP above is concave. Using its KKT condition, the unique optimal
confidence vector over batch $B$ is given as

$\overline{\lambda}^{*}=\min\\{1,\max\\{0,\Theta_{\beta,\rho}^{-1}((\rho-\beta)\cdot
A_{\beta}+M_{\beta,\rho}^{\top}\nu_{\beta,\rho}\\}\\},$ (9)

where $M_{\beta,\rho}=\text{blkdiag}(\\{[\rho(a|x)-\beta(a|x)]_{a\in
A}\\}_{x\in B})$ is a $|B|\cdot|A|\times|B|$-matrix, and the Lagrange
multiplier $\nu_{\beta,\rho}\in\mathbb{R}^{|B|}$ w.r.t. constraint
$M_{\beta,\rho}\overline{\lambda}=0$ is given by

$\nu_{\beta,\rho}\\!=\\!-(M_{\beta,\rho}^{\top}\Theta^{-1}_{\beta,\rho}M_{\beta,\rho})^{-1}(M_{\beta,\rho}^{\top}\Theta_{\beta,\rho}^{-1}(\rho-\beta)\cdot
A_{\beta}).$ (10)

We first construct the confidence function $\lambda(s,a)$ from the confidence
vector $\overline{\lambda}^{*}$ over $B$, in the following tabular fashion:

$\lambda(s,a)=\left\\{\begin{array}[]{cl}\overline{\lambda}^{*}_{s,a}&\text{if
$(s,a)\in B$}\\\ 0&\text{otherwise}\end{array}\right..$

While this construction preserves optimality w.r.t. the CPI objective (2), it
may be overly conservative, because the policy equates to the behavior policy
by setting $\lambda=0$ at state-action pairs that are not in $B$ (i.e., no
policy improvement). To alleviate this conservatism, we propose to learn a
confidence function that generalizes to out-of-distribution samples.

Environment-$\varepsilon$ | DQN | BRPO-C | BRPO (ours) | BCQ | KL-Q | SPIBB | BC | Behavior Policy
---|---|---|---|---|---|---|---|---
Acrobot-0.05 | -91.2 $\pm$ 9.1 |  -94.6 $\pm$ 3.8 | -91.9 $\pm$ 9.0 |  -96.9 $\pm$ 3.7 |  -93.0 $\pm$ 2.6 |  -103.5 $\pm$ 24.1 |  -102.3 $\pm$ 5.0 | -103.9
Acrobot-0.15 | -83.1 $\pm$ 5.2 |  -91.7 $\pm$ 4.0 | -86.1 $\pm$ 10.1 |  -97.1 $\pm$ 3.3 |  -92.1 $\pm$ 3.2 |  -91.1 $\pm$ 44.8 |  -113.1 $\pm$ 5.6 | -114.3
Acrobot-0.25 | -83.4 $\pm$ 3.9 |  -91.2 $\pm$ 4.1 | -85.3 $\pm$ 4.8 |  -96.7 $\pm$ 3.1 |  -90.0 $\pm$ 2.9 |  -86.0 $\pm$ 5.8 |  -124.1 $\pm$ 7.0 | -127.2
Acrobot-0.50 |  -84.3 $\pm$ 22.6 |  -90.9 $\pm$ 3.4 | -83.7 $\pm$ 16.6 | -77.8 $\pm$ 13.5 |  -84.5 $\pm$ 3.8 |  -106.8 $\pm$ 102.7 |  -173.7 $\pm$ 8.1 | -172.4
Acrobot-1.00 |  -208.9 $\pm$ 174.8 | -156.8 $\pm$ 22.0 | -121.7 $\pm$ 10.2 |  -236.0 $\pm$ 85.6 |  -227.5 $\pm$ 148.1 |  -184.8 $\pm$ 150.2 |  -498.3 $\pm$ 1.7 | -497.3
CartPole-0.05 |  82.7 $\pm$ 0.5 |  220.8 $\pm$ 117.0 | 336.3 $\pm$ 122.6 |  255.4 $\pm$ 11.1 | 323.0 $\pm$ 13.5 |  28.8 $\pm$ 1.2 |  205.6 $\pm$ 19.6 | 219.1
CartPole-0.15 |  299.3 $\pm$ 133.5 |  305.6 $\pm$ 95.2 | 409.9 $\pm$ 64.4 |  255.3 $\pm$ 11.4 | 357.7 $\pm$ 84.1 |  137.7 $\pm$ 11.7 |  151.6 $\pm$ 27.5 | 149.5
CartPole-0.25 |  368.5 $\pm$ 129.3 | 405.1 $\pm$ 74.4 |  316.8 $\pm$ 64.1 |  247.4 $\pm$ 128.7 | 441.4 $\pm$ 79.8 |  305.2 $\pm$ 119.7 |  103.0 $\pm$ 20.4 | 101.9
CartPole-0.50 |  271.5 $\pm$ 52.0 | 358.3 $\pm$ 114.1 | 433.8 $\pm$ 93.5 |  282.5 $\pm$ 111.8 |  314.1 $\pm$ 107.0 |  310.4 $\pm$ 128.0 |  39.7 $\pm$ 5.1 | 37.9
CartPole-1.00 |  118.3 $\pm$ 0.3 | 458.6 $\pm$ 51.5 | 369.0 $\pm$ 42.3 |  194.0 $\pm$ 25.1 |  209.7 $\pm$ 48.4 |  147.1 $\pm$ 0.1 |  22.6 $\pm$ 1.5 | 21.9
LunarLander-0.05 |  -236.4 $\pm$ 177.6 |  35.6 $\pm$ 61.7 | 88.2 $\pm$ 32.0 |  81.5 $\pm$ 14.9 | 84.4 $\pm$ 26.3 |  -200.4 $\pm$ 81.7 |  75.8 $\pm$ 17.7 | 73.7
LunarLander-0.15 |  -215.6 $\pm$ 140.4 |  79.6 $\pm$ 29.7 | 103.9 $\pm$ 49.8 |  80.3 $\pm$ 16.8 |  61.4 $\pm$ 39.0 | 86.1 $\pm$ 73.3 |  76.4 $\pm$ 16.6 | 84.9
LunarLander-0.25 |  2.5 $\pm$ 101.3 |  109.5 $\pm$ 40.7 | 141.6 $\pm$ 11.0 |  83.5 $\pm$ 14.6 |  78.7 $\pm$ 48.8 | 166.0 $\pm$ 90.6 |  57.9 $\pm$ 13.1 | 57.3
LunarLander-0.50 |  -104.6 $\pm$ 68.3 |  42.5 $\pm$ 71.4 | 101.0 $\pm$ 39.6 |  -13.2 $\pm$ 44.9 | 66.2 $\pm$ 78.0 |  -134.6 $\pm$ 17.1 |  -32.6 $\pm$ 6.5 | -36.0
LunarLander-1.00 |  -65.6 $\pm$ 45.9 | 53.5 $\pm$ 44.1 | 81.8 $\pm$ 42.1 |  -69.1 $\pm$ 44.0 |  -139.2 $\pm$ 29.1 |  -107.1 $\pm$ 94.4 |  -177.4 $\pm$ 13.1 | -182.6
Table 1: The mean and st. dev. of average return with the best hyperparameter
configuration (with the top-2 results boldfaced). Full training curves are
given in Figure 1 in the appendix. For BRPO-C, the optimal confidence
parameter is found by grid search.

#### Learning the Confidence.

Given a confidence vector $\overline{\lambda}^{*}$ corresponding to samples in
batch $B$, we learn the confidence function $\lambda_{\phi}(s,a)$ in
supervised fashion. To ensure that the confidence function satisfies the
constraint: $\lambda_{\phi}\in\Lambda$, i.e.,
$\sum_{a}\lambda_{\phi}(s,a)(\rho(a|s)-\beta(a|s))=0$,
$\lambda_{\phi}(s,a)\in[0,1]$, $\forall s,a$333If one restricts
$\lambda_{\phi}$ to be only _state_ -dependent, this constraint immediately
holds., we parameterize it as

$\lambda_{\phi^{*}}(s,a):=\frac{\pi_{\phi^{*}}(a|s)-\beta(a|s)}{\rho(a|s)-\beta(a|s)},\,\,\forall(s,a)\in
S\times A,$ (11)

where $\pi_{\phi}\in\Delta$ is a learnable policy mapping, such that
$\min\\{\beta(a|s),\rho(a|s)\\}\leq\pi_{\phi}(a|s)\leq\max\\{\beta(a|s),\rho(a|s)\\}$,
$\forall s,a$. We then learn $\phi$ via the following KL distribution-fitting
objective (Rusu et al., 2015):

$\min_{\phi}\frac{1}{B}\sum_{(s,a)\in
B}\\!\\!\pi_{\phi}(a|s)\log\left(\frac{\pi_{\phi}(a|s)}{(1-\overline{\lambda}^{*}_{s,a})\beta(a|s)+\overline{\lambda}^{*}_{s,a}\cdot\rho(a|s)}\right).$

While this approach learns $\lambda_{\phi}$ by generalizing the confidence
vector to out-of-distribution samples, when $\pi_{\phi}$ is a NN, one
challenge is to enforce the constraint:
$\min\\{\beta(a|s),\rho(a|s)\\}\leq\pi_{\phi}(a|s)\leq\max\\{\beta(a|s),\rho(a|s)\\}$,
$\forall s,a$. Instead, using an in-graph convex optimization NN (Amos and
Kolter, 2017), we parameterize $\lambda_{\phi}$ with a NN with the following
_constraint-projection layer_ $\Phi:S\rightarrow A$ before the output:

$\displaystyle\Phi(s)\in$
$\displaystyle\arg\min_{\lambda\in\mathbb{R}^{|A|}}\,\frac{1}{2}\sum_{a\in
A}\|\lambda_{a}-\widetilde{\lambda}^{*}_{s,a}\|^{2},$ s.t.
$\displaystyle\,\sum_{a}\lambda_{a}(\rho(a|s)-\beta(a|s))=0,\,\,0\leq\lambda\leq
1,$ (12)

where, at any $s\in S$, the $|A|$-dimensional confidence vector label
$\\{\widetilde{\lambda}^{*}_{s,a}\\}_{a\in A}$ is equal to
$\\{\overline{\lambda}^{*}_{\overline{s},a}\\}_{a\in A}$ chosen from the batch
confidence vector $\overline{\lambda}^{*}$ such that $\overline{s}$ in $B$ is
closest to $s$. Indeed, analogous to the closed-form solution in (9), this
projection layer has a closed-form QP formulation with linear constraints:
$\Phi(s)=\min\\{1,\max\\{0,\widetilde{\lambda}^{*}_{s,\cdot}+(\rho(\cdot|s)-\beta(\cdot|s))\cdot\mu_{\beta,\rho}\\}\\}$,
where Lagrange multiplier $\mu_{\beta,\rho}$ is given by
$\mu_{\beta,\rho}\\!=\\!-{(\rho(\cdot|s)-\beta(\cdot|s))^{\top}\widetilde{\lambda}^{*}_{s,\cdot}}/{\|\rho(\cdot|s)-\beta(\cdot|s)\|^{2}}.$

Although the $\rho$-update is theoretically justified, in practice, when the
magnitude of $\kappa_{\lambda}(s)$ becomes large (due to the conservatism of
the weighted Pinsker inequality), the relative-softmax candidate policy (7)
may be too close to the behavior policy $\beta$, impeding learning of the
residual policy (i.e., $\pi\approx\beta$). To avoid this in practice, we can
upper bound the temperature, i.e.,
$\kappa_{\lambda}(s)\leftarrow\min\\{\kappa_{\max},\kappa_{\lambda}(s)\\}$, or
introduce a weak temperature-decay schedule, i.e.,
$\kappa_{\lambda}(s)\leftarrow\kappa_{\lambda}(s)\cdot\epsilon^{k}$, with a
tunable $\epsilon\in[0,1)$.

Algorithm 1 BRPO algorithm

1: $B$: batch data; Tunable parameter $\mu\in[0,1]$

2:for $t=1,\ldots,N$ do

3: Sample mini-batch of transitions $(s,a,r,d,s^{\prime})\sim B$

4: Compute $\overline{\lambda}^{*}$ from Eq. (9)

5: Update confidence $\phi^{*}$ by Eq. (12)

6: Update candidate policy $\rho^{*}_{\lambda_{\phi^{*}}}$ by Eq. (7)

7: Construct target critic network
$V_{\theta^{\prime}}(s^{\prime})\\!:=\\!(1-\mu)\mathbb{E}_{a^{\prime}\sim\beta}[Q_{\theta^{\prime}}(s^{\prime},a^{\prime})]+\mu\max_{a^{\prime}}Q_{\theta^{\prime}}(s^{\prime},a^{\prime})$
$\triangleright$ See section 4 for the analysis in the case $\mu=1$

8: Update
$\theta\leftarrow\operatorname*{arg\,max}_{\theta}\frac{1}{2}\left(Q_{\theta}(s,a)-r-\gamma
V_{\theta^{\prime}}(s^{\prime})\right)^{2}$

9: Update target network:
$\theta^{\prime}\leftarrow\tau\theta+(1-\tau)\theta^{\prime}$

##  6 Experimental Results

To illustrate the effectiveness of BRPO, we compare against six baselines: DQN
(Mnih et al., 2013), discrete BCQ (Fujimoto et al., 2019), KL-regularized
Q-learning (KL-Q) (Jaques et al., 2019), SPIBB (Laroche and Trichelair, 2017),
Behavior Cloning (BC) (Kober and Peters, 2010), and BRPO-C, which is a
simplified version of BRPO that uses a constant (tunable) parameter as
confidence weight444For algorithms designed for online settings, we modify
data collection to sample only from offline / batch data.. We do not consider
ensemble models, thus do not include methods like BEAR (Kumar et al., 2019)
among our baselines. CPI is also excluded since it is subsumed by BRPO-C with
a grid search on the confidence. It is also generally inferior to BRPO-C
because candidate policy learning does not optimize the performance of the
final mixture policy. We evaluated on three discrete-action OpenAI Gym tasks
(Brockman et al., 2016): Cartpole-v1, Lunarlander-v2, and Acrobot-v1.

The behavior policy in each environment is trained using standard DQN until it
reaches $75\%$ of optimal performance, similar to the process adopted in
related work (e.g., Fujimoto et al. (2018)). To assess how exploration and the
quality of behavior policy affect learning, we generate five sets of data for
each task by injecting different random exploration into the same behavior
policy. Specifically, we add $\varepsilon$-greedy exploration for
$\varepsilon=1$ (fully random), $0.5$, $0.25$, $0.15$, and $0.05$, generating
$100K$ transitions each for batch RL training.

All models use the same architecture for a given environment—details
(architectures, hyper-parameters, etc.) are described in the appendix of the
extended paper. While training is entirely offline, policy performance is
evaluated online using the simulator, at every $1000$ training iterations.
Each measurement is the average return w.r.t. $40$ evaluation episodes and $5$
random seeds, and results are averaged over a sliding window of size $10$.

Table 1 shows the average return of BRPO and the other baselines under the
best hyper-parameter configurations in each task setting. Behavior policy
performance decreases as $\varepsilon$ increases, as expected, and BC matches
that very closely. DQN performs poorly in the batch setting. Its performance
improves as $\varepsilon$ increases from $0.05$ to $0.25$, due to increased
state-action coverage, but as $\varepsilon$ goes higher ($0.5$, $1.0$), the
state space coverage decreases again since the (near-) random policy is less
likely to reach a state far away from the initial state.

Baselines like BCQ, KL-Q and SPIBB follow the behavior policy in some ways,
and showing different performance characteristics over the data sets. The
underperformance relative to BRPO is more prominent for very low or very high
$\varepsilon$, suggesting deficiency due to overly conservative updates or
following the behavior policy too closely, when BRPO is able to learn.

Since BRPO exploits the statistics of each $(s,a)$ pair in the batch data, it
achieves good performance in almost all scenarios, outperforming the
baselines. The stable performance and robustness across various scenarios make
BRPO an appealing algorithm for batch/offline RL in real-world, where it is
usually difficult to estimate the amount of exploration required prior to
training, given access only to batch data.

##  7 Concluding Remarks

We have presented Batch Residual Policy Optimization (BRPO) for learning
residual policies in batch RL settings. Inspired by CPI, we derived learning
rules for jointly optimizing both the candidate policy and _state-action
dependent_ confidence mixture of a residual policy to maximize a conservative
lower bound on policy performance. BRPO is thus more exploitative in areas of
state space that are well-covered by the batch data and more conservative in
others. While we have shown successful application of BRPO to various
benchmarks, future work includes deriving finite-sample analysis of BRPO, and
applying BRPO to more practical batch domains (e.g., robotic manipulation,
recommendation systems).

## References

  * Abbasi-Yadkori et al. (2019) Y. Abbasi-Yadkori, P. Bartlett, X. Chen, and A. Malek.  Large-scale Markov decision problems via the linear programming dual.  arXiv:1901.01992, 2019.
  * Amos and Kolter (2017) B. Amos and Z. Kolter.  Optnet: Differentiable optimization as a layer in neural networks.  ICML-17, pp.136–145. 2017.
  * Bolley and Villani (2005) F. Bolley and C. Villani.  Weighted Csiszár-Kullback-Pinsker inequalities and applications to transportation inequalities.  Annales de la Faculté des sciences de Toulouse: Mathématiques, 14:331–352, 2005.
  * Boyd and Vandenberghe (2004) S. Boyd and L. Vandenberghe.  Convex optimization.  Cambridge University Press, 2004.
  * Brockman et al. (2016) G. Brockman, V. Cheung, L. Pettersson, J. Schneider, J. Schulman, J. Tang, and W. Zaremba.  OpenAI Gym, 2016.
  * Farias and Roy (2003) P. De Farias and B. Van Roy.  The linear programming approach to approximate dynamic programming.  Op. Res., 51(6):850–865, 2003.
  * Faybusovich and Moore (1997) L. Faybusovich and J. Moore.  Infinite-dimensional quadratic optimization: interior-point methods and control applications.  Appl. Math. and Opt., 36(1):43–66, 1997.
  * Fujimoto et al. (2018) S. Fujimoto, D. Meger, and D. Precup.  Off-policy deep reinforcement learning without exploration.  arXiv:1812.02900, 2018.
  * Fujimoto et al. (2019) S. Fujimoto, E. Conti, M. Ghavamzadeh, and J. Pineau.  Benchmarking batch deep reinforcement learning algorithms.  arXiv:1910.01708, 2019.
  * Gauci et al. (2018) J. Gauci, E. Conti, Y. Liang, K. Virochsiri, Y. He, Z. Kaden, V. Narayanan, and X. Ye.  Horizon: Facebook’s open source applied reinforcement learning platform.  arXiv:1811.00260, 2018.
  * Ghavamzadeh et al. (2016) M. Ghavamzadeh, M. Petrik, and Y. Chow.  Safe policy improvement by minimizing robust baseline regret.  NeurIPS-16, pp.2298–2306, 2016.
  * Gretton et al. (2007) A. Gretton, K. Borgwardt, M. Rasch, B. Schölkopf, and A. Smola.  A kernel approach to comparing distributions.  AAAI-07, pp.1637–1641, 2007.
  * Haarnoja et al. (2018) T. Haarnoja, A. Zhou, P. Abbeel, and S. Levine.  Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with a stochastic actor.  arXiv:1801.01290, 2018.
  * Hasselt et al. (2016) H. Van Hasselt, A. Guez, and D. Silver.  Deep reinforcement learning with double Q-learning.  AAAI-16, pp.2094–2200, 2016.
  * Hunter and Lange (2004) D. Hunter and K. Lange.  A tutorial on MM algorithms.  The American Statistician, 58(1):30–37, 2004.
  * Jaques et al. (2019) N. Jaques, A. Ghandeharioun, J. Shen, C. Ferguson, A. Lapedriza, N. Jones, S. Gu, and R. Picard.  Way off-policy batch deep reinforcement learning of implicit human preferences in dialog.  arXiv:1907.00456, 2019.
  * Johannink et al. (2019) T. Johannink, S. Bahl, A. Nair, J. Luo, A. Kumar, M. Loskyll, J. Ojea, E. Solowjow, and S.Levine.  Residual reinforcement learning for robot control.  ICRA-19, pp.6023–6029, 2019.
  * Kakade and Langford (2002) S. Kakade and J. Langford.  Approximately optimal approximate reinforcement learning.  ICML-02, pp.267–274, 2002.
  * Knight and Lerner (2018) E. Knight and O. Lerner.  Natural gradient deep Q-learning.  arXiv:1803.07482, 2018.
  * Kober and Peters (2010) J. Kober and J. Peters.  Imitation and reinforcement learning.  IEEE Rob. & Autom., 17(2):55–62, 2010.
  * Kumar et al. (2019) A. Kumar, J. Fu, G. Tucker, and S. Levine.  Stabilizing off-policy Q-learning via bootstrapping error reduction.  arXiv:1906.00949, 2019.
  * Lange et al. (2012) S. Lange, T. Gabel, and M. Riedmiller.  Batch reinforcement learning.  In Reinforcement Learning, pp.45–73. Springer, 2012.
  * Laroche and Trichelair (2017) R. Laroche and P. Trichelair.  Safe policy improvement with baseline bootstrapping.  arXiv:1712.06924, 2017.
  * Lillicrap et al. (2015) T. Lillicrap, J. Hunt, A. Pritzel, N. Heess, T. Erez, Y. Tassa, D. Silver, and D. Wierstra.  Continuous control with deep reinforcement learning.  arXiv:1509.02971, 2015.
  * Mahmood et al. (2014) A. Mahmood, H. van Hasselt, and R. Sutton.  Weighted importance sampling for off-policy learning with linear function approximation.  NeurIPS-14, pp.3014–3022, 2014.
  * Mnih et al. (2013) V. Mnih, K. Kavukcuoglu, D. Silver, A. Graves, I. Antonoglou, D. Wierstra, and M. Riedmiller.  Playing atari with deep reinforcement learning.  arXiv:1312.5602, 2013.
  * Nachum et al. (2019) O. Nachum, M. Ahn, H. Ponte, S. Gu, and V. Kumar.  Multi-agent manipulation via locomotion using hierarchical sim2real.  CORL-19, 2019.
  * O’Donoghue et al. (2016) B. O’Donoghue, R. Munos, K. Kavukcuoglu, and V. Mnih.  Combining policy gradient and Q-learning.  arXiv:1611.01626, 2016.
  * Pirotta et al. (2013) M. Pirotta, M. Restelli, A. Pecorino, and D. Calandriello.  Safe policy iteration.  ICML-13, pp.307–315, 2013.
  * Rusu et al. (2015) A. Rusu, S. Colmenarejo, C. Gulcehre, G. Desjardins, J. Kirkpatrick, R. Pascanu, V. Mnih, K. Kavukcuoglu, and R. Hadsell.  Policy distillation.  arXiv:1511.06295, 2015.
  * Schulman et al. (2015) J. Schulman, S. Levine, P. Abbeel, M. Jordan, and P. Moritz.  Trust region policy optimization.  ICML-15, pp.1889–1897, 2015.
  * Shapiro et al. (2009) A. Shapiro, D. Dentcheva, and A. Ruszczyński.  Lectures on stochastic programming: modeling and theory.  SIAM, 2009.
  * Silver et al. (2018) T. Silver, K. Allen, J. Tenenbaum, and L. Kaelbling.  Residual policy learning.  arXiv:1812.06298, 2018.
  * Sutton and Barto (2018) R. Sutton and A. Barto.  Reinforcement learning: An introduction.  MIT Press, 2018.
  * Xu and Yin (2013) Y. Xu and W. Yin.  A block coordinate descent method for regularized multiconvex optimization with applications to nonnegative tensor factorization and completion.  SIAM J. Imag. Sci., 6(3):1758–1789, 2013.

##  Appendix A Proofs for Results in Section 3

###  A.1 Proof of Lemma 1

Before going into the derivation of this theorem, we first have the following
technical result that studies the distance of the occupation measures that are
induced by $\beta$ and $\pi$.

######  Lemma 5.

The following expression holds for any state-next-state pair $(s,s^{\prime})$:

$\left((I-\gamma T_{\pi})^{-1}-(I-\gamma
T_{\beta})^{-1}\right)(s^{\prime}|s)=-\gamma(I-\gamma T_{\beta})^{-1}\Delta
T_{\beta,\rho,\lambda}(I-\gamma T_{\pi})^{-1}(s^{\prime}|s),$

where $T_{\pi}(s^{\prime}|s)$ and $T_{\beta}(s^{\prime}|s)$ represent the
transition probabilities from state $s$ to next-state $s^{\prime}$ following
policy $\pi$ and $\beta$ respectively, and for any state-next-state pair
$(s,s^{\prime})$, $\Delta T_{\beta,\rho,\lambda}(s^{\prime}|s)=\sum_{a\in
A}T(s^{\prime}|s,a)\beta(a|s)\cdot\lambda(s,a)\cdot\frac{\rho(a|s)-\beta(a|s)}{\beta(a|s)}$.

###### Proof.

Consider the following chain of equalities from matrix manipulations:

$\begin{split}(I-\gamma T_{\beta})^{-1}\cdot(I-\gamma T_{\pi})=&(I-\gamma
T_{\beta})^{-1}\cdot\left(I-\gamma\left\\{\sum_{a\in
A}T(s^{\prime}|s,a)\left(\beta(a|s)+\lambda(s,a)(\rho(a|s)-\beta(a|s))\right)\right\\}_{s,s^{\prime}}\right)\\\
=&\left(I-\gamma(I-\gamma T_{\beta})^{-1}\left\\{\sum_{a\in
A}T(s^{\prime}|s,a)\lambda(s,a)(\rho(a|s)-\beta(a|s))\right\\}_{s,s^{\prime}\in
S}\right).\end{split}$

By multiplying the matrix $(I-\gamma T_{\pi})^{-1}$ on both sides of the above
expression, it implies that

$\begin{split}(I-\gamma T_{\beta})^{-1}-(I-\gamma
T_{\pi})^{-1}=&-\left(\gamma(I-\gamma T_{\beta})^{-1}\left\\{\sum_{a\in
A}T(s^{\prime}|s,a)\lambda(s,a)(\rho(a|s)-\beta(a|s))\right\\}_{s,s^{\prime}\in
S}(I-\gamma T_{\pi})^{-1}\right).\end{split}$

Using the definition of $\Delta T_{\beta,\rho,\lambda}$ completes the proof of
this lemma. ∎

Using the above result, for any initial state $s\in S$, the value functions
that are induced by $\beta$ and $\pi$ have the following relationship:

$\begin{split}V_{\pi}(s)-V_{\beta}(s)=&\delta_{s_{0}=s}^{\top}(I-\gamma
T_{\pi})^{-1}R_{\pi}-\delta_{s_{0}=s}^{\top}(I-\gamma
T_{\beta})^{-1}R_{\beta}\\\ =&\delta_{s_{0}=s}^{\top}\left((I-\gamma
T_{\pi})^{-1}-(I-\gamma
T_{\beta})^{-1}\right)R_{\pi}+\delta_{s_{0}=s}^{\top}(I-\gamma
T_{\beta})^{-1}\left(R_{\pi}-R_{\beta}\right)\\\
=&\gamma\cdot\mathbb{E}_{T,\beta}\left[\sum_{t=0}^{\infty}\gamma^{t}\lambda(s_{t},a_{t})\cdot\frac{\rho(a_{t}|s_{t})-\beta(a_{t}|s_{t})}{\beta(a_{t}|s_{t})}\cdot
V_{\pi}(s_{t+1})\mid s_{0}=s\right]\\\
&\quad+\mathbb{E}_{T,\beta}\left[\sum_{t=0}^{\infty}\gamma^{t}\lambda(s_{t},a_{t})\cdot\frac{\rho(a_{t}|s_{t})-\beta(a_{t}|s_{t})}{\beta(a_{t}|s_{t})}\cdot
R(s_{t},a_{t})\mid s_{0}=s\right]\\\
=&\mathbb{E}_{T,\beta}\left[\sum_{t=0}^{\infty}\gamma^{t}\lambda(s_{t},a_{t})\cdot\frac{\rho(a_{t}|s_{t})-\beta(a_{t}|s_{t})}{\beta(a_{t}|s_{t})}\cdot
Q_{\pi}(s_{t},a_{t})\mid s_{0}=s\right]\\\
=&\mathbb{E}_{T,\beta}\left[\sum_{t=0}^{\infty}\gamma^{t}\lambda(s_{t},a_{t})\cdot\frac{\rho(a_{t}|s_{t})-\beta(a_{t}|s_{t})}{\beta(a_{t}|s_{t})}\cdot
A_{\pi}(s_{t},a_{t})\mid s_{0}=s\right].\end{split}$ (13)

The second equality follows from the fact that
$Q_{\pi}(s,a)=R(s,a)+\gamma\sum_{s^{\prime}\in
S}T(s^{\prime}|s,a)V_{\pi}(s^{\prime}).$ The third equality follows from the
result in Lemma 5 and the fact that for any state $s\in S$, $(I-\gamma
T_{\pi})^{-1}R_{\pi}(s)=V_{\pi}(s)$. The last equality is based on the fact of
the confidence constraint that

$\mathbb{E}_{T,\beta}\left[\sum_{t=0}^{\infty}\gamma^{t}V_{\pi}(s_{t})\cdot\sum_{a}\lambda(s_{t},a)\cdot(\rho(a|s_{t})-\beta(a|s_{t}))\mid
s_{0}=s\right]=0,\,\,\forall s\in S.$

###  A.2 Proof of Theorem 2

Denote by $V_{\pi}$ and $V_{\beta}$ the vectors of value functions
$V_{\pi}(s)$ and $V_{\beta}(s)$ at every state $s\in S$ respectively. Re-
writing the result in (13) in matrix form, it can be expressed as

$V_{\pi}-V_{\beta}=(I-\gamma T_{\beta})^{-1}\left(\Delta
R_{\beta,\rho,\lambda}+\gamma\Delta
T_{\beta,\rho,\lambda}V_{\beta}+\gamma\Delta
T_{\beta,\rho,\lambda}(V_{\pi}-V_{\beta})\right),$

where for any state $s\in S$, $\Delta
R_{\beta,\rho,\lambda}(s)=\sum_{a}\beta(a|s)\cdot\lambda(s,a)\cdot\frac{\rho(a|s)-\beta(a|s)}{\beta(a|s)}\cdot
R(s,a)$, and $\Delta T_{\beta,\rho,\lambda}(s^{\prime}|s)=\sum_{a\in
A}T(s^{\prime}|s,a)\beta(a|s)\cdot\lambda(s,a)\cdot\frac{\rho(a|s)-\beta(a|s)}{\beta(a|s)}$.
This expression implies that

$(I-(I-\gamma T_{\beta})^{-1}\gamma\Delta
T_{\beta,\rho,\lambda})(V_{\pi}-V_{\beta})=(I-\gamma T_{\beta})^{-1}(\Delta
R_{\beta,\rho,\lambda}+\gamma\Delta T_{\beta,\rho,\lambda}V_{\beta}),$

which further implies that

$V_{\pi}-V_{\beta}=(I-(I-\gamma T_{\beta})^{-1}\gamma\Delta
T_{\beta,\rho,\lambda})^{-1}(I-\gamma T_{\beta})^{-1}\left(\Delta
R_{\beta,\rho,\lambda}+\gamma\Delta T_{\beta,\rho,\lambda}V_{\beta}\right).$

Here based on the definition of $\Delta T_{\beta,\rho,\lambda}$ and the
confidence constraint, one can show that $(T_{\beta}+\Delta
T_{\beta,\rho,\lambda})$ is a stochastic matrix (all the elements are non-
negative, and $\sum_{s^{\prime}\in S}(T_{\beta}+\Delta
T_{\beta,\rho,\lambda})(s^{\prime}|s)=1$, $\forall s\in S$). Therefore the
matrix $(I-(I-\gamma T_{\beta})^{-1}\gamma\Delta T_{\beta,\rho,\lambda})$ is
invertible.

Using the matrix inversion lemma, one has the following equality:

$(I-(I-\gamma T_{\beta})^{-1}\cdot\gamma\cdot\Delta
T_{\beta,\rho,\lambda})^{-1}=(I-\gamma(T_{\beta}+\Delta
T_{\beta,\rho,\lambda}))^{-1}(I-\gamma T_{\beta}).$

Therefore the difference of value function $V_{\pi}-V_{\beta}$ can further be
expressed as

$V_{\pi}-V_{\beta}=(I-\gamma T_{\beta}-\gamma\Delta
T_{\beta,\rho,\lambda})^{-1}\left(\Delta R_{\beta,\rho,\lambda}+\gamma\Delta
T_{\beta,\rho,\lambda}V_{\beta}\right).$

In other words, at any state $s\in S$, the corresponding value function
$V_{\pi}(s)$ is given by the following expression:

$\begin{split}V_{\pi}(s)-V_{\beta}(s)=&\mathbb{E}\left[\sum_{t=0}^{\infty}\gamma^{t}\left(\Delta
R_{\beta,\rho,\lambda}+\gamma\Delta
T_{\beta,\rho,\lambda}V_{\beta}\right)(s_{t})\mid
T^{\prime}_{\beta,\rho},s_{0}=s\right]\\\
=&\mathbb{E}\left[\sum_{t=0}^{\infty}\gamma^{t}\Delta
Q_{\beta,\rho,\lambda}(s_{t},a_{t})\mid
T^{\prime}_{\beta,\rho},s_{0}=s\right]\\\
=&\mathbb{E}\left[\sum_{t=0}^{\infty}\gamma^{t}\Delta
A_{\beta,\rho,\lambda}(s_{t},a_{t})\mid
T^{\prime}_{\beta,\rho},s_{0}=s\right],\end{split}$ (14)

where the transition probability
$T^{\prime}_{\beta,\rho}(s^{\prime}|s)=(T_{\beta}+\Delta
T_{\beta,\rho,\lambda})(s^{\prime}|s)$ is given by $\sum_{a\in
A}\beta(a|s)\cdot
T(s^{\prime}|s,a)\cdot\left(1+\lambda(s,a)\cdot\frac{\rho(a|s)-\beta(a|s)}{\beta(a|s)}\right)$
at state-next-state pair $(s,s^{\prime})$. By noticing that
$T^{\prime}_{\beta,\rho}(s^{\prime}|s)$ is indeed $T_{\pi}(s^{\prime}|s)$ (the
transition probability that is induced by residual policy $\pi$), the proof of
Theorem 2 is completed.

##  Appendix B Proofs for Results in Section 4

###  B.1 Proof of Theorem 4

Define the state-action discounted stationary distribution w.r.t. an arbitrary
policy $\pi$ as
$d_{\pi}(s,a)=(1-\gamma)\sum_{t=0}^{\infty}\gamma^{t}\mathbb{P}(s_{t}=s,a_{t}=a|s_{0}\sim
P_{0},\pi)$ and its state-only counterpart as $d_{\pi}(s)=\sum_{a\in
A}d_{\pi}(s,a)\pi(a|s)$. Immediately one can write the difference of return
(objective function of this problem) with the following chain of
equalities/inequalities:

$\displaystyle\mathbb{E}\left[\sum_{t=0}^{\infty}\gamma^{t}\Delta
A_{\beta,\rho,\lambda}(s_{t})\mid T,\pi,s_{0}\sim P_{0}\right]$
$\displaystyle=\frac{1}{1-\gamma}\sum_{s\in S}d_{\pi}(s)\Delta
A_{\beta,\rho,\lambda}(s)$ $\displaystyle=\frac{1}{1-\gamma}\sum_{s\in
S}d_{\beta}(s)\Delta A_{\beta,\rho,\lambda}(s)+(d_{\pi}(s)-d_{\beta}(s))\Delta
A_{\beta,\rho,\lambda}(s).$

Recall that $\Delta T_{\beta,\rho,\lambda}(s^{\prime}|s)=\sum_{a\in
A}T(s^{\prime}|s,a)\beta(a|s)\cdot\lambda(s,a)\cdot\frac{\rho(a|s)-\beta(a|s)}{\beta(a|s)}$.
At any state $s\in S$, the difference of stationary distribution
$d_{\pi}(s)-d_{\beta}(s)$ can be further expressed as

$\begin{split}(d_{\pi}-d_{\beta}&)(s)=P_{0}^{\top}\left((I-\gamma
T_{\pi})^{-1}-(I-\gamma T_{\beta})^{-1}\right)(s)\\\
=&P_{0}^{\top}\big{(}(I-\gamma T_{\beta})^{-1}+(I-\gamma
T_{\beta})^{-1}\gamma\Delta T_{\beta,\rho,\lambda}(I-(I-\gamma
T_{\beta})^{-1}\gamma\Delta T_{\beta,\rho,\lambda})^{-1}\cdot\\\
&\qquad\qquad(I-\gamma T_{\beta})^{-1}-(I-\gamma T_{\beta})^{-1}\big{)}(s)\\\
=&P_{0}^{\top}\left((I-\gamma T_{\beta})^{-1}\gamma\Delta
T_{\beta,\rho,\lambda}(I-(I-\gamma T_{\beta})^{-1}\gamma\Delta
T_{\beta,\rho,\lambda})^{-1}(I-\gamma T_{\beta})^{-1}\right)(s).\end{split}$

Let
$D_{\beta}=\left\\{(1-\gamma)\mathbb{E}[\sum_{t=0}^{\infty}\gamma^{t}\mathbb{P}(s_{t}=s^{\prime}|s_{0}=s,\beta)]\right\\}_{s,s^{\prime}\in
S}$ be the occupation measure matrix induced by $\beta$. Combining the above
arguments one has

$\displaystyle\left|\langle d_{\pi}-d_{\beta},\Delta
A_{\beta,\rho,\lambda}\rangle\right|$ (15) $\displaystyle=$
$\displaystyle\left|\langle P_{0}^{\top}(I-\gamma T_{\beta})^{-1}\gamma\Delta
T_{\beta,\rho,\lambda}(I-(I-\gamma T_{\beta})^{-1}\gamma\Delta
T_{\beta,\rho,\lambda})^{-1}(I-\gamma T_{\beta})^{-1},\Delta
A_{\beta,\rho,\lambda}\rangle\right|$ $\displaystyle=$
$\displaystyle\frac{1}{1-\gamma}\left|\langle
P_{0}^{\top}D_{\beta}\gamma\Delta
T_{\beta,\rho,\lambda}((1-\gamma)I-D_{\beta}\gamma\Delta
T_{\beta,\rho,\lambda})^{-1},D_{\beta}\Delta
A_{\beta,\rho,\lambda}\rangle\right|$ $\displaystyle=$
$\displaystyle\frac{\gamma}{1-\gamma}\left|\langle P_{0}^{\top}D_{\beta}\Delta
T_{\beta,\rho,\lambda},\left(I-\gamma\left(I+D_{\beta}\Delta
T_{\beta,\rho,\lambda}\right)\right)^{-1}D_{\beta}\Delta
A_{\beta,\rho,\lambda}\rangle\right|.$

Now $I+D_{\beta}\Delta T_{\beta,\rho,\lambda}$ is a stochastic matrix, which
is because for any state $s\in S$,

$\displaystyle(D_{\beta}\Delta T_{\beta,\rho,\lambda}e)(s)$
$\displaystyle=(1-\gamma)\mathbb{E}\left[\sum_{t=0}^{\infty}\gamma^{t}\sum_{s^{\prime}}\Delta
T_{\beta,\rho,\lambda}(s^{\prime}|s)\mid T,\beta,s_{0}=s\right]$
$\displaystyle=(1-\gamma)\mathbb{E}\left[\sum_{t=0}^{\infty}\gamma^{t}\sum_{a\in
A}\lambda(s,a)\cdot(\rho(a|s)-\beta(a|s))\mid T,\beta,s_{0}=s\right]$
$\displaystyle=0.$

Using this property one can upper bound the magnitude of each element of
matrix $\left(I-\gamma\left(I+D_{\beta}\Delta
T_{\beta,\rho,\lambda}\right)\right)^{-1}$ by $\frac{1}{1-\gamma}$. Therefore,
using Holder inequality one can further upper bound the expression in (15) as
follows:

$\displaystyle\left|\langle d_{\pi}-d_{\beta},\Delta
A_{\beta,\rho,\lambda}\rangle\right|$
$\displaystyle\leq\frac{\gamma}{(1-\gamma)^{2}}\left\|P_{0}^{\top}D_{\beta}\Delta
T_{\beta,\rho,\lambda}\right\|_{1}\cdot\left\|D_{\beta}\Delta
A_{\beta,\rho,\lambda}\right\|_{\infty}$
$\displaystyle\leq\frac{\gamma}{(1-\gamma)^{2}}\sum_{s\in S,a\in
A}d_{\beta}(s)\beta(a|s)\cdot\lambda(s,a)\cdot\frac{|\rho(a|s)-\beta(a|s)|}{\beta(a|s)}\cdot\max_{s_{0}\in
S}\sum_{s\in S}d_{\beta}(s|s_{0})\left|\Delta A_{\beta,\rho,\lambda}\right|.$

Plugging in the definition of the discounted occupation measure w.r.t. $\beta$
into the above expression, the proof is this theorem is completed.

##  Appendix C Practical Implementation Details of BRPO

In this section, we discuss several practical techniques to further boost
training stability and effectiveness of BRPO.

#### Improving CPI with Optimal Advantage

The derivation in Section 4 and Section 5 shows that optimizing
$\mathcal{L}_{\beta,\rho,\lambda}$ finds a residual policy that performs no-
worse than the behavior policy (modulo any Lagrangian approximation error).
While we argue that this optimization is less conservative than existing
methods (like TRPO) due to the state-action-dependent learned confidence, it
might not be aggressive enough in leveraging the function approximation to
generalize to unseen state and action. One major reason is that by design,
$\mathcal{L}_{\beta,\rho,\lambda}$ only uses the long-term value of $\beta$
(in the form of $A_{\beta}$), in order to circumvent the issue of bad
generalization to unseen state-action pair. This also makes policy improvement
local to $\beta$. This is a fundamental challenge of batch RL, but can be
relaxed depending on the domain. As a remedy to this issue, by a convex
ensemble of the results from Lemma 1 and Theorem 2 (with any combination
weight $\mu\in[0,1]$), notice that the difference-return also satisfies

$J_{\pi}-J_{\beta}\geq\frac{1}{1-\gamma}\left(\widetilde{L}^{\prime}_{\mu,\beta,\rho,\lambda}-\frac{\gamma(1-\mu)}{1-\gamma}L^{\prime\prime}_{\beta,\rho,\lambda}\max_{s_{0}\in
S}\,L^{\prime\prime\prime}_{\beta,\rho,\lambda}(s_{0})\right),$

where

$\widetilde{L}^{\prime}_{\mu,\beta,\rho,\lambda}:=\mathbb{E}_{(s,a)\sim
d_{\beta}}\left[\lambda(s,a)\cdot\frac{\rho(a|s)-\beta(a|s)}{\beta(a|s)}\cdot
W(s,a)\right]$

with a _weighted advantage_ function $W:=(1-\mu)A_{\beta}+\mu A_{\pi}$.
Therefore, without loss of generality one can replace $A_{\beta}$ in
$\mathcal{L}_{\beta,\rho,\lambda}$ with the weighted advantage function.
Furthermore, to avoid estimating $A_{\pi}$ at each policy update and assuming
that CPI eventually finds $\pi\rightarrow\pi^{*}$, one may directly estimate
the optimal weighted advantage function

$W_{\pi^{*}}(s,a)=Q_{\mu,\beta,\pi^{*}}(s,a)-V_{\mu,\beta,\pi^{*}}(s),$

in which the value function $Q_{\mu,\beta,\pi^{*}}$ is a Bellman fixed-point
of $Q(s,a)=R(s,a)+\gamma\sum_{s^{\prime}}T(s^{\prime}|s,a)V(s^{\prime})$, with

$V(s)=(1-\mu)\mathbb{E}_{a\sim\beta}[Q(s,a)]+\mu\max_{a}Q(s,a).$

This approach of combining the optimal Bellman operator with the on-policy
counterpart belongs to the general class of hybrid on/off-policy RL algorithms
(O’Donoghue et al., 2016).

Therefore, we learn an advantage function $W$ that is a weighted combination
of $A_{\beta}$ and $A_{\pi^{*}}$. Using the batch data $B$, the expected
advantage $A_{\beta}$ can be learned with any critic-learning technique, such
as SARSA (Sutton and Barto, 2018). We can learn $A_{\pi^{*}}$ by DQN (Mnih et
al., 2013) or other Q-learning algorithm. We provide pseudo-code of our BRPO
algorithm in Algorithm 1.

##  Appendix D Experimental Details

This section describes more details about our experimental setup to evaluate
the algorithms.

###  D.1 Behavior policy

We train the behavior policy using DQN, using architecture and hyper-
parameters specified in Section D.2. The behavior policy was trained for each
task until the performance reaches around 75% of the optimal performance
similar to Fujimoto et al. (2018) and Kumar et al. (2019). Specifically, we
trained the behavior policy for 100,000 steps for Lunarlander-v2, and 50,000
steps for Cartpole-v1 and Acrobot-v1. We used two-layers MLP with
FC($32$)-FC($16$). The replay buffer size is $500,000$ and batch size is $64$.
The performance of the behavior policies are given in Table 1.

###  D.2 Hyperparameters

For fair comparison, we generally used the same set of hyper-parameters and
architecture across all methods and experiments, which are defined in Table 2
and Table 3. Similar to the behavior policy, we used two-layers MLP with
FC(32)-FC(16) for all the critic agents and Behavioral cloning agent’s policy.
The final hyperparameters are found using grid search, with candidate set
specified in Table 2 and Table 3.

Hyperparameters for BC, BCQ, SARSA, DQN, and KL-Q | Sweep range | Final value
---|---|---
Soft target update rate ($\tau$) | - | 0.5
Soft target update period | 150, 500, 1500 | 500
Discount factor | - | 0.99
Mini-batch size | - | 64
Q-function learning rates | 0.0003, 0.001, 0.002 | 0.001
Neural network optimizer | - | Adam
[BCQ] Behavior policy threshold ($\tau$ in Fujimoto et al. (2019)) | 0.1, 0.2, 0.3, 0.4 | 0.3
[SPIBB] Bootstrapping set threshold | 0.1, 0.2, 0.3, 0.4 | 0.2
[KL-Q] KL-regularization weight | 0.01, 0.03, 0.1, 0.3 | 0.1
Table 2: The range of hyperparameters sweeped over and the final hyperparameters used for the baselines (BC, BCQ, SARSA, DQN, and KL-Q). Hyperparameters for BRPO and BRPO-C | Sweep range | Final value
---|---|---
Soft target update rate ($\tau$) | - | 0.5
Soft target update period | 150, 500, 1500 | 500
Discount factor | - | 0.99
Mini-batch size | - | 64
Q-function learning rates | 0.0003, 0.001, 0.002 | 0.001
Neural network optimizer | - | Adam
[BRPO, BRPO-C] Mixing $\mu$ (for critic training) | 0.1, 0.5, 0.9 | 0.9
[BRPO] Confidence $\lambda_{\phi}(s,a)$ learning rates | 0.0002, 0.0001 | 0.0001
[BRPO-C] Constant $\lambda$ (for constant residual policy) | 0.25, 0.33, 0.5, 0.66, 0.75 | 0.5
Table 3: The range of hyperparameters sweeped over and the final
hyperparameters used for the proposed methods (BRPO and BRPO-C).

##  Appendix E Additional Results

Here are the learning curves for each environment and behavior policy over the
course of batch training.

Figure 1:  The mean $\pm$ standard error (shadowed area) of average return for
each environment and behavior policy $\varepsilon$-exploration.