# Generalizing distribution of partial rewards for multi-armed bandits with temporally-partitioned rewards

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 3 of its 9 references that are in the map.
- First posted on arXiv 13 Nov 2022.

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

- [Online Learning under Delayed Feedback](https://mlsanity.com/paper/1306.0686/) (2013)
- [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)

We investigate the Multi-Armed Bandit problem with Temporally-Partitioned Rewards (TP-MAB) setting in this paper. In the TP-MAB setting, an agent will receive subsets of the reward over multiple rounds rather than the entire reward for the arm all at once. In this paper, we introduce a general formulation of how an arm's cumulative reward is distributed across several rounds, called Beta-spread property. Such a generalization is needed to be able to handle partitioned rewards in which the maximum reward per round is not distributed uniformly across rounds. We derive a lower bound on the TP-MAB problem under the assumption that Beta-spread holds. Moreover, we provide an algorithm TP-UCB-FR-G, which uses the Beta-spread property to improve the regret upper bound in some scenarios. By generalizing how the cumulative reward is distributed, this setting is applicable in a broader range of applications.