High-dimensional Linear Bandits with Knapsacks
Wanteng Ma Dong Xia Jiashuo Jiang
We study the contextual bandits with knapsack (CBwK) problem under the
high-dimensional setting where the dimension of the feature is large. The
reward of pulling each arm equals the multiplication of a sparse
high-dimensional weight vector and the feature of the current arrival, with
additional random noise. In this paper, we investigate how to exploit this
sparsity structure to achieve improved regret for the CBwK problem. To this
end, we first develop an online variant of the hard thresholding algorithm that
performs the sparse estimation in an online manner. We further combine our
online estimator with a primal-dual framework, where we assign a dual variable
to each knapsack constraint and utilize an online learning algorithm to update
the dual variable, thereby controlling the consumption of the knapsack
capacity. We show that this integrated approach allows us to achieve a
sublinear regret that depends logarithmically on the feature dimension, thus
improving the polynomial dependency established in the previous literature. We
also apply our framework to the high-dimension contextual bandit problem
without the knapsack constraint and achieve optimal regret in both the
data-poor regime and the data-rich regime. We finally conduct numerical
experiments to show the efficient empirical performance of our algorithms under
the high dimensional setting.