Stochastic Linear Bandits with Partially Observed Actions

• URL: http://arxiv.org/abs/2607.08971v1
• Date: Thu, 09 Jul 2026 22:23:17 GMT
• Title: Stochastic Linear Bandits with Partially Observed Actions
• Abstract summary: We study a partially observed variant of the linear bandit problem in which the learning agent only sees a random subset of coordinates for each action.<n>We show that this barrier can be overcome when the action vectors have low intrinsic dimension.<n>Our theory shows that TOFU-POV enjoys a $sqrtT$ regret that scales with the intrinsic action subspace dimension.
• Score: 11.633556389435244
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The stochastic linear bandit, where actions are represented as vectors and rewards are linear, is a central paradigm for sequential decision making. We study a partially observed variant of this problem in which the learning agent only sees a random subset of coordinates for each action. Such partial observability arises naturally in settings like recommendation and healthcare, where full action descriptions can be expensive or even impossible to obtain. In general, this makes sublinear regret information-theoretically impossible. However, we show that this barrier can be overcome when the action vectors have low intrinsic dimension. We propose an algorithm, TOFU-POV, that estimates the latent action subspace using the masked actions, imputes current actions using an epoch-wise frozen representation, and runs OFUL in the resulting low-dimensional coordinates. Our theory shows that TOFU-POV enjoys a $\sqrt{T}$ regret that scales with the intrinsic action subspace dimension as opposed to the ambient dimension and quantifies the interaction between these quantities and the missingness, decision set size, and subspace conditioning. We also devise a rank-adaptive algorithm that does not require the knowledge of the intrinsic dimension. We complement these guarantees with a lower bound based on a novel product construction that separates usual reward-learning uncertainty from a missingness-dependent cost intrinsic to partial observation. Synthetic and real data experiments support our theory and show that TOFU-POV can substantially improve upon natural baselines in this challenging problem.

Related papers

• Partial Feedback Online Learning [88.27143767009376]
  We study a new learning protocol, termed partial-feedback online learning.<n>Each instance admits a set of acceptable labels, but the learner observes only one acceptable label per round.
  arXiv  Detail & Related papers  (2026-01-29T09:39:11Z)
• VAE with Hyperspherical Coordinates: Improving Anomaly Detection from Hypervolume-Compressed Latent Space [56.362776482614976]
  Variational autoencoders (VAE) encode data into lower-dimensional latent vectors before decoding those vectors back to data.<n>We propose to formulate the latent variables of a VAE using hyperspherical coordinates, which allows compressing the latent vectors towards a given direction on the hypersphere.<n>We show that this improves both the fully unsupervised and OOD anomaly detection ability of the VAE, achieving the best performance on the datasets we considered.
  arXiv  Detail & Related papers  (2026-01-25T03:10:24Z)
• Linear Bandits with Partially Observable Features [35.08645010112184]
  We study the linear bandit problem that accounts for partially observable features.<n>We propose a novel theoretical framework and an algorithm with sublinear regret guarantees.<n>Our algorithm requires no prior knowledge of the unobserved feature space, which may expand as more features become hidden.
  arXiv  Detail & Related papers  (2025-02-10T04:15:38Z)
• Dynamical Linear Bandits [45.3190496371625]
  In many real-world sequential decision-making problems, an action does not immediately reflect on the feedback and spreads its effects over a long time frame. Previous work has investigated the Multi-Armed Bandit framework with the possibility of delayed and aggregated feedback. In this paper, we introduce a novel setting, the Dynamical Linear Bandits (DLB), an extension of the linear bandits characterized by a hidden state.
  arXiv  Detail & Related papers  (2022-11-16T15:51:44Z)
• Exploration in Linear Bandits with Rich Action Sets and its Implications for Inference [23.364534479492715]
  We show that the minimum eigenvalue of the expected matrix grows as $Omega(sqrtn) whenever the expected cumulative regret of the algorithm is $sqrtn)$. We apply our result to two practical scenarios -- emphmodel selection and emphclustering in linear bandits.
  arXiv  Detail & Related papers  (2022-07-23T20:25:07Z)
• Origins of Low-dimensional Adversarial Perturbations [17.17170592140042]
  We study the phenomenon of low-dimensional adversarial perturbations in classification. The goal is to fool the classifier into flipping its decision on a nonzero fraction of inputs from a designated class. We compute lowerbounds for the fooling rate of any subspace.
  arXiv  Detail & Related papers  (2022-03-25T17:02:49Z)
• Anti-Concentrated Confidence Bonuses for Scalable Exploration [57.91943847134011]
  Intrinsic rewards play a central role in handling the exploration-exploitation trade-off. We introduce emphanti-concentrated confidence bounds for efficiently approximating the elliptical bonus. We develop a practical variant for deep reinforcement learning that is competitive with contemporary intrinsic rewards on Atari benchmarks.
  arXiv  Detail & Related papers  (2021-10-21T15:25:15Z)
• Orthogonal Jacobian Regularization for Unsupervised Disentanglement in Image Generation [64.92152574895111]
  We propose a simple Orthogonal Jacobian Regularization (OroJaR) to encourage deep generative model to learn disentangled representations. Our method is effective in disentangled and controllable image generation, and performs favorably against the state-of-the-art methods.
  arXiv  Detail & Related papers  (2021-08-17T15:01:46Z)
• Where and What? Examining Interpretable Disentangled Representations [96.32813624341833]
  Capturing interpretable variations has long been one of the goals in disentanglement learning. Unlike the independence assumption, interpretability has rarely been exploited to encourage disentanglement in the unsupervised setting. In this paper, we examine the interpretability of disentangled representations by investigating two questions: where to be interpreted and what to be interpreted.
  arXiv  Detail & Related papers  (2021-04-07T11:22:02Z)
• Nearly Dimension-Independent Sparse Linear Bandit over Small Action Spaces via Best Subset Selection [71.9765117768556]
  We consider the contextual bandit problem under the high dimensional linear model. This setting finds essential applications such as personalized recommendation, online advertisement, and personalized medicine. We propose doubly growing epochs and estimating the parameter using the best subset selection method.
  arXiv  Detail & Related papers  (2020-09-04T04:10:39Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.