Research map / Bandits and online learning / Contextual bandits and Thompson sampling

New Classes of the Greedy-Applicable Arm Feature Distributions in the Sparse Linear Bandit Problem

AAAI 2024 · Bandits and online learning › Contextual bandits and Thompson sampling · approach: Linear and generalized linear bandits · 2 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Shows the greedy arm-selection policy in sparse linear bandits keeps sample diversity for a much wider class of arm feature distributions, via mixture closure and new Gaussian-mixture, low-rank, discrete, and radial bases.

Problem

Sparsity-agnostic greedy algorithms for sparse linear contextual bandits need strong arm-feature distribution assumptions (relaxed symmetry) to guarantee sample diversity, which excludes origin-asymmetric distributions such as positive-valued or discrete features.

Approach

Proves that mixtures containing a greedy-applicable component are greedy-applicable, and introduces new greedy-applicable basis classes (Gaussian mixture, low-rank Gaussian mixture, discrete, radial mixture) that can have origin-asymmetric support, with the compatibility-constant lower bound derived from an independent arm's distribution.

Key results

• Proves that a mixture with a phi_0-greedy-applicable component is c*phi_0-greedy-applicable (Theorem 1).
• Shows Gaussian mixture, low-rank Gaussian mixture, discrete, and radial mixture bases are greedy-applicable, giving bar-phi > 0 and regret O(1/bar-phi^2 sqrt((log d + log T) T)) for greedy.
• Worked examples include a binary 2D discrete distribution with support in the positive quadrant and a uniform distribution on a square minus a disk, both shown to be greedy-applicable.

Limitations

• The size of the compatibility constant lower bound phi_0 is not quantitatively characterized and depends on unspecified selection probabilities.
• Requires at least one arm to be independent of the others and selected with positive probability.
• Radial basis and other bases may not cover all truncated distributions; correlated-arm settings left to future work.

Experimental setup

Metrics: compatibility constant lower bound regret upper bound order

Baselines: relaxed symmetry assumption thresholded lasso bandit greedy algorithm analysis of prior work

Builds on: LASSO relaxed symmetry sparse greedy analysis thresholded lasso bandit smoothed analysis of greedy bandits

Closest papers by meaning

• Semi-Parametric Sampling for Stochastic Bandits with Many Arms (AAAI 2019 · similarity 0.91)
• Thresholded Lasso Bandit (ICML 2022 · similarity 0.90)
• Lasso Bandit with Compatibility Condition on Optimal Arm (ICLR 2025 · similarity 0.90)
• Almost Minimax Optimal Best Arm Identification in Piecewise Stationary Linear Bandits (NeurIPS 2024 · similarity 0.90)
• Sparsity-Agnostic Linear Bandits with Adaptive Adversaries (NeurIPS 2024 · similarity 0.88)
• Generalized Linear Bandits with Limited Adaptivity (NeurIPS 2024 · similarity 0.88)