FLIPHAT addresses joint differential privacy for high-dimensional sparse linear bandits.
problem Efficient sequential decision-making with high-dimensional sparse features and privacy concerns.
method FLIPHAT combines iterative forgetting and N-IHT for sparse linear regression, achieving optimal regret.
result FLIPHAT achieves optimal regret in terms of privacy parameters, context dimension, and time horizon.
Improved Thompson Sampling for high-dimensional sparse bandits.
problem Stochastic linear contextual bandits with high-dimensional features.
method Thompson Sampling with spike-and-slab priors and variational inference.
result Nearly optimal upper bound on expected cumulative regret.
Study dynamic batch learning in high-dimensional sparse linear bandits.
problem Dynamic batch learning in high-dimensional sparse linear contextual bandits under batch constraints.
method Characterized fundamental learning limits via regret lower bound and provided matching upper bound.
result Prescribed an optimal scheme for dynamic batch learning in high-dimensional sparse linear contextual bandits.
New bounds for high-dimensional sparse linear bandits, balancing information and regret.
problem Stochastic linear bandits with high-dimensional sparse features.
method Derivation of minimax regret lower and upper bounds for explore-then-commit algorithm.
result Optimal rate of Θ ( n 2 / 3 ) Θ(n^{2/3}) Θ ( n 2/3 ) for data-poor regime, complemented by O ( n ) O(\sqrt{n}) O ( n ) under signal magnitude assumption. A privacy-preserving algorithm for high-dimensional bandits.
problem High-dimensional stochastic contextual linear bandits with sparse parameters under privacy constraints.
method PrivateLASSO algorithm based on sparse hard-thresholding and episodic thresholding.
result Minimax private lower bounds and utility guarantees for PrivateLASSO.
IDS improves sparse linear bandits by balancing information and regret.
problem Sparse linear bandits in high-dimensional decision-making.
method Information-directed sampling (IDS) with Bayesian regret bounds and empirical Bayesian sparse posterior sampling.
result IDS nearly matches existing lower bounds and significantly reduces regret.
A new method for sparse linear bandits reduces exploration-exploitation tradeoff.
problem Sparse linear bandits in high-dimensional settings with finite actions.
method Best subset selection for parameter estimation and doubly growing epochs for regret minimization.
result Achieves nearly dimension-independent regret of i l d e O ( s T ) ilde{\mathcal{O}}(s\sqrt{T}) i l d e O ( s T ) with high probability. Optimal algorithm for high-dimensional stochastic linear bandits with sparse parameters.
problem High-dimensional stochastic linear bandits with sparse parameters.
method Three-stage arm selection algorithm using thresholded Lasso for estimation.
result Achieves exact minimax optimality in cumulative regret.
Develops a method to tackle high-dimensional linear bandits with knapsacks using online sparse estimation and dual variables.
problem High-dimensional linear bandits with knapsacks.
method Online hard thresholding algorithm for sparse estimation, integrated with primal-dual scheme.
result Achieves sub-linear regret that scales logarithmically with feature dimension, improving on prior work.
Paper addresses regret minimization and inference in high-dimensional online decision-making.
problem Regret minimization and statistical inference in high-dimensional online decision-making.
method Integrates ε-greedy bandit algorithm with hard thresholding for sparse bandit parameters and debiasing method for inference.
result Achieves either O ( T 1 / 2 ) O(T^{1/2}) O ( T 1/2 ) regret or O ( T 1 / 2 ) O(T^{1/2}) O ( T 1/2 ) -consistent inference, with trade-off between exploration and exploitation. A two-phase algorithm identifies the best arm in sparse linear bandits with fixed budget.
problem Best arm identification in sparse linear bandits with limited budget.
method Lasso and Optimal-Design (Lasso-OD) based linear best-arm identification.
result Lasso-OD achieves significant performance improvement for sparse and high-dimensional linear bandits.
A new algorithm reduces communication costs for collaborative decision-making across clients.
problem Collaborative decision-making with sparse rewards and heterogeneous contexts.
method Federated Lasso algorithm for sparse linear contextual bandits.
result Achieves near-optimal regret with logarithmic communication costs.
A novel approach tackles sparse linear bandits with reduced communication costs and minimal cumulative regret.
problem Sparse linear bandits with high-dimensional feature vectors and limited relevant features.
method Cooperative Thresholded Lasso using Lasso and ridge regression for dimension reduction and aggregation.
result Regret bound of O ( s 0 log d + s 0 T ) \mathcal{O}(s_0 \log d + s_0 \sqrt{T}) O ( s 0 log d + s 0 T ) with high probability. PopArt efficiently solves sparse linear bandits with tighter recovery guarantees.
problem Sparse linear bandits where rewards depend on a few covariates.
method PopArt: a simple, computationally efficient sparse linear estimation method.
result Improved regret bounds compared to state-of-the-art algorithms.
New algorithms for generalized linear bandits with unknown reward functions.
problem Misspecification of reward functions in existing bandit algorithms.
method Introducing single index bandits, proposing STOR, ESTOR, and GSTOR algorithms.
result Achieved nearly optimal regret bound of i l d e O T ( T ) ilde{O}_T(\sqrt{T}) i l d e O T ( T ) . Improved online Lasso reduces regret in sparse linear contextual bandits.
problem Sparse linear contextual bandit problem with inefficient sampling.
method Perturbed adversary approach to alleviate sampling inefficiency.
result Online Lasso achieves O ( k T log d ) \mathcal{O}(\sqrt{kT\log d}) O ( k T log d ) regret bound. Algorithm achieves comparable performance to fully dynamic data with only a few batches.
problem High-dimensional multi-armed contextual bandits with batched feedback.
method Provable sample-efficient algorithm using batch allocation method.
result Achieves regret bounds comparable to fully sequential setting with only L = O(log T) batches.
Unified framework for high-dimensional bandit problems with low-dimensional structures.
problem Stochastic high-dimensional bandit problems with low-dimensional structures.
method Proposed a simple unified algorithm and a general analysis framework for the regret upper bound.
result Unified algorithm achieves comparable regret bounds in various high-dimensional bandit problems.
Study shows high-dimensional sparse RL hardness and Lasso Q-iteration's nearly dimension-free regret.
problem Hardness of online sparse reinforcement learning in high-dimensional MDPs.
method Lower bound construction and Lasso fitted Q-iteration analysis.
result Lasso Q-iteration achieves nearly dimension-free regret of O ~ ( s 2 / 3 N 2 / 3 ) \tilde{O}(s^{2/3}N^{2/3}) O ~ ( s 2/3 N 2/3 ) with oracle access to a good exploratory policy. Paper improves sparse linear bandits by accounting for noise variance.
problem Sparse linear bandits with unknown noise variance.
method Develops a general framework to convert variance-aware algorithms to sparse linear bandits.
result Achieves $\widetilde{\mathcal O}\left(\sqrt{d\sum_{t=1}^T σ_t^2} + 1
ight)$ regret, interpolating between worst-case and benign settings.
Contextual multi-armed bandit algorithms are widely used in sequential decision tasks such as news article recommendation systems, web page ad placement algorithms, and mobile health. Most of the existing algorithms have regret proportional to a polynomial function of the context dimension, d d d . In many applications ho…
New method for linear bandits with unknown sparsity, improving sparse regret bounds.
problem Sparse regret bounds for unknown sparsity and adversarial action sets.
method Combines online to confidence set conversions with randomized model selection over nested confidence sets.
result First sparse regret bounds for unknown sparsity and adversarial action sets.
Optimal multitask learning method for sparse heterogeneous datasets.
problem Efficiently learning from multiple related datasets with sparse task-specific differences.
method MOLAR estimator, combining weighted median and shrinkage.
result Improves estimation error dependence on data dimension compared to task-wise least squares.
Contextual bandits with linear payoffs, which are also known as linear bandits, provide a powerful alternative for solving practical problems of sequential decisions, e.g., online advertisements. In the era of big data, contextual data usually tend to be high-dimensional, which leads to new challenges for traditional l…
Thresholded Lasso bandit minimizes regret in sparse linear bandits.
problem Sparse stochastic contextual linear bandits with large feature vectors.
method Uses Lasso framework with thresholding to estimate reward function and its sparse support.
result Non-asymptotic regret upper bounds scaling as O ( log d + T ) \mathcal{O}( \log d + \sqrt{T}) O ( log d + T ) . SPARKLE handles high-dimensional covariates for online decision-making.
problem Complex reward-covariate relationships in high-dimensional settings.
method SPARKLE uses a sparse additive reward model with doubly penalized estimator and adaptive screening.
result SPARKLE achieves sublinear regret bound logarithmic in covariate dimensionality.
Study symmetric linear bandits with hidden symmetry, achieving improved regret bounds.
problem High-dimensional linear bandits with hidden symmetry.
method Model selection within low-dimensional subspaces to learn hidden symmetry.
result Achieved improved regret bounds of O ( d 0 2 / 3 T 2 / 3 log ( d ) ) O(d_0^{2/3} T^{2/3} \log(d)) O ( d 0 2/3 T 2/3 log ( d )) and O ( d 0 T log ( d ) ) O(d_0\sqrt{T\log(d)} ) O ( d 0 T log ( d ) ) . Unified approach tackles high-dimensional tensor bandits with convex optimization and weakly decomposable regularizers.
problem Challenges in high-dimensional generalized tensor bandits where existing algorithms fail.
method Proposes a generalized linear tensor bandits algorithm with a unified analytical framework using convex optimization and weakly decomposable regularizers.
result Unified analytical framework provides better bounds and broader applicability compared to existing methods.
IDS improves reinforcement learning with contextual information.
problem Optimizing IDS for contextual reinforcement learning.
method Investigated contextual bandit problems and proposed a computationally-efficient IDS.
result Contextual IDS outperforms conditional IDS by considering future contexts.
We study the neural-linear bandit model for solving sequential decision-making problems with high dimensional side information. Neural-linear bandits leverage the representation power of deep neural networks and combine it with efficient exploration mechanisms, designed for linear contextual bandits, on top of the last…
New method reduces linear regret in high-dimensional bandit problems.
problem Heavy spectral tails in streaming matrices lead to linear regret in sketch-based linear bandits.
method Dyadic Block Sketching, a multi-scale matrix sketching approach.
result Achieves sublinear regret bounds without prior knowledge of streaming matrix properties.
ALEXP improves model selection in linear bandits with exponential regret improvement.
problem Model selection in linear bandits is challenging due to balancing exploration and exploitation.
method ALEXP uses online learning with favorable bias-variance trade-off to emulate full-information feedback.
result ALEXP achieves an exponentially improved ( log M \log M log M ) regret dependence on the number of models M M M . New algorithms balance collaboration and adversarial behavior in linear bandits.
problem Minimizing regret in a collaborative linear bandit problem with adversarial agents.
method Robust collaborative phased elimination algorithm with tight analyses.
result Achieves near-optimal regret bounds of $O\left(α+ 1/\sqrt{M}
ight) \sqrt{dT}$ for good agents.
New algorithm reduces bandit problem's regret bound to logarithmic in dimension.
problem Sparse linear bandit problem with sparse reward structure.
method Proposes an algorithm that uses compatibility condition on optimal arm.
result Achieves regret bound of O(poly log dT) without additional diversity assumptions.
Paper solves stochastic contextual linear bandits using linear bandit algorithms.
problem Stochastic contextual linear bandits with unknown context distribution.
method Establishes a reduction framework to convert to linear bandit problems.
result Achieves nearly optimal regret bound of O ( d T log T ) O(d\sqrt{T\log T}) O ( d T log T ) . PROBE algorithm efficiently solves sparse high-dimensional linear regression.
problem Sparse high-dimensional linear regression models with complex parameter spaces.
method Partitioned empirical Bayes ECM algorithm for computationally efficient MAP estimation.
result PROBE algorithm provides robust and efficient coordinate-wise optimization.
Novel algorithm reduces feature inclusion in online decision-making.
problem Optimizing decision-making for personalized user experiences with fairness.
method Online Batched Sequential Inclusion (OBSI) algorithm for sequential feature inclusion.
result OBSI outperforms other algorithms in terms of regret, relevance of features, and compute.
We propose a minimax concave penalized multi-armed bandit algorithm under generalized linear model (G-MCP-Bandit) for a decision-maker facing high-dimensional data in an online learning and decision-making process. We demonstrate that the G-MCP-Bandit algorithm asymptotically achieves the optimal cumulative regret in t…
CDSSD detects sparse changes in partially observable data streams.
problem Online change detection of sparse changes in partially observable high-dimensional data streams.
method Smooth-sparse decomposition, spike-slab variational Bayesian inference, adaptive sampling via Thompson sampling.
result CDSSD effectively detects sparse changes in partially observable data streams.
The paper analyzes sparse high-dimensional linear regression with random design and unknown error variance, providing adaptiveness and concentration rates.
problem Sparse high-dimensional linear regression with random design and unknown error variance.
method Analysis of posterior concentration rates, employing techniques to address model misspecification.
result Adaptiveness and concentration rates of the posterior for sparse high-dimensional linear regression.
New algorithm reduces regret in bandit optimization for high-dimensional data.
problem Optimizing decisions in uncertain environments with high-dimensional data.
method Inspired by online Newton step, proposes a simple and efficient BCO algorithm.
result Achieves optimal regret bounds for κ κ κ -convex functions. New method tackles high-dimensional SBL without covariance matrices.
problem Sparse coding problem in high-dimensional settings.
method Parallel solution of multiple linear systems using conjugate gradient algorithm.
result Our method scales better in computation time and memory.
New distributions allow greedy arm selection in sparse bandit problems.
problem Sparse contextual bandit problem with sparse parameters and feature distributions.
method Introduced new distribution classes and demonstrated that mixtures of these distributions are also greedy-applicable.
result Greedy algorithm applicable to a wider range of arm feature distributions, including those with origin-asymmetric support.
New algorithm tackles high-dimensional contextual bandits without sparsity.
problem High-dimensional linear contextual bandit problem with large feature space.
method Proposes explore-then-commit (EtC) and adaptive explore-then-commit (AEtC) algorithms.
result Derives optimal rate for ETC algorithm and shows adaptive AEtC achieves it.
Picasso is a new library for sparse learning problems in R and Python.
problem Sparse learning problems in high-dimensional data analysis.
method Unified framework of pathwise coordinate optimization with efficient active set selection strategies.
result picasso can efficiently handle large-scale problems.
Stochastic zeroth-order (SZO), or gradient-free, optimization allows to optimize arbitrary functions by relying only on function evaluations under parameter perturbations, however, the iteration complexity of SZO methods suffers a factor proportional to the dimensionality of the perturbed function. We show that in scen…
Develops TOFU for tensor bandits with low-rank structure.
problem Linear bandit models fail to capture high-dimensional, low-rank tensor structures.
method Develops TOFU, a tensor bandit algorithm that estimates low-dimensional subspaces and uses norm constraints.
result Improves regret bound by a multiplicative factor that grows exponentially in system order.
Many conventional statistical procedures are extremely sensitive to seemingly minor deviations from modeling assumptions. This problem is exacerbated in modern high-dimensional settings, where the problem dimension can grow with and possibly exceed the sample size. We consider the problem of robust estimation of sparse…