Using Mario to Derive the Fundamentals of Reinforcement Learning

Basic Definitions

• $\pi(a| s)$: The probability distribution of taking action $a$ in state $s$. This is a policy function that samples to select actions. In the Mario game, it means deciding whether to move left, move right, or jump given the current state.

• $V(s)$: The value function, representing the expected cumulative reward obtainable from state $s$ onward. In the game, it refers to the total score you can accumulate from the current position until the game ends.

• On Policy: Optimizing the current policy while collecting data. In the game, it means optimizing the policy based on historical score rewards before the current game has even ended.

• Off Policy: Optimizing the policy only after collecting a complete set of data. In the game, it means you must finish an entire game, obtain the final score, and only then aggregate the historical data to optimize the policy.

• Advantage function: $A(s_t, a_t) = Q(s_t, a_t) - V(s_t)$: $Q(s_t, a_t)$ represents the expected cumulative reward obtainable in the future after taking action $a_t$ in state $s_t$ and entering the next state. Clearly, if the action $a_t$ taken yields a higher future reward than the average future reward of state $s_t$, then it is a good action. For example, if there's a coin above Mario's head, choosing to jump will provide more points in the future, while choosing not to jump means missing out and getting fewer future points. Obviously, jumping is better.

All theoretical derivations in RL revolve around one thing: how to optimize the policy function $\pi(a|s)$ so that $\pi(a|s)$ can choose the most beneficial action for the future in every state.

If there existed an omniscient value function $V(s_t)$ that knew the value of every state, things would be easy. In the current state, you could enumerate all possible actions, see which action leads to the next state with the greatest advantage gain, and pick that one. Unfortunately, $V(s_t)$ is very difficult to define directly—no one can predict the future.

Monte Carlo Methods

RL training based on Monte Carlo methods aims to find a policy $\pi(a|s)$ that maximizes the reward score.

The total future reward obtainable after taking action $a$ in state $s$: $Q(s, a) = E_{\pi} [\sum_{k = 0} \gamma^k r_{t + k +1}]$

After Mario finishes an entire game, we obtain the sequence $[s_1, a_1, r_2, s_2, a_2, .... ]$, with every reward at each moment recorded. Then the expected cumulative future reward for a given state is easy to compute: $G_t = r_{t + 1} + \gamma r_{t + 1} + \gamma^2 r_{t + 2} + ...$

Next, we use the Monte Carlo method to optimize the policy function: $Q(s, a) \leftarrow Q(s_t, a_t) + \alpha \cdot (G_t - Q(s_t, a_t))$

Explanation:

• The original $Q(s_t, a_t)$ is an estimate—a prediction of how much cumulative reward will be obtained in the future.

• $G_t$ is the actual cumulative reward computed after the game ends, representing the future reward obtained by taking action $a_t$ in state $s_t$.

• So we update based on the difference to fit the true value.

• $\alpha$ is the learning rate.

This completes one update of the policy function. What's next? Play another round of Mario, obtain another sequence and the scores at each step.

However, to ensure the model doesn't get stuck in a local optimum, we can have Mario take the action with maximum $\pi(a|s)$ with probability $1 - \epsilon$ in state $s$, ensuring there's still some probability of trying new actions.

Temporal Difference Methods

Monte Carlo methods are good, but you need to finish an entire game before training once. In large games, completing one round could take an unknown amount of time. So we want a way to optimize the policy function during the game based on the historical state sequence. This is where temporal difference comes in.

Same as before, we want to find a $\pi(a|s)$ that maximizes $Q(s, a)$.

Policy update: $Q(s_t, a_t) \leftarrow Q(s_t, a_t) + \alpha \cdot[r_{t + 1} + \gamma Q(s_{t + 1}, a_{t + 1}) - Q(s_t, a_t)]$

Training process: In state $s_t$, take action $a_t$, receive reward $r_{t + 1}$, enter the next state $s_{t + 1}$, and then update $Q(s_t, a_t)$.

Note: Both $Q(s_t, a_t)$ values are randomly initialized, but even so, using $Q(s_{t + 1}, a_{t + 1})$ to update $Q(s_t, a_t)$ is reasonable. With sufficiently long training, the updates to $Q(s_t, a_t)$ depend on the true environment reward function and state transition probabilities, so convergence is achievable.

A more rigorous proof relies on the recursive nature of the Bellman expectation equation. Since this derivation is complex, we won't go deeper here.

After completing one round of training, when sampling actions in the next round, similar to the Monte Carlo method, we still need to use an $\epsilon$-greedy strategy to ensure there remains an opportunity to explore new actions.

PPO (Proximal Policy Optimization)

After solving the slow training problem, RL training still faces many other issues, such as training instability. When policy gradient updates are too large, the model's policy can easily collapse, swinging from one extreme to another. For example, Mario discovers that if he doesn't move, he won't die, so he simply gives up and does nothing—at least the score won't be negative.

Once we understand the phenomenon, the solution naturally emerges: limit the update magnitude of the policy function. Don't take steps that are too large. We can use KL divergence to quantify the difference between two distributions and constrain it within a certain range.

Derivation: