Nearly Minimax-Optimal Regret for Linear Contextual Bandits with Arbitrary Adaptive Action Sets

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 widetilde O(K1/4√dT). When T≥ d2, we further prove a lower bound Omega(K1/4√dT). 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 widetilde 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 widetilde Od,Tleft(√dTmin√ d,(dlog K)1/4right) and a lower bound Omegaleft(√dTminleft√ d,left(fracdlog Klog(2d)right)1/4rightright). Here, widetilde 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/4√ T up to logarithmic factors, improving the standard widetilde O(d√ T) rate by a factor of d1/4. As K grows further, the regret smoothly recovers the d√ T scale once log K reaches order d.