In this paper, we study safe data collection for the purpose of policy
evaluation in tabular Markov decision processes (MDPs). In policy evaluation,
we are given a \textit{target} policy and asked to estimate the expected
cumulative reward it will obtain. Policy evaluation requires data and we are
interested in the question of what \textit{behavior} policy should collect the
data for the most accurate evaluation of the target policy. While prior work
has considered behavior policy selection, in this paper, we additionally
consider a safety constraint on the behavior policy. Namely, we assume there
exists a known default policy that incurs a particular expected cost when run
and we enforce that the cumulative cost of all behavior policies ran is better
than a constant factor of the cost that would be incurred had we always run the
default policy. We first show that there exists a class of intractable MDPs
where no safe oracle algorithm with knowledge about problem parameters can
efficiently collect data and satisfy the safety constraints. We then define the
tractability condition for an MDP such that a safe oracle algorithm can
efficiently collect data and using that we prove the first lower bound for this
setting. We then introduce an algorithm SaVeR for this problem that
approximates the safe oracle algorithm and bound the finite-sample mean squared
error of the algorithm while ensuring it satisfies the safety constraint.
Finally, we show in simulations that SaVeR produces low MSE policy evaluation
while satisfying the safety constraint.

本文研究了在表格化马尔可夫决策过程中针对策略评估目的的安全数据收集。我们考虑了行为策略的安全性约束，并提出了一种算法来近似安全的预言算法，并保证其满足安全性约束。通过模拟实验证明该算法在满足约束条件的情况下能够产生低均方误差的策略评估结果。