4
$\begingroup$

I'm trying to get a better understanding of Multi-Arm Bandits, Contextual Multi-Arm Bandits and Markov Decision Process.

Basically, Multi-Arm Bandits is a special case of Contextual Multi-Arm Bandits where there is no state(features/context). And Contextual Multi-Arm Bandits is a special case of Markov Decision Process, where there is only one state (features, but no transitions).

However, since MDP has Markov property, I wonder if every MDP problem can also be converted into a Contextual Multi-Arm Bandits problem, if we simply treat each state as a different input context (features)?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

The main difference between an MDP and contextual bandit setting is time steps and state progression. If those are important to the problem you want to solve, then it is not possible to convert.

Essentially MDPs are a strict generalisation of contextual bandits. You can model a CB as an MDP but not vice-versa.

In some very specific cases you can convert MDP to CB - any one of these situations means that the MDP can be simplified to CB, and then you could use bandit solving algorithms to optimise it:

  • When there is only one time step for an episodic problem.

  • When the discount factor is zero.

  • When state transition rules are completely independent of action choice, but reward is not.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks for your reply. If you have criteria #2 and #3, does #1 even matter any more? - I think that basically makes it a non-episodic problem? - Also MAB actually can have a non-zero discount factor. $\endgroup$
    – peidaqi
    Aug 18, 2020 at 13:37
  • $\begingroup$ It is any one of the criteria. The discount factor in MAB is not the same thing as in MDP $\endgroup$
    – Neil Slater
    Aug 18, 2020 at 15:10

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .