Poster
Linear Bandits with Partially Observable Features
Wonyoung Kim · Sungwoo PARK · Garud Iyengar · Assaf Zeevi · Min-hwan Oh
[
Abstract
]
Thu 17 Jul 11 a.m. PDT
— 1:30 p.m. PDT
Abstract:
We introduce a novel linear bandit problem with partially observable features, resulting in partial reward information and spurious estimates.Without proper address for latent part, regret possibly grows linearly in decision horizon $T$, as their influence on rewards are unknown.To tackle this, we propose a novel analysis to handle the latent features and an algorithm that achieves sublinear regret.The core of our algorithm involves (i) augmenting basis vectors orthogonal to the observed feature space, and (ii) introducing an efficient doubly robust estimator.Our approach achieves a regret bound of $\tilde{O}(\sqrt{(d + d\_h)T})$, where $d$ is the dimension of observed features, and $d\_h$ is the \emph{unknown} dimension of the subspace of the unobserved features. Notably, our algorithm requires no prior knowledge of the unobserved feature space, which may expand as more features become hidden.Numerical experiments confirm that our algorithm outperforms both non-contextual multi-armed bandits and linear bandit algorithms depending solely on observed features.
Live content is unavailable. Log in and register to view live content