Dynamic Batch Learning in High-Dimensional Sparse Linear Contextual Bandits
We study the problem of dynamic batch learning in high-dimensional sparse linear contextual bandits, where a decision maker, under a given maximum-number-of-batch constraint and only able to observe rewards at the end of each batch, can dynamically decide how many individuals to include in the next batch (at the end of the current batch) and what personalized action-selection scheme to adopt within each batch. Such batch constraints are ubiquitous in a variety of practical contexts, including personalized product offerings in marketing and medical treatment selection in clinical trials. We characterize the fundamental learning limit in this problem via a regret lower bound and provide a matching upper bound (up to log factors), thus prescribing an optimal scheme for this problem. To the best of our knowledge, our work provides the first inroad into a theoretical understanding of dynamic batch learning in high-dimensional sparse linear contextual bandits. Notably, even a special case of our result -- when no batch constraint is present -- yields that the simple exploration-free algorithm using the LASSO estimator already achieves the minimax optimal regret bound for standard online learning in high-dimensional linear contextual bandits (for the no-margin case), a result that appears unknown in the emerging literature of high-dimensional contextual bandits.
Code (0)
등록된 구현이 없습니다.
Tasks
Decision MakingMarketingMulti-Armed BanditsVocal Bursts Intensity PredictionSimilar Papers 제목 키워드 기반
Provably Efficient High-Dimensional Bandit Learning with Batched Feedbacks
We study high-dimensional multi-armed contextual bandits with batched feedback where the $T$ steps of online interactions are divided into $L$ batches. In specific, each batch collects data according to a policy that dep…
Multi-Armed BanditsHigh-dimensional online learning via asynchronous decomposition: Non-divergent results, dynamic regularization, and beyond
Existing high-dimensional online learning methods often face the challenge that their error bounds, or per-batch sample sizes, diverge as the number of data batches increases. To address this issue, we propose an asynchr…
SNAP-FM: Sparse Nonlinear Accelerated Projection for Physics-Constrained Generative Modeling
Generative models have emerged as scalable surrogates for physical simulation, yet they offer no guarantee that their outputs respect the conservation laws, boundary conditions, and nonlinear invariants that govern the u…
High-Dimensional Limit of Stochastic Gradient Flow via Dynamical Mean-Field Theory
Modern machine learning models are typically trained via multi-pass stochastic gradient descent (SGD) with small batch sizes, and understanding their dynamics in high dimensions is of great interest. However, an analytic…
Kernel Recursive Least Squares Dictionary Learning Algorithm
We propose an efficient online dictionary learning algorithm for kernel-based sparse representations. In this framework, input signals are nonlinearly mapped to a high-dimensional feature space and represented sparsely u…