# Efficient and Interpretable Bandit Algorithms

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 14 of its 36 references that are in the map.
- First posted on arXiv 23 Oct 2023.

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

- [Best-Arm Identification in Linear Bandits](https://mlsanity.com/paper/1409.6110/) (2014)
- [Sequential Experimental Design for Transductive Linear Bandits](https://mlsanity.com/paper/1906.08399/) (2019)
- [Explore First, Exploit Next: The True Shape of Regret in Bandit Problems](https://mlsanity.com/paper/1602.07182/) (2016)
- [Efficient First-Order Contextual Bandits: Prediction, Allocation, and Triangular Discrimination](https://mlsanity.com/paper/2107.02237/) (2021)
- [On Explore-Then-Commit Strategies](https://mlsanity.com/paper/1605.08988/) (2016)
- [An Empirical Process Approach to the Union Bound: Practical Algorithms for Combinatorial and Linear Bandits](https://mlsanity.com/paper/2006.11685/) (2020)
- [Carousel Personalization in Music Streaming Apps with Contextual Bandits](https://mlsanity.com/paper/2009.06546/) (2020)
- [Double Explore-then-Commit: Asymptotic Optimality and Beyond](https://mlsanity.com/paper/2002.09174/) (2020)
- [Nearly Optimal Algorithms for Level Set Estimation](https://mlsanity.com/paper/2111.01768/) (2021)
- [Chernoff Sampling for Active Testing and Extension to Active Regression](https://mlsanity.com/paper/2012.08073/) (2020)
- [Inverse Contextual Bandits: Learning How Behavior Evolves over Time](https://mlsanity.com/paper/2107.06317/) (2021)
- [Experimental Design for Regret Minimization in Linear Bandits](https://mlsanity.com/paper/2011.00576/) (2020)
- [Safe Data Collection for Offline and Online Policy Learning](https://mlsanity.com/paper/2111.04835/) (2021)
- [Deep neural network marketplace recommenders in online experiments](https://mlsanity.com/paper/1809.02130/) (2018)

## Abstract (arXiv)

Motivated by the importance of explainability in modern machine learning, we design bandit algorithms that are efficient and interpretable. A bandit algorithm is interpretable if it explores with the objective of reducing uncertainty in the unknown model parameter. To quantify the interpretability, we introduce a novel metric of model error, which compares the rate reduction of the mean reward estimates to their actual means among all the plausible actions. We propose CODE, a bandit algorithm based on a Constrained Optimal DEsign, that is interpretable and maximally reduces the uncertainty. The key idea in CODE is to explore among all plausible actions, determined by a statistical constraint, to achieve interpretability. We implement CODE efficiently in both multi-armed and linear bandits and derive near-optimal regret bounds by leveraging the optimality criteria of the approximate optimal design. CODE can be also viewed as removing phases in conventional phased elimination, which makes it more practical and general. We demonstrate the advantage of CODE by numerical experiments on both synthetic and real-world problems. CODE outperforms other state-of-the-art interpretable designs while matching the performance of popular but uninterpretable designs, such as upper confidence bound algorithms.