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.

Fully Dynamic Online Selection through Online Contention Resolution Schemes / Avadhanula, V.; Celli, A.; Colini-Baldeschi, R.; Leonardi, S.; Russo, M.. - 37:6(2023), pp. 6693-6700. (Intervento presentato al convegno National Conference of the American Association for Artificial Intelligence tenutosi a Washington; USA) [10.1609/aaai.v37i6.25821].

Fully Dynamic Online Selection through Online Contention Resolution Schemes

Leonardi S.
;
Russo M.
2023

Abstract

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.
2023
National Conference of the American Association for Artificial Intelligence
online learning; online contention resolution schemes; integrity
04 Pubblicazione in atti di convegno::04b Atto di convegno in volume
Fully Dynamic Online Selection through Online Contention Resolution Schemes / Avadhanula, V.; Celli, A.; Colini-Baldeschi, R.; Leonardi, S.; Russo, M.. - 37:6(2023), pp. 6693-6700. (Intervento presentato al convegno National Conference of the American Association for Artificial Intelligence tenutosi a Washington; USA) [10.1609/aaai.v37i6.25821].
File allegati a questo prodotto
File Dimensione Formato  
Avadhanula_Fully_2023.pdf

accesso aperto

Note: DOI: https://doi.org/10.1609/aaai.v37i6.25821
Tipologia: Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 166.56 kB
Formato Adobe PDF
166.56 kB Adobe PDF

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11573/1696073
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? ND
social impact