The Irrevocable Multi-Armed Bandit Problem

Abstract

This paper considers the multi-armed bandit problem with multiple simultaneous arm pulls and the additional restriction that we do not allow recourse to arms that were pulled at some point in the past but then discarded. This additional restriction is highly desirable from an operational perspective and we refer to this problem as the ‘Irrevocable Multi-Armed Bandit’ problem. We observe that natural modifications to well known heuristics for multi-armed bandit problems that satisfy this irrevocability constraint have unsatisfactory performance, and thus motivated introduce a new heuristic: the ‘packing ’ heuristic. We establish through numerical experiments that the packing heuristic offers excellent performance, even relative to heuristics that are not constrained to be irrevocable. We also provide a theoretical analysis that studies the ‘price ’ of irrevocability i.e. the performance loss incurred in imposing the constraint we propose on the multi-armed bandit model. We show that this performance loss is uniformly bounded for a general class of multi-armed bandit problems, and also indicate its dependence on various problem parameters. Finally, we obtain a computationally fast algorithm to implement the packing heuristic; the algorithm renders the packing heuristic computationally cheaper than methods that rely on the computation of Gittins indices. 1.

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 — 30 citations exist upstream.

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