Similar to my other question Bandit-like setup but taking max reward over multiple heads?, I'm interested in situations like the Multi-Armed Bandit setup, except where the reward is aggregated a maximising way rather than a summation.
This question is similarly about an altered scenario where the per-round reward is the maximum of a set of choices, but it allows me more information than my previous one.
Imagine per 'round' I can sequentially choose up to $k$ of my $n$ options. My choice of next option can depend both on the result of the previous ones this round as well as the usual dependence on the entire history of plays to this point. After $k$ pulls, my reward is the maximum of the outcomes of those $k$. Then a new round begins. My overall reward is the sum over rounds.
Can you share with me any literature analysing performance and regret of solutions to this kind of problem, perhaps under additional assumptions? Or can you think of any appropriate heuristics or transformations of the problem which could lead to a well-performing solution?
As in the other question, potentially there is a treatment as a $\binom n k$-armed bandit while taking care of the correlations between these 'combo arms'.
An additional approach for this special case could be to treat the initial choice as if $k=1$ (i.e. any standard MAB algorithm), then treat subsequent choices also as $k=1$ MABs, but yielding 'incremental reward' of
max(0, new_reward - current_best_reward). That would presumably require some special alteration to the reward estimation to zero out any reward mass below the 'current max'. But I haven't worked out how to do this appropriately yet and how it might interact with explore-exploit properties of existing algorithms.
As an illustrative example, I am a lone treasure-hunter. Every day the sea washes in junk or treasure to various of $n=100$ beaches and nearby islands. I have time to search $k=10$ beaches in order, but my pockets are only big enough to carry the single best thing I find! At the end of the day, the sea washes everything away. I take whatever best thing I found and add it to my treasure stash, and get ready for the next day. (I am not clever or rich enough to get bigger pockets. Travel time between beaches is fixed and I won't find anything better by searching the same beach multiple times on the same day.)