Rising Rested Bandits: Lower Bounds and Efficient Algorithms

2024/11/06 by Marco Fiandri, Fiandri, Marco, Alberto Maria Metelli +2
Decision Sciences · Computer Science · Engineering · #Advanced Bandit Algorithms Research #Cognitive Radio Networks and Spectrum Sensing #Advanced Wireless Network Optimization

paper · pdf · doi:10.48550/arxiv.2411.14446

Abstract

This paper is in the field of stochastic Multi-Armed Bandits (MABs), i.e. those sequential selection techniques able to learn online using only the feedback given by the chosen option (a.k.a. arm). We study a particular case of the rested bandits in which the arms' expected reward is monotonically non-decreasing and concave. We study the inherent sample complexity of the regret minimization problem by deriving suitable regret lower bounds. Then, we design an algorithm for the rested case R-ed-UCB, providing a regret bound depending on the properties of the instance and, under certain circumstances, of \widetildeO(T^(2)/(3)). We empirically compare our algorithms with state-of-the-art methods for non-stationary MABs over several synthetically generated tasks and an online model selection problem for a real-world dataset

Related

• Online Learning and Bandits with Queried Hints
• Sparse Stochastic Bandits
• Thompson Sampling-like Algorithms for Stochastic Rising Bandits
• Online Model Selection: a Rested Bandit Formulation
• Regret Bound Balancing and Elimination for Model Selection in Bandits\n and RL