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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
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$
4
  • $\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, 2020 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, 2020 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, 2020 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, 2020 at 18:15

You must log in to answer this question.

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