Regret lower bound and optimal algorithm for high-dimensional contextual linear bandit

DOI10.1214/21-EJS1909MaRDI QIDQ2074307zbMATH OpenOpenAlexFDO

Authors Ke Li, Yun Yang, Naveen Naidu Narisetty

Publication date 9 February 2022

Published in Electronic Journal of Statistics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2109.11612, https://projecteuclid.org/journals/electronic-journal-of-statistics/volume-15/issue-2/Regret-lower-bound-and-optimal-algorithm-for-high-dimensional-contextual/10.1214/21-EJS1909.full

zbMATH Keywords

contextual linear bandithigh-dimensionminimax regretsparsityupper confidence bound

Mathematics Subject Classification ID

Sequential statistical design (62L05)

Abstract: In this paper, we consider the multi-armed bandit problem with high-dimensional features. First, we prove a minimax lower bound, $$, for the cumulative regret, in terms of horizon $T$, dimension $d$ and a margin parameter $alphain[0,1]$, which controls the separation between the optimal and the sub-optimal arms. This new lower bound unifies existing regret bound results that have different dependencies on T due to the use of different values of margin parameter $alpha$ explicitly implied by their assumptions. Second, we propose a simple and computationally efficient algorithm inspired by the general Upper Confidence Bound (UCB) strategy that achieves a regret upper bound matching the lower bound. The proposed algorithm uses a properly centered $el{l}_1$-ball as the confidence set in contrast to the commonly used ellipsoid confidence set. In addition, the algorithm does not require any forced sampling step and is thereby adaptive to the practically unknown margin parameter. Simulations and a real data analysis are conducted to compare the proposed method with existing ones in the literature.

Recommendations

• Linearly parameterized bandits
• On two continuum armed bandit problems in high dimensions
• Online decision making with high-dimensional covariates
• UCB revisited: improved regret bounds for the stochastic multi-armed bandit problem
• Contextual bandits with continuous actions: smoothing, zooming, and adapting

Cites work

• 10.1162/153244303321897663
• A linear response bandit problem
• Decoding by Linear Programming
• Fast learning rates for plug-in classifiers
• Finite-time analysis of the multiarmed bandit problem
• High-dimensional statistics. A non-asymptotic viewpoint
• scientific article; zbMATH DE number 845714 (Why is no real title available?)
• Linearly parameterized bandits
• Nearly unbiased variable selection under minimax concave penalty
• Online decision making with high-dimensional covariates
• Reconstruction From Anisotropic Random Measurements
• Reinforcement learning with immediate rewards and linear hypotheses
• Statistics for high-dimensional data. Methods, theory and applications.
• The lower tail of random quadratic forms with applications to ordinary least squares
• Variable Selection via Nonconcave Penalized Likelihood and its Oracle Properties
• Woodroofe's one-armed bandit problem revisited

Cited in

(9)

• Improved regret for zeroth-order adversarial bandit convex optimisation
• Multidimensional binary search for contextual decision-making
• Regret and Convergence Bounds for a Class of Continuum-Armed Bandit Problems
• Regret Bounds and Regimes of Optimality for User-User and Item-Item Collaborative Filtering
• Bounded Regret for Finitely Parameterized Multi-Armed Bandits
• Regret bounds for Narendra-Shapiro bandit algorithms
• Online decision making with high-dimensional covariates
• Interior-Point Methods for Full-Information and Bandit Online Learning
• Bypassing the Monster: A Faster and Simpler Optimal Algorithm for Contextual Bandits Under Realizability

This page was built for publication: Regret lower bound and optimal algorithm for high-dimensional contextual linear bandit

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2074307)