Answers.Body: <p>Without any knowledge on the references you came across, I am assuming that the authors were considering common applications of MAB (planning, online learning, etc.) for which the time horizon is usually small. In such applications, we usually cannot afford a large average regret which is inevitable for standard MAB algorithms due to the <span class="math-container">$\sqrt{|K|}$</span> factor.</p>
  <p>Depending on the application or additional constraints you can impose on your problem, there are several works that consider structured stochastic MABs in which there are much better guarantees than the pessimistic <span class="math-container">$\sqrt{K}$</span> bounds. One variant of structured MABs is learning on graphs [1], where one can obtain regret bounds growing with <span class="math-container">$\sqrt{\beta(G)}$</span>, where <span class="math-container">$\beta(G)$</span> is the independence number of a graph <span class="math-container">$G$</span>.</p>
  <p>[1] F. Liu, Z. Zheng, N. Shroff, &quot;Analysis of Thompson Sampling for Graphical Bandits Without the Graphs&quot;, ArXiv. 2018.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-12-18T08:56:05.473Z
Answers.Text: I appreciate the reply and the reference to the paper. Sincere thank you for this one. However, in the above problem, the time horizon may also be very large: "In the case of the pizza machine, several days of computation time are available to determine the best pizza, so the number of itarations is allowed to be very large as well."
Answers.UserDisplayName: D. B.
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-12-19T09:18:07.943Z
Answers.Text: Isn't the problem resolved then? Either (1) run a standard MAB algorithm for a long time and you will find the best pizza or if the large number of actions is still an issue, (2) model similar toppings (e.g. sausage and Italian sausage) as "neighbors" and run a graphical MAB algorithm as in [1].
Answers.UserDisplayName: rhdxor
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-12-18T05:14:27.740Z
Answers.LastActivityDate: 2020-12-18T05:14:27.740Z
Answers.UserDisplayName: rhdxor
Body: <p>I'm dealing with a (stochastic) Multi Armed Bandit (MAB) with a large number of arms.</p>
  <p>Consider a pizza machine that produces a pizza depending on an input <span class="math-container">$i$</span> (equivalent to an arm). The (finite) set of arms <span class="math-container">$K$</span> is given by <span class="math-container">$K=X_1\times X_2 \times X_3\times X_4$</span> where <span class="math-container">$X_j$</span> denote the set of possible amounts of ingredient <span class="math-container">$j$</span>.</p>
  <p>e.g.
  <span class="math-container">$X_1=\{$</span> small, medium, large <span class="math-container">$\}$</span> (amount of cheese) or
  <span class="math-container">$X_2=\{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10\}$</span> (slices of salami)</p>
  <p>Thus, running the pizza machine with input <span class="math-container">$i$</span> is equivalent to pulling arm <span class="math-container">$i\in K$</span>. Due to the different permutations, the number of arms <span class="math-container">$|K|$</span> is very large (between 100,000 and 1,000,000). Depending on the pulled arm <span class="math-container">$i$</span>, the machine generates a pizza (associated with a reward that indicates how delicious the pizza is).
  However, the machine's rewards are non-static. Pulling an arm <span class="math-container">$i$</span> generates a reward according to an unknown (arm specific) distribution <span class="math-container">$P_i$</span>, with all rewards drawn from <span class="math-container">$P_i$</span> beeing i.i.d.. In addition, it is possible to normalize all rewards to the interval [0,1].</p>
  <p>The above problem corresponds to the standard problem of a stochastic MAB, but is characterized by the large number of arms. In the case of the pizza machine, several days of computation time are available to determine the best pizza, so the number of itarations is allowed to be large as well.</p>
  <p>In my investigation of MAB algorithms addressing a large number of arms, I came across studies that could call up to a few thousand arms.</p>
  <p>Are there algorithms that exist in the MAB domain, which specifically deal with large problem instances (e.g.with <span class="math-container">$|K|&gt;100,000$</span>)?</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-12-17T01:54:13.340Z
Comments.Text: I'm not an expert on MAB so I don't know off the top of my head, but this dissertation (http://file:///tmp/mozilla_kevin0/Xu_cornellgrad_0058F_11968.pdf) might be interesting for  you. Section 2 has a literature review of MAB with many arms, and Section 3 has a literature review of MAB with memory constraints. The papers referenced by these sections would be a good place to start. If you end up finding an answer, would appreciate if you answer your own post, as I would be interested in learning more as well!
Comments.UserDisplayName: user3667125
Tags: <reinforcement-learning><multi-armed-bandits><epsilon-greedy-policy><upper-confidence-bound>
Title: Multi Armed Bandits with large number of arms
UserDisplayName: D. B.
ThreadText: # Multi Armed Bandits with large number of arms
  
  (Asked by: username_0 on 2020-12-16)
  
  I'm dealing with a (stochastic) Multi Armed Bandit (MAB) with a large number of arms.
  
  Consider a pizza machine that produces a pizza depending on an input $i$ (equivalent to an arm). The (finite) set of arms $K$ is given by $K=X\_1\times X\_2 \times X\_3\times X\_4$ where $X\_j$ denote the set of possible amounts of ingredient $j$.
  
  e.g.
  $X\_1=\{$ small, medium, large $\}$ (amount of cheese) or
  $X\_2=\{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10\}$ (slices of salami)
  
  Thus, running the pizza machine with input $i$ is equivalent to pulling arm $i\in K$. Due to the different permutations, the number of arms $|K|$ is very large (between 100,000 and 1,000,000). Depending on the pulled arm $i$, the machine generates a pizza (associated with a reward that indicates how delicious the pizza is).
  However, the machine's rewards are non-static. Pulling an arm $i$ generates a reward according to an unknown (arm specific) distribution $P\_i$, with all rewards drawn from $P\_i$ beeing i.i.d.. In addition, it is possible to normalize all rewards to the interval [0,1].
  
  The above problem corresponds to the standard problem of a stochastic MAB, but is characterized by the large number of arms. In the case of the pizza machine, several days of computation time are available to determine the best pizza, so the number of itarations is allowed to be large as well.
  
  In my investigation of MAB algorithms addressing a large number of arms, I came across studies that could call up to a few thousand arms.
  
  Are there algorithms that exist in the MAB domain, which specifically deal with large problem instances (e.g.with $|K|>100,000$)?
  
  **Tags:** reinforcement-learning, multi-armed-bandits, epsilon-greedy-policy, upper-confidence-bound
  
  > **Comments:**
  > **username_1**: I'm not an expert on MAB so I don't know off the top of my head, but this dissertation (http://file:///tmp/mozilla_kevin0/Xu_cornellgrad_0058F_11968.pdf) might be interesting for  you. Section 2 has a literature review of MAB with many arms, and Section 3 has a literature review of MAB with memory constraints. The papers referenced by these sections would be a good place to start. If you end up finding an answer, would appreciate if you answer your own post, as I would be interested in learning more as well!  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_2 on 2020-12-18. Score: 1
  
  Without any knowledge on the references you came across, I am assuming that the authors were considering common applications of MAB (planning, online learning, etc.) for which the time horizon is usually small. In such applications, we usually cannot afford a large average regret which is inevitable for standard MAB algorithms due to the $\sqrt{|K|}$ factor.
  
  Depending on the application or additional constraints you can impose on your problem, there are several works that consider structured stochastic MABs in which there are much better guarantees than the pessimistic $\sqrt{K}$ bounds. One variant of structured MABs is learning on graphs [1], where one can obtain regret bounds growing with $\sqrt{\beta(G)}$, where $\beta(G)$ is the independence number of a graph $G$.
  
  [1] F. Liu, Z. Zheng, N. Shroff, "Analysis of Thompson Sampling for Graphical Bandits Without the Graphs", ArXiv. 2018.
  
  > **Comments:**
  > **username_0**: I appreciate the reply and the reference to the paper. Sincere thank you for this one. However, in the above problem, the time horizon may also be very large: "In the case of the pizza machine, several days of computation time are available to determine the best pizza, so the number of itarations is allowed to be very large as well."  
  > **username_2**: Isn't the problem resolved then? Either (1) run a standard MAB algorithm for a long time and you will find the best pizza or if the large number of actions is still an issue, (2) model similar toppings (e.g. sausage and Italian sausage) as "neighbors" and run a graphical MAB algorithm as in [1].  
  
  ---
  
  