paper-with-me

홈 › Papers

Random Shuffling and Resets for the Non-stationary Stochastic Bandit Problem

2016-09-07 · Robin Allesiardo, Raphaël Féraud, Odalric-Ambrym Maillard

We consider a non-stationary formulation of the stochastic multi-armed bandit where the rewards are no longer assumed to be identically distributed. For the best-arm identification task, we introduce a version of Successive Elimination based on random shuffling of the $K$ arms. We prove that under a novel and mild assumption on the mean gap $\Delta$, this simple but powerful modification achieves the same guarantees in term of sample complexity and cumulative regret than its original version, but in a much wider class of problems, as it is not anymore constrained to stationary distributions. We also show that the original {\sc Successive Elimination} fails to have controlled regret in this more general scenario, thus showing the benefit of shuffling. We then remove our mild assumption and adapt the algorithm to the best-arm identification task with switching arms. We adapt the definition of the sample complexity for that case and prove that, against an optimal policy with $N-1$ switches of the optimal arm, this new algorithm achieves an expected sample complexity of $O(\Delta^{-2}\sqrt{NK\delta^{-1} \log(K \delta^{-1})})$, where $\delta$ is the probability of failure of the algorithm, and an expected cumulative regret of $O(\Delta^{-1}{\sqrt{NTK \log (TK)}})$ after $T$ time steps.

📄 PDF Abstract BibTeX arXiv:1609.02139

Code (0)

등록된 구현이 없습니다.

Similar Papers 제목 키워드 기반

Fat Tails and Black Swans: Exact Results for Multiplicative Processes with Resets

2021-05-25 · Damián H. Zanette, Susanna Manrubia

We consider a class of multiplicative processes which, added with stochastic reset events, give origin to stationary distributions with power-law tails -- ubiquitous in the statistics of social, economic, and ecological …

Computing the Variance of Shuffling Stochastic Gradient Algorithms via Power Spectral Density Analysis

2022-06-01 · Carles Domingo-Enrich

When solving finite-sum minimization problems, two common alternatives to stochastic gradient descent (SGD) with theoretical benefits are random reshuffling (SGD-RR) and shuffle-once (SGD-SO), in which functions are samp…

Random Reshuffling for Stochastic Gradient Langevin Dynamics

2025-01-27 · Luke Shaw, Peter A. Whalley

We examine the use of different randomisation policies for stochastic gradient algorithms used in sampling, based on first-order (or overdamped) Langevin dynamics, the most popular of which is known as Stochastic Gradien…

Kolmogorov-Smirnov Test-Based Actively-Adaptive Thompson Sampling for Non-Stationary Bandits

2021-05-30 · Gourab Ghatak, Hardhik Mohanty, Aniq Ur Rahman

We consider the non-stationary multi-armed bandit (MAB) framework and propose a Kolmogorov-Smirnov (KS) test based Thompson Sampling (TS) algorithm named TS-KS, that actively detects change points and resets the TS param…

Edge-computingPortfolio OptimizationThompson Sampling

High Probability Guarantees for Random Reshuffling

2023-11-20 · Hengxu Yu, Xiao Li

We consider the stochastic gradient method with random reshuffling ($\mathsf{RR}$) for tackling smooth nonconvex optimization problems. $\mathsf{RR}$ finds broad applications in practice, notably in training neural netwo…