Answers.Body: <p>The (binary) multi-armed bandit actually <em>is</em> a MDP with one state and <span class="math-container">$K$</span> actions.</p>
  <p>So your suggestion boils down to meta-learning: Find the parameters of one MDP that can solve another. Let's go with that!</p>
  <p>So we need to specify this meta-MDP. To simplify, we make it solve <em>Bernoulli</em> (binary) multi-armed Bandits.</p>
  <h2>What <em>state</em> would this meta-MDP use?</h2>
  <ul>
  <li><p><strong>The full history of actions and rewards?</strong> One state would be <code>[(A-1), (A-0), (C-0), (B-1), (B-1), (B-1)]</code>,  Clearly this has redundant information. Because the bandit is stateless, the order in which we tried the arms is irrelevant for the optimal decision about the next action (which arm to try).</p>
  </li>
  <li><p><strong>Same as above, but ignoring order?</strong> That boils down to counting. One state would be <code>{A: (1,1), B: (0,3), C: (1,0), D: (0,0)}</code>. The number of states is infinite. But if we limit ourselves to a few steps, we could totally simulate this meta-MDP.</p>
  </li>
  </ul>
  <p>If we actually wanted to optimize this meta-MDP:</p>
  <ul>
  <li>We would have to specify the distribution of Bandits we want to be optimal for.</li>
  <li>We may want to specify a time-horizon. (Or the discounting of future rewards that we want to be optimal for.)</li>
  <li>We may notice more symmetry that we haven't exploited yet: If the optimal action in the state above is A, the surely in the state where A/B are swapped it should be B.</li>
  </ul>
  <h2>Back to your question:</h2>
  <blockquote>
  <p>Why dont we consider the information we gain by exploration? I.e, why dont we model this as a MDP?</p>
  </blockquote>
  <p>We have almost done this now! We could optimize the meta-MDP above and extract the optimal policy. The optimal policy is of course a deterministic function from state to action.</p>
  <p>Let's cross-check what the <a href="https://people.maths.bris.ac.uk/%7Emaajg/teaching/stochopt/ucb.pdf" rel="nofollow noreferrer">UCB algorithm (PDF)</a> does: <em>In the first <span class="math-container">$K$</span> rounds, where <span class="math-container">$K$</span> is the number of arms, play each arm once, in arbitrary order. [...]</em></p>
  <p>Wait, this specifies what action our optimal policy should take for some of the states! If we read further, we can find the action for other states too. This is a policy!</p>
  <p>So another way to think about UCB (or Thomson Sampling, or even <span class="math-container">$\epsilon$</span>-greedy) is that they are actually specific policies/solutions for the above meta-MDP.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-09-27T07:19:50.907Z
Answers.Text: my question was not really clear, i was more getting at information state space algorithms and the value of information, i.e if we know the value of information we can trade-off exploration and exploitation optimally, see 1:09:06 https://www.youtube.com/watch?v=sGuiWX07sKw&list=PLzuuYNsE1EZAXYR4FJ75jcJseBmo4KQ9-&index=9&t=48s
Answers.UserDisplayName: hugh
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-09-27T07:20:23.807Z
Answers.Text: however, i'll accept this answer as the question was not really clear. I'll will create a new question however...
Answers.UserDisplayName: hugh
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-09-27T07:33:24.230Z
Answers.Text: new thread: https://ai.stackexchange.com/questions/42218/thompson-ucb-e-greedy-vs-information-state-space-algorithms-for-bandits
Answers.UserDisplayName: hugh
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-09-27T14:35:27.063Z
Answers.Text: The maximally greedy algorithm would always choose the action with highest expected reward. Neither UCB, nor Thompson Sampling nor even $\epsilon$-greedy (with $\epsilon > 0)$ try to be optimal for such a short time-horizon. Maybe you have a misconception there, or maybe I still don't understand your question, sorry about that :)
Answers.UserDisplayName: maxy
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-09-26T20:37:13.310Z
Answers.LastActivityDate: 2023-09-26T21:05:38.873Z
Answers.LastEditDate: 2023-09-26T21:05:38.873Z
Answers.UserDisplayName: maxy
Body: <p>When considering multi-armed bandits in different formats, UCB, <span class="math-container">$\epsilon$</span>-greedy, thompson sampling etc seems so greedy/myopic in the sense that it solely considers reward for the current timestep.</p>
  <p>To be more precise, why dont we consider the information we gain by exploration and how this will affect us in future timesteps when making future decisions. More specifically, shouldnt it be better to try to quantify the value of information from exploratory actions and model this over a longer horizon..</p>
  <p>I.e, why dont we model this as a MDP and use (approximate)dynamic programming techniques?</p>
  <p>In that sense we might see that playing arm <span class="math-container">$x$</span> now will lead us to this information, which in turn will lead to this and so on.</p>
  <p>I must have missed out on some literature/techniques.</p>
  
Tags: <reinforcement-learning><markov-decision-process><multi-armed-bandits><upper-confidence-bound><thompson-sampling>
Title: UCB, Thompson sampling etc seems myopic/greedy for bandits?
UserDisplayName: hugh
ThreadText: # UCB, Thompson sampling etc seems myopic/greedy for bandits?
  
  (Asked by: username_0 on 2023-09-25)
  
  When considering multi-armed bandits in different formats, UCB, $\epsilon$-greedy, thompson sampling etc seems so greedy/myopic in the sense that it solely considers reward for the current timestep.
  
  To be more precise, why dont we consider the information we gain by exploration and how this will affect us in future timesteps when making future decisions. More specifically, shouldnt it be better to try to quantify the value of information from exploratory actions and model this over a longer horizon..
  
  I.e, why dont we model this as a MDP and use (approximate)dynamic programming techniques?
  
  In that sense we might see that playing arm $x$ now will lead us to this information, which in turn will lead to this and so on.
  
  I must have missed out on some literature/techniques.
  
  **Tags:** reinforcement-learning, markov-decision-process, multi-armed-bandits, upper-confidence-bound, thompson-sampling
  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2023-09-26. Score: 1 | Accepted answer
  
  The (binary) multi-armed bandit actually *is* a MDP with one state and $K$ actions.
  
  So your suggestion boils down to meta-learning: Find the parameters of one MDP that can solve another. Let's go with that!
  
  So we need to specify this meta-MDP. To simplify, we make it solve *Bernoulli* (binary) multi-armed Bandits.
  
  ## What *state* would this meta-MDP use?
  
  * **The full history of actions and rewards?** One state would be `[(A-1), (A-0), (C-0), (B-1), (B-1), (B-1)]`, Clearly this has redundant information. Because the bandit is stateless, the order in which we tried the arms is irrelevant for the optimal decision about the next action (which arm to try).
  * **Same as above, but ignoring order?** That boils down to counting. One state would be `{A: (1,1), B: (0,3), C: (1,0), D: (0,0)}`. The number of states is infinite. But if we limit ourselves to a few steps, we could totally simulate this meta-MDP.
  
  If we actually wanted to optimize this meta-MDP:
  
  * We would have to specify the distribution of Bandits we want to be optimal for.
  * We may want to specify a time-horizon. (Or the discounting of future rewards that we want to be optimal for.)
  * We may notice more symmetry that we haven't exploited yet: If the optimal action in the state above is A, the surely in the state where A/B are swapped it should be B.
  
  ## Back to your question:
  
  > Why dont we consider the information we gain by exploration? I.e, why dont we model this as a MDP?
  
  We have almost done this now! We could optimize the meta-MDP above and extract the optimal policy. The optimal policy is of course a deterministic function from state to action.
  
  Let's cross-check what the [UCB algorithm (PDF)](https://people.maths.bris.ac.uk/%7Emaajg/teaching/stochopt/ucb.pdf) does: *In the first $K$ rounds, where $K$ is the number of arms, play each arm once, in arbitrary order. [...]*
  
  Wait, this specifies what action our optimal policy should take for some of the states! If we read further, we can find the action for other states too. This is a policy!
  
  So another way to think about UCB (or Thomson Sampling, or even $\epsilon$-greedy) is that they are actually specific policies/solutions for the above meta-MDP.
  
  > **Comments:**
  > **username_0**: my question was not really clear, i was more getting at information state space algorithms and the value of information, i.e if we know the value of information we can trade-off exploration and exploitation optimally, see 1:09:06 https://www.youtube.com/watch?v=sGuiWX07sKw&list=PLzuuYNsE1EZAXYR4FJ75jcJseBmo4KQ9-&index=9&t=48s  
  > **username_0**: however, i'll accept this answer as the question was not really clear. I'll will create a new question however...  
  > **username_0**: new thread: https://ai.stackexchange.com/questions/42218/thompson-ucb-e-greedy-vs-information-state-space-algorithms-for-bandits  
  > **username_1**: The maximally greedy algorithm would always choose the action with highest expected reward. Neither UCB, nor Thompson Sampling nor even $\epsilon$-greedy (with $\epsilon > 0)$ try to be optimal for such a short time-horizon. Maybe you have a misconception there, or maybe I still don't understand your question, sorry about that :)  
  
  ---
  
  