# Paired multiarm bandit

I have a set of independent experiments with different distributions and I'm trying to determine which has the highest mean payoff. I would like to treat this as a multi-arm bandit problem, but the setting is a bit unusual.

At each iteration I choose 2 of the experiments, each randomly produces a set of items, then a single item is chosen out of the combined item sets and the experiment that produced the chosen item is the winner. It is possible for both experiments to produce the same (or similar) set of items and if the winning item was in both experiments, then its a draw.

I can keep track of the likelihood of overlap for all pairs of experiments if it makes sense that experiments producing identical item sets offer little information and experiments producing wildly different items contribute significantly.

My initial idea was to choose the experiment pair that maximizes

$$\text{UCB}(E_i) \text{UCB}(E_j) \hat{\Delta}(E_i, E_j),$$

but I have trouble justifying this or finding any bounds.

Has anyone seen something similar or have any idea how I should proceed?

• have you tried combinatorial bandits? May 13 at 16:30