An Adaptive Method for Contextual Stochastic Multi-armed Bandits with Rewards Generated by a Linear Dynamical System
Online decision-making can be formulated as the popular stochastic multi-armed bandit problem where a learner makes decisions (or takes actions) to maximize cumulative rewards collected from an unknown environment. This paper proposes to model a stochastic multi-armed bandit as an unknown linear Gaussian dynamical system, as many applications, such as bandits for dynamic pricing problems or hyperparameter selection for machine learning models, can benefit from this perspective. Following this approach, we can build a matrix representation of the system's steady-state Kalman filter that takes a set of previously collected observations from a time interval of length $s$ to predict the next reward that will be returned for each action. This paper proposes a solution in which the parameter $s$ is determined via an adaptive algorithm by analyzing the model uncertainty of the matrix representation. This algorithm helps the learner adaptively adjust its model size and its length of exploration based on the uncertainty of its environmental model. The effectiveness of the proposed scheme is demonstrated through extensive numerical studies, revealing that the proposed scheme is capable of increasing the rate of collected cumulative rewards.
Code (0)
등록된 구현이 없습니다.
Tasks
Multi-Armed BanditsMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
OSOM: A simultaneously optimal algorithm for multi-armed and linear contextual bandits
We consider the stochastic linear (multi-armed) contextual bandit problem with the possibility of hidden simple multi-armed bandit structure in which the rewards are independent of the contextual information. Algorithms …
Multi-Armed BanditsA Survey on Contextual Multi-armed Bandits
In this survey we cover a few stochastic and adversarial contextual bandit algorithms. We analyze each algorithm's assumption and regret bound.
Multi-Armed BanditsSurveyBatched Multi-armed Bandits Problem
In this paper, we study the multi-armed bandit problem in the batched setting where the employed policy must split data into a small number of batches. While the minimax regret for the two-armed stochastic bandits has be…
Multi-Armed BanditsThompson Sampling for Contextual Bandits with Linear Payoffs
Thompson Sampling is one of the oldest heuristics for multi-armed bandit problems. It is a randomized algorithm based on Bayesian ideas, and has recently generated significant interest after several studies demonstrated …
Multi-Armed BanditsThompson SamplingAdapting multi-armed bandits policies to contextual bandits scenarios
This work explores adaptations of successful multi-armed bandits policies to the online contextual bandits scenario with binary rewards using binary classification algorithms such as logistic regression as black-box orac…
Binary ClassificationClassificationGeneral ClassificationMulti-Armed Bandits+2