Find results with:

Add another field

Search by date

to

Searching collections:

Dartmouth Dissertations

Add or remove collections

Home Dartmouth Dissertations house2012 1

Reference URL

To link to the entire object, paste this link in email, IM or document

To embed the entire object, paste this HTML in website

To link to this page, paste this link in email, IM or document

To embed this page, paste this HTML in website

Game-theoretic approaches for adversarial multi-armed bandit scenarios.

you wish to report:

Your comment:

Your Name:

Submit

Cancel

...

Back to top

Powered by CONTENTdm®

Author	House, James Thomas
Title	Game-theoretic approaches for adversarial multi-armed bandit scenarios.
Date	2012
Abstract	We pose several adversarial variants of the multi-armed bandit scenario and propose new approaches for their play and analysis. Our casino patron seeks to discover information about an unknown system as a means to long-term payoff -- exploration enabling exploitation. Our casino owner, who as the administrator and guardian of such a system understands its characteristics thoroughly, seeks to deny him this payoff. We describe two complete, start-to-finish approaches, one for each side of an adversarial bandit scenario. For the casino owner we give an HMM-based algorithm which is able to learn and exploit weaknesses in a broad class of behaviors and games, while remaining safely constrained within a small distance from optimal Nash play. Our main contribution is a novel approach for the casino patron making use of the recent work by Candes and Recht on the matrix completion problem. We demonstrate that the algorithm we design is able to converge to optimal Nash play in very short order, even in the worst-case scenarios we generated. Additionally, it approaches Nash play in a safe manner -- in a fashion that permits little or no adaptation by the opponent. To the best of our knowledge, our bandit algorithm represents the first application of matrix completion to multi-armed bandit scenarios. The use of such an approach enables a very quick convergence to optimal behavior, even in the most difficult scenarios -- and in many real-world cases, where the matrix reconstruction is at its best, this convergence is faster still.
Description	xviii, 180 leaves : illustrations
Format	application/pdf
Advisor	Cybenko, George V. ; Chin, Sang ; Santos, Eugene ; Borsuk, Mark
College	Thayer School of Engineering.
Issuing Body	Dartmouth Dissertations are made available through the Dartmouth Digital Library.
Degree	Thesis (Ph.D)--Dartmouth College.
Copyright	In Copyright. This material is protected by copyright and/or related rights. You are free to use this material in any way that is permitted by copyright law that applies to your use. For other uses, you need to obtain permission from the rights-holder(s). http://rightsstatements.org/page/InC/1.0/
DOI	https://doi.org/10.1349/ddlp.3525

Title	house2012 1
Full Text	Game-Theoretic Approaches for Adversarial Multi-Armed Bandit Scenarios A Thesis Submitted to the Faculty in partial fulfillment of the requirements for the degree of Doctor of Philosophy by James Thomas House Thayer School of Engineering Dartmouth College Hanover, New Hampshire August 2012

Find results with:

Searching collections:

Home Dartmouth Dissertations house2012 1

Game-theoretic approaches for adversarial multi-armed bandit scenarios.

Object Description

Description

Game-theoretic approaches for adversarial multi-armed...

Game-theoretic approaches for adversarial multi-armed...

	All
	Pages Enter page numbers or page ranges separated by commas. For example: 1,3,5-12