1
$\begingroup$

Sample-based algorithms, like Monte Carlo Algorithms and TD-Learning, are often presented as useful since they do not require a transition model.

Assuming I do have access to a transition model, are there any reasons one might want to use sample-based methods instead of performing a full Bellman update?

$\endgroup$
1
$\begingroup$

A full Bellman update can be intractable. For instance, if your state space or action space are continuous, the full Bellman update is intractable. You can try to solve this by discretizing, but if your state space is large this will also be intractable.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Would it also make sense to prefer MC in MDPs where episodes run for a very long time, since it will take Bellman updates far longer to propagate back to the start state? $\endgroup$ – chessprogrammer Jul 9 at 15:15
  • $\begingroup$ Not necessarily, I believe you'd experience the same issue with MC. I believe in general if you can do bellman updates, you probably should. $\endgroup$ – harwiltz Jul 9 at 17:00
  • $\begingroup$ Interesting. In MC, all states in an episode are updated based on the terminal state. So if the reward signal is sparse and only present in terminal states, like in a game, I think the signal would propogate faster, since in Bellman updates, the reward propogates back one state at a time $\endgroup$ – chessprogrammer Jul 9 at 17:58
  • $\begingroup$ Don't forget, in MC you have to wait an entire episode before an update. Credit assignment will be difficult one way or the other, I believe. $\endgroup$ – harwiltz Jul 9 at 18:15

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.