Answers.Body: <p>MAB is fundamentally different from MDP problem, which so-called well-known RL algorithms trying to solve. The point is that MAB's policy is exactly the action. The Q function takes only action(policy) <span class="math-container">$a$</span> as its input. Whereas in MDP, the policy is a function, The Q function takes not only state-action <span class="math-container">$s,a$</span> but also policy parameter <span class="math-container">$\theta$</span>, which makes evaluation of policy and improvement of policy tangled together.</p>
  <p>In other words, in MAB, if one has good evaluation of a policy(action), then optimal policy is directly given. But in MDP, if one has good evaluation of a policy, the optimal policy is still unclear. That is why one needs DQN to do policy Evaluation and policy Improvement together.</p>
  <p>As for policy gradient policy like PPO, it takes another road to directly optimize the polciy to a more-promising gradient direction based on the feedback from reward.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-12-25T08:25:57.337Z
Answers.LastActivityDate: 2023-12-25T08:25:57.337Z
Answers.UserDisplayName: zhixin
Answers.Body: <p>You should start with the general definition of <a href="https://en.wikipedia.org/wiki/Reinforcement_learning" rel="noreferrer">Reinforcement Learning</a> problem. And what <a href="https://en.wikipedia.org/wiki/Markov_decision_process" rel="noreferrer">Markov Decision Process</a> is.</p>
  <p>DQN, A3C, PPO and REINFORCE are algorithms for solving reinforcement learning problems. These algorithms have their strengths and weaknesses depending on the details of the underlying problem.</p>
  <p><a href="https://en.wikipedia.org/wiki/Multi-armed_bandit" rel="noreferrer">Multi-Armed Bandit</a> is not even an algorithm - it is a subclass of reinforcement learning problems, where your environment (usually) doesn't have any state transitions and your actions are just a single choice from (usually) fixed and finite set of choices.</p>
  <p>Multi-Armed Bandit is used as an introductory problem to reinforcement learning, because it illustrates some basic concepts in the field: exploration-exploitation tradeoff, policy, target an estimate, learning rate and gradient optimization. All these concepts are basic vocabulary in RL. I recommend reading (and, very importantly, doing all the exercises) the <a href="http://incompleteideas.net/book/the-book.html" rel="noreferrer">Sutton and Barto book</a> chapter two to get familiarized with it.</p>
  <p><em>Edit: since the answer got popular, I'll address the comments and the question edit</em>.</p>
  <p>Being a special simplified subset of Markov Decision Processes, Multi Armed Bandit problems allow deeper theoretical understanding. For example, (as per @NeilSlater comment) the optimal policy would be to always go for the best arm. So it makes sense to introduce &quot;regret&quot; <span class="math-container">$\rho$</span> - the difference between a potential optimal reward and the actual collected reward by agent following your strategy:</p>
  <p><span class="math-container">$$\rho(T) = \mathbb{E}\left[T\mu^* -\sum_{t=1}^T\mu(a_t)\right]$$</span></p>
  <p>One can then study asymptotic behavior of this regret as a function of <span class="math-container">$T$</span> and devise strategies with different asymptotic properties. As you can see, the reward here is not discounted (<span class="math-container">$\gamma=1$</span>) - we usually can study the behavior of it as a function of <span class="math-container">$T$</span> without this regularization.</p>
  <p>Although, there is one famous result that uses discounted rewards - the <a href="https://en.wikipedia.org/wiki/Gittins_index" rel="noreferrer">Gittins index policy</a> (note, though, that they <a href="https://en.wikipedia.org/wiki/Gittins_index#Mathematical_definition" rel="noreferrer">use <span class="math-container">$\beta$</span> instead of <span class="math-container">$\gamma$</span></a> to denote the factor).</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-05-07T17:22:20.457Z
Answers.Text: I think this answer misses where MABs are different from MDPs in terms of reasons for studying and using them. Whilst MABs can be treated as a strict subset of MDPs, and that is how S&B uses them - as a stepping stone towards learning about RL - there are also approaches and analysis that are used more often with MABs because of what they model. Optimising *regret* during learning is a good example of this. Not usually of concern in RL (and difficult to define and measure in MDPs), but of great interest in applications of MABs in real-world projects.
Answers.UserDisplayName: Neil Slater
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-05-07T17:27:08.813Z
Answers.Text: @NeilSlater Are you up to make a full answer? I would be interested in seeing what you have to say on the subject.
Answers.UserDisplayName: notaprogrammertoday
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-05-07T17:28:25.027Z
Answers.Text: @NeilSlater I agree that you can go deeper into the usefulness of MABs. But, given that the question conflates RL algorithms with MABs I didn't feel like that this level of discussion would be helpful.
Answers.UserDisplayName: Kostya
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-05-14T19:29:29.340Z
Answers.Text: @Kostya Can we see DQN as a bandit problem?
Answers.UserDisplayName: notaprogrammertoday
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-05-14T21:02:05.580Z
Answers.Text: @notaprogrammertoday Can one see linux as a CPU? Your question conflates completely separate concepts.
Answers.UserDisplayName: Kostya
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-05-07T16:38:35.090Z
Answers.LastActivityDate: 2021-05-10T21:03:13.413Z
Answers.LastEditDate: 2021-05-10T21:03:13.413Z
Answers.UserDisplayName: Kostya
Body: <p>I have studied in the past different algorithms, i.e. DQN, DDQN, REINFORCE, A3C, PPO, TRPO, so on. I am doing an internship this summer where I have to use a multi-armed bandit (MAB). I am a bit confused between MAB and the other above algorithms.</p>
  <p>What are the major differences between MAB and REINFORCE, for instance? What are the major differences between MAB and the other well-known algorithms (DQN, A3C, PPO, etc)?</p>
  <p><strong>EDIT</strong></p>
  <p>The @Kostya's answer is fine, but it would be interested for me to have a deeper answer for that question. I am still a bit confused.</p>
  <p><strong>Question:</strong> Do we use the Markov Reward formula <span class="math-container">$$G_t = R_{t+1} + \gamma R_{t+2} + ... = \sum_{k=0}^{\infty} \gamma^k R_{t+k+1}$$</span> the same way in a Multi-Armed bandit problem versus a DQN problem?</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-05-10T22:21:55.363Z
Comments.Text: Hello. It's fine to edit your post to clarify the question, but your initial question asked for a general answer, which is different from your question asked in the last edit. If you have a more specific question, you can still ask another question but maybe in a separate post. Note that questions that ask the readers to write very long answers are not suitable for our site (so either you ask for the general idea or you need to ask specific questions, one for each post). Note also that the tag [tag:comparison] is suitable for this post, as you were asking people for a comparison/difference.
Comments.UserDisplayName: nbro
Tags: <reinforcement-learning><comparison><deep-rl><multi-armed-bandits>
Title: What are the major differences between multi-armed bandits and the other well-known algorithms (DQN, A3C, PPO, etc)?
UserDisplayName: notaprogrammertoday
ThreadText: # What are the major differences between multi-armed bandits and the other well-known algorithms (DQN, A3C, PPO, etc)?
  
  (Asked by: username_0 on 2021-05-07)
  
  I have studied in the past different algorithms, i.e. DQN, DDQN, REINFORCE, A3C, PPO, TRPO, so on. I am doing an internship this summer where I have to use a multi-armed bandit (MAB). I am a bit confused between MAB and the other above algorithms.
  
  What are the major differences between MAB and REINFORCE, for instance? What are the major differences between MAB and the other well-known algorithms (DQN, A3C, PPO, etc)?
  
  **EDIT**
  
  The @Kostya's answer is fine, but it would be interested for me to have a deeper answer for that question. I am still a bit confused.
  
  **Question:** Do we use the Markov Reward formula $$G\_t = R\_{t+1} + \gamma R\_{t+2} + ... = \sum\_{k=0}^{\infty} \gamma^k R\_{t+k+1}$$ the same way in a Multi-Armed bandit problem versus a DQN problem?
  
  **Tags:** reinforcement-learning, comparison, deep-rl, multi-armed-bandits
  > **Comments:**
  > **username_1**: Hello. It's fine to edit your post to clarify the question, but your initial question asked for a general answer, which is different from your question asked in the last edit. If you have a more specific question, you can still ask another question but maybe in a separate post. Note that questions that ask the readers to write very long answers are not suitable for our site (so either you ask for the general idea or you need to ask specific questions, one for each post). Note also that the tag [tag:comparison] is suitable for this post, as you were asking people for a comparison/difference.  
  
  ---
  
  ## 2 answers
  
  ### Answer by username_3 on 2021-05-07. Score: 12 | Accepted answer
  
  You should start with the general definition of [Reinforcement Learning](https://en.wikipedia.org/wiki/Reinforcement_learning) problem. And what [Markov Decision Process](https://en.wikipedia.org/wiki/Markov_decision_process) is.
  
  DQN, A3C, PPO and REINFORCE are algorithms for solving reinforcement learning problems. These algorithms have their strengths and weaknesses depending on the details of the underlying problem.
  
  [Multi-Armed Bandit](https://en.wikipedia.org/wiki/Multi-armed_bandit) is not even an algorithm - it is a subclass of reinforcement learning problems, where your environment (usually) doesn't have any state transitions and your actions are just a single choice from (usually) fixed and finite set of choices.
  
  Multi-Armed Bandit is used as an introductory problem to reinforcement learning, because it illustrates some basic concepts in the field: exploration-exploitation tradeoff, policy, target an estimate, learning rate and gradient optimization. All these concepts are basic vocabulary in RL. I recommend reading (and, very importantly, doing all the exercises) the [Sutton and Barto book](http://incompleteideas.net/book/the-book.html) chapter two to get familiarized with it.
  
  *Edit: since the answer got popular, I'll address the comments and the question edit*.
  
  Being a special simplified subset of Markov Decision Processes, Multi Armed Bandit problems allow deeper theoretical understanding. For example, (as per @NeilSlater comment) the optimal policy would be to always go for the best arm. So it makes sense to introduce "regret" $\rho$ - the difference between a potential optimal reward and the actual collected reward by agent following your strategy:
  
  $$\rho(T) = \mathbb{E}\left[T\mu^\* -\sum\_{t=1}^T\mu(a\_t)\right]$$
  
  One can then study asymptotic behavior of this regret as a function of $T$ and devise strategies with different asymptotic properties. As you can see, the reward here is not discounted ($\gamma=1$) - we usually can study the behavior of it as a function of $T$ without this regularization.
  
  Although, there is one famous result that uses discounted rewards - the [Gittins index policy](https://en.wikipedia.org/wiki/Gittins_index) (note, though, that they [use $\beta$ instead of $\gamma$](https://en.wikipedia.org/wiki/Gittins_index#Mathematical_definition) to denote the factor).
  
  > **Comments:**
  > **username_4**: I think this answer misses where MABs are different from MDPs in terms of reasons for studying and using them. Whilst MABs can be treated as a strict subset of MDPs, and that is how S&B uses them - as a stepping stone towards learning about RL - there are also approaches and analysis that are used more often with MABs because of what they model. Optimising *regret* during learning is a good example of this. Not usually of concern in RL (and difficult to define and measure in MDPs), but of great interest in applications of MABs in real-world projects.  
  > **username_0**: @NeilSlater Are you up to make a full answer? I would be interested in seeing what you have to say on the subject.  
  > **username_3**: @NeilSlater I agree that you can go deeper into the usefulness of MABs. But, given that the question conflates RL algorithms with MABs I didn't feel like that this level of discussion would be helpful.  
  > **username_0**: @Kostya Can we see DQN as a bandit problem?  
  > **username_3**: @notaprogrammertoday Can one see linux as a CPU? Your question conflates completely separate concepts.  
  
  ---
  
  ### Answer by username_2 on 2023-12-25. Score: -1
  
  MAB is fundamentally different from MDP problem, which so-called well-known RL algorithms trying to solve. The point is that MAB's policy is exactly the action. The Q function takes only action(policy) $a$ as its input. Whereas in MDP, the policy is a function, The Q function takes not only state-action $s,a$ but also policy parameter $\theta$, which makes evaluation of policy and improvement of policy tangled together.
  
  In other words, in MAB, if one has good evaluation of a policy(action), then optimal policy is directly given. But in MDP, if one has good evaluation of a policy, the optimal policy is still unclear. That is why one needs DQN to do policy Evaluation and policy Improvement together.
  
  As for policy gradient policy like PPO, it takes another road to directly optimize the polciy to a more-promising gradient direction based on the feedback from reward.
  
  
  ---
  
  