Nonstochastic Bandits with Composite Anonymous Feedback

Nicolò Cesa-Bianchi, Tommaso Cesari, Roberto Colomboni, Claudio Gentile, Yishay Mansour

TL;DR

This paper tackles adversarial multi-armed bandits where losses are not only delayed up to $d$ rounds but also arrive anonymously and aggregated into a single composite observation at each step. The authors introduce CoLoWrapper, a randomized blocking reduction that converts any standard bandit algorithm into one handling composite anonymous feedback, achieving an optimal $\mathcal{O}(\sqrt{(d+1)KT})$ minimax regret via Follow The Regularized Leader (FTRL) with Tsallis entropy.

What Problem Does This Paper Address?

In standard bandit theory, playing an arm immediately yields an observed reward or loss. In real-world applications (such as advertising campaigns or recommendation systems), an action’s effect is often delayed and smeared over time: an ad impression may prompt a click immediately, a purchase days later, and a repeat purchase weeks later.

Existing literature often assumes that delayed feedbacks are either discernible (you know which past round caused which feedback) or stochastic. This paper introduces the significantly harder adversarial composite anonymous feedback model:

  • The loss of an action chosen at round $t$ is adversarially partitioned across $d+1$ rounds ($t, t+1, \dots, t+d$).
  • At round $t$, the learner only observes a single scalar: the composite sum of all active loss components from actions chosen in rounds $t-d$ through $t$.
  • The learner cannot decompose this scalar into individual past actions.

Methods

The authors propose CoLoWrapper (Composite Loss Wrapper), a meta-algorithm that wraps around any standard nonstochastic bandit algorithm $\mathcal{A}$:

  1. Randomized Blocking: The algorithm plays actions in blocks of random length (at least $2d+1$ rounds). A block starts on a draw round, continues across several stay rounds where the same action is repeatedly played, and finishes on an update round.
  2. Loss Aggregation & Normalization: Because the chosen action is held constant for at least $2d+1$ steps, the feedback during the final $d+1$ rounds of a block contains loss components exclusively from that single action. The learner averages the composite losses over these $d+1$ steps, normalizing by $2d+1$ (shown via an "Accountants' Lemma" to guarantee an average loss bounded in $[0, 1]$), and feeds this cleanly to the base algorithm $\mathcal{A}$.
  3. Randomized Endpoints (Bernoulli bias $\beta$): Inspired by Dekel et al. (2014c), block termination is governed by an i.i.d. sequence of Bernoulli trials (with bias $\beta = \frac{1}{2d+1}$). The randomness prevents an oblivious adversary from exploiting the transition boundaries between blocks.
  4. Algorithmic Instantiation: When paired with FTRL with $\frac{1}{2}$-Tsallis entropy, the regret depends on the algorithm's $\xi$-stability (how much consecutive action distributions drift). The authors provide a novel stability analysis showing that FTRL with Tsallis entropy has $\xi \le \mathcal{O}\left(\frac{\ln K}{\eta}\right)$.

Datasets

Not discussed in the paper. The paper is purely theoretical and does not conduct experiments on synthetic or empirical benchmark datasets.

Key Insights and Ideas

  • Anonymous Feedback is Strictly Harder: In nonstochastic bandits with non-anonymous delay $d$, the minimax regret is $\mathcal{O}(\sqrt{(d+K)T})$. In contrast, anonymous composite feedback suffers $\widetilde{\Omega}(\sqrt{(d+1)KT})$. The multiplicative dependence on $d \cdot K$ proves that anonymity adds fundamental statistical hardness.
  • Overlapping Losses are Bounded: Although each instantaneous composite loss could sum up to $d+1$, the sum of composite losses across $d+1$ consecutive identical-action steps cannot exceed $2d+1$. Dividing by $2d+1$ normalizes the effective loss to $[0, 1]$ without blowing up variance.
  • Direct Stability Analysis for Tsallis Entropy: Standard stability proofs for FTRL rely on strong convexity of the regularizer in the $\ell_1$-norm, which yields a loose factor of $\mathcal{O}(K)$. The authors bypass this intermediate step and prove stability directly via the implicit function theorem on the KKT Lagrange multipliers, achieving the tighter $\mathcal{O}(\ln K)$ dependency needed to drop extra $\sqrt{K}$ penalties.
  • Lower Bound via Linear Bandits: The authors prove matching lower bounds by reducing linear bandits on the probability simplex $\Delta_K$ to composite anonymous bandits, showing that adversarial assignment of delays enables the adversary to "stack" information in a way that stochastic delay models forbid.

Key Results

  • Regret Upper Bound: Running CoLoWrapper with FTRL ($\frac{1}{2}$-Tsallis entropy) yields a worst-case regret of: $$R_T \le c \sqrt{(d+1)KT}$$ where $c = 2\sqrt{2}$ if $d = 0$, and $c = 28$ for $d \ge 1$.

  • Exp3 Baseline: When wrapping the simpler Exp3 algorithm, the regret is $\mathcal{O}(\sqrt{(d+1)KT \ln K})$.

  • Lower Bound: Any algorithm facing $d$-delayed composite anonymous feedback must suffer regret: $$R_T = \widetilde{\Omega}(\sqrt{(d+1)KT})$$ demonstrating that the upper bound with Tsallis entropy is optimal up to logarithmic factors.

Limitations and Future Work

  • Known Maximum Delay: The algorithm requires prior knowledge of the maximum delay $d$ to tune the block lengths and learning rate.
  • Oblivious Adversary Assumption: The theoretical guarantees hold against an oblivious adversary. Adaptive adversaries (whose loss assignments react dynamically to past actions) are not addressed.
  • Suboptimal Rates for Unknown Delay: The authors note that while follow-up work (e.g., Wang et al., 2021) handles unknown $d$, that analysis yields a slower $\mathcal{O}(T^{2/3})$ rate; achieving optimal $\sqrt{T}$ rates with unknown $d$ remains open.

Summary updated

Abstract

We investigate a nonstochastic bandit setting in which the loss of an action is not immediately charged to the player, but rather spread over the subsequent rounds in an adversarial way. The instantaneous loss observed by the player at the end of each round is then a sum of many loss components of previously played actions. This setting encompasses as a special case the easier task of bandits with delayed feedback, a well-studied framework where the player observes the delayed losses individually. Our first contribution is a general reduction transforming a standard bandit algorithm into one that can operate in the harder setting: We bound the regret of the transformed algorithm in terms of the stability and regret of the original algorithm. Then, we show that the transformation of a suitably tuned FTRL with Tsallis entropy has a regret of order $\sqrt{(d+1)KT}$, where $d$ is the maximum delay, $K$ is the number of arms, and $T$ is the time horizon. Finally, we show that our results cannot be improved in general by exhibiting a matching (up to a log factor) lower bound on the regret of any algorithm operating in this setting.
BibTeX
@inproceedings{cesabianchi2018nonstochastic,
  author = {Nicolò Cesa-Bianchi and Tommaso Cesari and Roberto Colomboni and Claudio Gentile and Yishay Mansour},
  title = {{Nonstochastic Bandits with Composite Anonymous Feedback}},
  booktitle = {Conference on Learning Theory},
  year = {2018},
  url = {https://openreview.net/forum?id=rTvwlf3GGX9},
}

Loading related content...

Figure