Answers.Body: <p>The bandit problem is an MDP. You can make the same argument about needing data to learn in the stateful MDP setting. The thing is, the data you need (the past rewards in this case) was drawn iid (conditioned on the arm) and is not actually a trajectory. For instance, once you learn an optimal policy, you no longer need to gather data and the sequence of past results doesn't influence your policy.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-06-16T09:03:44.707Z
Answers.Text: It seems to me that the OP is mixing the concept of a state and action and reward. It may be a good idea to clarify that these are distinct concepts and explain how are they related. Moreover, it may also be a good idea to clarify that a k-armed bandit problem can be modelled as an MPD with 1 state or no state, where the actions are the arms that you can pull; so, in this scenario, the policy would always be conditioned on the same state. That's why it would probably be redundant to write $\pi(a \mid s)$.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-06-16T10:53:57.310Z
Answers.Text: I assumed the OP understood this, he did write $\pi(a)$. I think he's questioning why the policy shouldn't be conditioned on the previous actions and associated rewards because you use those to estimate the optimal policy.
Answers.UserDisplayName: harwiltz
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-06-15T13:42:24.110Z
Answers.LastActivityDate: 2021-06-15T13:42:24.110Z
Answers.UserDisplayName: harwiltz
Body: <p>I've read Sutton and Barto's introductory RL book. They define a policy as a mapping from states to probabilities of selecting each possible action. If the agent is following policy <span class="math-container">$\pi$</span> at time <span class="math-container">$t$</span>, then <span class="math-container">$\pi(a|s)$</span> as the probability of taking action <span class="math-container">$A_t = a$</span> when the current state is <span class="math-container">$S_t = s$</span>. This definition is the context of the markov assumption, which is why the policy is only dependent on the current state.</p>
  <p>When discussing the standard k-armed bandits problem, they write <span class="math-container">$\pi(a)$</span> to denote the probability of taking action <span class="math-container">$a$</span>, since there are no states. However, when designing the agent, clearly, the agent needs to keep track of what the past rewards are for each lever, so either there is a summary statistic of each lever, or the entire history of actions and rewards must be kept.</p>
  <p>Is the k-armed bandit problem then a MDP? Why isn't the notation <span class="math-container">$\pi(a|A_0, R_1, A_1, \ldots, R_T)$</span> for some sequence  <span class="math-container">$A_0, R_1, A_1, \ldots, R_T$</span>?</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-12-14T09:03:42.750Z
Comments.Text: [Here](https://ai.stackexchange.com/q/20850/2444) is a related question.
Comments.UserDisplayName: nbro
Tags: <reinforcement-learning><comparison><markov-decision-process><notation><multi-armed-bandits>
Title: Is the Bandit Problem an MDP?
UserDisplayName: Snowball
ThreadText: # Is the Bandit Problem an MDP?
  
  (Asked by: username_0 on 2021-06-15)
  
  I've read Sutton and Barto's introductory RL book. They define a policy as a mapping from states to probabilities of selecting each possible action. If the agent is following policy $\pi$ at time $t$, then $\pi(a|s)$ as the probability of taking action $A\_t = a$ when the current state is $S\_t = s$. This definition is the context of the markov assumption, which is why the policy is only dependent on the current state.
  
  When discussing the standard k-armed bandits problem, they write $\pi(a)$ to denote the probability of taking action $a$, since there are no states. However, when designing the agent, clearly, the agent needs to keep track of what the past rewards are for each lever, so either there is a summary statistic of each lever, or the entire history of actions and rewards must be kept.
  
  Is the k-armed bandit problem then a MDP? Why isn't the notation $\pi(a|A\_0, R\_1, A\_1, \ldots, R\_T)$ for some sequence $A\_0, R\_1, A\_1, \ldots, R\_T$?
  
  **Tags:** reinforcement-learning, comparison, markov-decision-process, notation, multi-armed-bandits
  > **Comments:**
  > **username_1**: [Here](https://ai.stackexchange.com/q/20850/2444) is a related question.  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_2 on 2021-06-15. Score: 1 | Accepted answer
  
  The bandit problem is an MDP. You can make the same argument about needing data to learn in the stateful MDP setting. The thing is, the data you need (the past rewards in this case) was drawn iid (conditioned on the arm) and is not actually a trajectory. For instance, once you learn an optimal policy, you no longer need to gather data and the sequence of past results doesn't influence your policy.
  
  > **Comments:**
  > **username_1**: It seems to me that the OP is mixing the concept of a state and action and reward. It may be a good idea to clarify that these are distinct concepts and explain how are they related. Moreover, it may also be a good idea to clarify that a k-armed bandit problem can be modelled as an MPD with 1 state or no state, where the actions are the arms that you can pull; so, in this scenario, the policy would always be conditioned on the same state. That's why it would probably be redundant to write $\pi(a \mid s)$.  
  > **username_2**: I assumed the OP understood this, he did write $\pi(a)$. I think he's questioning why the policy shouldn't be conditioned on the previous actions and associated rewards because you use those to estimate the optimal policy.  
  
  ---
  
  