High-dimensional Contextual Bandit Problem without Sparsity
Junpei Komiyama Masaaki Imaizumi
In this research, we investigate the high-dimensional linear contextual
bandit problem where the number of features $p$ is greater than the budget $T$,
or it may even be infinite. Differing from the majority of previous works in
this field, we do not impose sparsity on the regression coefficients. Instead,
we rely on recent findings on overparameterized models, which enables us to
analyze the performance the minimum-norm interpolating estimator when data
distributions have small effective ranks. We propose an explore-then-commit
(EtC) algorithm to address this problem and examine its performance. Through
our analysis, we derive the optimal rate of the ETC algorithm in terms of $T$
and show that this rate can be achieved by balancing exploration and
exploitation. Moreover, we introduce an adaptive explore-then-commit (AEtC)
algorithm that adaptively finds the optimal balance. We assess the performance
of the proposed algorithms through a series of simulations.