Multiscale Non-stationary Stochastic Bandits

• URL: http://arxiv.org/abs/2002.05289v1
• Date: Thu, 13 Feb 2020 00:24:17 GMT
• Title: Multiscale Non-stationary Stochastic Bandits
• Authors: Qin Ding, Cho-Jui Hsieh, James Sharpnack
• Abstract summary: We propose a novel multiscale changepoint detection method for the non-stationary linear bandit problems, called Multiscale-LinUCB. Experimental results show that our proposed Multiscale-LinUCB algorithm outperforms other state-of-the-art algorithms in non-stationary contextual environments.
• Score: 83.48992319018147
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Classic contextual bandit algorithms for linear models, such as LinUCB, assume that the reward distribution for an arm is modeled by a stationary linear regression. When the linear regression model is non-stationary over time, the regret of LinUCB can scale linearly with time. In this paper, we propose a novel multiscale changepoint detection method for the non-stationary linear bandit problems, called Multiscale-LinUCB, which actively adapts to the changing environment. We also provide theoretical analysis of regret bound for Multiscale-LinUCB algorithm. Experimental results show that our proposed Multiscale-LinUCB algorithm outperforms other state-of-the-art algorithms in non-stationary contextual environments.

Related papers

• Indexed Minimum Empirical Divergence-Based Algorithms for Linear Bandits [55.938644481736446]
  Indexed Minimum Empirical Divergence (IMED) is a highly effective approach to the multi-armed bandit problem. It has been observed to empirically outperform UCB-based algorithms and Thompson Sampling. We present novel linear versions of the IMED algorithm, which we call the family of LinIMED algorithms.
  arXiv  Detail & Related papers  (2024-05-24T04:11:58Z)
• An L-BFGS-B approach for linear and nonlinear system identification under $\ell_1$- and group-Lasso regularization [0.0]
  We propose a very efficient numerical method for identifying linear and nonlinear discrete-time state-space models. A Python implementation of the proposed identification method is available in the package jax-sysid.
  arXiv  Detail & Related papers  (2024-03-06T16:17:34Z)
• Efficient Interpretable Nonlinear Modeling for Multiple Time Series [5.448070998907116]
  This paper proposes an efficient nonlinear modeling approach for multiple time series. It incorporates nonlinear interactions among different time-series variables. Experimental results show that the proposed algorithm improves the identification of the support of the VAR coefficients in a parsimonious manner.
  arXiv  Detail & Related papers  (2023-09-29T11:42:59Z)
• Low-rank extended Kalman filtering for online learning of neural networks from streaming data [71.97861600347959]
  We propose an efficient online approximate Bayesian inference algorithm for estimating the parameters of a nonlinear function from a potentially non-stationary data stream. The method is based on the extended Kalman filter (EKF), but uses a novel low-rank plus diagonal decomposition of the posterior matrix. In contrast to methods based on variational inference, our method is fully deterministic, and does not require step-size tuning.
  arXiv  Detail & Related papers  (2023-05-31T03:48:49Z)
• High-Dimensional Sparse Bayesian Learning without Covariance Matrices [66.60078365202867]
  We introduce a new inference scheme that avoids explicit construction of the covariance matrix. Our approach couples a little-known diagonal estimation result from numerical linear algebra with the conjugate gradient algorithm. On several simulations, our method scales better than existing approaches in computation time and memory.
  arXiv  Detail & Related papers  (2022-02-25T16:35:26Z)
• Cogradient Descent for Dependable Learning [64.02052988844301]
  We propose a dependable learning based on Cogradient Descent (CoGD) algorithm to address the bilinear optimization problem. CoGD is introduced to solve bilinear problems when one variable is with sparsity constraint. It can also be used to decompose the association of features and weights, which further generalizes our method to better train convolutional neural networks (CNNs)
  arXiv  Detail & Related papers  (2021-06-20T04:28:20Z)
• Covariance-Free Sparse Bayesian Learning [62.24008859844098]
  We introduce a new SBL inference algorithm that avoids explicit inversions of the covariance matrix. Our method can be up to thousands of times faster than existing baselines. We showcase how our new algorithm enables SBL to tractably tackle high-dimensional signal recovery problems.
  arXiv  Detail & Related papers  (2021-05-21T16:20:07Z)
• A polynomial-time algorithm for learning nonparametric causal graphs [18.739085486953698]
  The analysis is model-free and does not assume linearity, additivity, independent noise, or faithfulness. We impose a condition on the residual variances that is closely related to previous work on linear models with equal variances.
  arXiv  Detail & Related papers  (2020-06-22T02:21:53Z)

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.