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

$\endgroup$
0
$\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$
  • $\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 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 at 15:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.