Algorithms for slate bandits with non-separable reward functions
This addresses a specific challenge in recommendation systems or online advertising where slate-level rewards cannot be optimized slot-wise, though it appears incremental in bandit algorithm design.
The paper tackles the slate bandit problem with non-separable reward functions, where traditional methods are infeasible due to the large number of slates, and proposes algorithms achieving sub-linear regret, with experimental results showing outperformance over benchmarks.
In this paper, we study a slate bandit problem where the function that determines the slate-level reward is non-separable: the optimal value of the function cannot be determined by learning the optimal action for each slot. We are mainly concerned with cases where the number of slates is large relative to the time horizon, so that trying each slate as a separate arm in a traditional multi-armed bandit, would not be feasible. Our main contribution is the design of algorithms that still have sub-linear regret with respect to the time horizon, despite the large number of slates. Experimental results on simulated data and real-world data show that our proposed method outperforms popular benchmark bandit algorithms.