Stochastic Linear Bandits with Protected Subspace
This addresses a constrained optimization problem in online learning with potential applications in fairness or safety, but it appears incremental as it adapts existing bandit methods to a new constraint.
The paper tackles the stochastic linear bandit problem with an unknown protected subspace, where rewards are accrued only orthogonal to this subspace, and provides an algorithm with $ ilde{O}(sd\sqrt{T})$ regret for continuous action spaces while showing that discrete action spaces can lead to linear regret and establishing a $\Omega(T^{3/4})$ lower bound for certain settings.
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 $Ω(T^{3/4}).$ We finally empirically validate our results with synthetic and real datasets.