# Congested Bandits: Optimal Routing via Short-term Resets

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 5 of its 24 references that are in the map.
- First posted on arXiv 23 Jan 2023.

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

- [Introduction to Multi-Armed Bandits](https://mlsanity.com/paper/1904.07272/) (2019)
- [Contextual Markov Decision Processes](https://mlsanity.com/paper/1502.02259/) (2015)
- [Rotting Bandits](https://mlsanity.com/paper/1702.07274/) (2017)
- [Recovering Bandits](https://mlsanity.com/paper/1910.14354/) (2019)
- [PAC Reinforcement Learning with Rich Observations](https://mlsanity.com/paper/1602.02722/) (2016)

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

- [Online Recommendations for Agents with Discounted Adaptive Preferences](https://mlsanity.com/paper/2302.06014/) (2023)
- [Learning in Markov Games with Adaptive Adversaries: Policy Regret, Fundamental Barriers, and Efficient Algorithms](https://mlsanity.com/paper/2411.00707/) (2024)
- [Weighted Tallying Bandits: Overcoming Intractability via Repeated Exposure Optimality](https://mlsanity.com/paper/2305.02955/) (2023)

## Abstract (arXiv)

For traffic routing platforms, the choice of which route to recommend to a user depends on the congestion on these routes -- indeed, an individual's utility depends on the number of people using the recommended route at that instance. Motivated by this, we introduce the problem of Congested Bandits where each arm's reward is allowed to depend on the number of times it was played in the past Delta timesteps. This dependence on past history of actions leads to a dynamical system where an algorithm's present choices also affect its future pay-offs, and requires an algorithm to plan for this. We study the congestion aware formulation in the multi-armed bandit (MAB) setup and in the contextual bandit setup with linear rewards. For the multi-armed setup, we propose a UCB style algorithm and show that its policy regret scales as tildeO(√K Delta T). For the linear contextual bandit setup, our algorithm, based on an iterative least squares planner, achieves policy regret tildeO(√dT + Delta). From an experimental standpoint, we corroborate the no-regret properties of our algorithms via a simulation study.