An online learning game

Posted on: November 21st, 2013 by
Suppose $X_1(t),X_2(t),\dots X_n(t)$ are input bits (i.e. 0 or 1) at time t, and $Y(t)$ is the output bit. You are given samples for $t=1,2,3,4,\dots$. You know that $Y(t)$ is the OR (or disjunction) of a subset of $X_1(t),X_2(t),\dots X_n(t)$. For example $Y=X_1 OR X_n$, $Y=X_3 OR X_5 OR X_6$. You want to use online learning to learn the function that maps the inputs $X_1,\dots X_n$ to $Y$. At each time $t$, you will try to predict the output $Y(t)$ given the input $X_1(t),X_2(t),\dots X_n(t)$. Every time you make a mistake in your prediction, I will charge you $1. $Y(t)$ is the OR (or disjuction) of exactly $k$ values among $X_1(t)\dots X_n(t)$. I am free to choose the input samples $(X_1(t),X_2(t)\dots X_n(t)$. I will first ask you for the output $Y(t)$. If you are wrong, I will tell the correct value of $Y(t)$ and charge you$1. How will you minimize your loss if I play optimally to maximize your minimum loss? What is that minimum loss? We need the optimal online learning algorithm.