---

A Near-Optimal Play for a Discrepancy Learning Game

---

Abstract

In this article, we present a new discrepancy learning game between two players Alice and Bob. They will play on a set system from which Alice only knows the ground set at the start. She will choose colorings of the ground set and Bob chooses ranges from the set system. As Bob chooses ranges and reveals them to Alice, she learns about the set system. She wants to minimize the discrepancy of the ranges given by Bob with respect to the colorings she picks. We show that there exists a non-trivial strategy for Alice to obtain near-optimal value for the game when the set system has finite VC-dimension. Our strategy relies on the low-discrepancy algorithm of Lovett and Meka.