Tighter Bounds for Multi-Armed Bandits with Expert Advice

Abstract

Bandit problems are a classic way of formulating exploration versus exploitation tradeoffs. Auer et al. [ACBFS02] introduced the EXP4 algorithm, which explicitly decouples the set of A actions which can be taken in the world from the set of M experts (general strategies for selecting actions) with which we wish to be competitive. Auer et al. show that EXP4 has expected cumulative regret bounded by O ( √ T A log M), where T is the total number of rounds. This bound is attractive when the number of actions is small compared to the number of experts, but poor when the situation is reversed. In this paper we introduce a new algorithm, similar in spirit to EXP4, which has a bound of O ( √ T S log M). The S parameter measures the extent to which expert recommendations agree; we always have S ≤ min {A, M}. We discuss practical applications that arise in the contextual bandits

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

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