Bandits in autoregressive Markov models

Sun, Yicheng

Permalink

https://hdl.handle.net/2142/125840 Copy

Description

Title

Bandits in autoregressive Markov models

Author(s)

Sun, Yicheng

Issue Date

2024-07-19

Director of Research (if dissertation) or Advisor (if thesis)

Katselis, Dimitrios

Department of Study

Electrical & Computer Eng

Discipline

Electrical & Computer Engr

Degree Granting Institution

University of Illinois at Urbana-Champaign

Degree Name

M.S.

Degree Level

Thesis

Keyword(s)

Bandit Algorithms

Abstract

This thesis explores algorithms used in stochastic and Markovian multi-armed bandits, along with their applications in autoregressive models with a graphical structure. It begins by introducing some background of Markov chains, including concentration properties and variations of the Chernoff bounds. The work further elucidates the setup of multi-armed bandits, emphasizing fundamental concepts such as the exploration-exploitation tradeoff and regret minimization. Established algorithms in stochastic bandits, like the Upper Confidence Bound and epsilon-Greedy are analysed as well as their adaptations for Markovian environments. The thesis then introduces binary valued proccesses with a graphical structure, such as the ALARM and the BAR models, and assesses their structural implications for bandit problems. Combining the two topics, it formulates a bandit problem based on the BAR model and applies these algorithms to minimize the regret. A comprehensive analysis of various algorithms is conducted along with experimental validations. These experiments support the theoretical assertions, showing the practical robustness and effectiveness of Markovian bandit algorithms.

Graduation Semester

2024-08

Type of Resource

Thesis

Handle URL

https://hdl.handle.net/2142/125840

Copyright and License Information

Copyright 2024 Yicheng Sun

Owning Collections