Adversarial Linear Contextual Bandits with Graph-Structured Side Observations

Abstract

This paper studies the adversarial graphical contextual bandits, a variant of adversarial multi-armed bandits that leverage two categories of the most common side information: \emph{contexts} and \emph{side observations}. In this setting, a learning agent repeatedly chooses from a set of $K$ actions after being presented with a $d$-dimensional context vector. The agent not only incurs and observes the loss of the chosen action, but also observes the losses of its neighboring actions in the observation structures, which are encoded as a series of feedback graphs. This setting models a variety of applications in social networks, where both contexts and graph-structured side observations are available. Two efficient algorithms are developed based on \texttt{EXP3}. Under mild conditions, our analysis shows that for undirected feedback graphs the first algorithm, \texttt{EXP3-LGC-U}, achieves the regret of order $\mathcal{O}(\sqrt{(K+\alpha (G)d)T\log K})$ over the time horizon $T$, where $\alpha (G)$ is the average \emph{independence number} of the feedback graphs. A slightly weaker result is presented for the directed graph setting as well. The second algorithm, \texttt{EXP3-LGC-IX}, is developed for a special class of problems, for which the regret is reduced to $\mathcal{O}(\sqrt{\alpha (G)dT\log K\log (KT)})$ for both directed as well as undirected feedback graphs. Numerical tests corroborate the efficiency of proposed algorithms.

arXiv commentfix some typos

References in corpus (19)

• A Contextual-Bandit Approach to Personalized News Article Recommendation
• Analysis of Thompson Sampling for the multi-armed bandit problem
• Thompson Sampling for Contextual Bandits with Linear Payoffs
• Taming the Monster: A Fast and Simple Algorithm for Contextual Bandits
• Multi-armed Bandits with Application to 5G Small Cells
• Efficient learning by implicit exploration in bandit problems with side observations
• Finite-Time Analysis of Kernelised Contextual Bandits
• Efficient Optimal Learning for Contextual Bandits
• Cascading Bandits: Learning to Rank in the Cascade Model
• Efficient Contextual Bandits in Non-stationary Worlds
• A Survey on Contextual Multi-armed Bandits
• Neural Contextual Bandits with UCB-based Exploration
• Efficient Algorithms for Adversarial Contextual Learning
• From Bandits to Experts: A Tale of Domination and Independence
• Bandits on graphs and structures
• Online learning with noisy side observations
• Information Directed Sampling for Stochastic Bandits with Graph Feedback
• Nearly Optimal Algorithms for Piecewise-Stationary Cascading Bandits
• Contextual Bandits with Side-Observations