Multi-Dimensional Arms for Combinatorial Multi-Armed Bandit

The multi-armed bandit (MAB) problem with concave rewards has indeed become a significant area of research in recent years. In MAB problem, maximizing total rewards within a fixed number of pulls is a common objective. Previous works have indeed made substantial advancements in designing efficient online selection algorithms. However, the limitation of these works is that they fail to achieve a sublinear regret bound with multi-dimensional arms. In this paper, we study a combinatorial MAB problem with concave rewards and multi-dimensional arms for online advertising delivery. At first, we treat a multi-dimensional arm as a vector and adapt the choice of arm based on contextual information. Moreover, we utilize the confidence ellipsoid to construct optimistic estimate. Based on optimistic estimate, we combine online convex optimization with bandit methods to design selection algorithm. Our algorithm’s can achieve a sublinear regret bound of <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\mathcal {O}(\sqrt {T})$ </tex-math></inline-formula> with probability guarantees in T selection rounds. At last, we evaluate the performance of our algorithm through extensive simulations and demonstrate that it is better than the baseline algorithms.