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?