Efficient Algorithms for Combinatorial-Bandits with Monotonicity

This research introduces a new perspective to solving combinatoriarl bandit problems, with feedback provided from an unknown reward aggregation function. Previous approaches made strong assumptions on the structure of the reward function and had intractible sample complexities.

In this approach we are able to compare two arms directly by examining the rewards from sets including those arms, while randomizing over the other arms. This approach lets us compare two arms individually and get a pairwise preference over the arms.

We finally solved the combinatorial bandit problem by adapting an existing algorithm for pairwise preferences using our technique to solve the combinatorial bandit problem.

Recommended citation: Wagde, A., Saha, A., Efficient Algorithms for Combinatorial-Bandits with Monotonicity. NeurIPS OPTML (2025). https://openreview.net/forum?id=D3drIoEW5B
Download Paper