# Clustered KL-barycenter design for policy evaluation

arXiv: https://arxiv.org/abs/2503.02735 · HTML: https://mlsanity.com/paper/2503.02735/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 14 of its 32 references that are in the map.
- First posted on arXiv 4 Mar 2025.

## Builds on (most cited first, 14 of 14)

- [Is Pessimism Provably Efficient for Offline RL?](https://mlsanity.com/paper/2012.15085/) (2020)
- [Bridging Offline Reinforcement Learning and Imitation Learning: A Tale of Pessimism](https://mlsanity.com/paper/2103.12021/) (2021)
- [Optimal and Adaptive Off-policy Evaluation in Contextual Bandits](https://mlsanity.com/paper/1612.01205/) (2016)
- [Confident Off-Policy Evaluation and Selection through Self-Normalized Importance Weighting](https://mlsanity.com/paper/2006.10460/) (2020)
- [Policy learning "without" overlap: Pessimism and generalized empirical Bernstein's inequality](https://mlsanity.com/paper/2212.09900/) (2022)
- [Bayesian Counterfactual Risk Minimization](https://mlsanity.com/paper/1806.11500/) (2018)
- [Data-Efficient Policy Evaluation Through Behavior Policy Search](https://mlsanity.com/paper/1706.03469/) (2017)
- [Effective Evaluation using Logged Bandit Feedback from Multiple Loggers](https://mlsanity.com/paper/1703.06180/) (2017)
- [Logarithmic Smoothing for Pessimistic Off-Policy Evaluation, Selection and Learning](https://mlsanity.com/paper/2405.14335/) (2024)
- [Oracle-Efficient Pessimism: Offline Policy Optimization in Contextual Bandits](https://mlsanity.com/paper/2306.07923/) (2023)
- [Importance-Weighted Offline Learning Done Right](https://mlsanity.com/paper/2309.15771/) (2023)
- [Policy Gradient with Active Importance Sampling](https://mlsanity.com/paper/2405.05630/) (2024)
- [Efficient estimation of multiple expectations with the same sample by adaptive importance sampling and control variates](https://mlsanity.com/paper/2212.00568/) (2022)
- [Adaptive Exploration for Data-Efficient General Value Function Evaluations](https://mlsanity.com/paper/2405.07838/) (2024)

## Abstract (arXiv)

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.