Robust sequential decision-making on networks

In this thesis, I consider the research problem of designing optimal algorithms for two specific settings of the stochastic multi-armed bandit problem. The first setting considers the problem where rewards are drawn from a family of extremely heavy-tailed distributions known as a-stable distributions. For this setting, I extended an existing upper confidence bound algorithm, to create an optimal frequentist algorithm, titled [alpha]-UCB. Next, I developed a variant of the Bayesian Thompson Sampling algorithm in this setting, titled Robust [alpha]-TS, which involved developing an efficient pipeline for posterior inference. I also proved finite-time regret bounds for this algorithm, that are optimal up to logarithmic factors. The second problem setting I considered was the networked multi-agent problem where agents have local communication, and have unique preferences. This problem setting is a generalization of the co-operative multi-agent stochastic bandit problem, and is a closely related variant of the single-agent bandit setting with side observations. For this setting, I developed an optimal upper confidence bound algorithm, titled Net-UCB. I also proved finite-time regret bounds for this algorithm that are logarithmic in the number of rounds, and are sub-linear in the number of agents. For both settings, I conducted extensive experiments to verify the tightness of the regret bounds established, and compare performance with existing state-of-the-art algorithms. The algorithms proposed in this thesis obtain competitive regret and state-of-the-art performance across a variety of problem settings.

Name thesis:degree_name

Master

Department dc:contributor.department

Program in Media Arts and Sciences (Massachusetts Institute of Technology)

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2019

Author dc:creator

• Dubey, Abhimanyu.

Advisor dc:contributor.advisor

• Alex P. Pentland.

• Program in Media Arts and Sciences

Statement dc:rights

• MIT theses are protected by copyright. They may be viewed, downloaded, or printed from this source but further reproduction or distribution in any format is prohibited without written permission.

Licence dc:rights.uri

• http://dspace.mit.edu/handle/1721.1/7582

Language dc:language.iso

eng

Handle dc:identifier.uri

https://hdl.handle.net/1721.1/123636

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/123636