Linear contextual bandits achieve near optimal regret bounds with dynamic action sets
Nearly Minimax-Optimal Regret for Linear Contextual Bandits with Arbitrary Adaptive Action Sets
Machine LearningComputer Science and Game Theory
Summary
This paper looks at a problem where a system must pick actions based on changing options and past results, aiming to do almost as well as the best fixed choice. The authors improved the understanding of how the size and complexity of choices affect the system's performance. They show that for many settings, their new method is close to the best possible, even when the options adapt based on past outcomes. This means better decision-making algorithms can be designed for complex, changing environments.
What this means in practice
- •For online recommendation systems: Design decision algorithms that adapt to changing available options while minimizing performance loss compared to the best fixed strategy.
- •For adaptive clinical trial designers: Develop trial protocols that efficiently handle dynamically changing treatment choices with nearly optimal patient outcome guarantees.
A theory result. No direct application yet.
Authors
Tianyuan Jin
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 $2\le K\le d$, we prove an upper bound $\widetilde O(K^{1/4}\sqrt{dT})$. When $T\ge d^2$, we further prove a lower bound $Ω(K^{1/4}\sqrt{dT})$. Thus, for $T\ge d^2$ and $2\le K\le 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 $K\ge d$, we prove an upper bound $\widetilde O_{d,T}\left(\sqrt{dT}\min\{\sqrt d,(d\log K)^{1/4}\}\right)$ and a lower bound $Ω\left(\sqrt{dT}\min\left\{\sqrt d,\left(\frac{d\log 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 $K\ge d$, the upper and lower bounds both scale as $d^{3/4}\sqrt T$ up to logarithmic factors, improving the standard $\widetilde O(d\sqrt T)$ rate by a factor of $d^{1/4}$. As $K$ grows further, the regret smoothly recovers the $d\sqrt T$ scale once $\log K$ reaches order $d$.