Let's assume that I have an MDP $M$ which has a number of maximal end components. I also have a random policy (scheduler) $\pi$ that can convert the MDP $M$ into a Markov chain $m$. Can I argue that all recurrent classes of MC $m$ has states that belong to MDP $M$'s maximal end components?

  • $\begingroup$ What have you tried? Try to write down the explicit definition of a recurrent class for MDPs and for MCs, and consider a state in a recurrent class of the MC. What can you say about it? $\endgroup$ – Shaull Sep 19 '17 at 13:55
  • $\begingroup$ Can I say since the recurrent classes are irreducible then all states communicate with each other. This means that before applying the scheduler, these states were strongly connected to each other. Hence they belong to an MEC in the original MDP. $\endgroup$ – Perissiane Sep 19 '17 at 16:23
  • $\begingroup$ yes, this is the idea. If two states are reachable from each other in the MC, then surely they are also reachable from each other in the MDP, and are therefore in the same MEC. $\endgroup$ – Shaull Sep 19 '17 at 16:52

Your Answer

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

Browse other questions tagged or ask your own question.