Thompson Sampling in Partially Observable Contextual Bandits
Hongju Park Mohamad Kazem Shirani Faradonbeh
Contextual bandits constitute a classical framework for decision-making under
uncertainty. In this setting, the goal is to learn the arms of highest reward
subject to contextual information, while the unknown reward parameters of each
arm need to be learned by experimenting that specific arm. Accordingly, a
fundamental problem is that of balancing exploration (i.e., pulling different
arms to learn their parameters), versus exploitation (i.e., pulling the best
arms to gain reward). To study this problem, the existing literature mostly
considers perfectly observed contexts. However, the setting of partial context
observations remains unexplored to date, despite being theoretically more
general and practically more versatile. We study bandit policies for learning
to select optimal arms based on the data of observations, which are noisy
linear functions of the unobserved context vectors. Our theoretical analysis
shows that the Thompson sampling policy successfully balances exploration and
exploitation. Specifically, we establish the followings: (i) regret bounds that
grow poly-logarithmically with time, (ii) square-root consistency of parameter
estimation, and (iii) scaling of the regret with other quantities including
dimensions and number of arms. Extensive numerical experiments with both real
and synthetic data are presented as well, corroborating the efficacy of
Thompson sampling. To establish the results, we introduce novel martingale
techniques and concentration inequalities to address partially observed
dependent random variables generated from unspecified distributions, and also
leverage problem-dependent information to sharpen probabilistic bounds for
time-varying suboptimality gaps. These techniques pave the road towards
studying other decision-making problems with contextual information as well as
partial observations.