Learning Orthogonal Projections in Linear Bandits
This work addresses a specific challenge in recommendation systems by modeling and mitigating bias corruption, representing an incremental improvement over classical linear bandits.
The paper tackles the problem of learning the best arm in a linear stochastic bandit model where the reward is based on an unobservable projection onto a subspace, addressing corruption by individual biases in applications like recommendation systems. It develops strategies achieving O(|D| log n) regret for finite arms and O(n^{2/3} (log n)^{1/2}) regret for infinite compact sets, with experiments verifying efficiency.
In a linear stochastic bandit model, each arm is a vector in an Euclidean space and the observed return at each time step is an unknown linear function of the chosen arm at that time step. In this paper, we investigate the problem of learning the best arm in a linear stochastic bandit model, where each arm's expected reward is an unknown linear function of the projection of the arm onto a subspace. We call this the projection reward. Unlike the classical linear bandit problem in which the observed return corresponds to the reward, the projection reward at each time step is unobservable. Such a model is useful in recommendation applications where the observed return includes corruption by each individual's biases, which we wish to exclude in the learned model. In the case where there are finitely many arms, we develop a strategy to achieve $O(|\bbD|\log n)$ regret, where $n$ is the number of time steps and $|\bbD|$ is the number of arms. In the case where each arm is chosen from an infinite compact set, our strategy achieves $O(n^{2/3}(\log{n})^{1/2})$ regret. Experiments verify the efficiency of our strategy.