Editing Waiting:Sample Complexity for Streaming Multi-Armed Bandit and Coin Tossing

Jump to: navigation, search

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 {{cite|AssadiW-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) {{cite|MannorT-04}}. That is to say, for the $\boldsymbol{H}_{1}$ sample complexity, there is ''no sample-space tradeoff''.
+
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 {{cite|MannorT-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$).
+
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 {{cite|JinHTX-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.
+
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?

Please note that all contributions to Open Problems in Sublinear Algorithms may be edited, altered, or removed by other contributors. If you do not want your writing to be edited mercilessly, then do not submit it here.
You are also promising us that you wrote this yourself, or copied it from a public domain or similar free resource (see Open Problems in Sublinear Algorithms:Copyrights for details). Do not submit copyrighted work without permission!

To edit this page, please answer the question that appears below (more info):

Cancel Editing help (opens in new window)