Minimax-Optimal Regret with Near-Minimal Policy Updates in Linear Contextual Bandits

Can linear contextual bandits attain minimax-optimal regret up to constant factors uniformly across the small- and large-action regimes? How many policy updates are necessary to attain this statistical optimum? We introduce GATE for $d$-dimensional linear contextual bandits with at most $K$ actions per round and oblivious adversarial contexts. GATE achieves $$\begin{gathered} O(\sqrt{dT\log (1+T/d)\min \\ d,\log K \\ }) \end{gathered}$$ regret, with $$\begin{gathered} O(d\log (1+T/d)\log (2+\log (2+\min \\ d,\log K \\ ))/\log (2+\min \\ d,\log K \\ )) \end{gathered}$$ policy updates on every sample path. To the best of our knowledge, this is the first constant-factor minimax guarantee (i.e., the sharpest regret bound) uniformly across the small- and large-action regimes, without additional logarithmic or iterated-logarithmic multipliers. At the same regret level, a feedback lower bound establishes policy-update minimality up to an iterated-logarithmic factor in $$\begin{gathered} \min \\ d,\log K \end{gathered}$$. The central technical result is a sharp Gaussian information inequality with additive, rather than multiplicative, dependence on action-set complexity and design growth. Independent Gaussian testing and exploration, direct prediction-error control, and joint threshold calibration yield the stated regret and policy-update bounds without computing Gaussian width.