An Efficient Algorithm For Generalized Linear Bandit: Online Stochastic Gradient Descent and Thompson Sampling Article Swipe

MAKE IMPACT

Qin Ding , Cho‐Jui Hsieh , James Sharpnack · YOU? · · 2020 · Open Access · · DOI: https://doi.org/10.48550/arxiv.2006.04012

We consider the contextual bandit problem, where a player sequentially makes decisions based on past observations to maximize the cumulative reward. Although many algorithms have been proposed for contextual bandit, most of them rely on finding the maximum likelihood estimator at each iteration, which requires $O(t)$ time at the $t$-th iteration and are memory inefficient. A natural way to resolve this problem is to apply online stochastic gradient descent (SGD) so that the per-step time and memory complexity can be reduced to constant with respect to $t$, but a contextual bandit policy based on online SGD updates that balances exploration and exploitation has remained elusive. In this work, we show that online SGD can be applied to the generalized linear bandit problem. The proposed SGD-TS algorithm, which uses a single-step SGD update to exploit past information and uses Thompson Sampling for exploration, achieves $\tilde{O}(\sqrt{T})$ regret with the total time complexity that scales linearly in $T$ and $d$, where $T$ is the total number of rounds and $d$ is the number of features. Experimental results show that SGD-TS consistently outperforms existing algorithms on both synthetic and real datasets.

Type

preprint

Language

en

Landing Page

http://arxiv.org/abs/2006.04012

PDF

https://arxiv.org/pdf/2006.04012

OA Status

green

Cited By

8

References

31

Related Works

10

OpenAlex ID

https://openalex.org/W3034051564

Raw OpenAlex JSON

OpenAlex ID

https://openalex.org/W3034051564

Canonical identifier for this work in OpenAlex

DOI

https://doi.org/10.48550/arxiv.2006.04012

Digital Object Identifier

Title

An Efficient Algorithm For Generalized Linear Bandit: Online Stochastic Gradient Descent and Thompson Sampling

Work title

Type

preprint

OpenAlex work type

Language

en

Primary language

Publication year

2020

Year of publication

Publication date

2020-06-07

Full publication date if available

Authors

Qin Ding, Cho‐Jui Hsieh, James Sharpnack

List of authors in order

Landing page

https://arxiv.org/abs/2006.04012

Publisher landing page

PDF URL

https://arxiv.org/pdf/2006.04012

Direct link to full text PDF

Open access

Yes

Whether a free full text is available

OA status

green

Open access status per OpenAlex

OA URL

https://arxiv.org/pdf/2006.04012

Direct OA link when available

Concepts

Regret, Thompson sampling, Stochastic gradient descent, Estimator, Computer science, Constant (computer programming), Algorithm, Sampling (signal processing), Online algorithm, Streaming algorithm, Gradient descent, Tilde, Time complexity, Mathematical optimization, Mathematics, Artificial intelligence, Machine learning, Upper and lower bounds, Discrete mathematics, Statistics, Artificial neural network, Programming language, Mathematical analysis, Filter (signal processing), Computer vision

Top concepts (fields/topics) attached by OpenAlex

Cited by

8

Total citation count in OpenAlex

Citations by year (recent)

2025: 1, 2024: 3, 2023: 1, 2022: 3

Per-year citation counts (last 5 years)

References (count)

31

Number of works referenced by this work

Related works (count)

10

Other works algorithmically related by OpenAlex

Full payload