# In Monte Carlo learning, what do you do when an end state is reached, after having recorded the previously visited states and taken actions?

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?

• Comments are not for extended discussion; this conversation has been moved to chat.
– nbro
Jan 3 at 14:03

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.

• 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. Sep 16 '19 at 8:54
• @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$), Sep 16 '19 at 8:57
• 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. Sep 17 '19 at 9:25