Efficient Contextual Bandits with Uninformed Feedback Graphs
Bandits with feedback graphs are powerful online learning models that interpolate between the full information and classic bandit problems, capturing many real-life applications. A recent work by Zhang et al. (2023) studies the contextual version of this problem and proposes an efficient and optimal algorithm via a reduction to online regression. However, their algorithm crucially relies on seeing the feedback graph before making each decision, while in many applications, the feedback graph is uninformed, meaning that it is either only revealed after the learner makes her decision or even never fully revealed at all. This work develops the first contextual algorithm for such uninformed settings, via an efficient reduction to online regression over both the losses and the graphs. Importantly, we show that it is critical to learn the graphs using log loss instead of squared loss to obtain favorable regret guarantees. We also demonstrate the empirical effectiveness of our algorithm on a bidding application using both synthetic and real-world data.
Code (0)
등록된 구현이 없습니다.
Tasks
Multi-Armed BanditsregressionSimilar Papers 제목 키워드 기반
Practical Contextual Bandits with Feedback Graphs
While contextual bandit has a mature theory, effectively leveraging different feedback patterns to enhance the pace of learning remains unclear. Bandits with feedback graphs, which interpolates between the full informati…
Multi-Armed BanditsregressionStochastic contextual bandits with graph feedback: from independence number to MAS number
We consider contextual bandits with graph feedback, a class of interactive learning problems with richer structures than vanilla contextual bandits, where taking an action reveals the rewards for all neighboring actions …
Multi-Armed BanditsDiffusion Models Meet Contextual Bandits with Large Action Spaces
Efficient exploration is a key challenge in contextual bandits due to the large size of their action space, where uninformed exploration can result in computational and statistical inefficiencies. Fortunately, the reward…
Efficient ExplorationMulti-Armed BanditsThompson SamplingAdversarial Linear Contextual Bandits with Graph-Structured Side Observations
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}…
Multi-Armed BanditsImproved High-Probability Regret for Adversarial Bandits with Time-Varying Feedback Graphs
We study high-probability regret bounds for adversarial $K$-armed bandits with time-varying feedback graphs over $T$ rounds. For general strongly observable graphs, we develop an algorithm that achieves the optimal regre…
Multi-Armed Bandits