Clustered KL-barycenter design for policy evaluation
This addresses sample efficiency in policy evaluation for reinforcement learning, offering a novel method with incremental improvements over existing KL-based approaches.
The paper tackles the problem of designing sample-efficient behavior policies for evaluating multiple target policies in stochastic bandit models, proposing a clustered KL-barycenter approach that reduces sample complexity with proven theoretical bounds.
In the context of stochastic bandit models, this article examines how to design sample-efficient behavior policies for the importance sampling evaluation of multiple target policies. From importance sampling theory, it is well established that sample efficiency is highly sensitive to the KL divergence between the target and importance sampling distributions. We first analyze a single behavior policy defined as the KL-barycenter of the target policies. Then, we refine this approach by clustering the target policies into groups with small KL divergences and assigning each cluster its own KL-barycenter as a behavior policy. This clustered KL-based policy evaluation (CKL-PE) algorithm provides a novel perspective on optimal policy selection. We prove upper bounds on the sample complexity of our method and demonstrate its effectiveness with numerical validation.