Data Science and Analytics Thrust The Hong Kong University of Science and Technology (Guangzhou)
We study stochastic linear contextual bandits with arbitrary action menus that may depend on the fixed parameter and the interaction history. We establish matching upper and lower bounds, up to logarithmic factors. Let
d be the dimension,
K be the menu size, and
T the time horizon. For
2≤K≤d, we prove an upper bound
O(K1/4dT). When
T≥d2, we further prove a lower bound
Ω(K1/4dT). Thus, for
T≥d2 and
2≤K≤d, the upper and lower bounds match up to logarithmic factors, and the polynomial dependence on
K is optimal. Compared with the previous
O(dKT) bound, our upper bound improves the dependence on
K by a factor of
K1/4. For
K≥d, we prove an upper bound
Od,T(dTmin{d,(dlogK)1/4}) and a lower bound
Ω(dTmin{d,(log(2d)dlogK)1/4}). Here,
Od,T omits logarithmic factors only in
d and
T. In particular, for polynomially large
K≥d, the upper and lower bounds both scale as
d3/4T up to logarithmic factors, improving the standard
O(dT) rate by a factor of
d1/4. As
K grows further, the regret smoothly recovers the
dT scale once
logK reaches order
d.