# Adaptive Algorithms for Multi-armed Bandit with Composite and Anonymous Feedback

arXiv: https://arxiv.org/abs/2012.07048 · HTML: https://mlsanity.com/paper/2012.07048/

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 Dec 2020.

## Built on by (most cited first, 9 of 9)

- [Non-stochastic Bandits With Evolving Observations](https://mlsanity.com/paper/2405.16843/) (2024)
- [Dynamical Linear Bandits](https://mlsanity.com/paper/2211.08997/) (2022)
- [Stochastic Submodular Bandits with Delayed Composite Anonymous Bandit Feedback](https://mlsanity.com/paper/2303.13604/) (2023)
- [Reinforcement Learning with Delayed, Composite, and Partially Anonymous Reward](https://mlsanity.com/paper/2305.02527/) (2023)
- [Bounded Memory Adversarial Bandits with Composite Anonymous Delayed Feedback](https://mlsanity.com/paper/2204.12764/) (2022)
- [Stochastic Contextual Bandits with Long Horizon Rewards](https://mlsanity.com/paper/2302.00814/) (2023)
- [Adversarial Bandits with Multi-User Delayed Feedback: Theory and Application](https://mlsanity.com/paper/2310.11188/) (2023)
- [Generalizing distribution of partial rewards for multi-armed bandits with temporally-partitioned rewards](https://mlsanity.com/paper/2211.06883/) (2022)
- [Multi-Armed Bandits with Generalized Temporally-Partitioned Rewards](https://mlsanity.com/paper/2303.00620/) (2023)

## Abstract (arXiv)

We study the multi-armed bandit (MAB) problem with composite and anonymous feedback. In this model, the reward of pulling an arm spreads over a period of time (we call this period as reward interval) and the player receives partial rewards of the action, convoluted with rewards from pulling other arms, successively. Existing results on this model require prior knowledge about the reward interval size as an input to their algorithms. In this paper, we propose adaptive algorithms for both the stochastic and the adversarial cases, without requiring any prior information about the reward interval. For the stochastic case, we prove that our algorithm guarantees a regret that matches the lower bounds (in order). For the adversarial case, we propose the first algorithm to jointly handle non-oblivious adversary and unknown reward interval size. We also conduct simulations based on real-world dataset. The results show that our algorithms outperform existing benchmarks.