Research map / Bandits and online learning / Contextual bandits and Thompson sampling
Efficient Contextual Bandits with Uninformed Feedback Graphs
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Extends contextual bandits with feedback graphs (SquareCB-style DEC reduction) to uninformed settings by jointly learning the graph with a log-loss regression oracle, giving efficient regret bounds for partially and fully revealed graphs.
Problem
Contextual bandits with adversarial contexts where the directed feedback graph is unknown before the decision (uninformed) and may be revealed only partially or fully after the decision; prior efficient contextual methods required the graph beforehand.
Approach
Reduce uninformed contextual graph bandits to online regression on both losses (square loss) and graphs (log loss), plug the predicted graph into a DEC-minimizing action distribution; log loss is essential because it converts graph-estimation error into a triangular-discrimination term that cancels the DEC slack.
Key results
- Partially revealed graphs: regret O~(sqrt(alpha(G) T max{Reg_Sq, Reg_Log})), with no polynomial dependence on the number of actions K.
- Fully revealed graphs: improved regret O~(sqrt(sum_t alpha_t max{Reg_Sq, Reg_Log})), matching the informed-setting optimal rate.
- On synthetic and real auction data, the proposed algorithm outperforms SquareCB, greedy, and the always-bid-0 baseline, with SquareCB's regret growing with the number of actions while the proposed method's stays nearly flat.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use contextual bandit exploration with predicted feedback-graph information instead of ignoring graph feedback | Bidding on synthetic and real auction data · Synthetic datasets and real auction dataset | normalized regret (RegCB/T) | Helped |
| use graph feedback rather than the SquareCB approach that ignores graph feedback | Bidding with diverse synthetic contexts · Synthetic dataset with diverse contexts | normalized regret (RegCB/T) | Helped |
| increase the number of actions | SquareCB · Synthetic datasets | normalized regret (RegCB/T) | Hurt |
| use greedy action selection without explicit exploration | Bidding · Synthetic dataset with poor context diversity | normalized regret (RegCB/T) | Hurt |
| use greedy action selection without explicit exploration | Bidding · Synthetic dataset with diverse contexts | normalized regret (RegCB/T) | Helped |
| use greedy action selection without explicit exploration | Bidding · Real auction dataset | normalized regret (RegCB/T) | Mixed |
| learn feedback graphs with log loss rather than squared loss | Graph regression in Efficient Contextual Bandits with Uninformed Feedback Graphs · Partially revealed and fully revealed feedback graphs | regret guarantee | Helped |
Surprising findings
- Greedy performs nearly as badly as the trivial not-bidding baseline when contexts lack diversity, yielding linear regret.
Limitations
- Assumes strongly observable graphs; weakly observable case only sketched as extension.
- Requires knowledge of alpha(G) to set gamma (parameter-free variant given only for partially revealed setting via doubling trick).
- Requires realizability of both loss and graph function classes.
Experimental setup
Datasets: synthetic bidding data (T=5000, x in R^32) eBay auction dataset (5000-sample subset)
Benchmarks: synthetic first-price bidding environment eBay auction dataset
Metrics: normalized regret (Reg/T)
Baselines: SquareCB greedy always bid 0
Builds on: SquareCB Zhang et al. 2023 contextual bandits with feedback graphs (informed setting) Decision-Estimation Coefficient framework Foster and Rakhlin 2020 log-loss to square-loss conversion
Closest papers by meaning
- Practical Contextual Bandits with Feedback Graphs (NeurIPS 2023 · similarity 0.95)
- Stochastic contextual bandits with graph feedback: from independence number to MAS number (NeurIPS 2024 · similarity 0.93)
- Efficient First-Order Contextual Bandits: Prediction, Allocation, and Triangular Discrimination (NeurIPS 2021 · similarity 0.90)
- Adversarial Linear Contextual Bandits with Graph-Structured Side Observations (AAAI 2021 · similarity 0.90)
- Contextual Bandits with Online Neural Regression (ICLR 2024 · similarity 0.90)
- Neural Dueling Bandits: Preference-Based Optimization with Human Feedback (ICLR 2025 · similarity 0.89)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.