# Incentive-compatible Bandits: Importance Weighting No More

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 7 of its 15 references that are in the map.
- First posted on arXiv 10 May 2024.

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

- [Tsallis-INF: An Optimal Algorithm for Stochastic and Adversarial Bandits](https://mlsanity.com/paper/1807.07623/) (2018)
- [More Adaptive Algorithms for Adversarial Bandits](https://mlsanity.com/paper/1801.03265/) (2018)
- [Corralling a Band of Bandit Algorithms](https://mlsanity.com/paper/1612.06246/) (2016)
- [Bias no more: high-probability data-dependent regret bounds for adversarial bandits and MDPs](https://mlsanity.com/paper/2006.08040/) (2020)
- [A Closer Look at Small-loss Bounds for Bandits with Graph Feedback](https://mlsanity.com/paper/2002.00315/) (2020)
- [Online mirror descent and dual averaging: keeping pace in the dynamic case](https://mlsanity.com/paper/2006.02585/) (2020)
- [No-Regret and Incentive-Compatible Online Learning](https://mlsanity.com/paper/2002.08837/) (2020)

## Abstract (arXiv)

We study the problem of incentive-compatible online learning with bandit feedback. In this class of problems, the experts are self-interested agents who might misrepresent their preferences with the goal of being selected most often. The goal is to devise algorithms which are simultaneously incentive-compatible, that is the experts are incentivised to report their true preferences, and have no regret with respect to the preferences of the best fixed expert in hindsight. citetfreeman2020no propose an algorithm in the full information setting with optimal O(√T log(K)) regret and O(T2/3(Klog(K))1/3) regret in the bandit setting. In this work we propose the first incentive-compatible algorithms that enjoy O(√KT) regret bounds. We further demonstrate how simple loss-biasing allows the algorithm proposed in Freeman et al. 2020 to enjoy tilde O(√KT) regret. As a byproduct of our approach we obtain the first bandit algorithm with nearly optimal regret bounds in the adversarial setting which works entirely on the observed loss sequence without the need for importance-weighted estimators. Finally, we provide an incentive-compatible algorithm that enjoys asymptotically optimal best-of-both-worlds regret guarantees, i.e., logarithmic regret in the stochastic regime as well as worst-case O(√KT) regret.