Sparse Nonparametric Contextual Bandits

Hamish Flynn, Julia Olkhovskaya, Paul Rognon-Vael · 2025

Read Sparse Nonparametric Contextual Bandits by Hamish Flynn, Julia Olkhovskaya, Paul Rognon-Vael (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-16382.txt.

Introduction

Hamish Flynn, Julia Olkhovskaya, and Paul Rognon-Vael present a 2025 theory paper on choice problems where only a few of endless traits matter. A contextual bandit picks acts from cues and learns from payoffs, a loop behind ads and care plans. Here the cue pool can run to infinity, but the payoff leans on a sparse few. The team first prove floor bounds on regret, the loss versus a perfect picker.

Their bounds show a hard cost tied to the number of acts. A tuned Thompson sampling variant then meets those floors, up to small log factors, while its cost grows only with the count of traits that matter. Kernel and neural versions gain the same edge when time runs long. Sparsity, used well, tames endless feature lists.

Catalog record

CREATORHamish Flynn, Julia Olkhovskaya, Paul Rognon-Vael
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE112 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2503-16382

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Sparse Nonparametric Contextual Bandits Hamish Flynn, Julia Olkhovskaya, Paul Rognon-Vael Abstract We study the benefits of sparsity in nonparametric contextual bandit problems, in which the set of candidate features is countably or uncountably infinite. Our contribution is two-fold. First, using a novel reduction to sequences of multi-armed bandit problems, we provide lower bounds on the minimax regret, which show that polynomial dependence on the number of actions is generally unavoidable in this setting. Second, we show that a variant of the Feel-Good Thompson Sampling algorithm enjoys regret bounds that match our lower bounds up to logarithmic factors of the horizon, and have logarithmic dependence on the effective number of candidate features. When we apply our results to kernelised and neural contextual bandits, we find that sparsity enables better regret bounds whenever the horizon is large enough relative to the sparsity and the number of actions. \altauthor Universitat Pompeu Fabra and Delft University of Technology and Bocconi University 1 Introduction The contextual bandit problem is a general model for sequential decision-making problems, in which at each step, a learner observes a context, plays an action in response to the context and then receives a reward. The goal of the learner is to maximise the reward accumulated over n rounds, which is usually measured by the regret with respect to playing the best action for each context. The contextual bandit problem has attracted a great deal of attention because it is a faithful model of many real-world problems, such as personalised advertising ( Abe and Nakamura, 1999 ) , personalised news recommendation ( Li et al., 2010 ) and medical treatment ( Durand et al., 2018 ) . In many practical situations, the set of possible contexts is very large, and the learner must use some sort of function approximation to learn general patterns that apply to new contexts. Previous works have considered finite-dimensional linear function approximation ( Abe and Long, 1999 ; Dani et al., 2008 ; Abbasi-Yadkori et al., 2011 ) , nonparametric function approximation ( Bubeck et al., 2008 ; Kleinberg et al., 2008 ; Srinivas et al., 2010 ; Valko et al., 2013 ; Slivkins, 2014 ; Singh, 2021 ) and wide neural networks ( Zhou et al., 2020 ; Zhang et al., 2021 ; Kassraie and Krause, 2022 ) . However, none of these approaches is entirely satisfactory. While linear methods lead to efficient estimation of the reward function, they typically only work well when one has considerable prior knowledge about the relationship between contexts, actions and rewards. In particular, the user is required to specify a (small) set of features such that the reward function is a linear combination of these features. Nonparametric methods are much more flexible, but they suffer from a curse of dimensionality. If the contexts are vectors, then the regret of a nonparametric contextual bandit algorithm can grow exponentially with the dimension of the contexts. Neural contextual bandit algorithms typically operate in the lazy regime ( Jacot et al., 2018 ; Chizat et al., 2019 ) , in which neural networks behave like kernel methods. As a result, these algorithms suffer from the same drawbacks as nonparametric methods. Can we achieve the best of both worlds: a contextual bandit algorithm that selects a small set of useful features from an infinite set of candidate features to achieve both flexibility and sample efficiency? In this work, we study a class of contextual bandit problems that we call sparse nonparametric contextual bandits . Briefly, we assume that the expected reward for each context-action pair is a linear combination of features selected from a set of infinitely many candidate features, which enables flexible function modelling. We further assume a sparse structure opening the way to efficient estimation. We consider both the case of countable sparsity , where the set of candidate features is countable, and the case of uncountable sparsity , where the set is uncountable. We fully describe the class under study in Section 2.2 . Contributions. We consider sparse nonparametric contextual bandits with n rounds, K actions per round and sparsity s . In the uncountable sparsity model, we consider candidate features parameterised by a d -dimensional vector. Our contribution is as follows: • First, using a novel reduction to sequences of multi-armed bandit problems, we establish lower bounds of order \sqrt{Ksn} for countable sparsity and \sqrt{Ksdn} for uncountable sparsity. These lower bounds show that it is not possible to achieve low worst-case regret when the number of actions is large relative to the number of rounds. • Second, we propose an algorithm based on the Feel-Good Thompson Sampling (FGTS) algorithm ( Zhang, 2022 ) , which uses novel sparsity priors for nonparametric models. We prove that this algorithm enjoys regret bounds that nearly match our lower bounds, even when the sparsity s is unknown. When the sparsity is known, our results demonstrate that FGTS is minimax optimal, up to logarithmic factors of n (cf. Section 4). • In addition, we identify regimes in which sparsity enables improved regret bounds in kernelised and neural contextual bandit problems. Outline. The remainder of the paper is structured as follows. In Section 2 , we formally describe the setting of sparse nonparametric contextual bandits and introduce some mild regularity conditions. We also show that our framework includes interesting settings that require feature learning, such as sparse kernelised contextual bandits and neural contextual bandits. In Section 3 , we state our lower bounds on the minimax regret and outline their proofs. In Section 4 , we describe FGTS with our sparsity priors, and we show that it enjoys regret bounds that closely match our lower bounds. Finally, in Section 5 , we summarise our findings. The proofs and the discussions of related work, limitations and directions for future work are gathered in the Appendix. Additionally, in Appendix B.2 , we use our upper and lower bounds on the minimax regret to identify regimes in which sparsity is helpful for regret minimisation in kernelised and neural contextual bandits. Notation. For any x\in\mathbb{R} , \lfloor x\rfloor is the greatest integer that is less than or equal to x and \lceil x\rceil is the least integer that is greater than or equal to x . For any positive integer d , [d] is the set \{1,\ldots,d\} . For positive integers a and m , a~\mathrm{mod}~m is defined to be the unique integer r\in\{0,1,\dots,m-1\} , such that a=qm+r , for some non-negative integer q . For any q\in[1,\infty] , d\in\mathbb{N} and R>0 , we let \mathbb{B}_{q}^{d}(R)=\{\theta\in\mathbb{R}^{d}:\|\theta\|_{q}\leq R\} denote the d -dimensional \ell_{q} -ball with radius R . For any set \mathbb{T} and any \epsilon>0 , we use \mathcal{M}(\mathbb{T},\|\cdot\|,\epsilon) to denote the \epsilon -packing number of \mathbb{T} (w.r.t. the norm \|\cdot\| ) and \mathcal{N}(\mathbb{T},\|\cdot\|,\epsilon) to denote the \epsilon -covering number of \mathbb{T} . 2 Problem Setting 2.1 Contextual Bandits We consider the following contextual bandit protocol, in which a learner interacts with an environment over a sequence of n rounds. At the start of each round t\in[n] , the environment reveals a context X_{t}\in\mathcal{X} . In response, the learner selects an action A_{t}\in\mathcal{A} and observes a real-valued reward Y_{t} . We let \mathcal{F}_{t}=\sigma(X_{1},A_{1},Y_{1},\dots,X_{t},A_{t},Y_{t}) denote the \sigma -field generated by the interaction history

Read the complete text