Editing Waiting:Sample Complexity for Streaming Multi-Armed Bandit and Coin Tossing
Warning: You are not logged in. Your IP address will be publicly visible if you make any edits. If you log in or create an account, your edits will be attributed to your username, along with other benefits.
The edit can be undone.
Please check the comparison below to verify that this is what you want to do, and then save the changes below to finish undoing the edit.
Latest revision | Your text | ||
Line 9: | Line 9: | ||
and compare the empirical biases, and a stored coin can be discarded at any point. However, once a coin is discarded, it is lost forever and cannot be further tossed or even retrieved. The sample complexity is defined as the total number of coin tosses, and the space complexity is defined as the maximum number of coins an algorithm ever stores. | and compare the empirical biases, and a stored coin can be discarded at any point. However, once a coin is discarded, it is lost forever and cannot be further tossed or even retrieved. The sample complexity is defined as the total number of coin tosses, and the space complexity is defined as the maximum number of coins an algorithm ever stores. | ||
β | Denote $\boldsymbol{H}_{1}:=\frac{n}{\Delta^2_{[2]}}$. It is known that given the parameter $\Delta_{[2]}$ (the gap between the most and second-most biased coins), in a single pass over the stream, one can (with high constant probability) find the most biased coin with a sample complexity of $O(\boldsymbol{H}_{1})$ and a space complexity of ''a single'' coin | + | Denote $\boldsymbol{H}_{1}:=\frac{n}{\Delta^2_{[2]}}$. It is known that given the parameter $\Delta_{[2]}$ (the gap between the most and second-most biased coins), in a single pass over the stream, one can (with high constant probability) find the most biased coin with a sample complexity of $O(\boldsymbol{H}_{1})$ and a space complexity of ''a single'' coin (Assadi and Wang [STOC'20]). The sample complexity matches the worst-case lower bound for any algorithm even under the RAM setting (i.e., with a memory of $n$ coins) (Mannor and Tsitsiklis [COLT'04]). That is to say, for the $\boldsymbol{H}_{1}$ sample complexity, there is ''no sample-space tradeoff''. |
An interesting variant of the problem is the `instance-sensitive' sample complexity, defined as | An interesting variant of the problem is the `instance-sensitive' sample complexity, defined as | ||
Line 15: | Line 15: | ||
\boldsymbol{H}_{2}:= \sum_{i=2}^{n}\frac{1}{\Delta^2_{[i]}} \log\log(\frac{1}{\Delta_{[i]}}), | \boldsymbol{H}_{2}:= \sum_{i=2}^{n}\frac{1}{\Delta^2_{[i]}} \log\log(\frac{1}{\Delta_{[i]}}), | ||
$$ | $$ | ||
β | where $\Delta_{[i]}$ is the gap between the most biased and the $i$-th most biased coins. It is known that the $O(\boldsymbol{H}_{2})$ sample complexity can be achieved under the RAM setting even without the knowledge of $\Delta_{[2]}$. Note that this does not contradict the worst-case lower bound by | + | where $\Delta_{[i]}$ is the gap between the most biased and the $i$-th most biased coins. It is known that the $O(\boldsymbol{H}_{2})$ sample complexity can be achieved under the RAM setting even without the knowledge of $\Delta_{[2]}$. Note that this does not contradict the worst-case lower bound by (Mannor and Tsitsiklis [COLT'04]), as $O(\boldsymbol{H}_{2})$ becomes close to $O(\frac{n}{\Delta^2_{[2]}})$ when all the sub-optimal coins share the same bias (i.e., $\Delta_{[i]}=\Delta_{[2]}$, $\forall i\geq 2$). |
For the O($\boldsymbol{H}_{2}$) sample complexity, the sample-space tradeoff begins to emerge under the streaming coin tossing model. The following hardness results are known for single-pass streaming algorithms (to find the most biased coin with high constant probability). Consider the following assumptions: '''a). the knowledge of $\Delta_{[2]}$'''; '''b). the random arrival of coins'''; and '''c). an estimation of $\boldsymbol{H}_{2}$'''. No algorithm with a space of $o(n)$ coins can achieve the O($\boldsymbol{H}_{2}$) sample complexity given '''(a). and b).)''' or '''( a). and c). )'''. | For the O($\boldsymbol{H}_{2}$) sample complexity, the sample-space tradeoff begins to emerge under the streaming coin tossing model. The following hardness results are known for single-pass streaming algorithms (to find the most biased coin with high constant probability). Consider the following assumptions: '''a). the knowledge of $\Delta_{[2]}$'''; '''b). the random arrival of coins'''; and '''c). an estimation of $\boldsymbol{H}_{2}$'''. No algorithm with a space of $o(n)$ coins can achieve the O($\boldsymbol{H}_{2}$) sample complexity given '''(a). and b).)''' or '''( a). and c). )'''. | ||
β | On the other hand, if we are allowed to make multiple passes over the stream, the $O(\boldsymbol{H}_{2})$ sample complexity can be achieved. In particular, if we can make $O(\log(\frac{1}{\Delta_{[2]}}))$ passes, it is able to find the most biased coin with the $O(\boldsymbol{H}_{2})$ sample complexity and a space of a single coin | + | On the other hand, if we are allowed to make multiple passes over the stream, the $O(\boldsymbol{H}_{2})$ sample complexity can be achieved. In particular, if we can make $O(\log(\frac{1}{\Delta_{[2]}}))$ passes, it is able to find the most biased coin with the $O(\boldsymbol{H}_{2})$ sample complexity and a space of a single coin (Jin et al. [ICML'21]) even without the knowledge of $\Delta_{[2]}$. Note that this is a very strong dichotomy between the single-pass scenario, as one can show that if $\Delta_{[2]}$ is not given in a single pass, the sample complexity goes ''unbounded'' for an algorithm with $o(n)$-coin space. |
Based on the above context, the interesting open question is as follows: what is the tight number of passes (i.e. algorithms and lower bounds) for a streaming algorithm with $o(n)$-coin space to achieve the O($\boldsymbol{H}_{2}$) sample complexity? | Based on the above context, the interesting open question is as follows: what is the tight number of passes (i.e. algorithms and lower bounds) for a streaming algorithm with $o(n)$-coin space to achieve the O($\boldsymbol{H}_{2}$) sample complexity? |