Stochastic Linear Bandits with Protected Subspace

Advait Parulekar, Soumya Basu, Aditya Gopalan, Karthikeyan Shanmugam, Sanjay ShakkottaiarXiv 2020 · OpenReview

Abstract

This paper introduces the "Protected Linear Bandit" framework, a novel approach to linear optimization where rewards are only accrued orthogonal to an unknown "protected" subspace. This setting models real-world scenarios where an agent must maximize a primary objective while strictly avoiding unknown side effects or protected directions. We present the Protected LinUCB algorithm, which achieves $\tilde{O}(sd\sqrt{T})$ regret in continuous action spaces. Crucially, the paper identifies a fundamental gap between continuous and discrete settings, proving that discrete action spaces impose a significantly higher regret lower bound of $\Omega(T^{3/4})$.

Introduction

In the standard stochastic linear bandit problem, an agent selects an action $x_t$ and receives a reward based on the inner product with an unknown parameter vector $\theta$. However, many high-stakes applications—such as clinical medicine or algorithmic fairness—require the agent to avoid specific "protected" directions. For example, when prescribing a combination of medications, a physician seeks to maximize treatment efficacy (the target vector) while strictly avoiding interactions with unknown side-effect biomarkers (the protected subspace).

The challenge in the Protected Linear Bandit setting is twofold: the agent knows neither the target reward vector nor the protected subspace. Furthermore, the agent receives partial feedback, needing to decide at each step whether to observe the main objective or a specific side-effect marker. The goal is to maximize the reward component that is orthogonal to the protected subspace while simultaneously learning the constraints and the objective.

Methodology: The Protected LinUCB Algorithm

The authors propose Protected LinUCB, an optimistic algorithm designed to navigate the non-linearities inherent in subspace projections. The algorithm operates in two primary phases:

1. CORE-SET Estimation

While the environment may present numerous protected vectors ($L$), these vectors typically span a lower-dimensional subspace of dimension $s$. Protected LinUCB begins with a uniform exploration phase to identify a minimal "core set" of vectors that span this protected space. This pruning process removes redundant constraints and simplifies the optimization landscape.

2. Optimistic Play via OFUL

Following the core-set estimation, the algorithm applies the Optimization in the Face of Uncertainty (OFUL) principle. It maintains confidence ellipsoids for both the unknown target vector and the core-set of protected vectors.

A significant technical hurdle in this framework is that projecting an action onto an unknown subspace is a non-linear transformation. This non-linearity typically destroys the sub-Gaussian noise properties required for standard regret analysis. To resolve this, the authors avoid constructing a confidence region for the projection operator itself. Instead, they derive a confidence interval directly for the reward of the optimistic action, preserving theoretical tractability.

Theoretical Insights: The Cost of Discreteness

A central contribution of this research is the discovery of a fundamental performance gap based on the nature of the action space:

  • Continuous Action Spaces: When the action space is a full unit ball, Protected LinUCB achieves a pseudo-regret of $\tilde{O}(sd\sqrt{T})$. This matches the $\sqrt{T}$ scaling of standard linear bandits, suggesting that the protected subspace does not fundamentally worsen the convergence rate in continuous settings.
  • Discrete Action Spaces: Surprisingly, the authors prove that if the action space is finite or discrete, no consistent algorithm can achieve better than $\Omega(T^{3/4})$ regret. This occurs because an agent in a discrete space may be unable to pull the specific directions needed to collapse the confidence ellipsoids of the protected vectors, leading to a permanent "information vs. reward" disconnect.

Empirical Evaluation

The framework was validated using both synthetic and real-world data:

  • Synthetic Benchmarks: In $\mathbb{R}^5$ environments, Protected LinUCB demonstrated superior regret reduction compared to $\epsilon$-greedy and round-robin baselines.
  • Warfarin Clinical Dataset: The authors modeled a therapy optimization problem using pharmacogenetic data. The objective was to maximize patient stability (target vector) while minimizing deviations in the INR biomarker (the protected vector), which indicates bleeding risk. Protected LinUCB successfully navigated these constraints, outperforming standard bandit baselines over 1,000 rounds.

Conclusion and Future Work

The Protected Linear Bandit framework highlights a critical limitation of naive optimism in constrained settings. While continuous action spaces allow for efficient learning, discrete settings face a much steeper regret floor. Future research directions include developing adaptive methods that do not require prior knowledge of the subspace dimension ($s$) and finding ways to bridge the performance gap in discrete action environments.

Summary updated

Abstract

We study a variant of the stochastic linear bandit problem wherein we optimize a linear objective function but rewards are accrued only orthogonal to an unknown subspace (which we interpret as a \textit{protected space}) given only zero-order stochastic oracle access to both the objective itself and protected subspace. In particular, at each round, the learner must choose whether to query the objective or the protected subspace alongside choosing an action. Our algorithm, derived from the OFUL principle, uses some of the queries to get an estimate of the protected space, and (in almost all rounds) plays optimistically with respect to a confidence set for this space. We provide a $\tilde{O}(sd\sqrt{T})$ regret upper bound in the case where the action space is the complete unit ball in $\mathbb{R}^d$, $s < d$ is the dimension of the protected subspace, and $T$ is the time horizon. Moreover, we demonstrate that a discrete action space can lead to linear regret with an optimistic algorithm, reinforcing the sub-optimality of optimism in certain settings. We also show that protection constraints imply that for certain settings, no consistent algorithm can have a regret smaller than $\Omega(T^{3/4}).$ We finally empirically validate our results with synthetic and real datasets.
BibTeX
@misc{parulekar2020stochastic,
  author = {Advait Parulekar and Soumya Basu and Aditya Gopalan and Karthikeyan Shanmugam and Sanjay Shakkottai},
  title = {{Stochastic Linear Bandits with Protected Subspace}},
  year = {2020},
  eprint = {2011.01016},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2011.01016},
}
Figure