# Beyond Softmax: A New Perspective on Gradient Bandits

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

## Key facts

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

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

- [Introduction to Multi-Armed Bandits](https://mlsanity.com/paper/1904.07272/) (2019)
- [An efficient algorithm for learning with semi-bandit feedback](https://mlsanity.com/paper/1305.2732/) (2013)
- [Nested bandits](https://mlsanity.com/paper/2206.09348/) (2022)
- [Optimism in the Face of Ambiguity Principle for Multi-Armed Bandits](https://mlsanity.com/paper/2409.20440/) (2024)
- [Revisiting Follow-the-Perturbed-Leader with Unbounded Perturbations in Bandit Problems](https://mlsanity.com/paper/2508.18604/) (2025)
- [Discrete choice prox-functions on the simplex](https://mlsanity.com/paper/1909.05591/) (2019)
- [Dynamic pricing under nested logit demand](https://mlsanity.com/paper/2101.04486/) (2021)

## Abstract (arXiv)

We establish a link between a class of discrete choice models and the theory of online learning and multi-armed bandits. Our contributions are: (i) sublinear regret bounds for a broad algorithmic family, encompassing Exp3 as a special case; (ii) a new class of adversarial bandit algorithms derived from generalized nested logit models citepwen:2001; and (iii) textcolorblackwe introduce a novel class of generalized gradient bandit algorithms that extends beyond the widely used softmax formulation. By relaxing the restrictive independence assumptions inherent in softmax, our framework accommodates correlated learning dynamics across actions, thereby broadening the applicability of gradient bandit methods. Overall, the proposed algorithms combine flexible model specification with computational efficiency via closed-form sampling probabilities. Numerical experiments in stochastic bandit settings demonstrate their practical effectiveness.