TL;DR
This paper revisits the "policy choice" problem, a variant of best arm identification in bandit literature, and finds critical flaws in the theoretical guarantees provided by Kasy and Sautmann (2021) for their "exploration sampling" algorithm. The authors not only correct these flaws but also propose a new objective function, "posterior weighted policy regret," under which exploration sampling is shown to be asymptotically optimal.
What Problem Does This Paper Address?
The "policy choice" problem, as introduced by Kasy and Sautmann (2021), aims to find the best treatment (or "arm") among several options in an adaptive experimental design setting. This involves multiple waves of experiments where treatments are assigned, outcomes are observed, and assignments are updated based on past data. The ultimate goal is to identify the treatment with the highest expected outcome. Kasy and Sautmann (2021) proposed an algorithm called "exploration sampling" and claimed its asymptotic optimality in terms of "policy regret" (a measure of how much social welfare is lost due to suboptimal choices). This paper addresses the critical issue that the theoretical underpinnings of this claim are flawed, specifically in the proofs and statements of Theorem 1 in the original work. The authors aim to correct these inaccuracies and provide a more robust theoretical foundation for exploration sampling.
Methods
The paper's core methodology involves a rigorous re-examination and correction of the theoretical results presented by Kasy and Sautmann (2021). This includes:
- Identifying and correcting technical issues in proofs: The authors meticulously analyze the proofs of Theorem 1 (1) and (2) from the original paper, pinpointing where they deviate from established theoretical principles (e.g., misapplication of results from Russo (2016) to Beta-Bernoulli models).
- Providing counterexamples: For Theorem 1 (3), which claims asymptotic optimality of exploration sampling under expected policy regret, the authors construct a counterexample that demonstrates its falsity by contradicting existing theoretical lower bounds.
- Proposing a new objective function: To salvage the asymptotic optimality of exploration sampling, the authors introduce "posterior weighted policy regret." This new metric synthesizes aspects of frequentist policy regret and Bayesian posterior beliefs, aiming to capture both the true regret and the uncertainty in posterior estimates.
- Developing corrected theoretical statements and proofs: The paper presents a revised Theorem 4.1, which includes corrected statements and rigorous proofs for the asymptotic properties of exploration sampling, both under the original expected policy regret (with corrections) and the new posterior weighted policy regret.
- Extending to general priors: The corrected results are generalized to Beta(αd, βd) priors, moving beyond the uniform prior assumption.
Datasets
Not discussed in the paper. The paper focuses on theoretical analysis and does not involve empirical evaluation on specific datasets.
Key Insights and Ideas
- The subtle but critical difference in Bayesian bandit proofs: The paper highlights how assumptions in foundational works like Russo (2016) are not universally applicable, particularly to Beta-Bernoulli models with general priors. This underscores the need for careful, model-specific proofs.
- The limitations of "expected policy regret": The authors demonstrate that minimizing expected policy regret alone is insufficient to guarantee the desired asymptotic performance for exploration sampling, as it can be outpaced by hard problem instances.
- The power of "posterior weighted policy regret": By incorporating posterior probabilities into the objective function, the authors create a metric that better aligns with the adaptive nature of exploration sampling and allows for a stronger theoretical guarantee of asymptotic optimality. This suggests that a purely frequentist regret measure might be too simplistic for certain adaptive algorithms.
- The importance of almost sure convergence: The corrected theorems establish almost sure convergence for key quantities, which is a stronger form of convergence than probability convergence, providing more robust theoretical guarantees.
Key Results
- Theorem 1 (1) and (2) of Kasy and Sautmann (2021) are corrected: The paper provides corrected statements and rigorous proofs for these parts, addressing technical issues in the original proofs.
- Theorem 1 (3) of Kasy and Sautmann (2021) is shown to be false: A counterexample is provided, demonstrating that exploration sampling does not achieve asymptotic optimality under the expected policy regret.
- Asymptotic optimality under posterior weighted policy regret: The paper proves that exploration sampling is asymptotically optimal with respect to the newly proposed "posterior weighted policy regret" objective.
- Generalization to Beta(αd, βd) priors: The theoretical results are extended to a broader class of priors, increasing the applicability of the findings.
- Corrected Lemmata: Several crucial lemmata from the original work are corrected and re-proven to support the new theoretical results.
Limitations and Future Work
- Focus on asymptotic analysis: The current work provides asymptotic guarantees (as the number of experimental waves T goes to infinity). The behavior of the algorithm for finite T, while improved by the corrected theory, is not the primary focus.
- Computational tractability: While the theoretical properties are established, the computational complexity of the proposed posterior weighted policy regret and its implications for practical implementation are not deeply explored.
- Specific prior distributions: While generalized to Beta(αd, βd) priors, the analysis might not cover all possible prior distributions.
Future work could involve exploring finite-sample bounds, investigating the computational aspects of the new objective function, and potentially extending the analysis to more complex bandit settings.
Summary updated