Pseudodeterminism — Between Randomized and Deterministism

We study the class of Pseudodeterministic algorithms, which lie between randomized and deterministic algorithms. A pseudodeterministic algorithm is a randomized algorithm that, despite using random bits, outputs a single canonical value with high probability. We also introduce Representation Oblivious algorithms: given an equivalence relation specific to the problem, all equivalent inputs produce the same output distribution. For the task of estimating the number of unique elements in a stream over {1,...,n}, we show that representation oblivious pseudodeterministic algorithms must require at $\Omega(n)$ space. For estimating the number of unique elements, two streams are equivalent if the set of unique elements is the same for both streams.

We shall also be studying a weakened version of pseudodeterministic algorithms in the case of Multi-Armed Bandits (MAB).  For an MAB algorithm A, we say A is k-list replicable if there exists a set of traces L of size at most k, so that with high probability A plays some trace from L; k is said to be the list size of A. Here, a trace means a sequence of arms played during an execution. We exhibit near-optimal regret algorithms with a list size O(k) and also prove that achieving a list size of < k is impossible without suffering a regret linear in the horizon.

Committee: Pavan Aduri (major professor), Soma Chaudhuri, Samik Basu (substitute for Oliver Eulenstein), Jack Lutz, and Kristin-Yvonne Rozier