# Weighted Tallying Bandits: Overcoming Intractability via Repeated Exposure Optimality

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 57 references that are in the map.
- First posted on arXiv 4 May 2023.

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

- [Is Q-learning Provably Efficient?](https://mlsanity.com/paper/1807.03765/) (2018)
- [Introduction to Multi-Armed Bandits](https://mlsanity.com/paper/1904.07272/) (2019)
- [Is a Good Representation Sufficient for Sample Efficient Reinforcement Learning?](https://mlsanity.com/paper/1910.03016/) (2019)
- [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)
- [Stochastic Rising Bandits](https://mlsanity.com/paper/2212.03798/) (2022)
- [Multi-armed Bandit Problem with Known Trend](https://mlsanity.com/paper/1508.07091/) (2015)
- [Policy Regret in Repeated Games](https://mlsanity.com/paper/1811.04127/) (2018)
- [Discrepancy-Based Algorithms for Non-Stationary Rested Bandits](https://mlsanity.com/paper/1710.10657/) (2017)
- [Addressing the Long-term Impact of ML Decisions via Policy Regret](https://mlsanity.com/paper/2106.01325/) (2021)
- [Complete Policy Regret Bounds for Tallying Bandits](https://mlsanity.com/paper/2204.11174/) (2022)
- [Congested Bandits: Optimal Routing via Short-term Resets](https://mlsanity.com/paper/2301.09251/) (2023)

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

- [Learning in Markov Games with Adaptive Adversaries: Policy Regret, Fundamental Barriers, and Efficient Algorithms](https://mlsanity.com/paper/2411.00707/) (2024)
- [On Mitigating Affinity Bias through Bandits with Evolving Biased Feedback](https://mlsanity.com/paper/2503.05662/) (2025)

## Abstract (arXiv)

In recommender system or crowdsourcing applications of online learning, a human's preferences or abilities are often a function of the algorithm's recent actions. Motivated by this, a significant line of work has formalized settings where an action's loss is a function of the number of times that action was recently played in the prior m timesteps, where m corresponds to a bound on human memory capacity. To more faithfully capture decay of human memory with time, we introduce the Weighted Tallying Bandit (WTB), which generalizes this setting by requiring that an action's loss is a function of a weighted summation of the number of times that arm was played in the last m timesteps. This WTB setting is intractable without further assumption. So we study it under Repeated Exposure Optimality (REO), a condition motivated by the literature on human physiology, which requires the existence of an action that when repetitively played will eventually yield smaller loss than any other sequence of actions. We study the minimization of the complete policy regret (CPR), which is the strongest notion of regret, in WTB under REO. Since m is typically unknown, we assume we only have access to an upper bound M on m. We show that for problems with K actions and horizon T, a simple modification of the successive elimination algorithm has O left( √KT + (m+M)K right) CPR. Interestingly, upto an additive (in lieu of mutliplicative) factor in (m+M)K, this recovers the classical guarantee for the simpler stochastic multi-armed bandit with traditional regret. We additionally show that in our setting, any algorithm will suffer additive CPR of Omega left( mK + M right), demonstrating our result is nearly optimal. Our algorithm is computationally efficient, and we experimentally demonstrate its practicality and superiority over natural baselines.