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.
Introduction
In the classic multi-armed bandit (MAB) problem, a player chooses an action and immediately observes the resulting loss. However, real-world applications like digital advertising or e-commerce often involve feedback that is both delayed and aggregated. For instance, a product recommendation might lead to a click today, a cart addition tomorrow, and a purchase next week.
Existing research has addressed delayed feedback (where individual losses are eventually attributed to specific actions) and anonymous feedback (where only aggregate losses are observed). This paper tackles the more challenging combined framework: Nonstochastic Bandits with Composite Anonymous Feedback. In this setting, the loss from a single action is spread across up to $d$ future time steps, and the player only observes the sum of these overlapping loss components. Crucially, the losses and their temporal distribution are chosen by an adversary rather than a fixed probability distribution.
Methodology: The CoLoWrapper
The authors propose the CoLoWrapper (Composite Loss Wrapper), a general reduction technique that adapts standard bandit algorithms to the composite anonymous setting. The core idea is to force a "base" bandit algorithm to play the same action for a "block" of time.
By maintaining the same action for a duration of at least $2d+1$ steps, the feedback received in the latter half of the block is guaranteed to consist only of components originating from that specific action. This allows for an accurate estimation of the "true" loss. To prevent an adversary from exploiting fixed block boundaries, the wrapper employs a randomized schedule based on Bernoulli trials to determine block termination.
For the base algorithm, the authors identify Follow the Regularized Leader (FTRL) with Tsallis entropy as ideal due to its stability. A stable algorithm's action distribution does not shift drastically between steps, which is critical when feedback is slightly misaligned with current actions due to randomization.
Theoretical Results and Regret Analysis
The primary theoretical contribution is the establishment of minimax optimal regret bounds. The analysis reveals a fundamental difference between standard delayed feedback and anonymous composite feedback. While delay typically adds to the regret in non-anonymous settings, it becomes a multiplicative factor in the anonymous composite setting.
Using the CoLoWrapper with FTRL, the authors achieve a regret bound of $O(\sqrt{(d+1)KT})$. They further prove a matching lower bound of $\Omega(\sqrt{(d+1)KT})$, confirming the optimality of their approach. A key insight in achieving this rate is a normalization trick that allows the algorithm to treat composite losses (which can sum to $d+1$) as standard $[0,1]$ losses by averaging over appropriate windows.
Discussion
While this work provides optimal bounds for the oblivious adversary case, several avenues for future research remain. Currently, achieving these optimal rates requires prior knowledge of the maximum delay $d$. Approaches for unknown delays currently result in sub-optimal $T^{2/3}$ regret. Additionally, extending these results to adaptive adversaries, who can adjust their strategy based on the player's observed actions, remains an open challenge in the field of nonstochastic bandits.
Summary updated