# Is the Bandit Problem an MDP?

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$$?

• Here is a related question.
– nbro
Dec 14, 2021 at 9:03

• 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)$.
• 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. Jun 16, 2021 at 10:53