Nearly Dimension-Independent Sparse Linear Bandit over Small Action Spaces via Best Subset Selection
From MaRDI portal
Publication:6153988
Abstract: We consider the stochastic contextual bandit problem under the high dimensional linear model. We focus on the case where the action space is finite and random, with each action associated with a randomly generated contextual covariate. This setting finds essential applications such as personalized recommendation, online advertisement, and personalized medicine. However, it is very challenging as we need to balance exploration and exploitation. We propose doubly growing epochs and estimating the parameter using the best subset selection method, which is easy to implement in practice. This approach achieves regret with high probability, which is nearly independent in the ``ambient regression model dimension . We further attain a sharper regret by using the extsc{SupLinUCB} framework and match the minimax lower bound of low-dimensional linear stochastic bandit problems. Finally, we conduct extensive numerical experiments to demonstrate the applicability and robustness of our algorithms empirically.
Cites work
- 10.1162/153244303321897663
- \({\mathcal Q}\)-learning
- A linear response bandit problem
- A robust method for estimating optimal treatment regimes
- Algorithm selection for combinatorial search problems: a survey
- An information-theoretic analysis of Thompson sampling
- Asymptotically efficient adaptive allocation rules
- Bandit algorithms
- Best subset selection via a modern optimization lens
- Compressed sensing
- Demystifying Optimal Dynamic Treatment Regimes
- Doubly robust learning for estimating individualized treatment with censored data
- Estimating individualized treatment rules using outcome weighted learning
- Finite-time analysis of the multiarmed bandit problem
- scientific article; zbMATH DE number 3790208 (Why is no real title available?)
- scientific article; zbMATH DE number 1906319 (Why is no real title available?)
- scientific article; zbMATH DE number 845714 (Why is no real title available?)
- Inference for non-regular parameters in optimal dynamic treatment regimes
- Iterative hard thresholding for compressed sensing
- Linearly parameterized bandits
- Non-stationary stochastic optimization
- Optimal Dynamic Treatment Regimes
- Penalized Q-learning for dynamic treatment regimens
- Q-learning with censored data
- Randomized allocation with arm elimination in a bandit problem with covariates
- Randomized allocation with nonparametric estimation for a multi-armed bandit problem with covariates
- Regret analysis of stochastic and nonstochastic multi-armed bandit problems
- Reinforcement learning with immediate rewards and linear hypotheses
- Reinforcement learning. An introduction
- Restricted eigenvalue properties for correlated Gaussian designs
- Sharp Thresholds for High-Dimensional and Noisy Sparsity Recovery Using $\ell _{1}$-Constrained Quadratic Programming (Lasso)
- Simultaneous analysis of Lasso and Dantzig selector
- Sparse Approximate Solutions to Linear Systems
- Sparse learning via Boolean relaxations
- Sparse online learning via truncated gradient
- Sparsity regret bounds for individual sequences in online linear regression
- Statistical inference for online decision making: in a contextual bandit setting
- Statistics for high-dimensional data. Methods, theory and applications.
- Targeted sequential design for targeted learning inference of the optimal treatment rule and its mean reward
- The Dantzig selector: statistical estimation when \(p\) is much larger than \(n\). (With discussions and rejoinder).
This page was built for publication: Nearly Dimension-Independent Sparse Linear Bandit over Small Action Spaces via Best Subset Selection
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6153988)
