Week 1: Incorrect "Reflecting on results"

[nokados]

In the seminar of week 1, there is a problem: optimization goes up to around -50. You propose the next workaround:

To mitigate that problem, you can either reduce the threshold for elite sessions (duct tape way) or change the way you evaluate strategy (theoretically correct way). For each starting state, you can sample an action randomly, and then evaluate this action by running several games starting from it and averaging the total reward. Choosing elite sessions with this kind of sampling (where each session's reward is counted as the average of the rewards of all sessions with the same starting state and action) should improve the performance of your policy.

I think this will not work. In the video, you compare this problem with a "bandit" that gives you a reward randomly. It is not the Taxi task case, because, despite the random start state, your reward is defined by state and action. So I do not see the point to fix action for a starting point.

I propose a different solution. I agree that in case CEM failed to learn how to win from one distinct starting point, it will simply discard it because no sessions from that starting point will make it into the "elites". So let's take samples from each point into elite samples. To do this, we just calculate the percentile for each state independently instead of a single total percentile.

So, select_elites will look like this:

import pandas as pd

def select_elites(states_batch, actions_batch, rewards_batch, percentile):
    df = pd.DataFrame({
        'state': np.concatenate(states_batch),
        'action': np.concatenate(actions_batch),
        'reward': np.concatenate(
            [[rewards_batch[i]] * len(states_batch[i]) 
            for i in range(len(rewards_batch))]) # repeat reward len(states) times
        })

    reward_threshold = df.groupby('state').reward.quantile(percentile / 100)
    elite = df.apply(lambda row: row['reward'] > reward_threshold[row['state']], axis=1)

    return df[elite].state, df[elite].action

I have also increased n_sessions to 500 to have more samples per state.

As a result, the task converges to a positive score of around 5.

[nokados]

Oops. I haven't seen a homework suggesting fixing this when I wrote the issue. Probably we should delete this...

[dniku]

I'm not sure I understand which homework you are referring to where you say that it suggests to fix this issue. The next homework is deep CEM, which differs only by the environment (MountainCar instead of Taxi) and the estimator (a neural network instead of a table). We don't expect any changes for the learning algorithm there. In week 2 and onwards, we move on to more complex algorithms, none of which are a generalization of CEM.

However, I don't think that investing any effort into tuning the CEM assignment is worthwhile. It only serves the function of demonstrating that an extremely primitive algorithm can solve RL problems, but its performance is weak compared to Q-learning or any other "true RL" algorithms.