🤖 machine learning

Nearly Tight Bounds for Cross-Learning Contextual Bandits with Graphical Feedback

This paper resolves a central open question in contextual bandits by presenting an algorithm that achieves the optimal $\widetilde O(\sqrt{\alpha T})$ regret bound for cross-learning with graphical feedback under oblivious adversarial losses, effectively removing polynomial dependencies on the number of contexts even for graphs containing arms without self-loops.

Original authors: Ruiyuan Huang, Zengfeng Huang

Published 2026-07-28

📖 7 min read🧠 Deep dive

CC BY 4.0

Original authors: Ruiyuan Huang, Zengfeng Huang

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are playing a high-stakes video game where you have to make a choice every second, but you don't know the rules of the level yet. You only learn what happens after you pick an option, and sometimes the game hides the results of the choices you didn't make. This is the world of "contextual bandits," a branch of computer science where algorithms try to learn the best strategy by trial and error. Now, imagine the game gets even trickier: you aren't just learning from your own mistakes; you get to peek at the outcomes of your friends' moves too, but only if they are "connected" to you in a specific way. This is "graphical feedback." Finally, imagine the game changes its rules slightly every time you play, based on a hidden "context" (like the time of day or your character's mood), but you can use the lessons from one version of the game to help you in the next. This is "cross-learning."

The big question scientists have been asking is: If you have a massive library of these different game versions (contexts), can you learn the perfect strategy without getting bogged down by the sheer number of versions? Usually, having more versions makes the learning process slower and harder, like trying to memorize a million different maps instead of just one. Researchers wanted to know if there was a magic trick to ignore the number of versions and learn just as fast as if there were only one, while still using the helpful "peeking" from your friends.

This paper, written by Ruiyuan Huang and Zengfeng Huang, says "Yes, we can do it!" They designed a new algorithm that acts like a super-smart detective. It solves the puzzle of combining these three complex ideas—learning from different contexts, peeking at neighbors' moves, and dealing with tricky, changing rules—without getting slowed down by the number of contexts. The authors proved mathematically that their method works even when the game is rigged by a clever opponent (adversarial losses) and the rules are strict. They didn't just guess; they built a rigorous mathematical proof, which they even translated into a computer-verifiable language called Lean, involving over 100,000 lines of code to ensure every step is correct. Their experiments show that this new method learns significantly faster than previous attempts, scaling perfectly with the complexity of the game rather than getting stuck in the details.

The Detective's Dilemma: Too Many Maps, Too Few Clues

Let's break down the problem the authors tackled. Imagine you are a bidder in an online auction. Every day, you have a secret value for an item (your "context"), and you have to guess how much to bid. If you bid too low, you lose and get no info. If you bid high enough to win, you see the highest losing bid. But here's the cool part: even if you lose, you can figure out what would have happened if you had bid slightly higher. You can also use this information to guess what would have happened if your friend (who has a different secret value) had bid.

In the world of algorithms, this is a "contextual bandit with graphical feedback." The "arms" are your possible bids, the "graph" is the rulebook saying which bids reveal information about which other bids, and the "contexts" are your daily secret values. The problem is that if you have a million different secret values (contexts), a standard algorithm would have to learn a separate strategy for each one. That's like trying to memorize a million different maps to find the same treasure. The researchers wanted to know: Can we learn one master strategy that works for all contexts, using the "peeking" ability to speed things up, without the number of contexts slowing us down?

The "Special Arm" Problem

The authors discovered a sneaky trap that had stumped previous researchers. In some games, there are "arms" (choices) that don't have a "self-loop." In plain English, this means if you pick this specific choice, you don't get to see what would have happened if you had picked it again. You only see the results if someone else picks it.

Imagine a game where one specific card, the "Joker," is tricky. If you play the Joker, the game doesn't tell you if you would have won or lost with it again. You only find out if your opponent plays the Joker. If your strategy decides to play the Joker a lot, the game stops telling you about it, and you go blind. Previous methods struggled here because they couldn't figure out how to learn about the Joker without getting lost in the noise.

The Solution: The "Freeze and Split" Trick

The authors' algorithm, which they call a "FTRL" (Follow-the-Regularized-Leader) method with some fancy upgrades, solves this with a clever three-step dance:

The Snapshot (Freezing Time): Instead of trying to learn everything in real-time, the algorithm pauses every few rounds to take a "snapshot" of its current strategy. It freezes this snapshot and uses it to plan the next batch of moves. This stops the strategy from changing while it's trying to measure how well it's doing.
The Split (Two Teams): The algorithm splits its rounds into two teams. One team plays the game to gather data about how often they see the results (frequency estimation). The other team plays to gather the actual scores (loss estimation). By keeping these two groups separate, the algorithm avoids confusing its own strategy with the data it's trying to measure.
The Pessimistic Correction (The Safety Net): For that tricky "Joker" card (the arm without a self-loop), the algorithm adds a "pessimistic correction." It assumes the Joker is slightly worse than it looks to prevent the algorithm from overestimating it. This acts like a safety net, ensuring that even if the Joker is rarely seen, the algorithm doesn't get fooled into thinking it's a great choice just because it hasn't seen enough evidence to the contrary.

The Result: Fast and Furious

The authors proved that their new method achieves a "regret" (a measure of how much worse you did compared to the perfect strategy) that grows at a rate of roughly the square root of the number of rounds ( $T$ ) and the square root of the graph's complexity ( $\alpha$ ). Crucially, this rate does not depend on the number of contexts ( $M$ ).

In their simulations, they tested this against older methods. When they increased the number of contexts (the "maps"), the old methods got slower and slower. But their new method stayed fast, proving that it successfully learned to ignore the sheer volume of contexts and focus on the structure of the game. They even ran tests where they changed the complexity of the graph (the "connections" between choices), and the algorithm scaled perfectly, just as their math predicted.

Why This Matters

This isn't just about winning auctions. The ability to learn efficiently from "censored" feedback (where you don't see everything) across many different situations is huge for things like:

Recommendation systems: Learning what movies to suggest to millions of different users without needing a separate model for each person.
Medical trials: Figuring out which treatments work for different patient groups without testing every single combination.
Traffic routing: Adapting to different times of day and traffic patterns without getting overwhelmed by the data.

The authors didn't just suggest this might work; they provided a rigorous mathematical proof and a computer-checked verification to back it up. They showed that by combining the right kind of "peeking" with a smart way of handling tricky choices, we can learn faster and smarter, no matter how many different scenarios we face. It's a big step forward in teaching computers how to learn from the world without getting lost in the details.

Technical Summary: Nearly Tight Bounds for Cross-Learning Contextual Bandits with Graphical Feedback

1. Problem Setup

The paper addresses cross-learning contextual bandits with graphical feedback, a model combining three distinct learning paradigms:

Contextual Bandits: The learner faces a sequence of rounds where a context $c_t$ is drawn i.i.d. from an unknown distribution $\nu$ over a finite set $[M]$ .
Graphical Feedback: The learner selects an arm $a_t$ and observes not only the loss of the chosen arm but also the losses of its out-neighbors in a fixed, known directed feedback graph $G = ([K], E)$ .
Cross-Learning: Crucially, the feedback is "reusable" across contexts. Observing the loss of arm $a$ in context $c_t$ allows the learner to evaluate the counterfactual loss of arm $a$ under any context $c \in [M]$ .

The feedback graph $G$ is assumed to be strongly observable: every arm either has a self-loop or is observed by every other arm (i.e., $N_{in}(a) = [K] \setminus \{a\}$ ). The goal is to minimize expected regret against an oblivious adversary who fixes the loss tables $\ell_{t,c}(a) \in [0,1]$ in advance, while the adversary does not know the learner's randomization.

The Central Question: Can an algorithm achieve a regret bound of $\tilde{O}(\sqrt{\alpha T})$ —where $\alpha$ is the independence number of $G$ and $T$ is the horizon—without incurring a polynomial dependence on the number of contexts $M$ ? Previous work established this rate for non-contextual graphical bandits and for cross-learning without graphs, but the combined setting remained open, particularly for graphs containing arms without self-loops.

2. Methodology

The proposed algorithm utilizes Follow-The-Regularized-Leader (FTRL) with negative entropy regularization, integrated with an epoch-based construction to handle the unknown context distribution and the specific challenges of graphical feedback.

Key Technical Components:

Epoch Construction and Rejection Sampling:
To handle the unknown distribution $\nu$ , the algorithm divides time into epochs. Within each epoch, it uses a "delayed snapshot" of the FTRL policy (from two epochs prior) to define a fixed target distribution. This allows the learner to use rejection sampling to simulate playing from this fixed distribution. This technique decouples the policy used for playing from the data used for estimation, ensuring that the contexts used to estimate observation probabilities are fresh and independent of the current policy's trajectory.
Handling Arms Without Self-Loops (The Special Arm):
A primary obstruction in graphical bandits is that an arm without a self-loop can have a vanishing observation probability if the learner plays it frequently. The algorithm identifies a "special arm" $j_e$ in each epoch (if one exists) that has the highest empirical mass among arms without self-loops.
- Pessimistic Correction: A bias term $\beta / W_e(j_e)$ is added to the loss estimate of the special arm. This cancels the first-order estimation drift caused by implicit exploration (underestimating the loss of rarely observed arms).
- Loss Translation: To prevent the squared correction term from introducing an uncontrolled quadratic cost in the FTRL analysis, the algorithm subtracts the special arm's input from all coordinates. This translation leaves the FTRL iterate unchanged but ensures the special arm contributes zero to the local norm, shifting the quadratic cost to the remaining arms.
Random Denominator and Joint Stability:
Because the observation probability estimates appear in the denominator of the loss estimator, and the policy depends on these estimates, the trajectory and the denominators are correlated. The analysis introduces a population-denominator pseudo-estimator and an ideal trajectory. By conditioning on the snapshot and selector, the proof applies scalar random-denominator moment bounds coordinate-wise and uses a joint Softmax product-stability inequality to convert correlated trajectory errors into a sum of marginal second moments without assuming independence across arms.

3. Key Contributions

Resolution of the Context-Independent Regret Question: The paper provides an algorithm that achieves expected regret $\tilde{O}(\sqrt{\alpha T})$ for i.i.d. contexts and oblivious adversarial losses. This bound is independent of the number of contexts $M$ (up to logarithmic factors), matching the minimax rate for non-contextual strongly observable graphical bandits.
Generalization to All Strongly Observable Graphs: Unlike prior results that often required all arms to have self-loops, this method handles graphs with arms lacking self-loops. It addresses the specific difficulty where high-probability play on a no-self-loop arm leads to vanishing observation probability.
Novel Analysis for Dependent Estimators: The work develops a "random-denominator and joint-stability" analysis framework to handle the correlation between the adaptive policy and the empirical observation probabilities in the presence of cross-learning.
Formalization: The main theorem is formally verified in Lean, with an end-to-end development exceeding 100,000 lines of code, ensuring the correctness of the complex probabilistic arguments.

4. Results

Theoretical Guarantee: The algorithm achieves a regret bound of $\tilde{O}(\sqrt{\alpha T})$ . The hidden factors are logarithmic in $M$ , $K$ , and $T$ . This confirms that cross-learning can effectively eliminate the dependence on the context space size $M$ even in the presence of complex graphical feedback.
Experimental Validation: Controlled synthetic experiments demonstrate that the algorithm outperforms baselines that utilize only graph feedback or only cross-learning. The results exhibit the predicted square-root scaling with respect to both the horizon $T$ and the independence number $\alpha$ .
Robustness: The method functions correctly even when the context distribution is unknown, a significant improvement over warm-up scenarios where $\nu$ is assumed known.

5. Significance

The paper claims to settle a central open question in the field of contextual bandits with structured feedback. By proving that the context-independent rate $\tilde{O}(\sqrt{\alpha T})$ is attainable under oblivious adversarial losses, the work bridges the gap between the theoretical limits of graphical bandits and the practical needs of applications like repeated first-price auctions, where feedback is censored but reusable across contexts.

The significance is twofold:

Theoretical: It removes the restriction that arms must have self-loops to achieve optimal rates, extending the applicability of graphical bandit theory to a broader class of feedback structures.
Practical: It provides a robust algorithm for settings where the context distribution is unknown, a common real-world constraint, while leveraging the efficiency gains of both cross-learning and graphical feedback.

The authors emphasize that their result is a direct corollary for stochastic losses (since stochastic losses are a special case of oblivious adversarial losses) and that the formalization in Lean provides a high degree of confidence in the correctness of the intricate proof involving dependent estimators and epoch-based sampling.