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

arXiv:2609.15170v1 Announce Type: new Abstract: 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 2le Kle d, we prove an upper bound widetilde O(K^{1/4}sqrt{dT}). When Tge d^2, we further prove a lower bound Omega(K^{1/4}sqrt{dT}). Thus, for Tge d^2 and 2le Kle 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(sqrt{dKT}) bound, our upper bound improves the dependence on K by a factor of K^{1/4}. For Kge d, we prove an upper bound widetilde O_{d,T}left(sqrt{dT}min{sqrt d,(dlog K)^{1/4}}right) and a lower bound Omegaleft(sqrt{dT}minleft{sqrt d,left(frac{dlog K}{log(2d)}right)^{1/4}right}right). Here, widetilde O_{d,T} omits logarithmic factors only in d and T. In particular, for polynomially large Kge d, the upper and lower bounds both scale as d^{3/4}sqrt T up to logarithmic factors, improving the standard widetilde O(dsqrt T) rate by a factor of d^{1/4}. As K grows further, the regret smoothly recovers the dsqrt T scale once log K reaches order d.

Source: arXiv cs.LG | 2026-09-15