Research map / Bandits and online learning / Contextual bandits and Thompson sampling
Linear Bandits with Partially Observable Features
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.
Proposes RoLF, a linear bandit algorithm for partially observable features that augments observed features with orthogonal complement basis vectors and uses a doubly robust Lasso/ridge estimator with resampling and coupling, achieving Õ(√((d+d_h)T)) regret without knowing unobserved features.
Problem
Linear bandits where the reward depends on both observed and unobserved features; ignoring unobserved features can cause linear regret, and the agent does not know whether features are missing.
Approach
Augment observed features with an orthonormal basis of the orthogonal complement of the observed row space so the reward becomes exactly linear in augmented features, and estimate it with a doubly robust estimator that uses the Gram matrix over all actions, with resampling/coupling to bound inverse-propensity weights.
Key results
- Regret bound of Õ(√((d+d_h)T)) for RoLF without prior knowledge of unobserved feature space, sharper than OLB and MAB bounds (MAB Õ(√(KT)))
- In simulations with K=30, d_z=35, T=1200, RoLF-Lasso and RoLF-Ridge outperform LinUCB, LinTS, DRLasso and UCB(delta) in cumulative regret across three structural cases
- Lower-bound example shows OFUL and LinTS suffer linear regret under partial observability
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use RoLF-Lasso or RoLF-Ridge instead of observed-feature-only LinUCB, LinTS, or DRLasso | Linear bandits with partially observable features · Scenario 1 (partial observability) | cumulative regret | Helped |
| use RoLF-Lasso or RoLF-Ridge instead of observed-feature-only LinUCB or LinTS | Linear bandits without partially observable features · Scenario 2 (no partial observability) | cumulative regret | Helped |
| have the latent-feature row space contained in the observed-feature row space | RoLF-Lasso and RoLF-Ridge · Scenario 1, Case 2 | cumulative regret | Helped |
| vary the relationship between observed- and latent-feature row spaces | RoLF-Lasso and RoLF-Ridge · Scenario 1, Cases 1–3 | cumulative regret | No clear effect |
Surprising findings
- Even with fixed observed features, OFUL and LinTS can suffer linear regret when latent features are ignored
- Under the fixed-feature setting, DRLasso effectively reduces to using a single fixed context vector, limiting expressiveness
Limitations
- Assumes fixed observed and unobserved features; time-varying unobserved features make the problem non-learnable
- Latent reward assumed linear in unobserved features; K^3 exploration factor and dependence on K in exploration phase
- Experiments are small synthetic simulations with five seeds
Experimental setup
Datasets: synthetic bandit environments
Benchmarks: synthetic linear bandit simulations (Scenario 1 partial observability, Scenario 2 full observability)
Metrics: cumulative regret
Baselines: LinUCB LinTS DRLasso UCB(delta)
Builds on: LinUCB OFUL LinTS DR estimation for linear contextual bandits DRLasso
Closest papers by meaning
- Generalized Linear Bandits with Limited Adaptivity (NeurIPS 2024 · similarity 0.89)
- Geometry-Aware Approaches for Balancing Performance and Theoretical Guarantees in Linear Bandits (ICLR 2025 · similarity 0.89)
- Low-Rank Bandits via Tight Two-to-Infinity Singular Subspace Recovery (ICML 2024 · similarity 0.89)
- Exploration via Feature Perturbation in Contextual Bandits (NeurIPS 2025 · similarity 0.89)
- Sparsity-Agnostic Linear Bandits with Adaptive Adversaries (NeurIPS 2024 · similarity 0.89)
- Generalized Linear Bandits: Almost Optimal Regret with One-Pass Update (NeurIPS 2025 · similarity 0.88)
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.