Bandits in autoregressive Markov models

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.

Name thesis:degree_name

M.S.

Level thesis:degree_level

Thesis

Discipline thesis:degree_discipline

Electrical & Computer Engr

Grantor

University of Illinois at Urbana-Champaign

Year dc:date

2024

Author dc:creator

• Sun, Yicheng

Contributors dc:contributor

• Katselis, Dimitrios

• Bandit Algorithms

Statement dc:rights

• Copyright 2024 Yicheng Sun

Language dc:language

en, eng

Handle dc:identifier

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

OAI record oai:identifier

https://www.ideals.illinois.edu/oai-pmh?verb=GetRecord&metadataPrefix=etdms&identifier=oai%3Awww.ideals.illinois.edu%3A2142%2F125840