Cliff Walking With Monte Carlo Reinforcement Learning
A comparison of TD(0) and TD(1) learning, including a full Python implementation
New year, new cliff walking algorithm! This time, Monte Carlo Reinforcement Learning will be deployed. Arguably, it is the simplest and most intuitive form of Reinforcement Learning. This article contrasts the algorithm to temporal difference methods such as Q-learning and SARSA. Furthermore, the full Python implementation is provided and some numerical results are shown.
The cliff-walking problem
The cliff walking problem is a textbook problem (Sutton & Barto, 2018), in which an agent attempts to move from the left-bottom tile to the right-bottom tile, aiming to minimize the number of steps whilst avoiding the cliff. An episode ends when walking into the cliff (large negative reward) or on the target tile (positive reward).
Monte Carlo Reinforcement Learning
Monte Carlo RL is known under several other names (technically there are some minor differences, but let's ignore that), including:
Double pass: First a forward pass till the episode's end while collecting rewards, then a pass backwards to update value functions for all states encountered.
Backward pass: This term emphasizes the backwards mechanism that loops back over all states encountered during the episode.
Temporal Difference 1 or TD(1): TD(0) refers to updates taking place after every time step, TD(1) updates after a full trajectory.
I'm not very partial to either of the names, but I'll stick with Monte Carlo RL (MC-RL) for the remainder of the article.
At any rate, the core notion is that one first completes the full experience trajectory - in this case the steps walked until hitting the goal or falling into the cliff - and only then proceeds to update the lookup table.
The fundamental difference between MC-RL and temporal difference methods such as Q-learning and SARSA is that the latter update the lookup table after each time step, using the estimate Q(s_t+1,a) to update Q(s_t,a_t). This procedure is also known as bootstrapping; one estimate is used to update the other. As a refresher, here are the update functions:
In contrast, MC-RL only utilizes the actual observations of the trajectory to update the lookup table. The key benefit is that makes the procedure unbiased; for the sake of intuition, imagine the observations being randomly sampled from the corresponding probability distribution. Especially when Q-values are represented by approximation functions - which is often inevitable when problems grow in size - bias can seriously hamper performance. However, MC-RL reward trajectories exhibit much greater variance and thus typically learn (a lot) slower.
The update function for value function V(s_t) is very straightforward, simply computing the error between observed reward trajectory G_t and value function V(s_t), updating with a weight α:
where the cumulative reward trajectory G_t (downstream rewards discounted by γ) is given by:
The mechanism is very comprehensive and intuitive, but let's consider some complications. Take a look at the following two sample trajectories:
Although the trajectories are near-identical, one will result in positive reward updates for all states encountered and the other one in negative updates. As mentioned earlier, the variance of Monte Carlo methods tends to be very high, as cumulative rewards can be vastly different. The situation depicted above would have a much smaller impact in TD(0) learning.
Additionally, there is an increased risk of ending in suboptimal solutions. For this specific problem, the agent may stick to a single path, simply because it discovered that path once. Due to those tiles having higher values, the agent might follow the same path over and over.
Numerical experiment
The Monte Carlo method presented here is on-policy, meaning that it used actual observed rewards to update estimate. As such, a fair benchmark is SARSA, which also operates under the on-policy principle. Like always, the Python source code is found on my GitHub repository.
The first thing noticed is that, using a standard exploration rate of ϵ=0.05, MC-RL often simply does not converge to a satisfying solution within 10,000 episodes. I raise it to ϵ=0.10, and for a fair comparison do the same for SARSA.
Without further ado, it's time for the results. Clearly, Monte Carlo RL performs considerably worse than SARSA, taking much longer to converge and often sticking to a worse path as well. The steep drop implies that the agent keeps following the first successful path, with little improvement afterwards.
Corresponding solutions also tend to show some peculiar patterns. Being on-policy, it is natural that a detour around the cliff is taken (due to the positive ϵ). However, there are also patterns that obviously have no rational basis.
Despite the appealing intuition, the variance problem really hampers MC-RL in quickly identifying good solutions. If anything, these results illustrate why temporal difference learning methods have become the standard in value-based Reinforcement Learning.
Takeaways
Monte Carlo Reinforcement Learning (or TD(1), double pass) updates value functions based on the full reward trajectory observed.
Compared to temporal difference learning methods such as Q-learning and SARSA, MC-RL is unbiased, i.e., value updates are not affected by incorrect prior estimates of value functions.
MC-RL typically takes longer to converge than temporal difference learning, due to the high variance of reward trajectories.
_The full code of the Monte Carlo Reinforcement Learning algorithm can be found on my GitHub repository._
Also check out my other articles in this series!
Q-learning and SARSA:
Walking Off The Cliff With Off-Policy Reinforcement Learning
Discrete policy gradient:
Cliff-Walking Problem With The Discrete Policy Gradient Algorithm
Deep policy gradient:
Deep Q-learning:
A Minimal Working Example for Deep Q-Learning in TensorFlow 2.0
References
Powell, W. B. (2007). Approximate Dynamic Programming: Solving the curses of dimensionality (Vol. 703). John Wiley & Sons.
Sutton, R. S., & Barto, A. G. (2018). Reinforcement learning: An introduction. MIT Press.
