Research map / Bandits and online learning / Contextual bandits and Thompson sampling
Symmetric Linear Bandits with Hidden Symmetry
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.
Studies high-dimensional linear bandits whose reward is invariant under a hidden group of coordinate permutations, showing a general impossibility result and proposing the Explore-Models-then-Commit (EMC) model-selection algorithm over a sub-exponential collection of fixed-point subspaces.
Problem
Linear bandits in high dimension where the reward is invariant under a hidden permutation subgroup of arms' coordinates; the symmetry must be learned online, and without structural constraints regret scales linearly with the ambient dimension d.
Approach
Cast hidden symmetry as model selection over a collection of fixed-point subspaces (in bijection with set partitions of [d]); instead of model aggregation, explicitly select the best subspace from an explore phase via least-squares projection, then commit, leveraging Gaussian model selection and restricted isometry on unions of subspaces to get log(M) dependence.
Key results
- EMC achieves regret O(d0^{2/3} T^{2/3} log d) under an exploratory arm set assumption, versus the sub-exponential partition cardinality assumption.
- Under a well-separated partition assumption, regret improves to O(d0 sqrt(T) log d) (with the authors' stated ε0 ≥ T^{-1/4} condition).
- In simulations with d=100, d0=15, EMC is competitive with ESTC on sparsity and significantly outperforms it on non-crossing and non-nesting partitions.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use EMC instead of sparse-bandit ESTC | Symmetric linear bandits · Sparsity | regret | No clear effect |
| Use EMC instead of sparse-bandit ESTC | Symmetric linear bandits · Non-crossing partitions | regret | Helped |
| Use EMC instead of sparse-bandit ESTC | Symmetric linear bandits · Non-nesting partitions | regret | Helped |
| Add well-separatedness and use the corresponding model-selection procedure | EMC · Hidden symmetry with well-separated partitions | expected cumulative regret: O(d_0^{2/3}T^{2/3}\log(d)) -> O(d_0\sqrt{T}\log(d)) | Helped |
Surprising findings
- Knowing only that the hidden group is a subgroup of permutations gives no regret benefit; regret remains Omega(d sqrt(T)) even when the fixed-point subspace has dimension 2.
- The authors note that the lower-bound argument in the earlier submission was incorrect and retract it in the camera-ready version, conjecturing the correct lower bound.
Limitations
- General enumeration over the model collection is computationally expensive (exponential in d0 with polynomial in d), and NP-hardness is noted for sparsity-equivalent cases.
- Requires an exploratory arm-set assumption (minimum eigenvalue C_min) and bounded arms; the O(sqrt T) result needs well-separated partitions and a known separation constant ε0 ≥ T^{-1/4}.
Experimental setup
Benchmarks: simulated linear bandit with sparsity, non-crossing partitions, non-nesting partitions
Metrics: cumulative regret
Baselines: ESTC (sparse linear bandit explore-then-commit)
Builds on: Explore-then-Commit for sparse linear bandits Gaussian model selection compressed sensing restricted isometry property
Closest papers by meaning
- Low-Rank Bandits via Tight Two-to-Infinity Singular Subspace Recovery (ICML 2024 · similarity 0.88)
- Linear Bandits with Partially Observable Features (ICML 2025 · similarity 0.87)
- Efficient Low-Rank Matrix Estimation, Experimental Design, and Arm-Set-Dependent Low-Rank Bandits (ICML 2024 · similarity 0.87)
- Geometry-Aware Approaches for Balancing Performance and Theoretical Guarantees in Linear Bandits (ICLR 2025 · similarity 0.87)
- New Classes of the Greedy-Applicable Arm Feature Distributions in the Sparse Linear Bandit Problem (AAAI 2024 · similarity 0.87)
- Sparsity-Agnostic Linear Bandits with Adaptive Adversaries (NeurIPS 2024 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.