# Multi-Armed Bandits with Generalized Temporally-Partitioned Rewards

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 9 of its 47 references that are in the map.
- First posted on arXiv 1 Mar 2023.

## Builds on (most cited first, 9 of 9)

- [Online Learning under Delayed Feedback](https://mlsanity.com/paper/1306.0686/) (2013)
- [Linear Bandits with Stochastic Delayed Feedback](https://mlsanity.com/paper/1807.02089/) (2018)
- [Stochastic Bandit Models for Delayed Conversions](https://mlsanity.com/paper/1706.09186/) (2017)
- [Stochastic bandits with arm-dependent delays](https://mlsanity.com/paper/2006.10459/) (2020)
- [The Music Streaming Sessions Dataset](https://mlsanity.com/paper/1901.09851/) (2018)
- [Nonstochastic Bandits with Composite Anonymous Feedback](https://mlsanity.com/paper/2112.02866/) (2021)
- [Randomized Allocation with Nonparametric Estimation for Contextual Multi-Armed Bandits with Delayed Rewards](https://mlsanity.com/paper/1902.00819/) (2019)
- [Adaptive Algorithms for Multi-armed Bandit with Composite and Anonymous Feedback](https://mlsanity.com/paper/2012.07048/) (2020)
- [Multi-Armed Bandit Problem with Temporally-Partitioned Rewards: When Partial Feedback Counts](https://mlsanity.com/paper/2206.00586/) (2022)

## Abstract (arXiv)

Decision-making problems of sequential nature, where decisions made in the past may have an impact on the future, are used to model many practically important applications. In some real-world applications, feedback about a decision is delayed and may arrive via partial rewards that are observed with different delays. Motivated by such scenarios, we propose a novel problem formulation called multi-armed bandits with generalized temporally-partitioned rewards. To formalize how feedback about a decision is partitioned across several time steps, we introduce β-spread property. We derive a lower bound on the performance of any uniformly efficient algorithm for the considered problem. Moreover, we provide an algorithm called TP-UCB-FR-G and prove an upper bound on its performance measure. In some scenarios, our upper bound improves upon the state of the art. We provide experimental results validating the proposed algorithm and our theoretical results.