# Fully Dynamic Online Selection through Online Contention Resolution Schemes

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 10 of its 30 references that are in the map.
- First posted on arXiv 8 Jan 2023.

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

- [Online Learning: A Modern Introduction Using Convex Optimization](https://mlsanity.com/paper/1912.13213/) (2019)
- [Blocking Bandits](https://mlsanity.com/paper/1907.11975/) (2019)
- [Allocation Problems in Ride-Sharing Platforms: Online Matching with Offline Reusable Resources](https://mlsanity.com/paper/1711.08345/) (2017)
- [A Stochastic Probing Problem with Applications](https://mlsanity.com/paper/1302.5913/) (2013)
- [Contextual Blocking Bandits](https://mlsanity.com/paper/2003.03426/) (2020)
- [Online Learning for Min Sum Set Cover and Pandora's Box](https://mlsanity.com/paper/2202.04870/) (2022)
- [Online Contention Resolution Schemes](https://mlsanity.com/paper/1508.00142/) (2015)
- [Online Stochastic Max-Weight Matching: prophet inequality for vertex and edge arrival models](https://mlsanity.com/paper/2002.09807/) (2020)
- [Combinatorial Blocking Bandits with Stochastic Delays](https://mlsanity.com/paper/2105.10625/) (2021)
- [Tight Regret Bounds for Stochastic Combinatorial Semi-Bandits](https://mlsanity.com/paper/1410.0949/) (2014)

## Abstract (arXiv)

We study fully dynamic online selection problems in an adversarial/stochastic setting that includes Bayesian online selection, prophet inequalities, posted price mechanisms, and stochastic probing problems subject to combinatorial constraints. In the classical ``incremental'' version of the problem, selected elements remain active until the end of the input sequence. On the other hand, in the fully dynamic version of the problem, elements stay active for a limited time interval, and then leave. This models, for example, the online matching of tasks to workers with task/worker-dependent working times, and sequential posted pricing of perishable goods. A successful approach to online selection problems in the adversarial setting is given by the notion of Online Contention Resolution Scheme (OCRS), that uses a priori information to formulate a linear relaxation of the underlying optimization problem, whose optimal fractional solution is rounded online for any adversarial order of the input sequence. Our main contribution is providing a general method for constructing an OCRS for fully dynamic online selection problems. Then, we show how to employ such OCRS to construct no-regret algorithms in a partial information model with semi-bandit feedback and adversarial inputs.