# Bandit problems with fidelity rewards

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

## Key facts

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

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

- [Online Learning under Delayed Feedback](https://mlsanity.com/paper/1306.0686/) (2013)
- [What Doubling Tricks Can and Can't Do for Multi-Armed Bandits](https://mlsanity.com/paper/1803.06971/) (2018)
- [Kernel-based methods for bandit convex optimization](https://mlsanity.com/paper/1607.03084/) (2016)
- [Online Learning with Switching Costs and Other Adaptive Adversaries](https://mlsanity.com/paper/1302.4387/) (2013)
- [Rotting Bandits](https://mlsanity.com/paper/1702.07274/) (2017)
- [Bandits with Switching Costs: T^{2/3} Regret](https://mlsanity.com/paper/1310.2997/) (2013)
- [Recovering Bandits](https://mlsanity.com/paper/1910.14354/) (2019)
- [Blocking Bandits](https://mlsanity.com/paper/1907.11975/) (2019)
- [Stochastic Bandits with Delay-Dependent Payoffs](https://mlsanity.com/paper/1910.02757/) (2019)
- [Multi-armed Bandit Problem with Known Trend](https://mlsanity.com/paper/1508.07091/) (2015)
- [Discrepancy-Based Algorithms for Non-Stationary Rested Bandits](https://mlsanity.com/paper/1710.10657/) (2017)

## Abstract (arXiv)

The fidelity bandits problem is a variant of the K-armed bandit problem in which the reward of each arm is augmented by a fidelity reward that provides the player with an additional payoff depending on how 'loyal' the player has been to that arm in the past. We propose two models for fidelity. In the loyalty-points model the amount of extra reward depends on the number of times the arm has previously been played. In the subscription model the additional reward depends on the current number of consecutive draws of the arm. We consider both stochastic and adversarial problems. Since single-arm strategies are not always optimal in stochastic problems, the notion of regret in the adversarial setting needs careful adjustment. We introduce three possible notions of regret and investigate which can be bounded sublinearly. We study in detail the special cases of increasing, decreasing and coupon (where the player gets an additional reward after every m plays of an arm) fidelity rewards. For the models which do not necessarily enjoy sublinear regret, we provide a worst case lower bound. For those models which exhibit sublinear regret, we provide algorithms and bound their regret.