3
$\begingroup$

If I have a process where I can evaluate one of a number of options per 'round', with variable reward, and I want to maximise reward over time, the multi-armed bandit literature has lots of useful suggestions.

What if instead, per 'round', I can evaluate some subset of my options (say $k$ out of $n$ overall options), again with variable outcomes, but where the reward this round is the $max$ of the outcomes of the $k$ choices? As usual, my overall reward is the sum over rounds.

Clearly with $k = 1$ or $k = n-1$ the problem reduces to a standard MAB, and with $k = n$ there is no choice to be made and regret is necessarily zero. What about the in between cases?

I suppose it could be viewed as a MAB with $\binom n k$ arms but with the rewards correlated in a very particular way? But my gut says there must be a better way to analyse this. (And ideally it'd scale roughly with $n$ rather than $\binom n k$...)


For a motivating example, suppose each day the sea washes various flotsam, jetsam and/or treasure onto $n = 100$ beaches. I am part of a gang of $k=10$ explorers who can each accurately evaluate everything washed onto one beach each in the morning. And between us we have time and tools to collect any treasure from just one beach in the afternoon before everything is washed away again. Different beaches are more or less likely to surface nice things. How should we allocate our evaluation expeditions to get the best total return over the long run?

$\endgroup$
3
  • $\begingroup$ I'm more than happy with answers assuming fixed $n$ and $k$ per round, but of course welcome any more general answers as well! $\endgroup$
    – Oly
    Aug 16 '21 at 12:21
  • $\begingroup$ I wanted to add a tag exploration-exploitation which I thought would be appropriate, but don't have the reputation required on this site. Perhaps multiarmed-bandit is sufficient $\endgroup$
    – Oly
    Aug 16 '21 at 12:22
  • $\begingroup$ If I have an index-based approach to solving an otherwise-similar $k=1$ MAB problem, how much do I lose by simply selecting the top-$k$-indexed values for this modified problem? If I had a Thompson-style approach to an otherwise-similar $k=1$ MAB, how much do I lose by simply sampling my set-of-$k$ from the posterior distribution over top-$k$-means? $\endgroup$
    – Oly
    Aug 16 '21 at 14:22
1
$\begingroup$

I believe this setting falls under the category of combinatorial bandits. In such setting, the agent can select a subsets of all arms, i.e., the action set $\mathcal{A}$ is a subset of the power set $\mathcal{A} \subset 2^{[n]}$, where $n$ is the number of arms.

Set this paper: Combinatorial Multi-Armed Bandit: General Framework, Results and Applications for a comprehensive introduction to the topic of combinatorial bandits and related algorithms.

$\endgroup$
1
  • 1
    $\begingroup$ See my edit for a more informative way to present links! It is even better if you can also add a full reference, as links might not live forever. $\endgroup$ Aug 30 '21 at 1:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.