How does Monte Carlo Exploring Starts work?

Question

I'm having trouble understanding the 5th step in the flowchart.

For the 5th step, the 'update the Q function by taking the average of returns' is confusing.

From what I understand, the Q function is basically the state-action pair values put in a table (the Q table). To update it means to make adjustments to the state-action pair value of the individual states and their respective actions (e.g state 1 action 1, state 3 action 1, state 3 action 2, so on and so forth).

I'm not sure what 'average of returns' means though. Is it asking me to take the average of the returns after $x$ episodes? From my understanding, returns is the sum of rewards in a full episode (So, AVG=sum of returns for x episodes/x).

And what do I do with that 'average'?

I'm a little confused when they say 'update the Q function' because the Q function consists of many parameters that must be updated (the individual state-action pair value), and I'm not sure which one they are referring to.

What is the point of calculating the average of returns? Since the state-action pair value for a particular state and particular action will always be the same (e.g if I always take action 3 in state 4, I will always get value=2 forever)

Answer 1

each episode you will calculate the return, you will then update the action value or $Q(s,a)$ as the average each episode. Using the blackjack example from open AI gym and using a discount factor of 1, you get the following

episode 1 [{'state': (22, 10, False), 'reward': -1, 'action': 1}, {'state': (17, 10, False), 'reward': 0, 'action': 1}, {'state': (12, 10, False), 'reward': 0.0, 'action': 1}]

$Q((22, 10, False),0)=-1$

$Q((17, 10, False),1)=-1$

$Q((12, 10, False),1)=-1$

episode 2 [{'state': (21, 10, False), 'reward': 1, 'action': 0}, {'state': (17, 10, False), 'reward': 0, 'action': 1}, {'state': (12, 10, False), 'reward': 0.0, 'action': 1}]

$Q((21, 10, False),0)=1$

$Q((17, 10, False),1)=0$

$Q((12, 10, False),1)=0$

For $Q((17, 10, False),1)$ and $Q((12, 10, False),1)$ is the average return i.e -1 for the first episode and 1 for the second.

Answer 2

$Q(s,a)$ denotes the $Q-value$ for the state-action pair. It means the expected returns if we start from state $s$, take action $a$, and act according to whatever policy we are currently following.

Suppose we are in state $s_0$, take action $a_0$. To compute the returns, we would need to follow our current policy from whatever state we land up after taking $a_0$, till the end of the episode, and sum up the rewards (or discounted rewards) that we get along the way.

Why average of returns?
Because we would want to do this multiple times for a state-action pair and compute the average of all such episodes.

Why multiple times?
Generally, the environments and the transition function would have some randomness and we don't get the same reward every time.

Why would you want to compute this?
The idea is simple. Since our goal is to maximize the average return, if we compute Q-values for all the possible actions starting from state $s_0$, then we can compare between the values and decide which action is going to be most beneficial to take from state $s_0$.

Since this is a tabular approach, when they say update the Q-function, they just mean to update the Q-values.

As an example, suppose we are in state $s_0$ and can take actions $a_0$, $a_1$, and $a_2$. We first compute the Q-values for $(s_0, a_0), (s_0,a_1), (s_0, a_2)$ pairs, and then we would choose the action which has the maximum Q-value out of these three.