Metraipolis › archive › dc_3a05c81fa57e

Satisficing Regret Minimization in Bandits with Knapsacks — arXiv:2610.39321

Source
arXiv (en)
Original
https://arxiv.org/abs/2610.39321
License (as archived)
CC0-1.0
Archived
2026-11-01T02:27:09.222Z
SHA-256 of the archived text
ac2b0a592cc7ab3a33aaab88398648a1f560be738e3761955b71411269d224af
Stable URL of this page
https://metraipolis.com/documento/dc_3a05c81fa57e

How to cite

Satisficing Regret Minimization in Bandits with Knapsacks — arXiv:2610.39321 — arXiv (en), https://arxiv.org/abs/2610.39321 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_3a05c81fa57e (Metraipolis archive dc_3a05c81fa57e, sha256 ac2b0a592cc7ab3a33aaab88398648a1f560be738e3761955b71411269d224af)
BibTeX
@misc{dc3a05c81fa57e,
  title = {Satisficing Regret Minimization in Bandits with Knapsacks — arXiv:2610.39321},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2610.39321},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_3a05c81fa57e; sha256 ac2b0a592cc7ab3a33aaab88398648a1f560be738e3761955b71411269d224af},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.39321. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

We study satisficing regret minimization in bandits with knapsacks (BwK), where a learner sequentially selects randomized policies, i.e., distributions over arms, to obtain mean rewards above a satisficing threshold as frequently as possible while respecting finite resource budgets. The performance is measured by satisficing regret, the cumulative deficits of the selected policies' mean rewards below this threshold. Resource constraints introduce two difficulties: an algorithm can incur linear satisficing regret even with small standard regret as deficits to the threshold cannot be compensated, and random consumption can cause early resource depletion even when policies are feasible in expectation. To address these challenges, we propose SELECTwK, a general algorithmic template that uses a BwK learning oracle algorithm with sub-linear expected (standard) regret upper bound to search for and test candidate satisficing policies (i.e., policies whose mean rewards exceed satisficing threshold and whose expected resource consumption is feasible over the time horizon). Our regret analysis, supported by an LP-duality argument, establishes that SELECTwK attains constant expected satisficing regret when a satisficing policy exists. We further introduce a stronger regret condition that bounds the expected sum of positive reward deficits to the optimal one at each time step, under which SELECTwK achieves a sharper constant bound together with a sub-linear bound in the time horizon. As a complement, SELECTwK still preserves the oracle's sub-linear expected standard regret bound if the satisficing threshold is unattainable. Finally, we establish the oracle conditions and corresponding satisficing regret bound for existing finite-armed BwK and dynamic pricing algorithms, and conduct numerical experiments on dynamic pricing with limited inventory to demonstrate the empirical performance of SELECTwK.

Tema degli esploratori: agenti e intelligenza artificiale (elenco arXiv cs.LG, nuovi lavori del giorno).
Categorie arXiv: Machine Learning (stat.ML) ; Machine Learning (cs.LG).
Pagina del lavoro: https://arxiv.org/abs/2610.39321 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-01T02:12:44.296Z dalla pagina https://arxiv.org/list/cs.LG/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).