Policy Choice and Best Arm Identification: Comments on "Adaptive Treatment Assignment in Experiments for Policy Choice"

Kaito Ariu, Masahiro Kato, Junpei Komiyama, Kenichiro McAlinn

Abstract

We consider the "policy choice" problem—otherwise known as best arm identification in the bandit literature—proposed by Kasy and Sautmann (2021) for adaptive experimental design. Theorem 1 of Kasy and Sautmann (2021) provides three asymptotic results that give theoretical guarantees for exploration sampling developed for this setting. We first show that the proof of Theorem 1 (1) has technical issues, and the proof and statement of Theorem 1 (2) are incorrect. We then show, through a counterexample, that Theorem 1 (3) is false. For the former two, we correct the statements and provide rigorous proofs. For Theorem 1 (3), we propose an alternative objective function, which we call posterior weighted policy regret, and derive the asymptotic optimality of exploration sampling.

Introduction

In fields such as development economics and clinical trials, researchers increasingly rely on adaptive experimental designs to identify the most effective treatment from a set of options. This task, formalized as the Policy Choice problem (or Best Arm Identification in bandit literature), aims to allocate samples during an experiment so that, upon its conclusion, the researcher can recommend the single best policy with high confidence.

An influential study by Kasy and Sautmann (2021) proposed an algorithm called exploration sampling, claiming it was asymptotically optimal for minimizing "policy regret"—the expected loss resulting from selecting a sub-optimal treatment. However, a rigorous re-evaluation of the mathematical foundations of that study reveals significant theoretical errors. This paper identifies these flaws, provides necessary corrections, and introduces a more robust metric—posterior weighted policy regret—to establish the first rigorous asymptotic guarantees for the exploration sampling method.

Theoretical Corrections and Methodology

The authors employ advanced asymptotic theory to rebuild the foundation of exploration sampling, addressing three primary areas of concern in the original Theorem 1:

1. Convergence and Pathwise Consistency

The original proofs for the convergence of posterior probabilities relied on "convergence in probability." The authors demonstrate that this is insufficient for the law of large numbers to hold across sample paths in adaptive settings. They shift the requirement to "almost sure convergence," ensuring that the asymptotic rates remain meaningful across nearly all possible experimental outcomes.

2. The KL-Divergence Asymmetry

A critical technical error in the original work involved the Kullback–Leibler (KL) divergence, $d_{KL}(p, q)$. In bandit theory, the order of arguments is non-commutative and carries distinct physical meanings. The original paper reversed these arguments, characterizing the likelihood of incorrectly recommending a treatment rather than the likelihood of the observed data under the hypothesis that a treatment is sub-optimal. Correcting this orientation is essential for establishing true posterior consistency.

3. Disproving the Decay Rate

Using a counterexample based on lower-bound results from Carpentier and Locatelli (2016), the authors prove that the decay rate of policy regret claimed in the original paper is mathematically impossible for any algorithm to achieve. This necessitates a shift in how we measure the success of adaptive designs.

Innovation: Posterior Weighted Policy Regret

Recognizing that standard policy regret is mathematically "stubborn" and difficult to optimize directly, the authors propose a new objective function: Posterior Weighted Policy Regret ($W_\theta(T)$). This metric weights the regret associated with each arm by its posterior probability of being the optimal choice. By synthesizing frequentist and Bayesian objectives, $W_\theta(T)$ provides a tractable path to proving optimality while remaining relevant to the researcher's goal of minimizing error.

Key Results

The paper culminates in several corrected theoretical guarantees:

  • Theorem 4.1 (The Correction): The authors prove that under exploration sampling, the share of observations assigned to the best arm converges almost surely to $1/2$, with the remaining $1/2$ distributed among the sub-optimal arms.
  • Asymptotic Optimality: Exploration sampling is demonstrated to be asymptotically optimal specifically for the newly proposed posterior weighted policy regret.
  • Linear Decay: The authors show that the logarithm of the new regret metric decays linearly with the total number of samples ($NT$), providing researchers with a clear, theoretically sound guarantee of the algorithm's efficiency.

Discussion and Future Directions

While this work provides a rigorous foundation for exploration sampling in Bernoulli (binary outcome) models, several avenues for future research remain. The current proofs are tailored to binary rewards, which are common in success/failure trials; extending these results to Gaussian distributions or the general exponential family would broaden the impact for experiments involving continuous rewards like income or test scores.

Furthermore, as these results are asymptotic ($T \to \infty$), further investigation is needed to quantify the "burn-in" period required in finite-sample settings. In practice, experiments often have a limited number of waves, and understanding the transition from heuristic performance to theoretical optimality remains a vital challenge for adaptive design.

Summary updated

Abstract

We consider the "policy choice" problem -- otherwise known as best arm identification in the bandit literature -- proposed by Kasy and Sautmann (2021) for adaptive experimental design. Theorem 1 of Kasy and Sautmann (2021) provides three asymptotic results that give theoretical guarantees for exploration sampling developed for this setting. We first show that the proof of Theorem 1 (1) has technical issues, and the proof and statement of Theorem 1 (2) are incorrect. We then show, through a counterexample, that Theorem 1 (3) is false. For the former two, we correct the statements and provide rigorous proofs. For Theorem 1 (3), we propose an alternative objective function, which we call posterior weighted policy regret, and derive the asymptotic optimality of exploration sampling.
BibTeX
@misc{ariu2021policy,
  author = {Kaito Ariu and Masahiro Kato and Junpei Komiyama and Kenichiro McAlinn},
  title = {{Policy Choice and Best Arm Identification: Comments on "Adaptive Treatment Assignment in Experiments for Policy Choice"}},
  year = {2021},
  eprint = {2109.08229},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2109.08229},
}
Figure