Rising Rested MAB with Linear Drift
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{\Theta}(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.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Analysis of Drifting Features
The notion of concept drift refers to the phenomenon that the distribution, which is underlying the observed data, changes over time. We are interested in an identification of those features, that are most relevant for t…
feature selectionDrift and behavior of E. coli cells
Chemotaxis of the bacterium Escherichia coli is well understood in shallow chemical gradients, but its swimming behavior remains difficult to interpret in steep gradients. By focusing on single-cell trajectories from sim…
General Drift Analysis with Tail Bounds
Drift analysis is one of the state-of-the-art techniques for the runtime analysis of randomized search heuristics (RSHs) such as evolutionary algorithms (EAs), simulated annealing etc. The vast majority of existing drift…
Evolutionary AlgorithmsDesigning Resilient Linear Driftless Systems
Critical systems must be designed resilient to all kinds of malfunctions. We are especially interested by the loss of control authority over actuators. This malfunction considers actuators producing uncontrolled and poss…
Bridging Rested and Restless Bandits with Graph-Triggering: Rising and Rotting
Rested and Restless Bandits are two well-known bandit settings that are useful to model real-world sequential decision-making problems in which the expected reward of an arm evolves over time due to the actions we perfor…
Decision MakingSequential Decision Making