Thompson Sampling for Complex Online Problems

Abstract

We consider stochastic multi-armed bandit prob-lems with complex actions over a set of basic arms, where the decision maker plays a complex action rather than a basic arm in each round. The reward of the complex action is some function of the basic arms ’ rewards, and the feedback ob-served may not necessarily be the reward per-arm. For instance, when the complex actions are subsets of the arms, we may only observe the maximum reward over the chosen subset. Thus, feedback across complex actions may be cou-pled due to the nature of the reward function. We prove a frequentist regret bound for Thomp-son sampling in a very general setting involving parameter, action and observation spaces and a likelihood function over them. The bound holds for discretely-supported priors over the parame-ter space without additional structural properties such as closed-form posteriors, conjugate prior structure or independence across arms. The re-gret bound scales logarithmically with time but, more importantly, with an improved constant that non-trivially captures the coupling across complex actions due to the structure of the re-wards. As applications, we derive improved re-gret bounds for classes of complex bandit prob-lems involving selecting subsets of arms, includ-ing the first nontrivial regret bounds for nonlin-ear MAX reward feedback from subsets. Us-ing particle filters for computing posterior distri-butions which lack an explicit closed-form, we present numerical results for the performance of Thompson sampling for subset-selection and job

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

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