Faculty Recruiting Support CICS

Concentration Inequalities in the Wild: Case Studies in Blockchain & Reinforcement Learning

27 Aug
Thursday, 08/27/2020 11:00am to 1:00pm
Zoom Meeting
PhD Thesis Defense
Speaker: Pinar Ozisik

Zoom Meeting: https://umass-amherst.zoom.us/j/91769814744?pwd=c3o5OXA5c1ZPZDNxRXZ5NjFhdkhqdz09
Meeting ID: 917 6981 4744
Passcode: 495227

Abstract

Concentration inequalities (CIs) are a powerful tool that provide probability bounds on how a random variable deviates from its expectation. In this thesis, first I will describe a blockchain protocol that I have developed, called Graphene, which uses CIs to provide probabilistic guarantees on performance. Second, I will analyze the extent to which CIs are robust when the assumptions they require are violated, using Reinforcement Learning (RL) as the domain.

Graphene is a method for interactive set reconciliation among peers in blockchains and related distributed systems. Through the novel combination of a Bloom filter and an Invertible Bloom Lookup Table, Graphene uses a fraction of the network bandwidth used by deployed work for one- and two-way synchronization. It is a fast and implementation-independent algorithm that uses CIs for parameterizing an IBLT so that it is optimal in size for a given desired decode rate. I characterize performance improvements through analysis, detailed simulation, and deployment results for Bitcoin Cash, a prominent cryptocurrency. Implementations of Graphene, IBLTs, and the IBLT optimization algorithm are all open-source code.

Second, I analyze the extent to which existing methods rely on accurate training data for a specific class of RL algorithms, known as safe and Seldonian RL. Several Seldonian RL algorithms have a component called the safety test which use CIs to lower bound the performance of a new policy, using training data collected from another policy. I introduce a new measure of security to quantify the susceptibility to perturbations in training data, and show that a couple of Seldonian RL methods are extremely sensitive to even a few data corruptions, completely breaking the probability bounds guaranteed by CIs. I then introduce a new algorithm, called Panacea, that is more robust against data alterations, and demonstrate its usage in practice on some RL problems, including a grid-world and a diabetes treatment simulation.

Committee Members: Brian Levine, Philip Thomas, Yuriy Brun, Phillipa Gill, Nikunj Kapadia