# A Best-of-Both-Worlds Proof for Tsallis-INF without Fenchel Conjugates

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

## Key facts

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

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

- [Online Learning: A Modern Introduction Using Convex Optimization](https://mlsanity.com/paper/1912.13213/) (2019)
- [Tsallis-INF: An Optimal Algorithm for Stochastic and Adversarial Bandits](https://mlsanity.com/paper/1807.07623/) (2018)

## Abstract (arXiv)

In this short note, we present a simple derivation of the best-of-both-world guarantee for the Tsallis-INF multi-armed bandit algorithm from J. Zimmert and Y. Seldin. Tsallis-INF: An optimal algorithm for stochastic and adversarial bandits. Journal of Machine Learning Research, 22(28):1-49, 2021. URL https://jmlr.csail.mit.edu/papers/volume22/19-753/19-753.pdf. In particular, the proof uses modern tools from online convex optimization and avoid the use of conjugate functions. Also, we do not optimize the constants in the bounds in favor of a slimmer proof.