Multiple-policy Evaluation via Density Estimation
Yilei Chen Aldo Pacchiano Ioannis Ch. Paschalidis
In this work, we focus on the multiple-policy evaluation problem where we are
given a set of $K$ target policies and the goal is to evaluate their
performance (the expected total rewards) to an accuracy $\epsilon$ with
probability at least $1-\delta$. We propose an algorithm named
$\mathrm{CAESAR}$ to address this problem. Our approach is based on computing
an approximate optimal offline sampling distribution and using the data sampled
from it to perform the simultaneous estimation of the policy values.
$\mathrm{CAESAR}$ consists of two phases. In the first one we produce coarse
estimates of the vistation distributions of the target policies at a low order
sample complexity rate that scales with $\tilde{O}(\frac{1}{\epsilon})$. In the
second phase, we approximate the optimal offline sampling distribution and
compute the importance weighting ratios for all target policies by minimizing a
step-wise quadratic loss function inspired by the objective in DualDICE. Up to
low order and logarithm terms $\mathrm{CAESAR}$ achieves a sample complexity
$\tilde{O}\left(\frac{H^4}{\epsilon^2}\sum_{h=1}^H\max_{k\in[K]}\sum_{s,a}\frac{(d_h^{\pi^k}(s,a))^2}{\mu^*_h(s,a)}\right)$,
where $d^{\pi}$ is the visitation distribution of policy $\pi$ and $\mu^*$ is
the optimal sampling distribution.