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

• URL: http://arxiv.org/abs/2105.14586v1
• Date: Sun, 30 May 2021 17:28:41 GMT
• Title: Kolmogorov-Smirnov Test-Based Actively-Adaptive Thompson Sampling for Non-Stationary Bandits
• Authors: Gourab Ghatak, Hardhik Mohanty, Aniq Ur Rahman
• Abstract summary: 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. In particular, for the two-armed bandit case, we derive bounds on the number of samples of the reward distribution to detect the change once it occurs. Our results show that the proposed TS-KS algorithm outperforms not only the static TS algorithm but also it performs better than other bandit algorithms designed for non-stationary environments.
• Score: 2.879036956042183
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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 parameters once a change is detected. In particular, for the two-armed bandit case, we derive bounds on the number of samples of the reward distribution to detect the change once it occurs. Consequently, we show that the proposed algorithm has sub-linear regret. Contrary to existing works, our algorithm is able to detect a change when the underlying reward distribution changes even though the mean reward remains the same. Finally, to test the efficacy of the proposed algorithm, we employ it in two case-studies: i) task-offloading scenario in wireless edge-computing, and ii) portfolio optimization. Our results show that the proposed TS-KS algorithm outperforms not only the static TS algorithm but also it performs better than other bandit algorithms designed for non-stationary environments. Moreover, the performance of TS-KS is at par with the state-of-the-art forecasting algorithms such as Facebook-PROPHET and ARIMA.

Related papers

• Thompson Sampling-like Algorithms for Stochastic Rising Bandits [20.143361197609934]
  Rising rested bandit (SRRB) is a setting where the arms' expected rewards increase as they are pulled.<n>This work provides novel regret analyses for such algorithms in SRRBs, highlighting the challenges and providing new technical tools of independent interest.
  arXiv  Detail & Related papers  (2025-05-17T17:19:07Z)
• A Batch Sequential Halving Algorithm without Performance Degradation [0.8283940114367677]
  We show that a simple Sequential batch algorithm does not degrade the performance under practical conditions. We empirically validate our claim through experiments, demonstrating the robust nature of the algorithm in fixed-size batch settings.
  arXiv  Detail & Related papers  (2024-06-01T12:41:50Z)
• Variance-Dependent Regret Bounds for Non-stationary Linear Bandits [52.872628573907434]
  We propose algorithms that utilize the variance of the reward distribution as well as the $B_K$, and show that they can achieve tighter regret upper bounds. We introduce two novel algorithms: Restarted Weighted$textOFUL+$ and Restarted $textSAVE+$. Notably, when the total variance $V_K$ is much smaller than $K$, our algorithms outperform previous state-of-the-art results on non-stationary linear bandits under different settings.
  arXiv  Detail & Related papers  (2024-03-15T23:36:55Z)
• VITS : Variational Inference Thompson Sampling for contextual bandits [10.028119153832346]
  We introduce and analyze a variant of the Thompson sampling (TS) algorithm for contextual bandits. We propose a new algorithm, Varational Inference Thompson sampling VITS, based on Gaussian Variational Inference. We show that VITS achieves a sub-linear regret bound of the same order in the dimension and number of round as traditional TS for linear contextual bandit.
  arXiv  Detail & Related papers  (2023-07-19T17:53:22Z)
• Langevin Monte Carlo for Contextual Bandits [72.00524614312002]
  Langevin Monte Carlo Thompson Sampling (LMC-TS) is proposed to directly sample from the posterior distribution in contextual bandits. We prove that the proposed algorithm achieves the same sublinear regret bound as the best Thompson sampling algorithms for a special case of contextual bandits.
  arXiv  Detail & Related papers  (2022-06-22T17:58:23Z)
• Regret Bounds for Expected Improvement Algorithms in Gaussian Process Bandit Optimization [63.8557841188626]
  The expected improvement (EI) algorithm is one of the most popular strategies for optimization under uncertainty. We propose a variant of EI with a standard incumbent defined via the GP predictive mean. We show that our algorithm converges, and achieves a cumulative regret bound of $mathcal O(gamma_TsqrtT)$.
  arXiv  Detail & Related papers  (2022-03-15T13:17:53Z)
• Algorithms for Adaptive Experiments that Trade-off Statistical Analysis with Reward: Combining Uniform Random Assignment and Reward Maximization [50.725191156128645]
  Multi-armed bandit algorithms like Thompson Sampling can be used to conduct adaptive experiments. We present simulations for 2-arm experiments that explore two algorithms that combine the benefits of uniform randomization for statistical analysis.
  arXiv  Detail & Related papers  (2021-12-15T22:11:58Z)
• Extreme Bandits using Robust Statistics [12.6543086847761]
  We consider a multi-armed bandit problem motivated by situations where only the extreme values, as opposed to expected values in the classical bandit setting, are of interest. We propose distribution free algorithms using robust statistics and characterize the statistical properties.
  arXiv  Detail & Related papers  (2021-09-09T17:24:15Z)
• A Unifying Theory of Thompson Sampling for Continuous Risk-Averse Bandits [91.3755431537592]
  This paper unifies the analysis of risk-averse Thompson sampling algorithms for the multi-armed bandit problem. Using the contraction principle in the theory of large deviations, we prove novel concentration bounds for continuous risk functionals. We show that a wide class of risk functionals as well as "nice" functions of them satisfy the continuity condition.
  arXiv  Detail & Related papers  (2021-08-25T17:09:01Z)
• Batched Thompson Sampling for Multi-Armed Bandits [9.467098519620263]
  We study Thompson Sampling algorithms for multi-armed bandits in the batched setting. We propose two algorithms and demonstrate their effectiveness by experiments on both synthetic and real datasets.
  arXiv  Detail & Related papers  (2021-08-15T20:47:46Z)
• A Change-Detection Based Thompson Sampling Framework for Non-Stationary Bandits [7.012710335689297]
  We consider a non-stationary two-armed bandit framework and propose a change-detection based Thompson sampling algorithm. The proposed strategy compares the empirical mean of the recent rewards of an arm with the estimate of the mean of the rewards from its history. We validate the efficacy of TS-CD by testing it for edge-control of radio access technique (RAT)-selection in a wireless network.
  arXiv  Detail & Related papers  (2020-09-06T18:12:25Z)
• Analysis and Design of Thompson Sampling for Stochastic Partial Monitoring [91.22679787578438]
  We present a novel Thompson-sampling-based algorithm for partial monitoring. We prove that the new algorithm achieves the logarithmic problem-dependent expected pseudo-regret $mathrmO(log T)$ for a linearized variant of the problem with local observability.
  arXiv  Detail & Related papers  (2020-06-17T05:48:33Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.