Multi-Armed Bandits with Generalized Temporally-Partitioned Rewards
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 $\beta$-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.
Code (0)
등록된 구현이 없습니다.
Tasks
Decision MakingMulti-Armed BanditsSimilar Papers 제목 키워드 기반
Generalizing distribution of partial rewards for multi-armed bandits with temporally-partitioned rewards
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 en…
Multi-Armed BanditsMulti-Armed Bandit Problem with Temporally-Partitioned Rewards: When Partial Feedback Counts
There is a rising interest in industrial online applications where data becomes available sequentially. Inspired by the recommendation of playlists to users where their preferences can be collected during the listening o…
Identification of the Generalized Condorcet Winner in Multi-dueling Bandits
The reliable identification of the “best” arm while keeping the sample complexity as low as possible is a common task in the field of multi-armed bandits. In the multi-dueling variant of multi-armed bandits, where feedba…
Multi-Armed BanditsGeneralized Risk-Aversion in Stochastic Multi-Armed Bandits
We consider the problem of minimizing the regret in stochastic multi-armed bandit, when the measure of goodness of an arm is not the mean return, but some general function of the mean and the variance.We characterize the…
Multi-Armed BanditsGeneralized Thompson Sampling for Contextual Bandits
Thompson Sampling, one of the oldest heuristics for solving multi-armed bandits, has recently been shown to demonstrate state-of-the-art performance. The empirical success has led to great interests in theoretical unders…
Multi-Armed BanditsThompson Sampling