# Kernel Metric Learning for In-Sample Off-Policy Evaluation of Deterministic
RL Policies

Haanvid Lee1, Tri Wahyu Guntara1, Jongmin Lee2, Yung-Kyun Noh3,4, Kee-Eung
Kim1
1KAIST, 2UC Berkeley, 3Hanyang Univ., 4KIAS
{haanvid<EMAIL_ADDRESS><EMAIL_ADDRESS>
<EMAIL_ADDRESS><EMAIL_ADDRESS>

###### Abstract

We consider off-policy evaluation (OPE) of deterministic target policies for
reinforcement learning (RL) in environments with continuous action spaces.
While it is common to use importance sampling for OPE, it suffers from high
variance when the behavior policy deviates significantly from the target
policy. In order to address this issue, some recent works on OPE proposed in-
sample learning with importance resampling. Yet, these approaches are not
applicable to deterministic target policies for continuous action spaces. To
address this limitation, we propose to relax the deterministic target policy
using a kernel and learn the kernel metrics that minimize the overall mean
squared error of the estimated temporal difference update vector of an action
value function, where the action value function is used for policy evaluation.
We derive the bias and variance of the estimation error due to this relaxation
and provide analytic solutions for the optimal kernel metric. In empirical
studies using various test domains, we show that the OPE with in-sample
learning using the kernel with optimized metric achieves significantly
improved accuracy than other baselines.

##  1 Introduction

Off-policy evaluation (OPE) aims to assess the performance of a target policy
by using offline data sampled from a separate behavior policy, without the
target policy interacting with the environment (Su et al., 2020; Fujimoto et
al., 2021). OPE has gained considerable significance due to the potential
costs and risks associated with a reinforcement learning (RL) agent
interacting with real-world environments when evaluating a policy in domains
such as healthcare (Zhao et al., 2009; Murphy et al., 2001), education (Mandel
et al., 2014), robotics (Yu et al., 2020), and recommendation systems
(Swaminathan et al., 2017). In the context of offline RL, OPE plays a vital
role since the RL agent lacks access to an environment. Moreover, OPE can be
leveraged for policy selection (Konyushova et al., 2021) and to evaluate
policies prior to their deployment in real-world settings.

While OPE has been actively studied, OPE regarding deterministic target
policies has not been extensively studied, and existing OPE algorithms either
do not work or show low performance on evaluating deterministic policies
(Schlegel et al., 2019; Fujimoto et al., 2021). However, there are many cases
where deterministic policies are required. For example, safety-critical
systems such as industrial robot control systems require precise and
consistent control of action sequences without introducing variability (Silver
et al., 2014). Therefore, the need for OPE of deterministic policies emerges.
In this paper, we consider evaluating a deterministic policy with offline
data.

Most of the recent works on OPE use the marginalized importance sampling (MIS)
approach (Xie et al., 2019; Nachum et al., 2019; Zhang et al., 2020). This
approach learns density ratios between the state-action distributions of the
target policy and the sampling distribution to reweight the rewards in the
data. Since the MIS methods use a single correction ratio, they have a lower
variance than vanilla importance sampling (IS) methods, which use products of
IS ratios of actions in trajectories (Precup et al., 2001). However, these
methods are vulnerable to training instability due to optimizing the minimax
objective. SR-DICE (Fujimoto et al., 2021) avoided optimizing the minimax
objective by adopting a successor representation learning scheme. However, SR-
DICE may use out-of-distribution samples in learning successor representation
and thus may suffer from an extrapolation error.

In-sample learning methods learn Q-functions using only the samples in the
data, avoiding extrapolation error (Schlegel et al., 2019; Zhang et al.,
2023). The methods employ an IS ratio to correct the distribution of an action
used for querying the Q-value in a temporal difference (TD) target to learn
the Q-function. Since a single IS ratio is used, the method has lower variance
than the traditional IS approaches (Precup et al., 2001). However, a
limitation of these methods is their inapplicability to deterministic target
policies, as the IS ratios of actions are almost surely zeros. To overcome
this limitation, we aim to extend the use of IR to learn the Q-function in FQE
(Voloshin et al., 2019; Le et al., 2019) style specifically tailored for
deterministic target policies.

In this study, we introduce Kernel Metric learning for In-sample Fitted Q
Evaluation (KMIFQE), a novel approach that enables in-sample FQE using offline
data. Our contribution is twofold: 1) enabling in-sample OPE of deterministic
policies by kernel relaxation and metric learning that has not been used in
MDP settings (Kallus & Zhou, 2018; Lee et al., 2022), 2) providing the
theoretical guarantee of the proposed method. In theoretical studies, we first
derive the MSE of our estimator with kernel relaxation applied on a target
policy to avoid having zero IS ratios. From the MSE, we derive the optimal
metric scale, referred to as bandwidth, which balances between bias and
variance of the estimation and reduces the derived MSE. Then, we derive the
optimal metric shape, referred to as metric, which minimizes the bias induced
by the relaxation. Lastly, we show the error bound of the estimated Q-function
compared to the true Q-function of a target policy. For empirical studies, we
evaluate KMIFQE using a modified classic control domain sourced from OpenAI
Gym (Brockman et al., 2016). This evaluation serves to verify that the metrics
and bandwidths are learned as intended. Furthermore, we conduct experiments on
a more complex MuJoCo domain (Todorov et al., 2012). The experimental results
demonstrate the effectiveness of our metric learning approach.

##  2 Related Work

Marginalized importance sampling for OPE in RL Marginalized importance
sampling (MIS) OPE method was first introduced by Liu et al. (2018). They
pointed out that the importance sampling (IS) OPE estimation in RL suffers
from the "curse of horizon" due to products of IS ratios used for the IS. They
avoided the problem by learning a correction ratio for the marginalized state
distribution, which corrects the marginalized state distribution induced by a
behavior policy to that of a target policy. Their work was limited in that it
required a known behavior policy. Subsequent studies in MIS learned
marginalized state-action distribution correction ratios and estimated policy
values in a behavior-agnostic manner (Nachum et al., 2019; Zhang et al., 2020;
Yang et al., 2020). However, the methods required optimization of minimax
learning objectives, which caused instability in learning. SR-DICE (Fujimoto
et al., 2021) avoided the minimax learning objective by using the concept of
successor representation and made the learning process more stable. However,
their result showed that FQE (Voloshin et al., 2019; Le et al., 2019)
outperforms all MIS methods in a MuJoCo domain (Todorov et al., 2012) when the
target policy is deterministic.

In-sample learning for OPE in RL In-sample learning methods (Schlegel et al.,
2019; Zhang et al., 2023) learn a Q-function of a target policy by using the
semi-gradients from expected SARSA temporal-difference (TD) learning loss
computed on samples in the data. With importance resampling (IR), the methods
correct the distribution of TD update vectors before updating the Q-function
rather than reweighting the TD update vectors with IS ratios. They show that
IR estimation of the TD update vector has a lower variance than the IS
reweighted TD update vectors, resulting in more accurate Q-function
estimation. However, these methods cannot be applied to the case where the
target policy is deterministic since the IS ratios are zeros almost surely.

Kernel metric learning for OPE in contextual bandits The work of Kallus & Zhou
(2018) first enabled IS to estimate the expected rewards for a deterministic
target policy. They derived the MSE of the IS estimation when a kernel relaxes
the target policy distribution. Then, they derived the optimal bandwidth
(scale of the kernel metric) that minimizes it. Subsequent work by Lee et al.
(2022) learned a shape of the kernel as a Mahalanobis distance metric
(Mahalanobis, 1936; De Maesschalck et al., 2000) that further reduces MSE by
reducing the bias of the estimate. These works cannot be directly applied to
OPE in RL since that would result in IS estimations using products of IS
ratios to correct the distributions of action sequences in trajectories
sampled by a behavior policy. As the episode length becomes longer, more IS
ratios are multiplied, and this causes the curse of horizon problem (Liu et
al., 2018).

##  3 Background

We seek to evaluate a deterministic target policy that operates in continuous
action spaces given offline data sampled with a separate behavior policy.
Specifically, we consider the MDP
$\mathcal{M}=\langle\mathcal{S},\mathcal{A},P,R,p_{0},\gamma\rangle$ composed
of a set of states $\mathcal{S}\in\mathbb{R}^{q}$, set of actions
$\mathcal{S}\in\mathbb{R}^{d}$, reward function
$R:\mathcal{S}\times\mathcal{A}\rightarrow\mathbb{R}$, state transition
probability $P:\mathcal{S}\times\mathcal{A}\rightarrow\Delta(\mathcal{S})$,
initial state distribution $p_{0}\in\Delta(\mathcal{S})$, and a discount
factor $\gamma\in[0,1)$. We assume that the offline data
$\mathcal{D}=\left\\{\left(\operatorname*{\mathbf{s}}_{i},\operatorname*{\mathbf{a}}_{i},r_{i},\operatorname*{\mathbf{s}}_{i}^{\prime},\operatorname*{\mathbf{a}}_{i}^{\prime}\right)\right\\}_{i=1}^{n}$
is sampled from the MDP $\mathcal{M}$ by using a stochastic behavior policy
$\mu:\mathcal{S}\rightarrow\Delta(\mathcal{A})$. And $\mathcal{D}$ is used to
evaluate the deterministic target policy
$\tilde{\pi}:\mathcal{S}\rightarrow\mathcal{A}$. The distribution of the
target policy is denoted as $\pi:\mathcal{S}\rightarrow\Delta(\mathcal{A})$.
The goal is to evaluate the target policy as the normalized expected per-step
reward
$V(\pi)=(1-\gamma)\mathbb{E}_{\pi}\left[\sum_{t=0}^{\infty}\gamma^{t}R\left(\mathbf{s}_{t},\mathbf{a}_{t}\right)\right]$,
where $\mathbb{E}_{\pi}[\cdot]$ is the expectation using the data sampled from
$\mathcal{M}$ with $\pi$. The target policy value can be represented with an
Q-function $V(\pi)=(1-\gamma)\mathbb{E}_{\mathbf{s}_{0}\sim
p_{0}(\mathbf{s}_{0}),\operatorname*{\mathbf{a}}_{0}\sim\pi(\operatorname*{\mathbf{a}}_{0}|\operatorname*{\mathbf{s}}_{0})}\left[Q^{\pi}\left(\mathbf{s}_{0},\mathbf{a}_{0}\right)\right]$,
where the Q-function is defined as
$Q^{\pi}(\operatorname*{\mathbf{s}},\operatorname*{\mathbf{a}}):=\mathbb{E}_{\pi}\left[\sum_{t=0}^{\infty}\gamma^{t}R\left(\mathbf{s}_{t},\mathbf{a}_{t}\right)|\operatorname*{\mathbf{s}}_{0}=\operatorname*{\mathbf{s}},\operatorname*{\mathbf{a}}_{0}=\operatorname*{\mathbf{a}}\right]$.
This work estimates a Q-function to evaluate the target policy value.

###  3.1 In-sample TD learning

Temporal difference (TD) learning can be used for estimating $Q^{\pi}$ (Zhang
et al., 2023). FQE learns a Q-function by minimizing the following TD loss
$\mathcal{L}_{TD}(\theta)$ (Voloshin et al., 2019; Le et al., 2019):

$\displaystyle\mathcal{L}_{TD}(\theta)$
$\displaystyle=\mathbb{E}_{\left(\mathbf{s},\mathbf{a},\mathbf{s}^{\prime}\right)\sim
p_{\mu}}\left[\left(R(\mathbf{s},\mathbf{a})+\gamma\mathbb{E}_{\mathbf{a}^{\prime}\sim\pi\left({\operatorname*{\mathbf{a}}}^{\prime}\mid\mathbf{s}^{\prime}\right)}\left[Q_{\bar{\theta}}\left(\mathbf{s}^{\prime},\mathbf{a}^{\prime}\right)\right]-Q_{\theta}(\mathbf{s},\mathbf{a})\right)^{2}\right],$
(1)

where $Q_{\theta}$ is Q-function parameterized by $\theta$, $Q_{\bar{\theta}}$
is a frozen target network, a transition data sampling distribution is defined
as
$p_{\mu}:=d^{\mu}(\operatorname*{\mathbf{s}})\mu(\operatorname*{\mathbf{a}}|\operatorname*{\mathbf{s}})P(\operatorname*{\mathbf{s}}^{\prime}|\operatorname*{\mathbf{s}},\operatorname*{\mathbf{a}})p(r|\operatorname*{\mathbf{s}},\operatorname*{\mathbf{a}})\mu(\operatorname*{\mathbf{a}}^{\prime}|\operatorname*{\mathbf{s}}^{\prime})$,
and the stationary distribution of state induced by $\mu$ is:

$\displaystyle
d^{\mu}(\mathbf{s}):=(1-\gamma)\sum_{t=0}^{\infty}\gamma^{t}p\left(\mathbf{s}_{t}=\mathbf{s}\mid\mathbf{s}_{0}\sim
p_{0}\left(\mathbf{s}_{0}\right),\mathbf{s}_{t}\sim
P\left(\mathbf{s}_{t}\mid\mathbf{s}_{t-1},\mathbf{a}_{t-1}\right),\mathbf{a}_{t}\sim\pi\left(\mathbf{a}_{t}\mid\mathbf{s}_{t}\right)\right).$
(2)

In Eq. (1), $Q_{\theta}$ is trained only on
$(\operatorname*{\mathbf{s}},\operatorname*{\mathbf{a}})\sim
d^{\mu}(\operatorname*{\mathbf{s}})\mu(\operatorname*{\mathbf{a}}|\operatorname*{\mathbf{s}})$
while $Q_{\bar{\theta}}$ needs to be evaluated on out-of-distribution (OOD)
samples
$(\operatorname*{\mathbf{s}}^{\prime},\operatorname*{\mathbf{a}}^{\prime})\sim
d^{\mu}(\operatorname*{\mathbf{s}}^{\prime})\pi(\operatorname*{\mathbf{a}}^{\prime}|\operatorname*{\mathbf{s}}^{\prime})$
to compute the loss. Therefore, it may suffer from distributional shift and
may produce inaccurate Q-values (Levine et al., 2020).

To avoid using OOD samples while computing the update vector for $Q_{\theta}$,
gradient of $\mathcal{L}_{TD}(\theta)$ w.r.t. $\theta$, or the TD update
vector $\Delta_{TD}$, can be represented with an IS ratio
$w(\operatorname*{\mathbf{s}},\operatorname*{\mathbf{a}}):=\frac{\pi(\operatorname*{\mathbf{a}}|\operatorname*{\mathbf{s}})}{\mu(\operatorname*{\mathbf{a}}|\operatorname*{\mathbf{s}})}$:

$\displaystyle\Delta_{TD}$ $\displaystyle=\mathbb{E}_{x\sim
p_{\mu}}\Big{[}w\left(\mathbf{s}^{\prime},\mathbf{a}^{\prime}\right)\underbrace{\left(R(\mathbf{s},\mathbf{a})+\gamma
Q_{\bar{\theta}}\left(\mathbf{s}^{\prime},\mathbf{a}^{\prime}\right)-Q_{\theta}(\mathbf{s},\mathbf{a})\right)\nabla_{\theta}Q_{\theta}(\mathbf{s},\mathbf{a})}_{=:\Delta(x)}\Big{]},$
(3)

where a transition in the data is
$x:=\\{\operatorname*{\mathbf{s}},\operatorname*{\mathbf{a}},r,\operatorname*{\mathbf{s}}^{\prime},\operatorname*{\mathbf{a}}^{\prime}\\}$,
$\Delta(x)$ is the semi-gradient of the transition $x$. By the importance
ratio $w$, the data sampling distribution of $p_{\mu}$ is corrected to the
distribution of
$p_{\pi}:=d^{\mu}(\operatorname*{\mathbf{s}})\mu(\operatorname*{\mathbf{a}}|\operatorname*{\mathbf{s}})P(\operatorname*{\mathbf{s}}^{\prime}|\operatorname*{\mathbf{s}},\operatorname*{\mathbf{a}})p(r|\operatorname*{\mathbf{s}},\operatorname*{\mathbf{a}})\pi(\operatorname*{\mathbf{a}}^{\prime}|\operatorname*{\mathbf{s}}^{\prime})$.

In-sample TD learning (Schlegel et al., 2019; Zhang et al., 2023) uses IR to
estimate $\Delta_{TD}$ as $\widehat{\Delta}_{IR}$:

$\displaystyle\widehat{\Delta}_{IR}$
$\displaystyle=\frac{\bar{w}}{k}\sum_{j=1}^{k}\Delta\left(\bar{x}_{j}\right),\quad\bar{x}_{j}\stackrel{{\scriptstyle\rho}}{{\sim}}\left\\{x_{1},\ldots,x_{n}\right\\}\text{
with probability
}\rho_{j}=\frac{w\left(\mathbf{s}_{j}^{\prime},\mathbf{a}_{j}^{\prime}\right)}{\sum_{i=1}^{n}w\left(\mathbf{s}_{i}^{\prime},\mathbf{a}_{i}^{\prime}\right)},$
(4)

where
$\bar{w}:=\frac{1}{n}\sum_{i=1}^{n}w(\operatorname*{\mathbf{s}}_{i}^{\prime},\operatorname*{\mathbf{a}}_{i}^{\prime})$
is the bias correction term that corrects the bias induced by resampling from
a finite data $\mathcal{D}$ with size $n$.

###  3.2 Kernel metric learning

As the IS ratios used for in-sample learning (Schlegel et al., 2019; Zhang et
al., 2023) are almost surely zeros for a deterministic policy, it cannot be
directly applied to the evaluation of a deterministic target policy. In this
work, we enable in-sample learning to evaluate a deterministic target policy
by relaxing the density of the target policy in an IS ratio, which can be seen
as a Dirac delta function
$\pi(\operatorname*{\mathbf{a}}|\operatorname*{\mathbf{s}})=\delta(\operatorname*{\mathbf{a}}-\tilde{\pi}(\operatorname*{\mathbf{s}}))$,
by a Gaussian kernel (Eq. (5)). We assume that the support of
$\mu(\operatorname*{\mathbf{a}}|\operatorname*{\mathbf{s}})$ covers the
support of
$\frac{1}{h^{d}}K\left(\tfrac{L(\operatorname*{\mathbf{s}})^{\top}(\operatorname*{\mathbf{a}}-\tilde{\pi}(\operatorname*{\mathbf{s}}))}{h}\right)$
so the value of IS ratio is bounded. We seek to minimize the MSE between the
estimated TD update vector and the true TD update vector $\Delta_{TD}$ in Eq.
(3) by learning Mahalanobis metrics
$\tfrac{A(\operatorname*{\mathbf{s}})}{h^{2}}$ in their scales (hereafter
referred to as bandwidths) $h$ and metrics in their shapes (hereafter referred
to as metrics) $A(\operatorname*{\mathbf{s}})$ (Mahalanobis, 1936; De
Maesschalck et al., 2000), which is locally learned at each state
$\operatorname*{\mathbf{s}}$ (Eq. (6)). The metrics are locally learned at
each state $\operatorname*{\mathbf{s}}$ to reflect the Q-value landscape of
the target policy near the target actions
$\tilde{\pi}(\operatorname*{\mathbf{s}})$.

$\displaystyle
w(\operatorname*{\mathbf{s}},\operatorname*{\mathbf{a}})=\frac{\delta(\operatorname*{\mathbf{a}}-\tilde{\pi}(\operatorname*{\mathbf{s}}))}{\mu(\operatorname*{\mathbf{a}}|\operatorname*{\mathbf{s}})}$
$\displaystyle\approx\frac{1}{h^{d}\mu(\operatorname*{\mathbf{a}}|\operatorname*{\mathbf{s}})}K\left(\frac{L(\operatorname*{\mathbf{s}})^{\top}\left(\operatorname*{\mathbf{a}}-\tilde{\pi}(\operatorname*{\mathbf{s}})\right)}{h}\right),$
(5)
$\displaystyle\frac{1}{h^{d}}K\left(\frac{L(\operatorname*{\mathbf{s}})^{\top}(\operatorname*{\mathbf{a}}-\tilde{\pi}(\operatorname*{\mathbf{s}}))}{h}\right)$
$\displaystyle=\frac{1}{h^{d}(2\pi)^{\frac{d}{2}}}\exp\left(-\frac{(\operatorname*{\mathbf{a}}-\tilde{\pi}(\operatorname*{\mathbf{s}}))^{\top}A(\operatorname*{\mathbf{s}})(\operatorname*{\mathbf{a}}-\tilde{\pi}(\operatorname*{\mathbf{s}}))}{h^{2}}\right),$
(6)

where we assume that
$|A(\operatorname*{\mathbf{s}})|=1,A(\operatorname*{\mathbf{s}})\succ
0,A(\operatorname*{\mathbf{s}})^{\top}=A(\operatorname*{\mathbf{s}})$.
Applying Mahalanobis metric
($A(\operatorname*{\mathbf{s}})=L(\operatorname*{\mathbf{s}})L(\operatorname*{\mathbf{s}})^{\top}$)
to a Gaussian kernels can be viewed as linearly transforming the inputs with
the transformation matrix $L(\operatorname*{\mathbf{s}})$ as in Eq. (6) (Noh
et al., 2010; 2017).

##  4 Kernel metric learning for in-sample TD learning

Our work enables the in-sample estimation of TD update vector
$\widehat{\Delta}^{K}_{IR}$ with kernel relaxation and metric learning for
estimating $Q^{\pi}$ which is used to evaluate a deterministic target policy.
The in-sample estimation is enabled by relaxing the density of a deterministic
target policy in an importance sampling (IS) ratio in Eq. (4) by a Gaussian
kernel as in Eq. (5).

$\widehat{\Delta}_{IR}^{K}=\frac{\bar{w}^{K}}{k}\sum_{j=1}^{k}\Delta\left(\bar{x}_{j}\right),\quad\bar{x}_{j}\stackrel{{\scriptstyle\rho^{K}}}{{\sim}}x_{1},\ldots,x_{n}\text{
with probability
}\rho_{j}^{K}=\frac{w^{K}(\operatorname*{\mathbf{s}}_{j}^{\prime},\operatorname*{\mathbf{a}}_{j}^{\prime})}{\sum_{i=1}^{n}w^{K}(\operatorname*{\mathbf{s}}_{i}^{\prime},\operatorname*{\mathbf{a}}_{i}^{\prime})},$
(7)

where
$w^{K}(\operatorname*{\mathbf{s}}_{i}^{\prime},\operatorname*{\mathbf{a}}_{i}^{\prime}):=\tfrac{1}{h^{d}\mu(\operatorname*{\mathbf{a}}_{i}^{\prime}|\operatorname*{\mathbf{s}}_{i}^{\prime})}K\left(\tfrac{L(\operatorname*{\mathbf{s}}_{i}^{\prime})^{\top}(\operatorname*{\mathbf{a}}_{i}^{\prime}-\tilde{\pi}(\operatorname*{\mathbf{s}}_{i}^{\prime}))}{h}\right)$,
and the bias correction term with the kernel relaxation is denoted as
$\bar{w}^{K}:=\frac{1}{n}\sum_{i=1}^{n}w^{K}(\operatorname*{\mathbf{s}}_{i}^{\prime},\operatorname*{\mathbf{a}}_{i}^{\prime})$.
The relaxation reduces variance but increases bias. Next, we analyze the bias
and variance that together compose MSE of the proposed estimate and aim to
find kernel bandwidths and metrics that best balance the bias and the variance
to minimize the MSE of a TD update vector estimation.

###  4.1 MSE derivation

To derive the MSE of the estimated TD update vector
$\widehat{\Delta}_{IR}^{K}$ while assuming an isotropic kernel
($A({\operatorname*{\mathbf{s}}}^{\prime})=L({\operatorname*{\mathbf{s}}}^{\prime})=I$)
is used, The bias and variance of $\widehat{\Delta}_{IR}^{K}$ are derived.

######  Assumption 1.

Support of the behavior policy
$\mu(\operatorname*{\mathbf{a}}|\operatorname*{\mathbf{s}})$ contains the
actions determined by the target policy
$\tilde{\pi}(\operatorname*{\mathbf{s}})$ and the support of its kernel
relaxation
$\frac{1}{h^{d}}K\left(\tfrac{L(\operatorname*{\mathbf{s}})^{\top}(\operatorname*{\mathbf{a}}-\tilde{\pi}(\operatorname*{\mathbf{s}}))}{h}\right)$.

######  Assumption 2.

The target Q network
$Q_{\bar{\theta}}(\operatorname*{\mathbf{s}},\operatorname*{\mathbf{a}})$ is
twice differentiable w.r.t. an action $\operatorname*{\mathbf{a}}$.

######  Theorem 1.

Under Assumption 1-2, the bias and variance of $\widehat{\Delta}_{IR}^{K}$
are:

$\displaystyle\operatorname{Bias}[\widehat{\Delta}_{IR}^{K}]$
$\displaystyle=h^{2}\underbrace{\frac{\gamma}{2}\mathbb{E}_{\mathcal{D}\sim
p_{\mu}}\left[\nabla^{2}_{\operatorname*{\mathbf{a}}^{\prime}}Q_{\bar{\theta}}({\operatorname*{\mathbf{s}}}^{\prime},{\operatorname*{\mathbf{a}}}^{\prime})|_{\operatorname*{\mathbf{a}}^{\prime}=\tilde{\pi}(\operatorname*{\mathbf{s}}^{\prime})}\nabla_{\theta}Q_{\theta}(\operatorname*{\mathbf{s}},\operatorname*{\mathbf{a}})\right]}_{=:\operatorname*{\mathbf{b}}}+\mathcal{O}(h^{4}),$
(8) $\displaystyle\operatorname{Var}[\widehat{\Delta}_{IR}^{K}]$
$\displaystyle=\frac{1}{nh^{d}}\underbrace{C(K)\mathbb{E}_{p_{\mu}}\left[\frac{\left(r+\gamma
Q_{\bar{\theta}}\left(\mathbf{s}^{\prime},\tilde{\pi}\left(\mathbf{s}^{\prime}\right)\right)-Q_{\theta}(\mathbf{s},\mathbf{a})\right)^{2}\left\|\nabla_{\theta}Q_{\theta}(\mathbf{s},\mathbf{a})\right\|_{2}^{2}}{\mu\left(\tilde{\pi}\left(\mathbf{s}^{\prime}\right)\mid\mathbf{s}^{\prime}\right)}\right]}_{=:v}+\mathcal{O}\left(\frac{1}{nh^{d-2}}\right),$
(9)

where $\nabla^{2}_{\operatorname*{\mathbf{a}}^{\prime}}$ is a Laplacian
operator w.r.t. $\operatorname*{\mathbf{a}^{\prime}}$,
$\operatorname{Var}[\mathbf{z}]:=\operatorname{tr}[\operatorname{Cov}(\mathbf{z},\mathbf{z})]$
for a vector $\operatorname*{\mathbf{z}}$, $\operatorname*{\mathbf{b}}$ is the
bias constant vector, $v$ is the variance constant, $C(K):=\int
K(\mathbf{z})^{2}d\mathbf{z}$, $h^{2}\operatorname*{\mathbf{b}}$ is the
leading-order bias, and $\tfrac{v}{nh^{d}}$ is the leading-order variance.

In Theorem 1, as the bandwidth $h$ increases, the leading-order bias
increases, and the leading-order variance decreases as a bias-variance trade-
off. For the leading-order variance, it increases when the L2 norm of the TD
update vector ($\Delta(x)$ in Eq. (9) with
$x=\\{\operatorname*{\mathbf{s}},\operatorname*{\mathbf{a}},r,\operatorname*{\mathbf{s}^{\prime}},\tilde{\pi}(\operatorname*{\mathbf{s}^{\prime}})\\}$)
is large, and this is understandable since the variance of a random variable
(estimated TD update vector) would be increased if the scale of the random
variable is increased. The leading-order bias increases when the second-order
derivative of Q-function is large. This is reasonable since the estimation
bias would increase when the difference between
$Q_{\bar{\theta}}(\operatorname*{\mathbf{s}^{\prime}},\operatorname*{\mathbf{a}^{\prime}})$
and
$Q_{\bar{\theta}}(\operatorname*{\mathbf{s}^{\prime}},\tilde{\pi}({\operatorname*{\mathbf{s}^{\prime}}}))$
grows.

The bias and variance of the TD update vector estimation
$\widehat{\Delta}_{IR}^{K}$ are derived by applying the law of total
expectation and variance since the samples used for estimating
$\widehat{\Delta}_{IR}^{K}$ are first sampled with $p_{\mu}$ and then
resampled with $\rho^{K}$. Taylor expansion is also used for the derivation on
$\mu(\operatorname*{\mathbf{a}}^{\prime}|\operatorname*{\mathbf{s}}^{\prime})$
and target network
$Q_{\bar{\theta}}(\operatorname*{\mathbf{s}}^{\prime},\operatorname*{\mathbf{a}}^{\prime})$
at
$\operatorname*{\mathbf{a}}^{\prime}=\tilde{\pi}(\operatorname*{\mathbf{s}}^{\prime})$
and the odd terms of Taylor expansion are canceled out due to the symmetric
property of $K$ (proof in Appendix A.1).

Our derivation of bias and variance differs from the kernel metric learning
methods for OPE in contextual bandits (Kallus & Zhou, 2018; Lee et al., 2022)
in that it is the bias and variance of the update vector of the OPE estimate
rather than the bias and variance of the OPE estimate. The derivation also
differs from the derivations in previous in-sample learning methods (Schlegel
et al., 2019; Zhang et al., 2023) in that we derive the bias in terms of $h$,
$n$, $d$ to analyze the bias and variance w.r.t. these variables while the
derivations in the previous methods are made to mainly compare bias and
variance of IR and IS estimates.

From the bias and variance in Theorem 1, MSE can be derived (proof in Appendix
A.2).

######  Corollary 1.

Under Assumption 1-2, MSE between the TD update vector estimate
$\widehat{\Delta}_{IR}^{K}$ and the on-policy TD update vector $\Delta_{TD}$
is:

$\displaystyle\operatorname{MSE}(h,n,k,d)$
$\displaystyle=\underbrace{h^{4}\|\operatorname*{\mathbf{b}}\|^{2}_{2}+\frac{v}{nh^{d}}}_{=:\operatorname{LOMSE}(h,n,d)}+\mathcal{O}\left(h^{6}\right)+\mathcal{O}\left(\frac{1}{nh^{d-2}}\right),$
(10)

where $\operatorname{LOMSE}\left(h,n,d\right)$ is the leading-order MSE.

###  4.2 Optimal bandwidth and metric

This section derives the optimal bandwidth and metric from the leading order
MSE (LOMSE) in Eq. (10). The optimal bandwidth should minimize the LOMSE by
balancing the bias-variance trade-off.

######  Proposition 1.

The optimal bandwidth $h^{*}$ that minimizes the $\operatorname{LOMSE}(h,n,d)$
is:

$\displaystyle
h^{*}=\left(\frac{vd}{4n\|\operatorname*{\mathbf{b}}\|^{2}_{2}}\right)^{\frac{1}{d+4}}.$
(11)

The optimal bandwidth $h^{*}$ is derived by taking the derivative on
$\operatorname{LOMSE}(h,n,d)$ w.r.t. the bandwidth $h$ similarly to the work
of Kallus & Zhou (2018) since $\operatorname{LOMSE}(h,n,d)$ is convex w.r.t.
$h$ when $h>0$ (derivation in Appendix A). In Eq. (11), notice that the
optimal bandwidth $h^{*}\rightarrow 0$ as $n\rightarrow\infty$ and LOMSE
becomes dominant in MSE. Furthermore, the $h^{*}$ increases when the variance
constant $v$ is large, and the L2 norm of the bias constant vector
$\operatorname*{\mathbf{b}}$ is small, and vice versa, to balance between bias
and variance and minimize LOMSE (derivation in Appendix A.3).

Next, we analyze how the LOMSE is affected by $d$ when $h^{*}$ is applied to
our algorithm.

######  Proposition 2.

Given optimal bandwidth $h^{*}$ (Eq. (11)), in high-dimensional action space,
the squared L2-norm of leading-order bias
$h^{4}\|\operatorname*{\mathbf{b}}\|_{2}^{2}$ dominates over the leading-order
variance $\tfrac{v}{nh^{d}}$ in LOMSE (Eq. (10)). Furthermore,
$\operatorname{LOMSE}(h^{*},n,D)$ approximates to
$\|\operatorname*{\mathbf{b}}\|_{2}^{2}$.

The proof involves plugging in the optimal bandwidth $h^{*}$ in Eq. (11) to
the LOMSE in Eq. (10) and taking the limit $d\rightarrow\infty$ (derivation in
Appendix A.4). Proposition 2 suggests that the MSE of the estimate
$\widehat{\Delta}_{IR}^{K}$ is dominated by the bias in high-dimensional
action space when the optimal bandwidth $h^{*}$ is applied. Therefore, in a
high-dimensional action space, a significant amount of MSE can be reduced by
reducing the bias. We seek to further minimize the bias that dominates the MSE
in high-dimensional action space with metric learning.

Since applying the Mahalanobis metric
$A(\operatorname*{\mathbf{s}})=L(\operatorname*{\mathbf{s}})L(\operatorname*{\mathbf{s}})^{\top}$
to a kernel is equivalent to linearly transforming the kernel inputs with the
linear transformation matrix $L(\operatorname*{\mathbf{s}})$ (Section 3.2), we
analyze the effect of the kernel metric on the bias constant vector
$\operatorname*{\mathbf{b}}$ with the linearly transformed kernel inputs. The
squared L2-norm of the bias constant vector with kernel metric is:

$\displaystyle\|{\operatorname*{\mathbf{b}}}_{A}\|_{2}^{2}$
$\displaystyle=\frac{\gamma^{2}}{4}\|\mathbb{E}_{\mathcal{D}\sim
p_{\mu}}\left[\operatorname{tr}\left[A({\operatorname*{\mathbf{s}}}^{\prime})^{-1}\operatorname*{\mathbf{H}_{\mathbf{a}^{\prime}}}Q_{\bar{\theta}}({\operatorname*{\mathbf{s}}}^{\prime},{\operatorname*{\mathbf{a}}}^{\prime})|_{{\operatorname*{\mathbf{a}}}^{\prime}=\tilde{\pi}({\operatorname*{\mathbf{s}}}^{\prime})}\right]\nabla_{\theta}Q(\operatorname*{\mathbf{s}},\operatorname*{\mathbf{a}})\right]\|_{2}^{2},$
(12)

where $\operatorname*{\mathbf{H}_{\mathbf{a}^{\prime}}}$ is the Hessian
operator w.r.t. $\operatorname*{\mathbf{a}^{\prime}}$. The derivation involves
a change-of-variable on conditional distribution and derivatives (derivation
in Appendix A.5).

Minimizing Eq. (12) is challenging as it necessitates a comprehensive
examination of the collective impact exerted by every metric matrix
$A({\operatorname*{\mathbf{s}}}^{\prime})$ inside the expectation. Therefore,
an alternative approach is adopted wherein the focus shifts towards minimizing
the subsequent upper bound $U(A)$ in Eq. (13). This alternative strategy
enables the derivation of a closed-form metric matrix for each state,
employing a nonparametric methodology while being bandwidth-agnostic.

$\displaystyle\min_{\begin{subarray}{c}A:~{}A({\operatorname*{\mathbf{s}}}^{\prime})\succ
0,\\\
\;\;\;\;\;\;\;\;\;\;\;\;\;\;A({\operatorname*{\mathbf{s}}}^{\prime})=A({\operatorname*{\mathbf{s}}}^{\prime})^{\top},\\\
\;\;\;\;\;\;\;|A({\operatorname*{\mathbf{s}}}^{\prime})|=1~{}\forall{\operatorname*{\mathbf{s}}}^{\prime}\end{subarray}}U(A)$
$\displaystyle=\frac{\gamma^{2}}{4}\mathbb{E}_{\mathcal{D}\sim
p_{\mu}}\left[\operatorname{tr}\left(\left.A({\operatorname*{\mathbf{s}}}^{\prime})^{-1}\operatorname*{\mathbf{H}_{\mathbf{a}^{\prime}}}Q_{\bar{\theta}}({\operatorname*{\mathbf{s}}}^{\prime},{\operatorname*{\mathbf{a}}}^{\prime})\right|_{{\operatorname*{\mathbf{a}}}^{\prime}=\tilde{\pi}({\operatorname*{\mathbf{s}}}^{\prime})}\right)^{2}\|\nabla_{\theta}Q(\operatorname*{\mathbf{s}},\operatorname*{\mathbf{a}})\|_{2}^{2}\right].$
(13)

######  Proposition 3.

Under Assumption 2, define
$\Lambda_{+}(\operatorname*{\mathbf{s}}^{\prime})\in\mathbb{R}^{d_{+}(\operatorname*{\mathbf{s}}^{\prime})\times
d_{+}(\operatorname*{\mathbf{s}}^{\prime})}$ and
$\Lambda_{-}(\operatorname*{\mathbf{s}}^{\prime})\in\mathbb{R}^{d_{-}(\operatorname*{\mathbf{s}}^{\prime})\times
d_{-}(\operatorname*{\mathbf{s}}^{\prime})}$ as diagonal matrices of positive
and negative eigenvalues from the Hessian
$\mathbf{H}_{\operatorname*{\mathbf{a}}^{\prime}}Q_{\bar{\theta}}(\operatorname*{\mathbf{s}}^{\prime},\operatorname*{\mathbf{a}}^{\prime})|_{\operatorname*{\mathbf{a}}^{\prime}=\tilde{\pi}(\operatorname*{\mathbf{s}}^{\prime})}$,
and define $U_{+}(\operatorname*{\mathbf{s}}^{\prime})$ and
$U_{-}(\operatorname*{\mathbf{s}}^{\prime})$ as the matrices of eigenvectors
corresponding to $\Lambda_{+}(\operatorname*{\mathbf{s}}^{\prime})$ and
$\Lambda_{-}(\operatorname*{\mathbf{s}}^{\prime})$ respectively. Then the
$U(A)$ minimizing metric $A^{*}(\operatorname*{\mathbf{s}}^{\prime})$ is:

$\displaystyle A^{*}(\mathbf{s}^{\prime})$
$\displaystyle=\alpha({\operatorname*{\mathbf{s}}}^{\prime})\left[U_{+}({\operatorname*{\mathbf{s}}}^{\prime})U_{-}({\operatorname*{\mathbf{s}}}^{\prime})\right]\underbrace{\left(\begin{array}[]{cc}d_{+}({\operatorname*{\mathbf{s}}}^{\prime})\Lambda_{+}({\operatorname*{\mathbf{s}}}^{\prime})&0\\\
0&-d_{-}({\operatorname*{\mathbf{s}}}^{\prime})\Lambda_{-}({\operatorname*{\mathbf{s}}}^{\prime})\end{array}\right)}_{=:M({\operatorname*{\mathbf{s}}}^{\prime})}\left[U_{+}({\operatorname*{\mathbf{s}}}^{\prime})U_{-}({\operatorname*{\mathbf{s}}}^{\prime})\right]^{\top},$
(16)

where
$\alpha({\operatorname*{\mathbf{s}}}^{\prime}):=\left|M({\operatorname*{\mathbf{s}}}^{\prime})\right|^{-1/\left(d_{+}({\operatorname*{\mathbf{s}}}^{\prime})+d_{-}({\operatorname*{\mathbf{s}}}^{\prime})\right)}$.

The proof entails solving Eq. (13) for
$A(\operatorname*{\mathbf{s}^{\prime}})$ for each
$\operatorname*{\mathbf{s}^{\prime}}$ (thus locally learn metrics for each
$\operatorname*{\mathbf{s}^{\prime}}$) by means of the Lagrangian equation.
The closed-form solution to the minimization objective involving squared trace
term of two matrix products in Eq. (13) is reported in the work of Noh et al.
(2010) that learns kernel metric for kernel regression, and the solution had
been used in the context of kernel metric learning for OPE in contextual
bandits (Lee et al., 2022). We use the same solution for acquiring kernel
metrics that minimize the squared trace term.

Notice that when the Hessian
$\operatorname*{\mathbf{H}_{\mathbf{a}^{\prime}}}Q_{\bar{\theta}}(\operatorname*{\mathbf{s}^{\prime}},\operatorname*{\mathbf{a}^{\prime}})|_{\operatorname*{\mathbf{a}^{\prime}}=\tilde{\pi}(\operatorname*{\mathbf{s}^{\prime}})}$
contains both positive and negative eigenvalues, the trace in Eq. (13) becomes
zero. The optimal metric $A^{*}(\operatorname*{\mathbf{s}^{\prime}})$ regards
the next action $\operatorname*{\mathbf{a}^{\prime}}$ in data is similar to
the next target action $\tilde{\pi}(\operatorname*{\mathbf{s}^{\prime}})$ when
the eigenvalue of the Hessian in that direction is small, and decreases the
Mahalanobis distance between $\operatorname*{\mathbf{a}^{\prime}}$ and
$\tilde{\pi}(\operatorname*{\mathbf{s}^{\prime}})$. Consequently, as the
Mahalanobis distance decreases, kernel value in the IS ratio
$w^{K}(\operatorname*{\mathbf{s}^{\prime}},\operatorname*{\mathbf{a}^{\prime}})$
increases. Finally, the associated resampling probability increases, leading
to a higher resampling probability.

Utilizing the derived optimal bandwidth $h^{*}$ and optimal metric $A^{*}$,
the TD update vector for $Q_{\theta}$ can be estimated in an in-sample
learning manner by using importance resampling (IR). The estimated TD update
vector is then used for learning $Q_{\theta}$. As $Q_{\theta}$ is learned by
bootstrapping, the actual algorithm iterates between learning $h^{*}$,
$A^{*}$, and learning $Q_{\theta}$. Finally, when $Q_{\theta}$ converges, it
is used for evaluating the deterministic target policy. The detailed procedure
is in Algorithm 1 in Appendix B. Although we assumed a known behavior policy,
our method can be applied to offline data that is sampled from unknown
multiple behavior policies by estimating a behavior policy by maximum
likelihood estimation. The work by Hanna et al. (2019) shows that the IS
estimation of a target policy value is more accurate when an MLE behavior
policy is used instead of the true behavior policy.

###  4.3 Error Bound Analysis

In this section, we analyze the error bound of the estimated Q-function with
KMIFQE. The difference between the on-policy TD update vector $\Delta_{TD}$
and the KMIFQE estimated TD update vector $\widehat{\Delta}_{IR}^{K}$ is that
$\widehat{\Delta}_{IR}^{K}$ is obtained from the TD loss in Eq. (1) with $K$
instead of $\pi$. In other words, updating $\theta$ using
$\widehat{\Delta}_{IR}^{K}$ can be understood as evaluating the _stochastic_
target policy relaxed by the bandwidth $h$ and the matric $A$. We will show
the evaluation gap resulting from using the relaxed stochastic policy instead
of a deterministic policy. To this end, we first define Bellman operators $T$
and $T_{K}$ for the deterministic target policy $\tilde{\pi}$ and the
stochastic target policy
$\pi_{K}(\operatorname*{\mathbf{a}}|\operatorname*{\mathbf{s}})=\frac{1}{h^{d}}K\left(\tfrac{L\left(\operatorname*{\mathbf{s}}\right)^{\top}\left(\operatorname*{\mathbf{a}}-\tilde{\pi}\left(\operatorname*{\mathbf{s}}\right)\right)}{h}\right)$
respectively.

$\displaystyle TQ(\operatorname*{\mathbf{s}},\operatorname*{\mathbf{a}})$
$\displaystyle:=R(\operatorname*{\mathbf{s}},\operatorname*{\mathbf{a}})+\gamma\mathbb{E}_{\operatorname*{\mathbf{s}^{\prime}}\sim
P\left(\operatorname*{\mathbf{s}^{\prime}}\mid\operatorname*{\mathbf{s}},\operatorname*{\mathbf{a}}\right)}\left[Q\left(\operatorname*{\mathbf{s}^{\prime}},\tilde{\pi}\left(\operatorname*{\mathbf{s}^{\prime}}\right)\right)\right],$
(17) $\displaystyle
T_{K}Q(\operatorname*{\mathbf{s}},\operatorname*{\mathbf{a}})$
$\displaystyle:=R(\operatorname*{\mathbf{s}},\operatorname*{\mathbf{a}})+\gamma\mathbb{E}_{\operatorname*{\mathbf{s}^{\prime}}\sim
P\left(\operatorname*{\mathbf{s}^{\prime}}\mid\operatorname*{\mathbf{s}},\operatorname*{\mathbf{a}}\right),\operatorname*{\mathbf{a}^{\prime}}\sim\pi_{K}(\operatorname*{\mathbf{a}^{\prime}}|\operatorname*{\mathbf{s}^{\prime}})}\left[Q\left(\operatorname*{\mathbf{s}^{\prime}},\operatorname*{\mathbf{a}^{\prime}}\right)\right].$
(18)

We then analyze the difference in fixed points for each Bellman operator.

######  Assumption 3.

For all $\\{\operatorname*{\mathbf{s}},\operatorname*{\mathbf{a}}\\}\in
S\times A$, assume that the second-order derivatives of an arbitrary
$Q(\operatorname*{\mathbf{s}},\operatorname*{\mathbf{a}})$ w.r.t. actions are
bounded.

######  Theorem 2.

Under Assumption 3, denoting $m$ iterative applications of $T$ and $T_{K}$ to
an arbitrary $Q$ as $T^{m}Q$ and $T_{K}^{m}Q$ respectively, and $h$ and
$A(\operatorname*{\mathbf{s}^{\prime}})$ as an arbitrary bandwidth and metric
respectively, the following holds:

$\displaystyle\|Q^{\pi}-\lim_{m\rightarrow\infty}T_{K}^{m}Q\|_{\infty}\leq\frac{\gamma\xi}{1-\gamma},$
(19)
$\displaystyle\qquad\xi:=\max_{m,\\{\operatorname*{\mathbf{s}},\operatorname*{\mathbf{a}}\\}\in
S\times A}\frac{h^{2}}{2}\mathbb{E}_{\operatorname*{\mathbf{s}^{\prime}}\sim
P(\operatorname*{\mathbf{s}^{\prime}}|\operatorname*{\mathbf{s}},\operatorname*{\mathbf{a}})}\left[\left|\operatorname{tr}\left(A(\operatorname*{\mathbf{s}^{\prime}})^{-1}\operatorname*{\mathbf{H}_{\mathbf{a}^{\prime}}}T_{K}^{m}Q(\operatorname*{\mathbf{s}^{\prime}},\operatorname*{\mathbf{a}^{\prime}})|_{\operatorname*{\mathbf{a}^{\prime}}=\tilde{\pi}(\operatorname*{\mathbf{s}^{\prime}})}\right)\right|\right]+|\mathcal{O}(h^{4})|.$
(20)

The proof involves deriving $\xi$ that upperbounds $\|TQ-
T_{K}Q\|_{\infty}/\gamma$ by using Taylor expansion at
$\operatorname*{\mathbf{a}^{\prime}}=\tilde{\pi}(\operatorname*{\mathbf{s}^{\prime}})$,
and showing
$\|T^{\infty}Q-T^{\infty}_{K}Q\|_{\infty}\leq\sum_{i=1}^{\infty}\gamma^{i}\xi$
using mathematical induction (proof in Appendix A.6).

Theorem 2 shows that the evaluation gap is bounded by the degree of stochastic
relaxation $h$ and metric metric $A(\operatorname*{\mathbf{s}^{\prime}})$. It
is noteworthy that for any given $h$, we can always reduce the gap by applying
optimal metric $A^{*}(\operatorname*{\mathbf{s}^{\prime}})$ in Proposition 3,
which will also be shown empirically in the experiments (Figure 1b). While
$h=0$ seems to be always preferred in Theorem 2, it is because it only
considers the exact policy evaluation without any estimation error by using
finite samples. When we update $Q$ using finite samples, the bias-variance
trade-off by choice of $h$ should be considered, as shown in Theorem 1.

##  5 Experiments

In this section, we empirically validate the theoretical findings related to
the learned metrics and bandwidths in Section 4.2 and compare the performance
of KMIFQE with the baselines. The baselines include SR-DICE (Fujimoto et al.,
2021) and FQE (Voloshin et al., 2019), which are state-of-the-art model-free
OPE algorithms for evaluating deterministic target policies (Fujimoto et al.,
2021) but vulnerable to extrapolation errors due to the usage of OOD samples.
KMIFQE is evaluated on three test domains. First, we evaluate KMIFQE on OpenAI
gym Pendulum-v0 environment (Brockman et al., 2016) with dummy action
dimensions to see if the metrics and bandwidths are learned as intended. Then,
we compare KMIFQE with the baselines on more complex MuJoCo environments
(Todorov et al., 2012). Lastly, KMIFQE and baselines are evaluated on D4RL (Fu
et al., 2020) datasets sampled from unknown multiple behavior policies since
the baselines assume unknown multiple behavior policies. To apply KMIFQE,
which assumes a known behavior policy, on the D4RL datasets, maximum
likelihood estimated (MLE) behavior policies are used. For the hyperparameters
in the baselines, we used the hyperparameters in the work of Fujimoto et al.
(2021) as our test data is the same or similar to theirs. For KMIFQE, we used
the same hyperparameter settings to the baselines for those overlap and IS
ratio clipping in the range of [1e-3, 2] selected by grid search (see Appnedix
C). Our code is available at https://github.com/haanvid/kmifqe.

###  5.1 Pendulum with dummy action dimensions

Pendulum-v0 environment (Brockman et al., 2016) is modified by adding dummy
action dimensions that are unrelated to the estimation of target policy values
for imposing large OPE estimation bias when an OPE algorithm fails to ignore
the dummy action dimensions. The domain is prepared to observe if the KMIFQE
metrics are learned to reduce the bias of $\widehat{\Delta}^{K}_{IR}$ as
intended in Proposition 3, leading to less error in the estimation of
$Q^{\pi}$ as stated in Theorem 2. For the dataset, actions in the dummy action
dimensions are uniformly sampled from the original action range
$[-a_{\text{max}},a_{\text{max}}]$, and the original action is sampled from
the mixture of 20% uniform random distribution and 80% Gaussian density of
$N(\tilde{\mu}_{1}(\operatorname*{\mathbf{s}}),(0.5a_{\text{max}})^{2})$ where
$\tilde{\mu}_{1}$ is a TD3 policy showing medium-level performance. The target
policy $\tilde{\pi}(\operatorname*{\mathbf{s}})$ outputs action of
$\tilde{\pi}_{1}(\operatorname*{\mathbf{s}})$ for the original action
dimension and zeros for the dummy action dimensions.
$\tilde{\pi}_{1}(\operatorname*{\mathbf{s}})$ is a TD3 policy showing expert-
level performance. The dataset contains 0.5 million transitions (more details
in Appendix C).

We examine if our theoretical analysis made in Section 4.2 is supported by
empirical results. Due to the unavailability of the ground truth TD update
vectors, we analyze the impact of metric and bandwidth learning on the MSE of
the estimated target policy values instead of evaluating its effect on the
estimated TD update vector. We hypothesize that an estimation error in the TD
update vector would lead to an estimation error in the target policy values.

Figure 1: (a) Empirical bias and variance of the KMIFQE with and without
metric learning as the number of dummy action dimensions increases. (b)
Performance of KMIFQE with and without metric learning under various given
bandwidths. The bandwidths learned by KMIFQE are plotted as vertical lines
along with makers indicating the MSEs. The shaded area is the region within
one standard error. All experiments are repeated for 10 trials.

Firstly, Proposition 2 is empirically validated in Figure 1a. In the figure,
empirical bias becomes much larger than the variance with KMIFQE learned
bandwidth as the number of dummy action dimensions increases. Furthermore, the
bias is reduced by the KMIFQE learned metrics (Proposition 3). Secondly, in
Figure 1b, we show that the learned metrics reduce biases in all bandwidths as
claimed in Proposition 3. Furthermore, the "_U_ " shaped curve shows the bias-
variance trade-off on varying bandwidths. Notably, the learned bandwidth
balances between bias and variance as intended in Proposition 1. Finally,
KMIFQE learned metrics and Q-value landscapes are presented in Figure 2
showing that the metrics are learned to ignore the dummy action dimensions and
the estimated Q-value landscape changes a little along the dummy action
dimension compared to the one estimated by FQE. Moreover, the KMIFQE correctly
estimates high Q-values for target actions that are optimal, while FQE
estimates low Q-values for the actions.

Figure 2: Visualization of $Q^{\pi}$ estimated by KMIFQE and FQE, along with
the kernel metrics learned by KMIFQE in the modified Pendulum-v0 domain with
one dummy action dimension. The original action dimension is $a_{1}$, and the
dummy action dimension is $a_{2}$. The leftmost column illustrates the given
states. The center column shows the Q-landscapes and metrics (black crosses)
learned by KMIFQE. The rightmost column shows the Q-landscapes learned by FQE.
The target actions at the given states are presented in yellow circles.

The performance of KMIFQE with learned metric and bandwidth, as well as
baselines on the pendulum with one dummy action dimension are reported as root
mean squared errors (RMSEs) in the first row of Table 1. KMIFQE outperforms
the baselines that use OOD samples, and when metric learning is applied, the
RMSEs are further reduced. The result supports the statement in Theorem 2 that
the metric learning reduces the error bound.

Table 1: RMSEs of Baselines and KMIFQE with learned metric and bandwidth with
one standard error on 10 seeds. Note that m-e=medium-expert, m-r=medium-
replay.

Dataset | known $\mu$ | KMIFQE | KMIFQE w/o Metric | SR-DICE | FQE
---|---|---|---|---|---
Pendulum with dummy dim | O | 0.115 $\pm$ 0.018 | 0.250 $\pm$ 0.032 | 1.641 $\pm$ 0.426 | 8.126 $\pm$ 2.962
Hopper-v2 | O | 0.023 $\pm$ 0.006 | 0.034 $\pm$ 0.009 | 0.129 $\pm$ 0.023 | 0.083 $\pm$ 0.011
HalfCheetah-v2 | O | 2.080 $\pm$ 0.010 | 2.549 $\pm$ 0.017 | 2.784 $\pm$ 0.030 | 1.637 $\pm$ 0.051
Walker2d-v2 | O | 0.032 $\pm$ 0.008 | 0.048 $\pm$ 0.009 | 0.273 $\pm$ 0.054 | 241.319 $\pm$ 49.248
Ant-v2 | O | 1.800 $\pm$ 0.013 | 2.255 $\pm$ 0.014 | 1.996 $\pm$ 0.030 | 3.219 $\pm$ 0.736
Humanoid-v2 | O | 0.246 $\pm$ 0.010 | 0.293 $\pm$ 0.021 | 1.285 $\pm$ 0.050 | 8.860 $\pm$ 8.196
hopper-m-e-v2 | X | 0.019 $\pm$ 0.003 | 0.020 $\pm$ 0.005 | 0.045 $\pm$ 0.007 | 0.033 $\pm$ 0.010
halfcheetah-m-e-v2 | X | 0.418 $\pm$ 0.016 | 0.457 $\pm$ 0.007 | 0.239 $\pm$ 0.025 | 0.080 $\pm$ 0.007
walker2d-m-e-v2 | X | 0.036 $\pm$ 0.006 | 0.038 $\pm$ 0.006 | 0.115 $\pm$ 0.017 | 1.051 $\pm$ 0.633
hopper-m-r-v2 | X | 0.536 $\pm$ 0.099 | 0.517 $\pm$ 0.120 | 0.849 $\pm$ 0.052 | 0.561 $\pm$ 0.118
halfcheetah-m-r-v2 | X | 4.698 $\pm$ 0.044 | 4.765 $\pm$ 0.026 | 5.048 $\pm$ 0.090 | 6.394 $\pm$ 1.769
walker2d-m-r-v2 | X | 1.364 $\pm$ 0.052 | 1.360 $\pm$ 0.025 | 1.523 $\pm$ 0.061 | 86.315 $\pm$ 29.206

###  5.2 Continuous control tasks with a known behavior policy

We compare the performance of KMIFQE with baselines on more complex continuous
control tasks of MuJoCo (Todorov et al., 2012) with a known behavior policy.
Deterministic target policies are trained by TD3 Fujimoto et al. (2018). For
behavior policies, deterministic policies $\tilde{\mu}$ are trained with TD3
to achieve 70% $\sim$ 80% performance (in undiscounted returns) of the target
policy and are used for making the stochastic behavior policies
$\mu(\operatorname*{\mathbf{a}}|\operatorname*{\mathbf{s}})=N(\operatorname*{\mathbf{a}};\tilde{\mu}(\operatorname*{\mathbf{s}}),(0.3a_{\text{max}})^{2}I)$.
One million transitions are collected with the behavior policy as the dataset
for each environment.

The performance of OPE methods on five MuJoCo environments reported in Table 1
shows that KMIFQE outperforms other baselines in all environments except
HalfCheetah-v2 where FQE performs the best. Since HalfCheetah-v2 does not have
an episode termination condition, the $Q^{\pi}$ that is being estimated may be
relatively slowly changing w.r.t. changes in actions compared to the other
environments, inducing low extrapolation error on the TD targets of FQE with
OOD samples.

###  5.3 Continuous control tasks with unknown multiple behavior policies

KMIFQE can be applied to a dataset sampled with unknown multiple behavior
policies with a maximum likelihood estimated behavior policy. We evaluate
KMIFQE on a D4RL (1) medium-expert dataset sampled from medium and expert
level performance policies, and (2) medium-replay dataset collected from a
single policy while it is being trained to achieve medium-level performance
(Fu et al., 2020). The behavior policies used by KMIFQE are estimated as tanh-
squashed mixture-of-Gaussians. For target policies, we use the means of
stochastic expert policies provided by D4RL.

The last six rows of Table 1 show that KMIFQE outperforms the baselines except
in halfcheetah-medium-expert-v2. The dataset may induce small extrapolation
errors for the OPE methods that use OOD samples. First, half of the dataset is
sampled with a stochastic expert policy, in which the mean value is the action
selected by the target policy. Secondly, as discussed in Section 5.2, the
$Q^{\pi}$ being estimated in the halfcheetah environment may vary slowly
w.r.t. changes in actions, making the extrapolation error due to using OOD
samples small for FQE and SR-DICE.

##  6 Conclusion

We presented KMIFQE, an off-policy evaluation (OPE) algorithm for
deterministic reinforcement learning policies in continuous action spaces.
KMIFQE learns the Q-function of a deterministic target policy for OPE in an
in-sample manner through importance resampling (IR)-based Q-function update
vector estimation, avoiding extrapolation error from OOD samples. IR is
enabled by kernel-relaxing the deterministic target policy, and the estimation
error from the relaxation is minimized by kernel metric learning. To learn the
kernel metric, we first derived the MSE of an update vector estimation. Then,
to we derived an optimal bandwidth that minimizes the MSE. Upon our
observation that the bias is dominant in the MSE for a high-dimensional action
space, the bandwidth-agnostic optimal metric matrix for bias reduction was
derived as a closed-form solution. The optimal metric matrix is computed with
the Hessian of the learned Q-function. Lastly, we analyzed the error bound of
the learned Q-function by KMIFQE. Empirical studies show our KMIFQE
outperforms baselines on the offline data sampled with known or unknown
behavior policies.

##  7 Acknowledgements

This work was supported by IITP grant funded by MSIT (No.2020-0-00940,
Foundations of Safe Reinforcement Learning and Its Applications to Natural
Language Processing; No.2022-0-00311, Development of Goal-Oriented
Reinforcement Learning Techniques for Contact-Rich Robotic Manipulation of
Everyday Objects; No.2019-0-00075, AI Graduate School Program (KAIST)). Tri
Wahyu Guntara was partially supported by the Hyundai Motor Chung Mong-Koo
Foundation.

## References

  * Brockman et al. (2016) Greg Brockman, Vicki Cheung, Ludwig Pettersson, Jonas Schneider, John Schulman, Jie Tang, and Wojciech Zaremba.  Openai gym.  _arXiv preprint arXiv:1606.01540_ , 2016.
  * De Maesschalck et al. (2000) Roy De Maesschalck, Delphine Jouan-Rimbaud, and Désiré L Massart.  The mahalanobis distance.  _Chemometrics and Intelligent Laboratory Systems_ , 50(1):1–18, 2000.
  * Fu et al. (2020) Justin Fu, Aviral Kumar, Ofir Nachum, George Tucker, and Sergey Levine.  D4rl: Datasets for deep data-driven reinforcement learning.  _arXiv preprint arXiv:2004.07219_ , 2020.
  * Fujimoto et al. (2018) Scott Fujimoto, Herke van Hoof, and David Meger.  Addressing function approximation error in actor-critic methods.  In _Proceedings of the 35th International Conference on Machine Learning_ , pp. 1587–1596, 2018.
  * Fujimoto et al. (2021) Scott Fujimoto, David Meger, and Doina Precup.  A deep reinforcement learning approach to marginalized importance sampling with the successor representation.  In _International Conference on Machine Learning_ , pp. 3518–3529. PMLR, 2021.
  * Han & Sung (2019) Seungyul Han and Youngchul Sung.  Dimension-wise importance sampling weight clipping for sample-efficient reinforcement learning.  In _International Conference on Machine Learning_ , pp. 2586–2595. PMLR, 2019.
  * Hanna et al. (2019) Josiah Hanna, Scott Niekum, and Peter Stone.  Importance sampling policy evaluation with an estimated behavior policy.  In _International Conference on Machine Learning_ , pp. 2605–2613. PMLR, 2019.
  * Kallus & Zhou (2018) Nathan Kallus and Angela Zhou.  Policy evaluation and optimization with continuous treatments.  In _Proceedings of the Twenty-First International Conference on Artificial Intelligence and Statistics_ , pp. 1243–1251, 2018.
  * Kingma & Ba (2014) Diederik P Kingma and Jimmy Ba.  Adam: A method for stochastic optimization.  _arXiv preprint arXiv:1412.6980_ , 2014.
  * Konyushova et al. (2021) Ksenia Konyushova, Yutian Chen, Thomas Paine, Caglar Gulcehre, Cosmin Paduraru, Daniel J Mankowitz, Misha Denil, and Nando de Freitas.  Active offline policy selection.  _Advances in Neural Information Processing Systems_ , 34:24631–24644, 2021.
  * Le et al. (2019) Hoang Le, Cameron Voloshin, and Yisong Yue.  Batch policy learning under constraints.  In _International Conference on Machine Learning_ , pp. 3703–3712. PMLR, 2019.
  * Lee et al. (2022) Haanvid Lee, Jongmin Lee, Yunseon Choi, Wonseok Jeon, Byung-Jun Lee, Yung-Kyun Noh, and Kee-Eung Kim.  Local metric learning for off-policy evaluation in contextual bandits with continuous actions.  In _Advances in Neural Information Processing Systems_ , 2022.
  * Levine et al. (2020) Sergey Levine, Aviral Kumar, George Tucker, and Justin Fu.  Offline reinforcement learning: Tutorial, review, and perspectives on open problems.  _arXiv preprint arXiv:2005.01643_ , 2020.
  * Liu et al. (2018) Qiang Liu, Lihong Li, Ziyang Tang, and Dengyong Zhou.  Breaking the curse of horizon: Infinite-horizon off-policy estimation.  _Advances in neural information processing systems_ , 31, 2018.
  * Mahalanobis (1936) Prasanta Chandra Mahalanobis.  On the generalized distance in statistics.  In _Proceedings of the National Institute of Sciences of India_ , 1936.
  * Mandel et al. (2014) Travis Mandel, Yun-En Liu, Sergey Levine, Emma Brunskill, and Zoran Popovic.  Offline policy evaluation across representations with applications to educational games.  In _Autonomous Agents and Multiagent Systems_ , volume 1077, 2014.
  * Munos et al. (2016) Rémi Munos, Tom Stepleton, Anna Harutyunyan, and Marc Bellemare.  Safe and efficient off-policy reinforcement learning.  _Advances in neural information processing systems_ , 29, 2016.
  * Murphy et al. (2001) Susan A Murphy, Mark J van der Laan, James M Robins, and Conduct Problems Prevention Research Group.  Marginal mean models for dynamic regimes.  _Journal of the American Statistical Association_ , 96(456):1410–1423, 2001.
  * Nachum et al. (2019) Ofir Nachum, Yinlam Chow, Bo Dai, and Lihong Li.  Dualdice: Behavior-agnostic estimation of discounted stationary distribution corrections.  _Advances in Neural Information Processing Systems_ , 32, 2019.
  * Noh et al. (2010) Yung-Kyun Noh, Byoung-Tak Zhang, and Daniel D Lee.  Generative local metric learning for nearest neighbor classification.  In _Advances in Neural Information Processing Systems_ , pp. 1822–1830, 2010.
  * Noh et al. (2017) Yung-Kyun Noh, Masashi Sugiyama, Kee-Eung Kim, Frank Park, and Daniel D Lee.  Generative local metric learning for kernel regression.  In _Advances in Neural Information Processing Systems_ , pp. 2452–2462, 2017.
  * Precup et al. (2001) Doina Precup, Richard S Sutton, and Sanjoy Dasgupta.  Off-policy temporal-difference learning with function approximation.  In _International Conference on Machine Learning_ , pp. 417–424, 2001.
  * Schlegel et al. (2019) Matthew Schlegel, Wesley Chung, Daniel Graves, Jian Qian, and Martha White.  Importance resampling for off-policy prediction.  _Advances in Neural Information Processing Systems_ , 32, 2019.
  * Silver et al. (2014) David Silver, Guy Lever, Nicolas Heess, Thomas Degris, Daan Wierstra, and Martin Riedmiller.  Deterministic policy gradient algorithms.  In _International conference on machine learning_ , pp. 387–395. Pmlr, 2014.
  * Su et al. (2020) Yi Su, Pavithra Srinath, and Akshay Krishnamurthy.  Adaptive estimator selection for off-policy evaluation.  In _International Conference on Machine Learning_ , pp. 9196–9205. PMLR, 2020.
  * Swaminathan et al. (2017) Adith Swaminathan, Akshay Krishnamurthy, Alekh Agarwal, Miro Dudik, John Langford, Damien Jose, and Imed Zitouni.  Off-policy evaluation for slate recommendation.  _Advances in Neural Information Processing Systems_ , 30, 2017.
  * Todorov et al. (2012) Emanuel Todorov, Tom Erez, and Yuval Tassa.  Mujoco: A physics engine for model-based control.  In _2012 IEEE/RSJ International Conference on Intelligent Robots and Systems_ , pp. 5026–5033. IEEE, 2012.
  * Voloshin et al. (2019) Cameron Voloshin, Hoang M Le, Nan Jiang, and Yisong Yue.  Empirical study of off-policy policy evaluation for reinforcement learning.  _arXiv preprint arXiv:1911.06854_ , 2019.
  * Xie et al. (2019) Tengyang Xie, Yifei Ma, and Yu-Xiang Wang.  Towards optimal off-policy evaluation for reinforcement learning with marginalized importance sampling.  _Advances in Neural Information Processing Systems_ , 32, 2019.
  * Yang et al. (2020) Mengjiao Yang, Ofir Nachum, Bo Dai, Lihong Li, and Dale Schuurmans.  Off-policy evaluation via the regularized lagrangian.  _Advances in Neural Information Processing Systems_ , 33:6551–6561, 2020.
  * Yu et al. (2020) Tianhe Yu, Garrett Thomas, Lantao Yu, Stefano Ermon, James Y Zou, Sergey Levine, Chelsea Finn, and Tengyu Ma.  Mopo: Model-based offline policy optimization.  _Advances in Neural Information Processing Systems_ , 33:14129–14142, 2020.
  * Zhang et al. (2023) Hongchang Zhang, Yixiu Mao, Boyuan Wang, Shuncheng He, Yi Xu, and Xiangyang Ji.  In-sample actor critic for offline reinforcement learning.  In _International Conference on Learning Representations_ , 2023.
  * Zhang et al. (2020) Shangtong Zhang, Bo Liu, and Shimon Whiteson.  Gradientdice: Rethinking generalized offline estimation of stationary values.  In _International Conference on Machine Learning_ , pp. 11194–11203. PMLR, 2020.
  * Zhao et al. (2009) Yufan Zhao, Michael R Kosorok, and Donglin Zeng.  Reinforcement learning design for cancer clinical trials.  _Statistics in Medicine_ , 28(26):3294–3315, 2009.

##  Appendix A Derivations and proofs

###  A.1 Proof of Theorem 1

######  Theorem 1.

Under Assumption 1-2, the bias and variance of $\widehat{\Delta}_{IR}^{K}$
are:

$\displaystyle\operatorname{Bias}[\widehat{\Delta}_{IR}^{K}]$
$\displaystyle=h^{2}\underbrace{\frac{\gamma}{2}\mathbb{E}_{\mathcal{D}\sim
p_{\mu}}\left[\nabla^{2}_{\operatorname*{\mathbf{a}}^{\prime}}Q_{\bar{\theta}}({\operatorname*{\mathbf{s}}}^{\prime},{\operatorname*{\mathbf{a}}}^{\prime})|_{\operatorname*{\mathbf{a}}^{\prime}=\tilde{\pi}(\operatorname*{\mathbf{s}}^{\prime})}\nabla_{\theta}Q_{\theta}(\operatorname*{\mathbf{s}},\operatorname*{\mathbf{a}})\right]}_{=:\operatorname*{\mathbf{b}}}+\mathcal{O}(h^{4}),$
(21) $\displaystyle\operatorname{Var}[\widehat{\Delta}_{IR}^{K}]$
$\displaystyle=\frac{1}{nh^{d}}\underbrace{C(K)\mathbb{E}_{p_{\mu}}\left[\frac{\left(r+\gamma
Q_{\bar{\theta}}\left(\mathbf{s}^{\prime},\tilde{\pi}\left(\mathbf{s}^{\prime}\right)\right)-Q_{\theta}(\mathbf{s},\mathbf{a})\right)^{2}\left\|\nabla_{\theta}Q_{\theta}(\mathbf{s},\mathbf{a})\right\|_{2}^{2}}{\mu\left(\tilde{\pi}\left(\mathbf{s}^{\prime}\right)\mid\mathbf{s}^{\prime}\right)}\right]}_{=:v}+\mathcal{O}\left(\frac{1}{nh^{d-2}}\right),$
(22)

where
$\operatorname{Var}[\mathbf{z}]:=\operatorname{tr}[\operatorname{Cov}(\mathbf{z},\mathbf{z})]$
for a vector $\operatorname*{\mathbf{z}}$, $\operatorname*{\mathbf{b}}$ is the
bias constant vector, $v$ is the variance constant,
$h^{2}\operatorname*{\mathbf{b}}$ is the leading-order bias,
$\tfrac{v}{nh^{d}}$ is the leading-order variance, and $C(K):=\int
K(\mathbf{z})^{2}d\mathbf{z}$.

###### Proof.

With Assumptions 1-2,

Derivation of the bias in Eq. (8):

$\displaystyle\operatorname{Bias}$ $\displaystyle[\hat{\Delta}^{K}_{IR}]$
$\displaystyle=\mathbb{E}_{\mathcal{D}\sim
p_{\mu}}\left[\bar{w}^{K}\mathbb{E}_{\bar{x}\sim\rho^{K}}\left[\frac{1}{k}\sum_{i=1}^{k}\Delta(\bar{x}_{i})\middle|\mathcal{D}\right]\right]-\mathbb{E}_{x\sim
p_{\pi}}[\Delta(x)]$ (23) $\displaystyle=\mathbb{E}_{\mathcal{D}\sim
p_{\mu}}\left[\bar{w}^{K}\sum_{j=1}^{n}\frac{w^{K}(\operatorname*{\mathbf{s}}_{j}^{\prime},\operatorname*{\mathbf{a}}_{j}^{\prime})}{\sum_{i=1}^{n}w^{K}(\operatorname*{\mathbf{s}}_{i}^{\prime},\operatorname*{\mathbf{a}}_{i}^{\prime})}\Delta(x)\right]-\mathbb{E}_{x\sim
p_{\pi}}[\Delta(x)]$ (24) $\displaystyle=\mathbb{E}_{\mathcal{D}\sim
p_{\mu}}\left[\frac{1}{n}\sum_{j=1}^{n}w^{K}({\operatorname*{\mathbf{s}}}_{j}^{\prime},{\operatorname*{\mathbf{a}}}_{j}^{\prime})\Delta(x)\right]-\mathbb{E}_{x\sim
p_{\pi}}[\Delta(x)]$ (25) $\displaystyle=\mathbb{E}_{\mathcal{D}\sim
p_{\mu}}\left[w^{K}(\operatorname*{\mathbf{s}^{\prime}},\operatorname*{\mathbf{a}^{\prime}})\Delta(x)\right]-\mathbb{E}_{x\sim
p_{\pi}}[\Delta(x)]$ (26)
$\displaystyle=\mathbb{E}_{(\operatorname*{\mathbf{s}},\operatorname*{\mathbf{a}},r,{\operatorname*{\mathbf{s}}}^{\prime})\sim
p_{\mu}}\left[\int\frac{1}{h^{d}}K\left(\frac{\operatorname*{\mathbf{a}}^{\prime}-\tilde{\pi}(\operatorname*{\mathbf{s}}^{\prime})}{h}\right)\left(r+\gamma
Q_{\bar{\theta}}({\operatorname*{\mathbf{s}}}^{\prime},{\operatorname*{\mathbf{a}}}^{\prime})-Q_{\theta}(\operatorname*{\mathbf{s}},\operatorname*{\mathbf{a}})\right)\nabla_{\theta}Q_{\theta}(\operatorname*{\mathbf{s}},\operatorname*{\mathbf{a}})d{\operatorname*{\mathbf{a}}}^{\prime}\right]$
(27) $\displaystyle\;\;\;\;\;\;-\mathbb{E}_{x\sim p_{\pi}}[\Delta(x)],$
$\displaystyle=\mathbb{E}_{(\operatorname*{\mathbf{s}},\operatorname*{\mathbf{a}},r,{\operatorname*{\mathbf{s}}}^{\prime})\sim
p_{\mu}}\left[\left(r+\gamma\left\\{Q_{\bar{\theta}}({\operatorname*{\mathbf{s}}}^{\prime},\tilde{\pi}({\operatorname*{\mathbf{s}}}^{\prime}))+\frac{h^{2}}{2}\int
K({\operatorname*{\mathbf{z}}}^{\prime})({\operatorname*{\mathbf{z}}}^{\prime})^{\top}\operatorname*{\mathbf{H}_{\mathbf{a}^{\prime}}}Q_{\bar{\theta}}({\operatorname*{\mathbf{s}}}^{\prime},{\operatorname*{\mathbf{a}}}^{\prime})|_{{\operatorname*{\mathbf{a}}}^{\prime}=\tilde{\pi}({\operatorname*{\mathbf{s}}}^{\prime})}{\operatorname*{\mathbf{z}}}^{\prime}d{\operatorname*{\mathbf{z}}}^{\prime}\right\\}\right.\right.$
(28)
$\displaystyle\;\;\;\;\;\;-Q_{\theta}(\operatorname*{\mathbf{s}},\operatorname*{\mathbf{a}})\bigg{)}\nabla_{\theta}Q_{\theta}(\operatorname*{\mathbf{s}},\operatorname*{\mathbf{a}})\bigg{]}+\mathcal{O}(h^{4})-\mathbb{E}_{x\sim
p_{\pi}}[\Delta(x)]$
$\displaystyle=\mathbb{E}_{(\operatorname*{\mathbf{s}},\operatorname*{\mathbf{a}},r,{\operatorname*{\mathbf{s}}}^{\prime})\sim
p_{\mu}}\left[\left(r+\gamma\left\\{Q_{\bar{\theta}}({\operatorname*{\mathbf{s}}}^{\prime},\tilde{\pi}({\operatorname*{\mathbf{s}}}^{\prime}))+\frac{h^{2}}{2}\operatorname{tr}\left[\int
K({\operatorname*{\mathbf{z}}}^{\prime}){\operatorname*{\mathbf{z}}}^{\prime}({\operatorname*{\mathbf{z}}}^{\prime})^{\top}d{\operatorname*{\mathbf{z}}}^{\prime}\operatorname*{\mathbf{H}_{\mathbf{a}^{\prime}}}Q_{\bar{\theta}}({\operatorname*{\mathbf{s}}}^{\prime},{\operatorname*{\mathbf{a}}}^{\prime})|_{{\operatorname*{\mathbf{a}}}^{\prime}=\tilde{\pi}({\operatorname*{\mathbf{s}}}^{\prime})}\right]\right\\}\right.\right.$
(29)
$\displaystyle\;\;\;\;\;\;-Q_{\theta}(\operatorname*{\mathbf{s}},\operatorname*{\mathbf{a}})\bigg{)}\nabla_{\theta}Q_{\theta}(\operatorname*{\mathbf{s}},\operatorname*{\mathbf{a}})\bigg{]}+\mathcal{O}(h^{4})-\mathbb{E}_{x\sim
p_{\pi}}[\Delta(x)]$ $\displaystyle=\frac{\gamma
h^{2}}{2}\mathbb{E}_{(\operatorname*{\mathbf{s}},\operatorname*{\mathbf{a}},r,{\operatorname*{\mathbf{s}}}^{\prime})\sim
p_{\mu}}\left[\nabla^{2}_{{\operatorname*{\mathbf{a}}}^{\prime}}Q_{\bar{\theta}}({\operatorname*{\mathbf{s}}}^{\prime},{\operatorname*{\mathbf{a}}}^{\prime})|_{{\operatorname*{\mathbf{a}}}^{\prime}=\tilde{\pi}({\operatorname*{\mathbf{s}}}^{\prime})}\nabla_{\theta}Q_{\theta}(\operatorname*{\mathbf{s}},\operatorname*{\mathbf{a}})\right]+\mathcal{O}(h^{4}),$
(30)

where $\nabla^{2}_{\operatorname*{\mathbf{a}^{\prime}}}$ and
$\operatorname*{\mathbf{H}_{\mathbf{a}^{\prime}}}$ are the Laplacian and
Hessian operator w.r.t. the next action $\operatorname*{\mathbf{a}^{\prime}}$
respectively, equality on Eq. (28) is obtained by applying Taylor expansion in
Eq. (27), and change-of-variable
${\operatorname*{\mathbf{z}}}^{\prime}=\frac{{\operatorname*{\mathbf{a}}}^{\prime}-\tilde{\pi}({\operatorname*{\mathbf{s}}}^{\prime})}{h}$.
The Taylor expansion is applied on
$Q_{\bar{\theta}}({\operatorname*{\mathbf{s}}}^{\prime},{\operatorname*{\mathbf{a}}}^{\prime})$
at
${\operatorname*{\mathbf{a}}}^{\prime}=\tilde{\pi}({\operatorname*{\mathbf{s}}}^{\prime})$.
The odd terms of the Taylor expansion are canceled out due to the symmetric
property of the Gaussian kernel. For the equality in Eq. (30), we used the
property of a Gaussian kernel $\int
K({\operatorname*{\mathbf{z}}}^{\prime}){\operatorname*{\mathbf{z}}}^{\prime}\left({\operatorname*{\mathbf{z}}}^{\prime}\right)^{\top}d{\operatorname*{\mathbf{z}}}^{\prime}=I$.

Derivation of the variance in Eq. (9):

$\displaystyle\operatorname{Var}[\widehat{\Delta}^{K}_{IR}]$
$\displaystyle=\underbrace{\mathbb{E}_{\mathcal{D}\sim
p_{\mu}}\left[\operatorname{Var}_{\bar{x}\sim\rho^{K}}[\widehat{\Delta}^{K}_{IR}\mid\mathcal{D}]\right]}_{=:A}+\underbrace{\operatorname{Var}_{\mathcal{D}\sim
p_{\mu}}\left[\mathbb{E}_{\bar{x}\sim\rho^{K}}[\widehat{\Delta}^{K}_{IR}\mid\mathcal{D}]\right]}_{=:B},$
(31) $\displaystyle A$ $\displaystyle=\mathbb{E}_{\mathcal{D}\sim
p_{\mu}}\left[(\bar{w}^{K})^{2}\operatorname{Var}_{\bar{x}\sim\rho^{K}}\left[\frac{1}{k}\sum_{j=1}^{k}\Delta(\bar{x}_{j})\mid\mathcal{D}\right]\right]$
(32) $\displaystyle=\mathbb{E}_{\mathcal{D}\sim
p_{\mu}}\left[\frac{\left(\bar{w}^{K}\right)^{2}}{k}\operatorname{Var}_{\bar{x}\sim\rho^{K}}\left[\Delta({\bar{x}})|\mathcal{D}\right]\right]$
(33) $\displaystyle=\mathbb{E}_{\mathcal{D}\sim
p_{\mu}}\left[\frac{\left(\bar{w}^{K}\right)^{2}}{k}\left\\{\mathbb{E}_{\bar{x}\sim\rho^{K}}\left[\|\Delta({\bar{x}})\|_{2}^{2}|\mathcal{D}\right]-\|\mathbb{E}_{\bar{x}\sim
p_{\mu}}\left[\Delta(\bar{x})|\mathcal{D}\right]\|_{2}^{2}\right\\}\right]$
(34) $\displaystyle=\frac{1}{n^{2}k}\mathbb{E}_{\mathcal{D}\sim
p_{\mu}}\Bigg{[}\left(\sum_{i=1}^{n}w^{K}({\operatorname*{\mathbf{s}}}_{i}^{\prime},{\operatorname*{\mathbf{a}}}_{i}^{\prime})\right)^{\cancel{2}}\sum_{j=1}^{n}\left(\frac{w^{K}({\operatorname*{\mathbf{s}}}_{j}^{\prime},{\operatorname*{\mathbf{a}}}_{j}^{\prime})}{\cancel{\sum_{i=1}^{n}w^{K}({\operatorname*{\mathbf{s}}}_{i}^{\prime},{\operatorname*{\mathbf{a}}}_{i}^{\prime})}}\right)\|\Delta({x_{j}})\|_{2}^{2}$
(35)
$\displaystyle\qquad\qquad\qquad\qquad\qquad\qquad-\cancel{\left(\sum_{i=1}^{n}w^{K}({\operatorname*{\mathbf{s}}}_{i}^{\prime},{\operatorname*{\mathbf{a}}}_{i}^{\prime})\right)^{2}}\Big{\|}\sum_{j=1}^{n}\frac{w^{K}({\operatorname*{\mathbf{s}}}_{j}^{\prime},{\operatorname*{\mathbf{a}}}_{j}^{\prime})}{\cancel{\sum_{i=1}^{n}w^{K}({\operatorname*{\mathbf{s}}}_{i}^{\prime},{\operatorname*{\mathbf{a}}}_{i}^{\prime})}}\Delta(x_{j})\Big{\|}^{2}_{2}\Bigg{]}$
$\displaystyle=\frac{1}{n^{2}k}\mathbb{E}_{\mathcal{D}\sim
p_{\mu}}\left[\cancel{\sum_{j=1}^{n}(w^{K}({\operatorname*{\mathbf{s}}}_{j}^{\prime},{\operatorname*{\mathbf{a}}}_{j}^{\prime}))^{2}\|\Delta({x_{j}})\|_{2}^{2}}+\sum_{i\neq
j}^{n,n}w^{K}({\operatorname*{\mathbf{s}}}_{i}^{\prime},{\operatorname*{\mathbf{a}}}_{i}^{\prime})w^{K}({\operatorname*{\mathbf{s}}}_{j}^{\prime},{\operatorname*{\mathbf{a}}}_{j}^{\prime})\|\Delta({x_{j}})\|_{2}^{2}\right.$
(36)
$\displaystyle\qquad\quad\left.-\left(\cancel{\sum_{j=1}^{n}(w^{K}({\operatorname*{\mathbf{s}}}_{j}^{\prime},{\operatorname*{\mathbf{a}}}_{j}^{\prime}))^{2}\|\Delta(x_{j})\|_{2}^{2}}+\sum_{i\neq
j}^{n,n}w^{K}({\operatorname*{\mathbf{s}}}_{i}^{\prime},{\operatorname*{\mathbf{a}}}_{i}^{\prime})w^{K}({\operatorname*{\mathbf{s}}}_{j}^{\prime},{\operatorname*{\mathbf{a}}}_{j}^{\prime})\Delta(x_{i})^{\top}\Delta(x_{j})\right)\right]$
$\displaystyle=\frac{n^{2}-n}{n^{2}k}\left\\{\cancel{\mathbb{E}_{x\sim
p_{\mu}}\left[w^{K}(\operatorname*{\mathbf{s}^{\prime}},\operatorname*{\mathbf{a}^{\prime}})\right]}\mathbb{E}_{x\sim
p_{\mu}}\left[w^{K}(\operatorname*{\mathbf{s}^{\prime}},\operatorname*{\mathbf{a}^{\prime}})\|\Delta({x})\|_{2}^{2}\right]\right.$
(37)
$\displaystyle\qquad\qquad\qquad\qquad\qquad\qquad\left.-\mathbb{E}_{x\sim
p_{\mu}}[w^{K}(\operatorname*{\mathbf{s}^{\prime}},\operatorname*{\mathbf{a}^{\prime}})\Delta(x)]^{\top}\mathbb{E}_{x\sim
p_{\mu}}[w^{K}(\operatorname*{\mathbf{s}^{\prime}},\operatorname*{\mathbf{a}^{\prime}})\Delta(x)]\right\\}$
$\displaystyle=\frac{n^{2}-n}{n^{2}k}\left\\{\mathbb{E}_{x\sim
p_{\mu}}\left[w^{K}(\operatorname*{\mathbf{s}^{\prime}},\operatorname*{\mathbf{a}^{\prime}})\|\Delta({x})\|_{2}^{2}\right]\right.$
(38) $\displaystyle\qquad\qquad\qquad\qquad\qquad\left.-\mathbb{E}_{x\sim
p_{\mu}}[w^{K}(\operatorname*{\mathbf{s}^{\prime}},\operatorname*{\mathbf{a}^{\prime}})\Delta(x)]^{\top}\mathbb{E}_{x\sim
p_{\mu}}[w^{K}(\operatorname*{\mathbf{s}^{\prime}},\operatorname*{\mathbf{a}^{\prime}})\Delta(x)]\right\\}$
$\displaystyle=\frac{n^{2}-n}{n^{2}k}\operatorname{Var}_{(\operatorname*{\mathbf{s}},\operatorname*{\mathbf{a}},r,{\operatorname*{\mathbf{s}}}^{\prime})\sim
p_{\mu},\operatorname*{\mathbf{a}}^{\prime}\sim\frac{1}{h^{d}}K\left(\frac{{\operatorname*{\mathbf{a}}}^{\prime}-\tilde{\pi}(\operatorname*{\mathbf{s}^{\prime}})}{h}\right)}\left[\Delta(x)\right]$
(39) $\displaystyle=\mathcal{O}\left(\frac{1}{k}\right),$ (40) $\displaystyle
B$ $\displaystyle=\operatorname{Var}_{\mathcal{D}\sim
p_{\mu}}[\mathbb{E}_{\bar{x}\sim\rho^{K}}[\widehat{\Delta}^{K}_{IR}|\mathcal{D}]]$
(41) $\displaystyle=\operatorname{Var}_{\mathcal{D}\sim
p_{\mu}}\left[\bar{w}^{K}\mathbb{E}_{\bar{x}\sim\rho^{K}}\left[\cancel{\frac{1}{k}\sum_{j=1}^{k}}\Delta(\bar{x}_{j})\Bigg{|}\mathcal{D}\right]\right]$
(42) $\displaystyle=\operatorname{Var}_{\mathcal{D}\sim
p_{\mu}}\left[\frac{1}{n}\cancel{\sum_{i=1}^{n}w^{K}({\operatorname*{\mathbf{s}}}_{i}^{\prime},{\operatorname*{\mathbf{a}}}_{i}^{\prime})}\left[\sum_{j=1}^{n}\frac{w^{K}({\operatorname*{\mathbf{s}}}_{j}^{\prime},{\operatorname*{\mathbf{a}}}_{j}^{\prime})}{\cancel{\sum_{i=1}^{n}w^{K}({\operatorname*{\mathbf{s}}}_{i}^{\prime},{\operatorname*{\mathbf{a}}}_{i}^{\prime})}}\Delta(x_{j})\right]\right]$
(43) $\displaystyle=\frac{1}{n}\operatorname{Var}_{x\sim
p_{\mu}}\left[w^{K}(\operatorname*{\mathbf{s}^{\prime}},\operatorname*{\mathbf{a}^{\prime}})\Delta(x)\right]$
(44) $\displaystyle=\frac{1}{n}\left\\{\underbrace{\mathbb{E}_{x\sim
p_{\mu}}[(w^{K}(\operatorname*{\mathbf{s}^{\prime}},\operatorname*{\mathbf{a}^{\prime}}))^{2}\|\Delta(x)\|_{2}^{2}]}_{=:X}-\underbrace{\|\mathbb{E}_{x\sim
p_{\mu}}[w^{K}(\operatorname*{\mathbf{s}^{\prime}},\operatorname*{\mathbf{a}^{\prime}})\Delta(x)]\|_{2}^{2}}_{=\|\operatorname{Bias}[\widehat{\Delta}_{IR}]+\Delta_{TD}\|_{2}^{2}=\mathcal{O}(1)}\right\\}$
(45) $\displaystyle=\frac{X}{n}+\mathcal{O}\left(\frac{1}{n}\right),$ (46)

$\displaystyle X$
$\displaystyle=\mathbb{E}_{(\operatorname*{\mathbf{s}},\operatorname*{\mathbf{a}},r,{\operatorname*{\mathbf{s}}}^{\prime})\sim
p_{\mu}}\Bigg{[}\int\frac{1}{h^{2d}}K\left(\frac{{\operatorname*{\mathbf{a}}}^{\prime}-\tilde{\pi}({\operatorname*{\mathbf{s}}}^{\prime})}{h}\right)^{2}\underbrace{\frac{(R(\operatorname*{\mathbf{s}},\operatorname*{\mathbf{a}})+\gamma
Q_{\bar{\theta}}({\operatorname*{\mathbf{s}}}^{\prime},{\operatorname*{\mathbf{a}}}^{\prime})-Q_{\theta}(\operatorname*{\mathbf{s}},\operatorname*{\mathbf{a}}))^{2}}{\mu({\operatorname*{\mathbf{a}}}^{\prime}|{\operatorname*{\mathbf{s}}}^{\prime})}}_{=:g(\operatorname*{\mathbf{s}},\operatorname*{\mathbf{a}},r,{\operatorname*{\mathbf{s}}}^{\prime},{\operatorname*{\mathbf{a}}}^{\prime})}\|\nabla_{\theta}Q_{\theta}(\operatorname*{\mathbf{s}},\operatorname*{\mathbf{a}})\|_{2}^{2}d{\operatorname*{\mathbf{a}}}^{\prime}\Bigg{]}$
(47)
$\displaystyle=\mathbb{E}_{(\operatorname*{\mathbf{s}},\operatorname*{\mathbf{a}},r,{\operatorname*{\mathbf{s}}}^{\prime})\sim
p_{\mu}}\Bigg{[}\int\frac{K({\operatorname*{\mathbf{z}}}^{\prime})^{2}}{h^{\cancel{2}d}}g(\operatorname*{\mathbf{s}},\operatorname*{\mathbf{a}},r,{\operatorname*{\mathbf{s}}}^{\prime},h{\operatorname*{\mathbf{z}}}^{\prime}+\pi({\operatorname*{\mathbf{s}}}^{\prime}))\|\nabla_{\theta}Q_{\theta}(\operatorname*{\mathbf{s}},\operatorname*{\mathbf{a}})\|_{2}^{2}\cancel{h^{d}}d{\operatorname*{\mathbf{z}}}^{\prime}\Bigg{]}$
(48)
$\displaystyle=\frac{C(K)}{h^{d}}\mathbb{E}_{(\operatorname*{\mathbf{s}},\operatorname*{\mathbf{a}},r,{\operatorname*{\mathbf{s}}}^{\prime})\sim
p_{\mu}}\Bigg{[}g(\operatorname*{\mathbf{s}},\operatorname*{\mathbf{a}},r,{\operatorname*{\mathbf{s}}}^{\prime},\pi({\operatorname*{\mathbf{s}}}^{\prime}))\|\nabla_{\theta}Q_{\theta}(\operatorname*{\mathbf{s}},\operatorname*{\mathbf{a}})\|_{2}^{2}\Bigg{]}+\mathcal{O}\left(\frac{1}{h^{d-2}}\right),$
(49)

where $C(K):=\int K(\mathbf{z})^{2}d\mathbf{z}$, the equality in Eq. (48) is
made by applying change-of-variable
$\operatorname*{\mathbf{z}^{\prime}}=\frac{\operatorname*{\mathbf{a}^{\prime}}-\tilde{\pi}(\operatorname*{\mathbf{s}^{\prime}})}{h}$
in Eq. (47), and the equality in Eq. (49) is made by applying Taylor expansion
on
$g(\operatorname*{\mathbf{s}},\operatorname*{\mathbf{a}},r,\operatorname*{\mathbf{s}^{\prime}},\operatorname*{\mathbf{a}^{\prime}})$
at
$\operatorname*{\mathbf{a}^{\prime}}=\tilde{\pi}(\operatorname*{\mathbf{s}^{\prime}})$
in Eq. (48).

By plugging in Eq. (49) to Eq. (46),

$\displaystyle B$
$\displaystyle=\frac{C(K)}{nh^{d}}\mathbb{E}_{(\operatorname*{\mathbf{s}},\operatorname*{\mathbf{a}},r,\operatorname*{\mathbf{s}}^{\prime})\sim
p_{\mu}}\left[\frac{(R(\operatorname*{\mathbf{s}},\operatorname*{\mathbf{a}})+\gamma
Q_{\bar{\theta}}(\operatorname*{\mathbf{s}}^{\prime},\pi(\operatorname*{\mathbf{s}}^{\prime}))-Q_{\theta}(\operatorname*{\mathbf{s}},\operatorname*{\mathbf{a}}))^{2}\|\nabla_{\theta}Q_{\theta}(\operatorname*{\mathbf{s}},\operatorname*{\mathbf{a}})\|_{2}^{2}}{\mu(\tilde{\pi}(\operatorname*{\mathbf{s}^{\prime}})|\operatorname*{\mathbf{s}^{\prime}})}\right]+\mathcal{O}\left(\frac{1}{nh^{d-2}}\right).$
(50)

By substituting Eq. (40) and Eq. (50) into Eq. (31), and since the mini-batch
size $k$ is a constant multiple of $n$,

$\displaystyle\therefore\operatorname{Var}[\widehat{\Delta}^{K}_{IR}]$
$\displaystyle=\frac{C(K)}{nh^{d}}\mathbb{E}_{p_{\mu}}\left[\frac{(R(\operatorname*{\mathbf{s}},\operatorname*{\mathbf{a}})+\gamma
Q_{\bar{\theta}}(\operatorname*{\mathbf{s}}^{\prime},\tilde{\pi}(\operatorname*{\mathbf{s}}^{\prime}))-Q_{\theta}(\operatorname*{\mathbf{s}},\operatorname*{\mathbf{a}}))^{2}\|\nabla_{\theta}Q_{\theta}(\operatorname*{\mathbf{s}},\operatorname*{\mathbf{a}})\|^{2}_{2}}{\mu(\tilde{\pi}(\operatorname*{\mathbf{s}}^{\prime})|\operatorname*{\mathbf{s}}^{\prime})}\right]+\mathcal{O}\left(\frac{1}{nh^{d-2}}\right)$
(51)

∎

###  A.2 Proof of Corolloary 1

######  Corollary 1.

Under Assumption 1-2, MSE between the TD update vector estimate
$\widehat{\Delta}_{IR}^{K}$ and the on-policy TD update vector $\Delta_{TD}$
is:

$\displaystyle\operatorname{MSE}(h,n,k,d)$
$\displaystyle=\underbrace{h^{4}\|\operatorname*{\mathbf{b}}\|^{2}_{2}+\frac{v}{nh^{d}}}_{=:\operatorname{LOMSE}(h,n,d)}+\mathcal{O}\left(h^{6}\right)+\mathcal{O}\left(\frac{1}{nh^{d-2}}\right),$
(52)

where $\operatorname{LOMSE}\left(h,n,d\right)$ is the leading-order MSE.

###### Proof.

$\displaystyle\operatorname{MSE}(h,n,k,d)$
$\displaystyle=\left\|\operatorname{Bias}\left[\widehat{\Delta}_{IR}^{K}\right]\right\|_{2}^{2}+\operatorname{Var}\left[\widehat{\Delta}_{IR}^{K}\right]$
(53)
$\displaystyle=\underbrace{h^{4}\|\operatorname*{\mathbf{b}}\|^{2}_{2}+\frac{v}{nh^{d}}}_{=:\operatorname{LOMSE}(h,n,d)}+\mathcal{O}\left(h^{6}\right)+\mathcal{O}\left(\frac{1}{nh^{d-2}}\right).$
(54)

∎

###  A.3 Proof of Proposition 1

######  Proposition 1.

The optimal bandwidth $h^{*}$ that minimizes the $LOMSE(h,n,d)$ is:

$\displaystyle
h^{*}=\left(\frac{vd}{4n\|\operatorname*{\mathbf{b}}\|^{2}_{2}}\right)^{\frac{1}{d+4}}.$
(55)

###### Proof.

The $\operatorname{LOMSE}(h,n,d)$ (Eq. (10)) minimizing optimal bandwidth
$h^{*}$ is:

$\displaystyle\frac{d}{dh}\left(\operatorname{LOMSE}\left(h,n,d\right)\right)$
$\displaystyle=4h^{3}\|\operatorname*{\mathbf{b}}\|_{2}^{2}-\frac{vd}{nh^{d+1}}\text{,
}$ (56) $\displaystyle\therefore h^{*}$
$\displaystyle=\left(\frac{vd}{4n\|\operatorname*{\mathbf{b}}\|^{2}_{2}}\right)^{\frac{1}{d+4}}.$
(57)

∎

###  A.4 Proof of Proposition 2

######  Proposition 2.

Given optimal bandwidth $h^{*}$ (Eq. (11)), in high-dimensional action space,
the squared L2-norm of leading-order bias
$h^{4}\|\operatorname*{\mathbf{b}}\|_{2}^{2}$ dominates over the leading-order
variance $\tfrac{v}{nh^{d}}$ in LOMSE (Eq. (10)). Furthermore,
$\operatorname{LOMSE}(h^{*},n,d)$ approximates to
$\|\operatorname*{\mathbf{b}}\|_{2}^{2}$.

###### Proof.

$\operatorname{LOMSE}(h,n,d)$ in Eq. (10) is composed of leading-order bias
$\operatorname{LoBias}(h)$ and leading-order variance
$\operatorname{LoVar}(h,n,d)$:

$\displaystyle\operatorname{LoBias}(h):$
$\displaystyle=h^{2}\operatorname*{\mathbf{b}},$ (58)
$\displaystyle\operatorname{LoVar}(h,n,d)$ $\displaystyle:=\frac{v}{nh^{d}}.$
(59)

The ratio of $\|\operatorname{LoBias}(h^{*})\|^{2}_{2}$ and
$\operatorname{LoVar}(h^{*},n,d)$ with $h^{*}$ in Eq. (11) that together
compose $\operatorname{LOMSE}(h^{*},n,d)$ as $d\rightarrow\infty$ is:

$\displaystyle\lim_{d\rightarrow\infty}\frac{\|\operatorname{LoBias}(h^{*})\|^{2}_{2}}{\operatorname{LoVar}(h^{*},n,d)}=\lim_{d\rightarrow\infty}\frac{d}{4}=\infty.$
(60)

From Eq. (60), it can be observed that the leading-order bias dominates over
the leading-order variance in LOMSE when $d\gg 4$.

By plugging in $h^{*}$ (Eq. (11)) to the LOMSE in Eq. (10), and taking limit
$d\rightarrow\infty$, we derive similar relation between LOMSE and the bias as
in the work of Noh et al. (2017) that learned metric for kernel regression:

$\displaystyle\operatorname{LOMSE}(h^{*},n,d)$
$\displaystyle=n^{-\frac{4}{d+4}}\left(\left(\frac{d}{4}\right)^{\frac{4}{d+4}}+\left(\frac{4}{d}\right)^{\frac{d}{d+4}}\right)\|\operatorname*{\mathbf{b}}\|^{\frac{2d}{d+4}}v^{\frac{4}{d+4}},$
(61)
$\displaystyle\therefore\lim_{d\rightarrow\infty}\operatorname{LOMSE}(h^{*},n,d)$
$\displaystyle=\|\operatorname*{\mathbf{b}}\|_{2}^{2}.$ (62)

From Eq. (61) and Eq. (62), it can be observed that for a high-dimensional
action space with $d\gg 4$ and when the optimal bandwidth $h^{*}$ is used, the
LOMSE can be approximated to $\|\operatorname*{\mathbf{b}}\|_{2}^{2}$.

∎

###  A.5 Derivation of the bias with metric

Bias of the update vector estimation (Eq. (27)) with kernel inputs linearly
transformed by $L(\operatorname*{\mathbf{s}^{\prime}})$ $\left(\text{i.e.,
}\operatorname*{\mathbf{z}^{\prime}}=\frac{L(\operatorname*{\mathbf{s}^{\prime}})^{\top}(\operatorname*{\mathbf{a}^{\prime}}-\tilde{\pi}(\operatorname*{\mathbf{s}^{\prime}}))}{h}\right)$
is:

$\displaystyle\operatorname{Bias}$ $\displaystyle[\hat{\Delta}^{K}_{IR}]$
$\displaystyle=\mathbb{E}_{(\operatorname*{\mathbf{s}},\operatorname*{\mathbf{a}},r,{\operatorname*{\mathbf{s}}}^{\prime})\sim
p_{\mu}}\left[\int\tfrac{1}{h^{d}}K\left(\tfrac{L(\operatorname*{\mathbf{s}^{\prime}})^{\top}(\operatorname*{\mathbf{a}}^{\prime}-\tilde{\pi}(\operatorname*{\mathbf{s}}^{\prime}))}{h}\right)\left(r+\gamma
Q_{\bar{\theta}}({\operatorname*{\mathbf{s}}}^{\prime},{\operatorname*{\mathbf{a}}}^{\prime})-Q_{\theta}(\operatorname*{\mathbf{s}},\operatorname*{\mathbf{a}})\right)\nabla_{\theta}Q_{\theta}(\operatorname*{\mathbf{s}},\operatorname*{\mathbf{a}})d{\operatorname*{\mathbf{a}}}^{\prime}\right]$
(63) $\displaystyle\;\;\;\;\;\;-\mathbb{E}_{x\sim p_{\pi}}[\Delta(x)],$
$\displaystyle=\mathbb{E}_{(\operatorname*{\mathbf{s}},\operatorname*{\mathbf{a}},r,{\operatorname*{\mathbf{s}}}^{\prime})\sim
p_{\mu}}\bigg{[}\bigg{(}r+\gamma\bigg{\\{}Q_{\bar{\theta}}({\operatorname*{\mathbf{s}}}^{\prime},\tilde{\pi}({\operatorname*{\mathbf{s}}}^{\prime}))$
(64) $\displaystyle\;\;\;\;\;\;+\tfrac{h^{2}}{2}\int
K({\operatorname*{\mathbf{z}}}^{\prime})({\operatorname*{\mathbf{z}}}^{\prime})^{\top}L(\operatorname*{\mathbf{s}^{\prime}})^{-1}\operatorname*{\mathbf{H}_{\mathbf{a}^{\prime}}}Q_{\bar{\theta}}({\operatorname*{\mathbf{s}}}^{\prime},{\operatorname*{\mathbf{a}}}^{\prime})|_{{\operatorname*{\mathbf{a}}}^{\prime}=\tilde{\pi}({\operatorname*{\mathbf{s}}}^{\prime})}L(\operatorname*{\mathbf{s}^{\prime}})^{-\top}{\operatorname*{\mathbf{z}}}^{\prime}d{\operatorname*{\mathbf{z}}}^{\prime}\bigg{\\}}$
$\displaystyle\;\;\;\;\;\;-Q_{\theta}(\operatorname*{\mathbf{s}},\operatorname*{\mathbf{a}})\bigg{)}\nabla_{\theta}Q_{\theta}(\operatorname*{\mathbf{s}},\operatorname*{\mathbf{a}})\bigg{]}+\mathcal{O}(h^{4})-\mathbb{E}_{x\sim
p_{\pi}}[\Delta(x)]$
$\displaystyle=\mathbb{E}_{(\operatorname*{\mathbf{s}},\operatorname*{\mathbf{a}},r,{\operatorname*{\mathbf{s}}}^{\prime})\sim
p_{\mu}}\bigg{[}\bigg{(}\tfrac{h^{2}\gamma}{2}\operatorname{tr}\bigg{[}L(\operatorname*{\mathbf{s}^{\prime}})^{-\top}\underbrace{\int
K({\operatorname*{\mathbf{z}}}^{\prime}){\operatorname*{\mathbf{z}}}^{\prime}({\operatorname*{\mathbf{z}}}^{\prime})^{\top}d{\operatorname*{\mathbf{z}}}^{\prime}}_{=I}L(\operatorname*{\mathbf{s}^{\prime}})^{-1}\operatorname*{\mathbf{H}_{\mathbf{a}^{\prime}}}Q_{\bar{\theta}}({\operatorname*{\mathbf{s}}}^{\prime},{\operatorname*{\mathbf{a}}}^{\prime})|_{{\operatorname*{\mathbf{a}}}^{\prime}=\tilde{\pi}({\operatorname*{\mathbf{s}}}^{\prime})}\bigg{]}$
(65)
$\displaystyle\;\;\;\;\;\;\bigg{)}\nabla_{\theta}Q_{\theta}(\operatorname*{\mathbf{s}},\operatorname*{\mathbf{a}})\bigg{]}+\mathcal{O}(h^{4})$
$\displaystyle=h^{2}\cdot\underbrace{\frac{\gamma}{2}\mathbb{E}_{(\operatorname*{\mathbf{s}},\operatorname*{\mathbf{a}},r,\operatorname*{\mathbf{s}}^{\prime})\sim
p_{\mu}}\left[\operatorname{tr}\left[A(\operatorname*{\mathbf{s}^{\prime}})^{-1}\operatorname*{\mathbf{H}_{\mathbf{a}^{\prime}}}Q_{\bar{\theta}}(\operatorname*{\mathbf{s}^{\prime}},\operatorname*{\mathbf{a}^{\prime}})|_{\operatorname*{\mathbf{a}^{\prime}}=\tilde{\pi}(\operatorname*{\mathbf{s}^{\prime}})}\right]\nabla_{\theta}Q(\operatorname*{\mathbf{s}},\operatorname*{\mathbf{a}})\right]}_{=:{\operatorname*{\mathbf{b}}}_{A}}.$
(66)

For the second equality in Eq. (64), we used Taylor expansion on
$Q_{\bar{\theta}}(\operatorname*{\mathbf{s}^{\prime}},\operatorname*{\mathbf{a}^{\prime}})$
at
$\operatorname*{\mathbf{a}^{\prime}}=\tilde{\pi}(\operatorname*{\mathbf{s}^{\prime}})$.
The odd terms of the Taylor expansion are canceled out due to the symmetric
property of the Gaussian kernel. For the last equality, we use the relation
$A(\operatorname*{\mathbf{s}^{\prime}})=L(\operatorname*{\mathbf{s}^{\prime}})L(\operatorname*{\mathbf{s}^{\prime}})^{\top}$.

$\displaystyle\therefore\|{\operatorname*{\mathbf{b}}}_{A}\|_{2}^{2}$
$\displaystyle=\frac{\gamma^{2}}{4}\|\mathbb{E}_{\mathcal{D}\sim
p_{\mu}}\left[\operatorname{tr}\left[A({\operatorname*{\mathbf{s}}}^{\prime})^{-1}\operatorname*{\mathbf{H}_{\mathbf{a}^{\prime}}}Q_{\bar{\theta}}({\operatorname*{\mathbf{s}}}^{\prime},{\operatorname*{\mathbf{a}}}^{\prime})|_{{\operatorname*{\mathbf{a}}}^{\prime}=\tilde{\pi}({\operatorname*{\mathbf{s}}}^{\prime})}\right]\nabla_{\theta}Q(\operatorname*{\mathbf{s}},\operatorname*{\mathbf{a}})\right]\|_{2}^{2}.$

###  A.6 Proof of Theorem 2

######  Theorem 2.

Under Assumption 3, denoting $m$ iterative applications of $T$ and $T_{K}$ to
an arbitrary $Q$ as $T^{m}Q$ and $T_{K}^{m}Q$ respectively, and $h$ and
$A(\operatorname*{\mathbf{s}^{\prime}})$ as an arbitrary bandwidth and metric
respectively, the following holds:

$\displaystyle\|Q^{\pi}-\lim_{m\rightarrow\infty}T_{K}^{m}Q\|_{\infty}\leq\frac{\gamma\xi}{1-\gamma},$
(67)
$\displaystyle\qquad\xi:=\max_{m,\\{\operatorname*{\mathbf{s}},\operatorname*{\mathbf{a}}\\}\in
S\times A}\frac{h^{2}}{2}\mathbb{E}_{\operatorname*{\mathbf{s}^{\prime}}\sim
P(\operatorname*{\mathbf{s}^{\prime}}|\operatorname*{\mathbf{s}},\operatorname*{\mathbf{a}})}\left[\left|\operatorname{tr}\left(A(\operatorname*{\mathbf{s}^{\prime}})^{-1}\operatorname*{\mathbf{H}_{\mathbf{a}^{\prime}}}T_{K}^{m}Q(\operatorname*{\mathbf{s}^{\prime}},\operatorname*{\mathbf{a}^{\prime}})|_{\operatorname*{\mathbf{a}^{\prime}}=\tilde{\pi}(\operatorname*{\mathbf{s}^{\prime}})}\right)\right|\right]+|\mathcal{O}((h)^{4})|.$
(68)

###### Proof.

Derive $\|TQ-T_{K}Q\|_{\infty}/\gamma$ w.r.t. $h$ and
$A(\operatorname*{\mathbf{s}^{\prime}})$ by using Taylor expansion at
$\operatorname*{\mathbf{a}^{\prime}}=\tilde{\pi}(\operatorname*{\mathbf{s}^{\prime}})$:

$\displaystyle\|TQ-T_{K}Q\|_{\infty}/\gamma$
$\displaystyle=\max_{\\{\operatorname*{\mathbf{s}},\operatorname*{\mathbf{a}}\\}\in
S\times A}\left|\mathbb{E}_{\operatorname*{\mathbf{s}^{\prime}}\sim
P(\operatorname*{\mathbf{s}^{\prime}}|\operatorname*{\mathbf{s}},\operatorname*{\mathbf{a}})}\left[\int
K\left(\frac{L_{Q}^{*}(\operatorname*{\mathbf{s}^{\prime}})^{\top}(\operatorname*{\mathbf{a}^{\prime}}-\tilde{\pi}(\operatorname*{\mathbf{s}^{\prime}}))}{h_{Q}^{*}}\right)Q(\operatorname*{\mathbf{s}^{\prime}},\operatorname*{\mathbf{a}^{\prime}})d\operatorname*{\mathbf{a}^{\prime}}-Q(\operatorname*{\mathbf{s}^{\prime}},\tilde{\pi}(\operatorname*{\mathbf{s}^{\prime}}))\right]\right|$
$\displaystyle=\max_{\\{\operatorname*{\mathbf{s}},\operatorname*{\mathbf{a}}\\}\in
S\times A}\left|\mathbb{E}_{\operatorname*{\mathbf{s}^{\prime}}\sim
P(\operatorname*{\mathbf{s}^{\prime}}|\operatorname*{\mathbf{s}},\operatorname*{\mathbf{a}})}\left[\int
K(\operatorname*{\mathbf{z}^{\prime}})\left(\tfrac{(h_{Q}^{*})^{2}}{2}(\operatorname*{\mathbf{z}^{\prime}})^{\top}L_{Q}^{*}(\operatorname*{\mathbf{s}^{\prime}})^{-1}H_{\operatorname*{\mathbf{a}^{\prime}}}Q(\operatorname*{\mathbf{s}^{\prime}},\operatorname*{\mathbf{a}^{\prime}})|_{\operatorname*{\mathbf{a}^{\prime}}=\tilde{\pi}(\operatorname*{\mathbf{s}^{\prime}})}L_{Q}^{*}(\operatorname*{\mathbf{s}^{\prime}})^{-\top}\operatorname*{\mathbf{z}^{\prime}}\right.\right.\right.$
$\displaystyle\left.\left.\left.+\mathcal{O}((h_{Q}^{*})^{4})\right)d\operatorname*{\mathbf{z}^{\prime}}\right]\right|$
$\displaystyle=\max_{\\{\operatorname*{\mathbf{s}},\operatorname*{\mathbf{a}}\\}\in
S\times A}\left|\mathbb{E}_{\operatorname*{\mathbf{s}^{\prime}}\sim
P(\operatorname*{\mathbf{s}^{\prime}}|\operatorname*{\mathbf{s}},\operatorname*{\mathbf{a}})}\left[\frac{(h_{Q}^{*})^{2}}{2}\operatorname{tr}\left(A_{Q}^{*}(\operatorname*{\mathbf{s}^{\prime}})^{-1}H_{\operatorname*{\mathbf{a}^{\prime}}}Q(\operatorname*{\mathbf{s}^{\prime}},\operatorname*{\mathbf{a}^{\prime}})|_{\operatorname*{\mathbf{a}^{\prime}}=\tilde{\pi}(\operatorname*{\mathbf{s}^{\prime}})}\right)+\mathcal{O}((h_{Q}^{*})^{4})\right]\right|$
$\displaystyle\leq\underbrace{\max_{\\{\operatorname*{\mathbf{s}},\operatorname*{\mathbf{a}}\\}\in
S\times
A}\frac{(h_{Q}^{*})^{2}}{2}\mathbb{E}_{\operatorname*{\mathbf{s}^{\prime}}\sim
P(\operatorname*{\mathbf{s}^{\prime}}|\operatorname*{\mathbf{s}},\operatorname*{\mathbf{a}})}\left[\left|\operatorname{tr}\left(A_{Q}^{*}(\operatorname*{\mathbf{s}^{\prime}})^{-1}H_{\operatorname*{\mathbf{a}^{\prime}}}Q(\operatorname*{\mathbf{s}^{\prime}},\operatorname*{\mathbf{a}^{\prime}})|_{\operatorname*{\mathbf{a}^{\prime}}=\tilde{\pi}(\operatorname*{\mathbf{s}^{\prime}})}\right)\right|\right]+|\mathcal{O}((h_{Q}^{*})^{4})|}_{=:\xi}$
(69)

where we used
$\operatorname*{\mathbf{z}^{\prime}}:=\frac{L(\operatorname*{\mathbf{s}^{\prime}})^{\top}(\operatorname*{\mathbf{a}^{\prime}}-\tilde{\pi}(\operatorname*{\mathbf{s}^{\prime}}))}{h}$,
symmetricity of kernel
$K(\operatorname*{\mathbf{z}^{\prime}})=K(-\operatorname*{\mathbf{z}^{\prime}})$,
and $\int
K(\operatorname*{\mathbf{z}^{\prime}})\operatorname*{\mathbf{z}^{\prime}}\operatorname*{\mathbf{z}^{\prime}}^{\top}d\operatorname*{\mathbf{z}^{\prime}}=I$.

Next, we conjecture that
$\|T^{m}Q-T_{K}^{m}Q\|_{\infty}\leq\sum_{i=1}^{m}\gamma^{i}\xi$,

(i) For $m=1$, the conjecture is true by the definition of $\xi$ in Eq. (69).

(ii) Assuming that the conjecture is true for an arbitrary $m=j$,

$\displaystyle\|T^{j}Q-T_{K}^{j}Q\|_{\infty}$
$\displaystyle\leq\sum_{i=1}^{j}\gamma^{i}\xi,$ (70)
$\displaystyle\|T^{j+1}Q-T_{K}^{j+1}Q\|_{\infty}$
$\displaystyle\leq\|(T-T_{K})T_{K}^{j}Q\|_{\infty}+\|T(T^{j}Q-T_{K}^{j}Q)\|_{\infty}$
(71) $\displaystyle\leq\gamma\xi+\sum_{i=1}^{j}\gamma^{i+1}\xi$ (72)
$\displaystyle=\sum_{i=1}^{j+1}\gamma^{i}\xi$ (73)

$\therefore$ From (i) and (ii), the conjecture is proved to be true. Using the
relation $T^{\infty}Q=Q^{\pi}$, Eq.(5) can be derived. Eq.(6) can be derived
similarly.

∎

##  Appendix B Pseudo Code for KMIFQE

Algorithm 1 Kernel Metric Learning for In-Sample Fitted Q Evaluation

1:Offline data
$\mathcal{D}=\\{\operatorname*{\mathbf{s}}_{i},\operatorname*{\mathbf{a}}_{i},r_{i},\operatorname*{\mathbf{s}}_{i}^{\prime},\operatorname*{\mathbf{a}}_{i}^{\prime}\\}_{i=1}^{n}$,
stochastic behavior policy $\mu$, deterministic target policy $\tilde{\pi}$,
Q-function $Q_{\theta}$ with parameter $\theta$, target network
$Q_{\bar{\theta}}$ parameterized by $\bar{\theta}$, Gaussian kernel $K$,
initial linear transformation matrix $L({\operatorname*{\mathbf{s}}}_{i})=I$
for all $i$, learning rate $\alpha$, number of TD update iterations $N$, mini-
batch size $k$.

2:Estimated target policy value $\widehat{V}(\pi)$.

3:for until convergence do

4: for $N$ steps do

5: Update the bandwidth
$h=\left(\frac{vd}{4n\|\operatorname*{\mathbf{b}}\|^{2}_{2}}\right)^{\frac{1}{d+4}}$
(Eq. (11)),  $\displaystyle\text{where }\operatorname*{\mathbf{b}}$
$\displaystyle:=\frac{\gamma}{2k}\sum_{i=1}^{k}\nabla^{2}_{\operatorname*{\mathbf{a}}^{\prime}}Q_{\bar{\theta}}({\operatorname*{\mathbf{s}}}_{i}^{\prime},{\operatorname*{\mathbf{a}}}^{\prime})|_{{\operatorname*{\mathbf{a}}}^{\prime}=\tilde{\pi}({\operatorname*{\mathbf{s}}}_{i}^{\prime})}\nabla_{\theta}Q_{\theta}({\operatorname*{\mathbf{s}}}_{i},{\operatorname*{\mathbf{a}}}_{i}),$
$\displaystyle v$
$\displaystyle:=\frac{C(K)}{k}\sum_{i=1}^{k}\left[\frac{\left(r_{i}+\gamma
Q_{\bar{\theta}}\left(\mathbf{s}_{i}^{\prime},\tilde{\pi}\left(\mathbf{s}_{i}^{\prime}\right)\right)-Q_{\theta}(\mathbf{s}_{i},\mathbf{a}_{i})\right)^{2}\left\|\nabla_{\theta}Q_{\theta}(\mathbf{s}_{i},\mathbf{a}_{i})\right\|_{2}^{2}}{\mu\left(\tilde{\pi}\left(\mathbf{s}_{i}^{\prime}\right)\mid\mathbf{s}_{i}^{\prime}\right)}\right],$
$\displaystyle C(K)$ $\displaystyle:=\int K(\mathbf{z})^{2}d\mathbf{z}.$

6: Compute IS ratio for each sample $i$:
$w^{K}(\operatorname*{\mathbf{s}}_{i}^{\prime},\operatorname*{\mathbf{a}}_{i}^{\prime}):=\tfrac{1}{h^{d}\mu(\operatorname*{\mathbf{a}}_{i}^{\prime}|\operatorname*{\mathbf{s}}_{i}^{\prime})}K\left(\tfrac{L(\operatorname*{\mathbf{s}}_{i}^{\prime})^{\top}(\operatorname*{\mathbf{a}}_{i}^{\prime}-\tilde{\pi}(\operatorname*{\mathbf{s}}_{i}^{\prime}))}{h}\right)$

7: Compute resampling probability for each sample:
$\rho_{i}^{K}=\tfrac{w^{K}(\operatorname*{\mathbf{s}}_{i}^{\prime},\operatorname*{\mathbf{a}}_{i}^{\prime})}{\sum_{j=1}^{n}w^{K}(\operatorname*{\mathbf{s}}_{j}^{\prime},\operatorname*{\mathbf{a}}_{j}^{\prime})}$

8: Sample $k$ transitions with $\rho^{K}$:
$\bar{x}_{j}\stackrel{{\scriptstyle\rho^{K}}}{{\sim}}\left\\{x_{1},\ldots,x_{n}\right\\}$,
where
$x_{i}:=\\{\operatorname*{\mathbf{s}}_{i},\operatorname*{\mathbf{a}}_{i},r_{i},{\operatorname*{\mathbf{s}}}_{i}^{\prime},{\operatorname*{\mathbf{a}}}_{i}^{\prime}\\}$

9: Compute the estimated expectation of the update vector
$\widehat{\Delta}_{IR}^{K}=\tfrac{\bar{w}^{K}}{k}\sum_{j=1}^{k}\Delta\left(\bar{x}_{j}\right)$
in Eq. (7)

10: Update $\theta$ $\displaystyle\theta$
$\displaystyle\leftarrow\theta+\alpha\widehat{\Delta}^{K}_{IR}$

11: end for

12: Update $\bar{\theta}$ $\displaystyle\bar{\theta}$
$\displaystyle\leftarrow\theta$

13: Update linear transformation matrix
$L(\operatorname*{\mathbf{s}}_{i}^{\prime})$
($A(\operatorname*{\mathbf{s}}_{i}^{\prime})=L(\operatorname*{\mathbf{s}}_{i}^{\prime})L(\operatorname*{\mathbf{s}}_{i}^{\prime})^{\top})$)
for each sample  $\displaystyle L(\mathbf{s}_{i})$
$\displaystyle=\alpha({\operatorname*{\mathbf{s}}}_{i}^{\prime})^{\frac{1}{2}}\left[U_{+}({\operatorname*{\mathbf{s}}}_{i}^{\prime})U_{-}({\operatorname*{\mathbf{s}}}_{i}^{\prime})\right]\left(\begin{array}[]{cc}d_{+}({\operatorname*{\mathbf{s}}}_{i}^{\prime})\Lambda_{+}({\operatorname*{\mathbf{s}}}_{i}^{\prime})&0\\\
0&-d_{-}({\operatorname*{\mathbf{s}}}_{i}^{\prime})\Lambda_{-}({\operatorname*{\mathbf{s}}}_{i}^{\prime})\end{array}\right)^{\frac{1}{2}},$
$\displaystyle\text{where
}\alpha({\operatorname*{\mathbf{s}}}_{i}^{\prime}):=\left|\left(\begin{array}[]{cc}d_{+}({\operatorname*{\mathbf{s}}}_{i}^{\prime})\Lambda_{+}({\operatorname*{\mathbf{s}}}_{i}^{\prime})&0\\\
0&-d_{-}({\operatorname*{\mathbf{s}}}_{i}^{\prime})\Lambda_{-}({\operatorname*{\mathbf{s}}}_{i}^{\prime})\end{array}\right)\right|^{-1/\left(d_{+}({\operatorname*{\mathbf{s}}}_{i}^{\prime})+d_{-}({\operatorname*{\mathbf{s}}}_{i}^{\prime})\right)}.$

14:end for

15:Estimate
$\widehat{V}(\pi)=(1-\gamma)\tfrac{1}{m}\sum_{j=1}^{m}Q_{\theta}(\operatorname*{\mathbf{s}}_{0,j},\tilde{\pi}(\operatorname*{\mathbf{s}}_{0,j}))$,
where $\displaystyle\\{{\operatorname*{\mathbf{s}}}_{0,j}\\}_{j=1}^{m}\text{
is the set of initial states in $\mathcal{D}$}.$

##  Appendix C Experiment details

###  C.1 Pendulum with dummy action dimensions

#### Environment

The Pendulum-v0 environment in OpenAI Gym (Brockman et al., 2016) is modified
to have d-dimensional actions. Among the d-dimensional actions, only the first
dimension, which is the original action dimension in the Pendulum-v0
environment, is used for computing the next state transitions and rewards. The
other (d - 1) action dimensions are unrelated to next state transitions and
rewards. All of the dimensions have an action range equal to that of the
original action space, which is $[-a_{\text{max}},a_{\text{max}}]$, where
$a_{\text{max}}=2$. The episode length is 200 steps. The discount factor of
0.95 is used.

#### Target policy

We train a TD3 policy $\tilde{\pi}_{1}$ to be near-optimal on the original
Pendulum-v0 environment which has only one action dimension and use it to make
a target policy. The target policy $\tilde{\pi}$ is made with
$\tilde{\pi}_{1}(\operatorname*{\mathbf{s}})$:

$\tilde{\pi}(\operatorname*{\mathbf{s}})=\left[\begin{array}[]{c}\tilde{\pi}_{1}(\operatorname*{\mathbf{s}})\\\
0\\\ \vdots\\\ 0\end{array}\right].$

The policy value of $\pi_{0}$ estimated from the rollout of 1500 episodes is
$-3.791$. Since the dummy action dimensions do not have an effect on next
state transitions and rewards, the policy values of $\tilde{\pi}_{1}$ and
$\tilde{\pi}$ are the same.

#### Behavior policy

For the behavior policy, a TD3 policy $\tilde{\mu}_{1}$ is deliberately
trained to be inferior to $\tilde{\pi}_{1}$ and is used to make a stochastic
behavior policy. The behavior policy $\mu$ made with $\tilde{\mu}_{1}$ is as
follows:

$\mu(\operatorname*{\mathbf{a}}|\operatorname*{\mathbf{s}})=\left\\{0.8N(a_{1}|\tilde{\mu}_{1}(\operatorname*{\mathbf{s}}),(0.5a_{\text{max}})^{2})+0.2U(a_{1}|-a_{\text{max}},a_{\text{max}})\right\\}\prod_{i=2}^{d}U(a_{i}|-a_{\text{max}},a_{\text{max}}),$
(75)

where a uniform density with a range of $[-a_{\text{max}},a_{\text{max}}]$ for
$i^{\text{th}}$ action dimension is denoted as
$U(a_{i}|-a_{\text{max}},a_{\text{max}})$. For the first action dimension, the
mixture of 80% Gaussian density and 20% uniform density is used. For the other
dimensions, actions are sampled from the uniform densities. The behavior
policy is similar to the one used in the work of Fujimoto et al. (2021).

The policy values of $\mu$ and $\tilde{\mu}_{1}$ are estimated from the
rollout of 1500 episodes and reported in Table 3. Since the dummy action
dimensions are unrelated to next state transitions and rewards, the behavior
policy value does not change as the number of dummy action dimensions changes.

Table 2: Policy values | Modified Pendulum-v0
---|---
$R(\tilde{\mu}_{1})$ | -453.392
$R(\pi)$ | -142.553
$V(\tilde{\mu}_{1})$ | -4.413
$V(\mu)$ | -5.080
$V(\pi)$ | -3.971

#### Dataset

Half a million transitions are sampled with the behavior policy $\mu$ for all
experiments using the modified pendulum environment with dummy action
dimensions.

#### Target policy value evaluation with OPE methods

For KMIFQE and FQE, target policy values are estimated as
$\widehat{V}(\pi)=(1-\gamma)\frac{1}{m}\sum_{i=1}^{m}Q_{\theta}(\operatorname*{\mathbf{s}}_{0,i},\tilde{\pi}(\operatorname*{\mathbf{s}}_{0,i}))$,
where $m$ is the number of episodes in the dataset. For SR-DICE, the target
policy values are estimated with 10k transitions randomly sampled from the
data.

#### Network architecture

Our algorithm and FQE use the same architecture of a network of 2 hidden
layers with 256 hidden units. For SR-DICE, we use the network architecture
used in the work of Fujimoto et al. (2021). The encoder network of SR-DICE
uses one hidden layer with 256 hidden units which outputs a feature vector of
256. The decoder network of SR-DICE uses one hidden layer with 256 hidden
units for both next state and action decoders and uses a linear function of
the feature vector for the reward decoder. The successor representation
network of SR-DICE is composed of 2 hidden layers with 256 hidden units, and
SR-DICE also uses 256 hidden units for the density ratio weights. We use the
SR-DICE and FQE implementations in https://github.com/sfujim/SR-DICE.

#### Hyperparameters

Following the hyperparameter settings used in the work (Fujimoto et al.,
2021), all networks are trained with Adam optimizer (Kingma & Ba, 2014) with
the learning rate of $3e-4$. For mini-batch sizes, the encoder-decoder
network, and successor representation network of SR-DICE, as well as FQE, use
a mini-batch size of 256. For the learning of density ratio in SR-DICE and our
algorithm, we use a mini-batch size of 1024. FQE and SR-DICE use update rate
$\tau=0.005$ for the soft update of the target critic network and target
successor representation network respectively. For our proposed method, target
critic network is hard updated every 1000 iterations. We clip the behavior
policy density value at the target action by 1e-5 when the density value is
below the clipping value for numerical stability when evaluating $v$ defined
in Eq. (9). The IS ratios are clipped to be in the range of $[0.001,2]$ to
lower the variance of its estimations (Kallus & Zhou, 2018; Munos et al.,
2016; Han & Sung, 2019). The clipping range is selected by grid search on
Hopper-v2 domain from the cartesian product of minimum IS ratio clip values
{1e-5, 1e-3, 1e-1} and maximum IS ratio clip values {1, 2, 10}.

#### Computational resources used and KMIFQE train time

One i7 CPU with one NVIDIA Titan Xp GPU runs KMIFQE for two million train
steps in 5 hours.

###  C.2 Continuous control tasks with a known behavior policy

#### Environment

MuJoCo environments (Todorov et al., 2012) of Hopper-v2 (d=3), HalfCheetah-v2
(d=6), and Walker2D-v2 (d=6), Ant-v2 (d=8), and Humanoid-v2 (d=17) are used.
The maximum episode length of the environments is 1000 steps. HalfCheetah-v2
does not have a termination condition that terminates an episode before it
reaches 1000 steps. But the other two environments may terminate before
reaching the maximum episode length when the agent falls. The discount factor
of 0.99 is used. The action range for all environments and for all action
dimensions is in $[-a_{\text{max}},a_{\text{max}}]$, where $a_{\text{max}}=1$
except Humanoid-v2 which is $a_{\text{max}}=0.4$.

#### Target policy

We train a TD3 policy $\pi$ to be near-optimal and use it as a target policy.
The target policy values estimated with the rollout of 1000 episodes are
presented in Table 3.

#### Behavior policy

For the behavior policy of each environment of HalfCheetah-v2, Hopper-v2, and
Walker2D-v2, a TD3 policies $\tilde{\mu}$ are deliberately trained to be
inferior to a target policy, to achieve about 70%$\sim$80% of the undiscounted
return $(R)$ of $\pi$. Then, $\tilde{\mu}$ is used to make the Gaussian
behavior policy
$\mu(\operatorname*{\mathbf{a}}|\operatorname*{\mathbf{s}})=N(\operatorname*{\mathbf{a}}|\tilde{\mu}(\operatorname*{\mathbf{s}}),(0.3a_{\text{max}})^{2}I)$.
The policy values of the behavior policy $\mu$ and $\tilde{\mu}$ for each
environment are estimated with the rollout of 1000 episodes, and the policy
values are reported in Table 3.

#### Target policy value evaluation with OPE methods

For KMIFQE and FQE, target policy values are estimated as
$\widehat{V}(\pi)=(1-\gamma)\frac{1}{m}\sum_{i=1}^{m}Q_{\theta}(\operatorname*{\mathbf{s}}_{0,i},\tilde{\pi}(\operatorname*{\mathbf{s}}_{0,i}))$,
where $m$ is the number of episodes in the dataset. For SR-DICE, the target
policy values are estimated with 10k transitions randomly sampled from the
data.

#### Dataset

One million transitions are sampled with the behavior policy $\mu$ for all
experiments.

Table 3: Policy values | HalfCheetah-v2 | Hopper-v2 | Walker2D-v2 | Ant-v2 | Humnaoid-v2
---|---|---|---|---|---
$R(\tilde{\mu})$ | 7591.245 | 2054.226 | 3032.198 | 3736.888 | 3912.369
$R(\pi)$ | 10495.003 | 2600.161 | 4172.839 | 5034.756 | 5303.486
$V(\tilde{\mu})$ | 5.716 | 2.553 | 2.595 | 3.439 | 4.848
$V(\mu)$ | 4.211 | 2.506 | 2.605 | 1.886 | 4.396
$V(\pi)$ | 7.267 | 2.571 | 2.693 | 4.396 | 5.211

#### Target policy value evaluation with OPE methods

For KMIFQE and FQE, target policy values are estimated as
$\widehat{V}(\pi)=(1-\gamma)\frac{1}{m}\sum_{i=1}^{m}Q(\operatorname*{\mathbf{s}}_{0,i},\tilde{\pi}(\operatorname*{\mathbf{s}}_{0,i}))$,
where $m$ is the number of episodes in the dataset. For SR-DICE, the target
policy values are estimated with 10k transitions randomly sampled from the
data.

#### Network architecture

The network architectures used for the MuJoCo experiment are the same as that
of the architectures used in the experiments on pendulum environment with
dummy action dimensions.

#### Hyperparameters

The hyperparameters used for the MuJoCo experiments are the same as that of
the experiments on the pendulum environment with dummy action dimensions
except the mini-batch size used for the learning of density ratio in SR-DICE
and our algorithm is 2048 as in the work of Fujimoto et al. (2021). For our
proposed method, the IS ratios are dimension-wise clipped in the range of
$[0.001,2]$ to lower the variance of its estimations (Han & Sung, 2019).

#### Computational resources used and KMIFQE train time

One i7 CPU with one NVIDIA Titan Xp GPU runs KMIFQE for one million train
steps in 5 hours.

###  C.3 Continuous control tasks with unknown multiple behavior policies

#### Dataset

Among the D4RL dataset (Fu et al., 2020) we used halfcheetah-medium-expert-v2,
hopper-medium-expert-v2, walker2d-medium-expert-v2, halfcheetah-medium-
replay-v2, hopper-medium-replay-v2, walker2d-medium-replay-v2. The discount
factor of 0.99 is used. The action range for all environments and for all
action dimensions is in $[-a_{\text{max}},a_{\text{max}}]$, where
$a_{\text{max}}=1$.

#### Target policy

We use the mean values of the stochastic expert policies provided by D4RL
dataset (Fu et al., 2020) as deterministic target policies.

#### Target policy value evaluation with OPE methods

For KMIFQE and FQE, target policy values are estimated as
$\widehat{V}(\pi)=(1-\gamma)\frac{1}{m}\sum_{i=1}^{m}Q_{\theta}(\operatorname*{\mathbf{s}}_{0,i},\tilde{\pi}(\operatorname*{\mathbf{s}}_{0,i}))$,
where $m$ is the number of episodes in the dataset. For SR-DICE, the target
policy values are estimated with 10k transitions randomly sampled from the
data.

#### Maximum likelihood estimation of behavior policies for KMIFQE

Behavior policies are maximum likelihood estimated tanh-squashed mixture-of-
Gaussian (MoG) models. The MoGs are squashed by tanh to restrict the support
of the behavior policy to the action range of
$[-a_{\text{max}},a_{\text{max}}]$ for each action dimension. We fit tanh-
squashed MoGs with mixture number of 10, 20, 30, 40 and select a mixture
number by cross-validation for each dataset. The validation set is the 10% of
the data, and rest of the data is used for training. The validation log-
likelihood for each mixture number is reported in Table 4 with one standard
error.

Table 4: Validation log-likelihood of estimated behavior policies. | Number of Mixtures
---|---
Dataset | 10 | 20 | 30 | 40
hopper-m-e | 2.089 $\pm$ 0.002 | 2.114 $\pm$ 0.002 | 2.123 $\pm$ 0.003 | 2.125 $\pm$ 0.002
halfcheetah-m-e | 6.581 $\pm$ 0.003 | 6.591 $\pm$ 0.003 | 6.583 $\pm$ 0.003 | 6.578 $\pm$ 0.003
walker2d-m-e | 5.610 $\pm$ 0.002 | 5.626 $\pm$ 0.005 | 5.630 $\pm$ 0.005 | 5.629 $\pm$ 0.005
hopper-m-r | 0.767 $\pm$ 0.006 | 0.787 $\pm$ 0.007 | 0.797 $\pm$ 0.006 | 0.800 $\pm$ 0.005
halfcheetah-m-r | 5.315 $\pm$ 0.012 | 5.303 $\pm$ 0.012 | 5.281 $\pm$ 0.016 | 5.271 $\pm$ 0.014
walker2d-m-r | 2.508 $\pm$ 0.007 | 2.492 $\pm$ 0.013 | 2.480 $\pm$ 0.016 | 2.472 $\pm$ 0.011

#### Network architecture

The network architectures used for the D4RL experiment are the same as that of
the architectures used in the experiments on pendulum environment with dummy
action dimensions.

#### Hyperparameters

The hyperparameters used for the MuJoCo experiments are the same as those of
the experiments on the MuJoCo domain (Todorov et al., 2012) with a known
behavior policy except that since the dimension-wise clipping is not possible,
we clip the overall IS ratios. Furthermore, we clip the behavior policy
density value at the target action by 1e-3 when the density value is below the
clipping value for numerical stability when evaluating $v$.

#### Computational resources used and KMIFQE train time

One i7 CPU with one NVIDIA Titan Xp GPU runs KMIFQE for one million train
steps in 5 hours.