# Bandits with Dynamic Arm-acquisition Costs

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 29 references that are in the map.
- First posted on arXiv 23 Oct 2021.

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

- [What Doubling Tricks Can and Can't Do for Multi-Armed Bandits](https://mlsanity.com/paper/1803.06971/) (2018)
- [Rotting Bandits](https://mlsanity.com/paper/1702.07274/) (2017)
- [Optimal Exploration-Exploitation in a Multi-Armed-Bandit Problem with Non-stationary Rewards](https://mlsanity.com/paper/1405.3316/) (2014)
- [Simple regret for infinitely many armed bandits](https://mlsanity.com/paper/1505.04627/) (2015)
- [Stochastic Bandits with Delay-Dependent Payoffs](https://mlsanity.com/paper/1910.02757/) (2019)
- [An Asymptotically Optimal Index Policy for Finite-Horizon Restless Bandits](https://mlsanity.com/paper/1707.00205/) (2017)
- [Matching while Learning](https://mlsanity.com/paper/1603.04549/) (2016)
- [Bandits with many optimal arms](https://mlsanity.com/paper/2103.12452/) (2021)
- [From Finite to Countable-Armed Bandits](https://mlsanity.com/paper/2105.10721/) (2021)
- [Infinite Arms Bandit: Optimality via Confidence Bounds](https://mlsanity.com/paper/1805.11793/) (2018)

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

- [Max-Quantile Grouped Infinite-Arm Bandits](https://mlsanity.com/paper/2210.01295/) (2022)

## Abstract (arXiv)

We consider a bandit problem where at any time, the decision maker can add new arms to her consideration set. A new arm is queried at a cost from an "arm-reservoir" containing finitely many "arm-types," each characterized by a distinct mean reward. The cost of query reflects in a diminishing probability of the returned arm being optimal, unbeknown to the decision maker; this feature encapsulates defining characteristics of a broad class of operations-inspired online learning problems, e.g., those arising in markets with churn, or those involving allocations subject to costly resource acquisition. The decision maker's goal is to maximize her cumulative expected payoffs over a sequence of n pulls, oblivious to the statistical properties as well as types of the queried arms. We study two natural modes of endogeneity in the reservoir distribution, and characterize a necessary condition for achievability of sub-linear regret in the problem. We also discuss a UCB-inspired adaptive algorithm that is long-run-average optimal whenever said condition is satisfied, thereby establishing its tightness.