# Simultaneously Learning Stochastic and Adversarial Bandits under the Position-Based Model

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 20 of its 53 references that are in the map.
- First posted on arXiv 12 Jul 2022.

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

- [More Adaptive Algorithms for Adversarial Bandits](https://mlsanity.com/paper/1801.03265/) (2018)
- [Cascading Bandits: Learning to Rank in the Cascade Model](https://mlsanity.com/paper/1502.02763/) (2015)
- [What Doubling Tricks Can and Can't Do for Multi-Armed Bandits](https://mlsanity.com/paper/1803.06971/) (2018)
- [Beating Stochastic and Adversarial Semi-bandits Optimally and Simultaneously](https://mlsanity.com/paper/1901.08779/) (2019)
- [Simultaneously Learning Stochastic and Adversarial Episodic MDPs with Known Transition](https://mlsanity.com/paper/2006.05606/) (2020)
- [Achieving Near Instance-Optimality and Minimax-Optimality in Stochastic and Adversarial Linear Bandits Simultaneously](https://mlsanity.com/paper/2102.05858/) (2021)
- [An algorithm with nearly optimal pseudo-regret for both stochastic and adversarial bandits](https://mlsanity.com/paper/1605.08722/) (2016)
- [Cascading Bandits for Large-Scale Recommendation Problems](https://mlsanity.com/paper/1603.05359/) (2016)
- [An Improved Parametrization and Analysis of the EXP3++ Algorithm for Stochastic and Adversarial Bandits](https://mlsanity.com/paper/1702.06103/) (2017)
- [Minimal Exploration in Structured Stochastic Bandits](https://mlsanity.com/paper/1711.00400/) (2017)
- [On the optimality of the Hedge algorithm in the stochastic regime](https://mlsanity.com/paper/1809.01382/) (2018)
- [TopRank: A practical algorithm for online stochastic ranking](https://mlsanity.com/paper/1806.02248/) (2018)
- [Multiple-Play Bandits in the Position-Based Model](https://mlsanity.com/paper/1606.02448/) (2016)
- [First-order regret bounds for combinatorial semi-bandits](https://mlsanity.com/paper/1502.06354/) (2015)
- [Online Learning to Rank in Stochastic Click Models](https://mlsanity.com/paper/1703.02527/) (2017)
- [Stochastic Rank-1 Bandits](https://mlsanity.com/paper/1608.03023/) (2016)
- [An efficient algorithm for learning with semi-bandit feedback](https://mlsanity.com/paper/1305.2732/) (2013)
- [Online Learning to Rank with Features](https://mlsanity.com/paper/1810.02567/) (2018)
- [Combining Adversarial Guarantees and Stochastic Fast Rates in Online Learning](https://mlsanity.com/paper/1605.06439/) (2016)
- [Bandit Online Optimization Over the Permutahedron](https://mlsanity.com/paper/1312.1530/) (2013)

## Built on by (most cited first, 2 of 2)

- [A Blackbox Approach to Best of Both Worlds in Bandits and Beyond](https://mlsanity.com/paper/2302.09739/) (2023)
- [Best-of-three-worlds Analysis for Linear Bandits with Follow-the-regularized-leader Algorithm](https://mlsanity.com/paper/2303.06825/) (2023)

## Abstract (arXiv)

Online learning to rank (OLTR) interactively learns to choose lists of items from a large collection based on certain click models that describe users' click behaviors. Most recent works for this problem focus on the stochastic environment where the item attractiveness is assumed to be invariant during the learning process. In many real-world scenarios, however, the environment could be dynamic or even arbitrarily changing. This work studies the OLTR problem in both stochastic and adversarial environments under the position-based model (PBM). We propose a method based on the follow-the-regularized-leader (FTRL) framework with Tsallis entropy and develop a new self-bounding constraint especially designed for PBM. We prove the proposed algorithm simultaneously achieves O(logT) regret in the stochastic environment and O(m√nT) regret in the adversarial environment, where T is the number of rounds, n is the number of items and m is the number of positions. We also provide a lower bound of order Omega(m√nT) for adversarial PBM, which matches our upper bound and improves over the state-of-the-art lower bound. The experiments show that our algorithm could simultaneously learn in both stochastic and adversarial environments and is competitive compared to existing methods that are designed for a single environment.