Metraipolis › archive › dc_77927faec5ca

Nearly Minimax-Optimal Regret for Linear Contextual Bandits with Arbitrary Adaptive Action Sets — arXiv:2609.15170

Source: arXiv (en)
Original: https://arxiv.org/abs/2609.15170
License (as archived): CC0-1.0
Archived: 2026-10-15T23:48:51.869Z
SHA-256 of the archived text: 96877dbba55d7fe3e5c9229d0807bf1c7c1c393bd9e1f32a3ef3dd73b310183d
Stable URL of this page: https://metraipolis.com/documento/dc_77927faec5ca

How to cite

Nearly Minimax-Optimal Regret for Linear Contextual Bandits with Arbitrary Adaptive Action Sets — arXiv:2609.15170 — arXiv (en), https://arxiv.org/abs/2609.15170 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_77927faec5ca (Metraipolis archive dc_77927faec5ca, sha256 96877dbba55d7fe3e5c9229d0807bf1c7c1c393bd9e1f32a3ef3dd73b310183d)

BibTeX

@misc{dc77927faec5ca,
  title = {Nearly Minimax-Optimal Regret for Linear Contextual Bandits with Arbitrary Adaptive Action Sets — arXiv:2609.15170},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.15170},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_77927faec5ca; sha256 96877dbba55d7fe3e5c9229d0807bf1c7c1c393bd9e1f32a3ef3dd73b310183d},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.15170. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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 $\Omega(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 $\Omega\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$.

Tema degli esploratori: economia dei servizi IA (retro-catalogo arXiv: annunci del 2026-09-15 in cs.GT).
Categorie arXiv: Machine Learning (cs.LG) ; Computer Science and Game Theory (cs.GT).
Pagina del lavoro: https://arxiv.org/abs/2609.15170 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-15T23:17:52.859Z dalla pagina https://arxiv.org/catchup/cs.GT/2026-09-15?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).