/Risk-Aware Algorithms for Adversarial Contextual Bandits

Risk-Aware Algorithms for Adversarial Contextual Bandits

Wen Sun, Debadeepta Dey and Ashish Kapoor
Tech. Report, CMU-RI-TR-16-63, Robotics Institute, Carnegie Mellon University, arXiv, October, 2016

Download Publication (PDF)

Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author’s copyright. These works may not be reposted without the explicit permission of the copyright holder.

Abstract

In this work we consider adversarial contextual bandits with risk constraints. At each round, nature prepares a context, a cost for each arm, and additionally a risk for each arm. The learner leverages the context to pull an arm and then receives the corresponding cost and risk associated with the pulled arm. In addition to minimizing the cumulative cost, the learner also needs to satisfy long-term risk constraints — the average of the cumulative risk from all pulled arms should not be larger than a pre-defined threshold. To address this problem, we first study the full information setting where in each round the learner receives an adversarial convex loss and a convex constraint. We develop a meta algorithm leveraging online mirror descent for the full information setting and extend it to contextual bandit with risk constraints setting using expert advice. Our algorithms can achieve near-optimal regret in terms of minimizing the total cost, while successfully maintaining a sublinear growth of cumulative risk constraint violation.

BibTeX Reference
@techreport{Sun-2016-5613,
author = {Wen Sun and Debadeepta Dey and Ashish Kapoor},
title = {Risk-Aware Algorithms for Adversarial Contextual Bandits},
year = {2016},
month = {October},
institution = {Carnegie Mellon University},
address = {Pittsburgh, PA},
number = {CMU-RI-TR-16-63},
}
2017-09-13T10:38:13+00:00