Bandits with Global Convex Constraints and Objective

Abstract

Multiarmed bandit (MAB) is a classic model for capturing the exploration–exploitation trade-off inherent in many sequential decision-making problems. The classic MAB framework, however, only allows “local” constraints on decisions and “sum of rewards” as objective. In many real-world applications, there are multiple complex constraints on resources that are consumed during the entire decision process, and performance may be evaluated through nonlinear utility functions on aggregate rewards. This article presents a new MAB framework that allows such “global” convex constraints and concave objective functions along with new algorithmic techniques with provably near-optimal performance bounds. The authors discuss applications in several domains, such as network revenue management, crowdsourcing, and pay-per-click advertising, which benefit from the new more general framework by admitting richer models and more efficient risk-averse solutions.

Cite this work

No public copy is stored for this record, so only the metadata is cited.

Stored only when both papers are in the corpus — 29 citations exist upstream.

Papers that cite the same references — the relational fallback while embeddings are still backfilling.