Stochastic Linear Bandits with Partially Observed Actions

2026-07-09 · Source: Machine Learning · Field: Technology & Digital — Artificial Intelligence & Machine Learning, Mathematics & Computational Sciences · Depth: Expert, quick

Summary

A new study addresses the challenge of stochastic linear bandits with partially observed actions, a scenario common in recommendation and healthcare where full action descriptions are unavailable. While general partial observability typically prevents sublinear regret, this research demonstrates it can be achieved when action vectors possess a low intrinsic dimension. The proposed algorithm, TOFU-POV, tackles this by estimating the latent action subspace from masked actions, imputing current actions using an epoch-wise frozen representation, and applying OFUL in the resulting low-dimensional coordinates. TOFU-POV achieves a \u221aT regret that scales with the intrinsic action subspace dimension rather than the ambient dimension, with theoretical guarantees quantifying interactions with missingness, decision set size, and subspace conditioning. A rank-adaptive variant is also introduced, eliminating the need for prior knowledge of intrinsic dimension. Both synthetic and real-world experiments validate TOFU-POV's substantial performance improvements over existing baselines.

Key takeaway

For Machine Learning Engineers developing sequential decision-making systems with partially observed actions, such as in recommendation or healthcare, you should consider TOFU-POV. This algorithm enables sublinear regret even with incomplete data, provided the underlying action vectors have low intrinsic dimension. Implementing TOFU-POV, especially its rank-adaptive variant, can substantially improve performance over traditional baselines by effectively handling missingness and leveraging latent structure.

Key insights

Sublinear regret in partially observed linear bandits is achievable if action vectors have low intrinsic dimension, via the TOFU-POV algorithm.

Principles

• Low intrinsic dimension enables sublinear regret.
• Partial observation introduces missingness-dependent cost.
• Subspace estimation can overcome partial observability.

Method

TOFU-POV estimates latent action subspace, imputes actions using epoch-wise frozen representation, then applies OFUL in low-dimensional coordinates.

In practice

• Apply TOFU-POV in recommendation systems.
• Consider TOFU-POV for healthcare decision-making.
• Utilize rank-adaptive TOFU-POV without known intrinsic dimension.

Topics

• Stochastic Linear Bandits
• Partial Observation
• Latent Subspace Estimation
• Regret Minimization
• TOFU-POV Algorithm
• Recommendation Systems

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

Related on AIssential

• Stochastic Linear Bandits with Partially Observed Actions — Low-rank structure in partially observed linear bandits enables sublinear regret via subspace estimation and imputation.
• Near-Optimal Stochastic Linear Bandits with Delay — The study sharply characterizes how delayed feedback impacts stochastic linear bandits, revealing distinct behaviors based on delay models.
• Catching a Moving Subspace: Low-Rank Bandits Beyond Stationarity — Scalar rewards enable quadratic measurements for changing low-rank subspace recovery in non-stationary bandits.
• Offline Contextual Bandits in the Presence of New Actions — A new off-policy learning method, PONA, effectively selects both existing and novel actions in evolving environments.
• Efficient Online Proportional Sampling with Applications to Smoothed Online Learning — A novel data structure enables efficient online proportional sampling in high-dimensional, dynamically evolving systems, achieving tight bounds.
• 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 Machine Learning.