Rising Rested MAB with Linear Drift

Omer Amichay, Yishay Mansour
1/8/2025
cs.LG

No confident code implementation found for this paper.

Abstract

We consider non-stationary multi-arm bandit (MAB) where the expected reward of each action follows a linear function of the number of times we executed the action. Our main result is a tight regret bound of $\tildeΘ(T^{4/5}K^{3/5})$, by providing both upper and lower bounds. We extend our results to derive instance dependent regret bounds, which depend on the unknown parametrization of the linear drift of the rewards.

View on arXivView PDF

Code Implementations

No confident code match yet

We couldn't find an author-owned or strongly-evidenced community implementation for this paper. Any repos shown below are weak matches — verify before relying on them.

No code implementations found yet.

Know of an implementation? Let us know in the comments below!

Similar Papers

Rising Rested Bandits: Lower Bounds and Efficient Algorithms

87% match2024

Tracking Most Significant Shifts in Infinite-Armed Bandits

85% match2025

Complexity Analysis of a Countable-armed Bandit Problem

84% match2023

Variance-Dependent Regret Bounds for Non-stationary Linear Bandits

84% match2024

Linear Bandits with Memory: from Rotting to Rising

83% match2023

Adaptive Smooth Non-Stationary Bandits

83% match1 repo2024

Cite this paper

@article{amichay2025rising,
  title  = {Rising Rested MAB with Linear Drift},
  author = {Omer Amichay and Yishay Mansour},
  year   = {2025},
  eprint = {2501.04403},
  archivePrefix = {arXiv},
  url    = {http://arxiv.org/abs/2501.04403v1}
}

Add a badge to your README

Shows whether official code is linked for this paper.

Code of Paper badge
[![Code of Paper](https://codeofpaper.com/badge/2501.04403.svg)](https://codeofpaper.com/paper/2501.04403)

Discussion