Stochastic Linear Bandits with Partially Observed Actions

2026-07-13 · Source: stat.ML updates on arXiv.org · Field: Technology & Digital — Artificial Intelligence & Machine Learning, Data Science & Analytics · Depth: Expert, extended

Summary

Researchers Gautam Dasarathy, Vineet Gattani, and Lalit Jain introduce TOFU-POV, an algorithm designed for stochastic linear bandits (SLB) with partially observed actions. This variant of SLB, common in recommendation and healthcare, faces information-theoretic impossibility for sublinear regret without further structure. TOFU-POV overcomes this by exploiting low intrinsic dimension in action vectors. The algorithm estimates the latent action subspace from masked actions, imputes current actions using an epoch-wise frozen representation, and applies OFUL in the resulting low-dimensional coordinates. Theoretical analysis demonstrates a ~O(m√T+κ m√T/(p²√K)) regret, scaling with intrinsic dimension m instead of ambient dimension d. A rank-adaptive version, not requiring prior knowledge of m, is also presented. Synthetic and real-data experiments, including MNIST and 20 Newsgroups, validate TOFU-POV's performance, showing significant gains over baselines, particularly with substantial missingness. A novel lower bound quantifies the intrinsic cost of partial observation.

Key takeaway

If you are an ML Engineer designing contextual bandit systems where action features are often incomplete or sparse, you should consider adopting algorithms like TOFU-POV. This method effectively utilizes underlying low-rank structure to maintain sublinear regret, even with significant missingness. Traditional zero-filling approaches degrade rapidly under heavy missingness. TOFU-POV's epoch-wise subspace estimation and imputation offer superior performance. Evaluate its rank-adaptive variant if the intrinsic dimension is unknown for robust deployment.

Key insights

Low-rank structure in partially observed linear bandits enables sublinear regret via subspace estimation and imputation.

Principles

• Low intrinsic dimension overcomes partial observability.
• Epoch-wise freezing stabilizes representation updates.

Method

TOFU-POV estimates latent subspace from masked actions, freezes representation epoch-wise, imputes current actions, and runs OFUL in low-dimensional coordinates. A rank-adaptive variant is also available.

In practice

• Apply to recommendation systems with sparse features.
• Use in healthcare for limited sensing data.

Topics

• Stochastic Linear Bandits
• Partially Observed Features
• Low-Rank Models
• Subspace Estimation
• OFUL Algorithm
• Regret Bounds

Code references

• gautamdasarathy/tofu-pov-arxiv

Best for: Research Scientist, AI Scientist, Machine Learning Engineer

Related on AIssential

• Stochastic Linear Bandits with Partially Observed Actions — Sublinear regret in partially observed linear bandits is achievable if action vectors have low intrinsic dimension, via the TOFU-POV algorithm.
• Catching a Moving Subspace: Low-Rank Bandits Beyond Stationarity — Scalar rewards enable quadratic measurements for changing low-rank subspace recovery in non-stationary bandits.
• The Sample Complexity of Multiclass and Sparse Contextual Bandits — Algorithms achieve optimal sample complexity for s-sparse contextual bandits, closing a significant gap in prior work.
• Sharp analysis of linear ensemble sampling — Linear ensemble sampling achieves near Thompson sampling regret in linear bandits using a novel continuous-time analysis.
• The Role of Contextual Information in Best Arm Identification — Contextual information significantly improves the efficiency of best-arm identification in stochastic bandits by reducing sample complexity.
• A Convex Framework for Confounding Robust Inference — A convex programming framework provides a sharp lower bound for policy evaluation in offline contextual bandits, improving robustness against unobserved confounders.

See Counsel's argued verdicts on the open AI decisions leaders are weighing →

Open in AIssential →

Editorial summary, takeaway, and curation by AIssential. Original article published by stat.ML updates on arXiv.org.