Poster
Position-based Multiple-play Bandit Problem with Unknown Position Bias
Junpei Komiyama · Junya Honda · Akiko Takeda
Pacific Ballroom #31
Keywords: [ Bandit Algorithms ] [ Online Learning ] [ Combinatorial Optimization ] [ Non-Convex Optimization ]
Motivated by online advertising, we study a multiple-play multi-armed bandit problem with position bias that involves several slots and the latter slots yield fewer rewards. We characterize the hardness of the problem by deriving an asymptotic regret bound. We propose the Permutation Minimum Empirical Divergence (PMED) algorithm and derive its asymptotically optimal regret bound. Because of the uncertainty of the position bias, the optimal algorithm for such a problem requires non-convex optimizations that are different from usual partial monitoring and semi-bandit problems. We propose a cutting-plane method and related bi-convex relaxation for these optimizations by using auxiliary variables.
Live content is unavailable. Log in and register to view live content