Timezone: »

 
Spotlight
Strategies for Safe Multi-Armed Bandits with Logarithmic Regret and Risk
Tianrui Chen · Aditya Gangrade · Venkatesh Saligrama

Thu Jul 21 12:35 PM -- 12:40 PM (PDT) @ Ballroom 3 & 4
in T: Online Learning and Bandits »

We investigate a natural but surprisingly unstudied approach to the multi-armed bandit problem under safety risk constraints. Each arm is associated with an unknown law on safety risks and rewards, and the learner's goal is to maximise reward whilst not playing unsafe arms, as determined by a given threshold on the mean risk.We formulate a pseudo-regret for this setting that enforces this safety constraint in a per-round way by softly penalising any violation, regardless of the gain in reward due to the same. This has practical relevance to scenarios such as clinical trials, where one must maintain safety for each round rather than in an aggregated sense.We describe doubly optimistic strategies for this scenario, which maintain optimistic indices for both safety risk and reward. We show that schema based on both frequentist and Bayesian indices satisfy tight gap-dependent logarithmic regret bounds, and further that these play unsafe arms only logarithmically many times in total. This theoretical analysis is complemented by simulation studies demonstrating the effectiveness of the proposed schema, and probing the domains in which their use is appropriate.

Keywords: T: Online Learning and Bandits · MISC: Online Learning, Active Learning and Bandits

Author Information

Tianrui Chen (Boston University)
Aditya Gangrade (Carnegie Mellon University)
Venkatesh Saligrama (Boston University)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors