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