2
$\begingroup$

When you train a model using Monte Carlo-based learning the state and action taken at each step is recorded, and then at some point an end state is reached and the agent receives some reward - what do you do at that point?

Let's say there were 100 steps taken to reach this final reward state, would you update the full rollout of those 100 state/action/rewards and then begin the next episode, or do you then 'bubble up' that final reward to the previous states and update on those as well?

E.g.

  • Process an update for the full 100 experiences. Can either stop here, or...

  • Bubble up the final reward to the 99th step and process an update for the 99 state/action/reward.

  • Bubble up the final reward to the 98th step and process an update for the 98 state/action/reward.

  • and so on right the way to the first step...

Or, do you just process an update for the full 100-step roll-out and that's it?

Or perhaps these are two different approaches? Is there a situation where you'd one rather than the other?

$\endgroup$
  • $\begingroup$ Could you specify what do you mean under "bubble up"? I guess it's discounted reward, but I would like to answer upon wrong assumptions. $\endgroup$ – David Sep 14 at 10:54
  • $\begingroup$ Firstly, I'm performing a full depth-first exploration of the search tree, but only the terminal state gives a reward. I was thinking I could pass the reward at each terminal up to the previous branch level, and the max(rewards) at that level is then used to generate an experience list, then that max(rewards) is passed up to the previous level, and so on. Do this all the way back to the first state which then has the max(rewards) propagated from all possible branches. Does that make sense? $\endgroup$ – BigBadMe Sep 14 at 13:24
  • $\begingroup$ It makes sense. It has similarities to what Q-learning does. However, what you'd end up with is that your reward is actually a potential state value. It's interesting, but I'm not sure what the right implementation should be. $\endgroup$ – David Sep 14 at 13:55
  • $\begingroup$ Neither am I :-s I wonder what did DeepMind do for Go? Whether they 'bubbled up' the win reward to the previous branches...? $\endgroup$ – BigBadMe Sep 14 at 14:30
  • $\begingroup$ @BigBadMe: AlphaZero does not use Monte Carlo control, but a combination of other things, including Monte Caro Tree Search. You should not confuse MCTS with Monte Carlo control, although there are some similarities they are very different algorithms in key areas too. Could you make it clear which are you wanting to ask about? As the question stands I would assume Monte Carlo control. $\endgroup$ – Neil Slater Sep 15 at 9:15
1
$\begingroup$

I am assuming you are asking about Monte Carlo simulation for value estimates, perhaps as part of a Monte Carlo control learning agent.

The basic approach of all value-based methods is to estimate an expected return, often the action value $Q(s,a)$ which is a sum of expected future reward from taking action $a$ in state $s$. Monte Carlo methods take a direct and simple approach to this, which is to run the environment to the end of an episode and measure the return. This return is a sample out of all possible returns, so it can just be averaged with other observed returns to obtain an estimate. A minor complication is that the return depends on the current policy, and in control scenarios that will change, so the average needs to be recency-weighted for control e.g. using a fixed learning rate $\alpha$ in an update like $Q(s,a) \leftarrow Q(s,a) + \alpha(G - Q(s,a))$

Given this, you can run pretty much any approach that calculates the returns from observed state/action pairs. You will find that the "bubble up" approach is used commonly - the process usually termed backing up - working backwards from the end of the episode.

If you have an episode from $t=0$ to $t=T$ and records of states, actions, rewards $s_0, a_0, r_1, s_1, a_1, r_2, s_2, a_2, r_3 . . . s_{T-1}, a_{T-1}, r_T, s_T$ (note indexing, reward follows state/action, there is no $r_0$ and no $a_T$), then the following algorithm could be used to calculate individual returns $g_t$:

$g \leftarrow 0$

for $t = T-1$ down to $0$:

$\qquad g \leftarrow r_{t+1} + \gamma g$

$\qquad Q(s_t,a_t) \leftarrow Q(s_t,a_t) + \alpha(g - Q(s_t,a_t))$

This working backwards is an efficient way to process rewards and assign them with discounting to action values for all state, action pairs observed in the episode.

Or perhaps these are two different approaches?

It would be valid to calculate only the return for the first state/action, and randomly select state/actions to start from (called exploring starts). Or in fact take any arbitrary set of estimates generated this way. You don't have to use all return estimates, but you do need to have an algorithm that is guaranteed to update values of all state/action pairs in the long term.

Is there a situation where you'd one rather than the other?

Most usually you will see the backed up return estimates to all observed state/action pairs, as this is more sample efficient, and Monte Carlo is already a high variance method that requires lots of samples to get good estimates (especially for early state/action pairs at the start of long episodes).

However, if you work with function approximation such as neural networks, you need to avoid feeding in correlated data to learn from. A sequence of state/action pairs from a single episode are going to be correlated. There are a few ways to avoid that, but one simple approach could be to take just one sample from each rollout. You might do this if rollouts could be run very fast, possibly simulated on computer. But other alternatives may be better - for instance put all the state, action, return values into a data set, shuffle it after N episodes and learn from everything.

$\endgroup$
  • $\begingroup$ Thank you for your excellent answer, Neil. After further thought, if I set gamma to high number, 0.995, then the reward received at the Terminal state would be propagated through the previous experiences, so I think to start with I will simply train on the full experience roll-out with high gamma, rather than backing up the max(rewards) achieved from Terminal states coming from each branch level of the search tree and creating a truncated list of experiences. I can always experiment later on to see which approach is better. Thanks again. $\endgroup$ – BigBadMe Sep 16 at 8:54
  • $\begingroup$ @BigBadMe: That should be fine. In fact for episodic problems you can often set $\gamma=1$. That partly depends on whether you are using the discount factor to encourage solutions that use less time steps (e.g. a maze with reward +1 to exit and 0 reward otherwise needs $\gamma \lt 1$, but you could have a maze with reward -1 on all steps and use $\gamma = 1$), $\endgroup$ – Neil Slater Sep 16 at 8:57
  • $\begingroup$ Ahh interesting. I'm sure I'd read somewhere that setting gamma=1 would cause problems, but perhaps as you say it depends on the situation it's used. $\endgroup$ – BigBadMe Sep 17 at 9:25

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.